kit

kit
git clone https://git.ryansepassi.com/git/kit.git
Log | Files | Refs | README

CG type and type-id system clean cutover

Goal. Replace the current KitCgTypeId implementation and public type API with a simpler, explicit, and ABI-correct type table. Keep the good part: a small compiler-owned integer handle that can be stored cheaply throughout IR, ABI records, frontends, and backends. Change what that handle means, how void and aliases are represented, where layout facts are computed, and how nominal records are completed.

This is a clean-break rewrite, no backcompat. The old constructors, query semantics, KIT_CG_TYPE_NONE-as-void convention, segmented id encoding, and frontend workarounds are removed as the cutover lands. There is no compatibility adapter and no byte-identity gate.

1. Current State

The public API uses an opaque uint32_t KitCgTypeId:

Internally, src/cg/type.c owns CgApiState:

The C frontend lowers Type* to KitCgTypeId lazily and caches ids on C type nodes and parser stack slots. Incomplete records are handled outside CG: a temporarily incomplete record lowers to void, and record-field/function-param pointer lowering collapses pointees to void* so layout can proceed without a true incomplete nominal record id.

The ABI layer reads CgType entries and caches target layout/classification facts by type id. Some storage facts live eagerly on CgType (size, align); some target facts live in TargetABI; record layout is currently computed by the CG type constructor and re-exposed by the ABI cache.

2. Problems

2.1 NONE Has Too Many Meanings

KIT_CG_TYPE_NONE currently means:

There is also a real void builtin. Every caller must remember which API treats void as a real type and which treats NONE as absence. That is a correctness hazard and a permanent source of branchy special cases.

2.2 Alias Semantics Are Implicit

Some queries inspect the exact id. Others recurse through aliases. Examples:

The result is not one type model; it is a collection of local conventions.

2.3 ID Decode Complexity Does Not Buy Enough

The segmented builtin/user encoding makes every id lookup decode segment bits. That helped keep builtin ids stable and user pointers stable, but the hot path now contains extra decode logic and special builtin handling. A direct table index keeps the same public handle shape with less machinery.

2.4 Layout Authority Is Split

CgType eagerly stores size and align, while TargetABI is supposed to be the single authority for target-dependent layout and calling convention facts. This is especially fragile for:

2.5 Incomplete Nominal Records Are Not Modeled

The C frontend needs true identities for incomplete records so these are legal:

struct S;
struct T { struct S *p; };
struct S { int x; };

Today CG has no incomplete record declaration/completion API, so the frontend works around it by erasing some pointee identity to void* while lowering record fields and function parameters. That preserves layout but loses type identity and pushes a CG responsibility into the frontend.

2.6 Queries Are Too Fragmented

The public API exposes many one-off queries (kind, size, align, ptr_pointee, array_elem, func_param, record_field, etc.). That is easy to call but expensive and ambiguous at scale: each query chooses exact vs resolved behavior separately, and hot call sites decode the same id repeatedly.

3. Design Decisions

# Decision Choice
D1 Public handle shape Keep typedef uint32_t KitCgTypeId; 0 is invalid/none only
D2 Void representation Void is always the real void builtin type id; NONE never means void
D3 ID layout Builtin ids are 1..KIT_CG_BUILTIN_COUNT; user ids are KIT_CG_BUILTIN_COUNT + 1 + index
D4 Cross-compiler stability Type ids are stable only within one KitCompiler; never serialized as semantic identities
D5 Structural interning Pointer, array, and function constructors intern by exact constructor shape
D6 Nominal identity Records, enums, and aliases keep fresh source-facing ids
D7 Alias behavior Exact queries inspect aliases; storage/semantic queries resolve aliases explicitly
D8 Function void result Function result type is always a valid type id; use the void builtin for no value
D9 Layout authority TargetABI computes all size/align/scalar layout facts; type entries only cache ABI results
D10 Records Records are nominal and two-phase: declare first, complete once
D11 Incomplete use Pointers to incomplete records are legal; sizing, arrays, fields, by-value params/results, locals, and memory accesses require complete/sized types
D12 Caches Caches live on the owning type entry or ABI context and are filled only after the facts they depend on are final
D13 Implementation style C11, no VLAs, no global type state; everything hangs off KitCompiler/TargetABI

4. New Public Shape

4.1 IDs and Builtins

The id remains opaque, but implementation decode is direct:

#define KIT_CG_TYPE_NONE 0u

/* implementation rule, not a public promise beyond nonzero/stable per compiler:
 * builtin id = 1 + KitCgBuiltinType
 * user id    = 1 + KIT_CG_BUILTIN_COUNT + user_index
 */

