pray_core/
dependency_graph.rs

1use std::collections::{BTreeMap, BTreeSet};
2
3/// Returns one cycle path `A -> B -> ... -> A` when the directed dependency graph
4/// among known package names contains a cycle. Edges to unknown packages are ignored.
5pub fn find_dependency_cycle(edges: &BTreeMap<String, Vec<String>>) -> Option<Vec<String>> {
6    let mut visiting = BTreeSet::new();
7    let mut visited = BTreeSet::new();
8    let mut stack = Vec::new();
9
10    for name in edges.keys() {
11        if visited.contains(name) {
12            continue;
13        }
14        if let Some(cycle) =
15            depth_first_search(name, edges, &mut visiting, &mut visited, &mut stack)
16        {
17            return Some(cycle);
18        }
19    }
20    None
21}
22
23fn depth_first_search(
24    name: &str,
25    edges: &BTreeMap<String, Vec<String>>,
26    visiting: &mut BTreeSet<String>,
27    visited: &mut BTreeSet<String>,
28    stack: &mut Vec<String>,
29) -> Option<Vec<String>> {
30    if visited.contains(name) {
31        return None;
32    }
33    if !visiting.insert(name.to_string()) {
34        let cycle_start = stack.iter().position(|entry| entry == name)?;
35        let mut cycle = stack[cycle_start..].to_vec();
36        cycle.push(name.to_string());
37        return Some(cycle);
38    }
39
40    stack.push(name.to_string());
41    if let Some(dependencies) = edges.get(name) {
42        for dependency in dependencies {
43            if !edges.contains_key(dependency) {
44                continue;
45            }
46            if let Some(cycle) = depth_first_search(dependency, edges, visiting, visited, stack) {
47                return Some(cycle);
48            }
49        }
50    }
51    stack.pop();
52    visiting.remove(name);
53    visited.insert(name.to_string());
54    None
55}
56
57#[cfg(test)]
58mod tests {
59    use super::*;
60
61    fn graph(pairs: &[(&str, &[&str])]) -> BTreeMap<String, Vec<String>> {
62        pairs
63            .iter()
64            .map(|(name, deps)| {
65                (
66                    (*name).to_string(),
67                    deps.iter().map(|dep| (*dep).to_string()).collect(),
68                )
69            })
70            .collect()
71    }
72
73    #[test]
74    fn detects_two_node_cycle() {
75        let edges = graph(&[("a", &["b"]), ("b", &["a"])]);
76        let cycle = find_dependency_cycle(&edges).expect("cycle");
77        assert!(cycle.len() >= 3);
78        assert_eq!(cycle.first(), cycle.last());
79    }
80
81    #[test]
82    fn accepts_dag() {
83        let edges = graph(&[("a", &["b"]), ("b", &["c"]), ("c", &[])]);
84        assert!(find_dependency_cycle(&edges).is_none());
85    }
86
87    #[test]
88    fn ignores_edges_to_unknown_packages() {
89        let edges = graph(&[("a", &["missing"]), ("b", &[])]);
90        assert!(find_dependency_cycle(&edges).is_none());
91    }
92
93    #[test]
94    fn detects_self_cycle() {
95        let edges = graph(&[("a", &["a"])]);
96        let cycle = find_dependency_cycle(&edges).expect("self cycle");
97        assert_eq!(cycle, vec!["a".to_string(), "a".to_string()]);
98    }
99}
pray_core/dependency_graph.rs

pray_core/
dependency_graph.rs
