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

//! One index file read from its bytes, with no I/O: the header, the
//! index entries, the extensions as signatures and contents, and the
//! trailing checksum. What the extensions mean, and how a split index's
//! two files make one list of entries, is `Index`'s business.
//!
//! The format is gitformat-index(5)'s. What git does where that document
//! is silent was found by writing malformed index files and asking
//! `git ls-files`:
//!
//! - A file shorter than its header and checksum is "index file smaller
//!   than expected"; a wrong signature is "bad signature 0x…" and a
//!   version other than 2, 3 and 4 "bad index version N".
//! - The checksum is not checked when git reads an index. `checksum`
//!   says what it is, and `verifyChecksum` checks it for a caller who
//!   wants that; `index.skipHash` writes all zeros, which mean "not
//!   computed".
//! - An entry with the extended flag set has the extended flags after it
//!   whatever the version; extended flags with a bit set other than
//!   skip-worktree and intent-to-add are "unknown index entry format
//!   0x…", the flags shown shifted into the upper half.
//! - In version 4 the first entry's prefix length is ignored, since
//!   there is no earlier path to take a prefix of; git writes the whole
//!   length of the previous path at the start of each block of the index
//!   entry offset table, so that each block can be read alone. A later
//!   entry asking for more of the previous path than it has is
//!   "malformed name field in the index, near path '<previous>'".
//! - Extensions are read while at least eight bytes remain before the
//!   checksum. One whose signature begins with an upper-case letter and
//!   which git does not know is passed over ("ignoring XXXX extension");
//!   any other unknown one is "index uses XXXX extension, which we do not
//!   understand".
//!
//! Where git reads past the end of what it was given — an entry or an
//! extension running into the checksum, a path length that disagrees with
//! the path — it shows whatever it found there, or crashes. This refuses
//! the file instead (`MalformedIndex`), saying where.

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

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

/// "DIRC", for "dircache".
pub const signature = "DIRC";
/// The size of the header: signature, version and entry count.
pub const header_len = 12;

/// When a file last changed, as `stat(2)` gave it, cut to 32 bits.
pub const Timestamp = struct {
    seconds: u32,
    nanoseconds: u32,
};

/// One path in the index.
pub const Entry = struct {
    /// When the file's metadata last changed.
    ctime: Timestamp,
    /// When the file's contents last changed.
    mtime: Timestamp,
    dev: u32,
    ino: u32,
    /// The mode as recorded, which git shows in octal whatever it is.
    mode: u32,
    uid: u32,
    gid: u32,
    /// The file's size on disk, cut to 32 bits.
    size: u32,
    /// The object the entry names.
    id: Id,
    /// The 16-bit flags field: assume-valid, extended, the stage and the
    /// length of the path.
    flags: u16,
    /// The extended flags (versions 3 and 4, when `extended_flag` is set):
    /// skip-worktree and intent-to-add; zero otherwise.
    extended_flags: u16,
    /// The path from the top of the working tree; a sparse directory's
    /// ends in `/`. In a split index's main file, a replacement may have
    /// an empty path, standing for the one it replaces.
    path: []const u8,
    /// Where a split index's entry came from: the shared index, the main
    /// file as a replacement for one of the shared index's, or the main
    /// file as an addition (or an index that is not split).
    origin: Origin = .own,
    /// Whether the index's fsmonitor cache vouches for the entry: git
    /// takes the working tree file to be unchanged when `core.fsmonitor`
    /// is set and the monitor agrees.
    fsmonitor_valid: bool = false,

    /// The flag git calls assume-valid, which `git update-index
    /// --assume-unchanged` sets.
    pub const assume_valid_flag: u16 = 0x8000;
    /// Set when extended flags follow.
    pub const extended_flag: u16 = 0x4000;
    /// The stage's bits within `flags`.
    pub const stage_mask: u16 = 0x3000;
    /// The path length's bits within `flags`; this value when the path is
    /// that long or longer.
    pub const name_mask: u16 = 0x0fff;
    /// The extended flag sparse checkout sets for a path outside it.
    pub const skip_worktree_flag: u16 = 0x4000;
    /// The extended flag `git add -N` sets.
    pub const intent_to_add_flag: u16 = 0x2000;
    /// The extended flags git knows.
    pub const known_extended_flags: u16 = skip_worktree_flag | intent_to_add_flag;

    /// Which version of a conflicted path this is: 0 when it is not
    /// conflicted, 1 to 3 for the common ancestor's, ours and theirs.
    pub fn stage(e: *const Entry) u2 {
        return @intCast((e.flags & stage_mask) >> 12);
    }

    /// Whether git is to take the working tree file as unchanged.
    pub fn assumeValid(e: *const Entry) bool {
        return e.flags & assume_valid_flag != 0;
    }

    /// Whether the path is outside a sparse checkout.
    pub fn skipWorktree(e: *const Entry) bool {
        return e.extended_flags & skip_worktree_flag != 0;
    }

    /// Whether the path was added with `git add -N`, its contents not yet.
    pub fn intentToAdd(e: *const Entry) bool {
        return e.extended_flags & intent_to_add_flag != 0;
    }

    /// Whether this is a sparse directory: a directory outside a sparse
    /// checkout, standing for every path in its tree.
    pub fn isSparseDirectory(e: *const Entry) bool {
        return e.mode == 0o040000 and e.skipWorktree() and e.path.len != 0 and e.path[e.path.len - 1] == '/';
    }

    /// Orders entries as the index keeps them: by path, compared as
    /// unsigned bytes, then by stage.
    pub fn lessThan(_: void, a: Entry, b: Entry) bool {
        return switch (std.mem.order(u8, a.path, b.path)) {
            .lt => true,
            .gt => false,
            .eq => a.stage() < b.stage(),
        };
    }
};

