Skip to content

02 — The Structured Type System (crates/dream-types/src/)

5 min read

Start here before working on HIR or MIR. The type system gives every type a stable identity and records the facts later stages need. This chapter explains those identities and how to add or compare types.

The problem it replaces

Historically a type was identified by the string Type::get_type() produces:

Type Legacy string Problem
int[] "int[]" every consumer re-parses the [] suffix
Box<int> "Box_int" mangling; demangle_generic_struct heuristically splits on _
Pair<int,string> "Pair_int_string" ambiguous if a base name contains _
fun(int):bool "fun(int):bool" parsed by string surgery

Equality was a String compare, monomorphization was string mangling, and reference-ness was ends_with("[]") || known_struct(name). The structured system turns all of this into integer operations. (A former T? / TyKind::Nullable layer was purged in favor of Option<T> — see 09.)

The pieces

classDiagram
    class TypeInterner {
        +intern(TyKind) TypeId
        +kind(TypeId) TyKind
        +int()/bool()/string()/object()/void()/error() TypeId
        +array(TypeId) TypeId
        +struct_ty(DefId, args) TypeId
        +is_reference(TypeId) bool
    }
    class TyKind {
        Prim(PrimTy)
        Object
        Void
        Error
        Array(TypeId)
        Struct(DefId, Vec~TypeId~)
        Union(DefId, Vec~TypeId~)
        Interface(DefId, Vec~TypeId~)
        Enum(DefId)
        Func(Vec~TypeId~, TypeId)
        Js
    }
    class DefTable {
        +allocate(ModuleId, path, DefKind, name, generics) DefId
        +get(DefId) DefInfo
    }
    class TypeCtx {
        +interner TypeInterner
        +defs DefTable
        +register(DefKind, name, generics) DefId
        +lower(Type) TypeId
        +lower_with(Type, bindings) TypeId
    }
    TypeCtx --> TypeInterner
    TypeCtx --> DefTable
    TypeInterner --> TyKind

TypeId and TyKind — crates/dream-types/src/kind.rs, crates/dream-types/src/mod.rs

TypeId(u32) is an interned handle. TyKind is the shape of a type, and it is flat: nested types are referenced by TypeId, not owned, so a TyKind is cheap to clone, hash, and compare — which is what makes interning possible.

pub enum TyKind {
    Prim(PrimTy),                  // int, uint, long, ulong, byte, float, double, bool, char, string
    Object,                        // the universal top type
    Void,
    Error,                         // poison
    Array(TypeId),
    Struct(DefId, Vec<TypeId>),    // (definition, type arguments)
    Union(DefId, Vec<TypeId>),
    Interface(DefId, Vec<TypeId>),
    Enum(DefId),
    Func(Vec<TypeId>, TypeId),     // (params, return)
    Tuple(Vec<TypeId>),            // positional (T, U, …); always a value type
    Js,                            // dynamic JS-interop handle
}

PrimTy keeps string for naming convenience; whether a value is a heap reference is decided by TypeInterner::is_reference, not by PrimTy. Absence is Option<T> (a Union/Struct over the prelude Option def), not a dedicated nullable wrapper.

TypeInterner — crates/dream-types/src/interner.rs

Hash-conses TyKind → TypeId. The nullary types (all primitives, Object, Void, Error) are pre-interned in new() so their ids are stable and reachable via accessors (int(), bool(), …).

Equality is ==. Because identical TyKinds always intern to the same TypeId, you never compare type shapes — you compare ids. If you find yourself matching on TyKind to test equality, you almost certainly want id_a == id_b.

DefId and DefTable — crates/dream-types/src/def.rs

A DefId names a nominal declaration — a struct, union, enum, or function (DefKind) — and is independent of type arguments: Box<int> and Box<string> are Struct(box_def, [int]) and Struct(box_def, [string]) with the same box_def. DefInfo records the base name (never mangled) and the declared generic_params (["T"]).

DefId contains a ModuleId and a module-local index. DefTable stores definitions by that identity; source-name resolution belongs to module scopes in TypeCtx. Two modules can each declare User without sharing a nominal type or runtime layout.

Canonical type instances are keyed by (DefId, Vec<TypeId>). During HIR emission, dream-types::function_symbol builds the emitted name from the declaring module, function key and structural type arguments. dream-types::type_symbol includes the nominal module path, never numeric interner handles. Length framing and byte escaping distinguish underscores, punctuation and argument boundaries; _D-prefixed user names are escaped into a separate namespace. Frontend mangled-instance aliases and some function/generic metadata still need migration away from name keys.

