char/sorcery

git clone https://git.t4t.associates/char/sorcery

Charlotte Somexperiment: support sha-256 oids in git repos42f80d82026-09-04

import { inflate, oidBytes, toHex } from "./codec.ts";
import type { Fetcher, GitRepo } from "./repo.ts";
import type { GitObject, ObjectType } from "./types.ts";

/** pack entry types (`OBJ_*` in git) */
const TYPES: Record<number, ObjectType> = { 1: "commit", 2: "tree", 3: "blob", 4: "tag" };
const OFS_DELTA = 6;
const REF_DELTA = 7;

export interface PackIndex {
  lookup(oid: string): Promise<number | null>;
  entryEnd(offset: number): number | null;
}

const PACK_INDEX_HEADER_BYTES = 8 + 256 * 4;

interface PackIndexHeader {
  count: number;
  fanout: number[];
}

function parseIndexHeader(buf: Uint8Array): PackIndexHeader {
  const view = new DataView(buf.buffer, buf.byteOffset, buf.byteLength);
  if (buf.length < PACK_INDEX_HEADER_BYTES || view.getUint32(0) !== 0xff744f63 || view.getUint32(4) !== 2) {
    throw new Error("unsupported pack index format");
  }
  const fanout = Array.from({ length: 256 }, (_, i) => view.getUint32(8 + i * 4));
  return { count: fanout[255], fanout };
}

/** Eager path for small version-2 indexes. */
export function parseIndex(buf: Uint8Array, hashBytes: number): PackIndex {
  const { count, fanout } = parseIndexHeader(buf);
  const view = new DataView(buf.buffer, buf.byteOffset, buf.byteLength);
  const names = PACK_INDEX_HEADER_BYTES;
  const offsets = names + count * hashBytes + count * 4; // skip crc table
  const largeOffsets = offsets + count * 4;

  const oidAt = (i: number) => buf.subarray(names + i * hashBytes, names + (i + 1) * hashBytes);
  const offsetAt = (i: number): number => {
    const raw = view.getUint32(offsets + i * 4);
    if (raw & 0x80000000) {
      return Number(view.getBigUint64(largeOffsets + (raw & 0x7fffffff) * 8));
    }
    return raw;
  };

  const sortedOffsets = Array.from({ length: count }, (_, i) => offsetAt(i)).sort((a, b) => a - b);

  return {
    async lookup(oid: string): Promise<number | null> {
      const target = oidBytes(oid);
      if (target.length !== hashBytes) throw new Error(`object id ${oid} has the wrong hash format`);
      let lo = target[0] === 0 ? 0 : fanout[target[0] - 1];
      let hi = fanout[target[0]];
      while (lo < hi) {
        const mid = (lo + hi) >> 1;
        const cmp = compare(oidAt(mid), target);
        if (cmp === 0) return offsetAt(mid);
        if (cmp < 0) lo = mid + 1;
        else hi = mid;
      }
      return null;
    },
    entryEnd(offset: number): number | null {
      const i = sortedOffsets.findIndex(candidate => candidate > offset);
      return i === -1 ? null : sortedOffsets[i];
    },
  };
}

export function compare(a: Uint8Array, b: Uint8Array): number {
  for (let i = 0; i < a.length; i++) {
    if (a[i] !== b[i]) return a[i] - b[i];
  }
  return 0;
}

export interface PackEntry {
  type: number;
  /** inflated payload: object content, or delta instructions */
  data: Uint8Array;
  /** for OFS_DELTA: absolute offset of the base entry */
  baseOffset?: number;
  /** for REF_DELTA: oid of the base object */
  baseOid?: string;
}

export interface PackEntryHeader {
  type: number;
  size: number;
  bytes: number;
  baseOffset?: number;
  baseOid?: string;
}

export function parseEntryHeader(slice: Uint8Array, hashBytes: number, entryOffset = 0): PackEntryHeader {
  let pos = 0;
  let byte = slice[pos++];
  const type = (byte >> 4) & 7;
  let size = byte & 0x0f;
  let shift = 4;
  while (byte & 0x80) {
    if (pos >= slice.length) throw new Error("truncated pack entry header");
    byte = slice[pos++];
    size += (byte & 0x7f) * 2 ** shift;
    shift += 7;
  }

  let baseOffset: number | undefined;
  let baseOid: string | undefined;
  if (type === OFS_DELTA) {
    byte = slice[pos++];
    let relative = byte & 0x7f;
    while (byte & 0x80) {
      byte = slice[pos++];
      relative = ((relative + 1) << 7) | (byte & 0x7f);
    }
    baseOffset = entryOffset - relative;
  } else if (type === REF_DELTA) {
    baseOid = toHex(slice.subarray(pos, pos + hashBytes));
    pos += hashBytes;
  }

  return { type, size, bytes: pos, baseOffset, baseOid };
}

