diff-engine.ts

/* ============================================================
   diff-engine.ts — line & word diffing + unified-diff parsing.
   Produces the render-ready model consumed by the diff components.
   ============================================================ */
import type { FileDiff, Hunk, Row, Seg } from './types';
import type { FileStatus } from './types';

type Op = { t: 'eq'; a: number; b: number } | { t: 'del'; a: number } | { t: 'ins'; b: number };

/* ---- Myers O(ND) diff over arrays ---- */
export function myers<T>(a: T[], b: T[], eq: (x: T, y: T) => boolean = (x, y) => x === y): Op[] {
  const N = a.length;
  const M = b.length;
  const max = N + M;
  if (max === 0) return [];
  const v = new Array<number>(2 * max + 1).fill(0);
  const off = max;
  const trace: number[][] = [];
  let reached = -1;
  for (let d = 0; d <= max; d++) {
    trace.push(v.slice());
    for (let k = -d; k <= d; k += 2) {
      let x: number;
      if (k === -d || (k !== d && v[off + k - 1] < v[off + k + 1])) x = v[off + k + 1];
      else x = v[off + k - 1] + 1;
      let y = x - k;
      while (x < N && y < M && eq(a[x], b[y])) {
        x++;
        y++;
      }
      v[off + k] = x;
      if (x >= N && y >= M) {
        reached = d;
        break;
      }
    }
    if (reached >= 0) break;
  }
  const ops: Op[] = [];
  let x = N;
  let y = M;
  for (let d = reached; d > 0; d--) {
    const vp = trace[d];
    const k = x - y;
    let prevK: number;
    if (k === -d || (k !== d && vp[off + k - 1] < vp[off + k + 1])) prevK = k + 1;
    else prevK = k - 1;
    const prevX = vp[off + prevK];
    const prevY = prevX - prevK;
    while (x > prevX && y > prevY) {
      ops.push({ t: 'eq', a: x - 1, b: y - 1 });
      x--;
      y--;
    }
    if (d > 0) {
      if (x === prevX) {
        ops.push({ t: 'ins', b: y - 1 });
        y--;
      } else {
        ops.push({ t: 'del', a: x - 1 });
        x--;
      }
    }
  }
  while (x > 0 && y > 0) {
    ops.push({ t: 'eq', a: x - 1, b: y - 1 });
    x--;
    y--;
  }
  while (x > 0) {
    ops.push({ t: 'del', a: x - 1 });
    x--;
  }
  while (y > 0) {
    ops.push({ t: 'ins', b: y - 1 });
    y--;
  }
  ops.reverse();
  return ops;
}

/* ---- word-level tokenizer ---- */
function tokenize(s: string): string[] {
  const out: string[] = [];
  const re = /(\s+|[A-Za-z0-9_$]+|[^\sA-Za-z0-9_$])/g;
  let m: RegExpExecArray | null;
  while ((m = re.exec(s)) !== null) out.push(m[0]);
  return out;
}

export function wordDiff(oldLine: string, newLine: string): [Seg[], Seg[]] {
  const a = tokenize(oldLine);
  const b = tokenize(newLine);
  const ops = myers(a, b);
  const del: Seg[] = [];
  const add: Seg[] = [];
  const push = (arr: Seg[], t: string, hl: boolean) => {
    if (!t) return;
    const last = arr[arr.length - 1];
    if (last && last.hl === hl) last.t += t;
    else arr.push({ t, hl });
  };
  for (const op of ops) {
    if (op.t === 'eq') {
      push(del, a[op.a], false);
      push(add, b[op.b], false);
    } else if (op.t === 'del') {
      push(del, a[op.a], true);
    } else {
      push(add, b[op.b], true);
    }
  }
  return [del.length ? del : [{ t: oldLine, hl: false }], add.length ? add : [{ t: newLine, hl: false }]];
}

const plain = (text: string): Seg[] => [{ t: text, hl: false }];

function similar(a: string, b: string): boolean {
  if (!a.length || !b.length) return false;
  const la = a.length;
  const lb = b.length;
  if (Math.abs(la - lb) > Math.max(la, lb) * 0.7) return false;
  let p = 0;
  const min = Math.min(la, lb);
  while (p < min && a[p] === b[p]) p++;
  let s = 0;
  while (s < min - p && a[la - 1 - s] === b[lb - 1 - s]) s++;
  return p + s >= min * 0.25;
}