The public builtin query becomes singular. The whole-table query is removed unless a real caller needs it after the cutover.

KIT_API KitCgTypeId kit_cg_type_builtin(KitCompiler*, KitCgBuiltinType);

4.2 Function Signatures

KitCgFuncResult.type is always valid. A void function uses the void builtin.

typedef struct KitCgFuncResult {
  KitCgTypeId type;   /* valid; void builtin means no value */
  KitCgAbiAttrs attrs;
} KitCgFuncResult;

typedef struct KitCgFuncSig {
  KitCgFuncResult result;
  const KitCgFuncParam* params;
  uint32_t nparams;
  KitCgCallConv call_conv;
  bool abi_variadic;
} KitCgFuncSig;

The helper predicate is explicit:

KIT_API int kit_cg_type_is_void(KitCompiler*, KitCgTypeId);
KIT_API int kit_cg_func_result_has_value(KitCompiler*, KitCgFuncResult);

No caller tests result.type == KIT_CG_TYPE_NONE after this cutover.

4.3 Exact and Storage Queries

Exact identity and storage identity are separate operations.

KIT_API KitCgTypeId kit_cg_type_resolve_alias(KitCompiler*, KitCgTypeId);
KIT_API int kit_cg_type_same_storage(KitCompiler*, KitCgTypeId,
                                     KitCgTypeId);

Rules:

4.4 Descriptor Query

Add one structured query for hot callers and keep narrow helpers only where they remain clearly useful.

typedef enum KitCgTypeFlag {
  KIT_CG_TYPEF_COMPLETE = 1u << 0,
  KIT_CG_TYPEF_SIZED = 1u << 1,
  KIT_CG_TYPEF_BUILTIN = 1u << 2,
  KIT_CG_TYPEF_NOMINAL = 1u << 3,
} KitCgTypeFlag;

typedef enum KitCgStorageKind {
  KIT_CG_STORAGE_VOID,
  KIT_CG_STORAGE_BOOL,
  KIT_CG_STORAGE_INT,
  KIT_CG_STORAGE_FLOAT,
  KIT_CG_STORAGE_PTR,
  KIT_CG_STORAGE_AGGREGATE,
} KitCgStorageKind;

typedef struct KitCgTypeLayout {
  uint64_t size;
  uint32_t align;
  uint16_t scalar_width;
  uint8_t storage_kind; /* KitCgStorageKind */
  uint8_t valid;
} KitCgTypeLayout;

typedef struct KitCgTypeInfo {
  KitCgTypeId id;
  KitCgTypeId storage_id; /* alias-resolved id, or id */
  KitCgTypeKind kind;     /* exact kind */
  uint32_t flags;         /* KitCgTypeFlag */
  KitCgTypeLayout layout; /* valid only for sized/storage queries */
} KitCgTypeInfo;

KIT_API KitStatus kit_cg_type_info(KitCompiler*, KitCgTypeId,
                                   KitCgTypeInfo*);

This descriptor is intentionally shallow. Shape-specific data still comes from shape-specific APIs or internal entry access:

4.5 Record Declaration and Completion

Records are true nominal objects.

KIT_API KitCgTypeId kit_cg_type_record_decl(KitCompiler*, KitSym tag,
                                            int is_union);

KIT_API KitStatus kit_cg_type_record_complete(KitCompiler*, KitCgTypeId record,
                                              const KitCgRecordDesc*);

KIT_API int kit_cg_type_is_complete(KitCompiler*, KitCgTypeId);

Convenience construction stays possible, but it is just declare + complete:

KIT_API KitCgTypeId kit_cg_type_record(KitCompiler*, const KitCgRecordDesc*);

Completion rules:

The C frontend no longer lowers record-context pointers to void*.

4.6 Array Counts

The public array count remains uint64_t. The structural key must use the full 64-bit count or reject out-of-range counts with a documented status. Do not truncate the key. Prefer full-width support unless an object/backend limit requires a specific diagnostic.

KIT_API KitCgTypeId kit_cg_type_array(KitCompiler*, KitCgTypeId elem,
                                      uint64_t count);

5. Internal Architecture

5.1 Type Table

Use one compiler-owned table. Builtins occupy the first nonzero ids; user entries append after them.

