ReviewOS

zig-utils/zig-js

Parser: reserve strict-parameter uniqueness indexes once

#613
Closed chris opened this 9 days ago ·
9 days ago

Parent: #496 Related: #493, #520, #611, #612

Problem

After #611 removed impossible parameter/body conflict indexes and #612 shortened raw identifier scanning, the current ReleaseFast 4K Unicode-parameter profile spends most of the parser half in Parser.validateStrictParams. Its StringHashMapUnmanaged starts empty even though the complete params.len upper bound is already known, so attacker-sized unique lists repeatedly allocate, grow, and rehash the same names before the strict-mode duplicate early error can be decided.

The current #612 exact-parent ASCII control performs 57 allocation requests and allocates 2,534,568 bytes per parse. The profile attributes 88 of 91 sampled validateStrictParams frames to getOrPut/growth and its string hashes.

Proposed resolution

Give strict simple-parameter uniqueness validation one capacity decision derived from the already-parsed formal-parameter count, then retain the existing exact string hash/equality insertion and duplicate rejection semantics. Do not change sloppy duplicate permission, destructuring BoundNames validation, generator/async/arrow/method rules, or parameter/body lexical conflicts.

If sharing the reservation primitive with other UniqueFormalParameters paths is measurably beneficial, it must reserve from an exact bound-name count rather than under-reserving an arena-backed map that later leaks a superseded table.

Acceptance

  • Strict ordinary functions reject every duplicate, eval, arguments, and strict-reserved binding accepted by the current validator.
  • Sloppy simple ordinary functions retain duplicate-name compatibility.
  • Generator, async, arrow, method, default/rest, and destructuring uniqueness rules remain exact; no duplicate validation is accidentally performed twice.
  • Empty and small parameter lists avoid unnecessary capacity allocation; wide valid lists avoid geometric growth and rehashing.
  • Allocator exhaustion propagates without stale parser state or leaked scratch memory.
  • Exact-parent 1K/2K/4K ASCII, escaped, and Unicode controls preserve checksums while reducing wide-list allocation requests/bytes and CPU work; direct/nested body controls remain exact.
  • Focused parser/frontend Debug/TSan, full units, affected test262 subtrees, and forced tree-walker/required-bytecode witnesses pass.

Security boundary

Parameter count, name length, hash distribution, duplicate position, escape spelling, destructuring depth, and allocator failure are attacker-controlled. Capacity arithmetic must be checked, allocation must remain request-scoped scratch storage, equality must remain exact after hashing, and the algorithm must remain expected linear rather than introducing a quadratic pre-scan.

No-workaround rules

No parameter-count cap, approximate fingerprint equality, skipped Unicode/escape decoding, weakened early errors, source/benchmark recognition, AST widening, or jobs/Promise/microtask/Worker lifecycle changes.

9 days ago

Implemented and pushed to main in 09bcd444 (perf(parser): reserve strict parameter indexes once (#613)).

validateStrictParams now counts the already-parsed simple parameters and makes one checked StringHashMap capacity decision before exact string insertion. Empty and singleton lists allocate no index. The scratch table is still request-local, is fully freed on success/rejection, and retains exact hash-plus-equality duplicate detection; there is no count cap or fingerprint-only comparison.

The focused allocator contract proves:

  • 16 unique names allocate exactly once and free the complete allocation;
  • empty and singleton lists succeed with a zero-capacity allocator;
  • first-allocation exhaustion returns OutOfMemory;
  • a fresh retry succeeds;
  • duplicate names, eval, arguments, and strict-reserved bindings still reject.

Exact-parent evidence

Parent 9861bf53 versus candidate 09bcd444, ReleaseFast, 15 order-balanced pairs per row, 330 fresh processes total, no discarded samples. The timed boundary is one parser construction, parse, AST validation, and arena teardown. Every binary/source identity and checksum matched.

controlinstruction ratioallocationsallocated bytes
ASCII 1K0.8167x48 -> 40715,056 -> 680,184
ASCII 2K0.8259x52 -> 43993,448 -> 923,736
ASCII 4K0.8315x57 -> 472,534,568 -> 2,395,200
escaped 1K0.8957x2,096 -> 2,0881,177,696 -> 1,142,824
escaped 2K0.8952x4,148 -> 4,1391,907,752 -> 1,838,040
escaped 4K0.8965x8,249 -> 8,2394,197,304 -> 4,057,936
Unicode 1K0.8687x48 -> 40715,056 -> 680,184
Unicode 2K0.8791x52 -> 43993,448 -> 923,736
Unicode 4K0.8758x57 -> 472,534,568 -> 2,395,200
direct lexical body 4K0.8599x72 -> 622,813,688 -> 2,674,320
nested lexical body 4K0.8211x64 -> 542,535,648 -> 2,396,280

Retired-instruction RSD is below 5.4% in every row. The host is diagnostic and several sub-millisecond wall rows are noisy, so no public wall-time claim is made.

Correctness

  • focused Debug strict-parameter tests: passed;
  • focused TSan: 2/2 passed;
  • frontend: 12/12 passed;
  • full units: 1,730 passed, 1 expected skip, 0 failed, 0 leaked;
  • test262: ordinary functions 451, statement generators 266, expression generators 290, statement async generators 301, expression async generators 623, async arrows 60, async expressions 93, async declarations 74, object methods 303, class definitions 65; 2,526 -> 2,526, zero failures or flips;
  • four forced tree-walker/required-bytecode witnesses: passed in both tiers.

No jobs, stacks, queues, Promise, microtask, Worker, or lifecycle surface changed.

Sign in to comment on this issue.