oxide_core/

shape.rs

//! Shapes: the transition tree, dictionary mode and prototype validity cells.
//!
//! A transition shape describes one property added on top of its parent; the
//! tree has one root per `(prototype, kind)`. Lookup walks `parent` for eight
//! properties or fewer and otherwise uses a table built on first lookup.
//! Transition shapes are immutable and shared; reconfiguring a property or
//! changing the prototype replays the object's keys from another root, so the
//! slots keep their positions.
//!
//! Dictionary mode gives an object an unshared shape with its own hash table
//! and insertion-ordered entry list. It is entered on deletion, past
//! [`DICTIONARY_THRESHOLD`] properties, and always for the global object.
//!
//! Every object used as a prototype has a `PrototypeInfo`: a lazily created
//! validity cell and the list of prototype objects that inherit from it. Any
//! change to a prototype object clears its cell and, through the dependents
//! lists, every cell downstream. A shape caches its prototype's cell; the
//! prototype IC records `(holder, slot, cell)` and tests one boolean.

use std::cell::OnceCell;
use std::fmt;

use crate::heap::arena::Record;
use crate::heap::atom::{KeyKind, PropertyKey};
use crate::heap::hash::FxHashMap;
use crate::heap::object::{NONE, ObjectKind, flags};
use crate::heap::{Heap, HeapError, Need};
use crate::value::{ObjectId, ShapeId, ValidityCellId, Value};

/// Past this many properties a transition shape builds a lookup table.
pub const TABLE_THRESHOLD: u32 = 8;
/// Adding a property beyond this count moves the object to dictionary mode.
pub const DICTIONARY_THRESHOLD: u32 = 64;
/// The always-valid cell of shapes without a prototype.
pub const STATIC_CELL: ValidityCellId = ValidityCellId(0);

#[derive(Clone, Copy, PartialEq, Eq, Hash)]
pub struct PropertyFlags(u8);

impl PropertyFlags {
    pub const WRITABLE: u8 = 1 << 0;
    pub const ENUMERABLE: u8 = 1 << 1;
    pub const CONFIGURABLE: u8 = 1 << 2;
    pub const ACCESSOR: u8 = 1 << 3;
    /// A pending closure's `length`, `name` or `prototype`: the key and its
    /// attributes are in the shape, the value is not yet in a slot (see
    /// [`Heap::pending_closure_shape`]). Never read or written before the
    /// closure is materialized.
    pub const AUTOINIT: u8 = 1 << 4;
    /// Writable, enumerable, configurable data property.
    pub const DEFAULT: PropertyFlags = PropertyFlags::data(true, true, true);

    pub const fn data(writable: bool, enumerable: bool, configurable: bool) -> Self {
        PropertyFlags(
            (writable as u8 * Self::WRITABLE)
                | (enumerable as u8 * Self::ENUMERABLE)
                | (configurable as u8 * Self::CONFIGURABLE),
        )
    }

    pub const fn accessor(enumerable: bool, configurable: bool) -> Self {
        PropertyFlags(
            Self::ACCESSOR
                | (enumerable as u8 * Self::ENUMERABLE)
                | (configurable as u8 * Self::CONFIGURABLE),
        )
    }

    pub const fn bits(self) -> u8 {
        self.0
    }

    pub const fn has(self, flag: u8) -> bool {
        self.0 & flag != 0
    }

    pub const fn with(self, flag: u8) -> Self {
        PropertyFlags(self.0 | flag)
    }

    /// The slots a property with these flags occupies: two for an accessor
    /// (getter, then setter), one for a data property.
    pub const fn width(self) -> u32 {
        if self.has(Self::ACCESSOR) { 2 } else { 1 }
    }
}

impl fmt::Debug for PropertyFlags {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let flag = |bit, name| if self.has(bit) { name } else { "-" };
        write!(
            f,
            "{}{}{}{}{}",
            flag(Self::AUTOINIT, "i"),
            flag(Self::ACCESSOR, "a"),
            flag(Self::WRITABLE, "w"),
            flag(Self::ENUMERABLE, "e"),
            flag(Self::CONFIGURABLE, "c")
        )
    }
}

/// A shape's outgoing transitions: a vector for up to four entries, a map
/// beyond. Entries are weak: the collector drops those whose child died.
#[derive(Default)]
pub enum Transitions {
    #[default]
    None,
    Small(Vec<(PropertyKey, PropertyFlags, ShapeId)>),
    Map(Box<FxHashMap<(PropertyKey, PropertyFlags), ShapeId>>),
}

const SMALL_TRANSITIONS: usize = 4;

impl Transitions {
    #[inline]
    pub fn find(&self, key: PropertyKey, flags: PropertyFlags) -> Option<ShapeId> {
        match self {
            Transitions::None => None,
            Transitions::Small(entries) => entries
                .iter()
                .find(|(entry_key, entry_flags, _)| *entry_key == key && *entry_flags == flags)
                .map(|entry| entry.2),
            Transitions::Map(map) => map.get(&(key, flags)).copied(),
        }
    }

