diff.ts

1/**2 * One edit line: `a` and `b` are its 0-based line numbers in the old and new text. A removed line's `b`3 * (and an added line's `a`) is where it falls in the other text, which the hunk headers need.4 */5export type Edit = { kind: " " | "-" | "+"; a: number; b: number };67export type Hunk = { header: string; edits: Edit[] };89// Past this many differences the Myers trace (about D² numbers) stops paying for itself; the rest of10// the change is shown as a plain replacement, which is still a correct diff, just not a minimal one.11const MAX_DIFFERENCES = 2000;1213/** The line edits turning `a` into `b`: Myers' O(ND) diff between the common head and tail. */14export function diffLines(a: string[], b: string[]): Edit[] {15	let head = 0;16	while (head < a.length && head < b.length && a[head] === b[head]) head++;17	let endA = a.length;18	let endB = b.length;19	while (endA > head && endB > head && a[endA - 1] === b[endB - 1]) {20		endA--;21		endB--;22	}23	const edits: Edit[] = [];24	for (let i = 0; i < head; i++) edits.push({ kind: " ", a: i, b: i });25	edits.push(...(myers(a, b, head, endA, endB) ?? replacement(head, endA, endB)));26	for (let i = 0; endA + i < a.length; i++) edits.push({ kind: " ", a: endA + i, b: endB + i });27	return edits;28}2930function replacement(start: number, endA: number, endB: number): Edit[] {31	const edits: Edit[] = [];32	for (let i = start; i < endA; i++) edits.push({ kind: "-", a: i, b: start });33	for (let i = start; i < endB; i++) edits.push({ kind: "+", a: endA, b: i });34	return edits;35}3637function myers(a: string[], b: string[], start: number, endA: number, endB: number): Edit[] | null {38	const n = endA - start;39	const m = endB - start;40	const max = n + m;41	const v = new Int32Array(2 * max + 2);42	// trace[d] is the furthest x per diagonal k before step d, kept only for k in [-d, d].43	const trace: Int32Array[] = [];44	for (let d = 0; d <= Math.min(max, MAX_DIFFERENCES); d++) {45		trace.push(v.slice(max - d, max + d + 1));46		for (let k = -d; k <= d; k += 2) {47			const down = k === -d || (k !== d && (v[max + k - 1] as number) < (v[max + k + 1] as number));48			let x = down ? (v[max + k + 1] as number) : (v[max + k - 1] as number) + 1;49			let y = x - k;50			while (x < n && y < m && a[start + x] === b[start + y]) {51				x++;52				y++;53			}54			v[max + k] = x;55			if (x >= n && y >= m) return backtrack(trace, n, m, start);56		}57	}58	return null;59}6061function backtrack(trace: Int32Array[], n: number, m: number, start: number): Edit[] {62	const edits: Edit[] = [];63	let x = n;64	let y = m;65	for (let d = trace.length - 1; d > 0; d--) {66		const v = trace[d] as Int32Array;67		const at = (k: number) => v[k + d] as number;68		const k = x - y;69		const prevK = k === -d || (k !== d && at(k - 1) < at(k + 1)) ? k + 1 : k - 1;70		const prevX = at(prevK);71		const prevY = prevX - prevK;72		while (x > prevX && y > prevY) {73			x--;74			y--;75			edits.push({ kind: " ", a: start + x, b: start + y });76		}77		if (x === prevX) edits.push({ kind: "+", a: start + x, b: start + prevY });78		else edits.push({ kind: "-", a: start + prevX, b: start + y });79		x = prevX;80		y = prevY;81	}82	while (x > 0) {83		x--;84		edits.push({ kind: " ", a: start + x, b: start + x });85	}86	return edits.reverse();87}8889/** Groups edits into unified-diff hunks with `context` unchanged lines around each change. */90export function hunks(edits: Edit[], context = 3): Hunk[] {91	const out: Hunk[] = [];92	let i = 0;93	while (i < edits.length) {94		if (edits[i]?.kind === " ") {95			i++;96			continue;97		}98		let last = i;99		// Changes up to 2 × context unchanged lines apart share a hunk, as in GNU diff.100		for (let j = i; j < edits.length && j - last <= 2 * context + 1; j++) {101			if (edits[j]?.kind !== " ") last = j;102		}103		const lines = edits.slice(Math.max(0, i - context), Math.min(edits.length, last + context + 1));104		out.push({ header: header(lines), edits: lines });105		i = last + context + 1;106	}107	return out;108}109110// GNU's convention: a side with no lines names the line before the hunk.111function header(edits: Edit[]): string {112	const first = edits[0] as Edit;113	const oldCount = edits.filter((e) => e.kind !== "+").length;114	const newCount = edits.filter((e) => e.kind !== "-").length;115	const range = (start: number, count: number) =>116		`${count === 0 ? start : start + 1}${count === 1 ? "" : `,${count}`}`;117	return `@@ -${range(first.a, oldCount)} +${range(first.b, newCount)} @@`;118}