aptu_coder_core/graph/
structural.rs

1// SPDX-FileCopyrightText: 2026 aptu-coder contributors
2// SPDX-License-Identifier: Apache-2.0
3//! Structural knowledge graph over petgraph DiGraph with BFS blast-radius traversal.
4
5use crate::analyze::FileAnalysisOutput;
6use petgraph::graph::{DiGraph, NodeIndex};
7use serde::{Deserialize, Serialize};
8use std::collections::HashMap;
9use std::collections::HashSet;
10
11#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
12pub enum SymbolKind {
13    Function,
14    Class,
15    Struct,
16    Enum,
17    Trait,
18    Impl,
19}
20
21#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
22pub enum Node {
23    File {
24        path: String,
25    },
26    Symbol {
27        name: String,
28        kind: SymbolKind,
29        file_path: String,
30    },
31    Module {
32        path: String,
33    },
34}
35
36#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
37pub enum Edge {
38    Contains,
39    Calls,
40    Imports,
41    Implements,
42    HasMethod,
43    Tests,
44}
45
46#[derive(Debug, Clone, Serialize, Deserialize)]
47pub struct StructuralGraph(pub DiGraph<Node, Edge>);
48
49impl StructuralGraph {
50    pub fn build_from_analysis(entries: &[FileAnalysisOutput]) -> Self {
51        let mut graph = DiGraph::new();
52        let mut seen: HashSet<(NodeIndex, NodeIndex)> = HashSet::new();
53        let mut symbol_index: HashMap<String, NodeIndex> = HashMap::new();
54
55        for entry in entries {
56            let fp = entry.formatted.lines().next().unwrap_or("");
57            let file = graph.add_node(Node::File {
58                path: fp.to_string(),
59            });
60
61            for f in &entry.semantic.functions {
62                let n = graph.add_node(Node::Symbol {
63                    name: f.name.clone(),
64                    kind: SymbolKind::Function,
65                    file_path: fp.to_string(),
66                });
67                if seen.insert((file, n)) {
68                    graph.add_edge(file, n, Edge::Contains);
69                }
70                symbol_index.entry(f.name.clone()).or_insert(n);
71            }
72            for c in &entry.semantic.classes {
73                let n = graph.add_node(Node::Symbol {
74                    name: c.name.clone(),
75                    kind: SymbolKind::Class,
76                    file_path: fp.to_string(),
77                });
78                if seen.insert((file, n)) {
79                    graph.add_edge(file, n, Edge::Contains);
80                }
81                symbol_index.entry(c.name.clone()).or_insert(n);
82            }
83            for im in &entry.semantic.imports {
84                if !im.module.is_empty() {
85                    let n = graph.add_node(Node::Module {
86                        path: im.module.clone(),
87                    });
88                    if seen.insert((file, n)) {
89                        graph.add_edge(file, n, Edge::Imports);
90                    }
91                }
92            }
93            for cl in &entry.semantic.calls {
94                // Name-only keying preserves the prior first-definition-wins semantics: the first node inserted for a given name wins.
95                let caller = symbol_index.get(&cl.caller).copied();
96                let callee = symbol_index.get(&cl.callee).copied();
97                if let (Some(c), Some(e)) = (caller, callee)
98                    && seen.insert((c, e))
99                {
100                    graph.add_edge(c, e, Edge::Calls);
101                }
102            }
103        }
104        StructuralGraph(graph)
105    }
106
107    pub fn bfs_blast_radius(&self, symbol: &str, depth: usize) -> Vec<NodeIndex> {
108        let Some(start) = self
109            .0
110            .node_indices()
111            .find(|&i| matches!(&self.0[i], Node::Symbol { name, .. } if name == symbol))
112        else {
113            return vec![];
114        };
115        let mut visited = HashSet::new();
116        let mut result = Vec::new();
117        let mut frontier = vec![start];
118        visited.insert(start);
119        for _ in 0..depth {
120            if frontier.is_empty() {
121                break;
122            }
123            let mut next = Vec::new();
124            for node in frontier {
125                for nb in self.0.neighbors(node) {
126                    if visited.insert(nb) {
127                        result.push(nb);
128                        next.push(nb);
129                    }
130                }
131            }
132            frontier = next;
133        }
134        result
135    }
136}
137
138#[cfg(test)]
139mod tests {
140    use super::*;
141    use crate::types::{CallInfo, ClassInfo, FunctionInfo, ImportInfo, SemanticAnalysis};
142
143    fn make_output(
144        path: &str,
145        funcs: Vec<&str>,
146        classes: Vec<&str>,
147        imports: Vec<&str>,
148        calls: Vec<(&str, &str)>,
149    ) -> FileAnalysisOutput {
150        FileAnalysisOutput::new(
151            format!("{}:1:1:1", path),
152            SemanticAnalysis {
153                functions: funcs
154                    .into_iter()
155                    .map(|n| FunctionInfo {
156                        name: n.to_string(),
157                        line: 1,
158                        end_line: 6,
159                        parameters: vec![],
160                        return_type: None,
161                    })
162                    .collect(),
163                classes: classes
164                    .into_iter()
165                    .map(|n| ClassInfo {
166                        name: n.to_string(),
167                        line: 1,
168                        end_line: 10,
169                        methods: vec![],
170                        fields: vec![],
171                        inherits: vec![],
172                    })
173                    .collect(),
174                imports: imports
175                    .into_iter()
176                    .map(|m| ImportInfo {
177                        module: m.to_string(),
178                        items: vec![],
179                        line: 1,
180                    })
181                    .collect(),
182                references: vec![],
183                call_frequency: Default::default(),
184                calls: calls
185                    .into_iter()
186                    .map(|(c, e)| CallInfo {
187                        caller: c.to_string(),
188                        callee: e.to_string(),
189                        line: 1,
190                        column: 0,
191                        arg_count: None,
192                    })
193                    .collect(),
194                impl_traits: vec![],
195                def_use_sites: vec![],
196            },
197            10,
198            None,
199        )
200    }
201
202    #[test]
203    fn test_build_happy_path() {
204        let e = make_output(
205            "src/main.rs",
206            vec!["main", "helper"],
207            vec!["Config"],
208            vec!["std::collections"],
209            vec![("main", "helper")],
210        );
211        let g = StructuralGraph::build_from_analysis(&[e]);
212        assert!(g.0.node_count() >= 4, "nodes={}", g.0.node_count());
213        assert!(g.0.edge_count() >= 5, "edges={}", g.0.edge_count());
214        assert!(g.0.edge_indices().any(|i| g.0[i] == Edge::Calls));
215    }
216
217    #[test]
218    fn test_build_empty_input() {
219        let e = make_output("src/e.rs", vec![], vec![], vec![], vec![]);
220        let g = StructuralGraph::build_from_analysis(&[e]);
221        assert_eq!(g.0.node_count(), 1);
222        assert_eq!(g.0.edge_count(), 0);
223    }
224
225    #[test]
226    /// Two files with the same call edge produce exactly 1 Calls edge because the
227    /// HashMap index resolves both callers to the same first-definition node, and
228    /// the `seen` HashSet deduplicates the edge.
229    fn test_build_dedup_edges() {
230        let e1 = make_output(
231            "src/a.rs",
232            vec!["main", "helper"],
233            vec![],
234            vec![],
235            vec![("main", "helper")],
236        );
237        let e2 = make_output(
238            "src/b.rs",
239            vec!["main", "helper"],
240            vec![],
241            vec![],
242            vec![("main", "helper")],
243        );
244        let g = StructuralGraph::build_from_analysis(&[e1, e2]);
245        let n =
246            g.0.edge_indices()
247                .filter(|i| g.0[*i] == Edge::Calls)
248                .count();
249        assert_eq!(
250            n, 1,
251            "expected 1 Calls edge (first-definition-wins), got {}",
252            n
253        );
254    }
255
256    #[test]
257    fn test_bfs_diamond() {
258        let mut g = DiGraph::new();
259        let mut sym = |n: &str| {
260            g.add_node(Node::Symbol {
261                name: n.into(),
262                kind: SymbolKind::Function,
263                file_path: "t.rs".into(),
264            })
265        };
266        let a = sym("A");
267        let b = sym("B");
268        let c = sym("C");
269        let d = sym("D");
270        g.add_edge(a, b, Edge::Calls);
271        g.add_edge(a, c, Edge::Calls);
272        g.add_edge(b, d, Edge::Calls);
273        g.add_edge(c, d, Edge::Calls);
274        let graph = StructuralGraph(g);
275        let r = graph.bfs_blast_radius("A", 2);
276        assert_eq!(r.len(), 3, "expected 3 nodes, got {:?}", r);
277    }
278
279    #[test]
280    fn test_bfs_symbol_not_found() {
281        let graph = StructuralGraph(DiGraph::new());
282        assert!(graph.bfs_blast_radius("x", 3).is_empty());
283    }
284}
aptu_coder_core/graph/structural.rs

aptu_coder_core/graph/
structural.rs
