Two ways to be generic: monomorphisation, and the day abstract types lowered without one

There are two honest ways to compile a generic function, and Hew now carries both representations. For a long stretch it only had the first one, and I want to write down how the second one arrived, because the day it landed it changed what the phrase “lower a generic” even means here.

The first way is monomorphisation: pick a concrete instantiation, stamp out a specialised copy with the type filled in, and lower that copy like any other function. The second way is to lower the body once, abstractly, with the type parameter still a parameter — and defer the type-specific operations to a table you fill in later. The first is what most ahead-of-time languages do. The second is what you reach for when there might never be a concrete type to stamp.

Monomorphisation, from the registry up

Start with the simplest generic function there is:

fn id<T>(x: T) -> T {
    x
}

The type checker is perfectly happy to check id once, abstractly — T goes in, T comes out, nothing about the body depends on what T is. But the back end can’t emit a function whose argument has no LLVM type. T isn’t a layout. So before any of id reaches codegen, the compiler has to know which concrete types it’s actually used at.

That knowledge comes from the checker, not from guessing. Every time a generic function is called, the checker records the concrete type arguments it resolved for that call site into a side table — call_type_args. The first piece of the monomorphisation machinery is the consumer of that table: a registry that walks every generic-function call site and turns each distinct use into an entry. Here’s the key it’s built on:

// One MonoKey per distinct instantiation.
//   origin   — the ItemId of the generic fn declaration
//   type_args — the concrete types, in declared order

Pairing on the declaration’s ItemId rather than its name matters more than it looks. Two imported modules can each export a describe; keyed by name they’d collide, keyed by identity they don’t. And the type arguments come in as resolved types, not the checker’s internal Ty — the conversion at that boundary refuses any leaked inference variable or error type, so the registry is fail-closed at the seam it sits on. A half-resolved type can’t sneak into an instantiation key.

So id called at i64, at bool, and at f64 produces three keys, three entries, and — eventually — three separate LLVM functions:

fn main() {
    let a: i64 = id(7);
    let b: bool = id(true);
    let c: f64 = id(3.5);
    println(a);     // 7
    println(b);     // true
    println(c);     // 3.5
}

fn id<T>(x: T) -> T {
    x
}
 
fn main() {
    let a: i64 = id(7);
    let b: bool = id(true);
    let c: f64 = id(3.5);
    println(a);     // 7
    println(b);     // true
    println(c);     // 3.5
}

Each of those gets its own mangled symbol. The mangling scheme renders the origin name and the type arguments into one LLVM-safe string — $$ between the name and its arguments, a single $ between arguments, _ inside nested ones. $ is the sigil for a specific reason: the lexer’s identifier rule only admits [a-zA-Z0-9_], so $ can’t possibly collide with a name a user wrote, and $ is legal in LLVM IR and in ELF, Mach-O, and wasm symbol names. (I tried __ first. The lexer admits __ in identifiers, so two distinct mangles could alias a real symbol. $ is parser-illegal and back-end-legal, which is exactly the property a mangling sigil wants.)

There’s a cap. The registry stops collecting distinct instantiations — 1024 by default — and emits a structured diagnostic rather than collecting forever. (I don’t expect a real program to instantiate one generic at a thousand distinct types. But an inference path that admits T → Vec<T> → Vec<Vec<T>> across successive call sites can grow without bound, and “I don’t expect” is not something the back end can emit. So there’s a cap, and it fails closed.)

Self-recursion is the case I was most worried about looping. fn id<T>(x: T) -> T { id(x) } calls itself — does the registry chase that forever? It doesn’t, and the reason is upstream: the checker refuses to record a call whose type arguments still contain inference variables, so a polymorphic self-call where T is still abstract never lands in the side table at all. Only the concrete outer instantiation does. The registry observes one entry per concrete T and converges by construction.

Substituting the body, and dispatching inner calls

A registry of keys is bookkeeping. The next piece actually consumes it: for each (fn, type_args) pair, MIR emits one specialised function with a fully substituted signature and body. The builder threads a substitution through every write point that takes a type — local allocation, statement construction, the decision-tree lowering for matches — so the substitution is applied at the moment each typed thing is written, not patched up afterward.

Two subtleties earned their keep here.

The first is that a generic body can call another generic function. When outer<i64> calls id internally, that inner call has to dispatch to id’s i64 monomorphisation directly — id$$i64 — not to the generic original through some runtime trampoline. The substitution pass handles this by closing over instantiations: substituting outer’s body makes the inner call site concrete, which feeds a new concrete instantiation of id into the registry, which gets its own specialised function, which the inner call dispatches to by mangled name. No indirection at runtime; the dispatch is resolved entirely at compile time.

The second is the call-site rewrite itself. At each concrete generic call, MIR emits a direct call against the mangled symbol of the matching monomorphisation instead of against the generic original. The generic original, in the end, emits no code of its own — only its specialisations do.

Generic enums and records, end-to-end

Functions were the start. The same machinery generalises to types, and that’s where it stopped being a toy.

