// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie <jeff@ocjtech.us>
// SPDX-License-Identifier: MIT

//! Packs: many objects in one `.pack` file, most of them stored as deltas,
//! found through the pack index beside it (gitformat-pack(5)).
//!
//! A pack begins with `PACK`, a version (git reads 2 and 3, which are the
//! same format, and writes 2) and an object count, and ends with the hash
//! of everything before it. Each entry between has a header giving its
//! type and its inflated size, seven bits a byte after the first's four;
//! an OFS_DELTA follows it with the distance back to its base in the
//! pack's offset encoding, and a REF_DELTA with its base's object ID. Then
//! comes the zlib stream of the object, or of the delta.
//!
//! Reading an object resolves its delta chain without recursion, from the
//! object back to a base stored whole, then applies the deltas forward.
//! A REF_DELTA's base is looked for in the same pack first and then, if
//! the pack has a `Bases` to ask, anywhere else in the object database:
//! another pack, a loose object or an alternate, as a thin pack completed
//! by `git index-pack --fix-thin` would need. A chain of more than
//! `max_delta_depth` deltas, counted across packs, is an error, so one
//! that loops is caught rather than followed forever.
//!
//! - **Headers** (`readHeader`) walk the chain reading only entry headers
//!   to find the base's kind, and inflate only the first bytes of the
//!   outermost delta, where its result size is: no delta is applied.
//! - **Whole objects** (`read`) are checked as git checks them: every
//!   stream must inflate to exactly its entry's size.
//! - **Streaming** (`stream`) is bounded in memory for an object stored
//!   whole. A deltified object cannot be: its base must be in memory to
//!   copy from, so it is built whole and then written.
//!
//! **A size limit**, `Pack.max_object_size`, refuses with `ObjectTooLarge`
//! any object or delta whose size claim is over it, before anything of
//! that size is allocated: a whole entry's size, the result size each
//! delta of a chain declares, and each delta's own size, which may be up
//! to eight times the limit since a copy instruction of eight bytes may
//! make only one. Only what is built
//! in memory is limited; `readHeader` reports any size, and `stream`
//! writes an object stored whole however big it is.
//!
//! Every resolution starts afresh: there is no cache of delta bases, so
//! reading many objects of a deep chain repeats work. A `Pack` is not
//! changed by reading it, so concurrent readers may share one.
//!
//! The functions here take the pack's bytes, typically memory-mapped, and
//! do no I/O of their own; only a `Bases` lookup may.

const std = @import("std");
const Allocator = std.mem.Allocator;
const Io = std.Io;

const object = @import("object.zig");
const Format = object.Format;
const Id = object.Id;
const Kind = object.Kind;
const Diagnostics = @import("Diagnostics.zig");
const ObjectDatabase = @import("ObjectDatabase.zig");
const Object = ObjectDatabase.Object;
const ReadError = ObjectDatabase.ReadError;
const StreamError = ObjectDatabase.StreamError;
const PackIndex = @import("PackIndex.zig");
const delta = @import("delta.zig");
const zlib = @import("zlib.zig");

/// The most deltas a chain may have between an object and the base stored
/// whole, counting those in other packs. git writes no chain deeper than
/// 4095 (`git pack-objects --depth`), so this leaves room to spare while
/// stopping a chain that loops.
pub const max_delta_depth = 10_000;

/// The most times resolving one object may go to another pack, or a loose
/// object, for a REF_DELTA's base. Each such step is a nested lookup, so
/// this bounds how deep they go; a pack completed by `git index-pack
/// --fix-thin` holds its own bases and needs none.
pub const max_base_hops = 64;

/// How far into resolving a delta chain a read already is: how many
/// deltas have been followed, and how many of those steps went outside a
/// pack for a base.
pub const Depth = struct {
    links: u32 = 0,
    hops: u32 = 0,
};

/// What a pack entry is: one of the four kinds stored whole, or a delta.
/// The values are the type numbers gitformat-pack(5) gives them.
pub const EntryType = enum(u3) {
    commit = 1,
    tree = 2,
    blob = 3,
    tag = 4,
    ofs_delta = 6,
    ref_delta = 7,

    /// The kind of an object stored whole, or null for a delta.
    pub fn kind(t: EntryType) ?Kind {
        return switch (t) {
            .commit => .commit,
            .tree => .tree,
            .blob => .blob,
            .tag => .tag,
            .ofs_delta, .ref_delta => null,
        };
    }
};

