镜像站点 · 本页由第三方 GitHub 只读镜像提供,非 GitHub 官方站点,不接受任何登录或凭据输入。前往 github.com
Skip to content

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

Closed

Description

@glennmichael123

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/.

Activity

  1. glennmichael123 commented on Sep 15, 2026

    @glennmichael123
    ContributorAuthor

    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.

    shape N allocs × retained bytes ×
    siblings (growth) 256 4,410 5,822,088
    512 9,282 2.10 20,685,072 3.55
    1024 19,530 2.10 76,320,048 3.69
    2048 41,041 2.10 297,013,816 3.89
    deep (growth) 256 3,472 3,098,192
    512 7,419 2.14 10,904,048 3.52
    1024 15,818 2.13 36,901,776 3.38
    2048 33,640 2.13 142,200,904 3.85
    no_inherited (control) 256 2,351 1,089,056
    512 4,661 1.98 2,687,176 2.47
    1024 9,276 1.99 4,636,400 1.73
    2048 18,499 1.99 9,558,056 2.06
    single_inner (control) 256 59 152,216
    512 65 1.10 332,880 2.19
    1024 73 1.12 830,352 2.49
    2048 80 1.10 1,232,904 1.48

    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.)

    shape N min ns median ns within-width spread median ×
    single_inner (control) 1024 203,416 364,708 2.19×
    2048 462,000 552,584 2.19× 1.52
    no_inherited (control) 1024 564,000 596,625 1.25×
    2048 1,020,042 1,075,792 1.21× 1.80
    siblings (growth) 1024 32,820,875 39,488,875 1.75×
    2048 187,638,208 208,369,583 1.51× 5.28

    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.

  2. glennmichael123 commented on Sep 15, 2026

    @glennmichael123
    ContributorAuthor

    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.

    shape N time before time after speedup retained before retained after
    siblings 1024 37.1 ms 0.73 ms 51x 76.3 MB 5.0 MB
    siblings 2048 232.6 ms 1.51 ms 154x 297.0 MB 11.6 MB
    deep 1024 16.8 ms 0.63 ms 26x 36.9 MB 3.8 MB
    deep 2048 90.0 ms 1.38 ms 65x 142.2 MB 9.3 MB

    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).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    enhancementNew feature or requestperformanceMeasured runtime, memory, scaling, or build performance

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions