use std::collections::BTreeMap;
use std::collections::BTreeSet;
use std::collections::hash_map::RandomState;
use std::iter;
use std::num::NonZeroUsize;
use anyhow::Context as _;
use anyhow::Error;
use anyhow::Result;
use anyhow::ensure;
use getset::CopyGetters;
use getset::Getters;
use petgraph::algo::all_simple_paths;
use petgraph::algo::kosaraju_scc;
use petgraph::graph::DiGraph;
use petgraph::graph::GraphError;
use petgraph::graph::NodeIndex;
use petgraph::visit::EdgeFiltered;
use petgraph::visit::EdgeRef as _;
use petgraph::visit::IntoNeighbors as _;
use crate::model::Edge;
use crate::model::FileGraph;
use crate::model::FileNode;
use crate::model::FolderGraph;
use crate::model::FolderNode;
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, CopyGetters)]
#[getset(get_copy = "pub")]
pub struct CycleGroupId {
number: NonZeroUsize,
}
#[derive(Getters, CopyGetters)]
pub struct Cycle<Node> {
#[getset(get = "pub")]
nodes: Vec<Node>,
#[getset(get_copy = "pub")]
group: CycleGroupId,
}
#[derive(Getters, CopyGetters)]
pub(super) struct BoundedCycles<Node> {
#[getset(get = "pub(super)")]
cycles: Vec<Cycle<Node>>,
#[getset(get_copy = "pub(super)")]
truncated: bool,
}
struct CyclicComponent {
group: CycleGroupId,
nodes: BTreeSet<NodeIndex>,
}
pub struct CycleAnalysis<Node> {
topology: DiGraph<Node, ()>,
components: Vec<CyclicComponent>,
edge_groups: BTreeMap<Edge<Node>, Option<CycleGroupId>>,
}
impl<Node: Clone + Ord> CycleAnalysis<Node> {
fn new<'a>(nodes: &BTreeSet<Node>, edges: impl Iterator<Item = &'a Edge<Node>>) -> Result<Self> where Node: 'a {
let mut topology = DiGraph::new();
let node_indices = nodes.iter().map(|node| topology.try_add_node(node.clone()).map(|index| (node, index)));
let node_indices: Result<BTreeMap<_, _>, _> = node_indices.collect();
let node_indices = node_indices.context("Cycle analysis exceeds the supported node index capacity")?;
let mut edges: Vec<_> = edges.map(|edge| {
let endpoints = (node_indices.get(edge.source()), node_indices.get(edge.target()));
let (Some(&source_index), Some(&target_index)) = endpoints else {
unreachable!("Validated cycle edge endpoints must have topology indices");
};
(edge, source_index, target_index)
}).collect();
edges.sort_unstable_by_key(|&(_, source_index, target_index)| (source_index, target_index));
let mut previous_endpoints = None;
for &(_, source_index, target_index) in &edges {
let endpoints = (source_index, target_index);
if previous_endpoints == Some(endpoints) {
continue;
}
previous_endpoints = Some(endpoints);
topology.try_add_edge(source_index, target_index, ()).map_err(|error| match error {
GraphError::EdgeIxLimit => Error::new(error).context("Cycle analysis exceeds the supported edge index capacity"),
GraphError::NodeIxLimit => unreachable!("Adding a cycle edge cannot add nodes"),
GraphError::NodeMissed(_) | GraphError::NodeOutBounds => {
unreachable!("Cycle edge endpoints were added to the topology")
}
})?;
}
let mut components = kosaraju_scc(&topology);
components.retain(|component| {
component.len() > 1 || component.first().is_some_and(|node| topology.contains_edge(*node, *node))
});
for component in &mut components {
component.sort_unstable();
}
components.sort_unstable();
let mut node_groups = BTreeMap::new();
let cyclic_components = components.into_iter().enumerate().map(|(index, component)| {
let Some(number) = NonZeroUsize::new(index + 1) else {
unreachable!("One-based component vector indices are nonzero");
};
let group = CycleGroupId { number };
for node in &component {
node_groups.insert(*node, group);
}
CyclicComponent { group, nodes: component.into_iter().collect() }
}).collect();
let edge_groups = edges.into_iter().map(|(edge, source_index, target_index)| {
let source = node_groups.get(&source_index);
let target = node_groups.get(&target_index);
let group = match (source, target) {
(Some(source_group), Some(target_group)) if source_group == target_group => Some(*source_group),
_ => None,
};
(Edge::new(edge.source().clone(), edge.target().clone(), edge.kind()), group)
}).collect();
Ok(Self { topology, components: cyclic_components, edge_groups })
}
#[must_use]
pub fn edge_group(&self, edge: &Edge<Node>) -> Option<CycleGroupId> {
self.edge_groups.get(edge).copied().flatten()
}
#[must_use]
pub const fn group_count(&self) -> usize {
self.components.len()
}
pub fn cycles(&self, limit: NonZeroUsize) -> Result<Vec<Cycle<Node>>> {
let listing = self.bounded_cycles(limit);
ensure!(!listing.truncated(), "Cycle count exceeds {limit}; raise the limit to list all cycles");
Ok(listing.cycles)
}
#[must_use]
pub(super) fn bounded_cycles(&self, limit: NonZeroUsize) -> BoundedCycles<Node> {
let mut cycles = Vec::new();
let mut truncated = false;
'enumeration: for component in &self.components {
for &minimum_cycle_node in &component.nodes {
let cycle_subgraph = EdgeFiltered::from_fn(&self.topology, |edge| {
let endpoints = [edge.source(), edge.target()];
endpoints.into_iter().all(|node| node >= minimum_cycle_node && component.nodes.contains(&node))
});
for first_successor in cycle_subgraph.neighbors(minimum_cycle_node) {
let paths: Box<dyn Iterator<Item = Vec<NodeIndex>> + '_> = if first_successor == minimum_cycle_node {
Box::new(iter::once(vec![minimum_cycle_node]))
} else {
let paths = all_simple_paths::<Vec<_>, _, RandomState>(
&cycle_subgraph,
first_successor,
minimum_cycle_node,
0,
None,
);
Box::new(paths)
};
for path in paths {
if cycles.len() == limit.get() {
truncated = true;
break 'enumeration;
}
let path_nodes = iter::once(minimum_cycle_node).chain(path);
let nodes = path_nodes.map(|node| self.topology[node].clone()).collect();
cycles.push(Cycle { nodes, group: component.group });
}
}
}
}
cycles.sort_by(|left, right| (left.group, &left.nodes).cmp(&(right.group, &right.nodes)));
BoundedCycles { cycles, truncated }
}
}
pub fn analyze_folders(graph: &FolderGraph) -> Result<CycleAnalysis<FolderNode>> {
CycleAnalysis::new(graph.nodes(), graph.edges().keys())
}
pub fn analyze_files(graph: &FileGraph) -> Result<CycleAnalysis<FileNode>> {
CycleAnalysis::new(graph.files(), graph.edges().iter())
}
pub(crate) fn validate_folder_analysis(analysis: &CycleAnalysis<FolderNode>, graph: &FolderGraph) -> Result<()> {
ensure!(
analysis.topology.node_weights().eq(graph.nodes()) && analysis.edge_groups.keys().eq(graph.edges().keys()),
"Cycle analysis does not match the folder graph"
);
Ok(())
}
#[cfg(test)]
mod tests {
use std::collections::BTreeMap;
use std::collections::BTreeSet;
use std::iter;
use std::num::NonZeroUsize;
use std::panic::catch_unwind;
use std::path::Path;
use std::path::PathBuf;
use anyhow::Result;
use claims::assert_ok;
use nonzero_ext::nonzero;
use petgraph::visit::EdgeRef as _;
use pretty_assertions::assert_eq;
use rstest::rstest;
use super::CycleAnalysis;
use super::analyze_files;
use super::analyze_folders;
use super::validate_folder_analysis;
use crate::SourcePath;
use crate::model::DependencyCount;
use crate::model::DependencyKind;
use crate::model::DependencyKind::Production;
use crate::model::DependencyKind::Test;
use crate::model::Edge;
use crate::model::FileEdge;
use crate::model::FileGraph;
use crate::model::FileNode;
use crate::model::FolderEdge;
use crate::model::FolderGraph;
use crate::model::FolderNode;
fn folder_fixture(dependencies: &[(&str, &str, DependencyKind)]) -> Result<FolderGraph> {
let edges = folder_dependencies(dependencies);
let nodes = edges.keys().flat_map(|edge| [edge.source().clone(), edge.target().clone()]).collect();
FolderGraph::new(nodes, edges)
}
#[must_use]
fn folder_dependencies(dependencies: &[(&str, &str, DependencyKind)]) -> BTreeMap<FolderEdge, DependencyCount> {
dependencies.iter().map(|&(source, target, kind)| {
let edge = FolderEdge::new(FolderNode::new(source.into()), FolderNode::new(target.into()), kind);
(edge, DependencyCount::new(1))
}).collect()
}
#[must_use]
fn folder_path(labels: &[&str]) -> Vec<FolderNode> {
labels.iter().map(|label| FolderNode::new((*label).into())).collect()
}
#[rstest]
#[case(
&[],
vec![],
)]
#[case(
&[("alpha", "beta", Production), ("beta", "gamma", Production)],
vec![],
)]
#[case(
&[("alpha", "beta", Production), ("gamma", "beta", Production)],
vec![],
)]
#[case(
&[("alpha", "beta", Production), ("beta", "alpha", Production)],
vec![vec!["alpha", "beta", "alpha"]],
)]
#[case(
&[("alpha", "beta", Production), ("beta", "gamma", Production), ("gamma", "alpha", Production)],
vec![vec!["alpha", "beta", "gamma", "alpha"]],
)]
#[case(
&[
("alpha", "beta", Production), ("beta", "alpha", Production),
("beta", "gamma", Production), ("gamma", "beta", Production),
],
vec![vec!["alpha", "beta", "alpha"], vec!["beta", "gamma", "beta"]],
)]
#[case(
&[("alpha", "alpha", Production)],
vec![vec!["alpha", "alpha"]],
)]
#[case(
&[("alpha", "alpha", Production), ("alpha", "beta", Production), ("beta", "alpha", Production)],
vec![vec!["alpha", "alpha"], vec!["alpha", "beta", "alpha"]],
)]
#[case(
&[("alpha", "beta", Production), ("alpha", "beta", Test), ("beta", "alpha", Production), ("beta", "alpha", Test)],
vec![vec!["alpha", "beta", "alpha"]],
)]
#[case(
&[("alpha", "alpha", Production), ("alpha", "alpha", Test)],
vec![vec!["alpha", "alpha"]],
)]
#[case(
&[
("alpha", "beta", Production), ("alpha", "gamma", Production), ("beta", "omega", Production),
("gamma", "omega", Production), ("omega", "alpha", Production),
],
vec![vec!["alpha", "beta", "omega", "alpha"], vec!["alpha", "gamma", "omega", "alpha"]],
)]
#[case(
&[
("alpha", "beta", Production), ("beta", "gamma", Production), ("gamma", "alpha", Production),
("alpha", "gamma", Production), ("gamma", "beta", Production), ("beta", "alpha", Production),
],
vec![
vec!["alpha", "beta", "alpha"], vec!["alpha", "beta", "gamma", "alpha"],
vec!["alpha", "gamma", "alpha"], vec!["alpha", "gamma", "beta", "alpha"], vec!["beta", "gamma", "beta"],
],
)]
fn test_directed_cycle_routes(#[case] dependencies: &[(&str, &str, DependencyKind)], #[case] expected_paths: Vec<Vec<&str>>) {
let fixture = folder_fixture(dependencies);
let fixture = assert_ok!(fixture, "Cycle-route dependencies must form a valid folder graph");
let system_under_test = analyze_folders(&fixture);
let system_under_test = assert_ok!(system_under_test, "Folder cycle analysis must succeed");
let expected: Vec<_> = expected_paths.into_iter().map(|labels| folder_path(&labels)).collect();
let cycles = system_under_test.cycles(nonzero!(10_usize));
let cycles = assert_ok!(cycles, "All fixture cycles must fit within the enumeration limit");
let paths: Vec<_> = cycles.into_iter().map(|cycle| cycle.nodes).collect();
assert_eq!(expected, paths, "Directed cycle routes or their canonical order differ");
}
#[rstest]
#[case::unordered(false)]
#[case::sorted(true)]
fn test_topology_endpoint_deduplication(#[case] sort_dependencies: bool) {
let nodes = BTreeSet::from(["alpha", "beta", "gamma", "omega"]);
let dependencies = [
("omega", "omega", Test),
("alpha", "gamma", Production),
("alpha", "beta", Test),
("beta", "alpha", Production),
("alpha", "alpha", Test),
("alpha", "omega", Production),
("gamma", "alpha", Test),
("alpha", "beta", Production),
("omega", "omega", Production),
("alpha", "gamma", Test),
("alpha", "alpha", Production),
("alpha", "omega", Test),
("alpha", "beta", Production),
("omega", "omega", Test),
("alpha", "alpha", Production),
];
let mut dependencies: Vec<_> = dependencies.into_iter().map(|(source, target, kind)| {
Edge::new(source, target, kind)
}).collect();
if sort_dependencies {
dependencies.sort_unstable();
}
let system_under_test = CycleAnalysis::new(&nodes, dependencies.iter());
let system_under_test = assert_ok!(system_under_test, "Repeated typed edges must support cycle analysis");
let topology = &system_under_test.topology;
let mut topology_edges: Vec<_> = topology.edge_references().map(|edge| {
(topology[edge.source()], topology[edge.target()])
}).collect();
topology_edges.sort_unstable();
let edge_groups: Vec<_> = system_under_test.edge_groups.iter().map(|(edge, group)| {
(*edge.source(), *edge.target(), edge.kind(), group.map(|identifier| identifier.number().get()))
}).collect();
assert_eq!(topology_edges, [
("alpha", "alpha"), ("alpha", "beta"), ("alpha", "gamma"), ("alpha", "omega"),
("beta", "alpha"), ("gamma", "alpha"), ("omega", "omega"),
], "Topology must retain every distinct endpoint pair exactly once");
assert_eq!(edge_groups, [
("alpha", "alpha", Production, Some(1)), ("alpha", "alpha", Test, Some(1)),
("alpha", "beta", Production, Some(1)), ("alpha", "beta", Test, Some(1)),
("alpha", "gamma", Production, Some(1)), ("alpha", "gamma", Test, Some(1)),
("alpha", "omega", Production, None), ("alpha", "omega", Test, None),
("beta", "alpha", Production, Some(1)), ("gamma", "alpha", Test, Some(1)),
("omega", "omega", Production, Some(2)), ("omega", "omega", Test, Some(2)),
], "Topology deduplication must retain every typed group entry, including acyclic edges");
assert_eq!(system_under_test.group_count(), 2, "Independent cyclic components must retain separate group IDs");
let cycles = system_under_test.cycles(nonzero!(4_usize));
let cycles = assert_ok!(cycles, "Four distinct cycles must fit the limit despite repeated typed edges");
let routes: Vec<_> = cycles.into_iter().map(|cycle| (cycle.group().number().get(), cycle.nodes)).collect();
assert_eq!(routes, [
(1, vec!["alpha", "alpha"]),
(1, vec!["alpha", "beta", "alpha"]),
(1, vec!["alpha", "gamma", "alpha"]),
(2, vec!["omega", "omega"]),
], "Input ordering and repeated edges must not change cycle routes or group IDs");
}
#[rstest]
#[case("alpha", "beta", Production, Some(1))]
#[case("beta", "alpha", Test, Some(1))]
#[case("gamma", "omega", Production, Some(2))]
#[case("omega", "gamma", Production, Some(2))]
#[case("beta", "gamma", Production, None)]
#[case("alpha", "omega", Production, None)]
#[case("alpha", "beta", Test, None)]
#[case("unknown", "alpha", Production, None)]
#[case("entry", "alpha", Production, None)]
#[case("omega", "exit", Production, None)]
#[case("leaf", "sink", Production, None)]
fn test_component_edge_membership(
#[case] source: &str,
#[case] target: &str,
#[case] kind: DependencyKind,
#[case] expected_group: Option<usize>,
) {
let fixture = folder_fixture(&[
("omega", "gamma", Production),
("gamma", "omega", Production),
("beta", "gamma", Production),
("beta", "alpha", Test),
("alpha", "beta", Production),
("entry", "alpha", Production),
("omega", "exit", Production),
("leaf", "sink", Production),
]);
let fixture = assert_ok!(fixture, "Component-membership dependencies must form a valid folder graph");
let system_under_test = analyze_folders(&fixture);
let system_under_test = assert_ok!(system_under_test, "Component-membership analysis must succeed");
let edge = FolderEdge::new(FolderNode::new(source.into()), FolderNode::new(target.into()), kind);
let group = system_under_test.edge_group(&edge);
assert_eq!(2, system_under_test.group_count(), "Independent cyclic components were merged");
assert_eq!(expected_group, group.map(|identifier| identifier.number().get()), "Incorrect cycle edge group");
}
#[test]
fn test_cycle_group_assignment() {
let fixture = folder_fixture(&[
("gamma", "omega", Production),
("omega", "gamma", Production),
("alpha", "beta", Production),
("beta", "alpha", Production),
("beta", "gamma", Production),
]);
let fixture = assert_ok!(fixture, "Independent cycle groups and their bridge must form a valid graph");
let system_under_test = analyze_folders(&fixture);
let system_under_test = assert_ok!(system_under_test, "Independent cycle-group analysis must succeed");
let expected = [folder_path(&["alpha", "beta", "alpha"]), folder_path(&["gamma", "omega", "gamma"])];
let cycles = system_under_test.cycles(nonzero!(2_usize));
let cycles = assert_ok!(cycles, "Both independent cycles must fit within the limit");
let groups: Vec<_> = cycles.iter().map(|cycle| cycle.group().number().get()).collect();
let paths: Vec<_> = cycles.into_iter().map(|cycle| cycle.nodes).collect();
assert_eq!(groups, [1, 2], "Cycle group numbers differ");
assert_eq!(paths, expected, "Independent cycle routes or their order differ");
}
#[rstest]
#[case(nonzero!(1_usize), true)]
#[case(nonzero!(2_usize), false)]
#[case(nonzero!(3_usize), false)]
fn test_cycle_enumeration_limit(#[case] limit: NonZeroUsize, #[case] exceeds_limit: bool) {
let fixture = folder_fixture(&[
("alpha", "beta", Production),
("beta", "alpha", Production),
("beta", "gamma", Production),
("gamma", "beta", Production),
]);
let fixture = assert_ok!(fixture, "Overlapping-cycle dependencies must form a valid graph");
let system_under_test = analyze_folders(&fixture);
let system_under_test = assert_ok!(system_under_test, "Overlapping-cycle analysis must succeed");
let result = system_under_test.cycles(limit);
assert_eq!(1, system_under_test.group_count(), "Overlapping cycles have separate groups");
if exceeds_limit {
assert!(result.is_err(), "Excess cycles were silently truncated");
} else {
let cycles = assert_ok!(result, "Both overlapping cycles must fit within limit {limit}");
assert_eq!(2, cycles.len(), "Enumeration did not retain every cycle within the limit");
}
}
#[rstest]
#[case::within_group(nonzero!(1_usize), true, false)]
#[case::group_boundary(nonzero!(2_usize), true, false)]
#[case::later_group(nonzero!(3_usize), true, false)]
#[case::reversed_dependencies(nonzero!(3_usize), true, true)]
#[case::exact_limit(nonzero!(4_usize), false, false)]
#[case::below_limit(nonzero!(5_usize), false, false)]
fn test_bounded_cycle_listing(#[case] limit: NonZeroUsize, #[case] truncated: bool, #[case] reverse_dependencies: bool) {
const NODE_CYCLE_FIRST: &str = "alpha";
const NODE_CYCLE_SHARED: &str = "beta";
const NODE_CYCLE_SECOND: &str = "gamma";
const NODE_SELF_LOOP_FIRST: &str = "omega";
const NODE_SELF_LOOP_SECOND: &str = "zeta";
let nodes = BTreeSet::from([
NODE_CYCLE_FIRST, NODE_CYCLE_SHARED, NODE_CYCLE_SECOND, NODE_SELF_LOOP_FIRST, NODE_SELF_LOOP_SECOND,
]);
let mut dependencies: Vec<_> = [
(NODE_SELF_LOOP_SECOND, NODE_SELF_LOOP_SECOND, Test),
(NODE_CYCLE_SHARED, NODE_CYCLE_SECOND, Production),
(NODE_CYCLE_FIRST, NODE_CYCLE_SHARED, Test),
(NODE_SELF_LOOP_FIRST, NODE_SELF_LOOP_FIRST, Production),
(NODE_CYCLE_SECOND, NODE_CYCLE_SHARED, Production),
(NODE_CYCLE_SHARED, NODE_CYCLE_FIRST, Production),
(NODE_CYCLE_FIRST, NODE_CYCLE_SHARED, Production),
(NODE_SELF_LOOP_SECOND, NODE_SELF_LOOP_SECOND, Production),
].into_iter().map(|(source, target, kind)| Edge::new(source, target, kind)).collect();
if reverse_dependencies {
dependencies.reverse();
}
let system_under_test = CycleAnalysis::new(&nodes, dependencies.iter());
let system_under_test = assert_ok!(system_under_test, "Cycle analysis failed for the three-component fixture");
let expected: Vec<_> = [
(1, vec![NODE_CYCLE_FIRST, NODE_CYCLE_SHARED, NODE_CYCLE_FIRST]),
(1, vec![NODE_CYCLE_SHARED, NODE_CYCLE_SECOND, NODE_CYCLE_SHARED]),
(2, vec![NODE_SELF_LOOP_FIRST, NODE_SELF_LOOP_FIRST]),
(3, vec![NODE_SELF_LOOP_SECOND, NODE_SELF_LOOP_SECOND]),
].into_iter().take(limit.get()).collect();
let listing = system_under_test.bounded_cycles(limit);
let routes: Vec<_> = listing.cycles.into_iter().map(|cycle| (cycle.group().number().get(), cycle.nodes)).collect();
assert_eq!(routes, expected, "Bounded listing differed from the expected groups and chains");
assert_eq!(listing.truncated, truncated, "Bounded listing truncation flag differed from the expected value");
assert_eq!(system_under_test.group_count(), 3, "Cyclic component count differed from the expected total");
}
#[rstest]
#[case::empty(&[])]
#[case::acyclic(&[("alpha", "beta", Production), ("beta", "gamma", Production)])]
fn test_bounded_cycle_listing_without_cycles(#[case] dependencies: &[(&str, &str, DependencyKind)]) {
let system_under_test = folder_fixture(dependencies).and_then(|graph| analyze_folders(&graph));
let system_under_test = assert_ok!(system_under_test, "Building and analyzing the acyclic fixture failed");
let listing = system_under_test.bounded_cycles(NonZeroUsize::MIN);
assert!(listing.cycles().is_empty(), "Bounded enumeration returned cycles for an acyclic graph");
assert!(!listing.truncated(), "Empty cycle listing was marked truncated");
assert_eq!(system_under_test.group_count(), 0, "Cycle analysis reported cyclic components for an acyclic graph");
}
#[test]
fn test_isolated_nodes() {
let fixture = FolderGraph::new(BTreeSet::from([FolderNode::new("isolated".into())]), BTreeMap::new());
let fixture = assert_ok!(fixture, "An isolated folder must form a valid graph");
let system_under_test = analyze_folders(&fixture);
let system_under_test = assert_ok!(system_under_test, "An isolated folder must support cycle analysis");
let cycles = system_under_test.cycles(NonZeroUsize::MIN);
let cycles = assert_ok!(cycles, "An isolated folder must enumerate without exceeding the cycle limit");
assert_eq!(0, system_under_test.group_count(), "Isolated node became a cyclic component");
assert!(cycles.is_empty(), "Isolated node produced a phantom cycle");
}
#[rstest]
#[case(Path::new("."), false, 1)]
#[case(Path::new("."), true, 0)]
#[case(Path::new("alpha"), false, 0)]
#[case(Path::new("beta"), false, 0)]
fn test_file_cycle_routes(#[case] root: &Path, #[case] exclude_tests: bool, #[case] expected_cycles: usize) {
let first_path = SourcePath::new(PathBuf::from_iter(["alpha", "source.rs"]));
let first_path = assert_ok!(first_path, "First cycle file must have a valid source path");
let first_file = FileNode::new(first_path);
let second_path = SourcePath::new(PathBuf::from_iter(["beta", "source.rs"]));
let second_path = assert_ok!(second_path, "Second cycle file must have a valid source path");
let second_file = FileNode::new(second_path);
let fixture = FileGraph::new(
BTreeSet::from([first_file.clone(), second_file.clone()]),
BTreeSet::from([
FileEdge::new(first_file.clone(), second_file.clone(), Production),
FileEdge::new(second_file.clone(), first_file.clone(), Test),
]),
);
let fixture = assert_ok!(fixture, "Production and test cycle edges must form a valid file graph");
let fixture = if exclude_tests { fixture.without_test_dependencies() } else { fixture }.within_root(root);
let fixture = assert_ok!(fixture, "File cycle fixture must support the requested root: {root:?}");
let system_under_test = analyze_files(&fixture);
let system_under_test = assert_ok!(system_under_test, "Filtered file graph must support cycle analysis");
let expected = vec![first_file.clone(), second_file, first_file];
let cycles = system_under_test.cycles(NonZeroUsize::MIN);
let cycles = assert_ok!(cycles, "Filtered file graph must have at most one cycle");
assert_eq!(expected_cycles, system_under_test.group_count(), "File cycle components ignored root or test filtering");
assert_eq!(expected_cycles, cycles.len(), "File cycle count differs");
if expected_cycles != 0 {
assert!(cycles.first().is_some_and(|cycle| cycle.nodes() == &expected), "File cycle route differs");
assert!(
fixture.edges().iter().all(|edge| system_under_test.edge_group(edge).is_some()),
"File cycle edge was not grouped"
);
}
}
#[rstest]
#[case("alpha", "unknown")]
#[case("unknown", "alpha")]
fn test_dependency_endpoint_membership(#[case] source: &str, #[case] target: &str) {
let nodes = BTreeSet::from([FolderNode::new("alpha".into())]);
let edge = FolderEdge::new(FolderNode::new(source.into()), FolderNode::new(target.into()), Production);
let system_under_test = || CycleAnalysis::new(&nodes, iter::once(&edge));
let result = catch_unwind(system_under_test);
assert!(result.is_err(), "Missing validated endpoints must be invariant violations, not user errors");
}
#[rstest]
#[case(
&[("alpha", "beta", Production), ("beta", "gamma", Production)],
)]
#[case(
&[
("alpha", "beta", Production), ("beta", "alpha", Production),
("beta", "gamma", Production), ("gamma", "alpha", Production),
],
)]
#[case(
&[("alpha", "beta", Test), ("beta", "alpha", Production), ("beta", "gamma", Production)],
)]
#[case(
&[("alpha", "beta", Production), ("beta", "alpha", Production)],
)]
fn test_folder_analysis_dependencies(#[case] dependencies: &[(&str, &str, DependencyKind)]) {
let fixture_dependencies = [("alpha", "beta", Production), ("beta", "alpha", Production), ("beta", "gamma", Production)];
let fixture = folder_fixture(&fixture_dependencies);
let fixture = assert_ok!(fixture, "Original analysis dependencies must form a valid graph");
let system_under_test = analyze_folders(&fixture);
let system_under_test = assert_ok!(system_under_test, "Original topology must support cycle analysis");
let changed_graph = FolderGraph::new(fixture.nodes().clone(), folder_dependencies(dependencies));
let changed_graph = assert_ok!(changed_graph, "Changed dependencies must still form a valid graph");
let result = validate_folder_analysis(&system_under_test, &changed_graph);
assert!(result.is_err(), "Changed dependency topology or kind accepted an outdated cycle analysis");
}
#[rstest]
#[case(&["alpha", "beta"], false)]
#[case(&["alpha", "beta", "isolated", "other"], false)]
#[case(&["isolated", "beta", "alpha"], true)]
fn test_folder_analysis_nodes(#[case] labels: &[&str], #[case] matches_analysis: bool) {
let dependencies = [("alpha", "beta", Production), ("beta", "alpha", Production)];
let fixture = FolderGraph::new(
folder_path(&["alpha", "beta", "isolated"]).into_iter().collect(),
folder_dependencies(&dependencies),
);
let fixture = assert_ok!(fixture, "Cycle and isolated nodes must form a valid graph");
let system_under_test = analyze_folders(&fixture);
let system_under_test = assert_ok!(system_under_test, "Original node set must support cycle analysis");
let changed_graph = FolderGraph::new(folder_path(labels).into_iter().collect(), folder_dependencies(&dependencies));
let changed_graph = assert_ok!(changed_graph, "Changed node set must retain every dependency endpoint");
let result = validate_folder_analysis(&system_under_test, &changed_graph);
if matches_analysis {
assert_ok!(result, "Reordered folder nodes must preserve the cycle analysis topology");
} else {
assert!(result.is_err(), "Changed folder node set accepted an outdated cycle analysis");
}
}
#[rstest]
#[case(1)]
#[case(27)]
fn test_folder_analysis_dependency_counts(#[case] count: usize) {
let dependencies = [("alpha", "beta", Production), ("beta", "alpha", Production)];
let fixture = folder_fixture(&dependencies);
let fixture = assert_ok!(fixture, "Dependency-count fixture must form a valid graph");
let system_under_test = analyze_folders(&fixture);
let system_under_test = assert_ok!(system_under_test, "Dependency-count fixture must support cycle analysis");
let mut edges = folder_dependencies(&dependencies);
for weight in edges.values_mut() {
*weight = DependencyCount::new(count);
}
let changed_graph = FolderGraph::new(fixture.nodes().clone(), edges);
let changed_graph = assert_ok!(changed_graph, "Changed dependency counts must preserve graph validity");
let result = validate_folder_analysis(&system_under_test, &changed_graph);
assert_ok!(result, "Dependency counts must not invalidate an unchanged cycle topology");
}
}