changeset_project/
dependency_graph.rs

1use std::collections::{HashMap, HashSet, VecDeque};
2
3use crate::error::ProjectError;
4use crate::manifest::{DependencyEntry, read_manifest};
5use crate::project::CargoProject;
6
7pub struct WorkspaceDependencyGraph {
8    depended_on_by: HashMap<String, HashSet<String>>,
9    depends_on: HashMap<String, HashSet<String>>,
10}
11
12impl WorkspaceDependencyGraph {
13    /// Builds the dependency graph from the workspace, considering only `[dependencies]` and
14    /// `[build-dependencies]`.
15    ///
16    /// # Errors
17    ///
18    /// Returns `ProjectError` if any member's manifest cannot be read or parsed.
19    pub fn build(project: &CargoProject) -> Result<Self, ProjectError> {
20        let member_names: HashSet<String> = project
21            .packages()
22            .iter()
23            .map(|p| p.name().clone())
24            .collect();
25
26        let mut depended_on_by: HashMap<String, HashSet<String>> = member_names
27            .iter()
28            .map(|name| (name.clone(), HashSet::<String>::new()))
29            .collect();
30
31        let mut depends_on: HashMap<String, HashSet<String>> = member_names
32            .iter()
33            .map(|name| (name.clone(), HashSet::<String>::new()))
34            .collect();
35
36        for package in project.packages() {
37            let manifest_path = package.path().join("Cargo.toml");
38            let manifest = read_manifest(&manifest_path)?;
39
40            let dep_sections = [manifest.dependencies, manifest.build_dependencies];
41
42            for section in dep_sections.into_iter().flatten() {
43                for (key, entry) in &section {
44                    let resolved_name = resolve_package_name(key, entry);
45
46                    if member_names.contains(resolved_name) {
47                        if let Some(set) = depends_on.get_mut(package.name()) {
48                            set.insert(resolved_name.to_string());
49                        }
50                        if let Some(set) = depended_on_by.get_mut(resolved_name) {
51                            set.insert(package.name().clone());
52                        }
53                    }
54                }
55            }
56        }
57
58        Ok(Self {
59            depended_on_by,
60            depends_on,
61        })
62    }
63
64    #[cfg(any(test, feature = "testing"))]
65    #[must_use]
66    pub fn from_edges(member_names: HashSet<String>, edges: &[(String, String)]) -> Self {
67        let mut depended_on_by: HashMap<String, HashSet<String>> = member_names
68            .iter()
69            .map(|name| (name.clone(), HashSet::new()))
70            .collect();
71
72        let mut depends_on: HashMap<String, HashSet<String>> = member_names
73            .iter()
74            .map(|name| (name.clone(), HashSet::new()))
75            .collect();
76
77        for (dependent, dependency) in edges {
78            if member_names.contains(dependent) && member_names.contains(dependency) {
79                depends_on
80                    .entry(dependent.clone())
81                    .or_default()
82                    .insert(dependency.clone());
83
84                depended_on_by
85                    .entry(dependency.clone())
86                    .or_default()
87                    .insert(dependent.clone());
88            }
89        }
90
91        Self {
92            depended_on_by,
93            depends_on,
94        }
95    }
96
97    #[must_use]
98    pub fn transitive_dependents(&self, package: &str) -> HashSet<&str> {
99        let mut visited = HashSet::new();
100        let mut queue = VecDeque::new();
101
102        if let Some(direct) = self.depended_on_by.get(package) {
103            for dep in direct {
104                if dep != package && visited.insert(dep.as_str()) {
105                    queue.push_back(dep.as_str());
106                }
107            }
108        }
109
110        while let Some(current) = queue.pop_front() {
111            if let Some(dependents) = self.depended_on_by.get(current) {
112                for dep in dependents {
113                    if dep != package && visited.insert(dep.as_str()) {
114                        queue.push_back(dep.as_str());
115                    }
116                }
117            }
118        }
119
120        visited
121    }
122
123    #[must_use]
124    pub fn transitive_dependents_of_set<'a>(&'a self, packages: &[&str]) -> HashSet<&'a str> {
125        let input_set: HashSet<&str> = packages.iter().copied().collect();
126
127        let mut result = HashSet::new();
128        for &pkg in packages {
129            for dep in self.transitive_dependents(pkg) {
130                if !input_set.contains(dep) {
131                    result.insert(dep);
132                }
133            }
134        }
135
136        result
137    }
138
139    #[must_use]
140    pub fn direct_dependencies(&self, package: &str) -> HashSet<&str> {
141        self.depends_on
142            .get(package)
143            .map(|deps| deps.iter().map(String::as_str).collect())
144            .unwrap_or_default()
145    }
146}
147
148fn resolve_package_name<'a>(key: &'a str, entry: &'a DependencyEntry) -> &'a str {
149    match entry {
150        DependencyEntry::Table(table) => table.package.as_deref().unwrap_or(key),
151        DependencyEntry::Simple(_) => key,
152    }
153}
154
155#[cfg(test)]
156mod tests {
157    use super::*;
158
159    fn member_set(names: &[&str]) -> HashSet<String> {
160        names.iter().map(|&n| n.to_string()).collect()
161    }
162
163    fn edges(pairs: &[(&str, &str)]) -> Vec<(String, String)> {
164        pairs
165            .iter()
166            .map(|&(a, b)| (a.to_string(), b.to_string()))
167            .collect()
168    }
169
170    #[test]
171    fn empty_graph_has_no_dependents() {
172        let graph = WorkspaceDependencyGraph::from_edges(member_set(&["a", "b"]), &[]);
173
174        assert!(graph.transitive_dependents("a").is_empty());
175        assert!(graph.transitive_dependents("b").is_empty());
176    }
177
178    #[test]
179    fn single_package_no_edges() {
180        let graph = WorkspaceDependencyGraph::from_edges(member_set(&["solo"]), &[]);
181
182        assert!(graph.transitive_dependents("solo").is_empty());
183        assert!(graph.direct_dependencies("solo").is_empty());
184    }
185
186    #[test]
187    fn direct_dependency_detection() {
188        let graph = WorkspaceDependencyGraph::from_edges(
189            member_set(&["app", "lib"]),
190            &edges(&[("app", "lib")]),
191        );
192
193        let deps = graph.direct_dependencies("app");
194        assert_eq!(deps, HashSet::from(["lib"]));
195        assert!(graph.direct_dependencies("lib").is_empty());
196    }
197
198    #[test]
199    fn transitive_dependents_chain() {
200        let graph = WorkspaceDependencyGraph::from_edges(
201            member_set(&["a", "b", "c"]),
202            &edges(&[("b", "a"), ("c", "b")]),
203        );
204
205        let dependents = graph.transitive_dependents("a");
206        assert!(dependents.contains("b"));
207        assert!(dependents.contains("c"));
208        assert_eq!(dependents.len(), 2);
209    }
210
211    #[test]
212    fn transitive_dependents_diamond() {
213        let graph = WorkspaceDependencyGraph::from_edges(
214            member_set(&["core", "left", "right", "top"]),
215            &edges(&[
216                ("left", "core"),
217                ("right", "core"),
218                ("top", "left"),
219                ("top", "right"),
220            ]),
221        );
222
223        let dependents = graph.transitive_dependents("core");
224        assert!(dependents.contains("left"));
225        assert!(dependents.contains("right"));
226        assert!(dependents.contains("top"));
227        assert_eq!(dependents.len(), 3);
228    }
229
230    #[test]
231    fn transitive_dependents_of_set_excludes_input() {
232        let graph = WorkspaceDependencyGraph::from_edges(
233            member_set(&["a", "b", "c", "d"]),
234            &edges(&[("b", "a"), ("c", "b"), ("d", "c")]),
235        );
236
237        let result = graph.transitive_dependents_of_set(&["a", "b"]);
238        assert!(result.contains("c"));
239        assert!(result.contains("d"));
240        assert!(!result.contains("a"));
241        assert!(!result.contains("b"));
242    }
243
244    #[test]
245    fn transitive_dependents_of_set_deduplicates_shared_dependent() {
246        let graph = WorkspaceDependencyGraph::from_edges(
247            member_set(&["a", "b", "shared"]),
248            &edges(&[("shared", "a"), ("shared", "b")]),
249        );
250
251        let result = graph.transitive_dependents_of_set(&["a", "b"]);
252        assert_eq!(result.len(), 1);
253        assert!(result.contains("shared"));
254    }
255
256    #[test]
257    fn cycle_handling_terminates() {
258        let graph = WorkspaceDependencyGraph::from_edges(
259            member_set(&["a", "b"]),
260            &edges(&[("a", "b"), ("b", "a")]),
261        );
262
263        let dependents_a = graph.transitive_dependents("a");
264        assert!(dependents_a.contains("b"));
265        assert!(!dependents_a.contains("a"));
266
267        let dependents_b = graph.transitive_dependents("b");
268        assert!(dependents_b.contains("a"));
269        assert!(!dependents_b.contains("b"));
270    }
271
272    #[test]
273    fn cycle_three_nodes() {
274        let graph = WorkspaceDependencyGraph::from_edges(
275            member_set(&["a", "b", "c"]),
276            &edges(&[("a", "b"), ("b", "c"), ("c", "a")]),
277        );
278
279        let dependents = graph.transitive_dependents("a");
280        assert!(dependents.contains("b"));
281        assert!(dependents.contains("c"));
282    }
283
284    #[test]
285    fn unknown_package_returns_empty() {
286        let graph = WorkspaceDependencyGraph::from_edges(member_set(&["a"]), &[]);
287
288        assert!(graph.transitive_dependents("nonexistent").is_empty());
289        assert!(graph.direct_dependencies("nonexistent").is_empty());
290    }
291
292    #[test]
293    fn from_edges_ignores_non_member_edges() {
294        let graph = WorkspaceDependencyGraph::from_edges(
295            member_set(&["a", "b"]),
296            &edges(&[("a", "external"), ("external", "b")]),
297        );
298
299        assert!(graph.direct_dependencies("a").is_empty());
300        assert!(graph.transitive_dependents("b").is_empty());
301    }
302
303    #[test]
304    fn resolve_package_name_simple_entry() {
305        let entry = DependencyEntry::Simple(serde::de::IgnoredAny);
306        assert_eq!(resolve_package_name("my-dep", &entry), "my-dep");
307    }
308
309    #[test]
310    fn resolve_package_name_table_without_rename() {
311        let entry = DependencyEntry::Table(crate::manifest::DependencyTable { package: None });
312        assert_eq!(resolve_package_name("my-dep", &entry), "my-dep");
313    }
314
315    #[test]
316    fn resolve_package_name_table_with_rename() {
317        let entry = DependencyEntry::Table(crate::manifest::DependencyTable {
318            package: Some("actual-name".to_string()),
319        });
320        assert_eq!(resolve_package_name("alias", &entry), "actual-name");
321    }
322}
changeset_project/dependency_graph.rs

changeset_project/
dependency_graph.rs
