/* Copyright (c) 2024 Richard Rodger, MIT License */

// Line diff and three-way merge.
//
// This is jostraca's own implementation, replacing the `node-diff3` and
// `diff` dependencies. Two reasons:
//
//  1. Performance. The old dependency was unusable on the workload this
//     project actually has — regenerating a large file whose lines mostly
//     repeat (config and reference output). Measured on identical inputs:
//     6.4 s at 5 000 lines, 62 s at 10 000, roughly ten minutes at 20 000.
//
//  2. Parity. The Go port hand-implemented its own merge, and the two
//     disagreed on ~72% of non-trivial merges — both producing valid but
//     different output. The only way two stacks stay byte-identical is to
//     run the same algorithm, so `go/diff.go` mirrors this file directly.
//
// Algorithm:
//
//   - Trim the common prefix and suffix. For a regenerated file, where
//     most content is unchanged, this collapses the quadratic core to
//     almost nothing.
//   - Run Hirschberg's algorithm on the remainder: O(N·M) time as before,
//     but O(M) space rather than a full table, where M is the length of
//     the SECOND argument — the two DP rows are sized by `b`.
//
//     Not O(min(N,M)): nothing swaps the inputs so the shorter side backs
//     the rows, and it must not. The split tie-break below is
//     order-sensitive, so swapping `a` and `b` changes merge output on
//     ~11% of random inputs. Reducing the constant (a narrower row
//     element type) is the output-preserving option if this ever matters.
//   - Split the three inputs into regions around the lines that survive in
//     both, and reconcile each region (the classic diff3 shape).
//
// Exactly one tie-break is load-bearing: on a tie, take the LARGEST split
// point. Several subsequences can be equally long but different, and that
// choice decides which of a user's lines are reported as kept, so both
// stacks fix the same rule.
//
// Two nearby lines look like tie-breaks and are not — the `>=` in
// `lcsRow`, which picks between two numbers already known to be equal, and
// the direction of the single-row base-case scan, which pushes the same
// string whichever position matched. `ts/tools/mutate-diff.js` asserts all
// three claims against the corpus, including that the two decorative ones
// really are decorative.


// --- Public types ---------------------------------------------------------

// Explicit labels for the conflict markers. Overrides `when`/`last`.
type DiffLabels = {
  generated?: string
  existing?: string
}

type DiffSpec = {
  // Epoch ms stamped into the GENERATED label.
  when?: number
  // Epoch ms stamped into the EXISTING label.
  last?: number
  // Label suffix, e.g. 'merge' or 'diff'.
  kind?: string
  // Full label override; wins over when/last/kind.
  labels?: DiffLabels
}

// Why a merge produced what it did. These map straight onto jostraca's
// audit breadcrumbs, which is the point: the caller does not have to
// re-derive the decision the merge already made.
//
//   same       - the file on disk already equals the new generate
//   clean      - the file on disk is untouched since the last generate
//   unresolved - the file on disk still holds unresolved conflict markers
//   merged     - a real three-way merge ran
type MergeOutcome = 'same' | 'clean' | 'unresolved' | 'merged'

type MergeResult = {
  content: string
  conflict: boolean
  outcome: MergeOutcome
}

// same    - generated and existing are identical
// changed - the two differ and the result is annotated
type DiffOutcome = 'same' | 'changed'

type DiffResult = {
  content: string
  conflict: boolean
  outcome: DiffOutcome
}


// --- Markers --------------------------------------------------------------

const MARK_START = '<<<<<<< '
const MARK_MID = '=======\n'
const MARK_END = '>>>>>>> '

const LABEL_GENERATED = 'GENERATED'
const LABEL_EXISTING = 'EXISTING'

// The end-of-conflict marker for the EXISTING side. A file still holding
// this has an unresolved merge in it.
const UNRESOLVED_MARK = MARK_END + LABEL_EXISTING + ':'

// The largest epoch-ms magnitude a Date holds.
const MAX_DATE_MS = 8.64e15


