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

//! The pickaxe: changed paths kept only where they change what is looked
//! for, as gitdiffcore(7) describes `-S`, `-G` and `--find-object`, and
//! `--pickaxe-all` keeping every path of a diff where one is kept.
//!
//! What the documentation leaves out was found by asking git 2.56, one
//! commit at a time, whether it kept a change between two texts chosen
//! to tell rules apart (the probes are in the notes of the change that
//! brought this in):
//!
//! - `-S<string>` counts the string's occurrences in each side without
//!   letting them overlap (`aaaa` holds `aa` twice), and keeps a path whose
//!   two counts differ; an absent side holds none. NUL bytes are searched
//!   over like any other, so binary files are searched too. `-i` makes the
//!   comparison ignore the case of ASCII letters.
//! - With `--pickaxe-regex` the string is an extended regular expression,
//!   compiled as `REG_NEWLINE` compiles it (`.` and `^`, `$` keep to a line)
//!   and with GNU's escapes, `.` matching no NUL. Its matches are counted
//!   by searching again where the last one ended, the rest of the text
//!   taken as a new text that does not begin a line (`REG_NOTBOL`: `^`
//!   does not match at its start, even just after a newline, while `\<`,
//!   `\b` and `` \` `` do, seeing nothing before it). A match that is empty
//!   counts, and the search goes on one byte further. Searching stops at
//!   the end of the text, so an empty match there is not counted unless it
//!   is the first search's.
//! - `-G<regex>` keeps a path whose line diff adds or deletes a line the
//!   expression (extended, `REG_NEWLINE`, GNU's escapes) matches. Each
//!   line is matched alone, with its newline (one is added to a last line
//!   that has none, so `^$` matches every changed line); the `+` or `-`
//!   of the patch is not part of it, and context lines are not looked at.
//!   The line diff is the plain one, whatever the whitespace options say;
//!   a type change is compared as the two sides' contents, not as the
//!   deletion and addition the patch shows. A binary file is passed over
//!   unless `--text` is given.
//! - `--find-object=<object>` keeps a path whose old or new side is that
//!   object, whatever its mode or path (a rename of it is kept, and so is a
//!   change of its mode alone).
//! - `--pickaxe-all` keeps every path when any is kept, and nothing
//!   otherwise. `--diff-filter` applies afterwards.

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

const object = @import("../object.zig");
const regex = @import("../regex.zig");
const LineDiff = @import("LineDiff.zig");
const output = @import("output.zig");

const Pickaxe = @This();

/// What is looked for.
pub const Kind = enum {
    /// `-S<string>`: a fixed string, counted.
    string,
    /// `-S<regex> --pickaxe-regex`: an extended regular expression,
    /// counted.
    counted_regex,
    /// `-G<regex>`: an extended regular expression, matched against the
    /// lines a diff adds and deletes.
    lines,
    /// `--find-object=<object>`.
    object,
};

kind: Kind,
/// The string for `string`.
needle: []const u8 = "",
/// The compiled pattern for `counted_regex` and `lines`.
pattern: ?regex.Regex = null,
/// The objects for `object`: `--find-object` may be given more than
/// once, and a side that is any of them is kept.
ids: []const object.Id = &.{},
/// `-i`, `--regexp-ignore-case`.
ignore_case: bool = false,
/// `--pickaxe-all`.
all: bool = false,

/// Why a pickaxe's pattern was not compiled.
pub const CompileError = regex.Error;

/// A pickaxe looking for `text` as `kind` says (any but `object`); on
/// `InvalidPattern` or `Unsupported`, `failure` says why. `text` must
/// outlive it.
pub fn init(gpa: Allocator, kind: Kind, text: []const u8, ignore_case: bool, failure: ?*regex.Failure) CompileError!Pickaxe {
    switch (kind) {
        .string => return .{ .kind = .string, .needle = text, .ignore_case = ignore_case },
        .counted_regex, .lines => {
            const r = try regex.Regex.compileWith(gpa, text, .{
                .syntax = .extended,
                .newline = true,
                .gnu = true,
                .ignore_case = ignore_case,
                .dot_excludes_nul = true,
            }, failure);
            return .{ .kind = kind, .pattern = r, .ignore_case = ignore_case };
        },
        .object => unreachable,
    }
}

/// A pickaxe looking for the objects `ids`, which must outlive it.
pub fn initObjects(ids: []const object.Id) Pickaxe {
    return .{ .kind = .object, .ids = ids };
}

/// Frees the pattern.
pub fn deinit(p: *Pickaxe) void {
    if (p.pattern) |*r| r.deinit();
    p.* = undefined;
}

