LL(1): match with an explicit stack and a shared-input cursor - #1531

Approving. Verified against origin/main at c51e6dfa (merge-base 893b4eeb).

The head moved mid-review (1b7a34f2 → 5b421413). The new commit touches only
fjs/bnf/todo/*.md; git diff 1b7a34f2 5b421413 -- fjs/bnf/ll1 CHANGELOG.md is empty, so
the code verification below carries over unchanged, and I re-ran the link check at the new
head.

Gates

• npx tsc --noEmit → exit 0.
• npm run prepack from a freshly cleaned tree → exit 0 (both passes).
• npm test → 2539 pass, 0 fail. Merge-base 893b4eeb is 2537, origin/main is 2538
  (the +1 is #1528, which this branch is behind). 2537 + 2 new longInput cases = 2539. Exact.
• Link check → broken links 140 → 137, removals only, no additions. The todo/*.md
  reference that pointed at the deleted ll1/todo/stack-recursive-matching.md was
  redirected to the longInput proof groups rather than left stranded, and nothing else in
  the tree still names that file.
• Dual-axis surface diff (526 → 527 type aliases, 889 → 889 consts, both non-empty):
  added _Cursor, _Position, _Result, _Frame, _Stack, _Task — all _-prefixed
  per §6.2; removed MatchRule, _DispatchRuleOrName, _MatchResultEof. No unprefixed
  public type additions, no signature widened to any. @module survives in the emitted
  module.f.d.mts and types.d.ts; no elided / any in the emitted ll1 declarations.
• CHANGELOG: present, links only /pull/1531, and correctly carries **BREAKING CHANGES:**
  — removing the exported MatchRule is a real public-surface removal.

Behavioural equivalence with main

The thing I most wanted to rule out is the #1516 hazard: encodeTerminal is not
order-preserving (EOF is semantic -1 but encodes to the top of the encoded space), so a
rewrite of the matching loop is exactly where a comparison could regress onto encoded
values, and an ASCII-only test suite would not notice. It has not regressed here — the
dispatch map still holds decoded terminals (rangeDecode), and symbolAt yields a code
point or eofSymbol (-1), so every comparison is on decoded values.

I checked that behaviourally rather than by reading. Differential harness importing both
matchers side by side, comparing full JSON.stringify(MatchResult) — AST, success flag and
remainder — over 15 grammars × fixed inputs plus 4000 seeded-random inputs drawn from an
alphabet straddling ASCII / non-ASCII / structural characters:

compared=4510 mismatches=0

The grammars deliberately include the cases ASCII tests miss: range([0x80, 0x10FFFF]),
unicodeMax, remove(unicodeMax)(set('"')), a variant whose branches straddle
low / high / eof, and { z: range([0,0]), e: eof } — EOF adjacent to code point 0, the
one place a top-of-space encoded ordering would reorder. Inputs include lone U+10FFFF,
U+10FFFF before and after ASCII, and U+0000.

Negative controls, both fired:

• symbolAt masked to & 0xFFFF (only astral code points affected) → 3 mismatches.
• symbolAt returning 0xFFFFFF for EOF, i.e. exactly the "compared the encoded value"
  regression → 1071 mismatches.

So the harness is sensitive to both failure modes and the unmutated PR is clean on all 4510.

Whole-input grammars (the #1516 finish = beforeEOF || afterEOF property): [body, eof],
[eof], [eof, eof], [range('AA'), eof], [repeat0Plus(unicodeMax), eof] are all in the
harness and all agree with main. The full suite passing also covers the djs / js /
media/json tokenizers and parsers that ride on this backend.

Explicit stack, depth and termination. Compared both backends at increasing sizes:

n      flat repeat0Plus        deep [ ... ] nesting
1000   main ok      pr ok      main ok      pr ok
2000   main OVERFLOW pr ok     main OVERFLOW pr ok
50000  main OVERFLOW pr ok     main OVERFLOW pr ok

Identical results everywhere main survives, and main really does die at ~2000 — the PR's
stated motivation is accurate, not a hypothetical. Termination is sound: a frame is only
pushed when a symbol is consumed and pos > cp.length short-circuits dispatch to null,
so total pushes are bounded by cp.length + 1 and heap stack depth is O(n).

I also walked the case table against main's f/items and it lines up on every branch,
including the three-way dr === null split (emptyTag defined → success at pos;
pos >= cp.length → success with null remainder; otherwise fail at pos) and the
pos > cp.length state that replaces the old eofConsumed flag.

Mutation-testing the two new proof cases rather than trusting them: reverting the
remainder slice (remainderAt → return cp) fails both longInput[1] and longInput[2],
and both cases are exactly the shapes and sizes (10000 / 5000) at which main overflows — so
they genuinely pin the new paths. For completeness: they do not catch an AST-sequence
mutation ([...frame.seq, ast] → frame.seq), which is fine given their stated purpose;
the 4510-case AST-level differential covers that ground.

rules: readonly string[] narrowing is sound — the builder only ever appends names
(addRuleToDispatch), starts from rules: [], and addTagToDispatch preserves them, so
no _DispatchRule object was ever reachable in that position.

Not verified

• Coverage numbers. npm run cov is not trustworthy in this environment (Node v23) and
  reports the same vacuous result on main.
• The "no longer quadratic" half of the CHANGELOG claim I confirmed only directionally
  (n=50000 completes promptly), not by fitting a curve.

Nothing to change.