/// Where an entry of a split index came from.
pub const Origin = enum {
    /// Its own file: an index that is not split, or an entry a split
    /// index's main file adds.
    own,
    /// The shared index, unchanged.
    shared,
    /// The main file, replacing the shared index's entry for its path.
    /// git marks these when it shows `--debug` flags.
    replacement,
};

/// One extension: its signature and its contents.
pub const Extension = struct {
    signature: [4]u8,
    data: []const u8,
    /// Where its signature is, from the start of the file.
    offset: usize,
};

/// The signatures of the extensions git knows.
pub const known_extensions = [_]*const [4]u8{ "TREE", "REUC", "link", "UNTR", "FSMN", "EOIE", "IEOT", "sdir" };

/// Whether git knows the extension `sig`.
pub fn isKnownExtension(sig: [4]u8) bool {
    for (known_extensions) |k| if (std.mem.eql(u8, k, &sig)) return true;
    return false;
}

/// One index file.
pub const File = struct {
    version: u32,
    entries: []Entry,
    /// Where each entry begins, from the start of the file, for checking
    /// an index entry offset table.
    entry_offsets: []u32,
    /// Where the entries end and the extensions begin.
    entries_end: usize,
    /// Every extension, in the order they appear.
    extensions: []Extension,
    /// The optional extensions git does not know, which it passes over
    /// with a word; also in `extensions`.
    ignored: [][4]u8,
    /// The trailing checksum.
    checksum: []const u8,

    /// The extension with signature `sig`, if there is one; the last if
    /// there are several.
    pub fn extension(f: *const File, sig: *const [4]u8) ?Extension {
        var found: ?Extension = null;
        for (f.extensions) |e| {
            if (std.mem.eql(u8, &e.signature, sig)) found = e;
        }
        return found;
    }
};

/// Why an index file could not be read. Those git has words for:
///
/// - `IndexTooSmall`: "index file smaller than expected".
/// - `BadIndexSignature`: "bad signature 0x%08x"; the detail is the
///   signature in hexadecimal, read in the machine's byte order as git
///   reads it.
/// - `UnsupportedIndexVersion`: "bad index version N"; the detail is N.
/// - `UnknownEntryFormat`: "unknown index entry format 0x%08x"; the detail
///   is the value in hexadecimal.
/// - `MalformedEntryName`: "malformed name field in the index, near path
///   '…'"; the detail is the path.
/// - `UnknownRequiredExtension`: "index uses XXXX extension, which we do
///   not understand"; the detail is the four bytes of the signature.
///
/// And `MalformedIndex`, for what git does not check: the detail says
/// what, and the diagnostic's offset where.
pub const ParseError = error{
    IndexTooSmall,
    BadIndexSignature,
    UnsupportedIndexVersion,
    UnknownEntryFormat,
    MalformedEntryName,
    UnknownRequiredExtension,
    MalformedIndex,
} || Allocator.Error;

/// The fixed part of an entry before its path, in `format`: ten 32-bit
/// stat fields, the object ID and the flags.
pub fn fixedEntryLen(format: Format) usize {
    return 40 + format.byteLength() + 2;
}