/** decode one entry from an exact pack slice starting at its header */
export async function parseEntry(slice: Uint8Array, hashBytes: number, entryOffset: number): Promise<PackEntry> {
  const header = parseEntryHeader(slice, hashBytes, entryOffset);
  return {
    type: header.type,
    data: await inflate(slice.subarray(header.bytes)),
    baseOffset: header.baseOffset,
    baseOid: header.baseOid,
  };
}

export function entryType(type: number): ObjectType {
  const known = TYPES[type];
  if (!known) throw new Error(`unexpected pack entry type ${type}`);
  return known;
}

export function isDelta(type: number): boolean {
  return type === OFS_DELTA || type === REF_DELTA;
}

export function deltaResultSize(delta: Uint8Array): number {
  let pos = 0;
  const varint = () => {
    let value = 0;
    let shift = 0;
    let byte;
    do {
      byte = delta[pos++];
      value += (byte & 0x7f) * 2 ** shift;
      shift += 7;
    } while (byte & 0x80);
    return value;
  };
  varint();
  return varint();
}

/** apply copy/insert delta instructions to a base object */
export function applyDelta(base: Uint8Array, delta: Uint8Array): Uint8Array {
  let pos = 0;
  const varint = () => {
    let value = 0;
    let shift = 0;
    let byte;
    do {
      byte = delta[pos++];
      value |= (byte & 0x7f) << shift;
      shift += 7;
    } while (byte & 0x80);
    return value >>> 0;
  };

  const srcSize = varint();
  if (srcSize !== base.length) throw new Error("delta base size mismatch");
  const dstSize = varint();
  const out = new Uint8Array(dstSize);
  let outPos = 0;

  while (pos < delta.length) {
    const op = delta[pos++];
    if (op & 0x80) {
      // copy from base: bitmask selects which offset/size bytes follow
      let offset = 0;
      let size = 0;
      for (let i = 0; i < 4; i++) if (op & (1 << i)) offset |= delta[pos++] << (i * 8);
      for (let i = 0; i < 3; i++) if (op & (0x10 << i)) size |= delta[pos++] << (i * 8);
      if (size === 0) size = 0x10000;
      out.set(base.subarray(offset, offset + size), outPos);
      outPos += size;
    } else if (op !== 0) {
      out.set(delta.subarray(pos, pos + op), outPos);
      pos += op;
      outPos += op;
    } else {
      throw new Error("invalid delta opcode 0");
    }
  }
  if (outPos !== dstSize) throw new Error("delta output size mismatch");
  return out;
}

export class Pack {
  #index?: Promise<PackIndex>;
  readonly #hashBytes: number;

  constructor(
    readonly fetch: Fetcher,
    readonly stem: string,
  ) {
    const hash = stem.match(/^pack-([0-9a-f]{40}|[0-9a-f]{64})$/)?.[1];
    if (!hash) throw new Error(`invalid pack name ${stem}`);
    this.#hashBytes = hash.length / 2;
  }

  index(): Promise<PackIndex> {
    if (this.#index) return this.#index;
    this.#index = this.fetch(`.git/objects/pack/${this.stem}.idx`).then(result => {
      if (!result) throw new Error(`missing pack index ${this.stem}`);
      return parseIndex(result.bytes, this.#hashBytes);
    });
    this.#index.catch(() => (this.#index = undefined));
    return this.#index;
  }

  /** read + resolve (possibly delta-chained) object content at an offset */
  async readAt(offset: number, repo: GitRepo): Promise<GitObject> {
    const entry = await this.#readPackedEntry(offset);
    if (!isDelta(entry.type)) {
      return { type: entryType(entry.type), data: entry.data };
    }
    const base = entry.baseOffset !== undefined
      ? await this.readAt(entry.baseOffset, repo)
      : await repo.object(entry.baseOid!);
    return { type: base.type, data: applyDelta(base.data, entry.data) };
  }

  async #readPackedEntry(offset: number): Promise<PackEntry> {
    const index = await this.index();
    const path = `.git/objects/pack/${this.stem}.pack`;
    const end = index.entryEnd(offset);
    const res = await this.fetch(path, [offset, end]);
    if (!res) throw new Error(`missing pack ${this.stem}`);
    let bytes = res.bytes;
    if (end === null) bytes = bytes.subarray(0, res.total - this.#hashBytes - offset);
    return parseEntry(bytes, this.#hashBytes, offset);
  }
}