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

//! A pack index: the `.idx` file beside a pack, which finds each of the
//! pack's objects by object ID (gitformat-pack(5)). Both versions are
//! read:
//!
//! - **Version 1**, which `git index-pack --index-version=1` and
//!   `pack.indexVersion=1` still write and git still reads: a 256-entry
//!   fanout table, then one entry per object of a 4-byte offset and the
//!   object ID.
//! - **Version 2**, the default: the bytes `\377tOc`, the version, the
//!   fanout table, then the sorted object IDs, a CRC-32 per object, a
//!   4-byte offset per object whose top bit, when set, makes the rest an
//!   index into a table of 8-byte offsets for packs past 2 GiB.
//!
//! Both end with a copy of the pack's checksum and the index's own
//! checksum, each as long as an object ID.
//!
//! `parse` checks what git checks when it opens an index, found by
//! corrupting indexes and asking `git cat-file` about their objects: the
//! size, the version, and that the fanout table never decreases. Like git,
//! it does not check the index's checksum or the CRCs; `verifyChecksum`
//! does the first for a caller who wants it. The object IDs are assumed
//! sorted, as git assumes them: an index whose IDs are out of order simply
//! fails to find some of them.
//!
//! Nothing here does I/O: the index is bytes the caller has, typically
//! memory-mapped.

const std = @import("std");

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

const PackIndex = @This();

/// The whole file.
bytes: []const u8,
/// The object format of the IDs it holds.
format: Format,
/// 1 or 2.
version: u8,
/// How many objects the pack holds.
count: u32,
/// Where each table starts.
fanout_at: usize,
names_at: usize,
crcs_at: usize,
offsets_at: usize,
large_offsets_at: usize,
/// How many 8-byte offsets the large-offset table has room for.
large_count: usize,

/// The bytes a version 2 index begins with, which as a version 1 fanout
/// entry would be absurd.
pub const magic = "\xfftOc";

/// Why an index could not be read, each in git's words:
///
/// - `PackIndexTooSmall`: "index file … is too small".
/// - `UnsupportedPackIndexVersion`: "index file … is version N and is not
///   supported by this binary"; the detail is the version.
/// - `NonMonotonicPackIndex`: "non-monotonic index …": a fanout entry
///   smaller than the one before.
/// - `WrongPackIndexSize`: "wrong index v1 file size in …", or v2: the
///   size does not fit the number of objects the fanout table says. The
///   detail is the version.
pub const Error = error{
    PackIndexTooSmall,
    UnsupportedPackIndexVersion,
    NonMonotonicPackIndex,
    WrongPackIndexSize,
};

/// Reads the pack index `bytes` holds, checking it as git does when it
/// opens one. `bytes` must outlive the result.
pub fn parse(format: Format, bytes: []const u8, diag: ?*Diagnostics) Error!PackIndex {
    const h = format.byteLength();
    const version: u8 = if (bytes.len >= 8 and std.mem.eql(u8, bytes[0..4], magic)) v: {
        const v = std.mem.readInt(u32, bytes[4..8], .big);
        if (v != 2) {
            if (diag) |d| d.setDetail("{d}", .{v});
            return error.UnsupportedPackIndexVersion;
        }
        break :v 2;
    } else 1;
    const fanout_at: usize = if (version == 2) 8 else 0;
    if (bytes.len < fanout_at + 256 * 4 + 2 * h) return error.PackIndexTooSmall;
    var previous: u32 = 0;
    for (0..256) |i| {
        const n = std.mem.readInt(u32, bytes[fanout_at + 4 * i ..][0..4], .big);
        if (n < previous) return error.NonMonotonicPackIndex;
        previous = n;
    }
    const count = previous;
    const n: u64 = count;
    var idx: PackIndex = .{
        .bytes = bytes,
        .format = format,
        .version = version,
        .count = count,
        .fanout_at = fanout_at,
        .names_at = undefined,
        .crcs_at = 0,
        .offsets_at = undefined,
        .large_offsets_at = 0,
        .large_count = 0,
    };
    if (version == 1) {
        const want = 256 * 4 + n * (4 + h) + 2 * h;
        if (bytes.len != want) return wrongSize(1, diag);
        idx.offsets_at = 256 * 4;
        idx.names_at = 256 * 4 + 4;
    } else {
        const min = 8 + 256 * 4 + n * (h + 4 + 4) + 2 * h;
        // Room for a large offset for every object but the first, which
        // is at offset 12 in any pack.
        const max = min + (if (n > 0) n - 1 else 0) * 8;
        if (bytes.len < min or bytes.len > max) return wrongSize(2, diag);
        idx.names_at = 8 + 256 * 4;
        idx.crcs_at = idx.names_at + count * h;
        idx.offsets_at = idx.crcs_at + count * 4;
        idx.large_offsets_at = idx.offsets_at + count * 4;
        idx.large_count = (bytes.len - min) / 8;
    }
    return idx;
}

