meta_ast/graph/
mod.rs

1//! Dependency graph module for cross-file and symbol-level analysis.
2//!
3//! This module provides graph data structures and algorithms for analyzing
4//! dependencies between source files and their contained symbols. It supports:
5//!
6//! - Building a directed graph from extracted symbols
7//! - Computing strongly connected components (SCCs)
8//! - Providing deployability hints based on cycle detection
9//!
10//! # Design as stated in RFC 0008
11//!
12//! The graph layer sits between the extraction layer and the output layer:
13//! - `node.rs` defines `FileNode` and `SymbolNode` types
14//! - `edge.rs` defines `EdgeKind` (Ownership, Import, Reference)
15//! - `builder.rs` provides `GraphBuilder` for incremental construction
16//! - `scc.rs` provides SCC analysis via Tarjan's algorithm
17//!
18//! # Example
19//!
20//! ```
21//! use meta_ast::graph::{GraphBuilder, SccAnalysis, CodeGraph};
22//! use meta_ast::model::SnapshotId;
23//!
24//! // Create builder and add files/symbols
25//! let mut builder = GraphBuilder::new(SnapshotId::new(1).unwrap());
26//! // ... add nodes and edges ...
27//! let graph = builder.build();
28//!
29//! // Run SCC analysis
30//! let scc = SccAnalysis::analyze(&graph.graph);
31//! ```
32
33pub mod builder;
34pub mod edge;
35pub mod node;
36pub mod resolver;
37pub mod scc;
38
39use std::collections::HashMap;
40
41pub use builder::GraphBuilder;
42pub use edge::{EdgeData, EdgeKind};
43pub use node::{
44    DataGraphNode, ExternalClassification, ExternalNode, FileNode, NodeData, SymbolNode,
45};
46pub use scc::{DeployabilityHint, Scc, SccAnalysis};
47
48use crate::language::LangId;
49use crate::model::{FileId, SnapshotId, SymbolId};
50use petgraph::graph::{DiGraph, NodeIndex};
51
52/// The canonical dependency graph for a codebase snapshot.
53#[derive(Debug, Clone)]
54pub struct CodeGraph {
55    /// The underlying petgraph with our node/edge data types.
56    pub graph: DiGraph<NodeData, EdgeData>,
57
58    /// Map from FileId to graph node index for O(1) lookup.
59    pub(crate) file_to_index: HashMap<FileId, NodeIndex>,
60
61    /// Map from SymbolId to graph node index for O(1) lookup.
62    pub(crate) symbol_to_index: HashMap<SymbolId, NodeIndex>,
63
64    /// Map from external raw path to graph node index for O(1) lookup.
65    pub(crate) external_index: HashMap<String, NodeIndex>,
66
67    /// Snapshot identifier for this graph as discussed before.
68    pub snapshot_id: SnapshotId,
69}
70
71impl CodeGraph {
72    /// Creates an empty CodeGraph for the given snapshot.
73    pub fn new(snapshot_id: SnapshotId) -> Self {
74        Self {
75            graph: DiGraph::new(),
76            file_to_index: HashMap::new(),
77            symbol_to_index: HashMap::new(),
78            external_index: HashMap::new(),
79            snapshot_id,
80        }
81    }
82    pub fn file_node_index(&self, file_id: FileId) -> Option<NodeIndex> {
83        self.file_to_index.get(&file_id).copied()
84    }
85    pub fn symbol_node_index(&self, symbol_id: SymbolId) -> Option<NodeIndex> {
86        self.symbol_to_index.get(&symbol_id).copied()
87    }
88    pub fn file_node(&self, file_id: FileId) -> Option<&FileNode> {
89        let idx = self.file_node_index(file_id)?;
90        self.graph.node_weight(idx).and_then(|data| data.as_file())
91    }
92    pub fn symbol_node(&self, symbol_id: SymbolId) -> Option<&SymbolNode> {
93        let idx = self.symbol_node_index(symbol_id)?;
94        self.graph
95            .node_weight(idx)
96            .and_then(|data| data.as_symbol())
97    }
98    pub fn file_count(&self) -> usize {
99        self.file_to_index.len()
100    }
101    pub fn symbol_count(&self) -> usize {
102        self.symbol_to_index.len()
103    }
104    pub fn external_count(&self) -> usize {
105        self.external_index.len()
106    }
107    pub fn node_count(&self) -> usize {
108        self.graph.node_count()
109    }
110    pub fn edge_count(&self) -> usize {
111        self.graph.edge_count()
112    }
113    /// Resolves or creates the `External` node for a raw unresolved path, keeping
114    /// `external_index` consistent so repeated loads reuse a single node.
115    pub fn get_or_create_external_node(&mut self, raw_path: String, language: LangId) -> NodeIndex {
116        if let Some(&idx) = self.external_index.get(&raw_path) {
117            return idx;
118        }
119        let node = NodeData::External(ExternalNode {
120            raw_path: raw_path.clone(),
121            language,
122            classification: None,
123        });
124        let idx = self.graph.add_node(node);
125        self.external_index.insert(raw_path, idx);
126        idx
127    }
128    /// Adds an edge, normalizing duplicate `(src, dst, kind)` triples by max-merging
129    /// confidence so injected edges obey the same invariant as builder-constructed ones.
130    pub fn add_edge_normalized(
131        &mut self,
132        source: NodeIndex,
133        target: NodeIndex,
134        kind: EdgeKind,
135        confidence: f32,
136    ) {
137        let mut edge_idx = self.graph.first_edge(source, petgraph::Direction::Outgoing);
138        while let Some(e) = edge_idx {
139            let (_src, dst) = self.graph.edge_endpoints(e).unwrap();
140            if dst == target && self.graph[e].kind == kind {
141                self.graph[e].confidence = self.graph[e].confidence.max(confidence);
142                return;
143            }
144            edge_idx = self.graph.next_edge(e, petgraph::Direction::Outgoing);
145        }
146        self.graph.add_edge(
147            source,
148            target,
149            EdgeData {
150                kind,
151                confidence,
152                flow_kind: None,
153            },
154        );
155    }
156
157    /// Adds a Flow edge with a specific flow kind, normalizing duplicates by
158    /// max-merging confidence (same (src, dst, Flow) triple). When a duplicate
159    /// edge exists, the first non-None `flow_kind` is preserved.
160    pub fn add_edge_normalized_with_flow(
161        &mut self,
162        source: NodeIndex,
163        target: NodeIndex,
164        kind: EdgeKind,
165        confidence: f32,
166        flow_kind: Option<crate::model::FlowKind>,
167    ) {
168        let mut edge_idx = self.graph.first_edge(source, petgraph::Direction::Outgoing);
169        while let Some(e) = edge_idx {
170            let (_src, dst) = self.graph.edge_endpoints(e).unwrap();
171            if dst == target && self.graph[e].kind == kind {
172                self.graph[e].confidence = self.graph[e].confidence.max(confidence);
173                if self.graph[e].flow_kind.is_none() {
174                    self.graph[e].flow_kind = flow_kind;
175                }
176                return;
177            }
178            edge_idx = self.graph.next_edge(e, petgraph::Direction::Outgoing);
179        }
180        self.graph.add_edge(
181            source,
182            target,
183            EdgeData {
184                kind,
185                confidence,
186                flow_kind,
187            },
188        );
189    }
190
191    pub fn files(&self) -> impl Iterator<Item = (FileId, &FileNode)> + '_ {
192        self.file_to_index.iter().filter_map(|(file_id, &idx)| {
193            self.graph
194                .node_weight(idx)
195                .and_then(|data| data.as_file().map(|f| (*file_id, f)))
196        })
197    }
198    pub fn symbols(&self) -> impl Iterator<Item = (SymbolId, &SymbolNode)> + '_ {
199        self.symbol_to_index.iter().filter_map(|(symbol_id, &idx)| {
200            self.graph
201                .node_weight(idx)
202                .and_then(|data| data.as_symbol().map(|s| (*symbol_id, s)))
203        })
204    }
205    pub fn edges_of_kind(
206        &self,
207        kind: EdgeKind,
208    ) -> impl Iterator<Item = (NodeIndex, NodeIndex)> + '_ {
209        self.graph.edge_indices().filter_map(move |edge_idx| {
210            let (source, target) = self.graph.edge_endpoints(edge_idx)?;
211            let weight = self.graph.edge_weight(edge_idx)?;
212            if weight.kind == kind {
213                Some((source, target))
214            } else {
215                None
216            }
217        })
218    }
219}
220
221#[cfg(test)]
222mod tests {
223    use super::*;
224    use crate::language::LangId;
225    use crate::model::{LineColumn, SourceRange, Symbol, SymbolKind, Visibility, ids::SnapshotId};
226    use std::path::PathBuf;
227
228    fn test_range() -> SourceRange {
229        SourceRange {
230            byte_start: 0,
231            byte_end: 10,
232            start: LineColumn { line: 1, column: 0 },
233            end: LineColumn {
234                line: 1,
235                column: 10,
236            },
237        }
238    }
239
240    fn test_symbol(id: u32, name: &str) -> Symbol {
241        Symbol {
242            id: SymbolId::new(id).unwrap(),
243            name: name.to_string(),
244            kind: SymbolKind::Function,
245            language: LangId::Rust,
246            file_path: PathBuf::from("test.rs"),
247            source_range: test_range(),
248            visibility: Some(Visibility::Public),
249            signature: None,
250            docstring: None,
251            is_async: false,
252        }
253    }
254
255    #[test]
256    fn code_graph_new_empty() {
257        let graph = CodeGraph::new(SnapshotId::new(1).unwrap());
258        assert_eq!(graph.node_count(), 0);
259        assert_eq!(graph.edge_count(), 0);
260        assert_eq!(graph.snapshot_id.to_raw(), 1);
261    }
262
263    #[test]
264    fn code_graph_file_lookup_returns_none_for_missing() {
265        let graph = CodeGraph::new(SnapshotId::new(1).unwrap());
266        assert!(graph.file_node(FileId::new(1).unwrap()).is_none());
267        assert!(graph.file_node_index(FileId::new(1).unwrap()).is_none());
268    }
269
270    #[test]
271    fn code_graph_symbol_lookup_returns_none_for_missing() {
272        let graph = CodeGraph::new(SnapshotId::new(1).unwrap());
273        assert!(graph.symbol_node(SymbolId::new(1).unwrap()).is_none());
274        assert!(graph.symbol_node_index(SymbolId::new(1).unwrap()).is_none());
275    }
276
277    #[test]
278    fn builder_produces_valid_code_graph() {
279        let mut builder = GraphBuilder::new(SnapshotId::new(1).unwrap());
280        let file_id = builder.add_file(PathBuf::from("test.rs"), LangId::Rust);
281        let symbol = test_symbol(1, "main");
282        let _sym_idx = builder.add_symbol(&symbol).unwrap();
283
284        let graph = builder.build();
285
286        assert_eq!(graph.file_count(), 1);
287        assert_eq!(graph.symbol_count(), 1);
288        assert_eq!(graph.node_count(), 2);
289        assert_eq!(graph.edge_count(), 1); // ownership edge
290
291        // Test lookups
292        let file_lookup = graph.file_node(file_id);
293        assert!(file_lookup.is_some());
294        assert_eq!(file_lookup.unwrap().language, LangId::Rust);
295
296        let sym_lookup = graph.symbol_node(SymbolId::new(1).unwrap());
297        assert!(sym_lookup.is_some());
298        assert_eq!(sym_lookup.unwrap().name, "main");
299    }
300
301    #[test]
302    fn code_graph_iteration_over_files() {
303        let mut builder = GraphBuilder::new(SnapshotId::new(1).unwrap());
304        builder.add_file(PathBuf::from("a.rs"), LangId::Rust);
305        builder.add_file(PathBuf::from("b.py"), LangId::Python);
306
307        let graph = builder.build();
308        let files: Vec<_> = graph.files().collect();
309
310        assert_eq!(files.len(), 2);
311    }
312
313    #[test]
314    fn code_graph_iteration_over_symbols() {
315        let mut builder = GraphBuilder::new(SnapshotId::new(1).unwrap());
316        let _file_id = builder.add_file(PathBuf::from("test.rs"), LangId::Rust);
317        let sym1 = test_symbol(1, "func_a");
318        let sym2 = test_symbol(2, "func_b");
319        builder.add_symbol(&sym1).unwrap();
320        builder.add_symbol(&sym2).unwrap();
321
322        let graph = builder.build();
323        let symbols: Vec<_> = graph.symbols().collect();
324
325        assert_eq!(symbols.len(), 2);
326    }
327
328    #[test]
329    fn code_graph_edges_of_kind_filtering() {
330        let mut builder = GraphBuilder::new(SnapshotId::new(1).unwrap());
331        let file1 = builder.add_file(PathBuf::from("a.rs"), LangId::Rust);
332        let _file2 = builder.add_file(PathBuf::from("b.rs"), LangId::Rust);
333
334        // Add import edge
335        builder.add_import(file1, PathBuf::from("b.rs"));
336
337        let graph = builder.build();
338
339        let ownership_edges: Vec<_> = graph.edges_of_kind(EdgeKind::Ownership).collect();
340        let import_edges: Vec<_> = graph.edges_of_kind(EdgeKind::Import).collect();
341
342        assert_eq!(ownership_edges.len(), 0); // No symbols added
343        assert_eq!(import_edges.len(), 1);
344    }
345
346    #[test]
347    fn add_edge_normalized_handles_multiple_edge_kinds_between_same_nodes() {
348        let mut graph = CodeGraph::new(SnapshotId::new(1).unwrap());
349        let n1 = graph.graph.add_node(NodeData::File(FileNode {
350            id: FileId::new(1).unwrap(),
351            path: PathBuf::from("a.rs"),
352            language: LangId::Rust,
353            snapshot_id: SnapshotId::new(1).unwrap(),
354        }));
355        let n2 = graph.graph.add_node(NodeData::File(FileNode {
356            id: FileId::new(2).unwrap(),
357            path: PathBuf::from("b.rs"),
358            language: LangId::Rust,
359            snapshot_id: SnapshotId::new(1).unwrap(),
360        }));
361
362        // 1. Add Reference edge with confidence 0.7
363        graph.add_edge_normalized(n1, n2, EdgeKind::Reference, 0.7);
364        // 2. Add Import edge with confidence 0.5 (pushed to head of edge list)
365        graph.add_edge_normalized(n1, n2, EdgeKind::Import, 0.5);
366        // 3. Add Reference edge again with confidence 0.9 (should max-merge into existing Reference edge)
367        graph.add_edge_normalized(n1, n2, EdgeKind::Reference, 0.9);
368
369        let ref_count = graph
370            .graph
371            .edges_connecting(n1, n2)
372            .filter(|e| e.weight().kind == EdgeKind::Reference)
373            .count();
374        assert_eq!(
375            ref_count, 1,
376            "Expected 1 Reference edge, but found {ref_count}"
377        );
378        assert_eq!(graph.edge_count(), 2);
379    }
380
381    #[test]
382    fn add_edge_normalized_with_flow_preserves_first_flow_kind() {
383        use crate::model::{DataNodeId, DataScope, FlowKind};
384        let mut graph = CodeGraph::new(SnapshotId::new(1).unwrap());
385        let n1 = graph.graph.add_node(NodeData::Data(DataGraphNode {
386            id: DataNodeId::new(1).unwrap(),
387            symbol_id: None,
388            name: Some("x".into()),
389            scope: DataScope::Local,
390            type_hint: None,
391            source_range: test_range(),
392        }));
393        let n2 = graph.graph.add_node(NodeData::Data(DataGraphNode {
394            id: DataNodeId::new(2).unwrap(),
395            symbol_id: None,
396            name: Some("y".into()),
397            scope: DataScope::Local,
398            type_hint: None,
399            source_range: test_range(),
400        }));
401
402        graph.add_edge_normalized_with_flow(n1, n2, EdgeKind::Flow, 0.9, Some(FlowKind::DefUse));
403        graph.add_edge_normalized_with_flow(n1, n2, EdgeKind::Flow, 0.8, Some(FlowKind::Argument));
404
405        assert_eq!(graph.edge_count(), 1);
406        let edge = graph.graph.edges_connecting(n1, n2).next().unwrap();
407        assert_eq!(edge.weight().flow_kind, Some(FlowKind::DefUse));
408        assert_eq!(edge.weight().confidence, 0.9);
409    }
410}
meta_ast/graph/mod.rs

meta_ast/graph/
mod.rs
