openusd 0.6.0

//! Scene-graph instancing: shared prototypes for `instanceable` prims (spec
//! 11.3.3).
//!
//! Instances with the same [`InstanceKey`] — the arc-introduced opinions that
//! define their subtree, independent of stage path — share one composed
//! prototype. [`PrototypeRegistry`] owns that mapping (an [`IndexCache`] holds
//! one as a field); the composition-coupled glue stays on `IndexCache` because
//! it needs the composed indices. The prototype *namespace* is the single
//! composition of a set of identical instances and composes in place: the root
//! from its materialized `/__Prototype_N` index, a descendant by deepening that
//! graph. Every descendant-serving query enters through
//! [`IndexCache::effective_path`], which redirects an instance proxy `/A/tail`
//! onto `/__Prototype_N/tail` so identical instances are composed only once,
//! while an instance root composes in place (it may override property values).
//! Materializing the root independently keeps its shared content addressable
//! without the seeding instance's root-level overrides leaking in.

use std::collections::{HashMap, HashSet};

use anyhow::Result;

use crate::sdf;
use crate::sdf::schema::FieldKey;
use crate::sdf::{Path, PathElement, Value};

use super::index_cache::IndexCache;
use super::layer_graph::LayerGraph;
use super::load_rules::LoadRules;
use super::prim_graph::ArcType;
use super::prim_index::PrimIndex;
use super::prim_indexer::ExprVarDeps;
use super::LayerId;

/// The shared-prototype registry (spec 11.3.3): maps each instancing key to its
/// prototype and tracks the instances that share it. Owns no composition state
/// — the [`IndexCache`] computes an [`InstanceKey`] from a composed index and
/// hands it to [`register`](Self::register); the registry only dedups by key,
/// mints `/__Prototype_N` identities, and answers prototype/instance queries.
#[derive(Default)]
pub(super) struct PrototypeRegistry {
    /// Prototypes keyed by their `/__Prototype_N` root path. A namespace-aware
    /// table so the common query direction (path to prototype) is a single
    /// lookup, while change invalidation can fan a touched path up to an
    /// enclosing root and down to nested roots without scanning every entry.
    by_root: sdf::PathTable<Prototype>,
    /// Reverse index from each instance's stage path to its `/__Prototype_N`
    /// root, so a changed path resolves to the prototypes whose instances it
    /// touches via bounded ancestor/subtree lookups rather than a full scan.
    by_instance: sdf::PathTable<Path>,
    /// Maps an instancing key to its prototype root, the lookup direction used
    /// only when registering an instance to dedup against an existing key.
    by_key: HashMap<InstanceKey, Path>,
    /// Counter for minting `/__Prototype_N` identities in registration order.
    /// Stays monotonic across [`clear`](Self::clear) so a `/__Prototype_N`
    /// identity is never reused for a different composition within a session.
    count: usize,
}

/// A shared prototype for a set of instances with the same [`InstanceKey`]
/// (spec 11.3.3). The prototype *root* is composed as an independent
/// `/__Prototype_N` index, built from the canonical instance's shared subtree —
/// the instanceable arc, its descendants, and the implied classes — with the
/// instance-local opinions (the local root override and the ancestral references
/// above the instanceable arc) inerted (see
/// [`PrimIndex::mark_instance_local_inert`]) and the namespace re-anchored onto
/// the prototype root (see [`PrimIndex::rebase_root`]). Its descendants compose
/// in place by deepening that graph, and every sharing instance's proxies
/// redirect onto the prototype namespace through [`IndexCache::redirect_anchor`],
/// so identical instances compose once. Materializing the root is what keeps a
/// query on `/__Prototype_N` itself free of the seeding instance's root-level
/// overrides (spec 11.3.3 permits overriding property values at an instance
/// root).
struct Prototype {
    /// Registration order (the `N` in `/__Prototype_N`). Kept so prototypes can
    /// be returned in mint order without parsing the path.
    index: usize,
    /// Instance whose composed subtree seeds this prototype's materialization.
    canonical: Path,
    /// Every instance sharing this prototype.
    instances: Vec<Path>,
    /// The canonical instance's load rules, re-rooted onto the instance's own
    /// path (`LoadRules::make_relative_to`), so a `/__Prototype_N` descendant
    /// build resolves its own payload-inclusion decision against the
    /// instance's authored rules (see `IndexCache::scoped_load_rules`).
    relative_load_rules: LoadRules,
}

