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.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie <jeff@ocjtech.us>// SPDX-License-Identifier: MIT
//! The commits a walk reads, each read once and kept: its parents, its//! commit date and its generation number, from the commit-graph when the//! graph lists the commit and from the commit object otherwise.//!//! Commits are numbered in the order they are first named, and a walk//! keeps its own state in arrays indexed by those numbers. A commit is//! *named* when something refers to it, and *loaded* when its parents and//! dates have been read; naming costs nothing, and a commit's parents are//! named, not loaded, when it is loaded. Which commits have been loaded//! is part of what a walk can see, as it is of git's: git's rules for//! marking commits excluded reach through every commit it has read, by//! whatever means, so the store remembers it.//!//! A commit's tree is read with its parents, for comparing trees when a//! walk is limited to paths. The commit date is the committer line's; the author date, which only//! `--author-date-order` needs, is read from the commit object when asked//! for, even when the graph has the rest. A commit the graph does not list//! has an infinite generation number.//!//! Grafts and shallow commits (`Grafts`) have the parents those give them//! in place of their own. git does not read the commit-graph alongside//! them, nor alongside replace refs, and a caller should pass an empty//! one then (`Grafts.commitGraphUsable`, `Repository.commitGraphUsable`).//!//! Like git, the store trusts the commit-graph: a commit it lists is not//! looked for in the object database unless `verify_graph` asks, as//! `GIT_COMMIT_GRAPH_PARANOIA` does.
const std = @import("std");const Allocator = std.mem.Allocator;const Io = std.Io;
const object = @import("object.zig");const Id = object.Id;const Format = object.Format;const Diagnostics = @import("Diagnostics.zig");const ObjectDatabase = @import("ObjectDatabase.zig");const CommitGraph = @import("CommitGraph.zig");const Commit = @import("commit.zig").Commit;const Grafts = @import("Grafts.zig");
const Commits = @This();
gpa: Allocator,io: Io,db: ObjectDatabase,graph: *const CommitGraph,format: Format,/// Whether a commit the graph lists is checked for in the object/// database.verify_graph: bool,/// The parents grafts and the shallow boundary give commits.grafts: ?*const Grafts,by_id: std.AutoHashMapUnmanaged([object.max_byte_length]u8, u32) = .empty,entries: std.ArrayList(Entry) = .empty,/// Every loaded commit's parents, one run after another.parent_pool: std.ArrayList(u32) = .empty,/// Where `graph` positions have been named, so that a parent found by/// position is not looked up by object ID again.by_position: std.AutoHashMapUnmanaged(u32, u32) = .empty,/// Problems with the commit-graph met while reading commits that git/// reports and goes on from, in git's words.warnings: std.ArrayList([]u8) = .empty,
/// A commit's number in the store.pub const Index = u32;
/// The generation number of a commit the graph does not list.pub const infinite_generation = std.math.maxInt(u64);
const Entry = struct { id: Id, loaded: bool = false, graph_position: ?u32 = null, parents_at: u32 = 0, parents_len: u32 = 0, time: i64 = 0, generation: u64 = infinite_generation, author_time: ?i64 = null, tree: ?Id = null,};
/// What reading a commit can fail with, besides the object database's/// and the commit-graph's own errors:////// - `CommitNotFound`: the object is not there; git's "Could not read/// <id>". The diagnostic's object ID names it./// - `NotACommit`: the object is not a commit; git's "object <id> is a/// <kind>, not a commit"./// - `MalformedCommit`, `MalformedParent`: as `Commit.parse` says./// - `CommitGraphCommitMissing`: with `verify_graph`, a commit the graph/// lists is not in the object database; git's "commit <id> exists in/// commit-graph but not in the object database".pub const Error = error{ CommitNotFound, NotACommit, MalformedCommit, MalformedParent, CommitGraphCommitMissing, InvalidParentPosition, MissingGenerationOverflow, GenerationOverflowTooSmall,} || ObjectDatabase.ReadError || Allocator.Error;
/// What the store needs.pub const Options = struct { /// Check that every commit read from the graph is in the object /// database, as `GIT_COMMIT_GRAPH_PARANOIA` asks git to. verify_graph: bool = false, /// Parents given in place of commits' own; must outlive the store. grafts: ?*const Grafts = null,};
/// A store reading `db`, and `graph` when it has layers; both must outlive/// it.pub fn init(gpa: Allocator, io: Io, db: ObjectDatabase, graph: *const CommitGraph, format: Format, options: Options) Commits { return .{ .gpa = gpa, .io = io, .db = db, .graph = graph, .format = format, .verify_graph = options.verify_graph, .grafts = options.grafts };}
/// Frees everything.pub fn deinit(s: *Commits) void { s.by_id.deinit(s.gpa); s.entries.deinit(s.gpa); s.parent_pool.deinit(s.gpa); s.by_position.deinit(s.gpa); for (s.warnings.items) |w| s.gpa.free(w); s.warnings.deinit(s.gpa); s.* = undefined;}
/// How many commits have been named.pub fn count(s: *const Commits) u32 { return @intCast(s.entries.items.len);}
/// The number of the commit `id`, naming it if it has not been.pub fn name(s: *Commits, commit: Id) Allocator.Error!Index { const gop = try s.by_id.getOrPut(s.gpa, commit.bytes); if (gop.found_existing) return gop.value_ptr.*; errdefer _ = s.by_id.remove(commit.bytes); const i: Index = @intCast(s.entries.items.len); try s.entries.append(s.gpa, .{ .id = commit }); gop.value_ptr.* = i; return i;}
/// The number of `id` if it has been named.pub fn find(s: *const Commits, commit: Id) ?Index { return s.by_id.get(commit.bytes);}
fn nameAtPosition(s: *Commits, pos: u32) Allocator.Error!Index { if (s.by_position.get(pos)) |i| return i; const i = try s.name(s.graph.idAt(pos)); s.entries.items[i].graph_position = pos; try s.by_position.put(s.gpa, pos, i); return i;}
/// The commit's object ID.pub fn id(s: *const Commits, i: Index) Id { return s.entries.items[i].id;}
/// Whether the commit's parents and dates have been read.pub fn isLoaded(s: *const Commits, i: Index) bool { return s.entries.items[i].loaded;}
/// The parents of a loaded commit, in order.pub fn parents(s: *const Commits, i: Index) []const Index { const e = &s.entries.items[i]; return s.parent_pool.items[e.parents_at..][0..e.parents_len];}
/// The tree of a loaded commit, from the commit-graph or the object; null/// only for a commit object that names none, which git cannot read either.pub fn tree(s: *const Commits, i: Index) ?Id { return s.entries.items[i].tree;}
/// The commit date of a loaded commit.pub fn time(s: *const Commits, i: Index) i64 { return s.entries.items[i].time;}
/// The generation number of a loaded commit: `infinite_generation` when/// the graph does not list it.pub fn generation(s: *const Commits, i: Index) u64 { return s.entries.items[i].generation;}
/// A commit's date and generation number.pub const Dates = struct { time: i64, generation: u64 };
/// The commit date and generation number of a commit, read from the/// commit-graph without reading its parents when the graph lists it and/// it has not been loaded, and by loading it otherwise: what git looks at/// to queue a commit it may never need to read.pub fn peek(s: *Commits, i: Index, diag: ?*Diagnostics) Error!Dates { const e = &s.entries.items[i]; if (e.loaded) return .{ .time = e.time, .generation = e.generation }; if (s.graph.layers.len != 0) { if (e.graph_position orelse s.graph.find(e.id)) |pos| { s.entries.items[i].graph_position = pos; const g = s.graph.readGeneration(pos) catch |err| { if (diag) |d| { d.reset(); d.object_id = s.entries.items[i].id; } return err; }; return .{ .time = g.time, .generation = g.generation }; } } try s.load(i, diag); return .{ .time = s.entries.items[i].time, .generation = s.entries.items[i].generation };}
/// Reads the commit's parents and dates, if they have not been read.pub fn load(s: *Commits, i: Index, diag: ?*Diagnostics) Error!void { if (s.entries.items[i].loaded) return; const the_id = s.entries.items[i].id; if (s.graph.layers.len != 0) { const pos = s.entries.items[i].graph_position orelse s.graph.find(the_id); if (pos) |p| { if (try s.loadFromGraph(i, p, diag)) return; } } var o = s.db.read(s.io, s.gpa, the_id, diag) catch |err| switch (err) { error.ObjectNotFound => { if (diag) |d| { d.reset(); d.object_id = the_id; } return error.CommitNotFound; }, else => |e| return e, }; defer o.deinit(s.gpa); if (o.kind != .commit) { if (diag) |d| { d.reset(); d.object_id = the_id; d.setDetail("{s}", .{o.kind.name()}); } return error.NotACommit; } const c = Commit.parse(s.format, o.data) catch |err| { if (diag) |d| { d.reset(); d.object_id = the_id; } return err; }; const at: u32 = @intCast(s.parent_pool.items.len); if (s.graftOf(the_id)) |g| { for (g.parents) |p| try s.parent_pool.append(s.gpa, try s.name(p)); } else { var it = c.parents(); while (it.next()) |p| { const pi = try s.name(p); try s.parent_pool.append(s.gpa, pi); } } const e = &s.entries.items[i]; e.parents_at = at; e.parents_len = @intCast(s.parent_pool.items.len - at); e.time = commitTime(c); e.author_time = authorTimeOf(c); e.tree = Commit.treeOf(s.format, o.data); e.loaded = true;}
/// Reads a commit from the graph; false when git would read the object/// instead.fn loadFromGraph(s: *Commits, i: Index, pos: u32, diag: ?*Diagnostics) Error!bool { if (s.verify_graph) { const there = s.db.contains(s.io, s.entries.items[i].id, diag) catch false; if (!there) { if (diag) |d| { d.reset(); d.object_id = s.entries.items[i].id; } return error.CommitGraphCommitMissing; } } var positions: std.ArrayList(u32) = .empty; defer positions.deinit(s.gpa); const c = s.graph.read(s.gpa, pos, &positions, diag) catch |err| switch (err) { error.ExtraEdgesOutOfBounds => { const text = try s.gpa.dupe(u8, "error: commit-graph extra-edges pointer out of bounds\n"); errdefer s.gpa.free(text); try s.warnings.append(s.gpa, text); return false; }, else => |e| return e, }; const at: u32 = @intCast(s.parent_pool.items.len); if (s.graftOf(s.entries.items[i].id)) |g| { for (g.parents) |p| try s.parent_pool.append(s.gpa, try s.name(p)); } else for (positions.items) |p| { const pi = try s.nameAtPosition(p); try s.parent_pool.append(s.gpa, pi); } const e = &s.entries.items[i]; e.graph_position = pos; e.parents_at = at; e.parents_len = @intCast(s.parent_pool.items.len - at); e.time = c.time; e.generation = c.generation; e.tree = c.tree; e.loaded = true; return true;}
fn graftOf(s: *const Commits, commit: Id) ?Grafts.Entry { const g = s.grafts orelse return null; return g.lookup(commit);}
/// Whether a loaded commit is on the shallow boundary.pub fn isShallow(s: *const Commits, i: Index) bool { const e = s.graftOf(s.entries.items[i].id) orelse return false; return e.shallow;}
/// The author date of a commit, read from its object if need be.pub fn authorTime(s: *Commits, i: Index, diag: ?*Diagnostics) Error!i64 { if (s.entries.items[i].author_time) |t| return t; var o = s.db.read(s.io, s.gpa, s.entries.items[i].id, diag) catch |err| switch (err) { error.ObjectNotFound => return error.CommitNotFound, else => |e| return e, }; defer o.deinit(s.gpa); const c = Commit.parse(s.format, o.data) catch |err| return err; const t = authorTimeOf(c); s.entries.items[i].author_time = t; return t;}
/// The commit date git orders a walk by, which it reads more narrowly/// than it reads the committer line it shows, as git was seen to: the/// line straight after the parents must be an `author` line and the next/// a `committer` line, and the date is the number after that line's last/// `>`, read as `strtoul` reads one — blank space, a sign, digits, a/// negative number wrapping round — or 0 when any of that is missing./// Dates past the largest signed 64-bit value are taken as that value.fn commitTime(c: Commit) i64 { const after_parents = @intFromPtr(c.parent_lines.ptr) + c.parent_lines.len - @intFromPtr(c.contents.ptr); var rest = c.contents[after_parents..]; if (!std.mem.startsWith(u8, rest, "author ")) return 0; rest = rest[(std.mem.findScalar(u8, rest, '\n') orelse return 0) + 1 ..]; if (!std.mem.startsWith(u8, rest, "committer ")) return 0; const line = rest[0 .. std.mem.findScalar(u8, rest, '\n') orelse rest.len]; const gt = std.mem.findScalarLast(u8, line, '>') orelse return 0; var i = gt + 1; while (i < line.len and (line[i] == ' ' or (line[i] >= '\t' and line[i] <= '\r'))) i += 1; var negative = false; if (i < line.len and (line[i] == '+' or line[i] == '-')) { negative = line[i] == '-'; i += 1; } var v: u64 = 0; var overflow = false; while (i < line.len and std.ascii.isDigit(line[i])) : (i += 1) { const m = std.math.mul(u64, v, 10) catch { overflow = true; break; }; v = std.math.add(u64, m, line[i] - '0') catch { overflow = true; break; }; } if (overflow) return std.math.maxInt(i64); if (negative and v != 0) v = 0 -% v; return if (v > std.math.maxInt(i64)) std.math.maxInt(i64) else @intCast(v);}
fn authorTimeOf(c: Commit) i64 { const ident = c.author() orelse return 0; const d = ident.date() orelse return 0; return d.seconds;}
// -- tests -----------------------------------------------------------------------
const testing = std.testing;const fixture = @import("testing/fixture.zig");const DiskDatabase = @import("DiskDatabase.zig");
test "commits read from objects and from the commit-graph agree" { const gpa = testing.allocator; var repo = try fixture.Repo.init(gpa, testing.io); defer repo.deinit(); try repo.commitFile("a", "1\n", "one"); try repo.git(&.{ "checkout", "-q", "-b", "side" }); try repo.commitFile("b", "2\n", "two"); try repo.git(&.{ "checkout", "-q", "main" }); try repo.commitFile("c", "3\n", "three"); try repo.git(&.{ "merge", "-q", "--no-edit", "side" });
var objects = try repo.tmp.dir.openDir(repo.io, ".git/objects", .{}); defer objects.close(repo.io); 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); const out = try repo.output(&.{ "log", "--format=%H %ct %at %T %P", "main" }); defer gpa.free(out);
for ([_]bool{ false, true }) |with_graph| { if (with_graph) try repo.git(&.{ "commit-graph", "write", "--reachable" }); var graph = try CommitGraph.open(gpa, repo.io, repo.object_format, &.{.{ .dir = objects, .path = ".git/objects" }}, .{}); defer graph.close(repo.io); try testing.expectEqual(with_graph, graph.layers.len != 0); var s = init(gpa, repo.io, db.database(), &graph, repo.object_format, .{}); defer s.deinit(); var lines = std.mem.tokenizeScalar(u8, out, '\n'); while (lines.next()) |line| { var f = std.mem.tokenizeScalar(u8, line, ' '); const i = try s.name(try .parseHex(repo.object_format, f.next().?)); try s.load(i, null); try testing.expectEqual(try std.fmt.parseInt(i64, f.next().?, 10), s.time(i)); try testing.expectEqual(try std.fmt.parseInt(i64, f.next().?, 10), try s.authorTime(i, null)); try testing.expect(s.tree(i).?.eql(try .parseHex(repo.object_format, f.next().?))); for (s.parents(i)) |p| try testing.expect(s.id(p).eql(try .parseHex(repo.object_format, f.next().?))); try testing.expectEqual(null, f.next()); try testing.expectEqual(with_graph, s.generation(i) != infinite_generation); } }}