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