/**
 * Line diffing for the repository browser: two texts in, unified-diff hunks
 * out. Myers' greedy algorithm walks the edit graph, so the work scales with
 * the size of the change rather than the size of the file.
 *
 * Workers-clean: strings and typed arrays only.
 */

/** Lines of context around each change, matching git's default. */
const CONTEXT = 3;

/**
 * Edit-distance ceiling. Myers costs O((n+m)·d), so a file rewritten end to
 * end is the expensive case. Past this the caller reports the change without
 * hunks rather than stalling the page.
 */
const MAX_EDITS = 2000;

/**
 * @typedef {Object} DiffLine
 * @property {'context'|'add'|'delete'} type
 * @property {string} text
 * @property {number|null} oldLine - 1-based line number before the change
 * @property {number|null} newLine - 1-based line number after the change
 */

/**
 * @typedef {Object} DiffHunk
 * @property {number} oldStart
 * @property {number} oldLines
 * @property {number} newStart
 * @property {number} newLines
 * @property {DiffLine[]} lines
 */

/**
 * Split a text into lines for diffing. A trailing newline ends the last line
 * rather than starting an empty one, so a commit that only adds or removes a
 * final newline reports no hunks. git marks that case with
 * "\ No newline at end of file".
 * @param {string} text
 * @returns {string[]}
 */
export function splitLines(text) {
  if (text === '') return [];
  const lines = text.split('\n');
  if (lines[lines.length - 1] === '') lines.pop();
  return lines;
}

/**
 * The edit script between two line arrays, as an ordered list of operations.
 *
 * @param {string[]} before
 * @param {string[]} after
 * @param {number} maxEdits
 * @returns {Array<{type: 'context'|'add'|'delete', text: string}>|null} null
 *   when the edit distance passes maxEdits
 */
function editScript(before, after, maxEdits) {
  const n = before.length;
  const m = after.length;
  const max = Math.min(n + m, maxEdits);
  const offset = max;
  const v = new Int32Array(2 * max + 2);
  /** V at the start of each round, which the backtrack walks in reverse. */
  const trace = [];

  for (let d = 0; d <= max; d++) {
    trace.push(v.slice());
    for (let k = -d; k <= d; k += 2) {
      // Extend the furthest-reaching path on the neighbouring diagonal: down
      // when it reaches further, right otherwise.
      const down =
        k === -d || (k !== d && v[offset + k - 1] < v[offset + k + 1]);
      let x = down ? v[offset + k + 1] : v[offset + k - 1] + 1;
      let y = x - k;
      while (x < n && y < m && before[x] === after[y]) {
        x++;
        y++;
      }
      v[offset + k] = x;
      if (x >= n && y >= m) return backtrack(trace, before, after, d, offset);
    }
  }
  return null;
}

/**
 * Walk the recorded traces back from the end point, emitting the operations
 * in reverse and then reversing them.
 *
 * @param {Int32Array[]} trace
 * @param {string[]} before
 * @param {string[]} after
 * @param {number} depth
 * @param {number} offset
 * @returns {Array<{type: 'context'|'add'|'delete', text: string}>}
 */
function backtrack(trace, before, after, depth, offset) {
  /** @type {Array<{type: 'context'|'add'|'delete', text: string}>} */
  const ops = [];
  let x = before.length;
  let y = after.length;

  for (let d = depth; d > 0; d--) {
    const v = trace[d];
    const k = x - y;
    const down = k === -d || (k !== d && v[offset + k - 1] < v[offset + k + 1]);
    const previousK = down ? k + 1 : k - 1;
    const previousX = v[offset + previousK];
    const previousY = previousX - previousK;

    while (x > previousX && y > previousY) {
      x--;
      y--;
      ops.push({ type: 'context', text: before[x] });
    }
    if (x > previousX) {
      x--;
      ops.push({ type: 'delete', text: before[x] });
    } else {
      y--;
      ops.push({ type: 'add', text: after[y] });
    }
  }
  while (x > 0 && y > 0) {
    x--;
    y--;
    ops.push({ type: 'context', text: before[x] });
  }
  return ops.reverse();
}

