| 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, 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 | /** What a pack may unpack to by default (object contents and delta instructions together). */ |
| 25 | export const MAX_UNPACKED_BYTES = 512 * 1024 * 1024; |
| 26 | |
| 27 | /** |
| 28 | * Parse a packfile and fully resolve every object (including deltas). |
| 29 | * `external` resolves REF_DELTA bases that are not inside the pack (thin packs). |
| 30 | * Packs come from clients, so unpacking is bounded: each object stops inflating at its |
| 31 | * declared size, and the whole pack may unpack to at most `maxBytes`. |
| 32 | */ |
| 33 | export async function parsePack(pack: Uint8Array, external?: ExternalLookup, opts: { maxBytes?: number } = {}): Promise<PackedObject[]> { |
| 34 | if (pack.length < 32 || fromUtf8(pack.subarray(0, 4)) !== "PACK") throw new Error("not a packfile"); |
| 35 | const view = new DataView(pack.buffer, pack.byteOffset, pack.byteLength); |
| 36 | const version = view.getUint32(4); |
| 37 | if (version !== 2 && version !== 3) throw new Error(`unsupported pack version ${version}`); |
| 38 | const count = view.getUint32(8); |
| 39 | |
| 40 | const trailer = pack.subarray(pack.length - 20); |
| 41 | const digest = await sha1(pack.subarray(0, pack.length - 20)); |
| 42 | if (!equalBytes(trailer, digest)) throw new Error("pack checksum mismatch"); |
| 43 | |
| 44 | const maxBytes = opts.maxBytes ?? MAX_UNPACKED_BYTES; |
| 45 | let unpacked = 0; |
| 46 | const tooBig = () => new Error(`pack unpacks to more than ${maxBytes} bytes`); |
| 47 | |
| 48 | const raws: RawEntry[] = []; |
| 49 | let pos = 12; |
| 50 | for (let n = 0; n < count; n++) { |
| 51 | const offset = pos; |
| 52 | let c = pack[pos++]!; |
| 53 | const typeCode = (c >> 4) & 7; |
| 54 | let size = c & 15; |
| 55 | let shift = 4; |
| 56 | while (c & 0x80) { |
| 57 | c = pack[pos++]!; |
| 58 | size += (c & 0x7f) * 2 ** shift; |
| 59 | shift += 7; |
| 60 | } |
| 61 | const entry: RawEntry = { offset, typeCode, data: new Uint8Array(0) }; |
| 62 | if (typeCode === OFS_DELTA) { |
| 63 | c = pack[pos++]!; |
| 64 | let ofs = c & 0x7f; |
| 65 | while (c & 0x80) { |
| 66 | c = pack[pos++]!; |
| 67 | ofs = (ofs + 1) * 128 + (c & 0x7f); |
| 68 | } |
| 69 | entry.baseOffset = offset - ofs; |
| 70 | } else if (typeCode === REF_DELTA) { |
| 71 | entry.baseOid = toHex(pack.subarray(pos, pos + 20)); |
| 72 | pos += 20; |
| 73 | } else if (!CODE_TYPES[typeCode]) { |
| 74 | throw new Error(`bad object type ${typeCode} at ${offset}`); |
| 75 | } |
| 76 | if (unpacked + size > maxBytes) throw tooBig(); |
| 77 | const { out, consumed } = inflateAt(pack, pos, size); |
| 78 | if (out.length !== size) throw new Error(`size mismatch at ${offset}: ${out.length} != ${size}`); |
| 79 | unpacked += size; |
| 80 | entry.data = out; |
| 81 | pos += consumed; |
| 82 | raws.push(entry); |
| 83 | } |
| 84 | if (pos !== pack.length - 20) throw new Error("trailing garbage in pack"); |
| 85 | |
| 86 | const byOffset = new Map<number, PackedObject>(); |
| 87 | const byOid = new Map<string, PackedObject>(); |
| 88 | const results: PackedObject[] = []; |
| 89 | const add = async (raw: RawEntry, type: ObjectType, content: Uint8Array) => { |
| 90 | const obj: PackedObject = { oid: await hashObject(type, content), type, content }; |
| 91 | byOffset.set(raw.offset, obj); |
| 92 | byOid.set(obj.oid, obj); |
| 93 | results.push(obj); |
| 94 | }; |
| 95 | |
| 96 | let pending: RawEntry[] = []; |
| 97 | for (const raw of raws) { |
| 98 | const t = CODE_TYPES[raw.typeCode]; |
| 99 | if (t) await add(raw, t, raw.data); |
| 100 | else pending.push(raw); |
| 101 | } |
| 102 | |
| 103 | // Resolve deltas; chains may reference each other in any order. |
| 104 | while (pending.length) { |
| 105 | const next: RawEntry[] = []; |
| 106 | for (const raw of pending) { |
| 107 | let base: GitObject | undefined | null; |
| 108 | if (raw.baseOffset !== undefined) base = byOffset.get(raw.baseOffset); |
| 109 | else base = byOid.get(raw.baseOid!); |
| 110 | if (!base) { |
| 111 | next.push(raw); |
| 112 | continue; |
| 113 | } |
| 114 | const content = applyDelta(base.content, raw.data, maxBytes - unpacked); |
| 115 | unpacked += content.length; |
| 116 | await add(raw, base.type, content); |
| 117 | } |
| 118 | if (next.length === pending.length) { |
| 119 | // No progress: remaining bases must come from outside the pack. |
| 120 | let progressed = false; |
| 121 | for (const raw of next) { |
| 122 | if (raw.baseOid && external) { |
| 123 | const base = await external(raw.baseOid); |
| 124 | if (base) { |
| 125 | byOid.set(raw.baseOid, { oid: raw.baseOid, ...base }); |
| 126 | progressed = true; |
| 127 | } |
| 128 | } |
| 129 | } |
| 130 | if (!progressed) throw new Error(`unresolvable delta base(s): ${next.map((r) => r.baseOid ?? `@${r.baseOffset}`).join(", ")}`); |
| 131 | } |
| 132 | pending = next.filter((r) => !byOffset.has(r.offset)); |
| 133 | } |
| 134 | return results; |
| 135 | } |
| 136 | |
| 137 | export interface PackEntryInput { |
| 138 | type: ObjectType; |
| 139 | /** Uncompressed size of the object content. */ |
| 140 | size: number; |
| 141 | /** zlib-deflated object content. */ |
| 142 | deflated: Uint8Array; |
| 143 | } |
| 144 | |
| 145 | function writeEntryHeader(w: ByteWriter, typeCode: number, size: number) { |
| 146 | let c = (typeCode << 4) | (size & 15); |
| 147 | size = Math.floor(size / 16); |
| 148 | while (size > 0) { |
| 149 | w.byte(c | 0x80); |
| 150 | c = size & 0x7f; |
| 151 | size = Math.floor(size / 128); |
| 152 | } |
| 153 | w.byte(c); |
| 154 | } |
| 155 | |
| 156 | /** |
| 157 | * The same packfile as `writePack`, produced piece by piece as `entries` yields them, so a clone of a |
| 158 | * large repository never holds the whole pack: only the entry being written. |
| 159 | */ |
| 160 | export async function* packStream(count: number, entries: AsyncIterable<PackEntryInput>): AsyncGenerator<Uint8Array> { |
| 161 | const hash = new Sha1(); |
| 162 | const head = new ByteWriter(); |
| 163 | head.write(new TextEncoder().encode("PACK")); |
| 164 | head.uint32(2); |
| 165 | head.uint32(count); |
| 166 | let written = 0; |
| 167 | const out = (b: Uint8Array) => (hash.update(b), b); |
| 168 | yield out(head.bytes()); |
| 169 | for await (const e of entries) { |
| 170 | if (++written > count) throw new Error(`pack has more than the ${count} objects it announced`); |
| 171 | const h = new ByteWriter(); |
| 172 | writeEntryHeader(h, TYPE_CODES[e.type], e.size); |
| 173 | yield out(h.bytes()); |
| 174 | yield out(e.deflated); |
| 175 | } |
| 176 | if (written !== count) throw new Error(`pack announced ${count} objects but has ${written}`); |
| 177 | yield hash.digest(); |
| 178 | } |
| 179 | |
| 180 | /** Build a version 2 packfile of undeltified objects from pre-deflated content. */ |
| 181 | export async function writePack(entries: readonly PackEntryInput[]): Promise<Uint8Array> { |
| 182 | const w = new ByteWriter(); |
| 183 | w.write(new TextEncoder().encode("PACK")); |
| 184 | w.uint32(2); |
| 185 | w.uint32(entries.length); |
| 186 | for (const e of entries) { |
| 187 | writeEntryHeader(w, TYPE_CODES[e.type], e.size); |
| 188 | w.write(e.deflated); |
| 189 | } |
| 190 | const body = w.bytes(); |
| 191 | w.write(await sha1(body)); |
| 192 | return w.bytes(); |
| 193 | } |