1
import { describe, expect, it } from "vitest";
2
import { env } from "cloudflare:workers";
3
import { concatChunks } from "@/worker/git";
4
import { bytesToHex, createLogger } from "@/worker/common";
5
import { computeOid } from "@/worker/git/core/objects";
6
import { rewritePack } from "@/worker/git/pack/rewrite";
7
import { buildOutputOrder, buildSelection } from "@/worker/git/pack/rewrite/plan";
8
import type { PackCatalogRow } from "@/worker/do/repo/db/schema";
9
import { buildAppendOnlyDelta, buildPack } from "./util/test-helpers";
10
import { indexTestPack } from "./util/test-indexer";
11
 
12
function encodeDeltaVarint(value: number): Uint8Array {
13
  const out: number[] = [];
14
  do {
15
    let byte = value & 0x7f;
16
    value >>>= 7;
17
    if (value > 0) byte |= 0x80;
18
    out.push(byte);
19
  } while (value > 0);
20
  return Uint8Array.from(out);
21
}
22
 
23
function buildCopyPrefixDelta(base: Uint8Array, prefixLength: number): Uint8Array {
24
  return Uint8Array.from([
25
    ...encodeDeltaVarint(base.length),
26
    ...encodeDeltaVarint(prefixLength),
27
    0x90,
28
    prefixLength,
29
  ]);
30
}
31
 
32
async function readStreamBytes(stream: ReadableStream<Uint8Array>): Promise<Uint8Array> {
33
  const reader = stream.getReader();
34
  const chunks: Uint8Array[] = [];
35
  while (true) {
36
    const { done, value } = await reader.read();
37
    if (done) break;
38
    if (value) chunks.push(value);
39
  }
40
  return concatChunks(chunks);
41
}
42
 
