openusd 0.5.0

//! Lazily-built cache of per-prim composition indices.
//!
//! The [`IndexCache`] is the primary interface between [`Stage`](crate::usd::Stage)
//! and the composition engine. It caches [`PrimIndex`] results alongside the
//! [`CompositionContext`] that flows from parent prims to children, so ancestor
//! composition is never recomputed.
//!
//! Relocates (`layerRelocates`) are composed by the indexer as `ArcType::Relocate`
//! nodes; the cache applies each node's layer-stack relocates while folding the
//! child-name list (`compute_prim_child_names`), renaming or hiding relocated
//! sources and exposing targets in place.

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

use anyhow::Result;

use crate::ar::ResolvedPath;
use crate::sdf;
use crate::sdf::schema::{ChildrenKey, FieldKey};
use crate::sdf::{AbstractData, Path, SpecType, Value};

use super::clip::ResolvedClipSet;
use super::dependencies::Dependencies;
use super::instancing::PrototypeRegistry;
use super::layer_graph::LayerGraph;
use super::prim_graph::{ArcType, Node, NodeFlags, NodeId};
use super::prim_index::{AncestorArc, CompositionContext, PrimIndex};
use super::prim_resolve::InvalidTargetKind;
use super::relocates::{apply_child_relocates, chain_through_relocates, effective_relocates};
use super::{Error, LayerId, VariantFallbackMap};

/// Lazily-built composition graph.
///
/// Caches per-prim composition indices and contexts. When a prim is queried
/// for the first time, its index is built using the parent's cached context
/// (if available). During depth-first traversal, parents are always composed
/// before children, so the context chain is always populated.
///
/// An optional [`VariantFallbackMap`] provides fallback selections for variant
/// sets that have no authored opinion. Authored selections always take priority;
/// fallbacks are tried in order, and a set with no applicable fallback stays
/// unselected.
///
/// Recoverable composition errors are retained in
/// [`Self::composition_errors`], while operational failures are returned to the
/// caller.
pub struct IndexCache {
    /// Per-prim composition indices, keyed by composed path. `pub(super)` so the
    /// instancing pass ([`super::instancing`]) can read composed indices.
    pub(super) indices: HashMap<Path, PrimIndex>,
    /// Per-prim composition contexts for child propagation.
    contexts: HashMap<Path, CompositionContext>,
    /// Reverse `(layer, site) → prim_index_paths` map for surgical invalidation.
    deps: Dependencies,
    /// Variant fallback selections tried when no authored selection exists.
    variant_fallbacks: VariantFallbackMap,
    /// Lazily-loaded value-clip and manifest layers, keyed by resolved
    /// identifier. Clip layers do not participate in composition (spec
    /// 12.3.4), so they are held here rather than in the [`LayerGraph`](super::layer_graph::LayerGraph).
    clip_layers: HashMap<String, sdf::Layer>,
    /// Shared-prototype registry for scene-graph instancing (spec 11.3.3),
    /// internal machinery driven by the instancing glue in
    /// [`super::instancing`] (a second `impl IndexCache`). Callers go through
    /// the cache's facade methods (`is_instance` / `prototype_of` /
    /// `is_prototype` / …), never this field. Affected entries are dropped by
    /// [`Self::invalidate_prototypes`] on a prim-level change, or the whole
    /// registry by [`Self::clear_all_indices`] on a layer-stack rebuild.
    pub(super) prototypes: PrototypeRegistry,
    /// Memoized instance-proxy / prototype-descendant redirections (spec
    /// 11.3.3): a prim path mapped to the path that actually composes it
    /// ([`effective_path`](Self::effective_path) walks the namespace to find an
    /// enclosing instance, which is otherwise repeated on every descendant
    /// query). A non-redirected prim caches an identity entry, so the common
    /// non-instanced case skips the walk too. An entry holds only while the
    /// prototype registry that produced it is unchanged: it is cleared wholesale
    /// when prototypes are invalidated ([`Self::invalidate_prototypes`] /
    /// [`Self::clear_all_indices`]), and the subtree under a freshly
    /// minted `/__Prototype_N` is dropped at registration (a synthetic
    /// descendant queried before the mint cached an identity that must now
    /// redirect into the prototype namespace).
    //
    // TODO(rayon): a per-prim parallel composition driver would share this map
    // read-mostly; the entries are write-once until invalidation, so a
    // concurrent reader needs only a shared snapshot rather than a lock on the
    // hot path. Keep population off the critical section when that lands.
    pub(super) redirected_prims: HashMap<Path, Path>,
    /// One-shot errors from layer collection that the [`LayerGraph`](super::layer_graph::LayerGraph)
    /// cannot regenerate (e.g. `UnresolvedSublayer`). Set once at construction;
    /// never cleared, since nothing recomputes them.
    collection_errors: Vec<Error>,
    /// Recoverable per-prim build errors, keyed by composed prim path. Replaced
    /// wholesale each time the prim's index is (re)built and dropped when the
    /// index is invalidated, so they always reflect the current composition —
    /// no duplicates across rebuilds, no stale error after a prim is fixed.
    prim_errors: HashMap<Path, Vec<Error>>,
    /// Transient errors produced by on-demand target / property-stack queries
    /// (invalid external targets, inconsistent property types). Cleared on any
    /// index invalidation so they never go stale across an edit; they are
    /// recomputed on the next query.
    //
    // TODO: repeated queries on the same conflicting property re-append within a
    // session (no intervening edit) and duplicate. Settle this by computing the
    // conflicts once at index build and having queries read them.
    query_errors: Vec<Error>,
    /// Paths whose [`ensure_index`](Self::ensure_index) call is still on the
    /// stack. Pre-caching an inherit/specialize target (and that target's own
    /// targets) re-enters `ensure_index`; a cyclic class hierarchy (e.g. two
    /// prims that inherit each other) would otherwise recurse forever before any
    /// of them is inserted into `indices`. Re-entry for an in-progress path
    /// returns early, so the cycle-closing arc simply finds no cached target and
    /// drops out of composition.
    in_progress: HashSet<Path>,
}

enum FieldValue {
    NotAuthored,
    Authored(Option<Value>),
}

/// Collapses the spec sentinels for "no value" ([`Value::ValueBlock`] and
/// [`Value::None`]) to `None`, passing any real value through as `Some`. An
/// authored block stops fall-through to weaker sources yet presents as absent.
fn block_to_none(value: Value) -> Option<Value> {
    match value {
        Value::ValueBlock | Value::None => None,
        other => Some(other),
    }
}

impl IndexCache {
    /// Creates a new composition cache. The layer data lives in a separate
    /// [`LayerGraph`] owned by the [`Stage`](crate::usd::Stage) and passed to each
    /// query. `collection_errors` are the one-shot errors from layer collection
    /// the graph cannot regenerate (e.g. `UnresolvedSublayer`); per-prim build
    /// errors join them as indices are composed. The regenerable layer-graph
    /// diagnostics (sublayer cycles, invalid relocates) live on the
    /// [`LayerGraph`] and are read through [`LayerGraph::errors`].
    pub(crate) fn new(variant_fallbacks: VariantFallbackMap, collection_errors: Vec<Error>) -> Self {
        Self {
            indices: HashMap::new(),
            contexts: HashMap::new(),
            deps: Dependencies::default(),
            variant_fallbacks,
            clip_layers: HashMap::new(),
            prototypes: PrototypeRegistry::default(),
            redirected_prims: HashMap::new(),
            collection_errors,
            prim_errors: HashMap::new(),
            query_errors: Vec::new(),
            in_progress: HashSet::new(),
        }
    }

    /// Returns the recoverable composition errors encountered so far: the
    /// one-shot collection errors, the current per-prim build errors, and the
    /// transient query errors.
    pub(crate) fn composition_errors(&self) -> Vec<Error> {
        self.collection_errors
            .iter()
            .chain(self.prim_errors.values().flatten())
            .chain(&self.query_errors)
            .cloned()
            .collect()
    }

    #[cfg(test)]
    fn take_composition_errors(&mut self) -> Vec<Error> {
        let errors = self.composition_errors();
        self.collection_errors.clear();
        self.prim_errors.clear();
        self.query_errors.clear();
        errors
    }

    /// Loads a value-clip or manifest layer referenced by `asset_path`,
    /// anchored to the layer `anchor_layer` (the layer that authored the
    /// clip metadata). Layers are loaded on demand through the graph's
    /// resolver and cached by resolved identifier; clip layers never enter the
    /// composition [`LayerGraph`] (spec 12.3.4).
    ///
    /// Returns `Ok(None)` when the asset path cannot be resolved.
    pub(crate) fn clip_layer(
        &mut self,
        graph: &LayerGraph,
        asset_path: &str,
        anchor_layer: LayerId,
    ) -> Result<Option<&sdf::Layer>> {
        // Anchor the clip asset path to the authoring layer's location so
        // relative paths resolve like any other dependency.
        let anchor = graph.anchor_location(Some(anchor_layer));
        let clip_id = graph.resolver().create_identifier(asset_path, anchor.as_ref());

        if !self.clip_layers.contains_key(&clip_id) {
            let resolver = graph.resolver();
            let Some(resolved) = resolver.resolve(&clip_id) else {
                return Ok(None);
            };
            let data = crate::layer::open_layer(resolver, &resolved)?;
            self.clip_layers
                .insert(clip_id.clone(), sdf::Layer::new(clip_id.clone(), data));
        }

        Ok(self.clip_layers.get(&clip_id))
    }

    /// Resolves an attribute's value at `time`, honoring value clips
    /// (spec 12.3.4). Strength ordering:
    ///
    /// 1. Local (`Root` arc) `timeSamples` win over clips.
    /// 2. Value clips anchored on the attribute's prim or an ancestor.
    /// 3. The strongest remaining `timeSamples` (across reference/payload arcs).
    /// 4. The strongest authored `default`.
    ///
    /// `interp` applies the stage's interpolation policy to a sample map at a
    /// given time; it is supplied by the caller so this layer stays free of any
    /// interpolation policy.
    pub(crate) fn value_at(
        &mut self,
        graph: &LayerGraph,
        attr_path: &Path,
        time: f64,
        interp: &dyn Fn(&sdf::TimeSampleMap, f64) -> Option<Value>,
    ) -> Result<Option<Value>> {
        let attr_path = &self.effective_path(graph, attr_path)?;
        if !self.has_spec_at(graph, attr_path)? {
            return Ok(None);
        }

        let prim = attr_path.prim_path();
        let suffix = attr_path.property_suffix().to_owned();
        let local_layers = graph.local_layers();

        self.ensure_index(graph, &prim)?;

        // TODO: only the default-sourced returns below resolve their `asset`
        // values (via `anchor_asset_paths`); values from time samples
        // (`resolve_local_time_samples` / `resolve_time_samples`) and value
        // clips (`resolve_clip_value`) are returned with `evaluated_path` and
        // `resolved_path` unset. To close this, those resolvers must surface the
        // contributing layer/node so it can be anchored and its expression
        // variables composed — note a clip value anchors against the *clip
        // layer*, not a host-stack opinion, so it cannot reuse `asset_context`
        // directly. Asset-valued time samples and clips are rare in practice.

        // 1) Local time samples take precedence over clip data.
        if let Some(samples) = self.indices[&prim].resolve_local_time_samples(graph, Some(&suffix), &local_layers)? {
            return Ok(interp(&samples, time));
        }

        // 2) Local defaults also take precedence over clip data.
        if let FieldValue::Authored(value) =
            self.resolve_local_field_value(graph, &prim, &suffix, FieldKey::Default.as_str(), &local_layers)?
        {
            return Ok(self.anchor_asset_paths(graph, &prim, FieldKey::Default.as_str(), Some(&suffix), value));
        }

        // 3) Value clips, anchored on this prim or an ancestor. A clip set that
        //    owns the attribute resolves it authoritatively: an authored value
        //    block stops fall-through to weaker sources but presents as `None`,
        //    matching the local-default handling above and the default below.
        if let Some(value) = self.resolve_clip_value(graph, &prim, &suffix, time, interp)? {
            return Ok(block_to_none(value));
        }

        // 4) Remaining time samples (reference/payload arcs), retimed.
        if let Some(samples) = self.indices[&prim].resolve_time_samples(graph, Some(&suffix))? {
            return Ok(interp(&samples, time));
        }

        // 5) Fall back to the strongest authored default.
        let default = self.indices[&prim].resolve_field(FieldKey::Default.as_str(), graph, Some(&suffix))?;
        let default = self.anchor_asset_paths(graph, &prim, FieldKey::Default.as_str(), Some(&suffix), default);
        Ok(default.and_then(block_to_none))
    }

    fn resolve_local_field_value(
        &self,
        graph: &LayerGraph,
        prim: &Path,
        suffix: &str,
        field: &str,
        local_layers: &HashSet<LayerId>,
    ) -> Result<FieldValue> {
        let Some(index) = self.indices.get(prim) else {
            return Ok(FieldValue::NotAuthored);
        };

        for node in index.nodes() {
            let query_path = Path::new(&format!("{}{suffix}", node.path))?;
            for (layer, _) in node.layers() {
                if !local_layers.contains(&layer) {
                    continue;
                }
                let Some(value) = graph.layer(layer).try_get(&query_path, field)? else {
                    continue;
                };
                return Ok(FieldValue::Authored(block_to_none(value.into_owned())));
            }
        }

        Ok(FieldValue::NotAuthored)
    }

    /// Resolves a clip value for `attr_path` at `time` by searching the
    /// attribute's prim and then its ancestors, nearest first — a nearer clip
    /// set overrides one on an ancestor (spec 12.3.4.5).
    fn resolve_clip_value(
        &mut self,
        graph: &LayerGraph,
        attr_prim: &Path,
        suffix: &str,
        time: f64,
        interp: &dyn Fn(&sdf::TimeSampleMap, f64) -> Option<Value>,
    ) -> Result<Option<Value>> {
        let mut anchor_prim = attr_prim.clone();
        loop {
            if let Some(value) = self.clip_value_at(graph, &anchor_prim, attr_prim, suffix, time, interp)? {
                return Ok(Some(value));
            }
            match anchor_prim.parent() {
                Some(parent) if !parent.is_abs_root() => anchor_prim = parent,
                _ => return Ok(None),
            }
        }
    }

