1/**
2 * Git object codec: oid hashing, loose headers, commit/tree/tag parsing,
3 * tree encoding with git's directory sort rule, and the pack varint codecs
4 * (type+size, delta-size, OFS_DELTA offset).
5 *
6 * Pure CPU module. The only platform import is `node:crypto` (sha1), used
7 * synchronously and exposed behind Effect wrappers / a tiny incremental
8 * `Sha1` interface.
9 *
10 * Wire-format references (verified against gitformat-pack / gitprotocol-pack):
11 *
12 * - Object id = sha1 over `"<type> <size>\0" + content` (uncompressed).
13 * - Pack entry header: first byte `MSB | type(3) | size low 4 bits`, then
14 * little-endian 7-bit continuation groups.
15 * - OFS_DELTA offset: big-endian 7-bit groups **with a +1 bias applied per
16 * continuation byte** (the classic decoder bug).
17 * - Tree entries sort byte-wise by name with directories compared as if
18 * suffixed `/` (`foo.txt` < `foo/`).
19 */
20import * as Effect from "effect/Effect";
21import * as Schema from "effect/Schema";
22import crypto from "node:crypto";
23
24// ─────────────────────────────────────────────────────────────────────────────
25// Oids
26// ─────────────────────────────────────────────────────────────────────────────
27
28/**
29 * A 40-hex sha1 object id. Kept as a plain string alias in the codec layer;
30 * the REST surface brands it separately.
31 */
32export type Oid = string;
33
34/**
35 * The all-zero oid used by the wire protocol for "no object" (ref creation
36 * old-oid, ref deletion new-oid, empty-repo advertisement).
37 */
38export const ZERO_OID: Oid = "0".repeat(40);
39
40/**
41 * Regular expression matching a valid 40-hex sha1 oid.
42 */
43export const OID_REGEX = /^[0-9a-f]{40}$/;
44
45/**
46 * Returns `true` when the string is a well-formed 40-hex sha1 oid.
47 */
48// NOTE: deliberately NOT a type guard — `Oid` is an unbranded `string`
49// alias, so `s is Oid` would narrow the else-branch to `never`.
50export const isOid = (s: string): boolean => OID_REGEX.test(s);
51
52/**
53 * Error raised by the object codec when parsing malformed object content
54 * (commits, trees, tags) or malformed varint/offset encodings.
55 */
56export class ObjectParseError extends Schema.TaggedError<ObjectParseError>()(
57 "ObjectParseError",
58 { reason: Schema.String },
59) {}
60
61// ─────────────────────────────────────────────────────────────────────────────
62// Object types
63// ─────────────────────────────────────────────────────────────────────────────
64
65/**
66 * Numeric git object types as used in pack entry headers and the object
67 * store's `objects.type` column.
68 */
69export const ObjectType = {
70 commit: 1,
71 tree: 2,
72 blob: 3,
73 tag: 4,
74} as const;
75
76/**
77 * The numeric type of a real (non-delta) git object.
78 */
79export type ObjectType = (typeof ObjectType)[keyof typeof ObjectType];
80
81/**
82 * Numeric pack entry types: the four object types plus the two delta
83 * representations (`6 = OBJ_OFS_DELTA`, `7 = OBJ_REF_DELTA`). `0` is invalid
84 * and `5` is reserved by the format.
85 */
86export const PackEntryType = {
87 ...ObjectType,
88 ofsDelta: 6,
89 refDelta: 7,
90} as const;
91
92/**
93 * The numeric type of a pack entry (object or delta).
94 */
95export type PackEntryType = (typeof PackEntryType)[keyof typeof PackEntryType];
96
97/**
98 * The canonical text name of a git object type (as used in loose headers and
99 * commit/tag bodies).
100 */
101export type ObjectTypeName = "commit" | "tree" | "blob" | "tag";
102
103const TYPE_NAMES: Record<ObjectType, ObjectTypeName> = {
104 1: "commit",
105 2: "tree",
106 3: "blob",
107 4: "tag",
108};
109
110/**
111 * Maps a numeric object type to its canonical text name.
112 */
113export const objectTypeName = (type: ObjectType): ObjectTypeName =>
114 TYPE_NAMES[type];
115
116/**
117 * Maps a text object type name back to its numeric type, or `undefined` when
118 * the name is not one of `commit|tree|blob|tag`.
119 */
120export const objectTypeOf = (name: string): ObjectType | undefined => {
121 switch (name) {
122 case "commit":
123 return 1;
124 case "tree":
125 return 2;
126 case "blob":
127 return 3;
128 case "tag":
129 return 4;
130 default:
131 return undefined;
132 }
133};
134
135/**
136 * Returns `true` when a pack entry type denotes a delta (OFS or REF).
137 */
138export const isDeltaType = (type: PackEntryType): type is 6 | 7 =>
139 type === 6 || type === 7;
140
141// ─────────────────────────────────────────────────────────────────────────────
142// Bytes / hex helpers
143// ─────────────────────────────────────────────────────────────────────────────
144
145const HEX = "0123456789abcdef";
146
147/**
148 * Lowercase hex encoding of a byte array (used for oids and pack trailers).
149 */
150export const bytesToHex = (bytes: Uint8Array): string => {
151 let out = "";
152 for (let i = 0; i < bytes.length; i++) {
153 const b = bytes[i]!;
154 out += HEX[b >> 4]! + HEX[b & 0x0f]!;
155 }
156 return out;
157};
158
159/**
160 * Decodes a lowercase/uppercase hex string into bytes. Throws
161 * {@link ObjectParseError} on odd length or non-hex characters.
162 */
163export const hexToBytes = (hex: string): Uint8Array => {
164 if (hex.length % 2 !== 0) {
165 throw new ObjectParseError({
166 reason: `odd-length hex string: ${hex.length}`,
167 });
168 }
169 const out = new Uint8Array(hex.length / 2);
170 for (let i = 0; i < out.length; i++) {
171 const byte = Number.parseInt(hex.slice(i * 2, i * 2 + 2), 16);
172 if (Number.isNaN(byte)) {
173 throw new ObjectParseError({
174 reason: `invalid hex at position ${i * 2}`,
175 });
176 }
177 out[i] = byte;
178 }
179 return out;
180};
181
182/**
183 * Concatenates byte chunks into one contiguous buffer.
184 */
185export const concatBytes = (
186 chunks: ReadonlyArray<Uint8Array>,
187 totalLength?: number,
188): Uint8Array => {
189 const total =
190 totalLength ?? chunks.reduce((acc, chunk) => acc + chunk.length, 0);
191 const out = new Uint8Array(total);
192 let pos = 0;
193 for (const chunk of chunks) {
194 out.set(chunk, pos);
195 pos += chunk.length;
196 }
197 return out;
198};
199
200const encoder = new TextEncoder();
201const decoder = new TextDecoder("utf-8");
202
203/**
204 * UTF-8 encodes a string (small shared helper for the codec modules).
205 */
206export const utf8Encode = (s: string): Uint8Array => encoder.encode(s);
207
208/**
209 * UTF-8 decodes bytes (lossy for non-UTF-8 content — the codec never
210 * re-serializes from decoded text, so round-tripping is unaffected).
211 */
212export const utf8Decode = (bytes: Uint8Array): string => decoder.decode(bytes);
213
214// ─────────────────────────────────────────────────────────────────────────────
215// Hashing
216// ─────────────────────────────────────────────────────────────────────────────
217
218/**
219 * Minimal incremental sha1 hasher used for pack trailers and object ids.
220 * Construct via {@link makeSha1}. `digest`/`digestHex` may be called once.
221 */
222export interface Sha1 {
223 /** Feeds bytes into the hash. */
224 readonly update: (bytes: Uint8Array) => void;
225 /** Finalizes and returns the 20-byte raw digest. */
226 readonly digest: () => Uint8Array;
227 /** Finalizes and returns the 40-hex digest. */
228 readonly digestHex: () => string;
229}
230
231/**
232 * Creates an incremental sha1 hasher over `node:crypto`.
233 *
234 * This is a plain (synchronous, CPU-only) factory; call sites participate in
235 * the Effect runtime by constructing it inside `Effect.sync` (see
236 * `PackWriter`), keeping `node:crypto` contained to this module.
237 */
238export const makeSha1 = (): Sha1 => {
239 const hash = crypto.createHash("sha1");
240 let finalized: Uint8Array | undefined;
241 return {
242 update: (bytes) => {
243 hash.update(bytes);
244 },
245 digest: () => {
246 finalized ??= new Uint8Array(hash.digest());
247 return finalized;
248 },
249 digestHex: () => {
250 finalized ??= new Uint8Array(hash.digest());
251 return bytesToHex(finalized);
252 },
253 };
254};
255
256/**
257 * Builds the canonical loose-object header `"<type> <size>\0"` used as the
258 * hashing prefix (and git's on-disk loose format prefix).
259 */
260export const looseHeader = (type: ObjectType, size: number): Uint8Array =>
261 utf8Encode(`${objectTypeName(type)} ${size}\0`);
262
263/**
264 * Computes the object id: `sha1("<type> <size>\0" + content)` over the
265 * uncompressed content.
266 */
267/** Synchronous form of {@link hashObject} for hot loops (DESIGN §22.5). */
268export const hashObjectSync = (type: ObjectType, content: Uint8Array): Oid => {
269 const sha = makeSha1();
270 sha.update(looseHeader(type, content.length));
271 sha.update(content);
272 return sha.digestHex();
273};
274
275export const hashObject = (
276 type: ObjectType,
277 content: Uint8Array,
278): Effect.Effect<Oid> =>
279 Effect.sync(() => {
280 const sha = makeSha1();
281 sha.update(looseHeader(type, content.length));
282 sha.update(content);
283 return sha.digestHex();
284 });
285
286// ─────────────────────────────────────────────────────────────────────────────
287// Commit / tag parsing
288// ─────────────────────────────────────────────────────────────────────────────
289
290/**
291 * A parsed author/committer/tagger identity line:
292 * `Name <email> <unix-ts> <±hhmm>`.
293 */
294export interface Identity {
295 readonly name: string;
296 readonly email: string;
297 /** Unix timestamp in seconds. */
298 readonly when: number;
299 /** Timezone offset as written, e.g. `+0200` or `-0700`. */
300 readonly tz: string;
301}
302
303/**
304 * A parsed commit object. The raw bytes remain the source of truth for
305 * hashing/round-tripping; this structure feeds the commit graph and REST
306 * reads only.
307 */
308export interface ParsedCommit {
309 /** The commit's root tree oid. */
310 readonly tree: Oid;
311 /** Parent commit oids, in order. */
312 readonly parents: ReadonlyArray<Oid>;
313 readonly author: Identity;
314 readonly committer: Identity;
315 /** The full GPG signature block, when present. */
316 readonly gpgsig: string | undefined;
317 /** Commit message (everything after the first blank line), UTF-8 decoded. */
318 readonly message: string;
319 /**
320 * All raw headers in order as `[key, value]` pairs (continuation lines
321 * joined with `\n`), including the standard ones above.
322 */
323 readonly headers: ReadonlyArray<readonly [string, string]>;
324}
325
326/**
327 * A parsed annotated tag object.
328 */
329export interface ParsedTag {
330 /** The tagged object's oid. */
331 readonly object: Oid;
332 /** The tagged object's type name. */
333 readonly targetType: ObjectTypeName;
334 /** The tag name (without `refs/tags/`). */
335 readonly tag: string;
336 /** Tagger identity; optional (ancient tags may lack it). */
337 readonly tagger: Identity | undefined;
338 /** Tag message. */
339 readonly message: string;
340 /** All raw headers in order. */
341 readonly headers: ReadonlyArray<readonly [string, string]>;
342}
343
344const IDENTITY_REGEX = /^(.*) <(.*)> (\d+) ([+-]\d{4})$/;
345
346/**
347 * Parses an identity value (`Name <email> ts tz`). Fails with
348 * {@link ObjectParseError} when the shape does not match.
349 */
350export const parseIdentity = (
351 value: string,
352): Effect.Effect<Identity, ObjectParseError> =>
353 Effect.suspend(() => {
354 const match = IDENTITY_REGEX.exec(value);
355 if (match === null) {
356 return Effect.fail(
357 new ObjectParseError({ reason: `malformed identity: ${value}` }),
358 );
359 }
360 return Effect.succeed({
361 name: match[1]!,
362 email: match[2]!,
363 when: Number.parseInt(match[3]!, 10),
364 tz: match[4]!,
365 });
366 });
367
368/**
369 * Splits an object body into its header block and message, honoring
370 * continuation lines (lines starting with a single space extend the previous
371 * header's value, joined with `\n` — this is how `gpgsig` spans lines).
372 */
373const parseHeaderBlock = (
374 content: Uint8Array,
375): {
376 readonly headers: Array<readonly [string, string]>;
377 readonly message: string;
378} => {
379 const text = utf8Decode(content);
380 const sep = text.indexOf("\n\n");
381 const headerText = sep === -1 ? text : text.slice(0, sep);
382 const message = sep === -1 ? "" : text.slice(sep + 2);
383 const headers: Array<readonly [string, string]> = [];
384 for (const line of headerText.split("\n")) {
385 if (line.startsWith(" ") && headers.length > 0) {
386 const last = headers[headers.length - 1]!;
387 headers[headers.length - 1] = [last[0], `${last[1]}\n${line.slice(1)}`];
388 } else {
389 const space = line.indexOf(" ");
390 if (space === -1) {
391 headers.push([line, ""]);
392 } else {
393 headers.push([line.slice(0, space), line.slice(space + 1)]);
394 }
395 }
396 }
397 return { headers, message };
398};
399
400/**
401 * Parses a commit object's content (without the loose header). Strict about
402 * the fields the engine depends on: `tree`, `author`, `committer` must be
403 * present and well-formed; unknown headers (incl. `gpgsig`) are preserved.
404 */
405export const parseCommit = Effect.fn(function* (content: Uint8Array) {
406 const { headers, message } = parseHeaderBlock(content);
407 let tree: Oid | undefined;
408 const parents: Array<Oid> = [];
409 let authorRaw: string | undefined;
410 let committerRaw: string | undefined;
411 let gpgsig: string | undefined;
412 for (const [key, value] of headers) {
413 switch (key) {
414 case "tree":
415 if (!isOid(value)) {
416 return yield* new ObjectParseError({
417 reason: `commit tree is not a valid oid: ${value}`,
418 });
419 }
420 tree = value;
421 break;
422 case "parent":
423 if (!isOid(value)) {
424 return yield* new ObjectParseError({
425 reason: `commit parent is not a valid oid: ${value}`,
426 });
427 }
428 parents.push(value);
429 break;
430 case "author":
431 authorRaw = value;
432 break;
433 case "committer":
434 committerRaw = value;
435 break;
436 case "gpgsig":
437 gpgsig = value;
438 break;
439 default:
440 break;
441 }
442 }
443 if (tree === undefined) {
444 return yield* new ObjectParseError({ reason: "commit has no tree header" });
445 }
446 if (authorRaw === undefined) {
447 return yield* new ObjectParseError({
448 reason: "commit has no author header",
449 });
450 }
451 if (committerRaw === undefined) {
452 return yield* new ObjectParseError({
453 reason: "commit has no committer header",
454 });
455 }
456 const author = yield* parseIdentity(authorRaw);
457 const committer = yield* parseIdentity(committerRaw);
458 const parsed: ParsedCommit = {
459 tree,
460 parents,
461 author,
462 committer,
463 gpgsig,
464 message,
465 headers,
466 };
467 return parsed;
468});
469
470/**
471 * Formats an identity line value: `Name <email> <unix-ts> <±hhmm>`.
472 * Round-trips {@link parseIdentity}.
473 */
474export const formatIdentity = (id: Identity): string =>
475 `${id.name} <${id.email}> ${id.when} ${id.tz}`;
476
477/** Input of {@link encodeCommit}. */
478export interface CommitFields {
479 /** The commit's root tree oid. */
480 readonly tree: Oid;
481 /** Parent commit oids, in order. */
482 readonly parents: ReadonlyArray<Oid>;
483 readonly author: Identity;
484 readonly committer: Identity;
485 /** Message, verbatim — callers include the trailing `\n`. */
486 readonly message: string;
487}
488
489const TZ_REGEX = /^[+-]\d{4}$/;
490
491const validateIdentity = (
492 role: string,
493 id: Identity,
494): ObjectParseError | undefined => {
495 if (/[<>\n]/.test(id.name) || /[<>\n]/.test(id.email)) {
496 return new ObjectParseError({
497 reason: `commit ${role} name/email must not contain '<', '>' or newline`,
498 });
499 }
500 if (!Number.isInteger(id.when) || id.when < 0) {
501 return new ObjectParseError({
502 reason: `commit ${role} timestamp is not a non-negative integer: ${id.when}`,
503 });
504 }
505 if (!TZ_REGEX.test(id.tz)) {
506 return new ObjectParseError({
507 reason: `commit ${role} timezone is not ±hhmm: ${id.tz}`,
508 });
509 }
510 return undefined;
511};
512
513/**
514 * Encodes commit content (without the loose header):
515 * `tree <oid>\n` + `parent <oid>\n`* + `author …\n` + `committer …\n` +
516 * `\n` + message. Byte-exact round trip through {@link parseCommit}.
517 */
518export const encodeCommit = (
519 fields: CommitFields,
520): Effect.Effect<Uint8Array, ObjectParseError> =>
521 Effect.suspend(() => {
522 if (!isOid(fields.tree)) {
523 return Effect.fail(
524 new ObjectParseError({
525 reason: `commit tree is not a valid oid: ${fields.tree}`,
526 }),
527 );
528 }
529 for (const parent of fields.parents) {
530 if (!isOid(parent)) {
531 return Effect.fail(
532 new ObjectParseError({
533 reason: `commit parent is not a valid oid: ${parent}`,
534 }),
535 );
536 }
537 }
538 for (const [role, id] of [
539 ["author", fields.author],
540 ["committer", fields.committer],
541 ] as const) {
542 const invalid = validateIdentity(role, id);
543 if (invalid !== undefined) return Effect.fail(invalid);
544 }
545 const lines = [
546 `tree ${fields.tree}\n`,
547 ...fields.parents.map((parent) => `parent ${parent}\n`),
548 `author ${formatIdentity(fields.author)}\n`,
549 `committer ${formatIdentity(fields.committer)}\n`,
550 `\n`,
551 fields.message,
552 ];
553 return Effect.succeed(utf8Encode(lines.join("")));
554 });
555
556/**
557 * Parses an annotated tag object's content (without the loose header).
558 * `object`, `type`, and `tag` are required; `tagger` is optional.
559 */
560export const parseTag = Effect.fn(function* (content: Uint8Array) {
561 const { headers, message } = parseHeaderBlock(content);
562 let object: Oid | undefined;
563 let targetType: ObjectTypeName | undefined;
564 let tag: string | undefined;
565 let taggerRaw: string | undefined;
566 for (const [key, value] of headers) {
567 switch (key) {
568 case "object":
569 if (!isOid(value)) {
570 return yield* new ObjectParseError({
571 reason: `tag object is not a valid oid: ${value}`,
572 });
573 }
574 object = value;
575 break;
576 case "type": {
577 const t = objectTypeOf(value);
578 if (t === undefined) {
579 return yield* new ObjectParseError({
580 reason: `tag has invalid target type: ${value}`,
581 });
582 }
583 targetType = objectTypeName(t);
584 break;
585 }
586 case "tag":
587 tag = value;
588 break;
589 case "tagger":
590 taggerRaw = value;
591 break;
592 default:
593 break;
594 }
595 }
596 if (object === undefined || targetType === undefined || tag === undefined) {
597 return yield* new ObjectParseError({
598 reason: "tag is missing object/type/tag header",
599 });
600 }
601 const tagger =
602 taggerRaw === undefined ? undefined : yield* parseIdentity(taggerRaw);
603 const parsed: ParsedTag = {
604 object,
605 targetType,
606 tag,
607 tagger,
608 message,
609 headers,
610 };
611 return parsed;
612});
613
614// ─────────────────────────────────────────────────────────────────────────────
615// Trees
616// ─────────────────────────────────────────────────────────────────────────────
617
618/**
619 * One entry of a tree object.
620 *
621 * `mode` is the ascii octal mode without leading zeros as stored in canonical
622 * trees: `100644` file, `100755` executable, `120000` symlink, `160000`
623 * gitlink (submodule), `40000` subtree.
624 */
625export interface TreeEntry {
626 readonly mode: string;
627 readonly name: string;
628 readonly oid: Oid;
629}
630
631/** Tree mode string for a subtree entry. */
632export const TREE_MODE = "40000";
633/** Tree mode string for a gitlink (submodule) entry. */
634export const GITLINK_MODE = "160000";
635
636/**
637 * The high-level kind of a tree entry derived from its mode.
638 */
639export type TreeEntryKind = "blob" | "tree" | "commit";
640
641/**
642 * Classifies a tree entry mode: `40000` → `tree`, `160000` → `commit`
643 * (gitlink), anything else → `blob`.
644 */
645export const treeEntryKind = (mode: string): TreeEntryKind =>
646 mode === TREE_MODE ? "tree" : mode === GITLINK_MODE ? "commit" : "blob";
647
648/**
649 * Parses a tree object's content into its entries:
650 * `<mode ascii octal> SP <name> NUL <20 raw sha1 bytes>` concatenated with no
651 * separators.
652 */
653export const parseTree = (
654 content: Uint8Array,
655): Effect.Effect<ReadonlyArray<TreeEntry>, ObjectParseError> =>
656 Effect.suspend(() => {
657 const entries: Array<TreeEntry> = [];
658 let pos = 0;
659 while (pos < content.length) {
660 const spaceIdx = content.indexOf(0x20, pos);
661 if (spaceIdx === -1) {
662 return Effect.fail(
663 new ObjectParseError({
664 reason: `tree entry at ${pos}: no space after mode`,
665 }),
666 );
667 }
668 const mode = utf8Decode(content.subarray(pos, spaceIdx));
669 if (!/^[0-7]{1,6}$/.test(mode)) {
670 return Effect.fail(
671 new ObjectParseError({
672 reason: `tree entry at ${pos}: bad mode ${mode}`,
673 }),
674 );
675 }
676 const nulIdx = content.indexOf(0x00, spaceIdx + 1);
677 if (nulIdx === -1) {
678 return Effect.fail(
679 new ObjectParseError({
680 reason: `tree entry at ${pos}: no NUL after name`,
681 }),
682 );
683 }
684 const name = utf8Decode(content.subarray(spaceIdx + 1, nulIdx));
685 if (name.length === 0) {
686 return Effect.fail(
687 new ObjectParseError({ reason: `tree entry at ${pos}: empty name` }),
688 );
689 }
690 if (nulIdx + 21 > content.length) {
691 return Effect.fail(
692 new ObjectParseError({
693 reason: `tree entry at ${pos}: truncated sha`,
694 }),
695 );
696 }
697 const oid = bytesToHex(content.subarray(nulIdx + 1, nulIdx + 21));
698 entries.push({ mode, name, oid });
699 pos = nulIdx + 21;
700 }
701 return Effect.succeed(entries);
702 });
703
704/**
705 * Compares two tree entries with git's canonical sort rule: byte-wise on the
706 * name **with directory entries compared as if suffixed `/`** (so `foo.txt`
707 * sorts before the tree `foo`, which sorts as `foo/`). Wrong order changes
708 * the tree hash and trips `git fsck`.
709 */
710export const treeEntryCompare = (a: TreeEntry, b: TreeEntry): number => {
711 const aBytes = utf8Encode(
712 treeEntryKind(a.mode) === "tree" ? `${a.name}/` : a.name,
713 );
714 const bBytes = utf8Encode(
715 treeEntryKind(b.mode) === "tree" ? `${b.name}/` : b.name,
716 );
717 const len = Math.min(aBytes.length, bBytes.length);
718 for (let i = 0; i < len; i++) {
719 const d = aBytes[i]! - bBytes[i]!;
720 if (d !== 0) return d;
721 }
722 return aBytes.length - bBytes.length;
723};
724
725/**
726 * Encodes tree entries into canonical tree object content. Entries are sorted
727 * with {@link treeEntryCompare} and modes are normalized (leading zeros
728 * stripped, so `040000` becomes the canonical `40000`).
729 */
730export const encodeTree = (
731 entries: ReadonlyArray<TreeEntry>,
732): Effect.Effect<Uint8Array, ObjectParseError> =>
733 Effect.suspend(() => {
734 try {
735 const sorted = [...entries].sort(treeEntryCompare);
736 const parts: Array<Uint8Array> = [];
737 let total = 0;
738 for (const entry of sorted) {
739 const mode = entry.mode.replace(/^0+(?=\d)/, "");
740 if (!/^[0-7]{1,6}$/.test(mode)) {
741 throw new ObjectParseError({
742 reason: `invalid tree entry mode: ${entry.mode}`,
743 });
744 }
745 if (!isOid(entry.oid)) {
746 throw new ObjectParseError({
747 reason: `invalid tree entry oid: ${entry.oid}`,
748 });
749 }
750 const head = utf8Encode(`${mode} ${entry.name}\0`);
751 const sha = hexToBytes(entry.oid);
752 parts.push(head, sha);
753 total += head.length + sha.length;
754 }
755 return Effect.succeed(concatBytes(parts, total));
756 } catch (error) {
757 return error instanceof ObjectParseError
758 ? Effect.fail(error)
759 : Effect.fail(new ObjectParseError({ reason: String(error) }));
760 }
761 });
762
763// ─────────────────────────────────────────────────────────────────────────────
764// Varint codecs (pack format)
765// ─────────────────────────────────────────────────────────────────────────────
766
767/**
768 * Result of decoding a pack entry type+size header.
769 */
770export interface TypeSizeHeader {
771 readonly type: PackEntryType;
772 /** Uncompressed size of the entry data (for deltas: of the delta payload). */
773 readonly size: number;
774 /** Offset of the first byte after the header. */
775 readonly next: number;
776}
777
778/**
779 * Decodes the pack entry header varint at `offset`:
780 * `size = (b0 & 0x0F) | (b1 & 0x7F) << 4 | (b2 & 0x7F) << 11 | ...`,
781 * `type = (b0 >> 4) & 0x07`. Throws {@link ObjectParseError} on truncation
782 * or an invalid type (0 or 5).
783 */
784export const decodeTypeSize = (
785 buf: Uint8Array,
786 offset: number,
787): TypeSizeHeader => {
788 if (offset >= buf.length) {
789 throw new ObjectParseError({ reason: "truncated pack entry header" });
790 }
791 let b = buf[offset]!;
792 const rawType = (b >> 4) & 0x07;
793 if (rawType === 0 || rawType === 5) {
794 throw new ObjectParseError({
795 reason: `invalid pack entry type ${rawType} at offset ${offset}`,
796 });
797 }
798 const type = rawType as PackEntryType;
799 let size = b & 0x0f;
800 let shift = 4;
801 let i = offset + 1;
802 while ((b & 0x80) !== 0) {
803 if (i >= buf.length) {
804 throw new ObjectParseError({ reason: "truncated pack entry header" });
805 }
806 if (shift > 53) {
807 throw new ObjectParseError({ reason: "pack entry size varint overflow" });
808 }
809 b = buf[i]!;
810 i += 1;
811 size += (b & 0x7f) * 2 ** shift;
812 shift += 7;
813 }
814 return { type, size, next: i };
815};
816
817/**
818 * Encodes a pack entry type+size header varint (inverse of
819 * {@link decodeTypeSize}).
820 */
821export const encodeTypeSize = (
822 type: PackEntryType,
823 size: number,
824): Uint8Array => {
825 const out: Array<number> = [];
826 let rest = Math.floor(size / 16);
827 let first = ((type & 0x07) << 4) | (size & 0x0f);
828 if (rest > 0) first |= 0x80;
829 out.push(first);
830 while (rest > 0) {
831 let b = rest & 0x7f;
832 rest = Math.floor(rest / 128);
833 if (rest > 0) b |= 0x80;
834 out.push(b);
835 }
836 return Uint8Array.from(out);
837};
838
839/**
840 * Result of decoding a plain little-endian 7-bit varint.
841 */
842export interface Varint {
843 readonly value: number;
844 /** Offset of the first byte after the varint. */
845 readonly next: number;
846}
847
848/**
849 * Decodes a plain little-endian 7-bit varint (MSB = continue) — the encoding
850 * used by delta payload base/result size headers. Throws
851 * {@link ObjectParseError} on truncation or overflow past 2^53.
852 */
853export const decodeSizeVarint = (buf: Uint8Array, offset: number): Varint => {
854 let value = 0;
855 let shift = 0;
856 let i = offset;
857 for (;;) {
858 if (i >= buf.length) {
859 throw new ObjectParseError({ reason: "truncated size varint" });
860 }
861 if (shift > 53) {
862 throw new ObjectParseError({ reason: "size varint overflow" });
863 }
864 const b = buf[i]!;
865 i += 1;
866 value += (b & 0x7f) * 2 ** shift;
867 shift += 7;
868 if ((b & 0x80) === 0) break;
869 }
870 return { value, next: i };
871};
872
873/**
874 * Encodes a plain little-endian 7-bit varint (inverse of
875 * {@link decodeSizeVarint}).
876 */
877export const encodeSizeVarint = (value: number): Uint8Array => {
878 const out: Array<number> = [];
879 let v = value;
880 for (;;) {
881 let b = v & 0x7f;
882 v = Math.floor(v / 128);
883 if (v > 0) b |= 0x80;
884 out.push(b);
885 if (v === 0) break;
886 }
887 return Uint8Array.from(out);
888};
889
890/**
891 * Decodes an OFS_DELTA negative-offset varint at `offset`: big-endian 7-bit
892 * groups (MSB = continue) **with a +1 bias applied on every continuation**:
893 *
894 * ```
895 * n = b0 & 0x7F
896 * while (b0 & 0x80): b0 = next; n = ((n + 1) << 7) | (b0 & 0x7F)
897 * ```
898 *
899 * Naive concatenation without the `+1` is wrong for multi-byte offsets.
900 * Throws {@link ObjectParseError} on truncation.
901 */
902export const decodeOfsDeltaOffset = (
903 buf: Uint8Array,
904 offset: number,
905): Varint => {
906 if (offset >= buf.length) {
907 throw new ObjectParseError({ reason: "truncated ofs-delta offset" });
908 }
909 let i = offset;
910 let b = buf[i]!;
911 i += 1;
912 let n = b & 0x7f;
913 while ((b & 0x80) !== 0) {
914 if (i >= buf.length) {
915 throw new ObjectParseError({ reason: "truncated ofs-delta offset" });
916 }
917 b = buf[i]!;
918 i += 1;
919 n = (n + 1) * 128 + (b & 0x7f);
920 if (!Number.isSafeInteger(n)) {
921 throw new ObjectParseError({ reason: "ofs-delta offset overflow" });
922 }
923 }
924 return { value: n, next: i };
925};
926
927/**
928 * Encodes an OFS_DELTA negative-offset varint (inverse of
929 * {@link decodeOfsDeltaOffset}, matching git's encoder: subtract the bias per
930 * continuation byte, big-endian order).
931 */
932export const encodeOfsDeltaOffset = (value: number): Uint8Array => {
933 const out: Array<number> = [value & 0x7f];
934 let v = Math.floor(value / 128);
935 while (v > 0) {
936 v -= 1;
937 out.unshift(0x80 | (v & 0x7f));
938 v = Math.floor(v / 128);
939 }
940 return Uint8Array.from(out);
941};