List Type Support

Status: Done (2026-09-01)

Companion to knowledge/design/sum-types.md (this plan provides the
list<T> support its "re-enable df::filter" deferred item needs) and
knowledge/design/declared-layout-order.md (interaction with its ordering
constraint — see deferred df section below).

Scope per user: lists can be constructed (literals) and passed as
external types (param and result across the component boundary), with
explicit list tests in the sums test world. No iteration, no mutation,
no length/index operators at this stage; lists are never embedded inside
records/sums in the fixtures (those arms stay todo!(), same as the existing
String arms at lang/src/compiler/nucleus/mod.rs:747 and :1154).

Not in this plan: the df integration. The host filter in
stdlib/src/df.rs stays todo!(); the df fixture work (WIT fixes,
df.blr extern declarations, df test extension) is deferred — see
"Deferred: df integration" below. Its decisions are recorded so the
follow-up is unblocked.

Canonical ABI for lists (verified, wasmtime 40 / spec)

• CanonicalAbiInfo: InterfaceType::List(_) => POINTER_PAIR
  (wasmtime-environ-40 component/types.rs: flat_count 2, size32 8, align32 4)
  — lists have the exact same representation as strings.
  flatten_type(List) = [I32, I32].
• In-memory layout (spec store_list/load_list): an 8-byte header
  {begin: i32 @0, length: i32 @4}, begin pointing at a contiguous array
  of elements, each element stored inline at
  ptr + i * elem_size(elem_type) (no array-of-pointers — a list<node> is a
  contiguous run of inlined node in-memory variants).
• A 2-slot result triggers the existing resv path
  (flatten_function_type, nucleus/mod.rs:1487-1496) exactly like String:
  the caller allocs an 8-byte header-only resv (align 4, size 8); the
  host adapter fills begin/length and allocates the element array via the
  guest realloc. The resv pointer is the blr list value.
• Blr's existing String convention is precisely this layout (region
  {begin@0, len@4}; literal construction nucleus/mod.rs:332-358; param lift
  :441-458; resv arm :491-502). List is a mechanical mirror of String
  plus runtime-sized element storage.

Value/region model

• core::Type::List(Box<Type>); stack value = i32 region pointer.
• Local list region: one alloc(4, 8 + n * elem_size);
  region[0] = region + 8, region[1] = n; elements stored inline from
  offset 8 (scalars direct; sum elements via the existing inlined-region
  memory.copy convention; resource elements as i32 handles).
• Literal [e1, .., en] (empty [] allowed) constructs the region.
• Element type: inferred by unifying all elements to one T
  (list literal carries a fresh T; literal type = List(T)). No annotation
  required at the call site (extern aliases like df::node can't be named in
  annotations — inference resolves against the declared extern type, same as
  the sum tags in sum_param.blr).

Syntax

• Type: list<T> — new TypeExpr production. </> lexer tokens are new;
  they must not perturb the existing ">>" forward-expr token
  (parser.lalrpop:131-137) — verify token ordering.
