Skip to main content

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}