// Whether text still holds an unresolved conflict from an earlier merge.
// Keyed on the closing EXISTING marker alone: a half-resolved file, where
// the opening marker was removed but the closing one was not, must still
// count as unresolved rather than being re-merged.
//
// The `existingLabel` argument matters when the caller supplied a custom
// one: `writeConflict` emits `>>>>>>> ` + whatever label was configured, so
// a file conflicted under `labels.existing = 'E'` does not contain the
// default sentinel at all. Without it, merge's unresolved guard did not
// fire and the markers nested one level deeper on every run — exactly what
// the guard exists to prevent.
//
// Detection only holds when the SAME existing label is used across runs. A
// caller that changes its labels between generations cannot expect an older
// conflict to be recognised, and the default is unchanged for callers that
// never set one.
function hasConflicts(text: string, existingLabel?: string): boolean {
  // The default sentinel is a PREFIX (`>>>>>>> EXISTING:`), so it matches
  // whatever timestamp follows. Checking the fully-formatted label instead
  // would only match a conflict written in the same millisecond.
  if (text.includes(UNRESOLVED_MARK)) {
    return true
  }
  // Match the COMPLETE emitted marker, including its newline. A bare
  // substring check on `MARK_END + label` treats a custom label as a
  // prefix, so label `E` matched an ordinary line `>>>>>>> Example` and
  // merge returned `unresolved` — silently suppressing a legitimate
  // regeneration over a marker the engine never emitted. writeConflict
  // always appends '\n', so the newline is safe to require.
  return null != existingLabel && '' !== existingLabel &&
    text.includes(MARK_END + existingLabel + '\n')
}


// Total, so a cosmetic label can never abort a generate: an out-of-range
// value is clamped to the Date range, and one that is not a finite number
// is the epoch. go/diff.go isoOf formats the same strings.
function isoOf(when?: number): string {
  const ms = ('number' === typeof when && isFinite(when)) ?
    Math.max(-MAX_DATE_MS, Math.min(MAX_DATE_MS, Math.trunc(when))) : 0
  return new Date(ms).toISOString()
}


// An empty kind or label is unset, as it is in Go, whose plain string
// fields cannot tell the two apart.
function labelsOf(spec: DiffSpec | undefined, defaultKind: string): DiffLabels {
  const kind = null == spec?.kind || '' === spec.kind ? defaultKind : spec.kind

  return {
    generated: null == spec?.labels?.generated || '' === spec.labels.generated ?
      LABEL_GENERATED + ': ' + isoOf(spec?.when) + '/' + kind :
      spec.labels.generated,
    existing: null == spec?.labels?.existing || '' === spec.labels.existing ?
      LABEL_EXISTING + ': ' + isoOf(spec?.last) + '/' + kind :
      spec.labels.existing,
  }
}


// --- Line primitives ------------------------------------------------------

// Split on \n, keeping the newline on each line so join('') round-trips
// exactly, including a final line with no trailing newline.
function lines(text: string): string[] {
  if ('' === text) {
    return []
  }

  const out: string[] = []
  let rest = text

  for (; ;) {
    const at = rest.indexOf('\n')

    if (at < 0) {
      out.push(rest)
      return out
    }

    out.push(rest.substring(0, at + 1))
    rest = rest.substring(at + 1)

    if ('' === rest) {
      return out
    }
  }
}


// Longest common subsequence of two line arrays.
function lcs(a: string[], b: string[]): string[] {
  if (0 === a.length || 0 === b.length) {
    return []
  }

  // Common prefix, then common suffix of what is left. Those lines are in
  // every optimal LCS, and skipping them is what makes the realistic case
  // (a mostly-unchanged regenerated file) fast.
  let head = 0
  while (head < a.length && head < b.length && a[head] === b[head]) {
    head++
  }

  let tail = 0
  while (tail < a.length - head && tail < b.length - head &&
    a[a.length - 1 - tail] === b[b.length - 1 - tail]) {
    tail++
  }

  const out: string[] = a.slice(0, head)
  hirschberg(a.slice(head, a.length - tail), b.slice(head, b.length - tail), out)

  for (let i = a.length - tail; i < a.length; i++) {
    out.push(a[i])
  }

  return out
}


