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}