ifc_model/traverse/dfs.rs
1//! Bounded depth-first walk.
2//!
3//! Order is deterministic: successors are followed in the order the edge
4//! function yields them, so two runs over the same model agree. That matters
5//! for tests and for diffing two traversals of the same file.
6
7use ahash::AHashSet;
8
9use super::budget::{Budget, Stop, Walk};
10use crate::value::EntityId;
11
12/// Walk depth-first from `start`, following `successors`.
13///
14/// `successors` returns the entities reachable in one step. It is a closure
15/// rather than a fixed rule because the model does not know which references
16/// are meaningful -- containment, aggregation and voiding are all references,
17/// and only a domain crate can tell them apart.
18pub fn depth_first(
19 start: EntityId,
20 budget: Budget,
21 mut successors: impl FnMut(EntityId) -> Vec<EntityId>,
22) -> Walk {
23 let mut visited = Vec::new();
24 let mut seen = AHashSet::new();
25 let mut revisited = Vec::new();
26 // (node, depth); depth is carried so the limit counts edges from the
27 // start rather than stack size.
28 let mut stack = vec![(start, 0usize)];
29 let mut stop = Stop::Exhausted;
30
31 while let Some((node, depth)) = stack.pop() {
32 if !seen.insert(node) {
33 revisited.push(node);
34 continue;
35 }
36 if visited.len() >= budget.max_nodes {
37 stop = Stop::NodeLimit;
38 break;
39 }
40 visited.push(node);
41
42 if depth >= budget.max_depth {
43 // Record that the walk was cut short, but keep draining the stack:
44 // siblings at an admissible depth are still in scope.
45 stop = Stop::DepthLimit;
46 continue;
47 }
48 // Reversed so the first successor is popped first, making the visit
49 // order match the natural reading order of the edge list.
50 let next = successors(node);
51 for successor in next.into_iter().rev() {
52 stack.push((successor, depth + 1));
53 }
54 }
55
56 revisited.sort_unstable();
57 revisited.dedup();
58 Walk {
59 visited,
60 stop,
61 revisited,
62 }
63}