Move stdlib into src/

1 files changed, 798 insertions, 0 deletions

diff --git a/src/stdlib/tables.c b/src/stdlib/tables.c
new file mode 100644
index 00000000..97419327
--- /dev/null
+++ b/src/stdlib/tables.c
@@ -0,0 +1,798 @@
+// table.c - C Hash table implementation
+// Copyright 2024 Bruce Hill
+// Provided under the MIT license with the Commons Clause
+// See included LICENSE for details.
+
+// Hash table (aka Dictionary) Implementation
+// Hash keys and values are stored *by value*
+// The hash insertion/lookup implementation is based on Lua's tables,
+// which use a chained scatter with Brent's variation.
+
+#include <assert.h>
+#include <gc.h>
+#include <stdarg.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sys/param.h>
+
+#include "arrays.h"
+#include "c_strings.h"
+#include "datatypes.h"
+#include "memory.h"
+#include "metamethods.h"
+#include "pointers.h"
+#include "siphash.h"
+#include "tables.h"
+#include "text.h"
+#include "types.h"
+#include "util.h"
+
+// #define DEBUG_TABLES
+
+#ifdef DEBUG_TABLES
+#define hdebug(fmt, ...) printf("\x1b[2m" fmt "\x1b[m" __VA_OPT__(,) __VA_ARGS__)
+#else
+#define hdebug(...) (void)0
+#endif
+
+// Helper accessors for type functions/values:
+#define HASH_KEY(t, k) (generic_hash((k), type->TableInfo.key) % ((t).bucket_info->count))
+#define EQUAL_KEYS(x, y) (generic_equal((x), (y), type->TableInfo.key))
+#define END_OF_CHAIN UINT32_MAX
+
+#define GET_ENTRY(t, i) ((t).entries.data + (t).entries.stride*(i))
+
+static TypeInfo_t MemoryPointer = {
+    .size=sizeof(void*),
+    .align=__alignof__(void*),
+    .tag=PointerInfo,
+    .PointerInfo={
+        .sigil="@",
+        .pointed=&Memory$info,
+    },
+    .metamethods=Pointer$metamethods,
+};
+
+const TypeInfo_t CStrToVoidStarTable = {
+    .size=sizeof(Table_t),
+    .align=__alignof__(Table_t),
+    .tag=TableInfo,
+    .TableInfo={.key=&CString$info, .value=&MemoryPointer},
+    .metamethods=Table$metamethods,
+};
+
+PUREFUNC static INLINE size_t entry_size(const TypeInfo_t *info)
+{
+    size_t size = (size_t)info->TableInfo.key->size;
+    if (info->TableInfo.value->align > 1 && size % (size_t)info->TableInfo.value->align)
+        size += (size_t)info->TableInfo.value->align - (size % (size_t)info->TableInfo.value->align); // padding
+    size += (size_t)info->TableInfo.value->size;
+    if (info->TableInfo.key->align > 1 && size % (size_t)info->TableInfo.key->align)
+        size += (size_t)info->TableInfo.key->align - (size % (size_t)info->TableInfo.key->align); // padding
+    return size;
+}
+
+PUREFUNC static INLINE size_t entry_align(const TypeInfo_t *info)
+{
+    return (size_t)MAX(info->TableInfo.key->align, info->TableInfo.value->align);
+}
+
+PUREFUNC static INLINE size_t value_offset(const TypeInfo_t *info)
+{
+    size_t offset = (size_t)info->TableInfo.key->size;
+    if ((size_t)info->TableInfo.value->align > 1 && offset % (size_t)info->TableInfo.value->align)
+        offset += (size_t)info->TableInfo.value->align - (offset % (size_t)info->TableInfo.value->align); // padding
+    return offset;
+}
+
+static INLINE void hshow(const Table_t *t)
+{
+    hdebug("{");
+    for (uint32_t i = 0; t->bucket_info && i < t->bucket_info->count; i++) {
+        if (i > 0) hdebug(" ");
+        if (t->bucket_info->buckets[i].occupied)
+            hdebug("[%d]=%d(%d)", i, t->bucket_info->buckets[i].index, t->bucket_info->buckets[i].next_bucket);
+        else
+            hdebug("[%d]=_", i);
+    }
+    hdebug("}\n");
+}
+
+static void maybe_copy_on_write(Table_t *t, const TypeInfo_t *type)
+{
+    if (t->entries.data_refcount != 0)
+        Array$compact(&t->entries, (int64_t)entry_size(type));
+
+    if (t->bucket_info && t->bucket_info->data_refcount != 0) {
+        size_t size = sizeof(bucket_info_t) + sizeof(bucket_t[t->bucket_info->count]);
+        t->bucket_info = memcpy(GC_MALLOC(size), t->bucket_info, size);
+        t->bucket_info->data_refcount = 0;
+    }
+}
+
+// Return address of value or NULL
+PUREFUNC public void *Table$get_raw(Table_t t, const void *key, const TypeInfo_t *type)
+{
+    assert(type->tag == TableInfo);
+    if (!key || !t.bucket_info) return NULL;
+
+    uint64_t hash = HASH_KEY(t, key);
+    hshow(&t);
+    hdebug("Getting value with initial probe at %u\n", hash);
+    bucket_t *buckets = t.bucket_info->buckets;
+    for (uint64_t i = hash; buckets[i].occupied; i = buckets[i].next_bucket) {
+        hdebug("Checking against key in bucket %u\n", i);
+        void *entry = GET_ENTRY(t, buckets[i].index);
+        if (EQUAL_KEYS(entry, key)) {
+            hdebug("Found key!\n");
+            return entry + value_offset(type);
+        }
+        if (buckets[i].next_bucket == END_OF_CHAIN)
+            break;
+    }
+    return NULL;
+}
+
+PUREFUNC public void *Table$get(Table_t t, const void *key, const TypeInfo_t *type)
+{
+    assert(type->tag == TableInfo);
+    for (const Table_t *iter = &t; iter; iter = iter->fallback) {
+        void *ret = Table$get_raw(*iter, key, type);
+        if (ret) return ret;
+    }
+    return NULL;
+}
+
+static void Table$set_bucket(Table_t *t, const void *entry, int32_t index, const TypeInfo_t *type)
+{
+    assert(t->bucket_info);
+    hshow(t);
+    const void *key = entry;
+    bucket_t *buckets = t->bucket_info->buckets;
+    uint64_t hash = HASH_KEY(*t, key);
+    hdebug("Hash value (mod %u) = %u\n", t->bucket_info->count, hash);
+    bucket_t *bucket = &buckets[hash];
+    if (!bucket->occupied) {
+        hdebug("Got an empty space\n");
+        // Empty space:
+        bucket->occupied = 1;
+        bucket->index = index;
+        bucket->next_bucket = END_OF_CHAIN;
+        hshow(t);
+        return;
+    }
+
+    hdebug("Collision detected in bucket %u (entry %u)\n", hash, bucket->index);
+
+    while (buckets[t->bucket_info->last_free].occupied) {
+        assert(t->bucket_info->last_free > 0);
+        --t->bucket_info->last_free;
+    }
+
+    uint64_t collided_hash = HASH_KEY(*t, GET_ENTRY(*t, bucket->index));
+    if (collided_hash != hash) { // Collided with a mid-chain entry
+        hdebug("Hit a mid-chain entry at bucket %u (chain starting at %u)\n", hash, collided_hash);
+        // Find chain predecessor
+        uint64_t predecessor = collided_hash;
+        while (buckets[predecessor].next_bucket != hash)
+            predecessor = buckets[predecessor].next_bucket;
+
+        // Move mid-chain entry to free space and update predecessor
+        buckets[predecessor].next_bucket = t->bucket_info->last_free;
+        buckets[t->bucket_info->last_free] = *bucket;
+    } else { // Collided with the start of a chain
+        hdebug("Hit start of a chain\n");
+        uint64_t end_of_chain = hash;
+        while (buckets[end_of_chain].next_bucket != END_OF_CHAIN)
+            end_of_chain = buckets[end_of_chain].next_bucket;
+        hdebug("Appending to chain\n");
+        // Chain now ends on the free space:
+        buckets[end_of_chain].next_bucket = t->bucket_info->last_free;
+        bucket = &buckets[t->bucket_info->last_free];
+    }
+
+    bucket->occupied = 1;
+    bucket->index = index;
+    bucket->next_bucket = END_OF_CHAIN;
+    hshow(t);
+}
+
+static void hashmap_resize_buckets(Table_t *t, uint32_t new_capacity, const TypeInfo_t *type)
+{
+    if (unlikely(new_capacity > TABLE_MAX_BUCKETS))
+        fail("Table has exceeded the maximum table size (2^31) and cannot grow further!");
+    hdebug("About to resize from %u to %u\n", t->bucket_info ? t->bucket_info->count : 0, new_capacity);
+    hshow(t);
+    size_t alloc_size = sizeof(bucket_info_t) + sizeof(bucket_t[new_capacity]);
+    t->bucket_info = GC_MALLOC_ATOMIC(alloc_size);
+    memset(t->bucket_info->buckets, 0, sizeof(bucket_t[new_capacity]));
+    t->bucket_info->count = new_capacity;
+    t->bucket_info->last_free = new_capacity-1;
+    // Rehash:
+    for (int64_t i = 0; i < Table$length(*t); i++) {
+        hdebug("Rehashing %u\n", i);
+        Table$set_bucket(t, GET_ENTRY(*t, i), i, type);
+    }
+
+    hshow(t);
+    hdebug("Finished resizing\n");
+}
+
+// Return address of value
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wstack-protector"
+public void *Table$reserve(Table_t *t, const void *key, const void *value, const TypeInfo_t *type)
+{
+    assert(type->tag == TableInfo);
+    if (!t || !key) return NULL;
+    hshow(t);
+
+    t->hash = 0;
+
+    int64_t key_size = type->TableInfo.key->size,
+            value_size = type->TableInfo.value->size;
+    if (!t->bucket_info || t->bucket_info->count == 0) {
+        hashmap_resize_buckets(t, 8, type);
+    } else {
+        // Check if we are clobbering a value:
+        void *value_home = Table$get_raw(*t, key, type);
+        if (value_home) { // Update existing slot
+            // Ensure that `value_home` is still inside t->entries, even if COW occurs
+            ptrdiff_t offset = value_home - t->entries.data;
+            maybe_copy_on_write(t, type);
+            value_home = t->entries.data + offset;
+
+            if (value && value_size > 0)
+                memcpy(value_home, value, (size_t)value_size);
+
+            return value_home;
+        }
+    }
+    // Otherwise add a new entry:
+
+    // Resize buckets if necessary
+    if (t->entries.length >= (int64_t)t->bucket_info->count) {
+        // Current resize policy: +50% at a time:
+        uint32_t newsize = MAX(8, (uint32_t)(3*t->bucket_info->count)/2);
+        if (unlikely(newsize > TABLE_MAX_BUCKETS))
+            newsize = TABLE_MAX_BUCKETS;
+        hashmap_resize_buckets(t, newsize, type);
+    }
+
+    if (!value && value_size > 0) {
+        for (Table_t *iter = t->fallback; iter; iter = iter->fallback) {
+            value = Table$get_raw(*iter, key, type);
+            if (value) break;
+        }
+    }
+
+    maybe_copy_on_write(t, type);
+
+    char buf[entry_size(type)];
+    memset(buf, 0, sizeof(buf));
+    memcpy(buf, key, (size_t)key_size);
+    if (value && value_size > 0)
+        memcpy(buf + value_offset(type), value, (size_t)value_size);
+    else
+        memset(buf + value_offset(type), 0, (size_t)value_size);
+    Array$insert(&t->entries, buf, I(0), (int64_t)entry_size(type));
+
+    int64_t entry_index = t->entries.length-1;
+    void *entry = GET_ENTRY(*t, entry_index);
+    Table$set_bucket(t, entry, entry_index, type);
+    return entry + value_offset(type);
+}
+#pragma GCC diagnostic pop
+
+public void Table$set(Table_t *t, const void *key, const void *value, const TypeInfo_t *type)
+{
+    assert(type->tag == TableInfo);
+    (void)Table$reserve(t, key, value, type);
+}
+
+public void Table$remove(Table_t *t, const void *key, const TypeInfo_t *type)
+{
+    assert(type->tag == TableInfo);
+    if (!t || Table$length(*t) == 0) return;
+
+    // TODO: this work doesn't need to be done if the key is already missing
+    maybe_copy_on_write(t, type);
+
+    // If unspecified, pop the last key:
+    if (!key)
+        key = GET_ENTRY(*t, t->entries.length-1);
+
+    // Steps: look up the bucket for the removed key
+    // If missing, then return immediately
+    // Swap last key/value into the removed bucket's index1
+    // Zero out the last key/value and decrement the count
+    // Find the last key/value's bucket and update its index1
+    // Look up the bucket for the removed key
+    // If bucket is first in chain:
+    //    Move bucket->next to bucket's spot
+    //    zero out bucket->next's old spot
+    //    maybe update lastfree_index1 to second-in-chain's index
+    // Else:
+    //    set prev->next = bucket->next
+    //    zero out bucket
+    //    maybe update lastfree_index1 to removed bucket's index
+
+    uint64_t hash = HASH_KEY(*t, key);
+    hdebug("Removing key with hash %u\n", hash);
+    bucket_t *bucket, *prev = NULL;
+    for (uint64_t i = hash; t->bucket_info->buckets[i].occupied; i = t->bucket_info->buckets[i].next_bucket) {
+        if (EQUAL_KEYS(GET_ENTRY(*t, t->bucket_info->buckets[i].index), key)) {
+            bucket = &t->bucket_info->buckets[i];
+            hdebug("Found key to delete in bucket %u\n", i);
+            goto found_it;
+        }
+        if (t->bucket_info->buckets[i].next_bucket == END_OF_CHAIN)
+            return;
+        prev = &t->bucket_info->buckets[i];
+    }
+    return;
+
+  found_it:;
+    assert(bucket->occupied);
+
+    t->hash = 0;
+
+    // Always remove the last entry. If we need to remove some other entry,
+    // swap the other entry into the last position and then remove the last
+    // entry. This disturbs the ordering of the table, but keeps removal O(1)
+    // instead of O(N)
+    int64_t last_entry = t->entries.length-1;
+    if (bucket->index != last_entry) {
+        hdebug("Removing key/value from the middle of the entries array\n");
+
+        // Find the bucket that points to the last entry's index:
+        uint64_t i = HASH_KEY(*t, GET_ENTRY(*t, last_entry));
+        while (t->bucket_info->buckets[i].index != last_entry)
+            i = t->bucket_info->buckets[i].next_bucket;
+        // Update the bucket to point to the last entry's new home (the space
+        // where the removed entry currently sits):
+        t->bucket_info->buckets[i].index = bucket->index;
+
+        // Clobber the entry being removed (in the middle of the array) with
+        // the last entry:
+        memcpy(GET_ENTRY(*t, bucket->index), GET_ENTRY(*t, last_entry), entry_size(type));
+    }
+
+    // Last entry is being removed, so clear it out to be safe:
+    memset(GET_ENTRY(*t, last_entry), 0, entry_size(type));
+
+    Array$remove_at(&t->entries, I(t->entries.length), I(1), (int64_t)entry_size(type));
+
+    int64_t bucket_to_clear;
+    if (prev) { // Middle (or end) of a chain
+        hdebug("Removing from middle of a chain\n");
+        bucket_to_clear = (bucket - t->bucket_info->buckets);
+        prev->next_bucket = bucket->next_bucket;
+    } else if (bucket->next_bucket != END_OF_CHAIN) { // Start of a chain
+        hdebug("Removing from start of a chain\n");
+        bucket_to_clear = bucket->next_bucket;
+        *bucket = t->bucket_info->buckets[bucket_to_clear];
+    } else { // Empty chain
+        hdebug("Removing from empty chain\n");
+        bucket_to_clear = (bucket - t->bucket_info->buckets);
+    }
+
+    t->bucket_info->buckets[bucket_to_clear] = (bucket_t){0};
+    if (bucket_to_clear > t->bucket_info->last_free)
+        t->bucket_info->last_free = bucket_to_clear;
+
+    hshow(t);
+}
+
+CONSTFUNC public void *Table$entry(Table_t t, int64_t n)
+{
+    if (n < 1 || n > Table$length(t))
+        return NULL;
+    return GET_ENTRY(t, n-1);
+}
+
+public void Table$clear(Table_t *t)
+{
+    memset(t, 0, sizeof(Table_t));
+}
+
+public Table_t Table$sorted(Table_t t, const TypeInfo_t *type)
+{
+    Closure_t cmp = (Closure_t){.fn=generic_compare, .userdata=(void*)type->TableInfo.key};
+    Array_t entries = Array$sorted(t.entries, cmp, (int64_t)entry_size(type));
+    return Table$from_entries(entries, type);
+}
+
+PUREFUNC public bool Table$equal(const void *vx, const void *vy, const TypeInfo_t *type)
+{
+    if (vx == vy) return true;
+    Table_t *x = (Table_t*)vx, *y = (Table_t*)vy;
+
+    if (x->hash && y->hash && x->hash != y->hash)
+        return false;
+
+    assert(type->tag == TableInfo);
+    if (x->entries.length != y->entries.length)
+        return false;
+    
+    if ((x->fallback != NULL) != (y->fallback != NULL))
+        return false;
+
+    const TypeInfo_t *value_type = type->TableInfo.value;
+    size_t offset = value_offset(type);
+    for (int64_t i = 0; i < x->entries.length; i++) {
+        void *x_key = x->entries.data + i*x->entries.stride;
+        void *y_value = Table$get_raw(*y, x_key, type);
+        if (!y_value) return false;
+        void *x_value = x_key + offset;
+        if (!generic_equal(y_value, x_value, value_type))
+            return false;
+    }
+    return true;
+}
+
+PUREFUNC public int32_t Table$compare(const void *vx, const void *vy, const TypeInfo_t *type)
+{
+    if (vx == vy) return 0;
+
+    Table_t *x = (Table_t*)vx, *y = (Table_t*)vy;
+    assert(type->tag == TableInfo);
+    auto table = type->TableInfo;
+
+    // Sort empty tables before non-empty tables:
+    if (x->entries.length == 0 || y->entries.length == 0)
+        return ((x->entries.length > 0) - (y->entries.length > 0));
+
+    // Table comparison rules:
+    // - If two tables have different keys, then compare as if comparing a
+    // sorted array of the keys of the two tables:
+    //    `x.keys:sorted() <> y.keys:sorted()`
+    // - Otherwise, compare as if comparing arrays of values for the sorted key
+    // arrays:
+    //    `[x[k] for k in x.keys:sorted()] <> [y[k] for k in y.keys:sorted()]`
+    // 
+    // We can do this in _linear_ time if we find the smallest `k` such that
+    // `x[k] != y[k]`, as well as the largest key in `x` and `y`.
+
+    void *mismatched_key = NULL, *max_x_key = NULL;
+    for (int64_t i = 0; i < x->entries.length; i++) {
+        void *key = x->entries.data + x->entries.stride * i;
+        if (max_x_key == NULL || generic_compare(key, max_x_key, table.key) > 0)
+            max_x_key = key;
+
+        void *x_value = key + value_offset(type);
+        void *y_value = Table$get_raw(*y, key, type);
+
+        if (!y_value || (table.value->size > 0 && !generic_equal(x_value, y_value, table.value))) {
+            if (mismatched_key == NULL || generic_compare(key, mismatched_key, table.key) < 0) 
+                mismatched_key = key;
+        }
+    }
+
+    // If the keys are not all equal, we gotta check to see if there exists a
+    // `y[k]` such that `k` is smaller than all keys that `x` has and `y` doesn't:
+    void *max_y_key = NULL;
+    for (int64_t i = 0; i < y->entries.length; i++) {
+        void *key = y->entries.data + y->entries.stride * i;
+        if (max_y_key == NULL || generic_compare(key, max_y_key, table.key) > 0)
+            max_y_key = key;
+
+        void *y_value = key + value_offset(type);
+        void *x_value = Table$get_raw(*x, key, type);
+        if (!x_value || !generic_equal(x_value, y_value, table.value)) {
+            if (mismatched_key == NULL || generic_compare(key, mismatched_key, table.key) < 0) 
+                mismatched_key = key;
+        }
+    }
+
+    if (mismatched_key) {
+        void *x_value = Table$get_raw(*x, mismatched_key, type);
+        void *y_value = Table$get_raw(*y, mismatched_key, type);
+        if (x_value && y_value) {
+            return generic_compare(x_value, y_value, table.value);
+        } else if (y_value) {
+            // The smallest mismatched key is in Y, but not X.
+            // In this case, we should judge if the key is smaller than *any*
+            // key in X or if it's bigger than *every* key in X.
+            // Example 1:
+            //     x={10, 20, 30} > y={10, 20, 25, 30}
+            // The smallest mismatched key is `25`, and we know that `x` is
+            // larger than `y` because `30 > 25`.
+            // Example 2:
+            //     x={10, 20, 30} > y={10, 20, 30, 999}
+            // The smallest mismatched key is `999`, and we know that `x` is
+            // smaller than `y` because `30 < 999`.
+            return max_x_key ? generic_compare(max_x_key, mismatched_key, table.key) : -1;
+        } else {
+            assert(x_value);
+            // The smallest mismatched key is in X, but not Y. The same logic
+            // above applies, but reversed.
+            return max_y_key ? -generic_compare(max_y_key, mismatched_key, table.key) : 1;
+        }
+    }
+
+    assert(x->entries.length == y->entries.length);
+
+    // Assuming keys are the same, compare values:
+    if (table.value->size > 0) {
+        for (int64_t i = 0; i < x->entries.length; i++) {
+            void *key = x->entries.data + x->entries.stride * i;
+            void *x_value = key + value_offset(type);
+            void *y_value = Table$get_raw(*y, key, type);
+            int32_t diff = generic_compare(x_value, y_value, table.value);
+            if (diff != 0) return diff;
+        }
+    }
+
+    if (!x->fallback != !y->fallback) {
+        return (!x->fallback) - (!y->fallback);
+    } else if (x->fallback && y->fallback) {
+        return generic_compare(x->fallback, y->fallback, type);
+    }
+
+    return 0;
+}
+
+PUREFUNC public uint64_t Table$hash(const void *obj, const TypeInfo_t *type)
+{
+    assert(type->tag == TableInfo);
+    Table_t *t = (Table_t*)obj;
+    if (t->hash != 0)
+        return t->hash;
+
+    // Table hashes are computed as:
+    // hash(t.length, (xor: t.keys), (xor: t.values), t.fallback)
+    // Where fallback and default hash to zero if absent
+    auto table = type->TableInfo;
+    uint64_t keys_hash = 0, values_hash = 0;
+    size_t offset = value_offset(type);
+    if (table.value->size > 0) {
+        for (int64_t i = 0; i < t->entries.length; i++) {
+            keys_hash ^= generic_hash(t->entries.data + i*t->entries.stride, table.key);
+            values_hash ^= generic_hash(t->entries.data + i*t->entries.stride + offset, table.value);
+        }
+    } else {
+        for (int64_t i = 0; i < t->entries.length; i++)
+            keys_hash ^= generic_hash(t->entries.data + i*t->entries.stride, table.key);
+    }
+
+    struct {
+        int64_t length;
+        uint64_t keys_hash, values_hash;
+        Table_t *fallback;
+    } components = {
+        t->entries.length,
+        keys_hash,
+        values_hash,
+        t->fallback,
+    };
+    t->hash = siphash24((void*)&components, sizeof(components));
+    if unlikely (t->hash == 0)
+        t->hash = 1234567;
+    return t->hash;
+}
+
+public Text_t Table$as_text(const void *obj, bool colorize, const TypeInfo_t *type)
+{
+    Table_t *t = (Table_t*)obj;
+    assert(type->tag == TableInfo);
+    auto table = type->TableInfo;
+
+    if (!t) {
+        if (table.value != &Void$info) 
+            return Text$concat(
+                Text("{"),
+                generic_as_text(NULL, false, table.key),
+                Text(","),
+                generic_as_text(NULL, false, table.value),
+                Text("}"));
+        else
+            return Text$concat(
+                Text("{"),
+                generic_as_text(NULL, false, table.key),
+                Text("}"));
+    }
+
+    int64_t val_off = (int64_t)value_offset(type);
+    Text_t text = Text("{");
+    for (int64_t i = 0, length = Table$length(*t); i < length; i++) {
+        if (i > 0)
+            text = Text$concat(text, Text(", "));
+        void *entry = GET_ENTRY(*t, i);
+        text = Text$concat(text, generic_as_text(entry, colorize, table.key));
+        if (table.value != &Void$info) 
+            text = Text$concat(text, Text("="), generic_as_text(entry + val_off, colorize, table.value));
+    }
+
+    if (t->fallback) {
+        text = Text$concat(text, Text("; fallback="), Table$as_text(t->fallback, colorize, type));
+    }
+
+    text = Text$concat(text, Text("}"));
+    return text;
+}
+
+public Table_t Table$from_entries(Array_t entries, const TypeInfo_t *type)
+{
+    assert(type->tag == TableInfo);
+    if (entries.length == 0)
+        return (Table_t){};
+
+    Table_t t = {};
+    int64_t length = entries.length + entries.length / 4;
+    size_t alloc_size = sizeof(bucket_info_t) + sizeof(bucket_t[length]);
+    t.bucket_info = GC_MALLOC_ATOMIC(alloc_size);
+    memset(t.bucket_info->buckets, 0, sizeof(bucket_t[length]));
+    t.bucket_info->count = length;
+    t.bucket_info->last_free = length-1;
+
+    size_t offset = value_offset(type);
+    for (int64_t i = 0; i < entries.length; i++) {
+        void *key = entries.data + i*entries.stride;
+        Table$set(&t, key, key + offset, type);
+    }
+    return t;
+}
+
+// Overlap is "set intersection" in formal terms
+public Table_t Table$overlap(Table_t a, Table_t b, const TypeInfo_t *type)
+{
+    // Return a table such that t[k]==a[k] for all k such that a:has(k), b:has(k), and a[k]==b[k]
+    Table_t result = {};
+    const size_t offset = value_offset(type);
+    for (int64_t i = 0; i < Table$length(a); i++) {
+        void *key = GET_ENTRY(a, i);
+        void *a_value = key + offset;
+        void *b_value = Table$get(b, key, type);
+        if (b_value && generic_equal(a_value, b_value, type->TableInfo.value))
+            Table$set(&result, key, a_value, type);
+    }
+
+    if (a.fallback) {
+        result.fallback = new(Table_t);
+        *result.fallback = Table$overlap(*a.fallback, b, type);
+    }
+
+    return result;
+}
+
+// With is "set union" in formal terms
+public Table_t Table$with(Table_t a, Table_t b, const TypeInfo_t *type)
+{
+    // return a table such that t[k]==b[k] for all k such that b:has(k), and t[k]==a[k] for all k such that a:has(k) and not b:has(k)
+    Table_t result = {};
+    const size_t offset = value_offset(type);
+    for (int64_t i = 0; i < Table$length(a); i++) {
+        void *key = GET_ENTRY(a, i);
+        Table$set(&result, key, key + offset, type);
+    }
+    for (int64_t i = 0; i < Table$length(b); i++) {
+        void *key = GET_ENTRY(b, i);
+        Table$set(&result, key, key + offset, type);
+    }
+
+    if (a.fallback && b.fallback) {
+        result.fallback = new(Table_t);
+        *result.fallback = Table$with(*a.fallback, *b.fallback, type);
+    } else {
+        result.fallback = a.fallback ? a.fallback : b.fallback;
+    }
+
+    return result;
+}
+
+// Without is "set difference" in formal terms
+public Table_t Table$without(Table_t a, Table_t b, const TypeInfo_t *type)
+{
+    // Return a table such that t[k]==a[k] for all k such that not b:has(k) or b[k] != a[k]
+    Table_t result = {};
+    const size_t offset = value_offset(type);
+    for (int64_t i = 0; i < Table$length(a); i++) {
+        void *key = GET_ENTRY(a, i);
+        void *a_value = key + offset;
+        void *b_value = Table$get(b, key, type);
+        if (!b_value || !generic_equal(a_value, b_value, type->TableInfo.value))
+            Table$set(&result, key, a_value, type);
+    }
+
+    if (a.fallback) {
+        result.fallback = new(Table_t);
+        *result.fallback = Table$without(*a.fallback, b, type);
+    }
+
+    return result;
+}
+
+PUREFUNC public bool Table$is_subset_of(Table_t a, Table_t b, bool strict, const TypeInfo_t *type)
+{
+    if (a.entries.length > b.entries.length || (strict && a.entries.length == b.entries.length))
+        return false;
+
+    for (int64_t i = 0; i < Table$length(a); i++) {
+        void *found = Table$get_raw(b, GET_ENTRY(a, i), type);
+        if (!found) return false;
+    }
+    return true;
+}
+
+PUREFUNC public bool Table$is_superset_of(Table_t a, Table_t b, bool strict, const TypeInfo_t *type)
+{
+    return Table$is_subset_of(b, a, strict, type);
+}
+
+PUREFUNC public void *Table$str_get(Table_t t, const char *key)
+{
+    void **ret = Table$get(t, &key, &CStrToVoidStarTable);
+    return ret ? *ret : NULL;
+}
+
+PUREFUNC public void *Table$str_get_raw(Table_t t, const char *key)
+{
+    void **ret = Table$get_raw(t, &key, &CStrToVoidStarTable);
+    return ret ? *ret : NULL;
+}
+
+public void *Table$str_reserve(Table_t *t, const char *key, const void *value)
+{
+    return Table$reserve(t, &key, &value, &CStrToVoidStarTable);
+}
+
+public void Table$str_set(Table_t *t, const char *key, const void *value)
+{
+    Table$set(t, &key, &value, &CStrToVoidStarTable);
+}
+
+public void Table$str_remove(Table_t *t, const char *key)
+{
+    return Table$remove(t, &key, &CStrToVoidStarTable);
+}
+
+CONSTFUNC public void *Table$str_entry(Table_t t, int64_t n)
+{
+    return Table$entry(t, n);
+}
+
+PUREFUNC public bool Table$is_none(const void *obj, const TypeInfo_t*)
+{
+    return ((Table_t*)obj)->entries.length < 0;
+}
+
+public void Table$serialize(const void *obj, FILE *out, Table_t *pointers, const TypeInfo_t *type)
+{
+    Table_t *t = (Table_t*)obj;
+    int64_t len = t->entries.length;
+    Int64$serialize(&len, out, pointers, &Int64$info);
+
+    size_t offset = value_offset(type);
+    for (int64_t i = 0; i < len; i++) {
+        _serialize(t->entries.data + i*t->entries.stride, out, pointers, type->TableInfo.key);
+        _serialize(t->entries.data + i*t->entries.stride + offset, out, pointers, type->TableInfo.value);
+    }
+
+    Optional$serialize(&t->fallback, out, pointers, Optional$info(sizeof(void*), __alignof__(void*), Pointer$info("&", type)));
+}
+
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wstack-protector"
+public void Table$deserialize(FILE *in, void *outval, Array_t *pointers, const TypeInfo_t *type)
+{
+    int64_t len;
+    Int64$deserialize(in, &len, pointers, &Int$info);
+
+    Table_t t = {};
+    for (int64_t i = 0; i < len; i++) {
+        char key[type->TableInfo.key->size];
+        _deserialize(in, key, pointers, type->TableInfo.key);
+        char value[type->TableInfo.value->size];
+        _deserialize(in, value, pointers, type->TableInfo.value);
+        Table$set(&t, key, value, type);
+    }
+
+    Optional$deserialize(in, &t.fallback, pointers, Optional$info(sizeof(void*), __alignof__(void*), Pointer$info("&", type)));
+
+    *(Table_t*)outval = t;
+}
+#pragma GCC diagnostic pop
+
+// vim: ts=4 sw=0 et cino=L2,l1,(0,W4,m1