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.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie <jeff@ocjtech.us>// SPDX-License-Identifier: MIT
//! Merge bases: the best common ancestors of commits, as `git merge-base`//! finds them, and the questions answered the same way — whether one//! commit is an ancestor of another, which of several commits no other//! reaches, the bases of an octopus merge, and where a branch forked from//! a ref's earlier values.//!//! The common ancestors are found by painting: the first commit, and the//! others, go into a queue by commit date (newest first, first in first//! out among equals; with a commit-graph, by generation number first, as//! git does, which changes which commits are read but not the answer), each marked with the side it came from; a commit//! painted from both sides is a candidate, and what it reaches is painted//! stale; the walk stops when only stale commits are queued. The//! candidates no stale paint reached, less any that another reaches, are//! the merge bases, newest first by commit date and, among equals, in the//! order they were found. The order, in criss-cross histories and with//! equal dates, was checked against `git merge-base --all` in histories//! built to have many bases.//!//! Which commits the painting reads matters beyond its answer: `RevWalk`//! excludes through every commit that has been read, and a commit-graph//! that is corrupt past a point git never reads is no failure. So the//! painting queues a commit only when it paints it with something new.//! Without a commit-graph it reads the commit whole only when it comes//! out of the queue, and stops when only stale commits are queued. With//! one, git reads each commit as it queues it, and stops as soon as no//! commit queued could lead to another candidate: none painted from both//! sides and not stale, not one from each side, and none from one side//! whose generation number is above that of a commit painted from the//! other. That was found from what `rev-list A...B` then excludes, and//! from the commit-graph lookups `GIT_COMMIT_GRAPH_PARANOIA` makes git//! do, seen in the loose-object directories it lists.
const std = @import("std");const Allocator = std.mem.Allocator;
const Commits = @import("Commits.zig");const Index = Commits.Index;const Diagnostics = @import("Diagnostics.zig");
/// What finding merge bases can fail with.pub const Error = Commits.Error;
const first_side: u8 = 1;const second_side: u8 = 2;const stale: u8 = 4;const result: u8 = 8;
const Queued = struct { generation: u64, time: i64, sequence: u64, commit: Index };
fn newer(a: Queued, b: Queued) bool { if (a.generation != b.generation) return a.generation > b.generation; if (a.time != b.time) return a.time > b.time; return a.sequence < b.sequence;}
const Painter = struct { gpa: Allocator, store: *Commits, flags: std.AutoHashMapUnmanaged(Index, u8) = .empty, queue: std.ArrayList(Queued) = .empty, sequence: u64 = 0,
fn deinit(p: *Painter) void { p.flags.deinit(p.gpa); p.queue.deinit(p.gpa); }
fn flag(p: *Painter, c: Index) u8 { return p.flags.get(c) orelse 0; }
fn add(p: *Painter, c: Index, f: u8) Allocator.Error!void { const gop = try p.flags.getOrPut(p.gpa, c); if (!gop.found_existing) gop.value_ptr.* = 0; gop.value_ptr.* |= f; }
/// Queues a commit, knowing only its dates: with a commit-graph, git /// queues a commit by generation number first, read without its /// parents, and reads the rest only if it comes out of the queue. fn push(p: *Painter, c: Index, diag: ?*Diagnostics) Error!void { // With a commit-graph git reads a commit as it queues it, which // tells it the generation number. if (p.store.graph.layers.len != 0) try p.store.load(c, diag); const d = try p.store.peek(c, diag); const generation = if (p.store.graph.layers.len != 0) d.generation else 0; try p.queue.append(p.gpa, .{ .generation = generation, .time = d.time, .sequence = p.sequence, .commit = c }); p.sequence += 1; var i = p.queue.items.len - 1; while (i > 0) { const parent = (i - 1) / 2; if (!newer(p.queue.items[i], p.queue.items[parent])) break; std.mem.swap(Queued, &p.queue.items[i], &p.queue.items[parent]); i = parent; } }
fn pop(p: *Painter) Index { const items = p.queue.items; const top = items[0].commit; items[0] = items[items.len - 1]; p.queue.items.len -= 1; var i: usize = 0; const n = p.queue.items.len; while (true) { const l = 2 * i + 1; if (l >= n) break; var best = l; if (l + 1 < n and newer(p.queue.items[l + 1], p.queue.items[l])) best = l + 1; if (!newer(p.queue.items[best], p.queue.items[i])) break; std.mem.swap(Queued, &p.queue.items[i], &p.queue.items[best]); i = best; } return top; }
fn anyFresh(p: *Painter) bool { for (p.queue.items) |q| if (p.flag(q.commit) & stale == 0) return true; return false; }
/// Whether painting could still find a candidate: a commit queued /// that is painted from both sides and not stale; one queued from each /// side; or one queued from one side that could still reach a commit /// painted from the other, which has a lower generation number. fn mayFindMore(p: *Painter) bool { var highest: [2]?u64 = .{ null, null }; for (p.queue.items) |q| { const f = p.flag(q.commit) & (first_side | second_side | stale); if (f == first_side | second_side) return true; const side: usize = if (f == first_side) 0 else if (f == second_side) 1 else continue; const g = p.store.generation(q.commit); highest[side] = @max(highest[side] orelse 0, g); } if (highest[0] != null and highest[1] != null) return true; const side: usize = if (highest[0] != null) 0 else if (highest[1] != null) 1 else return false; const other: u8 = if (side == 0) second_side else first_side; const top = highest[side].?; var it = p.flags.iterator(); while (it.next()) |e| { if (e.value_ptr.* & (first_side | second_side | stale) != other) continue; if (top == Commits.infinite_generation or p.store.generation(e.key_ptr.*) < top) return true; } return false; }
/// Whether to go on painting: with a commit-graph, git stops once no /// new candidate can be found; without one, once every commit queued /// is stale. fn goOn(p: *Painter) bool { if (p.queue.items.len == 0) return false; if (p.store.graph.layers.len != 0) return p.mayFindMore(); return p.anyFresh(); }
/// Paints from `one` and `twos`, and returns the candidates no stale /// paint reached, in the order found. fn paint(p: *Painter, one: Index, twos: []const Index, out: *std.ArrayList(Index), diag: ?*Diagnostics) Error!void { try p.store.load(one, diag); try p.add(one, first_side); try p.push(one, diag); for (twos) |t| { try p.store.load(t, diag); try p.add(t, second_side); try p.push(t, diag); } var found: std.ArrayList(Index) = .empty; defer found.deinit(p.gpa); while (p.goOn()) { const c = p.pop(); try p.store.load(c, diag); var f = p.flag(c) & (first_side | second_side | stale); if (f == first_side | second_side) { if (p.flag(c) & result == 0) { try p.add(c, result); try found.append(p.gpa, c); } f |= stale; } var i: usize = 0; while (i < p.store.parents(c).len) : (i += 1) { const parent = p.store.parents(c)[i]; if (p.flag(parent) & f == f) continue; try p.add(parent, f); try p.push(parent, diag); } } for (found.items) |c| if (p.flag(c) & stale == 0) try out.append(p.gpa, c); }};
/// The candidates, without those another candidate reaches, in order./// With generation numbers, as a commit-graph gives, only commits at or/// above the lowest candidate's generation are read, as git reads them.fn removeRedundant(gpa: Allocator, store: *Commits, list: []Index, diag: ?*Diagnostics) Error!usize { if (store.graph.layers.len != 0) generations: { var lowest: u64 = Commits.infinite_generation; for (list) |c| { try store.load(c, diag); lowest = @min(lowest, store.generation(c)); } if (lowest == Commits.infinite_generation) break :generations; return removeRedundantByGeneration(gpa, store, list, lowest, diag); } const redundant = try gpa.alloc(bool, list.len); defer gpa.free(redundant); @memset(redundant, false); var others: std.ArrayList(Index) = .empty; defer others.deinit(gpa); var others_at: std.ArrayList(usize) = .empty; defer others_at.deinit(gpa); for (list, 0..) |c, i| { if (redundant[i]) continue; others.clearRetainingCapacity(); others_at.clearRetainingCapacity(); for (list, 0..) |o, j| if (j != i and !redundant[j]) { try others.append(gpa, o); try others_at.append(gpa, j); }; if (others.items.len == 0) continue; var p: Painter = .{ .gpa = gpa, .store = store }; defer p.deinit(); var ignored: std.ArrayList(Index) = .empty; defer ignored.deinit(gpa); try p.paint(c, others.items, &ignored, diag); if (p.flag(c) & second_side != 0) redundant[i] = true; for (others.items, others_at.items) |o, j| if (p.flag(o) & first_side != 0) { redundant[j] = true; }; } var kept: usize = 0; for (list, 0..) |c, i| if (!redundant[i]) { list[kept] = c; kept += 1; }; return kept;}
fn removeRedundantByGeneration(gpa: Allocator, store: *Commits, list: []Index, lowest: u64, diag: ?*Diagnostics) Error!usize { const redundant = try gpa.alloc(bool, list.len); defer gpa.free(redundant); @memset(redundant, false); var reached: std.AutoHashMapUnmanaged(Index, void) = .empty; defer reached.deinit(gpa); var stack: std.ArrayList(Index) = .empty; defer stack.deinit(gpa); for (list, 0..) |c, i| { if (redundant[i]) continue; reached.clearRetainingCapacity(); stack.clearRetainingCapacity(); try stack.append(gpa, c); while (stack.pop()) |x| { var k: usize = 0; while (k < store.parents(x).len) : (k += 1) { const p = store.parents(x)[k]; if ((try reached.getOrPut(gpa, p)).found_existing) continue; if ((try store.peek(p, diag)).generation < lowest) continue; try store.load(p, diag); try stack.append(gpa, p); } } for (list, 0..) |o, j| if (j != i and reached.contains(o)) { redundant[j] = true; }; } var kept: usize = 0; for (list, 0..) |c, i| if (!redundant[i]) { list[kept] = c; kept += 1; }; return kept;}
/// The merge bases of `one` and a merge of `twos`, newest first; with/// `all` false, only the first. The caller frees the result.pub fn bases(gpa: Allocator, store: *Commits, one: Index, twos: []const Index, all: bool, diag: ?*Diagnostics) Error![]Index { for (twos) |t| if (t == one) { try store.load(one, diag); const out = try gpa.alloc(Index, 1); out[0] = one; return out; }; var p: Painter = .{ .gpa = gpa, .store = store }; defer p.deinit(); var found: std.ArrayList(Index) = .empty; errdefer found.deinit(gpa); try p.paint(one, twos, &found, diag); // Newest first, and in the order found among equals. std.mem.sort(Index, found.items, store, struct { fn lt(s: *Commits, a: Index, b: Index) bool { return s.time(a) > s.time(b); } }.lt); if (found.items.len > 1) { const kept = try removeRedundant(gpa, store, found.items, diag); found.shrinkRetainingCapacity(kept); } if (!all and found.items.len > 1) found.shrinkRetainingCapacity(1); return found.toOwnedSlice(gpa);}
/// Whether `ancestor` is reachable from `descendant`, or is it.pub fn isAncestor(gpa: Allocator, store: *Commits, ancestor: Index, descendant: Index, diag: ?*Diagnostics) Error!bool { if (ancestor == descendant) return true; try store.load(ancestor, diag); try store.load(descendant, diag); // A commit cannot reach one with a greater generation number. const ga = store.generation(ancestor); const gd = store.generation(descendant); if (ga != Commits.infinite_generation and gd != Commits.infinite_generation and ga > gd) return false; const found = try bases(gpa, store, ancestor, &.{descendant}, true, diag); defer gpa.free(found); for (found) |b| if (b == ancestor) return true; return false;}
/// The commits of `list` that no other in it reaches, in the order given,/// each once. Returns how many there are, at the front of `list`.pub fn independent(gpa: Allocator, store: *Commits, list: []Index, diag: ?*Diagnostics) Error!usize { var n: usize = 0; for (list) |c| { try store.load(c, diag); if (std.mem.findScalar(Index, list[0..n], c) != null) continue; list[n] = c; n += 1; } return removeRedundant(gpa, store, list[0..n], diag);}
/// The best common ancestors of every commit in `list`, as an octopus/// merge of them would have; with `all` false, only the first. The/// caller frees the result.pub fn octopus(gpa: Allocator, store: *Commits, list: []const Index, all: bool, diag: ?*Diagnostics) Error![]Index { var current: std.ArrayList(Index) = .empty; defer current.deinit(gpa); try store.load(list[0], diag); try current.append(gpa, list[0]); for (list[1..]) |c| { var next: std.ArrayList(Index) = .empty; errdefer next.deinit(gpa); // The next commit with each base so far, all at once. const found = try bases(gpa, store, c, current.items, true, diag); defer gpa.free(found); try next.appendSlice(gpa, found); current.deinit(gpa); current = next; } if (!all and current.items.len > 1) current.shrinkRetainingCapacity(1); return current.toOwnedSlice(gpa);}
/// Where `commit` forked from the history whose earlier tips are/// `tips` — a ref's value and the values its reflog records: the newest/// merge base of `commit` and all of them, if it is one of them.pub fn forkPoint(gpa: Allocator, store: *Commits, commit: Index, tips: []const Index, diag: ?*Diagnostics) Error!?Index { if (tips.len == 0) return null; const found = try bases(gpa, store, commit, tips, true, diag); defer gpa.free(found); if (found.len == 0) return null; for (tips) |t| if (t == found[0]) return found[0]; return null;}
// -- tests -----------------------------------------------------------------------
const testing = std.testing;const fixture = @import("testing/fixture.zig");
test "merge bases of a criss-cross history are git's, in git's order" { const gpa = testing.allocator; var repo = try fixture.Repo.init(gpa, testing.io); defer repo.deinit(); try repo.commitFile("a", "0\n", "root"); try repo.git(&.{ "branch", "other" }); try repo.commitFile("a", "1\n", "one"); try repo.git(&.{ "checkout", "-q", "other" }); try repo.commitFile("b", "2\n", "two"); try repo.git(&.{ "checkout", "-q", "main" }); try repo.git(&.{ "branch", "m1" }); try repo.git(&.{ "merge", "-q", "--no-edit", "other" }); try repo.git(&.{ "checkout", "-q", "other" }); try repo.git(&.{ "merge", "-q", "--no-edit", "m1" }); try repo.commitFile("c", "3\n", "three"); try repo.git(&.{ "checkout", "-q", "main" }); try repo.commitFile("d", "4\n", "four");
const DiskDatabase = @import("DiskDatabase.zig"); const CommitGraph = @import("CommitGraph.zig"); const object = @import("object.zig"); var db = try DiskDatabase.open(gpa, repo.io, .{ .objects_path = ".git/objects", .base = repo.tmp.dir, .format = repo.object_format }, null); defer db.close(repo.io); var graph: CommitGraph = .empty; var store = Commits.init(gpa, repo.io, db.database(), &graph, repo.object_format, .{}); defer store.deinit(); const main_id = try revId(&repo, "main"); const other_id = try revId(&repo, "other"); const found = try bases(gpa, &store, try store.name(main_id), &.{try store.name(other_id)}, true, null); defer gpa.free(found); const out = try repo.output(&.{ "merge-base", "--all", "main", "other" }); defer gpa.free(out); var lines = std.mem.tokenizeScalar(u8, out, '\n'); for (found) |b| try testing.expect(store.id(b).eql(try object.Id.parseHex(repo.object_format, lines.next().?))); try testing.expectEqual(null, lines.next()); try testing.expect(found.len == 2);}
fn revId(repo: *fixture.Repo, rev: []const u8) !@import("object.zig").Id { const out = try repo.output(&.{ "rev-parse", rev }); defer repo.gpa.free(out); return .parseHex(repo.object_format, std.mem.trimEnd(u8, out, "\n"));}