/**
 * The three-way merge: what a pull request's changes and main's changes
 * since it branched come to when put together.
 *
 * Text merges line by line, the way `git merge` does. Each side's changes
 * against the base are found, and a region only one side changed takes that
 * side. A region both changed the same way takes either. A region they
 * changed differently is a conflict, and reads with git's own markers.
 *
 * A tree merges entry by entry. An entry only one side changed takes that
 * side; two blobs both changed merge as text; a change on one side against
 * a deletion on the other, or against a different kind of entry, is a
 * conflict. A merged tree is a new object where anything under it changed,
 * and the same object where nothing did.
 *
 * Workers-clean: no node imports.
 */

import { objectId, parseTree } from './objects.js';

const encoder = new TextEncoder();
const decoder = new TextDecoder();

/**
 * Lines at most a side may have before the merge gives up on a line-level
 * answer and treats the file as one region. Past this the table the diff
 * builds is the product of two sides, which is more than one file is worth.
 */
const MAX_LINES = 5000;

/**
 * @param {string} text
 * @returns {string[]} the lines, each with its newline, so joining them
 *   back gives the text
 */
function lines(text) {
  if (text === '') return [];
  const found = text.split('\n');
  const last = found.pop() ?? '';
  const out = found.map((line) => `${line}\n`);
  if (last !== '') out.push(last);
  return out;
}

/**
 * The longest common subsequence of two line lists, as index pairs in
 * order.
 * @param {string[]} a
 * @param {string[]} b
 * @returns {Array<[number, number]>}
 */
function matches(a, b) {
  const rows = a.length + 1;
  const cols = b.length + 1;
  const table = new Uint32Array(rows * cols);
  for (let i = a.length - 1; i >= 0; i--) {
    for (let j = b.length - 1; j >= 0; j--) {
      table[i * cols + j] =
        a[i] === b[j]
          ? table[(i + 1) * cols + j + 1] + 1
          : Math.max(table[(i + 1) * cols + j], table[i * cols + j + 1]);
    }
  }
  /** @type {Array<[number, number]>} */
  const found = [];
  let i = 0;
  let j = 0;
  while (i < a.length && j < b.length) {
    if (a[i] === b[j]) {
      found.push([i, j]);
      i++;
      j++;
    } else if (table[(i + 1) * cols + j] >= table[i * cols + j + 1]) {
      i++;
    } else {
      j++;
    }
  }
  return found;
}

/**
 * @typedef {Object} TextMerge
 * @property {string} text - the merged text, with conflict markers where
 *   the sides disagree
 * @property {number} conflicts - how many regions the sides disagree on
 */

/**
 * Merge two texts against their common base.
 * @param {string} base
 * @param {string} ours - main's side, which the markers call HEAD
 * @param {string} theirs - the branch's side
 * @param {Object} [labels]
 * @param {string} [labels.ours]
 * @param {string} [labels.theirs]
 * @returns {TextMerge}
 */
