export type DiffLine =
  | { kind: "equal"; text: string }
  | { kind: "add"; text: string }
  | { kind: "remove"; text: string };

export interface FileDiffInput {
  path: string;
  before: string | null;
  after: string | null;
}

export interface FileDiffResult {
  path: string;
  added: number;
  removed: number;
  text: string;
}

function splitLines(value: string): string[] {
  if (value.length === 0) return [];
  return value.replace(/\r\n/g, "\n").split("\n");
}

function coarseDiff(before: string[], after: string[]): DiffLine[] {
  let prefix = 0;
  while (
    prefix < before.length &&
    prefix < after.length &&
    before[prefix] === after[prefix]
  ) {
    prefix++;
  }
  let suffix = 0;
  while (
    suffix < before.length - prefix &&
    suffix < after.length - prefix &&
    before[before.length - 1 - suffix] === after[after.length - 1 - suffix]
  ) {
    suffix++;
  }
  return [
    ...before.slice(0, prefix).map((text) => ({ kind: "equal" as const, text })),
    ...before
      .slice(prefix, before.length - suffix)
      .map((text) => ({ kind: "remove" as const, text })),
    ...after
      .slice(prefix, after.length - suffix)
      .map((text) => ({ kind: "add" as const, text })),
    ...before
      .slice(before.length - suffix)
      .map((text) => ({ kind: "equal" as const, text })),
  ];
}

export function diffLines(beforeText: string, afterText: string): DiffLine[] {
  const before = splitLines(beforeText);
  const after = splitLines(afterText);
  const cells = (before.length + 1) * (after.length + 1);
  if (cells > 4_000_000) return coarseDiff(before, after);

  const rows: Uint32Array[] = Array.from(
    { length: before.length + 1 },
    () => new Uint32Array(after.length + 1),
  );
  for (let i = before.length - 1; i >= 0; i--) {
    const row = rows[i];
    const next = rows[i + 1];
    for (let j = after.length - 1; j >= 0; j--) {
      row[j] =
        before[i] === after[j]
          ? next[j + 1] + 1
          : Math.max(next[j], row[j + 1]);
    }
  }

  const out: DiffLine[] = [];
  let i = 0;
  let j = 0;
  while (i < before.length && j < after.length) {
    if (before[i] === after[j]) {
      out.push({ kind: "equal", text: before[i] });
      i++;
      j++;
    } else if (rows[i + 1][j] >= rows[i][j + 1]) {
      out.push({ kind: "remove", text: before[i++] });
    } else {
      out.push({ kind: "add", text: after[j++] });
    }
  }
  while (i < before.length) out.push({ kind: "remove", text: before[i++] });
  while (j < after.length) out.push({ kind: "add", text: after[j++] });
  return out;
}

type AnnotatedLine = DiffLine & {
  oldLine: number;
  newLine: number;
};

function annotate(lines: DiffLine[]): AnnotatedLine[] {
  let oldLine = 1;
  let newLine = 1;
  return lines.map((line) => {
    const annotated: AnnotatedLine = { ...line, oldLine, newLine };
    if (line.kind !== "add") oldLine++;
    if (line.kind !== "remove") newLine++;
    return annotated;
  });
}

function hunkRanges(lines: AnnotatedLine[], context: number): Array<[number, number]> {
  const changed: number[] = [];
  lines.forEach((line, index) => {
    if (line.kind !== "equal") changed.push(index);
  });
  if (changed.length === 0) return [];
  const ranges: Array<[number, number]> = [];
  let start = Math.max(0, changed[0] - context);
  let end = Math.min(lines.length, changed[0] + context + 1);
  for (const index of changed.slice(1)) {
    const nextStart = Math.max(0, index - context);
    const nextEnd = Math.min(lines.length, index + context + 1);
    if (nextStart <= end) {
      end = Math.max(end, nextEnd);
    } else {
      ranges.push([start, end]);
      start = nextStart;
      end = nextEnd;
    }
  }
  ranges.push([start, end]);
  return ranges;
}

