import { toHex } from "../crypto";
import { inflateZlib } from "./inflate";
import type { GitObjectType } from "./objects";

const PACK_HEADER_BYTES = 12;
const OFS_DELTA = 6;
const REF_DELTA = 7;
const SHA_BYTES = 20;
const OFFSET_BYTES = 4;
const SIZE_BYTES = 3;
const TYPE_NAMES: Record<number, GitObjectType> = { 1: "commit", 2: "tree", 3: "blob", 4: "tag" };
const encoder = new TextEncoder();

export type PackObject = { type: GitObjectType; sha: string; content: Uint8Array };

/** A delta whose base lives outside the pack (thin pack); only its inserted literals are known. */
export type UnresolvedDelta = { baseSha: string; inserted: Uint8Array[]; delta: Uint8Array };

export type PackLimits = { maxObjects: number; maxObjectBytes: number; maxTotalBytes: number };

export type ParsedPack = { objects: PackObject[]; unresolved: UnresolvedDelta[]; truncated: boolean };

type Raw = { offset: number; type: number; data: Uint8Array; baseOffset?: number; baseSha?: string };

async function objectSha(type: GitObjectType, content: Uint8Array): Promise<string> {
  const header = encoder.encode(`${type} ${content.byteLength}\0`);
  const bytes = new Uint8Array(header.byteLength + content.byteLength);
  bytes.set(header);
  bytes.set(content, header.byteLength);
  return toHex(await crypto.subtle.digest("SHA-1", bytes));
}

function readVarint(data: Uint8Array, start: number): { value: number; next: number } {
  let value = 0;
  let shift = 0;
  let position = start;
  let byte: number;
  do {
    byte = data[position++];
    value += (byte & 0x7f) * 2 ** shift;
    shift += 7;
  } while (byte & 0x80);
  return { value, next: position };
}

/** Applies a git delta; returns null when instructions are malformed. */
export function applyDelta(base: Uint8Array, delta: Uint8Array, maxBytes: number): Uint8Array | null {
  const source = readVarint(delta, 0);
  if (source.value !== base.byteLength) return null;
  const target = readVarint(delta, source.next);
  if (target.value > maxBytes) return null;
  const out = new Uint8Array(target.value);
  let position = target.next;
  let written = 0;
  while (position < delta.byteLength) {
    const op = delta[position++];
    if (op & 0x80) {
      let copyOffset = 0;
      let copySize = 0;
      for (let bit = 0; bit < OFFSET_BYTES; bit++)
        if (op & (1 << bit)) copyOffset += delta[position++] * 2 ** (8 * bit);
      for (let bit = 0; bit < SIZE_BYTES; bit++)
        if (op & (1 << (OFFSET_BYTES + bit))) copySize += delta[position++] << (8 * bit);
      if (copySize === 0) copySize = 0x10000;
      if (copyOffset + copySize > base.byteLength || written + copySize > out.byteLength) return null;
      out.set(base.subarray(copyOffset, copyOffset + copySize), written);
      written += copySize;
    } else if (op > 0) {
      if (written + op > out.byteLength || position + op > delta.byteLength) return null;
      out.set(delta.subarray(position, position + op), written);
      written += op;
      position += op;
    } else {
      return null;
    }
  }
  return written === out.byteLength ? out : null;
}

/** Extracts the literal insert runs from a delta, which carry all newly introduced bytes. */
export function deltaInserts(delta: Uint8Array): Uint8Array[] {
  const inserts: Uint8Array[] = [];
  let position = readVarint(delta, readVarint(delta, 0).next).next;
  while (position < delta.byteLength) {
    const op = delta[position++];
    if (op & 0x80) {
      for (let bit = 0; bit < OFFSET_BYTES + SIZE_BYTES; bit++) if (op & (1 << bit)) position++;
    } else if (op > 0) {
      inserts.push(delta.subarray(position, position + op));
      position += op;
    } else {
      break;
    }
  }
  return inserts;
}

function readEntries(pack: Uint8Array, limits: PackLimits): { raws: Raw[]; truncated: boolean } {
  const view = new DataView(pack.buffer, pack.byteOffset, pack.byteLength);
  if (pack.byteLength < PACK_HEADER_BYTES || String.fromCharCode(...pack.subarray(0, 4)) !== "PACK") {
    throw new Error("Not a packfile");
  }
  const count = view.getUint32(8);
  const raws: Raw[] = [];
  let position = PACK_HEADER_BYTES;
  let total = 0;
  for (let index = 0; index < count; index++) {
    if (raws.length >= limits.maxObjects || position >= pack.byteLength) return { raws, truncated: true };
    const offset = position;
    let byte = pack[position++];
    const type = (byte >> 4) & 0x07;
    while (byte & 0x80) byte = pack[position++];
    let baseOffset: number | undefined;
    let baseSha: string | undefined;
    if (type === OFS_DELTA) {
      byte = pack[position++];
      let distance = byte & 0x7f;
      while (byte & 0x80) {
        byte = pack[position++];
        distance = (distance + 1) * 128 + (byte & 0x7f);
      }
      baseOffset = offset - distance;
    } else if (type === REF_DELTA) {
      baseSha = toHex(pack.subarray(position, position + SHA_BYTES));
      position += SHA_BYTES;
    }
    let inflated: { data: Uint8Array; next: number };
    try {
      inflated = inflateZlib(pack, position, limits.maxObjectBytes);
    } catch {
      return { raws, truncated: true };
    }
    total += inflated.data.byteLength;
    if (total > limits.maxTotalBytes) return { raws, truncated: true };
    raws.push({ offset, type, data: inflated.data, baseOffset, baseSha });
    position = inflated.next;
  }
  return { raws, truncated: false };
}

/** Parses a version 2 packfile within the given budgets, resolving deltas whose bases are in the pack. */
export async function parsePack(pack: Uint8Array, limits: PackLimits): Promise<ParsedPack> {
  const { raws, truncated } = readEntries(pack, limits);
  const byOffset = new Map<number, { type: GitObjectType; content: Uint8Array }>();
  const bySha = new Map<string, { type: GitObjectType; content: Uint8Array }>();
  const objects: PackObject[] = [];
  const unresolved: UnresolvedDelta[] = [];
  let pending = raws;
  while (pending.length > 0) {
    const next: Raw[] = [];
    for (const raw of pending) {
      const named = TYPE_NAMES[raw.type];
      let resolved: { type: GitObjectType; content: Uint8Array } | null = null;
      if (named) resolved = { type: named, content: raw.data };
      else {
        const base =
          raw.baseOffset !== undefined ? byOffset.get(raw.baseOffset) : raw.baseSha ? bySha.get(raw.baseSha) : null;
        if (!base) {
          next.push(raw);
          continue;
        }
        const content = applyDelta(base.content, raw.data, limits.maxObjectBytes);
        if (content) resolved = { type: base.type, content };
      }
      if (!resolved) continue;
      const sha = await objectSha(resolved.type, resolved.content);
      byOffset.set(raw.offset, resolved);
      bySha.set(sha, resolved);
      objects.push({ sha, ...resolved });
    }
    if (next.length === pending.length) {
      for (const raw of next)
        unresolved.push({ baseSha: raw.baseSha ?? "", inserted: deltaInserts(raw.data), delta: raw.data });
      break;
    }
    pending = next;
  }
  return { objects, unresolved, truncated };
}