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.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie <jeff@ocjtech.us>// SPDX-License-Identifier: MIT
//! Repositories whose object IDs collide on their first digits, for the//! tests of abbreviated object IDs. A blob's ID depends only on its//! contents, so contents are searched for here, in the test, until their//! IDs begin as wanted: a blob beginning like a given commit, tag or tree,//! or groups of blobs sharing their first digits with one another. The//! search is the birthday one for groups (some 2^14 tries for seven//! digits) and a plain one for a given prefix (some 16^n tries for n//! digits), so it stays quick for the lengths the tests use.//!//! `build` makes the repository every abbreviation test reads: commits,//! annotated tags, and colliding blobs spread over two packs, a//! multi-pack-index, loose objects and an alternate.
const std = @import("std");const Allocator = std.mem.Allocator;
const object = @import("../object.zig");const Format = object.Format;const fixture = @import("fixture.zig");const Repo = fixture.Repo;
/// Contents of a blob whose ID begins with the hexadecimal `prefix`/// (lowercase, at most six digits), which the caller frees. `salt`/// varies the search, so that two calls with one prefix can find two/// blobs.pub fn blobBeginning(gpa: Allocator, format: Format, prefix: []const u8, salt: []const u8) ![]u8 { var i: u64 = 0; var buffer: [128]u8 = undefined; while (true) : (i += 1) { const contents = try std.fmt.bufPrint(&buffer, "collide {s} {s} {d}\n", .{ salt, prefix, i }); const id = object.hash(format, .blob, contents); var hex: [object.max_hex_length]u8 = undefined; if (std.mem.startsWith(u8, id.toHex(&hex), prefix)) return gpa.dupe(u8, contents); }}
/// Contents of `count` blobs whose IDs share exactly their first `digits`/// digits (at most eight) and no more, which the caller frees with/// `freeAll`. `salt` varies the search.pub fn blobsSharing(gpa: Allocator, format: Format, digits: u5, count: usize, salt: []const u8) ![][]u8 { std.debug.assert(digits >= 1 and digits <= 8 and count >= 2); var seen: std.AutoHashMapUnmanaged(u32, std.ArrayList(u64)) = .empty; defer { var it = seen.valueIterator(); while (it.next()) |v| v.deinit(gpa); seen.deinit(gpa); } var buffer: [128]u8 = undefined; var i: u64 = 0; while (true) : (i += 1) { const contents = try std.fmt.bufPrint(&buffer, "share {s} {d} {d}\n", .{ salt, digits, i }); const id = object.hash(format, .blob, contents); const key = std.mem.readInt(u32, id.bytes[0..4], .big) >> @intCast(32 - 4 * @as(u6, digits)); const gop = try seen.getOrPut(gpa, key); if (!gop.found_existing) gop.value_ptr.* = .empty; // Keep only those sharing no further digit with the ones before. const next_digit = digitAt(id, digits); const distinct = for (gop.value_ptr.items) |j| { const other = object.hash(format, .blob, try std.fmt.bufPrint(&buffer, "share {s} {d} {d}\n", .{ salt, digits, j })); if (digitAt(other, digits) == next_digit) break false; } else true; if (!distinct) continue; try gop.value_ptr.append(gpa, i); if (gop.value_ptr.items.len == count) { const out = try gpa.alloc([]u8, count); var made: usize = 0; errdefer { for (out[0..made]) |o| gpa.free(o); gpa.free(out); } for (gop.value_ptr.items) |j| { out[made] = try std.fmt.allocPrint(gpa, "share {s} {d} {d}\n", .{ salt, digits, j }); made += 1; } return out; } }}
fn digitAt(id: object.Id, n: usize) u8 { const b = id.bytes[n / 2]; return if (n % 2 == 0) b >> 4 else b & 0xf;}
/// Frees what `blobsSharing` returned.pub fn freeAll(gpa: Allocator, all: [][]u8) void { for (all) |a| gpa.free(a); gpa.free(all);}
/// Writes a blob with `git hash-object -w`, into `git_dir` if it is not/// null, and returns its ID in hexadecimal, which the caller frees.pub fn writeBlob(repo: *Repo, git_dir: ?[]const u8, contents: []const u8) ![]u8 { var dir_arg: [256]u8 = undefined; const args: []const []const u8 = if (git_dir) |d| &.{ try std.fmt.bufPrint(&dir_arg, "--git-dir={s}", .{d}), "hash-object", "-w", "--stdin" } else &.{ "hash-object", "-w", "--stdin" }; const out = try repo.outputWithInput(args, contents); defer repo.gpa.free(out); return repo.gpa.dupe(u8, std.mem.trimEnd(u8, out, "\n"));}
/// The ID `rev` names, in hexadecimal, which the caller frees.pub fn revParse(repo: *Repo, rev: []const u8) ![]u8 { const out = try repo.output(&.{ "rev-parse", rev }); defer repo.gpa.free(out); return repo.gpa.dupe(u8, std.mem.trimEnd(u8, out, "\n"));}
/// What `build` made: the prefixes worth asking about, each as its/// lowercase hexadecimal digits.pub const Collisions = struct { gpa: Allocator, prefixes: std.ArrayList([]u8) = .empty,
pub fn deinit(c: *Collisions) void { for (c.prefixes.items) |p| c.gpa.free(p); c.prefixes.deinit(c.gpa); }
fn add(c: *Collisions, hex: []const u8, digits: usize) !void { try c.prefixes.append(c.gpa, try c.gpa.dupe(u8, hex[0..digits])); }};
/// Makes, in `repo`:////// - three commits, an annotated tag of the last, a tag of that tag, a/// tag of its tree and a tag of a blob;/// - a blob beginning with the same four digits as each commit, tag and/// tree named above, and with the same five as the last commit;/// - three blobs sharing four digits, and pairs sharing five, six and/// seven;////// with the first half packed into one pack, the next into a second, a/// multi-pack-index over both, the rest loose, and some in an alternate/// (`alternate.git`, named by `objects/info/alternates`) colliding with/// objects of the repository's own.pub fn build(repo: *Repo) !Collisions { const gpa = repo.gpa; const format = repo.object_format; var c: Collisions = .{ .gpa = gpa }; errdefer c.deinit();
try repo.commitFile("a", "one\n", "first commit"); try repo.commitFile("b", "two\n", "second commit\n\nwith a body"); try repo.commitFile("a", "three\n", "third commit"); try repo.git(&.{ "tag", "-a", "-m", "version one", "v1" }); try repo.git(&.{ "tag", "-a", "-m", "again", "v1-again", "v1" }); try repo.git(&.{ "tag", "-a", "-m", "a tree", "tree-tag", "HEAD^{tree}" }); try repo.git(&.{ "tag", "-a", "-m", "a blob", "blob-tag", "HEAD:b" });
// Blobs beginning like each commit, tag and tree. for ([_][]const u8{ "HEAD", "HEAD~", "HEAD~2", "v1", "v1-again", "tree-tag", "blob-tag", "HEAD^{tree}", "HEAD~^{tree}", "HEAD:a" }) |rev| { const id = try revParse(repo, rev); defer gpa.free(id); const contents = try blobBeginning(gpa, format, id[0..4], rev); defer gpa.free(contents); gpa.free(try writeBlob(repo, null, contents)); try c.add(id, 4); } { const head = try revParse(repo, "HEAD"); defer gpa.free(head); const contents = try blobBeginning(gpa, format, head[0..5], "five"); defer gpa.free(contents); gpa.free(try writeBlob(repo, null, contents)); try c.add(head, 5); } // The first pack. try repo.git(&.{ "repack", "-a", "-d", "-q" });
// Groups of blobs, one of each group packed now, the others later or // loose. const Group = struct { digits: u5, count: usize }; var later: std.ArrayList([]u8) = .empty; defer { for (later.items) |l| gpa.free(l); later.deinit(gpa); } var loose: std.ArrayList([]u8) = .empty; defer { for (loose.items) |l| gpa.free(l); loose.deinit(gpa); } for ([_]Group{ .{ .digits = 4, .count = 3 }, .{ .digits = 5, .count = 2 }, .{ .digits = 6, .count = 2 }, .{ .digits = 7, .count = 2 } }) |g| { const blobs = try blobsSharing(gpa, format, g.digits, g.count, "group"); defer freeAll(gpa, blobs); const first = try writeBlob(repo, null, blobs[0]); defer gpa.free(first); try c.add(first, g.digits); try later.append(gpa, try gpa.dupe(u8, blobs[1])); if (g.count > 2) try loose.append(gpa, try gpa.dupe(u8, blobs[2])); } // The second pack holds the first of each group, and the // multi-pack-index covers both packs. try repo.git(&.{ "repack", "-d", "-q" }); for (later.items) |l| gpa.free(try writeBlob(repo, null, l)); try repo.git(&.{ "repack", "-d", "-q" }); try repo.git(&.{ "multi-pack-index", "write" }); for (loose.items) |l| gpa.free(try writeBlob(repo, null, l));
// An alternate holding blobs that collide with the repository's own // commits, and a pair of its own sharing five digits, one packed. try repo.git(&.{ "init", "-q", "--bare", "alternate.git" }); { const head = try revParse(repo, "HEAD~"); defer gpa.free(head); const contents = try blobBeginning(gpa, format, head[0..4], "alternate"); defer gpa.free(contents); gpa.free(try writeBlob(repo, "alternate.git", contents)); const blobs = try blobsSharing(gpa, format, 5, 2, "alternate"); defer freeAll(gpa, blobs); const first = try writeBlob(repo, "alternate.git", blobs[0]); defer gpa.free(first); try repo.git(&.{ "--git-dir=alternate.git", "repack", "-a", "-d", "-q" }); gpa.free(try writeBlob(repo, "alternate.git", blobs[1])); try c.add(first, 5); // And one in the repository's own loose objects sharing them. const own = try blobBeginning(gpa, format, first[0..5], "own"); defer gpa.free(own); gpa.free(try writeBlob(repo, null, own)); } const alternates = try std.fmt.allocPrint(gpa, "{s}/alternate.git/objects\n", .{repo.path}); defer gpa.free(alternates); try repo.tmp.dir.writeFile(repo.io, .{ .sub_path = ".git/objects/info/alternates", .data = alternates }); return c;}