RecursiveTypes.md

Recursive types — an implementation plan

An implementation plan for making recursive types work — structurally ([count: Int, next: & mut Foo]) exactly as nominally (class, distinct, distinct enum). Today they fail at an accidental cycle detection in the lowering. The style model: EnumImplementation.md, InterfaceStructural.md.

The three ingredients of recursion

Recursion needs three things — separating them cleanly is the whole plan:

1. A name that closes the loop. One cannot write an anonymous recursive type — in order to refer to "itself", the field needs a name (next: & mut Foo). Recursive types therefore always run over a named alias. The alias is the anchor — no distinct or class necessary. Structural types too are definable recursively this way.
2. Binding the knot (the identity cycle). lang types are interned (types.rs:129). Naive hash-consing of a self-reference fails, because one would need the TypeId of the inner type before it exists. The resolution: reserve the TypeId at the alias before lowering the body; a self-reference in the field then already finds it. That holds for structural and nominal RHSs alike.
3. Indirection (the size cycle). A type that contains itself as a value is infinitely large — fundamental, no compiler limit. The resolution: a reference & T (→ C++ T*) or a heap box (Box<T>, internally & mut T) at the back edge makes the size finite.

What goes wrong today: ensure_alias marks the alias as InProgress before it lowers the body; every self-reference runs into "type alias cycle involving X". This one check mixes identity and size and blocks the legal case along with it. The plan separates them: binding the knot (ingredient 2) allows the recursion, and a finiteness check of its own (ingredient 3) reports only the real size cycle any more.

Examples (the target picture)

// Legal: STRUCTURALLY recursive. The alias name closes the loop,
// the reference makes the size finite. No `class`/`distinct` necessary.
type Foo = [count: Int, next: & mut Foo];

// Legal: mutual structural recursion.
type A = [b: & mut B];
type B = [a: & mut A];

// Legal: nominal (class) + heap indirection through Box.
type Tree = class [
    value: Int,
    left:  Box<Tree>,        // Box internally holds `& mut Tree` → finite
    right: Box<Tree>,
];

// Legal: a structural recursive enum over a reference payload (copyable).
type List = enum [ Nil, Cons: [head: Int, tail: & List] ];

// AN ERROR (a size cycle): a value self-reference, infinitely large.
type Bad = [next: Bad];
//   → "recursive type has infinite size; insert indirection
//      (`& mut ...` or a heap `Box<...>`)"

The representation: a cyclic graph + canonicalization at intern time

The goal is real structural identity: type Foo = [count, next: & mut Foo] and an identically shaped Bar should be the same type — and likewise two identically shaped mutually recursive groups (A↔B = C↔D). An approach with de Bruijn Self variables (Rec/SelfVar) solves only the self-recursion canonically; for mutual recursion one would have to serialize the μ term, which is more work than the procedure below. Hence the direct route:

Recursive types stay a cyclic TypeId graph (binding the knot with concrete back TypeIds — no new TypeKind). The identity is canonicalized at interning time: on closing a cycle, a bisimulation collapse (partition refinement, Paige–Tarjan/Hopcroft-like) runs, which merges structurally equivalent nodes into one canonical TypeId.

• One mechanism, no frontier. Self- and mutual recursion are canonicalized uniformly — a mutual group is only a bigger SCC, no special case. A↔B and an identically shaped C↔D collapse automatically.
• A standard procedure. That is the classical decision of equi-recursive structural type equality (Amadio–Cardelli): the type graph is a deterministic, edge-labelled automaton; equality = automaton equivalence, decidable in near-linear time.
• It fits the InternPool invariant. Canonicalization happens eagerly at interning; afterwards "the same TypeId ⇔ the same type" is an integer comparison as usual (types.rs:1-7). No consumer needs a bisimulation comparison at runtime.
• Nominal types carry their uid in the node label — they never merge wrongly with structural ones or with each other. The canonicalization respects nominality automatically.
• The price compared with de Bruijn: no more "free termination" — type walks (display etc.) need a visited set again (local, simple; see M2). In exchange, all Rec/SelfVar surgery by the compiler falls away, and mutual recursion is no special case.

The label & the transitions of the canonicalization. The label of a node is its TypeKind constructor plus the identity-relevant non-type attributes (field names + order, variant names, mutable with a Ref, uid with a Distinct/Class). The transitions are the edges to the field/variant/ inner types. Two nodes are equivalent ⇔ the same label and corresponding transitions lead to equivalent nodes — the usual partition-refinement definition.

