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

//! Abbreviated object IDs, both ways: finding the objects a short
//! hexadecimal prefix stands for, and choosing how many digits an object
//! ID needs to stand for one object alone.
//!
//! The rules are git's observed ones, found by making repositories whose
//! objects collide on their first digits and asking `git rev-parse`,
//! `git cat-file` and the listing commands about them:
//!
//! - **A prefix** is one to 64 hexadecimal digits in either case. Digits
//!   past the object format's length are ignored, though they must still
//!   be hexadecimal; a prefix exactly as long as an object ID is a whole
//!   object ID, which names an object whether or not there is one. Commands
//!   accept a prefix of at least `min_length` digits (`--disambiguate`
//!   lists from two).
//! - **Expanding one** looks in every objects directory, the alternates'
//!   too: each multi-pack-index layer and each pack index outside them by
//!   a binary search within the range their fanout table gives the first
//!   byte, `O(log n + k)` for `n` objects and `k` matches; and the loose
//!   objects in the one fan-out directory the first two digits name, a
//!   directory listing read once and kept sorted. A prefix of one digit
//!   covers sixteen fan-out directories.
//! - **Several candidates** may be told apart by a `Hint`, as
//!   `core.disambiguate` and `<prefix>^{commit}` give: one candidate is
//!   the answer whatever the hint; otherwise the one candidate the hint
//!   allows is; otherwise the prefix is ambiguous, and git lists the
//!   candidates the hint allows, or all of them if it allows none.
//! - **The candidates are listed** tags first, then commits, trees and
//!   blobs, each in object ID order, as `writeCandidate` describes.
//! - **The length an object ID is shortened to** is the shortest that no
//!   other object in the database shares, and at least the length asked
//!   for: `core.abbrev`, `auto` unless it says otherwise. `auto` grows with
//!   the number of packed objects (`autoLength`): loose objects are not
//!   counted, and a multi-pack-index counts each object once where the
//!   packs it covers would count one held twice twice.

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

const object = @import("object.zig");
const Format = object.Format;
const Id = object.Id;
const Kind = object.Kind;
const Diagnostics = @import("Diagnostics.zig");
const DiskDatabase = @import("DiskDatabase.zig");
const ObjectDatabase = @import("ObjectDatabase.zig");
const PackIndex = @import("PackIndex.zig");
const MultiPackIndex = @import("MultiPackIndex.zig");
const RefStore = @import("RefStore.zig");
const commit = @import("commit.zig");
const Tag = @import("tag.zig").Tag;
const Identity = @import("Identity.zig");
const date = @import("date.zig");
const config_value = @import("config/value.zig");

/// The fewest digits a command takes as an abbreviated object ID, and
/// the fewest any object ID is shortened to.
pub const min_length = 4;

/// The fewest digits `auto` shortens to, however few objects there are.
pub const auto_min_length = 7;

fn hexValue(c: u8) ?u8 {
    return switch (c) {
        '0'...'9' => c - '0',
        'a'...'f' => c - 'a' + 10,
        'A'...'F' => c - 'A' + 10,
        else => null,
    };
}

/// Whether every byte of `text` is a hexadecimal digit, and there is at
/// least one.
pub fn isHex(text: []const u8) bool {
    if (text.len == 0) return false;
    for (text) |c| if (hexValue(c) == null) return false;
    return true;
}

// -- prefixes ----------------------------------------------------------------

/// The first digits of an object ID, as a caller wrote them.
pub const Prefix = struct {
    format: Format,
    /// The digits, two to a byte, high nibble first; zero past `len`.
    bytes: [object.max_byte_length]u8,
    /// How many digits count: those written, up to the format's length.
    len: usize,

    /// Why text is not a prefix: empty, longer than any object ID, or not
    /// hexadecimal.
    pub const ParseError = error{InvalidPrefix};

    /// Reads `text`, one to `object.max_hex_length` hexadecimal digits in
    /// either case, as a prefix of an object ID in `format`. Digits past
    /// the format's length must be hexadecimal but are otherwise ignored,
    /// as git ignores them.
    pub fn parse(format: Format, text: []const u8) ParseError!Prefix {
        if (text.len == 0 or text.len > object.max_hex_length) return error.InvalidPrefix;
        var p: Prefix = .{ .format = format, .bytes = @splat(0), .len = @min(text.len, format.hexLength()) };
        for (text, 0..) |c, i| {
            const v = hexValue(c) orelse return error.InvalidPrefix;
            if (i >= p.len) continue;
            p.bytes[i / 2] |= if (i % 2 == 0) v << 4 else v;
        }
        return p;
    }

    /// Whether the prefix is a whole object ID, which names an object
    /// whether or not the database holds one.
    pub fn isWhole(p: *const Prefix) bool {
        return p.len == p.format.hexLength();
    }

    /// The whole object ID, for a prefix that is one; otherwise the
    /// smallest object ID it begins.
    pub fn lowest(p: *const Prefix) Id {
        return .{ .object_format = p.format, .bytes = p.bytes };
    }

    /// Whether `id` begins with the prefix.
    pub fn matches(p: *const Prefix, id: Id) bool {
        const whole = p.len / 2;
        if (!std.mem.eql(u8, id.bytes[0..whole], p.bytes[0..whole])) return false;
        if (p.len % 2 == 1) return id.bytes[whole] >> 4 == p.bytes[whole] >> 4;
        return true;
    }

    /// The digits that count, in lowercase.
    pub fn toHex(p: *const Prefix, buffer: *[object.max_hex_length]u8) []const u8 {
        var full: [object.max_hex_length]u8 = undefined;
        const hex = p.lowest().toHex(&full);
        @memcpy(buffer[0..p.len], hex[0..p.len]);
        return buffer[0..p.len];
    }
};