/// Identity of an instance prim's shared composition (spec 11.3.3): the
/// arc-introduced opinions that determine its subtree, independent of the
/// instance's own stage path. Instances with equal keys share a prototype.
///
/// Variant selections are folded in explicitly via [`selections`](Self::selections)
/// rather than left implicit in the arc paths: each arc's path has its variant
/// selections stripped (so two instances of the same reference produce the same
/// arc path regardless of which variant they pick) and the resolved selection
/// set is carried as a separate, path-independent list. Without the explicit
/// list, two instances of one reference that differ only by a variant selection
/// would collide once the selection is stripped from the path.
#[derive(Clone, PartialEq, Eq, Hash)]
pub(super) struct InstanceKey {
    arcs: Vec<InstanceArc>,
    /// The resolved `(variant set, selection)` pairs, in composition order.
    selections: Vec<(String, String)>,
    /// The instance's load rules, re-rooted onto its own path
    /// (`LoadRules::make_relative_to`). Two otherwise-identical instances
    /// with different load rules mint separate prototypes (C++
    /// `Usd_InstanceKey`), since a shared prototype's descendants must
    /// resolve one consistent payload-inclusion decision.
    load_rules: LoadRules,
}

/// One arc contribution in an [`InstanceKey`]. Floats are stored as bit
/// patterns so the key is `Hash`/`Eq`.
#[derive(Clone, PartialEq, Eq, Hash)]
struct InstanceArc {
    arc: u8,
    layer: LayerId,
    path: String,
    offset_bits: u64,
    scale_bits: u64,
}

impl PrototypeRegistry {
    /// Registers `instance` against its prototype: dedups by `key`, recording
    /// the instance the first time a key is seen and minting `/__Prototype_N`.
    /// Returns the canonical instance, the prototype path, and whether this call
    /// minted a new prototype (so the caller knows to materialize its index).
    /// `key.load_rules` is stored as the prototype's relative load rules only
    /// on the minting call — a cache hit's existing entry is already
    /// guaranteed identical, since it was part of the matched key.
    fn register(&mut self, key: InstanceKey, instance: &Path) -> (Path, Path, bool) {
        if let Some(root) = self.by_key.get(&key) {
            let root = root.clone();
            let prototype = self.by_root.get_mut(&root).expect("key index points to a prototype");
            if !prototype.instances.contains(instance) {
                prototype.instances.push(instance.clone());
                self.by_instance.insert(instance.clone(), root.clone());
            }
            return (prototype.canonical.clone(), root, false);
        }

        let index = self.count;
        let path = Path::new(&format!("/__Prototype_{index}")).expect("synthetic prototype path is valid");
        self.count += 1;
        let relative_load_rules = key.load_rules.clone();
        self.by_key.insert(key, path.clone());
        self.by_root.insert(
            path.clone(),
            Prototype {
                index,
                canonical: instance.clone(),
                instances: vec![instance.clone()],
                relative_load_rules,
            },
        );
        self.by_instance.insert(instance.clone(), path.clone());
        (instance.clone(), path, true)
    }

    /// The canonical instance's load rules, re-rooted onto the instance's own
    /// path, for the prototype at `prototype`. `None` for an unknown path.
    fn relative_load_rules(&self, prototype: &Path) -> Option<&LoadRules> {
        self.by_root.get(prototype).map(|p| &p.relative_load_rules)
    }

    /// The canonical instance backing the prototype at `prototype`, or `None`
    /// for an unknown path. Used by registry tests to assert a prototype's
    /// presence; production composition reaches the prototype directly through
    /// [`register`](Self::register)'s return.
    #[cfg(test)]
    fn canonical_of(&self, prototype: &Path) -> Option<Path> {
        self.by_root.get(prototype).map(|p| p.canonical.clone())
    }

