Frontend: private-name use validation copies every inherited name per nested class

Parent: #493 Related: #496, #540, #539, #461

Status: investigation from code inspection. No measurement exists yet, and no

performance claim is made here.

Suspected mechanism

Parser.checkPrivateUsesInNode's class_expr arm passes the enclosing declared-name map into the nested class:

.class_expr => |c| {
    if (c.superclass) |sc| try self.checkPrivateUsesInNode(declared, sc);
    try self.checkPrivateNameUses(declared, c.members);
},

and checkPrivateNameUses opens a fresh map and copies every inherited entry into it before adding the class's own names:

var declared = self.secureStringMap(void);
var it = inherited.iterator();
while (it.next()) |entry| try declared.put(self.arena, entry.key_ptr.*, {});

So an outer class declaring N private names, containing M inner classes as siblings (field initializers, static blocks, methods returning class expressions), performs M × N inherited insertions for a source of size O(N + M). With M ≈ N that is quadratic work — and because the copies go into self.arena, which is not released during the parse, it is quadratic retained allocation, not only CPU.

This is attacker-controlled shape: the source is linear in size.

Why this is not #540

#540 bounded checkPrivateNames, the pairwise duplicate comparison among the N members of a single class, and is closed. This is a different function on a different axis: the copy of inherited names into each nested class. The two can both be true.

Why no existing benchmark would have caught it

bench/frontend_parse.zig's privateClassSource emits one flat class:

