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;10// the rest of the change is shown as a plain replacement, which is still a correct diff,11// just not a minimal one.12const MAX_DIFFERENCES = 2000;1314/** The line edits turning `a` into `b`: Myers' O(ND) diff between the common head and tail. */15export function diffLines(a: string[], b: string[]): Edit[] {16	let head = 0;17	while (head < a.length && head < b.length && a[head] === b[head]) head++;18	let endA = a.length;19	let endB = b.length;20	while (endA > head && endB > head && a[endA - 1] === b[endB - 1]) {21		endA--;22		endB--;23	}24	const edits: Edit[] = [];25	for (let i = 0; i < head; i++) edits.push({ kind: " ", a: i, b: i });26	edits.push(...(myers(a, b, head, endA, endB) ?? replacement(head, endA, endB)));27	for (let i = 0; endA + i < a.length; i++) edits.push({ kind: " ", a: endA + i, b: endB + i });28	return edits;29}3031function replacement(start: number, endA: number, endB: number): Edit[] {32	const edits: Edit[] = [];33	for (let i = start; i < endA; i++) edits.push({ kind: "-", a: i, b: start });34	for (let i = start; i < endB; i++) edits.push({ kind: "+", a: endA, b: i });35	return edits;36}3738function myers(a: string[], b: string[], start: number, endA: number, endB: number): Edit[] | null {39	const n = endA - start;40	const m = endB - start;41	const max = n + m;42	const v = new Int32Array(2 * max + 2);43	// trace[d] is the furthest x per diagonal k before step d, kept only for k in [-d, d].44	const trace: Int32Array[] = [];45	for (let d = 0; d <= Math.min(max, MAX_DIFFERENCES); d++) {46		trace.push(v.slice(max - d, max + d + 1));47		for (let k = -d; k <= d; k += 2) {48			const down = k === -d || (k !== d && (v[max + k - 1] as number) < (v[max + k + 1] as number));49			let x = down ? (v[max + k + 1] as number) : (v[max + k - 1] as number) + 1;50			let y = x - k;51			while (x < n && y < m && a[start + x] === b[start + y]) {52				x++;53				y++;54			}55			v[max + k] = x;56			if (x >= n && y >= m) return backtrack(trace, n, m, start);57		}58	}59	return null;60}6162function backtrack(trace: Int32Array[], n: number, m: number, start: number): Edit[] {63	const edits: Edit[] = [];64	let x = n;65	let y = m;66	for (let d = trace.length - 1; d > 0; d--) {67		const v = trace[d] as Int32Array;68		const at = (k: number) => v[k + d] as number;69		const k = x - y;70		const prevK = k === -d || (k !== d && at(k - 1) < at(k + 1)) ? k + 1 : k - 1;71		const prevX = at(prevK);72		const prevY = prevX - prevK;73		while (x > prevX && y > prevY) {74			x--;75			y--;76			edits.push({ kind: " ", a: start + x, b: start + y });77		}78		if (x === prevX) edits.push({ kind: "+", a: start + x, b: start + prevY });79		else edits.push({ kind: "-", a: start + prevX, b: start + y });80		x = prevX;81		y = prevY;82	}83	while (x > 0) {84		x--;85		edits.push({ kind: " ", a: start + x, b: start + x });86	}87	return edits.reverse();88}8990/** Groups edits into unified-diff hunks with `context` unchanged lines around each change. */91export function hunks(edits: Edit[], context = 3): Hunk[] {92	const out: Hunk[] = [];93	let i = 0;94	while (i < edits.length) {95		if (edits[i]?.kind === " ") {96			i++;97			continue;98		}99		let last = i;100		// Changes up to 2 × context unchanged lines apart share a hunk, as in GNU diff.101		for (let j = i; j < edits.length && j - last <= 2 * context + 1; j++) {102			if (edits[j]?.kind !== " ") last = j;103		}104		const lines = edits.slice(Math.max(0, i - context), Math.min(edits.length, last + context + 1));105		out.push({ header: header(lines), edits: lines });106		i = last + context + 1;107	}108	return out;109}110111// GNU's convention: a side with no lines names the line before the hunk.112function header(edits: Edit[]): string {113	const first = edits[0] as Edit;114	const oldCount = edits.filter((e) => e.kind !== "+").length;115	const newCount = edits.filter((e) => e.kind !== "-").length;116	const range = (start: number, count: number) =>117		`${count === 0 ? start : start + 1}${count === 1 ? "" : `,${count}`}`;118	return `@@ -${range(first.a, oldCount)} +${range(first.b, newCount)} @@`;119}