Repository Public
1/** Small bounded unified line diff for the console (edit_file / write_file results). Pure, deterministic. */23const MAX_CELLS = 4_000_000;45type Op = { t: ' ' | '-' | '+'; s: string };67function splitLines(s: string): string[] {8 if (s.length === 0) return [];9 const lines = s.split('\n');10 if (lines[lines.length - 1] === '') lines.pop();11 return lines;12}1314function lineOps(a: string[], b: string[]): Op[] {15 let pre = 0;16 while (pre < a.length && pre < b.length && a[pre] === b[pre]) pre++;17 let suf = 0;18 while (suf < a.length - pre && suf < b.length - pre && a[a.length - 1 - suf] === b[b.length - 1 - suf]) suf++;19 const am = a.slice(pre, a.length - suf);20 const bm = b.slice(pre, b.length - suf);21 const ops: Op[] = [];22 for (let i = 0; i < pre; i++) ops.push({ t: ' ', s: a[i] as string });23 const n = am.length;24 const m = bm.length;25 if (n === 0 || m === 0 || n * m > MAX_CELLS) {26 // too large for LCS (or trivially one-sided): present the middle as one replaced block27 for (const s of am) ops.push({ t: '-', s });28 for (const s of bm) ops.push({ t: '+', s });29 } else {30 const w = m + 1;31 const dp = new Uint32Array((n + 1) * w);32 for (let i = n - 1; i >= 0; i--) {33 for (let j = m - 1; j >= 0; j--) {34 dp[i * w + j] = am[i] === bm[j] ? (dp[(i + 1) * w + j + 1] as number) + 1 : Math.max(dp[(i + 1) * w + j] as number, dp[i * w + j + 1] as number);35 }36 }37 let i = 0;38 let j = 0;39 while (i < n && j < m) {40 if (am[i] === bm[j]) {41 ops.push({ t: ' ', s: am[i] as string });42 i++;43 j++;44 } else if ((dp[(i + 1) * w + j] as number) >= (dp[i * w + j + 1] as number)) {45 ops.push({ t: '-', s: am[i++] as string });46 } else {47 ops.push({ t: '+', s: bm[j++] as string });48 }49 }50 while (i < n) ops.push({ t: '-', s: am[i++] as string });51 while (j < m) ops.push({ t: '+', s: bm[j++] as string });52 }53 for (let i = a.length - suf; i < a.length; i++) ops.push({ t: ' ', s: a[i] as string });54 return ops;55}5657/**58 * Unified diff (3 context lines) between two texts, truncated to `maxChars`.59 * `before === null` means the file is new. Returns '' when the texts are identical.60 */61export function unifiedDiff(relPath: string, before: string | null, after: string, maxChars = 8000): string {62 if (before === after) return '';63 const a = splitLines(before ?? '');64 const b = splitLines(after);65 const ops = lineOps(a, b);66 const CONTEXT = 3;67 const out: string[] = [before === null ? '--- /dev/null' : `--- a/${relPath}`, `+++ b/${relPath}`];68 const changed: number[] = [];69 ops.forEach((o, i) => {70 if (o.t !== ' ') changed.push(i);71 });72 if (changed.length === 0) {73 // only the trailing newline differs74 out.push('@@ end of file @@', (before ?? '').endsWith('\n') ? '-(trailing newline)' : '+(trailing newline)');75 return out.join('\n') + '\n';76 }77 // line numbers before each op78 const aNo: number[] = [];79 const bNo: number[] = [];80 let ai = 1;81 let bi = 1;82 for (const o of ops) {83 aNo.push(ai);84 bNo.push(bi);85 if (o.t !== '+') ai++;86 if (o.t !== '-') bi++;87 }88 let k = 0;89 while (k < changed.length) {90 const start = Math.max(0, (changed[k] as number) - CONTEXT);91 let end = (changed[k] as number) + CONTEXT;92 while (k + 1 < changed.length && (changed[k + 1] as number) - CONTEXT <= end + 1) {93 k++;94 end = (changed[k] as number) + CONTEXT;95 }96 end = Math.min(ops.length - 1, end);97 k++;98 const slice = ops.slice(start, end + 1);99 const aCount = slice.filter((o) => o.t !== '+').length;100 const bCount = slice.filter((o) => o.t !== '-').length;101 const aStart = aCount === 0 ? (aNo[start] as number) - 1 : (aNo[start] as number);102 const bStart = bCount === 0 ? (bNo[start] as number) - 1 : (bNo[start] as number);103 out.push(`@@ -${aStart},${aCount} +${bStart},${bCount} @@`);104 for (const o of slice) out.push(o.t + o.s);105 }106 let text = out.join('\n') + '\n';107 if (text.length > maxChars) {108 const cut = text.lastIndexOf('\n', maxChars);109 text = text.slice(0, cut > 0 ? cut : maxChars) + `\n… diff truncated (${text.length} chars in total)\n`;110 }111 return text;112}113