function rangeCount(
  lines: AnnotatedLine[],
  start: number,
  end: number,
  side: "old" | "new",
): number {
  return lines.slice(start, end).filter((line) =>
    side === "old" ? line.kind !== "add" : line.kind !== "remove",
  ).length;
}

export function createFileDiff(input: FileDiffInput, context = 3): FileDiffResult {
  const before = input.before ?? "";
  const after = input.after ?? "";
  const lines = annotate(diffLines(before, after));
  const added = lines.filter((line) => line.kind === "add").length;
  const removed = lines.filter((line) => line.kind === "remove").length;
  if (added === 0 && removed === 0) {
    return { path: input.path, added: 0, removed: 0, text: "" };
  }
  const oldName = input.before === null ? "/dev/null" : `a/${input.path}`;
  const newName = input.after === null ? "/dev/null" : `b/${input.path}`;
  const output: string[] = [`--- ${oldName}`, `+++ ${newName}`];
  for (const [start, end] of hunkRanges(lines, context)) {
    const first = lines[start];
    const oldStart = first?.oldLine ?? 1;
    const newStart = first?.newLine ?? 1;
    const oldCount = rangeCount(lines, start, end, "old");
    const newCount = rangeCount(lines, start, end, "new");
    output.push(`@@ -${oldStart},${oldCount} +${newStart},${newCount} @@`);
    for (const line of lines.slice(start, end)) {
      const prefix = line.kind === "equal" ? " " : line.kind === "add" ? "+" : "-";
      output.push(`${prefix}${line.text}`);
    }
  }
  return { path: input.path, added, removed, text: `${output.join("\n")}\n` };
}

export function createMultiFileDiff(inputs: FileDiffInput[]): {
  text: string;
  files: FileDiffResult[];
  added: number;
  removed: number;
} {
  const files = inputs
    .map((input) => createFileDiff(input))
    .filter((result) => result.added > 0 || result.removed > 0);
  return {
    text: files.map((file) => file.text).join("\n"),
    files,
    added: files.reduce((sum, file) => sum + file.added, 0),
    removed: files.reduce((sum, file) => sum + file.removed, 0),
  };
}

export type DiffLine =
  | { kind: "equal"; text: string }
  | { kind: "add"; text: string }
  | { kind: "remove"; text: string };

export interface FileDiffInput {
  path: string;
  before: string | null;
  after: string | null;
}

export interface FileDiffResult {
  path: string;
  added: number;
  removed: number;
  text: string;
}

function splitLines(value: string): string[] {
  if (value.length === 0) return [];
  return value.replace(/\r\n/g, "\n").split("\n");
}

function coarseDiff(before: string[], after: string[]): DiffLine[] {
  let prefix = 0;
  while (
    prefix < before.length &&
    prefix < after.length &&
    before[prefix] === after[prefix]
  ) {
    prefix++;
  }
  let suffix = 0;
  while (
    suffix < before.length - prefix &&
    suffix < after.length - prefix &&
    before[before.length - 1 - suffix] === after[after.length - 1 - suffix]
  ) {
    suffix++;
  }
  return [
    ...before.slice(0, prefix).map((text) => ({ kind: "equal" as const, text })),
    ...before
      .slice(prefix, before.length - suffix)
      .map((text) => ({ kind: "remove" as const, text })),
    ...after
      .slice(prefix, after.length - suffix)
      .map((text) => ({ kind: "add" as const, text })),
    ...before
      .slice(before.length - suffix)
      .map((text) => ({ kind: "equal" as const, text })),
  ];
}

