cranpose_core/

subcompose.rs

//! State tracking for measure-time subcomposition.
//!
//! The [`SubcomposeState`] keeps book of which slots are active, which nodes can
//! be reused, and which precompositions need to be disposed. Reuse follows a
//! two-phase lookup: first [`SlotId`]s that match exactly are preferred. If no
//! exact match exists, the [`SlotReusePolicy`] is consulted to determine whether
//! a node produced for another slot is compatible with the requested slot.

use std::{any::Any, collections::VecDeque, fmt, rc::Rc};

use smallvec::SmallVec;

use crate::{
    CallbackHolder, NodeId, RecomposeScope, SlotTable, SlotsHost,
    collections::map::{HashMap, HashSet},
};

/// One group of a slot table, for debugging: the group index, its call site key, its scope id and
/// the length of its subtree.
pub type DebugSlotGroup = (usize, crate::Key, Option<usize>, usize);

/// Identifier for a subcomposed slot.
///
/// This mirrors the `slotId` concept in Jetpack Compose where callers provide
/// stable identifiers for reusable children during measure-time composition.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct SlotId(pub u64);

impl SlotId {
    /// Creates a slot id from `raw`.
    #[inline]
    pub fn new(raw: u64) -> Self {
        Self(raw)
    }

    /// Returns the identifier as a number.
    #[inline]
    pub fn raw(self) -> u64 {
        self.0
    }
}

/// Policy that decides which previously composed slots should be retained for
/// potential reuse during the next subcompose pass.
///
/// Note: This trait does NOT require Send + Sync because the compose runtime
/// is single-threaded (uses Rc/RefCell throughout).
pub trait SlotReusePolicy: 'static {
    /// Returns the subset of slots that should be retained for reuse after the
    /// current measurement pass. Slots that are not part of the returned set
    /// will be disposed.
    fn get_slots_to_retain(&self, active: &[SlotId]) -> HashSet<SlotId>;

    /// Determines whether a node that previously rendered the slot `existing`
    /// can be reused when the caller requests `requested`.
    ///
    /// Implementations should document what constitutes compatibility (for
    /// example, identical slot identifiers, matching layout classes, or node
    /// types). Returning `true` allows [`SubcomposeState`] to move the node
    /// across slots instead of disposing it.
    fn are_compatible(&self, existing: SlotId, requested: SlotId) -> bool;

    /// Registers the content type for a slot.
    ///
    /// Policies that support content-type-based reuse (like [`ContentTypeReusePolicy`])
    /// should override this to record the type. The default implementation is a no-op.
    ///
    /// Call this before subcomposing an item to enable content-type-aware slot reuse.
    fn register_content_type(&self, _slot_id: SlotId, _content_type: u64) {}

    /// Removes the content type for a slot (e.g., when transitioning to None).
    ///
    /// Policies that track content types should override this to clean up.
    /// The default implementation is a no-op.
    fn remove_content_type(&self, _slot_id: SlotId) {}
}

/// Default reuse policy that mirrors Jetpack Compose behaviour: dispose
/// everything from the tail so that the next measurement can decide which
/// content to keep alive. Compatibility defaults to exact slot matches.
#[derive(Debug, Default)]
pub struct DefaultSlotReusePolicy;

impl SlotReusePolicy for DefaultSlotReusePolicy {
    fn get_slots_to_retain(&self, active: &[SlotId]) -> HashSet<SlotId> {
        let _ = active;
        HashSet::default()
    }

    fn are_compatible(&self, existing: SlotId, requested: SlotId) -> bool {
        existing == requested
    }
}

/// Reuse policy that allows cross-slot reuse when content types match.
///
/// This policy enables efficient recycling of layout nodes across different
/// slot IDs when they share the same content type (e.g., list items with
/// similar structure but different data).
///
/// # Example
///
/// ```rust,ignore
/// use cranpose_core::{ContentTypeReusePolicy, SubcomposeState, SlotId};
///
/// let mut policy = ContentTypeReusePolicy::new();
///
/// // Register content types for slots
/// policy.set_content_type(SlotId::new(0), 1); // Header type
/// policy.set_content_type(SlotId::new(1), 2); // Item type
/// policy.set_content_type(SlotId::new(2), 2); // Item type (same as slot 1)
///
/// // Slot 1 can reuse slot 2's node since they share content type 2
/// assert!(policy.are_compatible(SlotId::new(2), SlotId::new(1)));
/// ```
pub struct ContentTypeReusePolicy {
    slot_types: std::cell::RefCell<HashMap<SlotId, u64>>,
}

impl std::fmt::Debug for ContentTypeReusePolicy {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let types = self.slot_types.borrow();
        f.debug_struct("ContentTypeReusePolicy")
            .field("slot_types", &*types)
            .finish()
    }
}

impl Default for ContentTypeReusePolicy {
    fn default() -> Self {
        Self::new()
    }
}

impl ContentTypeReusePolicy {
    /// Creates a new content-type-aware reuse policy.
    pub fn new() -> Self {
        Self {
            slot_types: std::cell::RefCell::new(HashMap::default()),
        }
    }

    /// Registers the content type for a slot.
    ///
    /// Call this when subcomposing an item with a known content type.
    pub fn set_content_type(&self, slot: SlotId, content_type: u64) {
        self.slot_types.borrow_mut().insert(slot, content_type);
    }

    /// Removes the content type for a slot (e.g., when disposed).
    pub fn remove_content_type(&self, slot: SlotId) {
        self.slot_types.borrow_mut().remove(&slot);
    }

