pit: Clean up tree traversals

3 files changed, 168 insertions, 125 deletions

diff --git a/pit/src/runtime/dump.c b/pit/src/runtime/dump.c
index 3d5ec9c..3c1cf13 100644
--- a/pit/src/runtime/dump.c
+++ b/pit/src/runtime/dump.c
@@ -1,100 +1,143 @@
 #include <lcq/pit/runtime/dump.h>
 
-#define CHECK_BUF if (buf >= end) { return buf - start; }
-#define CHECK_BUF_LABEL(label) if (buf >= end) { goto label; }
-i64 pit_dump(pit_runtime *rt, char *buf, i64 len, pit_value v, bool readable) {
+typedef bool (*pit_dump_callback)(char *buf, i64 len, void *data);
+i64 pit_dump_with_callback(
+    pit_runtime *rt, char *start, i64 buf_len, pit_value top, bool readable,
+    pit_dump_callback cb, void *data
+) {
+    i64 traversal_reset = rt->traversal->next;
+    char *buf = start;
+    char *end = start + buf_len;
     pit_value_heavy *h = NULL;
-    if (len <= 0) return 0;
-    switch (pit_value_sort(v)) {
-    case PIT_VALUE_SORT_DOUBLE:
-        #ifndef PIT_NO_DOUBLE
-        return pit_libc_string_snprintf(buf, (size_t) len, "%lf", pit_value_as_double(rt, v));
-        #else
-        return pit_string_snprintf(buf, (size_t) len, "<unsupported double>");
-        #endif
-    case PIT_VALUE_SORT_INTEGER:
-        return pit_libc_string_snprintf(buf, (size_t) len, "%ld", pit_value_as_integer(rt, v));
-    case PIT_VALUE_SORT_SYMBOL: {
-        pit_symtab_entry *ent = pit_symtab_lookup(rt, v);
-        if (ent
-            && pit_value_sort(ent->name) == PIT_VALUE_SORT_REF
-            && (h = pit_value_ref_deref(rt, pit_value_as_ref(rt, ent->name)))
-        ) {
-            i64 i = 0;
-            for (; i < h->in.bytes.len && i < len - 1; ++i) {
-                buf[i] = (char) h->in.bytes.data[i];
-            }
-            return i;
-        } else {
-            return pit_libc_string_snprintf(buf, (size_t) len, "<broken symbol %ld>", pit_value_as_symbol(rt, v));
+    pit_traversal_push_value(rt, rt->traversal, top);
+    while (rt->traversal->next > traversal_reset) {
+        pit_traversal_entry ent;
+        i64 len = (i64) (end - buf);
+        if (rt->error != PIT_NIL) goto end;
+        if (pit_vec_pop(pit_traversal_entry)(rt->traversal, &ent) < 0)
+            pit_error(rt, "dump stack underflow");
+        if (rt->error != PIT_NIL) goto end;
+        switch (ent.sort) {
+        case PIT_TRAVERSAL_ENTRY_DUMP_STRING: {
+            for (char *s = ent.in.dump_string; *s != 0 && buf < end; ++s) *(buf++) = *s;
+            break;
         }
-    }
-    case PIT_VALUE_SORT_REF: {
-        pit_ref r = pit_value_as_ref(rt, v);
-        char *end = buf + len;
-        char *start = buf;
-        h = pit_value_ref_deref(rt, r);
-        if (!h) pit_libc_string_snprintf(buf, (size_t) len, "<ref %ld>", r);
-        else {
-            switch (h->hsort) {
-            case PIT_VALUE_HEAVY_SORT_CELL: {
-                CHECK_BUF; *(buf++) = '{';
-                CHECK_BUF; buf += pit_dump(rt, buf, end - buf, pit_value_cons_car(rt, h->in.cell), readable);
-                CHECK_BUF; *(buf++) = '}';
-                return buf - start;
-            }
-            case PIT_VALUE_HEAVY_SORT_CONS: {
-                pit_value cur = v;
-                CHECK_BUF_LABEL(list_end);
-                do {
-                    if (pit_value_is_cons(rt, cur)) {
-                        CHECK_BUF_LABEL(list_end); *(buf++) = ' ';
-                        CHECK_BUF_LABEL(list_end); buf += pit_dump(rt, buf, end - buf, pit_value_cons_car(rt, cur), readable);
-                    } else {
-                        CHECK_BUF_LABEL(list_end); buf += pit_libc_string_snprintf(buf, (size_t) (end - buf), " . ");
-                        CHECK_BUF_LABEL(list_end); buf += pit_dump(rt, buf, end - buf, cur, readable);
+        case PIT_TRAVERSAL_ENTRY_VALUE: {
+            pit_value v = ent.in.value;
+            switch (pit_value_sort(v)) {
+            case PIT_VALUE_SORT_DOUBLE:
+#ifndef PIT_NO_DOUBLE
+                buf += pit_libc_string_snprintf(buf, (size_t) len, "%lf", pit_value_as_double(rt, v));
+#else
+                buf += pit_string_snprintf(buf, (size_t) len, "<unsupported double>");
+#endif
+                break;
+            case PIT_VALUE_SORT_INTEGER:
+                buf += pit_libc_string_snprintf(buf, (size_t) len, "%ld", pit_value_as_integer(rt, v));
+                break;
+            case PIT_VALUE_SORT_SYMBOL: {
+                pit_symtab_entry *se = pit_symtab_lookup(rt, v);
+                if (se
+                    && pit_value_sort(se->name) == PIT_VALUE_SORT_REF
+                    && (h = pit_value_ref_deref(rt, pit_value_as_ref(rt, se->name)))
+                ) {
+                    i64 i = 0;
+                    for (; i < h->in.bytes.len && i < len - 1; ++i) {
+                        buf[i] = (char) h->in.bytes.data[i];
                     }
-                } while (!pit_value_eq((cur = pit_value_cons_cdr(rt, cur)), PIT_NIL));
-                CHECK_BUF_LABEL(list_end); *(buf++) = ')';
-                list_end:
-                *start = '(';
-                return buf - start;
-            }
-            case PIT_VALUE_HEAVY_SORT_ARRAY: {
-                i64 i = 0;
-                CHECK_BUF_LABEL(array_end);
-                if (h->in.array.len == 0) {
-                    CHECK_BUF_LABEL(array_end); *(buf++) = '[';
-                } else for (; i < h->in.array.len; ++i) {
-                    CHECK_BUF_LABEL(array_end); *(buf++) = ' ';
-                    CHECK_BUF_LABEL(array_end); buf += pit_dump(rt, buf, end - buf, h->in.array.data[i], readable);
+                    buf += i;
+                } else {
+                    buf += pit_libc_string_snprintf(buf, (size_t) len, "<broken symbol %ld>", pit_value_as_symbol(rt, v));
                 }
-                CHECK_BUF_LABEL(array_end); *(buf++) = ']';
-                array_end:
-                *start = '[';
-                return buf - start;
+                break;
             }
-            case PIT_VALUE_HEAVY_SORT_BYTES: {
-                i64 i = 0;
-                if (readable) { CHECK_BUF; buf[i++] = '"'; }
-                i64 maxlen = len - i;
-                for (i64 j = 0; i < maxlen && j < h->in.bytes.len;) {
-                    if (buf[i - 1] != '\\' && (h->in.bytes.data[j] == '\\' || h->in.bytes.data[j] == '"')) {
-                        CHECK_BUF; buf[i++] = '\\';
+            case PIT_VALUE_SORT_REF: {
+                pit_ref r = pit_value_as_ref(rt, v);
+                h = pit_value_ref_deref(rt, r);
+                if (!h) pit_libc_string_snprintf(buf, (size_t) len, "<ref %ld>", r);
+                else {
+                    switch (h->hsort) {
+                    case PIT_VALUE_HEAVY_SORT_CELL: {
+                        pit_traversal_push_dump_string(rt, rt->traversal, "}");
+                        pit_traversal_push_value(rt, rt->traversal, h->in.cell);
+                        pit_traversal_push_dump_string(rt, rt->traversal, "{");
+                        break;
+                    }
+                    case PIT_VALUE_HEAVY_SORT_CONS: {
+                        i64 expr_stack_reset = rt->expr_stack->next;
+                        pit_value xs = v;
+                        bool first = true;
+                        while (xs != PIT_NIL && pit_value_is_cons(rt, xs)) {
+                            if (pit_vec_push(pit_value)(rt->expr_stack, pit_value_cons_car(rt, xs)) < 0) {
+                                pit_error(rt, "dump expr stack overflow");
+                                goto end;
+                            }
+                            xs = pit_value_cons_cdr(rt, xs);
+                        }
+                        pit_traversal_push_dump_string(rt, rt->traversal, ")");
+                        if (xs != PIT_NIL) {
+                            pit_traversal_push_value(rt, rt->traversal, xs);
+                            pit_traversal_push_dump_string(rt, rt->traversal, " . ");
+                        }
+                        while (rt->expr_stack->next > expr_stack_reset) {
+                            if (first) first = false;
+                            else pit_traversal_push_dump_string(rt, rt->traversal, " ");
+                            pit_value x = PIT_NIL;
+                            if (pit_vec_pop(pit_value)(rt->expr_stack, &x) < 0) {
+                                pit_error(rt, "dump expr stack underflow");
+                                goto end;
+                            }
+                            pit_traversal_push_value(rt, rt->traversal, x);
+                        }
+                        pit_traversal_push_dump_string(rt, rt->traversal, "(");
+                        rt->expr_stack->next = expr_stack_reset;
+                        break;
+                    }
+                    case PIT_VALUE_HEAVY_SORT_ARRAY: {
+                        bool first = true;
+                        pit_traversal_push_dump_string(rt, rt->traversal, "]");
+                        for (i64 i = h->in.array.len - 1; i >= 0; --i) {
+                            if (first) first = false;
+                            else pit_traversal_push_dump_string(rt, rt->traversal, " ");
+                            pit_traversal_push_value(rt, rt->traversal, h->in.array.data[i]);
+                        }
+                        pit_traversal_push_dump_string(rt, rt->traversal, "[");
+                        break;
                     }
-                    else {
-                        CHECK_BUF; buf[i++] = (char) h->in.bytes.data[j++];
+                    case PIT_VALUE_HEAVY_SORT_BYTES: {
+                        i64 i = 0;
+                        if (readable) { buf[i++] = '"'; }
+                        i64 maxlen = len - i;
+                        for (i64 j = 0; i < maxlen && j < h->in.bytes.len;) {
+                            if (buf[i - 1] != '\\' && (h->in.bytes.data[j] == '\\' || h->in.bytes.data[j] == '"')) {
+                                buf[i++] = '\\';
+                            }
+                            else {
+                                buf[i++] = (char) h->in.bytes.data[j++];
+                            }
+                        }
+                        if (readable && i < len - 1) buf[i++] = '"';
+                        buf += i;
+                        break;
+                    }
+                    default:
+                        buf += pit_libc_string_snprintf(buf, (size_t) len, "<ref %ld>", r);
                     }
                 }
-                if (readable && i < len - 1) buf[i++] = '"';
-                return i;
+                break;
             }
-            default:
-                return pit_libc_string_snprintf(buf, (size_t) len, "<ref %ld>", r);
             }
+            break;
+        }
+        default:
+            pit_error(rt, "unexpected traversal entry"); goto end;
         }
-        break;
-    }
     }
-    return 0;
+end:
+    rt->traversal->next = traversal_reset;
+    return (i64) (buf - start);
+}
+
+i64 pit_dump(pit_runtime *rt, char *buf, i64 len, pit_value v, bool readable) {
+    return pit_dump_with_callback(rt, buf, len, v, readable, NULL, NULL);
 }
diff --git a/pit/src/runtime/eval.c b/pit/src/runtime/eval.c
index f5eba97..301d8d0 100644
--- a/pit/src/runtime/eval.c
+++ b/pit/src/runtime/eval.c
@@ -3,11 +3,11 @@
 pit_value pit_eval(pit_runtime *rt, pit_value top) {
     i64 expr_stack_reset = rt->expr_stack->next;
     i64 result_stack_reset = rt->result_stack->next;
-    i64 program_reset = rt->program->next;
+    i64 traversal_reset = rt->traversal->next;
     // pit_vec_reset(pit_annotated_ref)(rt->backtrace);
     if (pit_vec_push(pit_value)(rt->expr_stack, top) < 0)
         pit_error(rt, "evaluation stack overflow");
-    /* first, convert the expression tree into "polish notation" in program */
+    /* first, convert the expression tree into "polish notation" in traversal */
     while (rt->expr_stack->next > expr_stack_reset) {
         pit_value cur = PIT_NIL;
         if (rt->error != PIT_NIL) goto end;
@@ -42,56 +42,56 @@ pit_value pit_eval(pit_runtime *rt, pit_value top) {
                     if (pit_vec_push(pit_value)(rt->expr_stack, fsym) < 0)
                         pit_error(rt, "evaluation stack overflow");
                 }
-                pit_runtime_eval_program_push_apply(rt, rt->program, argcount, ann);
+                pit_traversal_push_application(rt, rt->traversal, argcount, ann);
                 if (is_symbol) {
                     pit_value f = pit_symtab_fget(rt, fsym);
-                    pit_runtime_eval_program_push_literal(rt, rt->program, f);
+                    pit_traversal_push_value(rt, rt->traversal, f);
                 }
             }
         } else if (pit_value_is_symbol(rt, cur)) { /* unquoted symbols: variable lookup */
             pit_symtab_entry *ent = pit_symtab_lookup(rt, cur);
             if (ent->is_keyword) {
-                pit_runtime_eval_program_push_literal(rt, rt->program, cur);
+                pit_traversal_push_value(rt, rt->traversal, cur);
             } else {
-                pit_runtime_eval_program_push_literal(rt, rt->program, pit_symtab_get(rt, cur));
+                pit_traversal_push_value(rt, rt->traversal, pit_symtab_get(rt, cur));
             }
         } else { /* other expressions evaluate to themselves! */
-            pit_runtime_eval_program_push_literal(rt, rt->program, cur);
+            pit_traversal_push_value(rt, rt->traversal, cur);
         }
     }
-    /* then, execute the polish notation program from right to left
+    /* then, execute the polish notation traversal from right to left
        this has the nice consequence of putting the arguments in the right order */
-    for (i64 idx = rt->program->next - 1; idx >= program_reset; --idx) {
-        pit_runtime_eval_ins *ent = pit_vec_get(pit_runtime_eval_ins)(rt->program, idx);
-        if (ent == NULL) pit_error(rt, "evaluation program invalid");
+    for (i64 idx = rt->traversal->next - 1; idx >= traversal_reset; --idx) {
+        pit_traversal_entry *ent = pit_vec_get(pit_traversal_entry)(rt->traversal, idx);
+        if (ent == NULL) pit_error(rt, "evaluation traversal invalid");
         if (rt->error != PIT_NIL) goto end;
         switch (ent->sort) {
-        case PIT_RUNTIME_EVAL_INS_LITERAL:
-            if (pit_vec_push(pit_value)(rt->result_stack, ent->in.literal) < 0)
+        case PIT_TRAVERSAL_ENTRY_VALUE:
+            if (pit_vec_push(pit_value)(rt->result_stack, ent->in.value) < 0)
                 pit_error(rt, "evaluation result stack overflow");
             break;
-        case PIT_RUNTIME_EVAL_INS_APPLY: {
+        case PIT_TRAVERSAL_ENTRY_APPLICATION: {
             pit_value f = PIT_NIL;
             pit_value args = PIT_NIL;
             if (pit_vec_pop(pit_value)(rt->result_stack, &f) < 0)
                 pit_error(rt, "evaluation result stack underflow");
-            for (i64 i = 0; i < ent->in.apply.arity; ++i) {
+            for (i64 i = 0; i < ent->in.application.arity; ++i) {
                 pit_value a = PIT_NIL;
                 if (pit_vec_pop(pit_value)(rt->result_stack, &a) < 0)
                     pit_error(rt, "evaluation result stack underflow");
                 args = pit_value_cons(rt, a, args);
             }
-            if (ent->in.apply.annotation != NULL) {
-                rt->source_line = ent->in.apply.annotation->annotation.line;
-                rt->source_column = ent->in.apply.annotation->annotation.column;
-                pit_vec_push(pit_annotated_ref)(rt->backtrace, *ent->in.apply.annotation);
+            if (ent->in.application.annotation != NULL) {
+                rt->source_line = ent->in.application.annotation->annotation.line;
+                rt->source_column = ent->in.application.annotation->annotation.column;
+                pit_vec_push(pit_annotated_ref)(rt->backtrace, *ent->in.application.annotation);
             }
             if (pit_vec_push(pit_value)(rt->result_stack, pit_value_apply(rt, f, args)) < 0)
                 pit_error(rt, "evaluation result stack underflow");
             break;
         }
         default:
-            pit_error(rt, "unknown program entry");
+            pit_error(rt, "unknown traversal entry");
             goto end;
         }
     }
@@ -101,7 +101,7 @@ end: {
             pit_error(rt, "evaluation result stack underflow");
         rt->expr_stack->next = expr_stack_reset;
         rt->result_stack->next = result_stack_reset;
-        rt->program->next = program_reset;
+        rt->traversal->next = traversal_reset;
         return ret;
     }
 }
diff --git a/pit/src/runtime/macroexpand.c b/pit/src/runtime/macroexpand.c
index 13a4fdd..6252ae1 100644
--- a/pit/src/runtime/macroexpand.c
+++ b/pit/src/runtime/macroexpand.c
@@ -3,7 +3,7 @@
 pit_value pit_macroexpand(pit_runtime *rt, pit_value top) {
     i64 expr_stack_reset = rt->expr_stack->next;
     i64 result_stack_reset = rt->result_stack->next;
-    i64 program_reset = rt->program->next;
+    i64 traversal_reset = rt->traversal->next;
     if (pit_vec_push(pit_value)(rt->expr_stack, top) < 0)
         pit_error(rt, "macro expansion stack overflow");
     while (rt->expr_stack->next > expr_stack_reset) {
@@ -23,9 +23,9 @@ pit_value pit_macroexpand(pit_runtime *rt, pit_value top) {
                     pit_error(rt, "macro expansion stack overflow");
             } else if (is_symbol && pit_symtab_symbol_name_match_cstr(rt, fsym, "defer")) {
                 pit_value args = pit_value_cons_cdr(rt, cur);
-                pit_runtime_eval_program_push_literal(rt, rt->program, pit_value_cons_car(rt, args));
+                pit_traversal_push_value(rt, rt->traversal, pit_value_cons_car(rt, args));
             } else if (is_symbol && pit_symtab_symbol_name_match_cstr(rt, fsym, "quote")) {
-                pit_runtime_eval_program_push_literal(rt, rt->program, cur);
+                pit_traversal_push_value(rt, rt->traversal, cur);
             } else if (is_symbol && pit_symtab_symbol_name_match_cstr(rt, fsym, "lambda")) {
                 pit_value args = pit_value_cons_cdr(rt, cur);
                 pit_value bindings = pit_value_cons_car(rt, args);
@@ -40,8 +40,8 @@ pit_value pit_macroexpand(pit_runtime *rt, pit_value top) {
                     body = pit_value_cons_cdr(rt, body);
                     argcount += 1;
                 }
-                pit_runtime_eval_program_push_apply(rt, rt->program, argcount + 1, ann);
-                pit_runtime_eval_program_push_literal(rt, rt->program, fsym);
+                pit_traversal_push_application(rt, rt->traversal, argcount + 1, ann);
+                pit_traversal_push_value(rt, rt->traversal, fsym);
             } else {
                 pit_value args = pit_value_cons_cdr(rt, cur);
                 i64 argcount = 0;
@@ -56,46 +56,46 @@ pit_value pit_macroexpand(pit_runtime *rt, pit_value top) {
                     if (pit_vec_push(pit_value)(rt->expr_stack, fsym) < 0)
                         pit_error(rt, "macro expansion stack overflow");
                 }
-                pit_runtime_eval_program_push_apply(rt, rt->program, argcount, ann);
+                pit_traversal_push_application(rt, rt->traversal, argcount, ann);
                 if (is_symbol) {
-                    pit_runtime_eval_program_push_literal(rt, rt->program, fsym);
+                    pit_traversal_push_value(rt, rt->traversal, fsym);
                 }
             }
         } else {
-            pit_runtime_eval_program_push_literal(rt, rt->program, cur);
+            pit_traversal_push_value(rt, rt->traversal, cur);
         }
     }
-    for (i64 idx = rt->program->next - 1; idx >= program_reset; --idx) {
-        pit_runtime_eval_ins *ent = pit_vec_get(pit_runtime_eval_ins)(rt->program, idx);
-        if (ent == NULL) pit_error(rt, "macro expansion program invalid");
+    for (i64 idx = rt->traversal->next - 1; idx >= traversal_reset; --idx) {
+        pit_traversal_entry *ent = pit_vec_get(pit_traversal_entry)(rt->traversal, idx);
+        if (ent == NULL) pit_error(rt, "macro expansion traversal invalid");
         if (rt->error != PIT_NIL) goto end;
         switch (ent->sort) {
-        case PIT_RUNTIME_EVAL_INS_LITERAL:
-            if (pit_vec_push(pit_value)(rt->result_stack, ent->in.literal) < 0)
+        case PIT_TRAVERSAL_ENTRY_VALUE:
+            if (pit_vec_push(pit_value)(rt->result_stack, ent->in.value) < 0)
                 pit_error(rt, "macro expansion stack overflow");
             break;
-        case PIT_RUNTIME_EVAL_INS_APPLY: {
+        case PIT_TRAVERSAL_ENTRY_APPLICATION: {
             pit_value f = PIT_NIL;
             pit_value args = PIT_NIL;
             pit_value app = PIT_NIL;
             if (pit_vec_pop(pit_value)(rt->result_stack, &f) < 0)
                 pit_error(rt, "macro expansion stack underflow");
-            for (i64 i = 0; i < ent->in.apply.arity; ++i) {
+            for (i64 i = 0; i < ent->in.application.arity; ++i) {
                 pit_value a;
                 if (pit_vec_pop(pit_value)(rt->result_stack, &a) < 0)
                     pit_error(rt, "macro expansion stack underflow");
                 args = pit_value_cons(rt, a, args);
             }
             app = pit_value_cons(rt, f, args);
-            if (ent->in.apply.annotation != NULL) {
-                pit_annotation_set(rt, pit_value_as_ref(rt, app), ent->in.apply.annotation->annotation);
+            if (ent->in.application.annotation != NULL) {
+                pit_annotation_set(rt, pit_value_as_ref(rt, app), ent->in.application.annotation->annotation);
             }
             if (pit_vec_push(pit_value)(rt->result_stack, app) < 0)
                 pit_error(rt, "macro expansion stack overflow");
             break;
         }
         default:
-            pit_error(rt, "unknown program entry");
+            pit_error(rt, "unknown traversal entry");
             goto end;
         }
     }
@@ -105,7 +105,7 @@ end: {
             pit_error(rt, "macro expansion stack underflow");
         rt->expr_stack->next = expr_stack_reset;
         rt->result_stack->next = result_stack_reset;
-        rt->program->next = program_reset;
+        rt->traversal->next = traversal_reset;
         return ret;
     }
 }