ReviewOS

zig-utils/zig-js

Compiler: securely seed AST identity plan indexes

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

Parents: #493, #496 Related: #618, #628, #770, #788, #855

Problem

#770 keyed compiler identifier-content maps, but three source-populable AST identity plans still use default AutoHashMapUnmanaged hashing:

  • FnScope.annex_b_variables maps sloppy block-function declaration identity to its variable slot;
  • Compiler.environment_annex_b maps top-level Annex B declaration identity to its environment plan row;
  • RepeatedBodyCaptures.captured_catch_patterns caches repeated-body catch-pattern capture classification.

User source controls the number and insertion order of these arena nodes. Predictable arena placement/ASLR is not an explicit collision defense, and replacing identity keys with source content or repeated scans would change semantics or recover superlinear work.

Implementation

  • Add an exact AST-identity map context keyed from the existing lazy compilation-owned secure seed.
  • Convert all three plans while preserving exact pointer identity, slot/row numbering, capture decisions, and Chunk bytes.
  • Share the same seed across program, plain-function, nested-function, generator, async, and admission/prepass structures.
  • Publish a newly derived seed only after the first identity insertion succeeds; empty lookup paths remain allocation- and entropy-free.
  • Preserve compiler-arena ownership and add no AST metadata, extra pass, or runtime state.

Acceptance

  • All three AST identity plan indexes use the keyed context; no default pointer hash remains in compiler.zig.
  • A deterministic witness proves a legacy fixed-bucket identity family disperses under a keyed context while exact lookup remains correct.
  • Failed first insertion leaves both the identity index and compile-root seed unpublished; retry succeeds.
  • Annex B program/function planning and repeated-body catch capture preserve exact semantics and structural Chunk layout across distinct seeds.
  • Existing complete allocation replay covers the changed insertion paths.
  • Compiler/frontend Debug and TSan, full units, exact-parent Test262, threadfuzz, and public/private ABI gates pass.

No-workaround rules

No source blacklist, grammar limit, linear identity scan, address-secrecy assumption, forced interpreter fallback, predictable seed, per-map entropy call, extra AST pass, or third-party hash table.

9 days ago

Implemented and pushed to main as fix(compiler): seed AST identity plan indexes (#856).

What landed:

  • FnScope.annex_b_variables, Compiler.environment_annex_b, and RepeatedBodyCaptures.captured_catch_patterns now use exact-identity maps keyed from the existing lazy compilation root secret;
  • program/function Annex B rows, repeated catch classifications, slot numbering, and Chunk layout remain exact;
  • empty lookups remain allocation- and entropy-free; a failed first insertion publishes neither capacity nor seed;
  • no AST metadata, extra pass, source cap/blacklist, linear scan, address-secrecy assumption, or forced interpreter fallback was added.

Exact-tree evidence:

  • 32 identities colliding in one legacy 1,024-bucket partition disperse across at least 24 keyed buckets while exact values remain retrievable;
  • failed first insertion leaves zero capacity/entries and no seed; retry succeeds;
  • distinct compiler seeds produce identical frame and nested Chunk layout across function Annex B and repeated destructuring-catch capture paths;
  • complete allocation replay covers block-function, environment Annex B, and repeated-catch identity insertions;
  • compiler Debug and TSan: 113 passed, 0 failed, 0 leaked each;
  • full unit suite: 2,268 passed, 1 skipped, 0 failed, 0 leaked;
  • threadfuzz: 400 programs from seed 1, 0 failures;
  • exact-parent Test262: Annex B 1,086/1,086 and statements 9,337/9,337 for both parent and candidate, 0 flips. Diagnostics are byte-identical: Annex B SHA-256 a9055dcfca32c8bf26f818afe84f40a67becf7beeb71af967705d009d1b87dfd; statements SHA-256 d35be63632c4d3e6a0be21dc7da3c1404d17946a1a7b828989d494444302e16d;
  • public C API: 117/117; Home private ABI: 447/447 owned symbols and 392/392 runtime shims.

Sign in to comment on this issue.