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

//! The hunks of a patch: the changes of a `LineDiff` gathered with their
//! context, as `git diff` gathers them, and the text after `@@` that names
//! the function a hunk is in.

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

const LineDiff = @import("LineDiff.zig");

/// A run of changed lines: `a_len` lines of the old text from `a`
/// replaced by `b_len` lines of the new one from `b`, with the lines
/// before it matched one for one.
pub const Change = struct {
    a: usize,
    a_len: usize,
    b: usize,
    b_len: usize,
};

/// One hunk: the lines `a_start..a_start+a_len` of the old text and
/// `b_start..b_start+b_len` of the new, and the changes it shows.
pub const Hunk = struct {
    a_start: usize,
    a_len: usize,
    b_start: usize,
    b_len: usize,
    /// The changes inside it, as indexes into the list it was made from.
    first: usize,
    end: usize,
};

/// Which changes a patch may leave out, and how much context it shows.
pub const Options = struct {
    /// `-U<n>`: lines of context around each change.
    context: usize = 3,
    /// `--inter-hunk-context`: unchanged lines between two hunks that may
    /// join them into one, beyond those their context already joins.
    inter_hunk_context: usize = 0,
    /// `--ignore-blank-lines`.
    ignore_blank_lines: bool = false,
    /// Whether any whitespace option is set, which changes what
    /// `--ignore-blank-lines` takes for blank.
    whitespace: bool = false,
    /// `-I<regex>`: says whether a line (without its newline) is one whose
    /// changes may be left out. A seam for the caller's regular
    /// expressions.
    ignore_line: ?IgnoreLine = null,
    /// `-W`, `--function-context`: each hunk shows the whole of the
    /// functions its changes are in, as `function_lines` finds them. The
    /// caller refuses it together with `--ignore-blank-lines` and `-I`.
    function_context: bool = false,
    /// The rule for function lines, for `function_context`.
    function_lines: FunctionFinder = .default,
};

/// A predicate over lines, for `-I`.
pub const IgnoreLine = struct {
    context: *const anyopaque,
    matches: *const fn (context: *const anyopaque, line: []const u8) Allocator.Error!bool,
};

/// The changes of `d`, in order.
pub fn changes(gpa: Allocator, d: *const LineDiff) Allocator.Error![]Change {
    var out: std.ArrayList(Change) = .empty;
    errdefer out.deinit(gpa);
    var i: usize = 0;
    var j: usize = 0;
    const n = d.a_changed.len;
    const m = d.b_changed.len;
    while (i < n or j < m) {
        if ((i < n and d.a_changed[i]) or (j < m and d.b_changed[j])) {
            const si = i;
            const sj = j;
            while (i < n and d.a_changed[i]) i += 1;
            while (j < m and d.b_changed[j]) j += 1;
            try out.append(gpa, .{ .a = si, .a_len = i - si, .b = sj, .b_len = j - sj });
        } else {
            i += 1;
            j += 1;
        }
    }
    return out.toOwnedSlice(gpa);
}

/// Whether `--ignore-blank-lines` takes `line` for blank. With any
/// whitespace option, a line of blank space is blank; without one, git
/// takes only a line of at most one byte for blank: an empty line, or, as
/// git was seen to, a last line of one byte without a newline.
fn isBlank(line: []const u8, whitespace: bool) bool {
    if (!whitespace) return line.len <= 1;
    for (line) |c| switch (c) {
        ' ', '\t', '\r', '\n' => {},
        else => return false,
    };
    return true;
}

fn stripNewline(line: []const u8) []const u8 {
    return if (line.len != 0 and line[line.len - 1] == '\n') line[0 .. line.len - 1] else line;
}

/// Whether a change may be left out: every line of it blank, under
/// `--ignore-blank-lines`, or every line of it matching `-I`. A change of
/// blank lines and matching ones together is shown, as git was seen to.
fn ignorable(d: *const LineDiff, c: Change, options: Options) Allocator.Error!bool {
    var all_blank = options.ignore_blank_lines;
    var all_match = options.ignore_line != null;
    for ([_]LineDiff.Lines{ d.a, d.b }, [_]usize{ c.a, c.b }, [_]usize{ c.a_len, c.b_len }) |lines, start, len| {
        for (start..start + len) |k| {
            if (!all_blank and !all_match) return false;
            const line = lines.line(k);
            if (all_blank and !isBlank(line, options.whitespace)) all_blank = false;
            if (all_match) {
                const il = options.ignore_line.?;
                if (!try il.matches(il.context, stripNewline(line))) all_match = false;
            }
        }
    }
    return all_blank or all_match;
}

