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

//! git's indent heuristic: where a run of changed lines that can slide
//! over equal lines is put, by the indentation and blank lines around
//! each place it could go. No I/O.
//!
//! Everything here was found by asking git 2.56 (ADR 0003, ADR 0004); the
//! experiments are described in CONTRIBUTING.md. In outline:
//!
//! - A *split* is the boundary just above a line of the text holding the
//!   run. A placement of the run has two: above its first line and below
//!   its last.
//! - Each split is measured by looking at most `scan_limit` lines away
//!   from it in each direction: the blank lines just above it and the
//!   indentation of the first non-blank line above those, the blank lines
//!   from it down and the indentation of the first non-blank line below
//!   those, and whether the non-blank line after that one is indented
//!   further. A look that finds only blank lines takes indentation 0 for
//!   the line it did not reach.
//! - A placement scores an *indent*, the sum of the indentation of the
//!   first non-blank line at or below each of its splits (-1 at the end of
//!   the text), and a *penalty*, the sum of a value for each split.
//! - One placement is better than another when `Weights.indent` times the
//!   sign of the difference in indents, plus the difference in penalties,
//!   is below zero. Only the sign of the indent difference counts, so the
//!   comparison is not transitive.
//! - The candidates are the placements at most `L + 1` lines (and at most
//!   100) above the lowest, for a run of `L` lines. They are visited from
//!   the highest down, and each replaces the best so far unless the best
//!   so far is better than it.
//!
//! The weights in `git_weights` are integers: over a million generated
//! slides, exactly one set of integers with an indent weight of 60 (and
//! none with a smaller one) agrees with every choice git made, so they
//! are taken to be git's own, up to scale.

const std = @import("std");

/// The indentation at which measuring a line stops: a line indented this
/// far counts as non-blank and indented this far.
pub const max_indent = 200;

/// How many lines a split's measurement looks at in one direction beyond
/// where it starts: above the split, below the line at the split, and
/// below the first non-blank line under it.
pub const scan_limit = 20;

/// How far above the lowest placement the heuristic looks, at most.
pub const max_slide = 100;

/// The indentation of `line` in columns, tabs to the next multiple of 8,
/// or null when the line is blank (only spaces, tabs and carriage
/// returns, short of `max_indent` columns).
pub fn indentOf(line: []const u8) ?u32 {
    var col: u32 = 0;
    for (line) |c| {
        switch (c) {
            ' ' => col += 1,
            '\t' => col += 8 - col % 8,
            '\r', '\n' => {},
            else => return col,
        }
        if (col >= max_indent) return max_indent;
    }
    return null;
}

/// What is measured at a split.
pub const Measure = struct {
    /// Blank lines just above, at most `scan_limit`.
    blanks_above: u32,
    /// Indentation of the first non-blank line above them, or null at
    /// the start of the text. When `scan_limit` blank lines are all the
    /// look upward finds, this is 0.
    above: ?u32,
    /// Blank lines from the split down, at most `scan_limit + 1`: the
    /// line at the split and the lines the look below it reaches.
    blanks_below: u32,
    /// Indentation of the first non-blank line at or below the split, or
    /// null at the end of the text. When the line at the split and the
    /// `scan_limit` lines below it are all blank, this is 0.
    below: ?u32,
    /// Whether the next non-blank line after that one, within
    /// `scan_limit` lines of it, is indented further.
    deeper_after: bool,
};

/// Measures the split just above line `at` of a text whose line
/// indentations (null for blank) are `indents`.
pub fn measure(indents: []const ?u32, at: usize) Measure {
    var m: Measure = .{ .blanks_above = 0, .above = null, .blanks_below = 0, .below = null, .deeper_after = false };
    var i = at;
    while (i > 0) : (i -= 1) {
        if (indents[i - 1]) |v| {
            m.above = v;
            break;
        }
        m.blanks_above += 1;
        if (m.blanks_above == scan_limit) {
            m.above = 0;
            break;
        }
    }
    if (at >= indents.len) return m;
    if (indents[at]) |v| {
        m.below = v;
    } else {
        // The line at the split is blank: look below it.
        m.blanks_below = 1;
        var j = at + 1;
        while (true) : (j += 1) {
            if (j >= indents.len) return m;
            if (indents[j]) |v| {
                m.below = v;
                break;
            }
            m.blanks_below += 1;
            if (m.blanks_below == scan_limit + 1) {
                m.below = 0;
                return m;
            }
        }
    }
    const w = at + m.blanks_below;
    var k = w + 1;
    while (k < indents.len and k <= w + scan_limit) : (k += 1) {
        if (indents[k]) |v| {
            m.deeper_after = v > m.below.?;
            break;
        }
    }
    return m;
}

