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

//! git's glob dialect, as gitignore(5), gitglossary(7)'s `glob` pathspec
//! magic and git-config(1)'s `includeIf` describe it, with the corners the
//! documentation leaves out found by asking git: `git check-attr` for
//! patterns matched against whole paths, `git tag -l` for patterns that
//! are not, and `core.ignoreCase` and `--ignore-case` for case folding.
//! Ignore files, attributes, pathspecs, ref patterns and `includeIf` all
//! use it, so it depends on nothing else in the library.
//!
//! - `?` matches one byte, and `*` any run of bytes, empty included.
//! - `[...]` matches one byte from a set: single bytes, ranges `a-z`, and
//!   the classes `[:alpha:]` and its eleven POSIX siblings. A `!` or `^`
//!   first negates it, and a `]` first, after any negation, is a member.
//!   A `-` first or last is a member. A range runs from the byte before
//!   the `-` to the byte after it, either of them escapable; one whose
//!   end comes before its start matches only its start. Inside a set, `[:`
//!   begins a class only if the next `]` follows a second `:`, and is
//!   otherwise two members; an unknown class name, or a set that is never
//!   closed, makes the whole pattern match nothing. With `pathname`, a set
//!   never matches `/`, negated or not.
//! - `\` makes the next byte literal, inside a set as well as out, and a
//!   pattern ending in one matches nothing.
//!
//! With `pathname`, as paths are matched, no wildcard matches a `/`
//! except `**`, a run of two or more `*`s that is a path component of its
//! own — at the start of the pattern or after a `/`, and at its end or
//! before a `/` — which matches any run of bytes. Followed by a `/`, it
//! may also match nothing at all, slash included, so that `a/**/b`
//! matches `a/b`. Anywhere else a run of `*`s is one `*`.
//!
//! With `casefold`, ASCII letters match either case, except one written
//! after a `\`, which matches only a byte of its own case once the text
//! has been folded to lower case: git folds the text and every unescaped
//! byte of the pattern, and leaves escaped ones alone.

const std = @import("std");

/// How a pattern is matched.
pub const Flags = struct {
    /// Wildcards other than `**` do not match `/`, as when matching paths.
    pathname: bool = false,
    /// ASCII letters match regardless of case.
    casefold: bool = false,
};

/// Whether `text` matches the glob `pattern`.
pub fn match(pattern: []const u8, text: []const u8, flags: Flags) bool {
    var m: Matcher = .{ .pattern = pattern, .text = text, .flags = flags };
    return m.run();
}

/// Whether `pattern` holds anything that is not matched literally: an
/// unescaped `*`, `?`, `[` or `\`. A pattern without one matches only
/// itself, as git's ref and pathspec patterns treat it.
pub fn hasWildcards(pattern: []const u8) bool {
    for (pattern) |c| switch (c) {
        '*', '?', '[', '\\' => return true,
        else => {},
    };
    return false;
}

/// What one step through the pattern found.
const Token = union(enum) {
    /// A byte to match, and whether it was escaped.
    literal: struct { byte: u8, escaped: bool },
    /// `?`.
    any,
    /// A bracket expression, which ends where `end` says.
    set: struct { end: usize },
    /// `*`, which stops at a `/` under `pathname`.
    star,
    /// `**` as a whole component at the end of the pattern or before an
    /// escaped slash: anything at all.
    any_run,
    /// `**/`: nothing, or anything ending in a `/`.
    dirs,
    /// A pattern git rejects, which matches nothing.
    invalid,
};

