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, EdgeIndex, 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    graph: DiGraph<NodeData, EdgeData>,
57
58    /// O(1) dedup index: (source, target, kind) -> EdgeIndex, kept in sync
59    /// with `graph`. Every edge added through the normalized-add methods is
60    /// registered here; the builder populates it in `GraphBuilder::build`.
61    edge_index: HashMap<(NodeIndex, NodeIndex, EdgeKind), EdgeIndex>,
62
63    /// Map from FileId to graph node index for O(1) lookup.
64    pub(crate) file_to_index: HashMap<FileId, NodeIndex>,
65
66    /// Map from SymbolId to graph node index for O(1) lookup.
67    pub(crate) symbol_to_index: HashMap<SymbolId, NodeIndex>,
68
69    /// Map from external raw path to graph node index for O(1) lookup.
70    pub(crate) external_index: HashMap<String, NodeIndex>,
71
72    /// Snapshot identifier for this graph as discussed before.
73    pub snapshot_id: SnapshotId,
74}
75
76impl CodeGraph {
77    /// Creates an empty CodeGraph for the given snapshot.
78    pub fn new(snapshot_id: SnapshotId) -> Self {
79        Self {
80            graph: DiGraph::new(),
81            edge_index: HashMap::new(),
82            file_to_index: HashMap::new(),
83            symbol_to_index: HashMap::new(),
84            external_index: HashMap::new(),
85            snapshot_id,
86        }
87    }
88
89    /// Assemble a graph from builder parts without reindexing edges.
90    ///
91    /// The builder maintains the same `(source, target, kind)` dedup index
92    /// during construction, so `build()` moves it directly.
93    pub(crate) fn from_parts(
94        graph: DiGraph<NodeData, EdgeData>,
95        edge_index: HashMap<(NodeIndex, NodeIndex, EdgeKind), EdgeIndex>,
96        file_to_index: HashMap<FileId, NodeIndex>,
97        symbol_to_index: HashMap<SymbolId, NodeIndex>,
98        external_index: HashMap<String, NodeIndex>,
99        snapshot_id: SnapshotId,
100    ) -> Self {
101        Self {
102            graph,
103            edge_index,
104            file_to_index,
105            symbol_to_index,
106            external_index,
107            snapshot_id,
108        }
109    }
110    /// Immutable access to the underlying petgraph graph for SCC analysis,
111    /// serialization, and deploy algorithms.
112    pub fn graph(&self) -> &DiGraph<NodeData, EdgeData> {
113        &self.graph
114    }
115
116    /// Adds a raw node to the graph. Node additions do not affect edge
117    /// normalization, so this is the only direct mutation needed by
118    /// deploy/test code that injects synthetic nodes post-build.
119    ///
120    /// The caller remains responsible for registering the node in the
121    /// index maps (`file_to_index`, `symbol_to_index`, `external_index`)
122    /// when it is a `File`/`Symbol`/`External` node. This method does not
123    /// sync those maps; a bare `Data` node needs no registration.
124    pub fn add_node(&mut self, node: NodeData) -> NodeIndex {
125        self.graph.add_node(node)
126    }
127    pub fn file_node_index(&self, file_id: FileId) -> Option<NodeIndex> {
128        self.file_to_index.get(&file_id).copied()
129    }
130    pub fn symbol_node_index(&self, symbol_id: SymbolId) -> Option<NodeIndex> {
131        self.symbol_to_index.get(&symbol_id).copied()
132    }
133    pub fn file_node(&self, file_id: FileId) -> Option<&FileNode> {
134        let idx = self.file_node_index(file_id)?;
135        self.graph.node_weight(idx).and_then(|data| data.as_file())
136    }
137    pub fn symbol_node(&self, symbol_id: SymbolId) -> Option<&SymbolNode> {
138        let idx = self.symbol_node_index(symbol_id)?;
139        self.graph
140            .node_weight(idx)
141            .and_then(|data| data.as_symbol())
142    }
143    pub fn file_count(&self) -> usize {
144        self.file_to_index.len()
145    }
146    pub fn symbol_count(&self) -> usize {
147        self.symbol_to_index.len()
148    }
149    pub fn external_count(&self) -> usize {
150        self.external_index.len()
151    }
152    pub fn node_count(&self) -> usize {
153        self.graph.node_count()
154    }
155    pub fn edge_count(&self) -> usize {
156        self.graph.edge_count()
157    }
158    /// Resolves or creates the `External` node for a raw unresolved path, keeping
159    /// `external_index` consistent so repeated loads reuse a single node.
160    pub fn get_or_create_external_node(&mut self, raw_path: String, language: LangId) -> NodeIndex {
161        if let Some(&idx) = self.external_index.get(&raw_path) {
162            return idx;
163        }
164        let node = NodeData::External(ExternalNode {
165            raw_path: raw_path.clone(),
166            language,
167            classification: None,
168        });
169        let idx = self.graph.add_node(node);
170        self.external_index.insert(raw_path, idx);
171        idx
172    }
173    /// Adds an edge, normalizing duplicate `(src, dst, kind)` triples by max-merging
174    /// confidence so injected edges obey the same invariant as builder-constructed ones.
175    /// The O(1) `edge_index` makes duplicate detection independent of out-degree.
176    pub fn add_edge_normalized(
177        &mut self,
178        source: NodeIndex,
179        target: NodeIndex,
180        kind: EdgeKind,
181        confidence: f32,
182    ) {
183        let confidence = confidence.clamp(0.0, 1.0);
184        let key = (source, target, kind);
185        if let Some(&edge_idx) = self.edge_index.get(&key) {
186            let edge = &mut self.graph[edge_idx];
187            edge.confidence = edge.confidence.max(confidence);
188            return;
189        }
190        let edge_idx = self.graph.add_edge(
191            source,
192            target,
193            EdgeData {
194                kind,
195                confidence,
196                flow_kind: None,
197            },
198        );
199        self.edge_index.insert(key, edge_idx);
200    }
201
202    /// Adds a Flow edge with a specific flow kind, normalizing duplicates by
203    /// max-merging confidence (same (src, dst, Flow) triple). When a duplicate
204    /// edge exists, the first non-None `flow_kind` is preserved. The lookup is
205    /// O(1) via the dedup index.
206    pub fn add_edge_normalized_with_flow(
207        &mut self,
208        source: NodeIndex,
209        target: NodeIndex,
210        kind: EdgeKind,
211        confidence: f32,
212        flow_kind: Option<crate::model::FlowKind>,
213    ) {
214        let confidence = confidence.clamp(0.0, 1.0);
215        let key = (source, target, kind);
216        if let Some(&edge_idx) = self.edge_index.get(&key) {
217            let edge = &mut self.graph[edge_idx];
218            edge.confidence = edge.confidence.max(confidence);
219            if edge.flow_kind.is_none() {
220                edge.flow_kind = flow_kind;
221            }
222            return;
223        }
224        let edge_idx = self.graph.add_edge(
225            source,
226            target,
227            EdgeData {
228                kind,
229                confidence,
230                flow_kind,
231            },
232        );
233        self.edge_index.insert(key, edge_idx);
234    }
235
236    pub fn files(&self) -> impl Iterator<Item = (FileId, &FileNode)> + '_ {
237        self.file_to_index.iter().filter_map(|(file_id, &idx)| {
238            self.graph
239                .node_weight(idx)
240                .and_then(|data| data.as_file().map(|f| (*file_id, f)))
241        })
242    }
243    pub fn symbols(&self) -> impl Iterator<Item = (SymbolId, &SymbolNode)> + '_ {
244        self.symbol_to_index.iter().filter_map(|(symbol_id, &idx)| {
245            self.graph
246                .node_weight(idx)
247                .and_then(|data| data.as_symbol().map(|s| (*symbol_id, s)))
248        })
249    }
250    pub fn edges_of_kind(
251        &self,
252        kind: EdgeKind,
253    ) -> impl Iterator<Item = (NodeIndex, NodeIndex)> + '_ {
254        self.graph.edge_indices().filter_map(move |edge_idx| {
255            let (source, target) = self.graph.edge_endpoints(edge_idx)?;
256            let weight = self.graph.edge_weight(edge_idx)?;
257            if weight.kind == kind {
258                Some((source, target))
259            } else {
260                None
261            }
262        })
263    }
264
265    /// Reference edges as (source symbol, target symbol, confidence).
266    ///
267    /// Skips edges whose endpoints are not symbol nodes. Use for navigation
268    /// and confidence-ranked completion.
269    pub fn reference_edges(&self) -> impl Iterator<Item = (SymbolId, SymbolId, f32)> + '_ {
270        self.graph.edge_indices().filter_map(move |edge_idx| {
271            let weight = self.graph.edge_weight(edge_idx)?;
272            if weight.kind != EdgeKind::Reference {
273                return None;
274            }
275            let (source, target) = self.graph.edge_endpoints(edge_idx)?;
276            let source_id = self.graph.node_weight(source)?.as_symbol()?.id;
277            let target_id = self.graph.node_weight(target)?.as_symbol()?.id;
278            Some((source_id, target_id, weight.confidence))
279        })
280    }
281}
282
283#[cfg(test)]
284mod tests {
285    use super::*;
286    use crate::language::LangId;
287    use crate::model::{LineColumn, SourceRange, Symbol, SymbolKind, Visibility, ids::SnapshotId};
288    use std::path::PathBuf;
289
290    fn test_range() -> SourceRange {
291        SourceRange {
292            byte_start: 0,
293            byte_end: 10,
294            start: LineColumn { line: 1, column: 0 },
295            end: LineColumn {
296                line: 1,
297                column: 10,
298            },
299        }
300    }
301
302    fn test_file_node(id: u32, path: &str) -> NodeData {
303        NodeData::File(FileNode {
304            id: FileId::new(id).unwrap(),
305            path: PathBuf::from(path),
306            language: LangId::Rust,
307            snapshot_id: SnapshotId::new(1).unwrap(),
308        })
309    }
310
311    fn test_symbol(id: u32, name: &str) -> Symbol {
312        Symbol {
313            id: SymbolId::new(id).unwrap(),
314            name: name.to_string(),
315            kind: SymbolKind::Function,
316            language: LangId::Rust,
317            file_path: PathBuf::from("test.rs"),
318            source_range: test_range(),
319            visibility: Some(Visibility::Public),
320            signature: None,
321            docstring: None,
322            is_async: false,
323        }
324    }
325
326    #[test]
327    fn code_graph_new_empty() {
328        let graph = CodeGraph::new(SnapshotId::new(1).unwrap());
329        assert_eq!(graph.node_count(), 0);
330        assert_eq!(graph.edge_count(), 0);
331        assert_eq!(graph.snapshot_id.to_raw(), 1);
332    }
333
334    #[test]
335    fn code_graph_file_lookup_returns_none_for_missing() {
336        let graph = CodeGraph::new(SnapshotId::new(1).unwrap());
337        assert!(graph.file_node(FileId::new(1).unwrap()).is_none());
338        assert!(graph.file_node_index(FileId::new(1).unwrap()).is_none());
339    }
340
341    #[test]
342    fn code_graph_symbol_lookup_returns_none_for_missing() {
343        let graph = CodeGraph::new(SnapshotId::new(1).unwrap());
344        assert!(graph.symbol_node(SymbolId::new(1).unwrap()).is_none());
345        assert!(graph.symbol_node_index(SymbolId::new(1).unwrap()).is_none());
346    }
347
348    #[test]
349    fn builder_produces_valid_code_graph() {
350        let mut builder = GraphBuilder::new(SnapshotId::new(1).unwrap());
351        let file_id = builder.add_file(PathBuf::from("test.rs"), LangId::Rust);
352        let symbol = test_symbol(1, "main");
353        let _sym_idx = builder.add_symbol(&symbol).unwrap();
354
355        let graph = builder.build();
356
357        assert_eq!(graph.file_count(), 1);
358        assert_eq!(graph.symbol_count(), 1);
359        assert_eq!(graph.node_count(), 2);
360        assert_eq!(graph.edge_count(), 1); // ownership edge
361
362        // Test lookups
363        let file_lookup = graph.file_node(file_id);
364        assert!(file_lookup.is_some());
365        assert_eq!(file_lookup.unwrap().language, LangId::Rust);
366
367        let sym_lookup = graph.symbol_node(SymbolId::new(1).unwrap());
368        assert!(sym_lookup.is_some());
369        assert_eq!(sym_lookup.unwrap().name, "main");
370    }
371
372    #[test]
373    fn code_graph_iteration_over_files() {
374        let mut builder = GraphBuilder::new(SnapshotId::new(1).unwrap());
375        builder.add_file(PathBuf::from("a.rs"), LangId::Rust);
376        builder.add_file(PathBuf::from("b.py"), LangId::Python);
377
378        let graph = builder.build();
379        let files: Vec<_> = graph.files().collect();
380
381        assert_eq!(files.len(), 2);
382    }
383
384    #[test]
385    fn code_graph_iteration_over_symbols() {
386        let mut builder = GraphBuilder::new(SnapshotId::new(1).unwrap());
387        let _file_id = builder.add_file(PathBuf::from("test.rs"), LangId::Rust);
388        let sym1 = test_symbol(1, "func_a");
389        let sym2 = test_symbol(2, "func_b");
390        builder.add_symbol(&sym1).unwrap();
391        builder.add_symbol(&sym2).unwrap();
392
393        let graph = builder.build();
394        let symbols: Vec<_> = graph.symbols().collect();
395
396        assert_eq!(symbols.len(), 2);
397    }
398
399    #[test]
400    fn code_graph_edges_of_kind_filtering() {
401        let mut builder = GraphBuilder::new(SnapshotId::new(1).unwrap());
402        let file1 = builder.add_file(PathBuf::from("a.rs"), LangId::Rust);
403        let _file2 = builder.add_file(PathBuf::from("b.rs"), LangId::Rust);
404
405        // Add import edge
406        builder.add_import(file1, PathBuf::from("b.rs"));
407
408        let graph = builder.build();
409
410        let ownership_edges: Vec<_> = graph.edges_of_kind(EdgeKind::Ownership).collect();
411        let import_edges: Vec<_> = graph.edges_of_kind(EdgeKind::Import).collect();
412
413        assert_eq!(ownership_edges.len(), 0); // No symbols added
414        assert_eq!(import_edges.len(), 1);
415    }
416
417    #[test]
418    fn build_populated_edge_index_normalizes_post_build_edges() {
419        let mut builder = GraphBuilder::new(SnapshotId::new(1).unwrap());
420        let file_a = builder.add_file(PathBuf::from("a.rs"), LangId::Rust);
421        let file_b = builder.add_file(PathBuf::from("b.rs"), LangId::Rust);
422        builder.add_import(file_a, PathBuf::from("b.rs"));
423        let mut graph = builder.build();
424        assert_eq!(graph.edge_count(), 1);
425
426        let a_idx = graph.file_node_index(file_a).unwrap();
427        let b_idx = graph.file_node_index(file_b).unwrap();
428
429        // Duplicate triple already indexed by build(): must max-merge, not grow.
430        graph.add_edge_normalized(a_idx, b_idx, EdgeKind::Import, 0.5);
431        graph.add_edge_normalized(a_idx, b_idx, EdgeKind::Import, 0.8);
432        assert_eq!(graph.edge_count(), 1);
433
434        // Distinct kind on the same pair is a new edge.
435        graph.add_edge_normalized(a_idx, b_idx, EdgeKind::Reference, 0.9);
436        assert_eq!(graph.edge_count(), 2);
437    }
438
439    #[test]
440    fn add_edge_normalized_handles_multiple_edge_kinds_between_same_nodes() {
441        let mut graph = CodeGraph::new(SnapshotId::new(1).unwrap());
442        let n1 = graph.add_node(test_file_node(1, "a.rs"));
443        let n2 = graph.add_node(test_file_node(2, "b.rs"));
444
445        // 1. Add Reference edge with confidence 0.7
446        graph.add_edge_normalized(n1, n2, EdgeKind::Reference, 0.7);
447        // 2. Add Import edge with confidence 0.5 (pushed to head of edge list)
448        graph.add_edge_normalized(n1, n2, EdgeKind::Import, 0.5);
449        // 3. Add Reference edge again with confidence 0.9 (should max-merge into existing Reference edge)
450        graph.add_edge_normalized(n1, n2, EdgeKind::Reference, 0.9);
451
452        let ref_count = graph
453            .graph()
454            .edges_connecting(n1, n2)
455            .filter(|e| e.weight().kind == EdgeKind::Reference)
456            .count();
457        assert_eq!(
458            ref_count, 1,
459            "Expected 1 Reference edge, but found {ref_count}"
460        );
461        assert_eq!(graph.edge_count(), 2);
462    }
463
464    #[test]
465    fn add_edge_normalized_with_flow_preserves_first_flow_kind() {
466        use crate::model::{DataNodeId, DataScope, FlowKind};
467        let mut graph = CodeGraph::new(SnapshotId::new(1).unwrap());
468        let n1 = graph.add_node(NodeData::Data(DataGraphNode {
469            id: DataNodeId::new(1).unwrap(),
470            symbol_id: None,
471            name: Some("x".into()),
472            scope: DataScope::Local,
473            type_hint: None,
474            source_range: test_range(),
475        }));
476        let n2 = graph.add_node(NodeData::Data(DataGraphNode {
477            id: DataNodeId::new(2).unwrap(),
478            symbol_id: None,
479            name: Some("y".into()),
480            scope: DataScope::Local,
481            type_hint: None,
482            source_range: test_range(),
483        }));
484
485        graph.add_edge_normalized_with_flow(n1, n2, EdgeKind::Flow, 0.9, Some(FlowKind::DefUse));
486        graph.add_edge_normalized_with_flow(n1, n2, EdgeKind::Flow, 0.8, Some(FlowKind::Argument));
487
488        assert_eq!(graph.edge_count(), 1);
489        let edge = graph.graph().edges_connecting(n1, n2).next().unwrap();
490        assert_eq!(edge.weight().flow_kind, Some(FlowKind::DefUse));
491        assert_eq!(edge.weight().confidence, 0.9);
492    }
493
494    #[test]
495    fn add_edge_normalized_duplicate_never_grows_edge_count() {
496        let mut graph = CodeGraph::new(SnapshotId::new(1).unwrap());
497        let n1 = graph.add_node(test_file_node(1, "a.rs"));
498        let n2 = graph.add_node(test_file_node(2, "b.rs"));
499
500        graph.add_edge_normalized(n1, n2, EdgeKind::Import, 0.5);
501        for confidence in [0.6, 0.3, 0.9, 0.4, 0.7] {
502            graph.add_edge_normalized(n1, n2, EdgeKind::Import, confidence);
503        }
504
505        assert_eq!(graph.edge_count(), 1);
506        let edge = graph.graph().edges_connecting(n1, n2).next().unwrap();
507        assert_eq!(edge.weight().confidence, 0.9);
508    }
509
510    #[test]
511    fn add_edge_normalized_counts_only_distinct_triples() {
512        let mut graph = CodeGraph::new(SnapshotId::new(1).unwrap());
513        let n1 = graph.add_node(test_file_node(1, "a.rs"));
514        let n2 = graph.add_node(test_file_node(2, "b.rs"));
515        let n3 = graph.add_node(test_file_node(3, "c.rs"));
516
517        graph.add_edge_normalized(n1, n2, EdgeKind::Import, 0.5);
518        graph.add_edge_normalized(n1, n2, EdgeKind::Reference, 0.6);
519        graph.add_edge_normalized(n1, n3, EdgeKind::Reference, 0.7);
520        graph.add_edge_normalized(n1, n2, EdgeKind::Import, 0.9);
521
522        assert_eq!(graph.edge_count(), 3);
523    }
524}
meta_ast/graph/mod.rs

meta_ast/graph/
mod.rs
