pit: Clean up tree traversals

8 files changed, 89 insertions, 19 deletions

diff --git a/pit/include/lcq/pit.h b/pit/include/lcq/pit.h
index 8ff46c8..3afce9f 100644
--- a/pit/include/lcq/pit.h
+++ b/pit/include/lcq/pit.h
@@ -1,7 +1,7 @@
 #ifndef LCOLONQ_PIT_H
 #define LCOLONQ_PIT_H
 
-#include <lcq/prelude.h>
+#include <lcq/pit/types.h>
 #include <lcq/pit/utils.h>
 #include <lcq/pit/lexer.h>
 #include <lcq/pit/parser.h>
diff --git a/pit/include/lcq/pit/arena.h b/pit/include/lcq/pit/arena.h
index 18d7f96..fcaca55 100644
--- a/pit/include/lcq/pit/arena.h
+++ b/pit/include/lcq/pit/arena.h
@@ -1,7 +1,7 @@
 #ifndef LCOLONQ_PIT_ARENA_H
 #define LCOLONQ_PIT_ARENA_H
 
-#include <lcq/prelude.h>
+#include <lcq/pit/types.h>
 
 typedef i64 pit_arena_index;
 
diff --git a/pit/include/lcq/pit/lexer.h b/pit/include/lcq/pit/lexer.h
index d10d9c2..db452e7 100644
--- a/pit/include/lcq/pit/lexer.h
+++ b/pit/include/lcq/pit/lexer.h
@@ -1,7 +1,7 @@
 #ifndef LCOLONQ_PIT_LEXER_H
 #define LCOLONQ_PIT_LEXER_H
 