43
describe("pack rewrite cycles", () => {
44
  it("skips a cyclic selected REF_DELTA base duplicate and chooses an older alternate", async () => {
45
    const seedPayload = new TextEncoder().encode("seed\n");
46
    const aSuffix = new TextEncoder().encode("a\n");
47
    const aPayload = new Uint8Array(seedPayload.length + aSuffix.length);
48
    aPayload.set(seedPayload, 0);
49
    aPayload.set(aSuffix, seedPayload.length);
50
 
51
    const bSuffix = new TextEncoder().encode("b\n");
52
    const bPayload = new Uint8Array(aPayload.length + bSuffix.length);
53
    bPayload.set(aPayload, 0);
54
    bPayload.set(bSuffix, aPayload.length);
55
 
56
    const aOid = await computeOid("blob", aPayload);
57
    const bOid = await computeOid("blob", bPayload);
58
 
59
    const olderPackBytes = await buildPack([
60
      { type: "blob", payload: seedPayload },
61
      { type: "ofs-delta", baseIndex: 0, delta: buildAppendOnlyDelta(seedPayload, aSuffix) },
62
    ]);
63
    const middlePackBytes = await buildPack([
64
      {
65
        type: "ref-delta",
66
        baseOid: aOid,
67
        delta: buildAppendOnlyDelta(aPayload, bSuffix),
68
      },
69
    ]);
70
    const newerPackBytes = await buildPack([
71
      {
72
        type: "ref-delta",
73
        baseOid: bOid,
74
        delta: buildCopyPrefixDelta(bPayload, aPayload.length),
75
      },
76
    ]);
77
 
78
    const olderKey = `test/rewrite-ref-cycle-older-${Date.now()}.pack`;
79
    const middleKey = `test/rewrite-ref-cycle-middle-${Date.now()}.pack`;
80
    const newerKey = `test/rewrite-ref-cycle-newer-${Date.now()}.pack`;
81
    await env.REPO_BUCKET.put(olderKey, olderPackBytes);
82
    await env.REPO_BUCKET.put(middleKey, middlePackBytes);
83
    await env.REPO_BUCKET.put(newerKey, newerPackBytes);
84
 
85
    const olderResolve = await indexTestPack(env, olderKey, olderPackBytes.byteLength);
86
    const olderRow: PackCatalogRow = {
87
      packKey: olderKey,
88
      kind: "receive",
89
      state: "active",
90
      tier: 0,
91
      seqLo: 1,
92
      seqHi: 1,
93
      objectCount: olderResolve.objectCount,
94
      packBytes: olderPackBytes.byteLength,
95
      idxBytes: olderResolve.idxBytes,
96
      createdAt: Date.now(),
97
      supersededBy: null,
98
    };
99
    const middleResolve = await indexTestPack(env, middleKey, middlePackBytes.byteLength, [
100
      olderRow,
101
    ]);
102
    const middleRow: PackCatalogRow = {
103
      packKey: middleKey,
104
      kind: "receive",
105
      state: "active",
106
      tier: 0,
107
      seqLo: 2,
108
      seqHi: 2,
109
      objectCount: middleResolve.objectCount,
110
      packBytes: middlePackBytes.byteLength,
111
      idxBytes: middleResolve.idxBytes,
112
      createdAt: Date.now(),
113
      supersededBy: null,
114
    };
115
    const newerResolve = await indexTestPack(env, newerKey, newerPackBytes.byteLength, [
116
      middleRow,
117
      olderRow,
118
    ]);
119
 
120
    const snapshot = {
121
      packs: [
122
        { packKey: newerKey, packBytes: newerPackBytes.byteLength, idx: newerResolve.idxView },
123
        { packKey: middleKey, packBytes: middlePackBytes.byteLength, idx: middleResolve.idxView },
124
        { packKey: olderKey, packBytes: olderPackBytes.byteLength, idx: olderResolve.idxView },
125
      ],
126
    };
127
    const rewriteOptions = {
128
      limiter: { run: async <T>(_label: string, fn: () => Promise<T>) => await fn() },
129
      countSubrequest: () => {},
130
    };
131
 
132
    const selection = await buildSelection(
133
      env,
134
      snapshot,
135
      [aOid],
136
      createLogger("error", { service: "test" }),
137
      new Set(),
138
      rewriteOptions
139
    );
140
 
141
    expect(selection).toBeDefined();
142
    const table = selection!.table;
143
 
144
    let aSel = -1;
145
    let aCount = 0;
146
    let bSel = -1;
147
    let seedSel = -1;
148
    for (let sel = 0; sel < table.count; sel++) {
149
      const oid = bytesToHex(table.oidsRaw.subarray(sel * 20, sel * 20 + 20));
150
      if (oid === aOid) {
151
        aSel = sel;
152
        aCount++;
153
      }
154
      if (oid === bOid) bSel = sel;
155
      if (table.typeCodes[sel] < 6 && oid !== aOid && oid !== bOid) seedSel = sel;
156
    }
157
 
158
    expect(aCount).toBe(1);
159
    expect(aSel).toBeGreaterThanOrEqual(0);
160
    expect(bSel).toBeGreaterThanOrEqual(0);
161
    expect(seedSel).toBeGreaterThanOrEqual(0);
162
    expect(table.baseSlots[aSel]).toBe(seedSel);
163
    expect(table.baseSlots[bSel]).toBe(aSel);
164
    expect(buildOutputOrder(table, createLogger("error", { service: "test" }))).toBe(true);
165
 
166
    const stream = await rewritePack(env, snapshot, [aOid], rewriteOptions);
167
    expect(stream).toBeDefined();
168
    const rewrittenPack = await readStreamBytes(stream!);
169
 
170
    const verifyKey = `test/rewrite-ref-cycle-verify-${Date.now()}.pack`;
171
    await env.REPO_BUCKET.put(verifyKey, rewrittenPack);
172
    const verify = await indexTestPack(env, verifyKey, rewrittenPack.byteLength);
173
 
174
    const oidSet = new Set<string>();
175
    for (let i = 0; i < verify.idxView.count; i++) {
176
      const oidBytes = verify.idxView.rawNames.subarray(i * 20, (i + 1) * 20);
177
      oidSet.add(bytesToHex(oidBytes));
178
    }
179
    expect(oidSet.size).toBe(verify.idxView.count);
180
  });
181
 
182
  it("materializes a selected REF_DELTA row when a later base edge closes a cycle", async () => {
183
    const seedPayload = new TextEncoder().encode("seed\n");
184
    const bSuffix = new TextEncoder().encode("b\n");
185
    const bPayload = new Uint8Array(seedPayload.length + bSuffix.length);
186
    bPayload.set(seedPayload, 0);
187
    bPayload.set(bSuffix, seedPayload.length);
188
 
189
    const aSuffix = new TextEncoder().encode("a\n");
190
    const aPayload = new Uint8Array(bPayload.length + aSuffix.length);
191
    aPayload.set(bPayload, 0);
192
    aPayload.set(aSuffix, bPayload.length);
193
 
194
    const bOid = await computeOid("blob", bPayload);
195
    const aOid = await computeOid("blob", aPayload);
196
 
197
    const fallbackPackBytes = await buildPack([
198
      { type: "blob", payload: seedPayload },
199
      { type: "ofs-delta", baseIndex: 0, delta: buildAppendOnlyDelta(seedPayload, bSuffix) },
200
    ]);
201
    const sourceAPackBytes = await buildPack([
202
      {
203
        type: "ref-delta",
204
        baseOid: bOid,
205
        delta: buildAppendOnlyDelta(bPayload, aSuffix),
206
      },
207
    ]);
208
    const sourceBPackBytes = await buildPack([
209
      {
210
        type: "ref-delta",
211
        baseOid: aOid,
212
        delta: buildCopyPrefixDelta(aPayload, bPayload.length),
213
      },
214
    ]);
215
 
216
    const fallbackKey = `test/rewrite-latent-cycle-fallback-${Date.now()}.pack`;
217
    const sourceAKey = `test/rewrite-latent-cycle-a-${Date.now()}.pack`;
218
    const sourceBKey = `test/rewrite-latent-cycle-b-${Date.now()}.pack`;
219
    await env.REPO_BUCKET.put(fallbackKey, fallbackPackBytes);
220
    await env.REPO_BUCKET.put(sourceAKey, sourceAPackBytes);
221
    await env.REPO_BUCKET.put(sourceBKey, sourceBPackBytes);
222
 
223
    const fallbackResolve = await indexTestPack(env, fallbackKey, fallbackPackBytes.byteLength);
224
    const fallbackRow: PackCatalogRow = {
225
      packKey: fallbackKey,
226
      kind: "compact",
227
      state: "active",
228
      tier: 1,
229
      seqLo: 1,
230
      seqHi: 1,
231
      objectCount: fallbackResolve.objectCount,
232
      packBytes: fallbackPackBytes.byteLength,
233
      idxBytes: fallbackResolve.idxBytes,
234
      createdAt: Date.now(),
235
      supersededBy: null,
236
    };
237
    const sourceAResolve = await indexTestPack(env, sourceAKey, sourceAPackBytes.byteLength, [
238
      fallbackRow,
239
    ]);
240
    const sourceARow: PackCatalogRow = {
241
      packKey: sourceAKey,
242
      kind: "receive",
243
      state: "active",
244
      tier: 0,
245
      seqLo: 2,
246
      seqHi: 2,
247
      objectCount: sourceAResolve.objectCount,
248
      packBytes: sourceAPackBytes.byteLength,
249
      idxBytes: sourceAResolve.idxBytes,
250
      createdAt: Date.now(),
251
      supersededBy: null,
252
    };
253
    const sourceBResolve = await indexTestPack(env, sourceBKey, sourceBPackBytes.byteLength, [
254
      sourceARow,
255
      fallbackRow,
256
    ]);
257
 
258
    const snapshot = {
259
      packs: [
260
        {
261
          packKey: sourceAKey,
262
          packBytes: sourceAPackBytes.byteLength,
263
          idx: sourceAResolve.idxView,
264
        },
265
        {
266
          packKey: sourceBKey,
267
          packBytes: sourceBPackBytes.byteLength,
268
          idx: sourceBResolve.idxView,
269
        },
270
        {
271
          packKey: fallbackKey,
272
          packBytes: fallbackPackBytes.byteLength,
273
          idx: fallbackResolve.idxView,
274
        },
275
      ],
276
    };
277
    const rewriteOptions = {
278
      limiter: { run: async <T>(_label: string, fn: () => Promise<T>) => await fn() },
279
      countSubrequest: () => {},
280
    };
281
 
282
    const selection = await buildSelection(
283
      env,
284
      snapshot,
285
      [aOid, bOid],
286
      createLogger("error", { service: "test" }),
287
      new Set(),
288
      rewriteOptions
289
    );
290
 
291
    expect(selection).toBeDefined();
292
    const table = selection!.table;
293
 
294
    let syntheticCount = 0;
295
    for (let sel = 0; sel < table.count; sel++) {
296
      if (table.syntheticPayloads[sel]) syntheticCount++;
297
    }
298
    expect(syntheticCount).toBe(1);
299
    expect(buildOutputOrder(table, createLogger("error", { service: "test" }))).toBe(true);
300
 
301
    const stream = await rewritePack(env, snapshot, [aOid, bOid], rewriteOptions);
302
    expect(stream).toBeDefined();
303
    const rewrittenPack = await readStreamBytes(stream!);
304
 
305
    const verifyKey = `test/rewrite-latent-cycle-verify-${Date.now()}.pack`;
306
    await env.REPO_BUCKET.put(verifyKey, rewrittenPack);
307
    const verify = await indexTestPack(env, verifyKey, rewrittenPack.byteLength);
308
 
309
    const oidSet = new Set<string>();
310
    for (let i = 0; i < verify.idxView.count; i++) {
311
      const oidBytes = verify.idxView.rawNames.subarray(i * 20, (i + 1) * 20);
312
      oidSet.add(bytesToHex(oidBytes));
313
    }
314
    expect(oidSet.has(aOid)).toBe(true);
315
    expect(oidSet.has(bOid)).toBe(true);
316
    expect(oidSet.size).toBe(verify.idxView.count);
317
  });
318
 
319
  it("does not create an artificial cycle when an older OFS base has a newer duplicate OID", async () => {
320
    const basePayload = new TextEncoder().encode("shared\n");
321
    const suffix = new TextEncoder().encode("extra\n");
322
    const expandedPayload = new Uint8Array(basePayload.length + suffix.length);
323
    expandedPayload.set(basePayload, 0);
324
    expandedPayload.set(suffix, basePayload.length);
325
 
326
    const expandedOid = await computeOid("blob", expandedPayload);
327
    const baseOid = await computeOid("blob", basePayload);
328
 
329
    const olderPackBytes = await buildPack([
330
      { type: "blob", payload: basePayload },
331
      { type: "ofs-delta", baseIndex: 0, delta: buildAppendOnlyDelta(basePayload, suffix) },
332
    ]);
333
    const newerPackBytes = await buildPack([
334
      {
335
        type: "ref-delta",
336
        baseOid: expandedOid,
337
        delta: buildCopyPrefixDelta(expandedPayload, basePayload.length),
338
      },
339
    ]);
340
 
341
    const olderKey = `test/rewrite-cycle-older-${Date.now()}.pack`;
342
    const newerKey = `test/rewrite-cycle-newer-${Date.now()}.pack`;
343
    await env.REPO_BUCKET.put(olderKey, olderPackBytes);
344
    await env.REPO_BUCKET.put(newerKey, newerPackBytes);
345
 
346
    const olderResolve = await indexTestPack(env, olderKey, olderPackBytes.byteLength);
347
    const olderRow: PackCatalogRow = {
348
      packKey: olderKey,
349
      kind: "receive",
350
      state: "active",
351
      tier: 0,
352
      seqLo: 1,
353
      seqHi: 1,
354
      objectCount: olderResolve.objectCount,
355
      packBytes: olderPackBytes.byteLength,
356
      idxBytes: olderResolve.idxBytes,
357
      createdAt: Date.now(),
358
      supersededBy: null,
359
    };
360
    const newerResolve = await indexTestPack(env, newerKey, newerPackBytes.byteLength, [olderRow]);
361
 
362
    const selection = await buildSelection(
363
      env,
364
      {
365
        packs: [
366
          { packKey: newerKey, packBytes: newerPackBytes.byteLength, idx: newerResolve.idxView },
367
          { packKey: olderKey, packBytes: olderPackBytes.byteLength, idx: olderResolve.idxView },
368
        ],
369
      },
370
      [expandedOid, baseOid],
371
      createLogger("error", { service: "test" }),
372
      new Set(),
373
      {
374
        limiter: { run: async (_label, fn) => await fn() },
375
        countSubrequest: () => {},
376
      }
377
    );
378
 
379
    expect(selection).toBeDefined();
380
    const table = selection!.table;
381
    expect(Array.from(table.baseSlots.subarray(0, table.count))).toEqual([1, -1]);
382
    expect(buildOutputOrder(table, createLogger("error", { service: "test" }))).toBe(true);
383
  });
384
 
385
  it("redirects duplicate full-object bases to the existing OID owner", async () => {
386
    const basePayload = new TextEncoder().encode("shared base\n");
387
    const suffix = new TextEncoder().encode("child\n");
388
    const childPayload = new Uint8Array(basePayload.length + suffix.length);
389
    childPayload.set(basePayload, 0);
390
    childPayload.set(suffix, basePayload.length);
391
 
392
    const baseOid = await computeOid("blob", basePayload);
393
    const childOid = await computeOid("blob", childPayload);
394
 
395
    const olderPackBytes = await buildPack([{ type: "blob", payload: basePayload }]);
396
    const newerPackBytes = await buildPack([
397
      { type: "blob", payload: basePayload },
398
      { type: "ofs-delta", baseIndex: 0, delta: buildAppendOnlyDelta(basePayload, suffix) },
399
    ]);
400
 
401
    const olderKey = `test/rewrite-dup-full-older-${Date.now()}.pack`;
402
    const newerKey = `test/rewrite-dup-full-newer-${Date.now()}.pack`;
403
    await env.REPO_BUCKET.put(olderKey, olderPackBytes);
404
    await env.REPO_BUCKET.put(newerKey, newerPackBytes);
405
 
406
    const olderResolve = await indexTestPack(env, olderKey, olderPackBytes.byteLength);
407
    const newerResolve = await indexTestPack(env, newerKey, newerPackBytes.byteLength);
408
 
409
    const selection = await buildSelection(
410
      env,
411
      {
412
        packs: [
413
          { packKey: olderKey, packBytes: olderPackBytes.byteLength, idx: olderResolve.idxView },
414
          { packKey: newerKey, packBytes: newerPackBytes.byteLength, idx: newerResolve.idxView },
415
        ],
416
      },
417
      [baseOid, childOid],
418
      createLogger("error", { service: "test" }),
419
      new Set(),
420
      {
421
        limiter: { run: async (_label, fn) => await fn() },
422
        countSubrequest: () => {},
423
      }
424
    );
425
 
426
    expect(selection).toBeDefined();
427
    const table = selection!.table;
428
    expect(table.count).toBe(2);
429
    expect(Array.from(table.baseSlots.subarray(0, table.count))).toEqual([-1, 0]);
430
    expect(buildOutputOrder(table, createLogger("error", { service: "test" }))).toBe(true);
431
  });
432
 
433
  it("keeps an OFS base row live when a newer duplicate delta already owns the OID", async () => {
434
    const seedPayload = new TextEncoder().encode("seed\n");
435
    const xSuffix = new TextEncoder().encode("x\n");
436
    const xPayload = new Uint8Array(seedPayload.length + xSuffix.length);
437
    xPayload.set(seedPayload, 0);
438
    xPayload.set(xSuffix, seedPayload.length);
439
 
440
    const ySuffix = new TextEncoder().encode("y\n");
441
    const yPayload = new Uint8Array(xPayload.length + ySuffix.length);
442
    yPayload.set(xPayload, 0);
443
    yPayload.set(ySuffix, xPayload.length);
444
 
445
    const seedOid = await computeOid("blob", seedPayload);
446
    const xOid = await computeOid("blob", xPayload);
447
    const yOid = await computeOid("blob", yPayload);
448
 
449
    const olderPackBytes = await buildPack([
450
      { type: "blob", payload: seedPayload },
451
      { type: "ofs-delta", baseIndex: 0, delta: buildAppendOnlyDelta(seedPayload, xSuffix) },
452
      { type: "ofs-delta", baseIndex: 1, delta: buildAppendOnlyDelta(xPayload, ySuffix) },
453
    ]);
454
    const newerPackBytes = await buildPack([
455
      {
456
        type: "ref-delta",
457
        baseOid: yOid,
458
        delta: buildCopyPrefixDelta(yPayload, xPayload.length),
459
      },
460
    ]);
461
 
462
    const olderKey = `test/rewrite-ofs-base-owner-older-${Date.now()}.pack`;
463
    const newerKey = `test/rewrite-ofs-base-owner-newer-${Date.now()}.pack`;
464
    await env.REPO_BUCKET.put(olderKey, olderPackBytes);
465
    await env.REPO_BUCKET.put(newerKey, newerPackBytes);
466
 
467
    const olderResolve = await indexTestPack(env, olderKey, olderPackBytes.byteLength);
468
    const olderRow: PackCatalogRow = {
469
      packKey: olderKey,
470
      kind: "receive",
471
      state: "active",
472
      tier: 0,
473
      seqLo: 1,
474
      seqHi: 1,
475
      objectCount: olderResolve.objectCount,
476
      packBytes: olderPackBytes.byteLength,
477
      idxBytes: olderResolve.idxBytes,
478
      createdAt: Date.now(),
479
      supersededBy: null,
480
    };
481
    const newerResolve = await indexTestPack(env, newerKey, newerPackBytes.byteLength, [olderRow]);
482
 
483
    const selection = await buildSelection(
484
      env,
485
      {
486
        packs: [
487
          { packKey: newerKey, packBytes: newerPackBytes.byteLength, idx: newerResolve.idxView },
488
          { packKey: olderKey, packBytes: olderPackBytes.byteLength, idx: olderResolve.idxView },
489
        ],
490
      },
491
      [xOid, yOid],
492
      createLogger("error", { service: "test" }),
493
      new Set(),
494
      {
495
        limiter: { run: async (_label, fn) => await fn() },
496
        countSubrequest: () => {},
497
      }
498
    );
499
 
500
    expect(selection).toBeDefined();
501
    const table = selection!.table;
502
 
503
    let olderXSel = -1;
504
    let olderYSel = -1;
505
    let olderSeedSel = -1;
506
    for (let sel = 0; sel < table.count; sel++) {
507
      const oid = bytesToHex(table.oidsRaw.subarray(sel * 20, sel * 20 + 20));
508
      if (table.packSlots[sel] === 1 && oid === xOid) olderXSel = sel;
509
      if (table.packSlots[sel] === 1 && oid === seedOid) olderSeedSel = sel;
510
      if (oid === yOid) olderYSel = sel;
511
    }
512
 
513
    // The older OFS chain must keep its exact base row so pack-local topology
514
    // stays acyclic even when a newer duplicate delta advertises the same OID.
515
    expect(olderSeedSel).toBeGreaterThanOrEqual(0);
516
    expect(olderXSel).toBeGreaterThanOrEqual(0);
517
    expect(olderYSel).toBeGreaterThanOrEqual(0);
518
    expect(table.baseSlots[olderXSel]).toBe(olderSeedSel);
519
    expect(table.baseSlots[olderYSel]).toBe(olderXSel);
520
    expect(buildOutputOrder(table, createLogger("error", { service: "test" }))).toBe(true);
521
  });
522
 
523
  it("collapses pinned duplicate rows back into one live owner slot", async () => {
524
    const basePayload = new TextEncoder().encode("shared base\n");
525
    const childSuffix = new TextEncoder().encode("child\n");
526
    const childPayload = new Uint8Array(basePayload.length + childSuffix.length);
527
    childPayload.set(basePayload, 0);
528
    childPayload.set(childSuffix, basePayload.length);
529
 
530
    const baseOid = await computeOid("blob", basePayload);
531
    const childOid = await computeOid("blob", childPayload);
532
 
533
    const newerPackBytes = await buildPack([{ type: "blob", payload: basePayload }]);
534
    const olderPackBytes = await buildPack([
535
      {
536
        type: "ref-delta",
537
        baseOid,
538
        delta: buildCopyPrefixDelta(basePayload, basePayload.length),
539
      },
540
      { type: "ofs-delta", baseIndex: 0, delta: buildAppendOnlyDelta(basePayload, childSuffix) },
541
    ]);
542
 
543
    const newerKey = `test/rewrite-pinned-self-cycle-newer-${Date.now()}.pack`;
544
    const olderKey = `test/rewrite-pinned-self-cycle-older-${Date.now()}.pack`;
545
    await env.REPO_BUCKET.put(newerKey, newerPackBytes);
546
    await env.REPO_BUCKET.put(olderKey, olderPackBytes);
547
 
548
    const newerResolve = await indexTestPack(env, newerKey, newerPackBytes.byteLength);
549
    const newerRow: PackCatalogRow = {
550
      packKey: newerKey,
551
      kind: "receive",
552
      state: "active",
553
      tier: 0,
554
      seqLo: 2,
555
      seqHi: 2,
556
      objectCount: newerResolve.objectCount,
557
      packBytes: newerPackBytes.byteLength,
558
      idxBytes: newerResolve.idxBytes,
559
      createdAt: Date.now(),
560
      supersededBy: null,
561
    };
562
    const olderResolve = await indexTestPack(env, olderKey, olderPackBytes.byteLength, [newerRow]);
563
 
564
    const selection = await buildSelection(
565
      env,
566
      {
567
        packs: [
568
          { packKey: newerKey, packBytes: newerPackBytes.byteLength, idx: newerResolve.idxView },
569
          { packKey: olderKey, packBytes: olderPackBytes.byteLength, idx: olderResolve.idxView },
570
        ],
571
      },
572
      [baseOid, childOid],
573
      createLogger("error", { service: "test" }),
574
      new Set(),
575
      {
576
        limiter: { run: async (_label, fn) => await fn() },
577
        countSubrequest: () => {},
578
      }
579
    );
580
 
581
    expect(selection).toBeDefined();
582
    const table = selection!.table;
583
 
584
    let baseSel = -1;
585
    let baseCount = 0;
586
    let childSel = -1;
587
    for (let sel = 0; sel < table.count; sel++) {
588
      const oid = bytesToHex(table.oidsRaw.subarray(sel * 20, sel * 20 + 20));
589
      if (oid === baseOid) {
590
        baseSel = sel;
591
        baseCount++;
592
      }
593
      if (oid === childOid) childSel = sel;
594
    }
595
 
596
    // The planner now rewrites the live owner slot to the safe full-object
597
    // encoding instead of keeping both same-OID rows alive in the output pack.
598
    expect(baseSel).toBeGreaterThanOrEqual(0);
599
    expect(baseCount).toBe(1);
600
    expect(childSel).toBeGreaterThanOrEqual(0);
601
    expect(table.baseSlots[baseSel]).toBe(-1);
602
    expect(table.baseSlots[childSel]).toBe(baseSel);
603
    expect(buildOutputOrder(table, createLogger("error", { service: "test" }))).toBe(true);
604
  });
605
 
606
  it("repairs redirected duplicate delta bases before collapsing them away", async () => {
607
    const seedPayload = new TextEncoder().encode("seed\n");
608
    const xSuffix = new TextEncoder().encode("x\n");
609
    const xPayload = new Uint8Array(seedPayload.length + xSuffix.length);
610
    xPayload.set(seedPayload, 0);
611
    xPayload.set(xSuffix, seedPayload.length);
612
 
613
    const childSuffix = new TextEncoder().encode("child\n");
614
    const childPayload = new Uint8Array(xPayload.length + childSuffix.length);
615
    childPayload.set(xPayload, 0);
616
    childPayload.set(childSuffix, xPayload.length);
617
 
618
    const xOid = await computeOid("blob", xPayload);
619
    const childOid = await computeOid("blob", childPayload);
620
 
621
    // Layout:
622
    //   0: full seed
623
    //   1: OFS delta seed -> x
624
    //   2: OFS identity delta x -> x   (selected owner for x)
625
    //   3: OFS identity delta x -> x   (redirected duplicate for x)
626
    //   4: OFS delta x -> child        (depends on the selected owner)
627
    //
628
    // The selected x row depends on the duplicate x row, so dead-slot pruning
629
    // must keep that duplicate live to avoid folding the owner back onto
630
    // itself. Before the fix, row 3 survived compaction with `baseSlots = -1`
631
    // because redirected rows returned before resolving their own base edge.
632
    const packBytes = await buildPack([
633
      { type: "blob", payload: seedPayload },
634
      { type: "ofs-delta", baseIndex: 0, delta: buildAppendOnlyDelta(seedPayload, xSuffix) },
635
      { type: "ofs-delta", baseIndex: 1, delta: buildCopyPrefixDelta(xPayload, xPayload.length) },
636
      { type: "ofs-delta", baseIndex: 2, delta: buildCopyPrefixDelta(xPayload, xPayload.length) },
637
      { type: "ofs-delta", baseIndex: 2, delta: buildAppendOnlyDelta(xPayload, childSuffix) },
638
    ]);
639
 
640
    const packKey = `test/rewrite-retained-redirect-${Date.now()}.pack`;
641
    await env.REPO_BUCKET.put(packKey, packBytes);
642
    const resolve = await indexTestPack(env, packKey, packBytes.byteLength);
643
 
644
    const selection = await buildSelection(
645
      env,
646
      {
647
        packs: [{ packKey, packBytes: packBytes.byteLength, idx: resolve.idxView }],
648
      },
649
      [xOid, childOid],
650
      createLogger("error", { service: "test" }),
651
      new Set(),
652
      {
653
        limiter: { run: async (_label, fn) => await fn() },
654
        countSubrequest: () => {},
655
      }
656
    );
657
 
658
    expect(selection).toBeDefined();
659
    const table = selection!.table;
660
 
661
    let xSel = -1;
662
    let xCount = 0;
663
    let childSel = -1;
664
    for (let sel = 0; sel < table.count; sel++) {
665
      const oid = bytesToHex(table.oidsRaw.subarray(sel * 20, sel * 20 + 20));
666
      if (oid === xOid) {
667
        xSel = sel;
668
        xCount++;
669
      }
670
      if (oid === childOid) childSel = sel;
671
    }
672
 
673
    const selectedOwnerSel = childSel >= 0 ? table.baseSlots[childSel] : -1;
674
    const rootBaseSel = selectedOwnerSel >= 0 ? table.baseSlots[selectedOwnerSel] : -1;
675
 
676
    // The retained duplicate still needs its base chain repaired first, but
677
    // the final selection should collapse back to one live x row.
678
    expect(xCount).toBe(1);
679
    expect(xSel).toBeGreaterThanOrEqual(0);
680
    expect(childSel).toBeGreaterThanOrEqual(0);
681
    expect(selectedOwnerSel).toBe(xSel);
682
    expect(table.baseSlots[childSel]).toBe(xSel);
683
    expect(rootBaseSel).toBeGreaterThanOrEqual(0);
684
    expect(table.baseSlots[xSel]).toBe(rootBaseSel);
685
    expect(table.baseSlots[rootBaseSel]).toBe(-1);
686
    expect(table.typeCodes[rootBaseSel]).toBeLessThan(6);
687
    expect(buildOutputOrder(table, createLogger("error", { service: "test" }))).toBe(true);
688
  });
689
 
690
  it("collapses retained redirected ref-delta rows into the owner slot", async () => {
691
    const seedPayload = new TextEncoder().encode("seed\n");
692
    const xSuffix = new TextEncoder().encode("x\n");
693
    const xPayload = new Uint8Array(seedPayload.length + xSuffix.length);
694
    xPayload.set(seedPayload, 0);
695
    xPayload.set(xSuffix, seedPayload.length);
696
 
697
    const childSuffix = new TextEncoder().encode("child\n");
698
    const childPayload = new Uint8Array(xPayload.length + childSuffix.length);
699
    childPayload.set(xPayload, 0);
700
    childPayload.set(childSuffix, xPayload.length);
701
 
702
    const seedOid = await computeOid("blob", seedPayload);
703
    const childOid = await computeOid("blob", childPayload);
704
 
705
    // Layout:
706
    //   0: full seed
707
    //   1: REF delta seed -> x         (redirected duplicate for x)
708
    //   2: OFS identity delta x -> x   (selected owner for x)
709
    //   3: OFS delta x -> child        (depends on the selected owner)
710
    //
711
    // Row 1 is a retained redirected REF_DELTA. Before the retained-redirect
712
    // repair pass, this row stayed live with `baseSlots = -1`.
713
    const packBytes = await buildPack([
714
      { type: "blob", payload: seedPayload },
715
      {
716
        type: "ref-delta",
717
        baseOid: seedOid,
718
        delta: buildAppendOnlyDelta(seedPayload, xSuffix),
719
      },
720
      { type: "ofs-delta", baseIndex: 1, delta: buildCopyPrefixDelta(xPayload, xPayload.length) },
721
      { type: "ofs-delta", baseIndex: 2, delta: buildAppendOnlyDelta(xPayload, childSuffix) },
722
    ]);
723
 
724
    const packKey = `test/rewrite-retained-ref-delta-${Date.now()}.pack`;
725
    await env.REPO_BUCKET.put(packKey, packBytes);
726
    const resolve = await indexTestPack(env, packKey, packBytes.byteLength);
727
 
728
    const selection = await buildSelection(
729
      env,
730
      {
731
        packs: [{ packKey, packBytes: packBytes.byteLength, idx: resolve.idxView }],
732
      },
733
      [childOid],
734
      createLogger("error", { service: "test" }),
735
      new Set(),
736
      {
737
        limiter: { run: async (_label, fn) => await fn() },
738
        countSubrequest: () => {},
739
      }
740
    );
741
 
742
    expect(selection).toBeDefined();
743
    const table = selection!.table;
744
 
745
    let childSel = -1;
746
    for (let sel = 0; sel < table.count; sel++) {
747
      const oid = bytesToHex(table.oidsRaw.subarray(sel * 20, sel * 20 + 20));
748
      if (oid === childOid) childSel = sel;
749
    }
750
 
751
    const selectedOwnerSel = childSel >= 0 ? table.baseSlots[childSel] : -1;
752
    const rootBaseSel = selectedOwnerSel >= 0 ? table.baseSlots[selectedOwnerSel] : -1;
753
 
754
    expect(selectedOwnerSel).toBeGreaterThanOrEqual(0);
755
    expect(childSel).toBeGreaterThanOrEqual(0);
756
    expect(table.typeCodes[selectedOwnerSel]).toBe(7);
757
    expect(table.baseSlots[childSel]).toBe(selectedOwnerSel);
758
    expect(rootBaseSel).toBeGreaterThanOrEqual(0);
759
    expect(table.baseSlots[selectedOwnerSel]).toBe(rootBaseSel);
760
    expect(table.baseSlots[rootBaseSel]).toBe(-1);
761
    expect(table.typeCodes[rootBaseSel]).toBeLessThan(6);
762
    expect(buildOutputOrder(table, createLogger("error", { service: "test" }))).toBe(true);
763
  });
764
 
765
  it("collapses multi-hop retained redirect chains back into one live owner row", async () => {
766
    const seedPayload = new TextEncoder().encode("seed\n");
767
    const xSuffix = new TextEncoder().encode("x\n");
768
    const xPayload = new Uint8Array(seedPayload.length + xSuffix.length);
769
    xPayload.set(seedPayload, 0);
770
    xPayload.set(xSuffix, seedPayload.length);
771
 
772
    const childSuffix = new TextEncoder().encode("child\n");
773
    const childPayload = new Uint8Array(xPayload.length + childSuffix.length);
774
    childPayload.set(xPayload, 0);
775
    childPayload.set(childSuffix, xPayload.length);
776
 
777
    const seedOid = await computeOid("blob", seedPayload);
778
    const childOid = await computeOid("blob", childPayload);
779
 
780
    // Layout:
781
    //   0: full seed
782
    //   1: REF delta seed -> x         (retained redirect discovered on pass 2)
783
    //   2: OFS identity delta x -> x   (retained redirect discovered on pass 1)
784
    //   3: OFS identity delta x -> x   (selected owner for x)
785
    //   4: OFS delta x -> child        (depends on the selected owner)
786
    //
787
    // The owner row depends on row 2, and row 2 depends on row 1. This forces
788
    // the retained-redirect repair logic to run more than once.
789
    const packBytes = await buildPack([
790
      { type: "blob", payload: seedPayload },
791
      {
792
        type: "ref-delta",
793
        baseOid: seedOid,
794
        delta: buildAppendOnlyDelta(seedPayload, xSuffix),
795
      },
796
      { type: "ofs-delta", baseIndex: 1, delta: buildCopyPrefixDelta(xPayload, xPayload.length) },
797
      { type: "ofs-delta", baseIndex: 2, delta: buildCopyPrefixDelta(xPayload, xPayload.length) },
798
      { type: "ofs-delta", baseIndex: 3, delta: buildAppendOnlyDelta(xPayload, childSuffix) },
799
    ]);
800
 
801
    const packKey = `test/rewrite-retained-ref-chain-${Date.now()}.pack`;
802
    await env.REPO_BUCKET.put(packKey, packBytes);
803
    const resolve = await indexTestPack(env, packKey, packBytes.byteLength);
804
 
805
    const selection = await buildSelection(
806
      env,
807
      {
808
        packs: [{ packKey, packBytes: packBytes.byteLength, idx: resolve.idxView }],
809
      },
810
      [childOid],
811
      createLogger("error", { service: "test" }),
812
      new Set(),
813
      {
814
        limiter: { run: async (_label, fn) => await fn() },
815
        countSubrequest: () => {},
816
      }
817
    );
818
 
819
    expect(selection).toBeDefined();
820
    const table = selection!.table;
821
 
822
    let childSel = -1;
823
    for (let sel = 0; sel < table.count; sel++) {
824
      const oid = bytesToHex(table.oidsRaw.subarray(sel * 20, sel * 20 + 20));
825
      if (oid === childOid) childSel = sel;
826
    }
827
 
828
    const selectedOwnerSel = childSel >= 0 ? table.baseSlots[childSel] : -1;
829
    const rootBaseSel = selectedOwnerSel >= 0 ? table.baseSlots[selectedOwnerSel] : -1;
830
 
831
    expect(selectedOwnerSel).toBeGreaterThanOrEqual(0);
832
    expect(rootBaseSel).toBeGreaterThanOrEqual(0);
833
    expect(table.typeCodes[selectedOwnerSel]).toBe(7);
834
    expect(table.baseSlots[childSel]).toBe(selectedOwnerSel);
835
    expect(table.baseSlots[selectedOwnerSel]).toBe(rootBaseSel);
836
    expect(table.baseSlots[rootBaseSel]).toBe(-1);
837
    expect(table.typeCodes[rootBaseSel]).toBeLessThan(6);
838
    expect(buildOutputOrder(table, createLogger("error", { service: "test" }))).toBe(true);
839
  });
840
 
841
  it("streams an indexable pack for a retained redirected ref-delta shape", async () => {
842
    const seedPayload = new TextEncoder().encode("seed\n");
843
    const xSuffix = new TextEncoder().encode("x\n");
844
    const xPayload = new Uint8Array(seedPayload.length + xSuffix.length);
845
    xPayload.set(seedPayload, 0);
846
    xPayload.set(xSuffix, seedPayload.length);
847
 
848
    const childSuffix = new TextEncoder().encode("child\n");
849
    const childPayload = new Uint8Array(xPayload.length + childSuffix.length);
850
    childPayload.set(xPayload, 0);
851
    childPayload.set(childSuffix, xPayload.length);
852
 
853
    const seedOid = await computeOid("blob", seedPayload);
854
    const childOid = await computeOid("blob", childPayload);
855
 
856
    const packBytes = await buildPack([
857
      { type: "blob", payload: seedPayload },
858
      {
859
        type: "ref-delta",
860
        baseOid: seedOid,
861
        delta: buildAppendOnlyDelta(seedPayload, xSuffix),
862
      },
863
      { type: "ofs-delta", baseIndex: 1, delta: buildCopyPrefixDelta(xPayload, xPayload.length) },
864
      { type: "ofs-delta", baseIndex: 2, delta: buildAppendOnlyDelta(xPayload, childSuffix) },
865
    ]);
866
 
867
    const packKey = `test/rewrite-retained-ref-stream-${Date.now()}.pack`;
868
    await env.REPO_BUCKET.put(packKey, packBytes);
869
    const resolve = await indexTestPack(env, packKey, packBytes.byteLength);
870
 
871
    const stream = await rewritePack(
872
      env,
873
      {
874
        packs: [{ packKey, packBytes: packBytes.byteLength, idx: resolve.idxView }],
875
      },
876
      [childOid],
877
      {
878
        limiter: { run: async (_label, fn) => await fn() },
879
        countSubrequest: () => {},
880
      }
881
    );
882
 
883
    expect(stream).toBeDefined();
884
    const rewrittenPack = await readStreamBytes(stream!);
885
    expect(new TextDecoder().decode(rewrittenPack.subarray(0, 4))).toBe("PACK");
886
 
887
    const verifyKey = `test/rewrite-retained-ref-stream-verify-${Date.now()}.pack`;
888
    await env.REPO_BUCKET.put(verifyKey, rewrittenPack);
889
    const verify = await indexTestPack(env, verifyKey, rewrittenPack.byteLength);
890
    expect(verify.idxView.count).toBe(3);
891
 
892
    const oidSet = new Set<string>();
893
    for (let i = 0; i < verify.idxView.count; i++) {
894
      const oidBytes = verify.idxView.rawNames.subarray(i * 20, (i + 1) * 20);
895
      oidSet.add(bytesToHex(oidBytes));
896
    }
897
    expect(oidSet.size).toBe(verify.idxView.count);
898
  });
899
});