RFC 0008:Graph Module and SCC Analysis

Phase 1 of meta-ast established the foundation: file discovery, parsing, symbol extraction, and inspect-compatible JSON output. Phase 2 extends this with dependency graph construction and Strongly Connected Component (SCC) analysis to provide deployability insights for polyglot codebases.

The graph model was specified in specs/graph-model.md and the implementation approach using petgraph was validated through research. This RFC defines the concrete module structure, APIs, and implementation strategy.

Goals

Build a directed dependency/reference graph from extracted symbols
Implement Tarjan SCC algorithm for cycle detection
Provide deployability hints based on SCC analysis
Maintain stable inspect output contract (funcs, classes, objects)
Support cross-file dependency mapping for mixed-language projects

Non-Goals

Full inter-procedural dataflow analysis (Phase 3)
Live graph database integration (Phase 4)
Real-time incremental graph updates (Phase 4)
Cross-language type inference (out of scope for MVP)

Design

1. Module Structure

New modules under src/graph/:

File	Responsibility
`mod.rs`	Public exports, `CodeGraph` struct, graph operations
`node.rs`	`FileNode`, `SymbolNode`, `NodeData` enum
`edge.rs`	`EdgeKind`, `EdgeData` with metadata
`builder.rs`	`GraphBuilder` for incremental construction
`scc.rs`	`SccAnalysis`, Tarjan SCC, deployability hints

Output extension: src/output/graph.rs for graph serialization.

2. Graph Types

Node storage uses petgraph DiGraph<NodeData, EdgeData> with stable node indices. NodeData is an enum for heterogeneous node types:

#![allow(unused)]
fn main() {
pub enum NodeData {
    File(FileNode),
    Symbol(SymbolNode),
}

pub struct FileNode {
    pub id: FileId,
    pub path: PathBuf,           // Project-relative as discussed with vicente
    pub language_id: LangId,
    pub snapshot_id: SnapshotId,
}

pub struct SymbolNode {
    pub id: SymbolId,
    pub name: String,
    pub kind: SymbolKind,
    pub file_id: FileId,
    pub visibility: Option<Visibility>,
    pub source_range: SourceRange,
}
}

Edges carry kind and metadata:

#![allow(unused)]
fn main() {
pub enum EdgeKind {
    Import,      // File imports another file
    Reference,   // Symbol references another symbol
    Ownership,   // File owns symbol, or symbol contains nested symbol
}

pub struct EdgeData {
    pub kind: EdgeKind,
    pub strength: EdgeStrength,  // Strong, Weak, or Dynamic
}

pub enum EdgeStrength {
    Strong,      // Direct, resolvable dependency
    Weak,        // Optional or conditional
    Dynamic,     // Runtime-resolved
}
}

3. Graph Construction

Two-phase construction from extraction results:

Phase A - Ownership graph (always acyclic by construction):

Add FileNode for each processed file
Add SymbolNode for each extracted symbol
Add Ownership edges: FileNode -> SymbolNode

Phase B - Dependency graph:

Add Import edges: FileNode -> FileNode (cross-file imports)
Add Reference edges: SymbolNode -> SymbolNode (symbol usage)

Import extraction extends the language pack system with import-specific tree-sitter queries per language.

4. SCC Analysis

SCC computation follows specs/graph-model.md invariants:

SCC runs on dependency subgraph only (Import + Reference edges)
Ownership edges are explicitly excluded from SCC computation
Duplicate edges normalized by (src, dst, edge_kind)

Tarjan’s algorithm via petgraph::algo::tarjan_scc produces components in reverse topological order.

SccAnalysis result structure:

#![allow(unused)]
fn main() {
pub struct SccAnalysis {
    pub components: Vec<Scc>,
    pub node_to_component: HashMap<NodeIndex, usize>,
}

pub struct Scc {
    pub index: usize,
    pub nodes: Vec<NodeIndex>,
    pub is_cyclic: bool,
    pub deployability_hint: DeployabilityHint,
}

pub enum DeployabilityHint {
    Independent,        // Size=1, no self-loop
    AcyclicDependency,  // Size=1, depends on other components
    CyclicCluster,      // Size>1 or self-loop present
}
}

5. CLI Integration

New subcommand graph alongside existing inspect:

#![allow(unused)]
fn main() {
pub enum Cli {
    Inspect(InspectArgs),
    Graph(GraphArgs),  // New
}
}

GraphArgs accepts same path/language filters as InspectArgs plus output format options.

Output format (JSON):

{
  "meta": {
    "snapshot_id": 1,
    "file_count": 10,
    "symbol_count": 150,
    "edge_count": 200
  },
  "nodes": [
    {"id": "F0", "kind": "file", "path": "src/main.py", "language": "python"},
    {"id": "S42", "kind": "symbol", "name": "main", "kind": "function", "file_id": "F0"}
  ],
  "edges": [
    {"source": "F0", "target": "F1", "kind": "import"},
    {"source": "S42", "target": "S43", "kind": "reference"}
  ],
  "sccs": [
    {
      "index": 0,
      "nodes": ["S10", "S11"],
      "is_cyclic": true,
      "deployability": "cyclic_cluster",
      "size": 2
    }
  ],
  "deployability_report": {
    "independent_units": 120,
    "cyclic_clusters": 5,
    "total_components": 125
  }
}

6. Error Handling

Graph construction errors are recoverable and emit diagnostics:

Missing import target: warning, edge not added
Duplicate edge: deduplicated silently
Cycle in ownership edges: error (violates invariant)

SCC computation is infallible for valid graphs.

7. Testing Strategy

Unit tests for GraphBuilder with known input/output
Unit tests for SCC computation on synthetic cyclic/acyclic graphs
Fixture tests for cross-file import detection per language
Integration tests for mixed-language dependency chains
Snapshot tests for graph JSON output format

8. Performance Considerations

Graph construction: sequential (linear in symbols + edges)
Symbol extraction remains parallel (rayon)
SCC computation: O(V + E) via Tarjan
Memory: adjacency list via petgraph (O(V + E))
No incremental updates in Phase 2 (full graph rebuild)

Migration Path

This RFC introduces new modules without breaking existing Phase 1 functionality:

inspect subcommand unchanged
Symbol extraction interface unchanged
New graph functionality additive only

Existing tests continue to pass. New tests validate graph-specific behavior.

Should we include intra-file reference edges (symbol calls within same file) in SCC? yes, for completeness.
How to handle unresolved imports (external dependencies)? Skip with warning,? Decision: Skip with warning for Phase2.
Should deployability hints include suggested entry points for cyclic clusters? Deferred to Phase 3 when call graph is richer.

References

specs/graph-model.md - Graph semantics and invariants
specs/requirements.md - FR-4, FR-5 for graph and SCC requirements
ADR 0004 - Graph representation decision record
petgraph documentation: https://docs.rs/petgraph

meta-ast

RFC 0008:Graph Module and SCC Analysis

Status

Context