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

//! The `packed-refs` file: many refs in one file, each on a line of its
//! own as an object ID, a space and the name, with a `^` line after an
//! annotated tag giving the object it peels to.
//!
//!     # pack-refs with: peeled fully-peeled sorted
//!     4a298c2be86322f047cf44cef2d85c5426e59474 refs/heads/main
//!     23955d658730798c8c89f41fe773f25630d85138 refs/tags/v1
//!     ^4a298c2be86322f047cf44cef2d85c5426e59474
//!
//! These are git's observed rules, from files written by hand and read
//! back with `git for-each-ref` and `git show-ref -d`:
//!
//! - Only the first line may be the header, `# pack-refs with:` and the
//!   traits separated by spaces. Any other line beginning `#` is an
//!   "unexpected line", as is an empty line.
//! - A ref line is exactly as many hexadecimal digits as an object ID
//!   has, one blank (a space, a tab or a carriage return), and the name,
//!   which is the rest of the line: a CRLF file's names end in a carriage
//!   return, and are then broken names. A missing name, or anything else
//!   that is not digits and a blank, is an unexpected line.
//! - A peel line is `^` and the digits of an object ID and nothing else,
//!   straight after a ref line.
//! - Every line, the last included, ends in a line feed; one that does
//!   not is an "unterminated line".
//! - A peel line is believed whatever the traits say, and whatever the ref
//!   names; a ref without one is peeled by reading its object. The traits
//!   change nothing that can be seen, except `sorted`: git trusts a file
//!   that says it is sorted and reads it in the order it is in, and sorts
//!   one that does not say so.
//! - Whether a name is well formed is not this file's business: it is
//!   kept as it is, for the ref store to judge when it comes to the name
//!   (`name.isSafe`).
//!
//! Where git reads a single ref from a file it trusts to be sorted, it
//! searches the file rather than reading all of it, so it passes over a
//! malformed line it does not come to; this reader refuses a malformed
//! file whole.

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

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

/// The traits a header can declare.
pub const Traits = struct {
    peeled: bool = false,
    fully_peeled: bool = false,
    sorted: bool = false,
};

/// One ref from the file.
pub const Entry = struct {
    /// The name, as written; a slice of the file's contents.
    name: []const u8,
    id: Id,
    /// The object the `^` line after it says it peels to.
    peeled: ?Id,
};

/// A `packed-refs` file, read. The entries are slices of the contents,
/// which must outlive it.
pub const PackedRefs = struct {
    traits: Traits,
    /// In order of name, unless the file said it was sorted when it was
    /// not, in which case in the file's order, as git reads it.
    entries: []Entry,

    /// Frees the entries.
    pub fn deinit(p: *PackedRefs, gpa: Allocator) void {
        gpa.free(p.entries);
        p.* = undefined;
    }

    /// The entry named `name`, found as git finds it: by binary search in
    /// a file that says it is sorted, and by looking at every entry in one
    /// that does not (which has been sorted, so the search is the same).
    pub fn find(p: *const PackedRefs, name: []const u8) ?*const Entry {
        var lo: usize = 0;
        var hi: usize = p.entries.len;
        while (lo < hi) {
            const mid = lo + (hi - lo) / 2;
            switch (std.mem.order(u8, p.entries[mid].name, name)) {
                .lt => lo = mid + 1,
                .gt => hi = mid,
                .eq => return &p.entries[mid],
            }
        }
        return null;
    }
};

/// Why a `packed-refs` file could not be read:
///
/// - `UnexpectedPackedRefsLine`: "unexpected line in packed-refs"; the
///   diagnostic's detail is the line and its `line` the line number.
/// - `UnterminatedPackedRefsLine`: "unterminated line in packed-refs":
///   the last line has no line feed; the detail is the line.
pub const Error = Allocator.Error || error{ UnexpectedPackedRefsLine, UnterminatedPackedRefsLine };

const header_prefix = "# pack-refs with:";

