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