/// How many leading hexadecimal digits two object IDs share.
pub fn commonDigits(a: Id, b: Id) usize {
    const n = a.object_format.byteLength();
    for (a.bytes[0..n], b.bytes[0..n], 0..) |x, y, i| {
        if (x == y) continue;
        return if (x >> 4 == y >> 4) 2 * i + 1 else 2 * i;
    }
    return 2 * n;
}

// -- type hints --------------------------------------------------------------

/// Which kind of object an ambiguous prefix is meant to name, as
/// `core.disambiguate` and the peeling suffixes say.
pub const Hint = enum {
    /// Any kind: an ambiguous prefix stays ambiguous.
    none,
    commit,
    /// A commit, or a tag that leads to one.
    committish,
    tree,
    /// A commit or a tree, or a tag that leads to either.
    treeish,
    blob,

    /// Why a `core.disambiguate` value is refused: git's "missing value
    /// for 'core.disambiguate'" and "unknown hint type for
    /// 'core.disambiguate': <value>".
    pub const ParseError = error{ MissingValue, UnknownHint };

    /// Reads a `core.disambiguate` value: one of the names, in any case.
    pub fn parse(text: ?[]const u8) ParseError!Hint {
        const t = text orelse return error.MissingValue;
        inline for (@typeInfo(Hint).@"enum".field_names) |name| {
            if (std.ascii.eqlIgnoreCase(t, name)) return @field(Hint, name);
        }
        return error.UnknownHint;
    }

    /// Whether an object of `kind`, which is `peeled` once its tags are
    /// peeled, is one the hint allows.
    pub fn allows(h: Hint, kind: Kind, peeled: ?Kind) bool {
        return switch (h) {
            .none => true,
            .commit => kind == .commit,
            .tree => kind == .tree,
            .blob => kind == .blob,
            .committish => (peeled orelse kind) == .commit,
            .treeish => switch (peeled orelse kind) {
                .commit, .tree => true,
                else => false,
            },
        };
    }
};

// -- lengths -----------------------------------------------------------------

/// How long object IDs are to be shown, as `core.abbrev` says.
pub const Length = union(enum) {
    /// As long as the number of packed objects suggests: `autoLength`.
    auto,
    /// At least this many digits, `min_length` or more.
    digits: u32,
    /// Whole.
    full,
};

/// Why a `core.abbrev` value is refused, in git's words:
///
/// - `MissingValue`: "missing value for 'core.abbrev'".
/// - `LengthOutOfRange`: "abbrev length out of range: <n>", for a number
///   under `min_length`; the diagnostic's detail is the number.
/// - `InvalidUnit`, `OutOfRange`: "bad numeric config value", for what is
///   not a number that fits a C `int`.
pub const LengthError = error{ MissingValue, LengthOutOfRange } || config_value.IntError;

/// Reads a `core.abbrev` value: `auto` in any case, a word for false (or
/// nothing) for whole object IDs, or a number with an optional unit; a
/// word for true is not a number.
pub fn parseLength(text: ?[]const u8, diag: ?*Diagnostics) LengthError!Length {
    const t = text orelse return error.MissingValue;
    if (std.ascii.eqlIgnoreCase(t, "auto")) return .auto;
    if (config_value.boolWord(t) == false) return .full;
    const n = try config_value.parseInt(i32, t);
    if (n < min_length) {
        if (diag) |d| d.setDetail("{d}", .{n});
        return error.LengthOutOfRange;
    }
    return .{ .digits = @intCast(n) };
}

/// The length `auto` gives a database of `count` packed objects: half the
/// bits it takes to write the count, rounded up, and never under
/// `auto_min_length`. So 7 digits up to 16383 objects, 8 from 16384, 9
/// from 65536, each further digit at four times as many.
pub fn autoLength(count: u64) usize {
    const bits: usize = 64 - @clz(count);
    return @max(auto_min_length, (bits + 1) / 2);
}

/// The length a command's `--abbrev=<n>` asks for, by git's option
/// rules: 0 for whole object IDs (null), anything else at least
/// `min_length`, and nothing past the format's length.
pub fn optionLength(format: Format, n: i64) ?usize {
    if (n == 0) return null;
    if (n < min_length) return min_length;
    if (n >= format.hexLength()) return null;
    return @intCast(n);
}

// -- the candidates' lines ----------------------------------------------------

/// Why a candidate's line could not be written: the writer failed, or a
/// date is one git cannot show either (it stops on a tagger's negative
/// timestamp with "Timestamp too large for this system").
pub const LineError = Io.Writer.Error || error{UnsupportedDate};

