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(&[], 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}