sailfork / t3code-github / .repos/ alchemy-effect/ packages/ git/ src/ Protocol/ PartialScan.ts

/**
 * Scans pack entries out of a BUFFER that starts at an entry boundary and
 * may end mid-entry (DESIGN §22.7): the unit of work a hashing Worker
 * receives from the receive-pack pipeline — one spilled part plus the
 * carry-over of the previous part's incomplete tail.
 *
 * Everything that can be settled inside the buffer is settled here:
 * non-delta entries are inflated and hashed (the expensive part of
 * ingest), OFS/REF deltas whose base is in the same buffer are applied,
 * re-deflated and hashed. Deltas whose base lies outside the buffer are
 * reported as `unresolved` with what the caller needs to settle them
 * later. The scan stops at the first entry that does not fit; `consumedTo`
 * is the absolute offset where it starts, so the caller can carry the tail.
 * An entry only counts as fitting when the buffer extends at least one byte
 * past it, so the buffer must always end with what FOLLOWS the last entry
 * to consume (the next part's bytes, or the pack trailer).
 *
 * Pure: no store, no I/O. The trailer is NOT verified here (the caller
 * hashes the whole pack as it streams).
 */
import * as Effect from "effect/Effect";
import * as Result from "effect/Result";
import * as Schema from "effect/Schema";
import { applyDelta } from "./Delta.ts";
import {
  bytesToHex,
  decodeOfsDeltaOffset,
  decodeTypeSize,
  hashObjectSync,
  ObjectParseError,
  type ObjectType,
  type Oid,
} from "./ObjectCodec.ts";
import { ObjectTooLargeError, PackFormatError } from "./PackParser.ts";
import {
  deflate,
  inflate,
  inflateEntrySync,
  inflateExactSpan,
  type InflatedEntry,
} from "./Zlib.ts";

export interface ScannedEntry {
  readonly oid: Oid;
  readonly type: ObjectType;
  /** Absolute pack offset of the entry HEADER (what OFS_DELTAs point at). */
  readonly offset: number;
  /** Uncompressed size. */
  readonly size: number;
  /** Absolute pack offset of the entry's zdata (its header precedes it). */
  readonly dataOffset: number;
  /** Compressed span at `dataOffset` — verbatim for non-delta entries. */
  readonly span: number;
  /** Set for delta-resolved entries: a fresh deflate to store as the row. */
  readonly zdata?: Uint8Array | undefined;
  /** Inflated content for commits, trees and tags (the store parses them). */
  readonly content?: Uint8Array | undefined;
  /**
   * For a delta-resolved entry, its base reference — so a hasher that must
   * bound its response can demote the entry back to `unresolved`.
   */
  readonly baseOffset?: number | undefined;
  readonly baseOid?: Oid | undefined;
}

export interface UnresolvedDelta {
  /** Absolute pack offset of the entry header. */
  readonly offset: number;
  /** Absolute offset of the delta payload's zdata and its span. */
  readonly dataOffset: number;
  readonly span: number;
  /** The base: an absolute pack offset (OFS_DELTA) or an oid (REF_DELTA). */
  readonly baseOffset?: number | undefined;
  readonly baseOid?: Oid | undefined;
  /** Declared (uncompressed) size of the delta payload. */
  readonly size: number;
}

export interface ScanResult {
  /** Absolute offset of the first entry scanned (after resync), or -1 if none. */
  readonly firstOffset: number;
  readonly entries: ReadonlyArray<ScannedEntry>;
  readonly unresolved: ReadonlyArray<UnresolvedDelta>;
  /** Absolute offset of the first entry NOT consumed (carry from here). */
  readonly consumedTo: number;
  /** Entries consumed (resolved + unresolved). */
  readonly count: number;
}

const isDelta = (type: number) => type === 6 || type === 7;

/**
 * Scans `buf`, whose byte 0 is at absolute pack offset `base`. `remaining`
 * is how many entries the pack still owes (so a trailing partial entry
 * beyond the count is not mistaken for data); `maxObjectSize` bounds
 * inflated sizes.
 */