    /// Looks for a clip set anchored on `anchor_prim` that provides a value for
    /// the attribute `attr_prim + suffix` at `time`. Returns the interpolated
    /// clip value, or `None` when no applicable clip set is found.
    fn clip_value_at(
        &mut self,
        graph: &LayerGraph,
        anchor_prim: &Path,
        attr_prim: &Path,
        suffix: &str,
        time: f64,
        interp: &dyn Fn(&sdf::TimeSampleMap, f64) -> Option<Value>,
    ) -> Result<Option<Value>> {
        // Gather the clip sets, then drop the index borrow so
        // clip layers can be loaded through `&mut self`.
        let sets = {
            self.ensure_index(graph, anchor_prim)?;
            let index = &self.indices[anchor_prim];
            let sets = index.resolve_clip_sets(graph)?;
            if sets.is_empty() {
                return Ok(None);
            }
            sets
        };

        // Path of the attribute relative to the clip anchor prim (empty when
        // the clip set is authored on the attribute's own prim).
        let relative = &attr_prim.as_str()[anchor_prim.as_str().len()..];

        for resolved in &sets {
            let set = &resolved.set;
            let base = set.prim_path.clone().unwrap_or_else(|| anchor_prim.clone());
            let clip_path = Path::new(&format!("{base}{relative}{suffix}"))?;

            // Resolve the manifest once: its declaration gates the set and its
            // default later fills a gap (spec 12.3.4.6).
            let manifest = set
                .manifest_asset
                .as_deref()
                .map(|asset| (asset, resolved.manifest_layer.unwrap_or(resolved.asset_layer)));

            // A manifest, when authored, declares which attributes the clips
            // provide. A set whose manifest does not declare this attribute is
            // skipped. A set that *does* declare it owns the attribute's
            // time-varying value (spec 12.3.4.6): a gap in the active clip
            // resolves to a manifest default or a value block, never to a
            // weaker value source.
            let manifest_declared = match manifest {
                Some((asset, layer)) => {
                    let declared = match self.clip_layer(graph, asset, layer)? {
                        Some(opened) => opened.data().has_spec(&clip_path),
                        None => false,
                    };
                    if !declared {
                        continue;
                    }
                    true
                }
                None => false,
            };

            let Some(active) = set.active_clip(time) else {
                continue;
            };
            let Some(asset) = set.asset_paths.get(active) else {
                continue;
            };
            let clip_time = set.map_stage_to_clip(time);

            if let Some(value) =
                self.clip_sample_at(graph, asset, resolved.asset_layer, &clip_path, clip_time, interp)?
            {
                return Ok(Some(value));
            }

            // The active clip has no sample at `clip_time`. Only a
            // manifest-declared attribute gets the gap-filling treatment;
            // without a manifest there is no assurance this set owns the
            // attribute, so fall through to weaker value sources.
            if !manifest_declared {
                continue;
            }

            // (a) Manifest default: synthesize a sample at the clip's active
            //     time (spec 12.3.4.6). Reached only when the manifest declared
            //     the attribute, so the manifest asset is authored.
            if let Some((asset, layer)) = manifest {
                if let Some(value) = self.manifest_default(graph, asset, layer, &clip_path)? {
                    return Ok(Some(value));
                }
            }

            // (b) interpolateMissingClipValues: interpolate the gap across the
            //     nearest surrounding clips (spec 12.3.4.7).
            if set.interpolate_missing {
                if let Some(value) = self.interpolate_missing_value(graph, resolved, &clip_path, time, interp)? {
                    return Ok(Some(value));
                }
            }

            // (c) No default and nothing to interpolate: the manifest-declared
            //     attribute is authoritatively absent — a value block — which
            //     must not fall through to weaker sources (spec 12.3.4.6).
            return Ok(Some(Value::ValueBlock));
        }

        Ok(None)
    }

    /// Reads the time samples for `clip_path` from a single clip layer and
    /// interpolates at `clip_time`. Returns `None` when the layer is
    /// unresolved or the attribute has no time samples there.
    fn clip_sample_at(
        &mut self,
        graph: &LayerGraph,
        asset: &str,
        anchor_layer: LayerId,
        clip_path: &Path,
        clip_time: f64,
        interp: &dyn Fn(&sdf::TimeSampleMap, f64) -> Option<Value>,
    ) -> Result<Option<Value>> {
        let samples = match self.clip_layer(graph, asset, anchor_layer)? {
            Some(layer) => match layer.data().try_get(clip_path, FieldKey::TimeSamples.as_str())? {
                Some(value) => match value.into_owned() {
                    Value::TimeSamples(samples) => Some(samples),
                    _ => None,
                },
                None => None,
            },
            None => None,
        };
        Ok(samples.and_then(|samples| interp(&samples, clip_time)))
    }

    /// Reads the manifest's authored `default` for `clip_path` (spec 12.3.4.6):
    /// when the active clip has a gap, the manifest default stands in as the
    /// sample value. Returns `None` when the manifest is unresolved or holds no
    /// usable default for the attribute.
    fn manifest_default(
        &mut self,
        graph: &LayerGraph,
        manifest: &str,
        manifest_layer: LayerId,
        clip_path: &Path,
    ) -> Result<Option<Value>> {
        let value = match self.clip_layer(graph, manifest, manifest_layer)? {
            Some(layer) => layer
                .data()
                .try_get(clip_path, FieldKey::Default.as_str())?
                .map(|value| value.into_owned()),
            None => None,
        };
        Ok(value.and_then(block_to_none))
    }

    /// Fills a gap in the active clip by interpolating across the nearest
    /// surrounding clips that contribute a value (spec 12.3.4.7). Each
    /// contributing clip is anchored on the stage timeline at the active stage
    /// time it owns and valued by its sample there; `interp` then brackets
    /// `time` between the nearest such anchors, exactly as if the clips' samples
    /// formed one virtual sample map. The forward bracket is the next
    /// contributing clip's start time and the backward bracket the previous
    /// one's, matching the C++ resolver. When only one side contributes, its
    /// value is held across the gap.
    fn interpolate_missing_value(
        &mut self,
        graph: &LayerGraph,
        resolved: &ResolvedClipSet,
        clip_path: &Path,
        time: f64,
        interp: &dyn Fn(&sdf::TimeSampleMap, f64) -> Option<Value>,
    ) -> Result<Option<Value>> {
        let set = &resolved.set;
        let anchor = resolved.asset_layer;
        // Position of the active clip among the `active` entries at `time`.
        let active_pos = set.active.iter().rposition(|&(stage, _)| stage <= time).unwrap_or(0);

        // Forward: nearest later clip that contributes, anchored at its start.
        let mut upper = None;
        for &(stage, idx) in set.active.iter().skip(active_pos + 1) {
            if let Some(asset) = set.asset_paths.get(idx) {
                let clip_time = set.map_stage_to_clip(stage);
                if let Some(value) = self.clip_sample_at(graph, asset, anchor, clip_path, clip_time, interp)? {
                    upper = Some((stage, value));
                    break;
                }
            }
        }

        // Backward: nearest earlier clip that contributes, anchored at its start.
        let mut lower = None;
        for &(stage, idx) in set.active[..active_pos].iter().rev() {
            if let Some(asset) = set.asset_paths.get(idx) {
                let clip_time = set.map_stage_to_clip(stage);
                if let Some(value) = self.clip_sample_at(graph, asset, anchor, clip_path, clip_time, interp)? {
                    lower = Some((stage, value));
                    break;
                }
            }
        }

        Ok(match (lower, upper) {
            (Some((lt, lv)), Some((ut, uv))) => interp(&vec![(lt, lv), (ut, uv)], time),
            (Some((_, value)), None) | (None, Some((_, value))) => Some(value),
            (None, None) => None,
        })
    }

    /// Read-only access to the dependency map for change-driven invalidation.
    pub(super) fn dependencies(&self) -> &Dependencies {
        &self.deps
    }

    /// Returns `true` if a composed prim index is currently cached at `path`.
    pub fn is_indexed(&self, path: &Path) -> bool {
        self.indices.contains_key(path)
    }

    /// Number of cached prim indices.
    pub fn indexed_count(&self) -> usize {
        self.indices.len()
    }

    /// Caches a fully composed `index` at `path` with its child `context` and
    /// registers its dependencies. The single insertion point for the cache's
    /// three per-prim maps, shared by the ordinary [`build_index`](Self::build_index)
    /// path and the materialized-prototype path (which has no spec to build from).
    pub(super) fn cache_index(
        &mut self,
        graph: &LayerGraph,
        path: &Path,
        index: PrimIndex,
        context: CompositionContext,
    ) {
        self.deps.add(path, &index, graph.all_ids());
        self.indices.insert(path.clone(), index);
        self.contexts.insert(path.clone(), context);
    }

    /// The composition context for a namespace-root prim: empty except for the
    /// stage's variant fallbacks. Used to seed the root of an ordinary build and
    /// of a materialized prototype.
    pub(super) fn root_parent_context(&self) -> CompositionContext {
        CompositionContext {
            variant_fallbacks: self.variant_fallbacks.clone(),
            ..Default::default()
        }
    }

    /// Drop a single prim's cached index, context, dependency, and error
    /// entries. The transient query errors are cleared too — they may reference
    /// the dropped prim and are recomputed on the next query.
    pub(super) fn drop_index(&mut self, path: &Path) {
        self.indices.remove(path);
        self.contexts.remove(path);
        self.deps.remove(path);
        self.prim_errors.remove(path);
        self.query_errors.clear();
    }

    /// Drop a prim's cached index and every namespace descendant. Used by
    /// [`change::Changes`](super::change::Changes) when a significant change
    /// touches `prefix` — the topology may have changed for the entire
    /// subtree, so every dependent index is invalidated.
    ///
    /// Uses `HashMap::retain` so the prefix scan and removal happen in a
    /// single pass, capturing victims into a small `Vec` only to forward to
    /// the dependency map (which has no `retain` of its own).
    //
    // TODO: replace the `has_prefix` scan with an `SdfPathTable`-like trie
    // (`FindSubtreeRange` in C++). The current shape is O(n) per
    // invalidation, fine while index counts are modest but the wrong
    // long-term primitive.
    pub(super) fn drop_index_subtree(&mut self, prefix: &Path) {
        // `Path::has_prefix("")` returns `true` for every absolute path, so
        // a default-constructed `Path` would silently wipe the entire
        // cache without any layer-stack rebuild — almost certainly a
        // caller bug. Catch it loudly in debug builds; the absolute root
        // (`/`) is the legitimate "blow everything" prefix.
        debug_assert!(
            !prefix.is_empty(),
            "drop_index_subtree called with empty prefix — use Path::abs_root() to drop everything",
        );
        let mut victims: Vec<Path> = Vec::new();
        self.indices.retain(|p, _| {
            if p.has_prefix(prefix) {
                victims.push(p.clone());
                false
            } else {
                true
            }
        });
        for v in &victims {
            self.contexts.remove(v);
            self.deps.remove(v);
            self.prim_errors.remove(v);
        }
        self.query_errors.clear();
    }

    /// Drop every cached index, context, and dependency entry — plus the
    /// shared-prototype registry and its redirection memo — without touching the
    /// layer stack's precomputed state. Use this for a layer-stack rebuild, where
    /// every cached prim must be re-evaluated; clearing the registry here (rather
    /// than dropping each `/__Prototype_N` subtree first) avoids re-scanning the
    /// cache per prototype only to wipe it wholesale.
    pub(super) fn clear_all_indices(&mut self) {
        self.indices.clear();
        self.contexts.clear();
        self.deps.clear();
        self.prim_errors.clear();
        self.query_errors.clear();
        self.prototypes.clear();
        self.redirected_prims.clear();
    }

    /// Returns `true` if any layer has a spec at the given composed path.
    ///
    /// For property paths (e.g. `/Prim.attr`), checks whether the property
    /// exists in any layer contributing to the owning prim's composition index.
    pub fn has_spec(&mut self, graph: &LayerGraph, path: &Path) -> Result<bool> {
        let path = &self.effective_path(graph, path)?;
        self.has_spec_at(graph, path)
    }

    /// Resolves a value over the composition nodes of a property's owning prim,
    /// strongest first, reading each contributing layer live. `path` must be a
    /// property path: it is re-anchored onto each node's prim (crossing the
    /// `.` separator) and `probe` is called with that node's layer and the
    /// re-anchored property path; the first `Some` wins.
    ///
    /// Reading live — rather than from a property-keyed index — keeps results
    /// correct after a property spec is authored, since authoring a property
    /// never reshapes the owning prim's composition graph (the prim index
    /// stays valid).
    fn find_property_node<T>(
        &mut self,
        graph: &LayerGraph,
        path: &Path,
        mut probe: impl FnMut(&sdf::Layer, &Path) -> Option<T>,
    ) -> Result<Option<T>> {
        let prim_path = path.prim_path();
        self.ensure_index(graph, &prim_path)?;
        let Some(index) = self.indices.get(&prim_path) else {
            return Ok(None);
        };
        for node in index.nodes() {
            let Some(prop_path) = path.replace_prefix(&prim_path, &node.path) else {
                continue;
            };
            for (layer, _) in node.layers() {
                if let Some(found) = probe(graph.layer(layer), &prop_path) {
                    return Ok(Some(found));
                }
            }
        }
        Ok(None)
    }

    /// Like [`Self::has_spec`], but assumes `path` has already been redirected
    /// through [`Self::effective_path`]. Callers that redirected the path
    /// themselves (e.g. [`Self::value_at`]) use this to avoid redirecting twice.
    fn has_spec_at(&mut self, graph: &LayerGraph, path: &Path) -> Result<bool> {
        if path.is_property_path() {
            return Ok(self
                .find_property_node(graph, path, |layer, p| layer.has_spec(p).then_some(()))?
                .is_some());
        }
        self.ensure_index(graph, path)?;
        Ok(self.indices.get(path).is_some_and(|idx| !idx.is_empty()))
    }

    /// Returns the spec type at a composed path from the strongest contributing layer.
    ///
    /// For a property path the type is read live from the owning prim's
    /// composition nodes (see [`Self::find_property_node`]) rather than from a
    /// property-keyed index, so a property spec added after this path was first
    /// queried is picked up instead of a stale cached `None`.
    pub fn spec_type(&mut self, graph: &LayerGraph, path: &Path) -> Result<Option<SpecType>> {
        let path = &self.effective_path(graph, path)?;
        if path.is_property_path() {
            return self.find_property_node(graph, path, |layer, p| layer.spec_type(p));
        }
        self.ensure_index(graph, path)?;
        let Some(index) = self.indices.get(path) else {
            return Ok(None);
        };
        for node in index.nodes() {
            for (layer, _) in node.layers() {
                if let Some(ty) = graph.layer(layer).spec_type(&node.path) {
                    return Ok(Some(ty));
                }
            }
        }
        Ok(None)
    }

    /// Returns `true` if the layer at `layer` authors `field` at `path`. Used
    /// by change classification to detect, for an inert spec add, whether the
    /// new spec carries a field (e.g. `instanceable`) that reshapes
    /// composition.
    pub(super) fn layer_authors_field(&self, graph: &LayerGraph, layer: LayerId, path: &Path, field: &str) -> bool {
        graph
            .get(layer)
            .is_some_and(|node| node.layer.data().has_field(path, field))
    }

    /// Returns `true` if the composed prim index contains any non-local arc.
    pub(crate) fn has_composition_arc(&mut self, graph: &LayerGraph, path: &Path) -> Result<bool> {
        self.ensure_index(graph, path)?;
        Ok(self.indices.get(path).is_some_and(|index| index.has_composition_arc()))
    }

