Skip to main content

ifc_model/index/
maintained.rs

1//! Derived indexes a model keeps current once they are built (#587).
2//!
3//! The reverse index and a GlobalId index are built on the first query, one
4//! scan each, and every primitive write keeps them current after that: a
5//! write computes the [`Footprint`] of what it changes before and after, and
6//! [`Derived::update`] moves only the difference. A model nobody asks never
7//! builds them, so a codec read costs what it always did (ADR 0023).
8//!
9//! The GlobalId index is schema-free: it lists every entity whose first
10//! attribute is text that [`Guid::parse`] accepts, which is where IFC puts
11//! the `GlobalId` of every `IfcRoot`. Callers that know the schema filter
12//! the candidates by type.
13
14use std::fmt;
15use std::sync::OnceLock;
16
17use ahash::AHashMap;
18
19use super::reverse::{Referrer, ReverseIndex};
20use crate::entity::Entity;
21use crate::guid::Guid;
22use crate::model::Model;
23use crate::value::{EntityId, Value};
24
25/// The indexes of one model, each built on first request.
26#[derive(Clone, Default)]
27pub(crate) struct Derived {
28    reverse: OnceLock<ReverseIndex>,
29    global_ids: OnceLock<GlobalIds>,
30}
31
32impl fmt::Debug for Derived {
33    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
34        let state = |built: bool| if built { "built" } else { "unbuilt" };
35        f.debug_struct("Derived")
36            .field(
37                "reverse",
38                &format_args!("{}", state(self.reverse.get().is_some())),
39            )
40            .field(
41                "global_ids",
42                &format_args!("{}", state(self.global_ids.get().is_some())),
43            )
44            .finish()
45    }
46}
47
48/// Entities by the GlobalId text in their first attribute.
49#[derive(Debug, Clone, Default, PartialEq, Eq)]
50pub(crate) struct GlobalIds {
51    unique: AHashMap<Guid, EntityId>,
52    /// Ascending, at least two ids.
53    shared: AHashMap<Guid, Vec<EntityId>>,
54}
55
56impl GlobalIds {
57    pub(crate) fn build(model: &Model) -> Self {
58        let mut index = Self::default();
59        for (id, entity) in model.iter() {
60            if let Some(guid) = global_id_of(entity) {
61                index.add(guid, id);
62            }
63        }
64        index
65    }
66
67    pub(crate) fn candidates(&self, guid: &Guid) -> &[EntityId] {
68        if let Some(id) = self.unique.get(guid) {
69            std::slice::from_ref(id)
70        } else {
71            self.shared.get(guid).map_or(&[], Vec::as_slice)
72        }
73    }
74
75    fn add(&mut self, guid: Guid, id: EntityId) {
76        if let Some(ids) = self.shared.get_mut(&guid) {
77            if let Err(at) = ids.binary_search(&id) {
78                ids.insert(at, id);
79            }
80        } else if let Some(&holder) = self.unique.get(&guid) {
81            if holder != id {
82                self.unique.remove(&guid);
83                self.shared
84                    .insert(guid, vec![holder.min(id), holder.max(id)]);
85            }
86        } else {
87            self.unique.insert(guid, id);
88        }
89    }
90
91    fn remove(&mut self, guid: Guid, id: EntityId) {
92        if self.unique.get(&guid) == Some(&id) {
93            self.unique.remove(&guid);
94        } else if let Some(ids) = self.shared.get_mut(&guid) {
95            ids.retain(|held| *held != id);
96            if ids.len() == 1 {
97                let last = ids[0];
98                self.shared.remove(&guid);
99                self.unique.insert(guid, last);
100            }
101        }
102    }
103}
104
105fn global_id_of(entity: &Entity) -> Option<Guid> {
106    match entity.attributes.first() {
107        Some(Value::Text(text)) => Guid::parse(text),
108        _ => None,
109    }
110}
111
112/// What an entity contributes to the indexes: its references by slot and
113/// its GlobalId text.
114#[derive(Debug, Clone, Default, PartialEq, Eq)]
115pub(crate) struct Footprint {
116    /// Sorted and deduplicated, as the reverse index stores them.
117    refs: Vec<(usize, EntityId)>,
118    global_id: Option<Guid>,
119}
120
121impl Footprint {
122    /// Everything `entity` contributes.
123    pub(crate) fn of(entity: &Entity) -> Self {
124        let mut refs = Vec::new();
125        for (slot, attribute) in entity.attributes.iter().enumerate() {
126            attribute.for_each_ref(&mut |target| refs.push((slot, target)));
127        }
128        refs.sort_unstable();
129        refs.dedup();
130        Self {
131            refs,
132            global_id: global_id_of(entity),
133        }
134    }
135
136    /// What `slots` of `entity` contribute; a slot past the end contributes
137    /// nothing, and the GlobalId only counts when slot 0 is among them.
138    pub(crate) fn of_slots(entity: &Entity, slots: &[usize]) -> Self {
139        let mut refs = Vec::new();
140        for &slot in slots {
141            if let Some(attribute) = entity.attributes.get(slot) {
142                attribute.for_each_ref(&mut |target| refs.push((slot, target)));
143            }
144        }
145        refs.sort_unstable();
146        refs.dedup();
147        Self {
148            refs,
149            global_id: if slots.contains(&0) {
150                global_id_of(entity)
151            } else {
152                None
153            },
154        }
155    }
156}
157
158impl Derived {
159    pub(crate) fn is_built(&self) -> bool {
160        self.reverse.get().is_some() || self.global_ids.get().is_some()
161    }
162
163    /// Frees both indexes.
164    pub(crate) fn clear(&mut self) {
165        *self = Self::default();
166    }
167
168    /// Moves every built index from the `before` footprint of `id` to the
169    /// `after` one; `None` is an entity that was absent (or is removed).
170    pub(crate) fn update(
171        &mut self,
172        id: EntityId,
173        before: Option<&Footprint>,
174        after: Option<&Footprint>,
175    ) {
176        let none = Footprint::default();
177        let (before, after) = (before.unwrap_or(&none), after.unwrap_or(&none));
178        if let Some(reverse) = self.reverse.get_mut() {
179            for &(slot, target) in &before.refs {
180                if after.refs.binary_search(&(slot, target)).is_err() {
181                    reverse.unlink(target, Referrer { from: id, slot });
182                }
183            }
184            for &(slot, target) in &after.refs {
185                if before.refs.binary_search(&(slot, target)).is_err() {
186                    reverse.link(target, Referrer { from: id, slot });
187                }
188            }
189        }
190        if let Some(global_ids) = self.global_ids.get_mut() {
191            if before.global_id != after.global_id {
192                if let Some(guid) = before.global_id {
193                    global_ids.remove(guid, id);
194                }
195                if let Some(guid) = after.global_id {
196                    global_ids.add(guid, id);
197                }
198            }
199        }
200    }
201}
202
203impl Model {
204    /// The reverse index of this model, built on the first call (one scan,
205    /// decoding every entity) and kept current by every write after that.
206    ///
207    /// Equal to [`ReverseIndex::build`] at every moment. Cloning the model
208    /// clones the index; [`Model::drop_derived_indexes`] frees it.
209    pub fn reverse_index(&self) -> &ReverseIndex {
210        self.derived()
211            .reverse
212            .get_or_init(|| ReverseIndex::build(self))
213    }
214
215    /// Entities whose first attribute is the text of `global_id`, ascending
216    /// by id; built on the first call and kept current like
217    /// [`Model::reverse_index`].
218    ///
219    /// Schema-free: it lists any entity with that text first, so a caller
220    /// that knows the schema filters by type (`IfcRoot`).
221    pub fn global_id_candidates(&self, global_id: &Guid) -> &[EntityId] {
222        self.derived()
223            .global_ids
224            .get_or_init(|| GlobalIds::build(self))
225            .candidates(global_id)
226    }
227
228    /// Frees the reverse and GlobalId indexes; the next query rebuilds them.
229    pub fn drop_derived_indexes(&mut self) {
230        self.derived_mut().clear();
231    }
232
233    /// The reverse index if something already built it, else `None`; it
234    /// never builds it. A lookup that would rather scan a few record types
235    /// than build the whole index for one question asks this first (#608).
236    pub fn reverse_index_if_built(&self) -> Option<&ReverseIndex> {
237        self.derived().reverse.get()
238    }
239
240    /// Whether a write must report its footprints.
241    pub(crate) fn derived_is_built(&self) -> bool {
242        self.derived().is_built()
243    }
244
245    /// Tells the built indexes that `id` went from `before` to `after`.
246    pub(crate) fn note_write(
247        &mut self,
248        id: EntityId,
249        before: Option<Footprint>,
250        after: Option<Footprint>,
251    ) {
252        self.derived_mut()
253            .update(id, before.as_ref(), after.as_ref());
254    }
255}