step_io/
refgraph.rs

1//! [`RefGraph`] — reverse-reference index over a [`StepModel`].
2//!
3//! The model stores references in the forward direction: an entity points to
4//! what it uses. Many read queries want the inverse ("what references this
5//! entity?") — the [`scene`](crate::scene) handles need it to walk an
6//! assembly or a shape upward. [`StepModel::ref_graph`] builds the index by
7//! inverting every entity's outgoing references; the enumeration underneath is
8//! generated, so no entity type is missed.
9
10use std::collections::HashMap;
11
12use crate::StepModel;
13use crate::generated::model::EntityKey;
14use crate::generated::walk::for_each_entity;
15use crate::generated::write::Writer;
16
17/// An inverse-reference index: for each entity, the entities that reference it.
18pub struct RefGraph {
19    referrers: HashMap<EntityKey, Vec<EntityKey>>,
20}
21
22impl StepModel {
23    /// Build the reverse-reference index for this model.
24    ///
25    /// O(total references); builds the whole index in one pass. Build once and
26    /// reuse for many reverse queries.
27    #[must_use]
28    pub fn ref_graph(&self) -> RefGraph {
29        let writer = Writer::new(self);
30        let mut referrers: HashMap<EntityKey, Vec<EntityKey>> = HashMap::new();
31        let mut deps = Vec::new();
32        for_each_entity(self, |referrer| {
33            deps.clear();
34            writer.deps_of(referrer, &mut deps);
35            for &target in &deps {
36                referrers.entry(target).or_default().push(referrer);
37            }
38        });
39        RefGraph { referrers }
40    }
41}
42
43impl RefGraph {
44    /// The entities that reference `target` (empty if none). Order is the model's
45    /// entity-walk order.
46    #[must_use]
47    pub fn referrers(&self, target: EntityKey) -> &[EntityKey] {
48        self.referrers.get(&target).map_or(&[], Vec::as_slice)
49    }
50}
step_io/refgraph.rs

step_io/
refgraph.rs
