Repository navigation
Description
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
- Freeze growth workloads and controls in
bench/frontend_parse.zigbefore 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". - 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 Frontend: private-name use validation copies every inherited name per nested class #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.
- 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/.
Activity
bench(frontend): freeze lexical/var scan growth workloads for #928
glennmichael123 commentedon Sep 15, 2026
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_letsis 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
wideruns the scan the same number of times asnested_letsand stays flat. N sibling blocks each armcheckLexicalDupesexactly 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_lexicalalone could not have shown this: removing the lexical declaration disarms the scan entirely via theseen.count() > 0guard, so it conflates "no scan" with "cheap scan". This is the control #926 taught me to build — there I labelleddeepa 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
varon arrival — O(1) per var instead of O(depth).The correspondence is exact: a
varconflicts 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 reuseSecureStringMapUnmanaged.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:
funcs_lexical, src/parser.zig:1048-1049);recurseFnBodystopping at function boundaries, and theswitcharm 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.
test(parser): pin lexical and var early errors across nested blocks
glennmichael123 commentedon Sep 15, 2026
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
checkLexicalDupesin 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. Avarmust not see lexical names outside its enclosing function: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 depthvar: 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 — aletoutside the function is at a depth above that base and must not matchEvery 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
addDecldistinguishes rigid (let/const/class, async/generator functions, and anything in strict mode) from non-rigid plain function declarations, so two plainfunction 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.switcharm (src/parser.zig:1276-1279) flattens every case body into onecheckLexicalDupescall, so the whole switch is a single lexical scope. Any restructuring has to keep that flattening, and the pinned caseswitch (0) { case 1: let x; break; case 2: var x; }guards it.Also note
checkLexicalDupesis reached from five call sites (src/parser.zig:993, 1259, 1278, 1295, 4308). The map should be threaded as a parameter rather than stored onParser:SecureStringMapUnmanagedholds a*SecureHashState, andParseris returned by value withshared_secure_hash_stateassigned afterinit, so a Parser-resident map that captured&self.secure_hash_stateat 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.
glennmichael123 commentedon Sep 16, 2026
Fixed in 0fb72d2
The two walks are now one. A
LexicalScopethreaded through the walk maps each open lexical name to the depth of the innermost scope declaring it, and everyvaris tested on arrival against the names currently open.As the correction above anticipated, this is not #926's plain membership set: a
varmust not see lexical names outside its function, sorecurseFnBodyraises avar_basedepth 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.widedrops 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-levelseenmap. 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 onwideandflat(5-9%) are inside the run-to-run spread thatno_lexicalshows in the other direction, so I am not claiming them either way.Verification
annexB/languageand 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.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
recurseFnBodyor a fresh scope. The fix makes a violation loud rather than silent:closeLexicalScopetreats a missing shadowed key asunreachable, 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:
withbodies; 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.
fix(parser): reject a var reusing a destructuring catch parameter
fix(bench): supersede frontend runner pin in matrix v35
fix(compiler): raise RangeError when a tree is too deep to compile
bench(frontend): freeze function-body growth rows and re-pin the runner
perf(parser): check lexical for heads by declaration order, not by re…
fix(parser): check every function body as it is parsed (#930)