Object shapes (hidden classes): design + phased migration plan

Status: IMPLEMENTED (2026-07-12) — Phases 0–3 landed on this branch; every phase gated on the full test262 language+built-ins baseline with zero regressions (47,291 tests). See §6.5 for the deltas between this design and what actually landed (slots hold whole Property values so attribute edges never demote; transition edges are Weak; the per-shape index is an FxIndexMap for Equivalent-probe parity).

Original design note (2026-07-06): this answers the question js-performance-roadmap.md §3.7 deferred — "revisit with fresh callgrind data; if get_index_of still dominates property-heavy code, shapes are the next step" — with fresh data, and it comes to a more nuanced conclusion: hashing is no longer the headline cost; per-object construction is. Shapes are still the right structural answer, but their value here is structure sharing (allocation + key interning + enumeration for free) more than lookup acceleration, and the phasing below is chosen accordingly.

The three invariants are unchanged: zero unsafe, no new heavyweight dependencies, byte-identical deterministic replay. Shapes are derived purely from insertion order and property attributes, are never serialized, and never influence observable enumeration order — the determinism story is identical to the inline caches'.

1. Fresh data (callgrind, 2026-07-06, current branch head)

json_roundtrip (20k stringify+parse round-trips of a 5-key record with nested objects/arrays), 1.20 G instructions total:

Two conclusions:

1. The kernel tier already ate the lookup problem where it matters. Monomorphic property loops (property_access) run as register programs with entry-resolved slots (kernel prop localization); get_index_of no longer dominates any loop-shaped workload. What's left of it lives in cold structure — one lookup per key per object during parse/stringify, IC-verified interpreter accesses outside loops.
2. Construction is the bottleneck shapes actually fix. Every JSON.parse object allocates its own hash table and (until the Phase-0 interning below) its own copies of key strings that every sibling record spells identically; every {x, y} literal in a loop does the same. Structure sharing turns "N same-shape objects" into "one shared shape + N slot vectors."

Phase 0 (landed with this doc): interning parse keys by source slice cut ~4% of json_roundtrip — confirming keys were a real but minor slice, and that the per-object table churn is the dominant remainder.

2. Current model, and what 309 touch points mean

ObjectData today:

pub struct ObjectData {
    pub props: FxIndexMap<PropertyKey, Property>, // insertion-ordered
    pub internal: Internal,                       // exotic payloads
    pub proto: Option<JsObject>,
    pub extensible: bool,
}

props is public and directly manipulated at 309 sites across the engine (.props field accesses: gets, get_full/get_index[_mut], inserts, shift_remove, iteration, contains_key). The inline caches and the kernel prop machinery both already exploit IndexMap's stable insertion-order slot indices — that is, the engine has organically grown half a shape system: slot-indexed access with identity verified per use. What's missing is the sharable identity (one pointer comparison instead of key equality checks) and the shared storage (no per-object table).

A big-bang replacement of props is therefore not the plan. The plan is to make the existing map cheap to have for shaped objects, by splitting the key→slot index (shared, in the shape) from the slot values (per-object).

3. Design

3.1 Representation

/// One node in the shape tree. Immutable once created; shared via Rc.
pub struct Shape {
    /// Parent shape (None = the empty root for a given birth proto).
    parent: Option<Rc<Shape>>,
    /// The property this node appends to the parent, and its attributes.
    /// Attribute CHANGES (defineProperty) demote to dictionary mode rather
    /// than fork attribute-variant shape chains (rare; keeps the tree small).
    key: PropertyKey,
    enumerable: bool,
    // writable/configurable: shaped properties are always plain data
    // properties with default attributes; anything else demotes (§3.4).
    /// Slot index of `key` in the owning object's slot vector (== depth-1).
    slot: u32,
    /// key → child shape for the next appended property.
    /// Lazily allocated; most shapes have 0 or 1 transition.
    transitions: RefCell<FxHashMap<PropertyKey, Rc<Shape>>>,
    /// key → slot for O(1) lookup once the chain grows past a threshold;
    /// below it, lookup walks the parent chain (shorter than a hash for the
    /// 2-5 key objects that dominate real code). Built lazily per shape.
    index: OnceCell<FxHashMap<PropertyKey, u32>>,
}

