1/**
2 * The partial-pack scanner (src/Git/Protocol/PartialScan.ts): the hashing
3 * Worker's unit of work. Entries are settled inside a buffer that starts
4 * at an entry boundary; the tail is carried; deltas whose base lies in an
5 * earlier buffer are reported unresolved.
6 */
7import {
8 hashObject,
9 encodeTypeSize,
10 makeSha1,
11 type Oid,
12} from "@/Git/Protocol/ObjectCodec.ts";
13import {
14 findBoundary,
15 hashBounds,
16 scanBounds,
17 scanPart,
18} from "@/Git/Protocol/PartialScan.ts";
19import { packHeader } from "@/Git/Protocol/PackWriter.ts";
20import * as Zlib from "@/Git/Protocol/Zlib.ts";
21import * as BunServices from "@effect/platform-bun/BunServices";
22import { describe, expect, test } from "alchemy-test";
23import * as Effect from "effect/Effect";
24import * as FileSystem from "effect/FileSystem";
25import * as Path from "effect/Path";
26import { concat } from "./harness/pack.ts";
27
28const buildPack = (n: number) =>
29 Effect.gen(function* () {
30 const pieces: Array<Uint8Array> = [packHeader(n)];
31 const oids: Array<Oid> = [];
32 for (let i = 0; i < n; i++) {
33 const size = 100 + ((i * 977) % 4900);
34 const content = new Uint8Array(size);
35 crypto.getRandomValues(content);
36 content[0] = i & 0xff;
37 oids.push(yield* hashObject(3, content));
38 pieces.push(encodeTypeSize(3, size), yield* Zlib.deflate(content));
39 }
40 const body = concat(pieces);
41 const sha = makeSha1();
42 sha.update(body);
43 return { pack: concat([body, sha.digest()]), oids, count: n };
44 });
45
46/** Drives the scanner the way the pipeline does: parts + carry. */
47const scanInParts = (
48 pack: Uint8Array,
49 count: number,
50 partSizes: (i: number) => number,
51) =>
52 Effect.gen(function* () {
53 // Parts run to the END of the pack (trailer included) so the last entry
54 // is followed by bytes, per the scanner's contract.
55 const end = pack.length;
56 let consumedTo = 12; // after the pack header
57 let remaining = count;
58 let cursor = 12;
59 const all: Array<Oid> = [];
60 const unresolved: Array<{ offset: number }> = [];
61 let i = 0;
62 let carry: Uint8Array = new Uint8Array(0);
63 while (cursor < end) {
64 const n = Math.min(partSizes(i++), end - cursor);
65 const payload = concat([carry, pack.subarray(cursor, cursor + n)]);
66 const base = consumedTo;
67 const result = yield* scanPart(payload, {
68 base,
69 remaining,
70 maxObjectSize: 64 << 20,
71 });
72 for (const e of result.entries) all.push(e.oid);
73 for (const u of result.unresolved) unresolved.push(u);
74 remaining -= result.count;
75 cursor += n;
76 carry = payload.subarray(result.consumedTo - base);
77 consumedTo = result.consumedTo;
78 }
79 expect(remaining).toBe(0);
80 expect(carry.length).toBe(20); // exactly the trailer is left over
81 return { all, unresolved };
82 });
83
84describe("scanPart", { tags: ["unit", "local"] }, () => {
85 test("a pack split at arbitrary points, with carry, yields every entry exactly once", async () => {
86 await Effect.runPromise(
87 Effect.gen(function* () {
88 const { pack, oids, count } = yield* buildPack(400);
89 for (const sizes of [
90 () => 1000,
91 (i: number) => 100 + ((i * 7919) % 5000),
92 () => 1 << 20,
93 ]) {
94 const { all, unresolved } = yield* scanInParts(pack, count, sizes);
95 expect(all.length).toBe(count);
96 expect(new Set(all)).toEqual(new Set(oids));
97 expect(unresolved).toEqual([]);
98 }
99 }),
100 );
101 });
102
103 test("the ofs-delta fixture: whole-buffer scan resolves every delta; small parts report cross-part bases unresolved", async () => {
104 await Effect.runPromise(
105 Effect.gen(function* () {
106 const fs = yield* FileSystem.FileSystem;
107 const path = yield* Path.Path;
108 const dir = path.join(import.meta.dirname, "fixtures", "packs");
109 const pack = yield* fs.readFile(path.join(dir, "ofs-delta.pack"));
110 const manifest = JSON.parse(
111 yield* fs.readFileString(path.join(dir, "manifest.json")),
112 ) as {
113 packs: Record<string, { oids: ReadonlyArray<string> }>;
114 };
115 const expected = new Set(manifest.packs["ofs-delta"]!.oids);
116 const count = new DataView(pack.buffer, pack.byteOffset).getUint32(8);
117 const whole = yield* scanPart(pack.subarray(12), {
118 base: 12,
119 remaining: count,
120 maxObjectSize: 64 << 20,
121 });
122 expect(whole.unresolved).toEqual([]);
123 expect(whole.count).toBe(count);
124 expect(new Set(whole.entries.map((e) => e.oid))).toEqual(expected);
125 expect(whole.entries.some((e) => e.zdata !== undefined)).toBe(true); // delta-resolved ones carry fresh zdata
126 // Tiny parts: bases fall into earlier buffers.
127 const { all, unresolved } = yield* scanInParts(pack, count, () => 64);
128 expect(unresolved.length).toBeGreaterThan(0);
129 expect(all.length + unresolved.length).toBe(count);
130 for (const oid of all) expect(expected.has(oid)).toBe(true);
131 }).pipe(Effect.provide(BunServices.layer)),
132 );
133 });
134});
135
136describe(
137 "an entry ending exactly at the buffer edge is not consumed",
138 { tags: ["unit", "local"] },
139 () => {
140 test("the scanner carries it until bytes follow", async () => {
141 await Effect.runPromise(
142 Effect.gen(function* () {
143 const { pack, count } = yield* buildPack(3);
144 const first = yield* scanPart(pack.subarray(12), {
145 base: 12,
146 remaining: count,
147 maxObjectSize: 1 << 20,
148 });
149 expect(first.count).toBe(3);
150 const cut = first.entries[1]!.dataOffset + first.entries[1]!.span;
151 const partial = yield* scanPart(pack.subarray(12, cut), {
152 base: 12,
153 remaining: count,
154 maxObjectSize: 1 << 20,
155 });
156 expect(partial.count).toBe(1);
157 expect(partial.consumedTo).toBeLessThan(cut);
158 expect(partial.consumedTo).toBe(
159 first.entries[0]!.dataOffset + first.entries[0]!.span,
160 );
161 }),
162 );
163 });
164 },
165);
166
167describe(
168 "scanBounds + hashBounds (DESIGN §22.8)",
169 { tags: ["unit", "local"] },
170 () => {
171 test("boundary scan then known-span hashing equals the single-pass scan on a synthetic pack", async () => {
172 await Effect.runPromise(
173 Effect.gen(function* () {
174 const { pack, oids, count } = yield* buildPack(300);
175 const buf = pack.subarray(12);
176 const bounds = yield* scanBounds(buf, {
177 base: 12,
178 remaining: count,
179 maxObjectSize: 64 << 20,
180 });
181 expect(bounds.entries.length).toBe(count);
182 expect(bounds.consumedTo).toBe(pack.length - 20);
183 const hashed = yield* hashBounds(buf, bounds.entries, {
184 base: 12,
185 maxObjectSize: 64 << 20,
186 });
187 expect(hashed.entries.map((e) => e.oid)).toEqual(oids);
188 expect(hashed.unresolved).toEqual([]);
189 const single = yield* scanPart(buf, {
190 base: 12,
191 remaining: count,
192 maxObjectSize: 64 << 20,
193 });
194 expect(
195 hashed.entries.map((e) => [e.oid, e.offset, e.dataOffset, e.span]),
196 ).toEqual(
197 single.entries.map((e) => [e.oid, e.offset, e.dataOffset, e.span]),
198 );
199 }),
200 );
201 });
202
203 test("the ofs-delta fixture: bounds carry base offsets; hashing resolves every in-buffer delta", async () => {
204 await Effect.runPromise(
205 Effect.gen(function* () {
206 const fs = yield* FileSystem.FileSystem;
207 const path = yield* Path.Path;
208 const dir = path.join(import.meta.dirname, "fixtures", "packs");
209 const pack = yield* fs.readFile(path.join(dir, "ofs-delta.pack"));
210 const manifest = JSON.parse(
211 yield* fs.readFileString(path.join(dir, "manifest.json")),
212 ) as {
213 packs: Record<string, { oids: ReadonlyArray<string> }>;
214 };
215 const expected = new Set(manifest.packs["ofs-delta"]!.oids);
216 const count = new DataView(pack.buffer, pack.byteOffset).getUint32(8);
217 const buf = pack.subarray(12);
218 const bounds = yield* scanBounds(buf, {
219 base: 12,
220 remaining: count,
221 maxObjectSize: 64 << 20,
222 });
223 expect(bounds.entries.length).toBe(count);
224 expect(
225 bounds.entries.some(
226 (b) => b.type === 6 && b.baseOffset !== undefined,
227 ),
228 ).toBe(true);
229 const hashed = yield* hashBounds(buf, bounds.entries, {
230 base: 12,
231 maxObjectSize: 64 << 20,
232 });
233 expect(hashed.unresolved).toEqual([]);
234 expect(new Set(hashed.entries.map((e) => e.oid))).toEqual(expected);
235 // Hashing only the second half: bases in the first half are unresolved.
236 const half = bounds.entries.slice(Math.floor(count / 2));
237 const partial = yield* hashBounds(buf, half, {
238 base: 12,
239 maxObjectSize: 64 << 20,
240 });
241 expect(partial.entries.length + partial.unresolved.length).toBe(
242 half.length,
243 );
244 }).pipe(Effect.provide(BunServices.layer)),
245 );
246 });
247 },
248);
249
250describe("findBoundary (DESIGN §22.9)", { tags: ["unit", "local"] }, () => {
251 test("a boundary past the first MiB is found: the search covers the whole chunk", async () => {
252 await Effect.runPromise(
253 Effect.gen(function* () {
254 // One 1.5 MiB blob followed by small ones: a chunk starting inside
255 // the big blob has its first boundary ~1.5 MiB in.
256 const big = new Uint8Array(1_500_000);
257 crypto.getRandomValues(big);
258 const pieces: Array<Uint8Array> = [
259 packHeader(4),
260 encodeTypeSize(3, big.length),
261 yield* Zlib.deflate(big),
262 ];
263 for (let i = 0; i < 3; i++) {
264 const c = new Uint8Array(500);
265 crypto.getRandomValues(c);
266 pieces.push(encodeTypeSize(3, c.length), yield* Zlib.deflate(c));
267 }
268 const body = concat(pieces);
269 const sha = makeSha1();
270 sha.update(body);
271 const pack = concat([body, sha.digest()]);
272 const bigEnd = 12 + pieces[1]!.length + pieces[2]!.length;
273 const chunk = pack.subarray(100);
274 expect(findBoundary(chunk, { maxObjectSize: 1 << 24 })).toBe(
275 bigEnd - 100,
276 );
277 expect(
278 findBoundary(chunk, { maxObjectSize: 1 << 24, maxSearch: 1 << 20 }),
279 ).toBeUndefined();
280 }),
281 );
282 });
283 test("from arbitrary offsets in a synthetic pack, the first boundary found is a true entry start", async () => {
284 await Effect.runPromise(
285 Effect.gen(function* () {
286 const { pack, count } = yield* buildPack(200);
287 const truth = yield* scanBounds(pack.subarray(12), {
288 base: 12,
289 remaining: count,
290 maxObjectSize: 1 << 20,
291 });
292 const starts = new Set(truth.entries.map((b) => b.offset));
293 let seed = 3;
294 for (let i = 0; i < 60; i++) {
295 seed = (seed * 1103515245 + 12345) & 0x7fffffff;
296 const at = 12 + (seed % (pack.length - 40_000));
297 const chunk = pack.subarray(at, at + 30_000);
298 const found = findBoundary(chunk, { maxObjectSize: 1 << 20 });
299 expect(found).toBeDefined();
300 expect(starts.has(at + found!)).toBe(true);
301 // And it is the FIRST true boundary at or after `at`.
302 const first = truth.entries.find(
303 (b) => b.offset >= at && b.offset + 10 < at + 30_000,
304 )!;
305 expect(at + found!).toBe(first.offset);
306 }
307 }),
308 );
309 });
310
311 test("the ofs-delta fixture: resync from every byte offset lands on a true boundary", async () => {
312 await Effect.runPromise(
313 Effect.gen(function* () {
314 const fs = yield* FileSystem.FileSystem;
315 const path = yield* Path.Path;
316 const dir = path.join(import.meta.dirname, "fixtures", "packs");
317 const pack = yield* fs.readFile(path.join(dir, "ofs-delta.pack"));
318 const count = new DataView(pack.buffer, pack.byteOffset).getUint32(8);
319 const truth = yield* scanBounds(pack.subarray(12), {
320 base: 12,
321 remaining: count,
322 maxObjectSize: 1 << 20,
323 });
324 const starts = truth.entries.map((b) => b.offset);
325 // Skip the last two entries: a boundary needs a following entry.
326 const lastTestable = starts[starts.length - 2]!;
327 for (let at = 12; at < lastTestable; at++) {
328 const found = findBoundary(pack.subarray(at), {
329 maxObjectSize: 1 << 20,
330 });
331 expect(found, `from ${at}`).toBeDefined();
332 expect(
333 starts.includes(at + found!),
334 `from ${at} → ${at + found!}`,
335 ).toBe(true);
336 }
337 }).pipe(Effect.provide(BunServices.layer)),
338 );
339 });
340});