term: move the term core to subprojects/term

The core now builds, tests, and benchmarks alone, as a Meson subproject
with no dependency on the main tree.

- include/term/ holds term.h and the header-only unicode/. src/ holds
  the core and its private headers. The main tree gets only
  include/term through term_dep, so it cannot reach a private header.
- The term tests, the term benchmarks, the Kitty parser suite, and
  tools/amalgamate.py and tools/generate_unicode.py move with it. The
  tests run as term:<name>.
- The main build passes its -march (arch_flag) and b_ndebug to the
  subproject. A directory configured before this commit needs
  meson configure -Dterm:arch_flag=-march=... once.
- The term tests compile with -UNDEBUG. They do work inside assert.
- The subproject exports term_test_dep with term_api.h, for the main
  tree's render, thumbnail, color, and selection tests.
- The Kitty bridge used struct vector2i and has not compiled since the
  public API redesign. It builds again. 2 of its 14 tests fail: REP
  after a tab, and a cursor report after a resize.
- dirgraph.py drops the term and unicode layers. Its self-test uses pty.
- The symbols test ignores the __odr_asan symbols that ASan adds.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>

1 files changed, 380 insertions, 0 deletions

diff --git a/src/gstore.c b/src/gstore.c
new file mode 100644
index 0000000..c5109c6
--- /dev/null
+++ b/src/gstore.c
@@ -0,0 +1,380 @@
+#include "gstore.h"
+#include "internal.h"
+#include "screen.h"
+#include "unicode/grapheme.h"
+
+#include <stdlib.h>
+#include <string.h>
+
+#define GSTORE_MAX_ENTRIES 0x00FFFFFFu
+
+struct gentry {
+    union {
+        uint32_t offset;    /* Offset into arena for code points past index 1 */
+        uint32_t next_free; /* Next entry in free list (1-based, 0 = none) */
+    };
+    uint16_t len;           /* Number of code points */
+    bool mark;              /* Reachable in current GC sweep */
+    bool allocated;         /* True if actively holding a cluster */
+    uint32_t cp0;           /* First code point (inlined) */
+    uint32_t cp1;           /* Second code point (inlined) */
+};
+
+_Static_assert(sizeof(struct gentry) == 16,
+               "struct gentry must stay 16 bytes (4 entries per cache line)");
+
+struct gslot {
+    uint32_t hash;          /* 32-bit hash of cluster code points */
+    uint32_t entry_idx;     /* 1-based index into g->entries (0 = empty) */
+};
+
+struct gstore {
+    struct term *term;
+    uint32_t *arena;
+    size_t arena_len;
+    size_t arena_cap;
+
+    struct gentry *entries;
+    uint32_t entries_count;
+    uint32_t entries_cap;
+    uint32_t free_head; /* 1-based index, 0 = none */
+
+    uint32_t live_count;
+    uint32_t last_live;
+    uint32_t sweep_threshold;
+    uint32_t pin_depth;
+
+    struct gslot *slots;
+    size_t slot_count;
+};
+
+static uint64_t hash_cps(const uint32_t *cps, int len)
+{
+    uint64_t h = HASH64_BASIS;
+    for (int i = 0; i < len; i++)
+        h = hash64_step(h, cps[i]);
+    return hash64_finish(h);
+}
+
+static inline bool gentry_matches(const struct gstore *g, const struct gentry *e,
+                                  const uint32_t *cps, int n)
+{
+    if ((int)e->len != n)
+        return false;
+    if (e->cp0 != cps[0] || e->cp1 != cps[1])
+        return false;
+    if (n == 2)
+        return true;
+    return !memcmp(&g->arena[e->offset], &cps[2], (size_t)(n - 2) * sizeof(*cps));
+}
+
+int term_gstore_expand(const struct gstore *g, uint32_t handle, uint32_t *cps, int cap)
+{
+    if (cap <= 0)
+        return 0;
+    if (!g || !grapheme_is_handle(handle)) {
+        cps[0] = handle;
+        return 1;
+    }
+    uint32_t idx = handle - GRAPHEME_HANDLE_BASE;
+    if (idx >= g->entries_count || !g->entries[idx].allocated) {
+        cps[0] = 0xFFFD;
+        return 1;
+    }
+    const struct gentry *e = &g->entries[idx];
+    int n = (int)e->len;
+    if (n > cap) {
+        cps[0] = 0xFFFD;
+        return 1;
+    }
+    cps[0] = e->cp0;
+    cps[1] = e->cp1;
+    if (n > 2)
+        memcpy(&cps[2], &g->arena[e->offset], (size_t)(n - 2) * sizeof(*cps));
+    return n;
+}
+
+static void gstore_insert_slot(struct gstore *g, uint32_t h32, uint32_t entry_idx)
+{
+    uint32_t mask = (uint32_t)g->slot_count - 1;
+    uint32_t idx = h32 & mask;
+    for (uint32_t probe = 0; probe <= mask; probe++) {
+        struct gslot *slot = &g->slots[idx];
+        if (slot->entry_idx == 0) {
+            slot->hash = h32;
+            slot->entry_idx = entry_idx + 1;
+            return;
+        }
+        idx = (idx + 1) & mask;
+    }
+}
+
+static bool grow_slots(struct gstore *g)
+{
+    size_t want = g->slot_count ? g->slot_count * 2 : 256;
+    struct gslot *next = calloc(want, sizeof(*next));
+    if (!next)
+        return false;
+
+    free(g->slots);
+    g->slots = next;
+    g->slot_count = want;
+
+    for (uint32_t i = 0; i < g->entries_count; i++) {
+        struct gentry *e = &g->entries[i];
+        if (!e->allocated)
+            continue;
+        uint32_t cps_buf[GRAPHEME_MAX_LEN];
+        int n = term_gstore_expand(g, GRAPHEME_HANDLE_BASE + i, cps_buf, GRAPHEME_MAX_LEN);
+        uint64_t h = hash_cps(cps_buf, n);
+        uint32_t h32 = (uint32_t)h ? (uint32_t)h : 1;
+        gstore_insert_slot(g, h32, i);
+    }
+    return true;
+}
+
+static uint32_t gstore_find(const struct gstore *g, const uint32_t *cps, int n, uint32_t h32)
+{
+    if (!g->slots || g->slot_count == 0)
+        return 0;
+    uint32_t mask = (uint32_t)g->slot_count - 1;
+    uint32_t idx = h32 & mask;
+    for (uint32_t probe = 0; probe <= mask; probe++) {
+        const struct gslot *slot = &g->slots[idx];
+        if (slot->entry_idx == 0)
+            return 0;
+        if (slot->hash == h32) {
+            uint32_t e_idx = slot->entry_idx - 1;
+            const struct gentry *e = &g->entries[e_idx];
+            if (e->allocated && gentry_matches(g, e, cps, n))
+                return GRAPHEME_HANDLE_BASE + e_idx;
+        }
+        idx = (idx + 1) & mask;
+    }
+    return 0;
+}
+
+struct gstore *term_gstore_new(struct term *t)
+{
+    struct gstore *g = calloc(1, sizeof(*g));
+    if (!g)
+        return NULL;
+    g->term = t;
+    g->sweep_threshold = 1024;
+    return g;
+}
+
+void term_gstore_free(struct gstore *g)
+{
+    if (!g)
+        return;
+    free(g->arena);
+    free(g->entries);
+    free(g->slots);
+    free(g);
+}
+
+uint32_t term_gstore_count(const struct gstore *g)
+{
+    return g ? g->live_count : 0;
+}
+
+void term_gstore_pin(struct gstore *g)
+{
+    if (g)
+        g->pin_depth++;
+}
+
+void term_gstore_unpin(struct gstore *g)
+{
+    if (g && g->pin_depth > 0)
+        g->pin_depth--;
+}
+
+void term_gstore_mark(struct gstore *g, uint32_t handle)
+{
+    if (!g || !grapheme_is_handle(handle))
+        return;
+    uint32_t idx = handle - GRAPHEME_HANDLE_BASE;
+    if (idx < g->entries_count && g->entries[idx].allocated)
+        g->entries[idx].mark = true;
+}
+
+static void sweep_mark_row(struct gstore *g, const struct cell *cells, int len)
+{
+    for (int x = 0; x < len; x++) {
+        uint32_t c = cells[x].c;
+        if (grapheme_is_handle(c))
+            term_gstore_mark(g, c);
+    }
+}
+
+void term_gstore_sweep(struct gstore *g, struct term *t)
+{
+    if (!g)
+        return;
+
+    if (t) {
+        if (grapheme_is_handle(t->last_char))
+            term_gstore_mark(g, t->last_char);
+
+        struct screen *s = &t->scr;
+        for (int y = 0; y < s->rows; y++) {
+            struct srow *row = screen_get_row(s, y);
+            if (row && row->kind == ROW_CELLS && row->len > 0)
+                sweep_mark_row(g, row->cells, (int)row->len);
+        }
+        if (t->alternate && t->alt_allocated) {
+            struct screen *as = &t->alt_scr;
+            for (int y = 0; y < as->rows; y++) {
+                struct srow *row = screen_get_row(as, y);
+                if (row && row->kind == ROW_CELLS && row->len > 0)
+                    sweep_mark_row(g, row->cells, (int)row->len);
+            }
+        }
+    }
+
+    /* Compact the code point arena for clusters with n > 2. */
+    uint32_t new_arena_len = 0;
+    uint32_t *packed = g->arena ? malloc(g->arena_cap * sizeof(*packed)) : NULL;
+    if (packed) {
+        for (uint32_t i = 0; i < g->entries_count; i++) {
+            struct gentry *e = &g->entries[i];
+            if (e->allocated && e->mark && e->len > 2) {
+                size_t extra = (size_t)(e->len - 2);
+                memcpy(&packed[new_arena_len], &g->arena[e->offset],
+                       extra * sizeof(*packed));
+                e->offset = new_arena_len;
+                new_arena_len += (uint32_t)extra;
+            }
+        }
+        free(g->arena);
+        g->arena = packed;
+        g->arena_len = new_arena_len;
+    }
+
+    /* Rebuild open-addressing slot table and free list. */
+    g->free_head = 0;
+    uint32_t live = 0;
+    if (g->slots)
+        memset(g->slots, 0, g->slot_count * sizeof(*g->slots));
+
+    for (uint32_t i = 0; i < g->entries_count; i++) {
+        struct gentry *e = &g->entries[i];
+        if (e->allocated) {
+            if (e->mark) {
+                live++;
+                e->mark = false;
+                if (g->slots) {
+                    uint32_t cps_buf[GRAPHEME_MAX_LEN];
+                    int n = term_gstore_expand(g, GRAPHEME_HANDLE_BASE + i, cps_buf, GRAPHEME_MAX_LEN);
+                    uint64_t h = hash_cps(cps_buf, n);
+                    uint32_t h32 = (uint32_t)h ? (uint32_t)h : 1;
+                    gstore_insert_slot(g, h32, i);
+                }
+            } else {
+                e->allocated = false;
+                e->len = 0;
+                e->offset = 0;
+                e->cp0 = 0;
+                e->cp1 = 0;
+                e->next_free = g->free_head;
+                g->free_head = i + 1;
+            }
+        } else {
+            e->next_free = g->free_head;
+            g->free_head = i + 1;
+        }
+    }
+
+    g->live_count = live;
+    g->last_live = live;
+    g->sweep_threshold = live * 2;
+    if (g->sweep_threshold < 1024)
+        g->sweep_threshold = 1024;
+}
+
+uint32_t term_gstore_intern(struct gstore *g, const uint32_t *cps, int n)
+{
+    if (!g || n <= 0)
+        return 0;
+    if (n == 1)
+        return cps[0];
+    if (n > GRAPHEME_MAX_LEN)
+        n = GRAPHEME_MAX_LEN;
+
+    uint64_t h = hash_cps(cps, n);
+    uint32_t h32 = (uint32_t)h ? (uint32_t)h : 1;
+
+    uint32_t existing = gstore_find(g, cps, n, h32);
+    if (existing)
+        return existing;
+
+    if (g->term && g->pin_depth == 0 &&
+        (g->live_count >= g->sweep_threshold ||
+         g->live_count >= GSTORE_MAX_ENTRIES)) {
+        term_gstore_sweep(g, g->term);
+        existing = gstore_find(g, cps, n, h32);
+        if (existing)
+            return existing;
+    }
+
+    if (!g->slots || (g->live_count + 1) * 2 > g->slot_count) {
+        if (!grow_slots(g) && !g->slots)
+            return cps[0];
+    }
+
+    uint32_t entry_idx;
+    if (g->free_head) {
+        entry_idx = g->free_head - 1;
+        g->free_head = g->entries[entry_idx].next_free;
+    } else {
+        if (g->entries_count >= GSTORE_MAX_ENTRIES)
+            return cps[0];
+        if (g->entries_count == g->entries_cap) {
+            size_t new_cap = g->entries_cap ? (size_t)g->entries_cap * 2 : 128;
+            if (new_cap > GSTORE_MAX_ENTRIES)
+                new_cap = GSTORE_MAX_ENTRIES;
+            struct gentry *next = realloc(g->entries, new_cap * sizeof(*next));
+            if (!next)
+                return cps[0];
+            g->entries = next;
+            g->entries_cap = (uint32_t)new_cap;
+        }
+        entry_idx = g->entries_count++;
+    }
+
+    struct gentry *e = &g->entries[entry_idx];
+    e->cp0 = cps[0];
+    e->cp1 = cps[1];
+    e->len = (uint16_t)n;
+    e->mark = false;
+    e->allocated = true;
+    e->offset = 0;
+
+    if (n > 2) {
+        size_t extra = (size_t)(n - 2);
+        if (g->arena_len + extra > g->arena_cap) {
+            size_t new_cap = g->arena_cap ? g->arena_cap * 2 : 512;
+            while (new_cap < g->arena_len + extra)
+                new_cap *= 2;
+            uint32_t *next = realloc(g->arena, new_cap * sizeof(*next));
+            if (!next) {
+                e->allocated = false;
+                e->next_free = g->free_head;
+                g->free_head = entry_idx + 1;
+                return cps[0];
+            }
+            g->arena = next;
+            g->arena_cap = new_cap;
+        }
+        uint32_t off = (uint32_t)g->arena_len;
+        memcpy(&g->arena[off], &cps[2], extra * sizeof(*cps));
+        g->arena_len += extra;
+        e->offset = off;
+    }
+
+    gstore_insert_slot(g, h32, entry_idx);
+    g->live_count++;
+    return GRAPHEME_HANDLE_BASE + entry_idx;
+}