Object storage becomes an enum behind accessors:

pub enum PropStorage {
    /// Plain data properties with default attributes, insertion-ordered:
    /// the shape holds the keys, `slots[i]` holds the value for the
    /// property at chain depth i.
    Shaped { shape: Rc<Shape>, slots: Vec<Value> },
    /// Everything else: accessors, non-default attributes, deleted keys,
    /// symbol-keyed exotics mid-mutation — today's map, verbatim.
    Dict(FxIndexMap<PropertyKey, Property>),
}

3.2 Invariants

• Enumeration order is insertion order in both modes (shape chain order == insertion order by construction; spec integer-key ordering is applied at enumeration time exactly as today). Mode is unobservable.
• Replay determinism: shapes are derived from program behavior only (keys, insertion order, attribute operations). No addresses, no RNG. The transition tree is per-Vm (rooted in Realm), so cross-realm sharing never happens and identity checks stay realm-local — same policy as the proto-identity ICs.
• A shaped object's slot indices are stable for its lifetime in that shape — append-only transitions; any destructive change demotes.

3.3 Fast paths enabled

• Construction: object literals compile to "reserve slots, walk the transition chain once per site" — after warm-up the chain walk is N pointer hops with no hashing and ONE allocation (the slot vec). JSON.parse gets the same via a per-parser cursor cache: record shapes repeat, so each record after the first is Vec::with_capacity(n) + n value writes.
• ICs: today's key-verified ICs upgrade to (shape ptr, slot) — verification is one Rc::ptr_eq instead of a key compare + map probe. Misses re-resolve exactly as now; no invalidation protocol is added (same "verify on every use" discipline).
• Kernel prop localization: entry resolution becomes a shape-chain walk (or index probe) instead of get_full; the per-activation invariants are unchanged. Slot vec replaces get_index_mut in the write-back.
• own_keys/stringify: the key list is the shape chain — no per-object key cloning for the common all-enumerable case.

3.4 Demotion (dictionary mode) triggers

delete, defineProperty with any non-default attribute or accessor, preventExtensions/seal/freeze (reify then mark), index-keyed properties on non-arrays past a small bound, and proto mutation do NOT demote (shape is keyed by birth proto only for the root; proto lives on ObjectData as today and IC/kernel guards already verify it). Demotion materializes the map from the chain once; objects never re-promote.

3.5 What does NOT change

