/** Keeps the O(D^2) Myers trace to a few MB, well inside the Worker memory limit. */
const MAX_EDIT_DISTANCE = 1000;
/** Bounds total Myers work (diagonal visits plus snake steps) per file, since cost is O((N+M)·D). */
const MAX_DIFF_WORK = 4_000_000;
const MAX_MERGE_LINES = 50_000;
/** Total Myers work across every file of one merge (or of all merges sharing a budget). */
const MAX_TOTAL_DIFF_WORK = 20_000_000;

export type DiffBudget = { diffWork: number };
const NO_MATCH = -1;
const NEWLINE = 10;

export class MergeTooComplexError extends Error {}

/** Labels come from branch names; strip line breaks so a label can never forge a marker line. */
function markerLabel(label: string): string {
  return label.replace(/[\r\n]/g, " ");
}

/** Splits text into lines that keep their terminators, so joining them reproduces the input exactly. */
export function splitLines(text: string): string[] {
  const lines: string[] = [];
  let start = 0;
  for (let index = 0; index < text.length; index++) {
    if (text.charCodeAt(index) === NEWLINE) {
      lines.push(text.slice(start, index + 1));
      start = index + 1;
    }
  }
  if (start < text.length) lines.push(text.slice(start));
  return lines;
}

/**
 * Myers' O(ND) diff over interned lines, returning for each `left` index the matched `right` index
 * (or -1). Throws once the edit distance exceeds the budget so callers can fall back to real git.
 */
function lineMatches(left: number[], right: number[], budget: DiffBudget): Int32Array {
  const matches = new Int32Array(left.length).fill(NO_MATCH);
  let prefix = 0;
  while (prefix < left.length && prefix < right.length && left[prefix] === right[prefix]) {
    matches[prefix] = prefix;
    prefix++;
  }
  let suffix = 0;
  while (
    suffix < left.length - prefix &&
    suffix < right.length - prefix &&
    left[left.length - 1 - suffix] === right[right.length - 1 - suffix]
  ) {
    matches[left.length - 1 - suffix] = right.length - 1 - suffix;
    suffix++;
  }
  const a = left.slice(prefix, left.length - suffix);
  const b = right.slice(prefix, right.length - suffix);
  const n = a.length;
  const m = b.length;
  if (n === 0 || m === 0) return matches;

  const max = n + m;
  const offset = max + 1;
  const frontier = new Int32Array(2 * max + 3);
  const trace: Int32Array[] = [];
  let found = false;
  let work = 0;
  for (let depth = 0; depth <= max && !found; depth++) {
    if (depth > MAX_EDIT_DISTANCE) throw new MergeTooComplexError("Files differ too much to merge in the Worker");
    trace.push(frontier.slice(offset - depth - 1, offset + depth + 2));
    for (let k = -depth; k <= depth; k += 2) {
      let x =
        k === -depth || (k !== depth && frontier[offset + k - 1] < frontier[offset + k + 1])
          ? frontier[offset + k + 1]
          : frontier[offset + k - 1] + 1;
      let y = x - k;
      const startX = x;
      while (x < n && y < m && a[x] === b[y]) {
        x++;
        y++;
      }
      work += 1 + x - startX;
      budget.diffWork += 1 + x - startX;
      if (work > MAX_DIFF_WORK || budget.diffWork > MAX_TOTAL_DIFF_WORK)
        throw new MergeTooComplexError("Files differ too much to merge in the Worker");
      frontier[offset + k] = x;
      if (x >= n && y >= m) {
        found = true;
        break;
      }
    }
  }

  let x = n;
  let y = m;
  for (let depth = trace.length - 1; depth >= 0 && (x > 0 || y > 0); depth--) {
    const saved = trace[depth];
    const at = (k: number) => saved[k + depth + 1];
    const k = x - y;
    const down = k === -depth || (k !== depth && at(k - 1) < at(k + 1));
    const prevK = down ? k + 1 : k - 1;
    const prevX = depth === 0 ? 0 : at(prevK);
    const prevY = prevX - prevK;
    while (x > prevX && y > prevY) {
      x--;
      y--;
      matches[prefix + x] = prefix + y;
    }
    if (depth === 0) break;
    x = prevX;
    y = prevY;
  }
  return matches;
}

function intern(lines: string[], table: Map<string, number>): number[] {
  return lines.map((line) => {
    let id = table.get(line);
    if (id === undefined) {
      id = table.size;
      table.set(line, id);
    }
    return id;
  });
}

function sameLines(left: string[], right: string[]): boolean {
  return left.length === right.length && left.every((line, index) => line === right[index]);
}

