openbim_ifcx/compose/
tree.rs

1//! Composition: expand flattened nodes into a resolved tree.
2//!
3//! This is the second half of composition, upstream's `ComposeNode`,
4//! `FindRootsOrCycles`, and `CreateArtificialRoot`
5//! (`src/ifcx-core/composition/{compose,cycles}.ts` in
6//! buildingSMART/IFC5-development).
7
8use std::error::Error;
9use std::fmt;
10use std::sync::Arc;
11
12use indexmap::IndexMap;
13use serde_json::Value;
14
15use super::flatten::FlatNode;
16
17/// One node of the composed tree. Upstream calls this a post-composition
18/// node.
19///
20/// Children are shared through [`Arc`]: every instance that inherits a type
21/// points at the same composed sub-tree instead of a copy. A sub-tree is
22/// copied, one node at a time along the edited path, only where a path such
23/// as `instance/Body` edits it.
24#[derive(Debug, Clone, Default, PartialEq)]
25pub struct ComposedNode {
26    /// The path whose opinions started this node, upstream's `node` field.
27    /// A child reached through `children: {"Body": "b1"}` has path `b1`; a
28    /// child copied from an inherited node keeps that node's path. Empty for
29    /// the artificial root.
30    pub path: String,
31    /// Inherited attributes first, then local ones, which win.
32    pub attributes: IndexMap<String, Arc<Value>>,
33    pub children: IndexMap<String, Arc<ComposedNode>>,
34}
35
36impl ComposedNode {
37    /// Follows child names separated by `/`, as upstream's
38    /// `GetChildNodeWithPath`. An empty path returns this node.
39    pub fn descendant(self: &Arc<Self>, path: &str) -> Option<&Arc<ComposedNode>> {
40        let mut node = self;
41        let mut rest = path;
42        loop {
43            if rest.is_empty() {
44                return Some(node);
45            }
46            let (name, tail) = match rest.split_once('/') {
47                Some((name, tail)) => (name, Some(tail)),
48                None => (rest, None),
49            };
50            node = node.children.get(name)?;
51            match tail {
52                Some(tail) => rest = tail,
53                None => return Some(node),
54            }
55        }
56    }
57}
58
59impl Drop for ComposedNode {
60    // The default drop recurses once per tree level. Unwind children that
61    // nothing else shares with an explicit stack instead.
62    fn drop(&mut self) {
63        let mut stack: Vec<Arc<ComposedNode>> =
64            self.children.drain(..).map(|(_, child)| child).collect();
65        while let Some(child) = stack.pop() {
66            if let Some(mut child) = Arc::into_inner(child) {
67                stack.extend(child.children.drain(..).map(|(_, c)| c));
68            }
69        }
70    }
71}
72
73/// Why flattened nodes could not be composed.
74#[derive(Debug, Clone, PartialEq, Eq)]
75#[non_exhaustive]
76pub enum ComposeError {
77    /// References loop back to where they started. `cycle` lists head paths
78    /// (the part before the first `/`); each one references the next and
79    /// the last references the first. It is never empty.
80    Cycle { cycle: Vec<String> },
81    /// `reference`, named in `inherits` or `children` of the node at `path`,
82    /// names no node, or names a child that does not exist.
83    UnknownReference { path: String, reference: String },
84}
85
86impl fmt::Display for ComposeError {
87    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
88        match self {
89            Self::Cycle { cycle } => {
90                write!(f, "reference cycle: ")?;
91                for path in cycle {
92                    write!(f, "{path} -> ")?;
93                }
94                write!(f, "{}", cycle.first().map_or("", String::as_str))
95            }
96            Self::UnknownReference { path, reference } => {
97                write!(f, "node {path} references unknown node {reference}")
98            }
99        }
100    }
101}
102
103impl Error for ComposeError {}
104
105/// The composed tree of a set of flattened nodes.
106#[derive(Debug, Clone)]
107pub struct Composition {
108    /// Composed node per head path, in order of first appearance.
109    heads: IndexMap<String, Arc<ComposedNode>>,
110    roots: Vec<String>,
111}
112
113impl Composition {
114    /// Paths without `/` that no `inherits` or `children` reference names,
115    /// in order of first appearance.
116    pub fn roots(&self) -> &[String] {
117        &self.roots
118    }
119
120    /// The composed node at `path`, which is a node path optionally followed
121    /// by child names: `wall`, `wall/Body`, `wall/Body/Mesh`.
122    pub fn get(&self, path: &str) -> Option<&Arc<ComposedNode>> {
123        let (head, tail) = split_head(path);
124        self.heads.get(head)?.descendant(tail)
125    }
126
127    /// An artificial root with path `""`, no attributes, and every root as
128    /// a child named by its path, as upstream's `CreateArtificialRoot`.
129    pub fn root(&self) -> ComposedNode {
130        ComposedNode {
131            path: String::new(),
132            attributes: IndexMap::new(),
133            children: self
134                .roots
135                .iter()
136                .map(|root| (root.clone(), self.heads[root.as_str()].clone()))
137                .collect(),
138        }
139    }
140}
141
142/// `head/a/b` to (`head`, `a/b`), upstream's `GetHead` and `GetTail`.
143fn split_head(path: &str) -> (&str, &str) {
144    path.split_once('/').unwrap_or((path, ""))
145}
146
147/// Every flattened node whose path starts with one head.
148struct Head<'a> {
149    /// The node at the head path itself, if any.
150    node: Option<&'a FlatNode>,
151    /// Nodes at `head/...`, which edit children of the composed head.
152    edits: Vec<(&'a str, &'a FlatNode)>,
153    /// Heads this head's references name, by index; unknown ones left out.
154    deps: Vec<usize>,
155}
156
157impl<'a> Head<'a> {
158    fn nodes(&self) -> impl Iterator<Item = &'a FlatNode> + '_ {
159        self.node.into_iter().chain(self.edits.iter().map(|e| e.1))
160    }
161}
162
163fn references(node: &FlatNode) -> impl Iterator<Item = &str> {
164    node.inherits
165        .values()
166        .chain(node.children.values().flatten())
167        .map(String::as_str)
168}
169
170/// Composes flattened nodes into a tree, as upstream's `LoadIfcxFile` does
171/// after flattening.
172///
173/// For each node, in this order:
174///
175/// 1. each `inherits` entry, in order, copies the children and attributes of
176///    the node it references;
177/// 2. each `children` entry adds or replaces a child with the node it
178///    references, and a `None` entry deletes the child, inherited or not;
179/// 3. local attributes override inherited ones.
180///
181/// A reference is a node path optionally followed by child names, such as
182/// `type/Body`; the child names are looked up in the composed node. Then
183/// nodes with paths such as `wall/Body` are applied to the matching child,
184/// parents before children; one whose child does not exist is ignored.
185///
186/// Every head path is composed once and shared. A node costs the size of its
187/// own maps plus the top-level maps of the nodes it inherits, not the size of
188/// any sub-tree, and an edit such as `wall/Body` copies only the nodes along
189/// its path. Nothing recurses per tree level, including dropping the result.
190///
191/// # Errors
192///
193/// [`ComposeError::Cycle`] if references form a cycle, checked before
194/// anything is composed, and [`ComposeError::UnknownReference`] for a
195/// reference that does not resolve.
196///
197/// # Differences from upstream
198///
199/// - Cycles and roots look at the head of each reference, the part before
200///   the first `/`, as upstream's own `TODO` in `FindRootsOrCycles` asks.
201///   Upstream compares whole reference strings, so it misses cycles through
202///   `head/child` references and recurses until the stack overflows, and it
203///   lists a node referenced only as `head/child` as a root as well.
204/// - A reference to a path with no node is an error. Upstream composes it as
205///   an empty node.
206///
207/// ```
208/// use openbim_ifcx::{compose, flatten, IfcxNode};
209///
210/// let nodes: Vec<IfcxNode> = serde_json::from_str(r#"[
211///     {"path": "type", "children": {"Body": "mesh"}, "attributes": {"x::kind": "T"}},
212///     {"path": "mesh", "attributes": {"x::points": [0, 1, 2]}},
213///     {"path": "wall", "inherits": {"Type": "type"}, "attributes": {"x::kind": "W"}}
214/// ]"#)?;
215/// let composed = compose(&flatten(&nodes))?;
216/// assert_eq!(composed.roots(), ["wall"]);
217/// let wall = composed.get("wall").unwrap();
218/// assert_eq!(*wall.attributes["x::kind"], "W");
219/// // The body is the composed `mesh` node itself, not a copy.
220/// assert!(std::sync::Arc::ptr_eq(&wall.children["Body"], composed.get("mesh").unwrap()));
221/// # Ok::<(), Box<dyn std::error::Error>>(())
222/// ```
223pub fn compose(flat: &IndexMap<String, FlatNode>) -> Result<Composition, ComposeError> {
224    let mut heads: IndexMap<&str, Head<'_>> = IndexMap::new();
225    for (path, node) in flat {
226        let (head, _) = split_head(path);
227        let entry = heads.entry(head).or_insert_with(|| Head {
228            node: None,
229            edits: Vec::new(),
230            deps: Vec::new(),
231        });
232        if head.len() == path.len() {
233            entry.node = Some(node);
234        } else {
235            entry.edits.push((path.as_str(), node));
236        }
237    }
238
239    let mut referenced = vec![false; heads.len()];
240    for index in 0..heads.len() {
241        let mut deps: Vec<usize> = heads[index]
242            .nodes()
243            .flat_map(references)
244            .filter_map(|reference| heads.get_index_of(split_head(reference).0))
245            .collect();
246        deps.sort_unstable();
247        deps.dedup();
248        for &dep in &deps {
249            referenced[dep] = true;
250        }
251        heads[index].deps = deps;
252    }
253
254    let order = topological_order(&heads)?;
255
256    let mut composed: Vec<Option<Arc<ComposedNode>>> = vec![None; heads.len()];
257    for index in order {
258        let (path, head) = heads.get_index(index).expect("index from heads");
259        let node = compose_head(path, head, &heads, &composed)?;
260        composed[index] = Some(Arc::new(node));
261    }
262
263    let roots = heads
264        .iter()
265        .enumerate()
266        .filter(|(index, (_, head))| head.node.is_some() && !referenced[*index])
267        .map(|(_, (path, _))| (*path).to_owned())
268        .collect();
269    let heads = heads
270        .keys()
271        .zip(composed)
272        .map(|(path, node)| ((*path).to_owned(), node.expect("every head composed")))
273        .collect();
274    Ok(Composition { heads, roots })
275}
276
277/// Head indices with every head after the heads it references, or the
278/// first cycle found. Iterative depth-first search.
279fn topological_order(heads: &IndexMap<&str, Head<'_>>) -> Result<Vec<usize>, ComposeError> {
280    const NEW: u8 = 0;
281    const ACTIVE: u8 = 1;
282    const DONE: u8 = 2;
283    let mut state = vec![NEW; heads.len()];
284    let mut order = Vec::with_capacity(heads.len());
285    // (head, index of the next dependency to visit)
286    let mut stack: Vec<(usize, usize)> = Vec::new();
287    for start in 0..heads.len() {
288        if state[start] != NEW {
289            continue;
290        }
291        state[start] = ACTIVE;
292        stack.push((start, 0));
293        while let Some((index, next)) = stack.last_mut() {
294            let deps = &heads[*index].deps;
295            if let Some(&dep) = deps.get(*next) {
296                *next += 1;
297                match state[dep] {
298                    NEW => {
299                        state[dep] = ACTIVE;
300                        stack.push((dep, 0));
301                    }
302                    ACTIVE => {
303                        let from = stack.iter().position(|(i, _)| *i == dep).expect("active");
304                        let cycle = stack[from..]
305                            .iter()
306                            .map(|(i, _)| (*heads.get_index(*i).expect("index").0).to_owned())
307                            .collect();
308                        return Err(ComposeError::Cycle { cycle });
309                    }
310                    _ => {}
311                }
312            } else {
313                state[*index] = DONE;
314                order.push(*index);
315                stack.pop();
316            }
317        }
318    }
319    Ok(order)
320}
321
322fn compose_head(
323    path: &str,
324    head: &Head<'_>,
325    heads: &IndexMap<&str, Head<'_>>,
326    composed: &[Option<Arc<ComposedNode>>],
327) -> Result<ComposedNode, ComposeError> {
328    let mut node = ComposedNode {
329        path: path.to_owned(),
330        attributes: IndexMap::new(),
331        children: IndexMap::new(),
332    };
333    if let Some(flat) = head.node {
334        add_data(&mut node, path, flat, heads, composed)?;
335    }
336
337    // Upstream walks the composed tree and applies the node at each
338    // `head/a/b` it passes. Applying edits by depth, parents first, gives the
339    // same result: an edit only changes its own sub-tree.
340    let mut edits: Vec<&(&str, &FlatNode)> = head.edits.iter().collect();
341    edits.sort_by_key(|(edit_path, _)| edit_path.matches('/').count());
342    for (edit_path, flat) in edits {
343        let names = split_head(edit_path).1;
344        let mut target = &node;
345        let mut found = true;
346        for name in names.split('/') {
347            match target.children.get(name) {
348                Some(child) => target = child,
349                None => {
350                    found = false;
351                    break;
352                }
353            }
354        }
355        if !found {
356            continue;
357        }
358        let mut target = &mut node;
359        for name in names.split('/') {
360            let child = target.children.get_mut(name).expect("checked above");
361            target = Arc::make_mut(child);
362        }
363        add_data(target, edit_path, flat, heads, composed)?;
364    }
365    Ok(node)
366}
367
368/// Upstream's `AddDataFromPreComposition`.
369fn add_data(
370    node: &mut ComposedNode,
371    path: &str,
372    flat: &FlatNode,
373    heads: &IndexMap<&str, Head<'_>>,
374    composed: &[Option<Arc<ComposedNode>>],
375) -> Result<(), ComposeError> {
376    let resolve = |reference: &str| -> Result<&Arc<ComposedNode>, ComposeError> {
377        let (head, tail) = split_head(reference);
378        heads
379            .get_index_of(head)
380            .and_then(|index| composed[index].as_ref())
381            .and_then(|head| head.descendant(tail))
382            .ok_or_else(|| ComposeError::UnknownReference {
383                path: path.to_owned(),
384                reference: reference.to_owned(),
385            })
386    };
387
388    for reference in flat.inherits.values() {
389        let inherited = resolve(reference)?;
390        for (name, child) in &inherited.children {
391            node.children.insert(name.clone(), child.clone());
392        }
393        for (name, value) in &inherited.attributes {
394            node.attributes.insert(name.clone(), value.clone());
395        }
396    }
397    for (name, child) in &flat.children {
398        match child {
399            Some(reference) => {
400                let child = resolve(reference)?.clone();
401                node.children.insert(name.clone(), child);
402            }
403            // shift_remove so a later re-add goes to the end, like a
404            // JavaScript Map delete followed by a set.
405            None => {
406                node.children.shift_remove(name);
407            }
408        }
409    }
410    for (name, value) in &flat.attributes {
411        node.attributes.insert(name.clone(), value.clone());
412    }
413    Ok(())
414}
openbim_ifcx/compose/tree.rs

openbim_ifcx/compose/
tree.rs
