Frontend: index statement source locations in linear time

Parent: #496 Related: #461, #493, #501

Problem

Parser.parseStatement called sourceLocationAt(source, token.pos) for every statement. sourceLocationAt starts at byte zero and scans the entire prefix to count line terminators. A source containing N sequential statements therefore performed quadratic prefix work solely to retain debugger/source metadata. The source bytes and statement count are attacker-controlled, so this was both a cold-frontend bottleneck and a worst-case latency boundary.

Resolution

• Benchmark contract: 3bba3de9 (bench(frontend): add statement location growth rows (#554)).
• Runtime fix: 87eba6c2 (perf(parser): index repeated source locations (#554)).
• Evidence: 2de66881 (docs(frontend): publish statement location evidence (#554)).

The parser keeps its first two statement-location lookups allocation-free. On the third lookup it performs two bounded linear scans to size and fill one exact arena-owned line-start table, publishes the table only after successful construction, and resolves later locations with binary search. The sizing pass checks integer overflow. Standalone one-shot sourceLocationAt behavior remains unchanged.

Evidence

The overview and linked raw artifacts preserve six ReleaseFast rows, seven order-balanced exact-parent pairs per row, all 84 fresh processes, and no discarded samples.

• Repeated-statement wall medians are 0.006x to 0.038x of the quadratic parent; retired instructions are 0.0048x to 0.0263x.
• The 1K/2K/4K sequential candidate instruction counts grow approximately linearly while the parent grows approximately quadratically.
• The single-statement control keeps allocation requests 4133 -> 4133, allocated bytes 2470848 -> 2470848, instructions at 0.9991x, wall at 1.004x, and peak RSS at 1.0018x.
• The bounded index costs one allocation and 8,200/16,392/32,776 bytes for the 1K/2K/4K sequential rows.
• Raw JSON retains checksums, hashes, CPU, RSS, allocation, instruction, cycle, energy availability, power, thermal state, and dispersion. The battery/fair-thermal run is deliberately diagnostic; candidate energy deltas were below counter resolution, so no energy-ratio claim is made.

Correctness stayed line-terminators 41 -> 41, source-text 1 -> 1, debugger 2 -> 2, and Annex B 1086 -> 1086: 1130 -> 1130, zero failures or flips. Frontend Debug and TSan pass 12/12 each; full units pass 1625 with one expected skip and zero failures/leaks; four real-corpus witnesses pass in both forced tree-walker and required-bytecode modes.

No-workaround rules

• No omitted/coarsened locations, ASCII/LF-only counting, hidden warmup preprocessing, cached benchmark source, token/AST widening, benchmark recognition, or disabled debugger registration.
• Source scanning remains inside the claimed parse boundary.
• No stacks, queues, jobs, Promise/microtask, or Worker lifecycle code changed.

Acceptance

• Benchmark source, base/variant/control identities, jobs, checksums, warmup, and timed boundary landed before the runtime change.
• Total statement-location construction is O(source bytes + statements log lines), with bounded index storage and no repeated full-prefix scans.
• Exact byte offsets and 1-based lines/columns match for LF, CRLF, lone CR, U+2028/U+2029, comments, nested statements, and EOF diagnostics.
• The wide single-statement control does not regress materially in instructions, allocations, bytes, or peak RSS.
• OOM/fault paths are atomic and bounded; fresh parser retries and Context teardown release arena-owned index backing.
• Focused frontend Debug/TSan, full units, source-location/debugger/Annex B test262, and forced tree-walker/VM execution pass without regressions.
• Seven-pair exact-parent evidence publishes wall, CPU, allocation requests/bytes, peak RSS, instructions/cycles/energy availability, thermal state, and dispersion with no discarded samples.

Security boundary

Source length, line-break encoding, comment layout, and statement count are attacker-controlled. The fix bounds their work, checks index sizing overflow, folds CRLF exactly, treats LF/lone CR/U+2028/U+2029 consistently with the lexer, and preserves source/debug metadata.

Benchmark-first commit landed on main as 3bba3de9: bench(frontend): add statement location growth rows (#554).

Frozen rows:

• LF-separated statements at 1K/2K/4K;
• 4K mixed comments plus LF/CRLF/lone-CR/U+2028/U+2029;
• 1K nested if/block/expression statements, which deliberately request locations in inner/block/outer completion order rather than source order;
• a 4K-element single-statement control.

Source construction stays outside all warmup/scored boundaries. Each row performs real lexing/parsing/metadata construction and validates exact AST identity, metadata order/cardinality, byte offsets, 1-based lines/columns, source length, and checksum. With one scored parse after ten single-parse warmups, exact checksums are 8289455, 33900207, 138599087, 201534128, 50539705, and 8390657.

No parser/runtime fix is included in this commit.

Runtime change landed on main as 87eba6c2: perf(parser): index repeated source locations (#554).

The parser keeps its first two statement-location lookups allocation-free. On the third lookup it performs two bounded linear scans to size and fill one exact line-start table, publishes the table only after successful allocation/fill, and uses binary search thereafter. The counting path checks integer overflow. LF, CRLF, lone CR, U+2028/U+2029, comments, nested completion order, byte offsets, and one-based coordinates are covered directly; the standalone diagnostic/embedder sourceLocationAt API is unchanged.

Verification:

• frontend Debug and TSan: 12/12 each;
• full units: 1625 passed, 1 expected skip, 0 failed, 0 leaked;
• exact test262 parent -> candidate: line-terminators 41 -> 41, source-text 1 -> 1, debugger 2 -> 2, Annex B 1086 -> 1086 (0 flips);
• four real-corpus witnesses passed in both forced tree-walker and required-bytecode modes;
• allocation-failure sweep observes OOM and eventual success without publishing partial index state.

The benchmark checksums also match after the change. I am keeping this issue open while I collect and publish the required seven-pair exact-parent performance and resource evidence, including the single-statement control.

Completion evidence landed on main as 2de66881: docs(frontend): publish statement location evidence (#554).

The six exact-parent reports preserve seven alternating pairs each, all 84 processes, and all frozen checksums. Repeated-statement wall medians are 0.006x-0.038x of the parent and retired instructions are 0.0048x-0.0263x. The 4K-element one-statement control stays neutral: allocations 4133 -> 4133, bytes 2470848 -> 2470848, instructions 0.9991x, wall 1.004x, peak RSS 1.0018x.

All attribution artifacts validate; benchmark-comparison-test and docs-link-check pass. The issue body now links every commit and artifact and records all acceptance checks.

Child #610 is complete on main in 288136ba.

Statement coordinates now advance once at parse entry while retaining the existing completion-order debugger registry. Classic-for speculation transactionally rolls back its coordinate cursor and discarded ghost locations. Exact-parent instructions improve to 0.7327x on the causal Unicode row and 0.8835x–0.9107x across the repeated/mixed/nested location rows; the one-statement control is 0.9949x with allocation count and bytes exact. Test262 stays 1,028 -> 1,028; full units pass 1,726 plus one expected skip.

Related parser hash hardening landed in #761 via fix(parser): seed declaration name membership (#761). It reuses the realm Shape domain source for all transient parser string membership while preserving lazy candidate-free parsing.