const Matcher = struct {
    pattern: []const u8,
    text: []const u8,
    flags: Flags,

    /// Reads the token at `p`, and where the next one starts.
    fn token(m: *const Matcher, p: usize) struct { Token, usize } {
        const pat = m.pattern;
        switch (pat[p]) {
            '\\' => {
                if (p + 1 == pat.len) return .{ .invalid, p + 1 };
                return .{ .{ .literal = .{ .byte = pat[p + 1], .escaped = true } }, p + 2 };
            },
            '?' => return .{ .any, p + 1 },
            '[' => {
                const scan = scanSet(pat, p, 0, false) orelse return .{ .invalid, pat.len };
                return .{ .{ .set = .{ .end = scan.end } }, scan.end };
            },
            '*' => {
                var q = p;
                while (q < pat.len and pat[q] == '*') q += 1;
                if (!m.flags.pathname) return .{ .star, q };
                const stars = q - p;
                const starts_component = p == 0 or pat[p - 1] == '/';
                if (stars < 2 or !starts_component) return .{ .star, q };
                if (q == pat.len) return .{ .any_run, q };
                if (pat[q] == '/') return .{ .dirs, q + 1 };
                if (pat[q] == '\\' and q + 1 < pat.len and pat[q + 1] == '/') return .{ .any_run, q };
                return .{ .star, q };
            },
            else => |c| return .{ .{ .literal = .{ .byte = c, .escaped = false } }, p + 1 },
        }
    }

    fn fold(m: *const Matcher, c: u8) u8 {
        return if (m.flags.casefold) std.ascii.toLower(c) else c;
    }

    /// Whether the single-byte token at `p` (a literal, `?` or a set)
    /// matches `c`.
    fn matchesOne(m: *const Matcher, tok: Token, p: usize, c: u8) bool {
        return switch (tok) {
            .literal => |l| if (l.escaped) l.byte == m.fold(c) else m.fold(l.byte) == m.fold(c),
            .any => !(m.flags.pathname and c == '/'),
            .set => m.setMatches(p, c),
            else => unreachable,
        };
    }

    /// Whether the set from `start` (its `[`) matches `c`.
    fn setMatches(m: *const Matcher, start: usize, c: u8) bool {
        if (m.flags.pathname and c == '/') return false;
        const scan = scanSet(m.pattern, start, c, m.flags.casefold) orelse return false;
        return scan.found;
    }

    /// Matches the whole text against the whole pattern. A `*` that can
    /// stretch, and the last `**` that can, are each remembered as a
    /// place to resume from with more of the text taken by it; resuming
    /// from the latest of each is enough, since anything an earlier one
    /// could take a later one can take instead. That keeps the work to
    /// pattern length times text length, whatever the pattern.
    fn run(m: *Matcher) bool {
        const pat = m.pattern;
        const text = m.text;
        var p: usize = 0;
        var t: usize = 0;
        // Where to resume after the latest `*`: the pattern after it, and
        // the text it would take one more byte of.
        var star: ?struct { p: usize, t: usize } = null;
        // Likewise after the latest `**` or `**/`.
        var run_star: ?struct { p: usize, t: usize, dirs: bool } = null;
        while (true) {
            if (p < pat.len) {
                const tok, const next = m.token(p);
                switch (tok) {
                    .invalid => return false,
                    .star => {
                        star = .{ .p = next, .t = t + 1 };
                        p = next;
                        continue;
                    },
                    .any_run => {
                        if (next == pat.len) return true;
                        star = null;
                        run_star = .{ .p = next, .t = t + 1, .dirs = false };
                        p = next;
                        continue;
                    },
                    .dirs => {
                        star = null;
                        run_star = .{ .p = next, .t = t, .dirs = true };
                        p = next;
                        continue;
                    },
                    else => if (t < text.len and m.matchesOne(tok, p, text[t])) {
                        p = next;
                        t += 1;
                        continue;
                    },
                }
            } else if (t == text.len) return true;

            // A mismatch: take one more byte into the latest `*`, if it
            // can have one, or else more into the latest `**`.
            if (star) |*s| {
                if (s.t <= text.len and !(m.flags.pathname and text[s.t - 1] == '/')) {
                    p = s.p;
                    t = s.t;
                    s.t += 1;
                    continue;
                }
                star = null;
            }
            if (run_star) |*r| {
                if (r.dirs) {
                    // `**/` takes whole directories: up to and including
                    // the next slash.
                    const slash = std.mem.findScalarPos(u8, text, r.t, '/') orelse return false;
                    p = r.p;
                    t = slash + 1;
                    r.t = slash + 1;
                    continue;
                }
                if (r.t <= text.len) {
                    p = r.p;
                    t = r.t;
                    r.t += 1;
                    continue;
                }
            }
            return false;
        }
    }
};