export const scanPart = (
  buf: Uint8Array,
  options: {
    readonly base: number;
    readonly remaining: number;
    readonly maxObjectSize: number;
    /** Resolved content LRU budget for in-buffer delta bases. */
    readonly cacheBytes?: number | undefined;
    /**
     * `buf` does NOT necessarily start at an entry boundary (a raw chunk of
     * a pack, DESIGN §22.9): find the first boundary with {@link findBoundary}
     * and scan from there. No boundary within the chunk ⇒ no entries.
     */
    readonly resync?: boolean | undefined;
  },
): Effect.Effect<ScanResult, PackFormatError | ObjectTooLargeError> =>
  Effect.gen(function* () {
    const entries: Array<ScannedEntry> = [];
    const unresolved: Array<UnresolvedDelta> = [];
    let firstOffset = -1;
    let startAt = 0;
    if (options.resync === true) {
      const found = findBoundary(buf, { maxObjectSize: options.maxObjectSize });
      if (found === undefined) {
        return {
          firstOffset: -1,
          entries,
          unresolved,
          consumedTo: options.base,
          count: 0,
        };
      }
      startAt = found;
      firstOffset = options.base + found;
    }
    // In resync mode `remaining` is only an upper bound and the buffer may
    // run into the pack trailer: anything that does not parse as an entry
    // ends the scan instead of failing it (the pipeline validates the count,
    // the trailer hash and every object id downstream).
    const lenient = options.resync === true;
    // Content of resolved entries in this buffer, by absolute offset and by
    // oid, for in-buffer delta bases. Bounded; a miss becomes unresolved.
    const byOffset = new Map<number, { type: ObjectType; content: Uint8Array }>();
    const byOid = new Map<string, { type: ObjectType; content: Uint8Array }>();
    let cached = 0;
    const budget = options.cacheBytes ?? 20 * 1024 * 1024;
    const remember = (offset: number, oid: Oid, type: ObjectType, content: Uint8Array) => {
      if (content.length > budget / 4) return;
      while (cached + content.length > budget && byOffset.size > 0) {
        const oldest = byOffset.keys().next().value!;
        const dropped = byOffset.get(oldest)!;
        byOffset.delete(oldest);
        cached -= dropped.content.length;
      }
      byOffset.set(offset, { type, content });
      byOid.set(oid, { type, content });
      cached += content.length;
    };

    let pos = startAt;
    let count = 0;
    while (count < options.remaining && pos < buf.length) {
      const offset = options.base + pos;
      const headerResult = yield* Effect.result(
        Effect.try({
          try: () => decodeTypeSize(buf, pos),
          catch: (error) =>
            PackFormatError.make({
              reason: Schema.is(ObjectParseError)(error)
                ? `entry at ${offset}: ${error.reason}`
                : `entry at ${offset}: ${String(error)}`,
            }),
        }),
      );
      if (Result.isFailure(headerResult)) {
        // A header cut by the buffer edge: stop here, carry the tail.
        if (lenient || buf.length - pos < 16) break;
        return yield* headerResult.failure;
      }
      const header = headerResult.success;
      if (header.size > options.maxObjectSize) {
        if (lenient) break;
        return yield* ObjectTooLargeError.make({
          size: header.size,
          limit: options.maxObjectSize,
        });
      }
      let at = header.next;
      let baseOffset: number | undefined;
      let baseOid: Oid | undefined;
      if (header.type === 6) {
        const ofsResult = yield* Effect.result(
          Effect.try({
            try: () => decodeOfsDeltaOffset(buf, at),
            catch: () => PackFormatError.make({ reason: `entry at ${offset}: bad ofs-delta` }),
          }),
        );
        if (Result.isFailure(ofsResult)) {
          if (lenient || buf.length - at < 16) break;
          return yield* ofsResult.failure;
        }
        const ofs = ofsResult.success;
        at = ofs.next;
        baseOffset = offset - ofs.value;
      } else if (header.type === 7) {
        if (at + 20 > buf.length) break;
        baseOid = bytesToHex(buf.subarray(at, at + 20)) as Oid;
        at += 20;
      }
      const inflated: InflatedEntry | undefined = inflateEntrySync(buf, at, {
        maxOutput: options.maxObjectSize,
        expectedSize: header.size,
      });
      if (inflated === undefined) {
        // The compressed stream runs past the buffer (or is corrupt — the
        // next attempt, with more bytes, decides): carry from this entry.
        break;
      }
      const { bytesConsumed, content: payload } = inflated;
      // A stream cut inside its last bytes (end-of-block bits, adler32) can
      // inflate to exactly the declared size without having ended, and the
      // consumed count would then be short. An entry is complete only when
      // the buffer extends PAST it: callers always append what follows
      // (the next part, or the pack trailer for the last one).
      if (at + bytesConsumed >= buf.length) break;
      if (payload.length !== header.size) {
        if (lenient) break;
        return yield* PackFormatError.make({
          reason: `entry at ${offset}: inflated ${payload.length} bytes, header declared ${header.size}`,
        });
      }
      const dataOffset = options.base + at;
      if (!isDelta(header.type)) {
        const type = header.type as ObjectType;
        const oid = hashObjectSync(type, payload);
        entries.push({
          oid,
          type,
          offset,
          size: payload.length,
          dataOffset,
          span: bytesConsumed,
          content: type === 3 ? undefined : payload,
        });
        remember(offset, oid, type, payload);
      } else {
        const found = baseOffset !== undefined ? byOffset.get(baseOffset) : byOid.get(baseOid!);
        if (found === undefined) {
          unresolved.push({
            offset,
            dataOffset,
            span: bytesConsumed,
            baseOffset,
            baseOid,
            size: header.size,
          });
        } else {
          const content = yield* applyDelta(found.content, payload).pipe(
            Effect.mapError((error) =>
              PackFormatError.make({
                reason: `entry at ${offset}: ${error.reason}`,
              }),
            ),
          );
          if (content.length > options.maxObjectSize) {
            return yield* ObjectTooLargeError.make({
              size: content.length,
              limit: options.maxObjectSize,
            });
          }
          const oid = hashObjectSync(found.type, content);
          const zdata = yield* deflate(content).pipe(
            Effect.mapError((error) => PackFormatError.make({ reason: error.reason })),
          );
          entries.push({
            oid,
            type: found.type,
            offset,
            size: content.length,
            dataOffset,
            span: bytesConsumed,
            zdata,
            content: found.type === 3 ? undefined : content,
            baseOffset,
            baseOid,
          });
          remember(offset, oid, found.type, content);
        }
      }
      pos = at + bytesConsumed;
      count += 1;
    }
    return {
      firstOffset: firstOffset >= 0 ? firstOffset : entries.length > 0 ? options.base : -1,
      entries,
      unresolved,
      consumedTo: options.base + pos,
      count,
    };
  });

