1use crate::graph_builder::build_graph;
2use serde::{Deserialize, Serialize};
3use std::collections::VecDeque;
4
5#[derive(Debug, Clone, Serialize, Deserialize)]
6pub struct DeadCodeNode {
7 pub name: String,
8 pub reason: DeadCodeReason,
9 pub inbound_count: usize,
10 pub outbound_count: usize,
11}
12
13#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
14pub enum DeadCodeReason {
15 Unreachable,
16 NoOutboundCalls,
17 Isolated,
18 OrphanedLeaf,
19}
20
21impl std::fmt::Display for DeadCodeReason {
22 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
23 match self {
24 DeadCodeReason::Unreachable => write!(f, "unreachable"),
25 DeadCodeReason::NoOutboundCalls => write!(f, "no_outbound_calls"),
26 DeadCodeReason::Isolated => write!(f, "isolated"),
27 DeadCodeReason::OrphanedLeaf => write!(f, "orphaned_leaf"),
28 }
29 }
30}
31
32#[derive(Debug, Clone, Serialize, Deserialize)]
33pub struct DeadCodeResult {
34 pub dead_nodes: Vec<DeadCodeNode>,
35 pub total_nodes: usize,
36 pub total_edges: usize,
37 pub dead_count: usize,
38 pub dead_ratio: f64,
39 pub entry_points: Vec<String>,
40}
41
42pub fn detect_dead_code(edges: &[(String, String)], entry_points: &[String]) -> DeadCodeResult {
43 if edges.is_empty() {
44 return DeadCodeResult {
45 dead_nodes: Vec::new(),
46 total_nodes: 0,
47 total_edges: 0,
48 dead_count: 0,
49 dead_ratio: 0.0,
50 entry_points: entry_points.to_vec(),
51 };
52 }
53
54 let mut graph = build_graph(edges);
55 graph.ensure_nodes(entry_points);
56
57 let node_vec = &graph.node_vec;
58 let node_idx = &graph.node_idx;
59 let out_adj = &graph.out_adj;
60 let in_adj = &graph.in_adj;
61 let n = graph.node_count();
62
63 let mut reachable = vec![false; n];
64 let mut queue: VecDeque<usize> = VecDeque::new();
65 for name in entry_points {
66 if let Some(&idx) = node_idx.get(name)
67 && !reachable[idx]
68 {
69 reachable[idx] = true;
70 queue.push_back(idx);
71 }
72 }
73
74 while let Some(v) = queue.pop_front() {
75 for &w in &out_adj[v] {
76 if !reachable[w] {
77 reachable[w] = true;
78 queue.push_back(w);
79 }
80 }
81 }
82
83 let mut dead_nodes = Vec::new();
84 for (i, name) in node_vec.iter().enumerate() {
85 if reachable[i] {
86 continue;
87 }
88 let inbound = in_adj[i].len();
89 let outbound = out_adj[i].len();
90 let reason = if inbound == 0 && outbound == 0 {
91 DeadCodeReason::Isolated
92 } else if inbound == 0 {
93 DeadCodeReason::Unreachable
94 } else if outbound == 0 {
95 DeadCodeReason::OrphanedLeaf
96 } else {
97 DeadCodeReason::Unreachable
98 };
99 dead_nodes.push(DeadCodeNode {
100 name: name.clone(),
101 reason,
102 inbound_count: inbound,
103 outbound_count: outbound,
104 });
105 }
106
107 let dead_count = dead_nodes.len();
108 let total_nodes = n;
109 let dead_ratio = if total_nodes > 0 {
110 dead_count as f64 / total_nodes as f64
111 } else {
112 0.0
113 };
114
115 dead_nodes.sort_by(|a, b| {
116 a.reason
117 .to_string()
118 .cmp(&b.reason.to_string())
119 .then(a.name.cmp(&b.name))
120 });
121
122 DeadCodeResult {
123 dead_nodes,
124 total_nodes,
125 total_edges: edges.len(),
126 dead_count,
127 dead_ratio,
128 entry_points: entry_points.to_vec(),
129 }
130}
131
132#[cfg(test)]
133mod tests {
134 use super::*;
135
136 fn e(a: &str, b: &str) -> (String, String) {
137 (a.to_string(), b.to_string())
138 }
139
140 #[test]
141 fn empty_graph() {
142 let result = detect_dead_code(&[], &[]);
143 assert_eq!(result.dead_count, 0);
144 assert_eq!(result.total_nodes, 0);
145 }
146
147 #[test]
148 fn all_reachable_from_entry() {
149 let edges = vec![e("main", "helper"), e("helper", "util")];
150 let result = detect_dead_code(&edges, &["main".to_string()]);
151 assert_eq!(result.dead_count, 0);
152 }
153
154 #[test]
155 fn unreachable_node_detected() {
156 let edges = vec![e("main", "helper"), e("dead", "dead_helper")];
157 let result = detect_dead_code(&edges, &["main".to_string()]);
158 assert_eq!(result.dead_count, 2);
159 let names: Vec<&str> = result.dead_nodes.iter().map(|n| n.name.as_str()).collect();
160 assert!(names.contains(&"dead"));
161 assert!(names.contains(&"dead_helper"));
162 }
163
164 #[test]
165 fn isolated_node_detected() {
166 let edges = vec![e("a", "b")];
167 let result = detect_dead_code(&edges, &["a".to_string()]);
168 assert_eq!(result.dead_count, 0);
169 }
170
171 #[test]
172 fn isolated_with_no_edges() {
173 let edges: Vec<(String, String)> = vec![];
174 let result = detect_dead_code(&edges, &[]);
175 assert_eq!(result.dead_count, 0);
176 }
177
178 #[test]
179 fn multiple_entry_points() {
180 let edges = vec![e("main", "a"), e("init", "b"), e("a", "c"), e("dead", "d")];
181 let result = detect_dead_code(&edges, &["main".to_string(), "init".to_string()]);
182 assert_eq!(result.dead_count, 2);
183 }
184
185 #[test]
186 fn dead_ratio_computed() {
187 let edges = vec![e("main", "a"), e("dead", "b")];
188 let result = detect_dead_code(&edges, &["main".to_string()]);
189 assert!(result.dead_ratio > 0.0);
190 assert!(result.dead_ratio <= 1.0);
191 }
192
193 #[test]
194 fn no_entry_points_all_dead() {
195 let edges = vec![e("a", "b"), e("b", "c")];
196 let result = detect_dead_code(&edges, &[]);
197 assert_eq!(result.dead_count, 3);
198 }
199}