function terminated(lines: string[]): string[] {
  const last = lines.at(-1);
  if (last === undefined || last.endsWith("\n")) return lines;
  return [...lines.slice(0, -1), `${last}\n`];
}

export type MergeLabels = { ours: string; theirs: string };
/** The original sides of one conflict hunk, in the order its markers appear in the merged text. */
export type ConflictHunk = { base: string; ours: string; theirs: string };
export type TextMerge = { clean: boolean; text: string; conflicts: number; hunks: ConflictHunk[] };

/**
 * Three-way line merge (diff3). Non-overlapping changes merge cleanly; overlapping ones become
 * git-style conflict hunks whose common leading/trailing lines are hoisted out, like git's zealous mode.
 */
export function mergeText(
  base: string,
  ours: string,
  theirs: string,
  labels: MergeLabels,
  budget: DiffBudget = { diffWork: 0 },
): TextMerge {
  const baseLines = splitLines(base);
  const ourLines = splitLines(ours);
  const theirLines = splitLines(theirs);
  if (Math.max(baseLines.length, ourLines.length, theirLines.length) > MAX_MERGE_LINES) {
    throw new MergeTooComplexError("Files are too long to merge in the Worker");
  }
  const table = new Map<string, number>();
  const baseIds = intern(baseLines, table);
  const toOurs = lineMatches(baseIds, intern(ourLines, table), budget);
  const toTheirs = lineMatches(baseIds, intern(theirLines, table), budget);

  const out: string[] = [];
  const hunks: ConflictHunk[] = [];
  let conflicts = 0;
  let i = 0;
  let a = 0;
  let b = 0;
  while (i < baseLines.length || a < ourLines.length || b < theirLines.length) {
    if (i < baseLines.length && toOurs[i] === a && toTheirs[i] === b) {
      out.push(baseLines[i]);
      i++;
      a++;
      b++;
      continue;
    }
    let j = i;
    while (j < baseLines.length && (toOurs[j] === NO_MATCH || toTheirs[j] === NO_MATCH)) j++;
    const aEnd = j < baseLines.length ? toOurs[j] : ourLines.length;
    const bEnd = j < baseLines.length ? toTheirs[j] : theirLines.length;
    const baseChunk = baseLines.slice(i, j);
    const ourChunk = ourLines.slice(a, aEnd);
    const theirChunk = theirLines.slice(b, bEnd);
    if (sameLines(ourChunk, baseChunk) || sameLines(ourChunk, theirChunk)) out.push(...theirChunk);
    else if (sameLines(theirChunk, baseChunk)) out.push(...ourChunk);
    else {
      conflicts++;
      hunks.push({ base: baseChunk.join(""), ...hoisted(ourChunk, theirChunk) });
      out.push(...conflictHunk(ourChunk, theirChunk, labels));
    }
    i = j;
    a = aEnd;
    b = bEnd;
  }
  return { clean: conflicts === 0, text: out.join(""), conflicts, hunks };
}

function sharedEdges(ours: string[], theirs: string[]): { head: number; tail: number } {
  let head = 0;
  while (head < ours.length && head < theirs.length && ours[head] === theirs[head]) head++;
  let tail = 0;
  while (
    tail < ours.length - head &&
    tail < theirs.length - head &&
    ours[ours.length - 1 - tail] === theirs[theirs.length - 1 - tail]
  ) {
    tail++;
  }
  return { head, tail };
}

function hoisted(ours: string[], theirs: string[]): { ours: string; theirs: string } {
  const { head, tail } = sharedEdges(ours, theirs);
  return {
    ours: terminated(ours.slice(head, ours.length - tail)).join(""),
    theirs: terminated(theirs.slice(head, theirs.length - tail)).join(""),
  };
}

function conflictHunk(ours: string[], theirs: string[], labels: MergeLabels): string[] {
  const { head, tail } = sharedEdges(ours, theirs);
  return [
    ...ours.slice(0, head),
    `<<<<<<< ${markerLabel(labels.ours)}\n`,
    ...terminated(ours.slice(head, ours.length - tail)),
    "=======\n",
    ...terminated(theirs.slice(head, theirs.length - tail)),
    `>>>>>>> ${markerLabel(labels.theirs)}\n`,
    ...ours.slice(ours.length - tail),
  ];
}

const MARKER_START = /^<{7}(?: |$)/;
const MARKER_MIDDLE = /^={7}$/;
const MARKER_END = /^>{7}(?: |$)/;

/** True when any conflict marker line remains, even if the block was only partially removed. */
export function hasConflictMarkers(text: string): boolean {
  return splitLines(text).some((raw) => {
    const line = raw.replace(/\r?\n$/, "");
    return MARKER_START.test(line) || MARKER_MIDDLE.test(line) || MARKER_END.test(line);
  });
}