    fn insert(&mut self, key: PropertyKey, flags: PropertyFlags, child: ShapeId) {
        match self {
            Transitions::None => *self = Transitions::Small(vec![(key, flags, child)]),
            Transitions::Small(entries) if entries.len() < SMALL_TRANSITIONS => {
                entries.push((key, flags, child))
            }
            Transitions::Small(entries) => {
                let mut map: FxHashMap<_, _> =
                    entries.drain(..).map(|(k, f, c)| ((k, f), c)).collect();
                map.insert((key, flags), child);
                *self = Transitions::Map(Box::new(map));
            }
            Transitions::Map(map) => {
                map.insert((key, flags), child);
            }
        }
    }

    pub fn retain(&mut self, mut keep: impl FnMut(ShapeId) -> bool) {
        match self {
            Transitions::None => {}
            Transitions::Small(entries) => entries.retain(|entry| keep(entry.2)),
            Transitions::Map(map) => map.retain(|_, child| keep(*child)),
        }
    }

    pub fn len(&self) -> usize {
        match self {
            Transitions::None => 0,
            Transitions::Small(entries) => entries.len(),
            Transitions::Map(map) => map.len(),
        }
    }

    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct DictEntry {
    pub key: PropertyKey,
    pub flags: PropertyFlags,
    /// The value slot, or [`NONE`] for a deleted entry.
    pub slot: u32,
}

/// The unshared table of a dictionary-mode object.
#[derive(Default)]
pub struct Dictionary {
    map: FxHashMap<PropertyKey, u32>,
    entries: Vec<DictEntry>,
    free_slots: Vec<u32>,
    next_slot: u32,
}

impl Dictionary {
    fn from_entries(entries: impl IntoIterator<Item = (PropertyKey, PropertyFlags, u32)>) -> Self {
        let mut dictionary = Dictionary::default();
        for (key, flags, slot) in entries {
            dictionary.map.insert(key, dictionary.entries.len() as u32);
            dictionary.entries.push(DictEntry { key, flags, slot });
            dictionary.next_slot = dictionary.next_slot.max(slot + flags.width());
        }
        dictionary
    }

    #[inline]
    pub fn find(&self, key: PropertyKey) -> Option<(u32, PropertyFlags)> {
        let entry = &self.entries[*self.map.get(&key)? as usize];
        Some((entry.slot, entry.flags))
    }

    /// The slot the next insertion with `flags` will use. An accessor takes
    /// two fresh slots; a data property reuses a freed one first.
    fn next_slot(&self, flags: PropertyFlags) -> u32 {
        match self.free_slots.last() {
            Some(&slot) if flags.width() == 1 => slot,
            _ => self.next_slot,
        }
    }

    fn insert(&mut self, key: PropertyKey, flags: PropertyFlags) -> u32 {
        let slot = match self.free_slots.pop() {
            Some(slot) if flags.width() == 1 => slot,
            free => {
                self.free_slots.extend(free);
                self.next_slot += flags.width();
                self.next_slot - flags.width()
            }
        };
        self.map.insert(key, self.entries.len() as u32);
        self.entries.push(DictEntry { key, flags, slot });
        slot
    }

    fn remove(&mut self, key: PropertyKey) -> Option<u32> {
        let index = self.map.remove(&key)?;
        let entry = &mut self.entries[index as usize];
        let slot = entry.slot;
        entry.slot = NONE;
        self.free_slots.extend(slot..slot + entry.flags.width());
        if self.entries.len() > 16 && self.entries.len() > 2 * self.map.len() {
            self.entries.retain(|entry| entry.slot != NONE);
            for (index, entry) in self.entries.iter().enumerate() {
                self.map.insert(entry.key, index as u32);
            }
        }
        Some(slot)
    }

    /// Gives `key` new flags of a different width, keeping its place in the
    /// entry order: its old slots are freed and new ones taken. Returns the
    /// new slot.
    fn reslot(&mut self, key: PropertyKey, flags: PropertyFlags) -> Option<u32> {
        let index = *self.map.get(&key)? as usize;
        let old = self.entries[index];
        self.free_slots
            .extend(old.slot..old.slot + old.flags.width());
        let slot = match self.free_slots.pop() {
            Some(slot) if flags.width() == 1 => slot,
            free => {
                self.free_slots.extend(free);
                self.next_slot += flags.width();
                self.next_slot - flags.width()
            }
        };
        self.entries[index] = DictEntry { key, flags, slot };
        Some(slot)
    }

    fn set_flags(&mut self, key: PropertyKey, flags: PropertyFlags) -> bool {
        match self.map.get(&key) {
            Some(&index) => {
                self.entries[index as usize].flags = flags;
                true
            }
            None => false,
        }
    }

    /// Live entries in insertion order.
    pub fn entries(&self) -> impl Iterator<Item = &DictEntry> {
        self.entries.iter().filter(|entry| entry.slot != NONE)
    }

    pub fn len(&self) -> usize {
        self.map.len()
    }

    pub fn is_empty(&self) -> bool {
        self.map.is_empty()
    }

