← snapshot

/**
 * A small line diff. Classic LCS over lines, which is more than enough for
 * the file sizes a milestone-1 in-memory store holds, and keeps the whole
 * detail view dependency-free.
 */

export type RowKind = "ctx" | "add" | "del";

export interface DiffRow {
  kind: RowKind;
  text: string;
  /** 1-based line number in the old file, when the row exists there. */
  a?: number;
  /** 1-based line number in the new file, when the row exists there. */
  b?: number;
}

export interface DiffStat {
  added: number;
  removed: number;
}

function lines(s: string): string[] {
  if (s === "") return [];
  return s.replace(/\n$/, "").split("\n");
}

/** Longest common subsequence table, then walk it back into rows. */
export function diffLines(before: string, after: string): DiffRow[] {
  const a = lines(before);
  const b = lines(after);
  const n = a.length;
  const m = b.length;

  // lcs[i][j] = length of LCS of a[i..] and b[j..]
  const lcs: number[][] = Array.from({ length: n + 1 }, () =>
    new Array<number>(m + 1).fill(0),
  );
  for (let i = n - 1; i >= 0; i--) {
    for (let j = m - 1; j >= 0; j--) {
      const row = lcs[i] as number[];
      const next = lcs[i + 1] as number[];
      row[j] = a[i] === b[j] ? (next[j + 1] as number) + 1 : Math.max(next[j] as number, row[j + 1] as number);
    }
  }

  const rows: DiffRow[] = [];
  let i = 0;
  let j = 0;
  while (i < n && j < m) {
    if (a[i] === b[j]) {
      rows.push({ kind: "ctx", text: a[i] as string, a: i + 1, b: j + 1 });
      i++;
      j++;
    } else if (((lcs[i + 1] as number[])[j] as number) >= ((lcs[i] as number[])[j + 1] as number)) {
      rows.push({ kind: "del", text: a[i] as string, a: i + 1 });
      i++;
    } else {
      rows.push({ kind: "add", text: b[j] as string, b: j + 1 });
      j++;
    }
  }
  while (i < n) {
    rows.push({ kind: "del", text: a[i] as string, a: i + 1 });
    i++;
  }
  while (j < m) {
    rows.push({ kind: "add", text: b[j] as string, b: j + 1 });
    j++;
  }
  return rows;
}

export function statOf(rows: DiffRow[]): DiffStat {
  return {
    added: rows.filter((r) => r.kind === "add").length,
    removed: rows.filter((r) => r.kind === "del").length,
  };
}

/**
 * Collapses long unchanged stretches, the way any reviewer would want.
 * Returns rows with `null` marking an elision.
 */
export function withElisions(rows: DiffRow[], context = 3): (DiffRow | null)[] {
  const keep = new Set<number>();
  rows.forEach((row, i) => {
    if (row.kind === "ctx") return;
    for (let k = i - context; k <= i + context; k++) {
      if (k >= 0 && k < rows.length) keep.add(k);
    }
  });
  // A file with no changes at all shows its head rather than nothing.
  if (keep.size === 0) {
    return rows.slice(0, 12).map((r) => r);
  }
  const out: (DiffRow | null)[] = [];
  let elided = false;
  rows.forEach((row, i) => {
    if (keep.has(i)) {
      out.push(row);
      elided = false;
    } else if (!elided) {
      out.push(null);
      elided = true;
    }
  });
  return out;
}