Shapes: index deep named-property lookup without breaking transitions

Parent: #493 Related: #460, #471, #478, #480, #529

Problem

Shape.lookupState and Shape.lookup walk the immutable parent chain linearly. That is compact and effective for ordinary shallow objects, while inline caches remove repeated lookup at stable source sites. Generic or computed access to an object with N attacker-controlled named properties cannot use one stable inline-cache key, however: each HasProperty or Get walks O(N) shape operations. A length-N Array generic over a plain array-like with N numeric named properties therefore performs O(N²) shape-name comparisons.

The deterministic #529 diagnostic rows expose the independent curve: 1K, 2K, and 4K generic array-like traversal grows far faster than linearly even after temporary decimal-key allocation is removed. This issue owns the lookup complexity; #529 remains the separate temporary-key lifetime fix.

Scope

• Add an immutable or versioned exact name-to-latest-operation index for deep Shapes, preserving transition sharing, stable slots, deletion tombstones, re-add semantics, and prepared literal shapes.
• Keep shallow objects compact and fast; activate or consult indexed state only when exact attribution justifies it.
• Make every lookup collision-safe and deterministic in semantics under attacker-controlled property names.
• Prove publication ordering and lifetime for no-GIL readers, concurrent transitions, deletion compaction, moving GC, and Context teardown.
• Bound index construction, rebuild, and retained memory in terms of live/historical shape state.

No-workaround rules

• No cap on object property count or Array logical length, numeric-key special case presented as a general shape fix, semantic key cache, linear fallback on hash collisions, globally shared mutable cache, predictable collision-vulnerable table, GIL, or bypass of attributes/prototypes/Proxy behavior.
• Do not replace the shape chain with per-object maps or sacrifice transition convergence without exact evidence proving the full object-model tradeoff.

Acceptance

• Exact-parent 1K/2K/4K computed Has/Get and generic array-like rows demonstrate approximately linear work using instruction and shape-lookup counters, with frozen results.
• Shallow literal, monomorphic property, transition-hit/miss, deletion/re-add, sparse numeric, and dense Array controls do not regress materially.
• Collision corpus, adversarial names, deep delete/re-add history, deterministic OOM/fault injection, and bounded-heap/RSS tests pass.
• Shared transition publication scales monotonically at 1/2/4/8 lanes; no-GIL, threadfuzz, moving/parallel GC, lifecycle, and suppression-free TSan pass.
• Full units and affected test262 Object/Array/Proxy subtrees pass with nonzero denominators.

Security boundary

Property names and shape depth are attacker-controlled. Lookup must remain exact under collision and concurrent publication while CPU and retained memory stay bounded by documented shape state.

Implementation landed on main as 7666c5f1: perf(shape): index deep property lookup (#530).

What changed:

• deep shapes switch at depth 32 from linear parent-chain lookup to a collision-free persistent exact-key AVL index;
• transition fanout uses the same immutable exact-key tree instead of predictable hashing;
• writers path-copy under the existing transition lock and readers acquire a fully published immutable root;
• shallow shapes retain the compact chain, and delete/re-add keeps stable-slot/undo behavior.

Validation completed:

• full units: 1,586 pass, 1 skip, 0 fail/leak;
• focused TSan four-lane no-GIL construction/fanout convergence passes;
• exhaustive allocation-failure rollback passes;
• bounded 32 MiB heap plus real moving compaction over 4,096 properties passes;
• deterministic 4,096-name lookup and 2,048-way fanout both remain at AVL height <= 16 and every exact/missing lookup stays within tree height;
• threadfuzz default and broad: 400 seeds each, 0 failures;
• test262 Object 3,411/3,411, Array prototype 2,810/2,810, Proxy 311/311 in both parent and candidate (6,532 cases, 0 flips).

The intentionally oversized lifecycle run (400 seeds × 56 subcases) is still progressing; exact-parent timing/allocation evidence will follow in a separate evidence commit before this issue is closed.

Exact-parent evidence landed on main as 21a33f13: docs(performance): publish deep Shape index evidence (#530).

Direct implementation edge: 8592a7dc → 7666c5f1.

Stable work result (candidate / parent instructions):

• 1K computed Has/Get: 0.288x
• 2K: 0.190x
• 4K: 0.092x
• sparse Proxy over a 4K target: 0.360x

Candidate median instructions per traversed property/job stay nearly flat: 24,494.5 at 1K, 24,532.5 at 2K, and 25,086.8 at 4K (only 1.024x growth), while the parent rises from 85,040.9 to 273,604.1. Wall medians improve strongly too, but the report labels them diagnostic where this host exceeded the wall-dispersion threshold; no samples were discarded.

Controls:

• shallow classes: 1.003x wall / 1.011x instructions;
• mixed application: 0.973x / 0.999x;
• dense Array: 1.048x / 1.088x (inside the declared 10% material threshold).

Memory is explicit: 4K post-invocation retained RSS rises from 38,322,176 to 40,501,248 bytes, +2,179,072 bytes (1.057x). The 32 MiB heap/moving-compaction witness passes, and the index is Context-arena-owned.

Correctness:

• exact-source full units: 1,586 pass, 1 skip, 0 fail/leak;
• focused suppression-free TSan passes;
• default and broad threadfuzz: 400 seeds each, 0 failures;
• lifecycle: 3,359/3,360 subcases pass. The sole failure is the separately owned microtask/asyncHold score oracle; exact parent reproduces the same failure class (559/560), so it is not a Shape regression;
• Object + Array prototype + Proxy test262: 6,532 pass in both revisions, 0 flips;
• docs link check and checked 49-page build pass.

Evidence: exact-parent-deep-shape-index-2026-08-10.md.

I am keeping #530 open for its remaining declared acceptance item: a real 1/2/4/8-lane shared transition-throughput publication. The four-lane functional/TSan witness is not being presented as that missing scaling result.

#530 is complete on its deep-lookup/security scope:

• implementation: 7666c5f1
• exact-parent evidence/docs: 21a33f13
• evidence report: exact-parent-deep-shape-index-2026-08-10.md

The remaining 1/2/4/8 shared publication requirement exposed a distinct shared arena/object-model bottleneck and is now explicitly owned by #531. Its benchmark was committed first in d9d54b5b, with partitioned, anti-specialization, and contended rows and no runtime fix mixed in.

Closing this issue does not claim #531 scaling is solved; it records the completed collision-free logarithmic lookup implementation and preserves the independent concurrency defect in its own acceptance contract.