    /// Moves the present keys of `front` to the start of the insertion
    /// order, in that order; the rest keep their relative order. Slots are
    /// unchanged.
    fn reorder(&mut self, front: &[PropertyKey]) {
        let mut entries = Vec::with_capacity(self.map.len());
        for &key in front {
            if let Some(&index) = self.map.get(&key) {
                entries.push(self.entries[index as usize]);
            }
        }
        for entry in &self.entries {
            if entry.slot != NONE && !front.contains(&entry.key) {
                entries.push(*entry);
            }
        }
        self.map.clear();
        for (index, entry) in entries.iter().enumerate() {
            self.map.insert(entry.key, index as u32);
        }
        self.entries = entries;
    }
}

pub struct Shape {
    /// Transition-tree parent; `None` for roots and dictionary shapes.
    pub parent: Option<ShapeId>,
    /// The property this node adds (meaningless when `count == 0`).
    pub key: PropertyKey,
    pub flags: PropertyFlags,
    pub slot: u32,
    /// Properties up to and including this node.
    pub count: u32,
    /// Slots used up to and including this node: `count` plus one per
    /// accessor, whose getter and setter take two.
    pub width: u32,
    pub prototype: Option<ObjectId>,
    pub kind: ObjectKind,
    pub transitions: Transitions,
    /// Key → (slot, flags), built on the first lookup past
    /// [`TABLE_THRESHOLD`] properties.
    pub table: OnceCell<Box<FxHashMap<PropertyKey, (u32, PropertyFlags)>>>,
    /// The prototype's validity cell as last seen, or [`NONE`].
    pub validity: ValidityCellId,
    pub dictionary: Option<Box<Dictionary>>,
}

impl Shape {
    fn root(prototype: Option<ObjectId>, kind: ObjectKind) -> Self {
        Shape {
            parent: None,
            key: PropertyKey::index(0).unwrap(),
            flags: PropertyFlags::DEFAULT,
            slot: NONE,
            count: 0,
            width: 0,
            prototype,
            kind,
            transitions: Transitions::None,
            table: OnceCell::new(),
            validity: ValidityCellId(NONE),
            dictionary: None,
        }
    }

    pub fn is_dictionary(&self) -> bool {
        self.dictionary.is_some()
    }

    /// Whether the lookup table has been built.
    pub fn has_table(&self) -> bool {
        self.table.get().is_some()
    }
}

impl Record for Shape {
    fn vacant() -> Self {
        Shape::root(None, ObjectKind::Free)
    }
}

#[derive(Clone, Copy, Debug)]
pub struct ValidityCell {
    pub valid: bool,
}

impl Record for ValidityCell {
    fn vacant() -> Self {
        ValidityCell { valid: false }
    }
}

/// Per-prototype bookkeeping. The table holding it is weak in its key and in
/// `dependents`; the collector prunes dead objects after marking.
#[derive(Default, Debug)]
pub struct PrototypeInfo {
    pub cell: Option<ValidityCellId>,
    /// Prototype objects whose `[[Prototype]]` is this object.
    pub dependents: Vec<ObjectId>,
}

impl Heap {
    // ---- shape construction (raw: callers have passed a safepoint) ----

    #[inline]
    pub(crate) fn root_shape(&mut self, prototype: Option<ObjectId>, kind: ObjectKind) -> ShapeId {
        let key = (prototype.map_or(NONE, |p| p.0), kind);
        if let Some((cached, shape)) = self.last_root
            && cached == key
        {
            return shape;
        }
        self.root_shape_slow(prototype, kind, key)
    }

    #[inline(never)]
    fn root_shape_slow(
        &mut self,
        prototype: Option<ObjectId>,
        kind: ObjectKind,
        key: (u32, ObjectKind),
    ) -> ShapeId {
        if let Some(&shape) = self.shape_roots.get(&key) {
            self.last_root = Some((key, shape));
            return shape;
        }
        if let Some(prototype) = prototype {
            self.ensure_prototype(prototype);
        }
        let shape = ShapeId(
            self.shapes
                .alloc(Shape::root(prototype, kind), &mut self.gc.room),
        );
        self.shape_roots.insert(key, shape);
        self.last_root = Some((key, shape));
        shape
    }

    pub(crate) fn dictionary_shape(
        &mut self,
        prototype: Option<ObjectId>,
        kind: ObjectKind,
        dictionary: Dictionary,
    ) -> ShapeId {
        if let Some(prototype) = prototype {
            self.ensure_prototype(prototype);
        }
        let mut shape = Shape::root(prototype, kind);
        shape.dictionary = Some(Box::new(dictionary));
        ShapeId(self.shapes.alloc(shape, &mut self.gc.room))
    }

    fn transition(&mut self, shape: ShapeId, key: PropertyKey, flags: PropertyFlags) -> ShapeId {
        let parent = self.shapes.get(shape.0);
        if let Some(child) = parent.transitions.find(key, flags) {
            return child;
        }
        let mut child = Shape::root(parent.prototype, parent.kind);
        child.parent = Some(shape);
        child.key = key;
        child.flags = flags;
        child.slot = parent.width;
        child.count = parent.count + 1;
        child.width = parent.width + flags.width();
        let child = ShapeId(self.shapes.alloc(child, &mut self.gc.room));
        self.shapes
            .get_mut(shape.0)
            .transitions
            .insert(key, flags, child);
        child
    }

    fn build_table(&self, shape: ShapeId) -> FxHashMap<PropertyKey, (u32, PropertyFlags)> {
        let mut current = self.shapes.get(shape.0);
        let mut table = FxHashMap::default();
        table.reserve(current.count as usize);
        while current.count > 0 {
            table.insert(current.key, (current.slot, current.flags));
            current = self
                .shapes
                .get(current.parent.expect("non-root shape has a parent").0);
        }
        table
    }