    /// Clears all registered content types.
    pub fn clear(&self) {
        self.slot_types.borrow_mut().clear();
    }

    /// Returns the content type for a slot, if registered.
    pub fn get_content_type(&self, slot: SlotId) -> Option<u64> {
        self.slot_types.borrow().get(&slot).copied()
    }
}

impl SlotReusePolicy for ContentTypeReusePolicy {
    fn get_slots_to_retain(&self, active: &[SlotId]) -> HashSet<SlotId> {
        let _ = active;
        HashSet::default()
    }

    fn are_compatible(&self, existing: SlotId, requested: SlotId) -> bool {
        if existing == requested {
            return true;
        }

        let types = self.slot_types.borrow();
        match (types.get(&existing), types.get(&requested)) {
            (Some(existing_type), Some(requested_type)) => existing_type == requested_type,
            (None, None) => true,
            _ => false,
        }
    }

    fn register_content_type(&self, slot_id: SlotId, content_type: u64) {
        self.set_content_type(slot_id, content_type);
    }

    fn remove_content_type(&self, slot_id: SlotId) {
        ContentTypeReusePolicy::remove_content_type(self, slot_id);
    }
}

#[doc(hidden)]
pub struct ExactSlotActivation<'a> {
    pub nodes: &'a [NodeId],
    pub was_recycled: bool,
}

/// Evicted roots and the slot state that stays alive until their nodes are disposed.
/// Pass this batch to [`crate::Composer::dispose_subcomposed_nodes`].
#[derive(Default)]
pub struct SubcomposeDisposal {
    pub(crate) nodes: Vec<NodeId>,
    pub(crate) slot_hosts: Vec<Rc<SlotsHost>>,
}

impl SubcomposeDisposal {
    /// Returns the roots awaiting disposal.
    ///
    /// ```
    /// use cranpose_core::SubcomposeState;
    /// let mut state = SubcomposeState::default();
    /// let disposed = state.finish_pass();
    /// assert!(disposed.nodes().is_empty());
    /// ```
    pub fn nodes(&self) -> &[NodeId] {
        &self.nodes
    }

    fn append(&mut self, mut other: Self) {
        self.nodes.append(&mut other.nodes);
        self.slot_hosts.append(&mut other.slot_hosts);
    }
}

#[derive(Default, Clone)]

struct NodeSlotMapping {
    slot_to_nodes: HashMap<SlotId, Vec<NodeId>>,
    node_to_slot: HashMap<NodeId, SlotId>,
    slot_to_scopes: HashMap<SlotId, Vec<RecomposeScope>>,
}

impl fmt::Debug for NodeSlotMapping {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("NodeSlotMapping")
            .field("slot_to_nodes", &self.slot_to_nodes)
            .field("node_to_slot", &self.node_to_slot)
            .finish()
    }
}

impl NodeSlotMapping {
    fn set_nodes(&mut self, slot: SlotId, nodes: &[NodeId]) {
        self.slot_to_nodes.insert(slot, nodes.to_vec());
        for node in nodes {
            self.node_to_slot.insert(*node, slot);
        }
    }

    fn set_scopes(&mut self, slot: SlotId, scopes: &[RecomposeScope]) {
        self.slot_to_scopes.insert(slot, scopes.to_vec());
    }

    fn add_node(&mut self, slot: SlotId, node: NodeId) {
        self.slot_to_nodes.entry(slot).or_default().push(node);
        self.node_to_slot.insert(node, slot);
    }

    fn remove_by_node(&mut self, node: &NodeId) -> Option<SlotId> {
        if let Some(slot) = self.node_to_slot.remove(node) {
            if let Some(nodes) = self.slot_to_nodes.get_mut(&slot) {
                if let Some(index) = nodes.iter().position(|candidate| candidate == node) {
                    nodes.remove(index);
                }
                if nodes.is_empty() {
                    self.slot_to_nodes.remove(&slot);
                    self.slot_to_scopes.remove(&slot);
                }
            }
            Some(slot)
        } else {
            None
        }
    }

    fn get_nodes(&self, slot: &SlotId) -> Option<&[NodeId]> {
        self.slot_to_nodes.get(slot).map(Vec::as_slice)
    }

    fn get_scopes(&self, slot: &SlotId) -> Option<&[RecomposeScope]> {
        self.slot_to_scopes.get(slot).map(Vec::as_slice)
    }

    fn slot_has_invalid_scopes(&self, slot: SlotId) -> bool {
        self.slot_to_scopes
            .get(&slot)
            .is_some_and(|scopes| scopes.iter().any(RecomposeScope::is_invalid))
    }

    fn slot_has_inactive_scopes(&self, slot: SlotId) -> bool {
        self.slot_to_scopes
            .get(&slot)
            .is_some_and(|scopes| scopes.iter().any(|scope| !scope.is_active()))
    }

    fn deactivate_slot(&self, slot: SlotId) {
        if let Some(scopes) = self.slot_to_scopes.get(&slot) {
            for scope in scopes {
                scope.deactivate();
            }
        }
    }

    fn invalidate_scopes(&self) {
        for scopes in self.slot_to_scopes.values() {
            for scope in scopes {
                scope.invalidate();
            }
        }
    }
}

