I Built a Text Diff Tool in Pure Vanilla JS — Myers Algorithm from Scratch, 129 Tests, Zero Dependencies

#webdev #javascript #tools #opensource

Every developer ends up needing to compare two blocks of text at some point — a config before and after an edit, two versions of a log file, or just "what exactly changed between these two pastes?" Most tools either require a server round-trip or pull in a 200KB library.

I built one that runs entirely in the browser, with no dependencies, and implements the Myers diff algorithm from scratch.

👉 https://text-diff-60y.pages.dev

What It Does

Side-by-side view — original on the left, modified on the right, with line numbers
Unified view — traditional +/- format in a single pane
Real-time diffing — results update as you type, no button press needed
Color coding — additions in green, deletions in red
Diff statistics — "+N added / −N removed" badge in the toolbar
Copy diff — one click copies the full diff as unified text
Zero dependencies — single HTML file, no npm, no build step

The Algorithm: Myers Diff

The classic "diff" algorithm used in git diff, GNU diff, and most modern diff tools is the Myers diff algorithm, published by Eugene Myers in 1986. It finds the shortest edit script between two sequences — the minimum number of insertions and deletions to transform A into B.

The core insight: represent the diff problem as finding the shortest path through an edit graph where:

Moving right = delete a line from A
Moving down = insert a line from B
Moving diagonally = lines match (free move)

The algorithm explores diagonal "snakes" (sequences of matching lines) greedily, expanding by edit distance d = 0, 1, 2, ... until it reaches the bottom-right corner (n, m).

function myersDiff(a, b) {
  const n = a.length, m = b.length;
  const max = n + m;
  const v = new Int32Array(2 * max + 1);
  const trace = [];
  const offset = max;

  outer:
  for (let d = 0; d <= max; d++) {
    trace.push(new Int32Array(v));
    for (let k = -d; k <= d; k += 2) {
      let x = (k === -d || (k !== d && v[offset+k-1] < v[offset+k+1]))
        ? v[offset+k+1]
        : v[offset+k-1] + 1;
      let y = x - k;
      while (x < n && y < m && a[x] === b[y]) { x++; y++; }
      v[offset+k] = x;
      if (x >= n && y >= m) { trace.push(new Int32Array(v)); break outer; }
    }
  }
  // ... backtrack through trace to reconstruct ops
}

The tricky part is the backtracking phase. After finding the minimum edit distance D, you replay the trace in reverse to recover the actual sequence of insertions and deletions. Each step looks at V_{d-1} (the saved state from the previous edit depth) to determine whether the path came from an insert or a delete.

The backtrack bug that tripped me up: the trace array stores V_{d-1} at trace[d] (pushed before processing depth d), plus a final snapshot after finding the goal. So D = trace.length - 2, and the loop runs from d = D down to 1, using trace[d] as V_{d-1}. After the loop, any remaining diagonal from (x, y) back to (0, 0) is the d=0 snake (the longest common prefix).

Implementation Details

The whole thing is a single index.html — no bundler, no framework, no runtime dependencies.

Rendering: Two modes share the same diff output. Side-by-side uses a fixed-layout table with four columns (line number, content, divider, line number, content). Unified uses a three-column table (old line number, new line number, sign, content). HTML is escaped before insertion to prevent XSS from user-pasted content.

Performance: For typical developer use cases (config files, code snippets, log excerpts — up to a few thousand lines), the O(ND) algorithm is fast enough for real-time updates on every keystroke. For very large inputs the browser's event loop keeps things responsive.

Copy: Uses navigator.clipboard.writeText with a document.execCommand('copy') fallback for older browsers.

Testing

129 tests, all passing, using only Node.js assert — no test framework:

§1  myersDiff — edge cases         (20 tests)
§2  computeDiff — basic            (16 tests)
§3  computeDiff — counts           (10 tests)
§4  esc() — HTML escaping          (17 tests)
§5  myersDiff — larger inputs      (11 tests)
§6  computeDiff — special content  (10 tests)
§7  single vs multi-line           ( 5 tests)
§8  empty lines and whitespace     ( 7 tests)
§9  line number correctness        ( 6 tests)
§10 esc() edge cases               ( 6 tests)
§11 real-world diff scenarios      ( 8 tests)
§12 additional coverage            (13 tests)

Tests cover: empty inputs, identical inputs, pure insertions, pure deletions, changes in various positions, unicode, emoji, very long lines, Windows line endings, HTML content, JSON, CSS, code snippets, config files, and determinism checks.

What I Learned

Implementing Myers from scratch taught me a few things:

The trace is subtle. The algorithm stores a snapshot of V before each edit depth d. When you break early (goal found mid-loop), you push an extra snapshot. So D = trace.length - 2, not trace.length - 1. Off by one here causes identical strings to look like they have one deletion.
In-place V updates are safe. Within a single d level, k jumps by 2. So k=-1 writes to v[offset-1] and k=1 reads from v[offset+0] and v[offset+2] — no aliasing.
Backtrack uses V_{d-1}, not V_d. To determine whether a move was an insert or delete at depth d, you compare entries in the previous V array (trace[d]), not the current one.