/** One entry's coordinates from a boundary-only scan (DESIGN §22.8). */
export interface EntryBounds {
  /** Absolute pack offset of the entry header. */
  readonly offset: number;
  /** 1–4 for full objects, 6/7 for OFS/REF deltas. */
  readonly type: number;
  /** Declared (uncompressed) size. */
  readonly size: number;
  /** Absolute offset and length of the compressed span. */
  readonly dataOffset: number;
  readonly span: number;
  readonly baseOffset?: number | undefined;
  readonly baseOid?: Oid | undefined;
}

export interface BoundsResult {
  readonly entries: ReadonlyArray<EntryBounds>;
  /** Absolute offset of the first entry NOT consumed (carry from here). */
  readonly consumedTo: number;
}

/**
 * Boundary-only scan (DESIGN §22.8): finds every entry's compressed span in
 * `buf` without hashing or resolving anything — the one inherently
 * sequential step of pack ingest (a stream's end is only known by inflating
 * it). With spans known, hashing every part can run in parallel and can
 * inflate exact slices with the cheap one-shot path. Same contract as
 * {@link scanPart}: `buf` starts at an entry boundary and must extend past
 * the last entry to consume.
 */
export const scanBounds = (
  buf: Uint8Array,
  options: {
    readonly base: number;
    readonly remaining: number;
    readonly maxObjectSize: number;
  },
): Effect.Effect<BoundsResult, PackFormatError | ObjectTooLargeError> =>
  Effect.gen(function* () {
    const entries: Array<EntryBounds> = [];
    let pos = 0;
    let count = 0;
    while (count < options.remaining && pos < buf.length) {
      const offset = options.base + pos;
      const headerResult = yield* Effect.result(
        Effect.try({
          try: () => decodeTypeSize(buf, pos),
          catch: (error) =>
            PackFormatError.make({
              reason: Schema.is(ObjectParseError)(error)
                ? `entry at ${offset}: ${error.reason}`
                : `entry at ${offset}: ${String(error)}`,
            }),
        }),
      );
      if (Result.isFailure(headerResult)) {
        if (buf.length - pos < 16) break;
        return yield* headerResult.failure;
      }
      const header = headerResult.success;
      if (header.size > options.maxObjectSize) {
        return yield* ObjectTooLargeError.make({
          size: header.size,
          limit: options.maxObjectSize,
        });
      }
      let at = header.next;
      let baseOffset: number | undefined;
      let baseOid: Oid | undefined;
      if (header.type === 6) {
        const ofsResult = yield* Effect.result(
          Effect.try({
            try: () => decodeOfsDeltaOffset(buf, at),
            catch: () => PackFormatError.make({ reason: `entry at ${offset}: bad ofs-delta` }),
          }),
        );
        if (Result.isFailure(ofsResult)) {
          if (buf.length - at < 16) break;
          return yield* ofsResult.failure;
        }
        const ofs = ofsResult.success;
        at = ofs.next;
        baseOffset = offset - ofs.value;
      } else if (header.type === 7) {
        if (at + 20 > buf.length) break;
        baseOid = bytesToHex(buf.subarray(at, at + 20)) as Oid;
        at += 20;
      }
      const inflated = inflateEntrySync(buf, at, {
        maxOutput: options.maxObjectSize,
        expectedSize: header.size,
      });
      if (inflated === undefined) break;
      if (at + inflated.bytesConsumed >= buf.length) break;
      if (inflated.content.length !== header.size) {
        return yield* PackFormatError.make({
          reason: `entry at ${offset}: inflated ${inflated.content.length} bytes, header declared ${header.size}`,
        });
      }
      entries.push({
        offset,
        type: header.type,
        size: header.size,
        dataOffset: options.base + at,
        span: inflated.bytesConsumed,
        baseOffset,
        baseOid,
      });
      pos = at + inflated.bytesConsumed;
      count += 1;
    }
    return { entries, consumedTo: options.base + pos };
  });

