Something went wrong. Try again.
A Zig library that reads git repositories without running git, with log, show and diff output byte-identical to git's.
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307// 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 }));}