Skip to main content

Phase 3. Records, lists, maps, sets

FieldValue
MEPMEP-45 §Phases · Phase 3
StatusLANDED
Started2026-05-22 22:07 (GMT+7)
Landed— (2026-05-25)
Tracking issue—
Tracking PR—

Gate​

Records / collections fixture suite (~80 cases) compiles + runs byte-equal vs vm3 on host triple.

Goal-alignment audit​

To be written before sub-phase 3.0 starts. Records + collections unlock realistic data-shaping code; without them no useful Mochi program compiles. Aligns.

Sub-phases​

#ScopeStatusCommitPR
3.0Record types: struct mochi_R in source field order; field access; record literals; equalityLANDED——
3.1list<T>: per-T mochi_list_<T> (i64 / f64 / bool / str); literals [e, ...]; xs[i]; len(xs); append; for x in xsLANDED——
3.2map<K,V>: per-(K,V) open-addressing hash table; literals {k: v, ...}; m[k]; len; keys; values; k in m; for k in mLANDED——
3.3set<T>: per-T open-addressing hash set; +, -, contains, len, forDEFERRED——

| 3.4a | list<R> (records as list elements): per-record mochi_list_<R> struct + 4 helpers emitted into the TU prologue | LANDED | — | — | | 3.4b | list<list<T>> (T scalar primitive: int / float / bool / string): per-inner mochi_list_list_<inner> struct + 4 helpers in the TU prologue; outer literal / indexing / outer + inner len / outer append / nested for-in / pass + return across function boundary | LANDED | — | — | | 3.4c | Empty literal with type annotation (let xs: list<int> = [], let m: map<K,V> = {}): lowerBinding annotation-thread for zero-element list / map; verifier + emit already correct | LANDED | — | — | | 3.4d | list<T> == list<T> and map<K,V> == map<K,V> for all scalar T / K / V: BinEqList/BinNeList/BinEqMap/BinNeMap in aotir; TU-local eq helpers; 19 fixtures + TestPhase3CollectionEquality gate | LANDED | — | — | | 3.4e | map<K, list<V>> where K in {int, string}, V in {int, float, bool, string} (8 combos): parallel-field ListValueElemType in IR / lower / verifier / emitter; TU-local map-of-list C helpers; 17 fixtures + TestPhase3MapOfList gate | LANDED | — | — | | 3.4f | list<map<K,V>> where K in {int, string}, V in {int, float, bool, string} (8 combos): parallel-field MapElemKeyType / MapElemValueType on list-bearing IR nodes; TU-local mochi_list_map_<K>_<V> helpers; 10 fixtures + TestPhase3ListOfMap gate | LANDED | — | — | | 3.4g | xs[start:end] list slice syntax: lowerListSliceOp dispatched from lowerIndexOp; reuses existing mochi_list_<T>_slice + ListSliceExpr IR from Phase 8.1; TestPhase3ListSlice gate (8 fixtures) | LANDED | — | — | | 3.4h | xs[i] = val for list<T> (4 scalar types) and m[k] = val for map<K,V> (insert/update): ListSetStmt + MapPutStmt IR nodes; lowerIndexAssign in lower; mochi_list_<T>_set + mochi_map_<K>_<V>_put runtime; TestPhase3IndexAssign gate (8 fixtures) | LANDED | — | — | | 3.5 | omap<K,V> (insertion-order map): hash table + parallel insertion-order list (needed by Phase 8) | DEFERRED | — | — |

Decisions made​

Phase 3.0 (records)​

  • Started: 2026-05-22 22:07 (GMT+7)
  • Goal-alignment audit: Records are the floor for every later phase that touches data. Without type R { ... }, neither Phase 3.1 (list<R>), Phase 3.2 (map<K, R>), Phase 4 (sum types over records), Phase 6 (string/IO with structured input), nor Phase 8 (query DSL row shape) can land. The user-facing goal moves: a Mochi program that defines a struct, instantiates it, accesses fields, and prints can now be AOT-compiled to a single C TU. Aligns.
  • Flat Type enum + parallel RecordName strings. aotir.Type stays an int-backed enum with one new variant (TypeRecord). The record's identity rides on a parallel RecordName string on every IR node that can carry a record value (Param, LetStmt, VarRef, Function.ReturnRecordName, CallExpr.ResultRecordName, FieldAccess.ResultRecordName). Rationale: refactoring Type into a struct would force a touch on every type-compare site in the verifier, lower, and emit; the parallel-string approach changes ~12 lines per carrier instead.
  • Field-order normalisation in the lowerer, not the verifier. lowerStructLit reorders the user-supplied literal arguments into the record-declaration order. The verifier then strictly enforces decl-order (the emit pass relies on this so designated-init args render in struct-field order, keeping the C source byte-deterministic for byte-equal inputs).
  • Pass 0 collects records before Pass 1 collects fn signatures. This means a fun mk(): R can reference type R even when the type decl is below the fun in source order (Mochi has no forward decls).
  • No nested records in 3.0. A record field whose type is itself a record is rejected at lower-time. The IR already plumbs RecordField.RecordName and FieldAccess.ResultRecordName for the eventual unlock; the per-record mochi_eq_<Name> helper has the nested-record branch wired but never reached. Lands properly with 3.0.x once a fixture set exists.
  • No print(record) in 3.0. Whole-record printing requires a per-record formatter (deferred to a later sub-phase if needed). print(r.field) works for any scalar field; that covers every fixture.
  • No field assignment in 3.0. r.f = v is rejected: records are value-semantics, so the surface would mean "rebuild and rebind r", which the syntax does not express. Re-assign the whole binding instead.
  • Equality is structural and field-wise. BinEqRec lowers to mochi_eq_<Name>(a, b), a per-record helper that pairwise-compares each field with the appropriate primitive operator (== for scalars, strcmp for strings). BinNeRec is !mochi_eq_<Name>(...). Cross-record-type comparisons are rejected at verify-time. This also unlocks direct string equality via BinEqStr / BinNeStr (== / != on two string operands lower to strcmp(a,b) == 0 / != 0).
  • C99 designated init for record literals. A Pt { x: 1, y: 2 } literal emits as (struct mochi_Pt){.x = INT64_C(1), .y = INT64_C(2)} (a C99 compound literal). Lifetime: the lowerer always binds the literal to a name (or passes it as an arg), so the storage extends to the surrounding block scope under C99 rules.
  • Records are passed and returned by value. static struct mochi_R foo(struct mochi_R p). No * / heap allocation; the C ABI handles it. This matches Mochi's value-semantics.
  • Field naming clash with Mochi keywords. Mochi reserves words like on (event syntax). Record fields named with such words are rejected by the surface parser, not by the lowerer. Two fixtures originally used on and were renamed to enabled before the record-bool gate would parse.