    /// Resolves a field value from the strongest opinion across all composition nodes.
    ///
    /// Layer metadata authored on the pseudo-root is resolved directly from
    /// the root layer and does not compose with sublayers or arcs. The
    /// pseudo-root's `primChildren` field remains a child-list query and is
    /// handled by normal composition.
    pub fn resolve_field(&mut self, graph: &LayerGraph, path: &Path, field: &str) -> Result<Option<Value>> {
        let path = &self.effective_path(graph, path)?;
        if path.is_abs_root() && field != ChildrenKey::PrimChildren.as_str() {
            return self.root_layer_field(graph, field);
        }

        if path.is_property_path() {
            let prim_path = path.prim_path();
            let prop_suffix = path.property_suffix();
            self.ensure_index(graph, &prim_path)?;
            let value = self.indices[&prim_path].resolve_field(field, graph, Some(prop_suffix))?;
            Ok(self.anchor_asset_paths(graph, &prim_path, field, Some(prop_suffix), value))
        } else {
            self.ensure_index(graph, path)?;
            let value = self.indices[path].resolve_field(field, graph, None)?;
            Ok(self.anchor_asset_paths(graph, path, field, None, value))
        }
    }

    /// Fills the resolved path on any `asset` / `asset[]` value just resolved,
    /// anchoring each authored path against the layer of the strongest opinion
    /// (C++ `UsdStage::_MakeResolvedAssetPaths`). Non-asset values pass through;
    /// asset paths nested inside a dictionary value are not recursed into, only
    /// top-level `asset` / `asset[]` fields are resolved.
    ///
    /// TODO(perf): each asset read re-runs `Resolver::resolve` (a filesystem
    /// hit); a per-(layer, path) resolution cache would avoid repeating it.
    fn anchor_asset_paths(
        &self,
        graph: &LayerGraph,
        prim_path: &Path,
        field: &str,
        prop_suffix: Option<&str>,
        value: Option<Value>,
    ) -> Option<Value> {
        match value? {
            Value::AssetPath(asset) => {
                let needs_expr = sdf::expr::is_expression(asset.as_str());
                let (anchor, vars) = self.asset_context(graph, prim_path, field, prop_suffix, needs_expr);
                Some(Value::AssetPath(Self::resolve_asset_path(
                    graph,
                    asset,
                    anchor.as_ref(),
                    &vars,
                )))
            }
            Value::AssetPathVec(assets) => {
                let needs_expr = assets.iter().any(|a| sdf::expr::is_expression(a.as_str()));
                let (anchor, vars) = self.asset_context(graph, prim_path, field, prop_suffix, needs_expr);
                let resolved = assets
                    .into_iter()
                    .map(|asset| Self::resolve_asset_path(graph, asset, anchor.as_ref(), &vars))
                    .collect();
                Some(Value::AssetPathVec(resolved))
            }
            other => Some(other),
        }
    }

    /// The inputs for resolving `field`'s asset value, taken from its strongest
    /// opinion: the resolved location of that opinion's layer (the anchor for a
    /// relative path) and, when `needs_expr` is set, the `expressionVariables`
    /// in scope at that opinion's node. Computed once so every element of an
    /// `asset[]` reuses it; the variables are read only when an authored path
    /// is actually an expression.
    fn asset_context(
        &self,
        graph: &LayerGraph,
        prim_path: &Path,
        field: &str,
        prop_suffix: Option<&str>,
        needs_expr: bool,
    ) -> (Option<ResolvedPath>, HashMap<String, Value>) {
        let Some(index) = self.indices.get(prim_path) else {
            return (None, HashMap::new());
        };
        let Some((layer, node)) = index.strongest_opinion(field, graph, prop_suffix) else {
            return (None, HashMap::new());
        };
        let anchor = graph.anchor_location(Some(layer));
        let vars = if needs_expr {
            index.composed_expr_vars(node, graph)
        } else {
            HashMap::new()
        };
        (anchor, vars)
    }

    /// Resolves `asset` against `anchor` (its source layer's resolved location)
    /// and returns it with the evaluated and resolved paths recorded.
    ///
    /// A variable expression is evaluated against `expr_vars` to the path used
    /// as input to resolution (C++ `SdfAssetPath::GetAssetPath`); a malformed
    /// or non-string expression leaves both derived paths unset. Resolution
    /// owns the derived paths: the result is rebuilt from the authored path so
    /// any prior evaluated/resolved path is discarded.
    ///
    /// TODO: a failed expression is dropped silently, unlike a reference/payload
    /// arc asset-path expression which records `Error::InvalidExpression`
    /// (`prim_index::resolve_arc_asset_path`). Surfacing it needs an error
    /// channel through value resolution (`value_at` returns `Result<Option>` but
    /// this runs after the value is produced).
    fn resolve_asset_path(
        graph: &LayerGraph,
        asset: sdf::AssetPath,
        anchor: Option<&ResolvedPath>,
        expr_vars: &HashMap<String, Value>,
    ) -> sdf::AssetPath {
        let mut asset = sdf::AssetPath::new(asset.into_string());
        if asset.is_empty() {
            return asset;
        }
        // The per-element `is_expression` is load-bearing for `asset[]`: the
        // caller's `needs_expr` is true if *any* element is an expression, so a
        // plain element in a mixed array must still skip evaluation.
        let identifier = if sdf::expr::is_expression(asset.as_str()) {
            let Ok(evaluated) = sdf::expr::evaluate_asset_path(asset.as_str(), expr_vars) else {
                return asset;
            };
            let identifier = graph.resolver().create_identifier(&evaluated, anchor);
            asset.set_evaluated_path(evaluated);
            identifier
        } else {
            graph.resolver().create_identifier(asset.as_str(), anchor)
        };
        if let Some(resolved) = graph.resolver().resolve(&identifier) {
            asset.set_resolved_path(resolved.to_string_lossy().into_owned());
        }
        asset
    }

    /// Returns the composed `apiSchemas` list for a prim.
    pub fn api_schemas(&mut self, graph: &LayerGraph, path: &Path) -> Result<Vec<String>> {
        let path = self.effective_path(graph, &path.prim_path())?;
        self.ensure_index(graph, &path)?;
        self.indices[&path].resolve_token_list_op(FieldKey::ApiSchemas, graph, None)
    }

    /// Returns the composed `connectionPaths` list for an attribute path,
    /// folding list-op edits (prepend / append / add / delete) across every
    /// contributing layer. Non-property paths trivially return an empty list.
    pub fn connection_paths(&mut self, graph: &LayerGraph, path: &Path) -> Result<Vec<Path>> {
        self.property_targets(graph, path, FieldKey::ConnectionPaths)
    }

    /// Returns the composed raw `targetPaths` list for a relationship path,
    /// folding list-op edits (prepend / append / add / delete) across every
    /// contributing layer. Non-property paths trivially return an empty list.
    ///
    /// These are the raw targets (the resolved `targetPaths` list op, spec
    /// 12.4); target forwarding — recursively chasing relationship-to-
    /// relationship chains — is not applied here.
    pub fn relationship_targets(&mut self, graph: &LayerGraph, path: &Path) -> Result<Vec<Path>> {
        self.property_targets(graph, path, FieldKey::TargetPaths)
    }

    /// Returns the forwarded `targetPaths` for a relationship (spec 12.4):
    /// a target that resolves to a relationship is replaced, recursively, by
    /// that relationship's own forwarded targets. Every other target is kept
    /// as-is — prim paths, attribute paths, and any target that does not
    /// resolve to a relationship (a dangling or unloaded path). This matches
    /// C++ `UsdRelationship::GetForwardedTargets`, which forwards only through
    /// live relationships. Cycles are broken (each relationship is followed
    /// once) and duplicates collapse, keeping first occurrence.
    ///
    /// The walk uses an explicit stack rather than recursion (mirroring
    /// [`crate::usd::ConnectionGraph::resolve_chain`]) so a deep relationship
    /// chain cannot overflow the call stack.
    ///
    /// `is_populated` reports whether a prim is inside the stage's working set.
    /// A target relationship on a prim outside the set is not followed — its
    /// raw targets would be empty under the population mask anyway — so the
    /// forwarded result never leaks scene the mask excludes (it stays
    /// consistent with [`Self::relationship_targets`] on that path).
    pub fn forwarded_relationship_targets(
        &mut self,
        graph: &LayerGraph,
        path: &Path,
        is_populated: &dyn Fn(&Path) -> bool,
    ) -> Result<Vec<Path>> {
        let mut out = Vec::new();
        let mut emitted = HashSet::new();
        let mut followed = HashSet::new();
        followed.insert(path.clone());

        // Seed with the queried relationship's raw targets. Targets are pushed
        // reversed so the strongest (first) target is popped and resolved
        // first, preserving authored order in `out`.
        let mut stack: Vec<Path> = self.relationship_targets(graph, path)?.into_iter().rev().collect();
        while let Some(target) = stack.pop() {
            // Only property targets can be relationships; a prim-path target is
            // always terminal. Classify property targets by composed spec type.
            let is_relationship =
                target.is_property_path() && matches!(self.spec_type(graph, &target)?, Some(SpecType::Relationship));
            if is_relationship {
                // Don't follow a relationship the mask excludes; a masked-out
                // prim contributes no composed targets.
                if !is_populated(&target.prim_path()) {
                    continue;
                }
                if !followed.insert(target.clone()) {
                    continue; // already followed — break the cycle
                }
                stack.extend(self.relationship_targets(graph, &target)?.into_iter().rev());
            } else if emitted.insert(target.clone()) {
                out.push(target);
            }
        }
        Ok(out)
    }

    /// Composes a path-list-op property field (`connectionPaths` or
    /// `targetPaths`) by folding list-op edits across every contributing layer
    /// and mapping targets through composition arcs into the stage namespace.
    /// Both fields follow generic list-op value resolution (spec 12.2.6).
    fn property_targets(&mut self, graph: &LayerGraph, path: &Path, field: FieldKey) -> Result<Vec<Path>> {
        self.compose_property_paths(graph, path, field, false)
    }

    /// Composes a path-list-op property field into stage namespace. With
    /// `deleted` it returns the field's deleted entries (the `delete`-op paths);
    /// otherwise the resolved targets/connections. On an instance proxy both
    /// resolve against the shared prototype's subtree and map the
    /// prototype-namespace results back to the queried instance (spec 11.3.4
    /// under 11.3.3).
    fn compose_property_paths(
        &mut self,
        graph: &LayerGraph,
        path: &Path,
        field: FieldKey,
        deleted: bool,
    ) -> Result<Vec<Path>> {
        if !path.is_property_path() {
            return Ok(Vec::new());
        }
        let prim = path.prim_path();
        let prop_suffix = path.property_suffix().to_owned();
        let anchor = self.redirect_anchor(graph, &prim)?;

        let resolved_prim = match &anchor {
            Some((origin, canonical)) => prim.replace_prefix(origin, canonical).unwrap_or_else(|| prim.clone()),
            None => prim.clone(),
        };
        self.ensure_index(graph, &resolved_prim)?;
        // A connection/relationship target authored in a class that translates but
        // names a different instance of that class is dropped from that class
        // node's contribution (C++ `_TargetInClassAndTargetsInstance`). The cache
        // precomputes the cross-prim instance set; the per-node target walk
        // consults it so a valid stronger opinion for the same path survives.
        let instance_targets = if deleted {
            HashSet::new()
        } else {
            self.compute_instance_targets(graph, &resolved_prim, field, &prop_suffix)?
        };

        // The resolved-targets walk translates each target through its
        // contributing node's map (relocates folded in), so it needs no separate
        // relocate-chaining. The deleted-paths walk has no per-node origin, so it
        // still chains every entry through the prim's effective relocates.
        let index = &self.indices[&resolved_prim];
        let (mut targets, invalid) = if deleted {
            (
                index.resolve_path_list_op_deleted(field, graph, Some(&prop_suffix))?,
                Vec::new(),
            )
        } else {
            index.resolve_path_list_op_validated(field, graph, Some(&prop_suffix), &instance_targets)?
        };
        if deleted && graph.has_relocates() {
            let relocates = effective_relocates(graph, &resolved_prim, &self.indices);
            for target in &mut targets {
                *target = chain_through_relocates(target, &relocates, None);
            }
        }

        // Targets dropped during composition are reported in authored order, the
        // `invalid` list already honoring list-op composition (a target shadowed
        // by a stronger explicit, or retracted by a delete, is not reported).
        let is_connection = matches!(field, FieldKey::ConnectionPaths);
        for inv in invalid {
            self.query_errors.push(match inv.kind {
                InvalidTargetKind::External => Error::InvalidExternalTargetPath {
                    is_connection,
                    target: inv.target,
                    property: inv.property,
                    layer: graph.identifier(inv.layer).to_string(),
                    arc: inv.arc,
                    arc_root: inv.arc_root,
                    composing: prim.clone(),
                },
                InvalidTargetKind::Instance => Error::InvalidInstanceTargetPath {
                    is_connection,
                    target: inv.target,
                    property: inv.property,
                    layer: graph.identifier(inv.layer).to_string(),
                    composing: prim.clone(),
                },
            });
        }

        // Targets resolved in the shared prototype's namespace map back to the
        // queried instance (spec 11.3.4 under 11.3.3).
        if let Some((origin, target_prefix)) = &anchor {
            for target in &mut targets {
                if let Some(remapped) = target.replace_prefix(target_prefix, origin) {
                    *target = remapped;
                }
            }
        }
        Ok(targets)
    }

    /// Computes the cross-prim set of connection/relationship targets authored in
    /// a class (an inherit node) that name a *different* instance of that class
    /// (C++ `_TargetInClassAndTargetsInstance`), keyed by the `(target, property)`
    /// node-namespace pair the target walk matches on.
    ///
    /// This is the purely structural fact "is this class target an instance
    /// target"; list-op composition (delete / explicit shadowing) and the actual
    /// dropping/reporting are left to `resolve_path_list_op_validated`, which
    /// consults this set per node contribution. A target inside the class itself
    /// (`connectionPathInsideInheritedClass`) is never an instance target.
    fn compute_instance_targets(
        &mut self,
        graph: &LayerGraph,
        resolved_prim: &Path,
        field: FieldKey,
        prop_suffix: &str,
    ) -> Result<HashSet<(Path, Path)>> {
        // Phase 1: gather candidates that translate, releasing the index borrow
        // before the cross-prim composition in phase 2.
        let mut candidates: Vec<InstanceCandidate> = Vec::new();
        let mut seen: HashSet<(Path, Path)> = HashSet::new();
        {
            let index = &self.indices[resolved_prim];
            for node in index.nodes() {
                if node.arc != ArcType::Inherit || !node.has_specs() || node.is_permission_denied() {
                    continue;
                }
                let class_path = node.path_at_introduction();
                let class_layers: Vec<LayerId> = node.layer_stack().iter().map(|(l, _)| *l).collect();
                let map = index.map_to_root_for_targets(node);
                let property = Path::new(&format!("{}{prop_suffix}", node.path))?;
                for (layer, _) in node.layers() {
                    let Some(value) = graph.layer(layer).try_get(&property, field.as_str())? else {
                        continue;
                    };
                    let list_op = match value.into_owned() {
                        Value::PathListOp(op) => op,
                        Value::PathVec(paths) => sdf::PathListOp::explicit(paths),
                        _ => continue,
                    };
                    for path in list_op.iter() {
                        let target = property.make_absolute(path);
                        // A target inside the class itself is a normal within-class
                        // target (C++ `connectionPathInsideInheritedClass`); only a
                        // target that translates can name an instance.
                        if target.prim_path().has_prefix(&class_path) {
                            continue;
                        }
                        if !seen.insert((target.clone(), property.clone())) {
                            continue;
                        }
                        let Some(translated) = map.translate_to_target(&target) else {
                            continue;
                        };
                        candidates.push(InstanceCandidate {
                            target,
                            property: property.clone(),
                            translated,
                            class_layers: class_layers.clone(),
                            class_path: class_path.clone(),
                        });
                    }
                }
            }
        }

        // Phase 2: compose each target prim for the cross-prim inherit check.
        let mut instance_targets: HashSet<(Path, Path)> = HashSet::new();
        for c in candidates {
            let target_prim = c.translated.prim_path();
            self.ensure_index(graph, &target_prim)?;
            if target_prim_inherits_class(&self.indices[&target_prim], &c.class_layers, &c.class_path) {
                instance_targets.insert((c.target, c.property));
            }
        }
        Ok(instance_targets)
    }