    /// The instances sharing the prototype at `prototype` (a `/__Prototype_N`
    /// path), sorted by namespace path so the result does not depend on the
    /// order instances were queried. Empty for unknown paths.
    fn instances_of(&self, prototype: &Path) -> Vec<Path> {
        let mut instances = self.instances_unsorted(prototype).to_vec();
        instances.sort();
        instances
    }

    /// The instances sharing the prototype at `prototype`, in registration
    /// order, borrowed without the clone-and-sort of [`instances_of`](Self::instances_of).
    /// Used for membership checks (e.g. population-mask gating) where order is
    /// irrelevant. Empty for unknown paths.
    fn instances_unsorted(&self, prototype: &Path) -> &[Path] {
        self.by_root.get(prototype).map_or(&[], |p| &p.instances)
    }

    /// The registered `/__Prototype_N` roots, in registration order.
    fn roots(&self) -> Vec<Path> {
        let mut roots: Vec<(&Path, &Prototype)> = self.by_root.iter().collect();
        roots.sort_by_key(|(_, prototype)| prototype.index);
        roots.into_iter().map(|(root, _)| root.clone()).collect()
    }

    /// Whether `path` is a registered `/__Prototype_N` root.
    fn is_root(&self, path: &Path) -> bool {
        self.by_root.contains_key(path)
    }

    /// Whether `path` lies within a prototype's namespace — i.e. it has a
    /// `/__Prototype_N` ancestor (spec 11.3.3).
    fn is_in_prototype(&self, path: &Path) -> bool {
        let Some(parent) = path.parent() else {
            return false;
        };
        self.enclosing_root(Some(&parent)).is_some()
    }

    /// Returns the nearest `/__Prototype_N` root at or above `start`, or `None`.
    /// Passing the queried prim starts the walk inclusively; passing its parent
    /// excludes the prim itself.
    fn enclosing_root(&self, start: Option<&Path>) -> Option<Path> {
        self.by_root.nearest_ancestor(start?).map(|(root, _)| root.clone())
    }

    /// Removes every prototype the change set could have invalidated, returning
    /// the dropped `/__Prototype_N` roots so the cache can evict their indices.
    /// A prototype is affected when a changed prim path lies on the ancestor
    /// chain of one of its instances (the instance's `instanceable` opinion,
    /// arcs, or shared content may have changed) or of its prototype root.
    /// Unaffected prototypes keep their instance-to-prototype mapping and
    /// materialized index, so a localized edit no longer forces every key to be
    /// recomputed (spec 11.3.3).
    ///
    /// `count` stays monotonic (see its doc), so a re-registered instance mints
    /// a fresh identity rather than reusing a removed prototype's number.
    ///
    /// Each changed path resolves to the prototypes it could affect through
    /// bounded lookups: the [`by_root`](Self::by_root) entries nested with it
    /// (an enclosing root above, or `/__Prototype_N` roots below) and, via the
    /// [`by_instance`](Self::by_instance) reverse index, the prototypes whose
    /// instances it is nested with. The cost scales with the change set and the
    /// touched subtrees, not the total prototype count.
    fn remove_affected(&mut self, changed: &[Path]) -> Vec<Path> {
        let mut affected: HashSet<Path> = HashSet::new();
        for p in changed {
            for (root, _) in self.by_root.ancestors(p).chain(self.by_root.subtree(p)) {
                affected.insert(root.clone());
            }
            for (_, root) in self.by_instance.ancestors(p).chain(self.by_instance.subtree(p)) {
                affected.insert(root.clone());
            }
        }
        for root in &affected {
            if let Some(prototype) = self.by_root.remove(root) {
                for instance in &prototype.instances {
                    self.by_instance.remove(instance);
                }
            }
        }
        self.by_key.retain(|_, root| !affected.contains(root));
        affected.into_iter().collect()
    }
}