/// The weights of the heuristic. Arrays indexed `[blanks]` are indexed by
/// whether the split has blank lines next to it, above or below.
pub const Weights = struct {
    /// What the sign of the indent difference is worth.
    indent: i32,
    /// Each blank line above a split.
    blank_above: i32,
    /// Each blank line below a split.
    blank_below: i32,
    /// A split with no non-blank line below it, indexed by whether blank
    /// lines lie between it and the end of the text.
    end: [2]i32,
    /// A split with no non-blank line above it.
    start: [2]i32,
    /// The line below indented less than the line above.
    shallower: [2]i32,
    /// The same with no blank lines, when the line after the one below is
    /// indented further than it: a single line sticking out to the left.
    shallower_notch: i32,
    /// The line below indented as far as the line above.
    equal: [2]i32,
    /// The line below indented further than the line above.
    deeper: [2]i32,
};

/// The penalty of one split.
pub fn penalty(w: *const Weights, m: Measure) i32 {
    const p = w.blank_above * @as(i32, @intCast(m.blanks_above)) + w.blank_below * @as(i32, @intCast(m.blanks_below));
    const b = m.below orelse return p + w.end[@intFromBool(m.blanks_below > 0)];
    const blanks = @intFromBool(m.blanks_above > 0 or m.blanks_below > 0);
    const a = m.above orelse return p + w.start[blanks];
    if (b < a) {
        if (blanks == 0 and m.deeper_after) return p + w.shallower_notch;
        return p + w.shallower[blanks];
    }
    if (b == a) return p + w.equal[blanks];
    return p + w.deeper[blanks];
}

/// The score of a placement.
pub const Score = struct {
    indent: i32,
    penalty: i32,
};

/// The score of the run placed at lines `start..start + len`.
pub fn score(w: *const Weights, indents: []const ?u32, start: usize, len: usize) Score {
    var s: Score = .{ .indent = 0, .penalty = 0 };
    for ([_]usize{ start, start + len }) |at| {
        const m = measure(indents, at);
        s.indent += if (m.below) |b| @intCast(b) else -1;
        s.penalty += penalty(w, m);
    }
    return s;
}

/// Whether placement `a` is better than placement `b`.
pub fn better(w: *const Weights, a: Score, b: Score) bool {
    const sign: i32 = if (a.indent > b.indent) 1 else if (a.indent < b.indent) -1 else 0;
    return w.indent * sign + a.penalty - b.penalty < 0;
}

/// Where the heuristic puts a run of `len` lines that can start anywhere
/// from `top` to `bottom`: the start it chooses.
pub fn choose(w: *const Weights, indents: []const ?u32, top: usize, bottom: usize, len: usize) usize {
    const first = @max(top, bottom -| @min(len + 1, max_slide));
    var best = first;
    var best_score = score(w, indents, first, len);
    var p = first + 1;
    while (p <= bottom) : (p += 1) {
        const s = score(w, indents, p, len);
        if (!better(w, best_score, s)) {
            best = p;
            best_score = s;
        }
    }
    return best;
}

/// The weights git 2.56 was found to use (see the file comment).
pub const git_weights: Weights = .{
    .indent = 60,
    .blank_above = -30,
    .blank_below = -24,
    .end = .{ -3, 0 },
    .start = .{ 1, 0 },
    .shallower = .{ 23, 17 },
    .shallower_notch = 24,
    .equal = .{ 0, 0 },
    .deeper = .{ -4, 10 },
};

test indentOf {
    const t = std.testing;
    try t.expectEqual(@as(?u32, 0), indentOf("x"));
    try t.expectEqual(@as(?u32, 4), indentOf("    x"));
    try t.expectEqual(@as(?u32, 8), indentOf("\tx"));
    try t.expectEqual(@as(?u32, 8), indentOf("   \tx"));
    try t.expectEqual(@as(?u32, 9), indentOf(" \t x"));
    // A carriage return adds nothing and does not end the indentation.
    try t.expectEqual(@as(?u32, 4), indentOf("  \r  x"));
    // Vertical tab and form feed are not whitespace here.
    try t.expectEqual(@as(?u32, 0), indentOf("\x0b x"));
    try t.expectEqual(@as(?u32, null), indentOf(""));
    try t.expectEqual(@as(?u32, null), indentOf(" \t\r\n"));
    try t.expectEqual(@as(?u32, 0), indentOf("\x0c"));
    // At 200 columns measuring stops, even on a line of only whitespace.
    try t.expectEqual(@as(?u32, null), indentOf(&@as([199]u8, @splat(' '))));
    try t.expectEqual(@as(?u32, 200), indentOf(&@as([200]u8, @splat(' '))));
    try t.expectEqual(@as(?u32, 200), indentOf(&(@as([300]u8, @splat(' ')) ++ [_]u8{'x'})));
    try t.expectEqual(@as(?u32, 200), indentOf(&@as([25]u8, @splat('\t'))));
}