    /// Composes a relationship's target paths together with the paths its
    /// list-op deletes, returned as `(targets, deleted)` (C++
    /// `PcpBuildFilteredTargetIndex` and its `deletedPaths` out-param). Both are
    /// mapped into stage namespace; a non-property path yields two empty lists.
    pub fn compute_relationship_target_paths(
        &mut self,
        graph: &LayerGraph,
        path: &Path,
    ) -> Result<(Vec<Path>, Vec<Path>)> {
        self.compute_target_paths(graph, path, FieldKey::TargetPaths)
    }

    /// Composes an attribute's connection paths together with the paths its
    /// list-op deletes (the connection analog of
    /// [`Self::compute_relationship_target_paths`]).
    pub fn compute_attribute_connection_paths(
        &mut self,
        graph: &LayerGraph,
        path: &Path,
    ) -> Result<(Vec<Path>, Vec<Path>)> {
        self.compute_target_paths(graph, path, FieldKey::ConnectionPaths)
    }

    /// Composes both the resolved and the deleted entries of a path-list-op
    /// property field. TODO(perf): C++ surfaces both from a single target-index
    /// build; this composes the field twice.
    fn compute_target_paths(
        &mut self,
        graph: &LayerGraph,
        path: &Path,
        field: FieldKey,
    ) -> Result<(Vec<Path>, Vec<Path>)> {
        let targets = self.compose_property_paths(graph, path, field, false)?;
        let deleted = self.compose_property_paths(graph, path, field, true)?;
        Ok((targets, deleted))
    }

    /// Returns pseudo-root stage metadata, composing session-layer opinions
    /// over the root layer (strongest first).
    ///
    /// Unlike [`Self::root_layer_field`] — which is root-layer-only for the
    /// spec 12.2.7 fields such as `defaultPrim` — general stage metadata
    /// (e.g. `renderSettingsPrimPath`) honors a session-layer override,
    /// matching C++ `UsdStage::GetMetadata`. A [`Value::ValueBlock`] in a
    /// stronger layer blocks weaker opinions.
    pub fn stage_metadata(&self, graph: &LayerGraph, field: &str) -> Result<Option<Value>> {
        let root = Path::abs_root();
        // Walk session layers then the root layer so the session opinion wins.
        let layer_ids = graph
            .session_layers()
            .iter()
            .copied()
            .chain(graph.root_id())
            .collect::<Vec<_>>();
        for id in layer_ids {
            let layer = graph.layer(id);
            match layer.try_get(&root, field)? {
                Some(value) if matches!(value.as_ref(), Value::ValueBlock) => return Ok(None),
                Some(value) => return Ok(Some(value.into_owned())),
                None => {}
            }
        }
        Ok(None)
    }

    /// Returns pseudo-root layer metadata from the root layer only.
    ///
    /// Session-layer and sublayer opinions are intentionally ignored here,
    /// matching spec 12.2.7.
    fn root_layer_field(&self, graph: &LayerGraph, field: &str) -> Result<Option<Value>> {
        let root = Path::abs_root();
        let Some(root_layer) = graph.root_layer() else {
            return Ok(None);
        };
        let Some(value) = root_layer.try_get(&root, field)? else {
            return Ok(None);
        };
        if matches!(value.as_ref(), Value::ValueBlock) {
            return Ok(None);
        }
        Ok(Some(value.into_owned()))
    }

    /// Returns the composed list of child names for a prim path (C++
    /// `PcpPrimIndex::ComputePrimChildNames`'s `nameOrder` out-param).
    pub fn prim_children(&mut self, graph: &LayerGraph, path: &Path) -> Result<Vec<String>> {
        Ok(self.compute_prim_child_names(graph, path)?.0)
    }

    /// Composes a prim's child names alongside the names prohibited at it (C++
    /// `PcpPrimIndex::ComputePrimChildNames` / `_ComposePrimChildNames`, whose
    /// `nameOrder` and `prohibitedNames` out-params this returns as a pair).
    ///
    /// The composition graph is walked weakest-to-strongest. At each contributing
    /// node, the relocates authored in that node's layer stack are applied to the
    /// names contributed so far (`relocates::apply_child_relocates`) — a child renamed
    /// within the same parent keeps the source's position, a child relocated to a
    /// different parent is removed, and a child relocated in from elsewhere is
    /// appended in the normative element order (spec §8.2) — and then the node's own `primChildren` /
    /// `primOrder` compose over the running order (mirroring C++
    /// `_ComposePrimChildNamesAtNode`). Every relocation source becomes a
    /// prohibited name, removed from the final order.
    ///
    /// Within a node, the contributing layers fold weakest-first: each appends
    /// its not-yet-seen names in authored order, then its `primOrder` opinion
    /// reshuffles the running list, so several sublayers can contribute partial
    /// orderings. The recursive build already grafts inherit/specialize/reference
    /// targets with their subtrees, so a single structural walk covers class
    /// children. On an instance prim, locally-authored children are dropped (spec
    /// 11.3.3) so the children come only from the composition arcs.
    pub fn compute_prim_child_names(&mut self, graph: &LayerGraph, path: &Path) -> Result<(Vec<String>, Vec<String>)> {
        let path = self.effective_path(graph, path)?;
        self.ensure_index(graph, &path)?;

        // An instance prim's children come only from its composition arcs;
        // opinions authored at the instance's own namespace — the local root and
        // the ancestral references above the instanceable arc — are discarded
        // (spec 11.3.3). The instance prim's own index is otherwise left intact.
        let drop_local = self.is_instance(graph, &path)?;

        let index = &self.indices[&path];
        // The instance-local partition is keyed by the prim's own namespace depth
        // ([`PrimIndex::instance_local_nodes`]); empty when not dropping locals.
        let local = if drop_local {
            index.instance_local_nodes(path.prim_element_count() as u16)
        } else {
            Vec::new()
        };

        let has_relocates = graph.has_relocates();
        let mut name_order: Vec<String> = Vec::new();
        let mut name_set: HashSet<String> = HashSet::new();
        let mut prohibited: HashSet<String> = HashSet::new();

        // Contributing nodes are walked in reverse strength order (weak-to-
        // strong) — the order in which C++ `_ComposePrimChildNames` finishes each
        // node, visiting every descendant before its ancestor.
        let nodes = index
            .nodes_with_ids()
            .filter(|(id, node)| !(node.is_culled() || drop_local && local[id.idx()]))
            .map(|(_, node)| node)
            .rev();

        for node in nodes {
            // Apply this node's layer-stack relocates to the names contributed so
            // far, then compose the node's own children on top. A relocation
            // source is always a namespace child introduced by a composition arc
            // (a strictly weaker node), so by the time this node's relocates run
            // the source name is already in `name_order`; the relocates therefore
            // correctly run before this node's own `primChildren` fold.
            //
            // The pairs are chained within the node's layer stack
            // (`combined_relocates`, C++ `GetRelocatesSourceToTarget`): a same-
            // parent chain `A -> B`, `B -> C` resolves `A` straight to `C`, so the
            // intermediate `B` (a prohibited source) does not survive as the final
            // name. TODO(perf): `combined_relocates` rescans and re-allocates the
            // node's layer-stack relocates on every contributing node (here and in
            // the indexer's arc-map fold), gated on `has_relocates`. Precompute it
            // once per distinct ambient (keyed by the layer-id sequence) in
            // `LayerGraph::recompute_relocates`, alongside `sublayer_stacks`, so
            // this becomes a lookup (C++ caches these on `PcpLayerStack`).
            if has_relocates {
                let pairs = graph.combined_relocates(node.layer_stack());
                apply_child_relocates(&node.path, &pairs, &mut name_order, &mut name_set, &mut prohibited);
            }
            // The node's contributing layers fold weakest-first; `layer_stack()`
            // is strongest-first, so it is reversed here. Only the layer index is
            // needed (the offset `layers()` folds in is irrelevant to name
            // composition), so the borrowed slice is reversed in place.
            for &(layer, _) in node.layer_stack().iter().rev() {
                let layer_data = graph.layer(layer);
                append_unseen_names(
                    layer_data,
                    &node.path,
                    ChildrenKey::PrimChildren,
                    &mut name_order,
                    &mut name_set,
                );
                if let Ok(Value::TokenVec(order)) = layer_data
                    .get(&node.path, FieldKey::PrimOrder.as_str())
                    .map(|v| v.into_owned())
                {
                    sdf::apply_ordering(&mut name_order, &order);
                }
            }
        }

        // Names relocated away cannot reappear here (C++ removes the prohibited
        // set from the composed order after the walk).
        if !prohibited.is_empty() {
            name_order.retain(|name| !prohibited.contains(name));
        }
        let mut prohibited: Vec<String> = prohibited.into_iter().collect();
        // Order the prohibited set the same way as the child names (spec §8.2),
        // so the two outputs of this function stay consistent.
        prohibited.sort_by(|a, b| sdf::element_cmp(a, b));
        Ok((name_order, prohibited))
    }

    /// Returns the composed list of property names for a prim path.
    ///
    /// Merges `propertyChildren` weakest-to-strongest. `propertyOrder` is not
    /// applied: USD value resolution ignores `reorder properties` (C++
    /// `_ComposePrimPropertyNames` passes a null order field in USD mode), so
    /// composed property order follows authoring order alone.
    pub fn prim_properties(&mut self, graph: &LayerGraph, path: &Path) -> Result<Vec<String>> {
        let path = &self.effective_path(graph, path)?;
        self.composed_property_names(graph, path)
    }

    /// Pushes a [`Error::InconsistentPropertyType`] for each composed property of
    /// `prim_path` whose specs mix attribute and relationship kinds (C++
    /// `PcpErrorInconsistentPropertyType`). C++ reports the conflict on each
    /// property-index composition; the dump's property-name pass (here) and
    /// property-stack pass ([`property_stack`](Self::property_stack)) each compose
    /// it, so the error surfaces once per pass.
    fn report_property_type_conflicts(&mut self, graph: &LayerGraph, prim_path: &Path, names: &[String]) {
        let Some(index) = self.indices.get(prim_path) else {
            return;
        };
        let mut conflicts = Vec::new();
        for name in names {
            let Ok(prop_path) = prim_path.append_property(name) else {
                continue;
            };
            conflicts.extend(self.compose_property_specs(graph, index, prim_path, &prop_path).1);
        }
        self.query_errors.append(&mut conflicts);
    }

    /// Walks a property's specs strongest-first across the prim's composition
    /// graph, returning its `(layer identifier, spec path)` stack and the
    /// inconsistent-spec-type errors. The first spec's kind (attribute vs
    /// relationship) is the defining type; weaker specs of the other kind are
    /// inconsistent (C++ `PcpErrorInconsistentPropertyType`) — dropped from the
    /// stack and reported. `prop_path` is the property in `prim_path`'s namespace.
    fn compose_property_specs(
        &self,
        graph: &LayerGraph,
        index: &PrimIndex,
        prim_path: &Path,
        prop_path: &Path,
    ) -> (Vec<(String, Path)>, Vec<Error>) {
        let mut stack = Vec::new();
        let mut conflicts = Vec::new();
        let mut defining: Option<(SpecType, String, Path)> = None;
        for node in index.nodes() {
            let Some(p) = prop_path.replace_prefix(prim_path, &node.path) else {
                continue;
            };
            for (layer, _) in node.layers() {
                let Some(spec_type) = graph.layer(layer).spec_type(&p) else {
                    continue;
                };
                match &defining {
                    None => defining = Some((spec_type, graph.identifier(layer).to_string(), p.clone())),
                    Some((def_type, def_layer, def_path)) if *def_type != spec_type => {
                        conflicts.push(Error::InconsistentPropertyType {
                            property: prop_path.clone(),
                            defining_layer: def_layer.clone(),
                            defining_path: def_path.clone(),
                            defining_is_attribute: *def_type == SpecType::Attribute,
                            conflicting_layer: graph.identifier(layer).to_string(),
                            conflicting_path: p.clone(),
                            conflicting_is_attribute: spec_type == SpecType::Attribute,
                            composing: prim_path.clone(),
                        });
                        continue;
                    }
                    Some(_) => {}
                }
                stack.push((graph.identifier(layer).to_string(), p.clone()));
            }
        }
        (stack, conflicts)
    }

    /// Returns the composed [`PrimIndex`] for a prim, building it if needed (C++
    /// `UsdPrim::GetPrimIndex` / `PcpCache::ComputePrimIndex`). The borrow is
    /// tied to the cache, so callers reach it through the borrowing
    /// [`PrimIndexRef`](crate::usd::PrimIndexRef) view.
    pub fn index(&mut self, graph: &LayerGraph, path: &Path) -> Result<&PrimIndex> {
        let path = self.effective_path(graph, &path.prim_path())?;
        self.ensure_index(graph, &path)?;
        Ok(&self.indices[&path])
    }

    /// Returns the prim stack: each `(layer identifier, spec path)` site that
    /// contributes a prim spec, strongest first. Backs C++
    /// `UsdPrim::GetPrimStack` (each per-site node fans out into one entry per
    /// contributing layer in its layer stack, since every member authored a
    /// prim spec).
    pub fn prim_stack(&mut self, graph: &LayerGraph, path: &Path) -> Result<Vec<(String, Path)>> {
        let path = self.effective_path(graph, &path.prim_path())?;
        self.ensure_index(graph, &path)?;
        let index = &self.indices[&path];
        let mut stack = Vec::new();
        for node in index.nodes() {
            // A node may carry its full site layer stack; only the layers that
            // author a spec at its path belong in the prim stack.
            for (layer, _) in node.layers() {
                if graph.layer(layer).has_spec(&node.path) {
                    stack.push((graph.identifier(layer).to_string(), node.path.clone()));
                }
            }
        }
        Ok(stack)
    }

