| 1 | import { structuredPatch } from "diff"; |
| 2 | import { describe, expect, it } from "vitest"; |
| 3 | import { DiffBudget, MAX_EDIT_LENGTH, MemoryStore, fileDiff, mergeText, utf8 } from "../src/index.js"; |
| 4 | |
| 5 | // Two files with no line in common: Myers' worst case, quadratic in their length. |
| 6 | const unrelated = (n: number) => [Array.from({ length: n }, (_, i) => `old ${i}\n`).join(""), Array.from({ length: n }, (_, i) => `new ${i}\n`).join("")]; |
| 7 | |
| 8 | async function diffOf(a: string, b: string, budget?: DiffBudget) { |
| 9 | const store = new MemoryStore(); |
| 10 | const oldOid = await store.write("blob", utf8(a)); |
| 11 | const newOid = await store.write("blob", utf8(b)); |
| 12 | return fileDiff(store, { path: "f.txt", status: "modified", oldOid, newOid }, 3, budget); |
| 13 | } |
| 14 | |
| 15 | describe("diffs are bounded", () => { |
| 16 | it("a file rewritten from scratch is diffed in one pass, as one replaced block", async () => { |
| 17 | // 2 x 40k lines (about 0.8 MB): unbounded, this takes minutes. |
| 18 | const [a, b] = unrelated(40_000); |
| 19 | const t = Date.now(); |
| 20 | const d = await diffOf(`same 1\nsame 2\n${a}same 3\n`, `same 1\nsame 2\n${b}same 3\n`); |
| 21 | expect(Date.now() - t).toBeLessThan(5_000); |
| 22 | expect(d.truncated).toBeUndefined(); |
| 23 | expect([d.additions, d.deletions]).toEqual([40_000, 40_000]); |
| 24 | expect(d.hunks).toHaveLength(1); |
| 25 | const h = d.hunks[0]!; |
| 26 | expect([h.oldStart, h.oldLines, h.newStart, h.newLines]).toEqual([1, 40_003, 1, 40_003]); |
| 27 | expect(h.lines.slice(0, 3)).toEqual([" same 1", " same 2", "-old 0"]); |
| 28 | expect(h.lines.at(-1)).toBe(" same 3"); |
| 29 | }); |
| 30 | |
| 31 | it("the cheap diff matches Myers' line counts and marks a missing final newline", async () => { |
| 32 | const d = await diffOf("x\n", "y", new DiffBudget(undefined, 0)); |
| 33 | expect(d.hunks).toEqual([{ oldStart: 1, oldLines: 1, newStart: 1, newLines: 1, lines: ["-x", "+y", "\\ No newline at end of file"] }]); |
| 34 | const added = await diffOf("", "a\nb\n", new DiffBudget(undefined, 0)); |
| 35 | expect(added.hunks).toEqual(structuredPatch("f", "f", "", "a\nb\n", "", "", { context: 3 }).hunks.map(({ oldStart, oldLines, newStart, newLines, lines }) => ({ oldStart, oldLines, newStart, newLines, lines }))); |
| 36 | }); |
| 37 | |
| 38 | it("small changes still get Myers' minimal diff", async () => { |
| 39 | const base = Array.from({ length: 200 }, (_, i) => `line ${i}\n`); |
| 40 | const changed = [...base]; |
| 41 | changed[10] = "changed 10\n"; |
| 42 | changed[150] = "changed 150\n"; |
| 43 | const d = await diffOf(base.join(""), changed.join("")); |
| 44 | expect([d.additions, d.deletions, d.hunks.length]).toEqual([2, 2, 2]); |
| 45 | }); |
| 46 | |
| 47 | it("one request shares a budget: after it is spent, files are still listed but not diffed", async () => { |
| 48 | const budget = new DiffBudget(100, MAX_EDIT_LENGTH ** 2); |
| 49 | const first = await diffOf("a\n".repeat(20), "b\n".repeat(20), budget); |
| 50 | expect(first.truncated).toBeUndefined(); |
| 51 | expect(budget.bytes).toBe(20); |
| 52 | const second = await diffOf("c\n".repeat(20), "d\n".repeat(20), budget); |
| 53 | expect(second.truncated).toBe(true); |
| 54 | }); |
| 55 | |
| 56 | it("a three-way merge too large to compute is a conflict, quickly", () => { |
| 57 | const [a, b] = unrelated(30_000); |
| 58 | const t = Date.now(); |
| 59 | expect(mergeText(`top\n${a}`, `top\n${b}`, `changed\n${a}`)).toBeNull(); |
| 60 | expect(Date.now() - t).toBeLessThan(5_000); |
| 61 | expect(mergeText("1\n2\n3\n", "1\nx\n3\n", "1\n2\n3\n4\n")).toBe("1\nx\n3\n4\n"); |
| 62 | }); |
| 63 | }); |