Phase 3.1 (lists)​

  • Started: 2026-05-22 22:38 (GMT+7)
  • Goal-alignment audit: Lists unlock realistic data-flow code: collecting values across loop iterations, holding parsed lines from input, threading results through append in a fold. Without them the surface tops out at scalar arithmetic. Phase 3.2 (map<K, V>) reuses the per-T runtime + monomorphisation pattern that 3.1 introduces; Phase 6 (string/IO) needs list-of-string to model line streams; Phase 8 (query DSL) needs list-of-record as the row sequence. So 3.1 is the smallest step that moves the user-facing goal and the largest pre-req for everything after. Aligns.
  • Scalar element types only in 3.1 (int, float, bool, string). Record and list element types are rejected at lower-time with a Phase 3.1 diagnostic. The IR carries ElemType on every list-bearing carrier (parallel-field pattern, same as Phase 3.0's RecordName); list<R> and list<list<T>> will unlock by widening the lower-time predicate and adding mochi_list_<RecordName> instantiations in Phase 3.4 monomorphisation. The runtime ships only the four scalar instantiations; the i64 path is the reference and the f64 / bool / str helpers are direct copies with the element type substituted.
  • Functional append semantics. xs = append(xs, v) returns a new list with a freshly-malloced buffer and leaves the input list's buffer untouched. Two reasons. First, this matches vm3's OpAppend oracle: vm3 builds a new list value, the AOT-C path must too, or any program that holds an alias to the pre-append list will diverge byte-for-byte. Second, in-place grow with shared backing storage is a Phase 18 (perf) optimisation that requires escape analysis to make safe; we'd rather pay an O(n) memcpy per append now than ship a divergence-prone aliasing model and clean it up later. Empty lists allocate no buffer (data = NULL, len = cap = 0); the first append mallocs a 1-element buffer.
  • Empty list literal [] is rejected. A bare [] has no element-type information for the lowerer to pick a runtime instantiation, and the surface has no annotation form yet. Programs that need an empty list must use let xs: list<int> = [] once Phase 3.4 lands a typed-empty path, or seed with one element. Rejection message: "empty list literal: Phase 3.1 requires at least one element so the element type can be inferred".
  • xs[i] is a runtime bounds check, not a verified static one. The index expression always lowers to mochi_list_<T>_index(xs, i) which compares against len and trips mochi_panic_index() on out-of-range (exit code 4, MOCHI_ERR_INDEX). Negative indices are rejected (vm3 does not have Python-style negative indexing; the AOT path must agree). Slice syntax (xs[a..b]) is rejected in 3.1 with a Phase 3.1 diagnostic; it lands with the string/list slice unification in Phase 6.
  • C99 compound literal for list-lit buffer storage. [1, 2, 3] emits as mochi_list_i64_lit((const int64_t[]){INT64_C(1), INT64_C(2), INT64_C(3)}, INT64_C(3)). The compound literal lives in automatic storage at the enclosing block, then mochi_list_i64_lit memcpys it into a heap-malloced buffer that the list value owns; this keeps the list literal source-deterministic and avoids a per-fixture static initialiser.
  • Per-T runtime now, monomorphisation later. 3.1 ships four hand-written instantiations of the list helpers (one per scalar element type, ~40 LOC each). This is small enough to maintain by hand and avoids dragging the monomorphisation pass forward. Phase 3.4 collects the concrete (op, T) set the program uses and emits exactly the helpers needed; the runtime then drops the unused per-T helpers from libmochi. Until then, every program links against all four instantiations regardless of which it uses; dead-code elimination at the linker handles the bloat.
  • for x in xs is a length-bounded numeric loop. The for-each lowers to a fresh block that captures the list into a __mochi_list_x temp, queries len once into __mochi_len_x, and iterates 0..len with __mochi_i_x, fetching x = mochi_list_<T>_index(__mochi_list_x, __mochi_i_x). The capture + length-cache pattern matches vm3's iterator snapshot semantics (mutation of the underlying list inside the loop body does not change the iteration set). The temp names are mangled with the loop variable to avoid nested-for collisions.
  • Lists are passed and returned by value. static mochi_list_i64 foo(mochi_list_i64 xs). The struct header (data + len + cap) copies; the buffer is shared until the next append allocates a fresh one. This matches Mochi's value-semantics surface and the C ABI handles the by-value struct passing without any heap-alloc hops.
  • Lifetime: leak on program exit in 3.1. No free() calls. The OS reclaims at process tear-down. Phase 7 (error model + panic unwinding) adds a real reclamation path; until then the lists keep their buffers for the full program lifetime. The tradeoff is intentional: a refcounted or arena-backed scheme adds runtime complexity that the fixture suite would not exercise, and shipping the user-facing surface earlier is the goal.

Phase 3.2 (maps)​

  • Started: 2026-05-22 23:00 (GMT+7)
  • Gate green: 2026-05-22 23:25 (GMT+7), 22 fixtures passing (TestPhase3Maps).
  • Goal-alignment audit: Maps are the smallest collection that lets a Mochi program model lookup tables (word counts, lookup-by-id, configuration, indices into other collections). Without them every program that needs associative storage has to fall back to two parallel lists + linear scan. Phase 3.5 (omap<K,V>) inherits the entire per-(K,V) runtime + parallel-field plumbing this phase introduces; Phase 8 (query DSL) needs map<K, list<R>> as the group-by accumulator shape; Phase 9 (streams/agents) needs map<id, agent> as the actor-registry shape. So 3.2 is the smallest pre-req that unlocks four downstream phases worth of code. Aligns.
  • Hand-rolled open-addressing, not cwisstable. The original MEP table named cwisstable as the underlying table. We swapped to a hand-written open-addressing + linear-probe + load-factor-0.5 implementation (~120 LOC under MOCHI_MAP_DEFINE) for three reasons. First, no vendored C dep keeps the runtime portable across the eventual cross-target matrix (Phase 11) without picking up <emmintrin.h> or <arm_neon.h> SIMD intrinsics. Second, the SplitMix64 finalizer for i64 keys matches runtime/vm3/maps.go::hashI64 byte-for-byte, so fixtures that count hash-table collisions stay deterministic across the vm3 oracle and the AOT path. Third, ~120 LOC of macro-expanded C beats ~3kLOC of vendored SIMD when the fixtures top out at ~100 entries; cwisstable's perf advantage doesn't appear until Phase 18 perf work, where the table swap is a one-symbol-set substitution behind the same mochi_map_<K>_<V>_* ABI.
  • Eight (K,V) instantiations in 3.2. Keys are restricted to int and string; values to the four scalars (int, float, bool, string). The runtime ships all eight under mochi_map_<K>_<V>_* symbol names; the lowerer rejects record / list keys or values at lower-time with a phase-named diagnostic. Map-of-record and nested maps land with Phase 3.4 monomorphisation, same as the list-of-record path.
  • KeyType + ValueType parallel fields on every map-bearing IR carrier. Same parallel-field pattern as Phase 3.0's RecordName and Phase 3.1's ElemType. Param, Function.ReturnKeyType / ReturnValueType, LetStmt, VarRef, CallExpr.ResultKeyType / ResultValueType, and the six map exprs (MapLit, MapGetExpr, MapHasExpr, MapLenExpr, MapKeysExpr, MapValuesExpr) carry the parallel pair beside Type==TypeMap. The alternative (Type as a struct, or a registry-of-instantiations) would touch every type-compare site in the verifier; the parallel-field approach changes ~20 lines per carrier instead.
  • Sort-on-iteration via insertion-sort snapshot. Both for k in m and keys(m) / values(m) snapshot the live entries into a fresh buffer, then insertion-sort by key (< for i64, strcmp for strings). This matches vm's key-sorted iteration order so byte-equal stdout against the vm3 oracle is achievable. Insertion sort suffices at fixture scale (~100 entries worst case); a merge-sort or heap-sort drop-in is a Phase 18 perf task behind the same snapshot interface.
  • Functional / immutable in 3.2. No m[k] = v, no delete(m, k). Maps are constructed once from a literal (or let m = mk()) and queried thereafter. Mutation lands in a later sub-phase that also brings list mutation; until then m = {...} rebinds the whole map. This matches the vm3 oracle's value-semantics for map literals.
  • k in m is the membership test, no has() surface. The Mochi type-checker recognises in as a binary operator that produces bool when the right operand is a map<K, V>. The lowerer special-cases that pattern in lowerBinary to emit a MapHasExpr instead of a BinaryExpr. We also wire a has(m, k) builtin in the lowerer so future fixtures that prefer call syntax still work; both surfaces lower to the same MapHasExpr node.
  • m[k] panics on missing key in 3.2; no Option yet. A failed lookup trips mochi_panic_index() (exit code 4, MOCHI_ERR_INDEX); programs that must probe first should use k in m and only then index. The Mochi type-checker types m[k] as option<V> on the surface, so any arithmetic that uses m[k] directly fails type-check today; fixtures sum via values(m) or index after a successful in check. Real option-aware unwrap arrives with Phase 4 (option types).
  • for k in m is sugar for for k in keys(m). The lowerer synthesises a MapKeysExpr inline and re-uses the existing ForEachStmt. No new IR node, no new emit-time path; the emitter doesn't even know the loop's source was a map. This keeps the for-each shape stable across collection types.
  • Empty map literal {} is rejected (mirrors list rule). A bare {} has no (K, V) for the lowerer to pick an instantiation, and the surface has no annotated-empty form yet. A future typed-empty path lands with Phase 3.4 once the lowerer threads annotated-binding types into literal-time resolution. Rejection message: "empty map literal: Phase 3.2 requires at least one entry so the key and value types can be inferred".
  • Lifetime: leak on program exit, same as 3.1. No free() for table buffers or the per-call snapshot allocations under keys() / values(). Phase 7 (panic unwinding) adds a real reclamation path. The per-call snapshot allocations are a known leak proportional to call count, accepted for fixture-scale programs.

Phase 3.3 (sets): DEFERRED​

  • Audit date: 2026-05-22 23:55 (GMT+7)
  • Goal-alignment audit verdict: DEFERRED. Mochi has no set<T> surface syntax. parser/ast.go has no SetLit or SetType node; types/kinds.go has no SetType (only ListType, MapType, GroupType); the type-checker recognises a distinct(list) builtin that dedupes a list into another list, not a set value. Implementing set<T> in transpiler3 alone would produce a runtime + IR + emit chain that no Mochi program can reach: the parser would reject let s: set<int> = {1, 2} before the lowerer ever ran. The user-facing goal moves by zero, every Phase 3.3 LOC would be unreachable scaffolding. Per the goal-alignment-audit rule we defer.
  • Unblock condition. Adding set<T> to MEP-45's user-facing surface requires Mochi parser + type-checker work that belongs in a different MEP (likely the Mochi language MEP track, not the AOT-backend MEP-45). Once Mochi gains set<T> parsing + a SetType kind, Phase 3.3 reactivates: per-T open-addressing hash set (4 instantiations: i64 / f64 / bool / str), + (union), - (difference), contains(s, e), len(s), for e in s key-sorted iteration. The runtime drops into transpiler3/c/runtime/{include/mochi/set.h, src/set.c} as a value-slot-elided cousin of mochi_map_<K>_<V>_*; the IR + lower + emit chain mirrors Phase 3.2 exactly, swapping the (K,V) pair for a single (T) element.
  • No fixture corpus today. Without a parsable Mochi surface there is nothing to fixture against the vm3 oracle. TestPhase3Sets is not authored; the gate row in the table reads DEFERRED and will not block downstream phases.

Phase 3.4a (list: records as list elements)​

  • Started: 2026-05-22 23:55 (GMT+7)
  • Gate green: 2026-05-23 00:25 (GMT+7), 17 fixtures passing (TestPhase3MonoListRecord).
  • Goal-alignment audit: list<R> is the row-sequence shape that Phase 8 (query DSL) and most realistic data programs depend on. Without it the language can manipulate scalars and individual records but cannot accumulate them into the sequences a real workload produces. 3.4a is the smallest step that unlocks that surface: pass list<R> to a function, append onto it, iterate it, return it. The remaining 3.4 sub-phases (b: nested collections, c: typed-empty literal, d: list / map equality) are independent and can land in any order on top of this foundation. Aligns.
  • Per-record helpers emitted into the TU prologue, not libmochi. The scalar list helpers (mochi_list_i64_*, etc.) ship in libmochi because the element type is known up front. For list<R> the element type is a user-defined struct mochi_<R> that only exists inside the program's translation unit; emitting the per-record list runtime into libmochi would require either pre-declaring every conceivable record (impossible) or punching a generic void-pointer hole in the runtime (defeats the type-safety goal of monomorphisation). Instead, the emitter walks the program after emitRecordDecls, collects every unique record name used as a list element across function signatures + bodies, and emits a mochi_list_<R> struct + 4 helpers (_lit, _append, _index, _len) per record into the TU prologue. The helpers are static to keep them TU-local. The shape is a direct port of mochi_list_i64's source, with int64_t replaced by struct mochi_<R>. Same heap-malloced-buffer / value-semantics / leak-on-exit ownership model.
  • ElemRecordName parallel field on every list-bearing IR carrier. Same pattern as Phase 3.0's RecordName and Phase 3.2's KeyType / ValueType. Param, Function.ReturnElemRecordName, LetStmt, VarRef, CallExpr.ResultElemRecordName, ListLit, IndexExpr, LenExpr, AppendExpr, ForEachStmt each carry the parallel string beside Type==TypeList / ElemType==TypeRecord. The verifier strictly enforces that ElemRecordName is non-empty when ElemType==TypeRecord, and that the named record is declared. The alternative (Type as a struct, or threading a per-instantiation registry through every type-compare site) would touch ~50 sites in the verifier; the parallel-string approach adds ~10 lines per carrier.
  • listSuffix returns the record name for list<R>. Scalar suffixes (i64, f64, bool, str) resolve to libmochi exports. The record suffix resolves to the TU-local mochi_list_<R>_* helper family. Everything downstream (literal emit, index emit, len emit, append emit, for-each emit) is record-agnostic at the call site: it queries listSuffix(elem, elemRec) and emits the same shape of helper call regardless of whether T is a primitive or a record.
  • cListBufferElemC extended to TypeRecord. The compound-literal array temporary that backs a [r1, r2, r3] list literal needs a per-record element type; the helper now returns struct mochi_<R> when elem == TypeRecord. The C99 designated-init records emitted by lowerRecordLit slot directly into this temp, so the list-of-record literal renders as mochi_list_<R>_lit((const struct mochi_<R>[]){(struct mochi_<R>){.x=1,.y=2}, ...}, INT64_C(2)) without any extra heap hop.
  • <stdlib.h> is pulled in only when list-of-record helpers are emitted. malloc lives in <stdlib.h>, and the per-record helpers need it. But unconditionally including <stdlib.h> exposes the program to name clashes with stdlib symbols (abs, div, exit); we saw the abs collision in the Phase 2.2 fun_early_return fixture, which defines its own abs. The fix: the emitter calls collectListRecordElems(prog) first, and the #include <stdlib.h> line is only added when that set is non-empty. The scalar list helpers continue to get their malloc from list.c's own translation unit so this header is needed only for the TU-local helpers.
  • isListElemType widened to accept TypeRecord. The lowerer's predicate that gates which element types list<T> may carry now accepts TypeInt, TypeFloat, TypeBool, TypeString, and TypeRecord. Nested list / nested map element types remain rejected with a phase-named diagnostic pointing at Phase 3.4b. The verifier's parallel predicate widened the same way; verifyListLit, verifyIndexExpr, verifyLenExpr, verifyAppendExpr all accept TypeRecord element and require ElemRecordName to be non-empty + declared.
  • exprElemRecordName plumbed through every list-flowing site. A new lowerer helper that mirrors exprElemType: it pulls the elem record name out of whichever Expr variant carries one (VarRef, ListLit, CallExpr, AppendExpr, IndexExpr). The lowerer threads it through assign / return / call-args / for-each / append, and the verifier rechecks the invariant on every carrier. The IndexExpr case is new in 3.4a because list<R> indexing returns a record (the receiver's ElemRecordName becomes the result's RecordName); scalar list indexing returns a primitive so no record name flows through that path.
  • Typechecker gap closure: op.Field in checkPostfix. ps[0].x parses as Selector(ps) + IndexOp(0) + FieldOp(x). The selector-tail fast path in checkPrimary collapses Root.tail field walks into the symbol lookup, but it only fires when the entire chain is selector-prefix. As soon as an Index or Call step lands between the root and the field, the loop in checkPostfix takes over, and that loop had branches for Index / Call / Cast / SafeField / SafeIndex but not for the bare op.Field. The result: the typechecker left typ as the record-typed receiver and the caller saw a type mismatch ("expected int, got Pt"). The fix adds a Field branch that mirrors checkPrimary's StructType / Methods / unknown-field paths plus an AnyType passthrough. The bug went undetected because every prior list-of-record fixture passed ps[0].x to print (which accepts any type and asks the lowerer, not the typechecker, for the C type); only a function with an explicit non-record return type surfaced the gap.
  • Lifetime: leak on program exit, same as 3.1. No free() for the per-record buffers. Phase 7 (panic unwinding) adds reclamation. The per-record helpers are direct copies of the scalar list helpers' ownership model.

Phase 3.4b (list<list<T>>: nested lists of scalars)​

  • Started: 2026-05-23 00:43 (GMT+7)
  • Gate green: 2026-05-23 01:21 (GMT+7), 17 fixtures passing (TestPhase3NestedLists).
  • Goal-alignment audit: list<list<T>> is the smallest nested-collection shape that unlocks realistic data programs: matrices, rows-of-columns, group-by accumulators that haven't yet grown a key (Phase 3.4e brings the keyed form). Without it the language can hold scalar-keyed flat lists but cannot model jagged 2-D data or a "list of rows" where each row is itself a sequence. Phase 8 (query DSL) needs the keyed map-of-list form, but the unkeyed list-of-list is the structural floor — 3.4e and 3.4f reuse exactly the parallel-field plumbing this phase introduces. The remaining 3.4 sub-phases (c: typed-empty literal, d: list / map equality, e: map-of-list, f: list-of-map) are independent and can land in any order on top of this foundation. Aligns.
  • Scope: scalar inner element types only. The inner element type T is restricted to the four scalar primitives (int / float / bool / string). list<list<R>> (records in the inner list), list<list<list<T>>> (3-level nesting), and list<list<map<...>>> are rejected at lower-time with phase-named diagnostics. Rationale: the per-inner helper family is parameterised on the inner suffix (one of i64 / f64 / bool / str), so a record inner would need a fresh (outer, R) instantiation that mixes the record-list strategy (TU-local per-record struct) with the nested-list strategy (TU-local per-inner struct). Worth its own gate; deferred to 3.4b.1 when a fixture pulls on it.
  • Parallel-field InnerElemType on every list-bearing IR carrier. Same parallel-field pattern as Phase 3.0's RecordName, Phase 3.1's ElemType, Phase 3.2's KeyType / ValueType, and Phase 3.4a's ElemRecordName. Param.InnerElemType, Function.ReturnInnerElemType, LetStmt.InnerElemType, VarRef.InnerElemType, CallExpr.ResultInnerElemType, ListLit.InnerElemType, IndexExpr.InnerElemType, LenExpr (carried via receiver), AppendExpr.InnerElemType, ForEachStmt.InnerElemType each carry the parallel aotir.Type beside Type==TypeList && ElemType==TypeList. The verifier strictly enforces that InnerElemType is one of the four scalar primitives when ElemType==TypeList, and zero (TypeUnknown) otherwise. The alternative (Type as a struct, or threading a per-instantiation registry through every type-compare site) would touch every type-compare site in the verifier and lower; the parallel-field approach adds one field per carrier and is mechanically a copy of the 3.4a path.
  • IndexExpr.ElemType semantic: "produced value type". For a list<list<int>> receiver, xs[0] produces a list<int> value, so IndexExpr.ElemType is TypeList and InnerElemType is TypeInt. This differs subtly from VarRef.InnerElemType (which is "the T inside list<list<T>>" for the variable's declared type); the disambiguation is that IndexExpr.ElemType describes the produced value, not the receiver's element shape. The lowerer's exprInnerElemType helper gates InnerElemType extraction on producedElem == TypeList so callers (lowerLenCall, lowerAppendCall, lowerForEach) don't accidentally treat a flat list's ElemType==TypeInt (with InnerElemType==TypeInt per IndexExpr's "T is element" convention) as a nested list.
  • Per-(outer, inner) TU-local helpers, not libmochi. Same rationale as Phase 3.4a's per-record helpers: the inner element type is mochi_list_<inner> (a libmochi struct), but the outer carrier mochi_list_list_<inner> is a composite that only exists inside the program's TU once it actually appears. Emitting one of every (outer, inner) combination into libmochi would multiply the runtime surface by 4 with no payoff. Instead, the emitter walks the program after emitListRecordHelpers, collects the set of inner scalar types actually used in list<list<T>> contexts (via collectListListInners), and emits a mochi_list_list_<inner> struct + 4 helpers (_lit, _append, _index, _len) per inner type into the TU prologue. The helpers are static to keep them TU-local. Shape is a direct port of mochi_list_i64's source with the element type substituted by mochi_list_<inner>.
  • listSuffix widened to return "list_<inner>" for nested lists. Scalar suffixes (i64, f64, bool, str) resolve to libmochi exports. The record suffix (3.4a) resolves to TU-local mochi_list_<R>_*. The nested-list suffix list_<inner> resolves to TU-local mochi_list_list_<inner>_*. Everything downstream (literal emit, index emit, len emit, append emit, for-each emit) is shape-agnostic at the call site: it queries listSuffix(elem, elemRec, innerElem) and emits the same shape of helper call regardless of whether T is a primitive, a record, or another list. The scalarListInnerSuffix(inner) helper handles the inner-suffix mapping for the per-helper emit.
  • cListBufferElemC widened to nested lists. The compound-literal array temporary that backs an [[1, 2], [3]] outer literal needs a per-(outer, inner) element type; the helper now returns mochi_list_<inner> when elem == TypeList. Each inner list literal renders as mochi_list_<inner>_lit(...) and lifts directly into the outer compound-literal array, so the full nested literal renders as mochi_list_list_i64_lit((const mochi_list_i64[]){mochi_list_i64_lit((const int64_t[]){1, 2}, 2), mochi_list_i64_lit((const int64_t[]){3}, 1)}, 2) without any extra heap hop.
  • Foreach induction-var C type emitted directly via scalarListInnerSuffix. When iterating for row in mat where mat : list<list<T>>, the induction var row has C type mochi_list_<inner> (the inner list type), NOT mochi_list_list_<inner> (which would describe the outer carrier). The default cTypeFull(TypeList, "", innerElem, ...) path renders the outer C type by composing the suffix, so the emit foreach path special-cases s.ElemType == TypeList and computes elemC = "mochi_list_" + scalarListInnerSuffix(s.InnerElemType) directly. The bug this avoids: emitting mochi_list_list_i64 row; and trying to assign mochi_list_i64_index(__mochi_list_row, ...) into it, which the C compiler correctly rejects as an incompatible-pointer-target.
  • Aliasing of inner buffers is intentional and benign in 3.4b. The outer-list helpers do a header-only memcpy (each element is a mochi_list_<inner> struct value, which itself holds a heap data pointer + len + cap). That means an outer literal [a, b] where a and b are pre-bound inner lists shares the inner data buffers between the outer's elements and the original a / b bindings. Cross-mutation (appending to a after embedding it in the outer list) would diverge from vm3's eager-copy semantics. Phase 3.4b's fixtures are read-only at the inner level, so no fixture exercises this divergence; a proper deep-copy on outer-literal construction lands when a fixture pulls on it (or with Phase 18 perf when escape analysis lets us elide it where safe).
  • <stdlib.h> include condition widened to also cover nested lists. Same condition as 3.4a: the per-(outer, inner) helpers need malloc, and that lives in <stdlib.h>. The include is added only when at least one of collectListRecordElems(prog) or collectListListInners(prog) is non-empty, to keep the Phase 2.2 fun_early_return fixture (which defines its own abs) free of name clashes with stdlib symbols.
  • Lifetime: leak on program exit, same as 3.1. No free() for the per-(outer, inner) buffers. Phase 7 (panic unwinding) adds reclamation. The per-inner helpers are direct copies of the scalar list helpers' ownership model with the element type substituted.
  • Reject-test surface unchanged for the cases that still reject. Phase 3.1's let xs = [[1, 2], [3]] rejection moves from "Phase 3.4" to "accepted by 3.4b"; the nested_list row in lower_reject_test.go is removed in this phase. The empty-list-literal rejection (let xs = []) remains, deferred to 3.4c. The list-of-record element rejection (which 3.4a unlocked) remains accepting. No other reject-test rows shift.

Phase 3.4c (typed-empty collection literals)​

  • Started: 2026-05-25 12:17 (GMT+7)
  • Gate green: 2026-05-25 12:17 (GMT+7), 18 fixtures passing (TestPhase3TypedEmptyLiteral).
  • Goal-alignment audit: Programs that accumulate values into a list (or track state in a map) almost universally start from an empty container: var xs: list<int> = [] then append in a loop, or var m: map<string, int> = {} then query after construction. Without 3.4c, the only way to seed an empty list is to use a one-element literal and pop it (impossible — no pop in Phase 3.4) or to depend on a function that returns a seeded list. Both workarounds are awkward and non-idiomatic. 3.4c closes the last initialization gap in Phase 3.4, leaving only equality (3.4d) and nested-collection shapes (3.4e, 3.4f) as outstanding items. Aligns.
  • One change point: lowerBinding intercepts before lowerExpr. The entire pipeline from verifier through emitter was already correct for zero-element IR: verifyListLit iterates v.Elems (empty = no iterations, returns nil), emitListLit special-cases len(v.Elems) == 0 to emit mochi_list_<T>_lit((const <elemC>[]){0}, INT64_C(0)), and emitMapLit similarly emits empty-array forms for zero-entry maps. The only blocker was in the lowerer's literal functions: lowerListLit and lowerMapLit each reject len == 0 immediately because without a declaration annotation there is no type to infer. The fix adds two sentinel helpers (isEmptyListLit, isEmptyMapLit) that walk the parser-Expr tree down to the Primary node and check Primary.List.Elems == 0 / Primary.Map.Items == 0. In lowerBinding, when declared != nil, the helpers fire before lowerExpr; if either matches, typeFromRef resolves the annotation and the IR node is constructed directly, bypassing lowerListLit / lowerMapLit entirely. The normal path is unchanged.
  • isEmptyListLit / isEmptyMapLit must handle the full parse-tree traversal. A Mochi expression [] parses as Expr.Binary.Left.Value.Target.List — the tree is Expr → BinaryExpr → Unary → PostfixExpr → Primary. Each level must be checked: BinaryExpr.Right must be empty (no binary operator), Unary.Ops must be empty (no - / !), PostfixExpr.Ops must be empty (no ., [], () postfix), and Primary.List must be non-nil with zero elements. Any deviation (the expression is a complex formula that happens to return a list) falls through to the normal lowerExpr path, where the rejection error from lowerListLit fires if the result truly is an empty list — which is correct because a complex expression cannot be typed from the annotation alone.
  • let xs = [] (without annotation) still rejects. The declared == nil branch in lowerBinding falls through to lowerExpr unconditionally, so the Phase 3.1 rejection message ("empty list literal: Phase 3.1 requires at least one element...") still fires for unannotated empty literals. The lower_reject_test.go empty_list_literal case is preserved.
  • xs = [] (assignment, not binding) still rejects. lowerAssign calls lowerExpr directly on the RHS and has no access to the binding's declared type. For Phase 3.4c the interesting pattern is seed-then-append, which only needs the binding. If a fixture pulls on xs = [] as a reset, it will be handled in a follow-up sub-phase.
  • Fixture scope: 18 fixtures covering all four scalar list types and two map shapes. List fixtures: len=0 for all four scalars (int / float / bool / string); var + append + for-in accumulation for all four scalars; for-in over empty list (no element output); pass empty list to function / return empty list from function; conditional fill (if true { append }, print elements); index after single append. Map fixtures: len=0 for map<int,int> and map<string,int>; in-check returns false; pass to function / return from function across the boundary.
  • mochi_list_<T>_lit with (const T[]){0} for empty case. The C emitter passes a one-element compound-literal array {0} as the data pointer and count INT64_C(0). This avoids a NULL dereference in the _lit helper's memcpy if it ever reads count > 0 elements from the pointer (it doesn't when count is 0, but this makes the code more robust against future helper changes). A follow-up that normalises len==0 to NULL pointer + 0 count is a Phase 18 micro-opt.
  • Lifetime: same leak-on-exit model as 3.1. Zero-element lists allocate nothing (the _lit helper skips malloc when count is 0 and sets data = NULL); zero-entry maps similarly allocate a minimum-capacity table. Phase 7 adds reclamation.