    /// Returns the property stack for a property path: each `(layer identifier,
    /// spec path)` site that authors a property spec, strongest first. Backs
    /// C++ `UsdProperty::GetPropertyStack`. A non-property path yields an empty
    /// stack.
    pub fn property_stack(&mut self, graph: &LayerGraph, path: &Path) -> Result<Vec<(String, Path)>> {
        let path = self.effective_path(graph, path)?;
        if !path.is_property_path() {
            return Ok(Vec::new());
        }
        let prim_path = path.prim_path();
        self.ensure_index(graph, &prim_path)?;
        let Some(index) = self.indices.get(&prim_path) else {
            return Ok(Vec::new());
        };
        let (stack, mut conflicts) = self.compose_property_specs(graph, index, &prim_path, &path);
        // These transient conflicts are cleared on any index invalidation, so
        // they never go stale across an edit; repeated `property_stack` queries
        // on the same conflicting property without an intervening edit still
        // re-append within a session (the `query_errors` TODO).
        self.query_errors.append(&mut conflicts);
        Ok(stack)
    }

    /// Returns the variant selections composed onto a prim, as `(set,
    /// selection)` pairs sorted by set name. Backs C++
    /// `UsdVariantSets::GetAllVariantSelections`. These are the effective
    /// selections — authored, fallback, or default — read from the variant
    /// selection sites composed into the index, so they match the variant
    /// branches that actually contribute opinions.
    pub fn variant_selections(&mut self, graph: &LayerGraph, path: &Path) -> Result<Vec<(String, String)>> {
        let path = self.effective_path(graph, &path.prim_path())?;
        self.ensure_index(graph, &path)?;
        Ok(self.indices[&path].variant_selections())
    }

    /// Returns the `defaultPrim` metadata from the root layer, if set.
    ///
    /// When session layers are present, `defaultPrim` is read from the
    /// first non-session layer (the root layer), matching C++ behavior.
    pub fn default_prim(&self, graph: &LayerGraph) -> Option<String> {
        let root = Path::abs_root();
        let value = graph.root_layer()?.get(&root, FieldKey::DefaultPrim.as_str()).ok()?;
        match value.into_owned() {
            Value::Token(s) | Value::String(s) => Some(s),
            _ => None,
        }
    }

    /// Collects ancestor arcs from all cached ancestors of `path`.
    ///
    /// Returns references into the cached contexts, avoiding allocation
    /// of `AncestorArc` (which contains `MapFunction` with a `Vec`).
    fn collect_ancestor_arcs(&self, path: &Path) -> Vec<&AncestorArc> {
        let mut arcs = Vec::new();
        let mut p = Some(path.clone());
        while let Some(pp) = p {
            if let Some(ctx) = self.contexts.get(&pp) {
                arcs.extend(&ctx.ancestor_arcs);
            }
            p = pp.parent();
        }
        arcs
    }

    /// Pre-caches inherit/specialize targets declared in the prim's layer
    /// data. Reads inherit paths from each layer, resolves them to composed
    /// namespace using ancestor arcs, and ensures those targets are cached.
    fn precache_inherit_targets(&mut self, graph: &LayerGraph, path: &Path) {
        let Some(parent) = path.parent() else {
            return;
        };
        let Some(parent_index) = self.indices.get(&parent) else {
            return;
        };

        let ancestor_arcs = self.collect_ancestor_arcs(&parent);

        // Scan each parent composition node for inherit/specialize targets: the
        // parent's own path in that node's namespace, and the prim's path there
        // (the node's path extended by the prim name). A layer that authors the
        // prim directly contributes to the parent at the parent path, so it is
        // already covered here — no separate all-layers scan of the prim path is
        // needed.
        let mut nodes_to_scan: Vec<(Path, LayerId)> = Vec::new();
        for node in parent_index.nodes() {
            for (layer, _) in node.layers() {
                nodes_to_scan.push((node.path.clone(), layer));
                if let Some(name) = path.name() {
                    if let Ok(child_in_node) = node.path.append_path(name) {
                        nodes_to_scan.push((child_in_node, layer));
                    }
                }
            }
        }

        let mut targets_to_cache = Vec::new();
        for (scan_path, scan_layer) in &nodes_to_scan {
            for field in [FieldKey::InheritPaths, FieldKey::Specializes] {
                let Ok(val) = graph.layer(*scan_layer).get(scan_path, field.as_str()) else {
                    continue;
                };
                let Value::PathListOp(list_op) = val.into_owned() else {
                    continue;
                };
                for target in &list_op.flatten() {
                    // Anchor a relative inherit/specialize target at the path it
                    // is authored on (the scanned node's namespace), matching the
                    // indexer's `path.make_absolute`. Anchoring at the
                    // composed parent would mis-resolve `../` targets by a level.
                    let raw = scan_path.make_absolute(target);
                    // Try composed-namespace versions via ancestor arcs.
                    for a in &ancestor_arcs {
                        if let Some(composed) = a.map.map_source_to_target(&raw) {
                            if composed != raw && !targets_to_cache.contains(&composed) {
                                targets_to_cache.push(composed);
                            }
                        }
                    }
                    if !targets_to_cache.contains(&raw) {
                        targets_to_cache.push(raw);
                    }
                }
            }
        }

        for target in targets_to_cache {
            self.precache_path(graph, &target);
            // Recursively precache the target's own inherit targets.
            if self.indices.contains_key(&target) {
                self.precache_inherit_targets(graph, &target);
            }
        }
    }

    /// Returns the `(node, error)` pair for each direct composition arc on
    /// `path` whose target site is `permission = private` (spec 10.3.3).
    ///
    /// A direct arc is a reference/inherit/payload/specialize authored at this
    /// prim — its node sits at the prim's own namespace depth and is not an
    /// implied class. Mirroring C++ `_AddArc` + `_InertSubtree`, the caller
    /// surfaces the error and marks the node's subtree
    /// [`PERMISSION_DENIED`](NodeFlags::PERMISSION_DENIED), so the arc stops
    /// contributing to value resolution while staying visible structurally
    /// (`nodes`, `has_spec`, child names are unchanged).
    fn detect_arc_permissions(&self, graph: &LayerGraph, path: &Path, index: &PrimIndex) -> Vec<(NodeId, Error)> {
        let depth = path.prim_element_count() as u16;
        let mut denials = Vec::new();
        for (id, node) in index.nodes_with_ids() {
            let is_direct_arc = matches!(
                node.arc,
                ArcType::Inherit | ArcType::Specialize | ArcType::Reference | ArcType::Payload
            ) && node.namespace_depth() == depth
                && !node.flags().contains(NodeFlags::IMPLIED_CLASS);
            if is_direct_arc && self.target_is_private(graph, node) {
                denials.push((
                    id,
                    Error::ArcPermissionDenied {
                        site_path: path.clone(),
                        arc: node.arc,
                        target_path: node.path.clone(),
                    },
                ));
            }
        }
        denials
    }

    /// Returns `true` when the strongest `permission` opinion at a direct arc's
    /// target site (read across the node's contributing layers) is `private`.
    fn target_is_private(&self, graph: &LayerGraph, node: &Node) -> bool {
        for (layer, _) in node.layers() {
            if let Ok(Some(value)) = graph.layer(layer).try_get(&node.path, FieldKey::Permission.as_str()) {
                return matches!(value.as_ref(), Value::Permission(sdf::Permission::Private));
            }
        }
        false
    }

    // ------------------------------------------------------------------
    // Core composition
    // ------------------------------------------------------------------

    /// Ensures the prim index for `path` is built and cached.
    ///
    /// When LIVRPS composition produces an empty index (no layer has a direct
    /// spec at the composed path), parent composition nodes are checked for
    /// child specs at their respective paths. This handles prims that only
    /// exist through ancestor inherit, specialize, or reference arcs.
    pub(super) fn ensure_index(&mut self, graph: &LayerGraph, path: &Path) -> Result<()> {
        if self.indices.contains_key(path) {
            return Ok(());
        }
        // Composing a prim whose ancestor is still mid-build cannot seed from that
        // ancestor's opinions. This happens only when pre-caching an
        // inherit/specialize target that is a namespace descendant of an
        // in-progress ancestor (a prim inheriting its own descendant). The
        // descendant may be more than one level down (`/A` inheriting `/A/B/C`),
        // so every strict ancestor is checked, not just the parent. Defer without
        // caching an under-seeded result; a later query composes it correctly once
        // the ancestor is cached, and the cycle-closing arc finds no cached target.
        if self.in_progress.iter().any(|a| a != path && path.has_prefix(a)) {
            return Ok(());
        }
        // A re-entrant call for a path already mid-build is a class-hierarchy
        // cycle reached through inherit/specialize pre-caching. Bail out: the
        // outer build finishes, and the cycle-closing arc finds no cached target.
        if !self.in_progress.insert(path.clone()) {
            return Ok(());
        }
        let result = self.build_index(graph, path);
        self.in_progress.remove(path);
        result
    }

    /// Builds and caches the index for `path`, assuming `path` is already
    /// recorded in [`in_progress`](Self::in_progress) (see [`ensure_index`](Self::ensure_index)).
    fn build_index(&mut self, graph: &LayerGraph, path: &Path) -> Result<()> {
        // Compose ancestors first so the parent's `CompositionContext` (and
        // its `within_instance` flag, spec 11.3.3) is available. Composition
        // is a pure function of the layer stack, path, and parent context, so
        // building ancestors eagerly only fixes the parent context — it does
        // not change any prim's resolved opinions.
        if let Some(parent) = path.parent() {
            if !parent.is_abs_root() && !self.indices.contains_key(&parent) {
                self.precache_path(graph, &parent);
            }
        }

        // Pre-cache inherit/specialize targets so the indexer can
        // find them. This handles the timing issue where a target prim is
        // in a sibling subtree that hasn't been traversed yet.
        self.precache_inherit_targets(graph, path);

        let parent_ctx = path
            .parent()
            .and_then(|p| self.contexts.get(&p))
            .cloned()
            .unwrap_or_else(|| self.root_parent_context());

        // TODO(rayon): `build_with_cache` is a pure function of `graph`,
        // `&parent_ctx`, and `&self.indices`, so sibling prims compose
        // independently and this is the natural per-prim `par_iter` boundary.
        // The blocker is the shared `self.indices` map that inherit/specialize
        // targets read mid-build — parallelizing the driver needs a concurrent
        // map or a topological (targets-first) build order.
        let (mut index, mut build_errors) = match PrimIndex::build_with_cache(path, graph, &parent_ctx, &self.indices) {
            Ok(result) => result,
            Err(e) => return Err(e.into()),
        };
        // Retain recoverable composition errors recorded during the build (e.g.
        // an unresolvable arc). An invalid opinion at a
        // relocation source is reported "while composing" this prim, so stamp its
        // path — the indexer may have recorded it deep in a sub-index build whose
        // own site path differs.
        for error in &mut build_errors {
            match error {
                Error::OpinionAtRelocationSource { composing, .. } => *composing = path.clone(),
                Error::ProhibitedRelocationSource { composing, .. } => *composing = path.clone(),
                Error::ArcCycle(info) => info.composing = path.clone(),
                _ => {}
            }
        }
        // `build_errors` accumulates every error for this prim (the build errors
        // above plus the permission denials below) and is stored keyed by `path`
        // at the end, replacing any prior set, so a rebuild never duplicates and
        // a fixed prim drops its stale errors.

        // Inside an instance, local opinions on descendants are discarded
        // (spec 11.3.3): the subtree is composed purely from the arcs the
        // instance brings in. This is enforced at composition time — the indexer
        // marks the local root site inert for any prim whose parent context is
        // `within_instance`, so the local arcs are never followed — rather than
        // pruned afterwards, which would leave the nodes those local arcs spawned.

        // Arc permissions (spec 10.3.3, C++ `_AddArc` + `_InertSubtree`). A
        // direct arc to a `permission = private` site is reported and its target
        // path recorded; an ancestor's denied targets arrive on `parent_ctx`.
        // Every node reached through a denied arc — its grafted subtree here, or
        // the same arc extended to this descendant prim — is then inerted: it
        // stays visible structurally but contributes no opinions to value
        // resolution. This runs before deriving instance state below so a
        // private target's `instanceable`/arc opinions are already inert.
        let mut denied_prefixes = parent_ctx.denied_prefixes.clone();
        for (node_id, error) in self.detect_arc_permissions(graph, path, &index) {
            let target = index.node(node_id).path.clone();
            if !denied_prefixes.contains(&target) {
                denied_prefixes.push(target);
            }
            build_errors.push(error);
        }
        index.mark_permission_denied_under(&denied_prefixes);

        // Store (replace) this prim's recoverable errors; drop the entry when
        // there are none so a now-clean rebuild leaves nothing stale.
        if build_errors.is_empty() {
            self.prim_errors.remove(path);
        } else {
            self.prim_errors.insert(path.clone(), build_errors);
        }

        // Inside an instance, the ancestral references the instance prim is
        // nested under contribute opinions at the instance's own namespace that
        // must not leak into the shared subtree (spec 11.3.3). The indexer
        // already inerted the local root for an instance descendant; this inerts
        // those outer references too (the C++ `!HasTransitiveDirectDependency`
        // nodes), leaving only the instanceable arc, its descendants, and the
        // implied classes. Runs before deriving instance state below so the
        // suppressed opinions are already inert.
        if let Some(depth) = parent_ctx.instance_depth {
            index.mark_instance_local_inert(depth);
        }

        // This prim is an instance when its composition declares
        // `instanceable = true` and carries an arc; its descendants then
        // inherit `within_instance`. A nested instance therefore re-arms the
        // flag for its own subtree. Computed from the freshly built index (after
        // permission inerting, so it agrees with a later `Prim::is_instance`)
        // to avoid re-entering `ensure_index` for `path`.
        let is_instance = index.has_composition_arc()
            && matches!(
                index.resolve_field(FieldKey::Instanceable.as_str(), graph, None)?,
                Some(Value::Bool(true))
            );

        let mut child_context = index.context_for_children(graph, &parent_ctx);
        // A nested instance re-arms the depth to its own (deeper) level, so an
        // inner instance's descendants drop opinions above its instanceable arc
        // rather than the outer instance's.
        child_context.instance_depth = if is_instance {
            Some(path.prim_element_count() as u16)
        } else {
            parent_ctx.instance_depth
        };
        child_context.denied_prefixes = denied_prefixes;
        self.cache_index(graph, path, index, child_context);
        // Report inconsistent property types once per prim composition (C++
        // `PcpErrorInconsistentPropertyType`); a later property-stack query
        // reports the conflict again, matching C++'s per-pass reporting.
        // TODO(perf): this composes property names on every prim build to find a
        // rare conflict; gate it on a cheaper signal (e.g. a node carrying both
        // attribute and relationship specs) before scanning.
        let names = self.composed_property_names(graph, path)?;
        self.report_property_type_conflicts(graph, path, &names);
        Ok(())
    }

    /// Ensures a path and all its ancestors are cached (built on the fly if needed).
    fn precache_path(&mut self, graph: &LayerGraph, path: &Path) {
        let mut to_build = Vec::new();
        let mut p = Some(path.clone());
        while let Some(pp) = p {
            if pp == Path::abs_root() || self.indices.contains_key(&pp) {
                break;
            }
            to_build.push(pp.clone());
            p = pp.parent();
        }
        for pp in to_build.into_iter().rev() {
            let _ = self.ensure_index(graph, &pp);
        }
    }

