rgctl-analysis Architecture

The rgctl-analysis crate bridges the code knowledge graph (rgctl-graph) with static-analysis algorithms. It organizes graph usage into three tiers.

Tier 1: Repository graph (source of truth)

MemoryBackend — in-memory node/edge store with typed topology
Mmap snapshots — PreparedGraphSnapshot, MmappedGraphSnapshot, ColumnarGraphMmap / SnapshotNodeStore for zero-copy RGCL v2 reads

Nodes represent symbols (functions, types, modules). Edges carry EdgeType semantics (Calls, Uses, Contains, References, Overrides, CoChangesWith, etc.).

Tier 2: Projected views (repository-level analysis)

Type	Module	Purpose
`PetGraphView`	`graph_utils`	Façade over typed bidirectional CSR (`StructuralTopology`); UUID maps
`StructuralTopology` / `CodeGraphCsr`	`structural_topology` / `rgctl-graph::csr`	Hot edge residency (~5 B/edge/dir); community/centrality/blast/dependency
`ColdMetadataDb`	`cold_metadata`	Mmap-backed node payloads after early snapshot write
`CallGraph`	`callgraph`	u32-indexed call-only adjacency for fast traversal
`FlatGraphIndex`	`centrality`	Contiguous `usize` edge list for numeric algorithms
`MroIndex`	`mro`	Cross-language MRO → `EdgeType::Overrides`; polymorphic call retarget

Convention: Discover ingest uses segmented disk spill (GraphBuilder::with_spill → write_columnar_from_spill): nodes/edges are append-only length-prefixed bincode on disk, externally sorted, then compiled to columnar v2 — no full Vec<Node>/Vec<Edge> or MemoryBackend during discover. Analysis opens ColdMetadataDb + CSR from the mmap; hydrate a CodeGraph only for --with-dashboard / migration / JSON. Share &PetGraphView / StructuralTopology across community / centrality / blast, then drop the view after the SCC engine is built.

Incremental updates: when .rgctl/graph.snapshot.bin exists, IncrementalUpdater extracts only changed files into a DeltaSegment, stream-compacts with GraphCompactor (alive UUID filter + edge row streaming; name/type indexes rebuilt during spill compile), atomically renames the new snapshot, then reloads. Force rebuild uses process_repository_to_snapshot. Without a snapshot, the legacy in-memory edit path remains. write_columnar_from_backend / process_repository remain for callers that need a live backend.

Columnar content digest and cache invalidation

Columnar v2 headers store a 64-byte hex BLAKE3 content digest (not a hash of file layout/offsets). Writers (discover spill compile, write_columnar_from_*, compact) compute it as:

bincode(Node) for every live node, sorted by UUID
then bincode(Edge::for_columnar_digest()) for every live edge, sorted by (from, to, edge_type)

Edges are topology-only for the digest: columnar rows do not store edge properties (call_site_line, etc.), so hashing strips them. Compact recomputes this digest over the final live set (same helpers as spill compile) — never hash(old_digest || delta).

Sidecars under .rgctl/ that embed graph_digest (blast_engine.snapshot.bin, macro call index/lookup, analysis_results.bin, semantic index, CFG/PDG archive) are deleted after compact so the next discover / blast-radius / macro path rebuilds against the new header instead of serving a stale hit. Do not copy the old digest into a new snapshot header to “preserve” those caches.

Repository-level analyses