    /// Looks `key` up in one shape.
    #[inline]
    pub fn shape_lookup(&self, shape: ShapeId, key: PropertyKey) -> Option<(u32, PropertyFlags)> {
        let record = self.shapes.get(shape.0);
        if let Some(dictionary) = &record.dictionary {
            return dictionary.find(key);
        }
        if record.count > TABLE_THRESHOLD {
            return record
                .table
                .get_or_init(|| Box::new(self.build_table(shape)))
                .get(&key)
                .copied();
        }
        let mut current = record;
        while current.count > 0 {
            if current.key == key {
                return Some((current.slot, current.flags));
            }
            current = self
                .shapes
                .get(current.parent.expect("non-root shape has a parent").0);
        }
        None
    }

    /// `(key, flags, slot)` of every property in insertion order.
    pub fn shape_entries(&self, shape: ShapeId) -> Vec<(PropertyKey, PropertyFlags, u32)> {
        let record = self.shapes.get(shape.0);
        if let Some(dictionary) = &record.dictionary {
            return dictionary
                .entries()
                .map(|entry| (entry.key, entry.flags, entry.slot))
                .collect();
        }
        let mut entries = Vec::with_capacity(record.count as usize);
        let mut current = record;
        while current.count > 0 {
            entries.push((current.key, current.flags, current.slot));
            current = self
                .shapes
                .get(current.parent.expect("non-root shape has a parent").0);
        }
        entries.reverse();
        entries
    }

    pub fn shape(&self, shape: ShapeId) -> &Shape {
        self.shapes.get(shape.0)
    }

    pub(crate) fn prototype_of_shape(&self, shape: ShapeId) -> Option<ObjectId> {
        self.shapes.get(shape.0).prototype
    }

    pub fn shape_of(&self, object: ObjectId) -> ShapeId {
        self.objects.get(object.0).shape
    }

    pub fn is_dictionary(&self, object: ObjectId) -> bool {
        self.objects.get(object.0).has(flags::DICTIONARY)
    }

    pub fn prototype_of(&self, object: ObjectId) -> Option<ObjectId> {
        self.shapes
            .get(self.objects.get(object.0).shape.0)
            .prototype
    }

    // ---- properties ----

    /// The slot and flags of an own named property.
    #[inline]
    pub fn lookup_own(&self, object: ObjectId, key: PropertyKey) -> Option<(u32, PropertyFlags)> {
        self.shape_lookup(self.objects.get(object.0).shape, key)
    }

    /// Whether `object` is a pending closure: a function whose shape has more
    /// slots than its range, the `AUTOINIT` entries of
    /// [`Heap::pending_closure_shape`] not yet materialized.
    #[inline(always)]
    pub fn is_pending_closure(&self, object: ObjectId) -> bool {
        let header = self.objects.get(object.0);
        header.kind == ObjectKind::Function
            && header.slots().len < self.shapes.get(header.shape.0).width
    }

    /// Gives a new closure, allocated with no slots, the shape reached from
    /// the root for its prototype by adding `entries` with the `AUTOINIT`
    /// flag: its keys and attributes without their values. Returns the shape.
    pub(crate) fn pending_closure_shape(
        &mut self,
        function: ObjectId,
        entries: &[(PropertyKey, PropertyFlags)],
    ) -> Result<ShapeId, HeapError> {
        debug_assert_eq!(self.objects.get(function.0).slots().len, 0);
        let need = Need {
            shapes: entries.len() + 1,
            ..Need::default()
        };
        self.safepoint(&need, &[Value::object(function)])?;
        let mut shape = self.root_shape(self.prototype_of(function), ObjectKind::Function);
        for &(key, flags) in entries {
            shape = self.transition(shape, key, flags.with(PropertyFlags::AUTOINIT));
        }
        self.objects.get_mut(function.0).shape = shape;
        Ok(shape)
    }

    /// Turns a pending closure into a function with a range of `count` slots
    /// and no properties, the root shape for its prototype, for its
    /// properties to be added in their pending order.
    pub(crate) fn unpend_closure(
        &mut self,
        function: ObjectId,
        count: u32,
    ) -> Result<(), HeapError> {
        debug_assert!(self.is_pending_closure(function));
        let need = Need {
            shapes: 1,
            values: [count, 0],
            ..Need::default()
        };
        self.safepoint(&need, &[Value::object(function)])?;
        let shape = self.root_shape(self.prototype_of(function), ObjectKind::Function);
        let slots = self.values.alloc_slots(count, &mut self.gc.room);
        let header = self.objects.get_mut(function.0);
        header.shape = shape;
        header.set_slots(slots);
        if header.has(flags::USED_AS_PROTOTYPE) {
            self.invalidate(function);
        }
        Ok(())
    }

    /// `values[start + slot]`: one header load, one value load.
    #[inline]
    #[track_caller]
    pub fn get_slot(&self, object: ObjectId, slot: u32) -> Value {
        let header = self.objects.get(object.0);
        debug_assert!(
            slot < header.slots().len,
            "slot {slot} outside the object's range"
        );
        self.values.get_at(header.slots_start + slot)
    }