/// Gathers `cs` into hunks. Changes that may be left out are shown only
/// where they fall within the context of one that may not.
pub fn build(gpa: Allocator, d: *const LineDiff, cs: []const Change, options: Options) Allocator.Error![]Hunk {
    if (options.function_context) return buildWithFunctions(gpa, d, cs, options);
    const skip = try gpa.alloc(bool, cs.len);
    defer gpa.free(skip);
    for (cs, skip) |c, *s| s.* = try ignorable(d, c, options);

    var out: std.ArrayList(Hunk) = .empty;
    errdefer out.deinit(gpa);
    const ctx = options.context;
    const join = 2 * ctx + options.inter_hunk_context;
    var k: usize = 0;
    while (k < cs.len) {
        if (skip[k]) {
            k += 1;
            continue;
        }
        // A change that may not be left out takes with it those that may
        // which are near enough before and after it, and the hunk takes
        // the next such change when their reaches are near enough.
        var first = k;
        while (first > 0 and skip[first - 1] and gap(cs[first - 1], cs[first]) < ctx) first -= 1;
        var last = reach(cs, skip, k, ctx);
        while (true) {
            var r = last + 1;
            while (r < cs.len and skip[r]) r += 1;
            if (r >= cs.len) break;
            var r_first = r;
            while (r_first > last + 1 and skip[r_first - 1] and gap(cs[r_first - 1], cs[r_first]) < ctx) r_first -= 1;
            // Changes left out between them count as lines like any
            // other: each of their lines, old and new, as git was seen to
            // join them.
            if (distance(cs, last, r_first) > join) break;
            last = reach(cs, skip, r, ctx);
        }
        const fc = cs[first];
        const lc = cs[last];
        const before = @min(ctx, fc.a);
        const a_end = @min(d.a_changed.len, lc.a + lc.a_len + ctx);
        const b_end = @min(d.b_changed.len, lc.b + lc.b_len + ctx);
        const after = @min(a_end - (lc.a + lc.a_len), b_end - (lc.b + lc.b_len));
        const a_start = fc.a - before;
        const b_start = fc.b - before;
        try out.append(gpa, .{
            .a_start = a_start,
            .a_len = lc.a + lc.a_len + after - a_start,
            .b_start = b_start,
            .b_len = lc.b + lc.b_len + after - b_start,
            .first = first,
            .end = last + 1,
        });
        k = last + 1;
    }
    return out.toOwnedSlice(gpa);
}

/// The last change a change that may not be left out takes with it: the
/// ones that may, after it, each near enough to the one before.
fn reach(cs: []const Change, skip: []const bool, k: usize, ctx: usize) usize {
    var last = k;
    while (last + 1 < cs.len and skip[last + 1] and gap(cs[last], cs[last + 1]) < ctx) last += 1;
    return last;
}

/// Unchanged lines between two changes.
fn gap(x: Change, y: Change) usize {
    return y.a - (x.a + x.a_len);
}

/// Lines between changes `x` and `y`: the unchanged ones, and every line,
/// old and new, of the changes between them.
fn distance(cs: []const Change, x: usize, y: usize) usize {
    var lines = gap(cs[x], cs[y]);
    for (cs[x + 1 .. y]) |c| lines += c.b_len;
    return lines;
}

/// The longest a function name after `@@` may be, in bytes.
pub const function_name_max = 80;

/// The function name git's default rule finds in `line`: the line itself,
/// if it begins with a letter, `_` or `$`, cut and trimmed as
/// `trimFunctionName` says. Null if the line is not one.
pub fn defaultFunctionName(line: []const u8) ?[]const u8 {
    if (line.len == 0) return null;
    const c = line[0];
    if (!(std.ascii.isAlphabetic(c) or c == '_' or c == '$')) return null;
    return trimFunctionName(line);
}