/// A pack entry's header, and what follows it up to the zlib stream.
pub const EntryHeader = struct {
    type: EntryType,
    /// The size of what the zlib stream inflates to: the object, or the
    /// delta.
    size: u64,
    /// Where a delta's base is.
    base: Base,
    /// Where the zlib stream starts, from the start of the pack.
    data_offset: u64,

    /// Where a delta's base is: nowhere for an object stored whole, an
    /// offset in the same pack for an OFS_DELTA, an object ID for a
    /// REF_DELTA.
    pub const Base = union(enum) {
        none,
        offset: u64,
        id: Id,
    };
};

/// Why an entry's header could not be read: see `ObjectDatabase.PackError`.
pub const EntryError = error{ TruncatedPackEntry, BadPackEntryType, PackEntrySizeOverflow, BadDeltaBaseOffset };

/// Reads the header of the entry at `offset` in `data`, which is the pack
/// without its checksum: nothing an entry needs may come from there.
pub fn parseEntryHeader(format: Format, data: []const u8, offset: u64) EntryError!EntryHeader {
    if (offset >= data.len) return error.TruncatedPackEntry;
    var at: usize = @intCast(offset);
    const first = data[at];
    at += 1;
    const type_number: u3 = @truncate(first >> 4);
    const entry_type: EntryType = switch (type_number) {
        1, 2, 3, 4, 6, 7 => @fromBackingInt(@intCast(type_number)),
        else => return error.BadPackEntryType,
    };
    var size: u64 = first & 0x0f;
    var shift: u7 = 4;
    var more = first & 0x80 != 0;
    while (more) {
        if (at >= data.len) return error.TruncatedPackEntry;
        const b = data[at];
        at += 1;
        const part: u64 = b & 0x7f;
        if (part != 0 and (shift >= 64 or part > @as(u64, std.math.maxInt(u64)) >> @intCast(shift)))
            return error.PackEntrySizeOverflow;
        if (shift < 64) size |= part << @intCast(shift);
        shift +|= 7;
        more = b & 0x80 != 0;
    }
    var base: EntryHeader.Base = .none;
    switch (entry_type) {
        .ofs_delta => {
            if (at >= data.len) return error.TruncatedPackEntry;
            var b = data[at];
            at += 1;
            var distance: u64 = b & 0x7f;
            while (b & 0x80 != 0) {
                if (at >= data.len) return error.TruncatedPackEntry;
                b = data[at];
                at += 1;
                // Each further byte adds one before shifting, so that no
                // distance has two encodings.
                const plus = std.math.add(u64, distance, 1) catch return error.BadDeltaBaseOffset;
                if (plus > std.math.maxInt(u64) >> 7) return error.BadDeltaBaseOffset;
                distance = plus << 7 | (b & 0x7f);
            }
            if (distance == 0 or distance > offset) return error.BadDeltaBaseOffset;
            base = .{ .offset = offset - distance };
        },
        .ref_delta => {
            const h = format.byteLength();
            if (data.len - at < h) return error.TruncatedPackEntry;
            base = .{ .id = .fromBytes(format, data[at..][0..h]) };
            at += h;
        },
        else => {},
    }
    return .{ .type = entry_type, .size = size, .base = base, .data_offset = at };
}

/// What a pack's header says.
pub const Header = struct {
    /// 2 or 3.
    version: u32,
    /// How many objects the pack holds.
    count: u32,

    /// How many bytes the header takes.
    pub const len = 12;
};

/// Reads the header at the start of a pack.
pub fn parseHeader(bytes: []const u8, diag: ?*Diagnostics) error{ PackTooSmall, NotAPackfile, UnsupportedPackVersion }!Header {
    if (bytes.len < Header.len) return error.PackTooSmall;
    if (!std.mem.eql(u8, bytes[0..4], "PACK")) return error.NotAPackfile;
    const version = std.mem.readInt(u32, bytes[4..8], .big);
    if (version != 2 and version != 3) {
        if (diag) |d| d.setDetail("{d}", .{version});
        return error.UnsupportedPackVersion;
    }
    return .{ .version = version, .count = std.mem.readInt(u32, bytes[8..12], .big) };
}

/// Where a pack finds a REF_DELTA's base that it does not hold itself:
/// the object database it is part of. `depth` is how far resolution has
/// gone to get here, which the lookup passes on to any pack it reads the
/// base from, so that a chain crossing packs is still bounded.
pub const Bases = struct {
    ptr: *anyopaque,
    vtable: *const VTable,

    /// What a provider of bases implements.
    pub const VTable = struct {
        readHeader: *const fn (ptr: *anyopaque, io: Io, id: Id, depth: Depth, diag: ?*Diagnostics) ReadError!object.Header,
        read: *const fn (ptr: *anyopaque, io: Io, gpa: Allocator, id: Id, depth: Depth, diag: ?*Diagnostics) ReadError!Object,
    };
};

