lineDiff

tcmts.cli.diff.lineDiff · #3s2elzfk · term · runs anywhere

Longest-common-subsequence line diff. Definitions are short, so O(n·m) is fine.

export function lineDiff(a: string[], b: string[]): [" " | "-" | "+", string][] {
  const lcs = Array.from({ length: a.length + 1 }, () =>
    Array.from({ length: b.length + 1 }, () => 0),
  );
  for (let i = a.length - 1; i >= 0; i--) {
    for (let j = b.length - 1; j >= 0; j--)
      lcs[i]![j] =
        a[i] === b[j] ? lcs[i + 1]![j + 1]! + 1 : Math.max(lcs[i + 1]![j]!, lcs[i]![j + 1]!);
  }
  const out: [" " | "-" | "+", string][] = [];
  let i = 0;
  let j = 0;
  while (i < a.length || j < b.length) {
    if (i < a.length && j < b.length && a[i] === b[j]) {
      out.push([" ", a[i]!]);
      i++;
      j++;
    }
    // on ties, removals come first so old lines print above their replacements
    else if (i < a.length && (j === b.length || lcs[i + 1]![j]! >= lcs[i]![j + 1]!))
      out.push(["-", a[i++]!]);
    else out.push(["+", b[j++]!]);
  }
  return out;
}

used by