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 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}