Inside Git Diff: The Myers Diff Algorithm & Text Reconciliation

At the heart of every code review tool, Git commit view, and collaborative document editor lies the Shortest Edit Script (SES) problem. Given two sequences of characters or lines (original sequence A of length N, and modified sequence B of length M), find the minimum number of deletion and insertion operations required to transform A into B.

The SES problem is dual to the Longest Common Subsequence (LCS) problem: any element that is preserved between sequences belongs to the LCS, while non-common elements represent necessary additions or deletions.

In 1986, Eugene W. Myers published "An O(ND) Difference Algorithm and Its Variations", which became the default diff engine in GNU diff and Git. Myers visualized the comparison as finding the shortest path across an Edit Graph:

• The X-axis represents tokens in sequence A (deletions are horizontal moves (x+1, y)).
• The Y-axis represents tokens in sequence B (insertions are vertical moves (x, y+1)).
• Whenever tokens at index x and y match identical characters or lines, a diagonal move (x+1, y+1) is granted at zero cost.

Myers discovered that the search can be structured around diagonals k = x - y. By iteratively exploring search depths D, the algorithm executes in O((N+M)D) time and O(N+M) space, running lightning-fast when differences D are small.

• Line-Based Diff: Standard Git diff compares files line-by-line. This is computationally fast and maps cleanly to source code lines, but changing a single variable name inside an 80-character line highlights the entire line as deleted and re-added.
• Word-Level / Character-Level Diff: Performs a secondary Myers diff pass solely on the substrings of modified lines, highlighting specific token replacements in green and red.
• Semantic / AST Diffing: Compares Abstract Syntax Trees. It recognizes when a function was simply relocated to another file or reformatted without altering execution semantics, eliminating noise in code reviews.

// Unified Diff Format Example:
--- original.js
+++ modified.js
@@ -1,4 +1,4 @@
 function calculateTax(amount) {
-    const rate = 0.08;
+    const rate = 0.095; // Updated state tax rate
     return amount * rate;
 }

When two developers branch from a common commit (the Base Ancestor) and submit concurrent changes, Git utilizes a 3-Way Merge algorithm:

1. It compares Base to Branch A (diff(Base, A)).
2. It compares Base to Branch B (diff(Base, B)).
3. If Branch A modified lines 10–15 while Branch B modified lines 80–90, Git cleanly merges both changes.

However, if both branches modify overlapping line chunks relative to the Base ancestor, Git halts automatic merging and emits conflict markers (<<<<<<< HEAD, =======, >>>>>>> branch), requiring human intervention.

Running diff algorithms in client-side web applications requires memory management. For files exceeding tens of thousands of lines, hashing each unique line to an integer identifier allows Myers' diagonal search to compare fast 32-bit integers rather than heavy strings. Test and compare payloads locally using the DevUtils Diff Checker.

// Fast line-to-integer hashing for browser Myers diff
export function prepareDiffTokens(text) {
    const lines = text.split(/\r?\n/);
    const internMap = new Map();
    const tokenIds = [];
    
    for (const line of lines) {
        if (!internMap.has(line)) {
            internMap.set(line, internMap.size);
        }
        tokenIds.push(internMap.get(line));
    }
    return { tokenIds, internMap, lines };
}