deprot_core/
graph.rs

1//! A pure dependency-graph model and the graph analytics deprot layers on top of scoring:
2//! **blast radius** (how many of your packages transitively depend on a given one) and
3//! **leverage** (which single risky package, if fixed, removes the most risk from the project).
4//!
5//! Like the rest of `deprot-core` this is zero-I/O and deterministic: a manifest/lockfile parser
6//! builds the [`DepGraph`], and these methods reason about it without touching the network.
7
8use crate::facts::Ecosystem;
9
10/// One resolved node in the dependency tree — a concrete package at a concrete version.
11#[derive(Debug, Clone, PartialEq, Eq)]
12pub struct DepNode {
13    /// Registry name of the package.
14    pub name: String,
15    /// The exact resolved version (from the lockfile).
16    pub version: String,
17    /// Ecosystem the package belongs to.
18    pub ecosystem: Ecosystem,
19    /// Whether this is a direct dependency of the project (vs. pulled in transitively).
20    pub direct: bool,
21}
22
23/// A resolved dependency graph. `edges[i]` holds the indices of the nodes that node `i` depends
24/// on (forward adjacency).
25#[derive(Debug, Clone, Default)]
26pub struct DepGraph {
27    nodes: Vec<DepNode>,
28    edges: Vec<Vec<usize>>,
29}
30
31impl DepGraph {
32    /// An empty graph.
33    pub fn new() -> Self {
34        DepGraph::default()
35    }
36
37    /// Add a node, returning its index.
38    pub fn add_node(&mut self, node: DepNode) -> usize {
39        let idx = self.nodes.len();
40        self.nodes.push(node);
41        self.edges.push(Vec::new());
42        idx
43    }
44
45    /// Record that `from` depends on `to`.
46    pub fn add_edge(&mut self, from: usize, to: usize) {
47        if from < self.edges.len() && to < self.nodes.len() && from != to {
48            let e = &mut self.edges[from];
49            if !e.contains(&to) {
50                e.push(to);
51            }
52        }
53    }
54
55    /// All nodes, in insertion order.
56    pub fn nodes(&self) -> &[DepNode] {
57        &self.nodes
58    }
59
60    /// All nodes, mutably — used by lockfile parsers that only learn a node's `direct` status after
61    /// the whole file is read (e.g. bundler lists direct gems in a trailing `DEPENDENCIES` section).
62    pub fn nodes_mut(&mut self) -> &mut [DepNode] {
63        &mut self.nodes
64    }
65
66    /// Number of nodes.
67    pub fn len(&self) -> usize {
68        self.nodes.len()
69    }
70
71    /// Whether the graph has no nodes.
72    pub fn is_empty(&self) -> bool {
73        self.nodes.is_empty()
74    }
75
76    /// Number of direct dependencies.
77    pub fn direct_count(&self) -> usize {
78        self.nodes.iter().filter(|n| n.direct).count()
79    }
80
81    /// Reverse adjacency: `rev[i]` = indices of nodes that directly depend on node `i`.
82    fn reverse(&self) -> Vec<Vec<usize>> {
83        let mut rev = vec![Vec::new(); self.nodes.len()];
84        for (from, tos) in self.edges.iter().enumerate() {
85            for &to in tos {
86                rev[to].push(from);
87            }
88        }
89        rev
90    }
91
92    /// Blast radius of every node: the count of *distinct* other nodes that transitively depend on
93    /// it. Computed for the whole graph in one pass (shared reverse adjacency).
94    pub fn blast_radii(&self) -> Vec<usize> {
95        let rev = self.reverse();
96        let n = self.nodes.len();
97        let mut out = vec![0usize; n];
98        for start in 0..n {
99            let mut seen = vec![false; n];
100            seen[start] = true;
101            let mut stack = vec![start];
102            let mut count = 0;
103            while let Some(u) = stack.pop() {
104                for &p in &rev[u] {
105                    if !seen[p] {
106                        seen[p] = true;
107                        count += 1;
108                        stack.push(p);
109                    }
110                }
111            }
112            out[start] = count;
113        }
114        out
115    }
116}
117
118#[cfg(test)]
119mod tests {
120    use super::*;
121
122    fn node(name: &str, direct: bool) -> DepNode {
123        DepNode {
124            name: name.into(),
125            version: "1.0.0".into(),
126            ecosystem: Ecosystem::Cargo,
127            direct,
128        }
129    }
130
131    #[test]
132    fn blast_radius_counts_transitive_dependents() {
133        // app -> lib -> leaf ; app -> leaf
134        let mut g = DepGraph::new();
135        let app = g.add_node(node("app", true));
136        let lib = g.add_node(node("lib", false));
137        let leaf = g.add_node(node("leaf", false));
138        g.add_edge(app, lib);
139        g.add_edge(lib, leaf);
140        g.add_edge(app, leaf);
141
142        let radii = g.blast_radii();
143        assert_eq!(radii[app], 0, "nothing depends on the app");
144        assert_eq!(radii[lib], 1, "only app depends on lib");
145        assert_eq!(radii[leaf], 2, "both app and lib depend on leaf");
146    }
147
148    #[test]
149    fn duplicate_and_self_edges_are_ignored() {
150        let mut g = DepGraph::new();
151        let a = g.add_node(node("a", true));
152        let b = g.add_node(node("b", false));
153        g.add_edge(a, b);
154        g.add_edge(a, b); // dup
155        g.add_edge(a, a); // self
156        assert_eq!(g.blast_radii()[b], 1);
157    }
158}
deprot_core/graph.rs

deprot_core/
graph.rs
