Status: Accepted
Date: October 10, 2026 (#558)
Answers: how the compiler tells one expression from another once the code
that keys on an expression is written in Nikaia, which has no address of a value
Related:
ADR-294 (the road to Stage 1; the syntax tree is Nikaia),
ADR-152 D4 and ADR-282 D4 (a node that carries
a key of its own, at),
ADR-094 D7 (a tree rebuilt by value)
What names an expression to the checker, the text-tier pass and the emitter, once none of them can take its address?
Today the Rust side answers with the address of the node: about 68 sites
(31 in the checker, 28 in the emitter, 9 in the text-tier pass) hold a table
keyed on expr as *const Expr as usize. The checker’s Checked keys its
tables three ways (a statement’s byte offset with the shape of its text, an
address, a literal’s at). Nikaia has no type for an address (NK1122), so
code keyed that way cannot move.
| Compiler | Its answer | Source |
|---|---|---|
| Zig | a node is an index (Inst.Index) into the tree’s arrays, given in parse order |
from memory, not checked |
rustc |
every HIR node has a HirId, given when the HIR is made; the tables are keyed on it |
from memory, not checked |
| Go 1.5 | pointer identity, kept from the C compiler | from memory, not checked |
What they share: identity is a number the node carries, never its address.
| Option | Why it lost / won |
|---|---|
| the node’s address | lost: no Nikaia type; a clone has a new address, so the same fact is lost or held twice; text_tiers::wrap_item compares every address before it replaces any, to survive its own rewrite |
| a pre-order ordinal each walk computes | lost: two walks must number identically, a node inserted after parsing (into_either) or a cloned subtree shifts every later key, and a mismatch lowers silently wrong (a wrong suffix, a Some(..) in the wrong place) |
| an arena with indices (Zig) | lost: it changes how the tree is held, not only how a node is named |
| an id on every node, given by the parser | won: one scheme for what three schemes do today |
Expr node has an id, given by the numbering pass right after the parseThe id is a u32, unique among the nodes of one parsed file, given in input
order, without gaps, by a pass of its own over the tree the grammar returned
(ADR-383). A table that holds a fact about an expression is keyed on it,
together with the file it is in when the table spans files.
Changed by ADR-383 D1-D3.
A cloned subtree is the same expression, so the facts about it still hold. A node made after parsing (a rewrite, a wrapper) takes the next id the file has not given, so no two nodes of a tree share one.
Two trees that differ only in their ids are equal.
The address keys, the ordinals and the key at stands for on ListLit, LitStr
and With (ADR-152 D4, ADR-282 D4) become the id. Checked’s three key schemes
become one. An at read as a position stays.
A table that holds a fact about a statement itself (a loop that can fail, the
type a let was given) keys it by the byte the statement starts at. That is a
position, which D4 keeps: check runs over one file, two statements of a file
cannot start at the same byte, and the compiler builds no statement into a
checked tree. A fact about an expression is keyed by the expression’s id
(D1), never by its statement and a name: that key gave every node of a
statement one answer (ADR-270 D8).
Statements get an id of their own, carried by Spanned, when either premise
stops holding: a table spans the files of a package, or the compiler builds a
statement into a tree that is checked.
Rejected: an id on every statement now. It makes the key scheme literally one, but separates nothing a position does not separate today. Neither does it help a statement copied by unrolling, since a clone keeps its id (D2).
ast.nika and every construction of an Expr
(about 1 006 in Rust, 1 211 in tools/*.nika; a pattern with .. is
unaffected). The count is taken first, and it fixes whether the id is a field
of each variant or a wrapper around the expression.node_of: fn(ref Expr) -> i64 (text_tiers, bounds_basic,
bounds_walk) go when Rust no longer owns the tree.