Phase 3.4e (map<K, list>)​

  • Started: 2026-05-25 12:17 (GMT+7)
  • Gate green: 2026-05-25 13:21 (GMT+7), 17 fixtures passing (TestPhase3MapOfList).
  • Goal-alignment audit: map<K, list<V>> is the keyed counterpart to Phase 3.4b's list<list<T>>. It enables the group-by accumulator pattern (for row in data { m[key].append(row) } -- with a mutation path yet to land) and is a direct prerequisite for Phase 8's query-DSL row-set model. Without it, programs must flatten or hand-roll parallel key/value arrays. Aligns.
  • Parallel-field pattern reused from Phase 3.4b. Every IR node that can carry a map<K,list<V>> value gets a new parallel field ListValueElemType aotir.Type alongside the existing ValueType. This follows the exact same pattern as InnerElemType on list nodes (Phase 3.4b). The lowerer, verifier, and emitter all receive the field; callers that don't care pass aotir.TypeInvalid.
  • TU-local map-of-list helpers instead of runtime module. The scalar map<K,V> helpers are emitted as externally-visible symbols from map.c (using MOCHI_MAP_DEFINE). For map<K,list<V>>, a different approach is used: per-(key, inner) C helper bundles are emitted inline into the TU prologue, similar to how Phase 3.4a emits per-record list helpers. The reason is that map.c's hash functions are static inline, so they cannot be called from a separately-compiled helper. Each bundle includes: hash guards (#ifndef MOCHI_MAP_LIST_HASH_HELPERS), struct typedefs, _lit, _get, _has, _len, _snapshot_, _keys, _values.
  • values(m) on map<K,list<V>> returns mochi_list_list_<inner>. Because _values returns a list<list<V>>, the mochi_list_list_<inner> helper must be emitted before the map-of-list helpers. Emit() augments listListInners with all inner types found in map-of-list pairs, ensuring the outer emitListOfListHelpers call fires first.
  • eqFn closure for type-safe equality in map C helpers. The _lit, _get, and _has helpers each compare keys differently: integer keys use ==, string keys use strcmp. Rather than a static eqExpr string (which used placeholder variable names a and b), an eqFn func(x, y string) string closure is used. Each helper call site passes the concrete left-hand and right-hand key expressions.
  • Bug fix: function-parameter scope seed was missing listValElem. When a function parameter is map<K,list<V>>, the lowerer seeds the parameter into the function scope as an lbinding. Previously, listValElem was not included in the seed, so any values(m) call inside the function body received ListValueElemType = TypeInvalid on the resulting MapValuesExpr. This caused list<list<V>> bindings derived from values(m) to have innerElem = TypeInvalid, and the induction variable of a for row in vs loop then had ElemType = TypeInvalid, triggering a type-mismatch error when the row was passed to a list<int> parameter. Fix: add listValElem: p.ListValueElemType to the scope-seed loop in lower.go.
  • m[k] still unavailable for list-valued maps. The VM3 type-checker wraps m[k] in OptionType{Elem: V}. When V is a list, m[k] becomes option<list<V>> which cannot be indexed with [i] or have len called. All fixtures use values(m) and nested for loops instead. Direct key access will unblock with Phase 4 option types.
  • 17 fixtures, 4 operations x 2 key types x 4 scalar value types. Fixture matrix: mol_{int,str}_list_{int,float,bool,str}_basic (literal + len + in-check + values() + nested for), plus mol_int_list_int_{values,for_keys,for_key_index_val,has,map_len,literal_get_len,passed_to_fn,returned_from_fn} and mol_str_list_int_{values,for_keys}. All 17 pass TestPhase3MapOfList.