const space = " \t\n\r";

/// Writes what git's ambiguity hint says of a candidate after its
/// abbreviated object ID, given its kind and, for a commit or a tag, its
/// contents:
///
/// - a commit: `commit <date> - <subject>`, the date the last `author`
///   line's, as `--date=short` shows it in the author's own time zone, or
///   nothing if there is no readable one; the subject the message's first
///   paragraph, each line less its trailing blank space and the lines
///   joined with a space, as `%s` gives it, its bytes unconverted;
/// - a tag: `tag <date> - <name>`, the date the first `tagger` line's in
///   UTC, or the epoch without one; or `[bad tag, could not parse it]`
///   for a tag whose first three lines git cannot read;
/// - a tree or a blob: its kind alone.
pub fn writeCandidate(w: *Io.Writer, format: Format, kind: Kind, contents: []const u8) LineError!void {
    switch (kind) {
        .tree, .blob => return w.writeAll(kind.name()),
        .commit => {
            try w.writeAll("commit ");
            var headers = contents;
            var message: []const u8 = "";
            if (std.mem.find(u8, contents, "\n\n")) |blank| {
                headers = contents[0 .. blank + 1];
                message = contents[blank + 2 ..];
            }
            if (commit.lastValue(headers, "author")) |line| if (Identity.parse(line)) |id| if (id.date()) |d|
                try writeShortDate(w, d);
            try w.writeAll(" - ");
            try writeSubject(w, message);
        },
        .tag => {
            const t = Tag.parse(format, contents, null) catch
                return w.writeAll("[bad tag, could not parse it]");
            var seconds: i64 = 0;
            var it = t.fields();
            while (it.next()) |f| {
                if (!std.mem.eql(u8, f.name, "tagger")) continue;
                const v = f.value orelse break;
                const line = v[0 .. std.mem.findScalar(u8, v, '\n') orelse v.len];
                // git reads the seconds as an unsigned number, so a minus
                // sign wraps them past anything it can show.
                if (std.mem.findScalarLast(u8, line, '>')) |gt| {
                    const after = std.mem.trimStart(u8, line[gt + 1 ..], " ");
                    if (after.len > 1 and after[0] == '-' and std.ascii.isDigit(after[1])) return error.UnsupportedDate;
                }
                if (Identity.parse(line)) |id| if (id.date()) |d| {
                    seconds = d.seconds;
                };
                break;
            }
            try w.writeAll("tag ");
            try writeShortDate(w, .{ .seconds = seconds, .zone = 0 });
            try w.print(" - {s}", .{t.name});
        },
    }
}

fn writeShortDate(w: *Io.Writer, d: date.Date) LineError!void {
    date.format(w, d, .{ .style = .short }, .{ .now = 0, .zone = &date.Zone.utc }, null) catch |err| switch (err) {
        error.WriteFailed => return error.WriteFailed,
        else => return error.UnsupportedDate,
    };
}

fn isBlank(line: []const u8) bool {
    return std.mem.trim(u8, line, space).len == 0;
}

/// Writes a commit message's subject as `%s` gives it.
fn writeSubject(w: *Io.Writer, message: []const u8) Io.Writer.Error!void {
    var lines = std.mem.splitScalar(u8, message, '\n');
    var first = true;
    var started = false;
    while (lines.next()) |line| {
        if (isBlank(line)) {
            if (started) break;
            continue;
        }
        started = true;
        if (!first) try w.writeByte(' ');
        first = false;
        try w.writeAll(std.mem.trimEnd(u8, line, space));
    }
}

/// Where kinds come in a list of candidates: tags first, then commits,
/// trees and blobs.
fn kindRank(k: Kind) u8 {
    return switch (k) {
        .tag => 0,
        .commit => 1,
        .tree => 2,
        .blob => 3,
    };
}

// -- looking in the database ---------------------------------------------------

/// One object found by a prefix, with its kind.
pub const Candidate = struct {
    id: Id,
    kind: Kind,
};

/// The candidates of an ambiguous prefix that git lists, in its order.
pub const Ambiguity = struct {
    candidates: []Candidate,

    /// Frees the list.
    pub fn deinit(a: *Ambiguity, gpa: Allocator) void {
        gpa.free(a.candidates);
        a.* = undefined;
    }
};

/// What a prefix names.
pub const Resolution = union(enum) {
    /// One object.
    found: Id,
    /// No object.
    missing,
    /// More than one, which a caller frees.
    ambiguous: Ambiguity,
};

