kit

type.c (40739B)

---

 /* C type construction.
  *
  * Types are interned per-Pool: a single `type_void(pool)` returns the same
  * Type* on every call against the same pool, and structurally-equal calls
  * to type_prim/type_ptr/type_func collapse to the same Type*. The cache is
  * a small open structure stored through Pool.type_cache (opaque to other
  * consumers).
  *
  * Storage: every Type and every supporting array (TY_FUNC param vectors,
  * TY_STRUCT field arrays) is allocated from the Pool's arena, so pointers
  * are stable for the Pool's lifetime.
  *
  * v1 covers what the cg test harness drives:
  *   void / scalars / pointer / function / struct / union
  * Other constructors (array, qualified, enum) and predicates have minimal
  * implementations sufficient for the cg test surface; they will grow with
  * the parser. */
 
 #include "type/type.h"
 
 #include <stdint.h>
 #include <string.h>
 
 #define NUM_PRIM_KINDS ((unsigned)TY_LDOUBLE + 1u)
 
 typedef struct TypeListNode TypeListNode;
 struct TypeListNode {
   TypeListNode* next;
   Type ty;
 };
 
 static u32 type_fnv_ptr(u32 h, const void* q) {
   u64 u = (u64)(uintptr_t)q;
   h = (h ^ (u32)u) * 16777619u;
   h = (h ^ (u32)(u >> 32)) * 16777619u;
   return h;
 }
 
 /* Structural hash + equality over a (non-tagged) derived type's identity
  * fields. These hash-cons TY_PTR / TY_ARRAY / TY_FUNC and qualified variants of
  * non-tagged types: two independently built `int*` Types hash and compare equal
  * and so collapse to one canonical node. They compare fields, never raw bytes,
  * so a structural node's union tail and padding may stay uninitialized. */
 static u32 type_struct_hash(const Type* t) {
   u32 h = 2166136261u;
   h = (h ^ (u32)t->kind) * 16777619u;
   h = (h ^ (u32)t->qual) * 16777619u;
   switch (t->kind) {
     case TY_PTR:
       h = type_fnv_ptr(h, t->ptr.pointee);
       break;
     case TY_ARRAY:
       h = type_fnv_ptr(h, t->arr.elem);
       h = (h ^ t->arr.count) * 16777619u;
       h = (h ^ (u32)t->arr.incomplete) * 16777619u;
       break;
     case TY_FUNC: {
       u16 i;
       h = type_fnv_ptr(h, t->fn.ret);
       h = (h ^ (u32)t->fn.nparams) * 16777619u;
       h = (h ^ (u32)t->fn.variadic) * 16777619u;
       for (i = 0; i < t->fn.nparams; ++i) h = type_fnv_ptr(h, t->fn.params[i]);
       break;
     }
     default: /* qualified primitive: kind + qual is the whole key */
       break;
   }
   return h;
 }
 
 static int type_struct_eq(const Type* a, const Type* b) {
   if (a->kind != b->kind || a->qual != b->qual) return 0;
   switch (a->kind) {
     case TY_PTR:
       return a->ptr.pointee == b->ptr.pointee;
     case TY_ARRAY:
       return a->arr.elem == b->arr.elem && a->arr.count == b->arr.count &&
              a->arr.incomplete == b->arr.incomplete;
     case TY_FUNC: {
       u16 i;
       if (a->fn.ret != b->fn.ret || a->fn.nparams != b->fn.nparams ||
           a->fn.variadic != b->fn.variadic)
         return 0;
       for (i = 0; i < a->fn.nparams; ++i)
         if (a->fn.params[i] != b->fn.params[i]) return 0;
       return 1;
     }
     default: /* qualified primitive: kind + qual already matched */
       return 1;
   }
 }
 
 /* Structural intern SET: the canonical Type* IS the stored element and
  * membership is decided structurally (type_struct_eq) — which a scalar
  * key->value map cannot express, hence KIT_HASHSET_DEFINE. Interns
  * ptr/array/func + qualified non-tagged types; tagged types are interned by
  * declaration identity on `derived` and never enter this set. Replaces the
  * former O(types) linear scan of one flat derived list (which made each
  * derivation O(types) → type construction O(types^2)). */
 KIT_HASHSET_DEFINE(TypeInternSet, const Type*, type_struct_hash,
                    type_struct_eq);
 
 /* Completed record layout id, keyed by record identity. A record's identity is
  * its tag id (same_record_type is tag-id equality), so a plain u32->id map
  * captures it; the Pool is 1:1 with a compiler so no compiler key is needed.
  * Replaces the former per-lookup list scan (O(records^2) for record-heavy TUs).
  * Tag id 0 (TAG_NONE) never names a stored record, so it is safe as the empty
  * key sentinel. */
 KIT_HASHMAP_DEFINE(CgRecordMap, u32, KitCgTypeId, kit_hash_u32);
 
 static inline u32 type_ptr_hash(const Type* t) {
   return kit_hash_u64((uint64_t)(uintptr_t)t);
 }
 
 /* Canonical-unqualified Type* memo, keyed by the qualified Type*. Collapses the
  * O(derived) linear scan type_unqual runs for a complete tagged type (the hot
  * const-record path) to one lookup. Only stable answers are inserted (a
  * complete record's unqualified node never changes); incomplete/enum results
  * are left uncached because they can still change as a forward record
  * completes. */
 KIT_HASHMAP_DEFINE(CgUnqualMemo, const Type*, const Type*, type_ptr_hash);
 
 typedef struct PoolTypeCache {
   /* Direct slots for void + primitive kinds (TY_VOID..TY_LDOUBLE). */
   const Type* prim[NUM_PRIM_KINDS];
   /* Structurally-interned ptr/array/func + qualified non-tagged types. */
   TypeInternSet structural;
   /* Identity-interned tagged types (struct/union/enum, qualified or not) and
    * the throwaway record-builder results: a list, scanned only by the (rare)
    * tag-based type_qualified / type_unqual paths and never per derivation. */
   TypeListNode* derived;
   /* Completed record layout ids, keyed by tag id. */
   CgRecordMap cg_records;
   /* Records whose CG completion is currently in flight, keyed by tag id ->
    * decl id. Self-/mutually-recursive records reach themselves through a
    * pointer field mid-completion; this lets type_cg_record_layout hand back the
    * still-incomplete decl id (a pointer to an incomplete record is legal)
    * instead of recursing into a second completion of the same record. */
   CgRecordMap cg_records_completing;
   /* Canonical-unqualified node per qualified Type* (stable answers only). */
   CgUnqualMemo unqual;
   /* Tag id allocator (1-based; TAG_NONE = 0). */
   u32 next_tag;
 } PoolTypeCache;
 
 static PoolTypeCache* cache_get(Pool* p) {
   PoolTypeCache* c = (PoolTypeCache*)p->type_cache;
   if (c) return c;
   c = arena_new(p->arena, PoolTypeCache);
   if (!c) return NULL;
   memset(c, 0, sizeof *c);
   c->next_tag = 1;
   /* Both tables run on the pool's arena-heap facade: a resize orphans the old
    * array into the arena (reclaimed wholesale at teardown), so no fini hook is
    * needed. Lazy (cap 0): the first insert allocates. */
   TypeInternSet_init_cap(&c->structural, &p->arena_heap, 0);
   CgRecordMap_init_cap(&c->cg_records, &p->arena_heap, 0);
   CgRecordMap_init_cap(&c->cg_records_completing, &p->arena_heap, 0);
   CgUnqualMemo_init_cap(&c->unqual, &p->arena_heap, 0);
   p->type_cache = c;
   return c;
 }
 
 static Type* alloc_type_node(Pool* p, PoolTypeCache* c) {
   TypeListNode* n = arena_new(p->arena, TypeListNode);
   if (!n) return NULL;
   memset(n, 0, sizeof *n);
   n->next = c->derived;
   c->derived = n;
   return &n->ty;
 }
 
 /* Bare structural-type node: arena-allocated, NOT linked into `derived`, NOT
  * zeroed. Each constructor writes exactly the fields its kind reads; the
  * structural set compares those fields (not raw bytes), so the union tail and
  * padding may stay uninitialized. */
 static Type* alloc_struct_type(Pool* p) {
   Type* t = arena_new(p->arena, Type);
   /* cg_id is read before structural fields, so initialize it even though the
    * union tail is intentionally left undefined (see the header). Qualified /
    * unqual paths that do `*t = *base` inherit the cache, which is correct since
    * lowering ignores qualifiers today. */
   if (t) t->cg_id = KIT_CG_TYPE_NONE;
   return t;
 }
 
 const Type* type_void(Pool* p) { return type_prim(p, TY_VOID); }
 
 const Type* type_prim(Pool* p, TypeKind kind) {
   PoolTypeCache* c = cache_get(p);
   if (!c) return NULL;
   if ((unsigned)kind >= NUM_PRIM_KINDS) return NULL;
   if (c->prim[kind]) return c->prim[kind];
   Type* t = alloc_type_node(p, c);
   if (!t) return NULL;
   t->kind = (u16)kind;
   t->qual = 0;
   c->prim[kind] = t;
   return t;
 }
 
 const Type* type_ptr(Pool* p, const Type* pointee) {
   PoolTypeCache* c = cache_get(p);
   Type probe;
   const Type* found;
   Type* t;
   if (!c) return NULL;
   probe.kind = TY_PTR;
   probe.qual = 0;
   probe.ptr.pointee = pointee;
   found = TypeInternSet_find(&c->structural, &probe);
   if (found) return found;
   t = alloc_struct_type(p);
   if (!t) return NULL;
   t->kind = TY_PTR;
   t->qual = 0;
   t->ptr.pointee = pointee;
   TypeInternSet_add(&c->structural, t);
   return t;
 }
 
 const Type* type_array(Pool* p, const Type* elem, u32 count, int incomplete) {
   PoolTypeCache* c = cache_get(p);
   Type probe;
   const Type* found;
   Type* t;
   if (!c) return NULL;
   probe.kind = TY_ARRAY;
   probe.qual = 0;
   probe.arr.elem = elem;
   probe.arr.count = count;
   probe.arr.incomplete = (u8)(incomplete ? 1 : 0);
   found = TypeInternSet_find(&c->structural, &probe);
   if (found) return found;
   t = alloc_struct_type(p);
   if (!t) return NULL;
   t->kind = TY_ARRAY;
   t->qual = 0;
   t->arr.elem = elem;
   t->arr.count = count;
   t->arr.incomplete = (u8)(incomplete ? 1 : 0);
   TypeInternSet_add(&c->structural, t);
   return t;
 }
 
 const Type* type_func(Pool* p, const Type* ret, const Type** params, u16 n,
                       int variadic) {
   PoolTypeCache* c = cache_get(p);
   Type probe;
   const Type* found;
   Type* t;
   if (!c) return NULL;
   /* Borrow the caller's params array for the lookup; type_struct_eq compares it
    * element-wise. Only on a miss do we allocate a persistent copy. */
   probe.kind = TY_FUNC;
   probe.qual = 0;
   probe.fn.ret = ret;
   probe.fn.params = params;
   probe.fn.nparams = n;
   probe.fn.variadic = (u8)(variadic ? 1 : 0);
   found = TypeInternSet_find(&c->structural, &probe);
   if (found) return found;
   t = alloc_struct_type(p);
   if (!t) return NULL;
   t->kind = TY_FUNC;
   t->qual = 0;
   t->fn.ret = ret;
   t->fn.nparams = n;
   t->fn.variadic = (u8)(variadic ? 1 : 0);
   if (n) {
     const Type** dst = arena_array(p->arena, const Type*, n);
     if (!dst) return NULL;
     for (u16 i = 0; i < n; ++i) dst[i] = params[i];
     t->fn.params = dst;
   } else {
     t->fn.params = NULL;
   }
   TypeInternSet_add(&c->structural, t);
   return t;
 }
 
 /* Semantic identity of a tagged type for interning: kind + qual + the rec/enm
  * identity payload. Replaces a memcmp over sizeof(Type) — which worked only
  * because every tagged node carries zeroed padding (alloc_type_node memsets and
  * struct assignment propagates it), a latent footgun that also forced the
  * lowered-id cache off the node onto a side map. `incomplete` is part of the
  * key (unlike type_compatible) because the qualified-snapshot model keeps an
  * incomplete and a later-completed `const struct S` as distinct nodes. `n` is
  * an interned node; `base` + the wanted `qual` describe the target (the payload
  * is base's). */
 static int type_tagged_eq(const Type* n, const Type* base, u16 qual) {
   if (n->kind != base->kind || n->qual != qual) return 0;
   switch ((TypeKind)base->kind) {
     case TY_STRUCT:
     case TY_UNION:
       return n->rec.tag_id == base->rec.tag_id && n->rec.tag == base->rec.tag &&
              n->rec.fields == base->rec.fields &&
              n->rec.nfields == base->rec.nfields &&
              n->rec.incomplete == base->rec.incomplete &&
              n->rec.packed == base->rec.packed &&
              n->rec.max_align == base->rec.max_align &&
              n->rec.align_override == base->rec.align_override;
     case TY_ENUM:
       return n->enm.tag_id == base->enm.tag_id && n->enm.tag == base->enm.tag &&
              n->enm.base == base->enm.base;
     default:
       return 0;
   }
 }
 
 const Type* type_qualified(Pool* p, const Type* base, u16 qual) {
   PoolTypeCache* c;
   Type* t;
   if (!base || qual == 0) return base;
   c = cache_get(p);
   if (!c) return NULL;
   if (base->kind == TY_STRUCT || base->kind == TY_UNION ||
       base->kind == TY_ENUM) {
     /* Tagged types are identity-interned on `derived` by semantic payload
      * (type_tagged_eq), not a raw-byte compare. */
     for (TypeListNode* n = c->derived; n; n = n->next) {
       if (type_tagged_eq(&n->ty, base, qual)) return &n->ty;
     }
     t = alloc_type_node(p, c);
     if (!t) return NULL;
     *t = *base;
     t->qual = qual;
     return t;
   }
   /* Non-tagged: structurally interned (qualified prim / ptr / array / func). */
   {
     Type probe = *base;
     const Type* found;
     probe.qual = qual;
     found = TypeInternSet_find(&c->structural, &probe);
     if (found) return found;
     t = alloc_struct_type(p);
     if (!t) return NULL;
     *t = *base;
     t->qual = qual;
     TypeInternSet_add(&c->structural, t);
     return t;
   }
 }
 
 /* ---- aggregates ---- */
 
 struct TypeRecordBuilder {
   Pool* pool;
   TypeKind kind; /* TY_STRUCT or TY_UNION */
   TagId tag_id;
   Sym tag;
   Field* fields;
   u32 nfields;
   u32 cap;
   TypeRecordOpts opts;
 };
 
 TagId type_tag_new(Pool* p, TagDeclKind kind, Sym spelling, SrcLoc loc) {
   PoolTypeCache* c = cache_get(p);
   if (!c) return TAG_NONE;
   (void)kind;
   (void)spelling;
   (void)loc;
   return (TagId)(c->next_tag++);
 }
 
 TypeRecordBuilder* type_record_begin(Pool* p, TypeKind kind, TagId tag_id,
                                      Sym tag) {
   TypeRecordOpts opts;
   memset(&opts, 0, sizeof opts);
   return type_record_begin_ex(p, kind, tag_id, tag, opts);
 }
 
 TypeRecordBuilder* type_record_begin_ex(Pool* p, TypeKind kind, TagId tag_id,
                                         Sym tag, TypeRecordOpts opts) {
   TypeRecordBuilder* b = arena_new(p->arena, TypeRecordBuilder);
   if (!b) return NULL;
   memset(b, 0, sizeof *b);
   b->pool = p;
   b->kind = kind;
   b->tag_id = tag_id;
   b->tag = tag;
   b->opts = opts;
   return b;
 }
 
 void type_record_field(TypeRecordBuilder* b, Field f) {
   if (b->nfields == b->cap) {
     u32 nc = b->cap ? b->cap * 2 : 4;
     Field* nf = arena_array(b->pool->arena, Field, nc);
     if (!nf) return;
     if (b->fields) memcpy(nf, b->fields, sizeof(Field) * b->nfields);
     b->fields = nf;
     b->cap = nc;
   }
   b->fields[b->nfields++] = f;
 }
 
 const Type* type_record_end(Pool* p, TypeRecordBuilder* b) {
   PoolTypeCache* c = cache_get(p);
   if (!c) return NULL;
   Type* t = alloc_type_node(p, c);
   if (!t) return NULL;
   t->kind = (u16)b->kind;
   t->qual = 0;
   t->rec.tag_id = b->tag_id;
   t->rec.tag = b->tag;
   t->rec.fields = b->fields;
   t->rec.nfields = (u16)b->nfields;
   t->rec.incomplete = 0;
   t->rec.packed = b->opts.packed;
   t->rec.max_align = b->opts.max_align;
   t->rec.align_override = b->opts.align_override;
   return t;
 }
 
 Type* type_record_forward(Pool* p, TypeKind kind, TagId tag_id, Sym tag) {
   PoolTypeCache* c = cache_get(p);
   if (!c) return NULL;
   Type* t = alloc_type_node(p, c);
   if (!t) return NULL;
   t->kind = (u16)kind;
   t->qual = 0;
   t->rec.tag_id = tag_id;
   t->rec.tag = tag;
   t->rec.fields = NULL;
   t->rec.nfields = 0;
   t->rec.incomplete = 1;
   t->rec.packed = 0;
   t->rec.max_align = 0;
   t->rec.align_override = 0;
   return t;
 }
 
 void type_record_install(Type* forward, const Field* fields, u16 nfields) {
   if (!forward) return;
   forward->rec.fields = fields;
   forward->rec.nfields = nfields;
   forward->rec.incomplete = 0;
 }
 
 const Type* type_enum(Pool* p, TagId tag_id, Sym tag, const Type* base) {
   PoolTypeCache* c = cache_get(p);
   if (!c) return NULL;
   Type* t = alloc_type_node(p, c);
   if (!t) return NULL;
   t->kind = TY_ENUM;
   t->qual = 0;
   t->enm.tag_id = tag_id;
   t->enm.tag = tag;
   t->enm.base = base;
   return t;
 }
 
 /* ---- predicates / utilities ---- */
 
 const Type* type_unqual(Pool* p, const Type* t) {
   PoolTypeCache* c;
   Type* nt;
   if (!t || t->qual == 0) return t;
   if ((unsigned)t->kind < NUM_PRIM_KINDS)
     return type_prim(p, (TypeKind)t->kind);
   c = cache_get(p);
   if (!c) return NULL;
   if (t->kind == TY_STRUCT || t->kind == TY_UNION || t->kind == TY_ENUM) {
     /* Tagged types are identity-interned on `derived`. */
     if ((t->kind == TY_STRUCT || t->kind == TY_UNION) &&
         t->rec.tag_id != TAG_NONE) {
       /* The only memoized case: a complete record's unqualified node is fixed
        * for the pool's lifetime, so this O(derived) scan can be skipped after
        * the first hit. The memo holds only struct/union entries, so it is
        * consulted here rather than taxing the (single-hash) non-tagged path. */
       const Type* const* hit = CgUnqualMemo_get(&c->unqual, t);
       if (hit) return *hit;
       for (TypeListNode* n = c->derived; n; n = n->next) {
         if (n->ty.kind == t->kind && n->ty.qual == 0 &&
             n->ty.rec.tag_id == t->rec.tag_id && !n->ty.rec.incomplete) {
           /* The incomplete/enum fall-throughs below stay uncached — their
            * result can still change as a forward record completes. */
           CgUnqualMemo_set(&c->unqual, t, &n->ty);
           return &n->ty;
         }
       }
     }
     for (TypeListNode* n = c->derived; n; n = n->next) {
       if (type_tagged_eq(&n->ty, t, 0)) return &n->ty;
     }
     nt = alloc_type_node(p, c);
     if (!nt) return NULL;
     *nt = *t;
     nt->qual = 0;
     return nt;
   }
   /* Non-tagged: structurally interned (qualified prim is handled above as a
    * prim; here that leaves ptr / array / func). */
   {
     Type probe = *t;
     const Type* found;
     probe.qual = 0;
     found = TypeInternSet_find(&c->structural, &probe);
     if (found) return found;
     nt = alloc_struct_type(p);
     if (!nt) return NULL;
     *nt = *t;
     nt->qual = 0;
     TypeInternSet_add(&c->structural, nt);
     return nt;
   }
 }
 
 const Type* type_promoted(Pool* p, const Type* t) {
   if (!t) return t;
   switch (t->kind) {
     case TY_BOOL:
     case TY_CHAR:
     case TY_SCHAR:
     case TY_UCHAR:
     case TY_SHORT:
     case TY_USHORT:
       return type_prim(p, TY_INT);
     default:
       return t;
   }
 }
 
 static int type_compatible_inner(const Type* a, const Type* b, unsigned depth) {
   u16 i;
   if (depth > 64) return 0;
   if (a == b) return 1;
   if (!a || !b) return 0;
   if (a->qual != b->qual) return 0;
   if (a->kind != b->kind) return 0;
   switch (a->kind) {
     case TY_VOID:
     case TY_BOOL:
     case TY_CHAR:
     case TY_SCHAR:
     case TY_UCHAR:
     case TY_SHORT:
     case TY_USHORT:
     case TY_INT:
     case TY_UINT:
     case TY_LONG:
     case TY_ULONG:
     case TY_LLONG:
     case TY_ULLONG:
     case TY_INT128:
     case TY_UINT128:
     case TY_FLOAT:
     case TY_DOUBLE:
     case TY_LDOUBLE:
       return 1;
     case TY_PTR:
       return type_compatible_inner(a->ptr.pointee, b->ptr.pointee, depth + 1);
     case TY_ARRAY:
       if (!type_compatible_inner(a->arr.elem, b->arr.elem, depth + 1)) return 0;
       if (a->arr.incomplete || b->arr.incomplete) return 1;
       return a->arr.count == b->arr.count;
     case TY_FUNC:
       if (a->fn.variadic != b->fn.variadic) return 0;
       if (a->fn.nparams != b->fn.nparams) return 0;
       if (!type_compatible_inner(a->fn.ret, b->fn.ret, depth + 1)) return 0;
       for (i = 0; i < a->fn.nparams; ++i) {
         if (!type_compatible_inner(a->fn.params[i], b->fn.params[i], depth + 1))
           return 0;
       }
       return 1;
     case TY_STRUCT:
     case TY_UNION:
       return a->rec.tag_id != TAG_NONE && a->rec.tag_id == b->rec.tag_id;
     case TY_ENUM:
       if (a->enm.tag_id != TAG_NONE || b->enm.tag_id != TAG_NONE)
         return a->enm.tag_id == b->enm.tag_id;
       return type_compatible_inner(a->enm.base, b->enm.base, depth + 1);
     default:
       return 0;
   }
 }
 
 int type_compatible(const Type* a, const Type* b) {
   return type_compatible_inner(a, b, 0);
 }
 
 const Type* type_composite(Pool* p, const Type* a, const Type* b) {
   const Type* elem;
   const Type** params;
   u16 i;
   if (!type_compatible(a, b)) return NULL;
   if (a == b) return a;
   if (!a || !b) return NULL;
   switch (a->kind) {
     case TY_ARRAY:
       elem = type_composite(p, a->arr.elem, b->arr.elem);
       if (!elem) elem = a->arr.elem;
       if (a->arr.incomplete && !b->arr.incomplete)
         return type_array(p, elem, b->arr.count, 0);
       if (b->arr.incomplete && !a->arr.incomplete)
         return type_array(p, elem, a->arr.count, 0);
       return type_array(p, elem, a->arr.count, a->arr.incomplete);
     case TY_PTR: {
       const Type* pointee = type_composite(p, a->ptr.pointee, b->ptr.pointee);
       if (!pointee) pointee = a->ptr.pointee;
       /* Preserve the pointer's own qualifiers (e.g. the inner `const` of
        * `const char* const*`); type_ptr alone yields an unqualified pointer. */
       return type_qualified(p, type_ptr(p, pointee), a->qual);
     }
     case TY_FUNC:
       if (a->fn.nparams == 0) return a;
       params = arena_array(p->arena, const Type*, a->fn.nparams);
       if (!params) return NULL;
       for (i = 0; i < a->fn.nparams; ++i) {
         params[i] = type_composite(p, a->fn.params[i], b->fn.params[i]);
         if (!params[i]) params[i] = a->fn.params[i];
       }
       return type_func(p, type_composite(p, a->fn.ret, b->fn.ret), params,
                        a->fn.nparams, a->fn.variadic);
     default:
       return a;
   }
 }
 
 /* Single source of truth for per-TypeKind scalar facts. Indexed directly by
  * TypeKind (sized to TY_ENUM + 1); the aggregate kinds PTR/ARRAY/FUNC/STRUCT/
  * UNION are zero-filled holes. Columns:
  *   is_signed  - signed integer (drives sign-extension / signed cg ops)
  *   is_int     - integer type (bool/char/.../enum)
  *   is_fp      - floating-point type
  *   rank       - C integer conversion rank (0 for non-integers)
  *   uvariant   - corresponding unsigned TypeKind (TY_UINT for non-integers,
  *                matching the historical default)
  * Accessors below read this table instead of re-enumerating the kinds. */
 typedef struct TypeKindProps {
   u8 is_signed;
   u8 is_int;
   u8 is_fp;
   u8 rank;
   u8 uvariant; /* TypeKind */
 } TypeKindProps;
 
 static const TypeKindProps kTypeKindProps[TY_ENUM + 1] = {
     [TY_VOID] = {0, 0, 0, 0, TY_UINT},
     [TY_BOOL] = {0, 1, 0, 1, TY_UINT},
     [TY_CHAR] = {1, 1, 0, 2, TY_UINT},
     [TY_SCHAR] = {1, 1, 0, 2, TY_UINT},
     [TY_UCHAR] = {0, 1, 0, 2, TY_UINT},
     [TY_SHORT] = {1, 1, 0, 3, TY_UINT},
     [TY_USHORT] = {0, 1, 0, 3, TY_UINT},
     [TY_INT] = {1, 1, 0, 4, TY_UINT},
     [TY_UINT] = {0, 1, 0, 4, TY_UINT},
     [TY_LONG] = {1, 1, 0, 5, TY_ULONG},
     [TY_ULONG] = {0, 1, 0, 5, TY_ULONG},
     [TY_LLONG] = {1, 1, 0, 6, TY_ULLONG},
     [TY_ULLONG] = {0, 1, 0, 6, TY_ULLONG},
     [TY_INT128] = {1, 1, 0, 7, TY_UINT128},
     [TY_UINT128] = {0, 1, 0, 7, TY_UINT128},
     [TY_FLOAT] = {0, 0, 1, 0, TY_UINT},
     [TY_DOUBLE] = {0, 0, 1, 0, TY_UINT},
     [TY_LDOUBLE] = {0, 0, 1, 0, TY_UINT},
     /* PTR/ARRAY/FUNC/STRUCT/UNION: zero-filled holes (uvariant 0 == TY_VOID
      * is never read for non-integers; callers map non-int to TY_UINT). */
     [TY_ENUM] = {1, 1, 0, 4, TY_UINT},
 };
 
 static const TypeKindProps* type_kind_props(TypeKind k) {
   if ((unsigned)k > (unsigned)TY_ENUM) return &kTypeKindProps[TY_VOID];
   return &kTypeKindProps[k];
 }
 
 int type_kind_is_int(TypeKind k) { return type_kind_props(k)->is_int; }
 int type_kind_is_fp(TypeKind k) { return type_kind_props(k)->is_fp; }
 int type_kind_is_signed_integer(TypeKind k) {
   return type_kind_props(k)->is_signed;
 }
 u32 type_kind_int_rank(TypeKind k) { return type_kind_props(k)->rank; }
 TypeKind type_kind_unsigned_variant(TypeKind k) {
   const TypeKindProps* p = type_kind_props(k);
   return p->is_int ? (TypeKind)p->uvariant : TY_UINT;
 }
 
 int type_is_int(const Type* t) {
   return t ? type_kind_is_int((TypeKind)t->kind) : 0;
 }
 
 int type_is_arith(const Type* t) {
   if (!t) return 0;
   return type_kind_is_int((TypeKind)t->kind) ||
          type_kind_is_fp((TypeKind)t->kind);
 }
 
 int type_is_ptr(const Type* t) { return t && t->kind == TY_PTR; }
 
 int type_is_signed_integer(const Type* t) {
   return t ? type_kind_is_signed_integer((TypeKind)t->kind) : 0;
 }
 
 static KitCgTypeId type_cg_builtin(KitCompiler* c, TypeKind kind) {
   /* Hot path: one builtin id per query, no whole-table copy. The target spec
    * (a by-value struct) is only consulted for the two data-model-dependent
    * widths, so it is fetched lazily inside those cases rather than per call. */
   switch (kind) {
     case TY_VOID:
       return kit_cg_type_builtin(c, KIT_CG_BUILTIN_VOID);
     case TY_BOOL:
       return kit_cg_type_builtin(c, KIT_CG_BUILTIN_BOOL);
     case TY_CHAR:
     case TY_SCHAR:
     case TY_UCHAR:
       return kit_cg_type_builtin(c, KIT_CG_BUILTIN_I8);
     case TY_SHORT:
     case TY_USHORT:
       return kit_cg_type_builtin(c, KIT_CG_BUILTIN_I16);
     case TY_INT:
     case TY_UINT:
       return kit_cg_type_builtin(c, KIT_CG_BUILTIN_I32);
     case TY_LONG:
     case TY_ULONG:
       return kit_cg_type_builtin(
           c, kit_target_uses_lp64(kit_compiler_target_spec(c))
                  ? KIT_CG_BUILTIN_I64
                  : KIT_CG_BUILTIN_I32);
     case TY_LLONG:
     case TY_ULLONG:
       return kit_cg_type_builtin(c, KIT_CG_BUILTIN_I64);
     case TY_INT128:
     case TY_UINT128:
       return kit_cg_type_builtin(c, KIT_CG_BUILTIN_I128);
     case TY_FLOAT:
       return kit_cg_type_builtin(c, KIT_CG_BUILTIN_F32);
     case TY_DOUBLE:
       return kit_cg_type_builtin(c, KIT_CG_BUILTIN_F64);
     case TY_LDOUBLE:
       /* `long double` is IEEE-754 binary128 on targets that follow the quad
        * psABI (RISC-V, aarch64-linux, wasm32); elsewhere it aliases `double`.
        * See kit_target_long_double_is_binary128. */
       return kit_cg_type_builtin(
           c, kit_target_long_double_is_binary128(kit_compiler_target_spec(c))
                  ? KIT_CG_BUILTIN_F128
                  : KIT_CG_BUILTIN_F64);
     default:
       break;
   }
   return KIT_CG_TYPE_NONE;
 }
 
 /* Source spelling + debug encoding per integer/char TypeKind. CG integer
  * storage is width-only; this table drives the separate debug channel so C
  * signedness and spelling reach DWARF without changing the operational type id.
  * Kinds with a NULL name use the debug producer's default derivation. */
 typedef struct ScalarDbgSpec {
   const char* name;
   u8 enc; /* KitCgDebugEncoding */
 } ScalarDbgSpec;
 
 static const ScalarDbgSpec kScalarDbg[TY_ENUM + 1] = {
     [TY_CHAR] = {"char", KIT_CG_DEBUG_ENC_SIGNED_CHAR},
     [TY_SCHAR] = {"signed char", KIT_CG_DEBUG_ENC_SIGNED_CHAR},
     [TY_UCHAR] = {"unsigned char", KIT_CG_DEBUG_ENC_UNSIGNED_CHAR},
     [TY_SHORT] = {"short", KIT_CG_DEBUG_ENC_SIGNED},
     [TY_USHORT] = {"unsigned short", KIT_CG_DEBUG_ENC_UNSIGNED},
     [TY_INT] = {"int", KIT_CG_DEBUG_ENC_SIGNED},
     [TY_UINT] = {"unsigned int", KIT_CG_DEBUG_ENC_UNSIGNED},
     [TY_LONG] = {"long", KIT_CG_DEBUG_ENC_SIGNED},
     [TY_ULONG] = {"unsigned long", KIT_CG_DEBUG_ENC_UNSIGNED},
     [TY_LLONG] = {"long long", KIT_CG_DEBUG_ENC_SIGNED},
     [TY_ULLONG] = {"unsigned long long", KIT_CG_DEBUG_ENC_UNSIGNED},
     [TY_INT128] = {"__int128", KIT_CG_DEBUG_ENC_SIGNED},
     [TY_UINT128] = {"unsigned __int128", KIT_CG_DEBUG_ENC_UNSIGNED},
 };
 
 /* Lower a scalar TypeKind to its operational CG type id: a bare storage builtin
  * for scalar kinds, or NONE for non-scalar kinds (caller falls through to the
  * structural lowering). Pure function of (kind, target), like type_cg_builtin.
  */
 static KitCgTypeId type_cg_scalar(KitCompiler* c, TypeKind kind) {
   return type_cg_builtin(c, kind);
 }
 
 typedef enum TypeCgMode {
   TYPE_CG_VALUE,
 } TypeCgMode;
 
 typedef struct TypeCgLower {
   KitCompiler* c;
   Pool* p;
   PoolTypeCache* cache;
   /* Raised whenever lowering passes through a still-incomplete record; scoped
    * per subtree by type_cg_lower so a node is memoized only when its whole
    * lowering was incomplete-free (and thus stable for the pool's lifetime). */
   int saw_incomplete;
 } TypeCgLower;
 
 static KitCgTypeId type_cg_lower(TypeCgLower* l, const Type* t,
                                  TypeCgMode mode);
 
 /* Record identity is its tag id (records are never structurally interned), so
  * the memo is a plain tag-id -> layout-id map. Only ever called with STRUCT/
  * UNION types, so t->rec is live; complete records always carry a non-zero tag,
  * so tag 0 is free to serve as the map's empty-key sentinel. */
 static KitCgTypeId type_cg_record_memo_get(PoolTypeCache* cache, KitCompiler* c,
                                            const Type* t) {
   const KitCgTypeId* hit;
   (void)c;
   if (!cache) return KIT_CG_TYPE_NONE;
   hit = CgRecordMap_get(&cache->cg_records, t->rec.tag_id);
   return hit ? *hit : KIT_CG_TYPE_NONE;
 }
 
 static void type_cg_record_memo_put(Pool* p, PoolTypeCache* cache,
                                     KitCompiler* c, const Type* t,
                                     KitCgTypeId id) {
   (void)p;
   (void)c;
   if (!cache || !t || id == KIT_CG_TYPE_NONE) return;
   if (t->kind != TY_STRUCT && t->kind != TY_UNION) return;
   if (t->rec.tag_id == TAG_NONE) return;
   CgRecordMap_set(&cache->cg_records, t->rec.tag_id, id);
 }
 
 static KitCgTypeId type_cg_record_decl_id(TypeCgLower* l, const Type* t) {
   KitCgTypeId id;
   if (!l || !t || (t->kind != TY_STRUCT && t->kind != TY_UNION)) {
     return KIT_CG_TYPE_NONE;
   }
   id = type_cg_record_memo_get(l->cache, l->c, t);
   if (id != KIT_CG_TYPE_NONE) return id;
   id = kit_cg_type_record_decl(l->c, t->rec.tag, t->kind == TY_UNION);
   type_cg_record_memo_put(l->p, l->cache, l->c, t, id);
   return id;
 }
 
 static KitCgTypeId type_cg_record_layout(TypeCgLower* l, const Type* t) {
   KitCgFieldDesc* fields = NULL;
   KitCgRecordDesc desc;
   KitCgTypeId id;
   int tracked = 0;
   if (!l || !t || (t->kind != TY_STRUCT && t->kind != TY_UNION)) {
     return KIT_CG_TYPE_NONE;
   }
   id = type_cg_record_decl_id(l, t);
   if (id == KIT_CG_TYPE_NONE) return KIT_CG_TYPE_NONE;
   if (t->rec.incomplete) {
     l->saw_incomplete = 1;
     return id;
   }
   if (kit_cg_type_is_complete(l->c, id)) return id;
   /* Cycle safety net. Recursion *through a pointer* is already broken in the
    * TY_PTR case (the pointee takes the decl id, never re-entering here), so the
    * valid self-/mutual-reference shapes never reach this guard. What can still
    * re-enter mid-completion is a by-value path back to an in-flight record --
    * e.g. the invalid `struct N { struct N arr[10]; }`, where the array forces
    * its incomplete element to lay out. Hand back the still-incomplete decl id
    * (the array then fails the sized-element check, surfacing a clean error)
    * rather than recursing into a second completion and overflowing the stack.
    * Track every in-flight record so mutual by-value cycles are covered too.
    * Anonymous records carry no tag but cannot name themselves, so they never
    * reach this guard. */
   if (t->rec.tag_id != TAG_NONE) {
     if (CgRecordMap_get(&l->cache->cg_records_completing, t->rec.tag_id)) {
       l->saw_incomplete = 1;
       return id;
     }
     CgRecordMap_set(&l->cache->cg_records_completing, t->rec.tag_id, id);
     tracked = 1;
   }
   if (t->rec.nfields) {
     fields = arena_zarray(l->p->arena, KitCgFieldDesc, t->rec.nfields);
     if (!fields) {
       id = KIT_CG_TYPE_NONE;
       goto done;
     }
     for (u32 i = 0; i < t->rec.nfields; ++i) {
       fields[i].name = t->rec.fields[i].name;
       fields[i].type = type_cg_lower(l, t->rec.fields[i].type, TYPE_CG_VALUE);
       fields[i].align_override = t->rec.fields[i].align_override;
       fields[i].max_align = t->rec.fields[i].max_align;
       if (t->rec.max_align &&
           (fields[i].max_align == 0 || t->rec.max_align < fields[i].max_align))
         fields[i].max_align = t->rec.max_align;
       if (t->rec.fields[i].flags & FIELD_BITFIELD) {
         fields[i].flags |= KIT_CG_FIELD_BITFIELD;
         /* A zero-width bit-field is carried to CG as bit_width 0 (the layout
          * barrier); CG keys off BITFIELD && bit_width==0, no separate flag. */
         fields[i].bit_width = t->rec.fields[i].bitfield_width;
         fields[i].bit_signed = type_is_signed_integer(t->rec.fields[i].type);
       }
       if (t->rec.fields[i].packed && fields[i].align_override == 0) {
         fields[i].align_override = 1;
       }
       if (t->rec.packed && fields[i].align_override == 0) {
         fields[i].align_override = 1;
       }
     }
   }
   memset(&desc, 0, sizeof desc);
   desc.tag = t->rec.tag;
   desc.fields = fields;
   desc.nfields = t->rec.nfields;
   desc.is_union = t->kind == TY_UNION;
   desc.align_override = t->rec.align_override;
   if (kit_cg_type_record_complete(l->c, id, &desc) != KIT_OK)
     id = KIT_CG_TYPE_NONE;
 done:
   /* Clear the in-flight marker so a later, independent lowering of the same tag
    * (now CG-complete) takes the fast is_complete path rather than this guard.
    */
   if (tracked) CgRecordMap_del(&l->cache->cg_records_completing, t->rec.tag_id);
   return id;
 }
 
 static KitCgTypeId type_cg_lower(TypeCgLower* l, const Type* t,
                                  TypeCgMode mode) {
   KitCgTypeId id;
   int cacheable;
   int outer_incomplete;
   if (!l || !t) return KIT_CG_TYPE_NONE;
   /* Check the cache BEFORE the builtin switch: a cached cg_id (whether a
    * builtin id stamped below or a non-builtin lowering) always equals what the
    * switch would recompute, so this hoist only short-circuits already-lowered
    * types -- byte-identical, but skips the recompute. */
   cacheable = (mode == TYPE_CG_VALUE);
   if (cacheable && t->cg_id != KIT_CG_TYPE_NONE)
     return t->cg_id; /* cached => was incomplete-free => still stable */
   id = type_cg_scalar(l->c, (TypeKind)t->kind);
   if (id != KIT_CG_TYPE_NONE) {
     /* type_cg_scalar is a pure function of t->kind (and the fixed target), so
      * a scalar id is mode-independent and incomplete-free: stamp it on the
      * node so the next VALUE-mode crossing short-circuits above. Scalar ids are
      * never 0, so they can't alias the NONE sentinel. */
     if (cacheable) ((Type*)t)->cg_id = id;
     return id;
   }
   /* Scope saw_incomplete to this subtree so the post-recursion check reflects
    * only whether *this* node's lowering touched an incomplete record. */
   outer_incomplete = l->saw_incomplete;
   l->saw_incomplete = 0;
   switch ((TypeKind)t->kind) {
     case TY_PTR: {
       /* A pointer needs only its pointee's nominal identity, never its layout,
        * so a record/union pointee lowers to its (possibly incomplete) decl id
        * instead of being completed here. This is what makes a forward-declared
        * record used only through pointers legal without ever completing it, and
        * it breaks self-/mutual-reference cycles (struct N { struct N* next; },
        * A<->B) at the pointer rather than recursing into completion. A record
        * is completed only when something needs its layout -- a by-value local,
        * field, param/result, array element, sizeof, or member access -- all of
        * which lower the record itself, not a pointer to it. */
       const Type* pointee = t->ptr.pointee;
       KitCgTypeId pid;
       if (pointee->kind == TY_STRUCT || pointee->kind == TY_UNION) {
         pid = type_cg_record_decl_id(l, pointee);
         if (pid != KIT_CG_TYPE_NONE && !kit_cg_type_is_complete(l->c, pid))
           l->saw_incomplete = 1;
       } else {
         pid = type_cg_lower(l, pointee, TYPE_CG_VALUE);
       }
       id = pid == KIT_CG_TYPE_NONE ? KIT_CG_TYPE_NONE
                                    : kit_cg_type_ptr(l->c, pid, 0);
       break;
     }
     case TY_ARRAY:
       id = kit_cg_type_array(l->c, type_cg_lower(l, t->arr.elem, mode),
                              t->arr.count);
       break;
     case TY_FUNC: {
       KitCgFuncParam* params = NULL;
       KitCgFuncSig sig;
       memset(&sig, 0, sizeof sig);
       sig.result.type = type_cg_lower(l, t->fn.ret, TYPE_CG_VALUE);
       sig.nparams = t->fn.nparams;
       sig.abi_variadic = t->fn.variadic;
       sig.call_conv = KIT_CG_CC_TARGET_C;
       if (t->fn.nparams) {
         params = arena_zarray(l->p->arena, KitCgFuncParam, t->fn.nparams);
         if (!params) {
           id = KIT_CG_TYPE_NONE;
           break;
         }
         for (u32 i = 0; i < t->fn.nparams; ++i) {
           params[i].type = type_cg_lower(l, t->fn.params[i], TYPE_CG_VALUE);
         }
       }
       sig.params = params;
       id = kit_cg_type_func(l->c, sig);
       break;
     }
     case TY_STRUCT:
     case TY_UNION:
       id = type_cg_record_layout(l, t);
       break;
     case TY_ENUM: {
       KitCgTypeId ebase = type_cg_lower(l, t->enm.base, mode);
       KitCgEnumValue* evs = NULL;
       u32 nv = t->enm.nconsts;
       if (nv) {
         evs = arena_array(l->p->arena, KitCgEnumValue, nv);
         if (!evs) {
           nv = 0;
         } else {
           for (u32 i = 0; i < nv; ++i) {
             evs[i].name = t->enm.consts[i].name;
             evs[i].value = (u64)t->enm.consts[i].value;
           }
         }
       }
       id = kit_cg_type_enum(l->c, t->enm.tag, ebase, evs, nv);
       break;
     }
     default:
       id = KIT_CG_TYPE_NONE;
       break;
   }
   if (cacheable && id != KIT_CG_TYPE_NONE && !l->saw_incomplete) {
     /* The node is the canonical interned type and we own its storage (arena);
      * the const is only the public contract. Stashing the stable lowering here
      * is exactly what dropping the memcmp interning bought us. */
     ((Type*)t)->cg_id = id;
   }
   /* Propagate this subtree's incompleteness to the enclosing lowering. */
   l->saw_incomplete |= outer_incomplete;
   return id;
 }
 
 KitCgTypeId type_cg_id_in_pool(KitCompiler* c, Pool* p, const Type* t) {
   TypeCgLower l;
   if (!p) return KIT_CG_TYPE_NONE;
   /* TypeCgLower has exactly these four fields; explicit init writes the same
    * values the memset+assignments did, skipping a per-crossing struct clear. */
   l.c = c;
   l.p = p;
   l.cache = cache_get(p);
   l.saw_incomplete = 0;
   return type_cg_lower(&l, t, TYPE_CG_VALUE);
 }
 
 typedef struct TypeCgDebugLower {
   KitCg* cg;
   KitCompiler* c;
   Pool* p;
   PoolTypeCache* cache;
 } TypeCgDebugLower;
 
 static KitCgDebugType type_cg_debug_scalar(TypeCgDebugLower* l, TypeKind kind) {
   KitCgTypeId storage = type_cg_builtin(l->c, kind);
   const ScalarDbgSpec* s;
   uint32_t bytes;
   if (storage == KIT_CG_TYPE_NONE) return KIT_CG_DEBUG_TYPE_NONE;
   if ((unsigned)kind > (unsigned)TY_ENUM) {
     return kit_cg_debug_of_type(l->cg, storage);
   }
   s = &kScalarDbg[kind];
   if (!s->name) return kit_cg_debug_of_type(l->cg, storage);
   bytes = (uint32_t)kit_cg_type_size(l->c, storage);
   if (!bytes) bytes = 1;
   return kit_cg_debug_base(l->cg, kit_sym_intern(l->c, kit_slice_cstr(s->name)),
                            (KitCgDebugEncoding)s->enc, bytes);
 }
 
 static KitCgDebugType type_cg_debug_record_decl(TypeCgDebugLower* l,
                                                 const Type* t) {
   TypeCgLower op;
   KitCgTypeId id;
   op.c = l->c;
   op.p = l->p;
   op.cache = l->cache;
   op.saw_incomplete = 0;
   id = type_cg_record_decl_id(&op, t);
   return kit_cg_debug_of_type(l->cg, id);
 }
 
 static KitCgDebugType type_cg_debug_lower(TypeCgDebugLower* l, const Type* t) {
   KitCgDebugType id;
   if (!l || !t) return KIT_CG_DEBUG_TYPE_NONE;
 
   id = type_cg_debug_scalar(l, (TypeKind)t->kind);
   if (id != KIT_CG_DEBUG_TYPE_NONE) return id;
 
   switch ((TypeKind)t->kind) {
     case TY_PTR: {
       const Type* pointee = t->ptr.pointee;
       KitCgDebugType pd;
       if (pointee->kind == TY_STRUCT || pointee->kind == TY_UNION) {
         pd = type_cg_debug_record_decl(l, pointee);
       } else {
         pd = type_cg_debug_lower(l, pointee);
       }
       id = kit_cg_debug_ptr(l->cg, pd);
       break;
     }
     case TY_ARRAY:
       id = kit_cg_debug_array(l->cg, type_cg_debug_lower(l, t->arr.elem),
                               t->arr.incomplete ? 0u : t->arr.count);
       break;
     case TY_FUNC: {
       KitCgDebugType* params = NULL;
       KitCgDebugType ret = type_cg_debug_lower(l, t->fn.ret);
       if (t->fn.nparams) {
         params = arena_zarray(l->p->arena, KitCgDebugType, t->fn.nparams);
         if (!params) {
           id = KIT_CG_DEBUG_TYPE_NONE;
           break;
         }
         for (u32 i = 0; i < t->fn.nparams; ++i) {
           params[i] = type_cg_debug_lower(l, t->fn.params[i]);
         }
       }
       id = kit_cg_debug_func(l->cg, ret, params, t->fn.nparams, t->fn.variadic);
       break;
     }
     case TY_STRUCT:
     case TY_UNION: {
       KitCgTypeId op_id = type_cg_id_in_pool(l->c, l->p, t);
       id = kit_cg_debug_of_type(l->cg, op_id);
       break;
     }
     case TY_ENUM: {
       KitCgTypeId op_id = type_cg_id_in_pool(l->c, l->p, t);
       KitCgDebugType base = type_cg_debug_lower(l, t->enm.base);
       id = kit_cg_debug_enum(l->cg, op_id, base);
       break;
     }
     default:
       id = KIT_CG_DEBUG_TYPE_NONE;
       break;
   }
 
   return id;
 }
 
 KitCgDebugType type_cg_debug_in_pool(KitCg* cg, KitCompiler* c, Pool* p,
                                      const Type* t) {
   TypeCgDebugLower l;
   if (!cg || !p) return KIT_CG_DEBUG_TYPE_NONE;
   l.cg = cg;
   l.c = c;
   l.p = p;
   l.cache = cache_get(p);
   return type_cg_debug_lower(&l, t);
 }