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

//! A multi-pack-index: one table finding the objects of many packs at
//! once (`objects/pack/multi-pack-index`, gitformat-pack(5), in the
//! chunk-based layout of gitformat-chunk(5)).
//!
//! It begins with `MIDX`, a version (1 or 2), the object format's number
//! (1 for SHA-1, 2 for SHA-256), the number of chunks and of base files,
//! and the number of packs; then a table of contents of 12-byte rows, a
//! chunk ID and the offset where it starts, ending with a row whose ID is
//! zero. The chunks read here are the ones finding an object:
//!
//! - `PNAM`, the names of the packs' indexes, NUL-terminated;
//! - `OIDF`, a 256-entry fanout table;
//! - `OIDL`, the sorted object IDs;
//! - `OOFF`, for each object the number of its pack and its offset there;
//! - `LOFF`, optional, 8-byte offsets for those past 2 GiB.
//!
//! Others, such as the bitmap chunks, are skipped. An object in several
//! packs is listed once, so a multi-pack-index is only a faster way of
//! asking the packs it names; packs it does not name are still asked.
//!
//! `parse` checks what git checks when it loads one, found by corrupting
//! one and asking `git cat-file`. git stops outright on a bad signature,
//! an unknown version or a missing chunk, and otherwise says what was
//! wrong and goes on without it; `isFatal` says which is which. Like git,
//! it does not check the checksum at the end; `verifyChecksum` does.
//!
//! Nothing here does I/O.

const std = @import("std");

const object = @import("object.zig");
const Format = object.Format;
const Id = object.Id;
const Diagnostics = @import("Diagnostics.zig");
const PackIndex = @import("PackIndex.zig");

const MultiPackIndex = @This();

/// The whole file.
bytes: []const u8,
format: Format,
/// 1 or 2.
version: u8,
/// How many packs it names.
pack_count: u32,
/// How many objects it finds.
count: u32,
names: []const u8,
fanout_at: usize,
ids_at: usize,
offsets_at: usize,
large_at: usize,
large_count: usize,
/// Whether the file had a large-offset chunk, which decides what the top
/// bit of a 4-byte offset means: without one, offsets are plain 32-bit
/// numbers.
has_large: bool,

/// Why a multi-pack-index could not be read, each in git's words:
///
/// - `MultiPackIndexTooSmall`: "multi-pack-index file … is too small".
/// - `BadMultiPackIndexSignature`: "multi-pack-index signature 0x… does
///   not match signature 0x4d494458".
/// - `UnsupportedMultiPackIndexVersion`: "multi-pack-index version N not
///   recognized".
/// - `MultiPackIndexHashMismatch`: "multi-pack-index hash version N does
///   not match version M": it was written for the other object format.
/// - `UnsupportedMultiPackIndexBase`: a file claiming base files, which
///   gitformat-pack(5) says are always zero.
/// - `BadMultiPackIndexChunkOffsets`: "improper chunk offset(s) … and …":
///   the table of contents points outside the file or backwards.
/// - `MissingMultiPackIndexChunk`: "multi-pack-index required … chunk
///   missing or corrupted": one of the four required chunks is absent or
///   the wrong size. The detail names it as git does: `pack-name`, `OID
///   fanout`, `OID lookup` or `object offsets`.
/// - `CorruptMultiPackIndexPackNames`: fewer names than packs.
/// - `NonMonotonicMultiPackIndex`: a fanout entry smaller than the one
///   before.
pub const Error = error{
    MultiPackIndexTooSmall,
    BadMultiPackIndexSignature,
    UnsupportedMultiPackIndexVersion,
    MultiPackIndexHashMismatch,
    UnsupportedMultiPackIndexBase,
    BadMultiPackIndexChunkOffsets,
    MissingMultiPackIndexChunk,
    CorruptMultiPackIndexPackNames,
    NonMonotonicMultiPackIndex,
};

/// Whether git stops at this error rather than going on without the
/// multi-pack-index.
pub fn isFatal(err: Error) bool {
    return switch (err) {
        error.BadMultiPackIndexSignature,
        error.UnsupportedMultiPackIndexVersion,
        error.MissingMultiPackIndexChunk,
        => true,
        else => false,
    };
}

const header_len = 12;

