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.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie <jeff@ocjtech.us>// SPDX-License-Identifier: MIT
//! Combined diffs (`-c`): one file of a merge compared with each of its//! parents at once, every line marked in one column per parent.//!//! git-diff(1) describes the format; how the columns and hunks are built//! was found by asking git, over hundreds of generated merges, with git's//! own line diff of each parent against the result://!//! - Each line of the result is written once, with `+` in the column of//! each parent it was added against and a space in the others.//! - The lines a parent lost go before the result line they were lost//! before. Where several parents lost lines at one place, their lists//! are merged: each parent's list in turn is matched with the merged//! one by a longest common subsequence (taken from the end, preferring//! to give up the merged list's line on a tie), matched lines written//! once with `-` in every column that lost them, and between two//! matches the merged list's own lines before the new parent's.//! - A changed result line reaches the context around it; lost lines//! before line `g` reach the context lines before `g` and from `g`.//! Reaches that touch join; `--inter-hunk-context` plays no part.//! - The hunk header, between one more `@` than there are parents on//! each side, gives each parent's range and then the result's,//! every count written even when it is 1, and a range with no lines//! starting at the line after the place.//! - The function name is that of the nearest unchanged result line//! before the hunk, and after the lines the hunk before it showed,//! that git's default rule takes for a function line,//! written as `functionName` says. Diff drivers play no part: git was//! seen to use the default rule whatever `diff.<driver>.xfuncname`,//! `funcname` or a built-in driver says, and not to complain of a//! driver's pattern that does not compile. `-W` changes nothing.//! - Under `--cc` (`Options.dense`) some changes are left out, as//! `chooseDense` says; lost lines left out at the start of a hunk still//! count toward it, and those at its end do not; the lines of a change//! left out are written, counted and searched for function names as//! unchanged lines.//! - Without context (`-U0`) only the changes are written and counted,//! lost lines reach the line after them, and a hunk reaching past the//! last line has every count one less (a count of -1 is written as//! 2^64 - 1, as git writes it).
const std = @import("std");const Allocator = std.mem.Allocator;const Io = std.Io;
const LineDiff = @import("LineDiff.zig");const hunks = @import("hunks.zig");
/// The most parents a combined diff is worked out for.pub const max_parents = 32;
/// A line one or more parents lost.const Lost = struct { text: []const u8, /// The parents that lost it, a bit each. mask: u32, /// For each parent in `mask`, the line's place in that parent. at: [max_parents]u32,};
/// What combining can fail with.pub const Error = LineDiff.Error || Io.Writer.Error || error{TooManyParents};
/// How the lines are compared and the hunks written.pub const Options = struct { lines: LineDiff.Options = .{}, /// `-U<n>`. context: usize = 3, /// `--cc`: the changes where the result takes one of only two /// versions the parents have are left out (see `chooseDense`). dense: bool = false,};
/// The most bytes of a result line a combined hunk header's function/// name is taken from.const function_name_max = 40;
/// The function name a combined hunk header gives for result line/// `line`, as git was seen to write it, or null if git's default rule/// does not take the line for a function line: the line up to its first/// NUL, its first 40 bytes, less trailing spaces, tabs, carriage returns/// and newlines, and then less its last byte, whatever that splits./// Empty for a name of one byte, which still ends the search with/// nothing written after the `@@@`.pub fn functionName(line: []const u8) ?[]const u8 { if (hunks.defaultFunctionName(line) == null) return null; var text = line[0 .. std.mem.findScalar(u8, line, 0) orelse line.len]; text = hunks.trimFunctionName(text[0..@min(text.len, function_name_max)]); return text[0..text.len -| 1];}
/// Writes the hunks of the combined diff of `parents` against `result`:/// nothing when no line differs. Returns whether anything was written.pub fn writeHunks(gpa: Allocator, w: *Io.Writer, parents: []const []const u8, result: []const u8, options: Options) Error!bool { const np = parents.len; if (np > max_parents or np == 0) return error.TooManyParents; var arena_state: std.heap.ArenaAllocator = .init(gpa); defer arena_state.deinit(); const arena = arena_state.allocator();
var lo_opts = options.lines; lo_opts.trim_tail = false;
// The result's lines, from the first comparison. var result_lines: ?LineDiff.Lines = null; var n: usize = 0; // Per result line: the parents it was added against; and, per parent, // its place in that parent (when it is there). var added: []u32 = &.{}; var place: [][max_parents]u32 = &.{}; // Per gap (before each result line, and at the end): what was lost. var lost: []std.ArrayList(Lost) = &.{}; // Per gap and parent: how many of the parent's lines come before the // gap's lost lines. var before: [][max_parents]u32 = &.{};
var diffs: std.ArrayList(LineDiff) = .empty; defer { for (diffs.items) |*d| d.deinit(gpa); diffs.deinit(gpa); } for (parents, 0..) |p, pi| { try diffs.append(gpa, try LineDiff.compute(gpa, p, result, lo_opts)); const d = &diffs.items[diffs.items.len - 1]; if (result_lines == null) { result_lines = d.b; n = d.b.len(); added = try arena.alloc(u32, n); @memset(added, 0); place = try arena.alloc([max_parents]u32, n); lost = try arena.alloc(std.ArrayList(Lost), n + 1); for (lost) |*l| l.* = .empty; before = try arena.alloc([max_parents]u32, n + 1); } const bit = @as(u32, 1) << @intCast(pi); var mine: std.ArrayList(std.ArrayList(Lost)) = .empty; try mine.resize(arena, n + 1); for (mine.items) |*l| l.* = .empty; var i: usize = 0; var j: usize = 0; const na = d.a.len(); while (true) { if (i < na and d.a_changed[i]) { var entry: Lost = .{ .text = d.a.line(i), .mask = bit, .at = undefined }; entry.at[pi] = @intCast(i); if (mine.items[j].items.len == 0) before[j][pi] = @intCast(i); try mine.items[j].append(arena, entry); i += 1; continue; } if (mine.items[j].items.len == 0) before[j][pi] = @intCast(i); if (j == n) break; if (d.b_changed[j]) { added[j] |= bit; } else { place[j][pi] = @intCast(i); i += 1; } j += 1; } for (mine.items, 0..) |list, g| { if (list.items.len == 0) continue; if (lost[g].items.len == 0) { try lost[g].appendSlice(arena, list.items); } else { lost[g] = try mergeLost(arena, lost[g].items, list.items, pi); } } } const lines = result_lines.?;
// Under --cc, which changes are shown at all; every one under -c. const shown_gap: []bool = try arena.alloc(bool, n + 1); const shown_line: []bool = try arena.alloc(bool, n); @memset(shown_gap, !options.dense); @memset(shown_line, !options.dense); if (options.dense) try chooseDense(arena, .{ .lines = lines, .np = np, .added = added, .lost = lost, .context = options.context, }, shown_gap, shown_line);
// The reach of each change shown, joined into hunks. const Span = struct { lo: isize, hi: isize }; var spans: std.ArrayList(Span) = .empty; const ctx: isize = @intCast(options.context); for (0..n + 1) |g| { const gi: isize = @intCast(g); // Lost lines reach the context before them and from the line // after; without context, that line itself. if (lost[g].items.len != 0 and shown_gap[g]) try spans.append(arena, .{ .lo = gi - ctx, .hi = gi + @max(ctx - 1, 0) }); if (g < n and added[g] != 0 and shown_line[g]) try spans.append(arena, .{ .lo = gi - ctx, .hi = gi + ctx }); } if (spans.items.len == 0) return false; // Spans come in order of their starts already, but a line's may // reach further than the gap's before it. var groups: std.ArrayList(Span) = .empty; var cur = spans.items[0]; // git takes no `--inter-hunk-context` here: hunks join only where // their context touches. for (spans.items[1..]) |s| { if (s.lo <= cur.hi + 1) { cur.hi = @max(cur.hi, s.hi); } else { try groups.append(arena, cur); cur = s; } } try groups.append(arena, cur);
// Where the hunk before ends: the search for a function name does // not go back into the lines it showed. var previous_end: usize = 0; for (groups.items) |g| { const lo: usize = @intCast(@max(0, g.lo)); const hi_signed = @min(@as(isize, @intCast(n)) - 1, g.hi); // Result lines lo..hi (possibly none), and the lost lines of gaps // lo..hi+1. const hi_end: usize = @intCast(hi_signed + 1); // Without context only the changes are written, and counted; and // a hunk reaching the end of the file, past its last line, has // every count one less, as git was seen to write them (a count // of -1 coming out as 2^64 - 1). const bare = options.context == 0; const past_end: u64 = if (bare and g.hi >= @as(isize, @intCast(n))) 1 else 0; // One more @ than there are parents, each side. try w.splatByteAll('@', np + 1); for (0..np) |pi| { const bit = @as(u32, 1) << @intCast(pi); var count: u64 = 0; for (lo..hi_end + 1) |k| { // Under --cc, lost lines left out at the start of a hunk // still count toward it, and at its end do not. if (k < hi_end and !bare or shown_gap[k]) for (lost[k].items) |l| { if (l.mask & bit != 0) count += 1; }; if (k == hi_end) continue; if (bare) { if (shown_line[k] and added[k] != 0 and added[k] & bit == 0) count += 1; } else if (added[k] & bit == 0 or !shown_line[k]) { // A line added against this parent counts as one of // its lines where --cc shows it as context. count += 1; } } try w.print(" -{d},{d}", .{ @as(usize, before[lo][pi]) + 1, count -% past_end }); } var result_count: u64 = hi_end - lo; if (bare) { result_count = 0; for (lo..hi_end) |k| if (shown_line[k] and added[k] != 0) { result_count += 1; }; } try w.print(" +{d},{d} ", .{ lo + 1, result_count -% past_end }); try w.splatByteAll('@', np + 1); // The nearest unchanged line before the hunk, and after the one // before it, that names a function; --cc takes the lines of the // changes it leaves out for unchanged. var k = lo; while (k > previous_end) { k -= 1; if (added[k] != 0 and shown_line[k]) continue; if (functionName(lines.line(k))) |name| { if (name.len != 0) { try w.writeByte(' '); try w.writeAll(name); } break; } } try w.writeByte('\n'); previous_end = hi_end; for (lo..hi_end + 1) |line_index| { if (line_index <= n and shown_gap[line_index]) for (lost[line_index].items) |l| { for (0..np) |pi| try w.writeByte(if (l.mask & (@as(u32, 1) << @intCast(pi)) != 0) '-' else ' '); try writeLine(w, l.text); }; if (line_index < hi_end) { const marks = if (shown_line[line_index]) added[line_index] else 0; if (bare and marks == 0) continue; for (0..np) |pi| try w.writeByte(if (marks & (@as(u32, 1) << @intCast(pi)) != 0) '+' else ' '); try writeLine(w, lines.line(line_index)); } } } return true;}
/// What `chooseDense` looks at: the combined diff of one file, worked out.const Changes = struct { lines: LineDiff.Lines, np: usize, added: []const u32, lost: []const std.ArrayList(Lost), context: usize,};
/// Chooses the changes `--cc` shows, as git was seen to choose them.////// The changes of a combined diff fall into blocks: runs of lost and/// added lines with no unchanged line between them. Blocks close/// together are taken as one: those with at most `context - 1` unchanged/// lines between them, or at most one where the first ends in lost/// lines and the context is one line. Such a stretch of changes is left/// out when the parents have only two versions of it and the result is/// one of them as it is (git-diff-tree(1) describes it so); the rest are/// shown, each with its context as under `-c`.////// Found by comparing a model with git over thousands of generated/// merges of two to four parents, at contexts of one to five lines.fn chooseDense(arena: Allocator, c: Changes, shown_gap: []bool, shown_line: []bool) Allocator.Error!void { const n = c.added.len; // Elements in order: gap g (when it has lost lines) at 2g, line j at // 2j + 1. A stretch runs from one element to another. const Stretch = struct { first: usize, last: usize }; var stretches: std.ArrayList(Stretch) = .empty; var open: ?Stretch = null; var unchanged_between: usize = 0; var e: usize = 0; while (e <= 2 * n) : (e += 1) { const is_gap = e % 2 == 0; const index = e / 2; if (is_gap and c.lost[index].items.len == 0) continue; const changed = is_gap or c.added[index] != 0; if (!changed) { unchanged_between += 1; continue; } if (open) |*o| { if (unchanged_between == 0) { o.last = e; } else { const ends_lost = o.last % 2 == 0; const most: usize = if (ends_lost) @max(c.context, 2) - 1 else c.context -| 1; if (unchanged_between <= most) { o.last = e; } else { try stretches.append(arena, o.*); open = .{ .first = e, .last = e }; } } } else open = .{ .first = e, .last = e }; unchanged_between = 0; } if (open) |o| try stretches.append(arena, o);
var versions: std.ArrayList(std.ArrayList([]const u8)) = .empty; try versions.resize(arena, c.np + 1); for (stretches.items) |st| { // Each parent's version of the stretch, and the result's last. for (versions.items) |*v| v.* = .empty; var x = st.first; while (x <= st.last) : (x += 1) { const index = x / 2; if (x % 2 == 0) { for (c.lost[index].items) |l| for (0..c.np) |pi| { if (l.mask & (@as(u32, 1) << @intCast(pi)) != 0) try versions.items[pi].append(arena, l.text); }; } else { const text = c.lines.line(index); for (0..c.np) |pi| if (c.added[index] & (@as(u32, 1) << @intCast(pi)) == 0) try versions.items[pi].append(arena, text); try versions.items[c.np].append(arena, text); } } const parents = versions.items[0..c.np]; const result = versions.items[c.np].items; var other: ?usize = null; var two = true; for (parents[1..], 1..) |v, pi| { if (sameVersion(v.items, parents[0].items)) continue; if (other) |o| { if (!sameVersion(v.items, parents[o].items)) two = false; } else other = pi; } const picks = two and other != null and (sameVersion(result, parents[0].items) or sameVersion(result, parents[other.?].items)); if (picks) continue; x = st.first; while (x <= st.last) : (x += 1) { if (x % 2 == 0) shown_gap[x / 2] = true else shown_line[x / 2] = true; } }}
/// Whether two versions of a stretch are the same lines, byte for byte:/// a line missing its newline at the end of a file differs from the same/// line with one, as git was seen to tell them apart here (where merging/// lost lines does not).fn sameVersion(a: []const []const u8, b: []const []const u8) bool { if (a.len != b.len) return false; for (a, b) |x, y| if (!std.mem.eql(u8, x, y)) return false; return true;}
/// Writes a line as git was seen to write it in a combined diff: only as/// far as its first NUL, and always ended by a newline, a line missing/// one at the end of the text getting no `\ No newline at end of file`.fn writeLine(w: *Io.Writer, line: []const u8) Io.Writer.Error!void { const end = std.mem.findScalar(u8, line, 0) orelse if (std.mem.endsWith(u8, line, "\n")) line.len - 1 else line.len; try w.writeAll(line[0..end]); try w.writeByte('\n');}
/// Whether two lost lines are one when merged: the same bytes, NULs/// included, whether or not either ends in a newline.fn sameLost(a: []const u8, b: []const u8) bool { const x = if (std.mem.endsWith(u8, a, "\n")) a[0 .. a.len - 1] else a; const y = if (std.mem.endsWith(u8, b, "\n")) b[0 .. b.len - 1] else b; return std.mem.eql(u8, x, y);}
/// Merges parent `pi`'s lost lines `theirs` into `ours`, as git was seen/// to: a longest common subsequence, traced back from the end, a tie/// giving up `theirs`' line; between matches, `ours`' lines first. Lines/// are compared as `sameLost` says.fn mergeLost(arena: Allocator, ours: []const Lost, theirs: []const Lost, pi: usize) Allocator.Error!std.ArrayList(Lost) { const n = ours.len; const m = theirs.len; const width = m + 1; const dp = try arena.alloc(u32, (n + 1) * width); @memset(dp, 0); for (1..n + 1) |i| for (1..m + 1) |j| { dp[i * width + j] = if (sameLost(ours[i - 1].text, theirs[j - 1].text)) dp[(i - 1) * width + j - 1] + 1 else @max(dp[(i - 1) * width + j], dp[i * width + j - 1]); }; // The matches, from the end. var matches: std.ArrayList([2]usize) = .empty; var i = n; var j = m; while (i > 0 and j > 0) { if (sameLost(ours[i - 1].text, theirs[j - 1].text)) { try matches.append(arena, .{ i - 1, j - 1 }); i -= 1; j -= 1; } else if (dp[(i - 1) * width + j] > dp[i * width + j - 1]) { i -= 1; } else { j -= 1; } } std.mem.reverse([2]usize, matches.items); const bit = @as(u32, 1) << @intCast(pi); var out: std.ArrayList(Lost) = .empty; var a: usize = 0; var b: usize = 0; for (matches.items) |mt| { try out.appendSlice(arena, ours[a..mt[0]]); try out.appendSlice(arena, theirs[b..mt[1]]); var both = ours[mt[0]]; both.mask |= bit; both.at[pi] = theirs[mt[1]].at[pi]; try out.append(arena, both); a = mt[0] + 1; b = mt[1] + 1; } try out.appendSlice(arena, ours[a..]); try out.appendSlice(arena, theirs[b..]); return out;}
test "lost lines merged and columns marked" { const gpa = std.testing.allocator; var out: Io.Writer.Allocating = .init(gpa); defer out.deinit(); const p1 = "a\nb\nc\nX\nY\nZ\nd\ne\nf\n"; const p2 = "a\nb\nc\nZ\nY\nX\nd\ne\nf\n"; const result = "a\nb\nc\nQ\nd\ne\nf\n"; _ = try writeHunks(gpa, &out.writer, &.{ p1, p2 }, result, .{}); try std.testing.expectEqualStrings( \\@@@ -1,9 -1,9 +1,7 @@@ \\ a \\ b \\ c \\- X \\- Y \\--Z \\ -Y \\ -X \\++Q \\ d \\ e \\ f \\ , out.written());}
test "dense: a change taken whole from one side is left out" { const gpa = std.testing.allocator; var out: Io.Writer.Allocating = .init(gpa); defer out.deinit(); const p1 = "1\n2\nA3\n4\n5\n6\n7\n8\n9\n10\n11\n12\n13\n14\nA15\n16\n"; const p2 = "1\n2\nB3\n4\n5\n6\n7\n8\n9\nB10\n11\n12\n13\n14\n15\n16\n"; const result = "1\n2\nR3\n4\n5\n6\n7\n8\n9\nB10\n11\n12\n13\n14\nA15\n16\n"; _ = try writeHunks(gpa, &out.writer, &.{ p1, p2 }, result, .{ .dense = true }); try std.testing.expectEqualStrings( \\@@@ -1,6 -1,6 +1,6 @@@ \\ 1 \\ 2 \\- A3 \\ -B3 \\++R3 \\ 4 \\ 5 \\ 6 \\ , out.written()); // Taken changes a line apart are one stretch, which the result takes // from neither parent. out.clearRetainingCapacity(); _ = try writeHunks(gpa, &out.writer, &.{ "1\nA\n3\n4\n", "1\n2\n3\nB\n" }, "1\nA\n3\nB\n", .{ .dense = true, .context = 2 }); try std.testing.expectEqualStrings( \\@@@ -1,4 -1,4 +1,4 @@@ \\ 1 \\ -2 \\ +A \\ 3 \\- 4 \\+ B \\ , out.written()); // With one line of context, a stretch ending in an added line does // not reach across the line between: both are left out. out.clearRetainingCapacity(); try std.testing.expect(!try writeHunks(gpa, &out.writer, &.{ "1\nA\n3\n4\n", "1\n2\n3\nB\n" }, "1\nA\n3\nB\n", .{ .dense = true, .context = 1 }));}
test "combined function names" { const t = std.testing; try t.expectEqual(null, functionName(" indented\n")); try t.expectEqual(null, functionName("\x00x\n")); try t.expectEqualStrings("fn fo", functionName("fn foo \r\n").?); try t.expectEqualStrings("", functionName("f\n").?); try t.expectEqualStrings("f", functionName("fo\x00x\n").?); // Cut at 40 bytes, then trimmed, then a byte less: a UTF-8 sequence // is cut whatever it is. const a37: [37]u8 = @splat('a'); try t.expectEqualStrings(&a37, functionName(a37 ++ "a b\n").?); try t.expectEqualStrings(a37 ++ " ", functionName(a37 ++ " b\n").?); try t.expectEqualStrings("f\xc3", functionName("f\xc3\xa9\n").?);}
const fuzz_input = @import("../testing/fuzz.zig");
/// Two parents and a result from fuzzed input, split at 0xff bytes: the/// combined hunks are written without failing, and each line is marked/// in one column per parent.fn fuzzCombined(_: void, smith: *std.testing.Smith) anyerror!void { const gpa = std.testing.allocator; var buffer: [4096]u8 = undefined; const input = fuzz_input.bytes(smith, &buffer); var parts = std.mem.splitScalar(u8, input, 0xff); const p1 = parts.next() orelse return; const p2 = parts.next() orelse return; const result = parts.next() orelse return; var out: Io.Writer.Allocating = .init(gpa); defer out.deinit(); for ([_]bool{ false, true }) |dense| { _ = writeHunks(gpa, &out.writer, &.{ p1, p2 }, result, .{ .context = 1, .dense = dense }) catch |err| switch (err) { error.LongSearchUnsupported => return, else => return err, }; } var lines = std.mem.splitScalar(u8, out.written(), '\n'); while (lines.next()) |line| { if (line.len == 0 or std.mem.startsWith(u8, line, "@@@") or line[0] == '\\') continue; try std.testing.expect(line.len >= 2); for (line[0..2]) |c| try std.testing.expect(c == ' ' or c == '+' or c == '-'); }}
test "fuzz: combined diff" { try fuzz_input.fuzz({}, fuzzCombined, .{ .corpus = &.{ @embedFile("../fuzz/combined-merge"), } });}