// ---- compaction ----
//
// Myers reports one edit script, but a change surrounded by lines identical
// to its own can sit at several positions for the same cost. Inserting a doc
// comment into a file full of them is the everyday case. The pass below is
// git's xdl_change_compact: slide each group of changed lines to the extreme
// of its freedom, then place it where the surrounding indentation reads
// best. Its constants and weights come from git's xdiff, so the hunks land
// where a reader comparing against `git show` expects them.

/** Deepest indent that still counts, and the run of blanks that still counts. */
const MAX_INDENT = 200;
const MAX_BLANKS = 20;

/** How much a lower effective indent outweighs the penalties. */
const INDENT_WEIGHT = 60;

/** Cap on positions scored per group, so a huge block stays affordable. */
const MAX_SLIDING = 100;

const START_OF_FILE_PENALTY = 1;
const END_OF_FILE_PENALTY = 21;
const TOTAL_BLANK_WEIGHT = -30;
const POST_BLANK_WEIGHT = 6;
const RELATIVE_INDENT_PENALTY = -4;
const RELATIVE_INDENT_WITH_BLANK_PENALTY = 10;
const RELATIVE_OUTDENT_PENALTY = 24;
const RELATIVE_OUTDENT_WITH_BLANK_PENALTY = 17;
const RELATIVE_DEDENT_PENALTY = 23;
const RELATIVE_DEDENT_WITH_BLANK_PENALTY = 17;

/**
 * A line's indent in columns, or -1 when the line is blank. A tab advances to
 * the next multiple of eight; other whitespace advances nothing.
 * @param {string} line
 * @returns {number}
 */
function getIndent(line) {
  let indent = 0;
  for (const char of line) {
    if (char === ' ') indent += 1;
    else if (char === '\t') indent += 8 - (indent % 8);
    else if (char !== '\r' && char !== '\v' && char !== '\f') return indent;
    if (indent >= MAX_INDENT) return MAX_INDENT;
  }
  return -1;
}

/**
 * @typedef {Object} DiffSide
 * @property {string[]} lines
 * @property {Uint8Array} changed - 1 where the line is part of a change
 */

/**
 * What the neighbourhood of a split point looks like, for scoring.
 * @param {DiffSide} side
 * @param {number} split - index of the line just after the split
 */
function measureSplit(side, split) {
  const { lines } = side;
  const m = {
    endOfFile: split >= lines.length,
    indent: split >= lines.length ? -1 : getIndent(lines[split]),
    preBlank: 0,
    preIndent: -1,
    postBlank: 0,
    postIndent: -1,
  };

  for (let i = split - 1; i >= 0; i--) {
    m.preIndent = getIndent(lines[i]);
    if (m.preIndent !== -1) break;
    m.preBlank += 1;
    if (m.preBlank === MAX_BLANKS) {
      m.preIndent = 0;
      break;
    }
  }
  for (let i = split + 1; i < lines.length; i++) {
    m.postIndent = getIndent(lines[i]);
    if (m.postIndent !== -1) break;
    m.postBlank += 1;
    if (m.postBlank === MAX_BLANKS) {
      m.postIndent = 0;
      break;
    }
  }
  return m;
}

/**
 * Fold one split's measurement into a running score. Lower is better.
 * @param {ReturnType<typeof measureSplit>} m
 * @param {{effectiveIndent: number, penalty: number}} score
 */
function scoreAddSplit(m, score) {
  if (m.preIndent === -1 && m.preBlank === 0) {
    score.penalty += START_OF_FILE_PENALTY;
  }
  if (m.endOfFile) score.penalty += END_OF_FILE_PENALTY;

  const postBlank = m.indent === -1 ? 1 + m.postBlank : 0;
  const totalBlank = m.preBlank + postBlank;
  score.penalty += TOTAL_BLANK_WEIGHT * totalBlank;
  score.penalty += POST_BLANK_WEIGHT * postBlank;

  const indent = m.indent !== -1 ? m.indent : m.postIndent;
  const anyBlanks = totalBlank !== 0;
  score.effectiveIndent += indent;

  if (indent === -1 || m.preIndent === -1) return;
  if (indent > m.preIndent) {
    score.penalty += anyBlanks
      ? RELATIVE_INDENT_WITH_BLANK_PENALTY
      : RELATIVE_INDENT_PENALTY;
  } else if (indent < m.preIndent) {
    // Indented less than the line before. A line that the next one indents
    // under opens a block; otherwise it closes one.
    if (m.postIndent !== -1 && m.postIndent > indent) {
      score.penalty += anyBlanks
        ? RELATIVE_OUTDENT_WITH_BLANK_PENALTY
        : RELATIVE_OUTDENT_PENALTY;
    } else {
      score.penalty += anyBlanks
        ? RELATIVE_DEDENT_WITH_BLANK_PENALTY
        : RELATIVE_DEDENT_PENALTY;
    }
  }
}