/// Reads the set whose `[` is at `start`, and says where it ends, just
/// past its `]`, and whether it matches `c`; or null if nothing closes it
/// or it names an unknown class, when git matches nothing.
fn scanSet(pat: []const u8, start: usize, c: u8, casefold: bool) ?struct { end: usize, found: bool } {
    const t = if (casefold) std.ascii.toLower(c) else c;
    var i = start + 1;
    var negated = false;
    if (i < pat.len and (pat[i] == '!' or pat[i] == '^')) {
        negated = true;
        i += 1;
    }
    var found = false;
    var first = true;
    while (true) : (first = false) {
        if (i >= pat.len) return null;
        // A `]` first is a member.
        if (pat[i] == ']' and !first) return .{ .end = i + 1, .found = found != negated };
        if (pat[i] == '[' and i + 1 < pat.len and pat[i + 1] == ':') {
            if (classSpan(pat, i)) |span| {
                const class = Class.fromName(span.name) orelse return null;
                if (class.matches(c, casefold)) found = true;
                i = span.end;
                continue;
            }
        }
        var lo = pat[i];
        if (lo == '\\') {
            if (i + 1 == pat.len) return null;
            lo = pat[i + 1];
            i += 2;
            // An escaped byte is compared with the folded text as it is.
            if (lo == t) found = true;
        } else {
            i += 1;
            if ((if (casefold) std.ascii.toLower(lo) else lo) == t) found = true;
        }
        if (i + 1 < pat.len and pat[i] == '-' and pat[i + 1] != ']') {
            var hi = pat[i + 1];
            i += 2;
            if (hi == '\\') {
                if (i == pat.len) return null;
                hi = pat[i];
                i += 1;
            }
            if (lo <= t and t <= hi) found = true;
            if (casefold and std.ascii.isLower(t)) {
                const u = std.ascii.toUpper(t);
                if (lo <= u and u <= hi) found = true;
            }
        }
    }
}

/// The class named by `[:name:]` at `i`, and where it ends, if it is one:
/// a `[:` whose next `]` follows a colon other than its own.
fn classSpan(pat: []const u8, i: usize) ?struct { name: []const u8, end: usize } {
    const close = std.mem.findScalarPos(u8, pat, i + 2, ']') orelse return null;
    if (close == i + 2 or pat[close - 1] != ':') return null;
    return .{ .name = pat[i + 2 .. close - 1], .end = close + 1 };
}

/// The POSIX character classes, over ASCII only.
const Class = enum {
    alnum,
    alpha,
    blank,
    cntrl,
    digit,
    graph,
    lower,
    print,
    punct,
    space,
    upper,
    xdigit,

    fn fromName(name: []const u8) ?Class {
        return std.meta.stringToEnum(Class, name);
    }

    fn matches(class: Class, c: u8, casefold: bool) bool {
        return switch (class) {
            .alnum => std.ascii.isAlphanumeric(c),
            .alpha => std.ascii.isAlphabetic(c),
            .blank => c == ' ' or c == '\t',
            .cntrl => std.ascii.isControl(c),
            .digit => std.ascii.isDigit(c),
            .graph => c > ' ' and c < 0x7f,
            .lower => std.ascii.isLower(c) or (casefold and std.ascii.isUpper(c)),
            .print => c >= ' ' and c < 0x7f,
            .punct => std.ascii.isPrint(c) and !std.ascii.isAlphanumeric(c) and c != ' ',
            // Not vertical tab or form feed, which git leaves out.
            .space => c == ' ' or c == '\t' or c == '\n' or c == '\r',
            .upper => std.ascii.isUpper(c) or (casefold and std.ascii.isLower(c)),
            .xdigit => std.ascii.isHex(c),
        };
    }
};

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

/// The meaning of a pattern, followed the slow way: every way of
/// splitting the text among the wildcards is tried. The tests hold the
/// fast matcher to it.
fn reference(m: *const Matcher, p: usize, t: usize) bool {
    const pat = m.pattern;
    const text = m.text;
    if (p == pat.len) return t == text.len;
    const tok, const next = m.token(p);
    switch (tok) {
        .invalid => return false,
        .star => {
            var k = t;
            while (true) : (k += 1) {
                if (reference(m, next, k)) return true;
                if (k == text.len or (m.flags.pathname and text[k] == '/')) return false;
            }
        },
        .any_run => {
            for (t..text.len + 1) |k| if (reference(m, next, k)) return true;
            return false;
        },
        .dirs => {
            if (reference(m, next, t)) return true;
            for (t..text.len) |k| if (text[k] == '/' and reference(m, next, k + 1)) return true;
            return false;
        },
        else => return t < text.len and m.matchesOne(tok, p, text[t]) and reference(m, next, t + 1),
    }
}

