spb/khaelor Public

1/**2 * KHAELOR3 * File: src/tools/diff.ts4 * Description: Unified diff generation with addition/deletion counts for write/edit metadata.5 *6 * Author: Simon-Pierre Boucher7 * Contact: contact@spboucher.ai8 */910export interface UnifiedDiff {11  text: string;12  additions: number;13  deletions: number;14}1516const CONTEXT_LINES = 3;17/** LCS matrix guard: beyond this the diff degrades to a single replace hunk. */18const MAX_LCS_CELLS = 4_000_000;1920function splitLines(text: string): string[] {21  if (text.length === 0) return [];22  const lines = text.split("\n");23  if (lines[lines.length - 1] === "") lines.pop();24  return lines;25}2627type DiffOp = { kind: "equal" | "delete" | "insert"; line: string };2829function diffOps(oldLines: string[], newLines: string[]): DiffOp[] {30  // Trim common prefix/suffix to keep the DP small.31  let start = 0;32  while (start < oldLines.length && start < newLines.length && oldLines[start] === newLines[start]) {33    start += 1;34  }35  let endOld = oldLines.length;36  let endNew = newLines.length;37  while (endOld > start && endNew > start && oldLines[endOld - 1] === newLines[endNew - 1]) {38    endOld -= 1;39    endNew -= 1;40  }4142  const a = oldLines.slice(start, endOld);43  const b = newLines.slice(start, endNew);44  const ops: DiffOp[] = [];45  for (let i = 0; i < start; i++) ops.push({ kind: "equal", line: oldLines[i] as string });4647  if ((a.length + 1) * (b.length + 1) > MAX_LCS_CELLS) {48    for (const line of a) ops.push({ kind: "delete", line });49    for (const line of b) ops.push({ kind: "insert", line });50  } else {51    // LCS lengths table.52    const m = a.length;53    const n = b.length;54    const table = new Uint32Array((m + 1) * (n + 1));55    const at = (i: number, j: number): number => table[i * (n + 1) + j] as number;56    for (let i = m - 1; i >= 0; i--) {57      for (let j = n - 1; j >= 0; j--) {58        table[i * (n + 1) + j] =59          a[i] === b[j] ? at(i + 1, j + 1) + 1 : Math.max(at(i + 1, j), at(i, j + 1));60      }61    }62    let i = 0;63    let j = 0;64    while (i < m && j < n) {65      if (a[i] === b[j]) {66        ops.push({ kind: "equal", line: a[i] as string });67        i += 1;68        j += 1;69      } else if (at(i + 1, j) >= at(i, j + 1)) {70        ops.push({ kind: "delete", line: a[i] as string });71        i += 1;72      } else {73        ops.push({ kind: "insert", line: b[j] as string });74        j += 1;75      }76    }77    while (i < m) ops.push({ kind: "delete", line: a[i++] as string });78    while (j < n) ops.push({ kind: "insert", line: b[j++] as string });79  }8081  for (let i = endOld; i < oldLines.length; i++) ops.push({ kind: "equal", line: oldLines[i] as string });82  return ops;83}8485/** Compute a unified diff (3 lines of context) between two texts. */86export function unifiedDiff(87  oldText: string,88  newText: string,89  oldLabel: string,90  newLabel: string,91): UnifiedDiff {92  const ops = diffOps(splitLines(oldText), splitLines(newText));93  let additions = 0;94  let deletions = 0;95  for (const op of ops) {96    if (op.kind === "insert") additions += 1;97    if (op.kind === "delete") deletions += 1;98  }99  if (additions === 0 && deletions === 0) {100    return { text: "", additions: 0, deletions: 0 };101  }102103  // Group ops into hunks with context.104  interface Hunk {105    oldStart: number;106    oldCount: number;107    newStart: number;108    newCount: number;109    lines: string[];110  }111  const hunks: Hunk[] = [];112  let oldLine = 1;113  let newLine = 1;114  let index = 0;115116  while (index < ops.length) {117    const op = ops[index] as DiffOp;118    if (op.kind === "equal") {119      oldLine += 1;120      newLine += 1;121      index += 1;122      continue;123    }124    // Start of a change: back up for leading context.125    const contextStart = Math.max(0, index - CONTEXT_LINES);126    let leading = 0;127    for (let k = contextStart; k < index; k++) {128      if ((ops[k] as DiffOp).kind === "equal") leading += 1;129    }130    const hunk: Hunk = {131      oldStart: oldLine - leading,132      oldCount: 0,133      newStart: newLine - leading,134      newCount: 0,135      lines: [],136    };137    for (let k = index - leading; k < index; k++) {138      hunk.lines.push(` ${(ops[k] as DiffOp).line}`);139      hunk.oldCount += 1;140      hunk.newCount += 1;141    }142    // Consume changes and interleaved context until a gap of > 2×context equals.143    let equalRun = 0;144    while (index < ops.length) {145      const current = ops[index] as DiffOp;146      if (current.kind === "equal") {147        equalRun += 1;148        if (equalRun > CONTEXT_LINES * 2) break;149      } else {150        equalRun = 0;151      }152      index += 1;153      if (current.kind === "equal") {154        hunk.lines.push(` ${current.line}`);155        hunk.oldCount += 1;156        hunk.newCount += 1;157        oldLine += 1;158        newLine += 1;159      } else if (current.kind === "delete") {160        hunk.lines.push(`-${current.line}`);161        hunk.oldCount += 1;162        oldLine += 1;163      } else {164        hunk.lines.push(`+${current.line}`);165        hunk.newCount += 1;166        newLine += 1;167      }168    }169    // Trim trailing context beyond CONTEXT_LINES.170    let trailing = 0;171    while (172      trailing < hunk.lines.length &&173      (hunk.lines[hunk.lines.length - 1 - trailing] as string).startsWith(" ")174    ) {175      trailing += 1;176    }177    const excess = Math.max(0, trailing - CONTEXT_LINES);178    if (excess > 0) {179      hunk.lines.length -= excess;180      hunk.oldCount -= excess;181      hunk.newCount -= excess;182      oldLine -= excess;183      newLine -= excess;184      // Re-advance the outer scan past the trimmed equals.185      index -= excess;186    }187    hunks.push(hunk);188  }189190  const header = `--- ${oldLabel}\n+++ ${newLabel}`;191  const body = hunks192    .map(193      (h) =>194        `@@ -${h.oldStart},${h.oldCount} +${h.newStart},${h.newCount} @@\n${h.lines.join("\n")}`,195    )196    .join("\n");197  return { text: `${header}\n${body}`, additions, deletions };198}199200/** Cap a diff string for durable events (default 32 KiB) with an explicit marker. */201export function capDiff(diff: string, maxBytes = 32 * 1024): string {202  if (Buffer.byteLength(diff, "utf8") <= maxBytes) return diff;203  return `${diff.slice(0, maxBytes)}\n[diff truncated]`;204}205