export function mergeText(base, ours, theirs, labels = {}) {
  if (ours === theirs) return { text: ours, conflicts: 0 };
  if (ours === base) return { text: theirs, conflicts: 0 };
  if (theirs === base) return { text: ours, conflicts: 0 };

  const b = lines(base);
  const o = lines(ours);
  const t = lines(theirs);
  if (Math.max(b.length, o.length, t.length) > MAX_LINES) {
    return { text: conflict(ours, theirs, labels), conflicts: 1 };
  }

  // Where each side still has the base's lines, as a map from base index to
  // that side's index.
  const inOurs = new Map(matches(b, o));
  const inTheirs = new Map(matches(b, t));

  /** @type {string[]} */
  const out = [];
  let conflicts = 0;
  let bi = 0;
  let oi = 0;
  let ti = 0;

  while (bi < b.length || oi < o.length || ti < t.length) {
    // A base line both sides keep is stable: copy it and move all three.
    const oAt = inOurs.get(bi);
    const tAt = inTheirs.get(bi);
    if (
      bi < b.length &&
      oAt !== undefined &&
      tAt !== undefined &&
      oAt === oi &&
      tAt === ti
    ) {
      out.push(b[bi]);
      bi++;
      oi++;
      ti++;
      continue;
    }
    // Otherwise a changed region runs to the next base line both sides
    // keep in step.
    let end = bi;
    while (end < b.length) {
      const oNext = inOurs.get(end);
      const tNext = inTheirs.get(end);
      if (oNext !== undefined && tNext !== undefined) {
        // Both keep it, but a side may have inserted before it; the region
        // closes here and the insertion belongs to the region.
        break;
      }
      end++;
    }
    const oEnd =
      end < b.length ? /** @type {number} */ (inOurs.get(end)) : o.length;
    const tEnd =
      end < b.length ? /** @type {number} */ (inTheirs.get(end)) : t.length;
    const baseRegion = b.slice(bi, end).join('');
    const ourRegion = o.slice(oi, oEnd).join('');
    const theirRegion = t.slice(ti, tEnd).join('');
    if (ourRegion === theirRegion) out.push(ourRegion);
    else if (ourRegion === baseRegion) out.push(theirRegion);
    else if (theirRegion === baseRegion) out.push(ourRegion);
    else {
      out.push(conflict(ourRegion, theirRegion, labels));
      conflicts++;
    }
    bi = end;
    oi = oEnd;
    ti = tEnd;
  }
  return { text: out.join(''), conflicts };
}

/**
 * One conflicted region, as git writes it.
 * @param {string} ours @param {string} theirs
 * @param {{ours?: string, theirs?: string}} labels
 */
function conflict(ours, theirs, labels) {
  const ended = (/** @type {string} */ text) =>
    text === '' || text.endsWith('\n') ? text : `${text}\n`;
  return `<<<<<<< ${labels.ours ?? 'HEAD'}\n${ended(ours)}=======\n${ended(theirs)}>>>>>>> ${labels.theirs ?? 'branch'}\n`;
}

/**
 * Whether bytes are text this merge can read. A NUL in the first 8KB says
 * binary, the way git decides.
 * @param {Uint8Array} bytes
 */
const isBinary = (bytes) => bytes.subarray(0, 8192).includes(0);

/**
 * A tree's entries in git's own byte form, in git's own order: by name, a
 * directory sorting as if its name ended in a slash.
 * @param {import('./objects.js').TreeEntry[]} entries
 * @returns {Uint8Array}
 */
export function encodeTree(entries) {
  const sorted = [...entries].sort((a, b) => {
    const an = a.type === 'dir' ? `${a.name}/` : a.name;
    const bn = b.type === 'dir' ? `${b.name}/` : b.name;
    return an < bn ? -1 : an > bn ? 1 : 0;
  });
  /** @type {Uint8Array[]} */
  const parts = [];
  for (const entry of sorted) {
    const head = encoder.encode(`${entry.mode} ${entry.name}\0`);
    const raw = Uint8Array.from(
      (entry.sha.match(/../g) ?? []).map((pair) => Number.parseInt(pair, 16)),
    );
    const row = new Uint8Array(head.length + raw.length);
    row.set(head, 0);
    row.set(raw, head.length);
    parts.push(row);
  }
  const data = new Uint8Array(parts.reduce((n, part) => n + part.length, 0));
  let at = 0;
  for (const part of parts) {
    data.set(part, at);
    at += part.length;
  }
  return data;
}

/**
 * @typedef {Object} TreeMerge
 * @property {string} sha - the merged tree
 * @property {Map<string, {type: string, data: Uint8Array}>} objects - the
 *   blobs and trees the merge made, by id
 * @property {string[]} conflicts - paths the sides disagree on
 */

/**
 * @typedef {Object} MergeStore
 * @property {(sha: string) => Promise<{type: string, data: Uint8Array}|null>} get
 */