fn referenceMatch(pattern: []const u8, text: []const u8, flags: Flags) bool {
    const m: Matcher = .{ .pattern = pattern, .text = text, .flags = flags };
    return reference(&m, 0, 0);
}

const all_flags = [_]Flags{ .{}, .{ .pathname = true }, .{ .casefold = true }, .{ .pathname = true, .casefold = true } };

fn expectMatch(want: bool, pattern: []const u8, text: []const u8, flags: Flags) !void {
    errdefer std.debug.print("pattern \"{f}\" text \"{f}\" {any}\n", .{ std.zig.fmtString(pattern), std.zig.fmtString(text), flags });
    try testing.expectEqual(want, match(pattern, text, flags));
    try testing.expectEqual(want, referenceMatch(pattern, text, flags));
}

test "wildcards match as git's do" {
    const path: Flags = .{ .pathname = true };
    try expectMatch(true, "*", ".x", path);
    try expectMatch(true, "a/**/b", "a/b", path);
    try expectMatch(true, "a/**/b", "a/x/y/b", path);
    try expectMatch(true, "a/**/b", "a//b", path);
    try expectMatch(false, "a**b", "ax/b", path);
    try expectMatch(true, "a**b", "ax/b", .{});
    try expectMatch(false, "a/**b", "a/x/b", path);
    try expectMatch(true, "**", "a/b", path);
    try expectMatch(true, "a/***/b", "a/x/y/b", path);
    try expectMatch(true, "abc/**", "abc/x/y", path);
    try expectMatch(false, "abc/**", "abc", path);
    try expectMatch(true, "a\\/**", "a/b/c", path);
    try expectMatch(true, "**\\/b", "x/y/b", path);
    try expectMatch(false, "a/**\\/b", "a/b", path);
    try expectMatch(true, "a/**\\/b", "a/x/b", path);
    try expectMatch(false, "a?b", "a/b", path);
    try expectMatch(true, "a?b", "a/b", .{});
    try expectMatch(false, "a[/]b", "a/b", path);
    try expectMatch(false, "a[!x]b", "a/b", path);
    try expectMatch(true, "a[/]b", "a/b", .{});
}

test "bracket expressions are read as git reads them" {
    try expectMatch(false, "a[", "a[", .{});
    try expectMatch(false, "a[]", "a[]", .{});
    try expectMatch(true, "a[]]", "a]", .{});
    try expectMatch(true, "a[!]]b", "axb", .{});
    try expectMatch(false, "a\\", "a\\", .{});
    try expectMatch(true, "a[b-]", "a-", .{});
    try expectMatch(true, "a[\\]]", "a]", .{});
    try expectMatch(false, "a[[:foo:]]", "a[", .{});
    try expectMatch(true, "a[z-a]", "az", .{});
    try expectMatch(false, "a[z-a]", "am", .{});
    try expectMatch(true, "a[[:]", "a:", .{});
    try expectMatch(true, "a[[:alpha]", "al", .{});
    try expectMatch(false, "a[[:alpha]", "ab", .{});
    try expectMatch(false, "a[a-[:digit:]]", "a5", .{});
    try expectMatch(true, "a[a-[:digit:]]", "a:]", .{});
    try expectMatch(true, "[a-c-e]", "-", .{});
    try expectMatch(false, "[a-c-e]", "d", .{});
    try expectMatch(true, "x[[:a]b:]", "x[b:]", .{});
    try expectMatch(false, "x[[:ALPHA:]]", "xa", .{});
    try expectMatch(true, "[[:xdigit:][:upper:]]", "G", .{});
    try expectMatch(false, "[[:space:]]", "\x0b", .{});
    try expectMatch(false, "[[:space:]]", "\x0c", .{});
    try expectMatch(true, "[[:space:]]", "\r", .{});
    try expectMatch(true, "[]-a]", "^", .{});
    try expectMatch(true, "x[\\]-a]", "x^", .{});
}