interface TypedLine {
  type: 'ctx' | 'add' | 'del';
  oldNum?: number;
  newNum?: number;
  text: string;
}

/* ---- Build side-by-side rows from a typed line list ---- */
export function buildRows(lines: TypedLine[]): Row[] {
  const rows: Row[] = [];
  let i = 0;
  while (i < lines.length) {
    const ln = lines[i];
    if (ln.type === 'ctx') {
      rows.push({
        kind: 'ctx',
        left: { num: ln.oldNum!, segs: plain(ln.text) },
        right: { num: ln.newNum!, segs: plain(ln.text) },
      });
      i++;
      continue;
    }
    const dels: TypedLine[] = [];
    const adds: TypedLine[] = [];
    while (i < lines.length && lines[i].type === 'del') dels.push(lines[i++]);
    while (i < lines.length && lines[i].type === 'add') adds.push(lines[i++]);
    const pairCount = Math.min(dels.length, adds.length);
    for (let p = 0; p < pairCount; p++) {
      const d = dels[p];
      const a = adds[p];
      let lSeg: Seg[];
      let rSeg: Seg[];
      if (similar(d.text, a.text)) {
        const [ds, as] = wordDiff(d.text, a.text);
        lSeg = ds;
        rSeg = as;
      } else {
        lSeg = plain(d.text);
        rSeg = plain(a.text);
      }
      rows.push({ kind: 'rep', left: { num: d.oldNum!, segs: lSeg }, right: { num: a.newNum!, segs: rSeg } });
    }
    for (let p = pairCount; p < dels.length; p++)
      rows.push({ kind: 'del', left: { num: dels[p].oldNum!, segs: plain(dels[p].text) }, right: null });
    for (let p = pairCount; p < adds.length; p++)
      rows.push({ kind: 'add', left: null, right: { num: adds[p].newNum!, segs: plain(adds[p].text) } });
  }
  return rows;
}

/* ---- Parse a single file's unified diff body into hunks ---- */
function parseHunks(body: string): Hunk[] {
  const hunks: { header: string; ctx: string; lines: TypedLine[] }[] = [];
  const lines = body.split('\n');
  let cur: { header: string; ctx: string; lines: TypedLine[] } | null = null;
  let oldNum = 0;
  let newNum = 0;
  for (const raw of lines) {
    if (raw.startsWith('@@')) {
      const m = raw.match(/@@ -(\d+)(?:,(\d+))? \+(\d+)(?:,(\d+))? @@(.*)/);
      if (!m) continue;
      oldNum = parseInt(m[1], 10);
      newNum = parseInt(m[3], 10);
      cur = { header: raw.replace(/(@@ .*? @@).*/, '$1'), ctx: (m[5] || '').trim(), lines: [] };
      hunks.push(cur);
      continue;
    }
    if (!cur) continue;
    const tag = raw[0];
    const text = raw.slice(1);
    if (tag === '+') cur.lines.push({ type: 'add', newNum: newNum++, text });
    else if (tag === '-') cur.lines.push({ type: 'del', oldNum: oldNum++, text });
    else if (tag === '\\') {
      /* "No newline at end of file" */
    } else cur.lines.push({ type: 'ctx', oldNum: oldNum++, newNum: newNum++, text });
  }
  return hunks.map((h) => ({ header: h.header, ctx: h.ctx, rows: buildRows(h.lines) }));
}

function countChanges(hunks: Hunk[]): { adds: number; dels: number } {
  let adds = 0;
  let dels = 0;
  for (const h of hunks)
    for (const r of h.rows) {
      if (r.kind === 'add') adds++;
      else if (r.kind === 'del') dels++;
      else if (r.kind === 'rep') {
        adds++;
        dels++;
      }
    }
  return { adds, dels };
}

/* ---- Parse a multi-file `git diff` blob into FileDiffs ---- */
export function parseUnifiedDiff(raw: string): FileDiff[] {
  if (!raw || !raw.trim()) return [];
  const out: FileDiff[] = [];
  const chunks = raw.split(/\n(?=diff --git )/);
  for (let chunk of chunks) {
    if (!chunk.startsWith('diff --git')) {
      const idx = chunk.indexOf('diff --git');
      if (idx < 0) continue;
      chunk = chunk.slice(idx);
    }
    const fileDiff = parseOneFile(chunk);
    if (fileDiff) out.push(fileDiff);
  }
  return out;
}