    /// Composes a prim's property names across its composition index, folding
    /// `propertyChildren` weakest-to-strongest (C++ `_ComposePrimPropertyNames`).
    ///
    /// Nodes are visited weakest first (the reverse of strength order), and
    /// within each node its contributing layers weakest first; each layer appends
    /// its not-yet-seen names in authored order, so a name keeps its weakest
    /// position. `propertyOrder` is not applied — USD value resolution ignores
    /// `reorder properties` — so composed property order follows authoring order
    /// alone. The recursive build already grafts inherit/specialize/reference
    /// targets with their subtrees, so this single structural walk covers class
    /// properties with no separate target rediscovery.
    fn composed_property_names(&mut self, graph: &LayerGraph, path: &Path) -> Result<Vec<String>> {
        self.ensure_index(graph, path)?;

        let index = &self.indices[path];
        let mut result: Vec<String> = Vec::new();
        let mut seen: HashSet<String> = HashSet::new();

        // Fold weakest-to-strongest across both nodes and, within each node, its
        // layers: contributing nodes in reverse strength order, and `layer_stack()`
        // (strongest first) reversed in place. `seen` dedups names in O(1) while
        // `result` preserves the weakest-position order.
        for node in index.nodes().rev() {
            for &(layer, _) in node.layer_stack().iter().rev() {
                let layer_data = graph.layer(layer);
                append_unseen_names(
                    layer_data,
                    &node.path,
                    ChildrenKey::PropertyChildren,
                    &mut result,
                    &mut seen,
                );
            }
        }

        Ok(result)
    }
}

/// Appends a layer's not-yet-seen `field` children (`primChildren` /
/// `propertyChildren`) to `order` in authored order, recording each in `seen`.
/// A name already present keeps its weaker position. Shared by the prim- and
/// property-name folds (C++ `PcpComposeSiteChildNames`'s append step).
fn append_unseen_names(
    layer: &sdf::Layer,
    path: &Path,
    field: ChildrenKey,
    order: &mut Vec<String>,
    seen: &mut HashSet<String>,
) {
    if let Ok(Value::TokenVec(names)) = layer.get(path, field.as_str()).map(|v| v.into_owned()) {
        for name in names {
            if seen.insert(name.clone()) {
                order.push(name);
            }
        }
    }
}

/// A class-node target that translates, gathered by
/// [`IndexCache::compute_instance_targets`] for the cross-prim instance check.
struct InstanceCandidate {
    /// The authored target, in the authoring (class) node's namespace.
    target: Path,
    /// The owning property, in the authoring node's namespace.
    property: Path,
    /// The target translated to the root namespace (C++
    /// `PcpTranslatePathFromNodeToRoot`).
    translated: Path,
    /// The class node's layer-stack layers, for the cross-prim instance check.
    class_layers: Vec<LayerId>,
    /// The class path, in the node's namespace (the inherit's introduction path).
    class_path: Path,
}

