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.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie <jeff@ocjtech.us>// SPDX-License-Identifier: MIT
//! A pack index: the `.idx` file beside a pack, which finds each of the//! pack's objects by object ID (gitformat-pack(5)). Both versions are//! read://!//! - **Version 1**, which `git index-pack --index-version=1` and//! `pack.indexVersion=1` still write and git still reads: a 256-entry//! fanout table, then one entry per object of a 4-byte offset and the//! object ID.//! - **Version 2**, the default: the bytes `\377tOc`, the version, the//! fanout table, then the sorted object IDs, a CRC-32 per object, a//! 4-byte offset per object whose top bit, when set, makes the rest an//! index into a table of 8-byte offsets for packs past 2 GiB.//!//! Both end with a copy of the pack's checksum and the index's own//! checksum, each as long as an object ID.//!//! `parse` checks what git checks when it opens an index, found by//! corrupting indexes and asking `git cat-file` about their objects: the//! size, the version, and that the fanout table never decreases. Like git,//! it does not check the index's checksum or the CRCs; `verifyChecksum`//! does the first for a caller who wants it. The object IDs are assumed//! sorted, as git assumes them: an index whose IDs are out of order simply//! fails to find some of them.//!//! Nothing here does I/O: the index is bytes the caller has, typically//! memory-mapped.
const std = @import("std");
const object = @import("object.zig");const Format = object.Format;const Id = object.Id;const Diagnostics = @import("Diagnostics.zig");
const PackIndex = @This();
/// The whole file.bytes: []const u8,/// The object format of the IDs it holds.format: Format,/// 1 or 2.version: u8,/// How many objects the pack holds.count: u32,/// Where each table starts.fanout_at: usize,names_at: usize,crcs_at: usize,offsets_at: usize,large_offsets_at: usize,/// How many 8-byte offsets the large-offset table has room for.large_count: usize,
/// The bytes a version 2 index begins with, which as a version 1 fanout/// entry would be absurd.pub const magic = "\xfftOc";
/// Why an index could not be read, each in git's words:////// - `PackIndexTooSmall`: "index file … is too small"./// - `UnsupportedPackIndexVersion`: "index file … is version N and is not/// supported by this binary"; the detail is the version./// - `NonMonotonicPackIndex`: "non-monotonic index …": a fanout entry/// smaller than the one before./// - `WrongPackIndexSize`: "wrong index v1 file size in …", or v2: the/// size does not fit the number of objects the fanout table says. The/// detail is the version.pub const Error = error{ PackIndexTooSmall, UnsupportedPackIndexVersion, NonMonotonicPackIndex, WrongPackIndexSize,};
/// Reads the pack index `bytes` holds, checking it as git does when it/// opens one. `bytes` must outlive the result.pub fn parse(format: Format, bytes: []const u8, diag: ?*Diagnostics) Error!PackIndex { const h = format.byteLength(); const version: u8 = if (bytes.len >= 8 and std.mem.eql(u8, bytes[0..4], magic)) v: { const v = std.mem.readInt(u32, bytes[4..8], .big); if (v != 2) { if (diag) |d| d.setDetail("{d}", .{v}); return error.UnsupportedPackIndexVersion; } break :v 2; } else 1; const fanout_at: usize = if (version == 2) 8 else 0; if (bytes.len < fanout_at + 256 * 4 + 2 * h) return error.PackIndexTooSmall; var previous: u32 = 0; for (0..256) |i| { const n = std.mem.readInt(u32, bytes[fanout_at + 4 * i ..][0..4], .big); if (n < previous) return error.NonMonotonicPackIndex; previous = n; } const count = previous; const n: u64 = count; var idx: PackIndex = .{ .bytes = bytes, .format = format, .version = version, .count = count, .fanout_at = fanout_at, .names_at = undefined, .crcs_at = 0, .offsets_at = undefined, .large_offsets_at = 0, .large_count = 0, }; if (version == 1) { const want = 256 * 4 + n * (4 + h) + 2 * h; if (bytes.len != want) return wrongSize(1, diag); idx.offsets_at = 256 * 4; idx.names_at = 256 * 4 + 4; } else { const min = 8 + 256 * 4 + n * (h + 4 + 4) + 2 * h; // Room for a large offset for every object but the first, which // is at offset 12 in any pack. const max = min + (if (n > 0) n - 1 else 0) * 8; if (bytes.len < min or bytes.len > max) return wrongSize(2, diag); idx.names_at = 8 + 256 * 4; idx.crcs_at = idx.names_at + count * h; idx.offsets_at = idx.crcs_at + count * 4; idx.large_offsets_at = idx.offsets_at + count * 4; idx.large_count = (bytes.len - min) / 8; } return idx;}
fn wrongSize(version: u8, diag: ?*Diagnostics) Error { if (diag) |d| d.setDetail("{d}", .{version}); return error.WrongPackIndexSize;}
/// The object ID of the `i`th object, in object ID order.pub fn idAt(idx: *const PackIndex, i: u32) Id { std.debug.assert(i < idx.count); const h = idx.format.byteLength(); const at = if (idx.version == 1) idx.names_at + @as(usize, i) * (4 + h) else idx.names_at + @as(usize, i) * h; return .fromBytes(idx.format, idx.bytes[at..][0..h]);}
fn rawIdAt(idx: *const PackIndex, i: usize) []const u8 { const h = idx.format.byteLength(); const at = if (idx.version == 1) idx.names_at + i * (4 + h) else idx.names_at + i * h; return idx.bytes[at..][0..h];}
/// The position of the object `id`, if the pack holds it: a binary search/// within the IDs the fanout table says begin with its first byte.pub fn find(idx: *const PackIndex, id: Id) ?u32 { std.debug.assert(id.object_format == idx.format); const first = id.bytes[0]; var lo: usize = if (first == 0) 0 else idx.fanout(first - 1); var hi: usize = idx.fanout(first); const want = id.slice(); while (lo < hi) { const mid = lo + (hi - lo) / 2; switch (std.mem.order(u8, idx.rawIdAt(mid), want)) { .eq => return @intCast(mid), .lt => lo = mid + 1, .gt => hi = mid, } } return null;}
/// How many objects have IDs whose first byte is at most `b`.pub fn fanout(idx: *const PackIndex, b: u8) u32 { return std.mem.readInt(u32, idx.bytes[idx.fanout_at + 4 * @as(usize, b) ..][0..4], .big);}
/// The `i`th object's 4-byte offset entry as stored: an offset, or, in a/// version 2 index with its top bit set, an index into the large-offset/// table.pub fn rawOffsetAt(idx: *const PackIndex, i: u32) u32 { std.debug.assert(i < idx.count); const at = if (idx.version == 1) idx.offsets_at + @as(usize, i) * (4 + idx.format.byteLength()) else idx.offsets_at + @as(usize, i) * 4; return std.mem.readInt(u32, idx.bytes[at..][0..4], .big);}
/// Where in the pack the `i`th object's entry begins. A version 2 entry/// pointing past the end of the large-offset table is/// `BadLargeOffset`; the detail is the index it gave.pub fn offsetAt(idx: *const PackIndex, i: u32, diag: ?*Diagnostics) error{BadLargeOffset}!u64 { const raw = idx.rawOffsetAt(i); if (idx.version == 1 or raw & 0x8000_0000 == 0) return raw; const large = raw & 0x7fff_ffff; return idx.largeOffset(large) orelse { if (diag) |d| d.setDetail("large offset {d} of {d}", .{ large, idx.large_count }); return error.BadLargeOffset; };}
/// The `k`th entry of the large-offset table, or null if there is none.pub fn largeOffset(idx: *const PackIndex, k: usize) ?u64 { if (k >= idx.large_count) return null; return std.mem.readInt(u64, idx.bytes[idx.large_offsets_at + 8 * k ..][0..8], .big);}
/// The CRC-32 of the `i`th object's entry as stored in the pack, which only/// a version 2 index records.pub fn crcAt(idx: *const PackIndex, i: u32) ?u32 { std.debug.assert(i < idx.count); if (idx.version == 1) return null; return std.mem.readInt(u32, idx.bytes[idx.crcs_at + 4 * @as(usize, i) ..][0..4], .big);}
/// The copy of the pack's checksum the index ends with. git reads it from/// the end of the file, whatever comes before.pub fn packChecksum(idx: *const PackIndex) []const u8 { const h = idx.format.byteLength(); return idx.bytes[idx.bytes.len - 2 * h ..][0..h];}
/// The index's own checksum, its last bytes.pub fn checksum(idx: *const PackIndex) []const u8 { const h = idx.format.byteLength(); return idx.bytes[idx.bytes.len - h ..];}
/// Whether the index's checksum is the hash of everything before it, as/// `git verify-pack` checks and reading an object does not.pub fn verifyChecksum(idx: *const PackIndex) bool { return checksumMatches(idx.format, idx.bytes);}
/// Whether the last object-ID-sized bytes of `bytes` are the hash of the/// rest, as packs, pack indexes and multi-pack-indexes all end.pub fn checksumMatches(format: Format, bytes: []const u8) bool { const h = format.byteLength(); if (bytes.len < h) return false; var digest: [object.max_byte_length]u8 = undefined; switch (format) { .sha1 => std.crypto.hash.Sha1.hash(bytes[0 .. bytes.len - h], digest[0..20], .{}), .sha256 => std.crypto.hash.sha2.Sha256.hash(bytes[0 .. bytes.len - h], digest[0..32], .{}), } return std.mem.eql(u8, digest[0..h], bytes[bytes.len - h ..]);}
const testing = std.testing;const fixture = @import("testing/fixture.zig");const fuzz_input = @import("testing/fuzz.zig");const packs = @import("testing/packs.zig");
test "a pack index git wrote finds every object git says the pack holds" { const gpa = testing.allocator; var repo = try fixture.Repo.init(gpa, testing.io); defer repo.deinit(); for (0..12) |i| { var buf: [64]u8 = undefined; try repo.commitFile("f", try std.fmt.bufPrint(&buf, "version {d}\n", .{i}), "c"); } for ([_][]const u8{ "2", "1" }) |version| { var arg_buf: [32]u8 = undefined; try repo.git(&.{ "-c", try std.fmt.bufPrint(&arg_buf, "pack.indexVersion={s}", .{version}), "repack", "-adq" }); const bytes = try packs.readOnlyIndex(&repo); defer gpa.free(bytes); const idx = try parse(repo.object_format, bytes, null); try testing.expectEqual(version[0] - '0', idx.version);
const listing = try repo.outputWithInput(&.{"show-index"}, bytes); defer gpa.free(listing); var lines = std.mem.splitScalar(u8, std.mem.trimEnd(u8, listing, "\n"), '\n'); var i: u32 = 0; while (lines.next()) |line| : (i += 1) { var fields = std.mem.splitScalar(u8, line, ' '); const offset = try std.fmt.parseInt(u64, fields.next().?, 10); const id = try Id.parseHex(repo.object_format, fields.next().?); try testing.expect(Id.eql(id, idx.idAt(i))); try testing.expectEqual(i, idx.find(id).?); try testing.expectEqual(offset, try idx.offsetAt(i, null)); if (fields.next()) |crc| { try testing.expectEqual(try std.fmt.parseInt(u32, crc[1 .. crc.len - 1], 16), idx.crcAt(i).?); } else try testing.expectEqual(null, idx.crcAt(i)); } try testing.expectEqual(idx.count, i); try testing.expect(idx.verifyChecksum()); var missing = idx.idAt(0); missing.bytes[missing.object_format.byteLength() - 1] ^= 1; if (idx.find(missing)) |_| return error.TestUnexpectedResult; }}
test "large offsets come from the 8-byte table, and a bad one is an error" { const gpa = testing.allocator; for ([_]Format{ .sha1, .sha256 }) |format| { const bytes = try packs.craftIndex(gpa, format, &.{ 12, 0x8000_0000, 0x8000_0001, 0x8000_0005 }, &.{ 0x1_0000_0000, 0x7_ffff_ffff }); defer gpa.free(bytes); const idx = try parse(format, bytes, null); try testing.expectEqual(4, idx.count); try testing.expectEqual(2, idx.large_count); try testing.expectEqual(12, try idx.offsetAt(0, null)); try testing.expectEqual(0x1_0000_0000, try idx.offsetAt(1, null)); try testing.expectEqual(0x7_ffff_ffff, try idx.offsetAt(2, null)); var diag: Diagnostics = .{}; try testing.expectError(error.BadLargeOffset, idx.offsetAt(3, &diag)); try testing.expectEqualStrings("large offset 5 of 2", diag.detail()); try testing.expect(idx.verifyChecksum()); }}
test "a pack index is refused as git refuses it" { const gpa = testing.allocator; const format: Format = .sha1; const good = try packs.craftIndex(gpa, format, &.{ 12, 40, 80 }, &.{}); defer gpa.free(good); _ = try parse(format, good, null); try testing.expectError(error.PackIndexTooSmall, parse(format, good[0..1000], null)); try testing.expectError(error.WrongPackIndexSize, parse(format, good[0 .. good.len - 1], null)); // Two large offsets' worth of room is allowed for three objects, and // no more. const longer = try std.mem.concat(gpa, u8, &.{ good, &@as([17]u8, @splat(0)) }); defer gpa.free(longer); _ = try parse(format, longer[0 .. good.len + 16], null); try testing.expectError(error.WrongPackIndexSize, parse(format, longer, null)); const bad = try gpa.dupe(u8, good); defer gpa.free(bad); bad[7] = 3; var diag: Diagnostics = .{}; try testing.expectError(error.UnsupportedPackIndexVersion, parse(format, bad, &diag)); try testing.expectEqualStrings("3", diag.detail()); bad[7] = 2; bad[0] ^= 1; // no longer the magic, so a version 1 fanout that decreases try testing.expectError(error.NonMonotonicPackIndex, parse(format, bad, null));}
fn fuzzOne(_: void, smith: *testing.Smith) anyerror!void { var buffer: [4096]u8 = undefined; const bytes = fuzz_input.bytes(smith, &buffer); for ([_]Format{ .sha1, .sha256 }) |format| { const idx = parse(format, bytes, null) catch continue; var i: u32 = 0; while (i < idx.count) : (i += 1) { const id = idx.idAt(i); _ = idx.find(id); _ = idx.offsetAt(i, null) catch {}; _ = idx.crcAt(i); } _ = idx.verifyChecksum(); }}
test "fuzz: pack indexes" { try fuzz_input.fuzz({}, fuzzOne, .{ .corpus = &.{ @embedFile("fuzz/pack-idx"), @embedFile("fuzz/pack-idx-v1"), @embedFile("fuzz/pack-idx-sha256"), } });}