function parseOneFile(chunk: string): FileDiff | null {
  const headerEnd = chunk.indexOf('\n@@');
  const head = headerEnd === -1 ? chunk : chunk.slice(0, headerEnd);
  const body = headerEnd === -1 ? '' : chunk.slice(headerEnd + 1);
  const firstLine = head.split('\n')[0];
  const m = firstLine.match(/^diff --git a\/(.+?) b\/(.+)$/);
  let oldPath = m ? m[1] : '';
  let path = m ? m[2] : '';
  let status: FileStatus = 'M';
  if (/\nnew file mode/.test(head)) status = 'A';
  else if (/\ndeleted file mode/.test(head)) status = 'D';
  else if (/\nrename from /.test(head)) status = 'R';
  const binary = /\nBinary files /.test(head) || /\nGIT binary patch/.test(head);
  const rmFrom = head.match(/\nrename from (.+)/);
  const rmTo = head.match(/\nrename to (.+)/);
  if (rmFrom) oldPath = rmFrom[1].trim();
  if (rmTo) path = rmTo[1].trim();
  const hunks = binary ? [] : parseHunks(body);
  const { adds, dels } = countChanges(hunks);
  return { path, oldPath, status, binary, hunks, adds, dels };
}

/* ---- Compute a FileDiff from two full texts (used by the git engine) ---- */
export function computeFileDiff(
  oldText: string,
  newText: string,
  path: string,
  status: FileStatus = 'M',
): FileDiff {
  const oldLines = oldText.length ? oldText.replace(/\n$/, '').split('\n') : [];
  const newLines = newText.length ? newText.replace(/\n$/, '').split('\n') : [];
  const ops = myers(oldLines, newLines);

  type T = { type: 'ctx' | 'del' | 'add'; a?: number; b?: number };
  const typed: T[] = [];
  for (const op of ops) {
    if (op.t === 'eq') typed.push({ type: 'ctx', a: op.a, b: op.b });
    else if (op.t === 'del') typed.push({ type: 'del', a: op.a });
    else typed.push({ type: 'add', b: op.b });
  }

  const CTX = 3;
  const changedIdx = typed.map((t, i) => (t.type !== 'ctx' ? i : -1)).filter((i) => i >= 0);
  const hunks: Hunk[] = [];
  if (changedIdx.length) {
    const groups: [number, number][] = [];
    let start = changedIdx[0];
    let prev = changedIdx[0];
    for (let i = 1; i < changedIdx.length; i++) {
      if (changedIdx[i] - prev > CTX * 2) {
        groups.push([start, prev]);
        start = changedIdx[i];
      }
      prev = changedIdx[i];
    }
    groups.push([start, prev]);
    for (const [s, e] of groups) {
      const from = Math.max(0, s - CTX);
      const to = Math.min(typed.length - 1, e + CTX);
      const lines: TypedLine[] = [];
      let oldStart: number | null = null;
      let newStart: number | null = null;
      let oldCount = 0;
      let newCount = 0;
      for (let i = from; i <= to; i++) {
        const t = typed[i];
        if (t.type === 'ctx') {
          lines.push({ type: 'ctx', oldNum: t.a! + 1, newNum: t.b! + 1, text: oldLines[t.a!] });
          if (oldStart === null) {
            oldStart = t.a! + 1;
            newStart = t.b! + 1;
          }
          oldCount++;
          newCount++;
        } else if (t.type === 'del') {
          lines.push({ type: 'del', oldNum: t.a! + 1, text: oldLines[t.a!] });
          if (oldStart === null) {
            oldStart = t.a! + 1;
            newStart = (typed[from] && typed[from].b != null ? (typed[from].b as number) : 0) + 1;
          }
          oldCount++;
        } else {
          lines.push({ type: 'add', newNum: t.b! + 1, text: newLines[t.b!] });
          if (newStart === null) {
            newStart = t.b! + 1;
            oldStart = 1;
          }
          newCount++;
        }
      }
      const header = `@@ -${oldStart || 0},${oldCount} +${newStart || 0},${newCount} @@`;
      hunks.push({ header, ctx: '', rows: buildRows(lines) });
    }
  }
  const { adds, dels } = countChanges(hunks);
  return { path, oldPath: path, status, binary: false, hunks, adds, dels, full: { oldLines, newLines } };
}