synwire_agent/call_graph/
graph.rs

1//! Call graph node and edge types with cycle detection.
2
3use std::collections::{HashMap, HashSet};
4
5/// A node in the call graph.
6#[non_exhaustive]
7pub struct CallNode {
8    /// Qualified symbol name.
9    pub name: String,
10    /// File containing this symbol.
11    pub file: String,
12    /// Line number.
13    pub line: u32,
14}
15
16/// A directed call graph built incrementally via LSP goto-definition requests.
17pub struct DynamicCallGraph {
18    edges: Vec<(String, String)>,
19}
20
21impl DynamicCallGraph {
22    /// Create an empty call graph.
23    pub const fn new() -> Self {
24        Self { edges: Vec::new() }
25    }
26
27    /// Add a caller -> callee edge.
28    #[allow(clippy::similar_names)]
29    pub fn add_edge(&mut self, caller: &str, callee: &str) {
30        self.edges.push((caller.to_owned(), callee.to_owned()));
31    }
32
33    /// Get callees of a given caller (direct calls).
34    pub fn callees(&self, caller: &str) -> Vec<&str> {
35        self.edges
36            .iter()
37            .filter(|(c, _)| c == caller)
38            .map(|(_, callee)| callee.as_str())
39            .collect()
40    }
41
42    /// Get callers of a given callee.
43    pub fn callers(&self, callee: &str) -> Vec<&str> {
44        self.edges
45            .iter()
46            .filter(|(_, t)| t == callee)
47            .map(|(caller, _)| caller.as_str())
48            .collect()
49    }
50
51    /// Detect cycles using depth-first search.
52    ///
53    /// Returns `true` if the graph contains at least one cycle.
54    pub fn has_cycle(&self) -> bool {
55        fn dfs<'a>(
56            node: &'a str,
57            adj: &HashMap<&'a str, Vec<&'a str>>,
58            visited: &mut HashSet<&'a str>,
59            in_stack: &mut HashSet<&'a str>,
60        ) -> bool {
61            if in_stack.contains(node) {
62                return true;
63            }
64            if visited.contains(node) {
65                return false;
66            }
67            let _ = visited.insert(node);
68            let _ = in_stack.insert(node);
69            if let Some(neighbors) = adj.get(node) {
70                for &neighbor in neighbors {
71                    if dfs(neighbor, adj, visited, in_stack) {
72                        return true;
73                    }
74                }
75            }
76            let _ = in_stack.remove(node);
77            false
78        }
79
80        let mut adj: HashMap<&str, Vec<&str>> = HashMap::new();
81        for (from, to) in &self.edges {
82            adj.entry(from.as_str()).or_default().push(to.as_str());
83        }
84
85        let mut visited: HashSet<&str> = HashSet::new();
86        let mut in_stack: HashSet<&str> = HashSet::new();
87
88        let all_nodes: Vec<&str> = adj.keys().copied().collect();
89        for node in all_nodes {
90            if dfs(node, &adj, &mut visited, &mut in_stack) {
91                return true;
92            }
93        }
94        false
95    }
96}
97
98impl Default for DynamicCallGraph {
99    fn default() -> Self {
100        Self::new()
101    }
102}
103
104#[cfg(test)]
105mod tests {
106    use super::*;
107
108    #[test]
109    fn cycle_detection_finds_cycle() {
110        let mut g = DynamicCallGraph::new();
111        g.add_edge("a", "b");
112        g.add_edge("b", "c");
113        g.add_edge("c", "a"); // cycle
114        assert!(g.has_cycle());
115    }
116
117    #[test]
118    fn cycle_detection_no_false_positive() {
119        let mut g = DynamicCallGraph::new();
120        g.add_edge("a", "b");
121        g.add_edge("b", "c");
122        assert!(!g.has_cycle());
123    }
124
125    #[test]
126    fn callees_and_callers() {
127        let mut g = DynamicCallGraph::new();
128        g.add_edge("main", "parse");
129        g.add_edge("main", "execute");
130        assert_eq!(g.callees("main").len(), 2);
131        assert_eq!(g.callers("parse"), vec!["main"]);
132    }
133}
synwire_agent/call_graph/graph.rs

synwire_agent/call_graph/
graph.rs