/// Whether `index` (a composed target prim) inherits the class at `class_path`
/// from the same `class_layers` layer stack (C++
/// `_TargetInClassAndTargetsInstance`'s node scan): the target names an instance
/// of the class.
fn target_prim_inherits_class(index: &PrimIndex, class_layers: &[LayerId], class_path: &Path) -> bool {
    index.all_nodes().any(|n| {
        n.arc == ArcType::Inherit
            && n.layer_stack().iter().map(|(l, _)| *l).eq(class_layers.iter().copied())
            && n.path.has_prefix(class_path)
    })
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::ar::{DefaultResolver, Resolver};

    fn manifest_dir() -> String {
        std::env::var("CARGO_MANIFEST_DIR").unwrap()
    }

    /// Builds a stack with the root and every layer reachable through
    /// references/sublayers collected in, so composition can resolve them
    /// (clip layers are still opened lazily by the cache).
    fn collected_stack(path: &str) -> (LayerGraph, IndexCache) {
        let resolver = DefaultResolver::new();
        let layers = crate::layer::Collector::new(&resolver)
            .collect(path)
            .expect("collect layers");
        let graph = LayerGraph::from_layers(layers, 0, Box::new(DefaultResolver::new()), true);
        (graph, IndexCache::new(VariantFallbackMap::new(), Vec::new()))
    }

    /// Parses in-memory USDA text into a single `root.usda` layer.
    fn parse_layer(text: &str) -> sdf::Layer {
        let data = crate::usda::parser::Parser::new(text).parse().expect("parse usda");
        sdf::Layer::new("root.usda", Box::new(crate::usda::TextReader::from_data(data)))
    }

    /// Builds a one-layer graph + cache from in-memory USDA text, for
    /// composition cases that need no on-disk asset.
    fn in_memory_stack(text: &str) -> (LayerGraph, IndexCache) {
        let graph = LayerGraph::from_layers(vec![parse_layer(text)], 0, Box::new(DefaultResolver::new()), true);
        (graph, IndexCache::new(VariantFallbackMap::new(), Vec::new()))
    }

    /// Builds a one-layer graph + cache whose root is loaded from a real path,
    /// so the resolver can anchor clip asset paths relative to it.
    fn single_layer_stack(path: &str) -> (LayerGraph, IndexCache) {
        let resolver = DefaultResolver::new();
        let resolved = resolver.resolve(path).expect("root resolves");
        let id = resolver.create_identifier(path, None);
        let data = crate::layer::open_layer(&resolver, &resolved).expect("open root");
        let graph = LayerGraph::from_layers(
            vec![sdf::Layer::new(id, data)],
            0,
            Box::new(DefaultResolver::new()),
            true,
        );
        (graph, IndexCache::new(VariantFallbackMap::new(), Vec::new()))
    }

    /// `clip_layer` loads a clip layer relative to the authoring layer, caches
    /// it (clip layers never enter the composition stack), and reports an
    /// unresolvable path as `None`.
    #[test]
    fn loads_and_caches_clip_layer() -> Result<()> {
        let root = format!(
            "{}/vendor/core-spec-supplemental-release_dec2025/value_resolution/tests/assets/clip_basic/usda/root.usda",
            manifest_dir()
        );
        let (graph, mut cache) = single_layer_stack(&root);
        let root_id = graph.root_id().expect("root layer");

        {
            let clip = cache
                .clip_layer(&graph, "./clip.usda", root_id)?
                .expect("clip resolves");
            assert!(clip.identifier.contains("clip.usda"));
            assert!(clip.data().has_spec(&sdf::path("/Model.size")?));
        }

        // Second lookup is a cache hit; a bogus path resolves to None.
        assert!(cache.clip_layer(&graph, "./clip.usda", root_id)?.is_some());
        assert!(cache.clip_layer(&graph, "./does_not_exist.usda", root_id)?.is_none());
        Ok(())
    }

    /// A prim inheriting its own grand-descendant (`/A` inherits `/A/B/C`) is a
    /// cycle whose arc is dropped, but composing `/A` must not cache an
    /// under-seeded `/A/B/C`. The inherit-target precache builds `/A/B/C` while
    /// `/A` is in progress, and its parent `/A/B` is not the in-progress prim, so
    /// the deferral guard must check every ancestor, not just the parent. `/A/B`
    /// references `</Lib/Ref>`, so a correctly-seeded `/A/B/C` exposes the
    /// reference's `mark` property.
    #[test]
    fn grandchild_inherit_target_seeds_ancestors() -> Result<()> {
        let text = r#"#usda 1.0
def "Lib" {
    def "Ref" {
        def "C" { custom string mark = "from-ref" }
    }
}
def "A" (
    inherits = </A/B/C>
)
{
    def "B" (
        references = </Lib/Ref>
    )
    {
    }
}
"#;
        let (graph, mut cache) = in_memory_stack(text);
        // Compose /A first so its inherit-target precache runs before /A/B/C is
        // queried; the precache must not leave a stale, parentless /A/B/C cached.
        cache.ensure_index(&graph, &sdf::path("/A")?)?;
        assert!(
            cache
                .prim_properties(&graph, &sdf::path("/A/B/C")?)?
                .contains(&"mark".to_string()),
            "/A/B/C must inherit the reference's `mark` via /A/B even when reached through /A's precache"
        );
        Ok(())
    }

    /// A child reachable only through a chain of local-class inherits composes
    /// its own inherited grandchildren: `SymArmRig` inherits `_Class_ArmRig`
    /// (whose `ArmRegion` over inherits `Body/_class_Region`), so
    /// `SymArmRig/ArmRegion` must expose `Region`.
    #[test]
    fn inherited_child_chain_composes() -> Result<()> {
        let root = format!(
            "{}/vendor/core-spec-supplemental-release_dec2025/composition/tests/assets/\
             TrickyLocalClassHierarchyWithRelocates_root/usda/root.usd",
            manifest_dir()
        );
        let (graph, mut cache) = collected_stack(&root);
        let arm_region = sdf::path("/C_1/ArmsRig/SymArmRig/ArmRegion")?;
        assert!(
            cache
                .prim_children(&graph, &arm_region)?
                .contains(&"Region".to_string()),
            "deep local-class inherit chain must surface the inherited grandchild"
        );
        Ok(())
    }

    /// Child names fold weakest-to-strongest, reapplying each layer's
    /// `primOrder` as it merges. `sub.usda` (weaker) authors `a b c` reordered
    /// to `c b a`; `root.usda` (stronger) adds `d` and reorders `a d`. The fold
    /// yields `[c, b, a, d]` — a strongest-`primOrder`-wins union would instead
    /// give `[a, d, b, c]`.
    #[test]
    fn child_names_fold_weak_to_strong() -> Result<()> {
        let root = format!("{}/fixtures/child_order_fold/root.usda", manifest_dir());
        let (graph, mut cache) = collected_stack(&root);
        let children = cache.prim_children(&graph, &sdf::path("/P")?)?;
        assert_eq!(children, vec!["c", "b", "a", "d"]);
        Ok(())
    }

    /// A direct inherit to a `permission = private` class is reported as a
    /// non-fatal `ArcPermissionDenied` (spec 10.3.3), while the private class
    /// stays in the prim stack — C++ keeps the node and only records the error.
    /// Ground truth: `ErrorPermissionDenied_root` (`/Model` inherits the
    /// private `/_PrivateClass`).
    #[test]
    fn inherit_private_class_reports_arc() -> Result<()> {
        let root = format!(
            "{}/vendor/core-spec-supplemental-release_dec2025/composition/tests/assets/\
             ErrorPermissionDenied_root/usda/root.usd",
            manifest_dir()
        );
        let (graph, mut cache) = collected_stack(&root);
        let model = sdf::path("/Model")?;
        let private = sdf::path("/_PrivateClass")?;
        cache.ensure_index(&graph, &model)?;

        // Structural visibility is unchanged: the private class still composes
        // into the prim stack (it is inerted for value resolution, not removed).
        assert!(
            cache.indices[&model].nodes().any(|n| n.path == private),
            "private inherited class must remain in the prim stack"
        );

        // The direct inherit-to-private arc is queued for the stage to surface.
        let pending = cache.take_composition_errors();
        assert!(
            pending.iter().any(|e| matches!(
                e,
                Error::ArcPermissionDenied { site_path, arc, target_path }
                    if *site_path == model && *arc == ArcType::Inherit && *target_path == private
            )),
            "expected ArcPermissionDenied for /Model -> /_PrivateClass, got {pending:?}"
        );
        Ok(())
    }

    /// A direct inherit to a private class is inerted (C++ `_InertSubtree`): the
    /// inherited opinion is dropped from value resolution, yet the class stays
    /// in the prim stack and `has_spec`. A public inherit is the control.
    #[test]
    fn private_inherit_inerts_opinions() -> Result<()> {
        let root = format!("{}/fixtures/permission_private_inherit/root.usda", manifest_dir());
        let (graph, mut cache) = collected_stack(&root);

        // Control: a public inherit contributes its opinion.
        assert_eq!(
            cache.resolve_field(&graph, &sdf::path("/ViaPublic.attr")?, FieldKey::Default.as_str())?,
            Some(Value::Double(1.0)),
            "public inherited opinion must contribute"
        );

        // The private inherit is inerted: no opinion reaches value resolution,
        // but the class node and the property stay structurally present.
        let via_private = sdf::path("/ViaPrivate")?;
        let private_class = sdf::path("/PrivateClass")?;
        assert_eq!(
            cache.resolve_field(&graph, &sdf::path("/ViaPrivate.attr")?, FieldKey::Default.as_str())?,
            None,
            "private inherited opinion must not contribute to value resolution"
        );
        assert!(
            cache.indices[&via_private].nodes().any(|n| n.path == private_class),
            "private class stays in the prim stack"
        );
        assert!(
            cache.has_spec(&graph, &sdf::path("/ViaPrivate.attr")?)?,
            "the inherited attr stays structurally present"
        );
        Ok(())
    }

    /// The denial propagates to descendant prims composed separately: a child
    /// inherited through the private arc (an extended, not direct, arc) is
    /// inerted too, while the public child's opinion still resolves and the
    /// child name stays visible.
    #[test]
    fn private_inherit_inerts_descendants() -> Result<()> {
        let root = format!("{}/fixtures/permission_private_inherit/root.usda", manifest_dir());
        let (graph, mut cache) = collected_stack(&root);

        // Control: the public inherited child contributes its opinion.
        assert_eq!(
            cache.resolve_field(
                &graph,
                &sdf::path("/ViaPublic/Child.cattr")?,
                FieldKey::Default.as_str()
            )?,
            Some(Value::Double(2.0)),
            "public inherited child opinion must contribute"
        );

        // The private inherited child is inerted, but stays visible: the child
        // name is exposed and the property has a spec.
        assert_eq!(
            cache.resolve_field(
                &graph,
                &sdf::path("/ViaPrivate/Child.cattr")?,
                FieldKey::Default.as_str()
            )?,
            None,
            "private inherited child opinion must not contribute"
        );
        assert!(
            cache
                .prim_children(&graph, &sdf::path("/ViaPrivate")?)?
                .contains(&"Child".to_string()),
            "the inherited child name stays visible"
        );
        Ok(())
    }

    /// A private arc that authors `instanceable = true` is inerted before
    /// instance state is derived, so the prim is not treated as an instance and
    /// its local child opinions survive (the descendant subtree is not composed
    /// as a discarded-local instance subtree).
    #[test]
    fn private_instanceable_arc_not_instance() -> Result<()> {
        let root = format!("{}/fixtures/permission_private_inherit/root.usda", manifest_dir());
        let (graph, mut cache) = collected_stack(&root);

        let host = sdf::path("/InstHost")?;
        assert!(
            !cache.is_instance(&graph, &host)?,
            "a private (inerted) instanceable arc must not make the prim an instance"
        );
        assert_eq!(
            cache.resolve_field(&graph, &sdf::path("/InstHost/Local.lattr")?, FieldKey::Default.as_str())?,
            Some(Value::Double(7.0)),
            "the local child opinion must survive (within_instance not armed)"
        );
        Ok(())
    }

    /// A relocated prim's index carries relocate nodes (tagged
    /// `RELOCATE_SOURCE`) whose grafted source subtree forms a consistent
    /// tree: every stored parent link is mirrored by the parent's child list.
    #[test]
    fn relocate_nodes_form_subtree() -> Result<()> {
        use super::super::prim_graph::NodeFlags;

        let root = format!(
            "{}/vendor/core-spec-supplemental-release_dec2025/composition/tests/assets/\
             BasicRelocateToAnimInterface_root/usda/root.usd",
            manifest_dir()
        );
        let (graph, mut cache) = collected_stack(&root);
        let path = sdf::path("/Model/Anim/Path")?;
        cache.ensure_index(&graph, &path)?;
        let index = &cache.indices[&path];

        // The relocate source node is composed inert (salted earth, C++
        // `rootNodeShouldContributeSpecs == false`): its own site contributes
        // nothing — its ancestral children carry the relocated opinions — so it
        // is retained in the arena but skipped by `nodes`/`all_nodes`.
        assert!(
            index
                .arena()
                .iter()
                .any(|n| n.flags().contains(NodeFlags::RELOCATE_SOURCE)),
            "relocated prim has a relocate source node"
        );
        for (id, node) in index.nodes_with_ids() {
            if let Some(parent) = node.parent() {
                assert!(
                    index.children(parent).contains(&id),
                    "relocate node {id:?} parent {parent:?} missing it as a child"
                );
            }
        }
        Ok(())
    }

    /// A relocate source spanning several sublayers keeps every member in the
    /// per-site relocate node — the weaker sublayer opinion must not be lost.
    /// `/World/Src` (authored in both `root.usda` and `sub.usda`) relocates to
    /// `/World/Dst`, whose relocate node must carry both layers.
    #[test]
    fn relocate_source_spans_sublayers() -> Result<()> {
        use super::super::prim_graph::NodeFlags;

        let root = format!("{}/fixtures/relocate_multilayer/root.usda", manifest_dir());
        let (graph, mut cache) = collected_stack(&root);
        let path = sdf::path("/World/Dst")?;
        cache.ensure_index(&graph, &path)?;
        let index = &cache.indices[&path];

        // The relocate source node is composed inert (salted earth), so it is
        // retained in the arena but skipped by `nodes`/`all_nodes`.
        let relocate = index
            .arena()
            .iter()
            .find(|n| n.flags().contains(NodeFlags::RELOCATE_SOURCE))
            .expect("relocated prim has a relocate source node");
        let layers: Vec<LayerId> = relocate.layers().map(|(li, _)| li).collect();
        let expected: Vec<LayerId> = graph.root_layer_stack().iter().map(|&(id, _)| id).collect();
        assert_eq!(
            layers, expected,
            "relocate node folds both authoring sublayers, strongest first"
        );
        Ok(())
    }

    /// A cross-hierarchy relocation source is registered as a dependency of the
    /// relocated prim even though its node is inert. `/Source/Inner` relocates to
    /// `/Dest/Moved`; the source's ancestors (`/Source`) are not ancestors of the
    /// target, so only the source-site registration lets an edit at `/Source/Inner`
    /// invalidate `/Dest/Moved`.
    #[test]
    fn relocate_source_registers_dependency() -> Result<()> {
        let root = format!("{}/fixtures/relocate_cross_hierarchy/root.usda", manifest_dir());
        let (graph, mut cache) = collected_stack(&root);
        let dst = sdf::path("/Dest/Moved")?;
        cache.ensure_index(&graph, &dst)?;

        let src = sdf::path("/Source/Inner")?;
        assert!(
            cache
                .dependencies()
                .lookup_with_ancestors(graph.root_id().unwrap(), &src)
                .contains(&dst),
            "an edit at relocation source /Source/Inner must invalidate /Dest/Moved"
        );
        Ok(())
    }

    /// A recoverable composition error on an ancestor must not erase a
    /// descendant's own opinions. `/A` references a missing layer — an error the
    /// cache records and continues past — yet `/A/B`'s local opinion still
    /// composes, rather than the child caching an empty index.
    #[test]
    fn ancestor_error_keeps_child_opinions() -> Result<()> {
        let text = r#"#usda 1.0
def "A" (
    references = @nonexistent.usd@
)
{
    def "B"
    {
        custom string marker = "ok"
    }
}
"#;
        let data = crate::usda::parser::Parser::new(text).parse().expect("parse usda");
        let layer = sdf::Layer::new("root.usda", Box::new(crate::usda::TextReader::from_data(data)));
        let graph = LayerGraph::from_layers(vec![layer], 0, Box::new(DefaultResolver::new()), true);
        let mut cache = IndexCache::new(VariantFallbackMap::new(), Vec::new());

        let child = sdf::path("/A/B")?;
        cache.ensure_index(&graph, &child)?;
        assert!(
            !cache.indices[&child].is_empty(),
            "child local opinion must survive the ancestor's unresolved reference"
        );
        assert!(
            cache
                .take_composition_errors()
                .iter()
                .any(|e| matches!(e, Error::UnresolvedLayer { .. })),
            "the ancestor's unresolved reference is recorded"
        );
        Ok(())
    }

    /// A prim's recoverable build error is keyed by its path and replaced on
    /// rebuild, so dropping and recomposing the index (as a layer-stack edit
    /// does via `clear_all_indices` + re-query) does not duplicate it, and a
    /// prim that composes cleanly leaves no stale error behind.
    #[test]
    fn prim_errors_replace_on_rebuild() -> Result<()> {
        let (graph, mut cache) =
            in_memory_stack("#usda 1.0\ndef \"A\" (\n    references = @nonexistent.usd@\n)\n{\n}\n");
        let a = sdf::path("/A")?;
        let unresolved = |c: &IndexCache| {
            c.composition_errors()
                .iter()
                .filter(|e| matches!(e, Error::UnresolvedLayer { .. }))
                .count()
        };

        cache.ensure_index(&graph, &a)?;
        assert_eq!(unresolved(&cache), 1, "the unresolved reference is recorded once");

        // Drop and rebuild — the bookkeeping a SIGNIFICANT layer-stack edit
        // performs (clear_all_indices then a re-query). The error must not double.
        cache.drop_index(&a);
        cache.ensure_index(&graph, &a)?;
        assert_eq!(
            unresolved(&cache),
            1,
            "rebuilding replaces the prim's error, not appends"
        );

        // A prim with no error leaves no entry, so its (absent) errors can't go stale.
        let (clean_graph, mut clean_cache) = in_memory_stack("#usda 1.0\ndef \"A\" {}\n");
        clean_cache.ensure_index(&clean_graph, &a)?;
        assert!(
            clean_cache.composition_errors().is_empty(),
            "a cleanly composing prim records no error"
        );
        Ok(())
    }

    /// A reference whose asset path is a variable expression that fails to
    /// evaluate (here a non-string result) is recoverable: the broken arc is
    /// skipped and recorded as `InvalidExpression`, while the prim's own local
    /// opinion still composes — it does not abort the whole prim index.
    #[test]
    fn invalid_expression_arc_recoverable() -> Result<()> {
        let text = r#"#usda 1.0
def "A" (
    references = @`42`@
)
{
    custom string marker = "ok"
}
"#;
        let data = crate::usda::parser::Parser::new(text).parse().expect("parse usda");
        let layer = sdf::Layer::new("root.usda", Box::new(crate::usda::TextReader::from_data(data)));
        let graph = LayerGraph::from_layers(vec![layer], 0, Box::new(DefaultResolver::new()), true);
        let mut cache = IndexCache::new(VariantFallbackMap::new(), Vec::new());

        let a = sdf::path("/A")?;
        cache.ensure_index(&graph, &a)?;
        let interp = |_: &sdf::TimeSampleMap, _: f64| None;
        assert_eq!(
            cache.value_at(&graph, &sdf::path("/A.marker")?, 0.0, &interp)?,
            Some(Value::String("ok".to_string())),
            "the prim's local opinion survives the broken expression arc"
        );
        assert!(
            cache
                .take_composition_errors()
                .iter()
                .any(|e| matches!(e, Error::InvalidExpression { .. })),
            "the invalid asset-path expression is recorded as a recoverable error"
        );
        Ok(())
    }

    /// A connection authored in a class that targets another instance of the
    /// class but is removed by a stronger `delete` must not emit a spurious
    /// instance-target diagnostic: `classify_inherit_targets` only reports targets
    /// that survive list-op composition, so a deleted target is neither dropped
    /// again nor reported.
    #[test]
    fn class_instance_target_deleted_no_error() -> Result<()> {
        let text = r#"#usda 1.0
def "Scope"
{
    class "LocalClass"
    {
        double y
        double x
        add double x.connect = </Scope/Instance_2.y>
        delete double x.connect = </Scope/Instance_2.y>
    }

    def "Instance_1" (inherits = </Scope/LocalClass>) {}
    def "Instance_2" (inherits = </Scope/LocalClass>) {}
}
"#;
        let (graph, mut cache) = in_memory_stack(text);
        let (targets, _) = cache.compute_attribute_connection_paths(&graph, &sdf::path("/Scope/Instance_1.x")?)?;
        assert!(targets.is_empty(), "the deleted connection target composes to nothing");
        let errors = cache.take_composition_errors();
        assert!(
            !errors.iter().any(|e| matches!(
                e,
                Error::InvalidInstanceTargetPath { .. } | Error::InvalidExternalTargetPath { .. }
            )),
            "a class target removed by a stronger delete must not be reported: {errors:?}"
        );
        Ok(())
    }

    /// An instance-target invalid contribution from a class node drops only that
    /// node's contribution: a stronger local opinion authoring the same target
    /// validly keeps it, while the class's invalid opinion is still reported.
    #[test]
    fn class_instance_target_kept_by_stronger_local() -> Result<()> {
        let text = r#"#usda 1.0
def "Scope"
{
    class "LocalClass"
    {
        double y
        double x
        add double x.connect = </Scope/Instance_2.y>
    }

    def "Instance_1" (inherits = </Scope/LocalClass>)
    {
        add double x.connect = </Scope/Instance_2.y>
    }

    def "Instance_2" (inherits = </Scope/LocalClass>) {}
}
"#;
        let (graph, mut cache) = in_memory_stack(text);
        let (targets, _) = cache.compute_attribute_connection_paths(&graph, &sdf::path("/Scope/Instance_1.x")?)?;
        assert_eq!(
            targets,
            vec![sdf::path("/Scope/Instance_2.y")?],
            "the stronger local connection keeps the target even though the class's is invalid"
        );
        let errors = cache.take_composition_errors();
        assert!(
            errors
                .iter()
                .any(|e| matches!(e, Error::InvalidInstanceTargetPath { .. })),
            "the class node's instance-target contribution is still reported: {errors:?}"
        );
        Ok(())
    }

    /// A reference's asset-path expression authored inside a referenced layer
    /// is evaluated against the composed expression variables, with the
    /// referencing layer stack overriding the referenced one (C++
    /// `PcpExpressionVariables`). The root sets `TARGET = "right.usda"`,
    /// overriding mid.usda's local `TARGET = "wrong.usda"`, so `/Model` resolves
    /// through mid to right.usda — collection must load right.usda for the arc
    /// to compose rather than the locally-named wrong.usda.
    #[test]
    fn expr_vars_compose_across_reference() -> Result<()> {
        let root = format!("{}/fixtures/expr_vars_compose/root.usda", manifest_dir());
        let (graph, mut cache) = collected_stack(&root);
        let interp = |_: &sdf::TimeSampleMap, _: f64| None;
        assert_eq!(
            cache.value_at(&graph, &sdf::path("/Model.source")?, 0.0, &interp)?,
            Some(Value::String("right".to_string())),
            "the referencing layer's TARGET override resolves the nested reference to right.usda"
        );
        Ok(())
    }

    /// A template clip set (`templateAssetPath` + start/end/stride) is
    /// expanded to explicit clips and resolves end to end through
    /// `value_at` (spec 12.3.4.1.3): `clip.1.usda` drives t=1, `clip.2.usda`
    /// drives t=2.
    #[test]
    fn resolves_template_clip_values() -> Result<()> {
        let root = format!("{}/fixtures/clip_template/root.usda", manifest_dir());
        let (graph, mut cache) = single_layer_stack(&root);
        // Exact-match sampler: each clip authors a single sample at its frame.
        let interp =
            |samples: &sdf::TimeSampleMap, t: f64| samples.iter().find(|(time, _)| *time == t).map(|(_, v)| v.clone());

        let size =
            |cache: &mut IndexCache, t: f64| cache.value_at(&graph, &sdf::path("/Model.size").unwrap(), t, &interp);
        assert_eq!(size(&mut cache, 1.0)?, Some(sdf::Value::Double(10.0)));
        assert_eq!(size(&mut cache, 2.0)?, Some(sdf::Value::Double(20.0)));
        Ok(())
    }

    /// A template clip set authored in a sublayer with a layer offset has its
    /// derived schedule retimed into stage time (spec 12.3.4): the offset of 10
    /// shifts `clip.1`'s frame to stage t=11 and `clip.2`'s to t=12.
    #[test]
    fn template_clip_schedule_retimed_by_offset() -> Result<()> {
        let root = format!("{}/fixtures/clip_template_offset/root.usda", manifest_dir());
        let (graph, mut cache) = collected_stack(&root);
        let size =
            |cache: &mut IndexCache, t: f64| cache.value_at(&graph, &sdf::path("/Model.size").unwrap(), t, &exact);
        assert_eq!(size(&mut cache, 11.0)?, Some(Value::Double(10.0)));
        assert_eq!(size(&mut cache, 12.0)?, Some(Value::Double(20.0)));
        Ok(())
    }

    /// When a stronger layer authors explicit `assetPaths` and a weaker
    /// sublayer authors `templateAssetPath` for the same set, the explicit
    /// paths win (spec 12.3.4.1.3) and must anchor on the layer that authored
    /// them: `@./clip.usda@` resolves next to the root, not the sublayer.
    #[test]
    fn explicit_asset_paths_anchor_over_template() -> Result<()> {
        let root = format!("{}/fixtures/clip_asset_anchor/root.usda", manifest_dir());
        let (graph, mut cache) = collected_stack(&root);
        let size =
            |cache: &mut IndexCache, t: f64| cache.value_at(&graph, &sdf::path("/Model.size").unwrap(), t, &exact);
        assert_eq!(size(&mut cache, 0.0)?, Some(Value::Double(42.0)));
        Ok(())
    }

    /// Exact-match sampler: a clip resolves only at a frame it authors.
    fn exact(samples: &sdf::TimeSampleMap, t: f64) -> Option<Value> {
        samples.iter().find(|(time, _)| *time == t).map(|(_, v)| v.clone())
    }

    /// Linear sampler over `float` samples, held outside the sample range.
    fn lerp(samples: &sdf::TimeSampleMap, t: f64) -> Option<Value> {
        let as_f = |v: &Value| match v {
            Value::Float(f) => *f as f64,
            Value::Double(d) => *d,
            _ => 0.0,
        };
        let first = samples.first()?;
        if t <= first.0 {
            return Some(first.1.clone());
        }
        let last = samples.last()?;
        if t >= last.0 {
            return Some(last.1.clone());
        }
        let w = samples.windows(2).find(|w| t >= w[0].0 && t <= w[1].0)?;
        let f = (t - w[0].0) / (w[1].0 - w[0].0);
        Some(Value::Double(as_f(&w[0].1) + (as_f(&w[1].1) - as_f(&w[0].1)) * f))
    }

    /// A gap in the active clip falls to the manifest's authored default
    /// (spec 12.3.4.6): `t=0` is sampled from the clip, `t=10` (no sample)
    /// resolves to the manifest default `99.0`.
    #[test]
    fn missing_clip_value_uses_manifest_default() -> Result<()> {
        let root = format!("{}/fixtures/clip_missing_default/root.usda", manifest_dir());
        let (graph, mut cache) = single_layer_stack(&root);
        let size =
            |cache: &mut IndexCache, t: f64| cache.value_at(&graph, &sdf::path("/Model.size").unwrap(), t, &exact);
        assert_eq!(size(&mut cache, 0.0)?, Some(Value::Double(5.0)));
        assert_eq!(size(&mut cache, 10.0)?, Some(Value::Float(99.0)));
        Ok(())
    }

    /// A manifest-declared attribute with no default and a gap is
    /// authoritatively absent (spec 12.3.4.6): the clip owns the attribute, so
    /// the gap blocks fall-through to the referenced time samples (`777.0`) and
    /// resolves to `None` rather than the weaker value.
    #[test]
    fn missing_clip_value_without_default_blocks() -> Result<()> {
        let root = format!("{}/fixtures/clip_missing_block/root.usda", manifest_dir());
        let (graph, mut cache) = collected_stack(&root);
        let size =
            |cache: &mut IndexCache, t: f64| cache.value_at(&graph, &sdf::path("/Model.size").unwrap(), t, &exact);
        assert_eq!(size(&mut cache, 0.0)?, Some(Value::Double(5.0)));
        assert_eq!(size(&mut cache, 10.0)?, None);
        Ok(())
    }

    /// With `interpolateMissingClipValues`, a gap is filled by interpolating
    /// across the surrounding contributing clips (spec 12.3.4.7): the empty
    /// middle clip at `t=15` interpolates `0.0` (t=0 clip) and `100.0`
    /// (t=20 clip) to `75.0`.
    #[test]
    fn interpolate_missing_clip_values_across_clips() -> Result<()> {
        let root = format!("{}/fixtures/clip_missing_interp/root.usda", manifest_dir());
        let (graph, mut cache) = single_layer_stack(&root);
        let size =
            |cache: &mut IndexCache, t: f64| cache.value_at(&graph, &sdf::path("/Model.size").unwrap(), t, &lerp);
        assert_eq!(size(&mut cache, 0.0)?, Some(Value::Double(0.0)));
        assert_eq!(size(&mut cache, 15.0)?, Some(Value::Double(75.0)));
        assert_eq!(size(&mut cache, 20.0)?, Some(Value::Double(100.0)));
        Ok(())
    }

    /// Instances sharing a prototype compose their subtree once: every
    /// instance's descendants redirect into the shared prototype namespace, so
    /// the descendant is indexed under `/__Prototype_N` and never under an
    /// instance's own path (spec 11.3.3).
    #[test]
    fn instances_share_prototype() -> Result<()> {
        let root = format!("{}/fixtures/instancing_shared.usda", manifest_dir());
        let (graph, mut cache) = single_layer_stack(&root);
        let interp = |_: &sdf::TimeSampleMap, _: f64| None;

        // Query /A first so it mints /__Prototype_0 for its key.
        let size = |cache: &mut IndexCache, p: &str| cache.value_at(&graph, &sdf::path(p).unwrap(), 0.0, &interp);
        assert_eq!(size(&mut cache, "/A/Child.size")?, Some(sdf::Value::Double(5.0)));
        assert_eq!(size(&mut cache, "/B/Child.size")?, Some(sdf::Value::Double(5.0)));
        assert_eq!(size(&mut cache, "/C/Child.size")?, Some(sdf::Value::Double(9.0)));

        // /A and /B share /__Prototype_0; /C uses /__Prototype_1. The shared
        // subtree composes once in each prototype namespace, and no instance's
        // own descendant path is ever indexed.
        assert!(cache.is_indexed(&sdf::path("/__Prototype_0/Child")?));
        assert!(cache.is_indexed(&sdf::path("/__Prototype_1/Child")?));
        assert!(!cache.is_indexed(&sdf::path("/A/Child")?));
        assert!(!cache.is_indexed(&sdf::path("/B/Child")?));
        assert!(!cache.is_indexed(&sdf::path("/C/Child")?));
        Ok(())
    }

    /// Reading a deep instance-proxy value composes the shared prototype subtree
    /// once: the instance-ness check on an intermediate proxy prim redirects to
    /// the shared `/__Prototype_N` index instead of composing a throwaway literal
    /// index per instance, so no intermediate proxy path is ever indexed (spec
    /// 11.3.3).
    #[test]
    fn proxy_descendants_share_prototype() -> Result<()> {
        let root = format!("{}/fixtures/instancing_deep.usda", manifest_dir());
        let (graph, mut cache) = single_layer_stack(&root);
        let interp = |_: &sdf::TimeSampleMap, _: f64| None;
        let v = |cache: &mut IndexCache, p: &str| cache.value_at(&graph, &sdf::path(p).unwrap(), 0.0, &interp);

        // Reading the deep value walks the proxy ancestors (/A/Mid, /B/Mid),
        // testing each for instance-ness.
        assert_eq!(v(&mut cache, "/A/Mid/Leaf.v")?, Some(sdf::Value::Double(1.0)));
        assert_eq!(v(&mut cache, "/B/Mid/Leaf.v")?, Some(sdf::Value::Double(1.0)));

        // The shared subtree composes once, under the prototype namespace.
        assert!(cache.is_indexed(&sdf::path("/__Prototype_0/Mid")?));
        assert!(cache.is_indexed(&sdf::path("/__Prototype_0/Mid/Leaf")?));
        // No intermediate proxy prim is composed literally at an instance path.
        for p in ["/A/Mid", "/B/Mid", "/A/Mid/Leaf", "/B/Mid/Leaf"] {
            assert!(!cache.is_indexed(&sdf::path(p)?), "{p} must not be indexed literally");
        }
        Ok(())
    }

    /// A nested instance inside a prototype namespace mints its own prototype and
    /// its descendants redirect onto it: both an outer proxy (`/A/Nested/Leaf`)
    /// and the prototype-namespace path (`/__Prototype_0/Nested/Leaf`) resolve
    /// through the nested prototype, so the nested descendant never composes in
    /// place under the outer prototype (spec 11.3.3).
    #[test]
    fn nested_prototype_proxy_redirects() -> Result<()> {
        let root = format!("{}/fixtures/instancing_nested_in_prototype.usda", manifest_dir());
        let (graph, mut cache) = single_layer_stack(&root);
        let interp = |_: &sdf::TimeSampleMap, _: f64| None;
        let v = |cache: &mut IndexCache, p: &str| cache.value_at(&graph, &sdf::path(p).unwrap(), 0.0, &interp);

        // /A mints /__Prototype_0 (for /Outer); the nested instance mints
        // /__Prototype_1 (for /Inner). Both the outer proxy and the
        // prototype-namespace path resolve the nested leaf.
        assert_eq!(v(&mut cache, "/A/Nested/Leaf.v")?, Some(sdf::Value::Double(3.0)));
        assert_eq!(
            v(&mut cache, "/__Prototype_0/Nested/Leaf.v")?,
            Some(sdf::Value::Double(3.0))
        );

        // Both redirect to the nested prototype; neither the prototype-namespace
        // nested descendant nor the outer proxy is composed in place.
        assert!(cache.is_indexed(&sdf::path("/__Prototype_1/Leaf")?));
        assert!(!cache.is_indexed(&sdf::path("/__Prototype_0/Nested/Leaf")?));
        assert!(!cache.is_indexed(&sdf::path("/A/Nested/Leaf")?));

        // The nested instance reached via the instance namespace (/A/Nested) and
        // via the prototype namespace (/__Prototype_0/Nested) is the same shared
        // composition, so both resolve to one nested prototype — exactly two
        // prototypes total, not three.
        assert_eq!(
            cache.prototype_of(&graph, &sdf::path("/A/Nested")?)?,
            cache.prototype_of(&graph, &sdf::path("/__Prototype_0/Nested")?)?,
        );
        assert_eq!(cache.prototypes().len(), 2);
        Ok(())
    }

    /// A reference nested inside the prototype (below the instanceable arc) is
    /// shared (spec 11.3.3): its opinions reach the instance through the direct
    /// instanceable arc, so they survive in the instance's child names and
    /// descendants. The nested arc is authored in the referenced namespace, so
    /// its namespace depth is shallow — a flat `namespace_depth < instance_depth`
    /// test would wrongly drop it as an outer reference; the structural trunk
    /// partition keeps it because its parent (the prototype root) is not on the
    /// instance trunk.
    #[test]
    fn nested_reference_in_prototype_shared() -> Result<()> {
        let root = format!("{}/fixtures/instancing_nested_reference.usda", manifest_dir());
        let (graph, mut cache) = single_layer_stack(&root);
        let inst = sdf::path("/World/Inst")?;

        // The instance is at namespace depth 2 and is a real instance.
        assert!(cache.is_instance(&graph, &inst)?, "/World/Inst resolves as an instance");

        // Child names come from the shared prototype: ProtoChild from /Proto and
        // OtherChild from the nested /Other reference (the leaked case the flat
        // depth proxy dropped).
        let children = cache.prim_children(&graph, &inst)?;
        assert!(
            children.contains(&"ProtoChild".to_string()),
            "prototype child must appear: {children:?}"
        );
        assert!(
            children.contains(&"OtherChild".to_string()),
            "nested-reference child must appear: {children:?}"
        );

        // The nested reference's opinions resolve on the shared descendant.
        let interp = |_: &sdf::TimeSampleMap, _: f64| None;
        assert_eq!(
            cache.value_at(&graph, &sdf::path("/World/Inst/OtherChild.size")?, 0.0, &interp)?,
            Some(Value::Double(7.0)),
            "nested-reference descendant value survives in the shared subtree"
        );
        assert_eq!(
            cache.value_at(&graph, &sdf::path("/World/Inst.otherAttr")?, 0.0, &interp)?,
            Some(Value::Double(5.0)),
            "nested-reference attribute survives on the instance root"
        );
        Ok(())
    }

    /// `instances_of` is sorted by path, so the result is independent of the
    /// order instances were registered (spec 11.3.3).
    #[test]
    fn instances_of_sorted() -> Result<()> {
        let root = format!("{}/fixtures/instancing_shared.usda", manifest_dir());
        let (graph, mut cache) = single_layer_stack(&root);

        // Register /B before /A so registration order is [/B, /A].
        let proto = cache.prototype_of(&graph, &sdf::path("/B")?)?.unwrap();
        assert_eq!(cache.prototype_of(&graph, &sdf::path("/A")?)?, Some(proto.clone()));

        // The returned instances are still sorted by path.
        assert_eq!(cache.instances_of(&proto), vec![sdf::path("/A")?, sdf::path("/B")?]);
        Ok(())
    }

    /// A significant change (here, flipping `instanceable`) clears the
    /// prototype registry so stale instance-to-prototype mappings do not
    /// persist (spec 11.3.3).
    #[test]
    fn instance_change_invalidates_prototypes() -> Result<()> {
        let root = format!("{}/fixtures/instancing_shared.usda", manifest_dir());
        let (mut graph, mut cache) = single_layer_stack(&root);
        let root_id = graph.root_id().unwrap();

        assert!(cache.prototype_of(&graph, &sdf::path("/A")?)?.is_some());
        assert!(!cache.prototypes().is_empty());

        let mut cl = sdf::ChangeList::new();
        cl.entry_mut(&sdf::path("/A")?)
            .info_changed
            .insert(sdf::FieldKey::Instanceable.as_str());
        let mut changes = crate::pcp::Changes::new();
        changes.did_change(&cache, &graph, &[(root_id, cl)]);
        changes.apply(&mut cache, &mut graph);

        assert!(cache.prototypes().is_empty());
        Ok(())
    }

    /// Authors a `layerRelocates` edit on the root layer and drives it through
    /// the change pipeline, returning the graph's diagnostics afterward.
    fn relocate_edit(graph: &mut LayerGraph, cache: &mut IndexCache, text: &str) -> Vec<Error> {
        let root_id = graph.root_id().unwrap();
        graph.get_mut(root_id).expect("root layer exists").layer = parse_layer(text);
        let mut cl = sdf::ChangeList::new();
        cl.entry_mut(&Path::abs_root())
            .info_changed
            .insert(sdf::FieldKey::LayerRelocates.as_str());
        let mut changes = crate::pcp::Changes::new();
        changes.did_change(cache, graph, &[(root_id, cl)]);
        changes.apply(cache, graph);
        graph.errors()
    }

    /// A `layerRelocates` edit that authors an invalid relocate after stage
    /// creation must surface an `InvalidRelocate` diagnostic from the graph,
    /// which the recompute path refreshes in place.
    #[test]
    fn invalid_relocate_edit_surfaces_error() -> Result<()> {
        let (mut graph, mut cache) = in_memory_stack("#usda 1.0\ndef \"A\" {}\n");
        // No relocates authored yet, so the graph holds no diagnostics.
        assert!(graph.errors().is_empty());

        // Author an invalid relocate (the target is an ancestor of the source).
        let errors = relocate_edit(
            &mut graph,
            &mut cache,
            "#usda 1.0\n(\n    relocates = { </A/B/C>: </A> }\n)\ndef \"A\" {}\n",
        );
        assert!(
            errors.iter().any(|e| matches!(e, Error::InvalidRelocate { .. })),
            "an invalid relocate authored after construction must be retained"
        );
        Ok(())
    }

    /// Re-authoring a valid relocate over an invalid one clears the diagnostic,
    /// and recomputing the same state twice does not duplicate it — the graph's
    /// relocate-error bucket is replaced wholesale on every rebuild.
    #[test]
    fn relocate_error_clears_and_dedups() -> Result<()> {
        let (mut graph, mut cache) = in_memory_stack("#usda 1.0\ndef \"A\" {}\n");

        // Author an invalid relocate, then the same edit twice: still exactly one.
        let invalid = "#usda 1.0\n(\n    relocates = { </A/B/C>: </A> }\n)\ndef \"A\" {}\n";
        let _ = relocate_edit(&mut graph, &mut cache, invalid);
        let errors = relocate_edit(&mut graph, &mut cache, invalid);
        assert_eq!(
            errors
                .iter()
                .filter(|e| matches!(e, Error::InvalidRelocate { .. }))
                .count(),
            1,
            "recomputing the same invalid relocate must not duplicate the diagnostic"
        );

        // Re-author a valid relocate; the stale invalid diagnostic disappears.
        let valid = "#usda 1.0\n(\n    relocates = { </A/B>: </A/C> }\n)\ndef \"A\" {}\n";
        let errors = relocate_edit(&mut graph, &mut cache, valid);
        assert!(
            !errors.iter().any(|e| matches!(e, Error::InvalidRelocate { .. })),
            "fixing the relocate must clear the diagnostic"
        );
        Ok(())
    }
}