ifc_model/traverse/cycle.rs
1//! Cycle detection with the offending path.
2//!
3//! [`super::budget::Walk::revisited`] answers *whether* a graph is cyclic. When
4//! a file is malformed the caller usually needs to know *where*, so this
5//! reports the path that closes the loop.
6
7use ahash::AHashSet;
8
9use crate::value::EntityId;
10
11/// Find one cycle reachable from `start`, if any.
12///
13/// Returns the path from the first repeated entity back to itself, so the
14/// caller can name the entities involved in a diagnostic. Bounded by `max_depth`
15/// so a pathological file cannot spin.
16pub fn find_cycle(
17 start: EntityId,
18 max_depth: usize,
19 mut successors: impl FnMut(EntityId) -> Vec<EntityId>,
20) -> Option<Vec<EntityId>> {
21 // Iterative DFS carrying the path, so the cycle can be sliced out of it
22 // without a recursive walk that could itself overflow on a deep file.
23 let mut stack: Vec<(EntityId, Vec<EntityId>)> = vec![(start, Vec::new())];
24
25 while let Some((node, mut path)) = stack.pop() {
26 if let Some(position) = path.iter().position(|seen| *seen == node) {
27 let mut cycle = path[position..].to_vec();
28 cycle.push(node);
29 return Some(cycle);
30 }
31 if path.len() >= max_depth {
32 continue;
33 }
34 path.push(node);
35 // Deduplicate successors so a doubled edge is not mistaken for a cycle.
36 let mut unique = AHashSet::new();
37 for successor in successors(node) {
38 if unique.insert(successor) {
39 stack.push((successor, path.clone()));
40 }
41 }
42 }
43 None
44}