| 1 | import { ByteWriter, equalBytes, fromUtf8, toHex } from "./bytes.js"; |
| 2 | import { applyDelta } from "./delta.js"; |
| 3 | import { CODE_TYPES, TYPE_CODES, hashObject, type GitObject, type ObjectType } from "./objects.js"; |
| 4 | import { sha1 } from "./sha1.js"; |
| 5 | import { inflateAt } from "./zlib.js"; |
| 6 | |
| 7 | const OFS_DELTA = 6; |
| 8 | const REF_DELTA = 7; |
| 9 | |
| 10 | export interface PackedObject extends GitObject { |
| 11 | oid: string; |
| 12 | } |
| 13 | |
| 14 | interface RawEntry { |
| 15 | offset: number; |
| 16 | typeCode: number; |
| 17 | data: Uint8Array; // inflated: full content, or delta instructions |
| 18 | baseOffset?: number; |
| 19 | baseOid?: string; |
| 20 | } |
| 21 | |
| 22 | export type ExternalLookup = (oid: string) => Promise<GitObject | null>; |
| 23 | |
| 24 | /** |
| 25 | * Parse a packfile and fully resolve every object (including deltas). |
| 26 | * `external` resolves REF_DELTA bases that are not inside the pack (thin packs). |
| 27 | */ |
| 28 | export async function parsePack(pack: Uint8Array, external?: ExternalLookup): Promise<PackedObject[]> { |
| 29 | if (pack.length < 32 || fromUtf8(pack.subarray(0, 4)) !== "PACK") throw new Error("not a packfile"); |
| 30 | const view = new DataView(pack.buffer, pack.byteOffset, pack.byteLength); |
| 31 | const version = view.getUint32(4); |
| 32 | if (version !== 2 && version !== 3) throw new Error(`unsupported pack version ${version}`); |
| 33 | const count = view.getUint32(8); |
| 34 | |
| 35 | const trailer = pack.subarray(pack.length - 20); |
| 36 | const digest = await sha1(pack.subarray(0, pack.length - 20)); |
| 37 | if (!equalBytes(trailer, digest)) throw new Error("pack checksum mismatch"); |
| 38 | |
| 39 | const raws: RawEntry[] = []; |
| 40 | let pos = 12; |
| 41 | for (let n = 0; n < count; n++) { |
| 42 | const offset = pos; |
| 43 | let c = pack[pos++]!; |
| 44 | const typeCode = (c >> 4) & 7; |
| 45 | let size = c & 15; |
| 46 | let shift = 4; |
| 47 | while (c & 0x80) { |
| 48 | c = pack[pos++]!; |
| 49 | size += (c & 0x7f) * 2 ** shift; |
| 50 | shift += 7; |
| 51 | } |
| 52 | const entry: RawEntry = { offset, typeCode, data: new Uint8Array(0) }; |
| 53 | if (typeCode === OFS_DELTA) { |
| 54 | c = pack[pos++]!; |
| 55 | let ofs = c & 0x7f; |
| 56 | while (c & 0x80) { |
| 57 | c = pack[pos++]!; |
| 58 | ofs = (ofs + 1) * 128 + (c & 0x7f); |
| 59 | } |
| 60 | entry.baseOffset = offset - ofs; |
| 61 | } else if (typeCode === REF_DELTA) { |
| 62 | entry.baseOid = toHex(pack.subarray(pos, pos + 20)); |
| 63 | pos += 20; |
| 64 | } else if (!CODE_TYPES[typeCode]) { |
| 65 | throw new Error(`bad object type ${typeCode} at ${offset}`); |
| 66 | } |
| 67 | const { out, consumed } = inflateAt(pack, pos, size); |
| 68 | if (out.length !== size) throw new Error(`size mismatch at ${offset}: ${out.length} != ${size}`); |
| 69 | entry.data = out; |
| 70 | pos += consumed; |
| 71 | raws.push(entry); |
| 72 | } |
| 73 | if (pos !== pack.length - 20) throw new Error("trailing garbage in pack"); |
| 74 | |
| 75 | const byOffset = new Map<number, PackedObject>(); |
| 76 | const byOid = new Map<string, PackedObject>(); |
| 77 | const results: PackedObject[] = []; |
| 78 | const add = async (raw: RawEntry, type: ObjectType, content: Uint8Array) => { |
| 79 | const obj: PackedObject = { oid: await hashObject(type, content), type, content }; |
| 80 | byOffset.set(raw.offset, obj); |
| 81 | byOid.set(obj.oid, obj); |
| 82 | results.push(obj); |
| 83 | }; |
| 84 | |
| 85 | let pending: RawEntry[] = []; |
| 86 | for (const raw of raws) { |
| 87 | const t = CODE_TYPES[raw.typeCode]; |
| 88 | if (t) await add(raw, t, raw.data); |
| 89 | else pending.push(raw); |
| 90 | } |
| 91 | |
| 92 | // Resolve deltas; chains may reference each other in any order. |
| 93 | while (pending.length) { |
| 94 | const next: RawEntry[] = []; |
| 95 | for (const raw of pending) { |
| 96 | let base: GitObject | undefined | null; |
| 97 | if (raw.baseOffset !== undefined) base = byOffset.get(raw.baseOffset); |
| 98 | else base = byOid.get(raw.baseOid!); |
| 99 | if (!base) { |
| 100 | next.push(raw); |
| 101 | continue; |
| 102 | } |
| 103 | await add(raw, base.type, applyDelta(base.content, raw.data)); |
| 104 | } |
| 105 | if (next.length === pending.length) { |
| 106 | // No progress: remaining bases must come from outside the pack. |
| 107 | let progressed = false; |
| 108 | for (const raw of next) { |
| 109 | if (raw.baseOid && external) { |
| 110 | const base = await external(raw.baseOid); |
| 111 | if (base) { |
| 112 | byOid.set(raw.baseOid, { oid: raw.baseOid, ...base }); |
| 113 | progressed = true; |
| 114 | } |
| 115 | } |
| 116 | } |
| 117 | if (!progressed) throw new Error(`unresolvable delta base(s): ${next.map((r) => r.baseOid ?? `@${r.baseOffset}`).join(", ")}`); |
| 118 | } |
| 119 | pending = next.filter((r) => !byOffset.has(r.offset)); |
| 120 | } |
| 121 | return results; |
| 122 | } |
| 123 | |
| 124 | export interface PackEntryInput { |
| 125 | type: ObjectType; |
| 126 | /** Uncompressed size of the object content. */ |
| 127 | size: number; |
| 128 | /** zlib-deflated object content. */ |
| 129 | deflated: Uint8Array; |
| 130 | } |
| 131 | |
| 132 | function writeEntryHeader(w: ByteWriter, typeCode: number, size: number) { |
| 133 | let c = (typeCode << 4) | (size & 15); |
| 134 | size = Math.floor(size / 16); |
| 135 | while (size > 0) { |
| 136 | w.byte(c | 0x80); |
| 137 | c = size & 0x7f; |
| 138 | size = Math.floor(size / 128); |
| 139 | } |
| 140 | w.byte(c); |
| 141 | } |
| 142 | |
| 143 | /** Build a version 2 packfile of undeltified objects from pre-deflated content. */ |
| 144 | export async function writePack(entries: readonly PackEntryInput[]): Promise<Uint8Array> { |
| 145 | const w = new ByteWriter(); |
| 146 | w.write(new TextEncoder().encode("PACK")); |
| 147 | w.uint32(2); |
| 148 | w.uint32(entries.length); |
| 149 | for (const e of entries) { |
| 150 | writeEntryHeader(w, TYPE_CODES[e.type], e.size); |
| 151 | w.write(e.deflated); |
| 152 | } |
| 153 | const body = w.bytes(); |
| 154 | w.write(await sha1(body)); |
| 155 | return w.bytes(); |
| 156 | } |