/// One pack and its index, open for reading.
pub const Pack = struct {
    format: Format,
    /// The whole `.pack` file.
    bytes: []const u8,
    index: PackIndex,
    /// How to name the pack in diagnostics.
    path: []const u8,
    /// The most bytes an object or a delta read whole from the pack may
    /// claim, or null for no limit; see the file comment. `init` sets
    /// none, and `DiskDatabase` sets its own.
    max_object_size: ?u64 = null,

    /// The pack `bytes` holds, found through `index`, checked as git
    /// checks a pack when it opens one: its header, its version, and that
    /// it ends with the checksum the index copied. Neither checksum is
    /// recomputed. Both slices must outlive the result.
    pub fn init(format: Format, bytes: []const u8, index: PackIndex, path: []const u8, diag: ?*Diagnostics) ObjectDatabase.PackOpenError!Pack {
        if (diag) |d| d.setPath(&.{path});
        const header = try parseHeader(bytes, diag);
        const h = format.byteLength();
        if (bytes.len < Header.len + h) return error.PackTooSmall;
        if (!std.mem.eql(u8, bytes[bytes.len - h ..], index.packChecksum())) return error.PackDoesNotMatchIndex;
        if (header.count != index.count) {
            if (diag) |d| d.setDetail("the pack holds {d} objects, its index {d}", .{ header.count, index.count });
            return error.PackObjectCountMismatch;
        }
        return .{ .format = format, .bytes = bytes, .index = index, .path = path };
    }

    /// The pack without its checksum: where every entry must lie.
    pub fn data(p: *const Pack) []const u8 {
        return p.bytes[0 .. p.bytes.len - p.format.byteLength()];
    }

    /// Where in the pack the object `id` is, if it holds it.
    pub fn find(p: *const Pack, id: Id, diag: ?*Diagnostics) error{BadLargeOffset}!?u64 {
        const i = p.index.find(id) orelse return null;
        return try p.index.offsetAt(i, diag);
    }

    /// The header of the entry at `offset`.
    pub fn entryHeader(p: *const Pack, offset: u64, diag: ?*Diagnostics) EntryError!EntryHeader {
        return parseEntryHeader(p.format, p.data(), offset) catch |err| {
            if (diag) |d| d.offset = offset;
            return err;
        };
    }

    /// The kind and size of the object whose entry is at `offset`; see the
    /// file comment for how little of it that reads. Nothing is allocated
    /// for the object, so a size over `max_object_size` is reported rather
    /// than refused, as git reports it.
    pub fn readHeader(p: *const Pack, io: Io, offset: u64, bases: ?Bases, depth: Depth, diag: ?*Diagnostics) ReadError!object.Header {
        const top = try p.entryHeader(offset, diag);
        if (top.type.kind()) |k| return .{ .kind = k, .size = top.size, .len = 0 };
        const sizes = try p.deltaSizes(top, offset, diag);
        // Then the kind, from the base at the end of the chain.
        var at = offset;
        var entry = top;
        var links: u32 = depth.links;
        while (true) {
            links += 1;
            if (links > max_delta_depth) return error.DeltaChainTooDeep;
            switch (entry.base) {
                .none => return .{ .kind = entry.type.kind().?, .size = sizes.result_size, .len = 0 },
                .offset => |o| at = o,
                .id => |id| {
                    if (try p.find(id, diag)) |o| {
                        at = o;
                    } else {
                        const b = bases orelse return missingBase(id, entry.data_offset, diag);
                        if (depth.hops >= max_base_hops) return error.DeltaChainTooDeep;
                        const base = b.vtable.readHeader(b.ptr, io, id, .{ .links = links, .hops = depth.hops + 1 }, diag) catch |err| switch (err) {
                            error.ObjectNotFound => return missingBase(id, entry.data_offset, diag),
                            else => return err,
                        };
                        return .{ .kind = base.kind, .size = sizes.result_size, .len = 0 };
                    }
                },
            }
            entry = try p.entryHeader(at, diag);
        }
    }

    /// The whole object whose entry is at `offset`, its delta chain
    /// applied; the caller owns it.
    pub fn read(p: *const Pack, io: Io, gpa: Allocator, offset: u64, bases: ?Bases, depth: Depth, diag: ?*Diagnostics) ReadError!Object {
        // Back along the chain to an object stored whole, or to a base
        // read from elsewhere.
        var chain: std.ArrayList(EntryHeader) = .empty;
        defer chain.deinit(gpa);
        var at = offset;
        var offsets: std.ArrayList(u64) = .empty;
        defer offsets.deinit(gpa);
        var base: Object = while (true) {
            const entry = try p.entryHeader(at, diag);
            if (entry.type.kind()) |k| break try p.inflateWhole(gpa, k, entry, at, diag);
            if (depth.links + chain.items.len + 1 > max_delta_depth) return error.DeltaChainTooDeep;
            // Each delta's result size is checked from the first bytes of
            // its stream before anything along the chain is built, so a
            // chain ending in a result over the limit costs nothing. A
            // stream too broken to say is left for applying it to report,
            // in the order it would have been met without a limit.
            if (p.max_object_size) |max| {
                var scratch: Diagnostics = .{};
                if (p.deltaSizes(entry, at, &scratch)) |sizes| {
                    if (sizes.result_size > max) return tooLarge(sizes.result_size, max, at, diag);
                } else |_| {}
            }
            try chain.append(gpa, entry);
            try offsets.append(gpa, at);
            switch (entry.base) {
                .none => unreachable,
                .offset => |o| at = o,
                .id => |id| {
                    if (try p.find(id, diag)) |o| {
                        at = o;
                    } else {
                        const b = bases orelse return missingBase(id, entry.data_offset, diag);
                        if (depth.hops >= max_base_hops) return error.DeltaChainTooDeep;
                        const links: u32 = @intCast(depth.links + chain.items.len);
                        break b.vtable.read(b.ptr, io, gpa, id, .{ .links = links, .hops = depth.hops + 1 }, diag) catch |err| switch (err) {
                            error.ObjectNotFound => return missingBase(id, entry.data_offset, diag),
                            else => return err,
                        };
                    }
                },
            }
        };
        errdefer base.deinit(gpa);
        // Then forward, applying each delta to what the last one made.
        var i = chain.items.len;
        while (i > 0) {
            i -= 1;
            const entry = chain.items[i];
            const instructions = try p.inflate(gpa, entry, offsets.items[i], diag);
            defer gpa.free(instructions.allocation);
            const result = delta.applyAlloc(gpa, base.data, instructions.data, p.max_object_size, diag) catch |err| {
                if (diag) |d| d.offset = offsets.items[i];
                return err;
            };
            const k = base.kind;
            base.deinit(gpa);
            base = .{ .kind = k, .data = result, .allocation = result };
        }
        return base;
    }

    /// Writes the contents of the object whose entry is at `offset` to
    /// `out` and returns its header: as it is inflated, in bounded memory,
    /// for an object stored whole, and otherwise once it has been built.
    pub fn stream(p: *const Pack, io: Io, gpa: Allocator, offset: u64, out: *Io.Writer, bases: ?Bases, depth: Depth, diag: ?*Diagnostics) StreamError!object.Header {
        const entry = try p.entryHeader(offset, diag);
        const k = entry.type.kind() orelse {
            var obj = try p.read(io, gpa, offset, bases, depth, diag);
            defer obj.deinit(gpa);
            try out.writeAll(obj.data);
            return .{ .kind = obj.kind, .size = obj.data.len, .len = 0 };
        };
        var detail: []const u8 = "";
        const n = zlib.inflateStream(gpa, p.data()[@intCast(entry.data_offset)..], out, &detail) catch |err| {
            if (diag) |d| d.offset = offset;
            return switch (err) {
                error.InflateFailed => {
                    if (diag) |d| d.setDetail("{s}", .{detail});
                    return error.ContentInflateFailed;
                },
                error.TruncatedStream => error.TruncatedObject,
                error.OutOfMemory => error.OutOfMemory,
                error.WriteFailed => error.WriteFailed,
            };
        };
        if (n != entry.size) {
            if (diag) |d| d.offset = offset;
            return if (n > entry.size) error.ContentTooLong else error.ContentTooShort;
        }
        return .{ .kind = k, .size = entry.size, .len = 0 };
    }

    /// The two sizes the delta whose entry is `entry`, at `offset`, begins
    /// with, inflating no more of it than they take: two numbers of at
    /// most ten bytes each.
    fn deltaSizes(p: *const Pack, entry: EntryHeader, offset: u64, diag: ?*Diagnostics) ReadError!delta.Header {
        var prefix: [20]u8 = undefined;
        var detail: []const u8 = "";
        const n = zlib.inflatePrefix(p.data()[@intCast(entry.data_offset)..], &prefix, &detail) catch |err| {
            if (diag) |d| d.offset = offset;
            return switch (err) {
                error.InflateFailed => {
                    if (diag) |d| d.setDetail("{s}", .{detail});
                    return error.ContentInflateFailed;
                },
                error.TruncatedStream => error.TruncatedObject,
            };
        };
        return delta.parseHeader(prefix[0..n]) catch |err| {
            if (diag) |d| d.offset = offset;
            return err;
        };
    }

    fn inflateWhole(p: *const Pack, gpa: Allocator, k: Kind, entry: EntryHeader, at: u64, diag: ?*Diagnostics) ReadError!Object {
        var obj = try p.inflate(gpa, entry, at, diag);
        obj.kind = k;
        return obj;
    }

    /// Inflates an entry's zlib stream, which must come to exactly its
    /// size.
    fn inflate(p: *const Pack, gpa: Allocator, entry: EntryHeader, at: u64, diag: ?*Diagnostics) ReadError!Object {
        // A size no stream in the rest of the pack could inflate to is
        // refused before it is allocated: the header is a few bytes, and
        // must not be able to ask for more memory than the pack could
        // fill.
        const available = p.data().len - @as(usize, @intCast(entry.data_offset));
        if (entry.size > zlib.maxInflatedLen(available)) {
            if (diag) |d| {
                d.offset = at;
                d.setDetail("entry is {d} bytes, more than the {d} bytes after it could inflate to", .{ entry.size, available });
            }
            return error.ContentTooShort;
        }
        // A size the pack could hold, but more than the caller will have
        // built in memory. A delta may take more bytes than it makes, so
        // its own limit is the most a delta making an object at the limit
        // could take: its two sizes, then at most eight bytes of copy
        // instruction for every byte made.
        if (p.max_object_size) |max| {
            const limit = if (entry.type.kind() == null) max_delta_overhead +| max *| 8 else max;
            if (entry.size > limit) return tooLarge(entry.size, limit, at, diag);
        }
        const size = std.math.cast(usize, entry.size) orelse return error.OutOfMemory;
        const buffer = try gpa.alloc(u8, std.math.add(usize, size, 1) catch return error.OutOfMemory);
        errdefer gpa.free(buffer);
        var detail: []const u8 = "";
        zlib.inflateExact(p.data()[@intCast(entry.data_offset)..], buffer, size, &detail) catch |err| {
            if (diag) |d| d.offset = at;
            return switch (err) {
                error.InflateFailed => {
                    if (diag) |d| d.setDetail("{s}", .{detail});
                    return error.ContentInflateFailed;
                },
                error.TruncatedStream => error.TruncatedObject,
                error.StreamTooLong => error.ContentTooLong,
                error.StreamTooShort => error.ContentTooShort,
            };
        };
        return .{ .kind = .blob, .data = buffer[0..size], .allocation = buffer };
    }
};