/**
 * Hashes entries whose spans are already known (DESIGN §22.8): the parallel
 * half. `bounds` addresses spans inside `buf` (absolute offsets; `base` is
 * `buf[0]`'s offset). Non-delta entries are inflated with the one-shot
 * path and hashed; deltas whose base is among these entries (or already
 * resolved here) are applied, re-deflated and hashed; the rest are reported
 * unresolved.
 */
export const hashBounds = (
  buf: Uint8Array,
  bounds: ReadonlyArray<EntryBounds>,
  options: {
    readonly base: number;
    readonly maxObjectSize: number;
    readonly cacheBytes?: number | undefined;
  },
): Effect.Effect<ScanResult, PackFormatError | ObjectTooLargeError> =>
  Effect.gen(function* () {
    const entries: Array<ScannedEntry> = [];
    const unresolved: Array<UnresolvedDelta> = [];
    const byOffset = new Map<number, { type: ObjectType; content: Uint8Array }>();
    const byOid = new Map<string, { type: ObjectType; content: Uint8Array }>();
    const inflateExact = (b: EntryBounds) =>
      inflateExactSpan(
        buf.subarray(b.dataOffset - options.base, b.dataOffset - options.base + b.span),
        b.size,
      ).pipe(
        Effect.mapError((error) =>
          PackFormatError.make({
            reason: `entry at ${b.offset}: ${error.reason}`,
          }),
        ),
      );
    for (const b of bounds) {
      const payload = yield* inflateExact(b);
      if (!isDelta(b.type)) {
        const type = b.type as ObjectType;
        const oid = hashObjectSync(type, payload);
        entries.push({
          oid,
          type,
          offset: b.offset,
          size: payload.length,
          dataOffset: b.dataOffset,
          span: b.span,
          content: type === 3 ? undefined : payload,
        });
        byOffset.set(b.offset, { type, content: payload });
        byOid.set(oid, { type, content: payload });
        continue;
      }
      const found = b.baseOffset !== undefined ? byOffset.get(b.baseOffset) : byOid.get(b.baseOid!);
      if (found === undefined) {
        unresolved.push({
          offset: b.offset,
          dataOffset: b.dataOffset,
          span: b.span,
          baseOffset: b.baseOffset,
          baseOid: b.baseOid,
          size: b.size,
        });
        continue;
      }
      const content = yield* applyDelta(found.content, payload).pipe(
        Effect.mapError((error) =>
          PackFormatError.make({
            reason: `entry at ${b.offset}: ${error.reason}`,
          }),
        ),
      );
      if (content.length > options.maxObjectSize) {
        return yield* ObjectTooLargeError.make({
          size: content.length,
          limit: options.maxObjectSize,
        });
      }
      const oid = hashObjectSync(found.type, content);
      const zdata = yield* deflate(content).pipe(
        Effect.mapError((error) => PackFormatError.make({ reason: error.reason })),
      );
      entries.push({
        oid,
        type: found.type,
        offset: b.offset,
        size: content.length,
        dataOffset: b.dataOffset,
        span: b.span,
        zdata,
        content: found.type === 3 ? undefined : content,
      });
      byOffset.set(b.offset, { type: found.type, content });
      byOid.set(oid, { type: found.type, content });
    }
    const last = bounds[bounds.length - 1];
    return {
      firstOffset: bounds[0]?.offset ?? -1,
      entries,
      unresolved,
      consumedTo: last === undefined ? options.base : last.dataOffset + last.span,
      count: bounds.length,
    };
  });

