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(
230        &[],
231        vec![],
232    )]
233    #[case(
234        &[("alpha", "beta", Production), ("beta", "gamma", Production)],
235        vec![],
236    )]
237    #[case(
238        &[("alpha", "beta", Production), ("gamma", "beta", Production)],
239        vec![],
240    )]
241    #[case(
242        &[("alpha", "beta", Production), ("beta", "alpha", Production)],
243        vec![vec!["alpha", "beta", "alpha"]],
244    )]
245    #[case(
246        &[("alpha", "beta", Production), ("beta", "gamma", Production), ("gamma", "alpha", Production)],
247        vec![vec!["alpha", "beta", "gamma", "alpha"]],
248    )]
249    #[case(
250        &[
251            ("alpha", "beta", Production), ("beta", "alpha", Production),
252            ("beta", "gamma", Production), ("gamma", "beta", Production),
253        ],
254        vec![vec!["alpha", "beta", "alpha"], vec!["beta", "gamma", "beta"]],
255    )]
256    #[case(
257        &[("alpha", "alpha", Production)],
258        vec![vec!["alpha", "alpha"]],
259    )]
260    #[case(
261        &[("alpha", "alpha", Production), ("alpha", "beta", Production), ("beta", "alpha", Production)],
262        vec![vec!["alpha", "alpha"], vec!["alpha", "beta", "alpha"]],
263    )]
264    #[case(
265        &[("alpha", "beta", Production), ("alpha", "beta", Test), ("beta", "alpha", Production), ("beta", "alpha", Test)],
266        vec![vec!["alpha", "beta", "alpha"]],
267    )]
268    #[case(
269        &[("alpha", "alpha", Production), ("alpha", "alpha", Test)],
270        vec![vec!["alpha", "alpha"]],
271    )]
272    #[case(
273        &[
274            ("alpha", "beta", Production), ("alpha", "gamma", Production), ("beta", "omega", Production),
275            ("gamma", "omega", Production), ("omega", "alpha", Production),
276        ],
277        vec![vec!["alpha", "beta", "omega", "alpha"], vec!["alpha", "gamma", "omega", "alpha"]],
278    )]
279    #[case(
280        &[
281            ("alpha", "beta", Production), ("beta", "gamma", Production), ("gamma", "alpha", Production),
282            ("alpha", "gamma", Production), ("gamma", "beta", Production), ("beta", "alpha", Production),
283        ],
284        vec![
285            vec!["alpha", "beta", "alpha"], vec!["alpha", "beta", "gamma", "alpha"],
286            vec!["alpha", "gamma", "alpha"], vec!["alpha", "gamma", "beta", "alpha"], vec!["beta", "gamma", "beta"],
287        ],
288    )]
289    fn test_directed_cycle_routes(#[case] dependencies: &[(&str, &str, DependencyKind)], #[case] expected_paths: Vec<Vec<&str>>) {
290        let fixture = folder_fixture(dependencies);
291        let fixture = assert_ok!(fixture, "Cycle-route dependencies must form a valid folder graph");
292        let system_under_test = analyze_folders(&fixture);
293        let system_under_test = assert_ok!(system_under_test, "Folder cycle analysis must succeed");
294        let expected: Vec<_> = expected_paths.into_iter().map(|labels| folder_path(&labels)).collect();
295
296        let limit = NonZeroUsize::new(10);
297        let limit = assert_some!(limit, "Cycle-route enumeration limit must be nonzero");
298        let cycles = system_under_test.cycles(limit);
299        let cycles = assert_ok!(cycles, "All fixture cycles must fit within the enumeration limit");
300        let paths: Vec<_> = cycles.into_iter().map(|cycle| cycle.nodes).collect();
301
302        assert_eq!(expected, paths, "Directed cycle routes or their canonical order differ");
303    }
304
305    #[rstest]
306    #[case::unordered(false)]
307    #[case::sorted(true)]
308    fn test_topology_endpoint_deduplication(#[case] sort_dependencies: bool) {
309        let nodes = BTreeSet::from(["alpha", "beta", "gamma", "omega"]);
310        let dependencies = [
311            ("omega", "omega", Test),
312            ("alpha", "gamma", Production),
313            ("alpha", "beta", Test),
314            ("beta", "alpha", Production),
315            ("alpha", "alpha", Test),
316            ("alpha", "omega", Production),
317            ("gamma", "alpha", Test),
318            ("alpha", "beta", Production),
319            ("omega", "omega", Production),
320            ("alpha", "gamma", Test),
321            ("alpha", "alpha", Production),
322            ("alpha", "omega", Test),
323            ("alpha", "beta", Production),
324            ("omega", "omega", Test),
325            ("alpha", "alpha", Production),
326        ];
327        let mut dependencies: Vec<_> = dependencies.into_iter().map(|(source, target, kind)| {
328            Edge::new(source, target, kind)
329        }).collect();
330        if sort_dependencies {
331            dependencies.sort_unstable();
332        }
333        let limit = NonZeroUsize::new(4);
334        let limit = assert_some!(limit, "Topology deduplication fixture must have a nonzero cycle limit");
335
336        let system_under_test = CycleAnalysis::new(&nodes, dependencies.iter());
337        let system_under_test = assert_ok!(system_under_test, "Repeated typed edges must support cycle analysis");
338        let topology = &system_under_test.topology;
339        let mut topology_edges: Vec<_> = topology.edge_references().map(|edge| {
340            (topology[edge.source()], topology[edge.target()])
341        }).collect();
342        topology_edges.sort_unstable();
343        let edge_groups: Vec<_> = system_under_test.edge_groups.iter().map(|(edge, group)| {
344            (*edge.source(), *edge.target(), edge.kind(), group.map(|identifier| identifier.number().get()))
345        }).collect();
346
347        assert_eq!(topology_edges, [
348            ("alpha", "alpha"), ("alpha", "beta"), ("alpha", "gamma"), ("alpha", "omega"),
349            ("beta", "alpha"), ("gamma", "alpha"), ("omega", "omega"),
350        ], "Topology must retain every distinct endpoint pair exactly once");
351        assert_eq!(edge_groups, [
352            ("alpha", "alpha", Production, Some(1)), ("alpha", "alpha", Test, Some(1)),
353            ("alpha", "beta", Production, Some(1)), ("alpha", "beta", Test, Some(1)),
354            ("alpha", "gamma", Production, Some(1)), ("alpha", "gamma", Test, Some(1)),
355            ("alpha", "omega", Production, None), ("alpha", "omega", Test, None),
356            ("beta", "alpha", Production, Some(1)), ("gamma", "alpha", Test, Some(1)),
357            ("omega", "omega", Production, Some(2)), ("omega", "omega", Test, Some(2)),
358        ], "Topology deduplication must retain every typed group entry, including acyclic edges");
359        assert_eq!(system_under_test.group_count(), 2, "Independent cyclic components must retain separate group IDs");
360
361        let cycles = system_under_test.cycles(limit);
362        let cycles = assert_ok!(cycles, "Four distinct cycles must fit the limit despite repeated typed edges");
363        let routes: Vec<_> = cycles.into_iter().map(|cycle| (cycle.group().number().get(), cycle.nodes)).collect();
364
365        assert_eq!(routes, [
366            (1, vec!["alpha", "alpha"]),
367            (1, vec!["alpha", "beta", "alpha"]),
368            (1, vec!["alpha", "gamma", "alpha"]),
369            (2, vec!["omega", "omega"]),
370        ], "Input ordering and repeated edges must not change cycle routes or group IDs");
371    }
372
373    #[rstest]
374    #[case("alpha", "beta", Production, Some(1))]
375    #[case("beta", "alpha", Test, Some(1))]
376    #[case("gamma", "omega", Production, Some(2))]
377    #[case("omega", "gamma", Production, Some(2))]
378    #[case("beta", "gamma", Production, None)]
379    #[case("alpha", "omega", Production, None)]
380    #[case("alpha", "beta", Test, None)]
381    #[case("unknown", "alpha", Production, None)]
382    #[case("entry", "alpha", Production, None)]
383    #[case("omega", "exit", Production, None)]
384    #[case("leaf", "sink", Production, None)]
385    fn test_component_edge_membership(
386        #[case] source: &str,
387        #[case] target: &str,
388        #[case] kind: DependencyKind,
389        #[case] expected_group: Option<usize>,
390    ) {
391        let fixture = folder_fixture(&[
392            ("omega", "gamma", Production),
393            ("gamma", "omega", Production),
394            ("beta", "gamma", Production),
395            ("beta", "alpha", Test),
396            ("alpha", "beta", Production),
397            ("entry", "alpha", Production),
398            ("omega", "exit", Production),
399            ("leaf", "sink", Production),
400        ]);
401        let fixture = assert_ok!(fixture, "Component-membership dependencies must form a valid folder graph");
402        let system_under_test = analyze_folders(&fixture);
403        let system_under_test = assert_ok!(system_under_test, "Component-membership analysis must succeed");
404        let edge = FolderEdge::new(FolderNode::new(source.into()), FolderNode::new(target.into()), kind);
405
406        let group = system_under_test.edge_group(&edge);
407
408        assert_eq!(2, system_under_test.group_count(), "Independent cyclic components were merged");
409        assert_eq!(expected_group, group.map(|identifier| identifier.number().get()), "Incorrect cycle edge group");
410    }
411
412    #[test]
413    fn test_cycle_group_assignment() {
414        let fixture = folder_fixture(&[
415            ("gamma", "omega", Production),
416            ("omega", "gamma", Production),
417            ("alpha", "beta", Production),
418            ("beta", "alpha", Production),
419            ("beta", "gamma", Production),
420        ]);
421        let fixture = assert_ok!(fixture, "Independent cycle groups and their bridge must form a valid graph");
422        let system_under_test = analyze_folders(&fixture);
423        let system_under_test = assert_ok!(system_under_test, "Independent cycle-group analysis must succeed");
424        let expected = [folder_path(&["alpha", "beta", "alpha"]), folder_path(&["gamma", "omega", "gamma"])];
425
426        let limit = NonZeroUsize::new(2);
427        let limit = assert_some!(limit, "Two-cycle enumeration limit must be nonzero");
428        let cycles = system_under_test.cycles(limit);
429        let cycles = assert_ok!(cycles, "Both independent cycles must fit within the limit");
430        let groups: Vec<_> = cycles.iter().map(|cycle| cycle.group().number().get()).collect();
431        let paths: Vec<_> = cycles.into_iter().map(|cycle| cycle.nodes).collect();
432
433        assert_eq!(groups, [1, 2], "Cycle group numbers differ");
434        assert_eq!(paths, expected, "Independent cycle routes or their order differ");
435    }
436
437    #[rstest]
438    #[case(1, true)]
439    #[case(2, false)]
440    #[case(3, false)]
441    fn test_cycle_enumeration_limit(#[case] limit: usize, #[case] exceeds_limit: bool) {
442        let fixture = folder_fixture(&[
443            ("alpha", "beta", Production),
444            ("beta", "alpha", Production),
445            ("beta", "gamma", Production),
446            ("gamma", "beta", Production),
447        ]);
448        let fixture = assert_ok!(fixture, "Overlapping-cycle dependencies must form a valid graph");
449        let system_under_test = analyze_folders(&fixture);
450        let system_under_test = assert_ok!(system_under_test, "Overlapping-cycle analysis must succeed");
451
452        let limit = NonZeroUsize::new(limit);
453        let limit = assert_some!(limit, "Parameterized cycle limit must be nonzero");
454        let result = system_under_test.cycles(limit);
455
456        assert_eq!(1, system_under_test.group_count(), "Overlapping cycles have separate groups");
457        if exceeds_limit {
458            assert!(result.is_err(), "Excess cycles were silently truncated");
459        } else {
460            let cycles = assert_ok!(result, "Both overlapping cycles must fit within limit {limit}");
461            assert_eq!(2, cycles.len(), "Enumeration did not retain every cycle within the limit");
462        }
463    }
464
465    #[test]
466    fn test_isolated_nodes() {
467        let fixture = FolderGraph::new(BTreeSet::from([FolderNode::new("isolated".into())]), BTreeMap::new());
468        let fixture = assert_ok!(fixture, "An isolated folder must form a valid graph");
469        let system_under_test = analyze_folders(&fixture);
470        let system_under_test = assert_ok!(system_under_test, "An isolated folder must support cycle analysis");
471
472        let cycles = system_under_test.cycles(NonZeroUsize::MIN);
473        let cycles = assert_ok!(cycles, "An isolated folder must enumerate without exceeding the cycle limit");
474
475        assert_eq!(0, system_under_test.group_count(), "Isolated node became a cyclic component");
476        assert!(cycles.is_empty(), "Isolated node produced a phantom cycle");
477    }
478
479    #[rstest]
480    #[case(Path::new("."), false, 1)]
481    #[case(Path::new("."), true, 0)]
482    #[case(Path::new("alpha"), false, 0)]
483    #[case(Path::new("beta"), false, 0)]
484    fn test_file_cycle_routes(#[case] root: &Path, #[case] exclude_tests: bool, #[case] expected_cycles: usize) {
485        let first_path = SourcePath::new(PathBuf::from_iter(["alpha", "source.rs"]));
486        let first_path = assert_ok!(first_path, "First cycle file must have a valid source path");
487        let first_file = FileNode::new(first_path);
488        let second_path = SourcePath::new(PathBuf::from_iter(["beta", "source.rs"]));
489        let second_path = assert_ok!(second_path, "Second cycle file must have a valid source path");
490        let second_file = FileNode::new(second_path);
491        let fixture = FileGraph::new(
492            BTreeSet::from([first_file.clone(), second_file.clone()]),
493            BTreeSet::from([
494                FileEdge::new(first_file.clone(), second_file.clone(), Production),
495                FileEdge::new(second_file.clone(), first_file.clone(), Test),
496            ]),
497        );
498        let fixture = assert_ok!(fixture, "Production and test cycle edges must form a valid file graph");
499        let fixture = if exclude_tests { fixture.without_test_dependencies() } else { fixture }.within_root(root);
500        let fixture = assert_ok!(fixture, "File cycle fixture must support the requested root: {root:?}");
501        let system_under_test = analyze_files(&fixture);
502        let system_under_test = assert_ok!(system_under_test, "Filtered file graph must support cycle analysis");
503        let expected = vec![first_file.clone(), second_file, first_file];
504
505        let cycles = system_under_test.cycles(NonZeroUsize::MIN);
506        let cycles = assert_ok!(cycles, "Filtered file graph must have at most one cycle");
507
508        assert_eq!(expected_cycles, system_under_test.group_count(), "File cycle components ignored root or test filtering");
509        assert_eq!(expected_cycles, cycles.len(), "File cycle count differs");
510        if expected_cycles != 0 {
511            assert!(cycles.first().is_some_and(|cycle| cycle.nodes() == &expected), "File cycle route differs");
512            assert!(
513                fixture.edges().iter().all(|edge| system_under_test.edge_group(edge).is_some()),
514                "File cycle edge was not grouped"
515            );
516        }
517    }
518
519    #[rstest]
520    #[case("alpha", "unknown")]
521    #[case("unknown", "alpha")]
522    fn test_dependency_endpoint_membership(#[case] source: &str, #[case] target: &str) {
523        let nodes = BTreeSet::from([FolderNode::new("alpha".into())]);
524        let edge = FolderEdge::new(FolderNode::new(source.into()), FolderNode::new(target.into()), Production);
525        let system_under_test = || CycleAnalysis::new(&nodes, iter::once(&edge));
526
527        let result = catch_unwind(system_under_test);
528
529        assert!(result.is_err(), "Missing validated endpoints must be invariant violations, not user errors");
530    }
531
532    #[rstest]
533    #[case(
534        &[("alpha", "beta", Production), ("beta", "gamma", Production)],
535    )]
536    #[case(
537        &[
538            ("alpha", "beta", Production), ("beta", "alpha", Production),
539            ("beta", "gamma", Production), ("gamma", "alpha", Production),
540        ],
541    )]
542    #[case(
543        &[("alpha", "beta", Test), ("beta", "alpha", Production), ("beta", "gamma", Production)],
544    )]
545    #[case(
546        &[("alpha", "beta", Production), ("beta", "alpha", Production)],
547    )]
548    fn test_folder_analysis_dependencies(#[case] dependencies: &[(&str, &str, DependencyKind)]) {
549        let fixture_dependencies = [("alpha", "beta", Production), ("beta", "alpha", Production), ("beta", "gamma", Production)];
550        let fixture = folder_fixture(&fixture_dependencies);
551        let fixture = assert_ok!(fixture, "Original analysis dependencies must form a valid graph");
552        let system_under_test = analyze_folders(&fixture);
553        let system_under_test = assert_ok!(system_under_test, "Original topology must support cycle analysis");
554        let changed_graph = FolderGraph::new(fixture.nodes().clone(), folder_dependencies(dependencies));
555        let changed_graph = assert_ok!(changed_graph, "Changed dependencies must still form a valid graph");
556
557        let result = validate_folder_analysis(&system_under_test, &changed_graph);
558
559        assert!(result.is_err(), "Changed dependency topology or kind accepted an outdated cycle analysis");
560    }
561
562    #[rstest]
563    #[case(&["alpha", "beta"], false)]
564    #[case(&["alpha", "beta", "isolated", "other"], false)]
565    #[case(&["isolated", "beta", "alpha"], true)]
566    fn test_folder_analysis_nodes(#[case] labels: &[&str], #[case] matches_analysis: bool) {
567        let dependencies = [("alpha", "beta", Production), ("beta", "alpha", Production)];
568        let fixture = FolderGraph::new(
569            folder_path(&["alpha", "beta", "isolated"]).into_iter().collect(),
570            folder_dependencies(&dependencies),
571        );
572        let fixture = assert_ok!(fixture, "Cycle and isolated nodes must form a valid graph");
573        let system_under_test = analyze_folders(&fixture);
574        let system_under_test = assert_ok!(system_under_test, "Original node set must support cycle analysis");
575        let changed_graph = FolderGraph::new(folder_path(labels).into_iter().collect(), folder_dependencies(&dependencies));
576        let changed_graph = assert_ok!(changed_graph, "Changed node set must retain every dependency endpoint");
577
578        let result = validate_folder_analysis(&system_under_test, &changed_graph);
579
580        if matches_analysis {
581            assert_ok!(result, "Reordered folder nodes must preserve the cycle analysis topology");
582        } else {
583            assert!(result.is_err(), "Changed folder node set accepted an outdated cycle analysis");
584        }
585    }
586
587    #[rstest]
588    #[case(1)]
589    #[case(27)]
590    fn test_folder_analysis_dependency_counts(#[case] count: usize) {
591        let dependencies = [("alpha", "beta", Production), ("beta", "alpha", Production)];
592        let fixture = folder_fixture(&dependencies);
593        let fixture = assert_ok!(fixture, "Dependency-count fixture must form a valid graph");
594        let system_under_test = analyze_folders(&fixture);
595        let system_under_test = assert_ok!(system_under_test, "Dependency-count fixture must support cycle analysis");
596        let mut edges = folder_dependencies(&dependencies);
597        for weight in edges.values_mut() {
598            *weight = DependencyCount::new(count);
599        }
600        let changed_graph = FolderGraph::new(fixture.nodes().clone(), edges);
601        let changed_graph = assert_ok!(changed_graph, "Changed dependency counts must preserve graph validity");
602
603        let result = validate_folder_analysis(&system_under_test, &changed_graph);
604
605        assert_ok!(result, "Dependency counts must not invalidate an unchanged cycle topology");
606    }
607}