/// Tracks the state of nodes produced by subcomposition, enabling reuse between
/// measurement passes.
pub struct SubcomposeState {
    mapping: NodeSlotMapping,
    active_order: Vec<SlotId>,
    live_slots: HashSet<SlotId>,
    current_pass_active_slots: HashSet<SlotId>,
    reusable_by_type: HashMap<u64, VecDeque<(SlotId, NodeId)>>,
    reusable_nodes_untyped: VecDeque<(SlotId, NodeId)>,
    reusable_node_counts: HashMap<SlotId, usize>,
    exact_reactivation_slots: HashSet<SlotId>,
    slot_content_types: HashMap<SlotId, u64>,
    precomposed_nodes: HashMap<SlotId, Vec<NodeId>>,
    policy: Box<dyn SlotReusePolicy>,
    pub(crate) current_index: usize,
    pub(crate) reusable_count: usize,
    pub(crate) precomposed_count: usize,
    slot_compositions: HashMap<SlotId, Rc<SlotsHost>>,
    slot_callbacks: HashMap<SlotId, CallbackHolder>,
    max_reusable_per_type: usize,
    max_reusable_untyped: usize,
    last_slot_reused: Option<bool>,
    retained_capture_keys: HashMap<SlotId, RetainedCaptureKey>,
    content_generation: std::cell::Cell<u64>,
    slot_composed_generation: HashMap<SlotId, (u64, u64)>,
    /// The content generation from which slots compose under changed
    /// static composition locals; zero while none changed.
    locals_generation: std::cell::Cell<u64>,
}

struct RetainedCaptureKey {
    value: Box<dyn Any>,
    eq: fn(&dyn Any, &dyn Any) -> bool,
}

fn retained_capture_key_eq<K: PartialEq + 'static>(stored: &dyn Any, candidate: &dyn Any) -> bool {
    match (stored.downcast_ref::<K>(), candidate.downcast_ref::<K>()) {
        (Some(stored), Some(candidate)) => stored == candidate,
        _ => false,
    }
}

impl fmt::Debug for SubcomposeState {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("SubcomposeState")
            .field("mapping", &self.mapping)
            .field("active_order", &self.active_order)
            .field("reusable_by_type_count", &self.reusable_by_type.len())
            .field("reusable_untyped_count", &self.reusable_nodes_untyped.len())
            .field("precomposed_nodes", &self.precomposed_nodes)
            .field("current_index", &self.current_index)
            .field("reusable_count", &self.reusable_count)
            .field("precomposed_count", &self.precomposed_count)
            .field("slot_compositions_count", &self.slot_compositions.len())
            .finish()
    }
}

impl Default for SubcomposeState {
    fn default() -> Self {
        Self::new(Box::new(DefaultSlotReusePolicy))
    }
}

const DEFAULT_MAX_REUSABLE_PER_TYPE: usize = 5;

const DEFAULT_MAX_REUSABLE_UNTYPED: usize = 10;

impl SubcomposeState {
    /// Creates a new [`SubcomposeState`] using the supplied reuse policy.
    pub fn new(policy: Box<dyn SlotReusePolicy>) -> Self {
        Self {
            mapping: NodeSlotMapping::default(),
            active_order: Vec::new(),
            live_slots: HashSet::default(),
            current_pass_active_slots: HashSet::default(),
            reusable_by_type: HashMap::default(),
            reusable_nodes_untyped: VecDeque::new(),
            reusable_node_counts: HashMap::default(),
            exact_reactivation_slots: HashSet::default(),
            slot_content_types: HashMap::default(),
            precomposed_nodes: HashMap::default(),
            policy,
            current_index: 0,
            reusable_count: 0,
            precomposed_count: 0,
            slot_compositions: HashMap::default(),
            slot_callbacks: HashMap::default(),
            max_reusable_per_type: DEFAULT_MAX_REUSABLE_PER_TYPE,
            max_reusable_untyped: DEFAULT_MAX_REUSABLE_UNTYPED,
            last_slot_reused: None,
            retained_capture_keys: HashMap::default(),
            content_generation: std::cell::Cell::new(0),
            slot_composed_generation: HashMap::default(),
            locals_generation: std::cell::Cell::new(0),
        }
    }

    /// Sets the policy used for future reuse decisions.
    pub fn set_policy(&mut self, policy: Box<dyn SlotReusePolicy>) {
        self.policy = policy;
    }

    /// Sets how many composed nodes the reusable pool keeps: `per_type` for each content type and
    /// `untyped` for nodes without one. Nodes over a limit are disposed.
    pub fn set_reusable_pool_limits(&mut self, per_type: usize, untyped: usize) {
        self.max_reusable_per_type = per_type;
        self.max_reusable_untyped = untyped;
    }

    /// Registers a content type for a slot.
    ///
    /// Stores the content type locally for efficient pool-based reuse lookup,
    /// and also delegates to the policy for compatibility checking.
    ///
    /// Call this before subcomposing an item to enable content-type-aware slot reuse.
    pub fn register_content_type(&mut self, slot_id: SlotId, content_type: u64) {
        self.slot_content_types.insert(slot_id, content_type);
        self.policy.register_content_type(slot_id, content_type);
    }

    /// Updates the content type for a slot, handling optional content types.
    ///
    /// If `content_type` is `Some(type)`, registers the type for the slot.
    /// If `content_type` is `None`, removes any previously registered type.
    /// This ensures stale types don't drive incorrect reuse.
    pub fn update_content_type(&mut self, slot_id: SlotId, content_type: Option<u64>) {
        match content_type {
            Some(ct) => self.register_content_type(slot_id, ct),
            None => {
                self.slot_content_types.remove(&slot_id);
                self.policy.remove_content_type(slot_id);
            }
        }
    }

