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
//! The split index: the `link` extension of the index, read from its//! bytes, and the shared index's entries and the main file's made into//! one list.//!//! gitformat-index(5) describes the extension: the object ID of the//! shared index, `sharedindex.<id>` beside the index file (all zeros for//! none), then an EWAH bitmap of the shared index's entries to delete and//! one of those to replace. The main file's entries replace the shared//! index's entries the replace bitmap names, in order, and may have empty//! paths standing for theirs; the rest are added. Deleted entries are//! dropped after the replacing, so a replaced entry can be deleted too.//!//! What git says when the parts do not fit together, found by writing//! malformed extensions://!//! - fewer bytes than an object ID: "corrupt link extension (too short)";//! - a bitmap that cannot be read: the bitmap's complaint, then "corrupt//! delete bitmap in link extension" or "corrupt replace bitmap in link//! extension";//! - bytes after the bitmaps: "garbage at the end of link extension";//! each of those then "index file corrupt";//! - a bit past the shared index's entries: "position for delete N//! exceeds base index size M" or "position for replacement N exceeds//! base index size M";//! - more bits in the replace bitmap than the main file has entries: "too//! many replacements (N vs N)";//! - an added entry with an empty path: "corrupt link extension, entry N//! should have non-zero length name".//!//! The bitmaps' bit counts limit nothing: git acts on every set bit.
const std = @import("std");const Allocator = std.mem.Allocator;
const Diagnostics = @import("../Diagnostics.zig");const object = @import("../object.zig");const Format = object.Format;const Id = object.Id;const ewah = @import("ewah.zig");const file = @import("file.zig");const Entry = file.Entry;
/// The `link` extension.pub const Link = struct { /// The shared index's object ID; all zeros when there is none. shared_id: Id, delete: ewah.Bitmap, replace: ewah.Bitmap,
/// Whether there is a shared index to read. pub fn hasSharedIndex(l: *const Link) bool { return !std.mem.allEqual(u8, l.shared_id.slice(), 0); }};
/// Why a `link` extension could not be read, each in git's words:/// `LinkTooShort`, `CorruptDeleteBitmap` and `CorruptReplaceBitmap` (the/// detail is the bitmap's own complaint), and `LinkGarbage`.pub const ParseError = error{ LinkTooShort, CorruptDeleteBitmap, CorruptReplaceBitmap, LinkGarbage };
/// Reads the `link` extension's contents, in `format`.pub fn parse(format: Format, data: []const u8, diag: ?*Diagnostics) ParseError!Link { const n = format.byteLength(); if (data.len < n) return error.LinkTooShort; const id: Id = .fromBytes(format, data[0..n]); var pos = n; const delete = ewah.parse(data[pos..], diag) catch return error.CorruptDeleteBitmap; pos += delete.len; const replace = ewah.parse(data[pos..], diag) catch return error.CorruptReplaceBitmap; pos += replace.len; if (pos != data.len) return error.LinkGarbage; return .{ .shared_id = id, .delete = delete.bitmap, .replace = replace.bitmap };}
/// Why the two files of a split index do not make one list, each in git's/// words, which the diagnostic's detail holds in full:/// `DeletePositionOutOfRange`, `ReplacePositionOutOfRange`,/// `TooManyReplacements` and `EmptySplitEntryName`.pub const MergeError = error{ DeletePositionOutOfRange, ReplacePositionOutOfRange, TooManyReplacements, EmptySplitEntryName,} || Allocator.Error;
/// The shared index's entries with the main file's applied as `link`/// says, sorted as the index keeps them, allocated with `arena`, each/// marked with where it came from.pub fn merge(arena: Allocator, shared: []const Entry, main: []const Entry, link: Link, diag: ?*Diagnostics) MergeError![]Entry { const out = try arena.alloc(Entry, shared.len + main.len); const deleted = try arena.alloc(bool, shared.len); @memset(deleted, false); for (shared, out[0..shared.len]) |s, *o| { o.* = s; o.origin = .shared; }
var it = link.delete.iterator(); while (it.next()) |p| { if (p >= shared.len) return fail(diag, error.DeletePositionOutOfRange, "position for delete {d} exceeds base index size {d}", .{ p, shared.len }); deleted[@intCast(p)] = true; }
var used: usize = 0; it = link.replace.iterator(); while (it.next()) |p| { if (p >= shared.len) return fail(diag, error.ReplacePositionOutOfRange, "position for replacement {d} exceeds base index size {d}", .{ p, shared.len }); if (used == main.len) return fail(diag, error.TooManyReplacements, "too many replacements ({d} vs {d})", .{ used, main.len }); const i: usize = @intCast(p); var r = main[used]; if (r.path.len == 0) r.path = shared[i].path; r.origin = .replacement; out[i] = r; used += 1; }
var n: usize = 0; for (out[0..shared.len], deleted) |e, d| { if (d) continue; out[n] = e; n += 1; } for (main[used..], used..) |e, i| { if (e.path.len == 0) return fail(diag, error.EmptySplitEntryName, "corrupt link extension, entry {d} should have non-zero length name", .{i}); out[n] = e; out[n].origin = .own; n += 1; } const merged = out[0..n]; std.mem.sort(Entry, merged, {}, Entry.lessThan); return merged;}
fn fail(diag: ?*Diagnostics, err: MergeError, comptime fmt: []const u8, args: anytype) MergeError { if (diag) |d| d.setDetail(fmt, args); return err;}
// -- tests -----------------------------------------------------------------------
const testing = std.testing;
fn entry(path: []const u8, size: u32) Entry { return .{ .ctime = .{ .seconds = 0, .nanoseconds = 0 }, .mtime = .{ .seconds = 0, .nanoseconds = 0 }, .dev = 0, .ino = 0, .mode = 0o100644, .uid = 0, .gid = 0, .size = size, .id = .zero(.sha1), .flags = 0, .extended_flags = 0, .path = path, };}
fn bitmapBytes(comptime literal: u64) [28]u8 { var b: [28]u8 = undefined; std.mem.writeInt(u32, b[0..4], 64, .big); std.mem.writeInt(u32, b[4..8], 2, .big); std.mem.writeInt(u64, b[8..16], 0x0000_0002_0000_0000, .big); std.mem.writeInt(u64, b[16..24], literal, .big); std.mem.writeInt(u32, b[24..28], 0, .big); return b;}
const fuzz_input = @import("../testing/fuzz.zig");
test "a split index's entries are replaced, deleted and added as the link says" { var arena: std.heap.ArenaAllocator = .init(testing.allocator); defer arena.deinit(); const a = arena.allocator(); const zero: [20]u8 = @splat(0); const id: [20]u8 = @splat(1); // Delete the third shared entry; replace the first and second. const data = id ++ bitmapBytes(0b100) ++ bitmapBytes(0b011); const link = try parse(.sha1, &data, null); try testing.expect(link.hasSharedIndex()); const shared = [_]Entry{ entry("a", 1), entry("b", 1), entry("c", 1), entry("d", 1) }; const main = [_]Entry{ entry("", 2), entry("b", 2), entry("bb", 3) }; const merged = try merge(a, &shared, &main, link, null); try testing.expectEqual(4, merged.len); try testing.expectEqualStrings("a", merged[0].path); try testing.expectEqual(2, merged[0].size); try testing.expectEqual(.replacement, merged[0].origin); try testing.expectEqualStrings("bb", merged[2].path); try testing.expectEqual(.own, merged[2].origin); try testing.expectEqual(.shared, merged[3].origin); try testing.expectEqualStrings("d", merged[3].path);
var d: Diagnostics = .{}; const too_many = id ++ bitmapBytes(0) ++ bitmapBytes(0b1111); try testing.expectError(error.TooManyReplacements, merge(a, &shared, &main, try parse(.sha1, &too_many, null), &d)); try testing.expectEqualStrings("too many replacements (3 vs 3)", d.detail()); const past = id ++ bitmapBytes(1 << 7) ++ bitmapBytes(0); try testing.expectError(error.DeletePositionOutOfRange, merge(a, &shared, &main, try parse(.sha1, &past, null), &d)); try testing.expectEqualStrings("position for delete 7 exceeds base index size 4", d.detail()); const none = zero ++ bitmapBytes(0) ++ bitmapBytes(0); try testing.expectError(error.EmptySplitEntryName, merge(a, &shared, &main, try parse(.sha1, &none, null), &d)); try testing.expectEqualStrings("corrupt link extension, entry 0 should have non-zero length name", d.detail());
try testing.expectError(error.LinkTooShort, parse(.sha1, id[0..15], null)); try testing.expectError(error.CorruptDeleteBitmap, parse(.sha1, &(id ++ [_]u8{ 0, 0, 0, 0 }), &d)); try testing.expectEqualStrings("eof before length", d.detail()); try testing.expectError(error.LinkGarbage, parse(.sha1, &(data ++ [_]u8{0}), null));}
test "fuzz: link extensions" { try fuzz_input.fuzz({}, struct { fn one(_: void, smith: *testing.Smith) anyerror!void { var buffer: [1024]u8 = undefined; const input = @import("../testing/fuzz.zig").bytes(smith, &buffer); var arena: std.heap.ArenaAllocator = .init(testing.allocator); defer arena.deinit(); for ([_]Format{ .sha1, .sha256 }) |format| { const link = parse(format, input, null) catch continue; const shared = [_]Entry{ entry("a", 1), entry("b", 1), entry("c", 1) }; const main = [_]Entry{ entry("", 2), entry("d", 2) }; _ = merge(arena.allocator(), &shared, &main, link, null) catch continue; } } }.one, .{ .corpus = &.{ @embedFile("../fuzz/index-link"), @embedFile("../fuzz/index-link-sha256"), } });}