• Expression: [e1, e2] — the grammar already has a commented-out rule
  at parser.lalrpop:197 (//"[" <Exprs> "]" => Expr::List(...)); uncomment
  and adapt (allow empty). No clash: [...] in type position is a sum; in
  expression position it's a list.

Touch-point map (from repo survey)

air

• parser.lalrpop: lexer tokens (299-317); TypeExpr rule (271-282) gains
  list < TypeExpr >; Term list literal (197, uncomment); empty-list
  Exprs allowance (176-182 / 248-257).
• air/mod.rs: Expr::List(Vec<Self>) (76-113); TypeExpr::List(Box<TypeExpr>)
  (138-149); air sexpr arms (air/sexpr.rs:246-265, 828-862).

crust (list is a first-class type constructor)

• crust/ty.rs:114-138 Type::List (+ occurs_check 158-189, mentions
  191-215); unification.rs normalize_ty 148-171 + unify_ty_ty 179-220;
  inst.rs:94-127; subst.rs:121-150 (ty) + :152-271 (expr);
  crust/sexpr.rs:154-269 (+ expr sexpr 732/888/1122/1293).
• crust/mod.rs: _lower_typ (343-384) List arm;
  convert_to_ext_typ (411-514) List arm → ExternalType::List;
  new crust::Expr::List { elem var, values } (enum 90-147, id() 150-167)
  lowered next to the record arm (606-769); infer.rs literal arm (80-86
  area) unifying elements.

mantle

• mantle/mod.rs:70-81 Type::List, adjust 715-739, lower_ty 781-802;
  lower_expr 1174-1283; monomorph.rs:272-283 is_mono_type;
  simplify.rs expr traversals; mantle/sexpr.rs:88-111 + From.

core

• core/mod.rs:279-290 Type::List; lower_typ 321-357;
  convert_external_type 673-699; new core::Expr::List (+ free_vars_aux
  70-103, rename 121-155, type_of 157-189); mantle→core arm in
  convert (582-663, next to the Tuple arm at 621).
• core/sexpr.rs: Type To 34-81 / From 410-514 (no variant parse arm
  exists — add list tag plus the "list" tag to the allow-lists at
  465-475 and 731-735); convert_external_type_to_core 842-869; Expr sexpr
  93-176 / 534-702.

nucleus (nucleus/mod.rs — 12 match sites)

• emit_val_typ 104 (→ I32); AppExternal param lift 439-483 (String arm
  441-458 is the template: LocalTee; I32Load(0); I32Load(4));
  AppExternal ret_on_heap resv 487-536 (String arm 491-502 is the
  template: alloc(4, 8) header-only); Access 585-592 (List: no arm /
  unreachable — lists have no fields); emit_expr new list-literal arm
  (332-358 String arm is the construction template); emit_store_expr
  729-795 (→ todo!(), String parity); emit_case_slots 840-890 (→
  todo!() parity — no sum case may carry a list in scope);
  emit_value_slots 990-1048 (→ todo!() parity — no record field may
  carry a list in scope); flatten_fields 1109-1117 (verify a List result
  is resv-handled as a unit, not field-flattened); emit_load 1138-1176
  (→ todo!() parity); size_align 1193-1212 (→ (4,4) like String; note
  the record-field-inlining gap this implies is pre-existing for String
  too); core_flat_slots 1568-1577 (→ 2); core_flat_tys 1581-1593 (→
  [I32, I32]); flatten_type 1504-1525 (List → [I32, I32]).
• Element store inside the literal (new code, small): scalar =
  emit_scalar_slot-style store at 8 + i*elem_size; sum element =
  memory.copy of the element region (inlined-region convention); resource
  element = i32 handle store. Sizes come from size_align /
  cases_dt_size_align.

component (nucleus/component.rs)

• EmitInstanceType::convert_ext_ty_to_ctyp 442-507 and
  EmitComponent::convert_ty_to_ctyp 90-149: List arms emitting
  defined_type().list(elem) — wasm-encoder 0.242.0 has
  ComponentDefinedTypeEncoder::list (types.rs:618); add
  emit_list_type next to emit_record_type/emit_variant_type.
  Instance-type list needs a synthetic export name (e.g. list<N>); matching
  is structural, name only avoids clashes.

external types

• external_type.rs: ExternalType::List(Box<ExternalType>) + sexpr To
  49-84 / From 130-263 + roundtrip test (281-331 pattern).

Fixture changes (this plan)

Sums world (stdlib/wit/sums.wit + stdlib/src/sums.blr +
stdlib/src/sums.rs): two new interface functions + trivial host impls:

lsum: func(xs: list<f64>) -> f64;        # flat-element list through the boundary
lreverse: func(xs: list<f64>) -> list<f64>;  # list RESULT (exercises the resv path)

No other WIT changes in this plan.

Deferred: df integration (later follow-up, decisions recorded)

The df WIT (stdlib/wit/world.wit:3-29) still blocks df completion in two
ways besides lists; these are done in the follow-up (host filter stays
todo!() until then):

1. binary {left: u32, ..., right: u32} → change both fields to s64
   (blr has no u32; unsigned types are a future blr item). [decided]
2. Case order — reorder node {integer, binary} and binaryoperator
   (8 cases) in world.wit to alphabetical (panics at crust/mod.rs:447/482
   otherwise; see declared-layout-order.md). [decided — no layout work;
   reorder the fixture]
3. stdlib/src/df.blr gains extern type declarations (sums.blr syntax):

   pub extern type binaryoperator = [ `addition unit | `concat unit | ... ]
   pub extern type binary = {left: i64, op: binaryoperator, right: i64}
   pub extern type node = [ `binary binary | `integer i64 ]
   pub extern fn filter(frame: DataFrame, predicate: list<node>) -> DataFrame;
   

4. stdlib/src/df.rs — implement host filter (currently todo!();
   semantics decision deferred with the implementation — traverse+identity
   vs real datafusion predicate, the latter degenerate without a
   column-name form in node). [deferred]
5. Extend lang/tests/integration/df.blr: construct
   [ `integer(1), `binary({left: 2, op: `addition, right: 3}) ] and
   call df::filter(df::fromcsv("test.csv"), ...) → df::show(...) → 1
   (proves sum-in-list-in-param with nested record-in-sum).

Test strategy

• Sums-world list fixtures (new, in stdlib/wit/sums.wit + sums.blr +
  sums.rs host): lsum(xs: list<f64>) -> f64 (flat-element list through the
  boundary) and lreverse(xs: list<f64>) -> list<f64> (exercises the
  list-result resv path, which df alone never does — filter returns a
  resource). Both trivial host impls.
• lang/tests/integration/list_flat.blr: lsum([1.5, 2.5]) → 4;
  empty-list case lsum([]) → 0.
• lang/tests/integration/list_ret.blr: lsum(lreverse([1.5, 2.5])) → 4.
  (The df.blr extension with a constructed list<node> moves to the deferred
  df follow-up — item 5 there.)
• Unit tests: parser tests (list type + literal, incl. []);
  ExternalType::List sexpr roundtrip; flatten_type/core_flat_tys
  List; component-type snapshot with defined_type().list (wasmprinter,
  component_type_tests pattern); core sexpr roundtrip for Type::List.
• Gates: all pre-existing tests byte-green; BLR_SNAPSHOT WAT inspection of a
  list call to confirm (begin, len) slot emission + header layout;
  cargo fmt + cargo clippy --workspace -- -D warnings + full workspace.

Work items

Deferred (not work items here): the entire df integration — see
"Deferred: df integration" (WIT u32→s64 + case reorder, df.blr extern
declarations incl. filter, host filter impl, df.blr test extension).

Commits: one per phase (plumbing / fixtures+tests / hardening), per session
convention.

Risks

• LALRPOP lexer: </> introduction next to ">>" — run forward-expr and
  precedence parser tests first; token-order regression is the top parser
  risk.
• Type-constructor surface (L2) is wide but mechanical; the row machinery is
  untouched (lists are not rows).
• flatten_fields behavior for a List in resv context (L4 note: verify a
  list result is resv-handled as a unit, not field-flattened).

Decisions (2026-08-31)

1. Scope: list support + explicit list tests only. df integration
   deferred — host filter stays todo!(), df fixture work later.
2. Empty list literal []: included.
3. For the deferred df follow-up (recorded so it's unblocked):
   • WIT binary fields u32 → s64 (blr i64; unsigned is a future blr
     item).
   • Reorder node/binaryoperator in world.wit to alphabetical — do
     not do the declared-layout-order work.
   • Host filter semantics decided at that time (traverse+identity vs
     real datafusion predicate; the latter is degenerate without a
     column-name form in node).

All questions resolved.

Progress log

• 2026-08-31: Plan written (ABI confirmed against wasmtime 40
  POINTER_PAIR + spec store_list/load_list; full touch-point map from
  repo survey; existing commented-out grammar rule at parser.lalrpop:197
  noted). Not started.
• 2026-08-31: Decisions recorded — alphabetical WIT reorder (no layout work),
  u32→s64, empty [] included; host filter level still open (a
  clarification given for option (b)'s degeneracy).
• 2026-08-31: Scope narrowed per user — df integration deferred (host
  filter stays todo!()); this plan ships list plumbing + sums-world
  lsum/lreverse fixtures + list_flat/list_ret integration tests.
  df WIT decisions carried into "Deferred: df integration".
• 2026-09-01: L1–L5 implemented (air syntax/AST, crust, mantle, core, nucleus,
  component emission, ExternalType::List) — one commit per layer.
• 2026-09-01: L6 unit tests landed (parser list literal/type, air + core +
  external sexpr roundtrips incl. empty list, flatten_type/core_flat_tys/
  size_align list facts, component-type snapshot with
  defined_type().list and the synthetic list<N> export name).
• 2026-09-01: L7 fixtures landed — sums-world lsum/lreverse (WIT +
  sums.blr + host) and list_flat/list_ret integration tests. The new
  tests exposed a codegen bug: the list region was allocated align 4, but
  the canonical ABI requires the begin pointer aligned to the element
  alignment (8 for f64) — fixed by allocating the region at
  max(4, elem_align). Added a print_wasm dev example for
  BLR_SNAPSHOT WAT inspection.
• 2026-09-01: L8 hardening — snapshot WAT audit confirmed the (begin, len)
  header layout (begin = region + 8) and the header-only alloc(4, 8)
  resv path for list results; plan moved from .opencode/plans/ to
  knowledge/design/; sum-types deferred item and declared-layout-order
  note updated. fmt/clippy/full workspace green. Done.