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.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie <jeff@ocjtech.us>// SPDX-License-Identifier: MIT
//! Packs and pack indexes written byte by byte, for the tests that need//! one git will not write: a pack index with large offsets but no 2 GiB//! pack behind it, a REF_DELTA whose base is in another pack or loose, a//! delta chain that loops, and every kind of corruption. git still reads//! them, and is still the oracle for what reading them should say.//!//! The pack format is gitformat-pack(5)'s. Entries are compressed as//! stored DEFLATE blocks, which is the simplest valid zlib stream.
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 Kind = object.Kind;const fixture = @import("fixture.zig");
/// `raw` as a zlib stream of stored DEFLATE blocks, as many as it takes,/// which the caller frees.pub fn zlibStored(gpa: Allocator, raw: []const u8) ![]u8 { var out: std.ArrayList(u8) = .empty; errdefer out.deinit(gpa); try out.appendSlice(gpa, &.{ 0x78, 0x01 }); var rest = raw; while (true) { const n: u16 = @intCast(@min(rest.len, std.math.maxInt(u16))); const last = n == rest.len; try out.append(gpa, if (last) 1 else 0); var len: [4]u8 = undefined; std.mem.writeInt(u16, len[0..2], n, .little); std.mem.writeInt(u16, len[2..4], ~n, .little); try out.appendSlice(gpa, &len); try out.appendSlice(gpa, rest[0..n]); rest = rest[n..]; if (last) break; } var adler: [4]u8 = undefined; std.mem.writeInt(u32, &adler, std.hash.Adler32.hash(raw), .big); try out.appendSlice(gpa, &adler); return out.toOwnedSlice(gpa);}
/// The hash of `bytes` in `format`.pub fn digest(format: Format, bytes: []const u8) [object.max_byte_length]u8 { var d: [object.max_byte_length]u8 = @splat(0); switch (format) { .sha1 => std.crypto.hash.Sha1.hash(bytes, d[0..20], .{}), .sha256 => std.crypto.hash.sha2.Sha256.hash(bytes, d[0..32], .{}), } return d;}
/// A delta that makes `result` from a base of `base_len` bytes by/// inserting every byte of it.pub fn deltaInsert(gpa: Allocator, base_len: u64, result: []const u8) ![]u8 { var out: std.ArrayList(u8) = .empty; errdefer out.deinit(gpa); try writeSize(gpa, &out, base_len); try writeSize(gpa, &out, result.len); var rest = result; while (rest.len > 0) { const n = @min(rest.len, 127); try out.append(gpa, @intCast(n)); try out.appendSlice(gpa, rest[0..n]); rest = rest[n..]; } return out.toOwnedSlice(gpa);}
/// A delta that makes `base ++ suffix` from `base`: one copy of the whole/// base, then the suffix inserted.pub fn deltaAppend(gpa: Allocator, base_len: u32, suffix: []const u8) ![]u8 { var out: std.ArrayList(u8) = .empty; errdefer out.deinit(gpa); try writeSize(gpa, &out, base_len); try writeSize(gpa, &out, base_len + suffix.len); var at: u32 = 0; while (at < base_len) { const n: u32 = @min(base_len - at, 0xffff); try out.appendSlice(gpa, &.{ 0x80 | 0x0f | 0x30, @truncate(at), @truncate(at >> 8), @truncate(at >> 16), @truncate(at >> 24), @truncate(n), @truncate(n >> 8) }); at += n; } var rest = suffix; while (rest.len > 0) { const n = @min(rest.len, 127); try out.append(gpa, @intCast(n)); try out.appendSlice(gpa, rest[0..n]); rest = rest[n..]; } return out.toOwnedSlice(gpa);}
fn writeSize(gpa: Allocator, out: *std.ArrayList(u8), value: u64) !void { var v = value; while (v >= 0x80) : (v >>= 7) try out.append(gpa, @as(u8, @truncate(v)) | 0x80); try out.append(gpa, @intCast(v));}
/// A pack being written an entry at a time, and the version 2 index that/// goes with it.pub const PackWriter = struct { gpa: Allocator, format: Format, bytes: std.ArrayList(u8) = .empty, entries: std.ArrayList(Entry) = .empty,
/// One object the index will list. pub const Entry = struct { id: Id, offset: u64, crc: u32 };
/// A pack with a header and nothing else yet. pub fn init(gpa: Allocator, format: Format) !PackWriter { var w: PackWriter = .{ .gpa = gpa, .format = format }; try w.bytes.appendSlice(gpa, "PACK\x00\x00\x00\x02\x00\x00\x00\x00"); return w; }
/// Frees what has been written. pub fn deinit(w: *PackWriter) void { w.bytes.deinit(w.gpa); w.entries.deinit(w.gpa); }
/// An entry whose header says `type_number` and `size`, followed by /// `between` (a delta's base) and `compressed` exactly as given. It is /// listed in the index under `id`, if there is one. Returns its offset. pub fn raw(w: *PackWriter, type_number: u3, size: u64, between: []const u8, compressed: []const u8, id: ?Id) !u64 { const offset = w.bytes.items.len; var first: u8 = @as(u8, type_number) << 4 | @as(u8, @truncate(size & 0x0f)); var rest = size >> 4; while (true) { if (rest != 0) first |= 0x80; try w.bytes.append(w.gpa, first); if (rest == 0) break; first = @truncate(rest & 0x7f); rest >>= 7; } try w.bytes.appendSlice(w.gpa, between); try w.bytes.appendSlice(w.gpa, compressed); if (id) |i| try w.entries.append(w.gpa, .{ .id = i, .offset = offset, .crc = std.hash.Crc32.hash(w.bytes.items[offset..]), }); return offset; }
/// An object stored whole. Returns its offset. pub fn whole(w: *PackWriter, kind: Kind, contents: []const u8) !u64 { const z = try zlibStored(w.gpa, contents); defer w.gpa.free(z); return w.raw(@backingInt(kind), contents.len, "", z, object.hash(w.format, kind, contents)); }
/// An OFS_DELTA against the entry at `base_offset`, listed as `id`. pub fn ofsDelta(w: *PackWriter, base_offset: u64, delta: []const u8, id: ?Id) !u64 { const offset = w.bytes.items.len; var buf: [16]u8 = undefined; const enc = encodeOffset(offset - base_offset, &buf); const z = try zlibStored(w.gpa, delta); defer w.gpa.free(z); return w.raw(6, delta.len, enc, z, id); }
/// A REF_DELTA against the object `base`, listed as `id`. pub fn refDelta(w: *PackWriter, base: Id, delta: []const u8, id: ?Id) !u64 { const z = try zlibStored(w.gpa, delta); defer w.gpa.free(z); return w.raw(7, delta.len, base.slice(), z, id); }
/// The pack's bytes and its index's, with the object count and both /// checksums filled in; the caller frees both. pub fn finish(w: *PackWriter) !struct { pack: []u8, idx: []u8 } { std.mem.writeInt(u32, w.bytes.items[8..12], @intCast(w.entries.items.len), .big); const d = digest(w.format, w.bytes.items); try w.bytes.appendSlice(w.gpa, d[0..w.format.byteLength()]); const pack = try w.bytes.toOwnedSlice(w.gpa); errdefer w.gpa.free(pack); std.mem.sort(Entry, w.entries.items, {}, struct { fn lt(_: void, a: Entry, b: Entry) bool { return std.mem.order(u8, a.id.slice(), b.id.slice()) == .lt; } }.lt); const idx = try writeIndex(w.gpa, w.format, w.entries.items, pack[pack.len - w.format.byteLength() ..]); return .{ .pack = pack, .idx = idx }; }};
/// The offset encoding an OFS_DELTA's distance back to its base is/// written in.pub fn encodeOffset(distance: u64, buf: *[16]u8) []const u8 { var i: usize = buf.len - 1; var v = distance; buf[i] = @intCast(v & 0x7f); while (true) { v >>= 7; if (v == 0) break; v -= 1; i -= 1; buf[i] = 0x80 | @as(u8, @intCast(v & 0x7f)); } return buf[i..];}
/// A version 2 pack index of `entries`, which must be sorted by object/// ID, for a pack whose checksum is `pack_checksum`.pub fn writeIndex(gpa: Allocator, format: Format, entries: []const PackWriter.Entry, pack_checksum: []const u8) ![]u8 { var out: std.ArrayList(u8) = .empty; errdefer out.deinit(gpa); try out.appendSlice(gpa, "\xfftOc\x00\x00\x00\x02"); var fanout: [256]u32 = @splat(0); for (entries) |e| for (e.id.bytes[0]..256) |b| { fanout[b] += 1; }; for (fanout) |n| try appendInt(gpa, &out, u32, n); for (entries) |e| try out.appendSlice(gpa, e.id.slice()); for (entries) |e| try appendInt(gpa, &out, u32, e.crc); var large: std.ArrayList(u64) = .empty; defer large.deinit(gpa); for (entries) |e| { if (e.offset < 0x8000_0000) { try appendInt(gpa, &out, u32, @intCast(e.offset)); } else { try appendInt(gpa, &out, u32, 0x8000_0000 | @as(u32, @intCast(large.items.len))); try large.append(gpa, e.offset); } } for (large.items) |o| try appendInt(gpa, &out, u64, o); try out.appendSlice(gpa, pack_checksum); const d = digest(format, out.items); try out.appendSlice(gpa, d[0..format.byteLength()]); return out.toOwnedSlice(gpa);}
fn appendInt(gpa: Allocator, out: *std.ArrayList(u8), comptime T: type, v: T) !void { var buf: [@sizeOf(T)]u8 = undefined; std.mem.writeInt(T, &buf, v, .big); try out.appendSlice(gpa, &buf);}
/// A version 2 index with one made-up object per entry of `raw_offsets`,/// whose 4-byte offset entries are exactly those (so a large one is/// `0x80000000 | k`), and whose large-offset table is `large`: for testing/// offsets past 2 GiB without a pack that size.pub fn craftIndex(gpa: Allocator, format: Format, raw_offsets: []const u32, large: []const u64) ![]u8 { std.debug.assert(raw_offsets.len < 256); var out: std.ArrayList(u8) = .empty; errdefer out.deinit(gpa); try out.appendSlice(gpa, "\xfftOc\x00\x00\x00\x02"); for (0..256) |b| try appendInt(gpa, &out, u32, @intCast(@min(b + 1, raw_offsets.len))); for (0..raw_offsets.len) |i| { var id: [object.max_byte_length]u8 = @splat(0x5a); id[0] = @intCast(i); try out.appendSlice(gpa, id[0..format.byteLength()]); } for (0..raw_offsets.len) |i| try appendInt(gpa, &out, u32, @intCast(0x1234 + i)); for (raw_offsets) |o| try appendInt(gpa, &out, u32, o); for (large) |o| try appendInt(gpa, &out, u64, o); try out.appendNTimes(gpa, 0, format.byteLength()); const d = digest(format, out.items); try out.appendSlice(gpa, d[0..format.byteLength()]); return out.toOwnedSlice(gpa);}
/// Writes a pack and its index into the repository's pack directory under/// the name git would give them, from the pack's checksum, and returns/// that name without its extension (`pack-<hex>`), which the caller frees.pub fn install(repo: *fixture.Repo, pack: []const u8, idx: []const u8) ![]u8 { const h = repo.object_format.byteLength(); const id: Id = .fromBytes(repo.object_format, pack[pack.len - h ..]); const name = try std.fmt.allocPrint(repo.gpa, "pack-{f}", .{id}); errdefer repo.gpa.free(name); try repo.tmp.dir.createDirPath(repo.io, ".git/objects/pack"); var buf: [256]u8 = undefined; try repo.tmp.dir.writeFile(repo.io, .{ .sub_path = try std.fmt.bufPrint(&buf, ".git/objects/pack/{s}.pack", .{name}), .data = pack }); try repo.tmp.dir.writeFile(repo.io, .{ .sub_path = try std.fmt.bufPrint(&buf, ".git/objects/pack/{s}.idx", .{name}), .data = idx }); return name;}
/// The names (`pack-<hex>`, without extension) of the packs in the/// repository's pack directory, sorted; the caller frees them with/// `freeNames`.pub fn names(repo: *fixture.Repo) ![][]u8 { var dir = try repo.tmp.dir.openDir(repo.io, ".git/objects/pack", .{ .iterate = true }); defer dir.close(repo.io); var list: std.ArrayList([]u8) = .empty; errdefer { for (list.items) |n| repo.gpa.free(n); list.deinit(repo.gpa); } var it = dir.iterate(); while (try it.next(repo.io)) |entry| { if (std.mem.endsWith(u8, entry.name, ".pack")) try list.append(repo.gpa, try repo.gpa.dupe(u8, entry.name[0 .. entry.name.len - 5])); } std.mem.sort([]u8, list.items, {}, struct { fn lt(_: void, a: []u8, b: []u8) bool { return std.mem.order(u8, a, b) == .lt; } }.lt); return list.toOwnedSlice(repo.gpa);}
/// Frees what `names` returned.pub fn freeNames(gpa: Allocator, list: [][]u8) void { for (list) |n| gpa.free(n); gpa.free(list);}
/// The bytes of the repository's one pack index, which the caller frees.pub fn readOnlyIndex(repo: *fixture.Repo) ![]u8 { const list = try names(repo); defer freeNames(repo.gpa, list); if (list.len != 1) return error.NotOnePack; return readPackFile(repo, list[0], "idx");}
/// The bytes of `.git/objects/pack/<name>.<ext>`, which the caller frees.pub fn readPackFile(repo: *fixture.Repo, name: []const u8, ext: []const u8) ![]u8 { var buf: [256]u8 = undefined; const path = try std.fmt.bufPrint(&buf, ".git/objects/pack/{s}.{s}", .{ name, ext }); return repo.tmp.dir.readFileAlloc(repo.io, path, repo.gpa, .unlimited);}
/// Replaces `.git/objects/pack/<name>.<ext>`, which git writes read-only,/// with `bytes`.pub fn writePackFile(repo: *fixture.Repo, name: []const u8, ext: []const u8, bytes: []const u8) !void { var buf: [256]u8 = undefined; const path = try std.fmt.bufPrint(&buf, ".git/objects/pack/{s}.{s}", .{ name, ext }); repo.tmp.dir.deleteFile(repo.io, path) catch |err| switch (err) { error.FileNotFound => {}, else => return err, }; try repo.tmp.dir.writeFile(repo.io, .{ .sub_path = path, .data = bytes });}
test "a pack written here is one git reads" { const gpa = std.testing.allocator; var repo = try fixture.Repo.init(gpa, std.testing.io); defer repo.deinit(); var w: PackWriter = try .init(gpa, repo.object_format); defer w.deinit(); const base = "hello, world\n"; const at = try w.whole(.blob, base); const delta = try deltaAppend(gpa, base.len, "and more\n"); defer gpa.free(delta); const result_id = object.hash(repo.object_format, .blob, base ++ "and more\n"); _ = try w.ofsDelta(at, delta, result_id); const out = try w.finish(); defer gpa.free(out.pack); defer gpa.free(out.idx); const name = try install(&repo, out.pack, out.idx); defer gpa.free(name); const hex = try std.fmt.allocPrint(gpa, "{f}", .{result_id}); defer gpa.free(hex); const got = try repo.output(&.{ "cat-file", "blob", hex }); defer gpa.free(got); try std.testing.expectEqualStrings(base ++ "and more\n", got); var path_buf: [256]u8 = undefined; const verified = try repo.output(&.{ "verify-pack", try std.fmt.bufPrint(&path_buf, ".git/objects/pack/{s}.idx", .{name}) }); gpa.free(verified);}