/// Computes the instancing key for an already-built instance index: the
/// arc-introduced (shared) opinions that define the prototype subtree,
/// independent of the instance's own stage path (spec 11.3.3).
/// `instance_depth` is the instance prim's own namespace depth, used to
/// partition shared from instance-local nodes
/// ([`PrimIndex::instance_local_nodes`]).
///
/// Each contributing arc's path is stripped of variant selections, and the
/// resolved selection set is folded into the key explicitly (see
/// [`InstanceKey`]), so two instances of one reference share a prototype iff
/// their variant selections also match. `load_rules` is the instance's load
/// rules, already re-rooted onto its own path (`LoadRules::make_relative_to`),
/// so two instances also only share a prototype when their load state agrees.
fn instance_key(index: &PrimIndex, instance_depth: u16, load_rules: LoadRules) -> InstanceKey {
    let local = index.instance_local_nodes(instance_depth, instance_depth);
    let mut arcs = Vec::new();
    let mut selections = Vec::new();
    for (id, node) in index.nodes_with_ids() {
        if local[id.idx()] || node.is_culled() {
            continue;
        }
        if node.arc == ArcType::Variant {
            if let Some(PathElement::Variant { set, selection }) = node.path.last_element() {
                selections.push((set.to_string(), selection.to_string()));
            }
        }
        let offset = node.map_to_root.time_offset();
        arcs.push(InstanceArc {
            arc: node.arc as u8,
            layer: node.layer_id(),
            path: node.path.strip_all_variant_selections().to_string(),
            offset_bits: offset.offset.to_bits(),
            scale_bits: offset.scale.to_bits(),
        });
    }
    InstanceKey {
        arcs,
        selections,
        load_rules,
    }
}

impl IndexCache {
    /// Evicts only the prototypes a prim-level change touches (spec 11.3.3):
    /// every prototype whose instance subtree or prototype namespace lies on the
    /// ancestor chain of one of the `changed` prim paths is removed from the
    /// registry and has its materialized `/__Prototype_N` index dropped.
    /// Unaffected prototypes keep their mapping and index, so a localized edit
    /// does not recompute every key.
    ///
    /// Pure analysis over the change list (no composition), so it stays
    /// rayon-friendly: see [`PrototypeRegistry::remove_affected`]. A layer-stack
    /// edit instead drops the affected prototypes through
    /// [`Self::invalidate_layers`].
    pub(crate) fn invalidate_prototypes(&mut self, changed: &[Path]) {
        // A prototype's whole namespace composes in place now (the root from its
        // materialized index, descendants by deepening it; see
        // [`Self::redirect_anchor`]), so each affected root's entire subtree must
        // be dropped, not just the root spec.
        //
        // TODO(perf): `drop_index_subtree` is an O(n) cache scan per affected
        // root; batching the affected roots into one prefix-filtered pass (or an
        // `SdfPathTable`-like trie) would bound it by the change set.
        for root in self.prototypes.remove_affected(changed) {
            self.drop_index_subtree(&root);
        }
        // The redirection memo is keyed on instance/prototype structure that the
        // dropped prototypes may have defined, so clear it wholesale; it is
        // repopulated lazily on the next descendant query.
        self.redirected_prims.clear();
    }

    /// Returns `true` if `path` resolves as an instance prim (spec 11.3.3):
    /// the strongest `instanceable` opinion is `true` and the prim has at
    /// least one composition arc.
    ///
    /// A `/__Prototype_N` root is never an instance, whatever its composed
    /// `instanceable` opinion says. The opinion is routinely `true` there: an
    /// asset commonly authors `instanceable = true` on the very prim its
    /// referencing layer targets, so the opinion arrives on the instanceable arc
    /// itself and is shared content the prototype must keep. It describes the
    /// instances that share this prototype, not the prototype, which stands
    /// outside the instance namespace as the single composition those instances
    /// redirect onto. Exempting the root here is also what lets
    /// [`Self::redirect_anchor`] compose plain prototype content in place: were
    /// the root an instance, its own descendants would redirect back through it.
    /// A *nested* instance inside a prototype namespace is not a prototype root,
    /// so it still resolves as an instance and mints its own prototype.
    ///
    /// Reads `instanceable` off the index that actually composes `path` — for an
    /// instance proxy that is the shared `/__Prototype_N` index, reached through
    /// [`Self::effective_path`], not a throwaway per-instance copy. So checking
    /// instance-ness while walking a deep proxy subtree (every ancestor is tested
    /// by [`Self::enclosing_instance`]) composes the shared subtree once instead
    /// of a literal index per instance. `effective_path` re-enters `is_instance`
    /// on a strict ancestor to find the enclosing instance, but each step moves
    /// to a shorter path and bottoms out at the root, so the recursion
    /// terminates.
    pub(crate) fn is_instance(&mut self, graph: &LayerGraph, path: &Path) -> Result<bool> {
        if path.is_abs_root() || self.is_prototype(path) {
            return Ok(false);
        }
        let composed = self.effective_path(graph, path)?;
        self.ensure_index(graph, &composed)?;
        let index = self.cached(&composed);
        if !index.has_composition_arc() {
            return Ok(false);
        }
        Ok(matches!(
            index.resolve_field(FieldKey::Instanceable.as_str(), graph, None)?,
            Some(Value::Bool(true))
        ))
    }