// Hirschberg's divide and conquer: recurse on the two halves of `a`, each
// step holding only two rows of the length table.
function hirschberg(a: string[], b: string[], out: string[]): void {
  if (0 === a.length || 0 === b.length) {
    return
  }

  if (1 === a.length) {
    // Scanning backwards mirrors how a full-table walk recovers the LCS
    // (it starts at the end of `b` and steps back), which keeps this
    // readable against the oracle in the tests. It is not a tie-break:
    // `a[0]` is pushed whichever position matched, so first and last
    // occurrence produce the same string.
    for (let i = b.length - 1; 0 <= i; i--) {
      if (b[i] === a[0]) {
        out.push(a[0])
        return
      }
    }
    return
  }

  const mid = Math.floor(a.length / 2)
  const headRow = lcsRow(a.slice(0, mid), b, false)
  const tailRow = lcsRow(a.slice(mid), b, true)

  // `>=` so a tie takes the LARGEST split. This is THE load-bearing
  // tie-break: changing it to `>` changes the merged content on 658 of
  // the differential corpus cases (`make mutation` prints the live
  // number). See the note at the top of this file.
  let best = -1
  let split = 0
  for (let k = 0; k <= b.length; k++) {
    const sum = headRow[k] + tailRow[b.length - k]
    if (sum >= best) {
      best = sum
      split = k
    }
  }

  hirschberg(a.slice(0, mid), b.slice(0, split), out)
  hirschberg(a.slice(mid), b.slice(split), out)
}


// Final row of the LCS length table for `a` against `b`. With `reverse`,
// both sequences are walked back to front, so the result is indexed by
// suffix length rather than prefix length.
function lcsRow(a: string[], b: string[], reverse: boolean): number[] {
  let prev = new Array<number>(b.length + 1).fill(0)
  let cur = new Array<number>(b.length + 1).fill(0)

  const at = (xs: string[], i: number) => reverse ? xs[xs.length - 1 - i] : xs[i]

  for (let i = 0; i < a.length; i++) {
    const ai = at(a, i)
    cur[0] = 0

    for (let j = 0; j < b.length; j++) {
      if (ai === at(b, j)) {
        cur[j + 1] = prev[j] + 1
      }
      // max(prev[j+1], cur[j]). The `>=` is not a tie-break: on a tie both
      // branches assign the same number.
      else if (prev[j + 1] >= cur[j]) {
        cur[j + 1] = prev[j + 1]
      }
      else {
        cur[j + 1] = cur[j]
      }
    }

    const swap = prev
    prev = cur
    cur = swap
  }

  return prev
}


// Anchor map: `m[i]` is the index in `target` where `base[i]` sits in the
// LCS of the two, or -1 when `base[i]` is not in it.
function alignLcs(base: string[], target: string[]): number[] {
  const m = new Array<number>(base.length).fill(-1)

  if (0 === base.length || 0 === target.length) {
    return m
  }

  const common = lcs(base, target)
  let ci = 0
  let ti = 0
  let bi = 0

  while (ci < common.length && bi < base.length && ti < target.length) {
    while (bi < base.length && base[bi] !== common[ci]) {
      bi++
    }
    while (ti < target.length && target[ti] !== common[ci]) {
      ti++
    }
    if (bi < base.length && ti < target.length) {
      m[bi] = ti
      bi++
      ti++
      ci++
    }
  }

  return m
}


function sameLines(a: string[], b: string[]): boolean {
  if (a.length !== b.length) {
    return false
  }
  for (let i = 0; i < a.length; i++) {
    if (a[i] !== b[i]) {
      return false
    }
  }
  return true
}


// Not `out.push(...xs)`: V8 bounds spread arguments by stack size, so a
// region of about 125k lines threw RangeError where Go's append does not.
function pushAll(out: string[], xs: string[]): void {
  for (const x of xs) {
    out.push(x)
  }
}


