| 1 | import { describe, expect, it } from "vitest"; |
| 2 | import { MemoryStore, isAncestor, mergeBase, serializeCommit, type Signature } from "../src/index.js"; |
| 3 | |
| 4 | const TREE = "4b825dc642cb6eb9a060e54bf8d69288fbee4904"; |
| 5 | |
| 6 | /** A random history: each commit has one or two earlier parents (a few roots), and committer dates that may run backwards. */ |
| 7 | async function history(seed: number, n: number, skew: boolean, label = "c") { |
| 8 | let x = seed; |
| 9 | const rand = () => ((x = (x * 1103515245 + 12345) % 2147483648) / 2147483648); |
| 10 | const store = new MemoryStore(); |
| 11 | const oids: string[] = []; |
| 12 | const parents: number[][] = []; |
| 13 | for (let i = 0; i < n; i++) { |
| 14 | const ps = i === 0 || rand() < 0.03 ? [] : [Math.floor(rand() * i)]; |
| 15 | if (ps.length && i > 2 && rand() < 0.3) ps.push(Math.floor(rand() * i)); |
| 16 | const uniq = [...new Set(ps)]; |
| 17 | parents.push(uniq); |
| 18 | const time = 1_700_000_000 + i * 60 + (skew ? Math.floor((rand() - 0.5) * 3600) : 0); |
| 19 | const sig: Signature = { name: "t", email: "t@example.com", timestamp: time, timezone: "+0000" }; |
| 20 | oids.push(await store.write("commit", serializeCommit({ tree: TREE, parents: uniq.map((p) => oids[p]!), author: sig, committer: sig, message: `${label}${i}\n` }))); |
| 21 | } |
| 22 | const reach: Set<number>[] = []; |
| 23 | for (let i = 0; i < n; i++) reach.push(new Set([i, ...parents[i]!.flatMap((p) => [...reach[p]!])])); |
| 24 | return { store, oids, reach }; |
| 25 | } |
| 26 | |
| 27 | describe("merge base", () => { |
| 28 | it("is a best common ancestor, the only one when there is one, on random histories with and without clock skew", async () => { |
| 29 | let checked = 0; |
| 30 | for (const skew of [false, true]) { |
| 31 | for (let seed = 1; seed <= 12; seed++) { |
| 32 | const { store, oids, reach } = await history(seed, 120, skew); |
| 33 | for (let k = 0; k < 40; k++) { |
| 34 | const a = (seed * 31 + k * 17) % oids.length; |
| 35 | const b = (seed * 7 + k * 53 + 11) % oids.length; |
| 36 | const common = [...reach[a]!].filter((c) => reach[b]!.has(c)); |
| 37 | const best = common.filter((c) => !common.some((o) => o !== c && reach[o]!.has(c))); |
| 38 | const got = await mergeBase(store, oids[a]!, oids[b]!); |
| 39 | if (!best.length) expect(got).toBeNull(); |
| 40 | else if (best.length === 1) expect(got).toBe(oids[best[0]!]); |
| 41 | else expect(best.map((c) => oids[c])).toContain(got); |
| 42 | expect(await isAncestor(store, oids[a]!, oids[b]!)).toBe(reach[b]!.has(a)); |
| 43 | expect(await isAncestor(store, oids[b]!, oids[a]!)).toBe(reach[a]!.has(b)); |
| 44 | checked++; |
| 45 | } |
| 46 | } |
| 47 | } |
| 48 | expect(checked).toBe(960); |
| 49 | }); |
| 50 | |
| 51 | it("handles the same commit, missing commits and unrelated histories", async () => { |
| 52 | const { store, oids } = await history(5, 10, false); |
| 53 | expect(await mergeBase(store, oids[3]!, oids[3]!)).toBe(oids[3]); |
| 54 | expect(await isAncestor(store, oids[3]!, oids[3]!)).toBe(true); |
| 55 | const missing = "0".repeat(39) + "1"; |
| 56 | expect(await mergeBase(store, missing, oids[3]!)).toBeNull(); |
| 57 | expect(await mergeBase(store, missing, missing)).toBeNull(); |
| 58 | expect(await isAncestor(store, missing, oids[3]!)).toBe(false); |
| 59 | const other = await history(9, 5, false, "other"); |
| 60 | for (const [oid, o] of other.store.objects) store.objects.set(oid, o); |
| 61 | expect(await mergeBase(store, oids[9]!, other.oids[4]!)).toBeNull(); |
| 62 | }); |
| 63 | |
| 64 | it("reads only the commits since the merge base, not the whole history", async () => { |
| 65 | const { store, oids } = await history(3, 400, false); |
| 66 | let reads = 0; |
| 67 | const counted = { read: (oid: string) => (reads++, store.read(oid)) }; |
| 68 | // Two branches a few commits off the newest one. |
| 69 | const tip = oids[399]!; |
| 70 | const sig: Signature = { name: "t", email: "t@example.com", timestamp: 1_800_000_000, timezone: "+0000" }; |
| 71 | const a = await store.write("commit", serializeCommit({ tree: TREE, parents: [tip], author: sig, committer: sig, message: "a\n" })); |
| 72 | const b = await store.write("commit", serializeCommit({ tree: TREE, parents: [tip], author: sig, committer: sig, message: "b\n" })); |
| 73 | expect(await mergeBase(counted, a, b)).toBe(tip); |
| 74 | expect(reads).toBeLessThan(20); |
| 75 | }); |
| 76 | }); |