cargo_coupling/design/
graph.rs

1//! Canonical, deterministic dependency paths shared by CLI and design reports.
2
3use crate::{Distance, ProjectMetrics};
4use serde::Serialize;
5use std::collections::{BTreeMap, BTreeSet, VecDeque};
6
7#[derive(Debug, Clone, Serialize, PartialEq, Eq)]
8pub struct ImpactPath {
9    pub module: String,
10    /// Change origin first, affected consumer last (opposite dependency arrows).
11    pub path: Vec<String>,
12}
13
14#[derive(Debug, Clone, Default, Serialize)]
15pub struct Reachability {
16    pub paths: Vec<ImpactPath>,
17    pub max_depth: Option<usize>,
18    pub truncated: bool,
19}
20
21#[derive(Debug, Clone, Default)]
22pub struct DependencyGraph {
23    pub nodes: BTreeSet<String>,
24    pub outgoing: BTreeMap<String, BTreeSet<String>>,
25    pub incoming: BTreeMap<String, BTreeSet<String>>,
26    pub unresolved: BTreeSet<String>,
27}
28
29impl DependencyGraph {
30    pub fn from_metrics(metrics: &ProjectMetrics) -> Self {
31        let names = Self {
32            nodes: metrics.modules.keys().cloned().collect(),
33            ..Self::default()
34        };
35        let mut graph = names.clone();
36        // Keep nodes that only exist as endpoints, as legacy callers can build
37        // coupling-only metrics. Fully qualified aliases map to a unique module.
38        for edge in &metrics.couplings {
39            if edge.distance == Distance::DifferentCrate {
40                continue;
41            }
42            let source = names
43                .resolve(&edge.source)
44                .unwrap_or_else(|| edge.source.clone());
45            let target = names
46                .resolve(&edge.target)
47                .unwrap_or_else(|| edge.target.clone());
48            if !metrics.modules.contains_key(&source) {
49                graph.unresolved.insert(source.clone());
50            }
51            if !metrics.modules.contains_key(&target) {
52                graph.unresolved.insert(target.clone());
53            }
54            graph.nodes.insert(source.clone());
55            graph.nodes.insert(target.clone());
56            if source != target {
57                graph
58                    .outgoing
59                    .entry(source.clone())
60                    .or_default()
61                    .insert(target.clone());
62                graph.incoming.entry(target).or_default().insert(source);
63            }
64        }
65        graph
66    }
67
68    pub fn resolve(&self, name: &str) -> Option<String> {
69        if self.nodes.contains(name) {
70            return Some(name.to_string());
71        }
72        if let Some(found) = self
73            .nodes
74            .iter()
75            .filter(|key| name.ends_with(&format!("::{key}")))
76            .max_by_key(|key| key.len())
77        {
78            return Some(found.clone());
79        }
80        let mut matches = self
81            .nodes
82            .iter()
83            .filter(|key| key.ends_with(&format!("::{name}")));
84        let found = matches.next()?;
85        matches.next().is_none().then(|| found.clone())
86    }
87
88    pub fn select(&self, selector: &str) -> Vec<String> {
89        let Ok(pattern) = glob::Pattern::new(selector) else {
90            return vec![];
91        };
92        self.nodes
93            .iter()
94            .filter(|node| pattern.matches(node))
95            .cloned()
96            .collect()
97    }
98
99    pub fn impact(&self, origin: &str, max_depth: Option<usize>) -> Reachability {
100        self.walk(origin, max_depth, &self.incoming)
101    }
102
103    pub fn dependencies(&self, origin: &str, max_depth: Option<usize>) -> Reachability {
104        self.walk(origin, max_depth, &self.outgoing)
105    }
106
107    fn walk(
108        &self,
109        origin: &str,
110        max_depth: Option<usize>,
111        edges: &BTreeMap<String, BTreeSet<String>>,
112    ) -> Reachability {
113        let mut result = Reachability {
114            max_depth,
115            ..Reachability::default()
116        };
117        let Some(origin) = self.resolve(origin) else {
118            return result;
119        };
120        let mut visited = BTreeSet::from([origin.clone()]);
121        let mut queue = VecDeque::from([vec![origin]]);
122        let mut frontier = BTreeSet::new();
123        while let Some(path) = queue.pop_front() {
124            let current = path.last().expect("nonempty BFS path");
125            if max_depth.is_some_and(|depth| path.len() > depth) {
126                frontier.insert(current.clone());
127                continue;
128            }
129            for next in edges.get(current).into_iter().flatten() {
130                if visited.insert(next.clone()) {
131                    let mut next_path = path.clone();
132                    next_path.push(next.clone());
133                    result.paths.push(ImpactPath {
134                        module: next.clone(),
135                        path: next_path.clone(),
136                    });
137                    queue.push_back(next_path);
138                }
139            }
140        }
141        result.truncated = frontier.iter().any(|node| {
142            edges
143                .get(node)
144                .into_iter()
145                .flatten()
146                .any(|next| !visited.contains(next))
147        });
148        result
149    }
150}
151
152#[cfg(test)]
153mod tests {
154    use super::*;
155    use crate::{CouplingMetrics, IntegrationStrength, ModuleMetrics, Volatility};
156
157    #[test]
158    fn qualified_names_choose_the_longest_boundary_and_short_names_remain_ambiguous() {
159        let graph = DependencyGraph {
160            nodes: [
161                "design".into(),
162                "web::design".into(),
163                "web::graph".into(),
164                "design::graph".into(),
165            ]
166            .into(),
167            ..Default::default()
168        };
169        assert_eq!(
170            graph.resolve("cargo-coupling::web::design"),
171            Some("web::design".into())
172        );
173        assert_eq!(graph.resolve("graph"), None);
174        assert_eq!(graph.resolve("design"), Some("design".into()));
175    }
176
177    #[test]
178    fn paths_cover_three_hops_and_stop_at_explicit_limit_without_cycle_loops() {
179        let mut metrics = ProjectMetrics::new();
180        for name in ["a", "b", "c", "d"] {
181            metrics.add_module(ModuleMetrics::new(format!("{name}.rs").into(), name.into()));
182        }
183        for (source, target) in [("b", "a"), ("c", "b"), ("d", "c"), ("a", "d")] {
184            metrics.add_coupling(CouplingMetrics::new(
185                source.into(),
186                target.into(),
187                IntegrationStrength::Functional,
188                Distance::DifferentModule,
189                Volatility::High,
190            ));
191        }
192        let graph = DependencyGraph::from_metrics(&metrics);
193        assert_eq!(
194            graph.impact("a", None).paths.last().unwrap().path,
195            ["a", "b", "c", "d"]
196        );
197        let bounded = graph.impact("a", Some(2));
198        assert_eq!(bounded.paths.len(), 2);
199        assert!(bounded.truncated);
200        assert!(!graph.impact("a", Some(3)).truncated);
201    }
202}
cargo_coupling/design/graph.rs

cargo_coupling/design/
graph.rs