class PrivateWidth { #field0; #field1; ... }

representative_frontend_private_names_{1024,2048,4096} and their escaped controls all use that shape, so no frozen workload nests a class inside another class. The inherited-copy path is uncovered.

Plan, in this order

1. Freeze workloads and controls before touching parser code, added to the owned bench/frontend_parse.zig growth runner:
   • growth rows at 1024/2048/4096: outer class with N private names containing N sibling inner class expressions that reference an inherited name.
   • controls that must not move: the existing flat private_names family; an outer class with N names and a single inner class; N sibling inner classes with no inherited names to copy; a deep-nesting variant to separate depth from breadth.
   • correctness controls: shadowing an inherited name in an inner class, heritage evaluated in the enclosing environment (class C extends class { x = this.#foo; } { #foo; } must stay a SyntaxError), #x in obj brand checks, and a direct eval inside a class body.
2. Measure allocation requests/bytes and instructions per width with the owned runner under the 3072 MB bounded guard, and confirm the growth curve before proposing a fix.
3. Only then consider a scoped change — an active-name set with rollback, or passing the inherited map by reference with a depth-scoped overlay — preserving sibling isolation, shadowing, heritage ordering, secure hashing of attacker-controlled names, exact byte equality, and atomic OOM behaviour.

Explicit non-goals

No arbitrary nesting limit, no benchmark-name special-casing, no weakening of early errors, and no published benchmark claim until the owned generator (tools/algorithmic-growth.ts) produces dated evidence under docs/.data/.

Measured: the growth is real, and one of the four shapes I called a control is not one

Steps 1 and 2 of the plan are done. No parser code changed — the workloads and the semantic baseline landed first, which is the ordering this issue committed to.

Two corrections to the plan before the numbers

deep is not a control. The plan described it as "separating depth from breadth — a chain copies a growing set exactly once per level." The description is right and the conclusion drawn from it was wrong: copying a growing set once per level is 1+2+...+N, which is quadratic too. It separates depth from breadth but not linear from quadratic, so it cannot serve as a control. It is a second growth shape, measured at roughly half the siblings constant exactly as N²/2 vs N² predicts. Its doc comment in bench/frontend_parse.zig now says so. The real controls are no_inherited (N nested classes, nothing to copy) and single_inner (N names, exactly one copy).

Widths are 256/512/1024/2048, not the 1024/2048/4096 the plan named. Retention grows as N²: at 2048 the frontend arena already holds 297 MB for a 98 KB source, so 4096 would be ~1.2 GB for a 196 KB source — not a sensible routine row under the 3072 MB bounded guard.

Allocation requests and retained bytes

Deterministic: identical across all iterations of a run and across three independent runs.

Every source is linear in N: siblings is 12,082 → 24,370 → 48,994 → 98,242 bytes (×2.02, ×2.01, ×2.01), and the other three shapes match that to two decimals.

Retained bytes are the primary evidence. Both growth shapes converge on ×3.9 per doubling against a ×2.0 source; both controls stay at ×1.5–2.5.

Allocation count is not the signal here, and the reason is worth stating: each nested class's map doubles into self.arena in O(log N) steps, so a shape with N nested classes makes O(N log N) allocation requests (×2.10 for siblings, deep and no_inherited alike) while single_inner, which has exactly one nested class, stays near-constant (×1.10). What separates the growth shapes from the controls is that the arena is never released during the parse and each final block is O(N), so bytes accumulate as N². That is the quadratic retained allocation the issue body predicted, not only CPU — and it is why no_inherited can match siblings on allocation count (18,499 vs 41,041) while using 31× less memory.

Wall time

15 iterations after 2 warmups, because at 2048 the controls finish in ~1 ms and three samples of a sub-millisecond parse spread 3×, which is the noise floor rather than growth. (An earlier 3-iteration run showed single_inner at ×3.25 purely from that noise; with 15 iterations it is ×1.52.)

Both controls are linear. siblings is ×5.28 on median (×5.72 on min), i.e. above the ×4 that N² alone predicts — at 2048 the parse retains 297 MB of arena, so a memory-system tax compounds on top of the algorithmic quadratic. The clean algorithmic exponent is the byte ratio (×3.89); the time ratio is N² plus that tax, and I am not claiming a clean ×4 on time at this width.

What this establishes

• The cost is the copy, not the nesting. no_inherited parses the same N nested class expressions from a same-size source, and the only difference is whether there is an inherited set to copy. siblings is 66× slower at N=1024 and 194× at N=2048 — the penalty itself grows, which is the signature of the quadratic rather than a constant overhead. On retained bytes it is 16.5× and 31.1×.
• deep sits near half the siblings constant — 0.479 on bytes at 2048, against the 0.5 that N²/2 vs N² predicts. That arithmetic is what confirms it as a second quadratic shape rather than a control.
• The source is linear and attacker-controlled in shape, so this is reachable from untrusted input.

Semantic baseline landed alongside

parser private name scoping isolates siblings and descendants pins the behaviour any fix must preserve, and every case was confirmed against JavaScriptCore first rather than asserted from reading the spec:

• an inner class sees its ancestors' names, by use and by #x in o brand check;
• redeclaring shadows, and a sibling that does not redeclare still binds the outer name — so two inner classes must not end up sharing one mutable set;
• an inner class's heritage is checked in the enclosing environment;
• a name from an earlier sibling, from a descendant, or from the class's own body while checking its own extends clause is a SyntaxError — class C extends class { x = this.#foo; } { #foo; } stays an error.

That last group is what an "active set with rollback" fix would break most easily, which is why it is pinned before any such fix exists.

Not published evidence

These are bench/ investigation numbers, not a publication claim: no docs/.data/ report and no README change, per this issue's non-goals. Raw per-workload .tsv samples were kept per run and are not checked in.

Next

Step 3 — a scoped change preserving sibling isolation, shadowing, heritage ordering, secure hashing of attacker-controlled names, exact byte equality, and atomic OOM. The measured curve points the fix at the inherited copy itself rather than at the nesting: a single scoped set with explicit rollback at each class boundary, instead of a per-class copy.

Workloads, semantic baseline and doc corrections landed in 411b901.

Fixed in e07b13b — step 3 done, measured

checkPrivateNameUses now extends the enclosing set in place and unwinds it on the way out, instead of opening a fresh map per nested class and copying every inherited name into it.

The reason an undo log is safe: requirePrivateName only ever asks contains, and the map value type is void. Membership is the only query the structure ever answers, so extend-and-unwind is observationally identical to copy-per-class. Shadowing then falls out of insert-if-absent for free — a name an ancestor already declared is not inserted here, so it is not removed here either, and it correctly outlives the inner class.

Results

Median of 15 iterations on an idle machine, one job at a time under the bounded guard.

The speedup grows with N — 51x at 1024, 154x at 2048 — which is the exponent changing rather than a constant-factor win. Growth per doubling is now x2.08 (siblings) and x2.18 (deep) against a x2.01 source, down from x4.0-x5.3; retained bytes x2.1, down from x3.89.

Allocation requests at 2048 fall by 20,479 for siblings and 15,156 for deep. Both controls are at or below baseline at every width — no_inherited matches to the allocation (18,499 vs 18,499 at 2048), single_inner is 9 lower. That is the part that confirms the win is the removed copy and not removed work.

An intermediate version did regress no_inherited by 11% on allocations, because the undo log was reserved for every class including ones declaring no private name at all. Counting declarations first fixed it, and it also preserves the zero-allocation property the constrained-scratch tests depend on.

What the adversarial pass was actually worth

Four independent attacks tried to find a program where extend-and-unwind differs observably from copy-per-class. None found one — but three of their residual risks were real, and two were bugs I would otherwise have shipped:

1. SecureStringMapUnmanaged had **no remove at all**, so the design was unimplementable as stated. Added one that reads the published context like contains` rather than deriving a candidate seed.
2. The natural put + append pairing makes an inner class's shadowing #x delete the outer one on exit. Insert-if-absent via getOrPut is load-bearing, not an optimisation. Witness now pinned: class A { #x; m() { class B { #x; } } n() { return this.#x; } }.
3. If put succeeds and the undo-log append then fails, the name leaks outward as a missing SyntaxError. The log is now reserved before the first insertion so recording cannot fail after a name is visible.

The mark deliberately stays inside checkPrivateNameUses, after the heritage walk — hoisting it into the .class_expr arm would silently flip class C extends class { x = this.#foo; } { #foo; } from SyntaxError to accepted.

Verification

• parser private name scoping isolates siblings and descendants grows 10 -> 22 cases: accessor pairs, static blocks, template substitutions, computed keys and default-parameter classes, in both the valid and invalid direction.
• 10/10 parser tests pass, including parser private constructor members preserve lexical name validation (the checkAllAllocationFailures replay, which re-runs the parse under every allocation-failure point) and parser reports private name validation scratch exhaustion.
• test262: statements/class 4367, expressions/class 4059, eval-code 347, built-ins/Function 509 — 0 fail, every count matching baseline.
• checkPrivateUsesInProgram now asserts the map is empty after the walk, so a future arm that fails to roll back fails loudly in Debug.

Worth recording: no CI leg gates a private-name test262 subtree (.github/workflows/ci.yml:813 pins the only test262 leg to five unrelated directories), so the in-file unit test is the real gate here. That is why it was expanded rather than leaving the corpus to catch a regression.

Oracle caveat found on the way

home-tool — the JSC oracle this project uses for error parity — rejects valid private accessor declarations: class C { get #x() { return 7; } m() { return this.#x; } } gives SyntaxError: Cannot reference undeclared private names. node runs it and zig-js returns 7, and it is not the TypeScript layer (same on a .js file). The new accessor cases were therefore confirmed against node and the pre-change zig-js baseline instead.

Follow-ups filed

The same copy-per-nested-scope shape exists elsewhere, both verified by reading the code and both filed without a performance claim: #927 (runtime private-environment flattening in interpreter.zig, which bounds how much this parse-time fix is worth end-to-end) and #928 (checkLexicalDupes rebuilding the subtree var set per nested block).