/// A function line cut and trimmed as git cuts and trims it after `@@`:
/// its first 80 bytes, whatever they split, less trailing spaces, tabs,
/// carriage returns and newlines. Empty if nothing is left, when nothing
/// is written after `@@`; otherwise `shownFunctionName` says how much of
/// it is written.
pub fn trimFunctionName(line: []const u8) []const u8 {
    var text = line[0..@min(line.len, function_name_max)];
    var end = text.len;
    while (end > 0 and switch (text[end - 1]) {
        ' ', '\t', '\r', '\n' => true,
        else => false,
    }) end -= 1;
    text = text[0..end];
    return text;
}

/// How much of a trimmed function name git writes after `@@ `: up to its
/// first byte that does not begin a whole, valid UTF-8 sequence, so that a
/// name cut inside a sequence loses the rest of it, and one with a stray
/// byte stops there (or at U+FFFE or U+FFFF), trailing blank space before
/// it kept, as git was seen to do.
pub fn shownFunctionName(name: []const u8) []const u8 {
    var i: usize = 0;
    while (i < name.len) {
        const n = std.unicode.utf8ByteSequenceLength(name[i]) catch break;
        if (i + n > name.len) break;
        const c = std.unicode.utf8Decode(name[i..][0..n]) catch break;
        // U+FFFE and U+FFFF stop it too, though no other noncharacter.
        if (c == 0xfffe or c == 0xffff) break;
        i += n;
    }
    return name[0..i];
}

/// A rule for function lines: git's default, or a diff driver's
/// `xfuncname` or `funcname`.
pub const FunctionFinder = struct {
    context: ?*const anyopaque = null,
    /// The function name `line` (with its newline, if it has one) gives,
    /// or null if it is not a function line. The name may be written
    /// into `buffer`, and may be empty: a function line whose name is
    /// empty ends the search, and nothing is written after `@@`.
    find: *const fn (context: ?*const anyopaque, line: []const u8, buffer: *[function_name_max]u8) Allocator.Error!?[]const u8,
    /// Readies the rule before a patch first uses it, and may fail: a
    /// driver's pattern is compiled at that moment, which is when git was
    /// seen to say what is wrong with it. Null when there is nothing to
    /// ready.
    prepare: ?*const fn (context: ?*const anyopaque) PrepareError!void = null,

    /// What readying a rule can fail with: `error.FunctionLinesUnusable`
    /// when the rule cannot be used, its owner having said why.
    pub const PrepareError = Allocator.Error || error{FunctionLinesUnusable};

    /// git's default rule.
    pub const default: FunctionFinder = .{ .find = findDefault };

    fn findDefault(_: ?*const anyopaque, line: []const u8, _: *[function_name_max]u8) Allocator.Error!?[]const u8 {
        return defaultFunctionName(line);
    }

    /// Whether `line` is a function line.
    pub fn isFunction(f: FunctionFinder, line: []const u8) Allocator.Error!bool {
        var buffer: [function_name_max]u8 = undefined;
        return try f.find(f.context, line, &buffer) != null;
    }
};

/// Finds the function name for a hunk beginning at line `start` of the
/// old text, searching back from the line before it with `finder`. The
/// name may be in `buffer`.
pub fn functionName(lines: LineDiff.Lines, start: usize, finder: FunctionFinder, buffer: *[function_name_max]u8) Allocator.Error!?[]const u8 {
    var i = start;
    while (i > 0) {
        i -= 1;
        if (try finder.find(finder.context, lines.line(i), buffer)) |name| return name;
    }
    return null;
}

/// Whether `-W` takes `line` for blank: nothing but spaces, tabs and
/// carriage returns before its newline, as git was seen to; a form feed
/// or vertical tab is not blank.
fn functionBlank(line: []const u8) bool {
    for (line) |c| switch (c) {
        ' ', '\t', '\r', '\n' => {},
        else => return false,
    };
    return true;
}