M1 — bind the knot + canonicalize (the identity cycle)

• TypePool (src/types.rs): operations for provisional nodes. reserve(kind) -> TypeId pushes a placeholder (empty fields/variants) into kinds without a lookup entry; patch(id, kind) overwrites it with the finalized kind. No new TypeKind — recursive types are ordinary Struct/Enum/Classes whose field TypeIds point back cyclically.
• ensure_alias (src/sema/lower.rs:6) — for every RHS that can be recursive (a structural struct, a structural enum, a Class, a Distinct, later a distinct enum):
  1. reserve with a placeholder.
  2. Set alias_states[index] = Done(reserved) before the body lowering (so far: InProgress). A self-reference now finds Done(reserved) and closes the cycle instead of running into "type alias cycle".
  3. Lower the body (self-references become the reserved TypeId).
  4. patch(reserved, …).
• instantiate_alias (src/sema/lower.rs:113) — analogously for generic instances (Box<Tree>, List<Int>): register the reserved TypeId in alias_insts and from alias_inst_stack before the body lowering; the previous "re-entry = an error" (lower.rs:123-128) becomes "re-entry = return the reserved node".
• Canonicalization at the closing of a cycle (the core of the structural identity): as soon as an alias (or a mutual SCC of aliases) is fully patched, subject the freshly built nodes to a partition-refinement collapse (the label + transitions as in the representation chapter) — both among each other and against already interned types. Equivalent nodes are mapped onto one canonical TypeId (a remap table; the reserved IDs that do not become representatives fall away or are redirected). The collapse runs only for recursive new builds — non-recursive types deduplicate unchanged directly through lookup.
• The result: type Foo = [count: Int, next: & mut Foo] and an identically shaped Bar — as well as two identically shaped mutually recursive groups — get the same canonical TypeId. Non-recursive types are unchanged.

M2 — cycle-safe type walks (a prerequisite)

The cyclic graph brings the visited set back: as soon as a field type points (transitively) at itself, a naive structural walk would descend endlessly. Nominal types abbreviate to the name/uid today and terminate; structural ones do not. Before M3/M4, make the affected walks cycle-safe (a visited set over TypeId or a stop at TypeKind::Ref):

• display (types.rs:182) recurses into fields and Ref.inner → an endless loop with next: & mut Foo. A visited set breaks the cycle off (e.g. printing … at the back edge). Since recursive structural types carry no name of their own in the node, possibly carry the alias name along for the display.
• contains_class, is_copyable and similar field-traversing predicates: a visited set, so that a recursive field does not descend endlessly.
• The movecheck/emit walks over fields: check which stop at references anyway (non-owning) and which need a guard.

The visited set is local and cheap — the deliberate trade compared with the de Bruijn variant (there the walks terminated for free, but at the price of pervasive new variants).

M3 — the finiteness check (the size cycle)

Binding the knot removes the accidental barrier — now the real check is needed, which reports only the illegal value cycle.

• A new check (a pass of its own after the lowering): for every type, follow the value fields transitively (a visited set on the current path); if a value path reaches the starting type again without having crossed a Ref beforehand → the error "recursive type has infinite size; insert indirection". TypeKind::Ref and heap boxes break the walk off (pointer-sized). Box needs no special treatment — the walk ends at its & mut T field (std/box.lang:23). That is Rust's E0072. A back reference behind at least one Ref is exactly the legal case.
• The value dependency graph is thereby guaranteed acyclic — the invariant emit needs in M4.

M4 — emit: forward declarations + a topological value sort

Today "the pool order = the dependency order" holds (emit/mod.rs:219). Binding the knot breaks that: the type is reserved before its fields. Two additions:

1. Forward declarations. Before the definition loop, output a struct <name>; for every struct-like type — a structural Struct (S{n}), a Class, a payload Enum. C++ allows pointers/references (T*) to an incomplete type, and every recursive back edge crosses a pointer by construction. A & mut Foo field emits as a pointer to the (forward-declared) struct of the back-reference type. A prerequisite: pull the name assignment forward — today in the definition loop (emit/mod.rs:229, :256); for forward declarations the names have to stand fixed beforehand.
2. A topological sort of the definitions by value dependencies. The pool order no longer suffices: a value field (left: Box<Tree>) needs the field type completely, but is interned after the enclosing type. So sort the complete definitions by the value graph — reference edges are cut (the forward declaration covers those). The graph is acyclic thanks to M3. (For purely reference-recursive types like Foo the forward declaration already suffices; the sort applies with value chains.)

