Skip to content
rachel/git-on-cloudflare
File

Blob: test/pack-ref-index.test.ts

typescript713 lines
1import { assert, test } from "vitest";
2 
3import { hexToBytes } from "@/worker/common";
4import { objTypeCode, type GitObjectType } from "@/worker/git/core";
5import type { IdxView } from "@/worker/git/object-store/types";
6import {
7  getPackRefObjectType,
8  getPackRefRefsAt,
9  PackRefsBuilder,
10  parsePackRefView,
11  parseTreeClosureRefs,
12  type PackRefSnapshotEntry,
13} from "@/worker/git/pack/refIndex";
14import { allocateEntryTable, type PackEntryTable } from "@/worker/git/pack/indexer";
15import { computeNeededFromPackRefs } from "@/worker/git/operations/fetch/refClosure";
16 
17const HEADER_BYTES = 60;
18 
19function oid(prefix: string): string {
20  return prefix.padEnd(40, "0");
21}
22 
23function oidFromNumber(value: number): string {
24  return value.toString(16).padStart(40, "0");
25}
26 
27function makeIdxView(args: {
28  packKey: string;
29  count: number;
30  packSize: number;
31  packChecksum: Uint8Array;
32  idxChecksum: Uint8Array;
33  oids?: string[];
34}): IdxView {
35  const rawNames = new Uint8Array(args.count * 20);
36  const fanout = new Uint32Array(256);
37  const sortedOids = args.oids || Array.from({ length: args.count }, () => oid("00"));
38  if (sortedOids.length !== args.count) {
39    throw new Error("test idx view oid count mismatch");
40  }
41 
42  const firstByteCounts = new Uint32Array(256);
43  for (let index = 0; index < sortedOids.length; index++) {
44    const oidBytes = hexToBytes(sortedOids[index]!);
45    rawNames.set(oidBytes, index * 20);
46    firstByteCounts[oidBytes[0] || 0]++;
47  }
48 
49  let cumulative = 0;
50  for (let index = 0; index < fanout.length; index++) {
51    cumulative += firstByteCounts[index] || 0;
52    fanout[index] = cumulative;
53  }
54 
55  return {
56    packKey: args.packKey,
57    count: args.count,
58    fanout,
59    rawNames,
60    offsets: new Float64Array(args.count),
61    nextOffsetByIndex: new Float64Array(args.count),
62    sortedOffsets: new Float64Array(args.count),
63    sortedOffsetIndices: new Uint32Array(args.count),
64    packSize: args.packSize,
65    packChecksum: args.packChecksum,
66    idxChecksum: args.idxChecksum,
67  };
68}
69 
70function recordObject(args: {
71  table: PackEntryTable;
72  builder: PackRefsBuilder;
73  index: number;
74  oid: string;
75  type: GitObjectType;
76  payload: Uint8Array;
77}): void {
78  args.table.oids.set(hexToBytes(args.oid), args.index * 20);
79  args.table.objectTypes[args.index] = objTypeCode(args.type);
80  args.builder.recordObject(args.index, args.type, args.payload);
81}
82 
83function buildPackRefSnapshotEntry(args: {
84  packKey: string;
85  objects: Array<{
86    oid: string;
87    type: GitObjectType;
88    payload: Uint8Array;
89  }>;
90}): PackRefSnapshotEntry {
91  const packChecksum = hexToBytes(oid("aa"));
92  const idxChecksum = hexToBytes(oid("bb"));
93  const packSize = Math.max(256, args.objects.length * 64);
94  const table = allocateEntryTable(args.objects.length);
95  const builder = new PackRefsBuilder(args.objects.length);
96 
97  for (let index = 0; index < args.objects.length; index++) {
98    const object = args.objects[index]!;
99    recordObject({
100      table,
101      builder,
102      index,
103      oid: object.oid,
104      type: object.type,
105      payload: object.payload,
106    });
107  }
108 
109  const sortedOids = args.objects.map((object) => object.oid).sort();
110  const idx = makeIdxView({
111    packKey: args.packKey,
112    count: args.objects.length,
113    packSize,
114    packChecksum,
115    idxChecksum,
116    oids: sortedOids,
117  });
118  const built = builder.build({
119    table,
120    objectCount: args.objects.length,
121    packBytes: packSize,
122    packChecksum,
123    idxChecksum,
124  });
125  const parsed = parsePackRefView(args.packKey, built.bytes, idx);
126  if (parsed.type !== "Ready") {
127    throw new Error(`test sidecar failed to parse: ${parsed.type}`);
128  }
129 
130  return {
131    packKey: args.packKey,
132    packBytes: packSize,
133    idx,
134    refs: parsed.view,
135  };
136}
137 
138function treePayload(entries: Array<{ mode: string; name: string; oid: string }>): Uint8Array {
139  const encoder = new TextEncoder();
140  const parts: Uint8Array[] = [];
141  let total = 0;
142  for (const entry of entries) {
143    const header = encoder.encode(`${entry.mode} ${entry.name}`);
144    const oidBytes = hexToBytes(entry.oid);
145    parts.push(header, Uint8Array.from([0]), oidBytes);
146    total += header.byteLength + 1 + oidBytes.byteLength;
147  }
148  const out = new Uint8Array(total);
149  let offset = 0;
150  for (const part of parts) {
151    out.set(part, offset);
152    offset += part.byteLength;
153  }
154  return out;
155}
156 
157function buildSampleRefIndex() {
158  const packKey = "do/test/objects/pack/sample.pack";
159  const packChecksum = hexToBytes(oid("aa"));
160  const idxChecksum = hexToBytes(oid("bb"));
161  const packSize = 1234;
162  const table = allocateEntryTable(4);
163  const builder = new PackRefsBuilder(4);
164  const encoder = new TextEncoder();
165 
166  const blobOid = oid("40");
167  const treeOid = oid("20");
168  const parentOid = oid("50");
169  const tagTargetOid = oid("60");
170  const fileOid = oid("70");
171  const gitlinkOid = oid("80");
172 
173  recordObject({
174    table,
175    builder,
176    index: 0,
177    oid: oid("10"),
178    type: "commit",
179    payload: encoder.encode(`tree ${treeOid}\nparent ${parentOid}\n\nmessage\n`),
180  });
181  recordObject({
182    table,
183    builder,
184    index: 1,
185    oid: treeOid,
186    type: "tree",
187    payload: treePayload([
188      { mode: "100644", name: "file.txt", oid: fileOid },
189      { mode: "160000", name: "submodule", oid: gitlinkOid },
190    ]),
191  });
192  recordObject({
193    table,
194    builder,
195    index: 2,
196    oid: oid("30"),
197    type: "tag",
198    payload: encoder.encode(`object ${tagTargetOid}\ntype commit\ntag v1\n\nmessage\n`),
199  });
200  recordObject({
201    table,
202    builder,
203    index: 3,
204    oid: blobOid,
205    type: "blob",
206    payload: encoder.encode("blob\n"),
207  });
208 
209  const idx = makeIdxView({
210    packKey,
211    count: 4,
212    packSize,
213    packChecksum,
214    idxChecksum,
215  });
216  const built = builder.build({
217    table,
218    objectCount: 4,
219    packBytes: packSize,
220    packChecksum,
221    idxChecksum,
222  });
223 
224  return { built, idx, refs: { treeOid, parentOid, fileOid, tagTargetOid } };
225}
226 
227test("pack ref sidecar encodes and parses logical object refs", () => {
228  const { built, idx, refs } = buildSampleRefIndex();
229  const parsed = parsePackRefView(idx.packKey, built.bytes, idx);
230 
231  assert.strictEqual(parsed.type, "Ready");
232  if (parsed.type !== "Ready") return;
233 
234  assert.strictEqual(parsed.view.objectCount, 4);
235  assert.strictEqual(parsed.view.refStartsBytes.byteLength, 5 * 4);
236  assert.strictEqual(getPackRefObjectType(parsed.view, 0), "commit");
237  assert.deepEqual(getPackRefRefsAt(parsed.view, 0), [refs.treeOid, refs.parentOid]);
238  assert.strictEqual(getPackRefObjectType(parsed.view, 1), "tree");
239  assert.deepEqual(getPackRefRefsAt(parsed.view, 1), [refs.fileOid]);
240  assert.strictEqual(getPackRefObjectType(parsed.view, 2), "tag");
241  assert.deepEqual(getPackRefRefsAt(parsed.view, 2), [refs.tagTargetOid]);
242  assert.strictEqual(getPackRefObjectType(parsed.view, 3), "blob");
243  assert.deepEqual(getPackRefRefsAt(parsed.view, 3), []);
244});
245 
246test("tree closure parser excludes gitlinks", () => {
247  const fileOid = oid("11");
248  const gitlinkOid = oid("22");
249  const refs = parseTreeClosureRefs(
250    treePayload([
251      { mode: "100644", name: "file.txt", oid: fileOid },
252      { mode: "160000", name: "submodule", oid: gitlinkOid },
253      { mode: "40000", name: "dir", oid: oid("33") },
254    ])
255  );
256 
257  assert.deepEqual(refs, [fileOid, oid("33")]);
258});
259 
260test("pack ref sidecar keeps duplicate OID ordering deterministic", () => {
261  const packKey = "do/test/objects/pack/dupe.pack";
262  const packChecksum = hexToBytes(oid("aa"));
263  const idxChecksum = hexToBytes(oid("bb"));
264  const table = allocateEntryTable(2);
265  const builder = new PackRefsBuilder(2);
266  const encoder = new TextEncoder();
267  const duplicateOid = oid("10");
268  const treeA = oid("20");
269  const treeB = oid("30");
270 
271  recordObject({
272    table,
273    builder,
274    index: 0,
275    oid: duplicateOid,
276    type: "commit",
277    payload: encoder.encode(`tree ${treeA}\n\nfirst\n`),
278  });
279  recordObject({
280    table,
281    builder,
282    index: 1,
283    oid: duplicateOid,
284    type: "commit",
285    payload: encoder.encode(`tree ${treeB}\n\nsecond\n`),
286  });
287 
288  const idx = makeIdxView({
289    packKey,
290    count: 2,
291    packSize: 200,
292    packChecksum,
293    idxChecksum,
294  });
295  const built = builder.build({
296    table,
297    objectCount: 2,
298    packBytes: 200,
299    packChecksum,
300    idxChecksum,
301  });
302  const parsed = parsePackRefView(packKey, built.bytes, idx);
303 
304  assert.strictEqual(parsed.type, "Ready");
305  if (parsed.type !== "Ready") return;
306  assert.deepEqual(getPackRefRefsAt(parsed.view, 0), [treeA]);
307  assert.deepEqual(getPackRefRefsAt(parsed.view, 1), [treeB]);
308});
309 
310test("sidecar closure walks a wide graph with a cursor queue", async () => {
311  const packKey = "do/test/objects/pack/wide.pack";
312  const packChecksum = hexToBytes(oid("aa"));
313  const idxChecksum = hexToBytes(oid("bb"));
314  const blobCount = 4096;
315  const objectCount = blobCount + 2;
316  const packSize = 200_000;
317  const table = allocateEntryTable(objectCount);
318  const builder = new PackRefsBuilder(objectCount);
319  const encoder = new TextEncoder();
320 
321  const commitOid = oidFromNumber(1);
322  const treeOid = oidFromNumber(2);
323  const blobOids = Array.from({ length: blobCount }, (_value, index) => oidFromNumber(index + 3));
324 
325  recordObject({
326    table,
327    builder,
328    index: 0,
329    oid: commitOid,
330    type: "commit",
331    payload: encoder.encode(`tree ${treeOid}\n\nwide\n`),
332  });
333  recordObject({
334    table,
335    builder,
336    index: 1,
337    oid: treeOid,
338    type: "tree",
339    payload: treePayload(
340      blobOids.map((entryOid, index) => ({
341        mode: "100644",
342        name: `file-${index}.txt`,
343        oid: entryOid,
344      }))
345    ),
346  });
347 
348  const emptyBlob = new Uint8Array(0);
349  for (let index = 0; index < blobOids.length; index++) {
350    recordObject({
351      table,
352      builder,
353      index: index + 2,
354      oid: blobOids[index]!,
355      type: "blob",
356      payload: emptyBlob,
357    });
358  }
359 
360  const sortedOids = [commitOid, treeOid, ...blobOids].sort();
361  const idx = makeIdxView({
362    packKey,
363    count: objectCount,
364    packSize,
365    packChecksum,
366    idxChecksum,
367    oids: sortedOids,
368  });
369  const built = builder.build({
370    table,
371    objectCount,
372    packBytes: packSize,
373    packChecksum,
374    idxChecksum,
375  });
376  const parsed = parsePackRefView(packKey, built.bytes, idx);
377  assert.strictEqual(parsed.type, "Ready");
378  if (parsed.type !== "Ready") return;
379 
380  const closure = await computeNeededFromPackRefs({
381    repoId: "test/wide",
382    packs: [{ packKey, packBytes: packSize, idx, refs: parsed.view }],
383    wants: [commitOid, commitOid],
384    haves: [],
385  });
386 
387  assert.strictEqual(closure.type, "Ready");
388  if (closure.type !== "Ready") return;
389  assert.strictEqual(closure.neededOids.length, objectCount);
390  assert.strictEqual(new Set(closure.neededOids).size, objectCount);
391  assert.isTrue(closure.neededOids.includes(commitOid));
392  assert.isTrue(closure.neededOids.includes(treeOid));
393  assert.isTrue(closure.neededOids.includes(blobOids[blobOids.length - 1]!));
394});
395 
396test("sidecar closure queues duplicate wants once", async () => {
397  const blobOid = oid("11");
398  const pack = buildPackRefSnapshotEntry({
399    packKey: "do/test/objects/pack/duplicate-wants.pack",
400    objects: [
401      {
402        oid: blobOid,
403        type: "blob",
404        payload: new TextEncoder().encode("content\n"),
405      },
406    ],
407  });
408 
409  const closure = await computeNeededFromPackRefs({
410    repoId: "test/duplicate-wants",
411    packs: [pack],
412    wants: [blobOid, blobOid],
413    haves: [],
414  });
415 
416  assert.strictEqual(closure.type, "Ready");
417  if (closure.type !== "Ready") return;
418  assert.deepEqual(closure.neededOids, [blobOid]);
419  assert.strictEqual(closure.stats.indexedObjects, 1);
420  assert.strictEqual(closure.stats.queued, 1);
421  assert.strictEqual(closure.stats.seen, 1);
422  assert.strictEqual(closure.stats.needed, 1);
423  assert.strictEqual(closure.stats.duplicateQueueSkips, 1);
424});
425 
426test("sidecar closure does not grow the queue for duplicate tree edges", async () => {
427  const encoder = new TextEncoder();
428  const commitOid = oid("10");
429  const treeOid = oid("20");
430  const blobOid = oid("30");
431  const duplicateEntries = 4096;
432  const pack = buildPackRefSnapshotEntry({
433    packKey: "do/test/objects/pack/duplicate-tree-edges.pack",
434    objects: [
435      {
436        oid: commitOid,
437        type: "commit",
438        payload: encoder.encode(`tree ${treeOid}\n\nmessage\n`),
439      },
440      {
441        oid: treeOid,
442        type: "tree",
443        payload: treePayload(
444          Array.from({ length: duplicateEntries }, (_value, index) => ({
445            mode: "100644",
446            name: `file-${index}.txt`,
447            oid: blobOid,
448          }))
449        ),
450      },
451      {
452        oid: blobOid,
453        type: "blob",
454        payload: encoder.encode("same blob\n"),
455      },
456    ],
457  });
458 
459  const closure = await computeNeededFromPackRefs({
460    repoId: "test/duplicate-tree-edges",
461    packs: [pack],
462    wants: [commitOid],
463    haves: [],
464  });
465 
466  assert.strictEqual(closure.type, "Ready");
467  if (closure.type !== "Ready") return;
468  assert.strictEqual(closure.neededOids.length, 3);
469  assert.strictEqual(closure.stats.queued, 3);
470  assert.strictEqual(closure.stats.seen, 3);
471  assert.strictEqual(closure.stats.edgeVisits, duplicateEntries + 1);
472  assert.strictEqual(closure.stats.duplicateQueueSkips, duplicateEntries - 1);
473});
474 
475test("sidecar closure canonicalizes cross-pack duplicate OIDs by snapshot order", async () => {
476  const encoder = new TextEncoder();
477  const duplicateCommitOid = oid("10");
478  const newerTreeOid = oid("20");
479  const olderTreeOid = oid("30");
480  const newerPack = buildPackRefSnapshotEntry({
481    packKey: "do/test/objects/pack/newer.pack",
482    objects: [
483      {
484        oid: duplicateCommitOid,
485        type: "commit",
486        payload: encoder.encode(`tree ${newerTreeOid}\n\nnew\n`),
487      },
488      {
489        oid: newerTreeOid,
490        type: "tree",
491        payload: treePayload([]),
492      },
493    ],
494  });
495  const olderPack = buildPackRefSnapshotEntry({
496    packKey: "do/test/objects/pack/older.pack",
497    objects: [
498      {
499        oid: duplicateCommitOid,
500        type: "commit",
501        payload: encoder.encode(`tree ${olderTreeOid}\n\nold\n`),
502      },
503      {
504        oid: olderTreeOid,
505        type: "tree",
506        payload: treePayload([]),
507      },
508    ],
509  });
510 
511  const closure = await computeNeededFromPackRefs({
512    repoId: "test/cross-pack-duplicate",
513    packs: [newerPack, olderPack],
514    wants: [duplicateCommitOid],
515    haves: [],
516  });
517 
518  assert.strictEqual(closure.type, "Ready");
519  if (closure.type !== "Ready") return;
520  assert.isTrue(closure.neededOids.includes(duplicateCommitOid));
521  assert.isTrue(closure.neededOids.includes(newerTreeOid));
522  assert.isFalse(closure.neededOids.includes(olderTreeOid));
523  assert.strictEqual(closure.stats.queued, 2);
524  assert.strictEqual(closure.stats.needed, 2);
525});
526 
527test("sidecar closure keeps force-push overlap bounded by canonical active objects", async () => {
528  const encoder = new TextEncoder();
529  const commitOid = oid("10");
530  const treeOid = oid("20");
531  const blobOid = oid("30");
532  const newerPack = buildPackRefSnapshotEntry({
533    packKey: "do/test/objects/pack/force-newer.pack",
534    objects: [
535      {
536        oid: commitOid,
537        type: "commit",
538        payload: encoder.encode(`tree ${treeOid}\n\nforce push\n`),
539      },
540      {
541        oid: treeOid,
542        type: "tree",
543        payload: treePayload([{ mode: "100644", name: "file.txt", oid: blobOid }]),
544      },
545      {
546        oid: blobOid,
547        type: "blob",
548        payload: encoder.encode("overlap\n"),
549      },
550    ],
551  });
552  const olderPack = buildPackRefSnapshotEntry({
553    packKey: "do/test/objects/pack/force-older.pack",
554    objects: [
555      {
556        oid: blobOid,
557        type: "blob",
558        payload: encoder.encode("overlap\n"),
559      },
560    ],
561  });
562 
563  const closure = await computeNeededFromPackRefs({
564    repoId: "test/force-overlap",
565    packs: [newerPack, olderPack],
566    wants: [commitOid],
567    haves: [oid("99")],
568  });
569 
570  assert.strictEqual(closure.type, "Ready");
571  if (closure.type !== "Ready") return;
572  assert.deepEqual(new Set(closure.neededOids), new Set([commitOid, treeOid, blobOid]));
573  assert.strictEqual(closure.stats.indexedObjects, 4);
574  assert.strictEqual(closure.stats.queued, 3);
575  assert.strictEqual(closure.stats.seen, 3);
576  assert.strictEqual(closure.stats.needed, 3);
577});
578 
579test("sidecar closure returns a retryable budget result at the missing ref cap", async () => {
580  const treeOid = oid("20");
581  const missingEntries = 1025;
582  const pack = buildPackRefSnapshotEntry({
583    packKey: "do/test/objects/pack/missing-ref-budget.pack",
584    objects: [
585      {
586        oid: treeOid,
587        type: "tree",
588        payload: treePayload(
589          Array.from({ length: missingEntries }, (_value, index) => ({
590            mode: "100644",
591            name: `missing-${index}.txt`,
592            oid: oidFromNumber(index + 1),
593          }))
594        ),
595      },
596    ],
597  });
598 
599  const closure = await computeNeededFromPackRefs({
600    repoId: "test/missing-ref-budget",
601    packs: [pack],
602    wants: [treeOid],
603    haves: [],
604  });
605 
606  assert.strictEqual(closure.type, "BudgetExceeded");
607  if (closure.type !== "BudgetExceeded") return;
608  assert.strictEqual(closure.reason, "missing-ref-budget");
609  assert.strictEqual(closure.stats.queued, 1);
610  assert.strictEqual(closure.stats.seen, 1);
611  assert.strictEqual(closure.stats.missing, 1024);
612});
613 
614test("pack ref sidecar parser rejects invalid artifacts", () => {
615  const { built, idx } = buildSampleRefIndex();
616  const cases: Array<{ name: string; mutate: (bytes: Uint8Array) => Uint8Array; reason: string }> =
617    [
618      {
619        name: "bad magic",
620        mutate(bytes) {
621          bytes[0] = 0;
622          return bytes;
623        },
624        reason: "bad-magic",
625      },
626      {
627        name: "bad version",
628        mutate(bytes) {
629          new DataView(bytes.buffer, bytes.byteOffset, bytes.byteLength).setUint32(4, 2, false);
630          return bytes;
631        },
632        reason: "bad-version",
633      },
634      {
635        name: "count mismatch",
636        mutate(bytes) {
637          new DataView(bytes.buffer, bytes.byteOffset, bytes.byteLength).setUint32(8, 99, false);
638          return bytes;
639        },
640        reason: "object-count-mismatch",
641      },
642      {
643        name: "pack bytes mismatch",
644        mutate(bytes) {
645          new DataView(bytes.buffer, bytes.byteOffset, bytes.byteLength).setUint32(16, 999, false);
646          return bytes;
647        },
648        reason: "pack-bytes-mismatch",
649      },
650      {
651        name: "pack checksum mismatch",
652        mutate(bytes) {
653          bytes[20] ^= 0xff;
654          return bytes;
655        },
656        reason: "pack-checksum-mismatch",
657      },
658      {
659        name: "idx checksum mismatch",
660        mutate(bytes) {
661          bytes[40] ^= 0xff;
662          return bytes;
663        },
664        reason: "idx-checksum-mismatch",
665      },
666      {
667        name: "invalid type code",
668        mutate(bytes) {
669          bytes[HEADER_BYTES] = 9;
670          return bytes;
671        },
672        reason: "invalid-type-code",
673      },
674      {
675        name: "truncated type codes",
676        mutate(bytes) {
677          return bytes.slice(0, HEADER_BYTES + 1);
678        },
679        reason: "truncated-type-codes",
680      },
681      {
682        name: "non-monotonic starts",
683        mutate(bytes) {
684          const dv = new DataView(bytes.buffer, bytes.byteOffset, bytes.byteLength);
685          const startsOffset = HEADER_BYTES + idx.count;
686          dv.setUint32(startsOffset, 2, false);
687          dv.setUint32(startsOffset + 4, 1, false);
688          return bytes;
689        },
690        reason: "non-monotonic-ref-starts",
691      },
692      {
693        name: "bad final offset",
694        mutate(bytes) {
695          const dv = new DataView(bytes.buffer, bytes.byteOffset, bytes.byteLength);
696          const finalStartOffset = HEADER_BYTES + idx.count + idx.count * 4;
697          dv.setUint32(finalStartOffset, 999, false);
698          return bytes;
699        },
700        reason: "invalid-final-ref-offset",
701      },
702    ];
703 
704  for (const entry of cases) {
705    const mutated = entry.mutate(new Uint8Array(built.bytes));
706    const parsed = parsePackRefView(idx.packKey, mutated, idx);
707    assert.strictEqual(parsed.type, "Invalid", entry.name);
708    if (parsed.type === "Invalid") {
709      assert.strictEqual(parsed.reason, entry.reason, entry.name);
710    }
711  }
712});