test "case folding leaves escaped bytes alone" {
    const fold: Flags = .{ .pathname = true, .casefold = true };
    try expectMatch(true, "abc", "aBc", fold);
    try expectMatch(true, "[A-Z]", "a", fold);
    try expectMatch(true, "[[:upper:]]", "a", fold);
    try expectMatch(false, "[!a]", "A", fold);
    try expectMatch(true, "[Z-a]", "z", fold);
    try expectMatch(false, "[Z-a]", "B", fold);
    try expectMatch(false, "\\A", "a", fold);
    try expectMatch(true, "\\a", "A", fold);
    try expectMatch(false, "[\\A]", "A", fold);
    try expectMatch(true, "[\\A]", "A", .{});
}

test "a pattern of many stars takes no longer than its length times the text's" {
    const pattern = "*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*b";
    const text: [4000]u8 = @splat('a');
    for (all_flags) |flags| try testing.expect(!match(pattern, &text, flags));
    const dirs: [90]u8 = @bitCast(@as([30][3]u8, @splat("**/".*)));
    const deep: [2000]u8 = @bitCast(@as([1000][2]u8, @splat("a/".*)));
    try testing.expect(!match(&dirs ++ "b", &deep, .{ .pathname = true }));
}

/// Patterns for the comparisons with git: every one of up to three bytes
/// from an alphabet of the bytes that mean something, and those the
/// experiments that shaped this file used.
fn differentialPatterns(gpa: std.mem.Allocator) !std.ArrayList([]u8) {
    var list: std.ArrayList([]u8) = .empty;
    errdefer {
        for (list.items) |p| gpa.free(p);
        list.deinit(gpa);
    }
    const alphabet = "a/*?[]!-\\";
    for (1..4) |len| {
        var digits: [3]usize = @splat(0);
        outer: while (true) {
            var buf: [3]u8 = undefined;
            for (0..len) |k| buf[k] = alphabet[digits[k]];
            try list.append(gpa, try gpa.dupe(u8, buf[0..len]));
            var k: usize = 0;
            while (k < len) : (k += 1) {
                digits[k] += 1;
                if (digits[k] < alphabet.len) continue :outer;
                digits[k] = 0;
            }
            break;
        }
    }
    for (handwritten_patterns) |p| try list.append(gpa, try gpa.dupe(u8, p));
    return list;
}

const handwritten_patterns = [_][]const u8{
    "abc/**",                "**/x",          "a/**/b",         "a**b",           "**a",           "a**",
    "a/**b",                 "a**/b",         "**",             "***",            "a/***/b",       "a[/]b",
    "a[!x]b",                "a?b",           "a[",             "a[]",            "a[]]",          "a[!]]b",
    "a[b-]",                 "a[\\]]",        "a[[:alpha:]]",   "a[[:foo:]]",     "a[z-a]",        "[a-]x",
    "a[-z]",                 "a[^b]",         "a[[]",           "a[[:]",          "a[x[:digit:]]", "a[[:alpha:]",
    "a[[:alpha]",            "a[[:alpha:]x]", "a[[:alpha:]-z]", "a[a-[:digit:]]", "a[!",           "a[\\",
    "a[a\\-z]",              "a[\\a-\\z]",    "a\\*",           "a\\[b]",         "a[:alpha:]",    "[[:space:]]",
    "[[:xdigit:][:upper:]]", "[[:punct:]]",   "[[:print:]]",    "[[:graph:]]",    "[[:blank:]]",   "[[:cntrl:]]",
    "[[:lower:]]",           "[[:upper:]]",   "[[:alnum:]]",    "[[:digit:]]",    "*/*",           "**/**",
    "**/b/**",               "a/**/**/b",     "*a/**",          "\\\\",           "[\\\\]",        "a[^]]",
    "[]-a]",                 "[!]-a]",        "a[--0]",         "[[:alpha:]-]",   "[a-c-e]",       "**/a/**/b/**",
    "*.c",                   "[[:",           "[[:]]",          "[[::]]",         "[[=a=]]",       "[[.a.]]",
    "a?",                    "[\\A]",         "\\a",            "\\A",            "[a-\\]]",       "x[[:a]b:]",
    "[[:alpha:][:a]",        "x[a-]]",        "[a-z-]",         "x[[:al]",        "x[[:alpha:]]",  "x[[:ALPHA:]]",
    "x[[:alpha:]y",          "[a-]]",         "x[\\]-a]",       "x[!/]",          "x*/y",          "a/***b",
    "a\\/**",                "**\\/b",        "a/**\\/b",       "a/\\**/b",       "a/*\\*/b",      "[Z-a]",
    "[^-z]",                 "[A-Z]",         "[a-z]",          "A*",             "*B",            "a/*/b",
    "*/b/*",                 "a/**/*",        "**/*b",          "?/?",            "*?*",           "[!a-b]*",
    "a*b*c",                 "*a*b",          "a/b",            "A/B",            "**/A",          "a*/**/b",
    "\\**",                  "*\\*",          "\\?",            "[?*]",           "[*]/[?]",       "a[!a/]",
};

