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(1));
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::{ExternalClassification, ExternalNode, FileNode, NodeData, SymbolNode};
44pub use scc::{DeployabilityHint, Scc, SccAnalysis};
45
46use crate::language::LangId;
47use crate::model::{FileId, SnapshotId, SymbolId};
48use petgraph::graph::{DiGraph, NodeIndex};
49
50/// The canonical dependency graph for a codebase snapshot.
51#[derive(Debug, Clone)]
52pub struct CodeGraph {
53    /// The underlying petgraph with our node/edge data types.
54    pub graph: DiGraph<NodeData, EdgeData>,
55
56    /// Map from FileId to graph node index for O(1) lookup.
57    pub(crate) file_to_index: HashMap<FileId, NodeIndex>,
58
59    /// Map from SymbolId to graph node index for O(1) lookup.
60    pub(crate) symbol_to_index: HashMap<SymbolId, NodeIndex>,
61
62    /// Map from external raw path to graph node index for O(1) lookup.
63    pub(crate) external_index: HashMap<String, NodeIndex>,
64
65    /// Snapshot identifier for this graph as discussed before.
66    pub snapshot_id: SnapshotId,
67}
68
69impl CodeGraph {
70    /// Creates an empty CodeGraph for the given snapshot.
71    pub fn new(snapshot_id: SnapshotId) -> Self {
72        Self {
73            graph: DiGraph::new(),
74            file_to_index: HashMap::new(),
75            symbol_to_index: HashMap::new(),
76            external_index: HashMap::new(),
77            snapshot_id,
78        }
79    }
80    pub fn file_node_index(&self, file_id: FileId) -> Option<NodeIndex> {
81        self.file_to_index.get(&file_id).copied()
82    }
83    pub fn symbol_node_index(&self, symbol_id: SymbolId) -> Option<NodeIndex> {
84        self.symbol_to_index.get(&symbol_id).copied()
85    }
86    pub fn file_node(&self, file_id: FileId) -> Option<&FileNode> {
87        let idx = self.file_node_index(file_id)?;
88        self.graph.node_weight(idx).and_then(|data| data.as_file())
89    }
90    pub fn symbol_node(&self, symbol_id: SymbolId) -> Option<&SymbolNode> {
91        let idx = self.symbol_node_index(symbol_id)?;
92        self.graph
93            .node_weight(idx)
94            .and_then(|data| data.as_symbol())
95    }
96    pub fn file_count(&self) -> usize {
97        self.file_to_index.len()
98    }
99    pub fn symbol_count(&self) -> usize {
100        self.symbol_to_index.len()
101    }
102    pub fn external_count(&self) -> usize {
103        self.external_index.len()
104    }
105    pub fn node_count(&self) -> usize {
106        self.graph.node_count()
107    }
108    pub fn edge_count(&self) -> usize {
109        self.graph.edge_count()
110    }
111    /// Resolves or creates the `External` node for a raw unresolved path, keeping
112    /// `external_index` consistent so repeated loads reuse a single node.
113    pub fn get_or_create_external_node(&mut self, raw_path: String, language: LangId) -> NodeIndex {
114        if let Some(&idx) = self.external_index.get(&raw_path) {
115            return idx;
116        }
117        let node = NodeData::External(ExternalNode {
118            raw_path: raw_path.clone(),
119            language,
120            classification: None,
121        });
122        let idx = self.graph.add_node(node);
123        self.external_index.insert(raw_path, idx);
124        idx
125    }
126    /// Adds an edge, normalizing duplicate `(src, dst, kind)` triples by max-merging
127    /// confidence so injected edges obey the same invariant as builder-constructed ones.
128    pub fn add_edge_normalized(
129        &mut self,
130        source: NodeIndex,
131        target: NodeIndex,
132        kind: EdgeKind,
133        confidence: f32,
134    ) {
135        if let Some(edge_idx) = self.graph.find_edge(source, target) {
136            let existing = &mut self.graph[edge_idx];
137            if existing.kind == kind {
138                existing.confidence = existing.confidence.max(confidence);
139                return;
140            }
141        }
142        self.graph
143            .add_edge(source, target, EdgeData { kind, confidence });
144    }
145    pub fn files(&self) -> impl Iterator<Item = (FileId, &FileNode)> + '_ {
146        self.file_to_index.iter().filter_map(|(file_id, &idx)| {
147            self.graph
148                .node_weight(idx)
149                .and_then(|data| data.as_file().map(|f| (*file_id, f)))
150        })
151    }
152    pub fn symbols(&self) -> impl Iterator<Item = (SymbolId, &SymbolNode)> + '_ {
153        self.symbol_to_index.iter().filter_map(|(symbol_id, &idx)| {
154            self.graph
155                .node_weight(idx)
156                .and_then(|data| data.as_symbol().map(|s| (*symbol_id, s)))
157        })
158    }
159    pub fn edges_of_kind(
160        &self,
161        kind: EdgeKind,
162    ) -> impl Iterator<Item = (NodeIndex, NodeIndex)> + '_ {
163        self.graph.edge_indices().filter_map(move |edge_idx| {
164            let (source, target) = self.graph.edge_endpoints(edge_idx)?;
165            let weight = self.graph.edge_weight(edge_idx)?;
166            if weight.kind == kind {
167                Some((source, target))
168            } else {
169                None
170            }
171        })
172    }
173}
174
175#[cfg(test)]
176mod tests {
177    use super::*;
178    use crate::language::LangId;
179    use crate::model::{LineColumn, SourceRange, Symbol, SymbolKind, Visibility, ids::SnapshotId};
180    use std::path::PathBuf;
181
182    fn test_range() -> SourceRange {
183        SourceRange {
184            byte_start: 0,
185            byte_end: 10,
186            start: LineColumn { line: 1, column: 0 },
187            end: LineColumn {
188                line: 1,
189                column: 10,
190            },
191        }
192    }
193
194    fn test_symbol(id: u32, name: &str) -> Symbol {
195        Symbol {
196            id: SymbolId(id),
197            name: name.to_string(),
198            kind: SymbolKind::Function,
199            language: LangId::Rust,
200            file_path: PathBuf::from("test.rs"),
201            source_range: test_range(),
202            visibility: Some(Visibility::Public),
203            signature: None,
204            docstring: None,
205            is_async: false,
206        }
207    }
208
209    #[test]
210    fn code_graph_new_empty() {
211        let graph = CodeGraph::new(SnapshotId(1));
212        assert_eq!(graph.node_count(), 0);
213        assert_eq!(graph.edge_count(), 0);
214        assert_eq!(graph.snapshot_id.0, 1);
215    }
216
217    #[test]
218    fn code_graph_file_lookup_returns_none_for_missing() {
219        let graph = CodeGraph::new(SnapshotId(1));
220        assert!(graph.file_node(FileId(0)).is_none());
221        assert!(graph.file_node_index(FileId(0)).is_none());
222    }
223
224    #[test]
225    fn code_graph_symbol_lookup_returns_none_for_missing() {
226        let graph = CodeGraph::new(SnapshotId(1));
227        assert!(graph.symbol_node(SymbolId(0)).is_none());
228        assert!(graph.symbol_node_index(SymbolId(0)).is_none());
229    }
230
231    #[test]
232    fn builder_produces_valid_code_graph() {
233        let mut builder = GraphBuilder::new(SnapshotId(1));
234        let file_id = builder.add_file(PathBuf::from("test.rs"), LangId::Rust);
235        let symbol = test_symbol(1, "main");
236        let _sym_idx = builder.add_symbol(&symbol).unwrap();
237
238        let graph = builder.build();
239
240        assert_eq!(graph.file_count(), 1);
241        assert_eq!(graph.symbol_count(), 1);
242        assert_eq!(graph.node_count(), 2);
243        assert_eq!(graph.edge_count(), 1); // ownership edge
244
245        // Test lookups
246        let file_lookup = graph.file_node(file_id);
247        assert!(file_lookup.is_some());
248        assert_eq!(file_lookup.unwrap().language, LangId::Rust);
249
250        let sym_lookup = graph.symbol_node(SymbolId(1));
251        assert!(sym_lookup.is_some());
252        assert_eq!(sym_lookup.unwrap().name, "main");
253    }
254
255    #[test]
256    fn code_graph_iteration_over_files() {
257        let mut builder = GraphBuilder::new(SnapshotId(1));
258        builder.add_file(PathBuf::from("a.rs"), LangId::Rust);
259        builder.add_file(PathBuf::from("b.py"), LangId::Python);
260
261        let graph = builder.build();
262        let files: Vec<_> = graph.files().collect();
263
264        assert_eq!(files.len(), 2);
265    }
266
267    #[test]
268    fn code_graph_iteration_over_symbols() {
269        let mut builder = GraphBuilder::new(SnapshotId(1));
270        let _file_id = builder.add_file(PathBuf::from("test.rs"), LangId::Rust);
271        let sym1 = test_symbol(1, "func_a");
272        let sym2 = test_symbol(2, "func_b");
273        builder.add_symbol(&sym1).unwrap();
274        builder.add_symbol(&sym2).unwrap();
275
276        let graph = builder.build();
277        let symbols: Vec<_> = graph.symbols().collect();
278
279        assert_eq!(symbols.len(), 2);
280    }
281
282    #[test]
283    fn code_graph_edges_of_kind_filtering() {
284        let mut builder = GraphBuilder::new(SnapshotId(1));
285        let file1 = builder.add_file(PathBuf::from("a.rs"), LangId::Rust);
286        let _file2 = builder.add_file(PathBuf::from("b.rs"), LangId::Rust);
287
288        // Add import edge
289        builder.add_import(file1, PathBuf::from("b.rs"));
290
291        let graph = builder.build();
292
293        let ownership_edges: Vec<_> = graph.edges_of_kind(EdgeKind::Ownership).collect();
294        let import_edges: Vec<_> = graph.edges_of_kind(EdgeKind::Import).collect();
295
296        assert_eq!(ownership_edges.len(), 0); // No symbols added
297        assert_eq!(import_edges.len(), 1);
298    }
299}
meta_ast/graph/mod.rs

meta_ast/graph/
mod.rs
