Line Diff With an LCS Algorithm

function splitLines(text) {
  const lines = text.replace(/\r\n/g, "\n").split("\n");
  if (lines.length > 0 && lines[lines.length - 1] === "") lines.pop();
  return lines;
}

export function diffLines(before, after) {
  if (typeof before !== "string" || typeof after !== "string") {
    throw new TypeError("before and after must be strings");
  }
  const left = splitLines(before);
  const right = splitLines(after);
  const table = Array.from(
    { length: left.length + 1 },
    () => new Int32Array(right.length + 1),
  );

  for (let row = left.length - 1; row >= 0; row -= 1) {
    for (let column = right.length - 1; column >= 0; column -= 1) {
      table[row][column] =
        left[row] === right[column]
          ? table[row + 1][column + 1] + 1
          : Math.max(table[row + 1][column], table[row][column + 1]);
    }
  }

  const operations = [];
  let row = 0;
  let column = 0;
  while (row < left.length && column < right.length) {
    if (left[row] === right[column]) {
      operations.push({ type: "equal", line: left[row] });
      row += 1;
      column += 1;
    } else if (table[row + 1][column] >= table[row][column + 1]) {
      operations.push({ type: "delete", line: left[row] });
      row += 1;
    } else {
      operations.push({ type: "insert", line: right[column] });
      column += 1;
    }
  }
  while (row < left.length) {
    operations.push({ type: "delete", line: left[row] });
    row += 1;
  }
  while (column < right.length) {
    operations.push({ type: "insert", line: right[column] });
    column += 1;
  }
  return operations;
}

export function diffStats(operations) {
  const stats = { equal: 0, delete: 0, insert: 0 };
  for (const operation of operations) {
    if (!(operation.type in stats)) {
      throw new TypeError(`unknown operation: ${operation.type}`);
    }
    stats[operation.type] += 1;
  }
  return stats;
}

const before = "alpha\nbeta\ngamma\ndelta";
const after = "alpha\nbeta changed\ngamma\ndelta\nepsilon";
const operations = diffLines(before, after);
for (const operation of operations) {
  console.log(`${operation.type.padEnd(6)} ${operation.line}`);
}
console.log(diffStats(operations));