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.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie <jeff@ocjtech.us>// SPDX-License-Identifier: MIT
//! One index file read from its bytes, with no I/O: the header, the//! index entries, the extensions as signatures and contents, and the//! trailing checksum. What the extensions mean, and how a split index's//! two files make one list of entries, is `Index`'s business.//!//! The format is gitformat-index(5)'s. What git does where that document//! is silent was found by writing malformed index files and asking//! `git ls-files`://!//! - A file shorter than its header and checksum is "index file smaller//! than expected"; a wrong signature is "bad signature 0x…" and a//! version other than 2, 3 and 4 "bad index version N".//! - The checksum is not checked when git reads an index. `checksum`//! says what it is, and `verifyChecksum` checks it for a caller who//! wants that; `index.skipHash` writes all zeros, which mean "not//! computed".//! - An entry with the extended flag set has the extended flags after it//! whatever the version; extended flags with a bit set other than//! skip-worktree and intent-to-add are "unknown index entry format//! 0x…", the flags shown shifted into the upper half.//! - In version 4 the first entry's prefix length is ignored, since//! there is no earlier path to take a prefix of; git writes the whole//! length of the previous path at the start of each block of the index//! entry offset table, so that each block can be read alone. A later//! entry asking for more of the previous path than it has is//! "malformed name field in the index, near path '<previous>'".//! - Extensions are read while at least eight bytes remain before the//! checksum. One whose signature begins with an upper-case letter and//! which git does not know is passed over ("ignoring XXXX extension");//! any other unknown one is "index uses XXXX extension, which we do not//! understand".//!//! Where git reads past the end of what it was given — an entry or an//! extension running into the checksum, a path length that disagrees with//! the path — it shows whatever it found there, or crashes. This refuses//! the file instead (`MalformedIndex`), saying where.
const std = @import("std");const builtin = @import("builtin");const Allocator = std.mem.Allocator;
const Diagnostics = @import("../Diagnostics.zig");const object = @import("../object.zig");const Format = object.Format;const Id = object.Id;
/// "DIRC", for "dircache".pub const signature = "DIRC";/// The size of the header: signature, version and entry count.pub const header_len = 12;
/// When a file last changed, as `stat(2)` gave it, cut to 32 bits.pub const Timestamp = struct { seconds: u32, nanoseconds: u32,};
/// One path in the index.pub const Entry = struct { /// When the file's metadata last changed. ctime: Timestamp, /// When the file's contents last changed. mtime: Timestamp, dev: u32, ino: u32, /// The mode as recorded, which git shows in octal whatever it is. mode: u32, uid: u32, gid: u32, /// The file's size on disk, cut to 32 bits. size: u32, /// The object the entry names. id: Id, /// The 16-bit flags field: assume-valid, extended, the stage and the /// length of the path. flags: u16, /// The extended flags (versions 3 and 4, when `extended_flag` is set): /// skip-worktree and intent-to-add; zero otherwise. extended_flags: u16, /// The path from the top of the working tree; a sparse directory's /// ends in `/`. In a split index's main file, a replacement may have /// an empty path, standing for the one it replaces. path: []const u8, /// Where a split index's entry came from: the shared index, the main /// file as a replacement for one of the shared index's, or the main /// file as an addition (or an index that is not split). origin: Origin = .own, /// Whether the index's fsmonitor cache vouches for the entry: git /// takes the working tree file to be unchanged when `core.fsmonitor` /// is set and the monitor agrees. fsmonitor_valid: bool = false,
/// The flag git calls assume-valid, which `git update-index /// --assume-unchanged` sets. pub const assume_valid_flag: u16 = 0x8000; /// Set when extended flags follow. pub const extended_flag: u16 = 0x4000; /// The stage's bits within `flags`. pub const stage_mask: u16 = 0x3000; /// The path length's bits within `flags`; this value when the path is /// that long or longer. pub const name_mask: u16 = 0x0fff; /// The extended flag sparse checkout sets for a path outside it. pub const skip_worktree_flag: u16 = 0x4000; /// The extended flag `git add -N` sets. pub const intent_to_add_flag: u16 = 0x2000; /// The extended flags git knows. pub const known_extended_flags: u16 = skip_worktree_flag | intent_to_add_flag;
/// Which version of a conflicted path this is: 0 when it is not /// conflicted, 1 to 3 for the common ancestor's, ours and theirs. pub fn stage(e: *const Entry) u2 { return @intCast((e.flags & stage_mask) >> 12); }
/// Whether git is to take the working tree file as unchanged. pub fn assumeValid(e: *const Entry) bool { return e.flags & assume_valid_flag != 0; }
/// Whether the path is outside a sparse checkout. pub fn skipWorktree(e: *const Entry) bool { return e.extended_flags & skip_worktree_flag != 0; }
/// Whether the path was added with `git add -N`, its contents not yet. pub fn intentToAdd(e: *const Entry) bool { return e.extended_flags & intent_to_add_flag != 0; }
/// Whether this is a sparse directory: a directory outside a sparse /// checkout, standing for every path in its tree. pub fn isSparseDirectory(e: *const Entry) bool { return e.mode == 0o040000 and e.skipWorktree() and e.path.len != 0 and e.path[e.path.len - 1] == '/'; }
/// Orders entries as the index keeps them: by path, compared as /// unsigned bytes, then by stage. pub fn lessThan(_: void, a: Entry, b: Entry) bool { return switch (std.mem.order(u8, a.path, b.path)) { .lt => true, .gt => false, .eq => a.stage() < b.stage(), }; }};
/// Where an entry of a split index came from.pub const Origin = enum { /// Its own file: an index that is not split, or an entry a split /// index's main file adds. own, /// The shared index, unchanged. shared, /// The main file, replacing the shared index's entry for its path. /// git marks these when it shows `--debug` flags. replacement,};
/// One extension: its signature and its contents.pub const Extension = struct { signature: [4]u8, data: []const u8, /// Where its signature is, from the start of the file. offset: usize,};
/// The signatures of the extensions git knows.pub const known_extensions = [_]*const [4]u8{ "TREE", "REUC", "link", "UNTR", "FSMN", "EOIE", "IEOT", "sdir" };
/// Whether git knows the extension `sig`.pub fn isKnownExtension(sig: [4]u8) bool { for (known_extensions) |k| if (std.mem.eql(u8, k, &sig)) return true; return false;}
/// One index file.pub const File = struct { version: u32, entries: []Entry, /// Where each entry begins, from the start of the file, for checking /// an index entry offset table. entry_offsets: []u32, /// Where the entries end and the extensions begin. entries_end: usize, /// Every extension, in the order they appear. extensions: []Extension, /// The optional extensions git does not know, which it passes over /// with a word; also in `extensions`. ignored: [][4]u8, /// The trailing checksum. checksum: []const u8,
/// The extension with signature `sig`, if there is one; the last if /// there are several. pub fn extension(f: *const File, sig: *const [4]u8) ?Extension { var found: ?Extension = null; for (f.extensions) |e| { if (std.mem.eql(u8, &e.signature, sig)) found = e; } return found; }};
/// Why an index file could not be read. Those git has words for:////// - `IndexTooSmall`: "index file smaller than expected"./// - `BadIndexSignature`: "bad signature 0x%08x"; the detail is the/// signature in hexadecimal, read in the machine's byte order as git/// reads it./// - `UnsupportedIndexVersion`: "bad index version N"; the detail is N./// - `UnknownEntryFormat`: "unknown index entry format 0x%08x"; the detail/// is the value in hexadecimal./// - `MalformedEntryName`: "malformed name field in the index, near path/// '…'"; the detail is the path./// - `UnknownRequiredExtension`: "index uses XXXX extension, which we do/// not understand"; the detail is the four bytes of the signature.////// And `MalformedIndex`, for what git does not check: the detail says/// what, and the diagnostic's offset where.pub const ParseError = error{ IndexTooSmall, BadIndexSignature, UnsupportedIndexVersion, UnknownEntryFormat, MalformedEntryName, UnknownRequiredExtension, MalformedIndex,} || Allocator.Error;
/// The fixed part of an entry before its path, in `format`: ten 32-bit/// stat fields, the object ID and the flags.pub fn fixedEntryLen(format: Format) usize { return 40 + format.byteLength() + 2;}
/// Reads the index file `bytes`, whose object IDs are in `format`. Entry/// paths point into `bytes` where they can, so it must outlive what is/// returned; everything else is allocated with `arena`, which the caller/// frees all at once.pub fn parse(arena: Allocator, format: Format, bytes: []const u8, diag: ?*Diagnostics) ParseError!File { const hash_len = format.byteLength(); if (bytes.len < header_len + hash_len) return error.IndexTooSmall; if (!std.mem.eql(u8, bytes[0..4], signature)) { // git shows the four bytes as a number in the machine's own byte // order. if (diag) |d| d.setDetail("0x{x:0>8}", .{std.mem.readInt(u32, bytes[0..4], builtin.cpu.arch.endian())}); return error.BadIndexSignature; } const version = std.mem.readInt(u32, bytes[4..8], .big); if (version < 2 or version > 4) { if (diag) |d| d.setDetail("{d}", .{version}); return error.UnsupportedIndexVersion; } const count = std.mem.readInt(u32, bytes[8..12], .big); const end = bytes.len - hash_len; const fixed = fixedEntryLen(format); // Every entry takes at least its fixed part and a byte of path, or // the NUL that ends it, so a count that could not fit is refused // before anything is allocated for it. if (@as(u64, count) * (fixed + 1) > end - header_len) return malformed(diag, header_len, "{d} entries cannot fit in {d} bytes", .{ count, end - header_len });
const entries = try arena.alloc(Entry, count); const offsets = try arena.alloc(u32, count); var pos: usize = header_len; var previous: []const u8 = ""; var name_buffer: std.ArrayList(u8) = .empty; for (entries, offsets, 0..) |*e, *offset, i| { offset.* = @intCast(pos); if (end - pos < fixed) return malformed(diag, pos, "entry {d} runs past the end", .{i}); const b = bytes[pos..]; e.* = .{ .ctime = .{ .seconds = be32(b[0..]), .nanoseconds = be32(b[4..]) }, .mtime = .{ .seconds = be32(b[8..]), .nanoseconds = be32(b[12..]) }, .dev = be32(b[16..]), .ino = be32(b[20..]), .mode = be32(b[24..]), .uid = be32(b[28..]), .gid = be32(b[32..]), .size = be32(b[36..]), .id = .fromBytes(format, b[40..][0..hash_len]), .flags = std.mem.readInt(u16, b[40 + hash_len ..][0..2], .big), .extended_flags = 0, .path = "", }; var p = pos + fixed; if (e.flags & Entry.extended_flag != 0) { if (end - p < 2) return malformed(diag, pos, "entry {d} runs past the end", .{i}); e.extended_flags = std.mem.readInt(u16, bytes[p..][0..2], .big); p += 2; if (e.extended_flags & ~Entry.known_extended_flags != 0) { if (diag) |d| d.setDetail("0x{x:0>8}", .{@as(u32, e.extended_flags) << 16}); return error.UnknownEntryFormat; } } const name_field = e.flags & Entry.name_mask; if (version == 4) { const strip_start = p; const strip = readVarint(bytes[0..end], &p) orelse return malformed(diag, strip_start, "entry {d}'s prefix length runs past the end", .{i}); const nul = std.mem.findScalar(u8, bytes[p..end], 0) orelse return malformed(diag, p, "entry {d}'s path runs past the end", .{i}); const suffix = bytes[p..][0..nul]; const keep = if (i == 0) 0 else blk: { if (strip > previous.len) { if (diag) |d| d.setDetail("{s}", .{previous}); return error.MalformedEntryName; } break :blk previous.len - @as(usize, @intCast(strip)); }; name_buffer.clearRetainingCapacity(); try name_buffer.appendSlice(arena, previous[0..keep]); try name_buffer.appendSlice(arena, suffix); const path = try arena.dupe(u8, name_buffer.items); if (!nameFits(name_field, path.len)) { if (diag) |d| d.setDetail("{s}", .{path}); return error.MalformedEntryName; } e.path = path; previous = path; pos = p + nul + 1; } else { const nul = std.mem.findScalar(u8, bytes[p..end], 0) orelse return malformed(diag, p, "entry {d}'s path runs past the end", .{i}); if (!nameFits(name_field, nul)) return malformed(diag, pos, "entry {d}'s path is {d} bytes, where its flags say {d}", .{ i, nul, name_field }); e.path = bytes[p..][0..nul]; // One to eight NULs, to a multiple of eight bytes. const len = (p - pos + nul + 8) & ~@as(usize, 7); if (end - pos < len) return malformed(diag, pos, "entry {d} runs past the end", .{i}); pos += len; } } const entries_end = pos;
var extensions: std.ArrayList(Extension) = .empty; var ignored: std.ArrayList([4]u8) = .empty; while (end - pos >= 8) { const sig = bytes[pos..][0..4].*; const size = be32(bytes[pos + 4 ..]); const known = isKnownExtension(sig); if (!known and !(sig[0] >= 'A' and sig[0] <= 'Z')) { if (diag) |d| { d.offset = pos; d.setDetail("{s}", .{&sig}); } return error.UnknownRequiredExtension; } const available = end - pos - 8; if (!known) { // git passes over it, however long it says it is, and stops // reading extensions if that takes it to the end. try ignored.append(arena, sig); try extensions.append(arena, .{ .signature = sig, .data = bytes[pos + 8 ..][0..@min(size, available)], .offset = pos }); if (size > available) break; pos += 8 + size; continue; } if (size > available) return malformed(diag, pos, "the {s} extension runs past the end", .{&sig}); try extensions.append(arena, .{ .signature = sig, .data = bytes[pos + 8 ..][0..size], .offset = pos }); pos += 8 + size; } return .{ .version = version, .entries = entries, .entry_offsets = offsets, .entries_end = entries_end, .extensions = try extensions.toOwnedSlice(arena), .ignored = try ignored.toOwnedSlice(arena), .checksum = bytes[end..], };}
/// Whether a path of `len` bytes agrees with the length its flags give.fn nameFits(field: u16, len: usize) bool { if (field == Entry.name_mask) return len >= Entry.name_mask; return len == field;}
fn be32(b: []const u8) u32 { return std.mem.readInt(u32, b[0..4], .big);}
fn malformed(diag: ?*Diagnostics, offset: usize, comptime fmt: []const u8, args: anytype) ParseError { if (diag) |d| { d.offset = offset; d.setDetail(fmt, args); } return error.MalformedIndex;}
/// Reads the variable-width integer at `bytes[pos.*..]`, advancing `pos`:/// the encoding OFS_DELTA offsets use (gitformat-pack(5)), seven bits to/// a byte, most significant first, each continuing byte adding one before/// the next seven bits. Null if it runs past the end or past 64 bits.pub fn readVarint(bytes: []const u8, pos: *usize) ?u64 { var p = pos.*; if (p >= bytes.len) return null; var c = bytes[p]; p += 1; var v: u64 = c & 0x7f; while (c & 0x80 != 0) { if (p >= bytes.len) return null; if (v >= (1 << 57) - 1) return null; c = bytes[p]; p += 1; v = ((v + 1) << 7) | (c & 0x7f); } pos.* = p; return v;}
/// What checking a checksum found.pub const ChecksumResult = enum { /// It is the hash of everything before it. valid, /// It is all zeros, as `index.skipHash` writes: not computed. skipped, /// It is neither. mismatch,};
/// Checks the checksum at the end of `bytes`, an index file in `format`/// at least as long as one.pub fn verifyChecksum(format: Format, bytes: []const u8) ChecksumResult { const n = format.byteLength(); const stored = bytes[bytes.len - n ..]; if (std.mem.allEqual(u8, stored, 0)) return .skipped; var h: object.Hasher = .init(format); h.update(bytes[0 .. bytes.len - n]); const computed = h.final(); return if (std.mem.eql(u8, computed.slice(), stored)) .valid else .mismatch;}
// -- tests -----------------------------------------------------------------------
const testing = std.testing;
const fuzz_input = @import("../testing/fuzz.zig");
test "a version 2 index git wrote is read entry by entry" { var arena: std.heap.ArenaAllocator = .init(testing.allocator); defer arena.deinit(); const bytes = @embedFile("../fuzz/index-v2"); const f = try parse(arena.allocator(), .sha1, bytes, null); try testing.expectEqual(2, f.version); try testing.expect(f.entries.len > 0); for (f.entries[1..], f.entries[0 .. f.entries.len - 1]) |b, a| try testing.expect(Entry.lessThan({}, a, b)); try testing.expectEqual(ChecksumResult.valid, verifyChecksum(.sha1, bytes));}
test "a version 4 index's prefix-compressed paths are expanded" { var arena: std.heap.ArenaAllocator = .init(testing.allocator); defer arena.deinit(); const f = try parse(arena.allocator(), .sha1, @embedFile("../fuzz/index-v4"), null); try testing.expectEqual(4, f.version); for (f.entries[1..], f.entries[0 .. f.entries.len - 1]) |b, a| try testing.expect(Entry.lessThan({}, a, b));}
test "variable-width integers are read as OFS_DELTA offsets are" { var pos: usize = 0; try testing.expectEqual(5, readVarint(&.{0x05}, &pos)); pos = 0; // 0x80 0x00 is 128: the continuing byte adds one before shifting. try testing.expectEqual(128, readVarint(&.{ 0x80, 0x00 }, &pos)); try testing.expectEqual(2, pos); pos = 0; try testing.expectEqual(null, readVarint(&.{0x80}, &pos));}
test "a malformed header is refused in git's words" { var arena: std.heap.ArenaAllocator = .init(testing.allocator); defer arena.deinit(); const a = arena.allocator(); var d: Diagnostics = .{}; try testing.expectError(error.IndexTooSmall, parse(a, .sha1, "DIRC\x00\x00\x00\x02", &d)); const zeros: [20]u8 = @splat(0); try testing.expectError(error.BadIndexSignature, parse(a, .sha1, "DRID\x00\x00\x00\x02\x00\x00\x00\x00" ++ zeros, &d)); try testing.expectEqualStrings(if (builtin.cpu.arch.endian() == .little) "0x44495244" else "0x44524944", d.detail()); try testing.expectError(error.UnsupportedIndexVersion, parse(a, .sha1, "DIRC\x00\x00\x00\x05\x00\x00\x00\x00" ++ zeros, &d)); try testing.expectEqualStrings("5", d.detail()); try testing.expectError(error.MalformedIndex, parse(a, .sha1, "DIRC\x00\x00\x00\x02\x00\x00\x00\x02" ++ zeros, &d)); try testing.expectError(error.UnknownRequiredExtension, parse(a, .sha1, "DIRC\x00\x00\x00\x02\x00\x00\x00\x00abcd\x00\x00\x00\x00" ++ zeros, &d)); try testing.expectEqualStrings("abcd", d.detail()); const f = try parse(a, .sha1, "DIRC\x00\x00\x00\x02\x00\x00\x00\x00ABCD\x00\x00\x00\x09xy" ++ zeros, &d); try testing.expectEqual(1, f.ignored.len); try testing.expectEqual(ChecksumResult.skipped, verifyChecksum(.sha1, "DIRC\x00\x00\x00\x02\x00\x00\x00\x00" ++ zeros));}
test "fuzz: index files" { try fuzz_input.fuzz({}, struct { fn one(_: void, smith: *testing.Smith) anyerror!void { var buffer: [4096]u8 = undefined; const input = @import("../testing/fuzz.zig").bytes(smith, &buffer); for ([_]Format{ .sha1, .sha256 }) |format| { var arena: std.heap.ArenaAllocator = .init(testing.allocator); defer arena.deinit(); const f = parse(arena.allocator(), format, input, null) catch continue; for (f.entries) |e| { _ = e.stage(); _ = e.isSparseDirectory(); } _ = verifyChecksum(format, input); } } }.one, .{ .corpus = &.{ @embedFile("../fuzz/index-v2"), @embedFile("../fuzz/index-v4"), @embedFile("../fuzz/index-conflict"), @embedFile("../fuzz/index-split"), } });}