typedef struct CgTypeEntry {
  KitCgTypeKind kind;
  uint32_t flags;

  KitCgTypeId id;
  KitCgTypeId storage_id; /* alias terminal once known */

  uint8_t pred_bits;
  uint8_t pred_valid;
  uint8_t class_bits;
  uint8_t class_valid;
  uint8_t layout_valid;

  KitCgTypeLayout layout;

  union {
    CgBuiltinType builtin;
    CgPtrType ptr;
    CgArrayType array;
    CgFuncType func;
    CgRecordType record;
    CgEnumType enum_;
    CgAliasType alias;
  };
} CgTypeEntry;

typedef struct CgTypeTable {
  Heap* heap;
  CgTypeEntries entries;
  CgPtrMap ptr_index;
  CgArrayMap array_index;
  CgFuncMap func_index;
} CgTypeTable;

The table can still use a segmented vector if stable entry pointers are useful, but indexes are direct: id - 1 maps to an entry. Hash indexes store ids, not entry pointers, so the implementation is free to move entries later if that becomes desirable.

5.2 Structural Indexes

Pointer key:

{ pointee_id, address_space }

Array key:

{ elem_id, uint64_t count }

Function key:

{ result type+attrs, params type+attrs[], call_conv, abi_variadic }

The key is exact-id based. Alias preservation is therefore possible for source facing APIs and generated C/debug output. Storage equivalence is a separate query and must not depend on exact id equality.

5.3 Layout Cache

CgTypeEntry.layout is a cache of the ABI-computed layout, not an independent source of truth.

Flow:

kit_cg_type_size/align/info
  -> cg_type_require_layout
  -> TargetABI layout hook / shared ABI layout
  -> cache on CgTypeEntry after success

Builtins can be initialized with target facts, but they still follow the same layout contract. Target-shaped builtins such as vararg_state are computed through the ABI layer.

Record completion asks the ABI/layout authority to compute source-facing record layout before marking the record complete. If a future ABI has different bit-field layout rules, it plugs in at this boundary rather than after the record is already committed.

5.4 Predicates and Classes

Predicate bits and codegen class bits remain valuable, but they should be computed from one storage descriptor:

exact id -> resolve alias -> storage/layout descriptor -> pred/class bits

That avoids one-off predicate functions each re-decoding the id and each choosing its own alias behavior.

6. Frontend Impact

6.1 C Frontend

The C frontend should map source types to CG types as follows:

The current incomplete-record workaround is deleted. The C type pool can cache the declared record id as soon as the tag exists, then complete the same id when the definition is parsed.

6.2 Toy Frontend

Toy mostly uses CG storage types directly. It should switch to:

6.3 C Backend and Debug Info

The C backend and debug producer are the main consumers that care about exact source-facing ids. They should use exact queries for names and aliases, and storage queries for codegen legality.

7. Implementation Plan

Phase 1: Lock the New Contract in Tests

Add focused test/api/cg_type_test.c cases that fail under the old model:

Phase 2: Replace the Type Table

Introduce the new direct-index table behind src/cg/type.c:

Do this before converting all callers, accepting compile failures in the working tree during the phase. There is no compatibility shim.

Phase 3: Cut Over Public API and Call Sites

Update include/kit/cg.h and every caller:

Phase 4: Move Layout Authority to ABI

Make TargetABI the only layout authority:

Delete independent eager CgType.size / CgType.align ownership. A type entry may cache layout but does not define it.

Phase 5: Add Two-Phase Records and Convert C Lowering

Convert the C frontend record path:

Phase 6: Delete Old Caches and Helpers

Remove now-redundant pieces:

8. Validation

Use targeted runs during the cutover:

Broaden only after the API and frontend are compiling cleanly.

Important scenario coverage:

9. Acceptance Criteria

10. Open Questions

  1. Should KIT_CG_TYPE_ALIAS remain a true public kind, or should source aliases move entirely into debug/C-backend metadata after the cutover? The plan above keeps alias ids because they already serve source-facing consumers, but the storage semantics do not require them. Resolved → move them out. See CG-TYPE-DEBUG-SPLIT.md: KitCgTypeId becomes storage/ABI-only and source spelling (now including the KIT_CG_TYPE_SOURCE_BASE added since this question was written) moves onto a separate optional debug-type channel, deleting api_unalias_type and the per-backend unalias boilerplate.
  2. Should function types reject incomplete by-value records at construction, or permit declaration-like signatures and reject only when defining/calling? Prefer rejection unless a frontend has a concrete declaration use case.
  3. Should kit_cg_type_info include shallow shape facts, or stay layout-only with shape-specific accessors? Prefer shallow layout-only initially to keep the public struct stable.
  4. Should array counts larger than target addressable object size be rejected by the type constructor or by object/data/local users? Prefer constructor rejection if every backend agrees on the same maximum; otherwise diagnose at the first sized-object use.