/// Reads the multi-pack-index `bytes` holds for a repository of `format`.
/// `bytes` must outlive the result.
pub fn parse(format: Format, bytes: []const u8, diag: ?*Diagnostics) Error!MultiPackIndex {
    const h = format.byteLength();
    if (bytes.len < header_len + h) return error.MultiPackIndexTooSmall;
    if (!std.mem.eql(u8, bytes[0..4], "MIDX")) {
        if (diag) |d| d.setDetail("0x{x:0>8}", .{std.mem.readInt(u32, bytes[0..4], .big)});
        return error.BadMultiPackIndexSignature;
    }
    const version = bytes[4];
    if (version != 1 and version != 2) {
        if (diag) |d| d.setDetail("{d}", .{version});
        return error.UnsupportedMultiPackIndexVersion;
    }
    const want_hash: u8 = switch (format) {
        .sha1 => 1,
        .sha256 => 2,
    };
    if (bytes[5] != want_hash) {
        if (diag) |d| d.setDetail("{d} does not match version {d}", .{ bytes[5], want_hash });
        return error.MultiPackIndexHashMismatch;
    }
    const chunk_count = bytes[6];
    if (bytes[7] != 0) return error.UnsupportedMultiPackIndexBase;
    const pack_count = std.mem.readInt(u32, bytes[8..12], .big);

    // The table of contents, and the chunks it finds.
    const end = bytes.len - h;
    const toc_end = header_len + (@as(usize, chunk_count) + 1) * 12;
    if (toc_end > end) return error.MultiPackIndexTooSmall;
    var pnam: ?[]const u8 = null;
    var oidf: ?[]const u8 = null;
    var oidl: ?[]const u8 = null;
    var ooff: ?[]const u8 = null;
    var loff: ?[]const u8 = null;
    for (0..chunk_count) |i| {
        const row = bytes[header_len + 12 * i ..][0..24];
        const start = std.mem.readInt(u64, row[4..12], .big);
        const next = std.mem.readInt(u64, row[16..24], .big);
        if (start < toc_end or start > next or next > end) {
            if (diag) |d| d.setDetail("{x} and {x}", .{ start, next });
            return error.BadMultiPackIndexChunkOffsets;
        }
        const chunk = bytes[@intCast(start)..@intCast(next)];
        const which = row[0..4];
        if (std.mem.eql(u8, which, "PNAM")) pnam = chunk;
        if (std.mem.eql(u8, which, "OIDF")) oidf = chunk;
        if (std.mem.eql(u8, which, "OIDL")) oidl = chunk;
        if (std.mem.eql(u8, which, "OOFF")) ooff = chunk;
        if (std.mem.eql(u8, which, "LOFF")) loff = chunk;
    }

    const names = pnam orelse return missing(diag, "pack-name");
    const fanout_chunk = oidf orelse return missing(diag, "OID fanout");
    if (fanout_chunk.len != 256 * 4) return missing(diag, "OID fanout");
    var previous: u32 = 0;
    for (0..256) |i| {
        const n = std.mem.readInt(u32, fanout_chunk[4 * i ..][0..4], .big);
        if (n < previous) return error.NonMonotonicMultiPackIndex;
        previous = n;
    }
    const count = previous;
    const ids = oidl orelse return missing(diag, "OID lookup");
    if (ids.len != @as(u64, count) * h) return missing(diag, "OID lookup");
    const offsets = ooff orelse return missing(diag, "object offsets");
    if (offsets.len != @as(u64, count) * 8) return missing(diag, "object offsets");
    const large = loff orelse bytes[0..0];

    const m: MultiPackIndex = .{
        .bytes = bytes,
        .format = format,
        .version = version,
        .pack_count = pack_count,
        .count = count,
        .names = names,
        .fanout_at = @intFromPtr(fanout_chunk.ptr) - @intFromPtr(bytes.ptr),
        .ids_at = @intFromPtr(ids.ptr) - @intFromPtr(bytes.ptr),
        .offsets_at = @intFromPtr(offsets.ptr) - @intFromPtr(bytes.ptr),
        .large_at = @intFromPtr(large.ptr) - @intFromPtr(bytes.ptr),
        .large_count = if (loff != null) large.len / 8 else 0,
        .has_large = loff != null,
    };
    var it = m.packNames();
    var n: u32 = 0;
    while (n < pack_count) : (n += 1) _ = it.next() orelse return error.CorruptMultiPackIndexPackNames;
    return m;
}