/// The most bytes a delta's two sizes take, ten each.
const max_delta_overhead = 20;

fn tooLarge(size: u64, max: u64, offset: u64, diag: ?*Diagnostics) ReadError {
    if (diag) |d| {
        d.offset = offset;
        d.setDetail("{d} bytes, more than the limit of {d}", .{ size, max });
    }
    return error.ObjectTooLarge;
}

/// The diagnostic's offset is where the delta's data begins, just after
/// the base's object ID, which is the offset git names.
fn missingBase(id: Id, data_offset: u64, diag: ?*Diagnostics) ReadError {
    if (diag) |d| {
        d.setDetail("{f}", .{id});
        d.offset = data_offset;
    }
    return error.DeltaBaseMissing;
}

const testing = std.testing;
const fixture = @import("testing/fixture.zig");
const fuzz_input = @import("testing/fuzz.zig");
const packs = @import("testing/packs.zig");

/// A pack read from the test repository's pack directory.
const Loaded = struct {
    pack_bytes: []u8,
    idx_bytes: []u8,
    pack: Pack,

    fn init(repo: *fixture.Repo, name: []const u8) !Loaded {
        const pack_bytes = try packs.readPackFile(repo, name, "pack");
        errdefer repo.gpa.free(pack_bytes);
        const idx_bytes = try packs.readPackFile(repo, name, "idx");
        errdefer repo.gpa.free(idx_bytes);
        const index = try PackIndex.parse(repo.object_format, idx_bytes, null);
        return .{ .pack_bytes = pack_bytes, .idx_bytes = idx_bytes, .pack = try .init(repo.object_format, pack_bytes, index, name, null) };
    }

    fn deinit(l: *Loaded, gpa: Allocator) void {
        gpa.free(l.pack_bytes);
        gpa.free(l.idx_bytes);
    }
};