• Correct the comment emit/mod.rs:219-220.

M5 — recursive enums

It falls out of M1–M4 — structural recursive enums and distinct enums:

type List = enum [ Nil, Cons: [head: Int, tail: & List] ];   // structural

• Reference payloads (& List) are copyable → they work end to end.
• Class payloads (move-only) are now allowed too: the tagged union gets tag-switched special members (default/move/copy/dtor), is constructed through placement new and matched through a const& (see tests/emit/enum_class_payload.lang, tests/e2e.rs::enum_payloads).
• Owning recursive trees (Node: [Box<Tree>, Box<Tree>]) now run end to end (tests/e2e.rs::owning_recursion, ASan/UBSan/leak-clean). For that, Box<T> was made fit for a move-only T: var parameters (the function owns and may move), the runtime primitives construct (placement new into raw memory instead of an assignment) and free = destroy + deallocate.
• The EnumImplementation M3 ("recursion over a nominal anchor") thereby becomes a special case — structural recursive enums need no distinct wrap.

Verification (per milestone, as established)

• cargo fmt --check, cargo clippy (0 warnings), all suites green.
• The examples through g++ -std=c++20 -fsanitize=address,undefined — a linked list built up, traversed, released (ASan/UBSan clean; correct move/deinit with owning recursion).
• New fixtures:
  • tests/errors/recursive_types.lang — a value cycle (type Bad = [next: Bad]), a mutual value cycle: one precise message each.
  • tests/parser/tests/emit/recursive_types.lang — structural (Foo) and nominal (Tree): forward declarations + the definition order in the snapshot.
  • An identity test: identically shaped self- and mutually recursive types collapse into one TypeId (e.g. a function that expects a Foo accepts an identically shaped Bar value).
  • e2e: a list/tree end to end (building, summing, releasing), the exit code checked.
• The emit snapshot changes deliberately in M4 (forward declarations, the order).

Open questions / risks

• The canonicalization is the only non-trivial algorithm here (partition refinement over the type graph). It is standard and well-behaved in time, but the heart of M1 — the test focus: A↔B = C↔D, but A↔B ≠ a differently shaped group; nominal types (uid) never merge. Self- and mutual recursion are thereby both exact.
• Polymorphic recursion (type List<T> = [tail: & List<[T]>], T grows per level) produces infinitely many instances — a real endless loop of the monomorphization, as in Rust/C++. Not a goal; possibly a depth limit on instantiation later. Non-polymorphic recursion terminates through the alias_insts cache.
• Reserved, never patched nodes with field lowering errors: the placeholder (empty fields) has to stay harmless, so that no follow-on errors cascade.
• The move/deinit of owning recursion (Box<Tree>): the generated rule-of-five paths (emit/decls.rs:45) have to cope with the recursive field type. With reference children that falls away.

Status

Implemented and verified (fmt/clippy/all suites green, the examples through g++/ASan/UBSan):

• M1 — bind the knot + canonicalize. TypePool::reserve/patch/kill/ equiv; SCC detection (recursive_alias_set) gates the knot binding only for recursive aliases (non-recursive ones byte-identical). Pure self-recursion is canonicalized: an identically shaped Foo/Bar → one TypeId (a coinductive equiv, a dead placeholder). A cross-round cache (rec_alias_cache) keeps recursive TypeIds stable across monomorphization rounds.
• M2 — cycle-safe walks. display, is_copyable, contains_class, the size/emit walks with a visited set.
• M3 — the finiteness check. A value cycle → recursive type has infinite size; insert indirection.
• M4 — emit. A name pre-pass → forward declarations (only for cyclic types, the snapshots stable) → the definitions in value dependency order (a DFS over embed_deps), dead nodes skipped.
• M5 (partly) — structurally recursive enums with a reference payload run end to end (tests/e2e.rs::recursive_types).

Still open (follow-up turns):

• Mutual recursion: it runs and emits correctly, but is not yet deduplicated (only single SCCs are canonicalized; a node of a mutual group is referenced by its partner — killing it would be unsafe). It needs SCC-wide canonicalization.
• Generic recursion (type List<T> = …): instantiate_alias does not yet bind the knot — a separate path.
• distinct enum recursion and owning Box<…> enum payloads (move-only) — they hang on the enum payload copyability (EnumImplementation.md).