/// How many times `-S` finds what it looks for in `text`.
pub fn count(p: *const Pickaxe, gpa: Allocator, text: []const u8) Allocator.Error!usize {
    switch (p.kind) {
        .string => return countString(p.needle, text, p.ignore_case),
        .counted_regex => {
            const r = &p.pattern.?;
            var n: usize = 0;
            var pos: usize = 0;
            while (pos < text.len) {
                const m = try r.search(gpa, text[pos..], pos != 0) orelse break;
                n += 1;
                pos += if (m.end == m.start) m.start + 1 else m.end;
            }
            return n;
        },
        .lines, .object => unreachable,
    }
}

fn countString(needle: []const u8, text: []const u8, ignore_case: bool) usize {
    if (needle.len == 0) return 0;
    var n: usize = 0;
    var pos: usize = 0;
    while (pos + needle.len <= text.len) {
        const here = text[pos .. pos + needle.len];
        const same = if (ignore_case) std.ascii.eqlIgnoreCase(here, needle) else std.mem.eql(u8, here, needle);
        if (same) {
            n += 1;
            pos += needle.len;
        } else pos += 1;
    }
    return n;
}

/// Whether `-G` finds a line it matches among those the line diff of
/// `old` and `new` adds or deletes, compared with `algorithm`.
pub fn changesLines(p: *const Pickaxe, gpa: Allocator, old: []const u8, new: []const u8, algorithm: LineDiff.Algorithm) LineDiff.Error!bool {
    var d = try LineDiff.compute(gpa, old, new, .{ .algorithm = algorithm, .indent_heuristic = false });
    defer d.deinit(gpa);
    var line: std.ArrayList(u8) = .empty;
    defer line.deinit(gpa);
    for ([_]LineDiff.Lines{ d.a, d.b }, [_][]const bool{ d.a_changed, d.b_changed }) |lines, changed| {
        for (changed, 0..) |c, i| {
            if (!c) continue;
            const text = lines.line(i);
            if (text.len != 0 and text[text.len - 1] == '\n') {
                if (try p.pattern.?.matches(gpa, text)) return true;
                continue;
            }
            line.clearRetainingCapacity();
            try line.appendSlice(gpa, text);
            try line.append(gpa, '\n');
            if (try p.pattern.?.matches(gpa, line.items)) return true;
        }
    }
    return false;
}

/// What filtering can fail with.
pub const Error = output.Error || error{
    /// `-S` or `-G` met a tree's pair (`-t`), whose sides git cannot
    /// read as files to diff.
    TreeContents,
};

/// Whether pair `p` changes what is looked for. `options` are the
/// formats' options: their `--text` and binary rules decide which files
/// `-G` passes over, and their algorithm is the line diff's.
pub fn keeps(pk: *const Pickaxe, gpa: Allocator, p: *const output.Pair, source: output.Source, drivers: output.Drivers, options: output.Options) Error!bool {
    if (pk.kind == .object) {
        for (pk.ids) |id| {
            if (p.old.present() and p.old.id_known and p.old.id.eql(id)) return true;
            if (p.new.present() and p.new.id_known and p.new.id.eql(id)) return true;
        }
        return false;
    }
    if (output.isTree(p)) return error.TreeContents;
    var ob: [64 + object.max_hex_length]u8 = undefined;
    var nb: [64 + object.max_hex_length]u8 = undefined;
    const old: output.Contents = if (p.old.present()) try output.load(gpa, p, p.old, true, source, &ob) else .{ .bytes = "" };
    defer output.free(gpa, old);
    const new: output.Contents = if (p.new.present()) try output.load(gpa, p, p.new, false, source, &nb) else .{ .bytes = "" };
    defer output.free(gpa, new);
    switch (pk.kind) {
        .string, .counted_regex => return try pk.count(gpa, old.bytes) != try pk.count(gpa, new.bytes),
        .lines => {
            const driver = try drivers.get(drivers.context, p.path);
            if (output.binaryPair(p, old.bytes, new.bytes, driver, options)) return false;
            return pk.changesLines(gpa, old.bytes, new.bytes, options.patch.lines.algorithm);
        },
        .object => unreachable,
    }
}