test "every object of a pack git wrote, deltas and all, reads as git reads it" {
    const gpa = testing.allocator;
    var repo = try fixture.Repo.init(gpa, testing.io);
    defer repo.deinit();
    var text: std.ArrayList(u8) = .empty;
    defer text.deinit(gpa);
    for (0..400) |i| try text.print(gpa, "line {d}\n", .{i});
    for (0..25) |i| {
        // Small changes to a big file, so that git stores deltas of
        // deltas.
        const at = (i * 37) % (text.items.len - 10);
        text.items[at] = 'x';
        try repo.commitFile("f", text.items, "c");
    }
    try repo.git(&.{ "repack", "-adfq", "--depth=50", "--window=50" });
    const list = try packs.names(&repo);
    defer packs.freeNames(gpa, list);
    var loaded = try Loaded.init(&repo, list[0]);
    defer loaded.deinit(gpa);
    const p = &loaded.pack;

    var deltas: usize = 0;
    var i: u32 = 0;
    while (i < p.index.count) : (i += 1) {
        const id = p.index.idAt(i);
        const offset = (try p.find(id, null)).?;
        if ((try p.entryHeader(offset, null)).type.kind() == null) deltas += 1;
        const hex = try std.fmt.allocPrint(gpa, "{f}", .{id});
        defer gpa.free(hex);
        const kind_name = try repo.output(&.{ "cat-file", "-t", hex });
        defer gpa.free(kind_name);
        const want = try repo.output(&.{ "cat-file", std.mem.trimEnd(u8, kind_name, "\n"), hex });
        defer gpa.free(want);

        const header = try p.readHeader(testing.io, offset, null, .{}, null);
        try testing.expectEqualStrings(std.mem.trimEnd(u8, kind_name, "\n"), header.kind.name());
        try testing.expectEqual(want.len, header.size);
        var obj = try p.read(testing.io, gpa, offset, null, .{}, null);
        defer obj.deinit(gpa);
        try testing.expectEqualSlices(u8, want, obj.data);
        try testing.expect(Id.eql(id, object.hash(repo.object_format, obj.kind, obj.data)));
        var aw: Io.Writer.Allocating = .init(gpa);
        defer aw.deinit();
        _ = try p.stream(testing.io, gpa, offset, &aw.writer, null, .{}, null);
        try testing.expectEqualSlices(u8, want, aw.written());
    }
    try testing.expect(deltas > 10);
}

