pit: Hash table annotations, better dumper

12 files changed, 201 insertions, 96 deletions

diff --git a/pit/.dir-locals.el b/pit/.dir-locals.el
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/pit/.dir-locals.el
diff --git a/pit/include/lcq/pit/runtime.h b/pit/include/lcq/pit/runtime.h
index d981447..b9143cf 100644
--- a/pit/include/lcq/pit/runtime.h
+++ b/pit/include/lcq/pit/runtime.h
@@ -27,13 +27,9 @@ PIT_DECLARE_VEC(pit_symtab_entry)
 typedef struct {
     i64 line, column;
 } pit_annotation;
-typedef struct {
-    pit_ref ref;
-    pit_annotation annotation;
-} pit_annotated_ref;
-PIT_DECLARE_VEC(pit_annotated_ref)
+PIT_DECLARE_HASHTABLE(pit_ref, pit_annotation)
 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);
+pit_annotation *pit_annotation_get(struct pit_runtime *rt, pit_ref ref);
 
 /* entries on a stack used when traversing trees of values */
 typedef struct {
@@ -45,13 +41,13 @@ typedef struct {
     union {
         pit_value value;
         char *dump_string;
-        struct { i64 arity; pit_annotated_ref *annotation; } application; 
+        struct { i64 arity; pit_annotation *annotation; } application; 
     } in;
 } 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);
