ADR-383: A Parsed File’s Nodes Are Numbered by a Pass of Their Own, in Input Order, Right After the Parse; the Grammar Gives No Ids

Status: Accepted Date: October 28, 2026 (owner’s decision; #125, #557) Answers: where the nodes of a grammar written in Nikaia get their ids (ADR-340 D1), when ADR-339 D3 forbids the parser state the compiler’s grammar draws them from today Supersedes / Related: ADR-340 D1 (changed: who gives the id and in which order); ADR-339 D3 (stands: a grammar declares no state); ADR-347 (the first rewrite of the parsed tree); ADR-094 D7 (a tree rebuilt by value); Part II 10.8 (par_fold: the number of cores does not change the answer)

1. Question

Who numbers the nodes of a parsed file, if the grammar may hold no counter?

The compiler’s grammar (crates/nikaia/src/parser/mod.rs) gives an id in 71 actions with _state.user().id(), a u32 counter (Trivia::next_id) in the parser’s declared state, and sets runs of ids aside for the folds (Trivia::reserve, called by fold_binary, fold_postfix; guarded takes one). 27 actions record where a node was read with _state.user().at(expr, span), into Trivia::spans, a list indexed by id - spans_from; the parse hands it to Parsed::expr_spans, read by Parsed::span_of(id). A hole of a template and a type’s rule read later (Parsed::hole, read_expression, through parse_expression_from(.., first)) go on counting from Parsed::next_id. ADR-339 D3 removes the state, so all three need another home before the grammar can move.

2. How others do it

Compiler	Its answer	Source
`rustc`	the parser gives `DUMMY_NODE_ID`; a pass after macro expansion (`NodeId` assignment in the resolver’s collector) numbers the tree	from memory, not checked
Zig	a node is the index it was appended at, in the parser’s own arrays	from memory, not checked
Roslyn	no id; a node is its position in an immutable tree	from memory, not checked

3. Options, weighed

Option	Why it lost / won
a counter in the grammar’s state, as today	lost: ADR-339 D3, and a state is not the same on any number of cores
a counter saved and restored around each `par_fold` piece, prefix sums at the merge	lost: every author of a parallel grammar carries it, and backtracking leaves gaps
a pass of its own over the finished tree, before the first reader	won (owner, 2026-10-28): the grammar stays stateless; one walk; dense ids

	D1 the special case pays	D2 the compiler works	D3 no cost for the common case	D4 consistent	If it is wrong
state	every grammar carries a counter	the author threads it	free	breaks ADR-339 D3	-
prefix sums	parallel grammars pay	the generated parser restores it	a merge per piece	a second rule beside D3	gaps and order differ by cores
pass	nobody	the compiler walks once	one walk over the tree, linear in its nodes	one rule: the parser builds, the pass numbers	a reader that relied on the old order shows it in a test’s output

4. Decision

D1 — The grammar builds nodes without ids; a numbering pass gives them

A node the grammar’s action makes carries a parsed, not yet numbered id (NodeId::parsed(), below FIRST_BUILT, ADR-340 D2’s fresh ids stay above it). The folds (tools/tree_build.nika) take no first. No action reads or writes a counter.

D2 — The pass runs once, right after the parse and before the first rewrite

parse_to_ast calls it on the tree the grammar returned, before one_variant::expand (ADR-347) and every later reader; parse_expression_from calls it on the hole’s tree with the file’s next free number under the lock Parsed::hole already holds. Nothing between the grammar and the pass reads an id.

D3 — What it guarantees: dense, in input order, the same on any number of cores

It walks items, statements and expressions in the order they stand in the input (a node before its children, children left to right) and gives each parsed node the next number from first. The ids of a file are first .. first + n with no gap, whatever the grammar backtracked over and however par_fold cut the input: the tree is the same, so the numbers are. A node with a fresh id (ADR-340 D2) is passed over. A clone keeps its id (ADR-340 D2) from the pass on; an action makes no clone, so no two parsed nodes share an id.

D4 — A node carries its span until it is numbered; the pass writes the table

An action that knows where a node was read (span(p), ADR-339 D1) puts the span on the node’s id, the innermost rule first, as Trivia::at keeps it today. The pass moves it into Parsed::expr_spans, now a list indexed by id - first, one entry for every number (None where no rule gave a span). span_of(id) reads it as before.

D5 — What it costs

One walk over the tree per parsed file and per hole, linear in its nodes. The id grows by the span it carries until numbering (one Span, two u32).

5. Consequences

Trivia loses next_id, spans, spans_from, id(), reserve() and at(); the 71 _state.user().id() become NodeId::parsed(), the 27 _state.user().at(e, _span) a function of the node and its span.
Parsed::next_id stays: it is where the pass for a later hole starts.
Ids were given in the order nodes were made (children first, gaps where a branch lost); now in input order without gaps. A reader that depended on more than uniqueness is a defect the change shows.

6. What this does not decide

The rest of the state ADR-339 D3 removes: semi (a ; before a statement), ran, comment and block_comment (the comment list of ADR-337 D2), and the trailing-trivia cut at applies to a span (PrTrivia::cut). They are #557’s.
Whether statements get ids (ADR-340 D5).

Part I-III say nothing about node ids, so no specification text changes.

This site is open source. Improve this page.