/// A sorted table of object IDs: a pack index, a multi-pack-index layer
/// or one fan-out directory's loose objects.
const Table = union(enum) {
    pack: *const PackIndex,
    midx: *const MultiPackIndex,
    loose: []const Id,

    fn idAt(t: Table, i: usize) Id {
        return switch (t) {
            .pack => |p| p.idAt(@intCast(i)),
            .midx => |m| m.idAt(@intCast(i)),
            .loose => |l| l[i],
        };
    }

    /// Where the IDs whose first byte is from `lo` to `hi` are.
    fn range(t: Table, lo: u8, hi: u8) [2]usize {
        return switch (t) {
            .pack => |p| .{ if (lo == 0) 0 else p.fanout(lo - 1), p.fanout(hi) },
            .midx => |m| .{ if (lo == 0) 0 else m.fanout(lo - 1), m.fanout(hi) },
            .loose => |l| .{ 0, l.len },
        };
    }

    /// The first position in `[start, end)` whose ID is not less than
    /// `id`.
    fn lowerBound(t: Table, start: usize, end: usize, id: Id) usize {
        var lo = start;
        var hi = end;
        const want = id.slice();
        while (lo < hi) {
            const mid = lo + (hi - lo) / 2;
            const at = t.idAt(mid);
            if (std.mem.order(u8, at.slice(), want) == .lt) lo = mid + 1 else hi = mid;
        }
        return lo;
    }
};

