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