    #[inline]
    #[track_caller]
    pub fn set_slot(&mut self, object: ObjectId, slot: u32, value: Value) {
        let header = self.objects.get(object.0);
        debug_assert!(
            slot < header.slots().len,
            "slot {slot} outside the object's range"
        );
        self.values.set_at(header.slots_start + slot, value);
    }

    /// The value of a named property, following the prototype chain.
    pub fn get_property(&self, object: ObjectId, key: PropertyKey) -> Option<Value> {
        let mut current = object;
        loop {
            if let Some((slot, _)) = self.lookup_own(current, key) {
                return Some(self.get_slot(current, slot));
            }
            current = self.prototype_of(current)?;
        }
    }

    /// Adds a new own data property. `DuplicateKey` if it already exists.
    #[inline]
    pub fn add_property(
        &mut self,
        object: ObjectId,
        key: PropertyKey,
        flags: PropertyFlags,
        value: Value,
    ) -> Result<(), HeapError> {
        debug_assert!(!flags.has(PropertyFlags::ACCESSOR), "add_accessor");
        self.add_slots(object, key, flags, [value, Value::UNDEFINED])
    }

    /// Adds a new own accessor property: `getter` and `setter` take two
    /// consecutive slots, `undefined` for an absent half. `lookup_own`
    /// reports the getter's slot.
    pub fn add_accessor(
        &mut self,
        object: ObjectId,
        key: PropertyKey,
        flags: PropertyFlags,
        getter: Value,
        setter: Value,
    ) -> Result<(), HeapError> {
        debug_assert!(flags.has(PropertyFlags::ACCESSOR));
        self.add_slots(object, key, flags, [getter, setter])
    }

    #[inline]
    fn add_slots(
        &mut self,
        object: ObjectId,
        key: PropertyKey,
        flags: PropertyFlags,
        values: [Value; 2],
    ) -> Result<(), HeapError> {
        if let KeyKind::Index(_) = key.kind() {
            self.note_prototype_index(object);
        }
        // Fast path: a known transition and free slots. A transition for
        // `key` proves the current shape lacks it (shapes are immutable), so
        // no duplicate check, and nothing is allocated.
        let header = self.objects.get(object.0);
        if !header.has(flags::DICTIONARY) {
            let slots = header.slots();
            let shape = self.shapes.get(header.shape.0);
            let width = shape.width;
            if width + flags.width() <= slots.len
                && let Some(next) = shape.transitions.find(key, flags)
            {
                let header = self.objects.get_mut(object.0);
                header.shape = next;
                let prototype = header.has(flags::USED_AS_PROTOTYPE);
                self.values.set_at(slots.start + width, values[0]);
                if flags.width() == 2 {
                    self.values.set_at(slots.start + width + 1, values[1]);
                }
                if prototype {
                    self.invalidate(object);
                }
                return Ok(());
            }
        }
        self.add_property_slow(object, key, flags, values)
    }

    #[inline(never)]
    fn add_property_slow(
        &mut self,
        object: ObjectId,
        key: PropertyKey,
        flags: PropertyFlags,
        values: [Value; 2],
    ) -> Result<(), HeapError> {
        debug_assert!(!self.is_pending_closure(object), "a pending closure");
        let header = *self.objects.get(object.0);
        if header.has(flags::DICTIONARY) {
            return self.dictionary_add(object, key, flags, values);
        }
        let shape = self.shapes.get(header.shape.0);
        let (count, width) = (shape.count, shape.width);
        let known = shape.transitions.find(key, flags);
        // A known transition proves the key is absent; otherwise check.
        if known.is_none() && self.shape_lookup(header.shape, key).is_some() {
            return Err(HeapError::DuplicateKey);
        }
        let keep = [Value::object(object), key.to_value(), values[0], values[1]];
        if count >= DICTIONARY_THRESHOLD {
            self.enter_dictionary(object, &keep[1..])?;
            return self.dictionary_add(object, key, flags, values);
        }
        let slots = header.slots();
        let needed = width + flags.width();
        let grow = needed > slots.len;
        let new_len = (slots.len * 2).max(needed).max(4);
        let collections = self.gc.stats.collections;
        if grow || known.is_none() {
            let need = Need {
                shapes: 1,
                values: [if grow { new_len } else { 0 }, 0],
                ..Need::default()
            };
            self.safepoint(&need, &keep)?;
        }
        // The object was rooted, so its shape and ranges are unchanged. A
        // known child is reused only if no collection ran: it is reachable
        // only through the weak transition and may have died.
        let next = match known {
            Some(child) if self.gc.stats.collections == collections => child,
            _ => self.transition(header.shape, key, flags),
        };
        let mut slots = slots;
        if grow {
            slots = self.values.grow_slots(slots, new_len, &mut self.gc.room);
        }
        let header = self.objects.get_mut(object.0);
        header.shape = next;
        header.set_slots(slots);
        let prototype = header.has(flags::USED_AS_PROTOTYPE);
        self.values.set(slots, width, values[0]);
        if flags.width() == 2 {
            self.values.set(slots, width + 1, values[1]);
        }
        if prototype {
            self.invalidate(object);
        }
        Ok(())
    }