fn missing(diag: ?*Diagnostics, which: []const u8) Error {
    if (diag) |d| d.setDetail("{s}", .{which});
    return error.MissingMultiPackIndexChunk;
}

/// Steps through the names of the packs' indexes, in the order their
/// numbers refer to.
pub const NameIterator = struct {
    rest: []const u8,

    /// The next name, without its NUL, or null after the last.
    pub fn next(it: *NameIterator) ?[]const u8 {
        const nul = std.mem.findScalar(u8, it.rest, 0) orelse return null;
        if (nul == 0) return null;
        const name = it.rest[0..nul];
        it.rest = it.rest[nul + 1 ..];
        return name;
    }
};

/// The names of the packs' indexes (`pack-<hex>.idx`).
pub fn packNames(m: *const MultiPackIndex) NameIterator {
    return .{ .rest = m.names };
}

/// The object ID of the `i`th object, in object ID order.
pub fn idAt(m: *const MultiPackIndex, i: u32) Id {
    const h = m.format.byteLength();
    return .fromBytes(m.format, m.bytes[m.ids_at + @as(usize, i) * h ..][0..h]);
}

/// The position of the object `id`, if one of the packs holds it.
pub fn find(m: *const MultiPackIndex, id: Id) ?u32 {
    const h = m.format.byteLength();
    const first = id.bytes[0];
    var lo: usize = if (first == 0) 0 else m.fanoutAt(first - 1);
    var hi: usize = m.fanoutAt(first);
    const want = id.slice();
    while (lo < hi) {
        const mid = lo + (hi - lo) / 2;
        switch (std.mem.order(u8, m.bytes[m.ids_at + mid * h ..][0..h], want)) {
            .eq => return @intCast(mid),
            .lt => lo = mid + 1,
            .gt => hi = mid,
        }
    }
    return null;
}

/// How many objects have IDs whose first byte is at most `b`.
pub fn fanout(m: *const MultiPackIndex, b: u8) u32 {
    return m.fanoutAt(b);
}

fn fanoutAt(m: *const MultiPackIndex, b: u8) u32 {
    return std.mem.readInt(u32, m.bytes[m.fanout_at + 4 * @as(usize, b) ..][0..4], .big);
}

/// Where an object is: which pack, by its number in `packNames` order, and
/// where in it.
pub const Location = struct { pack: u32, offset: u64 };

/// Where the `i`th object is. A pack number past the last pack is
/// `BadMultiPackIndexEntry`, and an offset past the end of the
/// large-offset chunk `BadLargeOffset`.
pub fn locationAt(m: *const MultiPackIndex, i: u32, diag: ?*Diagnostics) error{ BadMultiPackIndexEntry, BadLargeOffset }!Location {
    const row = m.bytes[m.offsets_at + 8 * @as(usize, i) ..][0..8];
    const pack = std.mem.readInt(u32, row[0..4], .big);
    if (pack >= m.pack_count) {
        if (diag) |d| d.setDetail("pack {d} of {d}", .{ pack, m.pack_count });
        return error.BadMultiPackIndexEntry;
    }
    const raw = std.mem.readInt(u32, row[4..8], .big);
    if (!m.has_large or raw & 0x8000_0000 == 0) return .{ .pack = pack, .offset = raw };
    const k = raw & 0x7fff_ffff;
    if (k >= m.large_count) {
        if (diag) |d| d.setDetail("large offset {d} of {d}", .{ k, m.large_count });
        return error.BadLargeOffset;
    }
    return .{ .pack = pack, .offset = std.mem.readInt(u64, m.bytes[m.large_at + 8 * k ..][0..8], .big) };
}

/// The checksum the file ends with, which is also the name of a layer of
/// an incremental chain.
pub fn checksum(m: *const MultiPackIndex) []const u8 {
    return m.bytes[m.bytes.len - m.format.byteLength() ..];
}

/// Whether the checksum the file ends with is the hash of the rest, which
/// `git multi-pack-index verify` checks and reading an object does not.
pub fn verifyChecksum(m: *const MultiPackIndex) bool {
    return PackIndex.checksumMatches(m.format, m.bytes);
}

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