fn wrongSize(version: u8, diag: ?*Diagnostics) Error {
    if (diag) |d| d.setDetail("{d}", .{version});
    return error.WrongPackIndexSize;
}

/// The object ID of the `i`th object, in object ID order.
pub fn idAt(idx: *const PackIndex, i: u32) Id {
    std.debug.assert(i < idx.count);
    const h = idx.format.byteLength();
    const at = if (idx.version == 1) idx.names_at + @as(usize, i) * (4 + h) else idx.names_at + @as(usize, i) * h;
    return .fromBytes(idx.format, idx.bytes[at..][0..h]);
}

fn rawIdAt(idx: *const PackIndex, i: usize) []const u8 {
    const h = idx.format.byteLength();
    const at = if (idx.version == 1) idx.names_at + i * (4 + h) else idx.names_at + i * h;
    return idx.bytes[at..][0..h];
}

/// The position of the object `id`, if the pack holds it: a binary search
/// within the IDs the fanout table says begin with its first byte.
pub fn find(idx: *const PackIndex, id: Id) ?u32 {
    std.debug.assert(id.object_format == idx.format);
    const first = id.bytes[0];
    var lo: usize = if (first == 0) 0 else idx.fanout(first - 1);
    var hi: usize = idx.fanout(first);
    const want = id.slice();
    while (lo < hi) {
        const mid = lo + (hi - lo) / 2;
        switch (std.mem.order(u8, idx.rawIdAt(mid), 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(idx: *const PackIndex, b: u8) u32 {
    return std.mem.readInt(u32, idx.bytes[idx.fanout_at + 4 * @as(usize, b) ..][0..4], .big);
}

/// The `i`th object's 4-byte offset entry as stored: an offset, or, in a
/// version 2 index with its top bit set, an index into the large-offset
/// table.
pub fn rawOffsetAt(idx: *const PackIndex, i: u32) u32 {
    std.debug.assert(i < idx.count);
    const at = if (idx.version == 1)
        idx.offsets_at + @as(usize, i) * (4 + idx.format.byteLength())
    else
        idx.offsets_at + @as(usize, i) * 4;
    return std.mem.readInt(u32, idx.bytes[at..][0..4], .big);
}

/// Where in the pack the `i`th object's entry begins. A version 2 entry
/// pointing past the end of the large-offset table is
/// `BadLargeOffset`; the detail is the index it gave.
pub fn offsetAt(idx: *const PackIndex, i: u32, diag: ?*Diagnostics) error{BadLargeOffset}!u64 {
    const raw = idx.rawOffsetAt(i);
    if (idx.version == 1 or raw & 0x8000_0000 == 0) return raw;
    const large = raw & 0x7fff_ffff;
    return idx.largeOffset(large) orelse {
        if (diag) |d| d.setDetail("large offset {d} of {d}", .{ large, idx.large_count });
        return error.BadLargeOffset;
    };
}

/// The `k`th entry of the large-offset table, or null if there is none.
pub fn largeOffset(idx: *const PackIndex, k: usize) ?u64 {
    if (k >= idx.large_count) return null;
    return std.mem.readInt(u64, idx.bytes[idx.large_offsets_at + 8 * k ..][0..8], .big);
}

/// The CRC-32 of the `i`th object's entry as stored in the pack, which only
/// a version 2 index records.
pub fn crcAt(idx: *const PackIndex, i: u32) ?u32 {
    std.debug.assert(i < idx.count);
    if (idx.version == 1) return null;
    return std.mem.readInt(u32, idx.bytes[idx.crcs_at + 4 * @as(usize, i) ..][0..4], .big);
}

/// The copy of the pack's checksum the index ends with. git reads it from
/// the end of the file, whatever comes before.
pub fn packChecksum(idx: *const PackIndex) []const u8 {
    const h = idx.format.byteLength();
    return idx.bytes[idx.bytes.len - 2 * h ..][0..h];
}

/// The index's own checksum, its last bytes.
pub fn checksum(idx: *const PackIndex) []const u8 {
    const h = idx.format.byteLength();
    return idx.bytes[idx.bytes.len - h ..];
}

/// Whether the index's checksum is the hash of everything before it, as
/// `git verify-pack` checks and reading an object does not.
pub fn verifyChecksum(idx: *const PackIndex) bool {
    return checksumMatches(idx.format, idx.bytes);
}

/// Whether the last object-ID-sized bytes of `bytes` are the hash of the
/// rest, as packs, pack indexes and multi-pack-indexes all end.
pub fn checksumMatches(format: Format, bytes: []const u8) bool {
    const h = format.byteLength();
    if (bytes.len < h) return false;
    var digest: [object.max_byte_length]u8 = undefined;
    switch (format) {
        .sha1 => std.crypto.hash.Sha1.hash(bytes[0 .. bytes.len - h], digest[0..20], .{}),
        .sha256 => std.crypto.hash.sha2.Sha256.hash(bytes[0 .. bytes.len - h], digest[0..32], .{}),
    }
    return std.mem.eql(u8, digest[0..h], bytes[bytes.len - h ..]);
}

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 pack index git wrote finds every object git says the pack holds" {
    const gpa = testing.allocator;
    var repo = try fixture.Repo.init(gpa, testing.io);
    defer repo.deinit();
    for (0..12) |i| {
        var buf: [64]u8 = undefined;
        try repo.commitFile("f", try std.fmt.bufPrint(&buf, "version {d}\n", .{i}), "c");
    }
    for ([_][]const u8{ "2", "1" }) |version| {
        var arg_buf: [32]u8 = undefined;
        try repo.git(&.{ "-c", try std.fmt.bufPrint(&arg_buf, "pack.indexVersion={s}", .{version}), "repack", "-adq" });
        const bytes = try packs.readOnlyIndex(&repo);
        defer gpa.free(bytes);
        const idx = try parse(repo.object_format, bytes, null);
        try testing.expectEqual(version[0] - '0', idx.version);

        const listing = try repo.outputWithInput(&.{"show-index"}, bytes);
        defer gpa.free(listing);
        var lines = std.mem.splitScalar(u8, std.mem.trimEnd(u8, listing, "\n"), '\n');
        var i: u32 = 0;
        while (lines.next()) |line| : (i += 1) {
            var fields = std.mem.splitScalar(u8, line, ' ');
            const offset = try std.fmt.parseInt(u64, fields.next().?, 10);
            const id = try Id.parseHex(repo.object_format, fields.next().?);
            try testing.expect(Id.eql(id, idx.idAt(i)));
            try testing.expectEqual(i, idx.find(id).?);
            try testing.expectEqual(offset, try idx.offsetAt(i, null));
            if (fields.next()) |crc| {
                try testing.expectEqual(try std.fmt.parseInt(u32, crc[1 .. crc.len - 1], 16), idx.crcAt(i).?);
            } else try testing.expectEqual(null, idx.crcAt(i));
        }
        try testing.expectEqual(idx.count, i);
        try testing.expect(idx.verifyChecksum());
        var missing = idx.idAt(0);
        missing.bytes[missing.object_format.byteLength() - 1] ^= 1;
        if (idx.find(missing)) |_| return error.TestUnexpectedResult;
    }
}

test "large offsets come from the 8-byte table, and a bad one is an error" {
    const gpa = testing.allocator;
    for ([_]Format{ .sha1, .sha256 }) |format| {
        const bytes = try packs.craftIndex(gpa, format, &.{ 12, 0x8000_0000, 0x8000_0001, 0x8000_0005 }, &.{ 0x1_0000_0000, 0x7_ffff_ffff });
        defer gpa.free(bytes);
        const idx = try parse(format, bytes, null);
        try testing.expectEqual(4, idx.count);
        try testing.expectEqual(2, idx.large_count);
        try testing.expectEqual(12, try idx.offsetAt(0, null));
        try testing.expectEqual(0x1_0000_0000, try idx.offsetAt(1, null));
        try testing.expectEqual(0x7_ffff_ffff, try idx.offsetAt(2, null));
        var diag: Diagnostics = .{};
        try testing.expectError(error.BadLargeOffset, idx.offsetAt(3, &diag));
        try testing.expectEqualStrings("large offset 5 of 2", diag.detail());
        try testing.expect(idx.verifyChecksum());
    }
}

test "a pack index is refused as git refuses it" {
    const gpa = testing.allocator;
    const format: Format = .sha1;
    const good = try packs.craftIndex(gpa, format, &.{ 12, 40, 80 }, &.{});
    defer gpa.free(good);
    _ = try parse(format, good, null);
    try testing.expectError(error.PackIndexTooSmall, parse(format, good[0..1000], null));
    try testing.expectError(error.WrongPackIndexSize, parse(format, good[0 .. good.len - 1], null));
    // Two large offsets' worth of room is allowed for three objects, and
    // no more.
    const longer = try std.mem.concat(gpa, u8, &.{ good, &@as([17]u8, @splat(0)) });
    defer gpa.free(longer);
    _ = try parse(format, longer[0 .. good.len + 16], null);
    try testing.expectError(error.WrongPackIndexSize, parse(format, longer, null));
    const bad = try gpa.dupe(u8, good);
    defer gpa.free(bad);
    bad[7] = 3;
    var diag: Diagnostics = .{};
    try testing.expectError(error.UnsupportedPackIndexVersion, parse(format, bad, &diag));
    try testing.expectEqualStrings("3", diag.detail());
    bad[7] = 2;
    bad[0] ^= 1; // no longer the magic, so a version 1 fanout that decreases
    try testing.expectError(error.NonMonotonicPackIndex, parse(format, bad, null));
}

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 idx = parse(format, bytes, null) catch continue;
        var i: u32 = 0;
        while (i < idx.count) : (i += 1) {
            const id = idx.idAt(i);
            _ = idx.find(id);
            _ = idx.offsetAt(i, null) catch {};
            _ = idx.crcAt(i);
        }
        _ = idx.verifyChecksum();
    }
}

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