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