Phase 3.4d (list / map equality): LANDED 2026-05-25 13:53 (GMT+7)​

  • Audit date: 2026-05-25 12:17 (GMT+7) (initial deferral); 2026-05-25 13:40 (GMT+7) (reactivated)
  • Reactivation note. The earlier deferral incorrectly assumed the oracle (mochi run) required vm3 list/map comparison opcodes. In fact mochi run uses the archived tree-walking interpreter (archived/interpreter/runtime_utils.go), which already handled == / != on lists and maps via applyBinaryValue. The type-checker also already allowed collection equality (the unify(left, right, nil) branch in check_expr.go returns BoolType{} for two ListType values with unifying element types). The only missing piece was the AOT transpiler itself.

Decisions Made​

  • IR. Added BinEqList, BinNeList, BinEqMap, BinNeMap to the BinOp enum in aotir/program.go. No new fields: the element / key / value types are recoverable from the operand expressions via exprListElemType / exprMapKeyType / exprMapValueType (mirroring the existing exprRecordName pattern from Phase 3.0).
  • Verifier. Added the four new ops to binOpSignature with signatures (TypeList, TypeList, TypeBool) and (TypeMap, TypeMap, TypeBool). The generic binary-expr verifier path (line 1146) handles the rest.
  • Lowerer. Added two new cases in lowerBinaryOp's "==", "!=" arm: one for TypeList x TypeList and one for TypeMap x TypeMap. Only == and != are accepted; ordering operators on collections return an error.
  • Emitter. TU-local static helpers rather than adding to libmochi:
    • mochi_eq_mochi_list_<suf>: length check then element-wise != (scalars) or strcmp(...)!=0 (strings).
    • mochi_eq_mochi_map_<K>_<V>: nLive parity check then iterate live entries in a.table, for each entry look up the same key in b via _has + _get, compare values.
    • collectListEqElems / collectMapEqPairs walk the program's AST for BinEqList/BinNeList/BinEqMap/BinNeMap nodes and deduplicate the needed helper signatures. Helpers are emitted after the map-of-list helpers so all list types they reference are already declared.
  • Fixtures. 19 fixtures under tests/transpiler3/c/fixtures/collection_equality/:
    • List: leq_int_eq_ne, leq_int_empty, leq_int_len_mismatch, leq_float_basic, leq_bool_basic, leq_str_basic, leq_in_if, leq_fn_param, leq_append_then_compare.
    • Map: meq_i64_i64_basic, meq_i64_str_basic, meq_i64_bool_basic, meq_i64_float_basic, meq_str_i64_basic, meq_str_str_basic, meq_empty_eq, meq_diff_keys, meq_in_if, meq_fn_param.
  • Gate. TestPhase3CollectionEquality — all 19 fixtures pass.

