Hashing Strategy & CAS Caching

To track syntactic structures across commits with zero ambiguity, symtrace implements Two-Tier Content-Addressed Storage (CAS) Diff Caching at the repository layer and Four-Hash BLAKE3 Fingerprinting alongside 64-bit Token Bitsets at the AST node layer.

1. Two-Tier Content-Addressed Storage (CAS) Diff Cache

symtrace v0.5.0 caches completed FileDiff records keyed by the exact cryptographic identity of the input diff:

• Keying Scheme: DiffCacheKey = { old_blob_oid: [u8; 20], new_blob_oid: [u8; 20], logic_only: bool, limits_hash: u64 }
• Sub-Microsecond Warm Hit (under 0.004 ms): If both Git Blob OIDs and limits match, symtrace deserializes the cached diff immediately, skipping AST construction, SIMD vectorization, and graph matching.
• 16-Bucket RwLock Sharding: In-memory LRU cache is striped across 16 locks to eliminate worker thread contention in Rayon thread pools.
• Atomic Disk Commits: Cached files are written to temporary staging paths and renamed atomically, preventing partial cache corruptions on unexpected process exits.

2. The Four AST Node Hashes

Every AST node in the parse tree is annotated with 4 distinct SIMD-accelerated BLAKE3 hashes:

Hash	What it captures	Why it matters
Structural	The shape of the code (node types, children, and operator leaf tokens)	Detects moves: same shape, different location
Content	The raw token text content and literal values	Detects any source code text alteration
Identity	The shape with identifier names replaced by canonical placeholders	Detects renames: same structure, new variable names
Context	Parent node, preceding sibling, and following sibling hashes	Identifies code block surrounding scope

3. 64-Bit Token Bitset & SIMD Histograms

In addition to BLAKE3 hashes, each significant node computes:

• token_bitset (u64): A 64-bit bitset where each bit represents the presence of specific keyword/token classes, evaluated via hardware popcnt instructions.
• token_histogram_16 ([u8; 16]): A 16-bin frequency histogram vectorized with AVX2/SSE for fast multiset Jaccard candidate filtering.

4. Why Four Hashes + Bitsets?

A single fingerprint cannot distinguish between disparate kinds of code mutations. If a function is moved to another file and a variable inside is renamed:

• The structural hash matches -> candidate for MOVE or RENAME.
• The content hash differs -> not a byte-for-byte clone.
• The identity hash matches -> internal identifiers preserved or tracked via def-use data flow.
• The context hash differs -> confirms relocation to a new file or enclosing scope.

Combining all four fingerprints and token bitsets enables symtrace to isolate the exact semantic operation without falling back to noisy “deleted + inserted” line diffs.

5. Performance & Hardware SIMD

All hashes are computed with BLAKE3, leveraging AVX-512, AVX2, and ARM Neon SIMD intrinsics. Tree hashing throughput exceeds 4 GB/s per core, keeping total cold analysis latency under 30 ms on multi-file changesets.