/// Looks up abbreviated object IDs in a database on disk, and shortens
/// object IDs against it. It keeps the loose objects of each fan-out
/// directory it has listed, so shortening many object IDs reads each
/// directory once; a loose object written afterwards is not seen.
pub const Lookup = struct {
    gpa: Allocator,
    db: *DiskDatabase,
    /// Listed fan-out directories, by objects directory and first byte.
    loose: std.AutoHashMapUnmanaged(u32, []Id) = .empty,

    /// Why a lookup failed: a fan-out directory could not be listed.
    pub const Error = Allocator.Error || error{ ObjectUnreadable, Canceled };

    /// Why resolving a prefix failed: a lookup error, or a candidate's
    /// kind could not be read.
    pub const ResolveError = Error || ObjectDatabase.ReadError;

    /// A lookup in `db`, which must outlive it.
    pub fn init(gpa: Allocator, db: *DiskDatabase) Lookup {
        return .{ .gpa = gpa, .db = db };
    }

    /// Frees what it has listed.
    pub fn deinit(l: *Lookup) void {
        var it = l.loose.valueIterator();
        while (it.next()) |v| l.gpa.free(v.*);
        l.loose.deinit(l.gpa);
        l.* = undefined;
    }

    /// The loose objects whose first byte is `byte` in the `d`th objects
    /// directory, sorted.
    fn looseIds(l: *Lookup, io: Io, d: usize, byte: u8) Error![]const Id {
        const key: u32 = @as(u32, @intCast(d)) << 8 | byte;
        if (l.loose.get(key)) |ids| return ids;
        const format = l.db.format;
        var list: std.ArrayList(Id) = .empty;
        defer list.deinit(l.gpa);
        const digits = "0123456789abcdef";
        const name = [2]u8{ digits[byte >> 4], digits[byte & 0xf] };
        if (l.db.directories[d].loose.dir.openDir(io, &name, .{ .iterate = true })) |dir_const| {
            var dir = dir_const;
            defer dir.close(io);
            var it = dir.iterate();
            while (it.next(io) catch |err| switch (err) {
                error.Canceled => return error.Canceled,
                else => return error.ObjectUnreadable,
            }) |entry| {
                if (entry.name.len != format.hexLength() - 2) continue;
                var hex: [object.max_hex_length]u8 = undefined;
                hex[0..2].* = name;
                @memcpy(hex[2..][0..entry.name.len], entry.name);
                const id = Id.parseHex(format, hex[0..format.hexLength()]) catch continue;
                // git names loose objects in lowercase; a file in capitals
                // is not one it would find.
                if (std.mem.findAny(u8, entry.name, "ABCDEF") != null) continue;
                try list.append(l.gpa, id);
            }
        } else |err| switch (err) {
            error.FileNotFound, error.NotDir => {},
            error.Canceled => return error.Canceled,
            else => return error.ObjectUnreadable,
        }
        std.mem.sort(Id, list.items, {}, idLessThan);
        const owned = try list.toOwnedSlice(l.gpa);
        errdefer l.gpa.free(owned);
        try l.loose.put(l.gpa, key, owned);
        return owned;
    }

    /// Appends every sorted table in the `d`th objects directory a lookup
    /// asks, its loose objects aside: the multi-pack-index layers, and the
    /// packs they do not cover.
    fn packTables(l: *Lookup, d: usize, out: *std.ArrayList(Table)) Allocator.Error!void {
        const dir = l.db.directories[d];
        for (dir.midx_layers) |*layer| try out.append(l.gpa, .{ .midx = &layer.midx });
        for (dir.packs) |*p| {
            if (p.in_midx and dir.midx_layers.len > 0) continue;
            switch (p.state) {
                .ok => |*pk| try out.append(l.gpa, .{ .pack = &pk.index }),
                .bad_pack => |*b| try out.append(l.gpa, .{ .pack = &b.index }),
                .bad_index => {},
            }
        }
    }

    /// How many packed objects the database holds, roughly, as `auto`
    /// counts them: each multi-pack-index layer's objects and each pack
    /// outside them, in every objects directory. An object in two packs
    /// counts twice unless a multi-pack-index covers both.
    pub fn objectCount(l: *const Lookup) u64 {
        var n: u64 = 0;
        for (l.db.directories) |dir| {
            for (dir.midx_layers) |*layer| n += layer.midx.count;
            for (dir.packs) |*p| {
                if (p.in_midx and dir.midx_layers.len > 0) continue;
                switch (p.state) {
                    .ok => |*pk| n += pk.index.count,
                    .bad_pack => |*b| n += b.index.count,
                    .bad_index => {},
                }
            }
        }
        return n;
    }

    /// The fewest digits object IDs are shortened to under `length`.
    pub fn minimumLength(l: *const Lookup, length: Length) usize {
        const whole = l.db.format.hexLength();
        return switch (length) {
            .auto => @min(whole, autoLength(l.objectCount())),
            .digits => |n| @min(whole, n),
            .full => whole,
        };
    }

    /// Appends every object ID beginning with `prefix` to `out`, sorted
    /// and each once, whichever objects directories, packs and loose
    /// objects hold it.
    pub fn findAll(l: *Lookup, io: Io, prefix: Prefix, out: *std.ArrayList(Id)) Error!void {
        const start = out.items.len;
        const first_lo: u8 = if (prefix.len >= 2) prefix.bytes[0] else prefix.bytes[0] & 0xf0;
        const first_hi: u8 = if (prefix.len >= 2) prefix.bytes[0] else prefix.bytes[0] | 0x0f;
        const lowest = prefix.lowest();
        var tables: std.ArrayList(Table) = .empty;
        defer tables.deinit(l.gpa);
        for (0..l.db.directories.len) |d| {
            tables.clearRetainingCapacity();
            try l.packTables(d, &tables);
            var b: u16 = first_lo;
            while (b <= first_hi) : (b += 1) try tables.append(l.gpa, .{ .loose = try l.looseIds(io, d, @intCast(b)) });
            for (tables.items) |t| {
                const r = t.range(first_lo, first_hi);
                var i = t.lowerBound(r[0], r[1], lowest);
                while (i < r[1]) : (i += 1) {
                    const id = t.idAt(i);
                    if (!prefix.matches(id)) break;
                    try out.append(l.gpa, id);
                }
            }
        }
        const found = out.items[start..];
        std.mem.sort(Id, found, {}, idLessThan);
        var kept: usize = 0;
        for (found, 0..) |id, i| {
            if (i != 0 and Id.eql(id, found[kept - 1])) continue;
            found[kept] = id;
            kept += 1;
        }
        out.shrinkRetainingCapacity(start + kept);
    }

    /// The fewest digits, at least `at_least`, that no object in the
    /// database but `id` begins with; `id` need not be there itself.
    /// Each table is asked for the IDs on either side of `id`, so this
    /// costs a binary search per pack index and multi-pack-index layer,
    /// and one listing of a fan-out directory per objects directory.
    pub fn uniqueLength(l: *Lookup, io: Io, id: Id, at_least: usize) Error!usize {
        const whole = id.object_format.hexLength();
        var need = @min(@max(at_least, 1), whole);
        var tables: std.ArrayList(Table) = .empty;
        defer tables.deinit(l.gpa);
        for (0..l.db.directories.len) |d| {
            tables.clearRetainingCapacity();
            try l.packTables(d, &tables);
            try tables.append(l.gpa, .{ .loose = try l.looseIds(io, d, id.bytes[0]) });
            for (tables.items) |t| {
                const r = t.range(id.bytes[0], id.bytes[0]);
                var i = t.lowerBound(r[0], r[1], id);
                if (i > r[0]) need = @max(need, @min(whole, commonDigits(id, t.idAt(i - 1)) + 1));
                if (i < r[1] and Id.eql(t.idAt(i), id)) i += 1;
                if (i < r[1]) need = @max(need, @min(whole, commonDigits(id, t.idAt(i)) + 1));
            }
        }
        return need;
    }

    /// `id` shortened to `uniqueLength(id, at_least)` digits, in
    /// `buffer`.
    pub fn abbreviate(l: *Lookup, io: Io, id: Id, at_least: usize, buffer: *[object.max_hex_length]u8) Error![]const u8 {
        const n = try l.uniqueLength(io, id, at_least);
        return id.toHex(buffer)[0..n];
    }

    /// What `prefix` names, told apart by `hint` if need be, as the rules
    /// at the top of this file say. A whole object ID is not looked up:
    /// it names its object whether or not the database holds it.
    pub fn resolve(l: *Lookup, io: Io, prefix: Prefix, hint: Hint, diag: ?*Diagnostics) ResolveError!Resolution {
        if (prefix.isWhole()) return .{ .found = prefix.lowest() };
        var ids: std.ArrayList(Id) = .empty;
        defer ids.deinit(l.gpa);
        try l.findAll(io, prefix, &ids);
        if (ids.items.len == 0) return .missing;
        if (ids.items.len == 1) return .{ .found = ids.items[0] };
        const db = l.db.database();
        const all = try l.gpa.alloc(Candidate, ids.items.len);
        defer l.gpa.free(all);
        var allowed: std.ArrayList(Candidate) = .empty;
        defer allowed.deinit(l.gpa);
        for (ids.items, all) |id, *c| {
            const header = try db.readHeader(io, id, diag);
            c.* = .{ .id = id, .kind = header.kind };
            if (hint == .none) continue;
            var peeled: ?Kind = null;
            if (header.kind == .tag and (hint == .committish or hint == .treeish)) {
                if (RefStore.peel(io, l.gpa, db, id, null)) |p| {
                    peeled = p.kind;
                } else |err| switch (err) {
                    error.OutOfMemory => return error.OutOfMemory,
                    // A tag that leads nowhere leads to nothing allowed.
                    else => continue,
                }
            }
            if (hint.allows(header.kind, peeled)) try allowed.append(l.gpa, c.*);
        }
        if (allowed.items.len == 1) return .{ .found = allowed.items[0].id };
        const listed = try l.gpa.dupe(Candidate, if (allowed.items.len == 0) all else allowed.items);
        std.mem.sort(Candidate, listed, {}, candidateLessThan);
        return .{ .ambiguous = .{ .candidates = listed } };
    }

    /// Writes git's complaint about an ambiguous prefix, in lowercase
    /// whatever case it was written in, and its candidates each shortened
    /// to at least `length` digits:
    ///
    ///     error: short object ID <prefix> is ambiguous
    ///     hint: The candidates are:
    ///     hint:   <abbreviated ID> <line>
    ///
    /// with each line as `writeCandidate` writes it.
    pub fn writeAmbiguity(
        l: *Lookup,
        io: Io,
        w: *Io.Writer,
        prefix: Prefix,
        ambiguity: Ambiguity,
        length: usize,
        diag: ?*Diagnostics,
    ) (ResolveError || LineError)!void {
        // The lines are made first, so that a candidate that cannot be
        // read or shown leaves nothing half written.
        var aw: Io.Writer.Allocating = .init(l.gpa);
        defer aw.deinit();
        const out = &aw.writer;
        var digits: [object.max_hex_length]u8 = undefined;
        out.print("error: short object ID {s} is ambiguous\nhint: The candidates are:\n", .{prefix.toHex(&digits)}) catch return error.OutOfMemory;
        const db = l.db.database();
        for (ambiguity.candidates) |c| {
            var buffer: [object.max_hex_length]u8 = undefined;
            const short = try l.abbreviate(io, c.id, length, &buffer);
            out.print("hint:   {s} ", .{short}) catch return error.OutOfMemory;
            switch (c.kind) {
                .tree, .blob => writeCandidate(out, c.id.object_format, c.kind, "") catch |err| switch (err) {
                    error.WriteFailed => return error.OutOfMemory,
                    else => |e| return e,
                },
                .commit, .tag => {
                    var o = try db.read(io, l.gpa, c.id, diag);
                    defer o.deinit(l.gpa);
                    writeCandidate(out, c.id.object_format, c.kind, o.data) catch |err| switch (err) {
                        error.WriteFailed => return error.OutOfMemory,
                        else => |e| {
                            if (diag) |d| d.object_id = c.id;
                            return e;
                        },
                    };
                },
            }
            out.writeByte('\n') catch return error.OutOfMemory;
        }
        try w.writeAll(aw.written());
    }
};