/**
 * @param {{effectiveIndent: number, penalty: number}} a
 * @param {{effectiveIndent: number, penalty: number}} b
 */
function scoreCmp(a, b) {
  const indents =
    (a.effectiveIndent > b.effectiveIndent ? 1 : 0) -
    (a.effectiveIndent < b.effectiveIndent ? 1 : 0);
  return INDENT_WEIGHT * indents + (a.penalty - b.penalty);
}

/** @param {DiffSide} side */
function groupInit(side) {
  const g = { start: 0, end: 0 };
  while (g.end < side.changed.length && side.changed[g.end]) g.end++;
  return g;
}

/** @param {DiffSide} side @param {{start: number, end: number}} g */
function groupNext(side, g) {
  if (g.end === side.changed.length) return false;
  g.start = g.end + 1;
  g.end = g.start;
  while (g.end < side.changed.length && side.changed[g.end]) g.end++;
  return true;
}

/** @param {DiffSide} side @param {{start: number, end: number}} g */
function groupPrevious(side, g) {
  if (g.start === 0) return false;
  g.end = g.start - 1;
  g.start = g.end;
  while (g.start > 0 && side.changed[g.start - 1]) g.start--;
  return true;
}

/**
 * Move a group one line earlier, which is only possible when the line before
 * it repeats its last line. Sliding onto the single unchanged line that
 * separated this group from the one before it joins the two, so the group
 * then absorbs everything still marked ahead of it. Without that step the
 * next slide would clear a line the joined group owns, and the change would
 * be lost.
 * @param {DiffSide} side @param {{start: number, end: number}} g
 */
function slideUp(side, g) {
  if (g.start > 0 && side.lines[g.start - 1] === side.lines[g.end - 1]) {
    side.changed[--g.start] = 1;
    side.changed[--g.end] = 0;
    while (g.start > 0 && side.changed[g.start - 1]) g.start--;
    return true;
  }
  return false;
}

/**
 * Move a group one line later, absorbing a following group the same way.
 * @param {DiffSide} side @param {{start: number, end: number}} g
 */
function slideDown(side, g) {
  if (g.end < side.lines.length && side.lines[g.start] === side.lines[g.end]) {
    side.changed[g.start++] = 0;
    side.changed[g.end++] = 1;
    while (g.end < side.changed.length && side.changed[g.end]) g.end++;
    return true;
  }
  return false;
}

/**
 * Move every change group on one side to its best position, walking the other
 * side in step so a group can prefer to line up with a change over there.
 * @param {DiffSide} side - the side being compacted
 * @param {DiffSide} other
 */
function compact(side, other) {
  const g = groupInit(side);
  const go = groupInit(other);

  for (;;) {
    if (g.end !== g.start) {
      let groupSize;
      let earliestEnd;
      let endMatchingOther;
      // Sliding can merge this group with a neighbour, which makes it bigger
      // and gives it new freedom. Repeat until the size settles.
      do {
        groupSize = g.end - g.start;
        endMatchingOther = -1;

        while (slideUp(side, g)) groupPrevious(other, go);
        earliestEnd = g.end;
        if (go.end > go.start) endMatchingOther = g.end;

        while (slideDown(side, g)) {
          groupNext(other, go);
          if (go.end > go.start) endMatchingOther = g.end;
        }
      } while (groupSize !== g.end - g.start);

      if (g.end === earliestEnd) {
        // The group is pinned; nothing to choose.
      } else if (endMatchingOther !== -1) {
        // Line the group up with the last change on the other side that it
        // can reach, so both files show the change in the same place.
        while (go.end === go.start) {
          slideUp(side, g);
          groupPrevious(other, go);
        }
      } else {
        let shift = Math.max(
          earliestEnd,
          g.end - groupSize - 1,
          g.end - MAX_SLIDING,
        );
        let bestShift = -1;
        let bestScore = { effectiveIndent: 0, penalty: 0 };
        for (; shift <= g.end; shift++) {
          const score = { effectiveIndent: 0, penalty: 0 };
          scoreAddSplit(measureSplit(side, shift), score);
          scoreAddSplit(measureSplit(side, shift - groupSize), score);
          if (bestShift === -1 || scoreCmp(score, bestScore) <= 0) {
            bestScore = score;
            bestShift = shift;
          }
        }
        while (g.end > bestShift) {
          slideUp(side, g);
          groupPrevious(other, go);
        }
      }
    }

    if (!groupNext(side, g)) break;
    groupNext(other, go);
  }
}