test "a delta chain that loops, or runs too deep, is an error" {
    const gpa = testing.allocator;
    const format: Format = .sha1;
    var w: packs.PackWriter = try .init(gpa, format);
    defer w.deinit();
    const d = try packs.deltaInsert(gpa, 3, "abc");
    defer gpa.free(d);
    // Two REF_DELTAs, each the other's base.
    const a = object.hash(format, .blob, "a");
    const b = object.hash(format, .blob, "b");
    const at_a = try w.refDelta(b, d, a);
    _ = try w.refDelta(a, d, b);
    const out = try w.finish();
    defer gpa.free(out.pack);
    defer gpa.free(out.idx);
    const p: Pack = try .init(format, out.pack, try PackIndex.parse(format, out.idx, null), "loop.pack", null);
    try testing.expectError(error.DeltaChainTooDeep, p.read(testing.io, gpa, at_a, null, .{}, null));
    try testing.expectError(error.DeltaChainTooDeep, p.readHeader(testing.io, at_a, null, .{}, null));
}

test "a size no stream in the pack could inflate to is refused, not allocated" {
    const gpa = testing.allocator;
    const format: Format = .sha1;
    var w: packs.PackWriter = try .init(gpa, format);
    defer w.deinit();
    // A blob whose header claims fifty gigabytes, followed by a stream of
    // five bytes, and an OFS_DELTA against it: reading either would
    // otherwise allocate the fifty gigabytes, and `testing.allocator`
    // writes over all of what it frees.
    const z = try packs.zlibStored(gpa, "hello");
    defer gpa.free(z);
    const claimed: u64 = 50 << 30;
    const at_blob = try w.raw(3, claimed, "", z, object.hash(format, .blob, "big"));
    const d = try packs.deltaInsert(gpa, claimed, "abc");
    defer gpa.free(d);
    const at_delta = try w.ofsDelta(at_blob, d, object.hash(format, .blob, "abc"));
    const out = try w.finish();
    defer gpa.free(out.pack);
    defer gpa.free(out.idx);
    const p: Pack = try .init(format, out.pack, try PackIndex.parse(format, out.idx, null), "claim.pack", null);
    var bounded: fuzz_input.Bounded = .{ .backing = gpa, .limit = 1 << 20 };
    var diag: Diagnostics = .{};
    try testing.expectError(error.ContentTooShort, p.read(testing.io, bounded.allocator(), at_blob, null, .{}, &diag));
    try testing.expectEqual(at_blob, diag.offset);
    try testing.expectError(error.ContentTooShort, p.read(testing.io, bounded.allocator(), at_delta, null, .{}, null));
    try bounded.check();
    // The header alone is still what the entry says, as git's is.
    try testing.expectEqual(claimed, (try p.readHeader(testing.io, at_blob, null, .{}, null)).size);
}

