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.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie <jeff@ocjtech.us>// SPDX-License-Identifier: MIT
//! The cache tree: the `TREE` extension of the index, read from its bytes.//!//! gitformat-index(5) describes it: a node for each directory, top-down//! and depth first, each its path component and a NUL, the count of index//! entries it covers in ASCII decimal, a space, the count of its subtrees,//! a newline, and — unless the count of entries is negative, which marks//! a directory with changed entries — the object ID of the tree those//! entries make. git writes -1 for an invalidated node.//!//! git drops a `TREE` extension it cannot read without a word, so a//! caller of `parse` does the same with its error.
const std = @import("std");const Allocator = std.mem.Allocator;
const object = @import("../object.zig");const Format = object.Format;const Id = object.Id;
/// One directory of the cache tree.pub const Node = struct { /// The directory's path from the top, without a trailing slash; empty /// for the top. path: []const u8, /// How many index entries the directory covers; null when the node is /// invalidated, and then `id` is null too. entry_count: ?u32, /// What the entry count was written as, negative for an invalidated /// node. raw_entry_count: i64, /// The tree the directory's entries make, when known. id: ?Id, /// How many subdirectories have nodes of their own; they follow this /// one, each with its own subtrees after it. subtree_count: u32,};
/// The cache tree, every node in the order written: the top first, each/// node followed by its subtrees.pub const CacheTree = struct { nodes: []Node,
/// The node for directory `path` (no trailing slash; empty for the /// top), if there is one. pub fn find(t: *const CacheTree, path: []const u8) ?*const Node { for (t.nodes) |*n| if (std.mem.eql(u8, n.path, path)) return n; return null; }
/// The top's node, if the cache tree has any. pub fn root(t: *const CacheTree) ?*const Node { return if (t.nodes.len == 0) null else &t.nodes[0]; }};
/// Why a `TREE` extension could not be read.pub const Error = error{MalformedCacheTree} || Allocator.Error;
/// Reads the `TREE` extension's contents, in `format`, allocating with/// `arena`.pub fn parse(arena: Allocator, format: Format, data: []const u8) Error!CacheTree { var nodes: std.ArrayList(Node) = .empty; // The path of each open directory and how many subtrees it still // expects. const Open = struct { path_len: usize, remaining: u32 }; var stack: std.ArrayList(Open) = .empty; var path: std.ArrayList(u8) = .empty; var pos: usize = 0; while (pos < data.len) { if (nodes.items.len != 0 and stack.items.len == 0) return error.MalformedCacheTree; const nul = std.mem.findScalar(u8, data[pos..], 0) orelse return error.MalformedCacheTree; const name = data[pos..][0..nul]; pos += nul + 1; const count = try number(i64, data, &pos, ' '); const subtrees = try number(u32, data, &pos, '\n'); var id: ?Id = null; if (count >= 0) { const n = format.byteLength(); if (data.len - pos < n) return error.MalformedCacheTree; id = .fromBytes(format, data[pos..][0..n]); pos += n; } if (stack.items.len == 0) { if (name.len != 0) return error.MalformedCacheTree; } else { if (name.len == 0) return error.MalformedCacheTree; const parent = &stack.items[stack.items.len - 1]; path.shrinkRetainingCapacity(parent.path_len); parent.remaining -= 1; if (path.items.len != 0) try path.append(arena, '/'); try path.appendSlice(arena, name); } try nodes.append(arena, .{ .path = try arena.dupe(u8, path.items), .entry_count = if (count >= 0) std.math.cast(u32, count) orelse return error.MalformedCacheTree else null, .raw_entry_count = count, .id = id, .subtree_count = subtrees, }); try stack.append(arena, .{ .path_len = path.items.len, .remaining = subtrees }); while (stack.items.len != 0 and stack.items[stack.items.len - 1].remaining == 0) _ = stack.pop(); } if (stack.items.len != 0) return error.MalformedCacheTree; return .{ .nodes = try nodes.toOwnedSlice(arena) };}
/// Reads a decimal number ending at `end`, negative if `T` allows it.fn number(comptime T: type, data: []const u8, pos: *usize, end: u8) error{MalformedCacheTree}!T { var p = pos.*; const negative = std.math.minInt(T) < 0 and p < data.len and data[p] == '-'; if (negative) p += 1; const start = p; var v: T = 0; while (p < data.len and data[p] >= '0' and data[p] <= '9') : (p += 1) { v = std.math.mul(T, v, 10) catch return error.MalformedCacheTree; const digit: T = @intCast(data[p] - '0'); v = (if (negative) std.math.sub(T, v, digit) else std.math.add(T, v, digit)) catch return error.MalformedCacheTree; } if (p == start or p >= data.len or data[p] != end) return error.MalformedCacheTree; pos.* = p + 1; return v;}
// -- tests -----------------------------------------------------------------------
const testing = std.testing;
const fuzz_input = @import("../testing/fuzz.zig");
test "a cache tree with an invalidated node is read" { var arena: std.heap.ArenaAllocator = .init(testing.allocator); defer arena.deinit(); const id: [20]u8 = @splat(0xab); const data = "\x00-1 2\n" ++ "a\x003 1\n" ++ id ++ "b\x001 0\n" ++ id ++ "c\x00-1 0\n"; const t = try parse(arena.allocator(), .sha1, data); try testing.expectEqual(4, t.nodes.len); try testing.expectEqual(null, t.root().?.entry_count); try testing.expectEqualStrings("a/b", t.nodes[2].path); try testing.expectEqual(1, t.find("a/b").?.entry_count); try testing.expectEqualStrings("c", t.nodes[3].path); try testing.expect(t.find("c").?.id == null);}
test "malformed cache trees are refused" { var arena: std.heap.ArenaAllocator = .init(testing.allocator); defer arena.deinit(); for ([_][]const u8{ "12", "\x00-1 1\n", "\x00-1 0\nx\x00-1 0\n", "\x00x 0\n", "\x001 0\n", "a\x00-1 0\n", "\x00-1 1\n\x00-1 0\n", "\x00-1 -1\n", }) |data| try testing.expectError(error.MalformedCacheTree, parse(arena.allocator(), .sha1, data));}
test "fuzz: cache trees" { 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); for ([_]Format{ .sha1, .sha256 }) |format| { var arena: std.heap.ArenaAllocator = .init(testing.allocator); defer arena.deinit(); const t = parse(arena.allocator(), format, input) catch continue; for (t.nodes) |n| _ = t.find(n.path); } } }.one, .{ .corpus = &.{ @embedFile("../fuzz/index-tree"), @embedFile("../fuzz/index-tree-sha256"), } });}