rustinel_core/
graph.rs

1//! Dependency-graph queries over a parsed lockfile.
2//!
3//! The headline use is answering *"why is this crate in my tree?"* — the
4//! shortest path from a local/workspace crate down to a given dependency. That
5//! turns a bare finding ("openssl-sys is native FFI") into actionable triage
6//! ("you pull it in via reqwest → native-tls → openssl-sys").
7//!
8//! Pure and allocation-bounded: it walks crate *names* (the granularity Cargo
9//! records in `[[package]].dependencies`), multi-source BFS from every local
10//! crate, recording the first (shortest) path discovered to each name.
11
12use crate::lockfile::LockfileModel;
13use std::collections::{BTreeMap, BTreeSet, VecDeque};
14
15/// Map of crate name -> shortest dependency path (inclusive of both the root
16/// crate and the target), following forward dependency edges from any local
17/// (workspace) crate. Names only — version-agnostic, matching the lockfile's
18/// dependency granularity.
19pub fn dependency_paths(lock: &LockfileModel) -> BTreeMap<String, Vec<String>> {
20    // Adjacency: crate name -> set of direct dependency names (union over any
21    // duplicate versions of the same name).
22    let mut adj: BTreeMap<&str, BTreeSet<&str>> = BTreeMap::new();
23    for pkg in &lock.packages {
24        let entry = adj.entry(pkg.id.name.as_str()).or_default();
25        for dep in &pkg.dependencies {
26            entry.insert(dep.as_str());
27        }
28    }
29
30    let mut paths: BTreeMap<String, Vec<String>> = BTreeMap::new();
31    let mut queue: VecDeque<String> = VecDeque::new();
32
33    // Seed BFS from every local/workspace crate (the "products" being built).
34    for pkg in lock.packages.iter().filter(|p| p.id.is_local()) {
35        let name = pkg.id.name.clone();
36        if paths.contains_key(&name) {
37            continue;
38        }
39        paths.insert(name.clone(), vec![name.clone()]);
40        queue.push_back(name);
41    }
42
43    while let Some(current) = queue.pop_front() {
44        // Clone the current path before borrowing `adj` mutably-free.
45        let current_path = paths.get(&current).cloned().unwrap_or_default();
46        let Some(deps) = adj.get(current.as_str()) else {
47            continue;
48        };
49        // Deterministic order (BTreeSet is sorted) so paths are reproducible.
50        for dep in deps.iter() {
51            if paths.contains_key(*dep) {
52                continue; // first visit wins => shortest path
53            }
54            let mut next = current_path.clone();
55            next.push((*dep).to_string());
56            paths.insert((*dep).to_string(), next);
57            queue.push_back((*dep).to_string());
58        }
59    }
60
61    paths
62}
63
64/// Render a path as `a → b → c`.
65pub fn format_path(path: &[String]) -> String {
66    path.join(" \u{2192} ")
67}
68
69#[cfg(test)]
70mod tests {
71    use super::*;
72    use crate::lockfile::{Package, PackageId};
73    use std::path::PathBuf;
74
75    fn p(name: &str, deps: &[&str], local: bool) -> Package {
76        Package {
77            id: PackageId {
78                name: name.into(),
79                version: "1.0.0".into(),
80                source: if local {
81                    None
82                } else {
83                    Some("registry+https://github.com/rust-lang/crates.io-index".into())
84                },
85            },
86            checksum: None,
87            dependencies: deps.iter().map(|s| s.to_string()).collect(),
88        }
89    }
90
91    fn lock(packages: Vec<Package>) -> LockfileModel {
92        LockfileModel {
93            path: PathBuf::from("Cargo.lock"),
94            version: Some(3),
95            packages,
96        }
97    }
98
99    #[test]
100    fn finds_transitive_path() {
101        // demo -> reqwest -> native-tls -> openssl-sys
102        let model = lock(vec![
103            p("demo", &["reqwest"], true),
104            p("reqwest", &["native-tls"], false),
105            p("native-tls", &["openssl-sys"], false),
106            p("openssl-sys", &[], false),
107        ]);
108        let paths = dependency_paths(&model);
109        assert_eq!(
110            paths.get("openssl-sys").unwrap(),
111            &vec![
112                "demo".to_string(),
113                "reqwest".to_string(),
114                "native-tls".to_string(),
115                "openssl-sys".to_string()
116            ]
117        );
118        assert_eq!(
119            format_path(paths.get("openssl-sys").unwrap()),
120            "demo → reqwest → native-tls → openssl-sys"
121        );
122    }
123
124    #[test]
125    fn shortest_path_wins() {
126        // demo depends on both b (direct) and a->b; shortest is demo->b.
127        let model = lock(vec![
128            p("demo", &["a", "b"], true),
129            p("a", &["b"], false),
130            p("b", &[], false),
131        ]);
132        let paths = dependency_paths(&model);
133        assert_eq!(paths.get("b").unwrap().len(), 2); // demo -> b
134    }
135
136    #[test]
137    fn cycle_does_not_hang() {
138        let model = lock(vec![
139            p("demo", &["a"], true),
140            p("a", &["b"], false),
141            p("b", &["a"], false), // cycle a <-> b
142        ]);
143        let paths = dependency_paths(&model);
144        assert!(paths.contains_key("a"));
145        assert!(paths.contains_key("b"));
146    }
147}
rustinel_core/graph.rs

rustinel_core/
graph.rs
