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