For a while there was a guard I was embarrassed about. A generic enum value — Option<i64>, say — would type-check fine and then fall off a cliff at lowering with generic enum values are not yet supported. The checker understood the type; the back end refused to build it. The missing piece was, again, a registry: one keyed on (type_id, mono_args), the structural sibling of the function registry, each entry carrying a layout whose per-variant payload field types have been substituted to concrete types. Option<i64> and Option<string> are two different keys with two different layouts, the way they have to be.

Discovery walks every constructor call site and every match scrutinee, reads the type the checker resolved for that span — from the side table, not from whatever the AST happened to annotate — and feeds the concrete instantiation in. It runs to a fixpoint, because instantiations nest: Option<Option<i64>> has to register both the inner and the outer, and you only find the inner by looking at the outer first.

Here’s the shape that motivated it, lowering the whole way down:

enum Tree<T> {
    Leaf(T);
    Branch(T, T);
}
 
fn root_int(t: Tree<i64>) -> i64 {
    match t {
        .Leaf(v) => v,
        .Branch(a, b) => a + b,
    }
}
 
fn first_string(t: Tree<string>) -> string {
    match t {
        .Leaf(v) => v,
        .Branch(a, _) => a,
    }
}
 
fn main() {
    let ti: Tree<i64> = .Branch(3, 4);
    let ts: Tree<string> = .Leaf("hi");
    println(root_int(ti));        // 7
    println(first_string(ts));    // hi
}

The layout registry discovers both Tree<i64> and Tree<string> from those two construction sites and emits two distinct tagged-union layouts — one whose payload slots are sized for i64, one for the string handle. Codegen consumes a per-(type_id, mono_args) layout, and the not-yet-supported diagnostic narrows to fire only when a generic declaration has zero registered instantiations, which is the genuinely-defensive case where nobody ever used it and there’s nothing to build.

Getting there flushed out a bug I’d nearly shipped. Bare-name constructors — None instead of Option::None — were resolving through a function-signature table on the bare name alone. Two enums can both declare a None, and the lookup could hand back the wrong enum’s variant. The fix was to check that the signature’s type name matches the qualified prefix before accepting it. While I was in there I stopped reconstructing constructor result types from bare names entirely — all three constructor shapes now read the checker-authoritative result type from expr_types[span], with a boundary-violation diagnostic if that side table is somehow absent. The old code rebuilt the type from scratch at each site, which is exactly how you lose the type arguments you spent all that registry work preserving.

Records work the same way, through the structural sibling registry, and the case I cared about for records is impl methods. A by-value method on a concrete generic receiver monomorphises on the receiver:

type Box<T> {
    item: T;
}
 
trait Unwrap<T> {
    fn into_item(self) -> T;
}
 
impl Unwrap<i64> for Box<i64> {
    fn into_item(self) -> i64 {
        self.item
    }
}
 
fn main() {
    let b: Box<i64> = Box { item: 99 };
    println(b.into_item());   // 99
}

The receiver’s concrete type — Box<i64> — is what drives the monomorphisation key. into_item takes self by value, so the specialised function it lowers to has a fully concrete signature: it knows the layout of Box<i64>, it knows item is at a known offset, and the field read is a plain load. There’s nothing abstract left in it by the time codegen sees it.

One authority for every call

Stamping out the right specialisation only works if every call site agrees on which method it’s calling. As the generic surface grew, dispatch had been resolved in a few different places with subtly different rules, and that’s the kind of divergence that ships a wrong call.

So dispatch unified under a single authority. There’s an impl registry — a data-only table of every impl declaration, each carrying the trait, the receiver-type pattern it matches, its where-clause bounds, and its methods. And there’s a single verdict type, ResolvedCall, that the checker populates for each method call site: the impl that satisfied the call, the method, the concrete type arguments, and the resolved target symbol with its calling convention. HIR lowering consults that verdict as the dispatch authority. There is one place that decides what a call resolves to, and everything downstream reads its answer.

The part I insisted on is that the resolver never swallows a None. It commits to one of two things: a ResolvedCall, or a structured LookupError that names exactly what failed — no impl matched the receiver shape, or an impl matched structurally but a where bound wasn’t satisfied (with the offending concrete type captured, so the diagnostic can say “f64 does not implement Hash”), or the method name wasn’t on the impl. And consumers fail closed on a missing entry: if the checker recorded no verdict for a call site, lowering refuses rather than inventing one. Fail-closed-by-absence — silence is a stop, not a default.

The day a generic lowered without a concrete type

Everything above has a precondition baked in. Monomorphisation needs a concrete type before lowering can begin — pick an instantiation, stamp it out, lower the copy. A generic body with no concrete instantiation in sight had nothing to lower to. The whole pipeline insisted on resolving T to something real first.

Removing that precondition is the thing I spent the day on.