/**
 * Merge two trees against their common base.
 * @param {MergeStore} store - answers for every object of all three trees
 * @param {string|null} base - the base tree, null where the path is new
 * @param {string|null} ours
 * @param {string|null} theirs
 * @param {Object} [options]
 * @param {string} [options.path] - where this tree is, for the conflict paths
 * @param {{ours?: string, theirs?: string}} [options.labels]
 * @returns {Promise<TreeMerge>}
 */
export async function mergeTrees(store, base, ours, theirs, options = {}) {
  const at = options.path ?? '';
  /** @type {Map<string, {type: string, data: Uint8Array}>} */
  const objects = new Map();
  /** @type {string[]} */
  const conflicts = [];

  /** @param {string|null} sha */
  const entriesOf = async (sha) => {
    if (!sha) return new Map();
    const tree = await store.get(sha);
    if (!tree || tree.type !== 'tree') return new Map();
    return new Map(parseTree(tree.data).map((entry) => [entry.name, entry]));
  };
  const [b, o, t] = await Promise.all([
    entriesOf(base),
    entriesOf(ours),
    entriesOf(theirs),
  ]);

  /** @type {import('./objects.js').TreeEntry[]} */
  const merged = [];
  const names = [...new Set([...b.keys(), ...o.keys(), ...t.keys()])];
  for (const name of names) {
    const path = at ? `${at}/${name}` : name;
    const bE = b.get(name) ?? null;
    const oE = o.get(name) ?? null;
    const tE = t.get(name) ?? null;
    const same = (
      /** @type {import('./objects.js').TreeEntry|null} */ x,
      /** @type {import('./objects.js').TreeEntry|null} */ y,
    ) =>
      (x === null && y === null) || (x?.sha === y?.sha && x?.mode === y?.mode);

    if (same(oE, tE)) {
      if (oE) merged.push(oE);
      continue;
    }
    if (same(oE, bE)) {
      if (tE) merged.push(tE);
      continue;
    }
    if (same(tE, bE)) {
      if (oE) merged.push(oE);
      continue;
    }
    // Both sides changed it, differently.
    if (!oE || !tE) {
      // One side deleted what the other changed.
      conflicts.push(path);
      merged.push(/** @type {import('./objects.js').TreeEntry} */ (oE ?? tE));
      continue;
    }
    if (oE.type === 'dir' && tE.type === 'dir') {
      const inner = await mergeTrees(
        store,
        bE?.type === 'dir' ? bE.sha : null,
        oE.sha,
        tE.sha,
        { path, labels: options.labels },
      );
      for (const [sha, object] of inner.objects) objects.set(sha, object);
      conflicts.push(...inner.conflicts);
      merged.push({ ...oE, sha: inner.sha });
      continue;
    }
    if (oE.type === 'file' && tE.type === 'file' && oE.mode === tE.mode) {
      const [bB, oB, tB] = await Promise.all([
        bE?.type === 'file' ? store.get(bE.sha) : null,
        store.get(oE.sha),
        store.get(tE.sha),
      ]);
      if (oB && tB && !isBinary(oB.data) && !isBinary(tB.data)) {
        const answer = mergeText(
          bB ? decoder.decode(bB.data) : '',
          decoder.decode(oB.data),
          decoder.decode(tB.data),
          options.labels,
        );
        if (answer.conflicts > 0) conflicts.push(path);
        const data = encoder.encode(answer.text);
        const sha = objectId('blob', data);
        objects.set(sha, { type: 'blob', data });
        merged.push({ ...oE, sha });
        continue;
      }
    }
    // Different kinds, different modes, or bytes no merge can read.
    conflicts.push(path);
    merged.push(oE);
  }

  const data = encodeTree(merged);
  const sha = objectId('tree', data);
  if (sha !== ours && sha !== theirs && sha !== base) {
    objects.set(sha, { type: 'tree', data });
  }
  return { sha, objects, conflicts };
}