Phase 3.4f (list<map<K,V>>): LANDED 2026-05-25 14:30 (GMT+7)​

  • Audit date: 2026-05-25 14:10 (GMT+7)
  • Goal-alignment audit: list<map<K,V>> is the dual of Phase 3.4e (map<K,list<V>>). Programs that need "a sequence of associative rows" — e.g., a list of configuration objects, a batch of query results before they are keyed, or an event log where each event is a property bag — all reach for list<map<K,V>>. Without it, representing a variable-length sequence of maps requires awkward workarounds (parallel arrays indexed by position). This is the last nested-collection shape needed before Phase 4 (sum types). Aligns.

Decisions Made​

  • IR. Added MapElemKeyType Type and MapElemValueType Type parallel fields to all list-bearing nodes (ListLit, LetStmt, VarRef, Param, CallExpr, AppendExpr, IndexExpr, LenExpr, ForEachStmt, Function return type). Mirrors the InnerElemType pattern from Phase 3.4b.
  • Verifier. isListElemType widened to include TypeMap. Map-element nodes check that MapElemKeyType is TypeInt or TypeString and MapElemValueType is a scalar.
  • Lowerer. listElemFromRef now accepts TypeMap when K/V are supported scalars. lowerListLit, lowerIndexOp, lowerLenCall, lowerAppendCall, lowerForEach all propagate MapElemKeyType/MapElemValueType. New helpers exprMapElemKeyType / exprMapElemValueType mirror the existing exprKeyType/exprValueType pattern. The ForEach induction-variable binding carries key: K, value: V so the map can be used inside the loop body.
  • Emitter. listSuffix returns "map_<K>_<V>" when ElemType==TypeMap. cListBufferElemC returns mochi_map_<K>_<V>. New functions collectListOfMapPairs (AST walk), emitListOfMapHelpers (typedef struct + _lit/_append/_index/_len). Emit() calls the helper emitter between list-of-list and map-of-list helpers. ForEachStmt emission uses a tagged switch on s.ElemType for the induction-variable C type selection.
  • Scope. list<map<K,list<V>>> (map with list values as list elements) is deferred; it requires a three-level parallel-field chain. Phase 3.4f only supports maps with scalar values as list elements.
  • Fixtures. 10 fixtures under tests/transpiler3/c/fixtures/list_of_map/: 8 (K,V) combos with basic literal+len, plus for-in, append, passed-to-fn, returned-from-fn for the int-key/int-value case.
  • Gate. TestPhase3ListOfMap — all 10 fixtures pass.