    /// Returns the content type for a slot, if registered.
    pub fn get_content_type(&self, slot_id: SlotId) -> Option<u64> {
        self.slot_content_types.get(&slot_id).copied()
    }

    /// Returns the active slot that owns a registered root node.
    ///
    /// Descendants must be resolved to their slot root by the caller. Reusable
    /// and removed slots are excluded.
    pub fn active_slot_for_node(&self, node_id: NodeId) -> Option<SlotId> {
        self.mapping
            .node_to_slot
            .get(&node_id)
            .copied()
            .filter(|slot| self.live_slots.contains(slot))
    }

    /// Starts a new subcompose pass.
    ///
    /// Call this before subcomposing the current frame so the state can
    /// track which slots are active and dispose the inactive ones later.
    pub fn begin_pass(&mut self) {
        self.current_index = 0;
        self.current_pass_active_slots.clear();
    }

    /// Returns the current active slot cursor for the in-progress pass.
    pub fn active_slot_cursor(&self) -> usize {
        self.current_index
    }

    /// Restores the active slot cursor for work that should not become part of
    /// the rendered active set, such as lazy-list prefetch measurement.
    pub fn restore_active_slot_cursor(&mut self, cursor: usize) {
        self.current_index = cursor.min(self.active_order.len());
    }

    /// Moves an active slot out of the rendered set and into the reusable pool.
    pub fn recycle_active_slot(&mut self, slot_id: SlotId) -> SubcomposeDisposal {
        self.recycle_active_slot_internal(slot_id, false)
    }

    /// Like `recycle_active_slot`, for a slot that was composed ahead of need. The slot can be
    /// reactivated as it was when its id is asked for again, unless its effects were forgotten.
    pub fn recycle_prefetched_active_slot(&mut self, slot_id: SlotId) -> SubcomposeDisposal {
        self.recycle_active_slot_internal(slot_id, true)
    }

    /// Recycles every active slot that `predicate` accepts and that the current pass has not used.
    /// Returns the nodes and slot hosts that were disposed.
    pub fn recycle_active_slots_where(
        &mut self,
        mut predicate: impl FnMut(SlotId) -> bool,
    ) -> SubcomposeDisposal {
        let slots: Vec<_> = self
            .active_order
            .iter()
            .copied()
            .filter(|slot| !self.current_pass_active_slots.contains(slot))
            .filter(|slot| predicate(*slot))
            .collect();
        let mut disposed = SubcomposeDisposal::default();
        for slot in slots {
            disposed.append(self.recycle_active_slot(slot));
        }
        disposed
    }

    fn recycle_active_slot_internal(
        &mut self,
        slot_id: SlotId,
        allow_exact_reactivation: bool,
    ) -> SubcomposeDisposal {
        let Some(position) = self
            .active_order
            .iter()
            .position(|candidate| *candidate == slot_id)
        else {
            return SubcomposeDisposal::default();
        };
        self.active_order.remove(position);
        if position < self.current_index {
            self.current_index = self.current_index.saturating_sub(1);
        }
        self.move_slot_to_reusable(slot_id, allow_exact_reactivation);
        self.enforce_reusable_pool_limits()
    }

    /// Finishes a subcompose pass, disposing slots that were not used.
    pub fn finish_pass(&mut self) -> SubcomposeDisposal {
        self.dispose_or_reuse_starting_from_index(self.current_index)
    }

    /// Returns the SlotsHost for the given slot ID, creating a new one if it doesn't exist.
    /// Each slot gets its own isolated slot table, avoiding cursor-based conflicts when
    /// items are subcomposed in different orders.
    pub fn get_or_create_slots(&mut self, slot_id: SlotId) -> Rc<SlotsHost> {
        Rc::clone(
            self.slot_compositions
                .entry(slot_id)
                .or_insert_with(|| Rc::new(SlotsHost::new(SlotTable::new()))),
        )
    }

    /// Returns the latest callback holder for the given slot, creating one if needed.
    pub fn callback_holder(&mut self, slot_id: SlotId) -> CallbackHolder {
        self.slot_callbacks.entry(slot_id).or_default().clone()
    }

    #[doc(hidden)]
    pub fn activate_current_active_slot(&mut self, slot_id: SlotId) -> Option<&[NodeId]> {
        self.activate_current_active_slot_at_cursor(slot_id)
            .then(|| self.mapping.get_nodes(&slot_id))
            .flatten()
    }

    fn activate_current_active_slot_at_cursor(&mut self, slot_id: SlotId) -> bool {
        if self.current_pass_active_slots.contains(&slot_id)
            || self.exact_reactivation_slots.contains(&slot_id)
            || self.reusable_node_counts.contains_key(&slot_id)
            || self
                .active_order
                .get(self.current_index)
                .copied()
                .is_none_or(|active_slot| active_slot != slot_id)
            || self.mapping.slot_has_invalid_scopes(slot_id)
            || self.mapping.slot_has_inactive_scopes(slot_id)
        {
            return false;
        }

        if self.mapping.get_nodes(&slot_id).is_none() {
            return false;
        }
        self.last_slot_reused = Some(true);
        self.live_slots.insert(slot_id);
        self.current_pass_active_slots.insert(slot_id);
        self.current_index += 1;
        true
    }

    /// Whether precomposed nodes are waiting to be consumed for this slot.
    /// A pending precomposition means the retained mapping is about to be
    /// superseded, so clean-slot reuse must reject and compose.
    pub fn has_pending_precompositions(&self, slot_id: SlotId) -> bool {
        self.precomposed_nodes.contains_key(&slot_id)
    }

