| 1 | import { describe, expect, it } from "vitest"; |
| 2 | import { DatabaseSync } from "node:sqlite"; |
| 3 | import { randomBytes } from "node:crypto"; |
| 4 | import { execFileSync } from "node:child_process"; |
| 5 | import { mkdtempSync, writeFileSync } from "node:fs"; |
| 6 | import { tmpdir } from "node:os"; |
| 7 | import { join } from "node:path"; |
| 8 | import { deflate, hashObject, inflate, parsePack, utf8 } from "@diffinery/git-core"; |
| 9 | import { commitParents, historyOrder, memorySource, packedContents, repositoryBases, streamedContents } from "../../src/git/push-contents.js"; |
| 10 | import { RepoObjectStore } from "../../src/repo/objects.js"; |
| 11 | import { REPO_SCHEMA, migrateRepoSchema } from "../../src/repo/schema.js"; |
| 12 | |
| 13 | /** A minimal SqlStorage over node:sqlite with the repository schema (RETURNING gives rows back too). */ |
| 14 | function sqlStorage(): SqlStorage { |
| 15 | const db = new DatabaseSync(":memory:"); |
| 16 | db.exec(REPO_SCHEMA); |
| 17 | const sql = { |
| 18 | exec(query: string, ...bindings: unknown[]) { |
| 19 | const stmt = db.prepare(query); |
| 20 | const rows = /^\s*select|returning/i.test(query) ? stmt.all(...(bindings as never[])) : (stmt.run(...(bindings as never[])), []); |
| 21 | return { toArray: () => rows, one: () => rows[0] } as unknown as SqlStorageCursor<Record<string, SqlStorageValue>>; |
| 22 | }, |
| 23 | } as unknown as SqlStorage; |
| 24 | migrateRepoSchema(sql); |
| 25 | return sql; |
| 26 | } |
| 27 | |
| 28 | function setup() { |
| 29 | const sql = sqlStorage(); |
| 30 | const r2 = new Map<string, Uint8Array>(); |
| 31 | const bucket = { |
| 32 | put: async (key: string, body: Uint8Array | ReadableStream) => void r2.set(key, body instanceof ReadableStream ? new Uint8Array(await new Response(body).arrayBuffer()) : body), |
| 33 | get: async (key: string) => { |
| 34 | const v = r2.get(key); |
| 35 | return v ? { arrayBuffer: async () => v.slice().buffer } : null; |
| 36 | }, |
| 37 | } as unknown as R2Bucket; |
| 38 | let added = 0; |
| 39 | const store = new RepoObjectStore(sql, bucket, "r1", () => added++); |
| 40 | return { sql, r2, store, added: () => added }; |
| 41 | } |
| 42 | |
| 43 | describe("reading objects for a clone", () => { |
| 44 | it("reads them in batches, in the order asked, from SQLite and R2", async () => { |
| 45 | const { sql, store } = setup(); |
| 46 | const oids: string[] = []; |
| 47 | for (let i = 0; i < 250; i++) oids.push(await store.write("blob", utf8(`object ${i}\n`))); |
| 48 | // Two large ones in R2 among them, and one asked for twice. |
| 49 | oids.splice(40, 0, await store.write("blob", new Uint8Array(randomBytes(700 * 1024)))); |
| 50 | oids.splice(180, 0, await store.write("blob", new Uint8Array(randomBytes(600 * 1024)))); |
| 51 | oids.push(oids[3]!); |
| 52 | const want = await Promise.all(oids.map((o) => store.readRaw(o))); |
| 53 | let queries = 0; |
| 54 | const exec = sql.exec.bind(sql); |
| 55 | sql.exec = ((q: string, ...b: unknown[]) => (queries++, exec(q, ...(b as never[])))) as typeof sql.exec; |
| 56 | const got = []; |
| 57 | for await (const raw of store.readRawAll(oids)) got.push(raw); |
| 58 | expect(got.length).toBe(oids.length); |
| 59 | got.forEach((raw, i) => { |
| 60 | expect(raw.type).toBe(want[i]!.type); |
| 61 | expect(raw.size).toBe(want[i]!.size); |
| 62 | expect(Buffer.from(raw.deflated).equals(Buffer.from(want[i]!.deflated)), `object ${i}`).toBe(true); |
| 63 | }); |
| 64 | // Two queries per hundred objects, not one per object. |
| 65 | expect(queries).toBeLessThanOrEqual(6); |
| 66 | }); |
| 67 | |
| 68 | it("keeps a batch's inline data under its cap, and stops at an object that isn't stored", async () => { |
| 69 | const { sql, store } = setup(); |
| 70 | // 400 KB objects (incompressible, kept inline): ten of them pass the 4 MiB cap. |
| 71 | const oids: string[] = []; |
| 72 | for (let i = 0; i < 12; i++) oids.push(await store.write("blob", new Uint8Array(randomBytes(400 * 1024)))); |
| 73 | const sizes: number[] = []; |
| 74 | const exec = sql.exec.bind(sql); |
| 75 | sql.exec = ((q: string, ...b: unknown[]) => (/SELECT oid, data/.test(q) && sizes.push(b.length), exec(q, ...(b as never[])))) as typeof sql.exec; |
| 76 | let n = 0; |
| 77 | for await (const raw of store.readRawAll(oids)) n += raw.size > 0 ? 1 : 0; |
| 78 | expect(n).toBe(12); |
| 79 | expect(sizes.length).toBeGreaterThan(1); |
| 80 | expect(Math.max(...sizes)).toBeLessThanOrEqual(10); |
| 81 | const missing = "0".repeat(40); |
| 82 | const seen: number[] = []; |
| 83 | await expect( |
| 84 | (async () => { |
| 85 | for await (const raw of store.readRawAll([oids[0]!, missing, oids[1]!])) seen.push(raw.size); |
| 86 | })(), |
| 87 | ).rejects.toThrow(`missing object ${missing}`); |
| 88 | expect(seen.length).toBe(1); |
| 89 | }); |
| 90 | }); |
| 91 | |
| 92 | describe("git object storage accounting", () => { |
| 93 | it("keeps a running total of the compressed bytes stored, counting each object once", async () => { |
| 94 | const { store, r2, added } = setup(); |
| 95 | expect(store.sizeBytes()).toBe(0); |
| 96 | const text = utf8("hello\n".repeat(1000)); |
| 97 | await store.write("blob", text); |
| 98 | await store.write("blob", text); |
| 99 | expect(store.sizeBytes()).toBe(deflate(text).length); |
| 100 | expect(added()).toBe(1); |
| 101 | // Large objects go to R2 and count what R2 keeps. |
| 102 | const big = new Uint8Array(randomBytes(700 * 1024)); |
| 103 | await store.write("blob", big); |
| 104 | expect(r2.size).toBe(1); |
| 105 | expect(store.sizeBytes()).toBe(deflate(text).length + deflate(big).length); |
| 106 | // A pushed object stored from its zlib data counts that. |
| 107 | const small = utf8("pushed\n"); |
| 108 | await store.writeDeflated(await hashObject("blob", small), "blob", small.length, deflate(small)); |
| 109 | expect(store.sizeBytes()).toBe(deflate(text).length + deflate(big).length + deflate(small).length); |
| 110 | expect(added()).toBe(3); |
| 111 | }); |
| 112 | |
| 113 | it("adds up a repository from before the total was kept, and again after objects were deleted", async () => { |
| 114 | const { sql, store } = setup(); |
| 115 | // Rows as older code wrote them: no stored size; an R2 object counts its inflated size. |
| 116 | sql.exec("INSERT INTO objects (oid, type, size, data, r2) VALUES ('a', 3, 10, ?, 0)", new Uint8Array(4)); |
| 117 | sql.exec("INSERT INTO objects (oid, type, size, data, r2) VALUES ('b', 3, 900000, NULL, 1)"); |
| 118 | expect(store.sizeBytes()).toBe(4 + 900000); |
| 119 | await store.write("blob", utf8("new\n")); |
| 120 | expect(store.sizeBytes()).toBe(4 + 900000 + deflate(utf8("new\n")).length); |
| 121 | // A purge deletes objects, then has the total added up again. |
| 122 | sql.exec("DELETE FROM objects WHERE oid = 'b'"); |
| 123 | store.recount(); |
| 124 | expect(store.sizeBytes()).toBe(4 + deflate(utf8("new\n")).length); |
| 125 | }); |
| 126 | |
| 127 | it("compresses a large object a chunk at a time to store it, to the same zlib data", async () => { |
| 128 | const { store, r2 } = setup(); |
| 129 | // Random: its zlib data goes to R2. Text: small enough compressed to stay in SQLite. |
| 130 | const random = new Uint8Array(randomBytes(3 * 1024 * 1024)); |
| 131 | const text = utf8("a line of a large text file\n".repeat(120_000)); |
| 132 | for (const content of [random, text]) { |
| 133 | const oid = await hashObject("blob", content); |
| 134 | await store.writeKnown(oid, "blob", content, false); |
| 135 | const raw = (await store.readRaw(oid))!; |
| 136 | expect(Buffer.from(raw.deflated).equals(Buffer.from(deflate(content)))).toBe(true); |
| 137 | expect(Buffer.from(inflate(raw.deflated)).equals(Buffer.from(content))).toBe(true); |
| 138 | expect(store.readCost(oid)).toBe(content.length + raw.deflated.length); |
| 139 | expect(Buffer.from((await store.read(oid))!.content).equals(Buffer.from(content))).toBe(true); |
| 140 | } |
| 141 | expect(r2.size).toBe(1); |
| 142 | }); |
| 143 | |
| 144 | it("gives a thin pack's bases only when reading them fits, saying what they would take otherwise", async () => { |
| 145 | const { store } = setup(); |
| 146 | const zeros = new Uint8Array(8 * 1024 * 1024); |
| 147 | const oid = await store.write("blob", zeros); |
| 148 | const lookup = repositoryBases(store); |
| 149 | const cost = store.readCost(oid)!; |
| 150 | expect(cost).toBeGreaterThan(zeros.length); |
| 151 | expect(await lookup(oid, cost - 1)).toBe(cost); |
| 152 | expect(((await lookup(oid, cost)) as { content: Uint8Array }).content.length).toBe(zeros.length); |
| 153 | expect(await lookup("0".repeat(40), cost)).toBeNull(); |
| 154 | }); |
| 155 | }); |
| 156 | |
| 157 | const git = (cwd: string, ...args: string[]) => |
| 158 | execFileSync("git", args, { cwd, env: { ...process.env, GIT_AUTHOR_NAME: "T", GIT_AUTHOR_EMAIL: "t@x", GIT_COMMITTER_NAME: "T", GIT_COMMITTER_EMAIL: "t@x" } }); |
| 159 | |
| 160 | /** A history with a merge and a tag, packed as git sends it: newest commits first, files last. */ |
| 161 | function historyPack(): { pack: Uint8Array; commits: Map<string, string[]>; tag: string } { |
| 162 | const dir = mkdtempSync(join(tmpdir(), "order-")); |
| 163 | git(dir, "init", "-q", "-b", "main"); |
| 164 | const text = Array.from({ length: 300 }, (_, i) => `line ${i} of a file long enough for deltas`).join("\n"); |
| 165 | writeFileSync(join(dir, "a.txt"), text); |
| 166 | git(dir, "add", "-A"); |
| 167 | git(dir, "commit", "-q", "-m", "one"); |
| 168 | git(dir, "checkout", "-q", "-b", "side"); |
| 169 | writeFileSync(join(dir, "b.txt"), "side\n"); |
| 170 | git(dir, "add", "-A"); |
| 171 | git(dir, "commit", "-q", "-m", "side"); |
| 172 | git(dir, "checkout", "-q", "main"); |
| 173 | for (let i = 0; i < 3; i++) { |
| 174 | writeFileSync(join(dir, "a.txt"), text.replace(`line ${i * 50}`, `LINE ${i * 50}`)); |
| 175 | git(dir, "commit", "-qam", `main ${i}`); |
| 176 | } |
| 177 | git(dir, "merge", "-q", "--no-edit", "side"); |
| 178 | git(dir, "tag", "-a", "v1", "-m", "release"); |
| 179 | const commits = new Map<string, string[]>(); |
| 180 | for (const line of git(dir, "rev-list", "--parents", "--all").toString().trim().split("\n")) { |
| 181 | const [oid, ...parents] = line.split(" "); |
| 182 | commits.set(oid!, parents); |
| 183 | } |
| 184 | const tag = git(dir, "rev-parse", "v1").toString().trim(); |
| 185 | const pack = execFileSync("git", ["pack-objects", "--stdout", "--revs", "--all", "--delta-base-offset"], { cwd: dir, input: "" }); |
| 186 | return { pack: new Uint8Array(pack), commits, tag }; |
| 187 | } |
| 188 | |
| 189 | /** The oids `store` is asked to store, in order. */ |
| 190 | function recordWrites(store: RepoObjectStore): string[] { |
| 191 | const order: string[] = []; |
| 192 | for (const m of ["writeKnown", "writeDeflated", "writeDeflatedSlices"] as const) { |
| 193 | const real = (store[m] as (...a: unknown[]) => Promise<void>).bind(store); |
| 194 | (store as unknown as Record<string, unknown>)[m] = (oid: string, ...rest: unknown[]) => (order.push(oid), real(oid, ...rest)); |
| 195 | } |
| 196 | return order; |
| 197 | } |
| 198 | |
| 199 | /** Every commit is stored after every file and tree, and after its parents; the tag last. */ |
| 200 | function expectHistoryOrder(order: string[], commits: Map<string, string[]>, tag: string) { |
| 201 | const at = new Map(order.map((oid, i) => [oid, i])); |
| 202 | expect(new Set(order).size).toBe(order.length); |
| 203 | const firstCommit = Math.min(...[...commits.keys()].map((c) => at.get(c)!)); |
| 204 | expect(order.slice(firstCommit).every((oid) => commits.has(oid) || oid === tag)).toBe(true); |
| 205 | for (const [c, parents] of commits) for (const p of parents) expect(at.get(p)!).toBeLessThan(at.get(c)!); |
| 206 | expect(at.get(tag)).toBe(order.length - 1); |
| 207 | } |
| 208 | |
| 209 | describe("the order a push is stored in", () => { |
| 210 | it("reads a commit's parents from its header only", () => { |
| 211 | const a = "a".repeat(40), b = "b".repeat(40), c = "c".repeat(40); |
| 212 | expect(commitParents(utf8(`tree ${c}\nparent ${a}\nparent ${b}\nauthor T <t@x> 1 +0000\n\nparent ${c}\n`))).toEqual([a, b]); |
| 213 | expect(commitParents(utf8(`tree ${c}\nauthor T <t@x> 1 +0000\n\nroot\n`))).toEqual([]); |
| 214 | }); |
| 215 | |
| 216 | it("puts each commit after its parents however deep the history, and everything else after", () => { |
| 217 | const n = 50_000; |
| 218 | const oid = (i: number) => i.toString(16).padStart(40, "0"); |
| 219 | // Newest first, as a pack lists them, with a tree in between and a parent outside the push. |
| 220 | const items = [{ oid: "t".repeat(40), type: "tag" }, ...Array.from({ length: n }, (_, k) => ({ oid: oid(n - k), type: "commit" }))]; |
| 221 | const parents = (t: { oid: string }) => { const i = parseInt(t.oid, 16); return [oid(i - 1)]; }; |
| 222 | const out = historyOrder(items, parents); |
| 223 | expect(out.length).toBe(n + 1); |
| 224 | expect(out.slice(0, n).map((t) => t.oid)).toEqual(Array.from({ length: n }, (_, k) => oid(k + 1))); |
| 225 | expect(out[n]!.type).toBe("tag"); |
| 226 | }); |
| 227 | |
| 228 | it("stores a pack parsed in memory files and trees first, then commits after their parents, then tags", async () => { |
| 229 | const { pack, commits, tag } = historyPack(); |
| 230 | const { store } = setup(); |
| 231 | const order = recordWrites(store); |
| 232 | const objects = await parsePack(pack); |
| 233 | // git sends the newest commits first: stored as they come, a cut-off push would leave commits without their files. |
| 234 | expect(objects.findIndex((o) => o.type === "commit")).toBeLessThan(objects.findIndex((o) => o.type === "blob")); |
| 235 | await packedContents(store, objects, pack.length).write(); |
| 236 | expect(order.length).toBe(objects.length); |
| 237 | expectHistoryOrder(order, commits, tag); |
| 238 | }); |
| 239 | |
| 240 | it("stores a pack unpacked in pieces in the same order", async () => { |
| 241 | const { pack, commits, tag } = historyPack(); |
| 242 | const { store } = setup(); |
| 243 | const contents = await streamedContents(store, memorySource(pack), { largeObjectBytes: 4 * 1024 * 1024 }); |
| 244 | expect(contents.fsck()).toBeNull(); |
| 245 | const order = recordWrites(store); |
| 246 | await contents.write(); |
| 247 | expectHistoryOrder(order, commits, tag); |
| 248 | for (const c of commits.keys()) expect(store.has(c)).toBe(true); |
| 249 | }); |
| 250 | }); |