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

//! The split index: the `link` extension of the index, read from its
//! bytes, and the shared index's entries and the main file's made into
//! one list.
//!
//! gitformat-index(5) describes the extension: the object ID of the
//! shared index, `sharedindex.<id>` beside the index file (all zeros for
//! none), then an EWAH bitmap of the shared index's entries to delete and
//! one of those to replace. The main file's entries replace the shared
//! index's entries the replace bitmap names, in order, and may have empty
//! paths standing for theirs; the rest are added. Deleted entries are
//! dropped after the replacing, so a replaced entry can be deleted too.
//!
//! What git says when the parts do not fit together, found by writing
//! malformed extensions:
//!
//! - fewer bytes than an object ID: "corrupt link extension (too short)";
//! - a bitmap that cannot be read: the bitmap's complaint, then "corrupt
//!   delete bitmap in link extension" or "corrupt replace bitmap in link
//!   extension";
//! - bytes after the bitmaps: "garbage at the end of link extension";
//!   each of those then "index file corrupt";
//! - a bit past the shared index's entries: "position for delete N
//!   exceeds base index size M" or "position for replacement N exceeds
//!   base index size M";
//! - more bits in the replace bitmap than the main file has entries: "too
//!   many replacements (N vs N)";
//! - an added entry with an empty path: "corrupt link extension, entry N
//!   should have non-zero length name".
//!
//! The bitmaps' bit counts limit nothing: git acts on every set bit.

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

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

/// The `link` extension.
pub const Link = struct {
    /// The shared index's object ID; all zeros when there is none.
    shared_id: Id,
    delete: ewah.Bitmap,
    replace: ewah.Bitmap,

    /// Whether there is a shared index to read.
    pub fn hasSharedIndex(l: *const Link) bool {
        return !std.mem.allEqual(u8, l.shared_id.slice(), 0);
    }
};

/// Why a `link` extension could not be read, each in git's words:
/// `LinkTooShort`, `CorruptDeleteBitmap` and `CorruptReplaceBitmap` (the
/// detail is the bitmap's own complaint), and `LinkGarbage`.
pub const ParseError = error{ LinkTooShort, CorruptDeleteBitmap, CorruptReplaceBitmap, LinkGarbage };

/// Reads the `link` extension's contents, in `format`.
pub fn parse(format: Format, data: []const u8, diag: ?*Diagnostics) ParseError!Link {
    const n = format.byteLength();
    if (data.len < n) return error.LinkTooShort;
    const id: Id = .fromBytes(format, data[0..n]);
    var pos = n;
    const delete = ewah.parse(data[pos..], diag) catch return error.CorruptDeleteBitmap;
    pos += delete.len;
    const replace = ewah.parse(data[pos..], diag) catch return error.CorruptReplaceBitmap;
    pos += replace.len;
    if (pos != data.len) return error.LinkGarbage;
    return .{ .shared_id = id, .delete = delete.bitmap, .replace = replace.bitmap };
}

/// Why the two files of a split index do not make one list, each in git's
/// words, which the diagnostic's detail holds in full:
/// `DeletePositionOutOfRange`, `ReplacePositionOutOfRange`,
/// `TooManyReplacements` and `EmptySplitEntryName`.
pub const MergeError = error{
    DeletePositionOutOfRange,
    ReplacePositionOutOfRange,
    TooManyReplacements,
    EmptySplitEntryName,
} || Allocator.Error;

/// The shared index's entries with the main file's applied as `link`
/// says, sorted as the index keeps them, allocated with `arena`, each
/// marked with where it came from.
pub fn merge(arena: Allocator, shared: []const Entry, main: []const Entry, link: Link, diag: ?*Diagnostics) MergeError![]Entry {
    const out = try arena.alloc(Entry, shared.len + main.len);
    const deleted = try arena.alloc(bool, shared.len);
    @memset(deleted, false);
    for (shared, out[0..shared.len]) |s, *o| {
        o.* = s;
        o.origin = .shared;
    }

    var it = link.delete.iterator();
    while (it.next()) |p| {
        if (p >= shared.len) return fail(diag, error.DeletePositionOutOfRange, "position for delete {d} exceeds base index size {d}", .{ p, shared.len });
        deleted[@intCast(p)] = true;
    }

    var used: usize = 0;
    it = link.replace.iterator();
    while (it.next()) |p| {
        if (p >= shared.len) return fail(diag, error.ReplacePositionOutOfRange, "position for replacement {d} exceeds base index size {d}", .{ p, shared.len });
        if (used == main.len) return fail(diag, error.TooManyReplacements, "too many replacements ({d} vs {d})", .{ used, main.len });
        const i: usize = @intCast(p);
        var r = main[used];
        if (r.path.len == 0) r.path = shared[i].path;
        r.origin = .replacement;
        out[i] = r;
        used += 1;
    }

    var n: usize = 0;
    for (out[0..shared.len], deleted) |e, d| {
        if (d) continue;
        out[n] = e;
        n += 1;
    }
    for (main[used..], used..) |e, i| {
        if (e.path.len == 0) return fail(diag, error.EmptySplitEntryName, "corrupt link extension, entry {d} should have non-zero length name", .{i});
        out[n] = e;
        out[n].origin = .own;
        n += 1;
    }
    const merged = out[0..n];
    std.mem.sort(Entry, merged, {}, Entry.lessThan);
    return merged;
}