    /// Composes `instance`, registers it against its prototype, and materializes
    /// the prototype's index on first use, returning the `(canonical instance,
    /// prototype path)` pair. The first instance registered for a key becomes
    /// canonical and seeds the prototype; later instances with the same key reuse
    /// the already-materialized prototype, so its subtree is composed only once
    /// (spec 11.3.3). Composing the index here (and computing its [`InstanceKey`])
    /// is the cache's job; the dedup is the [`PrototypeRegistry`]'s.
    fn register_prototype(&mut self, graph: &LayerGraph, instance: &Path) -> Result<(Path, Path)> {
        self.ensure_index(graph, instance)?;
        let relative_load_rules = {
            let (rules, relative_instance) = self.scoped_load_rules(instance);
            rules.make_relative_to(&relative_instance)
        };
        let key = instance_key(
            self.cached(instance),
            instance.prim_element_count() as u16,
            relative_load_rules,
        );
        let (canonical, prototype, minted) = self.prototypes.register(key, instance);
        // Materialize the prototype's index only when this call minted it. Before
        // it existed, a query on the deterministic `/__Prototype_N` namespace
        // composed the synthetic path in place (no prototype to redirect to), so
        // an earlier query may have cached stale empty indices and identity
        // redirections anywhere under `/__Prototype_N`. Evict both so descendant
        // queries now redirect to the canonical instance; `materialize_prototype`
        // re-caches the root below. Keying off the mint signal (not
        // `indices.contains_key`) is what makes a stale synthetic index a miss
        // rather than a mistaken hit.
        if minted {
            self.drop_index_subtree(&prototype);
            self.redirected_prims.retain(|path, _| !path.has_prefix(&prototype));
            self.materialize_prototype(graph, &canonical, &prototype);
        }
        Ok((canonical, prototype))
    }

    /// Builds and caches the composed index for a freshly minted prototype root
    /// (`/__Prototype_N`) from the canonical instance's shared subtree (spec
    /// 11.3.3). The clone of the canonical index has its instance-local nodes
    /// inerted at the instance root's own depth, so only the instanceable arc,
    /// its descendants, and the implied classes contribute — the local root
    /// override and the ancestral references above the instanceable arc drop out
    /// — and its namespace is re-anchored onto the prototype root.
    ///
    /// The prototype root's child context is seeded as a namespace root with
    /// `instance_depth` cleared — a prototype root is not an instance (see
    /// [`Self::is_instance`]) — so a descendant built by deepening this graph
    /// composes as prototype content rather than instance-suppressed. Every
    /// instance proxy redirects onto this namespace through
    /// [`Self::redirect_anchor`], so the prototype subtree is the one place a set
    /// of identical instances' descendants compose.
    //
    // TODO(rayon): distinct prototypes (distinct instancing keys) compose
    // independent subtrees, so they can be materialized in parallel. The
    // `Indexer` already takes only `&` references; this needs the cache to build
    // off the `&mut self` path first (compose into per-prototype results, then
    // insert) and the shared `LayerGraph` handed to workers as `&`/`Arc`.
    fn materialize_prototype(&mut self, graph: &LayerGraph, canonical: &Path, prototype: &Path) {
        let mut index = self.cached(canonical).clone();
        let depth = canonical.prim_element_count() as u16;
        index.mark_instance_local_inert(depth, depth);
        // Re-anchor the seeding instance's composed namespace onto the prototype
        // root so the root's own target translation lands in the prototype
        // namespace, not the canonical instance's.
        index.rebase_root(canonical, prototype);

        let (mut context, _) = index.context_for_children(graph, &self.root_parent_context());
        context.instance_depth = None;

        self.cache_index(graph, prototype, index, context, Vec::new(), ExprVarDeps::default());
    }

