Similarity Scoring

When symtrace matches a code node across two commits (as a MOVE, RENAME, or MODIFY), it reports a high-precision similarity score alongside a change intensity rating.

Multi-Factor Scoring Formulation

The similarity score combines four structural and token-level metrics:

1. Structural Subtree Shape (40%): Compares AST tree nesting, arity, child node sequence, and unnamed operator tokens (=, +=, -=, *=, /=, ==, !=, ->).
2. SIMD Multiset Token Jaccard (30%): Evaluates token bag-of-words overlap accelerated by 64-bit bitset pre-filtering (token_bitset) and 16-bin SIMD histogram comparisons (simd_jaccard_histogram_16).
3. Positional Displacement (15%): Evaluates token displacement penalty to detect reordered statements vs true logic edits.
4. Cyclomatic Complexity (15%): Quantifies control flow shifts (branches, conditions, match arms, loop nests).

Similarity Score = (40% * Structure Shape) + (30% * Token Similarity) + (15% * Position Match) + (15% * Complexity Match)

Change Intensity Classification

The aggregate similarity percentage maps directly to change intensity:

Similarity Score	Intensity	Diagnostic Meaning
80% to 100%	low	Minor adjustment or cosmetic rename: safe refactor
50% to 79%	medium	Concrete modification: requires code review
Below 50%	high	Significant logic overhaul or rewrite

SIMD Hardware Acceleration

symtrace computes Multiset Token Jaccard similarity using AVX2 and SSE2 vector instructions:

• 64-Bit Bitset Filtering: Fast bitwise AND + popcount pre-checks node similarity before allocating token vectors.
• 16-Bin SIMD Frequency Histograms: Vectorized min/max frequency operations evaluate token overlaps in under 50 ns per pair.

Output Representation

CLI Text Output

~ [MODIFY] function_item 'parse_body' modified (L10 -> L10) [75% similarity, medium]
✎ [RENAME] function_item renamed from 'process' to 'execute' (L5 -> L5) [98% similarity, low]
↔ [MOVE]   function_item 'helper' moved (L20 -> L35) [100% similarity, low]

JSON / SARIF Representation

{
  "similarityPercent": 75.2,
  "changeIntensity": "medium",
  "structureSimilarity": 0.84,
  "tokenSimilarity": 0.61,
  "controlFlowChanged": true
}

Key Invariants

• [INSERT] and [DELETE] operations omit similarity scores (there is no paired node).
• A [MOVE] with 100% similarity proves code was relocated without a single character or logic change.
• A [RENAME] with 95% or higher similarity and identical def-use data flow verifies a safe identifier rename.