pit: Hash table annotations, better dumper

4 files changed, 107 insertions, 22 deletions

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