fn idLessThan(_: void, a: Id, b: Id) bool {
    return std.mem.order(u8, a.slice(), b.slice()) == .lt;
}

fn candidateLessThan(_: void, a: Candidate, b: Candidate) bool {
    const ra = kindRank(a.kind);
    const rb = kindRank(b.kind);
    if (ra != rb) return ra < rb;
    return idLessThan({}, a.id, b.id);
}

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

test "a prefix is read as git reads it" {
    for ([_]Format{ .sha1, .sha256 }) |format| {
        const p = try Prefix.parse(format, "2C7d5");
        try testing.expectEqual(5, p.len);
        var buffer: [object.max_hex_length]u8 = undefined;
        try testing.expectEqualStrings("2c7d5", p.toHex(&buffer));
        try testing.expect(!p.isWhole());
        var id = p.lowest();
        try testing.expect(p.matches(id));
        id.bytes[2] = 0x60;
        try testing.expect(!p.matches(id));
        id.bytes[2] = 0x5f;
        try testing.expect(p.matches(id));
        try testing.expectError(error.InvalidPrefix, Prefix.parse(format, ""));
        try testing.expectError(error.InvalidPrefix, Prefix.parse(format, "2c7g"));
        // Digits past an object ID's length are ignored, but must be
        // hexadecimal, and there may be no more than 64.
        const long: [object.max_hex_length]u8 = @splat('a');
        const whole = try Prefix.parse(format, &long);
        try testing.expect(whole.isWhole());
        try testing.expectEqual(format.hexLength(), whole.len);
        try testing.expectError(error.InvalidPrefix, Prefix.parse(format, long ++ "a"));
        var bad = long;
        bad[63] = 'x';
        try testing.expectError(error.InvalidPrefix, Prefix.parse(format, &bad));
    }
}

