drft/analyses/
impact_radius.rs

1use super::{Analysis, AnalysisContext};
2use std::collections::{HashSet, VecDeque};
3
4#[derive(Debug, Clone, serde::Serialize)]
5pub struct ImpactRadiusNode {
6    pub node: String,
7    /// Count of transitive dependents (nodes reachable via reverse edges).
8    pub radius: usize,
9    /// Count of direct dependents (reverse neighbors).
10    pub direct_dependents: usize,
11    /// Longest reverse path from this node to a dependent.
12    pub max_depth: usize,
13}
14
15#[derive(Debug, Clone, serde::Serialize)]
16pub struct ImpactRadiusResult {
17    pub nodes: Vec<ImpactRadiusNode>,
18}
19
20pub struct ImpactRadius;
21
22impl Analysis for ImpactRadius {
23    type Output = ImpactRadiusResult;
24
25    fn name(&self) -> &str {
26        "impact-radius"
27    }
28
29    fn run(&self, ctx: &AnalysisContext) -> ImpactRadiusResult {
30        let graph = ctx.graph;
31
32        let mut nodes: Vec<ImpactRadiusNode> = graph
33            .included_nodes()
34            .map(|(path, _)| {
35                let mut visited = HashSet::new();
36                let mut queue = VecDeque::new();
37                visited.insert(path.as_str());
38                queue.push_back((path.as_str(), 0usize));
39
40                let mut direct_dependents = 0usize;
41                let mut max_depth = 0usize;
42                let mut radius = 0usize;
43
44                while let Some((current, depth)) = queue.pop_front() {
45                    if let Some(edge_indices) = graph.reverse.get(current) {
46                        for &idx in edge_indices {
47                            let dependent = graph.edges[idx].source.as_str();
48                            if visited.insert(dependent) {
49                                let next_depth = depth + 1;
50                                radius += 1;
51                                if next_depth == 1 {
52                                    direct_dependents += 1;
53                                }
54                                if next_depth > max_depth {
55                                    max_depth = next_depth;
56                                }
57                                queue.push_back((dependent, next_depth));
58                            }
59                        }
60                    }
61                }
62
63                ImpactRadiusNode {
64                    node: path.clone(),
65                    radius,
66                    direct_dependents,
67                    max_depth,
68                }
69            })
70            .collect();
71
72        nodes.sort_by(|a, b| a.node.cmp(&b.node));
73
74        ImpactRadiusResult { nodes }
75    }
76}
77
78#[cfg(test)]
79mod tests {
80    use super::*;
81    use crate::analyses::AnalysisContext;
82    use crate::config::Config;
83    use crate::graph::test_helpers::{make_edge, make_node};
84    use crate::graph::{Edge, Graph, Node, NodeType};
85    use std::collections::HashMap;
86    use std::path::Path;
87
88    fn make_ctx<'a>(graph: &'a Graph, config: &'a Config) -> AnalysisContext<'a> {
89        AnalysisContext {
90            graph,
91            root: Path::new("."),
92            config,
93            lockfile: None,
94        }
95    }
96
97    #[test]
98    fn empty_graph() {
99        let graph = Graph::new();
100        let config = Config::defaults();
101        let result = ImpactRadius.run(&make_ctx(&graph, &config));
102        assert!(result.nodes.is_empty());
103    }
104
105    #[test]
106    fn single_node_no_edges() {
107        let mut graph = Graph::new();
108        graph.add_node(make_node("a.md"));
109
110        let config = Config::defaults();
111        let result = ImpactRadius.run(&make_ctx(&graph, &config));
112        assert_eq!(result.nodes.len(), 1);
113        assert_eq!(result.nodes[0].radius, 0);
114        assert_eq!(result.nodes[0].direct_dependents, 0);
115        assert_eq!(result.nodes[0].max_depth, 0);
116    }
117
118    #[test]
119    fn linear_chain() {
120        // a -> b -> c -> d
121        // d has radius 3 (a, b, c depend on it transitively)
122        // c has radius 2 (a, b)
123        // b has radius 1 (a)
124        // a has radius 0
125        let mut graph = Graph::new();
126        graph.add_node(make_node("a.md"));
127        graph.add_node(make_node("b.md"));
128        graph.add_node(make_node("c.md"));
129        graph.add_node(make_node("d.md"));
130        graph.add_edge(make_edge("a.md", "b.md"));
131        graph.add_edge(make_edge("b.md", "c.md"));
132        graph.add_edge(make_edge("c.md", "d.md"));
133
134        let config = Config::defaults();
135        let result = ImpactRadius.run(&make_ctx(&graph, &config));
136
137        let get = |name: &str| result.nodes.iter().find(|n| n.node == name).unwrap();
138
139        assert_eq!(get("d.md").radius, 3);
140        assert_eq!(get("d.md").direct_dependents, 1);
141        assert_eq!(get("d.md").max_depth, 3);
142
143        assert_eq!(get("c.md").radius, 2);
144        assert_eq!(get("c.md").direct_dependents, 1);
145        assert_eq!(get("c.md").max_depth, 2);
146
147        assert_eq!(get("b.md").radius, 1);
148        assert_eq!(get("b.md").direct_dependents, 1);
149        assert_eq!(get("b.md").max_depth, 1);
150
151        assert_eq!(get("a.md").radius, 0);
152        assert_eq!(get("a.md").direct_dependents, 0);
153        assert_eq!(get("a.md").max_depth, 0);
154    }
155
156    #[test]
157    fn diamond_graph() {
158        // a -> b, a -> c, b -> d, c -> d
159        // d has radius 3 (b, c, a)
160        // b has radius 1 (a), c has radius 1 (a)
161        let mut graph = Graph::new();
162        graph.add_node(make_node("a.md"));
163        graph.add_node(make_node("b.md"));
164        graph.add_node(make_node("c.md"));
165        graph.add_node(make_node("d.md"));
166        graph.add_edge(make_edge("a.md", "b.md"));
167        graph.add_edge(make_edge("a.md", "c.md"));
168        graph.add_edge(make_edge("b.md", "d.md"));
169        graph.add_edge(make_edge("c.md", "d.md"));
170
171        let config = Config::defaults();
172        let result = ImpactRadius.run(&make_ctx(&graph, &config));
173
174        let get = |name: &str| result.nodes.iter().find(|n| n.node == name).unwrap();
175
176        assert_eq!(get("d.md").radius, 3);
177        assert_eq!(get("d.md").direct_dependents, 2);
178        assert_eq!(get("d.md").max_depth, 2);
179
180        assert_eq!(get("b.md").radius, 1);
181        assert_eq!(get("b.md").direct_dependents, 1);
182
183        assert_eq!(get("a.md").radius, 0);
184    }
185
186    #[test]
187    fn cycle() {
188        // a -> b -> c -> a (cycle)
189        // Each node has radius 2 (can reach the other two via reverse edges)
190        let mut graph = Graph::new();
191        graph.add_node(make_node("a.md"));
192        graph.add_node(make_node("b.md"));
193        graph.add_node(make_node("c.md"));
194        graph.add_edge(make_edge("a.md", "b.md"));
195        graph.add_edge(make_edge("b.md", "c.md"));
196        graph.add_edge(make_edge("c.md", "a.md"));
197
198        let config = Config::defaults();
199        let result = ImpactRadius.run(&make_ctx(&graph, &config));
200
201        let get = |name: &str| result.nodes.iter().find(|n| n.node == name).unwrap();
202
203        assert_eq!(get("a.md").radius, 2);
204        assert_eq!(get("b.md").radius, 2);
205        assert_eq!(get("c.md").radius, 2);
206    }
207
208    #[test]
209    fn external_edges_dont_create_nodes() {
210        let mut graph = Graph::new();
211        graph.add_node(make_node("a.md"));
212        graph.add_node(Node {
213            path: "https://example.com".into(),
214            node_type: Some(NodeType::Uri),
215            included: false,
216            hash: None,
217            metadata: HashMap::new(),
218        });
219        graph.add_edge(Edge {
220            source: "a.md".into(),
221            target: "https://example.com".into(),
222            link: None,
223            parser: "markdown".into(),
224        });
225
226        let config = Config::defaults();
227        let result = ImpactRadius.run(&make_ctx(&graph, &config));
228        // Only included nodes appear in results — the URI is referenced, not included
229        assert_eq!(result.nodes.len(), 1);
230        assert_eq!(result.nodes[0].node, "a.md");
231        assert_eq!(result.nodes[0].radius, 0);
232    }
233}
drft/analyses/impact_radius.rs

drft/analyses/
impact_radius.rs
