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
42#[derive(Getters, CopyGetters)]
43pub(super) struct BoundedCycles<Node> {
44    #[getset(get = "pub(super)")]
45    cycles: Vec<Cycle<Node>>,
46    #[getset(get_copy = "pub(super)")]
47    truncated: bool,
48}
49
50struct CyclicComponent {
51    group: CycleGroupId,
52    nodes: BTreeSet<NodeIndex>,
53}
54
55pub struct CycleAnalysis<Node> {
56    topology: DiGraph<Node, ()>,
57    components: Vec<CyclicComponent>,
58    edge_groups: BTreeMap<Edge<Node>, Option<CycleGroupId>>,
59}
60
61impl<Node: Clone + Ord> CycleAnalysis<Node> {
62    fn new<'a>(nodes: &BTreeSet<Node>, edges: impl Iterator<Item = &'a Edge<Node>>) -> Result<Self> where Node: 'a {
63        let mut topology = DiGraph::new();
64        let node_indices = nodes.iter().map(|node| topology.try_add_node(node.clone()).map(|index| (node, index)));
65        let node_indices: Result<BTreeMap<_, _>, _> = node_indices.collect();
66        let node_indices = node_indices.context("Cycle analysis exceeds the supported node index capacity")?;
67        let mut edges: Vec<_> = edges.map(|edge| {
68            let endpoints = (node_indices.get(edge.source()), node_indices.get(edge.target()));
69            let (Some(&source_index), Some(&target_index)) = endpoints else {
70                unreachable!("Validated cycle edge endpoints must have topology indices");
71            };
72            (edge, source_index, target_index)
73        }).collect();
74        edges.sort_unstable_by_key(|&(_, source_index, target_index)| (source_index, target_index));
75        /* Dependency kinds share topology edges but retain separate group entries. */
76        let mut previous_endpoints = None;
77        for &(_, source_index, target_index) in &edges {
78            let endpoints = (source_index, target_index);
79            if previous_endpoints == Some(endpoints) {
80                continue;
81            }
82            previous_endpoints = Some(endpoints);
83            topology.try_add_edge(source_index, target_index, ()).map_err(|error| match error {
84                GraphError::EdgeIxLimit => Error::new(error).context("Cycle analysis exceeds the supported edge index capacity"),
85                GraphError::NodeIxLimit => unreachable!("Adding a cycle edge cannot add nodes"),
86                GraphError::NodeMissed(_) | GraphError::NodeOutBounds => {
87                    unreachable!("Cycle edge endpoints were added to the topology")
88                }
89            })?;
90        }
91        let mut components = kosaraju_scc(&topology);
92        components.retain(|component| {
93            component.len() > 1 || component.first().is_some_and(|node| topology.contains_edge(*node, *node))
94        });
95        for component in &mut components {
96            component.sort_unstable();
97        }
98        components.sort_unstable();
99        let mut node_groups = BTreeMap::new();
100        let cyclic_components = components.into_iter().enumerate().map(|(index, component)| {
101            let Some(number) = NonZeroUsize::new(index + 1) else {
102                unreachable!("One-based component vector indices are nonzero");
103            };
104            let group = CycleGroupId { number };
105            for node in &component {
106                node_groups.insert(*node, group);
107            }
108            CyclicComponent { group, nodes: component.into_iter().collect() }
109        }).collect();
110        let edge_groups = edges.into_iter().map(|(edge, source_index, target_index)| {
111            let source = node_groups.get(&source_index);
112            let target = node_groups.get(&target_index);
113            let group = match (source, target) {
114                (Some(source_group), Some(target_group)) if source_group == target_group => Some(*source_group),
115                _ => None,
116            };
117            (Edge::new(edge.source().clone(), edge.target().clone(), edge.kind()), group)
118        }).collect();
119        Ok(Self { topology, components: cyclic_components, edge_groups })
120    }
121
122    #[must_use]
123    pub fn edge_group(&self, edge: &Edge<Node>) -> Option<CycleGroupId> {
124        self.edge_groups.get(edge).copied().flatten()
125    }
126
127    #[must_use]
128    pub const fn group_count(&self) -> usize {
129        self.components.len()
130    }
131
132    pub fn cycles(&self, limit: NonZeroUsize) -> Result<Vec<Cycle<Node>>> {
133        let listing = self.bounded_cycles(limit);
134        ensure!(!listing.truncated(), "Cycle count exceeds {limit}; raise the limit to list all cycles");
135        Ok(listing.cycles)
136    }
137
138    #[must_use]
139    pub(super) fn bounded_cycles(&self, limit: NonZeroUsize) -> BoundedCycles<Node> {
140        let mut cycles = Vec::new();
141        let mut truncated = false;
142        'enumeration: for component in &self.components {
143            for &minimum_cycle_node in &component.nodes {
144                let cycle_subgraph = EdgeFiltered::from_fn(&self.topology, |edge| {
145                    let endpoints = [edge.source(), edge.target()];
146                    endpoints.into_iter().all(|node| node >= minimum_cycle_node && component.nodes.contains(&node))
147                });
148                for first_successor in cycle_subgraph.neighbors(minimum_cycle_node) {
149                    let paths: Box<dyn Iterator<Item = Vec<NodeIndex>> + '_> = if first_successor == minimum_cycle_node {
150                        Box::new(iter::once(vec![minimum_cycle_node]))
151                    } else {
152                        let paths = all_simple_paths::<Vec<_>, _, RandomState>(
153                            &cycle_subgraph,
154                            first_successor,
155                            minimum_cycle_node,
156                            0,
157                            None,
158                        );
159                        Box::new(paths)
160                    };
161                    for path in paths {
162                        if cycles.len() == limit.get() {
163                            truncated = true;
164                            break 'enumeration;
165                        }
166                        let path_nodes = iter::once(minimum_cycle_node).chain(path);
167                        let nodes = path_nodes.map(|node| self.topology[node].clone()).collect();
168                        cycles.push(Cycle { nodes, group: component.group });
169                    }
170                }
171            }
172        }
173        cycles.sort_by(|left, right| (left.group, &left.nodes).cmp(&(right.group, &right.nodes)));
174        BoundedCycles { cycles, truncated }
175    }
176}
177
178pub fn analyze_folders(graph: &FolderGraph) -> Result<CycleAnalysis<FolderNode>> {
179    CycleAnalysis::new(graph.nodes(), graph.edges().keys())
180}
181
182pub fn analyze_files(graph: &FileGraph) -> Result<CycleAnalysis<FileNode>> {
183    CycleAnalysis::new(graph.files(), graph.edges().iter())
184}
185
186pub(crate) fn validate_folder_analysis(analysis: &CycleAnalysis<FolderNode>, graph: &FolderGraph) -> Result<()> {
187    ensure!(
188        analysis.topology.node_weights().eq(graph.nodes()) && analysis.edge_groups.keys().eq(graph.edges().keys()),
189        "Cycle analysis does not match the folder graph"
190    );
191    Ok(())
192}
193
194#[cfg(test)]
195mod tests {
196    use std::collections::BTreeMap;
197    use std::collections::BTreeSet;
198    use std::iter;
199    use std::num::NonZeroUsize;
200    use std::panic::catch_unwind;
201    use std::path::Path;
202    use std::path::PathBuf;
203
204    use anyhow::Result;
205    use claims::assert_ok;
206    use nonzero_ext::nonzero;
207    use petgraph::visit::EdgeRef as _;
208    use pretty_assertions::assert_eq;
209    use rstest::rstest;
210
211    use super::CycleAnalysis;
212    use super::analyze_files;
213    use super::analyze_folders;
214    use super::validate_folder_analysis;
215    use crate::SourcePath;
216    use crate::model::DependencyCount;
217    use crate::model::DependencyKind;
218    use crate::model::DependencyKind::Production;
219    use crate::model::DependencyKind::Test;
220    use crate::model::Edge;
221    use crate::model::FileEdge;
222    use crate::model::FileGraph;
223    use crate::model::FileNode;
224    use crate::model::FolderEdge;
225    use crate::model::FolderGraph;
226    use crate::model::FolderNode;
227
228    fn folder_fixture(dependencies: &[(&str, &str, DependencyKind)]) -> Result<FolderGraph> {
229        let edges = folder_dependencies(dependencies);
230        let nodes = edges.keys().flat_map(|edge| [edge.source().clone(), edge.target().clone()]).collect();
231        FolderGraph::new(nodes, edges)
232    }
233
234    #[must_use]
235    fn folder_dependencies(dependencies: &[(&str, &str, DependencyKind)]) -> BTreeMap<FolderEdge, DependencyCount> {
236        dependencies.iter().map(|&(source, target, kind)| {
237            let edge = FolderEdge::new(FolderNode::new(source.into()), FolderNode::new(target.into()), kind);
238            (edge, DependencyCount::new(1))
239        }).collect()
240    }
241
242    #[must_use]
243    fn folder_path(labels: &[&str]) -> Vec<FolderNode> {
244        labels.iter().map(|label| FolderNode::new((*label).into())).collect()
245    }
246
247    #[rstest]
248    #[case(
249        &[],
250        vec![],
251    )]
252    #[case(
253        &[("alpha", "beta", Production), ("beta", "gamma", Production)],
254        vec![],
255    )]
256    #[case(
257        &[("alpha", "beta", Production), ("gamma", "beta", Production)],
258        vec![],
259    )]
260    #[case(
261        &[("alpha", "beta", Production), ("beta", "alpha", Production)],
262        vec![vec!["alpha", "beta", "alpha"]],
263    )]
264    #[case(
265        &[("alpha", "beta", Production), ("beta", "gamma", Production), ("gamma", "alpha", Production)],
266        vec![vec!["alpha", "beta", "gamma", "alpha"]],
267    )]
268    #[case(
269        &[
270            ("alpha", "beta", Production), ("beta", "alpha", Production),
271            ("beta", "gamma", Production), ("gamma", "beta", Production),
272        ],
273        vec![vec!["alpha", "beta", "alpha"], vec!["beta", "gamma", "beta"]],
274    )]
275    #[case(
276        &[("alpha", "alpha", Production)],
277        vec![vec!["alpha", "alpha"]],
278    )]
279    #[case(
280        &[("alpha", "alpha", Production), ("alpha", "beta", Production), ("beta", "alpha", Production)],
281        vec![vec!["alpha", "alpha"], vec!["alpha", "beta", "alpha"]],
282    )]
283    #[case(
284        &[("alpha", "beta", Production), ("alpha", "beta", Test), ("beta", "alpha", Production), ("beta", "alpha", Test)],
285        vec![vec!["alpha", "beta", "alpha"]],
286    )]
287    #[case(
288        &[("alpha", "alpha", Production), ("alpha", "alpha", Test)],
289        vec![vec!["alpha", "alpha"]],
290    )]
291    #[case(
292        &[
293            ("alpha", "beta", Production), ("alpha", "gamma", Production), ("beta", "omega", Production),
294            ("gamma", "omega", Production), ("omega", "alpha", Production),
295        ],
296        vec![vec!["alpha", "beta", "omega", "alpha"], vec!["alpha", "gamma", "omega", "alpha"]],
297    )]
298    #[case(
299        &[
300            ("alpha", "beta", Production), ("beta", "gamma", Production), ("gamma", "alpha", Production),
301            ("alpha", "gamma", Production), ("gamma", "beta", Production), ("beta", "alpha", Production),
302        ],
303        vec![
304            vec!["alpha", "beta", "alpha"], vec!["alpha", "beta", "gamma", "alpha"],
305            vec!["alpha", "gamma", "alpha"], vec!["alpha", "gamma", "beta", "alpha"], vec!["beta", "gamma", "beta"],
306        ],
307    )]
308    fn test_directed_cycle_routes(#[case] dependencies: &[(&str, &str, DependencyKind)], #[case] expected_paths: Vec<Vec<&str>>) {
309        let fixture = folder_fixture(dependencies);
310        let fixture = assert_ok!(fixture, "Cycle-route dependencies must form a valid folder graph");
311        let system_under_test = analyze_folders(&fixture);
312        let system_under_test = assert_ok!(system_under_test, "Folder cycle analysis must succeed");
313        let expected: Vec<_> = expected_paths.into_iter().map(|labels| folder_path(&labels)).collect();
314
315        let cycles = system_under_test.cycles(nonzero!(10_usize));
316        let cycles = assert_ok!(cycles, "All fixture cycles must fit within the enumeration limit");
317        let paths: Vec<_> = cycles.into_iter().map(|cycle| cycle.nodes).collect();
318
319        assert_eq!(expected, paths, "Directed cycle routes or their canonical order differ");
320    }
321
322    #[rstest]
323    #[case::unordered(false)]
324    #[case::sorted(true)]
325    fn test_topology_endpoint_deduplication(#[case] sort_dependencies: bool) {
326        let nodes = BTreeSet::from(["alpha", "beta", "gamma", "omega"]);
327        let dependencies = [
328            ("omega", "omega", Test),
329            ("alpha", "gamma", Production),
330            ("alpha", "beta", Test),
331            ("beta", "alpha", Production),
332            ("alpha", "alpha", Test),
333            ("alpha", "omega", Production),
334            ("gamma", "alpha", Test),
335            ("alpha", "beta", Production),
336            ("omega", "omega", Production),
337            ("alpha", "gamma", Test),
338            ("alpha", "alpha", Production),
339            ("alpha", "omega", Test),
340            ("alpha", "beta", Production),
341            ("omega", "omega", Test),
342            ("alpha", "alpha", Production),
343        ];
344        let mut dependencies: Vec<_> = dependencies.into_iter().map(|(source, target, kind)| {
345            Edge::new(source, target, kind)
346        }).collect();
347        if sort_dependencies {
348            dependencies.sort_unstable();
349        }
350
351        let system_under_test = CycleAnalysis::new(&nodes, dependencies.iter());
352        let system_under_test = assert_ok!(system_under_test, "Repeated typed edges must support cycle analysis");
353        let topology = &system_under_test.topology;
354        let mut topology_edges: Vec<_> = topology.edge_references().map(|edge| {
355            (topology[edge.source()], topology[edge.target()])
356        }).collect();
357        topology_edges.sort_unstable();
358        let edge_groups: Vec<_> = system_under_test.edge_groups.iter().map(|(edge, group)| {
359            (*edge.source(), *edge.target(), edge.kind(), group.map(|identifier| identifier.number().get()))
360        }).collect();
361
362        assert_eq!(topology_edges, [
363            ("alpha", "alpha"), ("alpha", "beta"), ("alpha", "gamma"), ("alpha", "omega"),
364            ("beta", "alpha"), ("gamma", "alpha"), ("omega", "omega"),
365        ], "Topology must retain every distinct endpoint pair exactly once");
366        assert_eq!(edge_groups, [
367            ("alpha", "alpha", Production, Some(1)), ("alpha", "alpha", Test, Some(1)),
368            ("alpha", "beta", Production, Some(1)), ("alpha", "beta", Test, Some(1)),
369            ("alpha", "gamma", Production, Some(1)), ("alpha", "gamma", Test, Some(1)),
370            ("alpha", "omega", Production, None), ("alpha", "omega", Test, None),
371            ("beta", "alpha", Production, Some(1)), ("gamma", "alpha", Test, Some(1)),
372            ("omega", "omega", Production, Some(2)), ("omega", "omega", Test, Some(2)),
373        ], "Topology deduplication must retain every typed group entry, including acyclic edges");
374        assert_eq!(system_under_test.group_count(), 2, "Independent cyclic components must retain separate group IDs");
375
376        let cycles = system_under_test.cycles(nonzero!(4_usize));
377        let cycles = assert_ok!(cycles, "Four distinct cycles must fit the limit despite repeated typed edges");
378        let routes: Vec<_> = cycles.into_iter().map(|cycle| (cycle.group().number().get(), cycle.nodes)).collect();
379
380        assert_eq!(routes, [
381            (1, vec!["alpha", "alpha"]),
382            (1, vec!["alpha", "beta", "alpha"]),
383            (1, vec!["alpha", "gamma", "alpha"]),
384            (2, vec!["omega", "omega"]),
385        ], "Input ordering and repeated edges must not change cycle routes or group IDs");
386    }
387
388    #[rstest]
389    #[case("alpha", "beta", Production, Some(1))]
390    #[case("beta", "alpha", Test, Some(1))]
391    #[case("gamma", "omega", Production, Some(2))]
392    #[case("omega", "gamma", Production, Some(2))]
393    #[case("beta", "gamma", Production, None)]
394    #[case("alpha", "omega", Production, None)]
395    #[case("alpha", "beta", Test, None)]
396    #[case("unknown", "alpha", Production, None)]
397    #[case("entry", "alpha", Production, None)]
398    #[case("omega", "exit", Production, None)]
399    #[case("leaf", "sink", Production, None)]
400    fn test_component_edge_membership(
401        #[case] source: &str,
402        #[case] target: &str,
403        #[case] kind: DependencyKind,
404        #[case] expected_group: Option<usize>,
405    ) {
406        let fixture = folder_fixture(&[
407            ("omega", "gamma", Production),
408            ("gamma", "omega", Production),
409            ("beta", "gamma", Production),
410            ("beta", "alpha", Test),
411            ("alpha", "beta", Production),
412            ("entry", "alpha", Production),
413            ("omega", "exit", Production),
414            ("leaf", "sink", Production),
415        ]);
416        let fixture = assert_ok!(fixture, "Component-membership dependencies must form a valid folder graph");
417        let system_under_test = analyze_folders(&fixture);
418        let system_under_test = assert_ok!(system_under_test, "Component-membership analysis must succeed");
419        let edge = FolderEdge::new(FolderNode::new(source.into()), FolderNode::new(target.into()), kind);
420
421        let group = system_under_test.edge_group(&edge);
422
423        assert_eq!(2, system_under_test.group_count(), "Independent cyclic components were merged");
424        assert_eq!(expected_group, group.map(|identifier| identifier.number().get()), "Incorrect cycle edge group");
425    }
426
427    #[test]
428    fn test_cycle_group_assignment() {
429        let fixture = folder_fixture(&[
430            ("gamma", "omega", Production),
431            ("omega", "gamma", Production),
432            ("alpha", "beta", Production),
433            ("beta", "alpha", Production),
434            ("beta", "gamma", Production),
435        ]);
436        let fixture = assert_ok!(fixture, "Independent cycle groups and their bridge must form a valid graph");
437        let system_under_test = analyze_folders(&fixture);
438        let system_under_test = assert_ok!(system_under_test, "Independent cycle-group analysis must succeed");
439        let expected = [folder_path(&["alpha", "beta", "alpha"]), folder_path(&["gamma", "omega", "gamma"])];
440
441        let cycles = system_under_test.cycles(nonzero!(2_usize));
442        let cycles = assert_ok!(cycles, "Both independent cycles must fit within the limit");
443        let groups: Vec<_> = cycles.iter().map(|cycle| cycle.group().number().get()).collect();
444        let paths: Vec<_> = cycles.into_iter().map(|cycle| cycle.nodes).collect();
445
446        assert_eq!(groups, [1, 2], "Cycle group numbers differ");
447        assert_eq!(paths, expected, "Independent cycle routes or their order differ");
448    }
449
450    #[rstest]
451    #[case(nonzero!(1_usize), true)]
452    #[case(nonzero!(2_usize), false)]
453    #[case(nonzero!(3_usize), false)]
454    fn test_cycle_enumeration_limit(#[case] limit: NonZeroUsize, #[case] exceeds_limit: bool) {
455        let fixture = folder_fixture(&[
456            ("alpha", "beta", Production),
457            ("beta", "alpha", Production),
458            ("beta", "gamma", Production),
459            ("gamma", "beta", Production),
460        ]);
461        let fixture = assert_ok!(fixture, "Overlapping-cycle dependencies must form a valid graph");
462        let system_under_test = analyze_folders(&fixture);
463        let system_under_test = assert_ok!(system_under_test, "Overlapping-cycle analysis must succeed");
464
465        let result = system_under_test.cycles(limit);
466
467        assert_eq!(1, system_under_test.group_count(), "Overlapping cycles have separate groups");
468        if exceeds_limit {
469            assert!(result.is_err(), "Excess cycles were silently truncated");
470        } else {
471            let cycles = assert_ok!(result, "Both overlapping cycles must fit within limit {limit}");
472            assert_eq!(2, cycles.len(), "Enumeration did not retain every cycle within the limit");
473        }
474    }
475
476    #[rstest]
477    #[case::within_group(nonzero!(1_usize), true, false)]
478    #[case::group_boundary(nonzero!(2_usize), true, false)]
479    #[case::later_group(nonzero!(3_usize), true, false)]
480    #[case::reversed_dependencies(nonzero!(3_usize), true, true)]
481    #[case::exact_limit(nonzero!(4_usize), false, false)]
482    #[case::below_limit(nonzero!(5_usize), false, false)]
483    fn test_bounded_cycle_listing(#[case] limit: NonZeroUsize, #[case] truncated: bool, #[case] reverse_dependencies: bool) {
484        const NODE_CYCLE_FIRST: &str = "alpha";
485        const NODE_CYCLE_SHARED: &str = "beta";
486        const NODE_CYCLE_SECOND: &str = "gamma";
487        const NODE_SELF_LOOP_FIRST: &str = "omega";
488        const NODE_SELF_LOOP_SECOND: &str = "zeta";
489
490        let nodes = BTreeSet::from([
491            NODE_CYCLE_FIRST, NODE_CYCLE_SHARED, NODE_CYCLE_SECOND, NODE_SELF_LOOP_FIRST, NODE_SELF_LOOP_SECOND,
492        ]);
493        let mut dependencies: Vec<_> = [
494            (NODE_SELF_LOOP_SECOND, NODE_SELF_LOOP_SECOND, Test),
495            (NODE_CYCLE_SHARED, NODE_CYCLE_SECOND, Production),
496            (NODE_CYCLE_FIRST, NODE_CYCLE_SHARED, Test),
497            (NODE_SELF_LOOP_FIRST, NODE_SELF_LOOP_FIRST, Production),
498            (NODE_CYCLE_SECOND, NODE_CYCLE_SHARED, Production),
499            (NODE_CYCLE_SHARED, NODE_CYCLE_FIRST, Production),
500            (NODE_CYCLE_FIRST, NODE_CYCLE_SHARED, Production),
501            (NODE_SELF_LOOP_SECOND, NODE_SELF_LOOP_SECOND, Production),
502        ].into_iter().map(|(source, target, kind)| Edge::new(source, target, kind)).collect();
503        if reverse_dependencies {
504            dependencies.reverse();
505        }
506        let system_under_test = CycleAnalysis::new(&nodes, dependencies.iter());
507        let system_under_test = assert_ok!(system_under_test, "Cycle analysis failed for the three-component fixture");
508        let expected: Vec<_> = [
509            (1, vec![NODE_CYCLE_FIRST, NODE_CYCLE_SHARED, NODE_CYCLE_FIRST]),
510            (1, vec![NODE_CYCLE_SHARED, NODE_CYCLE_SECOND, NODE_CYCLE_SHARED]),
511            (2, vec![NODE_SELF_LOOP_FIRST, NODE_SELF_LOOP_FIRST]),
512            (3, vec![NODE_SELF_LOOP_SECOND, NODE_SELF_LOOP_SECOND]),
513        ].into_iter().take(limit.get()).collect();
514
515        let listing = system_under_test.bounded_cycles(limit);
516        let routes: Vec<_> = listing.cycles.into_iter().map(|cycle| (cycle.group().number().get(), cycle.nodes)).collect();
517
518        assert_eq!(routes, expected, "Bounded listing differed from the expected groups and chains");
519        assert_eq!(listing.truncated, truncated, "Bounded listing truncation flag differed from the expected value");
520        assert_eq!(system_under_test.group_count(), 3, "Cyclic component count differed from the expected total");
521    }
522
523    #[rstest]
524    #[case::empty(&[])]
525    #[case::acyclic(&[("alpha", "beta", Production), ("beta", "gamma", Production)])]
526    fn test_bounded_cycle_listing_without_cycles(#[case] dependencies: &[(&str, &str, DependencyKind)]) {
527        let system_under_test = folder_fixture(dependencies).and_then(|graph| analyze_folders(&graph));
528        let system_under_test = assert_ok!(system_under_test, "Building and analyzing the acyclic fixture failed");
529
530        let listing = system_under_test.bounded_cycles(NonZeroUsize::MIN);
531
532        assert!(listing.cycles().is_empty(), "Bounded enumeration returned cycles for an acyclic graph");
533        assert!(!listing.truncated(), "Empty cycle listing was marked truncated");
534        assert_eq!(system_under_test.group_count(), 0, "Cycle analysis reported cyclic components for an acyclic graph");
535    }
536
537    #[test]
538    fn test_isolated_nodes() {
539        let fixture = FolderGraph::new(BTreeSet::from([FolderNode::new("isolated".into())]), BTreeMap::new());
540        let fixture = assert_ok!(fixture, "An isolated folder must form a valid graph");
541        let system_under_test = analyze_folders(&fixture);
542        let system_under_test = assert_ok!(system_under_test, "An isolated folder must support cycle analysis");
543
544        let cycles = system_under_test.cycles(NonZeroUsize::MIN);
545        let cycles = assert_ok!(cycles, "An isolated folder must enumerate without exceeding the cycle limit");
546
547        assert_eq!(0, system_under_test.group_count(), "Isolated node became a cyclic component");
548        assert!(cycles.is_empty(), "Isolated node produced a phantom cycle");
549    }
550
551    #[rstest]
552    #[case(Path::new("."), false, 1)]
553    #[case(Path::new("."), true, 0)]
554    #[case(Path::new("alpha"), false, 0)]
555    #[case(Path::new("beta"), false, 0)]
556    fn test_file_cycle_routes(#[case] root: &Path, #[case] exclude_tests: bool, #[case] expected_cycles: usize) {
557        let first_path = SourcePath::new(PathBuf::from_iter(["alpha", "source.rs"]));
558        let first_path = assert_ok!(first_path, "First cycle file must have a valid source path");
559        let first_file = FileNode::new(first_path);
560        let second_path = SourcePath::new(PathBuf::from_iter(["beta", "source.rs"]));
561        let second_path = assert_ok!(second_path, "Second cycle file must have a valid source path");
562        let second_file = FileNode::new(second_path);
563        let fixture = FileGraph::new(
564            BTreeSet::from([first_file.clone(), second_file.clone()]),
565            BTreeSet::from([
566                FileEdge::new(first_file.clone(), second_file.clone(), Production),
567                FileEdge::new(second_file.clone(), first_file.clone(), Test),
568            ]),
569        );
570        let fixture = assert_ok!(fixture, "Production and test cycle edges must form a valid file graph");
571        let fixture = if exclude_tests { fixture.without_test_dependencies() } else { fixture }.within_root(root);
572        let fixture = assert_ok!(fixture, "File cycle fixture must support the requested root: {root:?}");
573        let system_under_test = analyze_files(&fixture);
574        let system_under_test = assert_ok!(system_under_test, "Filtered file graph must support cycle analysis");
575        let expected = vec![first_file.clone(), second_file, first_file];
576
577        let cycles = system_under_test.cycles(NonZeroUsize::MIN);
578        let cycles = assert_ok!(cycles, "Filtered file graph must have at most one cycle");
579
580        assert_eq!(expected_cycles, system_under_test.group_count(), "File cycle components ignored root or test filtering");
581        assert_eq!(expected_cycles, cycles.len(), "File cycle count differs");
582        if expected_cycles != 0 {
583            assert!(cycles.first().is_some_and(|cycle| cycle.nodes() == &expected), "File cycle route differs");
584            assert!(
585                fixture.edges().iter().all(|edge| system_under_test.edge_group(edge).is_some()),
586                "File cycle edge was not grouped"
587            );
588        }
589    }
590
591    #[rstest]
592    #[case("alpha", "unknown")]
593    #[case("unknown", "alpha")]
594    fn test_dependency_endpoint_membership(#[case] source: &str, #[case] target: &str) {
595        let nodes = BTreeSet::from([FolderNode::new("alpha".into())]);
596        let edge = FolderEdge::new(FolderNode::new(source.into()), FolderNode::new(target.into()), Production);
597        let system_under_test = || CycleAnalysis::new(&nodes, iter::once(&edge));
598
599        let result = catch_unwind(system_under_test);
600
601        assert!(result.is_err(), "Missing validated endpoints must be invariant violations, not user errors");
602    }
603
604    #[rstest]
605    #[case(
606        &[("alpha", "beta", Production), ("beta", "gamma", Production)],
607    )]
608    #[case(
609        &[
610            ("alpha", "beta", Production), ("beta", "alpha", Production),
611            ("beta", "gamma", Production), ("gamma", "alpha", Production),
612        ],
613    )]
614    #[case(
615        &[("alpha", "beta", Test), ("beta", "alpha", Production), ("beta", "gamma", Production)],
616    )]
617    #[case(
618        &[("alpha", "beta", Production), ("beta", "alpha", Production)],
619    )]
620    fn test_folder_analysis_dependencies(#[case] dependencies: &[(&str, &str, DependencyKind)]) {
621        let fixture_dependencies = [("alpha", "beta", Production), ("beta", "alpha", Production), ("beta", "gamma", Production)];
622        let fixture = folder_fixture(&fixture_dependencies);
623        let fixture = assert_ok!(fixture, "Original analysis dependencies must form a valid graph");
624        let system_under_test = analyze_folders(&fixture);
625        let system_under_test = assert_ok!(system_under_test, "Original topology must support cycle analysis");
626        let changed_graph = FolderGraph::new(fixture.nodes().clone(), folder_dependencies(dependencies));
627        let changed_graph = assert_ok!(changed_graph, "Changed dependencies must still form a valid graph");
628
629        let result = validate_folder_analysis(&system_under_test, &changed_graph);
630
631        assert!(result.is_err(), "Changed dependency topology or kind accepted an outdated cycle analysis");
632    }
633
634    #[rstest]
635    #[case(&["alpha", "beta"], false)]
636    #[case(&["alpha", "beta", "isolated", "other"], false)]
637    #[case(&["isolated", "beta", "alpha"], true)]
638    fn test_folder_analysis_nodes(#[case] labels: &[&str], #[case] matches_analysis: bool) {
639        let dependencies = [("alpha", "beta", Production), ("beta", "alpha", Production)];
640        let fixture = FolderGraph::new(
641            folder_path(&["alpha", "beta", "isolated"]).into_iter().collect(),
642            folder_dependencies(&dependencies),
643        );
644        let fixture = assert_ok!(fixture, "Cycle and isolated nodes must form a valid graph");
645        let system_under_test = analyze_folders(&fixture);
646        let system_under_test = assert_ok!(system_under_test, "Original node set must support cycle analysis");
647        let changed_graph = FolderGraph::new(folder_path(labels).into_iter().collect(), folder_dependencies(&dependencies));
648        let changed_graph = assert_ok!(changed_graph, "Changed node set must retain every dependency endpoint");
649
650        let result = validate_folder_analysis(&system_under_test, &changed_graph);
651
652        if matches_analysis {
653            assert_ok!(result, "Reordered folder nodes must preserve the cycle analysis topology");
654        } else {
655            assert!(result.is_err(), "Changed folder node set accepted an outdated cycle analysis");
656        }
657    }
658
659    #[rstest]
660    #[case(1)]
661    #[case(27)]
662    fn test_folder_analysis_dependency_counts(#[case] count: usize) {
663        let dependencies = [("alpha", "beta", Production), ("beta", "alpha", Production)];
664        let fixture = folder_fixture(&dependencies);
665        let fixture = assert_ok!(fixture, "Dependency-count fixture must form a valid graph");
666        let system_under_test = analyze_folders(&fixture);
667        let system_under_test = assert_ok!(system_under_test, "Dependency-count fixture must support cycle analysis");
668        let mut edges = folder_dependencies(&dependencies);
669        for weight in edges.values_mut() {
670            *weight = DependencyCount::new(count);
671        }
672        let changed_graph = FolderGraph::new(fixture.nodes().clone(), edges);
673        let changed_graph = assert_ok!(changed_graph, "Changed dependency counts must preserve graph validity");
674
675        let result = validate_folder_analysis(&system_under_test, &changed_graph);
676
677        assert_ok!(result, "Dependency counts must not invalidate an unchanged cycle topology");
678    }
679}