// Whether the text accumulated so far ends with a newline, so a marker
// always starts on its own line.
//
// Precondition: `parts` is non-empty and holds no empty strings. Both hold
// at every call site — writeConflict pushes its opening marker first, and
// `lines` never yields an empty element.
function endsWithNewline(parts: string[]): boolean {
  return parts[parts.length - 1].endsWith('\n')
}


function writeConflict(
  out: string[],
  generated: string[],
  existing: string[],
  labels: DiffLabels,
): void {
  out.push(MARK_START + labels.generated + '\n')
  pushAll(out, generated)
  if (!endsWithNewline(out)) {
    out.push('\n')
  }

  out.push(MARK_MID)
  pushAll(out, existing)
  if (!endsWithNewline(out)) {
    out.push('\n')
  }

  out.push(MARK_END + labels.existing + '\n')
}


// --- Three-way merge ------------------------------------------------------

// Merge what was just generated with what is on disk, using the previous
// generate as the common ancestor.
//
//   generated - what this run produced
//   baseline  - what the last run produced (the merge base)
//   existing  - what is on disk now, possibly hand-edited
//
// Taking the previous generate as the ancestor is what preserves manual
// edits: anything in `existing` that is not in `baseline` is the user's.
function merge(
  generated: string,
  baseline: string,
  existing: string,
  spec?: DiffSpec,
): MergeResult {
  // Fast paths, in order. Each is semantics-identical to running the full
  // merge, and each avoids the quadratic core entirely.

  // Nothing changed on either side.
  if (generated === existing) {
    return { content: existing, conflict: false, outcome: 'same' }
  }

  // The file is untouched since the last generate, so there is nothing of
  // the user's to preserve: the new generate wins outright.
  if (existing === baseline) {
    return { content: generated, conflict: false, outcome: 'clean' }
  }

  // Never merge into an unresolved merge — that stacks conflict markers
  // inside conflict markers and is unreadable. Leave it for the user.
  // Pass the EXPLICIT custom label, not the formatted one: the formatted
  // default carries a timestamp and would never match an older conflict.
  if (hasConflicts(existing, spec?.labels?.existing)) {
    return { content: existing, conflict: false, outcome: 'unresolved' }
  }

  const labels = labelsOf(spec, 'merge')

  const gl = lines(generated)
  const bl = lines(baseline)
  const el = lines(existing)

  const gMap = alignLcs(bl, gl)
  const eMap = alignLcs(bl, el)

  const out: string[] = []
  let conflict = false

  let bi = 0
  let gi = 0
  let ei = 0

  while (bi < bl.length) {
    if (0 <= gMap[bi] && 0 <= eMap[bi]) {
      // Anchor: this baseline line survives on both sides. Reconcile
      // whatever each side inserted in front of it.
      const gIns = gl.slice(gi, gMap[bi])
      const eIns = el.slice(ei, eMap[bi])

      if (sameLines(gIns, eIns)) {
        pushAll(out, gIns)
      }
      else if (0 === gIns.length) {
        pushAll(out, eIns)
      }
      else if (0 === eIns.length) {
        pushAll(out, gIns)
      }
      else {
        writeConflict(out, gIns, eIns, labels)
        conflict = true
      }

      out.push(bl[bi])
      gi = gMap[bi] + 1
      ei = eMap[bi] + 1
      bi++
      continue
    }

    // Not an anchor: run forward to the next one and reconcile the whole
    // region between.
    let nextBi = bi
    while (nextBi < bl.length && (gMap[nextBi] < 0 || eMap[nextBi] < 0)) {
      nextBi++
    }

    const bRegion = bl.slice(bi, nextBi)
    let gRegion: string[]
    let eRegion: string[]

    if (nextBi < bl.length) {
      gRegion = gl.slice(gi, gMap[nextBi])
      eRegion = el.slice(ei, eMap[nextBi])
    }
    else {
      gRegion = gl.slice(gi)
      eRegion = el.slice(ei)
    }

    if (sameLines(bRegion, gRegion)) {
      // Only the user changed this region.
      pushAll(out, eRegion)
    }
    else if (sameLines(bRegion, eRegion)) {
      // Only the generator changed this region.
      pushAll(out, gRegion)
    }
    else if (sameLines(gRegion, eRegion)) {
      // Both made the same change.
      pushAll(out, gRegion)
    }
    else {
      writeConflict(out, gRegion, eRegion, labels)
      conflict = true
    }

    if (nextBi < bl.length) {
      gi = gMap[nextBi]
      ei = eMap[nextBi]
    }
    else {
      gi = gl.length
      ei = el.length
    }
    bi = nextBi
  }

  // Anything after the last anchor.
  if (gi < gl.length || ei < el.length) {
    const gTail = gl.slice(gi)
    const eTail = el.slice(ei)

    if (sameLines(gTail, eTail)) {
      pushAll(out, gTail)
    }
    else if (0 === gTail.length) {
      pushAll(out, eTail)
    }
    else if (0 === eTail.length) {
      pushAll(out, gTail)
    }
    else {
      writeConflict(out, gTail, eTail, labels)
      conflict = true
    }
  }

  return { content: out.join(''), conflict, outcome: 'merged' }
}