test "an object or a delta result over the size limit is refused before it is built" {
    const gpa = testing.allocator;
    const format: Format = .sha1;
    var w: packs.PackWriter = try .init(gpa, format);
    defer w.deinit();
    const at_base = try w.whole(.blob, "hello");
    // A delta of a dozen bytes that claims a terabyte and would make it,
    // with copies of 64 KiB of a base that has them, were the base bigger:
    // refused from its header, before the base is read.
    const huge = [_]u8{ 0x05, 0x80, 0x80, 0x80, 0x80, 0x80, 0x20, 0x80, 0x80, 0x80 };
    const at_huge = try w.ofsDelta(at_base, &huge, object.hash(format, .blob, "huge"));
    // And a delta on that delta, which never gets as far as it.
    const d = try packs.deltaInsert(gpa, 1 << 40, "x");
    defer gpa.free(d);
    const at_chain = try w.ofsDelta(at_huge, d, object.hash(format, .blob, "x"));
    // A delta making exactly eight bytes, in thirteen.
    const eight = try packs.deltaAppend(gpa, 5, "!!!");
    defer gpa.free(eight);
    const at_eight = try w.ofsDelta(at_base, eight, object.hash(format, .blob, "hello!!!"));
    const out = try w.finish();
    defer gpa.free(out.pack);
    defer gpa.free(out.idx);
    var p: Pack = try .init(format, out.pack, try PackIndex.parse(format, out.idx, null), "limit.pack", null);

    var bounded: fuzz_input.Bounded = .{ .backing = gpa, .limit = 1 << 16 };
    const limited = bounded.allocator();
    p.max_object_size = 8;
    var diag: Diagnostics = .{};
    try testing.expectError(error.ObjectTooLarge, p.read(testing.io, limited, at_huge, null, .{}, &diag));
    try testing.expectEqual(at_huge, diag.offset);
    try testing.expectEqualStrings("1099511627776 bytes, more than the limit of 8", diag.detail());
    try testing.expectError(error.ObjectTooLarge, p.read(testing.io, limited, at_chain, null, .{}, null));
    var nowhere: Io.Writer = .failing;
    try testing.expectError(error.ObjectTooLarge, p.stream(testing.io, limited, at_chain, &nowhere, null, .{}, null));
    try bounded.check();
    // The header is what the delta says, limit or not.
    try testing.expectEqual(1 << 40, (try p.readHeader(testing.io, at_huge, null, .{}, null)).size);
    // At the limit, the delta's result and the whole object read.
    {
        var obj = try p.read(testing.io, limited, at_eight, null, .{}, null);
        defer obj.deinit(limited);
        try testing.expectEqualStrings("hello!!!", obj.data);
    }
    p.max_object_size = 4;
    try testing.expectError(error.ObjectTooLarge, p.read(testing.io, limited, at_base, null, .{}, null));
    p.max_object_size = 5;
    {
        var obj = try p.read(testing.io, limited, at_base, null, .{}, null);
        defer obj.deinit(limited);
        try testing.expectEqualStrings("hello", obj.data);
    }
    // A whole object streams in bounded memory, so is not refused.
    p.max_object_size = 1;
    var aw: Io.Writer.Allocating = .init(gpa);
    defer aw.deinit();
    _ = try p.stream(testing.io, limited, at_base, &aw.writer, null, .{}, null);
    try testing.expectEqualStrings("hello", aw.written());
    // Without a limit the claim is believed as far as applying the delta,
    // which finds its copies out of the base's range.
    p.max_object_size = null;
    try testing.expectError(error.DeltaCopyOutOfRange, p.read(testing.io, limited, at_huge, null, .{}, null));
    try bounded.check();
}