/// Reads a `packed-refs` file's contents.
pub fn parse(gpa: Allocator, format: object.Format, contents: []const u8, diag: ?*Diagnostics) Error!PackedRefs {
    var entries: std.ArrayList(Entry) = .empty;
    errdefer entries.deinit(gpa);
    var traits: Traits = .{};
    var rest = contents;
    var line_number: u32 = 0;
    const hex_len = format.hexLength();
    // A peel line belongs to the ref line just before it, and to no other.
    var last_was_ref = false;
    while (rest.len != 0) {
        line_number += 1;
        const nl = std.mem.findScalar(u8, rest, '\n') orelse {
            if (diag) |d| {
                d.line = line_number;
                d.setDetail("{s}", .{rest});
            }
            return error.UnterminatedPackedRefsLine;
        };
        const line = rest[0..nl];
        rest = rest[nl + 1 ..];
        if (line_number == 1) {
            if (std.mem.cutPrefix(u8, line, header_prefix)) |words| {
                last_was_ref = false;
                var it = std.mem.tokenizeScalar(u8, words, ' ');
                while (it.next()) |w| {
                    if (std.mem.eql(u8, w, "peeled")) traits.peeled = true;
                    if (std.mem.eql(u8, w, "fully-peeled")) traits.fully_peeled = true;
                    if (std.mem.eql(u8, w, "sorted")) traits.sorted = true;
                }
                continue;
            }
        }
        if (line.len != 0 and line[0] == '^') {
            const id = if (line.len == 1 + hex_len) Id.parseHex(format, line[1..]) catch null else null;
            if (id == null or !last_was_ref) return unexpected(diag, line, line_number);
            entries.items[entries.items.len - 1].peeled = id;
            last_was_ref = false;
            continue;
        }
        if (line.len < hex_len + 2) return unexpected(diag, line, line_number);
        const id = Id.parseHex(format, line[0..hex_len]) catch return unexpected(diag, line, line_number);
        switch (line[hex_len]) {
            ' ', '\t', '\r' => {},
            else => return unexpected(diag, line, line_number),
        }
        try entries.append(gpa, .{ .name = line[hex_len + 1 ..], .id = id, .peeled = null });
        last_was_ref = true;
    }
    if (!traits.sorted) {
        std.sort.block(Entry, entries.items, {}, struct {
            fn lessThan(_: void, a: Entry, b: Entry) bool {
                return std.mem.lessThan(u8, a.name, b.name);
            }
        }.lessThan);
    }
    return .{ .traits = traits, .entries = try entries.toOwnedSlice(gpa) };
}

fn unexpected(diag: ?*Diagnostics, line: []const u8, line_number: u32) error{UnexpectedPackedRefsLine} {
    if (diag) |d| {
        d.line = line_number;
        d.setDetail("{s}", .{line});
    }
    return error.UnexpectedPackedRefsLine;
}

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

const testing = std.testing;

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

test "a packed-refs file is read as git reads it" {
    const gpa = testing.allocator;
    var p = try parse(gpa, .sha1, @embedFile("../fuzz/packed-refs"), null);
    defer p.deinit(gpa);
    try testing.expect(p.traits.sorted and p.traits.peeled and p.traits.fully_peeled);
    try testing.expectEqual(4, p.entries.len);
    try testing.expectEqualStrings("refs/tags/v1", p.entries[3].name);
    try testing.expect(p.entries[3].peeled != null);
    try testing.expect(p.entries[0].peeled == null);
    try testing.expect(p.find("refs/heads/side") != null);
    try testing.expect(p.find("refs/heads/nope") == null);
}

test "malformed packed-refs files are refused as git refuses them" {
    const gpa = testing.allocator;
    const h = "f262b5fdc70bf36bebcf70cc60cf788a294c8126";
    const header = "# pack-refs with: peeled fully-peeled sorted \n";
    for ([_][]const u8{
        header ++ h ++ " refs/heads/main\ngarbage\n",
        header ++ "# hi\n" ++ h ++ " refs/heads/main\n",
        header ++ "^" ++ h ++ "\n" ++ h ++ " refs/heads/main\n",
        header ++ h ++ " refs/heads/main\n^zz\n",
        header ++ h ++ " refs/heads/main\n^" ++ h ++ "\n^" ++ h ++ "\n",
        header ++ h ++ " \n",
        header ++ h ++ "\n",
        header ++ "\n",
        h ++ " refs/heads/main\n" ++ header,
        h ++ "x refs/heads/main\n",
    }) |c| {
        var d: Diagnostics = .{};
        try testing.expectError(error.UnexpectedPackedRefsLine, parse(gpa, .sha1, c, &d));
    }
    var d: Diagnostics = .{};
    try testing.expectError(error.UnterminatedPackedRefsLine, parse(gpa, .sha1, header ++ h ++ " refs/heads/main", &d));
    try testing.expectEqualStrings(h ++ " refs/heads/main", d.detail());
}

test "unsorted files are sorted, and files that say they are sorted are trusted" {
    const gpa = testing.allocator;
    const h = "f262b5fdc70bf36bebcf70cc60cf788a294c8126";
    var p = try parse(gpa, .sha1, h ++ " refs/tags/v1\n" ++ h ++ "\trefs/heads/main\n", null);
    defer p.deinit(gpa);
    try testing.expectEqualStrings("refs/heads/main", p.entries[0].name);
    var q = try parse(gpa, .sha1, "# pack-refs with: sorted\n" ++ h ++ " refs/tags/v1\n" ++ h ++ " refs/heads/main\r\n", null);
    defer q.deinit(gpa);
    try testing.expectEqualStrings("refs/tags/v1", q.entries[0].name);
    try testing.expectEqualStrings("refs/heads/main\r", q.entries[1].name);
}

test "fuzz: packed-refs" {
    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);
            for ([_]object.Format{ .sha1, .sha256 }) |f| {
                var p = parse(testing.allocator, f, input, null) catch continue;
                defer p.deinit(testing.allocator);
                for (p.entries) |e| _ = p.find(e.name);
            }
        }
    }.one, .{ .corpus = &.{
        @embedFile("../fuzz/packed-refs"),
        @embedFile("../fuzz/packed-refs-sha256"),
    } });
}