Skip to main content

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}