test measure {
    const t = std.testing;
    const n: ?u32 = null;
    // A run of blank lines between two lines, each direction looked at
    // from the middle.
    const text = [_]?u32{ 4, n, n, 8, 2, n, 6 };
    try t.expectEqual(Measure{ .blanks_above = 2, .above = 4, .blanks_below = 0, .below = 8, .deeper_after = false }, measure(&text, 3));
    try t.expectEqual(Measure{ .blanks_above = 1, .above = 4, .blanks_below = 1, .below = 8, .deeper_after = false }, measure(&text, 2));
    try t.expectEqual(Measure{ .blanks_above = 0, .above = 8, .blanks_below = 0, .below = 2, .deeper_after = true }, measure(&text, 4));
    try t.expectEqual(Measure{ .blanks_above = 0, .above = null, .blanks_below = 0, .below = 4, .deeper_after = true }, measure(&text, 0));
    try t.expectEqual(Measure{ .blanks_above = 0, .above = 6, .blanks_below = 0, .below = null, .deeper_after = false }, measure(&text, 7));

    // Twenty blank lines above are all the look upward sees: indentation
    // 0, not the start of the text.
    var up: [25]?u32 = @splat(null);
    up[24] = 4;
    try t.expectEqual(@as(?u32, null), measure(&up, 19).above);
    try t.expectEqual(@as(u32, 19), measure(&up, 19).blanks_above);
    try t.expectEqual(@as(?u32, 0), measure(&up, 20).above);
    try t.expectEqual(@as(u32, 20), measure(&up, 24).blanks_above);

    // Below, the line at the split and twenty more: past that the line
    // below counts as indentation 0, even where the text ends.
    var down: [23]?u32 = @splat(null);
    down[0] = 4;
    down[22] = 8;
    try t.expectEqual(Measure{ .blanks_above = 1, .above = 4, .blanks_below = 20, .below = 8, .deeper_after = false }, measure(&down, 2));
    try t.expectEqual(Measure{ .blanks_above = 0, .above = 4, .blanks_below = 21, .below = 0, .deeper_after = false }, measure(&down, 1));
    try t.expectEqual(Measure{ .blanks_above = 0, .above = 4, .blanks_below = 21, .below = 0, .deeper_after = false }, measure(down[0..22], 1));
    try t.expectEqual(Measure{ .blanks_above = 1, .above = 4, .blanks_below = 20, .below = null, .deeper_after = false }, measure(down[0..22], 2));

    // The line after the one below counts within twenty lines of it.
    var after: [23]?u32 = @splat(null);
    after[0] = 2;
    after[1] = 0;
    after[21] = 8;
    try t.expect(measure(&after, 1).deeper_after);
    after[21] = null;
    after[22] = 8;
    try t.expect(!measure(&after, 1).deeper_after);
}

test penalty {
    const t = std.testing;
    const w = &git_weights;
    const m: Measure = .{ .blanks_above = 0, .above = 8, .blanks_below = 0, .below = 4, .deeper_after = false };
    try t.expectEqual(@as(i32, 23), penalty(w, m));
    var notch = m;
    notch.deeper_after = true;
    try t.expectEqual(@as(i32, 24), penalty(w, notch));
    var blank = m;
    blank.blanks_above = 2;
    try t.expectEqual(@as(i32, 2 * -30 + 17), penalty(w, blank));
    try t.expectEqual(@as(i32, -24 + 0), penalty(w, .{ .blanks_above = 0, .above = 4, .blanks_below = 1, .below = null, .deeper_after = false }));
    try t.expectEqual(@as(i32, -3), penalty(w, .{ .blanks_above = 0, .above = 4, .blanks_below = 0, .below = null, .deeper_after = false }));
    try t.expectEqual(@as(i32, 1), penalty(w, .{ .blanks_above = 0, .above = null, .blanks_below = 0, .below = 4, .deeper_after = false }));
    try t.expectEqual(@as(i32, -4), penalty(w, .{ .blanks_above = 0, .above = 0, .blanks_below = 0, .below = 4, .deeper_after = true }));
}