-#include <lcq/prelude.h>
+#include <lcq/pit/types.h>
 
 typedef enum {
     PIT_LEX_TOKEN_ERROR=-1,
diff --git a/pit/include/lcq/pit/runtime.h b/pit/include/lcq/pit/runtime.h
index d9311b2..d981447 100644
--- a/pit/include/lcq/pit/runtime.h
+++ b/pit/include/lcq/pit/runtime.h
@@ -1,7 +1,7 @@
 #ifndef LCOLONQ_PIT_RUNTIME_H
 #define LCOLONQ_PIT_RUNTIME_H
 
-#include <lcq/prelude.h>
+#include <lcq/pit/types.h>
 #include <lcq/pit/utils.h>
 #include <lcq/pit/vec.h>
 #include <lcq/pit/arena.h>
@@ -35,20 +35,23 @@ PIT_DECLARE_VEC(pit_annotated_ref)
 void pit_annotation_set(struct pit_runtime *rt, pit_ref ref, pit_annotation annotation);
 pit_annotated_ref *pit_annotation_get(struct pit_runtime *rt, pit_ref ref);
 
-/* "programs"; vectors of "instructions" for a very simple VM used by the evaluator */
+/* entries on a stack used when traversing trees of values */
 typedef struct {
     enum {
-        PIT_RUNTIME_EVAL_INS_LITERAL,
-        PIT_RUNTIME_EVAL_INS_APPLY
+        PIT_TRAVERSAL_ENTRY_VALUE,
+        PIT_TRAVERSAL_ENTRY_DUMP_STRING,
+        PIT_TRAVERSAL_ENTRY_APPLICATION,
     } sort;
     union {
-        pit_value literal;
-        struct { i64 arity; pit_annotated_ref *annotation; } apply; 
+        pit_value value;
+        char *dump_string;
+        struct { i64 arity; pit_annotated_ref *annotation; } application; 
     } in;
-} pit_runtime_eval_ins;
-PIT_DECLARE_VEC(pit_runtime_eval_ins)
-void pit_runtime_eval_program_push_literal(struct pit_runtime *rt, pit_vec(pit_runtime_eval_ins) *s, pit_value x);
-void pit_runtime_eval_program_push_apply(struct pit_runtime *rt, pit_vec(pit_runtime_eval_ins) *s, i64 arity, pit_annotated_ref *annotation);
+} pit_traversal_entry;
+PIT_DECLARE_VEC(pit_traversal_entry)
+void pit_traversal_push_value(struct pit_runtime *rt, pit_vec(pit_traversal_entry) *s, pit_value x);
+void pit_traversal_push_dump_string(struct pit_runtime *rt, pit_vec(pit_traversal_entry) *s, char *m);
+void pit_traversal_push_application(struct pit_runtime *rt, pit_vec(pit_traversal_entry) *s, i64 arity, pit_annotated_ref *annotation);
 
 typedef struct pit_runtime {
     /* interpreter state */
@@ -58,12 +61,12 @@ typedef struct pit_runtime {
     pit_arena *backbuffer; /* additional allocation, the same size as the heap (used by GC) */
     pit_vec(pit_annotated_ref) *annotations;
     pit_vec(pit_annotated_ref) *backtrace; /* we reuse this vector for both backtraces and the GC */
-    pit_vec(pit_symtab_entry) *symtab;/* all symbols */
+    pit_vec(pit_symtab_entry) *symtab; /* all symbols */
     /* temporary/"scratch" memory */
     pit_vec(pit_value) *saved_bindings; /* stack used to save old values of bindings to be restored ("shallow binding") */
     pit_vec(pit_value) *expr_stack; /* stack of subexpressions to evaluate during evaluation */
     pit_vec(pit_value) *result_stack; /* stack of intermediate values during evaluation */
-    pit_vec(pit_runtime_eval_ins) *program; /* intermediate stack-based program constructed during evaluation */
+    pit_vec(pit_traversal_entry) *traversal; /* intermediate stack used during tree traversal */
     /* bookkeeping */
     /* "frozen" values offsets: values before these offsets are immutable, and we can reset here later */
     i64 frozen_values, frozen_symtab;
diff --git a/pit/include/lcq/pit/runtime/value.h b/pit/include/lcq/pit/runtime/value.h
index 5820bbd..fa59a46 100644
--- a/pit/include/lcq/pit/runtime/value.h
+++ b/pit/include/lcq/pit/runtime/value.h
@@ -1,7 +1,7 @@
 #ifndef LCOLONQ_PIT_RUNTIME_VALUE_H
 #define LCOLONQ_PIT_RUNTIME_VALUE_H
 
-#include <lcq/prelude.h>
+#include <lcq/pit/types.h>
 #include <lcq/pit/runtime.h>
 
 /* the basic value type - it's just a u64 */
diff --git a/pit/include/lcq/pit/types.h b/pit/include/lcq/pit/types.h
new file mode 100644
index 0000000..23a1a90
--- /dev/null
+++ b/pit/include/lcq/pit/types.h
@@ -0,0 +1,6 @@
+#ifndef LCOLONQ_PIT_TYPES_H
+#define LCOLONQ_PIT_TYPES_H
+
+#include <lcq/prelude.h>
+
+#endif
diff --git a/pit/include/lcq/pit/utils.h b/pit/include/lcq/pit/utils.h
index 4bea479..6769310 100644
--- a/pit/include/lcq/pit/utils.h
+++ b/pit/include/lcq/pit/utils.h
@@ -2,8 +2,7 @@
 #define LCOLONQ_PIT_UTILS_H
 
 #include <stdarg.h>
-#include <stddef.h>
-#include <lcq/prelude.h>
+#include <lcq/pit/types.h>
 
 /* macro helpers */
 #define PIT_CONCAT(a, b) a ## b
@@ -35,5 +34,6 @@ int pit_libc_string_snprintf(char *buf, size_t len, char *format, ...);
 
 /* assorted utilities and debugging tools */
 #define pit_mul(result, a, b) *result = (i64) (a) * (i64) (b)
+static inline i64 pit_mod(i64 x, i64 m) { return (m + (x % m)) % m; }
 
 #endif
diff --git a/pit/include/lcq/pit/vec.h b/pit/include/lcq/pit/vec.h
index 82276f1..e1f7ab4 100644
--- a/pit/include/lcq/pit/vec.h
+++ b/pit/include/lcq/pit/vec.h
@@ -1,7 +1,7 @@
 #ifndef LCOLONQ_PIT_VEC_H
 #define LCOLONQ_PIT_VEC_H
 
-#include <lcq/prelude.h>
+#include <lcq/pit/types.h>
 #include <lcq/pit/utils.h>
 
 #define pit_vec(ty) pit_vec__ ## ty ## __type
@@ -49,4 +49,65 @@
         return --s->next; \
     }
 
+#define pit_deque(ty) pit_deque__ ## ty ## __type
+#define pit_deque_new(ty) pit_deque__ ## ty ## __new
+#define pit_deque_get(ty) pit_deque__ ## ty ## __get
+#define pit_deque_reset(ty) pit_deque__ ## ty ## __reset
+#define pit_deque_push_front(ty) pit_deque__ ## ty ## __push_front
+#define pit_deque_push_back(ty) pit_deque__ ## ty ## __push_back
+#define pit_deque_pop_front(ty) pit_deque__ ## ty ## __pop_front
+#define pit_deque_pop_back(ty) pit_deque__ ## ty ## __pop_back
+
+#define PIT_DECLARE_DEQUE(ty) \
+    typedef struct { \
+        i64 capacity, head, len; \
+        ty data[]; \
+    } pit_deque(ty); \
+    static __attribute__ ((unused)) pit_deque(ty) *pit_deque_new(ty)(u8 *buf, i64 buf_len) { \
+        uintptr_t base = (uintptr_t) buf; \
+        uintptr_t aligned = pit_align_up(base, sizeof(void *)); \
+        pit_deque(ty) *ret = (pit_deque(ty) *) aligned; \
+        uintptr_t data = aligned + (i64) sizeof(pit_deque(ty)); \
+        i64 offset = (i64) data - (i64) base; \
+        i64 remaining = (i64) (buf_len - offset); \
+        ret->head = 0; \
+        ret->len = 0; \
+        ret->capacity = remaining / (i64) sizeof(ty); \
+        return ret; \
+    } \
+    static __attribute__ ((unused)) ty *pit_deque_get(ty)(pit_deque(ty) *s, i64 i) { \
+        if (i > s->len) return NULL; \
+        i64 idx = pit_mod(s->head + i, s->capacity); \
+        return &s->data[idx]; \
+    } \
+    static __attribute__ ((unused)) i64 pit_deque_push_front(ty)(pit_deque(ty) *s, ty v) { \
+        if (s->len + 1 > s->capacity) return -1; \
+        s->len += 1; \
+        s->head = pit_mod(s->head - 1, s->capacity); \
+        s->data[s->head] = v; \
+        return s->head; \
+    } \
+    static __attribute__ ((unused)) i64 pit_deque_push_back(ty)(pit_deque(ty) *s, ty v) { \
+        if (s->len + 1 > s->capacity) return -1; \
+        i64 idx = pit_mod(s->head + s->len, s->capacity); \
+        s->data[idx] = v; \
+        s->len += 1; \
+        return idx; \
+    } \
+    static __attribute__ ((unused)) i64 pit_deque_pop_front(ty)(pit_deque(ty) *s, ty *v) { \
+        if (s->len == 0) return -1; \
+        i64 idx = s->head; \
+        *v = s->data[s->head]; \
+        s->head = pit_mod(s->head + 1, s->capacity); \
+        s->len -= 1; \
+        return idx; \
+    } \
+    static __attribute__ ((unused)) i64 pit_deque_pop_back(ty)(pit_deque(ty) *s, ty *v) { \
+        if (s->len == 0) return -1; \
+        i64 idx = pit_mod(s->head + s->len - 1, s->capacity); \
+        *v = s->data[idx]; \
+        s->len -= 1; \
+        return idx; \
+    }
+
 #endif