Function buildEditScript

src/cache/diff-engine.ts:49–80

Walk the LCS DP table backwards to produce an ordered edit script.

(oldLines: string[], newLines: string[])

/** Walk the LCS DP table backwards to produce an ordered edit script. */
function buildEditScript(oldLines: string[], newLines: string[]): EditOp[] {
  const m = oldLines.length;
  const n = newLines.length;
  const stride = n + 1;
  const dp = computeLcsTable(oldLines, newLines);
  const ops: EditOp[] = [];
  let i = m;
  let j = n;
  while (i > 0 && j > 0) {
    if (oldLines[i - 1] === newLines[j - 1]) {
      ops.push({ type: 'equal', oldLine: oldLines[i - 1], newLine: newLines[j - 1] });
      i--;
      j--;
    } else if (dp[(i - 1) * stride + j] >= dp[i * stride + (j - 1)]) {
      ops.push({ type: 'delete', oldLine: oldLines[i - 1] });
      i--;
    } else {
      ops.push({ type: 'insert', newLine: newLines[j - 1] });
      j--;
    }
  }
  while (i > 0) {
    ops.push({ type: 'delete', oldLine: oldLines[i - 1] });
    i--;
  }
  while (j > 0) {
    ops.push({ type: 'insert', newLine: newLines[j - 1] });
    j--;
  }
  ops.reverse();
  return ops;
}

function countsFromOps(ops: EditOp[]): { added: number; removed: number; modified: number } {
  // Pair adjacent delete+insert runs as "modified" — git's default semantics.