/**
 * A line diff for the review queue and history: what a change adds and
 * removes, with unchanged lines folded down to a little context.
 */
export type DiffLine = { kind: "same" | "add" | "remove"; text: string } | { kind: "skip"; count: number };

/** Notes are short, so a plain longest-common-subsequence table is enough. */
const MAX_CELLS = 4_000_000;

export function diffLines(before: string, after: string, context = 3): DiffLine[] {
  const a = before === "" ? [] : before.replace(/\r\n/g, "\n").split("\n");
  const b = after === "" ? [] : after.replace(/\r\n/g, "\n").split("\n");
  let full: DiffLine[];
  if (a.length * b.length > MAX_CELLS) {
    // Too large to compare line by line: show it as replaced.
    full = [...a.map((text) => ({ kind: "remove" as const, text })), ...b.map((text) => ({ kind: "add" as const, text }))];
  } else {
    const n = a.length;
    const m = b.length;
    const lcs = Array.from({ length: n + 1 }, () => new Uint32Array(m + 1));
    for (let i = n - 1; i >= 0; i--) {
      for (let j = m - 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]!);
      }
    }
    full = [];
    let i = 0;
    let j = 0;
    while (i < n && j < m) {
      if (a[i] === b[j]) {
        full.push({ kind: "same", text: a[i]! });
        i++;
        j++;
      } else if (lcs[i + 1]![j]! >= lcs[i]![j + 1]!) full.push({ kind: "remove", text: a[i++]! });
      else full.push({ kind: "add", text: b[j++]! });
    }
    while (i < n) full.push({ kind: "remove", text: a[i++]! });
    while (j < m) full.push({ kind: "add", text: b[j++]! });
  }
  return fold(full, context);
}

function fold(lines: DiffLine[], context: number): DiffLine[] {
  const changed = lines.map((l) => l.kind !== "same");
  const keep = lines.map((_, i) => {
    for (let k = Math.max(0, i - context); k <= Math.min(lines.length - 1, i + context); k++) if (changed[k]) return true;
    return false;
  });
  const out: DiffLine[] = [];
  let skipped = 0;
  lines.forEach((l, i) => {
    if (keep[i]) {
      if (skipped) out.push({ kind: "skip", count: skipped });
      skipped = 0;
      out.push(l);
    } else skipped++;
  });
  if (skipped) out.push({ kind: "skip", count: skipped });
  return out;
}