/// Reads the index file `bytes`, whose object IDs are in `format`. Entry
/// paths point into `bytes` where they can, so it must outlive what is
/// returned; everything else is allocated with `arena`, which the caller
/// frees all at once.
pub fn parse(arena: Allocator, format: Format, bytes: []const u8, diag: ?*Diagnostics) ParseError!File {
    const hash_len = format.byteLength();
    if (bytes.len < header_len + hash_len) return error.IndexTooSmall;
    if (!std.mem.eql(u8, bytes[0..4], signature)) {
        // git shows the four bytes as a number in the machine's own byte
        // order.
        if (diag) |d| d.setDetail("0x{x:0>8}", .{std.mem.readInt(u32, bytes[0..4], builtin.cpu.arch.endian())});
        return error.BadIndexSignature;
    }
    const version = std.mem.readInt(u32, bytes[4..8], .big);
    if (version < 2 or version > 4) {
        if (diag) |d| d.setDetail("{d}", .{version});
        return error.UnsupportedIndexVersion;
    }
    const count = std.mem.readInt(u32, bytes[8..12], .big);
    const end = bytes.len - hash_len;
    const fixed = fixedEntryLen(format);
    // Every entry takes at least its fixed part and a byte of path, or
    // the NUL that ends it, so a count that could not fit is refused
    // before anything is allocated for it.
    if (@as(u64, count) * (fixed + 1) > end - header_len)
        return malformed(diag, header_len, "{d} entries cannot fit in {d} bytes", .{ count, end - header_len });

    const entries = try arena.alloc(Entry, count);
    const offsets = try arena.alloc(u32, count);
    var pos: usize = header_len;
    var previous: []const u8 = "";
    var name_buffer: std.ArrayList(u8) = .empty;
    for (entries, offsets, 0..) |*e, *offset, i| {
        offset.* = @intCast(pos);
        if (end - pos < fixed) return malformed(diag, pos, "entry {d} runs past the end", .{i});
        const b = bytes[pos..];
        e.* = .{
            .ctime = .{ .seconds = be32(b[0..]), .nanoseconds = be32(b[4..]) },
            .mtime = .{ .seconds = be32(b[8..]), .nanoseconds = be32(b[12..]) },
            .dev = be32(b[16..]),
            .ino = be32(b[20..]),
            .mode = be32(b[24..]),
            .uid = be32(b[28..]),
            .gid = be32(b[32..]),
            .size = be32(b[36..]),
            .id = .fromBytes(format, b[40..][0..hash_len]),
            .flags = std.mem.readInt(u16, b[40 + hash_len ..][0..2], .big),
            .extended_flags = 0,
            .path = "",
        };
        var p = pos + fixed;
        if (e.flags & Entry.extended_flag != 0) {
            if (end - p < 2) return malformed(diag, pos, "entry {d} runs past the end", .{i});
            e.extended_flags = std.mem.readInt(u16, bytes[p..][0..2], .big);
            p += 2;
            if (e.extended_flags & ~Entry.known_extended_flags != 0) {
                if (diag) |d| d.setDetail("0x{x:0>8}", .{@as(u32, e.extended_flags) << 16});
                return error.UnknownEntryFormat;
            }
        }
        const name_field = e.flags & Entry.name_mask;
        if (version == 4) {
            const strip_start = p;
            const strip = readVarint(bytes[0..end], &p) orelse
                return malformed(diag, strip_start, "entry {d}'s prefix length runs past the end", .{i});
            const nul = std.mem.findScalar(u8, bytes[p..end], 0) orelse
                return malformed(diag, p, "entry {d}'s path runs past the end", .{i});
            const suffix = bytes[p..][0..nul];
            const keep = if (i == 0) 0 else blk: {
                if (strip > previous.len) {
                    if (diag) |d| d.setDetail("{s}", .{previous});
                    return error.MalformedEntryName;
                }
                break :blk previous.len - @as(usize, @intCast(strip));
            };
            name_buffer.clearRetainingCapacity();
            try name_buffer.appendSlice(arena, previous[0..keep]);
            try name_buffer.appendSlice(arena, suffix);
            const path = try arena.dupe(u8, name_buffer.items);
            if (!nameFits(name_field, path.len)) {
                if (diag) |d| d.setDetail("{s}", .{path});
                return error.MalformedEntryName;
            }
            e.path = path;
            previous = path;
            pos = p + nul + 1;
        } else {
            const nul = std.mem.findScalar(u8, bytes[p..end], 0) orelse
                return malformed(diag, p, "entry {d}'s path runs past the end", .{i});
            if (!nameFits(name_field, nul))
                return malformed(diag, pos, "entry {d}'s path is {d} bytes, where its flags say {d}", .{ i, nul, name_field });
            e.path = bytes[p..][0..nul];
            // One to eight NULs, to a multiple of eight bytes.
            const len = (p - pos + nul + 8) & ~@as(usize, 7);
            if (end - pos < len) return malformed(diag, pos, "entry {d} runs past the end", .{i});
            pos += len;
        }
    }
    const entries_end = pos;

    var extensions: std.ArrayList(Extension) = .empty;
    var ignored: std.ArrayList([4]u8) = .empty;
    while (end - pos >= 8) {
        const sig = bytes[pos..][0..4].*;
        const size = be32(bytes[pos + 4 ..]);
        const known = isKnownExtension(sig);
        if (!known and !(sig[0] >= 'A' and sig[0] <= 'Z')) {
            if (diag) |d| {
                d.offset = pos;
                d.setDetail("{s}", .{&sig});
            }
            return error.UnknownRequiredExtension;
        }
        const available = end - pos - 8;
        if (!known) {
            // git passes over it, however long it says it is, and stops
            // reading extensions if that takes it to the end.
            try ignored.append(arena, sig);
            try extensions.append(arena, .{ .signature = sig, .data = bytes[pos + 8 ..][0..@min(size, available)], .offset = pos });
            if (size > available) break;
            pos += 8 + size;
            continue;
        }
        if (size > available) return malformed(diag, pos, "the {s} extension runs past the end", .{&sig});
        try extensions.append(arena, .{ .signature = sig, .data = bytes[pos + 8 ..][0..size], .offset = pos });
        pos += 8 + size;
    }
    return .{
        .version = version,
        .entries = entries,
        .entry_offsets = offsets,
        .entries_end = entries_end,
        .extensions = try extensions.toOwnedSlice(arena),
        .ignored = try ignored.toOwnedSlice(arena),
        .checksum = bytes[end..],
    };
}