/**
 * Finds the first entry boundary inside `buf` (DESIGN §22.9): the parallel
 * answer to "where does an entry start?", so chunks of a pack can be scanned
 * independently. A position is a boundary when it decodes as an entry
 * header, its stream inflates to exactly the declared size, AND the entry
 * that follows does too — two consecutive coincidences on arbitrary bytes
 * are not a realistic false positive, and the pack trailer plus per-object
 * hashing verify everything downstream regardless.
 *
 * Candidates are filtered cheaply: a deflate stream from git starts with
 * the zlib header `0x78` followed by one of four FLG bytes, right after a
 * 1–10 byte varint header. Returns the offset into `buf`, or `undefined`
 * when no boundary lies within `maxSearch` bytes — the whole chunk by
 * default: a part whose head is inside one large entry still has its own
 * entries to hash, and a part that reports no boundary is hashed serially
 * as a region by the caller (a 10 MB blob spanning three parts once cost
 * a whole part's worth of serial hashing under a 1 MiB limit).
 */
export const findBoundary = (
  buf: Uint8Array,
  options: {
    readonly maxObjectSize: number;
    readonly maxSearch?: number | undefined;
  },
): number | undefined => {
  const limit = Math.min(buf.length, options.maxSearch ?? buf.length);
  const isZlibHeader = (i: number) =>
    i + 1 < buf.length &&
    buf[i] === 0x78 &&
    (buf[i + 1] === 0x01 || buf[i + 1] === 0x5e || buf[i + 1] === 0x9c || buf[i + 1] === 0xda);
  const parses = (pos: number): number | undefined => {
    let header;
    try {
      header = decodeTypeSize(buf, pos);
    } catch {
      return undefined;
    }
    if (header.type < 1 || header.type > 7) return undefined;
    if (header.size > options.maxObjectSize) return undefined;
    let at = header.next;
    if (header.type === 6) {
      try {
        at = decodeOfsDeltaOffset(buf, at).next;
      } catch {
        return undefined;
      }
    } else if (header.type === 7) {
      at += 20;
    }
    if (!isZlibHeader(at)) return undefined;
    const inflated = inflateEntrySync(buf, at, {
      maxOutput: options.maxObjectSize,
      expectedSize: header.size,
    });
    if (inflated === undefined || inflated.content.length !== header.size) return undefined;
    const end = at + inflated.bytesConsumed;
    return end >= buf.length ? undefined : end;
  };
  for (let pos = 0; pos < limit; pos++) {
    // Cheap pre-filter: a zlib header must appear within the next 32 bytes
    // (header varint + optional base ref).
    let plausible = false;
    for (let k = pos + 1; k <= pos + 32 && k < buf.length; k++) {
      if (isZlibHeader(k)) {
        plausible = true;
        break;
      }
    }
    if (!plausible) continue;
    const next = parses(pos);
    if (next === undefined) continue;
    // Second entry must parse too (or the buffer ends right after — accept
    // only if the first entry ended cleanly inside the buffer).
    const after = parses(next);
    if (after !== undefined) return pos;
  }
  return undefined;
};

