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