Shape tree (#6759 Phase C): tracking + design review

[proggeramlug]

Tracking issue for #6759 Phase C (shape tree), per the parent issue's "own tracking issue + design review" gate.

Design doc: docs/shape-tree-plan.md, landing in #6797 — review of that doc is the design review. Core thesis: a shared keys_array already IS a shape (mutation always forks), the transition cache already IS the edge set, and typed_feedback/read-plan/wide-index already key on keys_array identity — Phase C promotes this to first-class Shape records and re-points consumers rung by rung.

Ladder (each rung lands independently behind green suites):

• C1 — shapes as first-class records; subsume per-object KEYS_INDEX + 4-entry WIDE_KEY_INDEX LRU → perf(runtime): #6759 Phase C1 — first-class Shape records keyed on keys_array identity (+ Phase C design doc) #6797
• C2 — property attributes + accessor-presence facts move into the shape (shape-split on descriptor install; diverged objects hang state off the Phase B meta record)
• C3 — shape pointer becomes object identity: unify class_id / literal shape ids / keys_array identity; codegen ICs + prop plans compare shape ids; keys_array demoted to a shape-owned enumeration artifact. Subsumes FIELD_CACHE, transition cache, read prop-plan. Own design review before landing (touches codegen + GC + every object path).
• C4 — dictionary mode formalized for wide/high-churn objects (today: ad-hoc thresholds 32/257 + delete compaction), authoritative per-object map in the meta record, off the transition system
• C5 — typed_feedback exactness: shape-adjacent guard families (object_get/set_by_name, class_field_get/set, method_direct_call) vet one exact shape id instead of re-deriving getter/setter/descriptor/prototype facts per call; representation-change invalidation gated on "shape actually changed"

Acceptance (from #6759): read/write/define/in/Object.keys within ~1.5× node across the micro suite; babel-class module init ≤2× node.

Known hard problems (doc §risks): class instances with keys_array == null (fourth shape representation, no array to key on); enumeration-order preservation through C4; per-thread shape tables on workers.

Prerequisites: #6795 (Phase A), #6796 (Phase B).

[proggeramlug]

Phase C3 design (for review — the entry gate #6759 prescribes)

Ground survey done against current main (four coexisting shape representations, all consumers mapped). Three load-bearing facts drive the staging:

1. The read PIC already compares shape identity in one load — each perry_ic_<site> global holds (cached_keys_array_ptr, slot) and the emitted IR compares obj->keys_array against it. What V8 has and we lack is not the compare — it's identity stability: ArrayHeader stores elements inline, so every append growth reallocates the keys array and every consumer keyed on its address (PIC, FIELD_CACHE, transition cache, C1 shape records) misses/rebuilds after each doubling.
2. class_id is immutable post-birth (all writes at allocation; vtable, instanceof, prototype resolution key on it), and anon-shape ids are compile-time content-addressed classes registered in a HashSet — NOT a numeric carve-out. So "reuse class_id as a mutable shape index" is off the table for class instances; their live identity stays the composite (class_id, keys_array) that typed_feedback::object_shape() already returns.
3. parent_class_id (header offset 8) is dead weight for class_id == 0 objects — a free, fixed-offset u32 in exactly the objects whose shape identity churns. Candidate home for a header-resident stable shape id (verification item: confirm no path reads parent_class_id unconditionally for class_id == 0; RegExp-header aliasing gets the usual regex_header_has_magic guard).

Staging (each rung lands independently, runtime-first)

• C3a — stable ShapeId, runtime-only. Shape records gain a monotonic shape_id: u32; a keys-addr→id table lives beside them in state().shapes. The append-grow chokepoint (the ONLY place a keys array is reallocated while logically remaining the same shape — the old array must be OWNED, not GC_FLAG_SHAPE_SHARED) migrates the C1 record old-addr→new-addr instead of dropping it: slot maps survive capacity doublings, killing the O(N) rebuild per doubling. A shared array's fork keeps allocating a NEW identity (that's a genuine transition edge, already recorded by the transition cache). GC array moves rekey the table during the metadata-rewrite phase (same pattern as descriptor owner rekeying); dead-owner prune extends to the id table.
• C3b — consumers re-key on ShapeId. FIELD_CACHE keys on (shape_id, key_hash) (survives grow AND GC moves); typed_feedback guard families vet the id (this is where C5 starts riding); store prop-plan gains the id for the class+expando hybrid case. Transition cache stays address-keyed (its entries are validated by target_len and re-primed cheaply).
• C3c — header-resident id + codegen. Plain objects (class_id == 0) carry their ShapeId in parent_class_id; inline allocation stamps it (codegen knows the literal shape at compile time — the transient shape_id/prebuilt-keys machinery already exists); the PIC compares the u32 id at fixed offset 8 instead of the keys pointer at 16. Ids are stable across grow and GC moves, so PIC hit-rate stops degrading with object growth, and the id half of IC caches needs no GC rewriting. Slot validity stays anchored in the shape table (accelerator-never-authoritative, as C1). This is the rung that touches perry-codegen property_get/set and gets its own review before landing.

Non-goals / preserved invariants

• Enumeration order: keys_array remains the order artifact through C3 (C4 moves it into the dictionary).
• Class instances: untouched in C3a/b except the composite-key guard exactness; folding class layouts into the id space is explicitly deferred (their identity is already stable).
• Trust model: shape table stays an accelerator — every hit validates against stored key bytes; ids are never dereferenced blindly.

C2 (per-key descriptor facts in the meta record, PR incoming) already covers the attrs/accessor half originally sketched for the shape sidecar — C3 does not move attrs again; they stay per-object until dictionary mode (C4) formalizes divergence.

Review points I'd like eyes on: (a) the owned-vs-shared grow-migration condition, (b) parent_class_id reuse for plain objects, (c) whether transition-cache should also move to ids in C3b or stay address-keyed.

[proggeramlug]

Ladder status — every rung now has a PR (stacked, merge in order):

• C1 — shapes as first-class records → perf(runtime): #6759 Phase C1 — first-class Shape records keyed on keys_array identity (+ Phase C design doc) #6797 (merged)
• C2 — per-key descriptor facts → perf(runtime): #6759 Phase C2 — per-key descriptor summaries in the ObjectMeta record #6800 (design refined: facts live in the per-object meta record, not the shape — per-shape negatives are unvalidatable pre-C3; doc updated in-PR). CI green except the known benchmark-drift lint; CodeRabbit clean.
• C3a — stable shape_id + owned-grow migration + GC rekey → perf(runtime): #6759 Phase C3a — stable shape identity: owned-grow migration + GC rekey #6801
• C5a — per-key vetting for the class-field inline-guard disable (babel-class acceptance blocker) → perf(runtime): #6759 C5a — per-key vetting for the class-field inline-guard disable #6802
• C3b/C3c-r — process-global id allocator (range-disjoint from class ids, never reused, worker-safe), header stamps in parent_class_id for plain objects, id-keyed FIELD_CACHE, PIC ABA fix → perf(runtime): #6759 C3c-r — header-stamped stable shape ids, id-keyed FIELD_CACHE, PIC ABA fix #6803
• C4 — concrete goals subsumed by C1+C3a+C3c-r (per-shape hash lookup, identity survives grow, never-reused ids, eager drop on compaction); residual formalization (meta-resident dict as enumeration-order authority, off the transition system) deferred until profiling shows transition-cache pollution — rationale in docs/shape-tree-plan.md.
• C3 codegen remainder (own review gate, per the original plan): eager stamping at allocation → typed_feedback tokens canonicalize on ids (lazy stamping would two-token-split each shape per site), PIC discriminated compare on the header id (the generic PIC also serves class instances, whose parent_class_id is real inheritance data), transition edges shape-resident. This is the one intentionally-open item; I'd propose tracking it as its own issue once this stack merges, with the Architecture: adopt V8's object-model construction — explicit runtime state, self-describing headers, shape tree (phases A–C) #6759 micro table as its acceptance gate.

Validation: each PR carries a full single-threaded runtime-suite run (1443 → 1445 → 1447 → 1450 green as the stack grows); gap suite vs node runs on the C2+C3a tip are in flight and a stack-tip run follows — results will land as PR comments.

[proggeramlug]

All rungs are merged to main:

• C1 → perf(runtime): #6759 Phase C1 — first-class Shape records keyed on keys_array identity (+ Phase C design doc) #6797, C2 → perf(runtime): #6759 Phase C2 — per-key descriptor summaries in the ObjectMeta record #6800, C3a → perf(runtime): #6759 Phase C3a — stable shape identity: owned-grow migration + GC rekey #6801, C5a → perf(runtime): #6759 C5a — per-key vetting for the class-field inline-guard disable #6802, C3b/C3c-r → perf(runtime): #6759 C3c-r — header-stamped stable shape ids, id-keyed FIELD_CACHE, PIC ABA fix #6803
• C4: concrete goals subsumed by C1+C3a+C3c-r (rationale in docs/shape-tree-plan.md); residual formalization deferred pending profiling evidence.
• C3 codegen remainder (eager stamping + PIC id compare + shape-resident transition edges): tracked in Shape tree C3 codegen remainder: eager shape-id stamping + PIC id compare (#6759/#6798) #6804 with its own design-review gate, per the original plan.

Validation: per-PR full runtime suites (1443→1450 green up the stack); gap suite on the C2+C3a tip 98.2% / 0 new untriaged (gate OK); a post-merge gap run on main-identical content is in flight and will be recorded on #6804 as the baseline. CodeRabbit: #6800 clean; the #6801 wrap-hazard finding was already superseded by #6803's parking range allocator (noted inline).

Closing — #6804 carries the remaining work against the #6759 acceptance table.