// --- Two-way diff ---------------------------------------------------------

const HUNK_SAME = 0
const HUNK_CHANGE = 1

type Hunk = {
  kind: number
  generated: string[]
  existing: string[]
}


// Hunks describing the difference between the two line arrays. Adjacent
// insertions and deletions merge into a single change hunk, so a modified
// region is reported once rather than as a delete followed by an add.
function hunks(generated: string[], existing: string[]): Hunk[] {
  const common = lcs(generated, existing)
  const out: Hunk[] = []

  let gi = 0
  let ei = 0

  // Two change hunks can never end up adjacent: every flush in the loop
  // below is immediately followed by a same-hunk, and the trailing flush is
  // the last thing to run. So there is nothing to merge into.
  const flush = (g: string[], e: string[]) => {
    if (0 === g.length && 0 === e.length) {
      return
    }
    out.push({ kind: HUNK_CHANGE, generated: g, existing: e })
  }

  for (const line of common) {
    const g: string[] = []
    const e: string[] = []

    while (gi < generated.length && generated[gi] !== line) {
      g.push(generated[gi])
      gi++
    }
    while (ei < existing.length && existing[ei] !== line) {
      e.push(existing[ei])
      ei++
    }
    flush(g, e)

    const last = out[out.length - 1]
    if (null != last && HUNK_SAME === last.kind) {
      last.generated.push(line)
    }
    else {
      out.push({ kind: HUNK_SAME, generated: [line], existing: [] })
    }

    gi++
    ei++
  }

  flush(generated.slice(gi), existing.slice(ei))

  return out
}


// Annotated view of the difference between the new generate and what is on
// disk. Unchanged text passes through; each changed region becomes a pair
// of marked blocks, the existing side first.
function diff(generated: string, existing: string, spec?: DiffSpec): DiffResult {
  if (generated === existing) {
    return { content: generated, conflict: false, outcome: 'same' }
  }

  const labels = labelsOf(spec, 'diff')
  const out: string[] = []

  const block = (block_lines: string[], label?: string) => {
    out.push(MARK_START + label + '\n')
    for (const line of block_lines) {
      out.push(line)
      if (!line.endsWith('\n')) {
        out.push('\n')
      }
    }
    out.push(MARK_END + label + '\n')
  }

  for (const hunk of hunks(lines(generated), lines(existing))) {
    if (HUNK_SAME === hunk.kind) {
      pushAll(out, hunk.generated)
      continue
    }
    if (0 < hunk.existing.length) {
      block(hunk.existing, labels.existing)
    }
    if (0 < hunk.generated.length) {
      block(hunk.generated, labels.generated)
    }
  }

  return { content: out.join(''), conflict: true, outcome: 'changed' }
}


export {
  merge,
  diff,
  hasConflicts,
  lines,
  lcs,
  alignLcs,
  hunks,
}

export type {
  DiffLabels,
  DiffSpec,
  DiffOutcome,
  DiffResult,
  MergeOutcome,
  MergeResult,
}