export function diffLines(beforeText: string, afterText: string): DiffLine[] {
  const before = splitLines(beforeText);
  const after = splitLines(afterText);
  const cells = (before.length + 1) * (after.length + 1);
  if (cells > 4_000_000) return coarseDiff(before, after);

  const rows: Uint32Array[] = Array.from(
    { length: before.length + 1 },
    () => new Uint32Array(after.length + 1),
  );
  for (let i = before.length - 1; i >= 0; i--) {
    const row = rows[i];
    const next = rows[i + 1];
    for (let j = after.length - 1; j >= 0; j--) {
      row[j] =
        before[i] === after[j]
          ? next[j + 1] + 1
          : Math.max(next[j], row[j + 1]);
    }
  }

  const out: DiffLine[] = [];
  let i = 0;
  let j = 0;
  while (i < before.length && j < after.length) {
    if (before[i] === after[j]) {
      out.push({ kind: "equal", text: before[i] });
      i++;
      j++;
    } else if (rows[i + 1][j] >= rows[i][j + 1]) {
      out.push({ kind: "remove", text: before[i++] });
    } else {
      out.push({ kind: "add", text: after[j++] });
    }
  }
  while (i < before.length) out.push({ kind: "remove", text: before[i++] });
  while (j < after.length) out.push({ kind: "add", text: after[j++] });
  return out;
}

type AnnotatedLine = DiffLine & {
  oldLine: number;
  newLine: number;
};

function annotate(lines: DiffLine[]): AnnotatedLine[] {
  let oldLine = 1;
  let newLine = 1;
  return lines.map((line) => {
    const annotated: AnnotatedLine = { ...line, oldLine, newLine };
    if (line.kind !== "add") oldLine++;
    if (line.kind !== "remove") newLine++;
    return annotated;
  });
}

function hunkRanges(lines: AnnotatedLine[], context: number): Array<[number, number]> {
  const changed: number[] = [];
  lines.forEach((line, index) => {
    if (line.kind !== "equal") changed.push(index);
  });
  if (changed.length === 0) return [];
  const ranges: Array<[number, number]> = [];
  let start = Math.max(0, changed[0] - context);
  let end = Math.min(lines.length, changed[0] + context + 1);
  for (const index of changed.slice(1)) {
    const nextStart = Math.max(0, index - context);
    const nextEnd = Math.min(lines.length, index + context + 1);
    if (nextStart <= end) {
      end = Math.max(end, nextEnd);
    } else {
      ranges.push([start, end]);
      start = nextStart;
      end = nextEnd;
    }
  }
  ranges.push([start, end]);
  return ranges;
}

function rangeCount(
  lines: AnnotatedLine[],
  start: number,
  end: number,
  side: "old" | "new",
): number {
  return lines.slice(start, end).filter((line) =>
    side === "old" ? line.kind !== "add" : line.kind !== "remove",
  ).length;
}

export function createFileDiff(input: FileDiffInput, context = 3): FileDiffResult {
  const before = input.before ?? "";
  const after = input.after ?? "";
  const lines = annotate(diffLines(before, after));
  const added = lines.filter((line) => line.kind === "add").length;
  const removed = lines.filter((line) => line.kind === "remove").length;
  if (added === 0 && removed === 0) {
    return { path: input.path, added: 0, removed: 0, text: "" };
  }
  const oldName = input.before === null ? "/dev/null" : `a/${input.path}`;
  const newName = input.after === null ? "/dev/null" : `b/${input.path}`;
  const output: string[] = [`--- ${oldName}`, `+++ ${newName}`];
  for (const [start, end] of hunkRanges(lines, context)) {
    const first = lines[start];
    const oldStart = first?.oldLine ?? 1;
    const newStart = first?.newLine ?? 1;
    const oldCount = rangeCount(lines, start, end, "old");
    const newCount = rangeCount(lines, start, end, "new");
    output.push(`@@ -${oldStart},${oldCount} +${newStart},${newCount} @@`);
    for (const line of lines.slice(start, end)) {
      const prefix = line.kind === "equal" ? " " : line.kind === "add" ? "+" : "-";
      output.push(`${prefix}${line.text}`);
    }
  }
  return { path: input.path, added, removed, text: `${output.join("\n")}\n` };
}

export function createMultiFileDiff(inputs: FileDiffInput[]): {
  text: string;
  files: FileDiffResult[];
  added: number;
  removed: number;
} {
  const files = inputs
    .map((input) => createFileDiff(input))
    .filter((result) => result.added > 0 || result.removed > 0);
  return {
    text: files.map((file) => file.text).join("\n"),
    files,
    added: files.reduce((sum, file) => sum + file.added, 0),
    removed: files.reduce((sum, file) => sum + file.removed, 0),
  };
}