/// The function lines of the old text, and the reaches of the functions
/// they begin, as `-W` measures them.
const Functions = struct {
    d: *const LineDiff,
    is_function: []const bool,
    finder: FunctionFinder,

    fn blank(f: *const Functions, i: usize) bool {
        return functionBlank(f.d.a.line(i));
    }

    /// Where the function a change at old line `c.a` is in begins: its
    /// function line, the nearest at or before the change, and the lines
    /// just before that, back to a blank line or another function line.
    /// With no function line before it, the start of the text. An
    /// insertion at the end of the old text that holds a function line
    /// of its own reaches back no further than itself.
    fn start(f: *const Functions, c: Change) Allocator.Error!usize {
        const n = f.is_function.len;
        if (c.a == n and c.a_len == 0) {
            for (c.b..c.b + c.b_len) |k| if (try f.finder.isFunction(f.d.b.line(k))) return c.a;
        }
        if (n == 0) return 0;
        var i = @min(c.a, n - 1) + 1;
        while (i > 0) {
            i -= 1;
            if (!f.is_function[i]) continue;
            var s = i;
            while (s > 0 and !f.blank(s - 1) and !f.is_function[s - 1]) s -= 1;
            return s;
        }
        return 0;
    }

    /// Where the function a change ending at old line `change_end` is in
    /// ends: before the next function line at or after it, less the blank
    /// lines just before that but never before the change; or, with no
    /// function line after it, at the end of the text, blank lines and
    /// all.
    fn end(f: *const Functions, change_end: usize) usize {
        const n = f.is_function.len;
        for (change_end..n) |k| if (f.is_function[k]) {
            var e = k;
            while (e > change_end and f.blank(e - 1)) e -= 1;
            return e;
        };
        return n;
    }

    /// Whether no function line lies after old line `after` and at or
    /// before `at`.
    fn noneBetween(f: *const Functions, after: usize, at: usize) bool {
        const n = f.is_function.len;
        if (n == 0) return true;
        var k = @min(at, n - 1);
        while (k > after) : (k -= 1) if (f.is_function[k]) return false;
        return true;
    }
};

/// Gathers `cs` into hunks for `-W`. As git was seen to: a hunk takes the
/// changes its context joins, as without `-W`; it then reaches back to
/// where the first one's function begins and on to where the last one's
/// ends, and takes every later change that its reach comes to (the
/// change's context touching it), or that no function line lies between
/// it and the reach. An insertion at the end of the old text is taken
/// for that as if it were one line earlier. Hunks may then overlap.
fn buildWithFunctions(gpa: Allocator, d: *const LineDiff, cs: []const Change, options: Options) Allocator.Error![]Hunk {
    const n = d.a_changed.len;
    const is_function = try gpa.alloc(bool, n);
    defer gpa.free(is_function);
    for (is_function, 0..) |*b, i| b.* = try options.function_lines.isFunction(d.a.line(i));
    const f: Functions = .{ .d = d, .is_function = is_function, .finder = options.function_lines };

    var out: std.ArrayList(Hunk) = .empty;
    errdefer out.deinit(gpa);
    const ctx = options.context;
    const join = 2 * ctx + options.inter_hunk_context;
    var k: usize = 0;
    while (k < cs.len) {
        const first = k;
        var last = k;
        while (last + 1 < cs.len and gap(cs[last], cs[last + 1]) <= join) last += 1;
        const fc = cs[first];
        var s = @min(fc.a -| ctx, try f.start(fc));
        var e = @max(@min(n, cs[last].a + cs[last].a_len + ctx), f.end(cs[last].a + cs[last].a_len));
        while (last + 1 < cs.len) {
            const c = cs[last + 1];
            const at = if (c.a == n and c.a > 0) c.a - 1 else c.a;
            if (!(at -| ctx <= e or f.noneBetween(e, at))) break;
            last += 1;
            e = @max(e, @min(n, c.a + c.a_len + ctx), f.end(c.a + c.a_len));
        }
        // A start inside a change, which no case seen has made, is moved
        // back to the start of the change.
        var b_offset: isize = 0;
        for (cs) |c| {
            if (c.a >= s) break;
            if (c.a + c.a_len > s) {
                s = c.a;
                break;
            }
            b_offset += @as(isize, @intCast(c.b_len)) - @as(isize, @intCast(c.a_len));
        }
        var b_len: isize = @intCast(e - s);
        for (cs[first .. last + 1]) |c| b_len += @as(isize, @intCast(c.b_len)) - @as(isize, @intCast(c.a_len));
        try out.append(gpa, .{
            .a_start = s,
            .a_len = e - s,
            .b_start = @intCast(@as(isize, @intCast(s)) + b_offset),
            .b_len = @intCast(b_len),
            .first = first,
            .end = last + 1,
        });
        k = last + 1;
    }
    return out.toOwnedSlice(gpa);
}