Text Diff Algorithms: Myers, Patience, Histogram, and the Edit Graph Model

Example: A = "ABCABBA", B = "CBABAC"

     C  B  A  B  A  C
  0──1──2──3──4──5──6
  |  |╲ |  |  |  |  |
A 1──.──.──╲──.──╲──.
  |  |  |╲ |  |  |  |
B 2──.──╲──.──╲──.──.
  |╲ |  |  |  |  |╲ |
C 3──╲──.──.──.──.──╲
  |  |  |╲ |  |╲ |  |
A 4──.──.──╲──.──╲──.
  |  |╲ |  |╲ |  |  |
B 5──.──╲──.──╲──.──.
  |  |╲ |  |╲ |  |  |
B 6──.──╲──.──╲──.──.
  |  |  |╲ |  |╲ |  |
A 7──.──.──╲──.──╲──.

Diagonal = free match
Horizontal = insert from B
Vertical = delete from A

def myers_diff(a: list, b: list) -> list:
    n, m = len(a), len(b)
    max_d = n + m
    
    v = {1: 0}
    trace = []
    
    for d in range(max_d + 1):
        trace.append(dict(v))
        for k in range(-d, d + 1, 2):
            if k == -d or (k != d and v.get(k - 1, 0) < v.get(k + 1, 0)):
                x = v.get(k + 1, 0)
            else:
                x = v.get(k - 1, 0) + 1
            
            y = x - k
            
            while x < n and y < m and a[x] == b[y]:
                x += 1
                y += 1
            
            v[k] = x
            
            if x >= n and y >= m:
                return _backtrack(trace, a, b, n, m, d)
    
    return []


def _backtrack(trace, a, b, n, m, d_final):
    edits = []
    x, y = n, m
    
    for d in range(d_final, 0, -1):
        v = trace[d]
        k = x - y
        
        if k == -d or (k != d and v.get(k - 1, 0) < v.get(k + 1, 0)):
            prev_k = k + 1
        else:
            prev_k = k - 1
        
        prev_x = v.get(prev_k, 0)
        prev_y = prev_x - prev_k
        
        while x > prev_x and y > prev_y:
            edits.append(('equal', a[x - 1]))
            x -= 1
            y -= 1
        
        if x == prev_x:
            edits.append(('insert', b[y - 1]))
            y -= 1
        else:
            edits.append(('delete', a[x - 1]))
            x -= 1
    
    while x > 0 and y > 0:
        edits.append(('equal', a[x - 1]))
        x -= 1
        y -= 1
    
    edits.reverse()
    return edits

// File A
void func_a() {
    int x = 1;
}

void func_b() {
    int x = 2;
}

// File B (func_a deleted)
void func_b() {
    int x = 2;
}

# Git with patience diff
git diff --patience
git config diff.algorithm patience

# Git's default algorithm since 2012
git diff --histogram
git config diff.algorithm histogram

--- a/src/auth.py
+++ b/src/auth.py
@@ -15,7 +15,9 @@ class AuthHandler:
     def validate_token(self, token: str) -> bool:
         """Validate JWT token."""
-        decoded = jwt.decode(token, self.secret)
-        return decoded is not None
+        try:
+            decoded = jwt.decode(token, self.secret, algorithms=["HS256"])
+            return not self._is_expired(decoded)
+        except jwt.InvalidTokenError:
+            return False
 
     def refresh_token(self, token: str) -> str:

import difflib

def unified_diff(text_a: str, text_b: str, filename: str = "file") -> str:
    lines_a = text_a.splitlines(keepends=True)
    lines_b = text_b.splitlines(keepends=True)
    
    diff = difflib.unified_diff(
        lines_a, lines_b,
        fromfile=f"a/{filename}",
        tofile=f"b/{filename}",
        lineterm=""
    )
    return "".join(diff)

     Base (ancestor)
      /         \
   Ours          Theirs
(our changes)  (their changes)
      \         /
       Merged

<<<<<<< HEAD (ours)
    return validate_strict(token)
=======
    return validate_lenient(token)
>>>>>>> feature-branch (theirs)

def three_way_merge(base: list, ours: list, theirs: list):
    diff_ours = myers_diff(base, ours)
    diff_theirs = myers_diff(base, theirs)
    
    result = []
    conflicts = []
    
    # Walk both diffs simultaneously, detecting overlapping changes
    # Regions where both modify the same base lines → conflict
    # Non-overlapping changes → auto-merge
    ...
    
    return result, conflicts

# Text diff sees 3 changed lines:
- x = foo(a, b, c)
+ x = foo(
+     a,
+     b,
+     c
+ )

# AST diff sees: no change (same function call, same arguments)

// Text diff: 2 lines changed
- {"name": "Alice", "age": 30}
+ {"age": 30, "name": "Alice"}

// Structural diff: no change (same object)

import hashlib

def diff_large_files(path_a: str, path_b: str):
    def hash_lines(path):
        with open(path) as f:
            return [hashlib.md5(line.encode()).digest() for line in f]
    
    hashes_a = hash_lines(path_a)
    hashes_b = hash_lines(path_b)
    
    # Diff the hash sequences (integer comparison, not string)
    edits = myers_diff(hashes_a, hashes_b)
    return edits

def trim_common(a: list, b: list):
    prefix = 0
    while prefix < len(a) and prefix < len(b) and a[prefix] == b[prefix]:
        prefix += 1
    
    suffix = 0
    while (suffix < len(a) - prefix and suffix < len(b) - prefix 
           and a[-(suffix + 1)] == b[-(suffix + 1)]):
        suffix += 1
    
    core_a = a[prefix:len(a) - suffix] if suffix else a[prefix:]
    core_b = b[prefix:len(b) - suffix] if suffix else b[prefix:]
    
    return prefix, suffix, core_a, core_b

def lcs_length(a: list, b: list) -> int:
    m, n = len(a), len(b)
    # Space-optimized: only two rows
    prev = [0] * (n + 1)
    curr = [0] * (n + 1)
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                curr[j] = prev[j - 1] + 1
            else:
                curr[j] = max(prev[j], curr[j - 1])
        prev, curr = curr, [0] * (n + 1)
    
    return prev[n]

def levenshtein(a: str, b: str) -> int:
    m, n = len(a), len(b)
    prev = list(range(n + 1))
    
    for i in range(1, m + 1):
        curr = [i] + [0] * n
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                curr[j] = prev[j - 1]
            else:
                curr[j] = 1 + min(prev[j], curr[j - 1], prev[j - 1])
        prev = curr
    
    return prev[n]