fleetreach_core/
depgraph.rs

1//! A name-level dependency graph + shortest introducer-chain BFS, shared by the
2//! toolchain-free feeders to populate `dependency_path` (the `pkg (via a → b)` provenance)
3//! without a toolchain.
4//!
5//! The graph is *name-level*: nodes are package names, edges are "directly requires". Each
6//! feeder builds one from its lockfile (npm `packages` map, composer `require`, uv/poetry
7//! `dependencies`), then asks [`DepGraph::chain_to`] for a representative shortest chain from
8//! the root project down to a vulnerable package. The chain shape — `[root, …, target]`,
9//! both ends included — matches the Rust native path so the report's middle-slice `via`
10//! rendering is identical across ecosystems. An empty result is the honest "unknown
11//! provenance" fallback (a flat lockfile with no edges), never a wrong chain.
12
13use std::collections::{BTreeMap, BTreeSet, VecDeque};
14
15/// A name-level dependency graph rooted at the scanned project.
16#[derive(Debug, Default, Clone)]
17pub struct DepGraph {
18    root: String,
19    edges: BTreeMap<String, BTreeSet<String>>,
20}
21
22impl DepGraph {
23    /// A graph rooted at the project named `root` (the first element of every chain).
24    pub fn new(root: impl Into<String>) -> Self {
25        DepGraph {
26            root: root.into(),
27            edges: BTreeMap::new(),
28        }
29    }
30
31    /// Record that `from` directly requires each name in `tos`.
32    pub fn add_edges<I, S>(&mut self, from: &str, tos: I)
33    where
34        I: IntoIterator<Item = S>,
35        S: Into<String>,
36    {
37        let set = self.edges.entry(from.to_string()).or_default();
38        for to in tos {
39            set.insert(to.into());
40        }
41    }
42
43    /// Whether the graph holds no edges (a flat lockfile with no resolvable tree).
44    pub fn is_empty(&self) -> bool {
45        self.edges.is_empty()
46    }
47
48    /// A shortest chain of names `[root, …, target]` by which `target` is pulled into the
49    /// project, via a multi-source-free BFS from the root. Empty when `target` is unreachable
50    /// or the graph carries no edges — the honest "unknown provenance" fallback.
51    pub fn chain_to(&self, target: &str) -> Vec<String> {
52        if self.edges.is_empty() || self.root == target {
53            return Vec::new();
54        }
55        let mut pred: BTreeMap<&str, &str> = BTreeMap::new();
56        let mut visited: BTreeSet<&str> = BTreeSet::new();
57        visited.insert(self.root.as_str());
58        let mut queue: VecDeque<&str> = VecDeque::from([self.root.as_str()]);
59        while let Some(node) = queue.pop_front() {
60            if node == target {
61                break;
62            }
63            if let Some(deps) = self.edges.get(node) {
64                for dep in deps {
65                    if visited.insert(dep.as_str()) {
66                        pred.insert(dep.as_str(), node);
67                        queue.push_back(dep.as_str());
68                    }
69                }
70            }
71        }
72        if !visited.contains(target) {
73            return Vec::new();
74        }
75        let mut path = vec![target.to_string()];
76        let mut cursor = target;
77        while let Some(&parent) = pred.get(cursor) {
78            path.push(parent.to_string());
79            cursor = parent;
80        }
81        path.reverse();
82        path
83    }
84}
85
86#[cfg(test)]
87mod tests {
88    use super::*;
89
90    #[test]
91    fn chain_includes_root_and_target() {
92        let mut g = DepGraph::new("app");
93        g.add_edges("app", ["express", "lodash"]);
94        g.add_edges("express", ["minimist"]);
95        assert_eq!(g.chain_to("minimist"), vec!["app", "express", "minimist"]);
96        assert_eq!(g.chain_to("lodash"), vec!["app", "lodash"]);
97        assert!(g.chain_to("absent").is_empty());
98    }
99
100    #[test]
101    fn empty_graph_yields_empty_chain() {
102        assert!(DepGraph::default().chain_to("anything").is_empty());
103        assert!(DepGraph::new("app").chain_to("x").is_empty());
104    }
105
106    #[test]
107    fn shortest_of_multiple_paths_wins() {
108        // app -> a -> target, and app -> b -> c -> target; BFS picks the 3-name chain.
109        let mut g = DepGraph::new("app");
110        g.add_edges("app", ["a", "b"]);
111        g.add_edges("a", ["target"]);
112        g.add_edges("b", ["c"]);
113        g.add_edges("c", ["target"]);
114        assert_eq!(g.chain_to("target"), vec!["app", "a", "target"]);
115    }
116}
fleetreach_core/depgraph.rs

fleetreach_core/
depgraph.rs