fn fail(diag: ?*Diagnostics, err: MergeError, comptime fmt: []const u8, args: anytype) MergeError {
    if (diag) |d| d.setDetail(fmt, args);
    return err;
}

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

const testing = std.testing;

fn entry(path: []const u8, size: u32) Entry {
    return .{
        .ctime = .{ .seconds = 0, .nanoseconds = 0 },
        .mtime = .{ .seconds = 0, .nanoseconds = 0 },
        .dev = 0,
        .ino = 0,
        .mode = 0o100644,
        .uid = 0,
        .gid = 0,
        .size = size,
        .id = .zero(.sha1),
        .flags = 0,
        .extended_flags = 0,
        .path = path,
    };
}

fn bitmapBytes(comptime literal: u64) [28]u8 {
    var b: [28]u8 = undefined;
    std.mem.writeInt(u32, b[0..4], 64, .big);
    std.mem.writeInt(u32, b[4..8], 2, .big);
    std.mem.writeInt(u64, b[8..16], 0x0000_0002_0000_0000, .big);
    std.mem.writeInt(u64, b[16..24], literal, .big);
    std.mem.writeInt(u32, b[24..28], 0, .big);
    return b;
}

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

test "a split index's entries are replaced, deleted and added as the link says" {
    var arena: std.heap.ArenaAllocator = .init(testing.allocator);
    defer arena.deinit();
    const a = arena.allocator();
    const zero: [20]u8 = @splat(0);
    const id: [20]u8 = @splat(1);
    // Delete the third shared entry; replace the first and second.
    const data = id ++ bitmapBytes(0b100) ++ bitmapBytes(0b011);
    const link = try parse(.sha1, &data, null);
    try testing.expect(link.hasSharedIndex());
    const shared = [_]Entry{ entry("a", 1), entry("b", 1), entry("c", 1), entry("d", 1) };
    const main = [_]Entry{ entry("", 2), entry("b", 2), entry("bb", 3) };
    const merged = try merge(a, &shared, &main, link, null);
    try testing.expectEqual(4, merged.len);
    try testing.expectEqualStrings("a", merged[0].path);
    try testing.expectEqual(2, merged[0].size);
    try testing.expectEqual(.replacement, merged[0].origin);
    try testing.expectEqualStrings("bb", merged[2].path);
    try testing.expectEqual(.own, merged[2].origin);
    try testing.expectEqual(.shared, merged[3].origin);
    try testing.expectEqualStrings("d", merged[3].path);

    var d: Diagnostics = .{};
    const too_many = id ++ bitmapBytes(0) ++ bitmapBytes(0b1111);
    try testing.expectError(error.TooManyReplacements, merge(a, &shared, &main, try parse(.sha1, &too_many, null), &d));
    try testing.expectEqualStrings("too many replacements (3 vs 3)", d.detail());
    const past = id ++ bitmapBytes(1 << 7) ++ bitmapBytes(0);
    try testing.expectError(error.DeletePositionOutOfRange, merge(a, &shared, &main, try parse(.sha1, &past, null), &d));
    try testing.expectEqualStrings("position for delete 7 exceeds base index size 4", d.detail());
    const none = zero ++ bitmapBytes(0) ++ bitmapBytes(0);
    try testing.expectError(error.EmptySplitEntryName, merge(a, &shared, &main, try parse(.sha1, &none, null), &d));
    try testing.expectEqualStrings("corrupt link extension, entry 0 should have non-zero length name", d.detail());

    try testing.expectError(error.LinkTooShort, parse(.sha1, id[0..15], null));
    try testing.expectError(error.CorruptDeleteBitmap, parse(.sha1, &(id ++ [_]u8{ 0, 0, 0, 0 }), &d));
    try testing.expectEqualStrings("eof before length", d.detail());
    try testing.expectError(error.LinkGarbage, parse(.sha1, &(data ++ [_]u8{0}), null));
}

test "fuzz: link extensions" {
    try fuzz_input.fuzz({}, struct {
        fn one(_: void, smith: *testing.Smith) anyerror!void {
            var buffer: [1024]u8 = undefined;
            const input = @import("../testing/fuzz.zig").bytes(smith, &buffer);
            var arena: std.heap.ArenaAllocator = .init(testing.allocator);
            defer arena.deinit();
            for ([_]Format{ .sha1, .sha256 }) |format| {
                const link = parse(format, input, null) catch continue;
                const shared = [_]Entry{ entry("a", 1), entry("b", 1), entry("c", 1) };
                const main = [_]Entry{ entry("", 2), entry("d", 2) };
                _ = merge(arena.allocator(), &shared, &main, link, null) catch continue;
            }
        }
    }.one, .{ .corpus = &.{
        @embedFile("../fuzz/index-link"),
        @embedFile("../fuzz/index-link-sha256"),
    } });
}