drft/analyses/
depth.rs

1use super::{Analysis, AnalysisContext};
2use crate::analyses::scc::StronglyConnectedComponents;
3use std::collections::{HashMap, HashSet, VecDeque};
4
5#[derive(Debug, Clone, serde::Serialize)]
6pub struct NodeDepth {
7    pub node: String,
8    pub depth: usize,
9    pub in_cycle: bool,
10}
11
12#[derive(Debug, Clone, serde::Serialize)]
13pub struct DepthResult {
14    pub max_depth: usize,
15    pub nodes: Vec<NodeDepth>,
16}
17
18pub struct Depth;
19
20impl Analysis for Depth {
21    type Output = DepthResult;
22
23    fn name(&self) -> &str {
24        "depth"
25    }
26
27    fn run(&self, ctx: &AnalysisContext) -> DepthResult {
28        let graph = ctx.graph;
29        // Step 1: Run SCC analysis to identify cycles
30        let scc_result = StronglyConnectedComponents.run(ctx);
31
32        // Identify which nodes are in non-trivial SCCs
33        let nontrivial_nodes: HashSet<&str> = scc_result
34            .sccs
35            .iter()
36            .flat_map(|s| s.members.iter().map(|m| m.as_str()))
37            .collect();
38
39        // Step 2: Build condensation DAG
40        // Map each real node to its super-node ID (SCC ID)
41        // For non-trivial SCCs, all members map to the same super-node
42        let node_to_super: &HashMap<String, usize> = &scc_result.node_scc;
43
44        // Collect unique super-node IDs
45        let super_nodes: HashSet<usize> = node_to_super.values().copied().collect();
46
47        // Build forward adjacency for the condensation DAG
48        let mut condensed_forward: HashMap<usize, HashSet<usize>> = HashMap::new();
49        let mut condensed_reverse: HashMap<usize, HashSet<usize>> = HashMap::new();
50        for super_id in &super_nodes {
51            condensed_forward.entry(*super_id).or_default();
52            condensed_reverse.entry(*super_id).or_default();
53        }
54
55        for edge in &graph.edges {
56            if !graph.is_file_node(&edge.source) || !graph.is_file_node(&edge.target) {
57                continue;
58            }
59            let src_super = node_to_super[&edge.source];
60            let tgt_super = node_to_super[&edge.target];
61            if src_super != tgt_super {
62                condensed_forward
63                    .entry(src_super)
64                    .or_default()
65                    .insert(tgt_super);
66                condensed_reverse
67                    .entry(tgt_super)
68                    .or_default()
69                    .insert(src_super);
70            }
71        }
72
73        // Step 3: BFS from roots (super-nodes with no incoming edges in condensation)
74        let roots: Vec<usize> = super_nodes
75            .iter()
76            .filter(|id| condensed_reverse.get(id).is_some_and(|s| s.is_empty()))
77            .copied()
78            .collect();
79
80        let mut super_depth: HashMap<usize, usize> = HashMap::new();
81        let mut queue = VecDeque::new();
82
83        for root_id in &roots {
84            super_depth.insert(*root_id, 0);
85            queue.push_back(*root_id);
86        }
87
88        while let Some(current) = queue.pop_front() {
89            let current_depth = super_depth[&current];
90            if let Some(neighbors) = condensed_forward.get(&current) {
91                for &neighbor in neighbors {
92                    let new_depth = current_depth + 1;
93                    let entry = super_depth.entry(neighbor).or_insert(0);
94                    // Use max depth (longest path from any root)
95                    if new_depth > *entry {
96                        *entry = new_depth;
97                        queue.push_back(neighbor);
98                    }
99                }
100            }
101        }
102
103        // Step 4: Expand back to per-node depths
104        let mut nodes: Vec<NodeDepth> = Vec::new();
105        let mut max_depth: usize = 0;
106
107        let mut real_nodes: Vec<&str> = graph
108            .nodes
109            .keys()
110            .filter(|p| graph.is_file_node(p))
111            .map(|s| s.as_str())
112            .collect();
113        real_nodes.sort();
114
115        for node in real_nodes {
116            let super_id = node_to_super[node];
117            let depth = super_depth.get(&super_id).copied().unwrap_or(0);
118            let in_cycle = nontrivial_nodes.contains(node);
119            max_depth = max_depth.max(depth);
120            nodes.push(NodeDepth {
121                node: node.to_string(),
122                depth,
123                in_cycle,
124            });
125        }
126
127        // Sort by depth ascending, then path alphabetically
128        nodes.sort_by(|a, b| a.depth.cmp(&b.depth).then_with(|| a.node.cmp(&b.node)));
129
130        DepthResult { max_depth, nodes }
131    }
132}
133
134#[cfg(test)]
135mod tests {
136    use super::*;
137    use crate::analyses::AnalysisContext;
138    use crate::config::Config;
139    use crate::graph::Graph;
140    use crate::graph::test_helpers::{make_edge, make_node};
141    use std::path::Path;
142
143    fn make_ctx<'a>(graph: &'a Graph, config: &'a Config) -> AnalysisContext<'a> {
144        AnalysisContext {
145            graph,
146            root: Path::new("."),
147            config,
148            lockfile: None,
149        }
150    }
151
152    #[test]
153    fn linear_chain() {
154        let mut graph = Graph::new();
155        graph.add_node(make_node("a.md"));
156        graph.add_node(make_node("b.md"));
157        graph.add_node(make_node("c.md"));
158        graph.add_edge(make_edge("a.md", "b.md"));
159        graph.add_edge(make_edge("b.md", "c.md"));
160
161        let config = Config::defaults();
162        let result = Depth.run(&make_ctx(&graph, &config));
163        assert_eq!(result.max_depth, 2);
164
165        let a = result.nodes.iter().find(|n| n.node == "a.md").unwrap();
166        assert_eq!(a.depth, 0);
167        assert!(!a.in_cycle);
168
169        let c = result.nodes.iter().find(|n| n.node == "c.md").unwrap();
170        assert_eq!(c.depth, 2);
171    }
172
173    #[test]
174    fn diamond() {
175        let mut graph = Graph::new();
176        graph.add_node(make_node("a.md"));
177        graph.add_node(make_node("b.md"));
178        graph.add_node(make_node("c.md"));
179        graph.add_node(make_node("d.md"));
180        graph.add_edge(make_edge("a.md", "b.md"));
181        graph.add_edge(make_edge("a.md", "c.md"));
182        graph.add_edge(make_edge("b.md", "d.md"));
183        graph.add_edge(make_edge("c.md", "d.md"));
184
185        let config = Config::defaults();
186        let result = Depth.run(&make_ctx(&graph, &config));
187        let d = result.nodes.iter().find(|n| n.node == "d.md").unwrap();
188        assert_eq!(d.depth, 2);
189    }
190
191    #[test]
192    fn cycle_gets_depth_and_flag() {
193        let mut graph = Graph::new();
194        graph.add_node(make_node("a.md"));
195        graph.add_node(make_node("b.md"));
196        graph.add_node(make_node("c.md"));
197        graph.add_edge(make_edge("a.md", "b.md"));
198        graph.add_edge(make_edge("b.md", "c.md"));
199        graph.add_edge(make_edge("c.md", "b.md"));
200
201        let config = Config::defaults();
202        let result = Depth.run(&make_ctx(&graph, &config));
203
204        let a = result.nodes.iter().find(|n| n.node == "a.md").unwrap();
205        assert_eq!(a.depth, 0);
206        assert!(!a.in_cycle);
207
208        let b = result.nodes.iter().find(|n| n.node == "b.md").unwrap();
209        assert!(b.in_cycle);
210        assert_eq!(b.depth, 1);
211
212        let c = result.nodes.iter().find(|n| n.node == "c.md").unwrap();
213        assert!(c.in_cycle);
214        assert_eq!(c.depth, 1);
215    }
216
217    #[test]
218    fn entirely_cyclic() {
219        let mut graph = Graph::new();
220        graph.add_node(make_node("a.md"));
221        graph.add_node(make_node("b.md"));
222        graph.add_node(make_node("c.md"));
223        graph.add_edge(make_edge("a.md", "b.md"));
224        graph.add_edge(make_edge("b.md", "c.md"));
225        graph.add_edge(make_edge("c.md", "a.md"));
226
227        let config = Config::defaults();
228        let result = Depth.run(&make_ctx(&graph, &config));
229        for nd in &result.nodes {
230            assert_eq!(nd.depth, 0);
231            assert!(nd.in_cycle);
232        }
233    }
234
235    #[test]
236    fn empty_graph() {
237        let graph = Graph::new();
238        let config = Config::defaults();
239        let result = Depth.run(&make_ctx(&graph, &config));
240        assert_eq!(result.max_depth, 0);
241        assert!(result.nodes.is_empty());
242    }
243
244    #[test]
245    fn multiple_roots() {
246        let mut graph = Graph::new();
247        graph.add_node(make_node("a.md"));
248        graph.add_node(make_node("b.md"));
249        graph.add_node(make_node("c.md"));
250        graph.add_edge(make_edge("a.md", "c.md"));
251        graph.add_edge(make_edge("b.md", "c.md"));
252
253        let config = Config::defaults();
254        let result = Depth.run(&make_ctx(&graph, &config));
255        let a = result.nodes.iter().find(|n| n.node == "a.md").unwrap();
256        let b = result.nodes.iter().find(|n| n.node == "b.md").unwrap();
257        let c = result.nodes.iter().find(|n| n.node == "c.md").unwrap();
258        assert_eq!(a.depth, 0);
259        assert_eq!(b.depth, 0);
260        assert_eq!(c.depth, 1);
261    }
262}
drft/analyses/depth.rs

drft/analyses/
depth.rs
