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

//! The order changed paths are written in: an orderfile's patterns
//! (`-O<orderfile>`, `diff.orderFile`) and `--skip-to` and `--rotate-to`,
//! as gitdiffcore(7) and git-diff(1) describe them.
//!
//! - An orderfile is read a line at a time; blank lines and lines
//!   beginning with `#` are passed over, and a `\` before a leading `#`
//!   is dropped. A path takes the place of the first pattern that matches
//!   it or any of the directories it is in, matched as `fnmatch(3)` does
//!   without `FNM_PATHNAME` (so `*` matches a `/`); paths no pattern
//!   matches come last, and paths of one place keep their order.
//! - `--skip-to=<path>` drops the paths before the one named and
//!   `--rotate-to=<path>` moves them to the end. For `git diff` the path
//!   must be one of those changed ("No such path '<path>' in the diff");
//!   `git log` starts instead from the first path that sorts at or after
//!   it, if any.
//! - Both look at the whole paths, as they were before `--relative` cut
//!   them short: `-O` with a pattern `dir/x`, or `--rotate-to=dir/x`,
//!   finds the path `--relative=dir/` writes as `x`, and a pattern or
//!   name `x` does not.

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

const wildmatch = @import("../wildmatch.zig");
const output = @import("output.zig");

/// The patterns of an orderfile, in its order; they borrow from its
/// text.
pub const OrderFile = struct {
    patterns: [][]const u8,

    /// Reads `text`'s patterns. The caller frees the list with `deinit`.
    pub fn parse(gpa: Allocator, text: []const u8) Allocator.Error!OrderFile {
        var list: std.ArrayList([]const u8) = .empty;
        errdefer list.deinit(gpa);
        var it = std.mem.splitScalar(u8, text, '\n');
        while (it.next()) |line| {
            if (line.len == 0 or line[0] == '#') continue;
            try list.append(gpa, if (std.mem.startsWith(u8, line, "\\#")) line[1..] else line);
        }
        return .{ .patterns = try list.toOwnedSlice(gpa) };
    }

    pub fn deinit(o: *OrderFile, gpa: Allocator) void {
        gpa.free(o.patterns);
        o.* = undefined;
    }

    /// The place of `path`: the index of the first pattern matching it or
    /// a directory it is in, or the number of patterns.
    pub fn rank(o: OrderFile, path: []const u8) usize {
        for (o.patterns, 0..) |p, i| {
            var end = path.len;
            while (true) {
                if (wildmatch.match(p, path[0..end], .{})) return i;
                end = std.mem.findScalarLast(u8, path[0..end], '/') orelse break;
            }
        }
        return o.patterns.len;
    }

    /// Sorts `pairs` by place, keeping the order of paths of one place.
    /// Each is placed by its entry in `paths`, which is sorted with it:
    /// the path as git saw it before `--relative` cut it short (a rename
    /// or copy by its new path).
    pub fn sort(o: OrderFile, gpa: Allocator, pairs: []output.Pair, paths: [][]const u8) Allocator.Error!void {
        std.debug.assert(pairs.len == paths.len);
        const ranks = try gpa.alloc(usize, pairs.len);
        defer gpa.free(ranks);
        const order = try gpa.alloc(usize, pairs.len);
        defer gpa.free(order);
        for (paths, ranks, order, 0..) |path, *r, *k, i| {
            r.* = o.rank(path);
            k.* = i;
        }
        std.mem.sort(usize, order, ranks, struct {
            fn less(rs: []const usize, a: usize, b: usize) bool {
                if (rs[a] != rs[b]) return rs[a] < rs[b];
                return a < b;
            }
        }.less);
        const copy = try gpa.dupe(output.Pair, pairs);
        defer gpa.free(copy);
        const path_copy = try gpa.dupe([]const u8, paths);
        defer gpa.free(path_copy);
        for (order, 0..) |k, i| {
            pairs[i] = copy[k];
            paths[i] = path_copy[k];
        }
    }
};

/// What `rotate` does with the paths before the one named.
pub const Rotation = enum {
    /// `--skip-to`: drop them.
    skip,
    /// `--rotate-to`: move them to the end.
    rotate,
};

/// Where `--skip-to` or `--rotate-to` starts among `paths`, one per
/// pair as `OrderFile.sort` takes them: the path that is `name`, or,
/// with `nearest` as `git log` looks, the first that sorts at or after
/// it; null when there is none. The name is compared with the whole
/// paths, before `--relative` cuts them.
pub fn start(paths: []const []const u8, name: []const u8, nearest: bool) ?usize {
    for (paths, 0..) |path, i| {
        const o = std.mem.order(u8, path, name);
        if (o == .eq or (nearest and o == .gt)) return i;
    }
    return null;
}

/// Rotates `pairs` in place to begin at `at`, as `how` says, returning
/// the pairs kept.
pub fn rotate(pairs: []output.Pair, at: usize, how: Rotation) []output.Pair {
    switch (how) {
        .skip => {
            std.mem.copyForwards(output.Pair, pairs[0 .. pairs.len - at], pairs[at..]);
            return pairs[0 .. pairs.len - at];
        },
        .rotate => {
            std.mem.rotate(output.Pair, pairs, at);
            return pairs;
        },
    }
}

test "orderfile places" {
    const gpa = std.testing.allocator;
    var o = try OrderFile.parse(gpa, "*.h\n\n# comment\nb\nREADME\n\\#x\n");
    defer o.deinit(gpa);
    try std.testing.expectEqual(@as(usize, 4), o.patterns.len);
    try std.testing.expectEqual(@as(usize, 0), o.rank("a/y.h"));
    try std.testing.expectEqual(@as(usize, 1), o.rank("b/z.c"));
    try std.testing.expectEqual(@as(usize, 2), o.rank("README"));
    try std.testing.expectEqual(@as(usize, 3), o.rank("#x"));
    try std.testing.expectEqual(@as(usize, 4), o.rank("a/x.c"));
}

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

/// An orderfile, a NUL, then NUL-separated paths: each takes a place no
/// further than one past the patterns.
fn fuzzOrder(_: void, smith: *std.testing.Smith) anyerror!void {
    const gpa = std.testing.allocator;
    var buffer: [512]u8 = undefined;
    const input = fuzz_input.bytes(smith, &buffer);
    var parts = std.mem.splitScalar(u8, input, 0);
    var o = try OrderFile.parse(gpa, parts.next() orelse return);
    defer o.deinit(gpa);
    while (parts.next()) |path| try std.testing.expect(o.rank(path) <= o.patterns.len);
}

test "fuzz: orderfile places" {
    try fuzz_input.fuzz({}, fuzzOrder, .{ .corpus = &.{@embedFile("../fuzz/orderfile")} });
}