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.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie <jeff@ocjtech.us>// SPDX-License-Identifier: MIT
//! Two texts compared line by line, as `git diff` compares them: which//! lines of each are changed, and which are matched with a line of the//! other. No I/O; the texts are bytes the caller already has.//!//! The edit script is the one git chooses, not merely a shortest one. It//! was found by comparing a model with git over many thousands of generated//! texts (ADR 0003, ADR 0004), and it goes like this://!//! 1. The common prefix and suffix of the two texts are matched.//! 2. In what is left, a line that occurs nowhere in the other text is//! changed, and taken out of the comparison. A line that occurs in the//! other text at least `frequentLimit` times is *provisional*. Looking//! from a provisional line at most 100 lines each way, and no further//! than a line that stays, it is taken out as well when there are//! taken-out lines on both sides and at least three times as many of//! them as provisional lines (itself included), plus four.//! `--minimal` takes out only the lines with no match.//! 3. What remains is compared with the linear-space refinement of Myers'//! algorithm ("An O(ND) Difference Algorithm and Its Variations", 1986,//! section 4b), exactly as the paper's procedure reads: common prefix//! and suffix matched in each box, the forward search then the//! backward one for each D, diagonals visited from the highest, the//! middle snake the forward path's last snake when the difference in//! lengths is odd and the backward path's when it is even. When the//! search for a middle snake reaches `costLimit` steps without one, it//! gives up and splits the box at the furthest point either search has//! reached. `--minimal` never gives up. A search that would go on past//! 256 steps, which only a comparison of more than 65,535 lines can//! need, is refused (`plain_steps`).//! 4. Each run of changed lines is slid up and down over equal lines,//! merging with the runs it meets, and left as low as it goes unless a//! position higher up lines up with a change in the other text.//!//! With the indent heuristic, git's default, a run that lines up with//! nothing is placed instead by the indentation and blank lines around//! it (`indent.zig`).//!//! For a patch without context git first sets aside the common tail of//! the two texts (`keptLength`), which can change where a run goes.
const std = @import("std");const Allocator = std.mem.Allocator;const indent = @import("indent.zig");
const LineDiff = @This();
/// The lines of the old text.a: Lines,/// The lines of the new text.b: Lines,/// For each line of `a`, whether it is changed (deleted).a_changed: []bool,/// For each line of `b`, whether it is changed (added).b_changed: []bool,
/// How the lines of a text were split: each line with its terminating/// newline, the last one perhaps without.pub const Lines = struct { text: []const u8, /// Start of each line in `text`, and one more entry for the end. starts: []u32,
/// The number of lines. pub fn len(l: Lines) usize { return l.starts.len - 1; }
/// Line `i`, with its newline if it has one. pub fn line(l: Lines, i: usize) []const u8 { return l.text[l.starts[i]..l.starts[i + 1]]; }
/// Whether the text ends without a newline (and is not empty). pub fn missingNewline(l: Lines) bool { return l.text.len != 0 and l.text[l.text.len - 1] != '\n'; }};
/// `--diff-algorithm`.pub const Algorithm = enum { myers, minimal, patience, histogram,
/// The algorithm a `--diff-algorithm` or `diff.algorithm` value names, /// as git spells them; `default` is `myers`. pub fn fromName(name: []const u8) ?Algorithm { if (std.ascii.eqlIgnoreCase(name, "default")) return .myers; inline for (@typeInfo(Algorithm).@"enum".field_names) |f| { if (std.ascii.eqlIgnoreCase(name, f)) return @field(Algorithm, f); } return null; }};
/// What makes two lines the same.pub const Whitespace = struct { /// `-w`, `--ignore-all-space`. ignore_all: bool = false, /// `-b`, `--ignore-space-change`. ignore_change: bool = false, /// `--ignore-space-at-eol`. ignore_at_eol: bool = false, /// `--ignore-cr-at-eol`. ignore_cr_at_eol: bool = false,
/// Whether any of them is set. pub fn any(w: Whitespace) bool { return w.ignore_all or w.ignore_change or w.ignore_at_eol or w.ignore_cr_at_eol; }};
/// How to compare.pub const Options = struct { algorithm: Algorithm = .myers, whitespace: Whitespace = .{}, /// `--indent-heuristic`, git's default. indent_heuristic: bool = true, /// Whether the common tail of the texts is set aside before comparing, /// as git does for a patch without context (`-U0`); see `keptLength`. trim_tail: bool = false,};
/// Why a comparison cannot be made as git makes it.pub const Error = Allocator.Error || error{ /// `--patience` and `--histogram`, whose choices were not matched. AlgorithmUnsupported, /// A text of more lines than fit in 32 bits. TooManyLines, /// A comparison whose search for a middle snake went on past /// `plain_steps` steps, where git's choice is not fully known. LongSearchUnsupported,};
/// Splits `text` into lines.pub fn splitLines(gpa: Allocator, text: []const u8) error{ OutOfMemory, TooManyLines }!Lines { if (text.len > std.math.maxInt(u32)) return error.TooManyLines; var count: usize = 0; for (text) |c| count += @intFromBool(c == '\n'); if (text.len != 0 and text[text.len - 1] != '\n') count += 1; const starts = try gpa.alloc(u32, count + 1); var n: usize = 0; starts[0] = 0; for (text, 0..) |c, i| if (c == '\n') { n += 1; starts[n] = @intCast(i + 1); }; starts[count] = @intCast(text.len); return .{ .text = text, .starts = starts };}
fn isSpace(c: u8) bool { return c == ' ' or c == '\t' or c == '\r' or c == '\n';}
/// The bytes that decide whether two lines are the same, under `ws`,/// written to `out`.pub fn comparisonKey(line: []const u8, ws: Whitespace, out: *std.ArrayList(u8), gpa: Allocator) Allocator.Error!void { out.clearRetainingCapacity(); if (!ws.any()) return out.appendSlice(gpa, line); // With any of them set, the newline itself is not compared, so a last // line without one is the same as that line with it. var body = line; if (body.len != 0 and body[body.len - 1] == '\n') { body = body[0 .. body.len - 1]; if (ws.ignore_cr_at_eol and body.len != 0 and body[body.len - 1] == '\r') body = body[0 .. body.len - 1]; } if (ws.ignore_all) { for (body) |c| if (!isSpace(c)) try out.append(gpa, c); return; } if (ws.ignore_change or ws.ignore_at_eol) { var end = body.len; while (end > 0 and isSpace(body[end - 1])) end -= 1; body = body[0..end]; } if (ws.ignore_change) { var i: usize = 0; while (i < body.len) { if (isSpace(body[i])) { while (i < body.len and isSpace(body[i])) i += 1; try out.append(gpa, ' '); } else { try out.append(gpa, body[i]); i += 1; } } return; } try out.appendSlice(gpa, body);}
/// Frees what `compute` returned.pub fn deinit(d: *LineDiff, gpa: Allocator) void { gpa.free(d.a.starts); gpa.free(d.b.starts); gpa.free(d.a_changed); gpa.free(d.b_changed); d.* = undefined;}
/// Compares `old` with `new`. The texts must outlive the result.pub fn compute(gpa: Allocator, old: []const u8, new: []const u8, options: Options) Error!LineDiff { switch (options.algorithm) { .myers, .minimal => {}, .patience, .histogram => return error.AlgorithmUnsupported, } var a = try splitLines(gpa, old); errdefer gpa.free(a.starts); var b = try splitLines(gpa, new); errdefer gpa.free(b.starts);
// The lines compared: all of them, or with `trim_tail` those before // the common tail set aside. The rest are unchanged. var ka = a; var kb = b; if (options.trim_tail) { const kept = keptLength(old, new); ka.starts = a.starts[0 .. lineCount(a, kept) + 1]; kb.starts = b.starts[0 .. lineCount(b, kept + new.len - old.len) + 1]; }
// Each line becomes the number of its class of equal lines. const ca = try gpa.alloc(u32, ka.len()); defer gpa.free(ca); const cb = try gpa.alloc(u32, kb.len()); defer gpa.free(cb); try classify(gpa, &ka, &kb, ca, cb, options.whitespace);
const a_changed = try gpa.alloc(bool, a.len()); errdefer gpa.free(a_changed); const b_changed = try gpa.alloc(bool, b.len()); errdefer gpa.free(b_changed); @memset(a_changed, false); @memset(b_changed, false); const xa = a_changed[0..ka.len()]; const xb = b_changed[0..kb.len()]; try diffClasses(gpa, ca, cb, xa, xb, options.algorithm == .minimal); try compact(gpa, ca, xa, xb, if (options.indent_heuristic) &ka else null); try compact(gpa, cb, xb, xa, if (options.indent_heuristic) &kb else null); return .{ .a = a, .b = b, .a_changed = a_changed, .b_changed = b_changed };}
/// With `trim_tail`, how many bytes at the start of `old` are compared:/// git sets aside the common tail of the two texts in whole blocks of/// 1024 bytes, then takes back the bytes up to and including the next/// newline. The same number of bytes is set aside from the end of `new`./// (Found by experiment: a run's placement changed with the length of/// the common tail, in steps of 1024 bytes, only under `-U0`.)pub fn keptLength(old: []const u8, new: []const u8) usize { var common: usize = 0; while (common < old.len and common < new.len and old[old.len - 1 - common] == new[new.len - 1 - common]) common += 1; const set_aside = common - common % tail_block; if (set_aside == 0) return old.len; const cut = old.len - set_aside; const nl = std.mem.findScalarPos(u8, old, cut, '\n') orelse return old.len; return nl + 1;}
const tail_block = 1024;
/// The number of lines of `l` that start before byte `end`, which is the/// start of a line or the end of the text.fn lineCount(l: Lines, end: usize) usize { var lo: usize = 0; var hi: usize = l.len(); while (lo < hi) { const mid = (lo + hi) / 2; if (l.starts[mid] < end) lo = mid + 1 else hi = mid; } return lo;}
fn classify(gpa: Allocator, a: *const Lines, b: *const Lines, ca: []u32, cb: []u32, ws: Whitespace) Allocator.Error!void { var arena_state: std.heap.ArenaAllocator = .init(gpa); defer arena_state.deinit(); const arena = arena_state.allocator(); var map: std.StringHashMapUnmanaged(u32) = .empty; var key: std.ArrayList(u8) = .empty; defer key.deinit(gpa); for ([_]*const Lines{ a, b }, [_][]u32{ ca, cb }) |lines, out| { for (out, 0..) |*c, i| { try comparisonKey(lines.line(i), ws, &key, gpa); const gop = try map.getOrPut(arena, key.items); if (!gop.found_existing) { gop.key_ptr.* = try arena.dupe(u8, key.items); gop.value_ptr.* = map.count() - 1; } c.* = gop.value_ptr.*; } }}
/// Twice the largest power of two whose square is at most `n`: the/// occurrences that make a line provisional, and (at least 256) the steps/// a middle snake is searched for, as git was seen to use them.fn twiceRoot(n: usize) usize { if (n == 0) return 2; const lg = std.math.log2_int(usize, n); return @as(usize, 2) << @intCast(lg / 2);}
/// How many times a line must occur in the other text to be provisional,/// for a text of `n` lines.pub fn frequentLimit(n: usize) usize { return twiceRoot(n);}
/// How many steps a middle snake is searched for, in a comparison of/// `total` lines in all, counted after the common prefix and suffix are/// set aside and lines are taken out. Git counts three more than that:/// 65,533 lines search to 512 steps, 65,532 to 256 (found by experiment/// at the 2^16 and 2^18 boundaries).pub fn costLimit(total: usize) usize { return @max(256, twiceRoot(total + 3));}
/// Steps 1 to 3: which lines are changed, before sliding.pub fn diffClasses(gpa: Allocator, ca: []const u32, cb: []const u32, a_changed: []bool, b_changed: []bool, minimal: bool) DiffError!void { @memset(a_changed, true); @memset(b_changed, true); var lo: usize = 0; while (lo < ca.len and lo < cb.len and ca[lo] == cb[lo]) : (lo += 1) { a_changed[lo] = false; b_changed[lo] = false; } var ha = ca.len; var hb = cb.len; while (ha > lo and hb > lo and ca[ha - 1] == cb[hb - 1]) { ha -= 1; hb -= 1; a_changed[ha] = false; b_changed[hb] = false; } if (ha == lo or hb == lo) return;
var classes: u32 = 0; for (ca) |c| classes = @max(classes, c + 1); for (cb) |c| classes = @max(classes, c + 1); const count_a = try gpa.alloc(u32, classes); defer gpa.free(count_a); const count_b = try gpa.alloc(u32, classes); defer gpa.free(count_b); @memset(count_a, 0); @memset(count_b, 0); for (ca) |c| count_a[c] += 1; for (cb) |c| count_b[c] += 1;
const keep_a = try gpa.alloc(bool, ha - lo); defer gpa.free(keep_a); const keep_b = try gpa.alloc(bool, hb - lo); defer gpa.free(keep_b); try discard(gpa, ca[lo..ha], count_b, frequentLimit(ca.len), minimal, keep_a); try discard(gpa, cb[lo..hb], count_a, frequentLimit(cb.len), minimal, keep_b);
var ia: std.ArrayList(u32) = .empty; defer ia.deinit(gpa); var ib: std.ArrayList(u32) = .empty; defer ib.deinit(gpa); for (keep_a, 0..) |k, i| if (k) try ia.append(gpa, @intCast(lo + i)); for (keep_b, 0..) |k, i| if (k) try ib.append(gpa, @intCast(lo + i)); const sa = try gpa.alloc(u32, ia.items.len); defer gpa.free(sa); const sb = try gpa.alloc(u32, ib.items.len); defer gpa.free(sb); for (sa, ia.items) |*s, i| s.* = ca[i]; for (sb, ib.items) |*s, i| s.* = cb[i]; const xa = try gpa.alloc(bool, sa.len); defer gpa.free(xa); const xb = try gpa.alloc(bool, sb.len); defer gpa.free(xb); @memset(xa, false); @memset(xb, false); try myers(gpa, sa, sb, xa, xb, if (minimal) std.math.maxInt(usize) else costLimit(sa.len + sb.len)); for (ia.items, xa) |i, x| a_changed[i] = x; for (ib.items, xb) |i, x| b_changed[i] = x;}
const Kind = enum(u2) { keep, out, provisional };
/// Step 2 for one text's middle: which of its lines stay in the/// comparison.fn discard(gpa: Allocator, lines: []const u32, other_count: []const u32, limit: usize, minimal: bool, keep: []bool) Allocator.Error!void { const kinds = try gpa.alloc(Kind, lines.len); defer gpa.free(kinds); for (lines, kinds, keep) |c, *k, *kp| { const n = other_count[c]; k.* = if (n == 0) .out else if (!minimal and n >= limit) .provisional else .keep; kp.* = k.* != .out; } // Each provisional line looks at most `provisional_window` lines each // way, stopping at a line that stays. for (kinds, 0..) |k, i| { if (k != .provisional) continue; var out_before: usize = 0; var prov_before: usize = 0; var j = i; while (j > 0 and i - (j - 1) <= provisional_window and kinds[j - 1] != .keep) : (j -= 1) { if (kinds[j - 1] == .out) out_before += 1 else prov_before += 1; } var out_after: usize = 0; var prov_after: usize = 0; j = i + 1; while (j < kinds.len and j - i <= provisional_window and kinds[j] != .keep) : (j += 1) { if (kinds[j] == .out) out_after += 1 else prov_after += 1; } if (out_before == 0 or out_after == 0) continue; if (out_before + out_after >= 3 * (prov_before + prov_after + 1) + 4) keep[i] = false; }}
/// How far a provisional line looks each way.const provisional_window = 100;
/// Step 3: Myers' linear-space algorithm over `a` and `b`, marking what/// it does not match.fn myers(gpa: Allocator, a: []const u32, b: []const u32, a_changed: []bool, b_changed: []bool, limit: usize) DiffError!void { const size = a.len + b.len + 3; const vf = try gpa.alloc(isize, size); defer gpa.free(vf); const vb = try gpa.alloc(isize, size); defer gpa.free(vb); var s: Search = .{ .a = a, .b = b, .vf = vf, .vb = vb, .offset = @intCast(b.len + 1), .limit = limit }; s.box(0, a.len, 0, b.len, a_changed, b_changed); if (s.too_long) return error.LongSearchUnsupported;}
/// The most steps a search for a middle snake is known to take as git/// takes them. Past 256 steps, which only a comparison of more than/// 65,535 lines can reach (`costLimit`), git sometimes splits the box/// early at a snake it has found. The rule was partly found by/// experiment: from step 257 on, a snake of at least 21 lines ending/// more than twice as many lines from the search's corner, in each/// text, as the steps taken, the one furthest from the corner in the/// nearer text. But git sometimes splits at a 20-line snake, and/// sometimes at a snake found before step 257, by a rule not yet found,/// so such a comparison is refused rather than approximated.pub const plain_steps = 256;
/// What `diffClasses` can fail with.pub const DiffError = Allocator.Error || error{ /// See `Error.LongSearchUnsupported`. LongSearchUnsupported,};
const Search = struct { a: []const u32, b: []const u32, vf: []isize, vb: []isize, /// Index of diagonal 0 in `vf` and `vb`. offset: isize, limit: usize, /// Set when some box's search went on past `plain_steps` steps. too_long: bool = false,
const Split = struct { x0: usize, y0: usize, x1: usize, y1: usize };
fn box(s: *Search, ax0: usize, ax1: usize, by0: usize, by1: usize, a_changed: []bool, b_changed: []bool) void { var x0 = ax0; var x1 = ax1; var y0 = by0; var y1 = by1; while (x0 < x1 and y0 < y1 and s.a[x0] == s.b[y0]) { x0 += 1; y0 += 1; } while (x0 < x1 and y0 < y1 and s.a[x1 - 1] == s.b[y1 - 1]) { x1 -= 1; y1 -= 1; } if (x0 == x1 or y0 == y1) { @memset(a_changed[x0..x1], true); @memset(b_changed[y0..y1], true); return; } const sp = s.middle(x0, x1, y0, y1); s.box(x0, sp.x0, y0, sp.y0, a_changed, b_changed); s.box(sp.x1, x1, sp.y1, y1, a_changed, b_changed); }
fn fv(s: *Search, k: isize) *isize { return &s.vf[@intCast(k + s.offset)]; }
fn bv(s: *Search, k: isize) *isize { return &s.vb[@intCast(k + s.offset)]; }
/// The middle snake of the box, in absolute coordinates; the box has /// no common prefix or suffix and neither side is empty. fn middle(s: *Search, x0: usize, x1: usize, y0: usize, y1: usize) Split { const n: isize = @intCast(x1 - x0); const m: isize = @intCast(y1 - y0); const a = s.a[x0..x1]; const b = s.b[y0..y1]; const kmin = -m; const kmax = n; const delta = n - m; const odd = @mod(delta, 2) != 0; s.fv(0).* = 0; s.bv(delta).* = n; var fmin: isize = 0; var fmax: isize = 0; var bmin: isize = delta; var bmax: isize = delta; var d: usize = 0; while (true) { d += 1; if (fmin > kmin) { fmin -= 1; s.fv(fmin - 1).* = -1; } else fmin += 1; if (fmax < kmax) { fmax += 1; s.fv(fmax + 1).* = -1; } else fmax -= 1; var k = fmax; while (k >= fmin) : (k -= 2) { var x = if (s.fv(k - 1).* >= s.fv(k + 1).*) s.fv(k - 1).* + 1 else s.fv(k + 1).*; var y = x - k; const sx = x; const sy = y; while (x < n and y < m and a[@intCast(x)] == b[@intCast(y)]) { x += 1; y += 1; } s.fv(k).* = x; if (odd and bmin <= k and k <= bmax and s.bv(k).* <= x) return .{ .x0 = x0 + @as(usize, @intCast(sx)), .y0 = y0 + @as(usize, @intCast(sy)), .x1 = x0 + @as(usize, @intCast(x)), .y1 = y0 + @as(usize, @intCast(y)) }; } if (bmin > kmin) { bmin -= 1; s.bv(bmin - 1).* = std.math.maxInt(isize); } else bmin += 1; if (bmax < kmax) { bmax += 1; s.bv(bmax + 1).* = std.math.maxInt(isize); } else bmax -= 1; k = bmax; while (k >= bmin) : (k -= 2) { var x = if (s.bv(k - 1).* < s.bv(k + 1).*) s.bv(k - 1).* else s.bv(k + 1).* - 1; var y = x - k; const ex = x; const ey = y; while (x > 0 and y > 0 and a[@intCast(x - 1)] == b[@intCast(y - 1)]) { x -= 1; y -= 1; } s.bv(k).* = x; if (!odd and fmin <= k and k <= fmax and x <= s.fv(k).*) return .{ .x0 = x0 + @as(usize, @intCast(x)), .y0 = y0 + @as(usize, @intCast(y)), .x1 = x0 + @as(usize, @intCast(ex)), .y1 = y0 + @as(usize, @intCast(ey)) }; } if (d >= s.limit) return s.giveUp(x0, y0, n, m, fmin, fmax, bmin, bmax); if (d == plain_steps and s.limit != std.math.maxInt(usize)) { // Past here git may split the box early at a snake, by a // rule only partly matched: give up and refuse. s.too_long = true; return s.giveUp(x0, y0, n, m, fmin, fmax, bmin, bmax); } } }
/// The point furthest along either search: the forward one only when /// it has come strictly further. fn giveUp(s: *Search, x0: usize, y0: usize, n: isize, m: isize, fmin: isize, fmax: isize, bmin: isize, bmax: isize) Split { var best_f: isize = -1; var fx: isize = 0; var fy: isize = 0; var k = fmax; while (k >= fmin) : (k -= 2) { const x = @min(s.fv(k).*, n); const y = x - k; if (y > m) continue; if (x + y > best_f) { best_f = x + y; fx = x; fy = y; } } var best_b: isize = std.math.maxInt(isize); var bx: isize = 0; var by: isize = 0; k = bmax; while (k >= bmin) : (k -= 2) { const x = @max(s.bv(k).*, 0); const y = x - k; if (y < 0) continue; if (x + y < best_b) { best_b = x + y; bx = x; by = y; } } const px, const py = if (best_f > (n + m) - best_b) .{ fx, fy } else .{ bx, by }; const ux = x0 + @as(usize, @intCast(px)); const uy = y0 + @as(usize, @intCast(py)); return .{ .x0 = ux, .y0 = uy, .x1 = ux, .y1 = uy }; }};
/// Step 4 for one text: slides its runs of changes, given the other's./// With `text`, the text's own lines, a run that lines up with nothing/// in the other text is placed by the indent heuristic (`indent.zig`).pub fn compact(gpa: Allocator, lines: []const u32, changed: []bool, other: []const bool, text: ?*const Lines) Allocator.Error!void { const n = lines.len; // The indentation of each line, null for a blank one, when the // heuristic is on. var indents: []?u32 = &.{}; defer gpa.free(indents); if (text) |t| { indents = try gpa.alloc(?u32, n); for (indents, 0..) |*v, i| v.* = indent.indentOf(t.line(i)); } // Where each unchanged line of the other text is, to tell whether a // place in this one lines up with a change there. var kept: std.ArrayList(u32) = .empty; defer kept.deinit(gpa); for (other, 0..) |c, j| if (!c) try kept.append(gpa, @intCast(j)); const linesUp = struct { fn f(k: []const u32, o: []const bool, u: usize) bool { const q = if (u < k.len) k[u] else o.len; return q > 0 and o[q - 1]; } }.f; var s: usize = 0; // Unchanged lines of this text before `s`. var before: usize = 0; while (true) { while (s < n and !changed[s]) { s += 1; before += 1; } if (s >= n) break; var e = s; while (e < n and changed[e]) e += 1; var aligned_end: ?usize = null; // The highest start the run can have, once it stops growing. var top = s; while (true) { const length = e - s; while (s > 0 and lines[s - 1] == lines[e - 1]) { s -= 1; e -= 1; changed[s] = true; changed[e] = false; before -= 1; while (s > 0 and changed[s - 1]) s -= 1; } top = s; aligned_end = if (linesUp(kept.items, other, before)) e else null; while (e < n and lines[s] == lines[e]) { changed[s] = false; changed[e] = true; s += 1; e += 1; before += 1; while (e < n and changed[e]) e += 1; if (linesUp(kept.items, other, before)) aligned_end = e; } if (e - s == length) break; } const target_end: ?usize = if (aligned_end) |t| t else if (text != null and top < s) indent.choose(&indent.git_weights, indents, top, s, e - s) + (e - s) else null; if (target_end) |t| { while (e > t) { s -= 1; e -= 1; changed[s] = true; changed[e] = false; before -= 1; } } s = e; }}
test { _ = @import("tests.zig");}