+void pit_traversal_push_application(struct pit_runtime *rt, pit_vec(pit_traversal_entry) *s, i64 arity, pit_annotation *annotation);
 
 typedef struct pit_runtime {
     /* interpreter state */
@@ -59,8 +55,8 @@ typedef struct pit_runtime {
     /* bytestrings and arrays are allocated at the end (descending), heavy values are allocated at the front */
     /* this allows us to iterate over only heavy values at the front (useful in Cheney's algorithm for GC */
     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_hashtable(pit_ref, pit_annotation) *annotations;
+    pit_hashtable(pit_ref, pit_annotation) *annotations_backbuffer;
     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") */
diff --git a/pit/include/lcq/pit/runtime/dump.h b/pit/include/lcq/pit/runtime/dump.h
index 581cba0..2aeba2f 100644
--- a/pit/include/lcq/pit/runtime/dump.h
+++ b/pit/include/lcq/pit/runtime/dump.h
@@ -3,8 +3,15 @@
 
 #include <lcq/pit/runtime.h>
 
+typedef i64 (*pit_dump_callback)(u8 *buf, i64 len, void *data);
+
+void pit_dump_with_callback(pit_runtime *rt, pit_value top, bool readable, pit_dump_callback write, void *data);
+
 /* pretty-print a pit value
    if readable is true, try to produce output that can be machine-read (quotes on strings, etc) */
 i64 pit_dump(pit_runtime *rt, char *buf, i64 len, pit_value v, bool readable);
 
+i64 pit_dump_to_stdout(pit_runtime *rt, char *buf, i64 len, pit_value v, bool readable);
+void pit_dump_to_file(pit_runtime *rt, void *vf, pit_value v, bool readable);
+
 #endif
diff --git a/pit/include/lcq/pit/utils.h b/pit/include/lcq/pit/utils.h
index 6769310..929472a 100644
--- a/pit/include/lcq/pit/utils.h
+++ b/pit/include/lcq/pit/utils.h
@@ -24,6 +24,21 @@ static inline size_t pit_libc_string_strlen(char *s) {
     while (s[idx] != 0) ++idx;
     return idx;
 }
+static inline u64 pit_string_hash(char *x) {
+    if (x == NULL) return 0;
+    u64 ret = 0;
+    while (*x != 0) {
+        u64 new = (ret << 6) + (ret << 16) - ret;
+        ret = (u64) *x++ + (u64) new;
+    }
+    return ret;
+}
+static inline bool pit_string_equal(char *x, char *y) {
+    if (x == NULL && y == NULL) return true;
+    if (x == NULL || y == NULL) return false;
+    while (*x != 0 && *y != 0) if (*x++ != *y++) return false;
+    return *x == *y;
+}
 static inline u8 *pit_libc_string_memcpy(u8 *dest, u8 *src, size_t n) {
     size_t i = 0;
     for (; i < n; ++i) dest[i] = src[i];
diff --git a/pit/include/lcq/pit/vec.h b/pit/include/lcq/pit/vec.h
index e1f7ab4..b60140f 100644
--- a/pit/include/lcq/pit/vec.h
+++ b/pit/include/lcq/pit/vec.h
@@ -14,7 +14,7 @@
 #define PIT_DECLARE_VEC(ty) \
     typedef struct { \
         i64 capacity, next; \
-        u8 data[]; \
+        ty data[]; \
     } pit_vec(ty); \
     static __attribute__ ((unused)) pit_vec(ty) *pit_vec_new(ty)(u8 *buf, i64 buf_len) { \
         uintptr_t base = (uintptr_t) buf; \
@@ -24,28 +24,28 @@
         i64 offset = (i64) data - (i64) base; \
         i64 remaining = (i64) (buf_len - offset); \
         ret->next = 0; \
-        ret->capacity = remaining; \
-        if ((ret->next + 1) * (i64) sizeof(ty) > ret->capacity) return NULL; \
+        ret->capacity = remaining / (i64) sizeof(ty); \
+        if ((ret->next + 1) > ret->capacity) return NULL; \
         return ret; \
     } \
     static __attribute__ ((unused)) void pit_vec_reset(ty)(pit_vec(ty) *s) { \
         s->next = 0; \
     } \
     static __attribute__ ((unused)) ty *pit_vec_get(ty)(pit_vec(ty) *s, i64 i) { \
-        i64 idx = i * (i64) sizeof(ty); \
-        if (idx + (i64) sizeof(ty) > s->capacity) return NULL; \
-        return (ty *) &s->data[idx]; \
+        i64 idx = i; \
+        if (idx + 1 > s->capacity) return NULL; \
+        return &s->data[idx]; \
     } \
     static __attribute__ ((unused)) i64 pit_vec_push(ty)(pit_vec(ty) *s, ty x) { \
-        i64 idx = s->next++ * (i64) sizeof(ty); \
-        if (idx + (i64) sizeof(ty) > s->capacity) { return -1; } \
-        *((ty *) &s->data[idx]) = x; \
+        i64 idx = s->next++; \
+        if (idx + 1 > s->capacity) { return -1; } \
+        s->data[idx] = x; \
         return s->next - 1; \
     } \
     static __attribute__ ((unused)) i64 pit_vec_pop(ty)(pit_vec(ty) *s, ty *v) { \
-        i64 idx = (s->next - 1) * (i64) sizeof(ty); \
-        if (s->next == 0 || idx + (i64) sizeof(ty) > s->capacity) return -1; \
-        *v = *((ty *) &s->data[idx]); \
+        i64 idx = (s->next - 1); \
+        if (s->next == 0 || idx + 1 > s->capacity) return -1; \
+        *v = s->data[idx]; \
         return --s->next; \
     }
 
@@ -110,4 +110,71 @@
         return idx; \
     }
 
+#define pit_hashtable_equal_cb(keyty) pit_hashtable__ ## keyty ## __equal_cb__type
+#define pit_hashtable_hash_cb(keyty) pit_hashtable__ ## keyty ## __hash_cb__type
+#define pit_hashtable_key_vtable(keyty) pit_hashtable__ ## keyty ## __key_vtable__type
+#define pit_hashtable_bucket(keyty, ty) pit_hashtable__ ## keyty ## __ ## ty ## __bucket__type
+#define pit_hashtable(keyty, ty) pit_hashtable__ ## keyty ## __ ## ty ## __type
+#define pit_hashtable_new(keyty, ty) pit_hashtable__ ## keyty ## __ ## ty ## __new
+#define pit_hashtable_reset(keyty, ty) pit_hashtable__ ## keyty ## __ ## ty ## __reset
+#define pit_hashtable_index(keyty, ty) pit_hashtable__ ## keyty ## __ ## ty ## __index
+#define pit_hashtable_insert(keyty, ty) pit_hashtable__ ## keyty ## __ ## ty ## __insert
+#define pit_hashtable_lookup(keyty, ty) pit_hashtable__ ## keyty ## __ ## ty ## __lookup
+
+#define PIT_DECLARE_HASHTABLE(keyty, ty) \
+    typedef bool (*pit_hashtable_equal_cb(keyty))(keyty x, keyty y); \
+    typedef u64 (*pit_hashtable_hash_cb(keyty))(keyty x); \
+    typedef struct { \
+        pit_hashtable_equal_cb(keyty) equal; \
+        pit_hashtable_hash_cb(keyty) hash; \
+    } pit_hashtable_key_vtable(keyty); \
+    typedef struct { \
+        bool present; \
+        keyty key; \
+        ty value; \
+    } pit_hashtable_bucket(keyty, ty); \
+    typedef struct { \
+        pit_hashtable_key_vtable(keyty) key_vtable; \
+        i64 capacity; \
+        pit_hashtable_bucket(keyty, ty) data[]; \
+    } pit_hashtable(keyty, ty); \
+    static __attribute__ ((unused)) pit_hashtable(keyty, ty) *pit_hashtable_new(keyty, ty)(u8 *buf, i64 buf_len, pit_hashtable_key_vtable(keyty) key_vtable) { \
+        uintptr_t base = (uintptr_t) buf; \
+        uintptr_t aligned = pit_align_up(base, sizeof(void *)); \
+        pit_hashtable(keyty, ty) *ret = (pit_hashtable(keyty, ty) *) aligned; \
+        uintptr_t data = aligned + (i64) sizeof(pit_hashtable(keyty, ty)); \
+        i64 offset = (i64) data - (i64) base; \
+        i64 remaining = (i64) (buf_len - offset); \
+        ret->key_vtable = key_vtable; \
+        ret->capacity = remaining / (i64) sizeof(pit_hashtable_bucket(keyty, ty)); \
+        for (i64 i = 0; i < ret->capacity; ++i) ret->data[i].present = false; \
+        return ret; \
+    } \
+    static __attribute__ ((unused)) void pit_hashtable_reset(keyty, ty)(pit_hashtable(keyty, ty) *ht) { \
+        for (i64 i = 0; i < ht->capacity; ++i) ht->data[i].present = false; \
+    } \
+    static __attribute__ ((unused)) i64 pit_hashtable_index(keyty, ty)(pit_hashtable(keyty, ty) *ht, keyty k) { \
+        u64 hash = ht->key_vtable.hash(k); \
+        i64 base = (i64) (hash % (u64) ht->capacity); \
+        for (i64 off = 0; off < ht->capacity; ++off) { \
+            i64 idx = (base + off) % ht->capacity; \
+            pit_hashtable_bucket(keyty, ty) *bucket = &ht->data[idx]; \
+            if (!bucket->present || ht->key_vtable.equal(bucket->key, k)) return idx; \
+        } \
+        return -1; \
+    } \
+    static __attribute__ ((unused)) i64 pit_hashtable_insert(keyty, ty)(pit_hashtable(keyty, ty) *ht, keyty k, ty v) { \
+        i64 idx = pit_hashtable_index(keyty, ty)(ht, k); \
+        if (idx < 0) return -1; \
+        ht->data[idx].present = true; \
+        ht->data[idx].key = k; \
+        ht->data[idx].value = v; \
+        return idx; \
+    } \
+    static __attribute__ ((unused)) ty *pit_hashtable_lookup(keyty, ty)(pit_hashtable(keyty, ty) *ht, keyty k) { \
+        i64 idx = pit_hashtable_index(keyty, ty)(ht, k); \
+        if (idx < 0 || !ht->data[idx].present) return NULL; \
+        return &ht->data[idx].value; \
+    }
+
 #endif
diff --git a/pit/src/main.c b/pit/src/main.c
index 61b4b9c..af759b6 100644
--- a/pit/src/main.c
+++ b/pit/src/main.c
@@ -7,7 +7,8 @@
 #include <lcq/pit/runtime.h>
 #include <lcq/pit/library.h>
 
-PIT_DECLARE_DEQUE(double)
+typedef char *mystr;
+PIT_DECLARE_HASHTABLE(mystr, double)
 
 int main(int argc, char **argv) {
     i64 sz = 256 * 1024 * 1024;
diff --git a/pit/src/native.c b/pit/src/native.c
index a62f82e..89d9c9b 100644
--- a/pit/src/native.c
+++ b/pit/src/native.c
@@ -23,16 +23,24 @@ i64 pit_lex_file(pit_lexer *ret, char *path) {
     return 0;
 }
 
+static i64 pit_dump_to_file_callback(u8 *buf, i64 len, void *data) {
+    if (fwrite(buf, sizeof(u8), (size_t) len, (FILE *) data) != (size_t) len) return -1;
+    return 0;
+}
+void pit_dump_to_file(pit_runtime *rt, void *vf, pit_value v, bool readable) {
+    pit_dump_with_callback(rt, v, readable, pit_dump_to_file_callback, vf);
+}
+
 bool pit_runtime_print_error(pit_runtime *rt) {
     if (!pit_value_eq(rt->error, PIT_NIL)) {
-        char buf[1024] = {0};
-        for (i64 i = 0; i < rt->backtrace->next; ++i) {
-            pit_annotated_ref *a = pit_vec_get(pit_annotated_ref)(rt->backtrace, i);
-            if (a == NULL) continue;
-            fprintf(stderr, "on line %ld, column %ld\n", a->annotation.line, a->annotation.column);
-        }
-        i64 end = pit_dump(rt, buf, sizeof(buf) - 1, rt->error, false); buf[end] = 0;
-        fprintf(stderr, "error at line %ld, column %ld: %s\n", rt->error_line, rt->error_column, buf);
+        // for (i64 i = 0; i < rt->backtrace->next; ++i) {
+        //     pit_annotated_ref *a = pit_vec_get(pit_annotated_ref)(rt->backtrace, i);
+        //     if (a == NULL) continue;
+        //     fprintf(stderr, "on line %ld, column %ld\n", a->annotation.line, a->annotation.column);
+        // }
+        fprintf(stderr, "error at line %ld, column %ld:", rt->error_line, rt->error_column);
+        pit_dump_to_file(rt, stderr, rt->error, false);
+        fprintf(stderr, "\n");
         return true;
     }
     return false;
@@ -149,10 +157,9 @@ void pit_repl(pit_runtime *rt) {
             rt->error = PIT_NIL;
             printf("> ");
         } else {
-            char dumpbuf[1024] = {0};
-            pit_dump(rt, dumpbuf, sizeof(dumpbuf) - 1, res, true);
+            pit_dump_to_file(rt, stdout, res, true);
             pit_gc(rt);
-            printf("%s\n> ", dumpbuf);
+            printf("\n> ");
         }
         len = 0;
     }
@@ -173,19 +180,15 @@ static pit_value impl_diagnostics(pit_runtime *rt, pit_value args, void *data) {
 static pit_value impl_print(pit_runtime *rt, pit_value args, void *data) {
     (void) data;
     pit_value x = pit_value_cons_car(rt, args);
-    char buf[1024] = {0};
-    pit_dump(rt, buf, sizeof(buf), x, true);
-    buf[1023] = 0;
-    puts(buf);
+    pit_dump_to_file(rt, stdout, x, true);
+    printf("\n");
     return x;
 }
 static pit_value impl_princ(pit_runtime *rt, pit_value args, void *data) {
     (void) data;
     pit_value x = pit_value_cons_car(rt, args);
-    char buf[1024] = {0};
-    pit_dump(rt, buf, sizeof(buf), x, false);
-    buf[1023] = 0;
-    puts(buf);
+    pit_dump_to_file(rt, stdout, x, false);
+    printf("\n");
     return x;
 }
 static pit_value impl_load(pit_runtime *rt, pit_value args, void *data) {
diff --git a/pit/src/runtime.c b/pit/src/runtime.c
index f13adb3..1e4309e 100644
--- a/pit/src/runtime.c
+++ b/pit/src/runtime.c
@@ -22,6 +22,8 @@ u64 pit_value_data(pit_value v) {
     return v & 0x1ffffffffffff;
 }
 
+static u64 ref_hash(pit_ref x) { return (u64) x; }
+static bool ref_equal(pit_ref x, pit_ref y) { return x == y; }
 pit_runtime *pit_runtime_new(u8 *buf, i64 len) {
     pit_arena *a = pit_arena_new(buf, len, sizeof(u8));
     pit_runtime *ret = pit_arena_alloc_back(a, sizeof(*ret));
@@ -29,10 +31,13 @@ pit_runtime *pit_runtime_new(u8 *buf, i64 len) {
     i64 annotations_size = len / 32;
     i64 symtab_size = len / 16;
     i64 stack_size = len / 32;
+    pit_hashtable_key_vtable(pit_ref) vt;
+    vt.hash = ref_hash;
+    vt.equal = ref_equal;
     ret->heap = pit_arena_new(pit_arena_alloc_back(a, heap_size), heap_size, sizeof(pit_value_heavy));
     ret->backbuffer = pit_arena_new(pit_arena_alloc_back(a, heap_size), heap_size, sizeof(pit_value_heavy));
-    ret->annotations = pit_vec_new(pit_annotated_ref)(pit_arena_alloc_back(a, annotations_size), annotations_size);
-    ret->backtrace = pit_vec_new(pit_annotated_ref)(pit_arena_alloc_back(a, annotations_size), annotations_size);
+    ret->annotations = pit_hashtable_new(pit_ref, pit_annotation)(pit_arena_alloc_back(a, annotations_size), annotations_size, vt);
+    ret->annotations_backbuffer = pit_hashtable_new(pit_ref, pit_annotation)(pit_arena_alloc_back(a, annotations_size), annotations_size, vt);
     ret->symtab = pit_vec_new(pit_symtab_entry)(pit_arena_alloc_back(a, symtab_size), symtab_size);
     ret->expr_stack = pit_vec_new(pit_value)(pit_arena_alloc_back(a, stack_size), stack_size);
     ret->result_stack = pit_vec_new(pit_value)(pit_arena_alloc_back(a, stack_size), stack_size);
@@ -82,21 +87,11 @@ void pit_error(pit_runtime *rt, char *format, ...) {
 }
 
 void pit_annotation_set(struct pit_runtime *rt, pit_ref ref, pit_annotation annotation) {
-    pit_annotated_ref a;
-    a.ref = ref;
-    a.annotation = annotation;
-    if (pit_vec_push(pit_annotated_ref)(rt->annotations, a) < 0)
+    if (pit_hashtable_insert(pit_ref, pit_annotation)(rt->annotations, ref, annotation) < 0)
         pit_error(rt, "annotation overflow");
 }
-pit_annotated_ref *pit_annotation_get(struct pit_runtime *rt, pit_ref ref) {
-    for (i64 i = 0; i < rt->annotations->next; ++i) {
-        pit_annotated_ref *a = pit_vec_get(pit_annotated_ref)(rt->annotations, i);
-        if (a == NULL) pit_error(rt, "failed to get annotation");
-        else if (a->ref == ref) {
-            return a;
-        }
-    }
-    return NULL;
+pit_annotation *pit_annotation_get(struct pit_runtime *rt, pit_ref ref) {
+    return pit_hashtable_lookup(pit_ref, pit_annotation)(rt->annotations, ref);
 }
 
 void pit_traversal_push_value(struct pit_runtime *rt, pit_vec(pit_traversal_entry) *s, pit_value x) {
@@ -113,7 +108,7 @@ void pit_traversal_push_dump_string(struct pit_runtime *rt, pit_vec(pit_traversa
     if (pit_vec_push(pit_traversal_entry)(s, ent) < 0)
         pit_error(rt, "traversal overflow");
 }
-void pit_traversal_push_application(struct pit_runtime *rt, pit_vec(pit_traversal_entry) *s, i64 arity, pit_annotated_ref *annotation) {
+void pit_traversal_push_application(struct pit_runtime *rt, pit_vec(pit_traversal_entry) *s, i64 arity, pit_annotation *annotation) {
     pit_traversal_entry ent;
     ent.sort = PIT_TRAVERSAL_ENTRY_APPLICATION;
     ent.in.application.arity = arity;
diff --git a/pit/src/runtime/dump.c b/pit/src/runtime/dump.c
index 3c1cf13..e8ba4b0 100644
--- a/pit/src/runtime/dump.c
+++ b/pit/src/runtime/dump.c
@@ -1,25 +1,26 @@
+#include <lcq/pit/utils.h>
 #include <lcq/pit/runtime/dump.h>
 
-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
+void pit_dump_with_callback(
+    pit_runtime *rt, pit_value top, bool readable,
+    pit_dump_callback write, void *data
 ) {
+    char buf[1024];
+    i64 len = (i64) sizeof(buf);
+    i64 slen = 0;
     i64 traversal_reset = rt->traversal->next;
-    char *buf = start;
-    char *end = start + buf_len;
     pit_value_heavy *h = NULL;
     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;
+            if (write((u8 *) ent.in.dump_string, (i64) pit_libc_string_strlen(ent.in.dump_string), data) < 0)
+                goto end;
             break;
         }
         case PIT_TRAVERSAL_ENTRY_VALUE: {
@@ -27,13 +28,15 @@ i64 pit_dump_with_callback(
             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));
+                slen = 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>");
+                slen = pit_libc_string_snprintf(buf, (size_t) len, "<unsupported double>");
 #endif
+                if (write((u8 *) buf, slen, data) < 0) goto end;
                 break;
             case PIT_VALUE_SORT_INTEGER:
-                buf += pit_libc_string_snprintf(buf, (size_t) len, "%ld", pit_value_as_integer(rt, v));
+                slen = pit_libc_string_snprintf(buf, (size_t) len, "%ld", pit_value_as_integer(rt, v));
+                if (write((u8 *) buf, slen, data) < 0) goto end;
                 break;
             case PIT_VALUE_SORT_SYMBOL: {
                 pit_symtab_entry *se = pit_symtab_lookup(rt, v);
@@ -41,21 +44,20 @@ i64 pit_dump_with_callback(
                     && 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];
-                    }
-                    buf += i;
+                    if (write(h->in.bytes.data, h->in.bytes.len, data) < 0) goto end;
                 } else {
-                    buf += pit_libc_string_snprintf(buf, (size_t) len, "<broken symbol %ld>", pit_value_as_symbol(rt, v));
+                    slen = pit_libc_string_snprintf(buf, (size_t) len, "<broken symbol %ld>", pit_value_as_symbol(rt, v));
+                    if (write((u8 *) buf, slen, data) < 0) goto end;
                 }
                 break;
             }
             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 {
+                if (!h) {
+                    pit_libc_string_snprintf(buf, (size_t) len, "<ref %ld>", r);
+                    if (write((u8 *) buf, slen, data) < 0) goto end;
+                } else {
                     switch (h->hsort) {
                     case PIT_VALUE_HEAVY_SORT_CELL: {
                         pit_traversal_push_dump_string(rt, rt->traversal, "}");
@@ -117,11 +119,12 @@ i64 pit_dump_with_callback(
                             }
                         }
                         if (readable && i < len - 1) buf[i++] = '"';
-                        buf += i;
+                        if (write((u8 *) buf, i, data) < 0) goto end;
                         break;
                     }
                     default:
-                        buf += pit_libc_string_snprintf(buf, (size_t) len, "<ref %ld>", r);
+                        slen = pit_libc_string_snprintf(buf, (size_t) len, "<ref %ld>", r);
+                        if (write((u8 *) buf, slen, data) < 0) goto end;
                     }
                 }
                 break;
@@ -135,9 +138,29 @@ i64 pit_dump_with_callback(
     }
 end:
     rt->traversal->next = traversal_reset;
-    return (i64) (buf - start);
+}
+
+struct pit_dump_to_buf_closure {
+    char *buf;
+    i64 len;
+    i64 off;
+};
+static i64 pit_dump_to_buf_callback(u8 *buf, i64 len, void *data) {
+    struct pit_dump_to_buf_closure *cl = (struct pit_dump_to_buf_closure *) data;
+    i64 i = 0;
+    for (; i < len && cl->off + i < cl->len; ++i) {
+        cl->buf[cl->off + i] = (char) buf[i];
+    }
+    cl->off += i;
+    if (cl->len - cl->off < len) return -1;
+    return 0;
 }
 
 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);
+    struct pit_dump_to_buf_closure cl;
+    cl.buf = buf;
+    cl.len = len;
+    cl.off = 0;
+    pit_dump_with_callback(rt, v, readable, pit_dump_to_buf_callback, &cl);
+    return cl.off;
 }
diff --git a/pit/src/runtime/eval.c b/pit/src/runtime/eval.c
index 301d8d0..f923760 100644
--- a/pit/src/runtime/eval.c
+++ b/pit/src/runtime/eval.c
@@ -16,7 +16,7 @@ pit_value pit_eval(pit_runtime *rt, pit_value top) {
         if (pit_value_is_cons(rt, cur)) { /* compound expressions: function/macro application special forms */
             pit_value fsym = pit_value_cons_car(rt, cur);
             bool is_symbol = pit_value_is_symbol(rt, fsym);
-            pit_annotated_ref *ann = pit_annotation_get(rt, pit_value_as_ref(rt, cur));
+            pit_annotation *ann = pit_annotation_get(rt, pit_value_as_ref(rt, cur));
             if (is_symbol && pit_symtab_is_symbol_special_form(rt, fsym)) { /* special forms */
                 pit_value f = pit_symtab_fget(rt, fsym);
                 pit_value args = pit_value_cons_cdr(rt, cur);
@@ -82,9 +82,9 @@ pit_value pit_eval(pit_runtime *rt, pit_value top) {
                 args = pit_value_cons(rt, a, args);
             }
             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);
+                rt->source_line = ent->in.application.annotation->line;
+                rt->source_column = ent->in.application.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");
diff --git a/pit/src/runtime/gc.c b/pit/src/runtime/gc.c
index fcb5f89..671202d 100644
--- a/pit/src/runtime/gc.c
+++ b/pit/src/runtime/gc.c
@@ -17,11 +17,9 @@ static pit_value gc_copy_value(pit_runtime *rt, pit_value v) {
         pit_ref r = pit_value_as_ref(rt, v);
         pit_value_heavy *h = pit_value_ref_deref(rt, r);
         i64 new = gc_copy(rt, h);
-        pit_annotated_ref *ann = pit_annotation_get(rt, r);
+        pit_annotation *ann = pit_annotation_get(rt, r);
         if (ann != NULL) {
-            pit_annotated_ref newann = *ann;
-            newann.ref = new;
-            if (pit_vec_push(pit_annotated_ref)(rt->backtrace, newann) < 0)
+            if (pit_hashtable_insert(pit_ref, pit_annotation)(rt->annotations_backbuffer, new, *ann) < 0)
                 pit_error(rt, "annotation overflow");
         }
         return pit_value_ref_new(rt, new);
@@ -34,10 +32,10 @@ void pit_gc(pit_runtime *rt) {
     rt->frozen_symtab = 0;
     pit_arena *fromspace = rt->heap;
     pit_arena *tospace = rt->backbuffer;
-    pit_vec(pit_annotated_ref) *fromspace_ann = rt->annotations;
-    pit_vec(pit_annotated_ref) *tospace_ann = rt->backtrace;
+    pit_hashtable(pit_ref, pit_annotation) *fromspace_ann = rt->annotations;
+    pit_hashtable(pit_ref, pit_annotation) *tospace_ann = rt->annotations_backbuffer;
     pit_arena_reset(tospace);
-    pit_vec_reset(pit_annotated_ref)(tospace_ann);
+    pit_hashtable_reset(pit_ref, pit_annotation)(tospace_ann);
     /* populate tospace with immediately reachable values */
     for (i64 i = 0; i < rt->symtab->next; ++i) {
         pit_symtab_entry *ent = pit_vec_get(pit_symtab_entry)(rt->symtab, i);
@@ -95,6 +93,6 @@ void pit_gc(pit_runtime *rt) {
     rt->heap = tospace;
     rt->backbuffer = fromspace;
     rt->annotations = tospace_ann;
-    rt->backtrace = fromspace_ann;
-    pit_vec_reset(pit_annotated_ref)(rt->backtrace);
+    rt->annotations_backbuffer = fromspace_ann;
+    pit_hashtable_reset(pit_ref, pit_annotation)(rt->annotations_backbuffer);
 }
diff --git a/pit/src/runtime/macroexpand.c b/pit/src/runtime/macroexpand.c
index 6252ae1..7ff1a6a 100644
--- a/pit/src/runtime/macroexpand.c
+++ b/pit/src/runtime/macroexpand.c
@@ -14,7 +14,7 @@ pit_value pit_macroexpand(pit_runtime *rt, pit_value top) {
         if (pit_value_is_cons(rt, cur)) {
             pit_value fsym = pit_value_cons_car(rt, cur);
             bool is_symbol = pit_value_is_symbol(rt, fsym);
-            pit_annotated_ref *ann = pit_annotation_get(rt, pit_value_as_ref(rt, cur));
+            pit_annotation *ann = pit_annotation_get(rt, pit_value_as_ref(rt, cur));
             if (is_symbol && pit_symtab_is_symbol_macro(rt, fsym)) {
                 pit_value f = pit_symtab_fget(rt, fsym);
                 pit_value args = pit_value_cons_cdr(rt, cur);
@@ -88,7 +88,7 @@ pit_value pit_macroexpand(pit_runtime *rt, pit_value top) {
             }
             app = pit_value_cons(rt, f, args);
             if (ent->in.application.annotation != NULL) {
-                pit_annotation_set(rt, pit_value_as_ref(rt, app), ent->in.application.annotation->annotation);
+                pit_annotation_set(rt, pit_value_as_ref(rt, app), *ent->in.application.annotation);
             }
             if (pit_vec_push(pit_value)(rt->result_stack, app) < 0)
                 pit_error(rt, "macro expansion stack overflow");