/// Paths for the comparisons with git: no slash first or last, no empty
/// component, since `git check-attr` reads those as something else.
const differential_paths = [_][]const u8{
    "a",         "b",        "A",     "B",       "ab",     "aB",      "Ab",    "aa",    "abc",     "ABC",
    "a/b",       "a/B",      "A/b",   "a/a",     "a/x/b",  "a/x/y/b", "a/b/c", "x/a",   "x/y/a",   "ax/b",
    "a-",        "-",        "-a",    "a-b",     "a]",     "]",       "a[",    "[",     "a!",      "!",
    "a*",        "*",        "a?",    "?",       "a\\",    "\\",      "a\\b",  "a\\/b", "*/?",     "a^",
    "^",         ":",        "a:",    "a:]",     "a[b:]",  "x[b:]",   "_",     "z",     "Z",       "m",
    "5",         " ",        "\t",    "\n",      "\r",     "\x0c",    "\x0b",  "\x01",  "\x7f",    "a.c",
    "x.c",       "d/x.c",    "abc/x", "abc/x/y", "xa/b",   "b/c",     "x/b/c", "a/b/x", "a/x/b/y", "x/a/y/b/z",
    "a\xc3\xa9", "\xc3\xa9", "a/xb",  "axb",     "abcabc", "a/b/b",   "aa/bb", "*/b/*", "[]",      "a[]",
};

/// Writes `s` C-quoted, as a `.gitattributes` pattern may be.
fn writeQuoted(w: *std.Io.Writer, s: []const u8) !void {
    try w.writeByte('"');
    for (s) |c| {
        if (c == '"' or c == '\\') {
            try w.writeAll(&.{ '\\', c });
        } else if (c < 0x20 or c >= 0x7f) {
            try w.print("\\{o:0>3}", .{c});
        } else try w.writeByte(c);
    }
    try w.writeByte('"');
}