Compatibility & widening — crates/dream-types/src/compat.rs

Three structural relations replace the old string comparisons:

  • numeric_widen(from, to) — the implicit numeric widening lattice (byte → int → long → float → double, plus unsigned/float cross-edges). from == to is false (identity is handled separately).
  • assignable(interner, target, value) — may value be assigned to target? Encodes: Error poison is bidirectional; anything widens into object; enums interconvert with int; numerics widen per the lattice; Option<T> follows ordinary union assignability (no special null literal).
  • overload_compatible(interner, param, arg) — looser than assignable: any two numeric primitives are compatible regardless of direction (exactness is scored separately during overload ranking).

Display — crates/dream-types/src/display.rs

display_name(interner, defs, id) renders source-level syntax for diagnostics and the LSP: int[], Option<string>, Box<int>, fun(int): bool. Generics use angle brackets, never the internal Box_int spelling. The LSP tests depend on this.

TypeCtx — crates/dream-types/src/lower.rs

The analyzer-facing bundle: it owns the TypeInterner and DefTable and lowers AST Type → TypeId.

  • register(kind, name, generics) records a nominal def — call it when you see a declaration.
  • lower(&Type) lowers a type annotation with no generics in scope.
  • lower_with(&Type, &bindings) lowers with generic parameter substitution (bindings: name → TypeId), used when instantiating a generic body.

Because the parser emits Type::Struct for any bare identifier, TypeCtx resolves its kind and definition in the current module and its imports. Register declarations before lowering their uses. The compiler-owned Future<T> definition is registered explicitly: async result types must remain reference types even though there is no source declaration for Future.

shared classes

The analyzer marks a class def as shared when it is declared shared class (TypeInterner::mark_shared_def / is_shared_def). That flag is load-bearing in three places downstream:

  1. Field validation — every field of a shared class must be unmanaged, itself shared, or a managed heap reference whose graph joins the shared region (relaxed closed-graph rule; see check_shared_field in crates/dream-sema/src/analyzer/declarations/structs.rs, re-checked per monomorphization for generic classes).
  2. Layout — shared allocations are four bytes larger than the equivalent non-shared class to hold a reentrant lock word past the last field (HEADER_LOCK_WORD_SIZE in crates/dream-mir/src/abi.rs; zero-initialized in Rvalue::New emission).
  3. Backend RC — retain/release codegen selects atomic helpers for shared types only (retain_sym / release_sym in crates/dream-mir/src/backend/shared/glue.rs).

Never compare types by mangled name to detect sharing — always go through TypeInterner::is_shared_type.

How to add a new type to the language

Worked example: a 128-bit integer i128.

  1. Lexer/parser/AST (crates/dream-syntax): add the keyword and a Type::I128(SyntaxToken) variant; update Type::get_type() and Type::from_token(). (get_type() now only produces the mangled instance name used as the deterministic emit identity; type decisions run on TypeId, and messages use display_name().)
  2. PrimTy (crates/dream-types/src/kind.rs): add PrimTy::I128 plus its name(), from_name(), is_numeric(), is_unsigned_integer() arms.
  3. Interner (crates/dream-types/src/interner.rs): pre-intern it in new() so it has a stable id.
  4. Widening (crates/dream-types/src/compat.rs): add the lattice edges in numeric_widen.
  5. Lowering (crates/dream-types/src/lower.rs): add the Type::I128(_) => self.interner.prim(PrimTy::I128) arm.
  6. Backend (crates/dream-mir/src/backend/llvm/): map it to an LLVM type in types.rs and choose the instruction lowering in the writers — likely an i64 pair or a runtime helper.
  7. Tests: add a types::tests case and an e2e fixture.

Type identity, equality, and display fall out for free once the PrimTy arm exists — that is the whole point of the structured representation.

Common pitfalls

  • Don't compare types by display_name. Display is lossy/for-humans. Use TypeId == TypeId.
  • Register defs before lowering their uses. An unresolved nominal name lowers to the poison type; lowering must never invent a definition.
  • Reference-ness goes through the interner (is_reference), which strips nullability. Don't re-implement it with string suffix checks.
  • Monomorphization keys are (DefId, Vec<TypeId>). Never reintroduce mangled-string keys.