    fn dictionary_add(
        &mut self,
        object: ObjectId,
        key: PropertyKey,
        flags: PropertyFlags,
        values: [Value; 2],
    ) -> Result<(), HeapError> {
        let header = *self.objects.get(object.0);
        let dictionary = self
            .shapes
            .get(header.shape.0)
            .dictionary
            .as_deref()
            .expect("dictionary shape");
        if dictionary.find(key).is_some() {
            return Err(HeapError::DuplicateKey);
        }
        let slot = dictionary.next_slot(flags);
        let end = slot + flags.width();
        let mut slots = header.slots();
        if end > slots.len {
            let new_len = (slots.len * 2).max(end).max(4);
            let need = Need {
                values: [new_len, 0],
                ..Need::default()
            };
            let keep = [Value::object(object), key.to_value(), values[0], values[1]];
            self.safepoint(&need, &keep)?;
            slots = self.values.grow_slots(slots, new_len, &mut self.gc.room);
            self.objects.get_mut(object.0).set_slots(slots);
        }
        let dictionary = self
            .shapes
            .get_mut(header.shape.0)
            .dictionary
            .as_deref_mut()
            .expect("dictionary shape");
        let used = dictionary.insert(key, flags);
        debug_assert_eq!(used, slot);
        self.values.set(slots, slot, values[0]);
        if flags.width() == 2 {
            self.values.set(slots, slot + 1, values[1]);
        }
        self.dictionary_changed(object);
        if header.has(flags::USED_AS_PROTOTYPE) {
            self.invalidate(object);
        }
        Ok(())
    }

    /// Bumps the global generation when `object` is the global object: an
    /// insert, remove or reflag of its dictionary moves a slot or a flag that a
    /// global cache entry may hold.
    #[inline]
    fn dictionary_changed(&mut self, object: ObjectId) {
        if self.objects.get(object.0).kind == ObjectKind::GlobalObject {
            self.bump_global_generation();
        }
    }

    /// Moves `object` to an unshared dictionary shape. `keep` are extra values
    /// to root across the allocation.
    pub(crate) fn enter_dictionary(
        &mut self,
        object: ObjectId,
        keep: &[Value],
    ) -> Result<(), HeapError> {
        debug_assert!(!self.is_pending_closure(object), "a pending closure");
        let mut roots = vec![Value::object(object)];
        roots.extend_from_slice(keep);
        self.safepoint(
            &Need {
                shapes: 1,
                ..Need::default()
            },
            &roots,
        )?;
        let header = *self.objects.get(object.0);
        let shape = self.shapes.get(header.shape.0);
        let (prototype, kind) = (shape.prototype, shape.kind);
        let dictionary = Dictionary::from_entries(self.shape_entries(header.shape));
        let shape = self.dictionary_shape(prototype, kind, dictionary);
        let header = self.objects.get_mut(object.0);
        header.shape = shape;
        header.flags |= flags::DICTIONARY;
        Ok(())
    }

    /// Moves the own properties `front` names to the start of a dictionary
    /// object's key order, in that order (realm setup: the global object's
    /// order is QuickJS's, not the install order). Values keep their slots.
    pub fn reorder_dictionary(&mut self, object: ObjectId, front: &[PropertyKey]) {
        let header = *self.objects.get(object.0);
        debug_assert!(header.has(flags::DICTIONARY), "a dictionary object");
        if let Some(dictionary) = self
            .shapes
            .get_mut(header.shape.0)
            .dictionary
            .as_deref_mut()
        {
            dictionary.reorder(front);
            self.dictionary_changed(object);
        }
    }

    /// Deletes an own property; returns whether it existed. The object enters
    /// dictionary mode.
    pub fn delete_property(
        &mut self,
        object: ObjectId,
        key: PropertyKey,
    ) -> Result<bool, HeapError> {
        if self.lookup_own(object, key).is_none() {
            return Ok(false);
        }
        if !self.is_dictionary(object) {
            self.enter_dictionary(object, &[])?;
        }
        let header = *self.objects.get(object.0);
        let dictionary = self
            .shapes
            .get_mut(header.shape.0)
            .dictionary
            .as_deref_mut()
            .expect("dictionary shape");
        let (_, flags) = dictionary.find(key).expect("present key");
        let slot = dictionary.remove(key).expect("present key");
        for slot in slot..slot + flags.width() {
            self.values.set(header.slots(), slot, Value::EMPTY);
        }
        self.dictionary_changed(object);
        if header.has(flags::USED_AS_PROTOTYPE) {
            self.invalidate(object);
        }
        Ok(true)
    }

    /// Changes the flags of an own property, keeping its slot. Returns whether
    /// the property exists.
    pub fn set_property_flags(
        &mut self,
        object: ObjectId,
        key: PropertyKey,
        flags: PropertyFlags,
    ) -> Result<bool, HeapError> {
        let Some((_, old)) = self.lookup_own(object, key) else {
            return Ok(false);
        };
        if old == flags {
            return Ok(true);
        }
        debug_assert!(!self.is_pending_closure(object), "a pending closure");
        debug_assert_eq!(old.width(), flags.width(), "a data/accessor change");
        let header = *self.objects.get(object.0);
        if header.has(flags::DICTIONARY) {
            let dictionary = self
                .shapes
                .get_mut(header.shape.0)
                .dictionary
                .as_deref_mut()
                .expect("dictionary shape");
            dictionary.set_flags(key, flags);
            self.dictionary_changed(object);
        } else {
            let mut entries = self.shape_entries(header.shape);
            for entry in &mut entries {
                if entry.0 == key {
                    entry.1 = flags;
                }
            }
            let prototype = self.prototype_of(object);
            self.replay_shape(object, prototype, &entries)?;
        }
        if header.has(flags::USED_AS_PROTOTYPE) {
            self.invalidate(object);
        }
        Ok(true)
    }