// ── delta resolution as a job (DESIGN §22.13) ──────────────────────────────

/** One base a batch of delta jobs refers to: zlib bytes, or already-inflated content. */
export interface DeltaBase {
  readonly bytes: Uint8Array;
  readonly isContent: boolean;
}

/** One delta to apply: its base (by index into the batch's bases) and its zlib bytes. */
export interface DeltaJob {
  readonly id: number;
  readonly type: ObjectType;
  readonly base: number;
  readonly delta: Uint8Array;
}

/** A resolved delta: the object's oid and a fresh deflate; content for non-blobs. */
export interface DeltaResolved {
  readonly id: number;
  readonly oid: Oid;
  readonly size: number;
  readonly zdata: Uint8Array;
  readonly content?: Uint8Array | undefined;
}

/**
 * Applies a batch of deltas whose bases the caller supplies — the work the
 * receiver would otherwise do itself for every delta whose base lies in
 * another chunk. Pure over its inputs, so a hasher isolate can run it.
 */
export const resolveDeltas = (
  bases: ReadonlyArray<DeltaBase>,
  jobs: ReadonlyArray<DeltaJob>,
  options: { readonly maxObjectSize: number },
): Effect.Effect<Array<DeltaResolved>, PackFormatError | ObjectTooLargeError> =>
  Effect.gen(function* () {
    const inflated = new Map<number, Uint8Array>();
    const baseContent = (index: number) =>
      Effect.gen(function* () {
        const cached = inflated.get(index);
        if (cached !== undefined) return cached;
        const base = bases[index];
        if (base === undefined) {
          return yield* PackFormatError.make({
            reason: `delta base ${index} missing`,
          });
        }
        const content = base.isContent
          ? base.bytes
          : yield* inflate(base.bytes).pipe(
              Effect.mapError((error) => PackFormatError.make({ reason: error.reason })),
            );
        inflated.set(index, content);
        return content;
      });
    const out: Array<DeltaResolved> = [];
    for (const job of jobs) {
      const base = yield* baseContent(job.base);
      const delta = yield* inflate(job.delta).pipe(
        Effect.mapError((error) => PackFormatError.make({ reason: error.reason })),
      );
      const content = yield* applyDelta(base, delta).pipe(
        Effect.mapError((error) => PackFormatError.make({ reason: error.reason })),
      );
      if (content.length > options.maxObjectSize) {
        return yield* ObjectTooLargeError.make({
          size: content.length,
          limit: options.maxObjectSize,
        });
      }
      const oid = hashObjectSync(job.type, content);
      const zdata = yield* deflate(content).pipe(
        Effect.mapError((error) => PackFormatError.make({ reason: error.reason })),
      );
      out.push({
        id: job.id,
        oid,
        size: content.length,
        zdata,
        content: job.type === 3 ? undefined : content,
      });
    }
    return out;
  });