    /// Returns the synthetic prototype path (`/__Prototype_N`) shared by
    /// `instance`, registering it on first use. `None` when `instance` is not
    /// an instance prim (spec 11.3.3).
    pub(crate) fn prototype_of(&mut self, graph: &LayerGraph, instance: &Path) -> Result<Option<Path>> {
        if !self.is_instance(graph, instance)? {
            return Ok(None);
        }
        Ok(Some(self.register_prototype(graph, instance)?.1))
    }

    /// The instances sharing the prototype at `prototype` (a `/__Prototype_N`
    /// path), sorted by namespace path. Empty for unknown paths.
    pub(crate) fn instances_of(&self, prototype: &Path) -> Vec<Path> {
        self.prototypes.instances_of(prototype)
    }

    /// The registered `/__Prototype_N` roots, in registration order.
    pub(crate) fn prototypes(&self) -> Vec<Path> {
        self.prototypes.roots()
    }

    /// Returns `true` if `path` is a `/__Prototype_N` root.
    pub(crate) fn is_prototype(&self, path: &Path) -> bool {
        self.prototypes.is_root(path)
    }

    /// Returns `true` if `path` lies within a prototype's namespace — i.e. it
    /// has a `/__Prototype_N` ancestor (spec 11.3.3).
    pub(crate) fn is_in_prototype(&self, path: &Path) -> bool {
        self.prototypes.is_in_prototype(path)
    }

    /// Returns the `/__Prototype_N` root enclosing `path` (inclusive of `path`
    /// when it is itself a root), or `None` when `path` is not in a prototype
    /// namespace (spec 11.3.3). Used to gate prototype content against the
    /// population mask through its instances.
    pub(crate) fn prototype_root_of(&self, path: &Path) -> Option<Path> {
        self.prototypes.enclosing_root(Some(path))
    }

    /// The canonical instance's load rules, re-rooted onto the instance's own
    /// path, for the prototype at `root`. `None` when `root` is not a
    /// registered prototype. Used by `IndexCache::scoped_load_rules` to
    /// resolve a `/__Prototype_N` descendant's payload-inclusion decision
    /// against the rules that governed its seeding instance.
    pub(super) fn relative_load_rules_of(&self, root: &Path) -> Option<&LoadRules> {
        self.prototypes.relative_load_rules(root)
    }

    /// The instances sharing the prototype at `root`, borrowed in registration
    /// order for membership checks (e.g. population-mask gating). Empty for a
    /// path that is not a prototype root.
    pub(crate) fn prototype_instances(&self, root: &Path) -> &[Path] {
        self.prototypes.instances_unsorted(root)
    }

    /// Returns `true` if `path` is an instance proxy — a strict descendant of an
    /// instance prim standing in for a prim in that instance's shared prototype
    /// (spec 11.3.3). This holds both in the ordinary instance namespace
    /// (`/A/child`) and inside a prototype namespace under a *nested* instance
    /// (`/__Prototype_N/.../NestedInstance/child`): each has an enclosing
    /// instance. Prototype content not under a nested instance has no enclosing
    /// instance (a prototype root is never one; see [`Self::is_instance`]), so it
    /// is in a prototype, not a proxy.
    ///
    /// A proxy stands in for a real prim in the shared prototype, so a path under
    /// an instance that composes to no prim (e.g. a misspelled child) is not a
    /// proxy — mirroring the existence check on [`Self::is_instance`] /
    /// `Prim::is_valid`.
    pub(crate) fn is_instance_proxy(&mut self, graph: &LayerGraph, path: &Path) -> Result<bool> {
        if path.is_abs_root() || self.is_prototype(path) {
            return Ok(false);
        }
        if self.enclosing_instance(graph, path)?.is_none() {
            return Ok(false);
        }
        self.has_spec(graph, path)
    }