Analysis	Primary graph	Algorithm
Centrality	`PetGraphView` → `FlatGraphIndex`	Pull-based CSR `FastPageRank` (dual-track `Calls` vs `STRUCTURAL_EDGE_TYPES`); `NodeRole` filter (`Production` / `Test` / `Generated` / `ExternalStub` / `Entrypoint` — non-production excluded from default hotspots; `--include-tests` to include); `SampledBetweenness` ($K=256$ degree-stratified Brandes pivots); `HyperBallHarmonic` (`discover --with-harmonic`)
Community	`PetGraphView` (undirected filter)	Fast-Leiden (local moving queue + BFS connected-subgraph refinement + coarsening) with $\mu+4\sigma$ `HubStripPolicy` → `"Shared / Infrastructure"` (`infrastructure_community_id`). JSON field `louvain_community_id` is historical schema name only
Blast radius (engine)	CSR Calls filter + kosaraju	Kosaraju SCC → on-demand reachability (flat graphs) or bitset rows
Blast radius (analyzer)	`PetGraphView` Calls filter	Reverse BFS
Dependencies	`PetGraphView` directed	Kosaraju SCC, reverse BFS impact
Complexity	Backend node properties	Aggregation
Migration	Community graph	Weighted topological sort
MRO / Overrides	Inheritance / mixin edges	`MroIndex` C3 (Python), Ruby prepend/include, Rust inherent-first, Java/C#/TS/Kotlin, C++ virtual bases, Go promotion → `Overrides`
SCIP overlay	Ambiguous `Calls`	`apply_scip_overlay` (`discover --scip`) upgrades resolution
Git churn	File co-change	`compute_and_apply_git_churn` → `git_hotspot_score` + `CoChangesWith` (`discover --with-git`, `metrics --churn`)
Clones	Function bodies / CFG	`exact` / `bloom` / `fragment` (SESE hammock + 2-iter 1-WL; `--seed`)

Tier 3: Intra-procedural graphs

Type	Module	Purpose
`ControlFlowGraph`	`cfg`, `cfg_builder`	Per-function CFG via tree-sitter
`ProgramDependenceGraph`	`pdg`	Data + control dependencies
`DominatorTree`	`dominance`	Immediate dominators and frontiers
`CfgPdgArchiveMmap`	`cfg_pdg_archive`	v3 indexed archive (`TocEntry` + `memmap2`); `ensure_cfg_pdg_for_source` lazy single-function append

Pipeline

tree-sitter AST → CFG → DominatorTree + ReachingDefs → PDG → Slicing / Taint

Reaching definitions track lexical (name, scope_id) pairs to prevent block-shadowing false edges while preserving let x = x + 1 RHS-before-LHS dataflow.

InterproceduralCFG stitches per-function CFGs with CallGraph for cross-function slicing.

Lazy vs whole-repo CFG: rgctl slice and rgctl cpg flows call ensure_cfg_pdg_for_source to build and cache one function without prior discover --with-cfg. Whole-repo rgctl taint --sink and rgctl cpg mutations still require discover --with-cfg.

Traversal depth

Graph BFS traversals (blast radius analyzer, dependency impact) share TraversalConfig with default depth 10 (DEFAULT_TRAVERSAL_DEPTH in graph_utils). Use TraversalConfig::unlimited() for full transitive closure; prefer BlastRadiusEngine for large graphs.

Caching and persistence

FlowCache / CfgPdgArchive — per-function CFG/PDG cache (v3 TOC; lazy append)
BlastEngineSnapshot — persisted SCC reachability bitsets (keyed by graph_digest)
AnalysisResults — columnar metrics decoupled from graph topology (CentralityTable, community, blast tables)
MacroCallIndex / lookup DB — digest-gated; invalidated after snapshot compact
.rgctl/analysis/git_churn.json — optional churn sidecar after --with-git

See Columnar content digest and cache invalidation above.

Centrality pipeline (discover)

Discover uses CentralityAnalyzer::analyze_columnar: flat scores from FlatGraphIndex are written directly into AnalysisResults without intermediate HashMap<Uuid, _> handoffs.

Graph size	PageRank (`FastPageRank`)	Betweenness (`SampledBetweenness`)	Harmonic (`HyperBallHarmonic`)
V ≤ 500	Exact (20 iter, ε=1e-6)	Exact Brandes	Exact BFS
500 < V ≤ 500,000	Exact (20 iter)	Sampled Brandes ($K=256$)	HyperBall (h=16, parallel HLL)
V > 500,000	Gated (8 iter, ε=1e-4)	Sampled Brandes ($K=256$)	HyperBall (h=8, parallel HLL)

Constants: LARGE_GRAPH_PAGERANK_*, LARGE_GRAPH_HYPERBALL_* in centrality.rs / centrality_approx.rs.

Profiling: discover -v with RUST_LOG=profile=info emits [profile] stage and [profile] centrality sub-phase lines (PageRank, betweenness, harmonic, columnar fill timings). Harmonic runs only with discover --with-harmonic.

See internal/profile.md for cold-profile commands and developer-machine timings; harmonic-centrality.md for HyperBall detail.