| 1 | import { ByteWriter, equalBytes, fromUtf8, toHex } from "./bytes.js"; |
| 2 | import { applyDelta, deltaResultSize } 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 | /** A delta entry waiting for its base: its instructions (inflated), freed once applied. */ |
| 32 | interface DeltaEntry { |
| 33 | offset: number; |
| 34 | data: Uint8Array; |
| 35 | } |
| 36 | |
| 37 | /** |
| 38 | * A REF_DELTA base from the repository (a thin pack's), or null when it has no such object. Given |
| 39 | * what the unpack may still hold, it checks what reading the object would take before reading it, |
| 40 | * and returns that number of bytes instead when it is more, so a small delta against a huge stored |
| 41 | * object is refused before the object is inflated. |
| 42 | */ |
| 43 | export type ExternalLookup = (oid: string, maxBytes: number) => Promise<GitObject | number | null>; |
| 44 | |
| 45 | /** What unpacking refuses when the pack inflates to more than `maxBytes` in all. */ |
| 46 | export function tooBigUnpacked(maxBytes: number): Error { |
| 47 | const mib = maxBytes / (1024 * 1024); |
| 48 | return new Error(`pack unpacks to more than ${Number.isInteger(mib) ? `${mib} MiB` : `${maxBytes} bytes`}; split it into smaller pushes`); |
| 49 | } |
| 50 | |
| 51 | /** Unpacking would hold more than it may. */ |
| 52 | export class TooMuchMemory extends Error {} |
| 53 | |
| 54 | /** What unpacking refuses when it would hold more than `maxHeld` bytes. */ |
| 55 | export function tooMuchMemory(maxHeld: number): TooMuchMemory { |
| 56 | return new TooMuchMemory(`pack needs more than ${Math.floor(maxHeld / (1024 * 1024))} MiB of memory to unpack; split it into smaller pushes`); |
| 57 | } |
| 58 | |
| 59 | /** What a pack may unpack to by default (object contents and delta instructions together). */ |
| 60 | export const MAX_UNPACKED_BYTES = 512 * 1024 * 1024; |
| 61 | |
| 62 | /** |
| 63 | * What unpacking a pack may hold in memory by default: the contents it returns (large blobs kept |
| 64 | * compressed aside), delta instructions until they are applied, a base while its deltas are applied, |
| 65 | * and OBJECT_OVERHEAD for each object. A repository's Durable Object has 128 MB, the pack included. |
| 66 | */ |
| 67 | export const MAX_HELD_BYTES = 80 * 1024 * 1024; |
| 68 | |
| 69 | /** |
| 70 | * Roughly what one object costs to hold beyond its content: the object and its oid, the Uint8Array |
| 71 | * and its buffer, and its entries in the indexes below. Measured at about 740 bytes in Node for |
| 72 | * 100,000 three-byte blobs. |
| 73 | */ |
| 74 | const OBJECT_OVERHEAD = 768; |
| 75 | |
| 76 | const EMPTY = new Uint8Array(0); |
| 77 | |
| 78 | /** |
| 79 | * Parse a packfile and fully resolve every object (including deltas). |
| 80 | * `external` resolves REF_DELTA bases that are not inside the pack (thin packs). |
| 81 | * Packs come from clients, so unpacking is bounded: each object stops inflating at its |
| 82 | * declared size, the whole pack may unpack to at most `maxBytes`, and what it holds in memory |
| 83 | * may come to at most `maxHeldBytes`. Deltas are resolved in one pass from their bases. |
| 84 | */ |
| 85 | export async function parsePack( |
| 86 | pack: Uint8Array, |
| 87 | external?: ExternalLookup, |
| 88 | opts: { maxBytes?: number; largeObjectBytes?: number; maxHeldBytes?: number } = {}, |
| 89 | ): Promise<PackedObject[]> { |
| 90 | if (pack.length < 32 || fromUtf8(pack.subarray(0, 4)) !== "PACK") throw new Error("not a packfile"); |
| 91 | const view = new DataView(pack.buffer, pack.byteOffset, pack.byteLength); |
| 92 | const version = view.getUint32(4); |
| 93 | if (version !== 2 && version !== 3) throw new Error(`unsupported pack version ${version}`); |
| 94 | const count = view.getUint32(8); |
| 95 | |
| 96 | const trailer = pack.subarray(pack.length - 20); |
| 97 | let digest: Uint8Array; |
| 98 | if (pack.length > SLICED_CHECKSUM_BYTES) { |
| 99 | const h = new Sha1(); |
| 100 | for (let i = 0; i < pack.length - 20; i += 1024 * 1024) h.update(pack.subarray(i, Math.min(i + 1024 * 1024, pack.length - 20))); |
| 101 | digest = h.digest(); |
| 102 | } else digest = await sha1(pack.subarray(0, pack.length - 20)); |
| 103 | if (!equalBytes(trailer, digest)) throw new Error("pack checksum mismatch"); |
| 104 | |
| 105 | const maxBytes = opts.maxBytes ?? MAX_UNPACKED_BYTES; |
| 106 | const maxHeld = opts.maxHeldBytes ?? MAX_HELD_BYTES; |
| 107 | const large = opts.largeObjectBytes ?? Infinity; |
| 108 | let unpacked = 0; |
| 109 | let held = 0; |
| 110 | const work = (n: number) => { |
| 111 | if (unpacked + n > maxBytes) throw tooBigUnpacked(maxBytes); |
| 112 | unpacked += n; |
| 113 | }; |
| 114 | const hold = (n: number) => { |
| 115 | if (held + n > maxHeld) throw tooMuchMemory(maxHeld); |
| 116 | held += n; |
| 117 | }; |
| 118 | |
| 119 | const results: PackedObject[] = []; |
| 120 | /** Each result's offset in the pack, to find the OFS_DELTAs against it. */ |
| 121 | const offsets: number[] = []; |
| 122 | const childrenByOffset = new Map<number, DeltaEntry[]>(); |
| 123 | const childrenByOid = new Map<string, DeltaEntry[]>(); |
| 124 | const waitFor = <K>(m: Map<K, DeltaEntry[]>, k: K, d: DeltaEntry) => { |
| 125 | const list = m.get(k); |
| 126 | if (list) list.push(d); |
| 127 | else m.set(k, [d]); |
| 128 | }; |
| 129 | const add = (offset: number, obj: PackedObject) => { |
| 130 | results.push(obj); |
| 131 | offsets.push(offset); |
| 132 | }; |
| 133 | |
| 134 | let pos = 12; |
| 135 | for (let n = 0; n < count; n++) { |
| 136 | const offset = pos; |
| 137 | let c = pack[pos++]!; |
| 138 | const typeCode = (c >> 4) & 7; |
| 139 | let size = c & 15; |
| 140 | let shift = 4; |
| 141 | while (c & 0x80) { |
| 142 | c = pack[pos++]!; |
| 143 | size += (c & 0x7f) * 2 ** shift; |
| 144 | shift += 7; |
| 145 | } |
| 146 | let baseOffset: number | undefined; |
| 147 | let baseOid: string | undefined; |
| 148 | if (typeCode === OFS_DELTA) { |
| 149 | c = pack[pos++]!; |
| 150 | let ofs = c & 0x7f; |
| 151 | while (c & 0x80) { |
| 152 | c = pack[pos++]!; |
| 153 | ofs = (ofs + 1) * 128 + (c & 0x7f); |
| 154 | } |
| 155 | baseOffset = offset - ofs; |
| 156 | } else if (typeCode === REF_DELTA) { |
| 157 | baseOid = toHex(pack.subarray(pos, pos + 20)); |
| 158 | pos += 20; |
| 159 | } else if (!CODE_TYPES[typeCode]) { |
| 160 | throw new Error(`bad object type ${typeCode} at ${offset}`); |
| 161 | } |
| 162 | if (typeCode === TYPE_CODES.blob && size >= large) { |
| 163 | // Hash it as it inflates and keep only the compressed bytes, so memory never holds it whole. |
| 164 | work(size); |
| 165 | hold(OBJECT_OVERHEAD); |
| 166 | const h = new Sha1().update(objectHeader("blob", size)); |
| 167 | const { consumed, produced } = inflateEach(pack, pos, (chunk) => h.update(chunk), size); |
| 168 | if (produced !== size) throw new Error(`size mismatch at ${offset}: ${produced} != ${size}`); |
| 169 | add(offset, largeBlob(toHex(h.digest()), size, pack.subarray(pos, pos + consumed))); |
| 170 | pos += consumed; |
| 171 | continue; |
| 172 | } |
| 173 | // Reserved at the declared size before inflating, so a declared size the budget can't hold is refused up front. |
| 174 | work(size); |
| 175 | hold(size + OBJECT_OVERHEAD); |
| 176 | const { out, consumed } = inflateAt(pack, pos, size); |
| 177 | if (out.length !== size) throw new Error(`size mismatch at ${offset}: ${out.length} != ${size}`); |
| 178 | pos += consumed; |
| 179 | if (baseOffset !== undefined) waitFor(childrenByOffset, baseOffset, { offset, data: out }); |
| 180 | else if (baseOid !== undefined) waitFor(childrenByOid, baseOid, { offset, data: out }); |
| 181 | else { |
| 182 | const type = CODE_TYPES[typeCode]!; |
| 183 | add(offset, { oid: await hashObject(type, out), type, content: out }); |
| 184 | } |
| 185 | } |
| 186 | if (pos !== pack.length - 20) throw new Error("trailing garbage in pack"); |
| 187 | |
| 188 | /** Applies every delta waiting for `base` (in the pack at `offset`, or -1 when it came from the repository). */ |
| 189 | const resolveDeltasOf = async (base: GitObject & { oid: string; deflated?: Uint8Array; size?: number }, offset: number) => { |
| 190 | const byOffset = offset >= 0 ? childrenByOffset.get(offset) : undefined; |
| 191 | const byOid = childrenByOid.get(base.oid); |
| 192 | if (!byOffset && !byOid) return; |
| 193 | if (byOffset) childrenByOffset.delete(offset); |
| 194 | if (byOid) childrenByOid.delete(base.oid); |
| 195 | // A large blob kept compressed is inflated once for all its deltas, and held while they are applied. |
| 196 | const inflated = base.deflated ? (base.size ?? 0) : 0; |
| 197 | if (inflated) { |
| 198 | work(inflated); |
| 199 | hold(inflated); |
| 200 | } |
| 201 | const content = base.content; |
| 202 | for (const d of [...(byOffset ?? []), ...(byOid ?? [])]) { |
| 203 | // A result the pack's limit allows but memory can't hold is refused as memory, before it is allocated. |
| 204 | const size = deltaResultSize(d.data); |
| 205 | if (size > maxBytes - unpacked) throw tooBigUnpacked(maxBytes); |
| 206 | if (size > maxHeld - held + d.data.length) throw tooMuchMemory(maxHeld); |
| 207 | const result = applyDelta(content, d.data, Math.min(maxBytes - unpacked, maxHeld - held + d.data.length)); |
| 208 | work(result.length); |
| 209 | held -= d.data.length; |
| 210 | hold(result.length); |
| 211 | d.data = EMPTY; |
| 212 | add(d.offset, { oid: await hashObject(base.type, result), type: base.type, content: result }); |
| 213 | } |
| 214 | held -= inflated; |
| 215 | }; |
| 216 | // Each object, as it is added, has its deltas applied: one pass, whatever order the pack lists them in. |
| 217 | let next = 0; |
| 218 | const drain = async () => { |
| 219 | for (; next < results.length; next++) await resolveDeltasOf(results[next]!, offsets[next]!); |
| 220 | }; |
| 221 | await drain(); |
| 222 | // REF_DELTA bases that aren't in the pack (thin packs) come from the repository, each read once. |
| 223 | if (external) { |
| 224 | for (const oid of [...childrenByOid.keys()]) { |
| 225 | if (!childrenByOid.has(oid)) continue; |
| 226 | const base = await external(oid, maxHeld - held); |
| 227 | if (base === null) continue; |
| 228 | if (typeof base === "number") throw tooMuchMemory(maxHeld); |
| 229 | work(base.content.length); |
| 230 | hold(base.content.length); |
| 231 | await resolveDeltasOf({ oid, ...base }, -1); |
| 232 | held -= base.content.length; |
| 233 | await drain(); |
| 234 | } |
| 235 | } |
| 236 | const unresolved = [...childrenByOid.keys(), ...[...childrenByOffset.keys()].map((o) => `@${o}`)]; |
| 237 | if (unresolved.length) throw new Error(`unresolvable delta base(s): ${unresolved.join(", ")}`); |
| 238 | return results; |
| 239 | } |
| 240 | |
| 241 | export interface PackEntryInput { |
| 242 | type: ObjectType; |
| 243 | /** Uncompressed size of the object content. */ |
| 244 | size: number; |
| 245 | /** zlib-deflated object content. */ |
| 246 | deflated: Uint8Array; |
| 247 | } |
| 248 | |
| 249 | function writeEntryHeader(w: ByteWriter, typeCode: number, size: number) { |
| 250 | let c = (typeCode << 4) | (size & 15); |
| 251 | size = Math.floor(size / 16); |
| 252 | while (size > 0) { |
| 253 | w.byte(c | 0x80); |
| 254 | c = size & 0x7f; |
| 255 | size = Math.floor(size / 128); |
| 256 | } |
| 257 | w.byte(c); |
| 258 | } |
| 259 | |
| 260 | /** |
| 261 | * The same packfile as `writePack`, produced piece by piece as `entries` yields them, so a clone of a |
| 262 | * large repository never holds the whole pack: only the entry being written. |
| 263 | */ |
| 264 | export async function* packStream(count: number, entries: AsyncIterable<PackEntryInput>): AsyncGenerator<Uint8Array> { |
| 265 | const hash = new Sha1(); |
| 266 | const head = new ByteWriter(); |
| 267 | head.write(new TextEncoder().encode("PACK")); |
| 268 | head.uint32(2); |
| 269 | head.uint32(count); |
| 270 | let written = 0; |
| 271 | const out = (b: Uint8Array) => (hash.update(b), b); |
| 272 | yield out(head.bytes()); |
| 273 | for await (const e of entries) { |
| 274 | if (++written > count) throw new Error(`pack has more than the ${count} objects it announced`); |
| 275 | const h = new ByteWriter(); |
| 276 | writeEntryHeader(h, TYPE_CODES[e.type], e.size); |
| 277 | yield out(h.bytes()); |
| 278 | yield out(e.deflated); |
| 279 | } |
| 280 | if (written !== count) throw new Error(`pack announced ${count} objects but has ${written}`); |
| 281 | yield hash.digest(); |
| 282 | } |
| 283 | |
| 284 | /** Build a version 2 packfile of undeltified objects from pre-deflated content. */ |
| 285 | export async function writePack(entries: readonly PackEntryInput[]): Promise<Uint8Array> { |
| 286 | const w = new ByteWriter(); |
| 287 | w.write(new TextEncoder().encode("PACK")); |
| 288 | w.uint32(2); |
| 289 | w.uint32(entries.length); |
| 290 | for (const e of entries) { |
| 291 | writeEntryHeader(w, TYPE_CODES[e.type], e.size); |
| 292 | w.write(e.deflated); |
| 293 | } |
| 294 | const body = w.bytes(); |
| 295 | w.write(await sha1(body)); |
| 296 | return w.bytes(); |
| 297 | } |