    /// Returns the prim in the shared prototype an instance proxy stands in for:
    /// a proxy `instance/tail` maps to `/__Prototype_N/tail` (spec 11.3.3).
    /// `None` when `path` is not an instance proxy (including a path under an
    /// instance that composes to no prim).
    pub(crate) fn prim_in_prototype(&mut self, graph: &LayerGraph, path: &Path) -> Result<Option<Path>> {
        if !self.is_instance_proxy(graph, path)? {
            return Ok(None);
        }
        let instance = self
            .enclosing_instance(graph, path)?
            .expect("an instance proxy has an enclosing instance");
        let (_canonical, prototype) = self.register_prototype(graph, &instance)?;
        Ok(path.replace_prefix(&instance, &prototype))
    }

    /// Returns the nearest strict ancestor of `path` that resolves as an
    /// instance prim (spec 11.3.3), or `None` when `path` is not inside an
    /// instance.
    //
    // TODO(perf): each [`is_instance`](Self::is_instance) here itself redirects
    // through `effective_path`, which walks back up via this function — so a cold
    // first query on a depth-d path is O(d²) (cheap path/hashmap ops, no extra
    // composition). The `redirected_prims` memo collapses it to O(d) once the
    // ancestors are warm, which a top-down traversal keeps it; a dedicated
    // `is_instance` memo would remove the cold-cache factor entirely.
    fn enclosing_instance(&mut self, graph: &LayerGraph, path: &Path) -> Result<Option<Path>> {
        let mut ancestor = path.parent();
        while let Some(current) = ancestor {
            if current.is_abs_root() {
                break;
            }
            if self.is_instance(graph, &current)? {
                return Ok(Some(current));
            }
            ancestor = current.parent();
        }
        Ok(None)
    }

    /// Maps a prim path to the path that actually composes it. An instance proxy
    /// — a strict descendant of an instance prim — is redirected into the shared
    /// prototype's namespace, so identical instances share one composed subtree
    /// (spec 11.3.3). Other paths — the prototype namespace itself, an instance
    /// root, and non-instanced prims — pass through unchanged.
    fn redirect_prim(&mut self, graph: &LayerGraph, prim: &Path) -> Result<Path> {
        match self.redirect_anchor(graph, prim)? {
            Some((origin, target)) => Ok(prim.replace_prefix(&origin, &target).unwrap_or_else(|| prim.clone())),
            None => Ok(prim.clone()),
        }
    }

    /// Returns the `(origin, target)` prefixes that map `prim`'s queried
    /// namespace onto the shared prototype's composition, or `None` when `prim`
    /// composes in place (spec 11.3.3).
    ///
    /// `prim` redirects onto the nearest enclosing instance's prototype, so
    /// identical instances share one composed subtree. This is uniform across
    /// namespaces: an ordinary instance proxy (`/A/tail` → `/__Prototype_N/tail`,
    /// including the canonical instance's own descendants) and a nested instance
    /// proxy *inside* a prototype (`/__Prototype_0/Nested/tail`, where `Nested`
    /// is itself an instance → the nested prototype) both map onto the prototype
    /// they stand in for.
    ///
    /// A prim with no enclosing instance composes in place: an instance *root*
    /// (spec 11.3.3 lets it override property values), the prototype root and its
    /// plain content (a prototype root is never an instance, so never an enclosing
    /// one; see [`Self::is_instance`] — the shared subtree lives there, composed by
    /// deepening the materialized index), and every non-instanced prim.
    pub(super) fn redirect_anchor(&mut self, graph: &LayerGraph, prim: &Path) -> Result<Option<(Path, Path)>> {
        if let Some(instance) = self.enclosing_instance(graph, prim)? {
            let (_canonical, prototype) = self.register_prototype(graph, &instance)?;
            return Ok(Some((instance, prototype)));
        }
        Ok(None)
    }