    /// Replaces an own property's flags and values, keeping its place in the
    /// key order. A change between data and accessor moves the object to
    /// dictionary mode. `values` are rooted for the call.
    pub fn reshape_property(
        &mut self,
        object: ObjectId,
        key: PropertyKey,
        flags: PropertyFlags,
        values: [Value; 2],
    ) -> Result<(), HeapError> {
        let (_, old) = self.lookup_own(object, key).expect("an own property");
        let mark = self.roots.stack.mark();
        self.roots.stack.push(values[0]);
        self.roots.stack.push(values[1]);
        let result = (|| {
            if old.width() == flags.width() {
                self.set_property_flags(object, key, flags)?;
            } else {
                if !self.is_dictionary(object) {
                    self.enter_dictionary(object, &[])?;
                }
                let header = *self.objects.get(object.0);
                let dictionary = self
                    .shapes
                    .get_mut(header.shape.0)
                    .dictionary
                    .as_deref_mut()
                    .expect("dictionary shape");
                let slot = dictionary.reslot(key, flags).expect("present key");
                let end = slot + flags.width();
                let slots = header.slots();
                if end > slots.len {
                    let new_len = (slots.len * 2).max(end).max(4);
                    self.safepoint(
                        &Need {
                            values: [new_len, 0],
                            ..Need::default()
                        },
                        &[Value::object(object)],
                    )?;
                    let slots = self.values.grow_slots(slots, new_len, &mut self.gc.room);
                    self.objects.get_mut(object.0).set_slots(slots);
                }
                self.dictionary_changed(object);
                if header.has(flags::USED_AS_PROTOTYPE) {
                    self.invalidate(object);
                }
            }
            let (slot, _) = self.lookup_own(object, key).expect("an own property");
            self.set_slot(object, slot, values[0]);
            if flags.width() == 2 {
                self.set_slot(object, slot + 1, values[1]);
            }
            Ok(())
        })();
        self.roots.stack.truncate(mark);
        result
    }

    /// Gives a transition-tree object the shape reached from the root for
    /// `(prototype, kind)` by adding `entries` in order. Slots keep their
    /// positions.
    fn replay_shape(
        &mut self,
        object: ObjectId,
        prototype: Option<ObjectId>,
        entries: &[(PropertyKey, PropertyFlags, u32)],
    ) -> Result<(), HeapError> {
        let need = Need {
            shapes: entries.len() + 1,
            ..Need::default()
        };
        let proto_value = prototype.map_or(Value::UNDEFINED, Value::object);
        self.safepoint(&need, &[Value::object(object), proto_value])?;
        let kind = self.shapes.get(self.objects.get(object.0).shape.0).kind;
        let mut shape = self.root_shape(prototype, kind);
        for &(key, flags, slot) in entries {
            debug_assert_eq!(slot, self.shapes.get(shape.0).width);
            shape = self.transition(shape, key, flags);
        }
        self.objects.get_mut(object.0).shape = shape;
        Ok(())
    }

    /// Sets `[[Prototype]]`. `PrototypeCycle` if `prototype` inherits from
    /// `object`.
    pub fn set_prototype(
        &mut self,
        object: ObjectId,
        prototype: Option<ObjectId>,
    ) -> Result<(), HeapError> {
        let old = self.prototype_of(object);
        if old == prototype {
            return Ok(());
        }
        let mut walk = prototype;
        while let Some(current) = walk {
            if current == object {
                return Err(HeapError::PrototypeCycle);
            }
            walk = self.prototype_of(current);
        }
        let header = *self.objects.get(object.0);
        if header.has(flags::DICTIONARY) {
            if let Some(prototype) = prototype {
                self.ensure_prototype(prototype);
            }
            let shape = self.shapes.get_mut(header.shape.0);
            shape.prototype = prototype;
            shape.validity = ValidityCellId(NONE);
        } else {
            let entries = self.shape_entries(header.shape);
            self.replay_shape(object, prototype, &entries)?;
        }
        if header.has(flags::USED_AS_PROTOTYPE) {
            if let Some(old) = old
                && let Some(info) = self.prototypes.get_mut(&old)
            {
                info.dependents.retain(|&dependent| dependent != object);
            }
            if let Some(new) = prototype {
                self.prototypes
                    .entry(new)
                    .or_default()
                    .dependents
                    .push(object);
            }
            self.invalidate(object);
        }
        Ok(())
    }

