diff.test.ts

1import { describe, expect, test } from "bun:test";2import { diffLines, hunks } from "../src/pages/diff.ts";34// Longest common subsequence by dynamic programming: the minimal diff keeps exactly this many lines.5function lcs(a: string[], b: string[]): number {6	const row = new Array<number>(b.length + 1).fill(0);7	for (const line of a) {8		let diagonal = 0;9		for (let j = 1; j <= b.length; j++) {10			const above = row[j] as number;11			row[j] = line === b[j - 1] ? diagonal + 1 : Math.max(above, row[j - 1] as number);12			diagonal = above;13		}14	}15	return row[b.length] as number;16}1718// A small seeded generator, so every run tests the same inputs.19function random(seed: number): () => number {20	let s = seed;21	return () => {22		s = (s * 1103515245 + 12345) % 2147483648;23		return s / 2147483648;24	};25}2627describe("diffLines", () => {28	test("rebuilds both sides and keeps a longest common subsequence", () => {29		const next = random(7);30		for (let round = 0; round < 300; round++) {31			const lines = (n: number) =>32				Array.from({ length: n }, () => "abcd"[Math.floor(next() * 4)] as string);33			const a = lines(Math.floor(next() * 14));34			const b = lines(Math.floor(next() * 14));35			const edits = diffLines(a, b);36			expect(edits.filter((e) => e.kind !== "+").map((e) => a[e.a])).toEqual(a);37			expect(edits.filter((e) => e.kind !== "-").map((e) => b[e.b])).toEqual(b);38			for (const e of edits.filter((e) => e.kind === " ")) expect(a[e.a]).toBe(b[e.b] as string);39			expect(edits.filter((e) => e.kind === " ").length).toBe(lcs(a, b));40		}41	});4243	test("an empty side is all additions or all removals", () => {44		expect(diffLines([], ["x", "y"]).map((e) => e.kind)).toEqual(["+", "+"]);45		expect(diffLines(["x"], []).map((e) => e.kind)).toEqual(["-"]);46	});4748	test("past the difference cap, a plain replacement still rebuilds both sides", () => {49		const a = Array.from({ length: 3000 }, (_, i) => `a${i}`);50		const b = ["same", ...Array.from({ length: 3000 }, (_, i) => `b${i}`), "end"];51		a.unshift("same");52		a.push("end");53		const edits = diffLines(a, b);54		expect(edits.filter((e) => e.kind !== "+").map((e) => a[e.a])).toEqual(a);55		expect(edits.filter((e) => e.kind !== "-").map((e) => b[e.b])).toEqual(b);56	});57});5859describe("hunks", () => {60	test("match GNU diff -u's headers and grouping", () => {61		const a = Array.from({ length: 20 }, (_, i) => `line ${i + 1}`);62		const b = [...a];63		b[1] = "changed 2";64		b.splice(9, 1);65		b.push("line 21");66		expect(hunks(diffLines(a, b)).map((h) => h.header)).toEqual([67			"@@ -1,5 +1,5 @@",68			"@@ -7,7 +7,6 @@",69			"@@ -18,3 +17,4 @@",70		]);71		// Changes six unchanged lines apart share one hunk; seven apart do not.72		const six = [...a];73		six[2] = "x";74		six[9] = "y";75		expect(hunks(diffLines(a, six)).length).toBe(1);76		const seven = [...a];77		seven[2] = "x";78		seven[10] = "y";79		expect(hunks(diffLines(a, seven)).length).toBe(2);80		expect(hunks(diffLines([], ["new"]))[0]?.header).toBe("@@ -0,0 +1 @@");81	});82});