chadtmiller.com/pds.js

Switch repository

Loading…

/**
 * A bundle's object index: one fixed-width row per pack entry, giving its
 * id, byte extent, resolved type and size, and its delta base. A reader
 * holding the index can fetch single objects from the bundle with ranged
 * blob reads instead of downloading the chain.
 *
 * The index is derived data in the sense git's own pack .idx is: the
 * builder walks the pack and anyone can rebuild it from the bundle bytes.
 * It carries two fields a git .idx does not, the resolved size and type per
 * entry, so a tree listing needs no blob reads at all.
 */

import { parseBundle } from './bundle.js';
import { indexPacks } from './objects.js';

/** The mime the index blob is uploaded under. */
export const PACK_INDEX_MIME = 'application/vnd.pdsjs.git-pack-index';

const MAGIC = [0x50, 0x47, 0x49, 0x58]; // "PGIX"
const VERSION = 1;
const HEADER_BYTES = 16;
const ROW_BYTES = 33; // sha(20) + offset(4) + size(4) + base(4) + type(1)

/** `base` sentinel: the entry is not a delta. */
export const BASE_NONE = 0;
/**
 * `base` sentinel: the entry is a ref-delta whose base is outside this
 * pack. The reader learns the base id from the entry bytes themselves.
 */
export const BASE_EXTERNAL = 1;

/** @type {Record<string, number>} */
const TYPE_CODES = { commit: 1, tree: 2, blob: 3, tag: 4 };
/** @type {Record<number, string>} */
const TYPE_NAMES = { 1: 'commit', 2: 'tree', 3: 'blob', 4: 'tag' };

/**
 * @typedef {Object} PackIndexEntry
 * @property {string} sha
 * @property {number} offset - entry start, relative to the pack's first byte
 * @property {number} size - materialized object size in bytes
 * @property {number} base - offset of the delta base entry, or a BASE_
 *   sentinel
 * @property {string} type - resolved object type
 */

/**
 * @typedef {Object} PackIndex
 * @property {number} packStart - where the pack begins inside the bundle
 * @property {PackIndexEntry[]} entries - in entry order, offsets ascending
 */

/**
 * Walk a bundle's pack and produce its index.
 * @param {Uint8Array} bundleBytes - a complete bundle file
 * @param {(sha: string) => Promise<import('./objects.js').GitObject|null>} [resolveBase] -
 *   supplies a delta base outside this bundle. An incremental bundle may
 *   delta against its prerequisites, so the builder needs the repository
 *   those came from.
 * @returns {Promise<PackIndex>}
 */
export async function buildBundleIndex(bundleBytes, resolveBase) {
  const { pack } = parseBundle(bundleBytes);
  const packStart = bundleBytes.length - pack.length;
  /** @type {PackIndexEntry[]} */
  const entries = [];
  /** @type {Map<string, number>} */
  const offsetBySha = new Map();
  /**
   * @param {string} sha
   * @param {import('./objects.js').PackEntryMeta} meta
   */
  const collect = (sha, meta) => {
    let base = BASE_NONE;
    if (meta.baseOffset !== null) {
      base = meta.baseOffset;
    } else if (meta.baseSha !== null) {
      // A ref-delta against this same pack names an entry already walked;
      // any other base is external.
      base = offsetBySha.get(meta.baseSha) ?? BASE_EXTERNAL;
    }
    offsetBySha.set(sha, meta.offset);
    entries.push({
      sha,
      offset: meta.offset,
      size: meta.size,
      base,
      type: meta.type,
    });
  };
  // The index is the whole product here, so no object outlives its use as a
  // delta base.
  await indexPacks([pack], collect, resolveBase, { retain: 'none' });
  entries.sort((a, b) => a.offset - b.offset);
  return { packStart, entries };
}

/**
 * @param {PackIndex} index
 * @returns {Uint8Array}
 */
export function encodePackIndex(index) {
  const bytes = new Uint8Array(HEADER_BYTES + index.entries.length * ROW_BYTES);
  const view = new DataView(bytes.buffer);
  bytes.set(MAGIC, 0);
  bytes[4] = VERSION;
  view.setUint32(8, index.packStart, true);
  view.setUint32(12, index.entries.length, true);
  let pos = HEADER_BYTES;
  const MAX_U32 = 0xffffffff;
  for (const entry of index.entries) {
    if (!/^[0-9a-f]{40}$/.test(entry.sha)) {
      throw new Error(`pack index entry has a malformed sha: ${entry.sha}`);
    }
    // The v1 rows hold u32 fields, which caps the bundle at 4 GiB. A caller
    // whose bundle overflows gets an error rather than a wrapped offset.
    if (
      entry.offset > MAX_U32 ||
      entry.size > MAX_U32 ||
      entry.base > MAX_U32
    ) {
      throw new Error('pack index v1 cannot address past 4 GiB');
    }
    for (let i = 0; i < 20; i++) {
      bytes[pos + i] = Number.parseInt(entry.sha.slice(i * 2, i * 2 + 2), 16);
    }
    view.setUint32(pos + 20, entry.offset, true);
    view.setUint32(pos + 24, entry.size, true);
    view.setUint32(pos + 28, entry.base, true);
    const type = TYPE_CODES[entry.type];
    if (!type)
      throw new Error(`pack index entry has unknown type ${entry.type}`);
    bytes[pos + 32] = type;
    pos += ROW_BYTES;
  }
  return bytes;
}

/**
 * @param {Uint8Array} bytes
 * @returns {PackIndex}
 */
export function decodePackIndex(bytes) {
  if (bytes.length < HEADER_BYTES || !MAGIC.every((b, i) => bytes[i] === b)) {
    throw new Error('not a pack index');
  }
  if (bytes[4] !== VERSION) {
    throw new Error(`unsupported pack index version ${bytes[4]}`);
  }
  const view = new DataView(bytes.buffer, bytes.byteOffset, bytes.byteLength);
  const packStart = view.getUint32(8, true);
  const count = view.getUint32(12, true);
  if (bytes.length < HEADER_BYTES + count * ROW_BYTES) {
    throw new Error('pack index is truncated');
  }
  /** @type {PackIndexEntry[]} */
  const entries = [];
  let pos = HEADER_BYTES;
  for (let i = 0; i < count; i++) {
    let sha = '';
    for (let j = 0; j < 20; j++) {
      sha += bytes[pos + j].toString(16).padStart(2, '0');
    }
    const type = TYPE_NAMES[bytes[pos + 32]];
    if (!type) {
      throw new Error(`pack index entry has unknown type ${bytes[pos + 32]}`);
    }
    entries.push({
      sha,
      offset: view.getUint32(pos + 20, true),
      size: view.getUint32(pos + 24, true),
      base: view.getUint32(pos + 28, true),
      type,
    });
    pos += ROW_BYTES;
  }
  return { packStart, entries };
}