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 5-phase 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")
           │                                                               │
           ▼                                                               ▼
 Bounded TreeCache LRU ◄────── Incremental AST Parsing ◄───── Versioned AST Cache
  (Cap: 500 trees)             (BLAKE3 Hash Reuse)           (Blob + Limits Key)
           │
           ▼
 5-Phase AST Matching ───────► Deep BFS Symbol Tracking ─────► Output Formats
 (Parallel via Rayon)          (5-Level Name Resolution)     (ANSI / Pager / JSON)

---

1. Repository Target Resolution & File Extraction

symtrace uses libgit2 in-process (zero shell-outs) to resolve target commit refs, staged index entries, or working tree state.

• Positional Defaults — Missing arguments automatically default:
  • REPO_PATH → . (current directory)
  • COMMIT_A → HEAD~1
  • COMMIT_B → Working tree (or HEAD if --staged is set)
• Dual-Path Git Rename Tracking — For file rename events, symtrace retains both old_path and new_path across commit snapshots.
• Path Glob Filtering — When --path <GLOB> is provided, symtrace filters FileChange items against standard glob patterns before tree parsing.

---

2. AST Parsing & Two-Tier Caching

For each changed file, symtrace parses both the old and new file contents into concrete syntax trees using language-specific Tree-sitter grammars.

Bounded Arena Allocation (bumpalo)

Syntax trees are constructed using thread-local bumpalo arena allocators, achieving zero heap allocation overhead during tree traversal.

Two-Tier Caching Strategy

1. In-Memory TreeCache LRU — An in-memory LRU cache (500 tree capacity) retains recently parsed AST trees for instant reuse during multi-file passes.
2. On-Disk Versioned AST Cache — Parsed AST data is cached on disk using binary bincode serialization. Cache keys combine the blob BLAKE3 content hash with resource limit parameters (max_file_size, max_ast_nodes, max_recursion_depth) to guarantee cache invalidation when limits change.

---

3. Four-Hash BLAKE3 Node Fingerprinting

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

---

4. Five-Phase Node Matching Algorithm

Matching operates in 5 progressive phases executed concurrently across files using rayon data parallelism:

Phase 1: Exact Identity & Content Hash Match
               │
               ▼
Phase 2: Structural Hash & Parent Context Match
               │
               ▼
Phase 3: Semantic Similarity Scoring (Structure + Token + Complexity)
               │
               ▼
Phase 4: Name & Scope Resolution Match
               │
               ▼
Phase 5: Unmatched Leftovers Classification (INSERT / DELETE)

1. Phase 1: Exact Hash Match — Nodes with identical identity and content hashes are paired immediately as 100% matches.
2. Phase 2: Structural & Context Match — Nodes sharing structural hashes and parent context are paired as MOVE operations.
3. Phase 3: Similarity Scoring — Candidate pairs undergo tri-factor similarity evaluation (structural similarity, token edit distance, and cyclomatic complexity delta). Pairs exceeding threshold score are matched as MODIFY or RENAME.
4. Phase 4: Name Resolution — Deep BFS name tracking pairs functions or methods whose names match across scope shifts.
5. Phase 5: Leftover Classification — Remaining unpaired nodes in COMMIT_A are tagged as DELETE; remaining unpaired nodes in COMMIT_B are tagged as INSERT.

---

5. Refactor Pattern & Symbol Tracking

After node matching, symtrace performs cross-file analysis:

• Extract Method / Move Method — Detects when statements inside a function are extracted into a new helper function or moved to a different module.
• Cross-File Symbol Movement — Tracks functions, classes, or types relocated between separate files.
• Commit Auto-Classification — Evaluates net operation counts and similarity intensity to classify commit intent:
  • formatting_only (100% structural match, formatting changes only)
  • refactor (high move/rename count, high similarity)
  • feature (high insert count, new entities)
  • bugfix (low modification count, localized diff)
  • cleanup (high deletion count)

---

6. Output Pipeline & Shell Paging

Finally, results are formatted and emitted:

• TTY Pager Integration — When running in an interactive terminal, symtrace automatically forks $GIT_PAGER or $PAGER (defaulting to less -RFX) for seamless scrolling.
• ANSI Color Modes — --color <auto|always|never> controls ANSI color rendering while respecting NO_COLOR environment variables.
• Structured JSON — --json emits machine-readable JSON containing full per-file operations, refactor patterns, cross-file events, commit classification, and performance telemetry.