/**
 * The hunks between two texts, the way `git diff -U3` groups them.
 *
 * @param {string} beforeText
 * @param {string} afterText
 * @param {{context?: number, maxEdits?: number}} [options]
 * @returns {DiffHunk[]|null} null when the change is too large to diff
 */
export function diffLines(beforeText, afterText, options = {}) {
  const context = options.context ?? CONTEXT;
  const before = splitLines(beforeText);
  const after = splitLines(afterText);
  const ops = editScript(before, after, options.maxEdits ?? MAX_EDITS);
  if (!ops) return null;

  // The edit script says which lines changed. Compaction then decides where
  // each run of them sits, so the two sides are tracked as flags rather than
  // as the ordered operations Myers emitted.
  const beforeSide = {
    lines: before,
    changed: new Uint8Array(before.length),
  };
  const afterSide = { lines: after, changed: new Uint8Array(after.length) };
  let atBefore = 0;
  let atAfter = 0;
  for (const op of ops) {
    if (op.type === 'context') {
      atBefore++;
      atAfter++;
    } else if (op.type === 'delete') {
      beforeSide.changed[atBefore++] = 1;
    } else {
      afterSide.changed[atAfter++] = 1;
    }
  }

  compact(beforeSide, afterSide);
  compact(afterSide, beforeSide);

  /** @type {DiffLine[]} */
  const lines = [];
  let oldLine = 0;
  let newLine = 0;
  while (oldLine < before.length || newLine < after.length) {
    // A group's deletions all print before its additions, the way a unified
    // diff reads.
    if (oldLine < before.length && beforeSide.changed[oldLine]) {
      oldLine++;
      lines.push({
        type: 'delete',
        text: before[oldLine - 1],
        oldLine,
        newLine: null,
      });
    } else if (newLine < after.length && afterSide.changed[newLine]) {
      newLine++;
      lines.push({
        type: 'add',
        text: after[newLine - 1],
        oldLine: null,
        newLine,
      });
    } else {
      oldLine++;
      newLine++;
      lines.push({
        type: 'context',
        text: before[oldLine - 1],
        oldLine,
        newLine,
      });
    }
  }

  const changed = lines
    .map((line, index) => (line.type === 'context' ? -1 : index))
    .filter((index) => index >= 0);
  if (changed.length === 0) return [];

  /** Ranges of lines to show, each a change plus its context. */
  /** @type {Array<{from: number, to: number}>} */
  const ranges = [];
  for (const index of changed) {
    const from = Math.max(0, index - context);
    const to = Math.min(lines.length - 1, index + context);
    const last = ranges[ranges.length - 1];
    // Ranges that touch or overlap become one hunk, so the context between
    // two nearby changes is not printed twice.
    if (last && from <= last.to + 1) last.to = Math.max(last.to, to);
    else ranges.push({ from, to });
  }

  return ranges.map((range) => {
    const body = lines.slice(range.from, range.to + 1);
    const oldCount = body.filter((line) => line.type !== 'add').length;
    const newCount = body.filter((line) => line.type !== 'delete').length;
    const firstOld = body.find((line) => line.oldLine !== null);
    const firstNew = body.find((line) => line.newLine !== null);
    return {
      // An empty side starts at 0, which is what git prints for a file that
      // gains or loses all of its lines.
      oldStart: oldCount === 0 ? 0 : (firstOld?.oldLine ?? 0),
      oldLines: oldCount,
      newStart: newCount === 0 ? 0 : (firstNew?.newLine ?? 0),
      newLines: newCount,
      lines: body,
    };
  });
}