    /// Redirects `path` (prim or property) through [`Self::redirect_prim`],
    /// preserving any property suffix. Applied at every descendant-serving
    /// query entry point so an instance proxy's subtree is served from the
    /// shared prototype rather than recomposed per instance.
    ///
    /// The prim-level redirection is memoized in `redirected_prims` (including
    /// the identity result for a non-redirected prim, the common case), so the
    /// ancestor walk that finds an enclosing instance runs once per prim path
    /// rather than once per query; the memo is cleared whenever the prototype
    /// registry is invalidated.
    pub(super) fn effective_path(&mut self, graph: &LayerGraph, path: &Path) -> Result<Path> {
        let prim = path.prim_path();
        let redirected = match self.redirected_prims.get(&prim) {
            Some(hit) => hit.clone(),
            None => {
                let pending_before = self.pending_loads.len();
                let redirected = self.redirect_prim(graph, &prim)?;
                // Only memoize a redirect resolved against fully-loaded indices.
                // If finding the enclosing instance demanded a not-yet-loaded
                // layer, that ancestor read as a non-instance (its index is the
                // empty-on-miss one), so this identity result is provisional;
                // leave it unmemoized for the stage's load loop to recompute once
                // the layer loads and the instance composes.
                if self.pending_loads.len() == pending_before {
                    self.redirected_prims.insert(prim.clone(), redirected.clone());
                }
                redirected
            }
        };
        if redirected == prim {
            return Ok(path.clone());
        }
        // Re-anchor any property suffix onto the redirected prim; for a prim
        // path this is the redirected prim itself.
        Ok(path.replace_prefix(&prim, &redirected).unwrap_or(redirected))
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn path(s: &str) -> Path {
        Path::new(s).expect("valid test path")
    }

    /// A key whose identity is a single tagged selection, enough to drive the
    /// registry's dedup without composing a real index.
    fn key(tag: &str) -> InstanceKey {
        InstanceKey {
            arcs: Vec::new(),
            selections: vec![(tag.to_string(), tag.to_string())],
            load_rules: LoadRules::default(),
        }
    }

    /// `remove_affected` drops only the prototypes whose instances or root the
    /// change set touches, leaving the rest mapped, and re-registration mints a
    /// fresh identity for a dropped prototype.
    #[test]
    fn remove_affected_targets_touched() {
        let mut reg = PrototypeRegistry::default();
        // /A and /B share one prototype; /C has its own.
        let (_, p0, minted0) = reg.register(key("p"), &path("/A"));
        reg.register(key("p"), &path("/B"));
        let (_, p1, minted1) = reg.register(key("q"), &path("/C"));
        assert!(minted0 && minted1);
        assert_ne!(p0, p1);

        // A change under /C touches only its prototype.
        let dropped = reg.remove_affected(&[path("/C/Child")]);
        assert_eq!(dropped, vec![p1.clone()]);
        assert_eq!(reg.canonical_of(&p0), Some(path("/A")));
        assert!(reg.canonical_of(&p1).is_none());

        // Re-registering /C mints a fresh identity (count stays monotonic).
        let (_, p1b, minted) = reg.register(key("q"), &path("/C"));
        assert!(minted);
        assert_ne!(p1b, p1);
    }

    /// An unrelated change leaves every prototype mapping intact.
    #[test]
    fn remove_affected_keeps_unrelated() {
        let mut reg = PrototypeRegistry::default();
        let (_, p0, _) = reg.register(key("p"), &path("/A"));
        let (_, p1, _) = reg.register(key("q"), &path("/C"));

        assert!(reg.remove_affected(&[path("/Extra")]).is_empty());
        assert!(reg.canonical_of(&p0).is_some());
        assert!(reg.canonical_of(&p1).is_some());
    }

    /// A change at an instance's ancestor (or the prototype root itself) is on
    /// the chain, so it invalidates the prototype.
    #[test]
    fn remove_affected_ancestor_and_root() {
        let mut reg = PrototypeRegistry::default();
        let (_, p0, _) = reg.register(key("p"), &path("/Group/A"));

        // The prototype root itself is on the chain.
        assert_eq!(reg.remove_affected(std::slice::from_ref(&p0)), vec![p0.clone()]);

        // Re-register, then touch an ancestor of the instance.
        let (_, p0b, _) = reg.register(key("p"), &path("/Group/A"));
        assert_eq!(reg.remove_affected(&[path("/Group")]), vec![p0b]);
    }
}