test "an entry's header is read as gitformat-pack(5) lays it out" {
    const format: Format = .sha1;
    // A blob of 0x123 bytes: type 3, the low four bits, then the rest.
    const blob = [_]u8{ 0x80 | 0x30 | 0x03, 0x12, 0xaa };
    const h = try parseEntryHeader(format, &blob, 0);
    try testing.expectEqual(EntryType.blob, h.type);
    try testing.expectEqual(0x123, h.size);
    try testing.expectEqual(2, h.data_offset);
    try testing.expectError(error.BadPackEntryType, parseEntryHeader(format, &.{0x50}, 0));
    try testing.expectError(error.BadPackEntryType, parseEntryHeader(format, &.{0x00}, 0));
    try testing.expectError(error.TruncatedPackEntry, parseEntryHeader(format, &.{0xb0}, 0));
    // An OFS_DELTA 200 bytes back: 200 - 128 = 72 after the first byte's
    // implicit one.
    var bytes: [300]u8 = @splat(0);
    bytes[250] = 0x60 | 0x05;
    bytes[251] = 0x80 | 0x00;
    bytes[252] = 72;
    const o = try parseEntryHeader(format, &bytes, 250);
    try testing.expectEqual(50, o.base.offset);
    try testing.expectEqual(253, o.data_offset);
    bytes[250] = 0x60;
    bytes[251] = 0x00;
    try testing.expectError(error.BadDeltaBaseOffset, parseEntryHeader(format, &bytes, 250));
    bytes[251] = 0x80 | 0x7f;
    bytes[252] = 0x7f;
    try testing.expectError(error.BadDeltaBaseOffset, parseEntryHeader(format, &bytes, 250));
    var buf: [16]u8 = undefined;
    try testing.expectEqualSlices(u8, &.{ 0x80, 72 }, packs.encodeOffset(200, &buf));
}

/// A version 2 pack index of no objects, long enough for either format.
const empty_index_bytes = PackIndex.magic ++ "\x00\x00\x00\x02" ++ @as([1024 + 64]u8, @splat(0));

fn fuzzOne(_: void, smith: *testing.Smith) anyerror!void {
    // A few kilobytes of pack can make no more than a few megabytes of
    // object, unless deltas multiply one another: anything much bigger
    // was taken from a header rather than made.
    var bounded: fuzz_input.Bounded = .{ .backing = testing.allocator, .limit = 64 << 20 };
    const gpa = bounded.allocator();
    var buffer: [4096]u8 = undefined;
    const bytes = fuzz_input.bytes(smith, &buffer);
    _ = parseHeader(bytes, null) catch {};
    // Every entry header from the start of the entries, and every object
    // they hold, read as a pack with no index.
    for ([_]Format{ .sha1, .sha256 }) |format| {
        const h = format.byteLength();
        if (bytes.len < Header.len + h) continue;
        const empty_index = try PackIndex.parse(format, empty_index_bytes[0 .. 8 + 1024 + 2 * h], null);
        const p: Pack = .{ .format = format, .bytes = bytes, .index = empty_index, .path = "fuzz" };
        var at: u64 = Header.len;
        var n: usize = 0;
        while (at < p.data().len and n < 16) : (n += 1) {
            const entry = p.entryHeader(at, null) catch break;
            if (entry.size < 1 << 16) {
                if (p.read(testing.io, gpa, at, null, .{}, null)) |obj| {
                    var o = obj;
                    const header = try p.readHeader(testing.io, at, null, .{}, null);
                    try testing.expectEqual(header.size, o.data.len);
                    o.deinit(gpa);
                } else |_| {}
            }
            if (entry.data_offset <= at) break;
            at = entry.data_offset + 1;
        }
    }
    try bounded.check();
}

test "fuzz: pack entries and headers" {
    try fuzz_input.fuzz({}, fuzzOne, .{
        .corpus = &.{
            @embedFile("fuzz/pack"),
            @embedFile("fuzz/pack-deltas"),
            @embedFile("fuzz/pack-sha256"),
            // An OFS_DELTA whose base claims fifty gigabytes.
            @embedFile("fuzz/pack-size-claim"),
        },
    });
}