test "the lengths core.abbrev and --abbrev ask for" {
    try testing.expectEqual(Length.auto, try parseLength("AUTO", null));
    try testing.expectEqual(Length.full, try parseLength("no", null));
    try testing.expectEqual(Length.full, try parseLength("", null));
    try testing.expectEqual(Length{ .digits = 8 }, try parseLength(" 8", null));
    try testing.expectEqual(Length{ .digits = 8 }, try parseLength("0x8", null));
    var diag: Diagnostics = .{};
    try testing.expectError(error.LengthOutOfRange, parseLength("-1", &diag));
    try testing.expectEqualStrings("-1", diag.detail());
    try testing.expectError(error.MissingValue, parseLength(null, null));
    try testing.expectError(error.InvalidUnit, parseLength("yes", null));
    try testing.expectError(error.OutOfRange, parseLength("2147483648", null));
    // The thresholds found by packing 2^n - 1 and 2^n blobs.
    try testing.expectEqual(7, autoLength(0));
    try testing.expectEqual(7, autoLength(16383));
    try testing.expectEqual(8, autoLength(16384));
    try testing.expectEqual(8, autoLength(65535));
    try testing.expectEqual(9, autoLength(65536));
    try testing.expectEqual(10, autoLength(262144));
    try testing.expectEqual(32, autoLength(std.math.maxInt(u64)));
    try testing.expectEqual(null, optionLength(.sha1, 0));
    try testing.expectEqual(4, optionLength(.sha1, -1));
    try testing.expectEqual(39, optionLength(.sha1, 39));
    try testing.expectEqual(null, optionLength(.sha1, 40));
    try testing.expectEqual(Hint.committish, try Hint.parse("CommitTish"));
    try testing.expectError(error.UnknownHint, Hint.parse("tag"));
}

fn openDatabase(repo: *fixture.Repo) !DiskDatabase {
    return DiskDatabase.open(repo.gpa, repo.io, .{
        .objects_path = ".git/objects",
        .base = repo.tmp.dir,
        .format = repo.object_format,
    }, null);
}

fn allObjects(repo: *fixture.Repo) ![]u8 {
    return repo.output(&.{ "cat-file", "--batch-all-objects", "--batch-check=%(objectname)" });
}

test "a prefix finds what git finds, wherever the objects are" {
    const gpa = testing.allocator;
    var repo = try fixture.Repo.init(gpa, testing.io);
    defer repo.deinit();
    var c = try collide.build(&repo);
    defer c.deinit();
    var db = try openDatabase(&repo);
    defer db.close(repo.io);
    var lookup: Lookup = .init(gpa, &db);
    defer lookup.deinit();

    var ids: std.ArrayList(Id) = .empty;
    defer ids.deinit(gpa);
    var got: Io.Writer.Allocating = .init(gpa);
    defer got.deinit();
    for (c.prefixes.items) |p| {
        // Every length from two digits to one past the collision.
        for (2..p.len + 2) |n| {
            const hex = try std.fmt.allocPrint(gpa, "{s}{s}", .{ p, "0" });
            defer gpa.free(hex);
            const asked = hex[0..@min(n, hex.len)];
            const arg = try std.fmt.allocPrint(gpa, "--disambiguate={s}", .{asked});
            defer gpa.free(arg);
            const want = try repo.output(&.{ "rev-parse", arg });
            defer gpa.free(want);
            ids.clearRetainingCapacity();
            try lookup.findAll(repo.io, try Prefix.parse(repo.object_format, asked), &ids);
            got.clearRetainingCapacity();
            for (ids.items) |id| try got.writer.print("{f}\n", .{id});
            try testing.expectEqualStrings(want, got.written());
        }
    }

    // Every object is shortened as git shortens it.
    try testing.expectEqual(7, lookup.minimumLength(.auto));
    const all = try allObjects(&repo);
    defer gpa.free(all);
    var lines = std.mem.tokenizeScalar(u8, all, '\n');
    while (lines.next()) |hex| {
        const id = try Id.parseHex(repo.object_format, hex);
        for ([_][]const u8{ "--short=4", "--short" }) |opt| {
            const want = try repo.output(&.{ "rev-parse", opt, hex });
            defer gpa.free(want);
            var buffer: [object.max_hex_length]u8 = undefined;
            const n: usize = if (opt.len > "--short".len) 4 else lookup.minimumLength(.auto);
            try testing.expectEqualStrings(std.mem.trimEnd(u8, want, "\n"), try lookup.abbreviate(repo.io, id, n, &buffer));
        }
    }
}