/// Whether a path of `len` bytes agrees with the length its flags give.
fn nameFits(field: u16, len: usize) bool {
    if (field == Entry.name_mask) return len >= Entry.name_mask;
    return len == field;
}

fn be32(b: []const u8) u32 {
    return std.mem.readInt(u32, b[0..4], .big);
}

fn malformed(diag: ?*Diagnostics, offset: usize, comptime fmt: []const u8, args: anytype) ParseError {
    if (diag) |d| {
        d.offset = offset;
        d.setDetail(fmt, args);
    }
    return error.MalformedIndex;
}

/// Reads the variable-width integer at `bytes[pos.*..]`, advancing `pos`:
/// the encoding OFS_DELTA offsets use (gitformat-pack(5)), seven bits to
/// a byte, most significant first, each continuing byte adding one before
/// the next seven bits. Null if it runs past the end or past 64 bits.
pub fn readVarint(bytes: []const u8, pos: *usize) ?u64 {
    var p = pos.*;
    if (p >= bytes.len) return null;
    var c = bytes[p];
    p += 1;
    var v: u64 = c & 0x7f;
    while (c & 0x80 != 0) {
        if (p >= bytes.len) return null;
        if (v >= (1 << 57) - 1) return null;
        c = bytes[p];
        p += 1;
        v = ((v + 1) << 7) | (c & 0x7f);
    }
    pos.* = p;
    return v;
}

/// What checking a checksum found.
pub const ChecksumResult = enum {
    /// It is the hash of everything before it.
    valid,
    /// It is all zeros, as `index.skipHash` writes: not computed.
    skipped,
    /// It is neither.
    mismatch,
};

/// Checks the checksum at the end of `bytes`, an index file in `format`
/// at least as long as one.
pub fn verifyChecksum(format: Format, bytes: []const u8) ChecksumResult {
    const n = format.byteLength();
    const stored = bytes[bytes.len - n ..];
    if (std.mem.allEqual(u8, stored, 0)) return .skipped;
    var h: object.Hasher = .init(format);
    h.update(bytes[0 .. bytes.len - n]);
    const computed = h.final();
    return if (std.mem.eql(u8, computed.slice(), stored)) .valid else .mismatch;
}

// -- tests -----------------------------------------------------------------------

