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::Result;
9use anyhow::ensure;
10use getset::CopyGetters;
11use getset::Getters;
12use petgraph::algo::all_simple_paths;
13use petgraph::algo::kosaraju_scc;
14use petgraph::graph::DiGraph;
15use petgraph::graph::NodeIndex;
16use petgraph::visit::EdgeFiltered;
17use petgraph::visit::EdgeRef as _;
18use petgraph::visit::IntoNeighbors as _;
19
20use crate::model::Edge;
21use crate::model::FileGraph;
22use crate::model::FileNode;
23use crate::model::FolderGraph;
24use crate::model::FolderNode;
25
26#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, CopyGetters)]
27#[getset(get_copy = "pub")]
28pub struct CycleGroupId {
29 number: NonZeroUsize,
30}
31
32#[derive(Getters, CopyGetters)]
33pub struct Cycle<Node> {
34 #[getset(get = "pub")]
35 nodes: Vec<Node>,
36 #[getset(get_copy = "pub")]
37 group: CycleGroupId,
38}
39
40struct CyclicComponent {
41 group: CycleGroupId,
42 nodes: BTreeSet<NodeIndex>,
43}
44
45pub struct CycleAnalysis<Node> {
46 topology: DiGraph<Node, ()>,
47 components: Vec<CyclicComponent>,
48 edge_groups: BTreeMap<Edge<Node>, Option<CycleGroupId>>,
49}
50
51impl<Node: Clone + Ord> CycleAnalysis<Node> {
52 fn new<'a>(nodes: &BTreeSet<Node>, edges: impl Iterator<Item = &'a Edge<Node>>) -> Result<Self>
53 where
54 Node: 'a,
55 {
56 let edges: Vec<_> = edges.collect();
57 ensure!(
58 edges.iter().all(|edge| nodes.contains(edge.source()) && nodes.contains(edge.target())),
59 "Cycle analysis has an unknown dependency endpoint"
60 );
61 let mut topology = DiGraph::new();
62 let node_indices: BTreeMap<_, _> = nodes.iter()
63 .map(|node| (node, topology.add_node(node.clone())))
64 .collect();
65 for edge in &edges {
66 topology.update_edge(
67 *node_indices.get(edge.source()).context("Missing cycle source node")?,
68 *node_indices.get(edge.target()).context("Missing cycle target node")?,
69 (),
70 );
71 }
72 let mut components = kosaraju_scc(&topology);
73 components.retain(|component| {
74 component.len() > 1
75 || 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 cyclic_components = Vec::new();
82 let mut node_groups = BTreeMap::new();
83 for (index, component) in components.into_iter().enumerate() {
84 let group = CycleGroupId {
85 number: index.checked_add(1).and_then(NonZeroUsize::new)
86 .context("Cycle group count overflow")?,
87 };
88 for node in &component {
89 node_groups.insert(*node, group);
90 }
91 cyclic_components.push(CyclicComponent {
92 group,
93 nodes: component.into_iter().collect(),
94 });
95 }
96 let edge_groups = edges.into_iter().map(|edge| {
97 let source = node_indices.get(edge.source()).and_then(|node| node_groups.get(node));
98 let target = node_indices.get(edge.target()).and_then(|node| node_groups.get(node));
99 let group = match (source, target) {
100 (Some(source_group), Some(target_group)) if source_group == target_group => {
101 Some(*source_group)
102 }
103 _ => None,
104 };
105 (Edge::new(edge.source().clone(), edge.target().clone(), edge.kind()), group)
106 }).collect();
107 Ok(Self {
108 topology,
109 components: cyclic_components,
110 edge_groups,
111 })
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 [edge.source(), edge.target()].into_iter()
130 .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 Box::new(all_simple_paths::<Vec<_>, _, RandomState>(&cycle_subgraph, first_successor, minimum_cycle_node, 0, None))
137 };
138 for path in paths {
139 ensure!(
140 cycles.len() < limit.get(),
141 "Cycle count exceeds the configured limit of {limit}; increase the limit to enumerate every cycle"
142 );
143 let nodes = iter::once(minimum_cycle_node).chain(path)
144 .map(|node| self.topology.node_weight(node).cloned().context("Missing cycle path node"))
145 .collect::<Result<Vec<_>>>()?;
146 cycles.push(Cycle { nodes, group: component.group });
147 }
148 }
149 }
150 }
151 cycles.sort_by(|left, right| (left.group, &left.nodes).cmp(&(right.group, &right.nodes)));
152 Ok(cycles)
153 }
154}
155
156pub fn analyze_folders(graph: &FolderGraph) -> Result<CycleAnalysis<FolderNode>> {
157 CycleAnalysis::new(graph.nodes(), graph.edges().keys())
158}
159
160pub fn analyze_files(graph: &FileGraph) -> Result<CycleAnalysis<FileNode>> {
161 CycleAnalysis::new(graph.files(), graph.edges().iter())
162}
163
164pub(crate) fn validate_folder_analysis(analysis: &CycleAnalysis<FolderNode>, graph: &FolderGraph) -> Result<()> {
165 ensure!(
166 analysis.topology.node_weights().eq(graph.nodes())
167 && analysis.edge_groups.keys().eq(graph.edges().keys()),
168 "Cycle analysis does not match the folder graph"
169 );
170 Ok(())
171}
172
173#[cfg(test)]
174#[expect(
175 clippy::panic_in_result_fn,
176 reason = "Tests use assertions for expectations while returning Result for fallible setup."
177)]
178mod tests {
179 use std::collections::BTreeMap;
180 use std::collections::BTreeSet;
181 use std::iter;
182 use std::num::NonZeroUsize;
183 use std::path::Path;
184 use std::path::PathBuf;
185
186 use anyhow::Context as _;
187 use anyhow::Result;
188 use pretty_assertions::assert_eq;
189 use rstest::rstest;
190
191 use super::CycleAnalysis;
192 use super::analyze_files;
193 use super::analyze_folders;
194 use super::validate_folder_analysis;
195 use crate::model::DependencyCount;
196 use crate::model::DependencyKind;
197 use crate::model::DependencyKind::Production;
198 use crate::model::DependencyKind::Test;
199 use crate::model::FileEdge;
200 use crate::model::FileGraph;
201 use crate::model::FileNode;
202 use crate::model::FolderEdge;
203 use crate::model::FolderGraph;
204 use crate::model::FolderNode;
205
206 fn folder_fixture(dependencies: &[(&str, &str, DependencyKind)]) -> Result<FolderGraph> {
207 let edges = folder_dependencies(dependencies);
208 let nodes = edges.keys()
209 .flat_map(|edge| [edge.source().clone(), edge.target().clone()])
210 .collect();
211 FolderGraph::new(nodes, edges)
212 }
213
214 #[must_use]
215 fn folder_dependencies(dependencies: &[(&str, &str, DependencyKind)]) -> BTreeMap<FolderEdge, DependencyCount> {
216 dependencies.iter().map(|&(source, target, kind)| {
217 (FolderEdge::new(FolderNode::new(source.into()), FolderNode::new(target.into()), kind), DependencyCount::new(1))
218 }).collect()
219 }
220
221 #[must_use]
222 fn folder_path(labels: &[&str]) -> Vec<FolderNode> {
223 labels.iter().map(|label| FolderNode::new((*label).into())).collect()
224 }
225
226 #[rstest]
227 #[case(&[], vec![])]
228 #[case(&[("alpha", "beta", Production), ("beta", "gamma", Production)], vec![])]
229 #[case(&[("alpha", "beta", Production), ("gamma", "beta", Production)], vec![])]
230 #[case(
231 &[("alpha", "beta", Production), ("beta", "alpha", Production)],
232 vec![vec!["alpha", "beta", "alpha"]]
233 )]
234 #[case(
235 &[("alpha", "beta", Production), ("beta", "gamma", Production), ("gamma", "alpha", Production)],
236 vec![vec!["alpha", "beta", "gamma", "alpha"]]
237 )]
238 #[case(
239 &[("alpha", "beta", Production), ("beta", "alpha", Production), ("beta", "gamma", Production), ("gamma", "beta", Production)],
240 vec![vec!["alpha", "beta", "alpha"], vec!["beta", "gamma", "beta"]]
241 )]
242 #[case(
243 &[("alpha", "alpha", Production)],
244 vec![vec!["alpha", "alpha"]]
245 )]
246 #[case(
247 &[("alpha", "alpha", Production), ("alpha", "beta", Production), ("beta", "alpha", Production)],
248 vec![vec!["alpha", "alpha"], vec!["alpha", "beta", "alpha"]]
249 )]
250 #[case(
251 &[("alpha", "beta", Production), ("alpha", "beta", Test), ("beta", "alpha", Production), ("beta", "alpha", Test)],
252 vec![vec!["alpha", "beta", "alpha"]]
253 )]
254 #[case(
255 &[("alpha", "alpha", Production), ("alpha", "alpha", Test)],
256 vec![vec!["alpha", "alpha"]]
257 )]
258 #[case(
259 &[("alpha", "beta", Production), ("alpha", "gamma", Production), ("beta", "omega", Production), ("gamma", "omega", Production), ("omega", "alpha", Production)],
260 vec![vec!["alpha", "beta", "omega", "alpha"], vec!["alpha", "gamma", "omega", "alpha"]]
261 )]
262 #[case(
263 &[("alpha", "beta", Production), ("beta", "gamma", Production), ("gamma", "alpha", Production), ("alpha", "gamma", Production), ("gamma", "beta", Production), ("beta", "alpha", Production)],
264 vec![vec!["alpha", "beta", "alpha"], vec!["alpha", "beta", "gamma", "alpha"], vec!["alpha", "gamma", "alpha"], vec!["alpha", "gamma", "beta", "alpha"], vec!["beta", "gamma", "beta"]]
265 )]
266 fn test_directed_cycle_routes(
267 #[case] dependencies: &[(&str, &str, DependencyKind)],
268 #[case] expected_paths: Vec<Vec<&str>>,
269 ) -> Result<()> {
270 let fixture = folder_fixture(dependencies)?;
271 let system_under_test = analyze_folders(&fixture)?;
272 let expected: Vec<_> = expected_paths.into_iter().map(|labels| folder_path(&labels)).collect();
273
274 let cycles = system_under_test.cycles(NonZeroUsize::new(10).context("Invalid test cycle limit")?)?;
275 let paths: Vec<_> = cycles.into_iter().map(|cycle| cycle.nodes).collect();
276
277 assert_eq!(expected, paths, "Directed cycle routes or their canonical order differ");
278 Ok(())
279 }
280
281 #[rstest]
282 #[case("alpha", "beta", Production, Some(1))]
283 #[case("beta", "alpha", Test, Some(1))]
284 #[case("gamma", "omega", Production, Some(2))]
285 #[case("omega", "gamma", Production, Some(2))]
286 #[case("beta", "gamma", Production, None)]
287 #[case("alpha", "omega", Production, None)]
288 #[case("alpha", "beta", Test, None)]
289 #[case("unknown", "alpha", Production, None)]
290 fn test_component_edge_membership(
291 #[case] source: &str,
292 #[case] target: &str,
293 #[case] kind: DependencyKind,
294 #[case] expected_group: Option<usize>,
295 ) -> Result<()> {
296 let fixture = folder_fixture(&[
297 ("omega", "gamma", Production),
298 ("gamma", "omega", Production),
299 ("beta", "gamma", Production),
300 ("beta", "alpha", Test),
301 ("alpha", "beta", Production),
302 ])?;
303 let system_under_test = analyze_folders(&fixture)?;
304 let edge = FolderEdge::new(FolderNode::new(source.into()), FolderNode::new(target.into()), kind);
305
306 let group = system_under_test.edge_group(&edge);
307
308 assert_eq!(2, system_under_test.group_count(), "Independent cyclic components were merged");
309 assert_eq!(expected_group, group.map(|identifier| identifier.number().get()), "Incorrect cycle edge group");
310 Ok(())
311 }
312
313 #[test]
314 fn test_cycle_group_assignment() -> Result<()> {
315 let fixture = folder_fixture(&[
316 ("gamma", "omega", Production),
317 ("omega", "gamma", Production),
318 ("alpha", "beta", Production),
319 ("beta", "alpha", Production),
320 ("beta", "gamma", Production),
321 ])?;
322 let system_under_test = analyze_folders(&fixture)?;
323 let expected = [folder_path(&["alpha", "beta", "alpha"]), folder_path(&["gamma", "omega", "gamma"])];
324
325 let cycles = system_under_test.cycles(NonZeroUsize::new(2).context("Invalid test cycle limit")?)?;
326 let groups: Vec<_> = cycles.iter().map(|cycle| cycle.group().number().get()).collect();
327 let paths: Vec<_> = cycles.into_iter().map(|cycle| cycle.nodes).collect();
328
329 assert_eq!(groups, [1, 2], "Cycle group numbers differ");
330 assert_eq!(paths, expected, "Independent cycle routes or their order differ");
331 Ok(())
332 }
333
334 #[rstest]
335 #[case(1, true)]
336 #[case(2, false)]
337 #[case(3, false)]
338 fn test_cycle_enumeration_limit(#[case] limit: usize, #[case] exceeds_limit: bool) -> Result<()> {
339 let fixture = folder_fixture(&[
340 ("alpha", "beta", Production),
341 ("beta", "alpha", Production),
342 ("beta", "gamma", Production),
343 ("gamma", "beta", Production),
344 ])?;
345 let system_under_test = analyze_folders(&fixture)?;
346
347 let result = system_under_test.cycles(NonZeroUsize::new(limit).context("Invalid test cycle limit")?);
348
349 assert_eq!(1, system_under_test.group_count(), "Overlapping cycles have separate groups");
350 if exceeds_limit {
351 assert!(result.is_err(), "Excess cycles were silently truncated");
352 } else {
353 assert_eq!(2, result?.len(), "Enumeration did not retain every cycle within the limit");
354 }
355 Ok(())
356 }
357
358 #[test]
359 fn test_isolated_nodes() -> Result<()> {
360 let fixture = FolderGraph::new(BTreeSet::from([FolderNode::new("isolated".into())]), BTreeMap::new())?;
361 let system_under_test = analyze_folders(&fixture)?;
362
363 let cycles = system_under_test.cycles(NonZeroUsize::MIN)?;
364
365 assert_eq!(0, system_under_test.group_count(), "Isolated node became a cyclic component");
366 assert!(cycles.is_empty(), "Isolated node produced a phantom cycle");
367 Ok(())
368 }
369
370 #[rstest]
371 #[case(Path::new("."), false, 1)]
372 #[case(Path::new("."), true, 0)]
373 #[case(Path::new("alpha"), false, 0)]
374 #[case(Path::new("beta"), false, 0)]
375 fn test_file_cycle_routes(
376 #[case] root: &Path,
377 #[case] exclude_tests: bool,
378 #[case] expected_cycles: usize,
379 ) -> Result<()> {
380 let first_file = FileNode::new(PathBuf::from_iter(["alpha", "source.rs"]))?;
381 let second_file = FileNode::new(PathBuf::from_iter(["beta", "source.rs"]))?;
382 let fixture = FileGraph::new(
383 BTreeSet::from([first_file.clone(), second_file.clone()]),
384 BTreeSet::from([
385 FileEdge::new(first_file.clone(), second_file.clone(), Production),
386 FileEdge::new(second_file.clone(), first_file.clone(), Test),
387 ]),
388 )?;
389 let fixture = if exclude_tests { fixture.without_test_dependencies() } else { fixture }.within_root(root)?;
390 let system_under_test = analyze_files(&fixture)?;
391 let expected = vec![first_file.clone(), second_file, first_file];
392
393 let cycles = system_under_test.cycles(NonZeroUsize::MIN)?;
394
395 assert_eq!(expected_cycles, system_under_test.group_count(), "File cycle components ignored root or test filtering");
396 assert_eq!(expected_cycles, cycles.len(), "File cycle count differs");
397 if expected_cycles != 0 {
398 assert!(cycles.first().is_some_and(|cycle| cycle.nodes() == &expected), "File cycle route differs");
399 assert!(fixture.edges().iter().all(|edge| system_under_test.edge_group(edge).is_some()), "File cycle edge was not grouped");
400 }
401 Ok(())
402 }
403
404 #[test]
405 fn test_dependency_endpoint_membership() -> Result<()> {
406 let nodes = BTreeSet::from([FolderNode::new("alpha".into())]);
407 let edge = FolderEdge::new(FolderNode::new("alpha".into()), FolderNode::new("unknown".into()), Production);
408
409 let system_under_test = CycleAnalysis::new(&nodes, iter::once(&edge));
410
411 assert!(system_under_test.is_err(), "Unknown dependency endpoint was accepted");
412 Ok(())
413 }
414
415 #[rstest]
416 #[case(&[("alpha", "beta", Production), ("beta", "gamma", Production)])]
417 #[case(&[("alpha", "beta", Production), ("beta", "alpha", Production), ("beta", "gamma", Production), ("gamma", "alpha", Production)])]
418 #[case(&[("alpha", "beta", Test), ("beta", "alpha", Production), ("beta", "gamma", Production)])]
419 #[case(&[("alpha", "beta", Production), ("beta", "alpha", Production)])]
420 fn test_folder_analysis_dependencies(#[case] dependencies: &[(&str, &str, DependencyKind)]) -> Result<()> {
421 let fixture = folder_fixture(&[
422 ("alpha", "beta", Production),
423 ("beta", "alpha", Production),
424 ("beta", "gamma", Production),
425 ])?;
426 let system_under_test = analyze_folders(&fixture)?;
427 let changed_graph = FolderGraph::new(fixture.nodes().clone(), folder_dependencies(dependencies))?;
428
429 let result = validate_folder_analysis(&system_under_test, &changed_graph);
430
431 assert!(result.is_err(), "Changed dependency topology or kind accepted an outdated cycle analysis");
432 Ok(())
433 }
434
435 #[rstest]
436 #[case(&["alpha", "beta"], false)]
437 #[case(&["alpha", "beta", "isolated", "other"], false)]
438 #[case(&["isolated", "beta", "alpha"], true)]
439 fn test_folder_analysis_nodes(#[case] labels: &[&str], #[case] matches_analysis: bool) -> Result<()> {
440 let dependencies = [("alpha", "beta", Production), ("beta", "alpha", Production)];
441 let fixture = FolderGraph::new(
442 folder_path(&["alpha", "beta", "isolated"]).into_iter().collect(),
443 folder_dependencies(&dependencies),
444 )?;
445 let system_under_test = analyze_folders(&fixture)?;
446 let changed_graph = FolderGraph::new(folder_path(labels).into_iter().collect(), folder_dependencies(&dependencies))?;
447
448 let result = validate_folder_analysis(&system_under_test, &changed_graph);
449
450 assert_eq!(matches_analysis, result.is_ok(), "Cycle analysis did not validate the full folder node set");
451 Ok(())
452 }
453
454 #[rstest]
455 #[case(1)]
456 #[case(27)]
457 fn test_folder_analysis_dependency_counts(#[case] count: usize) -> Result<()> {
458 let dependencies = [("alpha", "beta", Production), ("beta", "alpha", Production)];
459 let fixture = folder_fixture(&dependencies)?;
460 let system_under_test = analyze_folders(&fixture)?;
461 let mut edges = folder_dependencies(&dependencies);
462 for weight in edges.values_mut() {
463 *weight = DependencyCount::new(count);
464 }
465 let changed_graph = FolderGraph::new(fixture.nodes().clone(), edges)?;
466
467 let result = validate_folder_analysis(&system_under_test, &changed_graph);
468
469 assert!(result.is_ok(), "Dependency counts invalidated an unchanged cycle topology");
470 Ok(())
471 }
472}