How It Works

symtrace replaces noisy line-by-line diffing with structural tree comparison. It parses code into concrete syntax trees using Tree-sitter, computes unique node identity hashes, and executes a 6-stage matching algorithm to isolate semantic operations.

Architecture Pipeline

Repository Target Resolution ──> Dual-Path Git File Changes ──> Path Glob Filtering
 (Commits / Index / Work)        (Old & New Path Pairs)          (--path "src/**/*.rs")
           │                                                               │
           ▼                                                               ▼
 Two-Tier CAS Diff Cache <────── Incremental AST Parsing <───── Versioned AST Cache
  (DiffCacheKey OID Map)          (BLAKE3 Hash Reuse)           (16-Shard RwLock LRU)
           │
           ▼
 6-Stage AST Matching ───────> Global Node Index Graph ──> Semantic Intelligence
  (SIMD & Bitset Jaccard)       (Parallel Rayon Candidate Index)  (Call Graph & Data-Flow)
           │                                                               │
           ▼                                                               ▼
 Adaptive Granularity ────────────────────────────────────────> Multi-Format Output
  (MicroCompact / Standard / Full)                               (CLI / Prompt / SARIF)

1. Zero-Copy Repository Access & Delta Extraction

symtrace uses libgit2 in-process (zero shell-outs) with a thread-safe Single-Handle Shared OID Reader:

• Zero-Copy Byte Slice Streaming: Implemented read_blob_bytes() and parse_bytes() for direct Tree-sitter byte-slice parsing from Git blobs without intermediate string allocations.
• Native Git Rename Hints: Enables diff.find_similar() in git2::DiffOptions to resolve native Git file renames instantly before AST parsing begins.
• Positional Defaults: Positional arguments automatically default:
  • REPO_PATH: . (current directory)
  • COMMIT_A: HEAD~1
  • COMMIT_B: Working tree (or HEAD if --staged is set)
• Path Glob Filtering: --path <GLOB> filters deltas before AST parsing.

2. AST Parsing & Two-Tier CAS Diff Caching

Before parsing, symtrace checks its high-performance caching infrastructure:

Two-Tier Content-Addressed Storage (CAS) FileDiff Cache

• Instant Precomputed OID Lookup: Keyed by DiffCacheKey (old_blob_oid || new_blob_oid || logic_only || limits_hash), returning warm diff records in under 0.004 ms (4 microseconds), completely bypassing tree-sitter parsing and graph matching.
• 16-Bucket Lock Striping & Atomic Writes: In-memory LRU cache is striped across 16 RwLock shards to eliminate thread contention, while disk cache writes are committed atomically using temporary files and filesystem renames.

Thread-Local Arena & Parser Recycler (BumpaloRecycler)

• Re-uses bumpalo::Bump arenas and tree_sitter::Parser instances across worker threads in Rayon thread pools, reducing heap allocations by 50%.

Subtree Diff-Window Engine

• Pushes line window boundary checks directly into recursive AST descent in collect_significant_nodes_windowed(), avoiding full-tree traversal and reducing peak memory allocations by 95% on oversized files (> 1 MiB).

3. Four-Hash BLAKE3 Node Fingerprinting & SIMD Histograms

To uniquely identify syntactic nodes regardless of position or formatting, symtrace computes 4 distinct SIMD-accelerated BLAKE3 hashes for every AST node:

Hash Type	What It Captures	Robustness
Structural Hash	Node type and parent-child structural shape (ignoring tokens and variable names)	Immune to renames and formatting
Content Hash	Raw token text content and literal values	Detects exact code duplication
Identity Hash	Node kind + declared entity name (e.g. function_declaration + parse_body)	Matches entities across position moves
Context Hash	Hashes of parent, preceding sibling, and following sibling nodes	Identifies code block context

In addition, each node computes a 64-bit token bitset (token_bitset) and a 16-bin frequency histogram (token_histogram_16) for vectorized SIMD Jaccard similarity pre-filtering.

4. 6-Stage AST Matching Pipeline

Matching operates via a unified global index across all modified files concurrently:

pub struct GlobalNodeIndex {
    /// structural_hash -> Vec<(file_id, node_id)>
    by_structural_hash: HashMap<[u8; 32], Vec<GlobalNodeRef>>,
    /// signature_hash -> Vec<(file_id, node_id)>
    by_signature_hash: HashMap<[u8; 32], Vec<GlobalNodeRef>>,
}

1. Stage 1: Fast-Path Isomorphic Micro-Edit Match: Linear 1:1 pairwise scan for structurally identical ASTs (ast_a.structural_hash == ast_b.structural_hash), reducing micro-edit diff latency to under 0.1 ms.
2. Stage 2: Token Multiset Bitset & SIMD Frequency Jaccard: 64-bit bitset pre-filtering (token_bitset) and AVX2/SSE SIMD histogram evaluation (simd_jaccard_histogram_16).
3. Stage 3: Topological Data-Flow Isomorphism: Intra-procedural def-use variable lineage verification (analyze_intra_procedural_data_flow) separating harmless renames from functional data-flow mutations.
4. Stage 4: Subtree Windowing & Candidate Pruning: Bounded window matching on large files.
5. Stage 5: Parallel Global Node Index Graph: Parallel Rayon candidate indexing across all files for cross-file moves and renames at O(N log N) complexity.
6. Stage 6: Hash-Indexed Symbol Tracking: Hash-bucket lookup tables for cross-file symbol move and rename resolution with cycle guards at O(M + N) complexity.

5. Semantic Intelligence & Developer Ecosystem

• Cross-File Call Graph & Blast Radius: Computes transitive BFS caller impact up to depth 5 across file boundaries when signatures change.
• Contract & Safety Guard Alerts: Detects removed null checks, deleted bounds guards, stripped mutexes, or omitted resource cleanup.
• Declarative AST Semantic Linter (symtrace lint): Evaluates custom Tree-sitter .scm rules with severity tiers and CI thresholds.
• Adaptive Granularity Controller: Dynamically switches between MicroCompact (--compact), Standard, and FullStructural views.
• LLM Context Optimization (--format prompt): Ultra-dense serialization saving up to 80% tokens for AI coding assistants.
• Interactive TUI Inspector (symtrace tui): Full terminal workspace for interactive refactor inspection, call graph visualization, and symbol search.
• 3-Way AST Merge Driver (symtrace merge-driver): AST scope splicing and tree-sitter validation re-parse (has_ast_errors()) for conflict-free rebases.