The piece that was missing was a representation for an abstract type parameter — one that survives all the way into MIR instead of being a placeholder the pipeline resolves first. MIR’s resolved-type enum gets a new structural variant for exactly that: a T that is genuinely just T, the single authority for an un-monomorphised type. The conversion from the checker’s types is total and lossless in both directions, but it only ever produces this variant inside a scope that actually declares the parameter. The unscoped path can’t produce it at all — which means every existing program, none of which carry abstract parameters into lowering, is completely unaffected. The new variant shows up only where a real type parameter is in scope.

Here’s the shape that now lowers without a concrete type:

type Pair<T> {
    first: T;
    second: T;
}
 
fn swap<T>(p: Pair<T>) -> Pair<T> {
    Pair { first: p.second, second: p.first }
}
 
fn main() {
    let p: Pair<i64> = Pair { first: 1, second: 2 };
    let q = swap(p);
    println(q.first);    // 2
    println(q.second);   // 1
}

Nothing in swap needs to know what T is to be lowered into MIR. It’s lowered once, abstractly. The i64 instantiation that main forces still gets monomorphised for emission — but the abstract body is now a real artefact in its own right, the substrate the monomorphic copy is cut from rather than a thing that can’t exist until a copy is demanded.

Clone, drop, move — through witnesses

“Lowered abstractly” leaves a problem: a generic body still needs to clone, drop, and move values whose type it doesn’t know. You can’t emit the type-specific copy or destructor inline, because there isn’t one yet.

The answer is to not emit those operations as concrete code at all. There are four first-class MIR witness instructions that stand in for the type-dependent operations a generic body needs — size-of, align-of, drop-glue, and move. Each carries a resolved-type operand. When that operand is an abstract T, the instruction is a witness: a promise that says “the size of T goes here,” or “run T’s drop glue on this value,” to be filled in against T’s value-witness table once a concrete type is known.

Conceptually, where the abstract body needs to release or relocate a T, it emits the witness form rather than a concrete one:

// For an abstract T inside a generic body, the operations that would be
// a concrete drop or move on a known type lower to witness ops instead:
//   WitnessDropGlue  — run T's drop glue (vs Instr::Drop on a named fn)
//   WitnessMove      — relocate using T's move semantics
//   WitnessSizeOf / WitnessAlignOf — read size/align from T's witness table
// Each one resolves against the value-witness table at monomorphisation.

WitnessDropGlue is the abstract counterpart of a plain drop: where a concrete drop names a destructor function (or is a trivial no-op), the witness defers the strategy to T’s table, so a value of abstract type can be dropped correctly before its concrete type is known. WitnessMove is the counterpart of a plain move for a value whose LLVM shape isn’t known yet — the size and move glue come from the table at monomorphisation time.

A generic body lowers into a separate polymorphic bucket, kept entirely out of the set of bodies bound for codegen. The monomorphic pipeline still drives everything that actually gets emitted. The polymorphic bodies are the raw material; monomorphisation consumes them later by resolving each witness against a concrete type’s table.

The substitution recurses, which is the part I cared most about getting right. An abstract T inside a borrow, inside a trait object, inside a tuple or array or function type — the traversal walks all of those composite shapes and finds the parameter wherever it’s nested. A witness operand that’s (&T, Vec<T>) resolves both Ts.

And it fails closed, at three points. The witness operand is built through a constructor that admits only a resolved type or a declared type parameter, rejecting any unresolved inference variable outright. The MIR verifier re-checks that every witness operand naming a parameter names one that’s actually declared on the enclosing function — an out-of-scope abstract type, or worse an unresolved inference variable, reaching a witness is a lowering bug, and the verifier rejects it rather than letting it slide. Codegen has the same guard on both ends: an abstract type parameter or a witness instruction arriving at the LLVM emitter is a hard failure, not a guess. The witnesses are real instructions in the IR, but no concrete code can be emitted from one until it’s resolved. (I’d rather the compiler refuse than fabricate a size.)

What this actually buys, and what it costs

Monomorphisation gives you the fastest possible code — every operation is concrete, every layout is known, there’s no indirection. Its cost is code size: id at three types is three functions, and a heavily-generic program can stamp out a lot of nearly-identical machine code.

Value-witness lowering inverts that trade. One body, lowered once, that works for every T — at the cost of going through the witness table for the operations that depend on the type. Size comes from a table lookup instead of being a compile-time constant; drop dispatches through glue instead of a direct call. It’s the indirection monomorphisation spends code to avoid.

The honest state of it today is that both representations exist and the abstract one lowers cleanly into its bucket — but the witness resolution against a concrete type’s table lands with the monomorphisation collector that consumes those buckets, not in this slice. So right now the abstract body is produced and verified and kept off the codegen path, and the monomorphic pipeline still emits all the actual code. The substrate is in place; the consumer that closes the loop is the next piece. I’d rather land the representation fail-closed and on its own — abstract types and witnesses that cannot reach the emitter — than wire the whole path live in one motion and go hunting for a fabricated layout afterward.

That’s the shape of generics in Hew now: a registry that finds every concrete use, specialised functions and layouts stamped from it, one authority that every call defers to, and underneath all of it a way to represent a type that may never be made concrete at all.