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.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie <jeff@ocjtech.us>// SPDX-License-Identifier: MIT
//! A multi-pack-index: one table finding the objects of many packs at//! once (`objects/pack/multi-pack-index`, gitformat-pack(5), in the//! chunk-based layout of gitformat-chunk(5)).//!//! It begins with `MIDX`, a version (1 or 2), the object format's number//! (1 for SHA-1, 2 for SHA-256), the number of chunks and of base files,//! and the number of packs; then a table of contents of 12-byte rows, a//! chunk ID and the offset where it starts, ending with a row whose ID is//! zero. The chunks read here are the ones finding an object://!//! - `PNAM`, the names of the packs' indexes, NUL-terminated;//! - `OIDF`, a 256-entry fanout table;//! - `OIDL`, the sorted object IDs;//! - `OOFF`, for each object the number of its pack and its offset there;//! - `LOFF`, optional, 8-byte offsets for those past 2 GiB.//!//! Others, such as the bitmap chunks, are skipped. An object in several//! packs is listed once, so a multi-pack-index is only a faster way of//! asking the packs it names; packs it does not name are still asked.//!//! `parse` checks what git checks when it loads one, found by corrupting//! one and asking `git cat-file`. git stops outright on a bad signature,//! an unknown version or a missing chunk, and otherwise says what was//! wrong and goes on without it; `isFatal` says which is which. Like git,//! it does not check the checksum at the end; `verifyChecksum` does.//!//! Nothing here does I/O.
const std = @import("std");
const object = @import("object.zig");const Format = object.Format;const Id = object.Id;const Diagnostics = @import("Diagnostics.zig");const PackIndex = @import("PackIndex.zig");
const MultiPackIndex = @This();
/// The whole file.bytes: []const u8,format: Format,/// 1 or 2.version: u8,/// How many packs it names.pack_count: u32,/// How many objects it finds.count: u32,names: []const u8,fanout_at: usize,ids_at: usize,offsets_at: usize,large_at: usize,large_count: usize,/// Whether the file had a large-offset chunk, which decides what the top/// bit of a 4-byte offset means: without one, offsets are plain 32-bit/// numbers.has_large: bool,
/// Why a multi-pack-index could not be read, each in git's words:////// - `MultiPackIndexTooSmall`: "multi-pack-index file … is too small"./// - `BadMultiPackIndexSignature`: "multi-pack-index signature 0x… does/// not match signature 0x4d494458"./// - `UnsupportedMultiPackIndexVersion`: "multi-pack-index version N not/// recognized"./// - `MultiPackIndexHashMismatch`: "multi-pack-index hash version N does/// not match version M": it was written for the other object format./// - `UnsupportedMultiPackIndexBase`: a file claiming base files, which/// gitformat-pack(5) says are always zero./// - `BadMultiPackIndexChunkOffsets`: "improper chunk offset(s) … and …":/// the table of contents points outside the file or backwards./// - `MissingMultiPackIndexChunk`: "multi-pack-index required … chunk/// missing or corrupted": one of the four required chunks is absent or/// the wrong size. The detail names it as git does: `pack-name`, `OID/// fanout`, `OID lookup` or `object offsets`./// - `CorruptMultiPackIndexPackNames`: fewer names than packs./// - `NonMonotonicMultiPackIndex`: a fanout entry smaller than the one/// before.pub const Error = error{ MultiPackIndexTooSmall, BadMultiPackIndexSignature, UnsupportedMultiPackIndexVersion, MultiPackIndexHashMismatch, UnsupportedMultiPackIndexBase, BadMultiPackIndexChunkOffsets, MissingMultiPackIndexChunk, CorruptMultiPackIndexPackNames, NonMonotonicMultiPackIndex,};
/// Whether git stops at this error rather than going on without the/// multi-pack-index.pub fn isFatal(err: Error) bool { return switch (err) { error.BadMultiPackIndexSignature, error.UnsupportedMultiPackIndexVersion, error.MissingMultiPackIndexChunk, => true, else => false, };}
const header_len = 12;
/// Reads the multi-pack-index `bytes` holds for a repository of `format`./// `bytes` must outlive the result.pub fn parse(format: Format, bytes: []const u8, diag: ?*Diagnostics) Error!MultiPackIndex { const h = format.byteLength(); if (bytes.len < header_len + h) return error.MultiPackIndexTooSmall; if (!std.mem.eql(u8, bytes[0..4], "MIDX")) { if (diag) |d| d.setDetail("0x{x:0>8}", .{std.mem.readInt(u32, bytes[0..4], .big)}); return error.BadMultiPackIndexSignature; } const version = bytes[4]; if (version != 1 and version != 2) { if (diag) |d| d.setDetail("{d}", .{version}); return error.UnsupportedMultiPackIndexVersion; } const want_hash: u8 = switch (format) { .sha1 => 1, .sha256 => 2, }; if (bytes[5] != want_hash) { if (diag) |d| d.setDetail("{d} does not match version {d}", .{ bytes[5], want_hash }); return error.MultiPackIndexHashMismatch; } const chunk_count = bytes[6]; if (bytes[7] != 0) return error.UnsupportedMultiPackIndexBase; const pack_count = std.mem.readInt(u32, bytes[8..12], .big);
// The table of contents, and the chunks it finds. const end = bytes.len - h; const toc_end = header_len + (@as(usize, chunk_count) + 1) * 12; if (toc_end > end) return error.MultiPackIndexTooSmall; var pnam: ?[]const u8 = null; var oidf: ?[]const u8 = null; var oidl: ?[]const u8 = null; var ooff: ?[]const u8 = null; var loff: ?[]const u8 = null; for (0..chunk_count) |i| { const row = bytes[header_len + 12 * i ..][0..24]; const start = std.mem.readInt(u64, row[4..12], .big); const next = std.mem.readInt(u64, row[16..24], .big); if (start < toc_end or start > next or next > end) { if (diag) |d| d.setDetail("{x} and {x}", .{ start, next }); return error.BadMultiPackIndexChunkOffsets; } const chunk = bytes[@intCast(start)..@intCast(next)]; const which = row[0..4]; if (std.mem.eql(u8, which, "PNAM")) pnam = chunk; if (std.mem.eql(u8, which, "OIDF")) oidf = chunk; if (std.mem.eql(u8, which, "OIDL")) oidl = chunk; if (std.mem.eql(u8, which, "OOFF")) ooff = chunk; if (std.mem.eql(u8, which, "LOFF")) loff = chunk; }
const names = pnam orelse return missing(diag, "pack-name"); const fanout_chunk = oidf orelse return missing(diag, "OID fanout"); if (fanout_chunk.len != 256 * 4) return missing(diag, "OID fanout"); var previous: u32 = 0; for (0..256) |i| { const n = std.mem.readInt(u32, fanout_chunk[4 * i ..][0..4], .big); if (n < previous) return error.NonMonotonicMultiPackIndex; previous = n; } const count = previous; const ids = oidl orelse return missing(diag, "OID lookup"); if (ids.len != @as(u64, count) * h) return missing(diag, "OID lookup"); const offsets = ooff orelse return missing(diag, "object offsets"); if (offsets.len != @as(u64, count) * 8) return missing(diag, "object offsets"); const large = loff orelse bytes[0..0];
const m: MultiPackIndex = .{ .bytes = bytes, .format = format, .version = version, .pack_count = pack_count, .count = count, .names = names, .fanout_at = @intFromPtr(fanout_chunk.ptr) - @intFromPtr(bytes.ptr), .ids_at = @intFromPtr(ids.ptr) - @intFromPtr(bytes.ptr), .offsets_at = @intFromPtr(offsets.ptr) - @intFromPtr(bytes.ptr), .large_at = @intFromPtr(large.ptr) - @intFromPtr(bytes.ptr), .large_count = if (loff != null) large.len / 8 else 0, .has_large = loff != null, }; var it = m.packNames(); var n: u32 = 0; while (n < pack_count) : (n += 1) _ = it.next() orelse return error.CorruptMultiPackIndexPackNames; return m;}
fn missing(diag: ?*Diagnostics, which: []const u8) Error { if (diag) |d| d.setDetail("{s}", .{which}); return error.MissingMultiPackIndexChunk;}
/// Steps through the names of the packs' indexes, in the order their/// numbers refer to.pub const NameIterator = struct { rest: []const u8,
/// The next name, without its NUL, or null after the last. pub fn next(it: *NameIterator) ?[]const u8 { const nul = std.mem.findScalar(u8, it.rest, 0) orelse return null; if (nul == 0) return null; const name = it.rest[0..nul]; it.rest = it.rest[nul + 1 ..]; return name; }};
/// The names of the packs' indexes (`pack-<hex>.idx`).pub fn packNames(m: *const MultiPackIndex) NameIterator { return .{ .rest = m.names };}
/// The object ID of the `i`th object, in object ID order.pub fn idAt(m: *const MultiPackIndex, i: u32) Id { const h = m.format.byteLength(); return .fromBytes(m.format, m.bytes[m.ids_at + @as(usize, i) * h ..][0..h]);}
/// The position of the object `id`, if one of the packs holds it.pub fn find(m: *const MultiPackIndex, id: Id) ?u32 { const h = m.format.byteLength(); const first = id.bytes[0]; var lo: usize = if (first == 0) 0 else m.fanoutAt(first - 1); var hi: usize = m.fanoutAt(first); const want = id.slice(); while (lo < hi) { const mid = lo + (hi - lo) / 2; switch (std.mem.order(u8, m.bytes[m.ids_at + mid * h ..][0..h], 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(m: *const MultiPackIndex, b: u8) u32 { return m.fanoutAt(b);}
fn fanoutAt(m: *const MultiPackIndex, b: u8) u32 { return std.mem.readInt(u32, m.bytes[m.fanout_at + 4 * @as(usize, b) ..][0..4], .big);}
/// Where an object is: which pack, by its number in `packNames` order, and/// where in it.pub const Location = struct { pack: u32, offset: u64 };
/// Where the `i`th object is. A pack number past the last pack is/// `BadMultiPackIndexEntry`, and an offset past the end of the/// large-offset chunk `BadLargeOffset`.pub fn locationAt(m: *const MultiPackIndex, i: u32, diag: ?*Diagnostics) error{ BadMultiPackIndexEntry, BadLargeOffset }!Location { const row = m.bytes[m.offsets_at + 8 * @as(usize, i) ..][0..8]; const pack = std.mem.readInt(u32, row[0..4], .big); if (pack >= m.pack_count) { if (diag) |d| d.setDetail("pack {d} of {d}", .{ pack, m.pack_count }); return error.BadMultiPackIndexEntry; } const raw = std.mem.readInt(u32, row[4..8], .big); if (!m.has_large or raw & 0x8000_0000 == 0) return .{ .pack = pack, .offset = raw }; const k = raw & 0x7fff_ffff; if (k >= m.large_count) { if (diag) |d| d.setDetail("large offset {d} of {d}", .{ k, m.large_count }); return error.BadLargeOffset; } return .{ .pack = pack, .offset = std.mem.readInt(u64, m.bytes[m.large_at + 8 * k ..][0..8], .big) };}
/// The checksum the file ends with, which is also the name of a layer of/// an incremental chain.pub fn checksum(m: *const MultiPackIndex) []const u8 { return m.bytes[m.bytes.len - m.format.byteLength() ..];}
/// Whether the checksum the file ends with is the hash of the rest, which/// `git multi-pack-index verify` checks and reading an object does not.pub fn verifyChecksum(m: *const MultiPackIndex) bool { return PackIndex.checksumMatches(m.format, m.bytes);}
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 multi-pack-index git wrote finds every object of every pack it names" { const gpa = testing.allocator; var repo = try fixture.Repo.init(gpa, testing.io); defer repo.deinit(); for (0..4) |i| { var buf: [32]u8 = undefined; try repo.commitFile("f", try std.fmt.bufPrint(&buf, "v{d}\n", .{i}), "c"); try repo.git(&.{ "repack", "-dq" }); } try repo.git(&.{ "multi-pack-index", "write" }); const bytes = try repo.tmp.dir.readFileAlloc(repo.io, ".git/objects/pack/multi-pack-index", gpa, .unlimited); defer gpa.free(bytes); const m = try parse(repo.object_format, bytes, null); try testing.expect(m.verifyChecksum()); try testing.expectEqual(4, m.pack_count);
// Every pack's index agrees about where each of its objects is. var names: std.ArrayList([]const u8) = .empty; defer names.deinit(gpa); var it = m.packNames(); while (it.next()) |n| try names.append(gpa, n); try testing.expectEqual(4, names.items.len); var seen: u32 = 0; for (names.items, 0..) |name, pack_number| { const idx_bytes = try packs.readPackFile(&repo, name[0 .. name.len - 4], "idx"); defer gpa.free(idx_bytes); const idx = try PackIndex.parse(repo.object_format, idx_bytes, null); var i: u32 = 0; while (i < idx.count) : (i += 1) { const pos = m.find(idx.idAt(i)) orelse return error.TestUnexpectedResult; const loc = try m.locationAt(pos, null); if (loc.pack != pack_number) continue; seen += 1; try testing.expectEqual(try idx.offsetAt(i, null), loc.offset); } } try testing.expectEqual(m.count, seen);}
test "a multi-pack-index is refused as git refuses it" { const gpa = testing.allocator; const good = @embedFile("fuzz/midx"); _ = try parse(.sha1, good, null); var diag: Diagnostics = .{}; try testing.expectError(error.MultiPackIndexHashMismatch, parse(.sha256, good, &diag)); try testing.expectEqualStrings("1 does not match version 2", diag.detail()); try testing.expectError(error.MultiPackIndexTooSmall, parse(.sha1, good[0..10], null)); try testing.expectError(error.BadMultiPackIndexChunkOffsets, parse(.sha1, good[0..1000], null)); const bad = try gpa.dupe(u8, good); defer gpa.free(bad); bad[0] = 'L'; try testing.expectError(error.BadMultiPackIndexSignature, parse(.sha1, bad, &diag)); try testing.expectEqualStrings("0x4c494458", diag.detail()); bad[0] = 'M'; bad[4] = 6; try testing.expectError(error.UnsupportedMultiPackIndexVersion, parse(.sha1, bad, null)); bad[4] = 1; bad[12] = 'Q'; // PNAM is the first chunk try testing.expectError(error.MissingMultiPackIndexChunk, parse(.sha1, bad, &diag)); try testing.expectEqualStrings("pack-name", diag.detail()); try testing.expect(isFatal(error.MissingMultiPackIndexChunk)); try testing.expect(!isFatal(error.MultiPackIndexTooSmall));}
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 m = parse(format, bytes, null) catch continue; var it = m.packNames(); while (it.next()) |_| {} var i: u32 = 0; while (i < m.count) : (i += 1) { _ = m.find(m.idAt(i)); _ = m.locationAt(i, null) catch {}; } _ = m.verifyChecksum(); }}
test "fuzz: multi-pack-indexes" { try fuzz_input.fuzz({}, fuzzOne, .{ .corpus = &.{ @embedFile("fuzz/midx"), @embedFile("fuzz/midx-sha256"), } });}