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