1/**
2 * Tier-1 pure codec tests (DESIGN.md §9): pkt-line framing, pack varints
3 * (including the OFS_DELTA +1-bias multibyte offsets), delta application
4 * (including the `size==0 ⇒ 0x10000` copy special case), tree sort rules,
5 * object hashing against real-git-computed oids, and zlib entry-boundary
6 * accounting over concatenated deflate streams.
7 *
8 * No cloud, no deploy — everything runs in-process in milliseconds.
9 */
10import { describe, expect, it } from "alchemy-test";
11import * as Effect from "effect/Effect";
12import * as Result from "effect/Result";
13import * as Stream from "effect/Stream";
14import { applyDelta, readDeltaHeader } from "@/Git/Protocol/Delta.ts";
15import {
16 bytesToHex,
17 concatBytes,
18 decodeOfsDeltaOffset,
19 decodeSizeVarint,
20 decodeTypeSize,
21 encodeCommit,
22 encodeOfsDeltaOffset,
23 encodeSizeVarint,
24 encodeTree,
25 encodeTypeSize,
26 formatIdentity,
27 hashObject,
28 hexToBytes,
29 ObjectType,
30 parseCommit,
31 parseTree,
32 treeEntryCompare,
33 utf8Decode,
34 utf8Encode,
35} from "@/Git/Protocol/ObjectCodec.ts";
36import {
37 decodePktLines,
38 decodePktStream,
39 errPkt,
40 flushPkt,
41 MAX_PKT_PAYLOAD,
42 pktLine,
43 pktPayloadText,
44 pktText,
45 readPktLineAt,
46} from "@/Git/Protocol/Pkt.ts";
47import { SIDEBAND_DATA_MAX, sidebandFrames } from "@/Git/Protocol/Sideband.ts";
48import { deflate, inflate, inflateEntry } from "@/Git/Protocol/Zlib.ts";
49
50describe("pkt-line", { tags: ["unit", "local"] }, () => {
51 it.live("encodes data, text (LF-appended), flush, and ERR pkts", () =>
52 Effect.gen(function* () {
53 expect(utf8Decode(pktText("done"))).toBe("0009done\n");
54 // pktText must not double-append the LF
55 expect(utf8Decode(pktText("done\n"))).toBe("0009done\n");
56 expect(utf8Decode(flushPkt)).toBe("0000");
57 expect(utf8Decode(errPkt("boom"))).toBe("000dERR boom\n");
58 const data = pktLine(utf8Encode("abc"));
59 expect(utf8Decode(data)).toBe("0007abc");
60 }),
61 );
62
63 it.live(
64 "round-trips a mixed body and strips trailing LF in payload text",
65 () =>
66 Effect.gen(function* () {
67 const body = concatBytes([
68 pktText(
69 "want 0000000000000000000000000000000000000001 side-band-64k",
70 ),
71 flushPkt,
72 pktText("done"),
73 ]);
74 const pkts = yield* decodePktLines(body);
75 expect(pkts.length).toBe(3);
76 expect(pkts[0]!._tag).toBe("data");
77 expect(pkts[1]!._tag).toBe("flush");
78 expect(pkts[2]!._tag).toBe("data");
79 const first = pkts[0]!;
80 if (first._tag === "data") {
81 expect(pktPayloadText(first.payload)).toBe(
82 "want 0000000000000000000000000000000000000001 side-band-64k",
83 );
84 }
85 }),
86 );
87
88 it.live("stream decoder survives pathological 1-byte chunking", () =>
89 Effect.gen(function* () {
90 const body = concatBytes([
91 pktText("hello"),
92 flushPkt,
93 pktLine(utf8Encode("raw")),
94 ]);
95 const chunks: Uint8Array[] = [];
96 for (let i = 0; i < body.length; i++) {
97 chunks.push(body.subarray(i, i + 1));
98 }
99 const pkts = yield* Stream.runCollect(
100 decodePktStream(Stream.fromArray(chunks)),
101 );
102 expect(pkts.length).toBe(3);
103 }),
104 );
105
106 it.live("readPktLineAt reports incomplete and invalid frames", () =>
107 Effect.gen(function* () {
108 // a declared 8-byte pkt with only 6 bytes present
109 const partial = utf8Encode("0008ab");
110 expect(readPktLineAt(partial, 0)._tag).toBe("incomplete");
111 // non-hex length prefix
112 expect(readPktLineAt(utf8Encode("zzzzabcd"), 0)._tag).toBe("invalid");
113 // lengths 1-3 are reserved/invalid
114 expect(readPktLineAt(utf8Encode("0003x"), 0)._tag).toBe("invalid");
115 }),
116 );
117
118 it.live("rejects payloads over the 65516-byte cap", () =>
119 Effect.gen(function* () {
120 const max = new Uint8Array(MAX_PKT_PAYLOAD);
121 expect(pktLine(max).length).toBe(4 + MAX_PKT_PAYLOAD);
122 expect(() => pktLine(new Uint8Array(MAX_PKT_PAYLOAD + 1))).toThrow();
123 }),
124 );
125});
126
127describe("sideband framing", { tags: ["unit", "local"] }, () => {
128 it.live("splits payloads at the 65515-byte data cap with the band byte", () =>
129 Effect.gen(function* () {
130 const big = new Uint8Array(SIDEBAND_DATA_MAX + 10).fill(7);
131 const frames = sidebandFrames(1, big);
132 expect(frames.length).toBe(2);
133 expect(frames[0]!.length).toBe(4 + 1 + SIDEBAND_DATA_MAX);
134 expect(frames[1]!.length).toBe(4 + 1 + 10);
135 expect(frames[0]![4]).toBe(1);
136 expect(frames[1]![4]).toBe(1);
137 }),
138 );
139});
140
141describe("pack varints", { tags: ["unit", "local"] }, () => {
142 it.live(
143 "type/size header round-trips across the continuation boundaries",
144 () =>
145 Effect.gen(function* () {
146 for (const size of [
147 0,
148 15,
149 16,
150 127,
151 128,
152 4095,
153 4096,
154 1 << 20,
155 2 ** 32 + 5,
156 ]) {
157 for (const type of [1, 2, 3, 4, 6, 7] as const) {
158 const enc = encodeTypeSize(type, size);
159 const dec = decodeTypeSize(enc, 0);
160 expect(dec.type).toBe(type);
161 expect(dec.size).toBe(size);
162 expect(dec.next).toBe(enc.length);
163 }
164 }
165 // 4-bit sizes fit in one byte; 5 bits force a continuation
166 expect(encodeTypeSize(ObjectType.blob, 15).length).toBe(1);
167 expect(encodeTypeSize(ObjectType.blob, 16).length).toBe(2);
168 }),
169 );
170
171 it.live("delta-payload size varint round-trips", () =>
172 Effect.gen(function* () {
173 for (const v of [0, 1, 127, 128, 16383, 16384, 2 ** 31]) {
174 const enc = encodeSizeVarint(v);
175 const dec = decodeSizeVarint(enc, 0);
176 expect(dec.value).toBe(v);
177 expect(dec.next).toBe(enc.length);
178 }
179 }),
180 );
181
182 it.live("OFS_DELTA offsets carry the +1 bias per continuation byte", () =>
183 Effect.gen(function* () {
184 // The classic bug: without the bias, [0x80, 0x00] would decode as 0.
185 // With it, two-byte encodings cover exactly 128..16511 (128 + 2^14 - 1).
186 expect(encodeOfsDeltaOffset(127).length).toBe(1);
187 expect(encodeOfsDeltaOffset(128).length).toBe(2);
188 expect(Array.from(encodeOfsDeltaOffset(128))).toEqual([0x80, 0x00]);
189 expect(encodeOfsDeltaOffset(16511).length).toBe(2);
190 expect(encodeOfsDeltaOffset(16512).length).toBe(3);
191 for (const v of [
192 1,
193 127,
194 128,
195 129,
196 255,
197 256,
198 16383,
199 16384,
200 16511,
201 16512,
202 2 ** 24,
203 ]) {
204 const enc = encodeOfsDeltaOffset(v);
205 const dec = decodeOfsDeltaOffset(enc, 0);
206 expect(dec.value).toBe(v);
207 expect(dec.next).toBe(enc.length);
208 }
209 // known decode vectors
210 expect(decodeOfsDeltaOffset(Uint8Array.from([0x80, 0x00]), 0).value).toBe(
211 128,
212 );
213 expect(decodeOfsDeltaOffset(Uint8Array.from([0x81, 0x00]), 0).value).toBe(
214 256,
215 );
216 }),
217 );
218});
219
220describe("delta application", { tags: ["unit", "local"] }, () => {
221 it.live("applies copy + insert instruction streams", () =>
222 Effect.gen(function* () {
223 const base = utf8Encode("the quick brown fox jumps over the lazy dog");
224 const delta = concatBytes([
225 encodeSizeVarint(base.length),
226 encodeSizeVarint(16 + 5 + 18),
227 Uint8Array.from([0b10010001, 4, 16]), // copy offset=4 size=16
228 Uint8Array.from([5]), // insert 5 bytes
229 utf8Encode("leaps"),
230 Uint8Array.from([0b10010001, 25, 18]), // copy offset=25 size=18
231 ]);
232 const header = readDeltaHeader(delta);
233 expect(header.baseSize).toBe(base.length);
234 expect(header.resultSize).toBe(39);
235 const out = yield* applyDelta(base, delta);
236 expect(utf8Decode(out)).toBe("quick brown fox leaps over the lazy dog");
237 }),
238 );
239
240 it.live("copy size 0 means 0x10000 bytes", () =>
241 Effect.gen(function* () {
242 const base = new Uint8Array(0x10000 + 10);
243 for (let i = 0; i < base.length; i++) base[i] = i % 251;
244 const delta = concatBytes([
245 encodeSizeVarint(base.length),
246 encodeSizeVarint(0x10000),
247 // copy bit set, no offset bytes, no size bytes ⇒ offset 0, size 0x10000
248 Uint8Array.from([0b10000000]),
249 ]);
250 const out = yield* applyDelta(base, delta);
251 expect(out.length).toBe(0x10000);
252 expect(out[0]).toBe(base[0]);
253 expect(out[0xffff]).toBe(base[0xffff]);
254 }),
255 );
256
257 it.live("rejects a result-size mismatch as DeltaFormatError", () =>
258 Effect.gen(function* () {
259 const base = utf8Encode("0123456789");
260 const delta = concatBytes([
261 encodeSizeVarint(base.length),
262 encodeSizeVarint(99), // declared result size never produced
263 Uint8Array.from([0b10010001, 0, 4]), // copy 4 bytes
264 ]);
265 const result = yield* Effect.result(applyDelta(base, delta));
266 expect(Result.isFailure(result)).toBe(true);
267 if (Result.isFailure(result)) {
268 expect(result.failure._tag).toBe("DeltaFormatError");
269 }
270 }),
271 );
272});
273
274describe("tree codec", { tags: ["unit", "local"] }, () => {
275 it.live("sorts directories as name + '/' (the fsck rule)", () =>
276 Effect.gen(function* () {
277 const entries = [
278 { mode: "100644", name: "foo.txt", oid: "a".repeat(40) },
279 { mode: "40000", name: "foo", oid: "b".repeat(40) },
280 { mode: "100644", name: "foo", oid: "c".repeat(40) },
281 ];
282 const sorted = [...entries].sort(treeEntryCompare);
283 // blob "foo" < blob "foo.txt" < tree "foo" (compares as "foo/")
284 expect(sorted[0]!.oid).toBe("c".repeat(40));
285 expect(sorted[1]!.name).toBe("foo.txt");
286 expect(sorted[2]!.mode).toBe("40000");
287 }),
288 );
289
290 it.live("encode → parse round-trips and normalizes entry order", () =>
291 Effect.gen(function* () {
292 const entries = [
293 { mode: "100644", name: "zebra", oid: "a".repeat(40) },
294 { mode: "40000", name: "dir", oid: "b".repeat(40) },
295 { mode: "100755", name: "run.sh", oid: "c".repeat(40) },
296 ];
297 const encoded = yield* encodeTree(entries);
298 const parsed = yield* parseTree(encoded);
299 expect(parsed.length).toBe(3);
300 expect(parsed.map((e) => e.name)).toEqual(["dir", "run.sh", "zebra"]);
301 expect(parsed[0]!.mode).toBe("40000");
302 }),
303 );
304});
305
306describe(
307 "object hashing (real-git oracle oids)",
308 { tags: ["unit", "local"] },
309 () => {
310 it.live("hashes blobs to the oids git computes", () =>
311 Effect.gen(function* () {
312 // git hash-object oracle values
313 expect(yield* hashObject(ObjectType.blob, utf8Encode("hello\n"))).toBe(
314 "ce013625030ba8dba906f756967f9e9ca394464a",
315 );
316 expect(
317 yield* hashObject(ObjectType.blob, utf8Encode("hello world\n")),
318 ).toBe("3b18e512dba79e4c8300dd08aeb37f8e728b8dad");
319 // the famous empty blob / empty tree constants
320 expect(yield* hashObject(ObjectType.blob, new Uint8Array(0))).toBe(
321 "e69de29bb2d1d6434b8b29ae775ad8c2e48c5391",
322 );
323 expect(yield* hashObject(ObjectType.tree, new Uint8Array(0))).toBe(
324 "4b825dc642cb6eb9a060e54bf8d69288fbee4904",
325 );
326 }),
327 );
328
329 it.live("hex codecs round-trip", () =>
330 Effect.gen(function* () {
331 const hex = "9e0b5a0bd293f9feda554193a204193a2c3c5d9c";
332 expect(bytesToHex(hexToBytes(hex))).toBe(hex);
333 }),
334 );
335 },
336);
337
338describe("commit parsing", { tags: ["unit", "local"] }, () => {
339 it.live("parses tree/parents/identities/message", () =>
340 Effect.gen(function* () {
341 const tree = "4b825dc642cb6eb9a060e54bf8d69288fbee4904";
342 const parent = "ce013625030ba8dba906f756967f9e9ca394464a";
343 const commit = utf8Encode(
344 `tree ${tree}\n` +
345 `parent ${parent}\n` +
346 `author A U Thor <author@example.com> 1700000000 +0130\n` +
347 `committer C O Mitter <committer@example.com> 1700000100 -0500\n` +
348 `\n` +
349 `subject line\n\nbody\n`,
350 );
351 const parsed = yield* parseCommit(commit);
352 expect(parsed.tree).toBe(tree);
353 expect(parsed.parents).toEqual([parent]);
354 expect(parsed.author.email).toBe("author@example.com");
355 expect(parsed.author.when).toBe(1700000000);
356 expect(parsed.author.tz).toBe("+0130");
357 expect(parsed.committer.tz).toBe("-0500");
358 expect(parsed.message).toBe("subject line\n\nbody\n");
359 }),
360 );
361
362 it.live("preserves gpgsig continuation lines", () =>
363 Effect.gen(function* () {
364 const tree = "4b825dc642cb6eb9a060e54bf8d69288fbee4904";
365 const commit = utf8Encode(
366 `tree ${tree}\n` +
367 `author A <a@b.c> 1 +0000\n` +
368 `committer A <a@b.c> 1 +0000\n` +
369 `gpgsig -----BEGIN PGP SIGNATURE-----\n` +
370 ` line2\n` +
371 ` -----END PGP SIGNATURE-----\n` +
372 `\n` +
373 `msg\n`,
374 );
375 const parsed = yield* parseCommit(commit);
376 expect(parsed.gpgsig).toContain("line2");
377 expect(parsed.gpgsig).toContain("-----END PGP SIGNATURE-----");
378 }),
379 );
380});
381
382describe("commit encoding", { tags: ["unit", "local"] }, () => {
383 // A real git-produced commit (git 2.x, `git commit -m`), checked in as a
384 // fixture: the oid is git's own, so a matching hash proves the bytes are
385 // byte-exact.
386 const FIXTURE_OID = "805ee86374143354d5a6e5e4df894aa1d631fbb1";
387 const FIXTURE_COMMIT =
388 "tree 44caf5de156e5707051d55989b7db370a80af206\n" +
389 "parent a684c642abd0ef33ec672ce701f48f824837cd03\n" +
390 "author A U Thor <author@example.com> 1700000200 +0000\n" +
391 "committer A U Thor <author@example.com> 1700000300 +0000\n" +
392 "\n" +
393 "second commit\n" +
394 "\n" +
395 "with a body line\n";
396
397 it.live("round-trips a real git commit byte-exactly (fixture oid)", () =>
398 Effect.gen(function* () {
399 const bytes = utf8Encode(FIXTURE_COMMIT);
400 // the fixture really is the commit git hashed
401 expect(yield* hashObject(ObjectType.commit, bytes)).toBe(FIXTURE_OID);
402 const parsed = yield* parseCommit(bytes);
403 const encoded = yield* encodeCommit({
404 tree: parsed.tree,
405 parents: parsed.parents,
406 author: parsed.author,
407 committer: parsed.committer,
408 message: parsed.message,
409 });
410 expect(utf8Decode(encoded)).toBe(FIXTURE_COMMIT);
411 expect(yield* hashObject(ObjectType.commit, encoded)).toBe(FIXTURE_OID);
412 }),
413 );
414
415 it.live("encodes multi-parent commits and formats identities", () =>
416 Effect.gen(function* () {
417 const tree = "4b825dc642cb6eb9a060e54bf8d69288fbee4904";
418 const p1 = "ce013625030ba8dba906f756967f9e9ca394464a";
419 const p2 = "3b18e512dba79e4c8300dd08aeb37f8e728b8dad";
420 const identity = {
421 name: "git-service",
422 email: "git-service@localhost",
423 when: 1700000000,
424 tz: "+0000",
425 };
426 expect(formatIdentity(identity)).toBe(
427 "git-service <git-service@localhost> 1700000000 +0000",
428 );
429 const encoded = yield* encodeCommit({
430 tree,
431 parents: [p1, p2],
432 author: identity,
433 committer: identity,
434 message: "Merge pull request #1 from feature\n",
435 });
436 const parsed = yield* parseCommit(encoded);
437 expect(parsed.tree).toBe(tree);
438 expect(parsed.parents).toEqual([p1, p2]);
439 expect(parsed.author).toEqual(identity);
440 expect(parsed.message).toBe("Merge pull request #1 from feature\n");
441 }),
442 );
443
444 it.live("rejects malformed oids and identities", () =>
445 Effect.gen(function* () {
446 const tree = "4b825dc642cb6eb9a060e54bf8d69288fbee4904";
447 const identity = {
448 name: "ok",
449 email: "ok@example.com",
450 when: 1,
451 tz: "+0000",
452 };
453 const badTree = yield* Effect.result(
454 encodeCommit({
455 tree: "nope",
456 parents: [],
457 author: identity,
458 committer: identity,
459 message: "m\n",
460 }),
461 );
462 expect(Result.isFailure(badTree)).toBe(true);
463 const badName = yield* Effect.result(
464 encodeCommit({
465 tree,
466 parents: [],
467 author: { ...identity, name: "evil <injector>" },
468 committer: identity,
469 message: "m\n",
470 }),
471 );
472 expect(Result.isFailure(badName)).toBe(true);
473 const badTz = yield* Effect.result(
474 encodeCommit({
475 tree,
476 parents: [],
477 author: { ...identity, tz: "UTC" },
478 committer: identity,
479 message: "m\n",
480 }),
481 );
482 expect(Result.isFailure(badTz)).toBe(true);
483 }),
484 );
485});
486
487describe("zlib boundary accounting", { tags: ["unit", "local"] }, () => {
488 it.live("inflateEntry reports the exact compressed span of each entry", () =>
489 Effect.gen(function* () {
490 const a = yield* deflate(utf8Encode("first object content"));
491 const b = yield* deflate(utf8Encode("second object content"));
492 const buf = concatBytes([a, b]);
493 const first = yield* inflateEntry(buf, 0);
494 expect(first.bytesConsumed).toBe(a.length);
495 expect(utf8Decode(first.content)).toBe("first object content");
496 const second = yield* inflateEntry(buf, first.bytesConsumed);
497 expect(second.bytesConsumed).toBe(b.length);
498 expect(utf8Decode(second.content)).toBe("second object content");
499 }),
500 );
501
502 it.live("tolerates trailing junk after Z_STREAM_END", () =>
503 Effect.gen(function* () {
504 const z = yield* deflate(utf8Encode("payload"));
505 const buf = concatBytes([z, utf8Encode("TRAILING GARBAGE")]);
506 const entry = yield* inflateEntry(buf, 0);
507 expect(entry.bytesConsumed).toBe(z.length);
508 expect(utf8Decode(entry.content)).toBe("payload");
509 }),
510 );
511
512 it.live("strict inflate round-trips deflate output", () =>
513 Effect.gen(function* () {
514 const content = utf8Encode("round trip me ".repeat(1000));
515 const z = yield* deflate(content);
516 expect(z.length).toBeLessThan(content.length);
517 const back = yield* inflate(z);
518 expect(utf8Decode(back)).toBe(utf8Decode(content));
519 }),
520 );
521
522 it.live("strict inflate fails on a truncated stream", () =>
523 Effect.gen(function* () {
524 const z = yield* deflate(utf8Encode("payload to truncate"));
525 const result = yield* Effect.result(inflate(z.subarray(0, z.length - 3)));
526 expect(Result.isFailure(result)).toBe(true);
527 if (Result.isFailure(result)) {
528 expect(result.failure._tag).toBe("ZlibError");
529 }
530 }),
531 );
532});