tldr_cli/commands/remaining/
graph_utils.rs

1//! Graph utilities for cycle detection and traversal
2//!
3//! This module provides shared utilities for call graph traversal,
4//! implementing TIGER-02 mitigation for circular import protection.
5//!
6//! # TIGER-02 Mitigation
7//!
8//! Risk: Cycle detection in diff-impact call graph traversal
9//! Severity: Critical
10//! Mitigation: Implement visited set for call graph traversal.
11//!             Use HashSet<(PathBuf, String)> to track (file, function) pairs.
12//!             Abort with partial results if cycle detected.
13
14use std::collections::HashSet;
15use std::path::{Path, PathBuf};
16
17// =============================================================================
18// Constants
19// =============================================================================
20
21/// Maximum depth for graph traversal to prevent stack overflow
22pub const MAX_GRAPH_DEPTH: usize = 100;
23
24/// Maximum depth for import resolution
25pub const MAX_IMPORT_DEPTH: usize = 10;
26
27// =============================================================================
28// Cycle Detection
29// =============================================================================
30
31/// Type alias for the visited set
32pub type VisitedSet = HashSet<(PathBuf, String)>;
33
34/// Cycle detector for graph traversal operations
35///
36/// Tracks visited (file, function) pairs to detect cycles during
37/// call graph traversal, import resolution, or other graph operations.
38///
39/// # Example
40///
41/// ```rust,ignore
42/// use tldr_cli::commands::remaining::graph_utils::CycleDetector;
43/// use std::path::Path;
44///
45/// let mut detector = CycleDetector::new();
46///
47/// // First visit returns false (no cycle)
48/// assert!(!detector.visit(Path::new("a.py"), "func"));
49///
50/// // Visiting same location returns true (cycle detected)
51/// assert!(detector.visit(Path::new("a.py"), "func"));
52/// ```
53#[derive(Debug, Clone)]
54pub struct CycleDetector {
55    /// Set of visited (file, function) pairs
56    visited: VisitedSet,
57    /// Whether a cycle has been detected
58    cycle_detected: bool,
59    /// Current depth in traversal
60    depth: usize,
61}
62
63impl CycleDetector {
64    /// Create a new cycle detector
65    pub fn new() -> Self {
66        Self {
67            visited: HashSet::new(),
68            cycle_detected: false,
69            depth: 0,
70        }
71    }
72
73    /// Create a cycle detector with a specific capacity hint
74    pub fn with_capacity(capacity: usize) -> Self {
75        Self {
76            visited: HashSet::with_capacity(capacity),
77            cycle_detected: false,
78            depth: 0,
79        }
80    }
81
82    /// Visit a (file, function) pair.
83    ///
84    /// Returns `true` if this location was already visited (cycle detected).
85    /// Returns `false` if this is a new location.
86    pub fn visit(&mut self, file: &Path, func: &str) -> bool {
87        let key = (file.to_path_buf(), func.to_string());
88        if !self.visited.insert(key) {
89            self.cycle_detected = true;
90            true
91        } else {
92            false
93        }
94    }
95
96    /// Visit a file path only (for import resolution)
97    pub fn visit_file(&mut self, file: &Path) -> bool {
98        self.visit(file, "")
99    }
100
101    /// Check if a cycle has been detected during traversal
102    pub fn is_cycle_detected(&self) -> bool {
103        self.cycle_detected
104    }
105
106    /// Get the number of visited locations
107    pub fn visited_count(&self) -> usize {
108        self.visited.len()
109    }
110
111    /// Check if a specific location has been visited
112    pub fn was_visited(&self, file: &Path, func: &str) -> bool {
113        let key = (file.to_path_buf(), func.to_string());
114        self.visited.contains(&key)
115    }
116
117    /// Get all visited files (unique)
118    pub fn visited_files(&self) -> Vec<PathBuf> {
119        let mut files: Vec<PathBuf> = self.visited.iter().map(|(path, _)| path.clone()).collect();
120        files.sort();
121        files.dedup();
122        files
123    }
124
125    /// Reset the detector for reuse
126    pub fn reset(&mut self) {
127        self.visited.clear();
128        self.cycle_detected = false;
129        self.depth = 0;
130    }
131
132    /// Enter a new depth level. Returns false if max depth exceeded.
133    pub fn enter_depth(&mut self) -> bool {
134        if self.depth >= MAX_GRAPH_DEPTH {
135            return false;
136        }
137        self.depth += 1;
138        true
139    }
140
141    /// Exit a depth level
142    pub fn exit_depth(&mut self) {
143        self.depth = self.depth.saturating_sub(1);
144    }
145
146    /// Get current depth
147    pub fn current_depth(&self) -> usize {
148        self.depth
149    }
150}
151
152impl Default for CycleDetector {
153    fn default() -> Self {
154        Self::new()
155    }
156}
157
158// =============================================================================
159// Graph Traversal Helpers
160// =============================================================================
161
162/// Result of a graph traversal operation
163#[derive(Debug, Clone)]
164pub struct TraversalResult<T> {
165    /// The collected results
166    pub results: Vec<T>,
167    /// Whether the traversal was complete (no cycles or depth limit hit)
168    pub complete: bool,
169    /// Number of nodes visited
170    pub nodes_visited: usize,
171    /// Cycle detected during traversal
172    pub cycle_detected: bool,
173    /// Maximum depth reached
174    pub max_depth_reached: usize,
175}
176
177impl<T> TraversalResult<T> {
178    /// Create a new empty traversal result
179    pub fn new() -> Self {
180        Self {
181            results: Vec::new(),
182            complete: true,
183            nodes_visited: 0,
184            cycle_detected: false,
185            max_depth_reached: 0,
186        }
187    }
188
189    /// Mark traversal as incomplete due to cycle
190    pub fn mark_cycle(&mut self) {
191        self.cycle_detected = true;
192        self.complete = false;
193    }
194
195    /// Mark traversal as incomplete due to depth limit
196    pub fn mark_depth_limit(&mut self, depth: usize) {
197        self.complete = false;
198        if depth > self.max_depth_reached {
199            self.max_depth_reached = depth;
200        }
201    }
202
203    /// Add a result
204    pub fn add(&mut self, item: T) {
205        self.results.push(item);
206        self.nodes_visited += 1;
207    }
208}
209
210impl<T> Default for TraversalResult<T> {
211    fn default() -> Self {
212        Self::new()
213    }
214}
215
216// =============================================================================
217// Tests
218// =============================================================================
219
220#[cfg(test)]
221mod tests {
222    use super::*;
223
224    #[test]
225    fn test_cycle_detector_new() {
226        let detector = CycleDetector::new();
227        assert!(!detector.is_cycle_detected());
228        assert_eq!(detector.visited_count(), 0);
229    }
230
231    #[test]
232    fn test_cycle_detector_visit() {
233        let mut detector = CycleDetector::new();
234
235        // First visit should return false (not a cycle)
236        assert!(!detector.visit(Path::new("file.py"), "func"));
237        assert_eq!(detector.visited_count(), 1);
238
239        // Second visit to same location should return true (cycle)
240        assert!(detector.visit(Path::new("file.py"), "func"));
241        assert!(detector.is_cycle_detected());
242
243        // Different location should return false
244        assert!(!detector.visit(Path::new("other.py"), "func"));
245        assert_eq!(detector.visited_count(), 2);
246
247        // Same file, different function
248        assert!(!detector.visit(Path::new("file.py"), "other_func"));
249        assert_eq!(detector.visited_count(), 3);
250    }
251
252    #[test]
253    fn test_cycle_detector_was_visited() {
254        let mut detector = CycleDetector::new();
255
256        assert!(!detector.was_visited(Path::new("file.py"), "func"));
257
258        detector.visit(Path::new("file.py"), "func");
259
260        assert!(detector.was_visited(Path::new("file.py"), "func"));
261        assert!(!detector.was_visited(Path::new("file.py"), "other"));
262    }
263
264    #[test]
265    fn test_cycle_detector_reset() {
266        let mut detector = CycleDetector::new();
267
268        detector.visit(Path::new("file.py"), "func");
269        detector.visit(Path::new("file.py"), "func"); // causes cycle
270
271        assert!(detector.is_cycle_detected());
272        assert_eq!(detector.visited_count(), 1);
273
274        detector.reset();
275
276        assert!(!detector.is_cycle_detected());
277        assert_eq!(detector.visited_count(), 0);
278    }
279
280    #[test]
281    fn test_cycle_detector_depth() {
282        let mut detector = CycleDetector::new();
283
284        assert_eq!(detector.current_depth(), 0);
285
286        assert!(detector.enter_depth());
287        assert_eq!(detector.current_depth(), 1);
288
289        detector.exit_depth();
290        assert_eq!(detector.current_depth(), 0);
291
292        // Test depth limit
293        for _ in 0..MAX_GRAPH_DEPTH {
294            assert!(detector.enter_depth());
295        }
296        assert!(!detector.enter_depth()); // Should fail at max depth
297    }
298
299    #[test]
300    fn test_cycle_detector_visited_files() {
301        let mut detector = CycleDetector::new();
302
303        detector.visit(Path::new("a.py"), "func1");
304        detector.visit(Path::new("a.py"), "func2");
305        detector.visit(Path::new("b.py"), "func1");
306
307        let files = detector.visited_files();
308        assert_eq!(files.len(), 2);
309        assert!(files.contains(&PathBuf::from("a.py")));
310        assert!(files.contains(&PathBuf::from("b.py")));
311    }
312
313    #[test]
314    fn test_traversal_result() {
315        let mut result: TraversalResult<String> = TraversalResult::new();
316
317        assert!(result.complete);
318        assert_eq!(result.nodes_visited, 0);
319
320        result.add("node1".to_string());
321        assert_eq!(result.nodes_visited, 1);
322        assert_eq!(result.results.len(), 1);
323
324        result.mark_cycle();
325        assert!(!result.complete);
326        assert!(result.cycle_detected);
327    }
328}
tldr_cli/commands/remaining/graph_utils.rs

tldr_cli/commands/remaining/
graph_utils.rs