test "a multi-pack-index git wrote finds every object of every pack it names" {
    const gpa = testing.allocator;
    var repo = try fixture.Repo.init(gpa, testing.io);
    defer repo.deinit();
    for (0..4) |i| {
        var buf: [32]u8 = undefined;
        try repo.commitFile("f", try std.fmt.bufPrint(&buf, "v{d}\n", .{i}), "c");
        try repo.git(&.{ "repack", "-dq" });
    }
    try repo.git(&.{ "multi-pack-index", "write" });
    const bytes = try repo.tmp.dir.readFileAlloc(repo.io, ".git/objects/pack/multi-pack-index", gpa, .unlimited);
    defer gpa.free(bytes);
    const m = try parse(repo.object_format, bytes, null);
    try testing.expect(m.verifyChecksum());
    try testing.expectEqual(4, m.pack_count);

    // Every pack's index agrees about where each of its objects is.
    var names: std.ArrayList([]const u8) = .empty;
    defer names.deinit(gpa);
    var it = m.packNames();
    while (it.next()) |n| try names.append(gpa, n);
    try testing.expectEqual(4, names.items.len);
    var seen: u32 = 0;
    for (names.items, 0..) |name, pack_number| {
        const idx_bytes = try packs.readPackFile(&repo, name[0 .. name.len - 4], "idx");
        defer gpa.free(idx_bytes);
        const idx = try PackIndex.parse(repo.object_format, idx_bytes, null);
        var i: u32 = 0;
        while (i < idx.count) : (i += 1) {
            const pos = m.find(idx.idAt(i)) orelse return error.TestUnexpectedResult;
            const loc = try m.locationAt(pos, null);
            if (loc.pack != pack_number) continue;
            seen += 1;
            try testing.expectEqual(try idx.offsetAt(i, null), loc.offset);
        }
    }
    try testing.expectEqual(m.count, seen);
}

test "a multi-pack-index is refused as git refuses it" {
    const gpa = testing.allocator;
    const good = @embedFile("fuzz/midx");
    _ = try parse(.sha1, good, null);
    var diag: Diagnostics = .{};
    try testing.expectError(error.MultiPackIndexHashMismatch, parse(.sha256, good, &diag));
    try testing.expectEqualStrings("1 does not match version 2", diag.detail());
    try testing.expectError(error.MultiPackIndexTooSmall, parse(.sha1, good[0..10], null));
    try testing.expectError(error.BadMultiPackIndexChunkOffsets, parse(.sha1, good[0..1000], null));
    const bad = try gpa.dupe(u8, good);
    defer gpa.free(bad);
    bad[0] = 'L';
    try testing.expectError(error.BadMultiPackIndexSignature, parse(.sha1, bad, &diag));
    try testing.expectEqualStrings("0x4c494458", diag.detail());
    bad[0] = 'M';
    bad[4] = 6;
    try testing.expectError(error.UnsupportedMultiPackIndexVersion, parse(.sha1, bad, null));
    bad[4] = 1;
    bad[12] = 'Q'; // PNAM is the first chunk
    try testing.expectError(error.MissingMultiPackIndexChunk, parse(.sha1, bad, &diag));
    try testing.expectEqualStrings("pack-name", diag.detail());
    try testing.expect(isFatal(error.MissingMultiPackIndexChunk));
    try testing.expect(!isFatal(error.MultiPackIndexTooSmall));
}

fn fuzzOne(_: void, smith: *testing.Smith) anyerror!void {
    var buffer: [4096]u8 = undefined;
    const bytes = fuzz_input.bytes(smith, &buffer);
    for ([_]Format{ .sha1, .sha256 }) |format| {
        const m = parse(format, bytes, null) catch continue;
        var it = m.packNames();
        while (it.next()) |_| {}
        var i: u32 = 0;
        while (i < m.count) : (i += 1) {
            _ = m.find(m.idAt(i));
            _ = m.locationAt(i, null) catch {};
        }
        _ = m.verifyChecksum();
    }
}

test "fuzz: multi-pack-indexes" {
    try fuzz_input.fuzz({}, fuzzOne, .{ .corpus = &.{
        @embedFile("fuzz/midx"),
        @embedFile("fuzz/midx-sha256"),
    } });
}