Skip to main content

source_mesh_core/graph/
cycles.rs

1use std::collections::BTreeMap;
2use std::collections::BTreeSet;
3use std::collections::hash_map::RandomState;
4use std::iter;
5use std::num::NonZeroUsize;
6
7use anyhow::Context as _;
8use anyhow::Result;
9use anyhow::ensure;
10use getset::CopyGetters;
11use getset::Getters;
12use petgraph::algo::all_simple_paths;
13use petgraph::algo::kosaraju_scc;
14use petgraph::graph::DiGraph;
15use petgraph::graph::NodeIndex;
16use petgraph::visit::EdgeFiltered;
17use petgraph::visit::EdgeRef as _;
18use petgraph::visit::IntoNeighbors as _;
19
20use crate::model::Edge;
21use crate::model::FileGraph;
22use crate::model::FileNode;
23use crate::model::FolderGraph;
24use crate::model::FolderNode;
25
26#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, CopyGetters)]
27#[getset(get_copy = "pub")]
28pub struct CycleGroupId {
29    number: NonZeroUsize,
30}
31
32#[derive(Getters, CopyGetters)]
33pub struct Cycle<Node> {
34    #[getset(get = "pub")]
35    nodes: Vec<Node>,
36    #[getset(get_copy = "pub")]
37    group: CycleGroupId,
38}
39
40struct CyclicComponent {
41    group: CycleGroupId,
42    nodes: BTreeSet<NodeIndex>,
43}
44
45pub struct CycleAnalysis<Node> {
46    topology: DiGraph<Node, ()>,
47    components: Vec<CyclicComponent>,
48    edge_groups: BTreeMap<Edge<Node>, Option<CycleGroupId>>,
49}
50
51impl<Node: Clone + Ord> CycleAnalysis<Node> {
52    fn new<'a>(nodes: &BTreeSet<Node>, edges: impl Iterator<Item = &'a Edge<Node>>) -> Result<Self>
53    where
54        Node: 'a,
55    {
56        let edges: Vec<_> = edges.collect();
57        ensure!(
58            edges.iter().all(|edge| nodes.contains(edge.source()) && nodes.contains(edge.target())),
59            "Cycle analysis has an unknown dependency endpoint"
60        );
61        let mut topology = DiGraph::new();
62        let node_indices: BTreeMap<_, _> = nodes.iter()
63            .map(|node| (node, topology.add_node(node.clone())))
64            .collect();
65        for edge in &edges {
66            topology.update_edge(
67                *node_indices.get(edge.source()).context("Missing cycle source node")?,
68                *node_indices.get(edge.target()).context("Missing cycle target node")?,
69                (),
70            );
71        }
72        let mut components = kosaraju_scc(&topology);
73        components.retain(|component| {
74            component.len() > 1
75                || component.first().is_some_and(|node| topology.contains_edge(*node, *node))
76        });
77        for component in &mut components {
78            component.sort_unstable();
79        }
80        components.sort_unstable();
81        let mut cyclic_components = Vec::new();
82        let mut node_groups = BTreeMap::new();
83        for (index, component) in components.into_iter().enumerate() {
84            let group = CycleGroupId {
85                number: index.checked_add(1).and_then(NonZeroUsize::new)
86                    .context("Cycle group count overflow")?,
87            };
88            for node in &component {
89                node_groups.insert(*node, group);
90            }
91            cyclic_components.push(CyclicComponent {
92                group,
93                nodes: component.into_iter().collect(),
94            });
95        }
96        let edge_groups = edges.into_iter().map(|edge| {
97            let source = node_indices.get(edge.source()).and_then(|node| node_groups.get(node));
98            let target = node_indices.get(edge.target()).and_then(|node| node_groups.get(node));
99            let group = match (source, target) {
100                (Some(source_group), Some(target_group)) if source_group == target_group => {
101                    Some(*source_group)
102                }
103                _ => None,
104            };
105            (Edge::new(edge.source().clone(), edge.target().clone(), edge.kind()), group)
106        }).collect();
107        Ok(Self {
108            topology,
109            components: cyclic_components,
110            edge_groups,
111        })
112    }
113
114    #[must_use]
115    pub fn edge_group(&self, edge: &Edge<Node>) -> Option<CycleGroupId> {
116        self.edge_groups.get(edge).copied().flatten()
117    }
118
119    #[must_use]
120    pub const fn group_count(&self) -> usize {
121        self.components.len()
122    }
123
124    pub fn cycles(&self, limit: NonZeroUsize) -> Result<Vec<Cycle<Node>>> {
125        let mut cycles = Vec::new();
126        for component in &self.components {
127            for &minimum_cycle_node in &component.nodes {
128                let cycle_subgraph = EdgeFiltered::from_fn(&self.topology, |edge| {
129                    [edge.source(), edge.target()].into_iter()
130                        .all(|node| node >= minimum_cycle_node && component.nodes.contains(&node))
131                });
132                for first_successor in cycle_subgraph.neighbors(minimum_cycle_node) {
133                    let paths: Box<dyn Iterator<Item = Vec<NodeIndex>> + '_> = if first_successor == minimum_cycle_node {
134                        Box::new(iter::once(vec![minimum_cycle_node]))
135                    } else {
136                        Box::new(all_simple_paths::<Vec<_>, _, RandomState>(&cycle_subgraph, first_successor, minimum_cycle_node, 0, None))
137                    };
138                    for path in paths {
139                        ensure!(
140                            cycles.len() < limit.get(),
141                            "Cycle count exceeds the configured limit of {limit}; increase the limit to enumerate every cycle"
142                        );
143                        let nodes = iter::once(minimum_cycle_node).chain(path)
144                            .map(|node| self.topology.node_weight(node).cloned().context("Missing cycle path node"))
145                            .collect::<Result<Vec<_>>>()?;
146                        cycles.push(Cycle { nodes, group: component.group });
147                    }
148                }
149            }
150        }
151        cycles.sort_by(|left, right| (left.group, &left.nodes).cmp(&(right.group, &right.nodes)));
152        Ok(cycles)
153    }
154}
155
156pub fn analyze_folders(graph: &FolderGraph) -> Result<CycleAnalysis<FolderNode>> {
157    CycleAnalysis::new(graph.nodes(), graph.edges().keys())
158}
159
160pub fn analyze_files(graph: &FileGraph) -> Result<CycleAnalysis<FileNode>> {
161    CycleAnalysis::new(graph.files(), graph.edges().iter())
162}
163
164pub(crate) fn validate_folder_analysis(analysis: &CycleAnalysis<FolderNode>, graph: &FolderGraph) -> Result<()> {
165    ensure!(
166        analysis.topology.node_weights().eq(graph.nodes())
167            && analysis.edge_groups.keys().eq(graph.edges().keys()),
168        "Cycle analysis does not match the folder graph"
169    );
170    Ok(())
171}
172
173#[cfg(test)]
174#[expect(
175    clippy::panic_in_result_fn,
176    reason = "Tests use assertions for expectations while returning Result for fallible setup."
177)]
178mod tests {
179    use std::collections::BTreeMap;
180    use std::collections::BTreeSet;
181    use std::iter;
182    use std::num::NonZeroUsize;
183    use std::path::Path;
184    use std::path::PathBuf;
185
186    use anyhow::Context as _;
187    use anyhow::Result;
188    use pretty_assertions::assert_eq;
189    use rstest::rstest;
190
191    use super::CycleAnalysis;
192    use super::analyze_files;
193    use super::analyze_folders;
194    use super::validate_folder_analysis;
195    use crate::model::DependencyCount;
196    use crate::model::DependencyKind;
197    use crate::model::DependencyKind::Production;
198    use crate::model::DependencyKind::Test;
199    use crate::model::FileEdge;
200    use crate::model::FileGraph;
201    use crate::model::FileNode;
202    use crate::model::FolderEdge;
203    use crate::model::FolderGraph;
204    use crate::model::FolderNode;
205
206    fn folder_fixture(dependencies: &[(&str, &str, DependencyKind)]) -> Result<FolderGraph> {
207        let edges = folder_dependencies(dependencies);
208        let nodes = edges.keys()
209            .flat_map(|edge| [edge.source().clone(), edge.target().clone()])
210            .collect();
211        FolderGraph::new(nodes, edges)
212    }
213
214    #[must_use]
215    fn folder_dependencies(dependencies: &[(&str, &str, DependencyKind)]) -> BTreeMap<FolderEdge, DependencyCount> {
216        dependencies.iter().map(|&(source, target, kind)| {
217            (FolderEdge::new(FolderNode::new(source.into()), FolderNode::new(target.into()), kind), DependencyCount::new(1))
218        }).collect()
219    }
220
221    #[must_use]
222    fn folder_path(labels: &[&str]) -> Vec<FolderNode> {
223        labels.iter().map(|label| FolderNode::new((*label).into())).collect()
224    }
225
226    #[rstest]
227    #[case(&[], vec![])]
228    #[case(&[("alpha", "beta", Production), ("beta", "gamma", Production)], vec![])]
229    #[case(&[("alpha", "beta", Production), ("gamma", "beta", Production)], vec![])]
230    #[case(
231        &[("alpha", "beta", Production), ("beta", "alpha", Production)],
232        vec![vec!["alpha", "beta", "alpha"]]
233    )]
234    #[case(
235        &[("alpha", "beta", Production), ("beta", "gamma", Production), ("gamma", "alpha", Production)],
236        vec![vec!["alpha", "beta", "gamma", "alpha"]]
237    )]
238    #[case(
239        &[("alpha", "beta", Production), ("beta", "alpha", Production), ("beta", "gamma", Production), ("gamma", "beta", Production)],
240        vec![vec!["alpha", "beta", "alpha"], vec!["beta", "gamma", "beta"]]
241    )]
242    #[case(
243        &[("alpha", "alpha", Production)],
244        vec![vec!["alpha", "alpha"]]
245    )]
246    #[case(
247        &[("alpha", "alpha", Production), ("alpha", "beta", Production), ("beta", "alpha", Production)],
248        vec![vec!["alpha", "alpha"], vec!["alpha", "beta", "alpha"]]
249    )]
250    #[case(
251        &[("alpha", "beta", Production), ("alpha", "beta", Test), ("beta", "alpha", Production), ("beta", "alpha", Test)],
252        vec![vec!["alpha", "beta", "alpha"]]
253    )]
254    #[case(
255        &[("alpha", "alpha", Production), ("alpha", "alpha", Test)],
256        vec![vec!["alpha", "alpha"]]
257    )]
258    #[case(
259        &[("alpha", "beta", Production), ("alpha", "gamma", Production), ("beta", "omega", Production), ("gamma", "omega", Production), ("omega", "alpha", Production)],
260        vec![vec!["alpha", "beta", "omega", "alpha"], vec!["alpha", "gamma", "omega", "alpha"]]
261    )]
262    #[case(
263        &[("alpha", "beta", Production), ("beta", "gamma", Production), ("gamma", "alpha", Production), ("alpha", "gamma", Production), ("gamma", "beta", Production), ("beta", "alpha", Production)],
264        vec![vec!["alpha", "beta", "alpha"], vec!["alpha", "beta", "gamma", "alpha"], vec!["alpha", "gamma", "alpha"], vec!["alpha", "gamma", "beta", "alpha"], vec!["beta", "gamma", "beta"]]
265    )]
266    fn test_directed_cycle_routes(
267        #[case] dependencies: &[(&str, &str, DependencyKind)],
268        #[case] expected_paths: Vec<Vec<&str>>,
269    ) -> Result<()> {
270        let fixture = folder_fixture(dependencies)?;
271        let system_under_test = analyze_folders(&fixture)?;
272        let expected: Vec<_> = expected_paths.into_iter().map(|labels| folder_path(&labels)).collect();
273
274        let cycles = system_under_test.cycles(NonZeroUsize::new(10).context("Invalid test cycle limit")?)?;
275        let paths: Vec<_> = cycles.into_iter().map(|cycle| cycle.nodes).collect();
276
277        assert_eq!(expected, paths, "Directed cycle routes or their canonical order differ");
278        Ok(())
279    }
280
281    #[rstest]
282    #[case("alpha", "beta", Production, Some(1))]
283    #[case("beta", "alpha", Test, Some(1))]
284    #[case("gamma", "omega", Production, Some(2))]
285    #[case("omega", "gamma", Production, Some(2))]
286    #[case("beta", "gamma", Production, None)]
287    #[case("alpha", "omega", Production, None)]
288    #[case("alpha", "beta", Test, None)]
289    #[case("unknown", "alpha", Production, None)]
290    fn test_component_edge_membership(
291        #[case] source: &str,
292        #[case] target: &str,
293        #[case] kind: DependencyKind,
294        #[case] expected_group: Option<usize>,
295    ) -> Result<()> {
296        let fixture = folder_fixture(&[
297            ("omega", "gamma", Production),
298            ("gamma", "omega", Production),
299            ("beta", "gamma", Production),
300            ("beta", "alpha", Test),
301            ("alpha", "beta", Production),
302        ])?;
303        let system_under_test = analyze_folders(&fixture)?;
304        let edge = FolderEdge::new(FolderNode::new(source.into()), FolderNode::new(target.into()), kind);
305
306        let group = system_under_test.edge_group(&edge);
307
308        assert_eq!(2, system_under_test.group_count(), "Independent cyclic components were merged");
309        assert_eq!(expected_group, group.map(|identifier| identifier.number().get()), "Incorrect cycle edge group");
310        Ok(())
311    }
312
313    #[test]
314    fn test_cycle_group_assignment() -> Result<()> {
315        let fixture = folder_fixture(&[
316            ("gamma", "omega", Production),
317            ("omega", "gamma", Production),
318            ("alpha", "beta", Production),
319            ("beta", "alpha", Production),
320            ("beta", "gamma", Production),
321        ])?;
322        let system_under_test = analyze_folders(&fixture)?;
323        let expected = [folder_path(&["alpha", "beta", "alpha"]), folder_path(&["gamma", "omega", "gamma"])];
324
325        let cycles = system_under_test.cycles(NonZeroUsize::new(2).context("Invalid test cycle limit")?)?;
326        let groups: Vec<_> = cycles.iter().map(|cycle| cycle.group().number().get()).collect();
327        let paths: Vec<_> = cycles.into_iter().map(|cycle| cycle.nodes).collect();
328
329        assert_eq!(groups, [1, 2], "Cycle group numbers differ");
330        assert_eq!(paths, expected, "Independent cycle routes or their order differ");
331        Ok(())
332    }
333
334    #[rstest]
335    #[case(1, true)]
336    #[case(2, false)]
337    #[case(3, false)]
338    fn test_cycle_enumeration_limit(#[case] limit: usize, #[case] exceeds_limit: bool) -> Result<()> {
339        let fixture = folder_fixture(&[
340            ("alpha", "beta", Production),
341            ("beta", "alpha", Production),
342            ("beta", "gamma", Production),
343            ("gamma", "beta", Production),
344        ])?;
345        let system_under_test = analyze_folders(&fixture)?;
346
347        let result = system_under_test.cycles(NonZeroUsize::new(limit).context("Invalid test cycle limit")?);
348
349        assert_eq!(1, system_under_test.group_count(), "Overlapping cycles have separate groups");
350        if exceeds_limit {
351            assert!(result.is_err(), "Excess cycles were silently truncated");
352        } else {
353            assert_eq!(2, result?.len(), "Enumeration did not retain every cycle within the limit");
354        }
355        Ok(())
356    }
357
358    #[test]
359    fn test_isolated_nodes() -> Result<()> {
360        let fixture = FolderGraph::new(BTreeSet::from([FolderNode::new("isolated".into())]), BTreeMap::new())?;
361        let system_under_test = analyze_folders(&fixture)?;
362
363        let cycles = system_under_test.cycles(NonZeroUsize::MIN)?;
364
365        assert_eq!(0, system_under_test.group_count(), "Isolated node became a cyclic component");
366        assert!(cycles.is_empty(), "Isolated node produced a phantom cycle");
367        Ok(())
368    }
369
370    #[rstest]
371    #[case(Path::new("."), false, 1)]
372    #[case(Path::new("."), true, 0)]
373    #[case(Path::new("alpha"), false, 0)]
374    #[case(Path::new("beta"), false, 0)]
375    fn test_file_cycle_routes(
376        #[case] root: &Path,
377        #[case] exclude_tests: bool,
378        #[case] expected_cycles: usize,
379    ) -> Result<()> {
380        let first_file = FileNode::new(PathBuf::from_iter(["alpha", "source.rs"]))?;
381        let second_file = FileNode::new(PathBuf::from_iter(["beta", "source.rs"]))?;
382        let fixture = FileGraph::new(
383            BTreeSet::from([first_file.clone(), second_file.clone()]),
384            BTreeSet::from([
385                FileEdge::new(first_file.clone(), second_file.clone(), Production),
386                FileEdge::new(second_file.clone(), first_file.clone(), Test),
387            ]),
388        )?;
389        let fixture = if exclude_tests { fixture.without_test_dependencies() } else { fixture }.within_root(root)?;
390        let system_under_test = analyze_files(&fixture)?;
391        let expected = vec![first_file.clone(), second_file, first_file];
392
393        let cycles = system_under_test.cycles(NonZeroUsize::MIN)?;
394
395        assert_eq!(expected_cycles, system_under_test.group_count(), "File cycle components ignored root or test filtering");
396        assert_eq!(expected_cycles, cycles.len(), "File cycle count differs");
397        if expected_cycles != 0 {
398            assert!(cycles.first().is_some_and(|cycle| cycle.nodes() == &expected), "File cycle route differs");
399            assert!(fixture.edges().iter().all(|edge| system_under_test.edge_group(edge).is_some()), "File cycle edge was not grouped");
400        }
401        Ok(())
402    }
403
404    #[test]
405    fn test_dependency_endpoint_membership() -> Result<()> {
406        let nodes = BTreeSet::from([FolderNode::new("alpha".into())]);
407        let edge = FolderEdge::new(FolderNode::new("alpha".into()), FolderNode::new("unknown".into()), Production);
408
409        let system_under_test = CycleAnalysis::new(&nodes, iter::once(&edge));
410
411        assert!(system_under_test.is_err(), "Unknown dependency endpoint was accepted");
412        Ok(())
413    }
414
415    #[rstest]
416    #[case(&[("alpha", "beta", Production), ("beta", "gamma", Production)])]
417    #[case(&[("alpha", "beta", Production), ("beta", "alpha", Production), ("beta", "gamma", Production), ("gamma", "alpha", Production)])]
418    #[case(&[("alpha", "beta", Test), ("beta", "alpha", Production), ("beta", "gamma", Production)])]
419    #[case(&[("alpha", "beta", Production), ("beta", "alpha", Production)])]
420    fn test_folder_analysis_dependencies(#[case] dependencies: &[(&str, &str, DependencyKind)]) -> Result<()> {
421        let fixture = folder_fixture(&[
422            ("alpha", "beta", Production),
423            ("beta", "alpha", Production),
424            ("beta", "gamma", Production),
425        ])?;
426        let system_under_test = analyze_folders(&fixture)?;
427        let changed_graph = FolderGraph::new(fixture.nodes().clone(), folder_dependencies(dependencies))?;
428
429        let result = validate_folder_analysis(&system_under_test, &changed_graph);
430
431        assert!(result.is_err(), "Changed dependency topology or kind accepted an outdated cycle analysis");
432        Ok(())
433    }
434
435    #[rstest]
436    #[case(&["alpha", "beta"], false)]
437    #[case(&["alpha", "beta", "isolated", "other"], false)]
438    #[case(&["isolated", "beta", "alpha"], true)]
439    fn test_folder_analysis_nodes(#[case] labels: &[&str], #[case] matches_analysis: bool) -> Result<()> {
440        let dependencies = [("alpha", "beta", Production), ("beta", "alpha", Production)];
441        let fixture = FolderGraph::new(
442            folder_path(&["alpha", "beta", "isolated"]).into_iter().collect(),
443            folder_dependencies(&dependencies),
444        )?;
445        let system_under_test = analyze_folders(&fixture)?;
446        let changed_graph = FolderGraph::new(folder_path(labels).into_iter().collect(), folder_dependencies(&dependencies))?;
447
448        let result = validate_folder_analysis(&system_under_test, &changed_graph);
449
450        assert_eq!(matches_analysis, result.is_ok(), "Cycle analysis did not validate the full folder node set");
451        Ok(())
452    }
453
454    #[rstest]
455    #[case(1)]
456    #[case(27)]
457    fn test_folder_analysis_dependency_counts(#[case] count: usize) -> Result<()> {
458        let dependencies = [("alpha", "beta", Production), ("beta", "alpha", Production)];
459        let fixture = folder_fixture(&dependencies)?;
460        let system_under_test = analyze_folders(&fixture)?;
461        let mut edges = folder_dependencies(&dependencies);
462        for weight in edges.values_mut() {
463            *weight = DependencyCount::new(count);
464        }
465        let changed_graph = FolderGraph::new(fixture.nodes().clone(), edges)?;
466
467        let result = validate_folder_analysis(&system_under_test, &changed_graph);
468
469        assert!(result.is_ok(), "Dependency counts invalidated an unchanged cycle topology");
470        Ok(())
471    }
472}