Skip to main content

ifc_model/index/
reverse.rs

1//! Target-to-referrer index: "which entities point at this one?"
2//!
3//! # Why this is not built during insertion
4//!
5//! The type index is built eagerly because almost every consumer asks for
6//! "every IfcWall". The reverse index is different: a codec that parses a file
7//! and writes it straight back never asks who references what, and paying for
8//! the index on every load would tax the common path to serve the rarer one.
9//!
10//! So it is built on first request, from a `&Model`. [`ReverseIndex::build`]
11//! hands back a value the caller owns and can drop: a caller doing one lookup
12//! pays for one scan; a caller doing thousands builds it once.
13//! [`Model::reverse_index`] builds one the model keeps, and from then on every
14//! write updates it (`maintained.rs`), so editing a large model does not
15//! rescan it for each edit (#587).
16//!
17//! # Slots are recorded, not just referrers
18//!
19//! IFC relationships are objectified: `IfcRelContainedInSpatialStructure` holds
20//! its elements in one attribute and its container in another. "Who references
21//! this storey" is not enough -- a consumer must know *which slot* the
22//! reference sat in to tell containment from the inverse. So each hit carries
23//! the attribute index.
24
25use ahash::AHashMap;
26
27use crate::value::EntityId;
28use crate::Model;
29
30/// One reference to a target entity.
31#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
32pub struct Referrer {
33    /// The entity holding the reference.
34    pub from: EntityId,
35    /// Which top-level attribute slot of `from` the reference sits in.
36    ///
37    /// Nested references inside a `List` or `Typed` wrapper report the index of
38    /// the outermost attribute, because that is the slot the schema names.
39    pub slot: usize,
40}
41
42/// Reverse-reference index over a model snapshot.
43///
44/// A value from [`ReverseIndex::build`] reflects the model as it was when
45/// built: mutating the model afterwards does not update it, and the borrow
46/// checker enforces that for the common `&Model` case. The one behind
47/// [`Model::reverse_index`] is kept current by the model's writes.
48#[derive(Debug, Clone, Default, PartialEq, Eq)]
49pub struct ReverseIndex {
50    /// Target to the entities referencing it, sorted and deduplicated so
51    /// results are deterministic across runs.
52    incoming: AHashMap<EntityId, Vec<Referrer>>,
53}
54
55impl ReverseIndex {
56    /// Scan every entity once and record each reference by target.
57    #[must_use]
58    pub fn build(model: &Model) -> Self {
59        // File order, so the result is stable rather than hash-ordered.
60        Self::collect(model, model.ids())
61    }
62
63    /// The references held by `referrers` only, in one pass over them.
64    ///
65    /// For every target, [`ReverseIndex::referrers`] equals what
66    /// [`ReverseIndex::build`] reports for it, restricted to those
67    /// entities: the same slots, ascending. Ids the model does not hold are
68    /// skipped, and an id repeated counts once. A caller that knows which
69    /// record types can point at what it asks about pays for those records,
70    /// not for the model (#608).
71    #[must_use]
72    pub fn build_from(model: &Model, referrers: impl IntoIterator<Item = EntityId>) -> Self {
73        let mut ids: Vec<EntityId> = referrers.into_iter().collect();
74        ids.sort_unstable();
75        ids.dedup();
76        Self::collect(model, ids)
77    }
78
79    fn collect(model: &Model, from: impl IntoIterator<Item = EntityId>) -> Self {
80        let mut incoming: AHashMap<EntityId, Vec<Referrer>> = AHashMap::new();
81        for from in from {
82            let Some(entity) = model.get(from) else {
83                continue;
84            };
85            for (slot, attribute) in entity.attributes.iter().enumerate() {
86                attribute.for_each_ref(&mut |target| {
87                    incoming
88                        .entry(target)
89                        .or_default()
90                        .push(Referrer { from, slot });
91                });
92            }
93        }
94        // An attribute may name the same target twice (a degenerate polyline
95        // closing on its start point). Report the pair once per slot.
96        for referrers in incoming.values_mut() {
97            referrers.sort_unstable();
98            referrers.dedup();
99        }
100        Self { incoming }
101    }
102
103    /// Records `referrer` of `target`, keeping the ascending order and the
104    /// one-pair-per-slot rule of [`ReverseIndex::build`].
105    pub(crate) fn link(&mut self, target: EntityId, referrer: Referrer) {
106        let referrers = self.incoming.entry(target).or_default();
107        if let Err(at) = referrers.binary_search(&referrer) {
108            referrers.insert(at, referrer);
109        }
110    }
111
112    /// Forgets `referrer` of `target`, and `target` once nothing refers to
113    /// it.
114    pub(crate) fn unlink(&mut self, target: EntityId, referrer: Referrer) {
115        let Some(referrers) = self.incoming.get_mut(&target) else {
116            return;
117        };
118        if let Ok(at) = referrers.binary_search(&referrer) {
119            referrers.remove(at);
120        }
121        if referrers.is_empty() {
122            self.incoming.remove(&target);
123        }
124    }
125
126    /// Every reference pointing at `target`, in ascending `(from, slot)` order.
127    #[must_use]
128    pub fn referrers(&self, target: EntityId) -> &[Referrer] {
129        self.incoming.get(&target).map_or(&[], Vec::as_slice)
130    }
131
132    /// Entities referencing `target` from the given attribute slot.
133    ///
134    /// This is the query objectified relationships need: "which relationship
135    /// entities name me in their *RelatingStructure* slot".
136    pub fn referrers_in_slot(
137        &self,
138        target: EntityId,
139        slot: usize,
140    ) -> impl Iterator<Item = EntityId> + '_ {
141        self.referrers(target)
142            .iter()
143            .filter(move |r| r.slot == slot)
144            .map(|r| r.from)
145    }
146
147    /// Whether anything references `target`.
148    #[must_use]
149    pub fn is_referenced(&self, target: EntityId) -> bool {
150        !self.referrers(target).is_empty()
151    }
152
153    /// Number of distinct targets that have at least one referrer.
154    #[must_use]
155    pub fn len(&self) -> usize {
156        self.incoming.len()
157    }
158
159    /// Whether no entity references any other.
160    #[must_use]
161    pub fn is_empty(&self) -> bool {
162        self.incoming.is_empty()
163    }
164}