ifc_lite_server/services/data_model/
spatial_canonical_parent.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//! Cycle-safe canonical-parent resolution, split out of `spatial.rs` (same
6//! reason `spatial_elevation.rs`, `spatial_invariant.rs` and `spatial_tree.rs`
7//! already are: stay under the module-size ratchet). Mirrors
8//! `packages/parser/src/spatial-hierarchy-canonical-parent.ts`, which split
9//! the same concern out of `spatial-hierarchy-builder.ts` for the same
10//! reason.
11
12use super::super::types::Relationship;
13use rustc_hash::{FxHashMap, FxHashSet};
14
15/// Upper bound on aggregate-graph node visits spent on back-edge cycle checks
16/// for one upload. The check only runs for children named by MORE THAN ONE
17/// `IFCRELAGGREGATES` (already malformed) and costs one descendant walk per
18/// such child - O(V+E) each - so a crafted upload with thousands of contested
19/// children could otherwise hold a blocking worker for O(C·(V+E)). Past the
20/// budget the resolver falls back to plain first-declared-wins and logs once.
21/// Mirrors `CYCLE_CHECK_VISIT_BUDGET` in
22/// `packages/parser/src/spatial-hierarchy-canonical-parent.ts`.
23pub(super) const CYCLE_CHECK_VISIT_BUDGET: u64 = 2_000_000;
24
25/// Aggregated descendants of `child_id` (transitive, forward
26/// `IFCRELAGGREGATES`), charged against `budget`. `None` when the budget ran
27/// out mid-walk: a partial set must not be used, since a missing descendant
28/// reads as "no cycle" - the wrong side to err on. Used only to disqualify a
29/// tied candidate parent that would close a cycle back through the child
30/// itself (#4246: the STEP-authoring-tool mistake of declaring an aggregation
31/// pair in both directions, or an indirect A -> B -> C -> A chain) - the
32/// common case (one candidate) never calls this. Mirrors
33/// `packages/parser/src/spatial-hierarchy-canonical-parent.ts`'s
34/// `aggregatedDescendants`.
35fn aggregated_descendants(
36    child_id: u32,
37    raw_aggregates_children: &FxHashMap<u32, Vec<u32>>,
38    budget: &mut u64,
39) -> Option<FxHashSet<u32>> {
40    let mut visited: FxHashSet<u32> = FxHashSet::default();
41    visited.insert(child_id);
42    let mut stack = vec![child_id];
43    while let Some(current) = stack.pop() {
44        if let Some(kids) = raw_aggregates_children.get(&current) {
45            for &kid in kids {
46                if *budget == 0 {
47                    return None;
48                }
49                *budget -= 1;
50                if visited.insert(kid) {
51                    stack.push(kid);
52                }
53            }
54        }
55    }
56    Some(visited)
57}
58
59/// Resolve each spatial child's ONE canonical `IFCRELAGGREGATES` parent,
60/// globally, from the raw relationship list. Plain first-declared-wins,
61/// EXCEPT that a candidate closing a cycle back through the child is skipped
62/// first (#4246) - a mutual or longer aggregation back-edge (a
63/// STEP-authoring-tool mistake: a parent/child pair declared in both
64/// directions) cannot win a tie against a candidate that doesn't orphan the
65/// child's own subtree from itself. Falls through to plain first-declared if
66/// every candidate closes a cycle, so a child is never left without a
67/// parent. Mirrors
68/// `packages/parser/src/spatial-hierarchy-canonical-parent.ts`'s
69/// `computeCanonicalParent`.
70///
71/// Only resolves `IFCRELAGGREGATES` edges; the
72/// `IFCRELCONTAINEDINSPATIALSTRUCTURE` promotion (a spatial-structure target
73/// with no Aggregates edge at all, #1075) is layered on top by the caller in
74/// `spatial.rs`, same as before this split.
75pub(in crate::services::data_model) fn resolve_aggregate_canonical_parents(
76    relationships: &[Relationship],
77) -> FxHashMap<u32, u32> {
78    resolve_aggregate_canonical_parents_with_budget(relationships, CYCLE_CHECK_VISIT_BUDGET)
79}
80
81pub(in crate::services::data_model) fn resolve_aggregate_canonical_parents_with_budget(
82    relationships: &[Relationship],
83    cycle_check_visit_budget: u64,
84) -> FxHashMap<u32, u32> {
85    // Raw (unresolved) forward IFCRELAGGREGATES edges, parent -> children, in
86    // file-declaration order. Used only by `aggregated_descendants` above
87    // to detect a spurious back-edge; distinct from the returned map, which
88    // holds the single resolved winner per child.
89    let mut raw_aggregates_children: FxHashMap<u32, Vec<u32>> = FxHashMap::default();
90    // Candidate parents named for each child by an IFCRELAGGREGATES edge, in
91    // file-declaration order (mirrors `edges` in the TS `computeCanonicalParent`).
92    let mut aggregate_candidates: FxHashMap<u32, Vec<u32>> = FxHashMap::default();
93    for rel in relationships {
94        if rel.rel_type.to_uppercase() == "IFCRELAGGREGATES" {
95            raw_aggregates_children
96                .entry(rel.relating_id)
97                .or_default()
98                .push(rel.related_id);
99            aggregate_candidates
100                .entry(rel.related_id)
101                .or_default()
102                .push(rel.relating_id);
103        }
104    }
105
106    let mut canonical_parent: FxHashMap<u32, u32> = FxHashMap::default();
107    let mut budget = cycle_check_visit_budget;
108    let mut budget_exhausted = false;
109    for (&child_id, candidates) in &aggregate_candidates {
110        let mut winner = candidates[0];
111        if candidates.len() > 1 && !budget_exhausted {
112            // One descendant walk per contested child (not per candidate),
113            // under the upload-wide visit budget.
114            match aggregated_descendants(child_id, &raw_aggregates_children, &mut budget) {
115                None => {
116                    budget_exhausted = true;
117                    tracing::warn!(
118                        budget = cycle_check_visit_budget,
119                        "Aggregation back-edge cycle checks stopped: visit budget spent; remaining multi-parent children resolve first-declared"
120                    );
121                }
122                Some(descendants) => {
123                    let rejected: Vec<u32> = candidates
124                        .iter()
125                        .copied()
126                        .filter(|candidate| descendants.contains(candidate))
127                        .collect();
128                    if let Some(&non_cyclic) =
129                        candidates.iter().find(|candidate| !descendants.contains(candidate))
130                    {
131                        if non_cyclic != winner {
132                            tracing::warn!(
133                                child_id,
134                                kept_parent = non_cyclic,
135                                rejected_cyclic_parents = ?rejected,
136                                "Ignored aggregation back-edge cycle(s) in spatial hierarchy"
137                            );
138                        }
139                        winner = non_cyclic;
140                    }
141                    // else: every candidate closes a cycle back through the
142                    // child - fall through to plain first-declared so it is
143                    // never left without a parent.
144                }
145            }
146        }
147        canonical_parent.insert(child_id, winner);
148    }
149    canonical_parent
150}
ifc_lite_server/services/data_model/spatial_canonical_parent.rs

ifc_lite_server/services/data_model/
spatial_canonical_parent.rs