const testing = std.testing;

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

test "a version 2 index git wrote is read entry by entry" {
    var arena: std.heap.ArenaAllocator = .init(testing.allocator);
    defer arena.deinit();
    const bytes = @embedFile("../fuzz/index-v2");
    const f = try parse(arena.allocator(), .sha1, bytes, null);
    try testing.expectEqual(2, f.version);
    try testing.expect(f.entries.len > 0);
    for (f.entries[1..], f.entries[0 .. f.entries.len - 1]) |b, a| try testing.expect(Entry.lessThan({}, a, b));
    try testing.expectEqual(ChecksumResult.valid, verifyChecksum(.sha1, bytes));
}

test "a version 4 index's prefix-compressed paths are expanded" {
    var arena: std.heap.ArenaAllocator = .init(testing.allocator);
    defer arena.deinit();
    const f = try parse(arena.allocator(), .sha1, @embedFile("../fuzz/index-v4"), null);
    try testing.expectEqual(4, f.version);
    for (f.entries[1..], f.entries[0 .. f.entries.len - 1]) |b, a| try testing.expect(Entry.lessThan({}, a, b));
}

test "variable-width integers are read as OFS_DELTA offsets are" {
    var pos: usize = 0;
    try testing.expectEqual(5, readVarint(&.{0x05}, &pos));
    pos = 0;
    // 0x80 0x00 is 128: the continuing byte adds one before shifting.
    try testing.expectEqual(128, readVarint(&.{ 0x80, 0x00 }, &pos));
    try testing.expectEqual(2, pos);
    pos = 0;
    try testing.expectEqual(null, readVarint(&.{0x80}, &pos));
}

test "a malformed header is refused in git's words" {
    var arena: std.heap.ArenaAllocator = .init(testing.allocator);
    defer arena.deinit();
    const a = arena.allocator();
    var d: Diagnostics = .{};
    try testing.expectError(error.IndexTooSmall, parse(a, .sha1, "DIRC\x00\x00\x00\x02", &d));
    const zeros: [20]u8 = @splat(0);
    try testing.expectError(error.BadIndexSignature, parse(a, .sha1, "DRID\x00\x00\x00\x02\x00\x00\x00\x00" ++ zeros, &d));
    try testing.expectEqualStrings(if (builtin.cpu.arch.endian() == .little) "0x44495244" else "0x44524944", d.detail());
    try testing.expectError(error.UnsupportedIndexVersion, parse(a, .sha1, "DIRC\x00\x00\x00\x05\x00\x00\x00\x00" ++ zeros, &d));
    try testing.expectEqualStrings("5", d.detail());
    try testing.expectError(error.MalformedIndex, parse(a, .sha1, "DIRC\x00\x00\x00\x02\x00\x00\x00\x02" ++ zeros, &d));
    try testing.expectError(error.UnknownRequiredExtension, parse(a, .sha1, "DIRC\x00\x00\x00\x02\x00\x00\x00\x00abcd\x00\x00\x00\x00" ++ zeros, &d));
    try testing.expectEqualStrings("abcd", d.detail());
    const f = try parse(a, .sha1, "DIRC\x00\x00\x00\x02\x00\x00\x00\x00ABCD\x00\x00\x00\x09xy" ++ zeros, &d);
    try testing.expectEqual(1, f.ignored.len);
    try testing.expectEqual(ChecksumResult.skipped, verifyChecksum(.sha1, "DIRC\x00\x00\x00\x02\x00\x00\x00\x00" ++ zeros));
}

test "fuzz: index files" {
    try fuzz_input.fuzz({}, struct {
        fn one(_: void, smith: *testing.Smith) anyerror!void {
            var buffer: [4096]u8 = undefined;
            const input = @import("../testing/fuzz.zig").bytes(smith, &buffer);
            for ([_]Format{ .sha1, .sha256 }) |format| {
                var arena: std.heap.ArenaAllocator = .init(testing.allocator);
                defer arena.deinit();
                const f = parse(arena.allocator(), format, input, null) catch continue;
                for (f.entries) |e| {
                    _ = e.stage();
                    _ = e.isSparseDirectory();
                }
                _ = verifyChecksum(format, input);
            }
        }
    }.one, .{ .corpus = &.{
        @embedFile("../fuzz/index-v2"),
        @embedFile("../fuzz/index-v4"),
        @embedFile("../fuzz/index-conflict"),
        @embedFile("../fuzz/index-split"),
    } });
}