add the save page: facts, flag reason, parent past checkpoints, files changed with line stats and highlighted unified diffs from a small Myers diff (v3.0.14)

@@ -0,0 +1,118 @@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+ */5+export type Edit = { kind: " " | "-" | "+"; a: number; b: number };6+7+export type Hunk = { header: string; edits: Edit[] };8+9+// 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.11+const MAX_DIFFERENCES = 2000;12+13+/** The line edits turning `a` into `b`: Myers' O(ND) diff between the common head and tail. */14+export 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+}29+30+function 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+}36+37+function 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+}60+61+function 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+}88+89+/** Groups edits into unified-diff hunks with `context` unchanged lines around each change. */90+export 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+}109+110+// GNU's convention: a side with no lines names the line before the hunk.111+function 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+}

@@ -0,0 +1,210 @@1+import type { Database } from "bun:sqlite";2+import type { Hono } from "hono";3+import {4+	type FileEntry,5+	filesAt,6+	flagReason,7+	objectBytes,8+	type Save,9+	saveByPrefix,10+	visibleParent,11+} from "../mirror/queries.ts";12+import { diffLines, type Edit, hunks } from "./diff.ts";13+import { isText } from "./files.ts";14+import { highlightLines } from "./highlight.ts";15+import { type Html, html } from "./html.ts";16+import {17+	cacheFor,18+	formatDate,19+	notFound,20+	openPublicRepo,21+	type PageContext,22+	page,23+	pathUrl,24+	plural,25+	relativeTime,26+} from "./layout.ts";27+28+// A side over the file viewer's 1 MB is not diffed; past 256 KB it is shown without highlighting.29+const DIFF_MAX_BYTES = 1024 * 1024;30+const HIGHLIGHT_MAX_BYTES = 256 * 1024;31+// A file's diff longer than this starts collapsed; once the page has shown this many lines, the32+// remaining files are listed without their diffs so one huge save can't make a huge page.33+const COLLAPSE_LINES = 300;34+const PAGE_MAX_LINES = 5000;35+36+type Change = {37+	path: string;38+	status: "added" | "removed" | "modified";39+	before: FileEntry | null;40+	after: FileEntry | null;41+};42+43+type FileDiff = Change & {44+	kind: "text" | "binary" | "large";45+	oldText: string;46+	newText: string;47+	edits: Edit[];48+	added: number;49+	removed: number;50+};51+52+export function registerSavePage(app: Hono, ctx: PageContext): void {53+	app.get("/:repo/saves/:id", async (c) => {54+		const repo = openPublicRepo(ctx, c.req.param("repo"));55+		const id = c.req.param("id");56+		const save = repo && saveByPrefix(repo.mirror, id);57+		// Checkpoints never appear (§21.4), so a link to one finds nothing, like an unknown ID.58+		if (!repo || !save || save.is_checkpoint) return notFound(c, ctx);59+		const name = repo.settings.name;60+		if (save.id !== id) return c.redirect(`/${name}/saves/${save.id}`, 302);61+		const parent = visibleParent(repo.mirror, save);62+		const diffs = changes(repo.mirror, save, parent).map((change) => fileDiff(repo.mirror, change));63+		// Not a year like other per-save content: a flag or a strip can arrive for this save later.64+		cacheFor(c, false);65+		const [title = "", ...rest] = save.message.split("\n");66+		return c.html(67+			page(ctx, {68+				title: `${title} · ${name}`,69+				description: `${save.id} · ${plural(diffs.length, "file")} changed`,70+				path: `/${name}/saves/${save.id}`,71+				body: html`<p class="breadcrumb mono"><a href="/${name}">${name}</a> / <a href="/${name}#history">history</a></p>72+${saveHeader(repo.mirror, name, save, parent, title, rest.join("\n").trim())}73+<section class="repo-section">74+<details class="repo-section-toggle" open>75+<summary class="section-head"><span class="section-label">files changed</span><span class="section-count">${plural(diffs.length, "file")}</span></summary>76+${diffs.length === 0 ? html`<p class="muted mono save-empty">no files changed</p>` : diffs.map((d, i) => changeRow(d, i))}77+</details>78+</section>79+<section class="repo-section">${await diffSections(name, save, parent, diffs)}</section>`,80+			}),81+		);82+	});83+}84+85+function saveHeader(86+	db: Database,87+	name: string,88+	save: Save,89+	parent: Save | null,90+	title: string,91+	body: string,92+): Html {93+	const reason = flagReason(db, save.id);94+	const facts: [string, Html | string][] = [95+		["time", `${formatDate(save.created_at)} UTC · ${relativeTime(save.created_at)}`],96+		["machine", save.machine],97+		...(save.agent ? [["agent", save.agent] as [string, string]] : []),98+		...(save.session ? [["session", save.session] as [string, string]] : []),99+		[100+			"parent",101+			parent102+				? html`<a href="/${name}/saves/${parent.id}">${parent.id}</a>`103+				: "none, the first save",104+		],105+	];106+	return html`<p class="save-id mono">${save.id}</p>107+${reason !== null && html`<p class="save-flag"><span class="save-flag-label mono">flagged</span> ${reason || "no reason given"}</p>`}108+<h1 class="save-message-head">${title}</h1>109+${body && html`<p class="save-message-body">${body}</p>`}110+<dl class="save-facts mono">${facts.map(([term, value]) => html`<dt>${term}</dt><dd>${value}</dd>`)}</dl>111+<p class="save-links mono"><a href="/${name}/archive/${save.id}.tar.gz">↓ ${name}-${save.id.slice(0, 8)}.tar.gz</a><a href="/${name}?at=${save.id}#atlas">atlas at this save</a></p>`;112+}113+114+function changes(db: Database, save: Save, parent: Save | null): Change[] {115+	const before = new Map(parent ? filesAt(db, parent.id).map((f) => [f.path, f]) : []);116+	const after = new Map(filesAt(db, save.id).map((f) => [f.path, f]));117+	const paths = [...new Set([...before.keys(), ...after.keys()])].sort();118+	return paths.flatMap((path) => {119+		const old = before.get(path) ?? null;120+		const now = after.get(path) ?? null;121+		if (old && now && old.hash === now.hash && old.executable === now.executable) return [];122+		const status = !old ? "added" : !now ? "removed" : "modified";123+		return [{ path, status, before: old, after: now }];124+	});125+}126+127+function fileDiff(db: Database, change: Change): FileDiff {128+	const empty = { oldText: "", newText: "", edits: [], added: 0, removed: 0 };129+	const sides = [change.before, change.after];130+	if (sides.some((f) => f && f.size > DIFF_MAX_BYTES))131+		return { ...change, ...empty, kind: "large" };132+	const [oldBytes, newBytes] = sides.map((f) => (f && objectBytes(db, f.hash)) ?? new Uint8Array());133+	if (!isText(oldBytes as Uint8Array) || !isText(newBytes as Uint8Array)) {134+		return { ...change, ...empty, kind: "binary" };135+	}136+	const oldText = new TextDecoder().decode(oldBytes);137+	const newText = new TextDecoder().decode(newBytes);138+	const edits = diffLines(lines(oldText), lines(newText));139+	const added = edits.filter((e) => e.kind === "+").length;140+	const removed = edits.filter((e) => e.kind === "-").length;141+	return { ...change, kind: "text", oldText, newText, edits, added, removed };142+}143+144+function lines(text: string): string[] {145+	return text === "" ? [] : text.replace(/\n$/, "").split("\n");146+}147+148+function stat(d: FileDiff): Html {149+	if (d.kind !== "text") return html`<span class="diff-note">${d.kind}</span>`;150+	return html`<span class="diff-add">+${d.added}</span> <span class="diff-del">−${d.removed}</span>`;151+}152+153+function changeRow(d: FileDiff, index: number): Html {154+	return html`<a class="change-row change-${d.status}" href="#diff-${index}"><span class="change-path">${d.path}</span><span class="change-stat mono">${stat(d)}</span></a>`;155+}156+157+async function diffSections(158+	name: string,159+	save: Save,160+	parent: Save | null,161+	diffs: FileDiff[],162+): Promise<Html[]> {163+	let shown = 0;164+	const sections: Html[] = [];165+	for (const [index, d] of diffs.entries()) {166+		const at = d.status === "removed" ? parent?.id : save.id;167+		const view = `/${name}/files/${pathUrl(d.path)}?at=${at}`;168+		const hunkList = hunks(d.edits);169+		const length = hunkList.reduce((sum, h) => sum + h.edits.length + 1, 0);170+		const mode =171+			d.before && d.after && d.before.executable !== d.after.executable172+				? html`<p class="diff-note mono">${d.after.executable ? "now executable" : "no longer executable"}</p>`173+				: "";174+		let content: Html | string = "";175+		if (d.kind === "binary") content = html`<p class="diff-note mono">binary file, not shown</p>`;176+		else if (d.kind === "large") content = html`<p class="diff-note mono">over 1 MB, not shown</p>`;177+		else if (shown + length > PAGE_MAX_LINES) {178+			content = html`<p class="diff-note mono">not shown here: too long for one page</p>`;179+		} else if (length > 0) {180+			shown += length;181+			content = await diffBody(d, hunkList);182+		}183+		sections.push(html`<details class="diff-file change-${d.status}" id="diff-${index}"${length <= COLLAPSE_LINES && " open"}>184+<summary class="diff-head"><span class="change-path">${d.path}</span><span class="change-stat mono">${stat(d)}</span></summary>185+${mode}${content}186+<p class="diff-view mono"><a href="${view}">view file${d.status === "removed" && " at the parent"}</a></p>187+</details>`);188+	}189+	return sections;190+}191+192+async function diffBody(d: FileDiff, hunkList: ReturnType<typeof hunks>): Promise<Html> {193+	const [oldLines, newLines] = await Promise.all([194+		highlighted(d.oldText, d.path),195+		highlighted(d.newText, d.path),196+	]);197+	const row = (e: Edit) => {198+		const code = e.kind === "-" ? oldLines[e.a] : newLines[e.b];199+		const kind = e.kind === "+" ? "add" : e.kind === "-" ? "del" : "ctx";200+		return html`<span class="dl dl-${kind}"><span class="ln">${e.kind !== "+" && e.a + 1}</span><span class="ln">${e.kind !== "-" && e.b + 1}</span><span class="ds">${e.kind}</span><span class="lc">${code}</span></span>`;201+	};202+	return html`<div class="file-view"><pre class="code diff"><code>${hunkList.map(203+		(h) => html`<span class="dh">${h.header}</span>${h.edits.map(row)}`,204+	)}</code></pre></div>`;205+}206+207+function highlighted(text: string, path: string): Promise<Html[]> | Html[] {208+	if (text.length > HIGHLIGHT_MAX_BYTES) return lines(text).map((line) => html`${line}`);209+	return highlightLines(text, path);210+}

@@ -0,0 +1,82 @@1+import { describe, expect, test } from "bun:test";2+import { diffLines, hunks } from "../src/pages/diff.ts";3+4+// Longest common subsequence by dynamic programming: the minimal diff keeps exactly this many lines.5+function 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+}17+18+// A small seeded generator, so every run tests the same inputs.19+function random(seed: number): () => number {20+	let s = seed;21+	return () => {22+		s = (s * 1103515245 + 12345) % 2147483648;23+		return s / 2147483648;24+	};25+}26+27+describe("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+	});42+43+	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+	});47+48+	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+});58+59+describe("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+});