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