/**
 * One edit line: `a` and `b` are its 0-based line numbers in the old and new text. A removed line's `b`
 * (and an added line's `a`) is where it falls in the other text, which the hunk headers need.
 */
export type Edit = { kind: " " | "-" | "+"; a: number; b: number };

export type Hunk = { header: string; edits: Edit[] };

// Past this many differences the Myers trace (about D² numbers) stops paying for itself; the rest of
// the change is shown as a plain replacement, which is still a correct diff, just not a minimal one.
const MAX_DIFFERENCES = 2000;

/** The line edits turning `a` into `b`: Myers' O(ND) diff between the common head and tail. */
export function diffLines(a: string[], b: string[]): Edit[] {
	let head = 0;
	while (head < a.length && head < b.length && a[head] === b[head]) head++;
	let endA = a.length;
	let endB = b.length;
	while (endA > head && endB > head && a[endA - 1] === b[endB - 1]) {
		endA--;
		endB--;
	}
	const edits: Edit[] = [];
	for (let i = 0; i < head; i++) edits.push({ kind: " ", a: i, b: i });
	edits.push(...(myers(a, b, head, endA, endB) ?? replacement(head, endA, endB)));
	for (let i = 0; endA + i < a.length; i++) edits.push({ kind: " ", a: endA + i, b: endB + i });
	return edits;
}

function replacement(start: number, endA: number, endB: number): Edit[] {
	const edits: Edit[] = [];
	for (let i = start; i < endA; i++) edits.push({ kind: "-", a: i, b: start });
	for (let i = start; i < endB; i++) edits.push({ kind: "+", a: endA, b: i });
	return edits;
}

function myers(a: string[], b: string[], start: number, endA: number, endB: number): Edit[] | null {
	const n = endA - start;
	const m = endB - start;
	const max = n + m;
	const v = new Int32Array(2 * max + 2);
	// trace[d] is the furthest x per diagonal k before step d, kept only for k in [-d, d].
	const trace: Int32Array[] = [];
	for (let d = 0; d <= Math.min(max, MAX_DIFFERENCES); d++) {
		trace.push(v.slice(max - d, max + d + 1));
		for (let k = -d; k <= d; k += 2) {
			const down = k === -d || (k !== d && (v[max + k - 1] as number) < (v[max + k + 1] as number));
			let x = down ? (v[max + k + 1] as number) : (v[max + k - 1] as number) + 1;
			let y = x - k;
			while (x < n && y < m && a[start + x] === b[start + y]) {
				x++;
				y++;
			}
			v[max + k] = x;
			if (x >= n && y >= m) return backtrack(trace, n, m, start);
		}
	}
	return null;
}

function backtrack(trace: Int32Array[], n: number, m: number, start: number): Edit[] {
	const edits: Edit[] = [];
	let x = n;
	let y = m;
	for (let d = trace.length - 1; d > 0; d--) {
		const v = trace[d] as Int32Array;
		const at = (k: number) => v[k + d] as number;
		const k = x - y;
		const prevK = k === -d || (k !== d && at(k - 1) < at(k + 1)) ? k + 1 : k - 1;
		const prevX = at(prevK);
		const prevY = prevX - prevK;
		while (x > prevX && y > prevY) {
			x--;
			y--;
			edits.push({ kind: " ", a: start + x, b: start + y });
		}
		if (x === prevX) edits.push({ kind: "+", a: start + x, b: start + prevY });
		else edits.push({ kind: "-", a: start + prevX, b: start + y });
		x = prevX;
		y = prevY;
	}
	while (x > 0) {
		x--;
		edits.push({ kind: " ", a: start + x, b: start + x });
	}
	return edits.reverse();
}

/** Groups edits into unified-diff hunks with `context` unchanged lines around each change. */
export function hunks(edits: Edit[], context = 3): Hunk[] {
	const out: Hunk[] = [];
	let i = 0;
	while (i < edits.length) {
		if (edits[i]?.kind === " ") {
			i++;
			continue;
		}
		let last = i;
		// Changes up to 2 × context unchanged lines apart share a hunk, as in GNU diff.
		for (let j = i; j < edits.length && j - last <= 2 * context + 1; j++) {
			if (edits[j]?.kind !== " ") last = j;
		}
		const lines = edits.slice(Math.max(0, i - context), Math.min(edits.length, last + context + 1));
		out.push({ header: header(lines), edits: lines });
		i = last + context + 1;
	}
	return out;
}

// GNU's convention: a side with no lines names the line before the hunk.
function header(edits: Edit[]): string {
	const first = edits[0] as Edit;
	const oldCount = edits.filter((e) => e.kind !== "+").length;
	const newCount = edits.filter((e) => e.kind !== "-").length;
	const range = (start: number, count: number) =>
		`${count === 0 ? start : start + 1}${count === 1 ? "" : `,${count}`}`;
	return `@@ -${range(first.a, oldCount)} +${range(first.b, newCount)} @@`;
}