    /// Own keys in `[[OwnPropertyKeys]]` order: array indices ascending
    /// (elements and named), then strings, then symbols, each in insertion
    /// order. Private names are hidden.
    pub fn own_keys(&self, object: ObjectId) -> Vec<PropertyKey> {
        let header = self.objects.get(object.0);
        let mut indices = Vec::new();
        let elements = header.elements();
        let element_count = if header.kind == ObjectKind::Array {
            header.payload.min(elements.len)
        } else {
            elements.len
        };
        for index in 0..element_count {
            if !self.values.get(elements, index).is_empty()
                && let Some(key) = PropertyKey::index(index)
            {
                indices.push((index, key));
            }
        }
        let mut strings = Vec::new();
        let mut symbols = Vec::new();
        for (key, _, _) in self.shape_entries(header.shape) {
            match key.kind() {
                KeyKind::Index(index) => indices.push((index, key)),
                KeyKind::String(id) => match self.strings.get(id.0).array_index {
                    NONE => strings.push(key),
                    index => indices.push((index, key)),
                },
                KeyKind::Symbol(id) => {
                    if !self.symbols.get(id.0).private {
                        symbols.push(key);
                    }
                }
            }
        }
        indices.sort_by_key(|&(index, _)| index);
        indices
            .into_iter()
            .map(|(_, key)| key)
            .chain(strings)
            .chain(symbols)
            .collect()
    }

    /// Whether `object` has an element or a named property with an index
    /// key.
    fn has_index_property(&self, object: ObjectId) -> bool {
        let header = self.objects.get(object.0);
        let elements = header.elements();
        if self
            .values
            .slice(elements)
            .iter()
            .any(|value| !value.is_empty())
        {
            return true;
        }
        self.shape_entries(header.shape)
            .iter()
            .any(|(key, _, _)| match key.kind() {
                KeyKind::Index(_) => true,
                KeyKind::String(id) => self.strings.get(id.0).array_index != NONE,
                KeyKind::Symbol(_) => false,
            })
    }

    // ---- prototypes and validity cells ----

    /// Flags `prototype` as used as a prototype and registers it with its own
    /// prototype's dependents, up the chain.
    pub(crate) fn ensure_prototype(&mut self, prototype: ObjectId) {
        let header = self.objects.get_mut(prototype.0);
        if header.has(flags::USED_AS_PROTOTYPE) {
            return;
        }
        header.flags |= flags::USED_AS_PROTOTYPE;
        let kind = header.kind;
        if self.holes_writable
            && (kind.is_exotic()
                || matches!(kind, ObjectKind::Arguments)
                || self.has_index_property(prototype))
        {
            self.holes_writable = false;
        }
        self.prototypes.entry(prototype).or_default();
        if let Some(parent) = self.prototype_of(prototype) {
            self.ensure_prototype(parent);
            self.prototypes
                .entry(parent)
                .or_default()
                .dependents
                .push(prototype);
        }
    }

    /// Clears the validity cell of `object` and of every prototype object that
    /// inherits from it.
    pub(crate) fn invalidate(&mut self, object: ObjectId) {
        let mut work = vec![object];
        while let Some(current) = work.pop() {
            if let Some(info) = self.prototypes.get_mut(&current) {
                if let Some(cell) = info.cell.take() {
                    self.cells.get_mut(cell.0).valid = false;
                }
                work.extend_from_slice(&info.dependents);
            }
        }
    }

    /// The cell guarding `object`'s prototype chain: valid until any object on
    /// that chain changes. Allocates a fresh cell after an invalidation.
    pub fn validity_cell(&mut self, object: ObjectId) -> Result<ValidityCellId, HeapError> {
        let shape_id = self.objects.get(object.0).shape;
        let shape = self.shapes.get(shape_id.0);
        let Some(prototype) = shape.prototype else {
            return Ok(STATIC_CELL);
        };
        if shape.validity.0 != NONE && self.cells.get(shape.validity.0).valid {
            return Ok(shape.validity);
        }
        let cell = self.chain_cell_keeping(prototype, Value::object(object))?;
        // The object was rooted, so its shape is unchanged.
        self.shapes.get_mut(shape_id.0).validity = cell;
        Ok(cell)
    }

    /// The cell guarding the chain that starts at `prototype`: valid until
    /// `prototype` or any object above it changes. It is the cell
    /// [`Heap::validity_cell`] gives an object whose prototype is `prototype`;
    /// the string-receiver cache uses it for `%String.prototype%`, which no
    /// object inherits from.
    pub fn chain_cell(&mut self, prototype: ObjectId) -> Result<ValidityCellId, HeapError> {
        self.chain_cell_keeping(prototype, Value::UNDEFINED)
    }

    fn chain_cell_keeping(
        &mut self,
        prototype: ObjectId,
        keep: Value,
    ) -> Result<ValidityCellId, HeapError> {
        self.ensure_prototype(prototype);
        if let Some(cell) = self.prototypes.get(&prototype).and_then(|info| info.cell) {
            return Ok(cell);
        }
        self.safepoint(
            &Need {
                cells: 1,
                ..Need::default()
            },
            &[Value::object(prototype), keep],
        )?;
        let cell = ValidityCellId(
            self.cells
                .alloc(ValidityCell { valid: true }, &mut self.gc.room),
        );
        self.prototypes.entry(prototype).or_default().cell = Some(cell);
        Ok(cell)
    }

    #[inline]
    pub fn cell_is_valid(&self, cell: ValidityCellId) -> bool {
        self.cells.get(cell.0).valid
    }
}