Something went wrong. Try again.
Reading and writing git repositories in Zig, without running git.
Something went wrong. Try again.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie <jeff@ocjtech.us>// SPDX-License-Identifier: MIT
//! The commit-graph (gitformat-commit-graph(5)): a file, or a chain of//! them, listing commits by object ID with each one's tree, parents,//! commit date and generation number, so that a walk can step from commit//! to commit without inflating a single commit object.//!//! A file begins with `CGPH`, a version (1), the object format's number (1//! for SHA-1, 2 for SHA-256), the number of chunks and the number of base//! files, then a table of contents in the layout of gitformat-chunk(5).//! The chunks are://!//! - `OIDF`, a 256-entry fanout table, and `OIDL`, the sorted object IDs;//! - `CDAT`, for each commit its tree, the positions of its first two//! parents, its topological level and its commit date;//! - `EDGE`, the third and later parents of octopus merges;//! - `GDA2` and `GDO2`, the corrected commit dates, as offsets from the//! commit date, the large ones in a table of their own;//! - `BIDX` and `BDAT`, the changed-path Bloom filters (`bloom.zig`);//! - `BASE`, the checksums of the files below this one in a chain.//!//! A chain is `info/commit-graphs/commit-graph-chain`, naming its files//! bottom first by their checksums, each a `graph-<checksum>.graph`//! beside it; a commit's position counts through the files below its//! own, and parents may be anywhere beneath.//!//! What git accepts and what it refuses were found by corrupting the files//! git wrote, a byte or a chunk at a time, and asking `git rev-list`://!//! - **Which graph**: each objects directory in turn, the repository's//! own first, then its alternates: its `info/commit-graph` if that can//! be read, and otherwise its chain; the first directory with either//! wins. A chain's files are looked for in every objects directory.//! - **A file** is passed over, with git's error, if it is smaller than a//! header, table of contents, fanout table and checksum could be; if its//! signature, version or object format is wrong; if its table of//! contents is malformed (an early or missing terminator, offsets out of//! order or past the checksum, a chunk named twice); or if `OIDF`,//! `OIDL` or `CDAT` is missing or the wrong size, or the fanout goes//! backwards. A size is right when dividing it by the size of one entry//! gives the number expected, so a few bytes over are accepted.//! - **Optional chunks** that are the wrong size are dropped and the rest//! of the file used: `GDA2` with an error, `BIDX` with a warning, and//! `BDAT` too small for its header with another. Filters of a version//! the caller does not read are dropped without a word.//! - **A chain** is read for as many lines as its size holds whole//! (`size / (hex digits + 1)`). A line must begin with an object ID's//! worth of hexadecimal digits, but the whole line, whatever follows,//! names the file. Each file above the first must have a `BASE` chunk//! listing the checksums of every file below it, as they are, and not//! as they are named. The chain is read up to the first file that is//! missing, unreadable or does not match, and that file and every one//! after it are passed over, with git's warning.//! - **The checksum** at the end is not checked, and neither is the base//! count in the header.//! - **What a commit says** is checked only when the commit is read: a//! parent position past the end is fatal to git, as is a large//! corrected commit date with no table to find it in; an `EDGE` list//! that runs off the end is an error, and git reads the commit object//! instead.//!//! Generation numbers are corrected commit dates when the caller asks for//! version 2, as git does by default, and every file has them, and//! topological levels otherwise.//!//! Parsing does no I/O; `open` reads the files.
const std = @import("std");const Allocator = std.mem.Allocator;const Io = std.Io;
const object = @import("object.zig");const Format = object.Format;const Id = object.Id;const Diagnostics = @import("Diagnostics.zig");const bloom = @import("bloom.zig");
const CommitGraph = @This();
gpa: Allocator,format: Format,/// The files, bottom first; empty when there is no commit-graph.layers: []Layer,/// What the layers' bytes live in.maps: []Mapped,/// The paths the layers were read from, as git names them.paths: [][]u8,/// Whether generation numbers are corrected commit dates rather than/// topological levels.corrected_dates: bool,/// What was wrong with the commit-graph but worked around, in git's/// words, in the order git says it.problems: []Problem,
/// No commit-graph at all.pub const empty: CommitGraph = .{ .gpa = undefined, .format = .sha1, .layers = &.{}, .maps = &.{}, .paths = &.{}, .corrected_dates = false, .problems = &.{},};
/// The value `CDAT` holds for a parent that is not there.const no_parent: u32 = 0x70000000;/// The bit in `CDAT`'s second parent that points into `EDGE`, and in an/// `EDGE` entry that ends the list.const high_bit: u32 = 0x80000000;
/// Why a commit-graph file was passed over. Each has git's message, which/// `writeError` writes:////// - `CommitGraphTooSmall`: "commit-graph file is too small"./// - `CommitGraphTooSmallForChunks`: "commit-graph file is too small to/// hold N chunks"; the detail is N./// - `BadCommitGraphSignature`, `UnsupportedCommitGraphVersion`,/// `CommitGraphHashMismatch`: the header's signature, version or object/// format; the detail is the value found, in git's hexadecimal./// - `CommitGraphChunkTableEndsEarly`: "terminating chunk id appears/// earlier than expected"./// - `CommitGraphChunkTableUnterminated`: "final chunk has non-zero id/// …"./// - `BadCommitGraphChunkOffsets`: "improper chunk offset(s) … and …"./// - `DuplicateCommitGraphChunk`: "duplicate chunk ID … found"./// - `BadCommitGraphFanout`, `BadCommitGraphLookup`,/// `BadCommitGraphCommitData`: a required chunk is the wrong size, or/// the fanout goes backwards; git says what, then that the chunk is/// "missing or corrupted"./// - `MissingCommitGraphChunk`: a required chunk is not there; the detail/// is git's name for it.pub const Error = error{ CommitGraphTooSmall, CommitGraphTooSmallForChunks, BadCommitGraphSignature, UnsupportedCommitGraphVersion, CommitGraphHashMismatch, CommitGraphChunkTableEndsEarly, CommitGraphChunkTableUnterminated, BadCommitGraphChunkOffsets, DuplicateCommitGraphChunk, BadCommitGraphFanout, BadCommitGraphLookup, BadCommitGraphCommitData, MissingCommitGraphChunk,};
/// What was wrong but worked around: a file passed over, a chain cut/// short, or an optional chunk dropped.pub const Problem = struct { err: ProblemError, /// What git says, each line with its `error: ` or `warning: ` and its /// line feed. text: []u8,};
/// The problems `Problem` records: a file's `Error`, or////// - `CommitGraphGenerationsWrongSize`: `GDA2` dropped./// - `CommitGraphBloomIndexTooSmall`, `CommitGraphBloomDataTooSmall`: the/// Bloom filters dropped./// - `InvalidCommitGraphChain`: a chain line that is not an object ID./// - `CommitGraphChainMismatch`: a file's `BASE` does not list the files/// below it./// - `CommitGraphMissingBase`, `CommitGraphBaseTooSmall`: a file above/// the first has no `BASE`, or too short a one./// - `IncompleteCommitGraphChain`: "unable to find all commit-graph/// files".pub const ProblemError = Error || error{ CommitGraphGenerationsWrongSize, CommitGraphBloomIndexTooSmall, CommitGraphBloomDataTooSmall, InvalidCommitGraphChain, CommitGraphChainMismatch, CommitGraphMissingBase, CommitGraphBaseTooSmall, IncompleteCommitGraphChain,};
/// How to read a file's optional chunks.pub const ParseOptions = struct { /// `commitGraph.generationVersion`: 2 reads `GDA2`, anything else does /// not. generation_version: i64 = 2, /// `commitGraph.changedPathsVersion`: -1 reads Bloom filters of /// either version, 0 none, and 1 or 2 only that version. changed_paths_version: i64 = -1,};
/// An optional chunk dropped while parsing a file.pub const Note = union(enum) { generations_wrong_size, bloom_index_too_small, /// The size of the `BDAT` chunk. bloom_data_too_small: u64,};
/// One commit-graph file.pub const Layer = struct { bytes: []const u8, format: Format, /// How many commits it lists. count: u32, /// How many commits the files below it list: its first commit's /// position. base: u32 = 0, fanout_at: usize, ids_at: usize, data_at: usize, /// `GDA2`, if read. generations_at: ?usize, /// `GDO2`. overflow: []const u8, /// `EDGE`. edges: []const u8, /// `BIDX`, if the filters are read. bloom_index_at: ?usize, /// `BDAT` after its header. bloom_data: []const u8, bloom_settings: ?bloom.Settings, /// `BASE`, if there is one. bases: ?[]const u8, notes: [3]Note = undefined, note_count: u8 = 0,
/// Reads the file `bytes` holds, for a repository of `format`. `bytes` /// must outlive the result. pub fn parse(format: Format, bytes: []const u8, options: ParseOptions, diag: ?*Diagnostics) Error!Layer { const h = format.byteLength(); const min_size = 8 + 4 * 12 + 256 * 4 + h; if (bytes.len < min_size) return error.CommitGraphTooSmall; if (!std.mem.eql(u8, bytes[0..4], "CGPH")) { setDetail(diag, "{X}", .{std.mem.readInt(u32, bytes[0..4], .big)}); return error.BadCommitGraphSignature; } if (bytes[4] != 1) { setDetail(diag, "{X}", .{bytes[4]}); return error.UnsupportedCommitGraphVersion; } const want_hash: u8 = switch (format) { .sha1 => 1, .sha256 => 2, }; if (bytes[5] != want_hash) { setDetail(diag, "{X} does not match version {X}", .{ bytes[5], want_hash }); return error.CommitGraphHashMismatch; } const chunk_count: usize = bytes[6]; if (bytes.len < 8 + (chunk_count + 1) * 12 + 256 * 4 + h) { setDetail(diag, "{d}", .{chunk_count}); return error.CommitGraphTooSmallForChunks; }
const end = bytes.len - h; var chunks: [16]struct { id: [4]u8, start: usize, end: usize } = undefined; var known: usize = 0; var oidf: ?[]const u8 = null; var oidl: ?[]const u8 = null; var cdat: ?[]const u8 = null; var gda2: ?[]const u8 = null; var gdo2: ?[]const u8 = null; var edge: ?[]const u8 = null; var bidx: ?[]const u8 = null; var bdat: ?[]const u8 = null; var base: ?[]const u8 = null; for (0..chunk_count) |i| { const row = bytes[8 + 12 * i ..][0..24]; if (std.mem.readInt(u32, row[0..4], .big) == 0) return error.CommitGraphChunkTableEndsEarly; const start = std.mem.readInt(u64, row[4..12], .big); const next = std.mem.readInt(u64, row[16..24], .big); if (start > next or next > end) { setDetail(diag, "{x} and {x}", .{ start, next }); return error.BadCommitGraphChunkOffsets; } const id = row[0..4].*; for (chunks[0..@min(known, chunks.len)]) |c| if (std.mem.eql(u8, &c.id, &id)) { setDetail(diag, "{x}", .{std.mem.readInt(u32, &id, .big)}); return error.DuplicateCommitGraphChunk; }; if (known < chunks.len) chunks[known] = .{ .id = id, .start = @intCast(start), .end = @intCast(next) }; known += 1; const chunk = bytes[@intCast(start)..@intCast(next)]; const slot: ?*?[]const u8 = if (std.mem.eql(u8, &id, "OIDF")) &oidf else if (std.mem.eql(u8, &id, "OIDL")) &oidl else if (std.mem.eql(u8, &id, "CDAT")) &cdat else if (std.mem.eql(u8, &id, "GDA2")) &gda2 else if (std.mem.eql(u8, &id, "GDO2")) &gdo2 else if (std.mem.eql(u8, &id, "EDGE")) &edge else if (std.mem.eql(u8, &id, "BIDX")) &bidx else if (std.mem.eql(u8, &id, "BDAT")) &bdat else if (std.mem.eql(u8, &id, "BASE")) &base else null; if (slot) |s| s.* = chunk; } const last = bytes[8 + 12 * chunk_count ..][0..4]; if (std.mem.readInt(u32, last, .big) != 0) { setDetail(diag, "{x}", .{std.mem.readInt(u32, last, .big)}); return error.CommitGraphChunkTableUnterminated; }
const fanout = oidf orelse return missing(diag, "OID fanout"); if (fanout.len / 4 != 256) return wrong(diag, error.BadCommitGraphFanout, "oid fanout chunk is wrong size"); var previous: u32 = 0; for (0..256) |i| { const n = std.mem.readInt(u32, fanout[4 * i ..][0..4], .big); if (n < previous) return wrong(diag, error.BadCommitGraphFanout, "fanout values out of order"); previous = n; } const total = previous; const ids = oidl orelse return missing(diag, "OID lookup"); if (ids.len / h != total) return wrong(diag, error.BadCommitGraphLookup, "OID lookup chunk is the wrong size"); const data = cdat orelse return missing(diag, "commit data"); if (data.len / (h + 16) != total) return wrong(diag, error.BadCommitGraphCommitData, "commit data chunk is wrong size");
var layer: Layer = .{ .bytes = bytes, .format = format, .count = total, .fanout_at = offsetOf(bytes, fanout), .ids_at = offsetOf(bytes, ids), .data_at = offsetOf(bytes, data), .generations_at = null, .overflow = gdo2 orelse &.{}, .edges = edge orelse &.{}, .bloom_index_at = null, .bloom_data = &.{}, .bloom_settings = null, .bases = base, }; if (options.generation_version == 2) if (gda2) |g| { if (g.len / 4 == total) layer.generations_at = offsetOf(bytes, g) else layer.note(.generations_wrong_size); }; if (options.changed_paths_version != 0) if (bidx) |index| if (bdat) |filters| { if (index.len / 4 != total) { layer.note(.bloom_index_too_small); } else if (filters.len < 12) { layer.note(.{ .bloom_data_too_small = filters.len }); } else { const version = std.mem.readInt(u32, filters[0..4], .big); const hashes = std.mem.readInt(u32, filters[4..8], .big); const wanted = options.changed_paths_version == -1 or options.changed_paths_version == version; if (wanted and (version == 1 or version == 2) and hashes <= bloom.max_hashes) { layer.bloom_index_at = offsetOf(bytes, index); layer.bloom_data = filters[12..]; layer.bloom_settings = .{ .version = @fromBackingInt(@intCast(version)), .hashes = hashes, .bits_per_entry = std.mem.readInt(u32, filters[8..12], .big), }; } } }; return layer; }
fn note(l: *Layer, n: Note) void { l.notes[l.note_count] = n; l.note_count += 1; }
/// The optional chunks dropped while parsing. pub fn droppedChunks(l: *const Layer) []const Note { return l.notes[0..l.note_count]; }
/// The checksum at the end, which names the file in a chain. pub fn checksum(l: *const Layer) []const u8 { return l.bytes[l.bytes.len - l.format.byteLength() ..]; }
/// The object ID of the `i`th commit the file lists. pub fn idAt(l: *const Layer, i: u32) Id { const h = l.format.byteLength(); return .fromBytes(l.format, l.bytes[l.ids_at + @as(usize, i) * h ..][0..h]); }
/// Where the file lists `id`, if it does. pub fn find(l: *const Layer, id: Id) ?u32 { const h = l.format.byteLength(); const first = id.bytes[0]; var lo: usize = if (first == 0) 0 else l.fanoutAt(first - 1); var hi: usize = @min(l.fanoutAt(first), l.count); lo = @min(lo, hi); const want = id.slice(); while (lo < hi) { const mid = lo + (hi - lo) / 2; switch (std.mem.order(u8, l.bytes[l.ids_at + mid * h ..][0..h], want)) { .eq => return @intCast(mid), .lt => lo = mid + 1, .gt => hi = mid, } } return null; }
fn fanoutAt(l: *const Layer, b: u8) u32 { return std.mem.readInt(u32, l.bytes[l.fanout_at + 4 * @as(usize, b) ..][0..4], .big); }
fn entry(l: *const Layer, i: u32) []const u8 { const size = l.format.byteLength() + 16; return l.bytes[l.data_at + @as(usize, i) * size ..][0..size]; }
/// The Bloom filter of the `i`th commit, as `filter` describes. pub fn bloomFilter(l: *const Layer, i: u32) Filter { const index = l.bloom_index_at orelse return .none; const end = std.mem.readInt(u32, l.bytes[index + 4 * @as(usize, i) ..][0..4], .big); const start: u32 = if (i == 0) 0 else std.mem.readInt(u32, l.bytes[index + 4 * @as(usize, i - 1) ..][0..4], .big); if (end > l.bloom_data.len or start > l.bloom_data.len) return .{ .out_of_range = if (end > l.bloom_data.len) end else start }; if (start > end) return .{ .decreasing = .{ start, end } }; return .{ .bytes = l.bloom_data[start..end] }; }};
/// A commit's Bloom filter, or why there is none to read.pub const Filter = union(enum) { /// The filter, which may be empty if git did not compute it. bytes: []const u8, /// The file has no usable filters. none, /// `BIDX` points past the end of `BDAT`: git warns "ignoring /// out-of-range offset (N) for changed-path filter". out_of_range: u32, /// `BIDX` goes backwards: git warns "ignoring decreasing changed-path /// index offsets (A > B)". decreasing: [2]u32,};
fn offsetOf(bytes: []const u8, chunk: []const u8) usize { return @intFromPtr(chunk.ptr) - @intFromPtr(bytes.ptr);}
fn setDetail(diag: ?*Diagnostics, comptime fmt: []const u8, args: anytype) void { if (diag) |d| { d.reset(); d.setDetail(fmt, args); }}
fn missing(diag: ?*Diagnostics, which: []const u8) Error { setDetail(diag, "{s}", .{which}); return error.MissingCommitGraphChunk;}
fn wrong(diag: ?*Diagnostics, err: Error, what: []const u8) Error { setDetail(diag, "{s}", .{what}); return err;}
/// Writes what git says when it passes over a file for `err`, the/// diagnostic holding what `parse` put in it.pub fn writeError(w: *Io.Writer, err: Error, detail: []const u8) Io.Writer.Error!void { switch (err) { error.CommitGraphTooSmall => try w.writeAll("error: commit-graph file is too small\n"), error.CommitGraphTooSmallForChunks => try w.print("error: commit-graph file is too small to hold {s} chunks\n", .{detail}), error.BadCommitGraphSignature => try w.print("error: commit-graph signature {s} does not match signature 43475048\n", .{detail}), error.UnsupportedCommitGraphVersion => try w.print("error: commit-graph version {s} does not match version 1\n", .{detail}), error.CommitGraphHashMismatch => try w.print("error: commit-graph hash version {s}\n", .{detail}), error.CommitGraphChunkTableEndsEarly => try w.writeAll("error: terminating chunk id appears earlier than expected\n"), error.CommitGraphChunkTableUnterminated => try w.print("error: final chunk has non-zero id {s}\n", .{detail}), error.BadCommitGraphChunkOffsets => try w.print("error: improper chunk offset(s) {s}\n", .{detail}), error.DuplicateCommitGraphChunk => try w.print("error: duplicate chunk ID {s} found\n", .{detail}), error.BadCommitGraphFanout => try w.print("error: commit-graph {s}\nerror: commit-graph required OID fanout chunk missing or corrupted\n", .{detail}), error.BadCommitGraphLookup => try w.print("error: commit-graph {s}\nerror: commit-graph required OID lookup chunk missing or corrupted\n", .{detail}), error.BadCommitGraphCommitData => try w.print("error: commit-graph {s}\nerror: commit-graph required commit data chunk missing or corrupted\n", .{detail}), error.MissingCommitGraphChunk => try w.print("error: commit-graph required {s} chunk missing or corrupted\n", .{detail}), }}
// -- commits -------------------------------------------------------------------
/// What the commit-graph says of one commit.pub const Commit = struct { tree: Id, /// The commit date, in seconds since the epoch. time: i64, /// The corrected commit date or the topological level, as /// `corrected_dates` says. generation: u64,};
/// Why a commit could not be read from the commit-graph. git stops at the/// first, third and fourth; the second it reports and reads the commit/// object instead:////// - `InvalidParentPosition`: "invalid parent position N"; the detail is/// N./// - `ExtraEdgesOutOfBounds`: "commit-graph extra-edges pointer out of/// bounds"./// - `MissingGenerationOverflow`: "commit-graph requires overflow/// generation data but has none"./// - `GenerationOverflowTooSmall`: "commit-graph overflow generation data/// is too small".pub const ReadError = Allocator.Error || error{ InvalidParentPosition, ExtraEdgesOutOfBounds, MissingGenerationOverflow, GenerationOverflowTooSmall,};
/// How many commits the commit-graph lists.pub fn count(g: *const CommitGraph) u32 { if (g.layers.len == 0) return 0; const top = &g.layers[g.layers.len - 1]; return top.base + top.count;}
/// The position of `id`, if the commit-graph lists it.pub fn find(g: *const CommitGraph, id: Id) ?u32 { var i = g.layers.len; while (i > 0) { i -= 1; const l = &g.layers[i]; if (l.find(id)) |at| return l.base + at; } return null;}
/// The layer holding position `pos`, and where in it.pub fn locate(g: *const CommitGraph, pos: u32) ?struct { layer: *const Layer, index: u32 } { for (g.layers) |*l| { if (pos >= l.base and pos - l.base < l.count) return .{ .layer = l, .index = pos - l.base }; } return null;}
/// The object ID at position `pos`, which must be one the graph lists.pub fn idAt(g: *const CommitGraph, pos: u32) Id { const at = g.locate(pos).?; return at.layer.idAt(at.index);}
/// Reads the commit at `pos`, appending its parents' positions to/// `parents` in order. On `ExtraEdgesOutOfBounds`, `parents` is left as/// it was found.pub fn read(g: *const CommitGraph, gpa: Allocator, pos: u32, parents: *std.ArrayList(u32), diag: ?*Diagnostics) ReadError!Commit { const at = g.locate(pos).?; const l = at.layer; const e = l.entry(at.index); const h = l.format.byteLength(); const total = g.count(); const first = std.mem.readInt(u32, e[h..][0..4], .big); const second = std.mem.readInt(u32, e[h + 4 ..][0..4], .big); const keep = parents.items.len; errdefer parents.shrinkRetainingCapacity(keep); if (first != no_parent) { try parents.append(gpa, try checkParent(first, total, diag)); if (second != no_parent) { if (second & high_bit == 0) { try parents.append(gpa, try checkParent(second, total, diag)); } else { var i: usize = second & ~high_bit; while (true) : (i += 1) { if (i >= l.edges.len / 4) return error.ExtraEdgesOutOfBounds; const v = std.mem.readInt(u32, l.edges[4 * i ..][0..4], .big); try parents.append(gpa, try checkParent(v & ~high_bit, total, diag)); if (v & high_bit != 0) break; } } } } const levels = std.mem.readInt(u32, e[h + 8 ..][0..4], .big); const low = std.mem.readInt(u32, e[h + 12 ..][0..4], .big); const time: i64 = @as(i64, levels & 3) << 32 | low; var generation: u64 = levels >> 2; if (g.corrected_dates) if (l.generations_at) |ga| { const offset = std.mem.readInt(u32, l.bytes[ga + 4 * @as(usize, at.index) ..][0..4], .big); if (offset & high_bit == 0) { generation = @as(u64, @intCast(time)) + offset; } else { if (l.overflow.len == 0) return error.MissingGenerationOverflow; const i: usize = offset & ~high_bit; if (i >= l.overflow.len / 8) return error.GenerationOverflowTooSmall; generation = @as(u64, @intCast(time)) +% std.mem.readInt(u64, l.overflow[8 * i ..][0..8], .big); } }; return .{ .tree = .fromBytes(l.format, e[0..h]), .time = time, .generation = generation };}
/// The commit date and generation number of the commit at `pos`, without/// its parents, as git reads them to decide whether a commit is worth/// reading at all.pub fn readGeneration(g: *const CommitGraph, pos: u32) error{ MissingGenerationOverflow, GenerationOverflowTooSmall }!struct { time: i64, generation: u64 } { const at = g.locate(pos).?; const l = at.layer; const e = l.entry(at.index); const h = l.format.byteLength(); const levels = std.mem.readInt(u32, e[h + 8 ..][0..4], .big); const low = std.mem.readInt(u32, e[h + 12 ..][0..4], .big); const time: i64 = @as(i64, levels & 3) << 32 | low; var generation: u64 = levels >> 2; if (g.corrected_dates) if (l.generations_at) |ga| { const offset = std.mem.readInt(u32, l.bytes[ga + 4 * @as(usize, at.index) ..][0..4], .big); if (offset & high_bit == 0) { generation = @as(u64, @intCast(time)) + offset; } else { if (l.overflow.len == 0) return error.MissingGenerationOverflow; const i: usize = offset & ~high_bit; if (i >= l.overflow.len / 8) return error.GenerationOverflowTooSmall; generation = @as(u64, @intCast(time)) +% std.mem.readInt(u64, l.overflow[8 * i ..][0..8], .big); } }; return .{ .time = time, .generation = generation };}
fn checkParent(p: u32, total: u32, diag: ?*Diagnostics) ReadError!u32 { if (p >= total) { setDetail(diag, "{d}", .{p}); return error.InvalidParentPosition; } return p;}
/// The changed-path Bloom filter of the commit at `pos`, and the settings/// to read it with.pub fn bloomFilter(g: *const CommitGraph, pos: u32) struct { filter: Filter, settings: ?bloom.Settings } { const at = g.locate(pos).?; return .{ .filter = at.layer.bloomFilter(at.index), .settings = at.layer.bloom_settings };}
// -- reading the files ---------------------------------------------------------
/// A file memory-mapped read-only.const Mapped = struct { map: ?Io.File.MemoryMap, bytes: []const u8,
fn open(io: Io, dir: Io.Dir, sub_path: []const u8) !Mapped { const file = try dir.openFile(io, sub_path, .{}); defer file.close(io); const size = try file.length(io); if (size == 0) return .{ .map = null, .bytes = &.{} }; const len = std.math.cast(usize, size) orelse return error.FileTooBig; const map = try Io.File.MemoryMap.create(io, file, .{ .len = len, .protection = .{ .read = true }, .populate = false, }); return .{ .map = map, .bytes = map.memory[0..len] }; }
fn close(m: *Mapped, io: Io) void { if (m.map) |*map| map.destroy(io); m.* = .{ .map = null, .bytes = &.{} }; }};
/// An objects directory to look for a commit-graph in.pub const Source = struct { dir: Io.Dir, /// How git names the directory in its messages. path: []const u8,};
/// Finds and reads the commit-graph of a repository whose objects/// directories are `sources`, the repository's own first, as the top of/// this file describes. A repository without one has a commit-graph with/// no layers. What was wrong is in `problems`.pub fn open(gpa: Allocator, io: Io, format: Format, sources: []const Source, options: ParseOptions) (Allocator.Error || Io.Cancelable)!CommitGraph { var loader: Loader = .{ .gpa = gpa, .io = io, .format = format, .options = options, .sources = sources }; errdefer loader.deinit(); for (sources) |s| { if (try loader.tryFile(s.dir, s.path, "info/commit-graph", 0)) break; if (try loader.tryChain(s)) break; } const layers = try loader.layers.toOwnedSlice(gpa); errdefer gpa.free(layers); const maps = try loader.maps.toOwnedSlice(gpa); errdefer gpa.free(maps); const paths = try loader.paths.toOwnedSlice(gpa); errdefer gpa.free(paths); const problems = try loader.problems.toOwnedSlice(gpa); var corrected = options.generation_version == 2 and layers.len > 0; for (layers) |l| { if (l.generations_at == null) corrected = false; } return .{ .gpa = gpa, .format = format, .layers = layers, .maps = maps, .paths = paths, .corrected_dates = corrected, .problems = problems, };}
/// Unmaps the files and frees everything.pub fn close(g: *CommitGraph, io: Io) void { if (g.layers.len == 0 and g.problems.len == 0 and g.maps.len == 0) return; for (g.maps) |*m| m.close(io); g.gpa.free(g.maps); g.gpa.free(g.layers); for (g.paths) |p| g.gpa.free(p); g.gpa.free(g.paths); for (g.problems) |p| g.gpa.free(p.text); g.gpa.free(g.problems); g.* = empty;}
const Loader = struct { gpa: Allocator, io: Io, format: Format, options: ParseOptions, sources: []const Source, layers: std.ArrayList(Layer) = .empty, maps: std.ArrayList(Mapped) = .empty, paths: std.ArrayList([]u8) = .empty, problems: std.ArrayList(Problem) = .empty,
fn deinit(o: *Loader) void { for (o.maps.items) |*m| m.close(o.io); o.maps.deinit(o.gpa); o.layers.deinit(o.gpa); for (o.paths.items) |p| o.gpa.free(p); o.paths.deinit(o.gpa); for (o.problems.items) |p| o.gpa.free(p.text); o.problems.deinit(o.gpa); }
fn problem(o: *Loader, err: ProblemError, comptime fmt: []const u8, args: anytype) Allocator.Error!void { const text = try std.fmt.allocPrint(o.gpa, fmt, args); errdefer o.gpa.free(text); try o.problems.append(o.gpa, .{ .err = err, .text = text }); }
/// Reads one file as layer `index` of what is being loaded; false if /// it is not there or was passed over. fn tryFile(o: *Loader, dir: Io.Dir, dir_path: []const u8, sub_path: []const u8, index: usize) (Allocator.Error || Io.Cancelable)!bool { var map = Mapped.open(o.io, dir, sub_path) catch |err| switch (err) { error.Canceled => |e| return e, else => return false, }; errdefer map.close(o.io); var diag: Diagnostics = .{}; var layer = Layer.parse(o.format, map.bytes, o.options, &diag) catch |err| { var text: Io.Writer.Allocating = .init(o.gpa); defer text.deinit(); writeError(&text.writer, err, diag.detail()) catch return error.OutOfMemory; try o.problems.append(o.gpa, .{ .err = err, .text = try text.toOwnedSlice() }); map.close(o.io); return false; }; const path = try std.fs.path.join(o.gpa, &.{ dir_path, sub_path }); errdefer o.gpa.free(path); for (layer.droppedChunks()) |n| switch (n) { .generations_wrong_size => try o.problem(error.CommitGraphGenerationsWrongSize, "error: commit-graph generations chunk is wrong size\n", .{}), .bloom_index_too_small => try o.problem(error.CommitGraphBloomIndexTooSmall, "warning: commit-graph changed-path index chunk is too small\n", .{}), .bloom_data_too_small => |size| try o.problem(error.CommitGraphBloomDataTooSmall, "warning: ignoring too-small changed-path chunk ({d} < 12) in commit-graph file\n", .{size}), }; if (index > 0) { const h = o.format.byteLength(); const bases = layer.bases orelse { try o.problem(error.CommitGraphMissingBase, "warning: commit-graph has no base graphs chunk\n", .{}); o.gpa.free(path); map.close(o.io); return false; }; if (bases.len / h < index) { try o.problem(error.CommitGraphBaseTooSmall, "warning: commit-graph base graphs chunk is too small\n", .{}); o.gpa.free(path); map.close(o.io); return false; } for (o.layers.items, 0..) |*below, j| { if (!std.mem.eql(u8, bases[j * h ..][0..h], below.checksum())) { try o.problem(error.CommitGraphChainMismatch, "warning: commit-graph chain does not match\n", .{}); o.gpa.free(path); map.close(o.io); return false; } } const top = &o.layers.items[o.layers.items.len - 1]; layer.base = std.math.add(u32, top.base, top.count) catch { try o.problem(error.CommitGraphChainMismatch, "warning: commit-graph chain does not match\n", .{}); o.gpa.free(path); map.close(o.io); return false; }; } try o.paths.append(o.gpa, path); errdefer _ = o.paths.pop(); try o.maps.append(o.gpa, map); errdefer _ = o.maps.pop(); try o.layers.append(o.gpa, layer); return true; }
/// Reads the chain in `s`, if it has one; true if any of it was read. fn tryChain(o: *Loader, s: Source) (Allocator.Error || Io.Cancelable)!bool { var buffer: [64 * 1024]u8 = undefined; const contents = s.dir.readFile(o.io, "info/commit-graphs/commit-graph-chain", &buffer) catch |err| switch (err) { error.Canceled => |e| return e, else => return false, }; const hex_len = o.format.hexLength(); const lines = contents.len / (hex_len + 1); var rest = contents; for (0..lines) |i| { const nl = std.mem.findScalar(u8, rest, '\n') orelse rest.len; const line = rest[0..nl]; rest = rest[@min(nl + 1, rest.len)..]; if (line.len < hex_len or !isHex(line[0..hex_len])) { try o.problem(error.InvalidCommitGraphChain, "warning: invalid commit-graph chain: line '{s}' not a hash\n", .{line}); break; } var name_buffer: [512]u8 = undefined; const name = std.fmt.bufPrint(&name_buffer, "info/commit-graphs/graph-{s}.graph", .{line}) catch ""; const found = found: { if (name.len == 0) break :found false; for (o.sources) |where| { if (try o.tryFileIfThere(where, name, i)) |ok| break :found ok; } break :found false; }; if (!found) { try o.problem(error.IncompleteCommitGraphChain, "warning: unable to find all commit-graph files\n", .{}); break; } } return o.layers.items.len > 0; }
/// `tryFile`, or null when the file is not in this directory. fn tryFileIfThere(o: *Loader, s: Source, name: []const u8, index: usize) (Allocator.Error || Io.Cancelable)!?bool { s.dir.access(o.io, name, .{}) catch |err| switch (err) { error.Canceled => |e| return e, else => return null, }; return try o.tryFile(s.dir, s.path, name, index); }};
fn isHex(text: []const u8) bool { for (text) |c| if (!std.ascii.isHex(c)) return false; return true;}
// -- tests -----------------------------------------------------------------------
const testing = std.testing;const fixture = @import("testing/fixture.zig");const fuzz_input = @import("testing/fuzz.zig");
fn fuzzOne(format: Format, smith: *testing.Smith) anyerror!void { var buffer: [8192]u8 = undefined; const input = fuzz_input.bytes(smith, &buffer); var diag: Diagnostics = .{}; const layer = Layer.parse(format, input, .{}, &diag) catch return; // Every commit, its parents, generation and filter, read as a walk // would read them, in a graph of this one layer. const layers = [_]Layer{layer}; const g: CommitGraph = .{ .gpa = testing.allocator, .format = format, .layers = @constCast(&layers), .maps = &.{}, .paths = &.{}, .corrected_dates = layer.generations_at != null, .problems = &.{}, }; var parents: std.ArrayList(u32) = .empty; defer parents.deinit(testing.allocator); var i: u32 = 0; while (i < layer.count) : (i += 1) { const id = layer.idAt(i); _ = layer.find(id); parents.clearRetainingCapacity(); _ = g.read(testing.allocator, i, &parents, &diag) catch {}; for (parents.items) |p| try testing.expect(p < layer.count); switch (layer.bloomFilter(i)) { .bytes => |f| if (layer.bloom_settings) |s| { _ = bloom.mayContain(f, s.hashes, .init(s.version, "a/b")); }, else => {}, } }}
test "fuzz: commit-graph files" { try testing.fuzz(Format.sha1, fuzzOne, .{ .corpus = &.{ @embedFile("fuzz/commit-graph"), @embedFile("fuzz/commit-graph-octopus"), @embedFile("fuzz/commit-graph-split"), } });}
test "fuzz: SHA-256 commit-graph files" { try testing.fuzz(Format.sha256, fuzzOne, .{ .corpus = &.{ @embedFile("fuzz/commit-graph-sha256"), } });}
/// The corrected commit dates and topological levels of every commit, as/// gitformat-commit-graph(5) defines them, from git's own account of the/// parents and dates.fn expectGenerations(repo: *fixture.Repo, g: *const CommitGraph) !void { const gpa = repo.gpa; const out = try repo.output(&.{ "rev-list", "--reverse", "--topo-order", "--parents", "--timestamp", "--all" }); defer gpa.free(out); var levels: std.StringHashMapUnmanaged(struct { level: u64, corrected: u64 }) = .empty; defer levels.deinit(gpa); var lines = std.mem.tokenizeScalar(u8, out, '\n'); var parents: std.ArrayList(u32) = .empty; defer parents.deinit(gpa); while (lines.next()) |line| { var fields = std.mem.tokenizeScalar(u8, line, ' '); const time = try std.fmt.parseInt(u64, fields.next().?, 10); const hex = fields.next().?; var level: u64 = 1; var corrected: u64 = time; while (fields.next()) |p| { const pl = levels.get(p).?; level = @max(level, pl.level + 1); corrected = @max(corrected, pl.corrected + 1); } try levels.put(gpa, hex, .{ .level = level, .corrected = corrected }); const id = try Id.parseHex(repo.object_format, hex); const pos = g.find(id) orelse return error.CommitNotInGraph; parents.clearRetainingCapacity(); const c = try g.read(gpa, pos, &parents, null); try testing.expectEqual(@as(i64, @intCast(time)), c.time); try testing.expectEqual(if (g.corrected_dates) corrected else level, c.generation); }}
fn openGraph(repo: *fixture.Repo, options: ParseOptions) !CommitGraph { var dir = try repo.tmp.dir.openDir(repo.io, ".git/objects", .{}); defer dir.close(repo.io); return open(repo.gpa, repo.io, repo.object_format, &.{.{ .dir = dir, .path = ".git/objects" }}, options);}
fn makeOctopus(repo: *fixture.Repo) !void { try repo.commitFile("a", "a\n", "root"); for ([_][]const u8{ "x1", "x2", "x3" }) |b| { try repo.git(&.{ "checkout", "-q", "-b", b, "main" }); try repo.commitFile(b, "x\n", b); } try repo.git(&.{ "checkout", "-q", "main" }); try repo.git(&.{ "merge", "-q", "--no-edit", "-m", "octopus", "x1", "x2", "x3" }); try repo.commitFile("d", "d\n", "after");}
test "a commit-graph git wrote reads as git's history says" { const gpa = testing.allocator; var repo = try fixture.Repo.init(gpa, testing.io); defer repo.deinit(); try makeOctopus(&repo); // A commit with a date that needs a corrected commit date offset too // large for 31 bits, and one before its parent. try repo.env.put("GIT_COMMITTER_DATE", "@8589934592 +0000"); try repo.git(&.{ "commit", "-q", "--allow-empty", "-m", "future" }); try repo.env.put("GIT_COMMITTER_DATE", "@1000 +0000"); try repo.git(&.{ "commit", "-q", "--allow-empty", "-m", "past" }); try repo.git(&.{ "commit-graph", "write", "--reachable", "--changed-paths" });
var g = try openGraph(&repo, .{}); defer g.close(repo.io); try testing.expectEqual(0, g.problems.len); try testing.expectEqual(1, g.layers.len); try testing.expect(g.corrected_dates); try testing.expect(g.layers[0].overflow.len > 0); try testing.expect(g.layers[0].edges.len > 0);
// Every commit's parents and tree are git's. const out = try repo.output(&.{ "log", "--all", "--format=%H %T %P" }); defer gpa.free(out); var lines = std.mem.tokenizeScalar(u8, out, '\n'); var parents: std.ArrayList(u32) = .empty; defer parents.deinit(gpa); var n: u32 = 0; while (lines.next()) |line| : (n += 1) { var fields = std.mem.tokenizeScalar(u8, line, ' '); const pos = g.find(try .parseHex(repo.object_format, fields.next().?)).?; parents.clearRetainingCapacity(); const c = try g.read(gpa, pos, &parents, null); try testing.expect(c.tree.eql(try .parseHex(repo.object_format, fields.next().?))); for (parents.items) |p| try testing.expect(g.idAt(p).eql(try .parseHex(repo.object_format, fields.next().?))); try testing.expectEqual(null, fields.next()); } try testing.expectEqual(n, g.count()); try expectGenerations(&repo, &g);
// Without corrected commit dates, generation numbers are levels. var v1 = try openGraph(&repo, .{ .generation_version = 1 }); defer v1.close(repo.io); try testing.expect(!v1.corrected_dates); try expectGenerations(&repo, &v1);}
test "changed-path Bloom filters hold every path a commit changed" { const gpa = testing.allocator; for ([_][]const u8{ "1", "2" }) |version| { var repo = try fixture.Repo.init(gpa, testing.io); defer repo.deinit(); try repo.tmp.dir.createDirPath(repo.io, "d/e"); try repo.commitFile("d/e/f", "1\n", "one"); try repo.commitFile("caf\xc3\xa9", "2\n", "two"); try repo.commitFile("d/g", "3\n", "three"); try repo.git(&.{ "commit", "-q", "--allow-empty", "-m", "empty" }); const setting = try std.fmt.allocPrint(gpa, "commitGraph.changedPathsVersion={s}", .{version}); defer gpa.free(setting); try repo.git(&.{ "-c", setting, "commit-graph", "write", "--reachable", "--changed-paths" }); var g = try openGraph(&repo, .{}); defer g.close(repo.io); const out = try repo.output(&.{ "log", "--format=%H" }); defer gpa.free(out); var commits = std.mem.tokenizeScalar(u8, out, '\n'); while (commits.next()) |hex| { const pos = g.find(try .parseHex(repo.object_format, hex)).?; const f = g.bloomFilter(pos); const settings = f.settings.?; try testing.expectEqual(try std.fmt.parseInt(u32, version, 10), @backingInt(settings.version)); const changed = try repo.output(&.{ "-c", "core.quotePath=false", "diff-tree", "--root", "-r", "-t", "--name-only", "--no-commit-id", hex }); defer gpa.free(changed); var paths = std.mem.tokenizeScalar(u8, changed, '\n'); var any = false; while (paths.next()) |p| { any = true; try testing.expect(bloom.mayContain(f.filter.bytes, settings.hashes, .init(settings.version, p))); } // An empty commit's filter holds nothing. if (!any) try testing.expect(!bloom.mayContain(f.filter.bytes, settings.hashes, .init(settings.version, "d"))); } // Filters of the version the caller does not read are dropped. const other: i64 = if (version[0] == '1') 2 else 1; var none = try openGraph(&repo, .{ .changed_paths_version = other }); defer none.close(repo.io); try testing.expectEqual(null, none.layers[0].bloom_settings); }}
test "a split commit-graph chain reads as one" { 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.commitFile("a", "2\n", "two"); try repo.git(&.{ "commit-graph", "write", "--reachable", "--split" }); try makeOctopus(&repo); try repo.git(&.{ "commit-graph", "write", "--reachable", "--split=no-merge" }); try repo.commitFile("a", "3\n", "three"); try repo.git(&.{ "commit-graph", "write", "--reachable", "--split=no-merge", "--changed-paths" }); var g = try openGraph(&repo, .{}); defer g.close(repo.io); try testing.expectEqual(0, g.problems.len); try testing.expectEqual(3, g.layers.len); try expectGenerations(&repo, &g);
// A chain whose middle file is missing keeps what is below it. const chain = try repo.tmp.dir.readFileAlloc(repo.io, ".git/objects/info/commit-graphs/commit-graph-chain", gpa, .unlimited); defer gpa.free(chain); const second = chain[repo.object_format.hexLength() + 1 ..][0..repo.object_format.hexLength()]; const name = try std.fmt.allocPrint(gpa, ".git/objects/info/commit-graphs/graph-{s}.graph", .{second}); defer gpa.free(name); try repo.tmp.dir.deleteFile(repo.io, name); var cut = try openGraph(&repo, .{}); defer cut.close(repo.io); try testing.expectEqual(1, cut.layers.len); try testing.expectEqual(error.IncompleteCommitGraphChain, cut.problems[0].err);}
test "a corrupt commit-graph file is passed over in git's words" { const gpa = testing.allocator; var repo = try fixture.Repo.init(gpa, testing.io); defer repo.deinit(); try makeOctopus(&repo); try repo.git(&.{ "commit-graph", "write", "--reachable" }); const path = ".git/objects/info/commit-graph"; const good = try repo.tmp.dir.readFileAlloc(repo.io, path, gpa, .unlimited); defer gpa.free(good); const bytes = try gpa.dupe(u8, good); defer gpa.free(bytes); const Case = struct { at: usize, value: u8, want: Error, text: []const u8 }; const hash_text = if (repo.object_format == .sha1) "error: commit-graph hash version 2 does not match version 1\n" else "error: commit-graph hash version 1 does not match version 2\n"; for ([_]Case{ .{ .at = 0, .value = 0xab, .want = error.BadCommitGraphSignature, .text = "error: commit-graph signature AB475048 does not match signature 43475048\n" }, .{ .at = 4, .value = 2, .want = error.UnsupportedCommitGraphVersion, .text = "error: commit-graph version 2 does not match version 1\n" }, .{ .at = 5, .value = if (repo.object_format == .sha1) 2 else 1, .want = error.CommitGraphHashMismatch, .text = hash_text }, .{ .at = 6, .value = 255, .want = error.CommitGraphTooSmallForChunks, .text = "error: commit-graph file is too small to hold 255 chunks\n" }, .{ .at = 6, .value = 2, .want = error.CommitGraphChunkTableUnterminated, .text = "error: final chunk has non-zero id 43444154\n" }, .{ .at = 8, .value = 'X', .want = error.MissingCommitGraphChunk, .text = "error: commit-graph required OID fanout chunk missing or corrupted\n" }, }) |case| { @memcpy(bytes, good); bytes[case.at] = case.value; var diag: Diagnostics = .{}; try testing.expectError(case.want, Layer.parse(repo.object_format, bytes, .{}, &diag)); var text: Io.Writer.Allocating = .init(gpa); defer text.deinit(); try writeError(&text.writer, case.want, diag.detail()); try testing.expectEqualStrings(case.text, text.written());
// And git says the same, and reads the history without it. try repo.tmp.dir.deleteFile(repo.io, path); try repo.tmp.dir.writeFile(repo.io, .{ .sub_path = path, .data = bytes }); const o = try repo.runIn(".", &.{ "rev-list", "--all" }, ""); defer o.deinit(gpa); try testing.expectEqualStrings(case.text, o.stderr); } try testing.expectError(error.CommitGraphTooSmall, Layer.parse(repo.object_format, good[0..100], .{}, null));}