/// The pairs of `pairs` the pickaxe keeps: those it finds a change in,
/// or with `--pickaxe-all` every one if it finds any. The caller frees
/// the list.
pub fn filter(pk: *const Pickaxe, gpa: Allocator, pairs: []const output.Pair, source: output.Source, drivers: output.Drivers, options: output.Options) Error![]output.Pair {
    var kept: std.ArrayList(output.Pair) = .empty;
    errdefer kept.deinit(gpa);
    for (pairs) |*p| {
        if (!try pk.keeps(gpa, p, source, drivers, options)) continue;
        if (pk.all) {
            kept.clearRetainingCapacity();
            try kept.appendSlice(gpa, pairs);
            break;
        }
        try kept.append(gpa, p.*);
    }
    return kept.toOwnedSlice(gpa);
}

test "fixed strings are counted without overlapping" {
    try std.testing.expectEqual(@as(usize, 2), countString("aa", "aaaa", false));
    try std.testing.expectEqual(@as(usize, 2), countString("aa", "aaaaa", false));
    try std.testing.expectEqual(@as(usize, 2), countString("a", "a\x00a", false));
    try std.testing.expectEqual(@as(usize, 2), countString("a", "aA", true));
    try std.testing.expectEqual(@as(usize, 0), countString("abc", "ab", false));
}

test "a pattern's matches are counted as git counts them" {
    const gpa = std.testing.allocator;
    const cases = [_]struct { []const u8, []const u8, usize }{
        // Empty matches count, one byte at a time, but not at the end.
        .{ "a*", "x\n", 2 },
        .{ "a*", "aaa\n", 2 },
        .{ "a*", "aa aa\n", 4 },
        .{ "a*", "", 0 },
        // `^` keeps to lines, and not where a search resumes.
        .{ "^a", "aa", 1 },
        .{ "^a", "a\na\n", 2 },
        .{ "^a*", "\na", 1 },
        .{ "^a*", "x\na", 2 },
        // `\<` and `` \` `` see nothing before where a search resumes.
        .{ "\\<a", "aa", 2 },
        .{ "\\`a", "aa", 2 },
        // `.` matches no NUL or newline.
        .{ "a.b", "a\x00b", 0 },
        .{ "a.", "a\nb", 0 },
        .{ "a[^x]b", "a\x00b", 1 },
    };
    for (cases) |c| {
        var p = try Pickaxe.init(gpa, .counted_regex, c[0], false, null);
        defer p.deinit();
        std.testing.expectEqual(c[2], try p.count(gpa, c[1])) catch |err| {
            std.debug.print("pattern '{s}' text '{s}'\n", .{ c[0], c[1] });
            return err;
        };
    }
}

test "-G matches each changed line with its newline" {
    const gpa = std.testing.allocator;
    const cases = [_]struct { []const u8, []const u8, []const u8, bool }{
        .{ "^y", "x\n", "y\n", true },
        .{ "^\\+", "x\n", "y\n", false },
        .{ "y\n", "x\ny\n", "y", true },
        .{ "y\\'", "x\ny\n", "y", false },
        .{ "^$", "x\n", "x\nq", true },
        .{ "a", "a\nb\nc\n", "a\nB\nc\n", false },
        .{ "x\ny", "z\n", "x\ny\n", false },
        .{ "\\`y", "z\n", "x\ny\n", true },
        .{ "b", "x\n", "a\x00b\n", true },
        .{ "a.b", "x\n", "a\x00b\n", false },
    };
    for (cases) |c| {
        var p = try Pickaxe.init(gpa, .lines, c[0], false, null);
        defer p.deinit();
        std.testing.expectEqual(c[3], try p.changesLines(gpa, c[1], c[2], .myers)) catch |err| {
            std.debug.print("pattern '{s}'\n", .{c[0]});
            return err;
        };
    }
}

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

/// A pattern line, then a text: its `--pickaxe-regex` count must not run
/// past the text, and a fixed string's count must not exceed what fits.
fn fuzzCount(_: void, smith: *std.testing.Smith) anyerror!void {
    const gpa = std.testing.allocator;
    var buffer: [512]u8 = undefined;
    const input = fuzz_input.bytes(smith, &buffer);
    const nl = std.mem.findScalar(u8, input, '\n') orelse return;
    const pattern = input[0..nl];
    const text = input[nl + 1 ..];
    if (pattern.len != 0) {
        const n = countString(pattern, text, false);
        try std.testing.expect(n * pattern.len <= text.len);
    }
    var p = Pickaxe.init(gpa, .counted_regex, pattern, false, null) catch return;
    defer p.deinit();
    try std.testing.expect(try p.count(gpa, text) <= text.len + 1);
}

test "fuzz: pickaxe counts" {
    try fuzz_input.fuzz({}, fuzzCount, .{ .corpus = &.{@embedFile("../fuzz/pickaxe-count")} });
}