ifc_lite_server/services/data_model/
spatial_invariant.rs

1// This Source Code Form is subject to the terms of the Mozilla Public
2// License, v. 2.0. If a copy of the MPL was not distributed with this
3// file, You can obtain one at https://mozilla.org/MPL/2.0/.
4
5//! Structural invariant over a finished spatial-node set, split out of
6//! `spatial.rs` to stay under the module-size ratchet (the same reason
7//! `spatial_tree.rs` and `spatial_elevation.rs` exist).
8//!
9//! #3973 fixed the same defect shape twice, pointwise, in two different
10//! code paths: a dangling `children_ids` entry naming an entity with no
11//! corresponding node in `nodes_map` (first a depth-capped node resurrected
12//! as a fake root, then a rescued orphan's `children_ids` populated straight
13//! from `spatial_children_map` with no filtering). Each fix closed one path
14//! into the tree without ruling the shape out structurally, so this checks
15//! the finished tree instead of any one code path.
16
17use super::super::types::SpatialNode;
18use rustc_hash::FxHashMap;
19use std::collections::VecDeque;
20
21/// Check a finished node set for the dangling-reference shape #3973 fixed
22/// twice pointwise: (a) every id in every node's `children_ids` must resolve
23/// to a node in the set, (b) every node's `parent_id` must either resolve to
24/// a node or be the root sentinel (`0` - never a real STEP entity id), and
25/// (c) the two directions must agree - `A.children_ids` containing `B` and
26/// `B.parent_id == A` are two representations of the same fact. Clause (c)
27/// is the one that actually catches the family: a fake root with a real
28/// parent_id disagreement passes (a) and (b) - it names no nonexistent id
29/// and has a resolvable-or-sentinel parent - while still being wrong.
30///
31/// Called from both `build_spatial_hierarchy`'s own `debug_assert!` and the
32/// test suite (`super::spatial::spatial_hierarchy_consistency_violations`),
33/// so this is the single place either has to change.
34///
35/// #4022 widened this from purely local edge consistency to two global
36/// checks (see [`reachability_and_depth_violations`]): every node must be
37/// reachable from a root by walking `children_ids`, and a reachable node's
38/// `level` must equal its actual depth from that walk. A third candidate
39/// class - requiring exactly one root - is deliberately NOT enforced:
40/// `DISCONNECTED_SITE_AGGREGATES_BUILDING_IFC` in `tests.rs` legitimately
41/// produces two independent `parent_id == 0` nodes (the true `IfcProject`
42/// and a rescued orphan promoted to a fake root because it has no reachable
43/// canonical parent), so a hard root-uniqueness rule would fire on valid
44/// output rather than a defect. A model with a second root that is fully
45/// disconnected from the real tree - internally consistent, reachable
46/// on its own, but never reachable from the real root - still passes every
47/// clause here; ruling that out needs a way to tell a legitimate rescued
48/// island apart from a genuine second tree, which none of the clauses below
49/// (or #3973's fixes) has any information to do.
50pub(crate) fn spatial_hierarchy_consistency_violations(nodes: &[&SpatialNode]) -> Vec<String> {
51    let by_id: FxHashMap<u32, &&SpatialNode> = nodes.iter().map(|n| (n.entity_id, n)).collect();
52    let mut violations = Vec::new();
53
54    for node in nodes {
55        for &child_id in &node.children_ids {
56            match by_id.get(&child_id) {
57                None => violations.push(format!(
58                    "node #{} lists child #{child_id} in children_ids, but no node #{child_id} exists",
59                    node.entity_id
60                )),
61                Some(child) if child.parent_id != node.entity_id => violations.push(format!(
62                    "node #{} lists child #{child_id} in children_ids, but #{child_id}.parent_id is #{} (expected #{})",
63                    node.entity_id, child.parent_id, node.entity_id
64                )),
65                Some(_) => {}
66            }
67        }
68
69        if node.parent_id != 0 {
70            match by_id.get(&node.parent_id) {
71                None => violations.push(format!(
72                    "node #{} has parent_id #{}, but no node #{} exists",
73                    node.entity_id, node.parent_id, node.parent_id
74                )),
75                Some(parent) if !parent.children_ids.contains(&node.entity_id) => {
76                    violations.push(format!(
77                        "node #{} has parent_id #{}, but #{}.children_ids does not list #{}",
78                        node.entity_id, node.parent_id, node.parent_id, node.entity_id
79                    ))
80                }
81                Some(_) => {}
82            }
83        }
84    }
85
86    violations.extend(reachability_and_depth_violations(nodes, &by_id));
87
88    violations
89}
90
91/// Global check, added for #4022: BFS every `children_ids` edge starting
92/// from every node whose `parent_id` is the sentinel `0` (there can
93/// legitimately be more than one, see the module doc above), tracking depth
94/// as it goes. Any node the walk never reaches is flagged - this is what
95/// catches a cycle isolated from every root (e.g. two nodes that are each
96/// other's parent and only listed child: each satisfies the local clauses
97/// above, but neither has a `parent_id == 0` node in its ancestry, so
98/// neither is ever enqueued). Any node the walk does reach has its `level`
99/// compared against the depth the walk assigned it, catching a `level` that
100/// disagrees with the node's actual position in the tree.
101///
102/// This does not - and structurally cannot - detect a second root that is
103/// itself internally well-formed and reachable purely from itself: it is
104/// indistinguishable, by this walk, from a legitimate rescued-orphan island
105/// (see the module doc above), so it is out of scope for this clause.
106fn reachability_and_depth_violations(
107    nodes: &[&SpatialNode],
108    by_id: &FxHashMap<u32, &&SpatialNode>,
109) -> Vec<String> {
110    let mut visited: FxHashMap<u32, u16> = FxHashMap::default();
111    let mut queue: VecDeque<(u32, u16)> = nodes
112        .iter()
113        .filter(|n| n.parent_id == 0)
114        .map(|n| (n.entity_id, 0))
115        .collect();
116
117    while let Some((id, depth)) = queue.pop_front() {
118        if visited.contains_key(&id) {
119            continue;
120        }
121        visited.insert(id, depth);
122        if let Some(node) = by_id.get(&id) {
123            for &child_id in &node.children_ids {
124                if !visited.contains_key(&child_id) {
125                    queue.push_back((child_id, depth + 1));
126                }
127            }
128        }
129    }
130
131    let mut violations = Vec::new();
132    for node in nodes {
133        match visited.get(&node.entity_id) {
134            None => violations.push(format!(
135                "node #{} is unreachable from any root (a node with parent_id 0) by walking \
136                 children_ids - it may be part of a cycle isolated from the rest of the tree",
137                node.entity_id
138            )),
139            Some(&depth) if depth != node.level => violations.push(format!(
140                "node #{} has level {}, but walking children_ids from its root puts it at depth {depth}",
141                node.entity_id, node.level
142            )),
143            Some(_) => {}
144        }
145    }
146
147    violations
148}
149
150#[cfg(test)]
151#[path = "spatial_invariant_tests.rs"]
152mod spatial_invariant_tests;
ifc_lite_server/services/data_model/spatial_invariant.rs

ifc_lite_server/services/data_model/
spatial_invariant.rs
