Parser: nested classic for-heads with function bodies parse in exponential time and memory

Parent: #933 (adversarial complexity) Related: #936, whose review found this; that fix covers only the stack-exhaustion case

Confirmed by execution

A valid program whose classic for heads nest function expressions makes the parser do exponential work: time and memory double with each level. Each program below is wrapped in function __never(){ … }, so only parsing runs. Measured with test262 --eval built at 480516b (ReleaseFast), with /usr/bin/time -l for peak memory:

The member form keeps doubling on the parent of #936 (d91ae16): depth 20 took 821 MB and 0.75 s, and at depth 22 the process passed 3 GB before the memory guard killed it. node validates every shape and parses depth 200 of the member form in 0.2 ms.

Cause

parseFor (src/parser.zig:2478) first tries the head as a for-in/of target through tryForTarget (2577). For the forms above, that attempt parses the whole head, including every nested function body and the for statements inside it. When no in/of follows, it rewinds (self.pos = save, 2523) and parses the same tokens again as a classic initializer. Every nested for inside does the same during both passes, so N levels cost about 2^N parses. The discarded ASTs are arena-owned and never freed, so memory doubles too.

The two controls stay flat because their target attempt stops before any function body: an identifier target is one token, and a for-in commits to the first parse.

Direction

The first parse should be reused, not repeated. Either continue the classic initializer from the already-parsed left-hand side (it is the start of the same expression), or decide the head form before parsing it. A token scan for in/of at bracket depth zero would keep one parse per level, though it would still scan each head's tokens once per enclosing head. Pin the member and lexical-pattern forms at a depth that is instant with the fix and hangs or exhausts memory without it.

Fixed in b1acc36.

Reproduced first on the current engine (zig-js 2dce0416, ReleaseFast) — the curve was still there, so the measurement in the issue holds:

Fix. Rather than reusing the discarded parse, the head's form is now decided before it is parsed at all, which is both cheaper and simpler to reason about: a classic head always has a ; at the head's own bracket depth, and an iteration head never does. Any ; belonging to something nested sits inside a parenthesis, bracket or brace, and a template substitution or regular expression is a single token in this lexer, so neither can contribute one at head depth. The check is therefore exact, not a heuristic, and each head is parsed exactly once.

I did consider continuing the classic initializer from the already-parsed left-hand side, as the issue suggested. It breaks on the cover grammar: for (async () => {}; ;) parses as a call under tryForTarget and only becomes an arrow once => is seen, so reuse would need a rewind exception per cover form. The scan avoids that entirely.

After:

Flat, and depth 200 — the depth node parses in 0.2 ms — now parses in 0.01 s. node --check validates every program used in the measurement.

No conformance change: test/language/statements/for 385, for-in 115, for-of 751, for-await-of 1,234, test/annexB 1,086, test/language/expressions 11,038 — 14,609 tests, 0 fail on both sides, every failure list identical. Flips 0 cases. Focused suites: runtime 16, frontend 26, vm 4, jit 393.

The new regression case pins depth 24 of both shapes — tens of gigabytes for the old parser, instant now — together with eight checks that deciding the form did not change what any head means: for-in key order, for-of iteration, classic counting, a member for-in target (for (o.x in …)), destructuring for-of, a classic head whose initializer is a function expression, and the for (async of => 1; false;) head, which is a classic for and not a for-of.

Landed in b1acc36 with the evidence above.