    /// Whether the slot's stored capture key equals `key`. A missing key never
    /// matches: a slot must compose at least once under the key discipline
    /// before it may skip.
    pub fn retained_capture_key_matches<K: PartialEq + 'static>(
        &self,
        slot_id: SlotId,
        key: &K,
    ) -> bool {
        self.retained_capture_keys
            .get(&slot_id)
            .is_some_and(|retained| (retained.eq)(retained.value.as_ref(), key))
    }

    /// Records the capture key the slot is being composed under.
    pub fn store_retained_capture_key<K: PartialEq + 'static>(&mut self, slot_id: SlotId, key: K) {
        self.retained_capture_keys.insert(
            slot_id,
            RetainedCaptureKey {
                value: Box::new(key),
                eq: retained_capture_key_eq::<K>,
            },
        );
    }

    #[doc(hidden)]
    pub fn activate_exact_slot(&mut self, slot_id: SlotId) -> Option<ExactSlotActivation<'_>> {
        if self.activate_current_active_slot_at_cursor(slot_id) {
            return Some(ExactSlotActivation {
                nodes: self.mapping.get_nodes(&slot_id)?,
                was_recycled: false,
            });
        }
        let active_position = self
            .active_order
            .iter()
            .position(|candidate| *candidate == slot_id);
        let is_exact_reactivation = self.exact_reactivation_slots.contains(&slot_id);
        if active_position.is_none() && !is_exact_reactivation
            || self.mapping.slot_has_invalid_scopes(slot_id)
        {
            return None;
        }

        let node_count = self.mapping.get_nodes(&slot_id)?.len();
        if active_position.is_none() {
            for index in 0..node_count {
                let node = self.mapping.get_nodes(&slot_id)?[index];
                let _ = self.remove_from_reusable_pools(node);
            }
            for scope in self.mapping.get_scopes(&slot_id).unwrap_or_default() {
                scope.reactivate();
            }
        }
        self.mark_slot_active(slot_id, true);
        Self::consume_precomposed_nodes(
            &mut self.precomposed_nodes,
            &mut self.precomposed_count,
            slot_id,
            self.mapping.get_nodes(&slot_id)?,
        );
        Some(ExactSlotActivation {
            nodes: self.mapping.get_nodes(&slot_id)?,
            was_recycled: active_position.is_none(),
        })
    }

    /// Records that the nodes in `node_ids` are currently rendering the provided
    /// `slot_id`.
    pub fn register_active(
        &mut self,
        slot_id: SlotId,
        node_ids: &[NodeId],
        scopes: &[RecomposeScope],
    ) {
        let was_reused = self.mapping.get_nodes(&slot_id).is_some();
        for scope in scopes {
            scope.reactivate();
        }
        self.update_active_slot_mapping(slot_id, node_ids, scopes);
        self.mark_slot_active(slot_id, was_reused);
    }

    fn mark_slot_active(&mut self, slot_id: SlotId, was_reused: bool) {
        self.last_slot_reused = Some(was_reused);
        self.live_slots.insert(slot_id);
        self.current_pass_active_slots.insert(slot_id);
        self.exact_reactivation_slots.remove(&slot_id);

        if let Some(position) = self.active_order.iter().position(|slot| *slot == slot_id) {
            if position < self.current_index {
                return;
            }
            self.active_order.remove(position);
        }
        let insert_at = self.current_index.min(self.active_order.len());
        self.active_order.insert(insert_at, slot_id);
        self.current_index += 1;
    }

    fn update_active_slot_mapping(
        &mut self,
        slot_id: SlotId,
        node_ids: &[NodeId],
        scopes: &[RecomposeScope],
    ) {
        self.mapping.set_nodes(slot_id, node_ids);
        self.mapping.set_scopes(slot_id, scopes);
        Self::consume_precomposed_nodes(
            &mut self.precomposed_nodes,
            &mut self.precomposed_count,
            slot_id,
            node_ids,
        );
    }

    fn consume_precomposed_nodes(
        precomposed_nodes: &mut HashMap<SlotId, Vec<NodeId>>,
        precomposed_count: &mut usize,
        slot_id: SlotId,
        node_ids: &[NodeId],
    ) {
        if let Some(nodes) = precomposed_nodes.get_mut(&slot_id) {
            let before_len = nodes.len();
            nodes.retain(|node| !node_ids.contains(node));
            let removed = before_len - nodes.len();
            *precomposed_count = precomposed_count.saturating_sub(removed);
            if nodes.is_empty() {
                precomposed_nodes.remove(&slot_id);
            }
        }
    }

    /// Stores a precomposed node for the provided slot. Precomposed nodes stay
    /// detached from the tree until they are activated by `register_active`.
    pub fn register_precomposed(&mut self, slot_id: SlotId, node_id: NodeId) {
        self.precomposed_nodes
            .entry(slot_id)
            .or_default()
            .push(node_id);
        self.precomposed_count += 1;
    }

    fn increment_reusable_slot(&mut self, slot_id: SlotId) {
        *self.reusable_node_counts.entry(slot_id).or_insert(0) += 1;
        self.reusable_count += 1;
    }

    fn decrement_reusable_slot(&mut self, slot_id: SlotId) {
        let Some(entry) = self.reusable_node_counts.get_mut(&slot_id) else {
            self.reusable_count = self.reusable_count.saturating_sub(1);
            return;
        };
        *entry = entry.saturating_sub(1);
        if *entry == 0 {
            self.reusable_node_counts.remove(&slot_id);
        }
        self.reusable_count = self.reusable_count.saturating_sub(1);
    }

    /// Whether `slot_id` is composed and active: the last pass kept it, or
    /// the current one did.
    pub fn slot_is_active(&self, slot_id: SlotId) -> bool {
        self.live_slots.contains(&slot_id)
    }

    /// Whether `slot_id` still has a composition here: active, or kept in the
    /// reuse pool where it can be reactivated. A slot that is neither has
    /// been disposed, and nothing measured for it can be used again.
    pub fn slot_is_retained(&self, slot_id: SlotId) -> bool {
        self.live_slots.contains(&slot_id) || self.reusable_node_counts.contains_key(&slot_id)
    }

    fn prune_slot_if_unused(&mut self, slot_id: SlotId) -> Option<Rc<SlotsHost>> {
        if self.slot_is_retained(slot_id) {
            return None;
        }

        debug_assert!(
            self.mapping.get_nodes(&slot_id).is_none(),
            "inactive slot {slot_id:?} still has mapped nodes",
        );

        let host = self.slot_compositions.remove(&slot_id);
        self.slot_callbacks.remove(&slot_id);
        self.slot_content_types.remove(&slot_id);
        self.retained_capture_keys.remove(&slot_id);
        self.slot_composed_generation.remove(&slot_id);
        self.policy.remove_content_type(slot_id);
        if let Some(nodes) = self.precomposed_nodes.remove(&slot_id) {
            self.precomposed_count = self.precomposed_count.saturating_sub(nodes.len());
        }
        host
    }

    /// Returns the node that previously rendered this slot, if it is still
    /// considered reusable, and whether it was REBOUND — taken from another
    /// slot, so its retained subtree is about to show different content. An
    /// exact-slot reactivation hands the same item its own subtree back and
    /// is not a rebinding.
    ///
    /// Lookup order:
    /// 1. Exact slot match in the appropriate pool (not a rebinding)
    /// 2. Any policy-compatible node from the same content-type pool
    /// 3. Fallback to untyped pool with policy compatibility check
    pub fn take_node_from_reusables(&mut self, slot_id: SlotId) -> Option<(NodeId, bool)> {
        if let Some(nodes) = self.mapping.get_nodes(&slot_id) {
            let first_node = nodes.first().copied();
            if let Some(node_id) = first_node {
                let _ = self.remove_from_reusable_pools(node_id);
                self.exact_reactivation_slots.remove(&slot_id);
                return Some((node_id, false));
            }
        }

        let content_type = self.slot_content_types.get(&slot_id).copied();

        if let Some(ct) = content_type
            && let Some((old_slot, node_id)) = self.take_compatible_typed_reusable(ct, slot_id)
        {
            self.decrement_reusable_slot(old_slot);
            self.move_node_to_slot(node_id, old_slot, slot_id);
            return Some((node_id, true));
        }

        let exact_reactivation_slots = &self.exact_reactivation_slots;
        let policy = &self.policy;
        let position = self
            .reusable_nodes_untyped
            .iter()
            .position(|(existing_slot, _)| {
                !exact_reactivation_slots.contains(existing_slot)
                    && policy.are_compatible(*existing_slot, slot_id)
            });

        if let Some(index) = position
            && let Some((old_slot, node_id)) = self.reusable_nodes_untyped.remove(index)
        {
            self.decrement_reusable_slot(old_slot);
            self.move_node_to_slot(node_id, old_slot, slot_id);
            return Some((node_id, true));
        }

        None
    }

    fn take_compatible_typed_reusable(
        &mut self,
        content_type: u64,
        requested_slot: SlotId,
    ) -> Option<(SlotId, NodeId)> {
        let reused = {
            let policy = &self.policy;
            let exact_reactivation_slots = &self.exact_reactivation_slots;
            let pool = self.reusable_by_type.get_mut(&content_type)?;
            let index = pool.iter().position(|(existing_slot, _)| {
                !exact_reactivation_slots.contains(existing_slot)
                    && policy.are_compatible(*existing_slot, requested_slot)
            })?;
            pool.remove(index)
        };

        if self
            .reusable_by_type
            .get(&content_type)
            .is_some_and(std::collections::VecDeque::is_empty)
        {
            self.reusable_by_type.remove(&content_type);
        }

        reused
    }

    fn remove_from_reusable_pools(&mut self, node_id: NodeId) -> Option<SlotId> {
        let mut typed_match = None;
        for (&content_type, pool) in &self.reusable_by_type {
            if let Some(position) = pool
                .iter()
                .position(|(_, pooled_node)| *pooled_node == node_id)
            {
                typed_match = Some((content_type, position));
                break;
            }
        }
        if let Some((content_type, position)) = typed_match {
            let pool = self.reusable_by_type.get_mut(&content_type)?;
            let (slot, _) = pool.remove(position)?;
            if pool.is_empty() {
                self.reusable_by_type.remove(&content_type);
            }
            self.decrement_reusable_slot(slot);
            return Some(slot);
        }
        if let Some(position) = self
            .reusable_nodes_untyped
            .iter()
            .position(|(_, n)| *n == node_id)
            && let Some((slot, _)) = self.reusable_nodes_untyped.remove(position)
        {
            self.decrement_reusable_slot(slot);
            return Some(slot);
        }
        None
    }

    fn move_node_to_slot(&mut self, node_id: NodeId, old_slot: SlotId, new_slot: SlotId) {
        if old_slot == new_slot {
            return;
        }

        self.mapping.remove_by_node(&node_id);
        self.exact_reactivation_slots.remove(&old_slot);
        self.mapping.add_node(new_slot, node_id);
        self.slot_content_types.remove(&old_slot);
        self.retained_capture_keys.remove(&old_slot);
        self.retained_capture_keys.remove(&new_slot);
        self.slot_composed_generation.remove(&old_slot);
        self.slot_composed_generation.remove(&new_slot);
        self.policy.remove_content_type(old_slot);
        if let Some(slots) = self.slot_compositions.remove(&old_slot) {
            self.slot_compositions.insert(new_slot, slots);
        }
        if let Some(callback) = self.slot_callbacks.remove(&old_slot) {
            self.slot_callbacks.insert(new_slot, callback);
        }
        if let Some(nodes) = self.precomposed_nodes.get_mut(&old_slot) {
            let before_len = nodes.len();
            nodes.retain(|candidate| *candidate != node_id);
            let removed = before_len - nodes.len();
            self.precomposed_count = self.precomposed_count.saturating_sub(removed);
            if nodes.is_empty() {
                self.precomposed_nodes.remove(&old_slot);
            }
        }
    }

    /// Moves active slots starting from `start_index` to the reusable bucket.
    /// Returns the list of node ids that were DISPOSED (not just moved to reusable).
    /// Nodes that exceed max_reusable_per_type are disposed instead of cached.
    pub fn dispose_or_reuse_starting_from_index(
        &mut self,
        start_index: usize,
    ) -> SubcomposeDisposal {
        if start_index >= self.active_order.len() {
            return SubcomposeDisposal::default();
        }

        let retain = self
            .policy
            .get_slots_to_retain(&self.active_order[start_index..]);
        let mut retained = Vec::new();
        while self.active_order.len() > start_index {
            let Some(slot) = self.active_order.pop() else {
                break;
            };
            if retain.contains(&slot) {
                retained.push(slot);
                continue;
            }
            self.move_slot_to_reusable(slot, false);
        }
        retained.reverse();
        self.active_order.extend(retained);

        self.enforce_reusable_pool_limits()
    }

    fn move_slot_to_reusable(&mut self, slot: SlotId, allow_exact_reactivation: bool) {
        self.live_slots.remove(&slot);
        self.current_pass_active_slots.remove(&slot);
        self.mapping.deactivate_slot(slot);
        let forgot_effects = self
            .slot_compositions
            .get(&slot)
            .is_some_and(|host| host.forget_effects());
        if allow_exact_reactivation && !forgot_effects {
            self.exact_reactivation_slots.insert(slot);
        } else {
            self.exact_reactivation_slots.remove(&slot);
        }

        let content_type = self.slot_content_types.get(&slot).copied();
        let nodes: SmallVec<[NodeId; 4]> = self
            .mapping
            .get_nodes(&slot)
            .into_iter()
            .flatten()
            .copied()
            .collect();
        for node in nodes {
            if let Some(ct) = content_type {
                self.reusable_by_type
                    .entry(ct)
                    .or_default()
                    .push_back((slot, node));
            } else {
                self.reusable_nodes_untyped.push_back((slot, node));
            }
            self.increment_reusable_slot(slot);
        }
    }

    fn enforce_reusable_pool_limits(&mut self) -> SubcomposeDisposal {
        let mut disposed = SubcomposeDisposal::default();
        let mut typed_disposals = Vec::new();
        for pool in self.reusable_by_type.values_mut() {
            while pool.len() > self.max_reusable_per_type {
                if let Some((slot, node_id)) = pool.pop_front() {
                    typed_disposals.push((slot, node_id));
                }
            }
        }
        for (slot, node_id) in typed_disposals {
            self.decrement_reusable_slot(slot);
            self.mapping.remove_by_node(&node_id);
            self.exact_reactivation_slots.remove(&slot);
            disposed.slot_hosts.extend(self.prune_slot_if_unused(slot));
            disposed.nodes.push(node_id);
        }

        while self.reusable_nodes_untyped.len() > self.max_reusable_untyped {
            if let Some((slot, node_id)) = self.reusable_nodes_untyped.pop_front() {
                self.decrement_reusable_slot(slot);
                self.mapping.remove_by_node(&node_id);
                self.exact_reactivation_slots.remove(&slot);
                disposed.slot_hosts.extend(self.prune_slot_if_unused(slot));
                disposed.nodes.push(node_id);
            }
        }

        self.reusable_by_type.retain(|_, pool| !pool.is_empty());
        disposed
    }

    /// Returns a snapshot of currently reusable nodes.
    pub fn reusable(&self) -> Vec<NodeId> {
        let mut nodes: Vec<NodeId> = self
            .reusable_by_type
            .values()
            .flat_map(|pool| pool.iter().map(|(_, n)| *n))
            .collect();
        nodes.extend(self.reusable_nodes_untyped.iter().map(|(_, n)| *n));
        nodes
    }

    /// Returns the number of slots currently active (in use during this pass).
    ///
    /// This reflects the slots that were activated via `register_active()` during
    /// the current measurement pass.
    pub fn active_slots_count(&self) -> usize {
        self.active_order.len()
    }

    /// Returns the number of reusable slots in the pool.
    ///
    /// These are slots that were previously active but are now available for reuse
    /// by compatible content types.
    pub fn reusable_slots_count(&self) -> usize {
        self.reusable_count
    }

    /// Invalidates all tracked subcomposition scopes.
    ///
    /// Hosts should call this when parent-captured inputs change without directly invalidating
    /// the child scopes themselves. The next subcompose pass will then re-run active slot
    /// content instead of skipping with stale captures.
    /// Invalidating scopes alone is not a reliable "recompose on next
    /// measure" signal: the recomposer drains invalid scopes before measure
    /// runs, re-executing the RETAINED slot callbacks — parent-captured
    /// values baked into a replaced closure never flow in, yet the scopes
    /// come back valid. The generation bump is the unlaunderable half: only
    /// a measure-time compose of the slot brings it current, so clean-slot
    /// reuse stays blocked until the new content actually landed.
    pub fn invalidate_scopes(&self) {
        self.mapping.invalidate_scopes();
        self.content_generation
            .set(self.content_generation.get() + 1);
    }

    /// Records that a static composition local the slots compose under
    /// changed: every slot composed before must compose again, and run
    /// every body it holds, before it may be reused.
    pub fn invalidate_locals(&self) {
        self.bump_content_generation();
        self.locals_generation.set(self.content_generation.get());
    }

    /// Whether the slot composed before a static composition local it reads
    /// from changed; see [`Self::invalidate_locals`]. A composition another
    /// slot left counts as fresh: its scopes come back inactive, and a group
    /// entered with an inactive scope composes again anyway.
    pub fn slot_locals_stale(&self, slot_id: SlotId) -> bool {
        let changed_at = self.locals_generation.get();
        self.slot_composed_generation
            .get(&slot_id)
            .is_some_and(|(generation, _)| *generation < changed_at)
    }

    /// Advances the content generation without invalidating scopes: every
    /// slot must re-compose once before clean-slot reuse may skip it again.
    /// Called when the owning node leaves its parent — a retained subtree
    /// that comes back from the reuse pool restarts its effects only if its
    /// slots actually recompose, and scope flags carry no durable trace of
    /// the detach (deactivation walks stop at nested slot-host boundaries).
    pub fn bump_content_generation(&self) {
        self.content_generation
            .set(self.content_generation.get() + 1);
    }

    /// Whether the slot last composed under the current content generation
    /// and owner-chain deactivation epoch. False after any
    /// [`Self::invalidate_scopes`], and false after any composition up the
    /// owner chain was deactivated, until a measure-time compose of this
    /// slot runs.
    pub fn slot_content_generation_current(&self, slot_id: SlotId, owner_epoch: u64) -> bool {
        self.slot_composed_generation.get(&slot_id).copied()
            == Some((self.content_generation.get(), owner_epoch))
    }

    /// Records that the slot just composed under the current generation and
    /// the given owner-chain deactivation epoch.
    pub fn mark_slot_composed_current(&mut self, slot_id: SlotId, owner_epoch: u64) {
        self.slot_composed_generation
            .insert(slot_id, (self.content_generation.get(), owner_epoch));
    }

    /// Returns whether the last slot registered via [`Self::register_active`] was reused.
    ///
    /// Returns `Some(true)` if the slot already existed (was reused from pool or
    /// was recomposed), `Some(false)` if it was newly created, or `None` if no
    /// slot has been registered yet this pass.
    ///
    /// This is useful for tracking composition statistics in lazy layouts.
    pub fn was_last_slot_reused(&self) -> Option<bool> {
        self.last_slot_reused
    }

    #[doc(hidden)]
    pub fn debug_scope_ids_by_slot(&self) -> Vec<(u64, Vec<usize>)> {
        self.mapping
            .slot_to_scopes
            .iter()
            .map(|(slot, scopes)| (slot.raw(), scopes.iter().map(RecomposeScope::id).collect()))
            .collect()
    }

    #[doc(hidden)]
    pub fn debug_slot_table_for_slot(&self, slot_id: SlotId) -> Option<Vec<crate::SlotDebugEntry>> {
        let slots = self.slot_compositions.get(&slot_id)?;
        Some(slots.borrow().debug_dump_slot_entries())
    }

    #[doc(hidden)]
    pub fn debug_slot_table_groups_for_slot(&self, slot_id: SlotId) -> Option<Vec<DebugSlotGroup>> {
        let slots = self.slot_compositions.get(&slot_id)?;
        Some(slots.borrow().debug_dump_groups())
    }

    /// Returns a snapshot of precomposed nodes.
    pub fn precomposed(&self) -> &HashMap<SlotId, Vec<NodeId>> {
        &self.precomposed_nodes
    }

    /// Removes any precomposed nodes whose slots were not activated during the
    /// current pass and returns their identifiers for disposal.
    pub fn drain_inactive_precomposed(&mut self) -> SubcomposeDisposal {
        let mut disposed = SubcomposeDisposal::default();
        let mut empty_slots = Vec::new();
        for (slot, nodes) in &mut self.precomposed_nodes {
            if !self.current_pass_active_slots.contains(slot) {
                disposed.nodes.extend(nodes.iter().copied());
                empty_slots.push(*slot);
            }
        }
        for slot in empty_slots {
            self.precomposed_nodes.remove(&slot);
            disposed.slot_hosts.extend(self.prune_slot_if_unused(slot));
        }
        self.precomposed_count = self.precomposed_count.saturating_sub(disposed.nodes.len());
        disposed
    }
}

#[cfg(test)]
#[path = "tests/subcompose_tests.rs"]
mod tests;