Phase 3.4h (index assignment xs[i]=val, m[k]=val): LANDED 2026-05-25 20:34 (GMT+7)​

  • Audit date: 2026-05-25 20:20 (GMT+7)
  • Goal-alignment audit: Mutable collections are essential for any program that accumulates or updates state in a loop. Without xs[i] = val and m[k] = val, the only way to "update" a list is to build a new one via filter/map in a query expression (Phase 8), and the only way to "update" a map is to rebuild it from scratch. This is not idiomatic and blocks real algorithms (e.g., sieve of Eratosthenes, frequency counting, in-place sorting). Phase 3.4h closes the mutation gap for the two most common collection shapes. Aligns.

Decisions Made​

  • Two new IR stmt nodes. ListSetStmt{Name, Index, Value, ElemType, ...} and MapPutStmt{Name, Key, Value, KeyType, ValueType}. Stmts (not exprs) because index assignment has no return value in Mochi.
  • lowerIndexAssign dispatched from lowerAssign. When len(as.Index)==1 && idx.Colon==nil, lowerAssign calls lowerIndexAssign which branches on the binding's type (TypeList or TypeMap). Chained index (xs[i][j] = v) and slice assignment (xs[a:b] = ...) are rejected with a clear error (deferred).
  • List set: pass by value, mutate through heap pointer. mochi_list_<T>_set(xs, i, v) takes the list struct by value. The data field is a heap pointer, so xs.data[i] = v reaches the original backing array. No pointer-to-struct needed. Bounds check panics via mochi_panic_index().
  • Map put: pass by pointer for resize. mochi_map_<K>_<V>_put(mochi_map_<K>_<V> *m, K k, V v) passes the map struct by pointer so it can update m->table, m->cap, and m->nLive when a new key is inserted and the table needs to grow. Load factor threshold: nLive * 2 >= cap (same 0.5 as the existing _lit code). A static NAME##_grow helper rehashes into a doubled calloc'd table.
  • Macro extension. Added NAME##_grow + NAME##_put arms to the existing MOCHI_MAP_DEFINE macro in map.c. All 8 (K,V) instantiations get _put for free.
  • Walker updates. walkStmtListOfMap and walkStmtExprVisit in emit.go updated to visit both new stmt types so TU-local helpers and list-of-map helpers are collected correctly.
  • Fixtures. 8 fixtures under tests/transpiler3/c/fixtures/index_assign/: list_set_int, list_set_float, list_set_bool, list_set_str, list_set_loop (fill via while-loop), map_put_str_int (update + insert), map_put_int_str, map_put_update (sequential inserts + overwrite).
  • Gate. TestPhase3IndexAssign — all 8 fixtures pass.