• Internal exotics (arrays' dense storage, typed arrays, proxies) — all already bypass props on their fast paths.
• The array kernel ops, dense-element machinery, prototype-chain guards.
• The journal/replay surface: nothing shape-related is recorded.

4. Phased migration (each phase gates test262 language+built-ins)

1. Phase 0 — parse-key interning (landed with this doc): JSON object keys interned by source slice; ~4% on json_roundtrip, zero structural risk.
2. Phase 1 — accessor extraction: replace direct .props field access with a narrow ObjectData API (own_get, own_get_full, own_insert, own_remove, own_iter, own_index/get_index_mut for the IC/kernel paths). Pure mechanical refactor of the 309 sites, zero behavior change, landable in slices. This is the bulk of the diff and de-risks everything after it.
3. Phase 2 — PropStorage behind the API: introduce the enum with Dict as the only constructor (still zero behavior change), then flip plain-object birth to Shaped with demotion triggers per §3.4. Differential coverage: the kernels corpus + a new shapes-focused corpus (delete/defineProperty/freeze mid-loop, enumeration order, proxies).
4. Phase 3 — consumers: IC upgrade to (shape, slot); kernel prop entry resolution via shape; literal-site transition caching; JSON.parse record-shape cursor; stringify keys-from-shape.
5. Phase 4 — measurement + demotion tuning: re-profile json/closures/ property-heavy workloads; tune the chain-walk vs index threshold and the literal-site cache.

Expected wins (from the profile shares): json_roundtrip construction+lookup slices total ~35% of its instructions today; shapes address most of the map/key allocation and hashing within it — a 1.3–1.6× on json is realistic, plus across-the-board gains on object-literal-heavy code (closures workload allocates a record per iteration) and colder property access.

5. Risks and mitigations

• The 309-site refactor is where mistakes hide. Mitigation: Phase 1 is semantically inert and mechanical; land it in reviewable slices, each gated on the full test262 baseline (the gate caught two real bugs during the kernel work on this branch; it is the effective spec oracle).
• Engines grow their worst bugs in transitions (delete, redefinition, proto swaps). Mitigation: demote on every destructive edge — the dictionary path IS today's battle-tested code; shapes only ever serve the append-only common case.
• Memory: transition trees can retain dead shapes. Per-Vm rooting + the existing cycle collector's registry covers reclamation at quiescence; shapes hold no Values, only keys.
• u128 liveness / slot bounds: slot vecs cap at the same bound as dictionary properties today (no new limit).

6.5 Implementation deltas (what actually landed, 2026-07-12)

The landed implementation follows §3–§4 with four refinements, each chosen to shrink the correctness surface rather than to chase speed:

1. Slots hold whole Property values (Shaped { shape, slots: Vec<Property> }), not bare Values, and the shape does NOT carry an enumerable bit. The shape therefore encodes exactly one thing — the insertion-ordered key list — and every attribute/kind mutation (defineProperty with any attributes, accessors, seal/freeze) works identically in both modes with NO demotion. The §3.4 demotion set shrinks to the order-destroying edges only: delete of a present key, and integer-index keys past a small bound (8). This also let the Phase-1 accessor API keep IndexMap-shaped signatures (&Property/&mut Property, 3-tuple get_full), which is what made the ~340-site refactor mechanical. The cost is size_of::<Property>() per slot instead of size_of::<Value>() — the allocation-count win (one slot vec vs. a per-object IndexMap + key strings) is unchanged.
2. Transition edges are Weak (transitions: RefCell<FxHashMap<PropertyKey, Weak<Shape>>>); the child holds its parent strongly. The §3.1 sketch's strong child edges would form parent↔child Rc cycles that the reference-counting GC can never reclaim. With weak edges a shape subtree dies with its last object / cache entry, and a later transition simply rebuilds the node — no registry, no §5 quiescence sweep needed.
3. The per-shape index is an FxIndexMap<PropertyKey, u32> (not a plain FxHashMap) so it accepts the same Equivalent<PropertyKey> probes (StrKeyRef) as the dictionary path.
4. ICs hold Rc<Shape> strongly in the new IcEntry::{own_shape, proto_shape} fields — one small key chain pinned per monomorphic site, in exchange for upgrade-free verification. The JSON.parse cursor is a per-nesting-depth path (Vec<Rc<Shape>> per depth) so nested records don't clobber their parent's cursor mid-object.

Measured (callgrind instruction counts, examples/shapebench, vs the fork point efb16a0): object_literals −19%, mixed_helpers −5.8%, for-in over per-iteration records −3.8%, JSON.parse −1.9%, json_roundtrip −0.8%, JSON.stringify +1.7% — of which ~+0.5M instructions in every workload is one-time realm setup (intrinsic container objects now mint shape chains; ≈0.15 ms per Engine::new, and two rounds of tuning already halved it twice: an inline single-entry transition slot, and two-touch arming of the per-shape key index so grow-by-insert singletons never pay O(n²) index builds). The §4 1.3–1.6× json estimate did NOT materialize on this corpus: with Phase-0 interning and the pre-reserved parse maps already landed, per-record construction was a smaller slice of json_roundtrip than the 2026-07-06 table suggested, and stringify/parse inherent work dominates. The structural wins concentrate where construction actually dominates (object literals in loops, record-processing helpers).

Phase-4 items still open: stringify-from-shape (serializing slots directly for all-plain-data records — deliberately skipped because the spec's per-key re-lookup during serialization is observable under mutating toJSON), and shrinking the residual realm-setup delta if Engine::new latency ever matters.

6. Relationship to register bytecode (§3.5 of the roadmap)

Independent. Register bytecode removes interpreter dispatch/operand-stack costs; shapes remove per-object storage costs. The kernel tier's typed-slot experience (entry-resolved indices, verify-per-use, decline-to-generic) is the proven pattern both reuse. Shapes first: they also make the register-bytecode ICs cheaper when that lands.