Matching Algorithm

symtrace v0.5.0 uses a 6-Stage AST Matching Pipeline alongside a Global Multi-File AST Node Index (GlobalNodeIndex) to match AST nodes across all modified files simultaneously at O(N log N) complexity.

Global Multi-File Index

Instead of comparing files in isolation, symtrace indexes all parsed AST nodes across the entire changeset concurrently using Rayon:

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>>,
}

This allows cross-file MOVE and RENAME operations to be detected directly during primary matching.

6-Stage Matching Pipeline

Stage 1: Fast-Path Isomorphic Micro-Edit Match
  Structurally identical ASTs (ast_a.structural_hash == ast_b.structural_hash):
    Pair isomorphic nodes in linear O(N) scan -> (under 0.1 ms latency)

Stage 2: Token Multiset Bitset & SIMD Frequency Jaccard
  Filter candidate node pairs:
    64-bit token_bitset pre-filtering
    16-bin SIMD frequency histogram (simd_jaccard_histogram_16)

Stage 3: Topological Data-Flow Isomorphism
  Verify def-use variable chains (analyze_intra_procedural_data_flow):
    Preserved def-use topology -> Cosmetic Variable RENAME
    Mutated def-use lineage    -> Functional Logic MODIFY

Stage 4: Subtree Windowing & Candidate Pruning
  Bounded recursive descent on large files (> 1 MiB):
    Push hunk line boundaries into AST collection -> (95% RAM reduction)

Stage 5: Global Node Index Candidate Search (O(N log N))
  Multi-file structural hash lookups across the repository:
    Same shape, different file  -> CROSS-FILE MOVE
    Same shape, changed name    -> RENAME
    Moderate similarity         -> MODIFY

Stage 6: Hash-Indexed Symbol Tracking (O(M + N))
  Hash-bucket symbol table lookups for remaining unmatched items:
    Unmatched old nodes         -> DELETE
    Unmatched new nodes         -> INSERT

Stage Details

Stage 1: Fast-Path Isomorphic Micro-Edit Match

When an entire AST’s structural hash matches between commits, symtrace executes a linear 1:1 pairwise scan to locate exact micro-edits, delivering sub-millisecond diff results.

Stage 2: Token Multiset Bitset & SIMD Frequency Jaccard

Candidate nodes are pre-filtered via 64-bit bitset popcounts and scored via 16-bin SIMD vector histograms, bypassing heavy string diffs.

Stage 3: Topological Data-Flow Isomorphism

Intra-procedural def-use variable tracking verifies whether identifier renames alter data flow or preserve functional equivalence.

Stage 4: Subtree Windowing & Pruning

For files exceeding 1 MiB, recursive AST traversal prunes subtrees outside Git diff hunk bounds, ensuring bounded diff time.

Stage 5 & 6: Global Node Graph & Leftover Classification

Remaining candidates are resolved through global multi-file hash tables. Unpaired old nodes are classified as [DELETE]; unpaired new nodes are classified as [INSERT].

Determinism & Soundness

The algorithm is 100% deterministic: identical code inputs always produce identical AST diff operations across platforms. Verified with 332 automated invariant tests.