test "an ambiguous prefix is resolved and reported as git does" {
    const gpa = testing.allocator;
    var repo = try fixture.Repo.init(gpa, testing.io);
    defer repo.deinit();
    var c = try collide.build(&repo);
    defer c.deinit();
    var db = try openDatabase(&repo);
    defer db.close(repo.io);
    var lookup: Lookup = .init(gpa, &db);
    defer lookup.deinit();

    var report: Io.Writer.Allocating = .init(gpa);
    defer report.deinit();
    for (c.prefixes.items) |p| {
        inline for (@typeInfo(Hint).@"enum".field_names) |name| {
            const hint = @field(Hint, name);
            const setting = "core.disambiguate=" ++ name;
            const theirs = try repo.runIn(".", &.{ "-c", setting, "rev-parse", "--verify", p }, "");
            defer theirs.deinit(gpa);
            var r = try lookup.resolve(repo.io, try Prefix.parse(repo.object_format, p), hint, null);
            switch (r) {
                .found => |id| {
                    try testing.expectEqual(0, theirs.code);
                    var buffer: [object.max_hex_length]u8 = undefined;
                    try testing.expectEqualStrings(std.mem.trimEnd(u8, theirs.stdout, "\n"), id.toHex(&buffer));
                },
                .missing => return error.TestUnexpectedResult,
                .ambiguous => |*a| {
                    defer a.deinit(gpa);
                    try testing.expectEqual(128, theirs.code);
                    report.clearRetainingCapacity();
                    try lookup.writeAmbiguity(repo.io, &report.writer, try Prefix.parse(repo.object_format, p), a.*, lookup.minimumLength(.auto), null);
                    try report.writer.writeAll("fatal: Needed a single revision\n");
                    try testing.expectEqualStrings(theirs.stderr, report.written());
                },
            }
        }
    }
    // A prefix of no object, and a whole object ID of none.
    const nothing = "0000000000000000000000000000000000000000000000000000000000000000";
    try testing.expectEqual(Resolution.missing, try lookup.resolve(repo.io, try Prefix.parse(repo.object_format, nothing[0..12]), .none, null));
    const whole = try lookup.resolve(repo.io, try Prefix.parse(repo.object_format, nothing), .none, null);
    try testing.expect(Id.eql(Id.zero(repo.object_format), whole.found));
}

test "fuzz: prefixes" {
    try fuzz_input.fuzz({}, struct {
        fn one(_: void, smith: *testing.Smith) anyerror!void {
            var buffer: [80]u8 = undefined;
            const bytes = fuzz_input.bytes(smith, &buffer);
            for ([_]Format{ .sha1, .sha256 }) |format| {
                const p = Prefix.parse(format, bytes) catch {
                    try testing.expect(!isHex(bytes) or bytes.len > object.max_hex_length);
                    continue;
                };
                try testing.expect(isHex(bytes));
                var hex: [object.max_hex_length]u8 = undefined;
                const digits = p.toHex(&hex);
                try testing.expect(std.ascii.eqlIgnoreCase(digits, bytes[0..p.len]));
                try testing.expect(p.matches(p.lowest()));
                const again = try Prefix.parse(format, digits);
                try testing.expect(std.mem.eql(u8, &again.bytes, &p.bytes));
                try testing.expectEqual(digits.len, commonDigits(p.lowest(), again.lowest()) - (format.hexLength() - p.len));
            }
        }
    }.one, .{ .corpus = &.{ @embedFile("fuzz/abbrev-prefixes"), "2C7d5", "0", "4b825dc642cb6eb9a060e54bf8d69288fbee4904ffff" } });
}

test "fuzz: abbreviation lengths" {
    try fuzz_input.fuzz({}, struct {
        fn one(_: void, smith: *testing.Smith) anyerror!void {
            var buffer: [40]u8 = undefined;
            const bytes = fuzz_input.bytes(smith, &buffer);
            var diag: Diagnostics = .{};
            const length = parseLength(bytes, &diag) catch |err| switch (err) {
                error.LengthOutOfRange => return testing.expect(diag.detail().len > 0),
                else => return,
            };
            switch (length) {
                .digits => |n| try testing.expect(n >= min_length),
                .auto, .full => {},
            }
            var n: u64 = 0;
            for (bytes) |b| n = n *% 131 +% b;
            const auto = autoLength(n);
            try testing.expect(auto >= auto_min_length and auto <= 32);
            if (n > 0) try testing.expect(auto >= autoLength(n / 2));
            for ([_]Format{ .sha1, .sha256 }) |format| {
                const opt = optionLength(format, @as(i64, @bitCast(n)));
                if (opt) |o| try testing.expect(o >= min_length and o < format.hexLength());
            }
        }
    }.one, .{ .corpus = &.{ @embedFile("fuzz/abbrev-lengths"), "auto", "no", "4k", "07", "-1" } });
}

test "fuzz: the lines of an ambiguity hint" {
    try fuzz_input.fuzz({}, struct {
        fn one(_: void, smith: *testing.Smith) anyerror!void {
            var buffer: [512]u8 = undefined;
            const bytes = fuzz_input.bytes(smith, &buffer);
            var out: [1024]u8 = undefined;
            for ([_]Kind{ .commit, .tag }) |kind| {
                var w: Io.Writer = .fixed(&out);
                writeCandidate(&w, .sha1, kind, bytes) catch |err| switch (err) {
                    error.UnsupportedDate => continue,
                    error.WriteFailed => return err,
                };
                try testing.expect(std.mem.findScalar(u8, w.buffered(), '\n') == null);
            }
        }
    }.one, .{ .corpus = &.{ @embedFile("fuzz/commit"), @embedFile("fuzz/tag"), "tree 4b825dc642cb6eb9a060e54bf8d69288fbee4904\nauthor A <a@x> 1600000000 -1300\n\n\n \nfirst\n  second  \n\nbody\n" } });
}