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_internal_edge(edge) {
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.included_nodes().map(|(s, _)| s.as_str()).collect();
108        real_nodes.sort();
109
110        for node in real_nodes {
111            let super_id = node_to_super[node];
112            let depth = super_depth.get(&super_id).copied().unwrap_or(0);
113            let in_cycle = nontrivial_nodes.contains(node);
114            max_depth = max_depth.max(depth);
115            nodes.push(NodeDepth {
116                node: node.to_string(),
117                depth,
118                in_cycle,
119            });
120        }
121
122        // Sort by depth ascending, then path alphabetically
123        nodes.sort_by(|a, b| a.depth.cmp(&b.depth).then_with(|| a.node.cmp(&b.node)));
124
125        DepthResult { max_depth, nodes }
126    }
127}
128
129#[cfg(test)]
130mod tests {
131    use super::*;
132    use crate::analyses::AnalysisContext;
133    use crate::config::Config;
134    use crate::graph::Graph;
135    use crate::graph::test_helpers::{make_edge, make_node};
136    use std::path::Path;
137
138    fn make_ctx<'a>(graph: &'a Graph, config: &'a Config) -> AnalysisContext<'a> {
139        AnalysisContext {
140            graph,
141            root: Path::new("."),
142            config,
143            lockfile: None,
144        }
145    }
146
147    #[test]
148    fn linear_chain() {
149        let mut graph = Graph::new();
150        graph.add_node(make_node("a.md"));
151        graph.add_node(make_node("b.md"));
152        graph.add_node(make_node("c.md"));
153        graph.add_edge(make_edge("a.md", "b.md"));
154        graph.add_edge(make_edge("b.md", "c.md"));
155
156        let config = Config::defaults();
157        let result = Depth.run(&make_ctx(&graph, &config));
158        assert_eq!(result.max_depth, 2);
159
160        let a = result.nodes.iter().find(|n| n.node == "a.md").unwrap();
161        assert_eq!(a.depth, 0);
162        assert!(!a.in_cycle);
163
164        let c = result.nodes.iter().find(|n| n.node == "c.md").unwrap();
165        assert_eq!(c.depth, 2);
166    }
167
168    #[test]
169    fn diamond() {
170        let mut graph = Graph::new();
171        graph.add_node(make_node("a.md"));
172        graph.add_node(make_node("b.md"));
173        graph.add_node(make_node("c.md"));
174        graph.add_node(make_node("d.md"));
175        graph.add_edge(make_edge("a.md", "b.md"));
176        graph.add_edge(make_edge("a.md", "c.md"));
177        graph.add_edge(make_edge("b.md", "d.md"));
178        graph.add_edge(make_edge("c.md", "d.md"));
179
180        let config = Config::defaults();
181        let result = Depth.run(&make_ctx(&graph, &config));
182        let d = result.nodes.iter().find(|n| n.node == "d.md").unwrap();
183        assert_eq!(d.depth, 2);
184    }
185
186    #[test]
187    fn cycle_gets_depth_and_flag() {
188        let mut graph = Graph::new();
189        graph.add_node(make_node("a.md"));
190        graph.add_node(make_node("b.md"));
191        graph.add_node(make_node("c.md"));
192        graph.add_edge(make_edge("a.md", "b.md"));
193        graph.add_edge(make_edge("b.md", "c.md"));
194        graph.add_edge(make_edge("c.md", "b.md"));
195
196        let config = Config::defaults();
197        let result = Depth.run(&make_ctx(&graph, &config));
198
199        let a = result.nodes.iter().find(|n| n.node == "a.md").unwrap();
200        assert_eq!(a.depth, 0);
201        assert!(!a.in_cycle);
202
203        let b = result.nodes.iter().find(|n| n.node == "b.md").unwrap();
204        assert!(b.in_cycle);
205        assert_eq!(b.depth, 1);
206
207        let c = result.nodes.iter().find(|n| n.node == "c.md").unwrap();
208        assert!(c.in_cycle);
209        assert_eq!(c.depth, 1);
210    }
211
212    #[test]
213    fn entirely_cyclic() {
214        let mut graph = Graph::new();
215        graph.add_node(make_node("a.md"));
216        graph.add_node(make_node("b.md"));
217        graph.add_node(make_node("c.md"));
218        graph.add_edge(make_edge("a.md", "b.md"));
219        graph.add_edge(make_edge("b.md", "c.md"));
220        graph.add_edge(make_edge("c.md", "a.md"));
221
222        let config = Config::defaults();
223        let result = Depth.run(&make_ctx(&graph, &config));
224        for nd in &result.nodes {
225            assert_eq!(nd.depth, 0);
226            assert!(nd.in_cycle);
227        }
228    }
229
230    #[test]
231    fn empty_graph() {
232        let graph = Graph::new();
233        let config = Config::defaults();
234        let result = Depth.run(&make_ctx(&graph, &config));
235        assert_eq!(result.max_depth, 0);
236        assert!(result.nodes.is_empty());
237    }
238
239    #[test]
240    fn multiple_roots() {
241        let mut graph = Graph::new();
242        graph.add_node(make_node("a.md"));
243        graph.add_node(make_node("b.md"));
244        graph.add_node(make_node("c.md"));
245        graph.add_edge(make_edge("a.md", "c.md"));
246        graph.add_edge(make_edge("b.md", "c.md"));
247
248        let config = Config::defaults();
249        let result = Depth.run(&make_ctx(&graph, &config));
250        let a = result.nodes.iter().find(|n| n.node == "a.md").unwrap();
251        let b = result.nodes.iter().find(|n| n.node == "b.md").unwrap();
252        let c = result.nodes.iter().find(|n| n.node == "c.md").unwrap();
253        assert_eq!(a.depth, 0);
254        assert_eq!(b.depth, 0);
255        assert_eq!(c.depth, 1);
256    }
257}
drft/analyses/depth.rs

drft/analyses/
depth.rs
