Frontend: lexical/var early-error scan rebuilds the subtree var set at every nested block

Parent: #493 Related: #926 (same class, different scan), #496

Status: code inspection, verified by reading. No measurement exists yet and no performance claim is made here.

Found while tracing #926's blast radius. This is a second instance of the same "re-scan the whole subtree per nested scope" shape in src/parser.zig, on a different axis from the private-name one.

Mechanism

checkLexicalDupes enforces the Block 14.2.1 / Script 16.1.1 / FunctionBody 15.2.1 early error that a scope's LexicallyDeclaredNames must not intersect its VarDeclaredNames. Because var hoists out of nested blocks, it collects var names across the whole subtree (src/parser.zig:1059-1061):

if (seen.count() > 0) {
    var var_names = self.secureStringMap(void);
    for (stmts) |s| try self.collectVarNames(s, &var_names);

collectVarNames (src/parser.zig:1143) descends through .block, .if_stmt, loops and try without crossing a function boundary, and recurseScope re-enters checkLexicalDupes for each nested block. So a block nested D deep has its var subtree walked once per enclosing block: O(N x D) time for a source of size O(N), and the maps are self.arena-backed (out.put(self.arena, ...)) so each rebuild is retained for the rest of the parse.

Reachability

The if (seen.count() > 0) guard means the scan only runs for a block that actually has lexical declarations — but that is trivially satisfiable from attacker-controlled source, e.g. { let a; { let b; { let c; ... { var x; } ... } } }, where every level pays for the whole remaining subtree.

Why this is not #926

#926 was the private-name membership set, keyed per class. This is the var-name set, keyed per block, in a different function with no shared state — which is also why the #926 fix neither helps nor hurts it. Both are instances of #493's class.

Suggested order, mirroring #926

1. Freeze growth workloads and controls in bench/frontend_parse.zig before touching parser code — width and depth varied independently, plus a control with lexical declarations but no nested blocks, so "depth is expensive" is separated from "re-scanning is expensive".
2. Measure allocation requests, retained bytes and wall time per width under the bounded guard. Confirm the curve before proposing a fix — I have deliberately not claimed one here. Note from #926 that retained bytes are the cleaner algorithmic signal; wall time picks up a memory-system tax once the arena passes a few hundred MB.
3. Only then consider computing the var set once per function-level scope and consulting it from nested blocks, preserving the exact Annex B.3.3 rigid/non-rigid distinction at src/parser.zig:1048-1049 and the function-boundary stop.

Non-goals

No depth limit, no weakening of the early error, and no published benchmark claim until dated evidence lands under docs/.data/.

Measured: confirmed quadratic, and the control that matters holds

Workloads frozen and landed in 54126cf before any parser change, following the #926 ordering. Median of 5 iterations after 2 warmups, one job at a time under the 3072 MB bounded guard. All 16 rows exited 0 with empty stderr and passed their structural verifiers; allocation counts and byte counts are deterministic across iterations.

Every source is linear: nested_lets is 5,157 -> 10,533 -> 21,333 -> 44,885 bytes (x2.04, x2.03, x2.10), and the other three match to two decimals.

The discriminating result

wide runs the scan the same number of times as nested_lets and stays flat. N sibling blocks each arm checkLexicalDupes exactly as N nested blocks do — same scan count, same linear source — yet at width 2048 the nested shape is 257x slower (166.7 ms vs 0.65 ms) and retains 46x more (291 MB vs 6.4 MB).

That is what establishes the cost is the depth each scan walks, not how often the scan runs. no_lexical alone could not have shown this: removing the lexical declaration disarms the scan entirely via the seen.count() > 0 guard, so it conflates "no scan" with "cheap scan". This is the control #926 taught me to build — there I labelled deep a control when its own description ("copies a growing set once per level") made it a second quadratic, and had to correct the issue. This time the label was checked against the algorithm before being claimed, and it held.

Retained bytes are again the cleaner algorithmic signal: x3.90 converging on the 4.0 that N^2 predicts, while wall time overshoots to x4.53 once the arena passes a few hundred MB and the memory system starts charging rent.

What this points the fix at

The measurement says the target is each scan's depth. Notably this is the same problem #926 turned out to be, and the same remedy appears to apply: rather than every block collecting its subtree's var names into a fresh arena-backed map, a single DFS can carry one shared lexical-name map with mark/rollback at each block boundary and test each var on arrival — O(1) per var instead of O(depth).

The correspondence is exact: a var conflicts precisely with the LexicallyDeclaredNames of the blocks currently open, which is exactly what such a map holds at that point. Lexical names of a block are known from that block's own statement list without recursing, so they can be pushed before descending. That would reuse SecureStringMapUnmanaged.remove, added for #926 in e07b13b.

Two things to preserve that #926 did not have to worry about, and which I have not yet verified in detail:

• the Annex B.3.3 rigid/non-rigid distinction for block-level function declarations (funcs_lexical, src/parser.zig:1048-1049);
• recurseFnBody stopping at function boundaries, and the switch arm that flattens all cases into one lexical scope.

No fix is proposed yet beyond that sketch, and no parser code has been touched. Next step is the same as #926's: pin the semantics with tests confirmed against another engine first, then change the scan.

Correction to the fix sketch, and the baseline

Baseline landed in 2d04e81: 17 cases pinning the semantics, each confirmed against another engine first, and all 17 pass against the current parser.

The sketch in my previous comment was too optimistic

I wrote that this is "the same problem #926 was" and that the same remedy applies. Having now read checkLexicalDupes in full, that is not quite right and the difference is the expensive part.

#926's set was SecureStringMapUnmanaged(void) answering exactly one question, contains, with no scope qualification. A private name in scope is in scope, full stop. That is not true here. A var must not see lexical names outside its enclosing function:

{ let x; function f() { var x; } }   // legal -- the boundary hides the outer let
{ let x; { var x; } }                // error -- no boundary in between

So a single shared open-lexical map has to become invisible below a function boundary. Clearing and restoring it around each function body reintroduces exactly the copy-per-scope this issue is about, just keyed on functions instead of blocks — a source nesting N functions each holding lexical names would stay quadratic.

The design that does work

Tag each open name with the scope depth at which it was declared, and track the depth at which the current function scope began:

• open_lexical: name -> innermost open scope depth
• on entering a block: for each of its lexical names, record the previous depth (or absence) on an undo log, then set the name's depth to the current one
• on exiting: restore each recorded previous depth rather than simply removing — shadowing means a name may be open at several depths at once
• on encountering a var: it conflicts iff the name is present and its recorded depth is at or below the current function's base depth in the enclosing direction — a let outside the function is at a depth above that base and must not match
• entering a function body raises the base; leaving restores it

Every operation is O(1), so the whole walk is O(N). The undo log restores a previous depth rather than just deleting the key, which is the part #926 did not need.

Two further constraints, both verified by reading

• Annex B.3.3: addDecl distinguishes rigid (let/const/class, async/generator functions, and anything in strict mode) from non-rigid plain function declarations, so two plain function f(){} in one sloppy block are legal. That per-level duplicate detection is already linear and should be left alone — only the var half moves.
• The switch arm (src/parser.zig:1276-1279) flattens every case body into one checkLexicalDupes call, so the whole switch is a single lexical scope. Any restructuring has to keep that flattening, and the pinned case switch (0) { case 1: let x; break; case 2: var x; } guards it.

Also note checkLexicalDupes is reached from five call sites (src/parser.zig:993, 1259, 1278, 1295, 4308). The map should be threaded as a parameter rather than stored on Parser: SecureStringMapUnmanaged holds a *SecureHashState, and Parser is returned by value with shared_secure_hash_state assigned after init, so a Parser-resident map that captured &self.secure_hash_state at construction would dangle. #926 avoided that hazard by threading, and the same applies here.

No parser code has been touched. The measurement, the workloads and the baseline are in; the fix is a larger and more delicate change than #926's and is not something to half-land.

Fixed in 0fb72d2

The two walks are now one. A LexicalScope threaded through the walk maps each open lexical name to the depth of the innermost scope declaring it, and every var is tested on arrival against the names currently open.

As the correction above anticipated, this is not #926's plain membership set: a var must not see lexical names outside its function, so recurseFnBody raises a var_base depth and a conflict needs the open name at or below it. The undo log restores a shadowed name's previous depth rather than deleting it.

Results — median of 15 iterations

The speedup climbs 19x -> 42x -> 88x -> 199x across the four widths, and time now grows x1.95, x1.98, x2.00 per doubling against a x2.04 source.

Controls. no_lexical — the same block chain with no lexical names — is byte- and allocation-identical to baseline at every width, so the walk itself costs nothing when there is nothing to open. wide drops 12% in allocations and 5% in bytes. flat, which holds all N names open in one scope at once, costs 14 more allocations and 3.6% more bytes: N simultaneously open names now live in the scope map and undo log as well as the per-level seen map. Allocation counts are deterministic, so that cost is real. It comes from the design and is small next to the quadratic that was removed. Timing differences on wide and flat (5-9%) are inside the run-to-run spread that no_lexical shows in the other direction, so I am not claiming them either way.

Verification

• test262 before vs after, both built from source: 15 subtrees covering block scope, switch, let/const, for/for-in/for-of, labeled, try, global/eval/function code, annexB/language and both class trees — 11,890 tests, 0 fail under both parsers. With zero failures on both sides, no regression can be hidden behind an unrelated gain.
• 73/73 parser tests, including the 17-case baseline from 2d04e81, re-run after the Debug hardening below.
• Adversarial review: four independent lenses (function boundaries, reach divergence between the merged walks, the three entry points, undo/ordering) each tried to construct a program on which the old and new algorithms disagree. None found one.

The review's main residual concern, raised by three lenses independently, was a maintenance hazard: correctness now depends on every arm that enters a new var scope doing so through recurseFnBody or a fresh scope. The fix makes a violation loud rather than silent: closeLexicalScope treats a missing shadowed key as unreachable, and all three entry points assert the scope fully unwound.

Found on the way — 22 pre-existing bugs, all executed

The review also turned up bugs where the old and new code agree but both disagree with node. I executed every one against node and against a test262 binary built from the pre-#928 parser before believing any of them — all 22 are real and all 22 predate this fix:

• #929 — 2 valid programs rejected: class static blocks treat their function declarations as lexical and rigid, where the spec makes them var-scoped.
• #930 — 20 invalid programs accepted, in four families: function bodies the walk never reaches (IIFEs, callbacks, object methods, arrows in expressions, field initializers, default parameters, declaration-group initializers); with bodies; labelled function declarations; and strict duplicate block functions checked after strictness has already been restored.

The #930 walk-reach family is worth flagging for whoever picks it up: widening the walk is precisely the change that could reintroduce this issue's quadratic, so the #928 frozen workloads should be re-run as part of that fix.