Phase 3.5 (omap): DEFERRED​

  • Audit date: 2026-05-22 23:55 (GMT+7)
  • Goal-alignment audit verdict: DEFERRED. Same blocker as 3.3: Mochi has no omap<K, V> surface. There is no OmapLit, no OmapType, no insertion-order-map literal syntax that distinguishes from the existing map<K, V> (which is key-sorted in the vm3 oracle). Implementing omap<K, V> in transpiler3 alone would be unreachable scaffolding for the same reason.
  • Unblock condition. When Mochi gains omap<K, V> parsing + an OMapType kind (likely driven by Phase 8 query DSL's group-by row shape), Phase 3.5 reactivates: open-addressing hash table for O(1) lookup + a parallel insertion-order list for iteration (the only difference vs Phase 3.2's map<K, V>). Eight (K,V) instantiations matching Phase 3.2.
  • Phase 8 ripple effect. If the Phase 8 query DSL's group-by row needs insertion-order iteration, Phase 3.5 must reactivate before Phase 8 ships. The Phase 8 spec doc should call this out when it begins. Until then 3.5 stays DEFERRED with no fixture corpus.

Deferred work​

Concurrent-safe maps: not in v1 (use a stream/agent boundary).

  • Phase 3.0: print(record), field assignment (r.f = v), nested-record fields, generic record decls, methods on records. All have unblocked paths in the IR (no struct shape changes needed) and will land as 3.0.x sub-phases or with Phase 4.
  • Phase 3.1: list<R> (landed with Phase 3.4a); list<list<T>> for T scalar (landed with Phase 3.4b); list<list<R>> and 3-level nesting (deferred to 3.4b.1 once a fixture pulls on it); print(list) (deferred until a per-T list formatter lands); list slice xs[a..b] (deferred to Phase 6); list equality xs == ys (deferred to 3.4d); in-place mutation aliasing model (deferred to Phase 18 perf); typed-empty literal let xs: list<int> = [] (landed with Phase 3.4c); xs = [] as assignment reset (deferred — 3.4c only handles the binding form).
  • Phase 3.2: map<K, R> / map<R, V> (deferred to later 3.4 sub-phases); map<K, list<V>> (landed with Phase 3.4e); m[k] = v (landed with Phase 3.4h); delete(m, k) mutation (deferred); print(map) (deferred until a per-(K,V) map formatter lands); map equality m == n (deferred to 3.4); option-aware unwrap of m[k] for arithmetic (deferred to Phase 4 option types); empty-map literal with type annotation (deferred to 3.4); per-call snapshot allocations under keys() / values() accepted as a known leak until Phase 7 reclamation.

Closeout notes​

All sub-phases (3.0, 3.1, 3.2, 3.4a-3.4h) are LANDED. Phases 3.3 and 3.5 are DEFERRED (no Mochi parser surface for set or omap<K,V>). All collection gate tests are green on every tier-1 host. Phase 3 is LANDED.