test "patterns match whole paths as git check-attr matches them" {
    const gpa = testing.allocator;
    var repo = try fixture.Repo.init(gpa, testing.io);
    defer repo.deinit();
    var patterns = try differentialPatterns(gpa);
    defer {
        for (patterns.items) |p| gpa.free(p);
        patterns.deinit(gpa);
    }

    // One attribute per pattern, each anchored by a leading slash so that
    // it is matched against the whole path, as `pathname` matches. git
    // reads a pattern ending in a slash as one only for directories, so
    // those are left out.
    var attributes: std.Io.Writer.Allocating = .init(gpa);
    defer attributes.deinit();
    var kept: std.ArrayList(usize) = .empty;
    defer kept.deinit(gpa);
    for (patterns.items, 0..) |p, i| {
        if (p[p.len - 1] == '/') continue;
        // An escaped slash at the end is the same to git.
        if (std.mem.endsWith(u8, p, "\\/")) continue;
        const anchored = try std.fmt.allocPrint(gpa, "/{s}", .{p});
        defer gpa.free(anchored);
        try writeQuoted(&attributes.writer, anchored);
        try attributes.writer.print(" p{d}\n", .{i});
        try kept.append(gpa, i);
    }
    try repo.tmp.dir.writeFile(repo.io, .{ .sub_path = ".gitattributes", .data = attributes.written() });

    var input: std.ArrayList(u8) = .empty;
    defer input.deinit(gpa);
    for (differential_paths) |path| {
        try input.appendSlice(gpa, path);
        try input.append(gpa, 0);
    }

    for ([_]bool{ false, true }) |casefold| {
        const args: []const []const u8 = if (casefold)
            &.{ "-c", "core.ignoreCase=true", "check-attr", "--stdin", "-z", "-a" }
        else
            &.{ "check-attr", "--stdin", "-z", "-a" };
        const out = try repo.outputWithInput(args, input.items);
        defer gpa.free(out);
        // Which (path, pattern) pairs git says match.
        var matched: std.AutoHashMapUnmanaged(struct { usize, usize }, void) = .empty;
        defer matched.deinit(gpa);
        var fields = std.mem.splitScalar(u8, out, 0);
        while (fields.next()) |path| {
            if (path.len == 0) break;
            const attr = fields.next().?;
            _ = fields.next().?;
            const path_index = for (differential_paths, 0..) |p, k| {
                if (std.mem.eql(u8, p, path)) break k;
            } else return error.UnexpectedPath;
            const pattern_index = try std.fmt.parseInt(usize, attr[1..], 10);
            try matched.put(gpa, .{ path_index, pattern_index }, {});
        }
        var compared: usize = 0;
        for (kept.items) |i| {
            for (differential_paths, 0..) |path, k| {
                const want = matched.contains(.{ k, i });
                try expectMatch(want, patterns.items[i], path, .{ .pathname = true, .casefold = casefold });
                compared += 1;
            }
        }
        try testing.expect(compared > 50_000);
    }
}

test "patterns match names without the pathname rule as git tag -l matches them" {
    const gpa = testing.allocator;
    var repo = try fixture.Repo.init(gpa, testing.io);
    defer repo.deinit();
    try repo.commit("first");
    const names = [_][]const u8{
        "a", "ab", "b", "A", "Ab", "a-b", "a.b", "c/d", "c/de", "e/f/g", "e/fg", "-a", "a]b", "!a", "a!b", "xay", "aXa/b",
    };
    var updates: std.ArrayList(u8) = .empty;
    defer updates.deinit(gpa);
    for (names) |n| try updates.print(gpa, "create refs/tags/{s} HEAD\n", .{n});
    const ignored = try repo.outputWithInput(&.{ "update-ref", "--stdin" }, updates.items);
    gpa.free(ignored);

    const patterns = handwritten_patterns ++ [_][]const u8{ "a*", "*b", "a?b", "c*", "[a-c]*", "*/*", "e**g", "?", "*", "[!a]*", "a[!/]b", "*X*" };
    for (patterns) |pattern| {
        for ([_]bool{ false, true }) |casefold| {
            const args: []const []const u8 = if (casefold) &.{ "tag", "-l", "-i", pattern } else &.{ "tag", "-l", pattern };
            const out = try repo.output(args);
            defer gpa.free(out);
            for (names) |n| {
                var lines = std.mem.splitScalar(u8, out, '\n');
                const want = while (lines.next()) |l| {
                    if (std.mem.eql(u8, l, n)) break true;
                } else false;
                try expectMatch(want, pattern, n, .{ .casefold = casefold });
            }
        }
    }
}

fn fuzzOne(_: void, smith: *testing.Smith) anyerror!void {
    var buffer: [256]u8 = undefined;
    const input = fuzz_input.bytes(smith, &buffer);
    // The pattern, a NUL, and the text.
    const nul = std.mem.findScalar(u8, input, 0) orelse input.len;
    const pattern = input[0..nul];
    const text = if (nul == input.len) "" else input[nul + 1 ..];
    for (all_flags) |flags| {
        const got = match(pattern, text, flags);
        // The slow way is exponential, so it is asked only of what it can
        // answer quickly.
        if (pattern.len <= 24 and text.len <= 24) try testing.expectEqual(referenceMatch(pattern, text, flags), got);
    }
}

test "fuzz: wildmatch" {
    try fuzz_input.fuzz({}, fuzzOne, .{ .corpus = &.{
        @embedFile("fuzz/wildmatch-dirs"),
        @embedFile("fuzz/wildmatch-set"),
        @embedFile("fuzz/wildmatch-stars"),
    } });
}