chadtmiller.com/pds.js

Switch repository

Loading…

/**
 * Packfile merging without object inflation. A pack is a 12-byte header
 * (PACK, version, object count), back-to-back entries, and a 20-byte SHA-1
 * trailer. Entry bytes can be copied verbatim between packs: ref-delta bases
 * are absolute object ids, and ofs-delta bases are backward distances that
 * stay valid as long as each source pack's entry region is kept contiguous
 * and in order. Merging is therefore header surgery: sum the counts,
 * concatenate the entry regions, recompute the trailer.
 *
 * A merged pack must not repeat an object: a clone runs index-pack with
 * --check-self-contained-and-connected, which dies on "the same object
 * appears twice in the pack". git-remote-atproto keeps chained bundles
 * disjoint by excluding every recorded bundle head from each push bundle.
 * A chain written without that rule needs a repack to serve clones.
 */

import { Sha1 } from './sha1.js';

const PACK_MAGIC = 0x5041434b;

/**
 * @param {Uint8Array} pack - complete packfile
 * @returns {{count: number, entries: Uint8Array}} the entry region between
 *   header and trailer
 */
export function splitPack(pack) {
  if (pack.length < 32) throw new Error('pack too short');
  return {
    count: parsePackHeader(pack.subarray(0, 12)),
    entries: pack.subarray(12, pack.length - 20),
  };
}

/**
 * @param {Uint8Array} header - a packfile's first 12 bytes
 * @returns {number} the object count
 */
export function parsePackHeader(header) {
  if (header.length < 12) throw new Error('pack header too short');
  const view = new DataView(header.buffer, header.byteOffset, 12);
  if (view.getUint32(0) !== PACK_MAGIC) throw new Error('bad pack magic');
  const packVersion = view.getUint32(4);
  if (packVersion !== 2 && packVersion !== 3) {
    throw new Error(`unsupported pack version ${packVersion}`);
  }
  return view.getUint32(8);
}

/**
 * @param {number} count - objects the pack holds
 * @returns {Uint8Array} a 12-byte packfile header
 */
function packHeader(count) {
  const header = new Uint8Array(12);
  const view = new DataView(header.buffer);
  view.setUint32(0, PACK_MAGIC);
  view.setUint32(4, 2);
  view.setUint32(8, count);
  return header;
}

/**
 * A valid packfile with zero objects, for fetches that update refs without
 * needing any objects sent.
 * @returns {Uint8Array}
 */
export function emptyPack() {
  const out = new Uint8Array(32);
  out.set(packHeader(0), 0);
  out.set(new Sha1().update(out.subarray(0, 12)).digest(), 12);
  return out;
}

/**
 * Merge complete packfiles into one. Order is preserved; with chained
 * bundles pass them oldest first so delta bases precede their deltas.
 * @param {Uint8Array[]} packs
 * @returns {Uint8Array}
 */
export function mergePacks(packs) {
  if (packs.length === 1) return packs[0];
  if (packs.length === 0) return emptyPack();
  const parts = packs.map(splitPack);
  const header = packHeader(parts.reduce((sum, p) => sum + p.count, 0));
  const total = 12 + parts.reduce((sum, p) => sum + p.entries.length, 0) + 20;
  const out = new Uint8Array(total);
  out.set(header, 0);
  let offset = 12;
  for (const part of parts) {
    out.set(part.entries, offset);
    offset += part.entries.length;
  }
  const sha = new Sha1().update(out.subarray(0, offset)).digest();
  out.set(sha, offset);
  return out;
}

/**
 * A packfile the merge reads in ranges instead of holding.
 * @typedef {Object} PackSource
 * @property {number} count - objects the pack holds
 * @property {number} length - complete packfile length in bytes
 * @property {(start: number, end: number) => AsyncIterable<Uint8Array>} read -
 *   pack bytes in [start, end), in order
 */

/**
 * The bytes mergePacks returns for the same packs, yielded in order and
 * without holding any source whole. Peak memory is one source read. Pass
 * the sources oldest first, as mergePacks wants them.
 * @param {PackSource[]} sources
 * @returns {AsyncGenerator<Uint8Array>}
 */
export async function* mergePackStream(sources) {
  if (sources.length === 0) {
    yield emptyPack();
    return;
  }
  // A single pack is already its own merge, trailer included, so it passes
  // through without a rehash.
  if (sources.length === 1) {
    yield* sources[0].read(0, sources[0].length);
    return;
  }
  const header = packHeader(sources.reduce((sum, s) => sum + s.count, 0));
  const sha = new Sha1().update(header);
  yield header;
  for (const source of sources) {
    for await (const chunk of source.read(12, source.length - 20)) {
      if (chunk.length === 0) continue;
      sha.update(chunk);
      yield chunk;
    }
  }
  yield sha.digest();
}