//! Checkout-local bisection state — the bisect section of the `.zit-checkout`
//! container (legacy `.zit-bisect` sibling on a pre-container checkout); the
//! `undo.zig` state tier applied to `zit bisect`. No RFC governs it: a settled
//! checkout-layer decision, never repository state, never synced, never a tag.
//!
//! One session records the start check-in (for `reset` to restore), and the
//! bad / good / skipped mark sets. The next probe and the culprit are NOT stored
//! — they are re-derived from the marks by the one general-purpose repostate
//! query (`RepoState.bisectSpan`), so the file never caches a stale midpoint.
//!
//! Durability mirrors `undo.zig`: the record is written temp + fsync + rename
//! BEFORE any checkout move, and read back through a bounds-checked cursor. A
//! damaged file is `error.Corrupt` at parse, before any trust — never a partial
//! read (B-bisect-6). The parser never panics on adversarial bytes (B-bisect-15).
const std = @import("std");
const repeat = @import("repeat.zig").repeat;
const crc32 = @import("crc32.zig");
const checkout = @import("checkout.zig");
const magic = "ZITBSCT\x00"; // 8 bytes
const fmt_version: u8 = 1;
/// A stored mark / start value is a lowercase-hex artifact name (<= 64 bytes);
/// the cap rejects an absurd length before allocation. A session never holds
/// more marks than the repository has check-ins; the cap bounds a corrupt count.
const max_str: usize = 256;
const max_marks: usize = 1 << 20;
/// A well-formed record: framing, a start value, and three bounded mark lists.
/// Larger than this and the file is rejected before allocation grows unbounded.
const read_cap: usize = magic.len + 1 + (2 + max_str) +
3 * (4 + 64 * (2 + max_str)) + 4 + 4096;
pub const StateError = error{ Storage, Corrupt, OutOfMemory };
/// A parsed bisection session. All slices are owned by `arena`; `deinit` frees
/// them in one shot. The mark sets are in stored order (append order).
pub const Session = struct {
arena: std.heap.ArenaAllocator,
/// The check-in current when the session started — where `reset` returns.
start: []const u8,
bad: []const []const u8,
good: []const []const u8,
skipped: []const []const u8,
pub fn deinit(self: *Session) void {
self.arena.deinit();
}
};
/// The current session, or null when no bisect section exists (no bisect in
/// progress) — read from the `.zit-checkout` container, or the legacy
/// `.zit-bisect` sibling on a pre-container checkout (checkout.zig §5.1; the
/// record format is identical either way). A damaged record is
/// `error.Corrupt` (name `reset` as the recovery).
pub fn read(gpa: std.mem.Allocator, io: std.Io, root: std.Io.Dir) StateError!?Session {
const raw = (try checkout.readSectionAlloc(gpa, io, root, .bisect)) orelse return null;
defer gpa.free(raw);
if (raw.len > read_cap) return error.Corrupt; // the same absurd-length gate the file read had
return try parse(gpa, raw);
}
/// Persist a session durably (write temp + fsync + rename), replacing any prior
/// record. Called BEFORE the checkout move so a crash leaves the marks recorded
/// and the move re-derivable, never a moved checkout with lost marks.
pub fn write(
gpa: std.mem.Allocator,
io: std.Io,
root: std.Io.Dir,
start: []const u8,
bad: []const []const u8,
good: []const []const u8,
skipped: []const []const u8,
) StateError!void {
const bytes = try encode(gpa, start, bad, good, skipped);
defer gpa.free(bytes);
checkout.updateSections(io, root, &.{.{ .tag = .bisect, .payload = bytes }}) catch |e| switch (e) {
error.Storage => return error.Storage,
error.Corrupt => return error.Corrupt,
};
}
/// End the session: best-effort removal of the bisect section (an absent
/// section is not an error). Mirrors `undo.clear`.
pub fn clear(io: std.Io, root: std.Io.Dir) void {
checkout.updateSections(io, root, &.{.{ .tag = .bisect, .payload = null }}) catch {};
}
// ---------------------------------------------------------------------------
// Wire format. `magic(8) | fmt(1) | str16(start) | list(bad) | list(good) |
// list(skipped) | crc32 le(4)`, crc over all preceding bytes. `str16` is
// `len u16 | bytes`; `list` is `count u32 | str16 ...`. Every length is
// bounds-checked against the remaining input and its cap before use;
// consumption must be exact; the crc must match. Any violation is
// `error.Corrupt`.
// ---------------------------------------------------------------------------
fn encode(
gpa: std.mem.Allocator,
start: []const u8,
bad: []const []const u8,
good: []const []const u8,
skipped: []const []const u8,
) StateError![]u8 {
var buf: std.ArrayList(u8) = .empty;
errdefer buf.deinit(gpa);
buf.appendSlice(gpa, magic) catch return error.OutOfMemory;
buf.append(gpa, fmt_version) catch return error.OutOfMemory;
try encodeStr16(gpa, &buf, start);
try encodeList(gpa, &buf, bad);
try encodeList(gpa, &buf, good);
try encodeList(gpa, &buf, skipped);
var crc: [4]u8 = undefined;
std.mem.writeInt(u32, &crc, crc32.Crc32.hash(buf.items), .little);
buf.appendSlice(gpa, &crc) catch return error.OutOfMemory;
return buf.toOwnedSlice(gpa) catch return error.OutOfMemory;
}
fn encodeList(gpa: std.mem.Allocator, buf: *std.ArrayList(u8), items: []const []const u8) StateError!void {
var count: [4]u8 = undefined;
std.mem.writeInt(u32, &count, @intCast(items.len), .little);
buf.appendSlice(gpa, &count) catch return error.OutOfMemory;
for (items) |s| try encodeStr16(gpa, buf, s);
}
fn encodeStr16(gpa: std.mem.Allocator, buf: *std.ArrayList(u8), s: []const u8) StateError!void {
std.debug.assert(s.len <= max_str);
var len: [2]u8 = undefined;
std.mem.writeInt(u16, &len, @intCast(s.len), .little);
buf.appendSlice(gpa, &len) catch return error.OutOfMemory;
buf.appendSlice(gpa, s) catch return error.OutOfMemory;
}
/// A forward cursor over the record bytes. Every read bounds-checks against the
/// remaining input; an over-read is `error.Corrupt`, never a panic.
const Cursor = struct {
bytes: []const u8,
pos: usize = 0,
fn u8v(self: *Cursor) StateError!u8 {
if (self.pos + 1 > self.bytes.len) return error.Corrupt;
const v = self.bytes[self.pos];
self.pos += 1;
return v;
}
fn u16v(self: *Cursor) StateError!u16 {
if (self.pos + 2 > self.bytes.len) return error.Corrupt;
const v = std.mem.readInt(u16, self.bytes[self.pos..][0..2], .little);
self.pos += 2;
return v;
}
fn u32v(self: *Cursor) StateError!u32 {
if (self.pos + 4 > self.bytes.len) return error.Corrupt;
const v = std.mem.readInt(u32, self.bytes[self.pos..][0..4], .little);
self.pos += 4;
return v;
}
fn take(self: *Cursor, n: usize) StateError![]const u8 {
if (self.pos + n > self.bytes.len) return error.Corrupt;
const s = self.bytes[self.pos..][0..n];
self.pos += n;
return s;
}
};
/// Parse a `.zit-bisect` record. The arena in the returned `Session` owns every
/// string. Never panics: adversarial bytes yield `error.Corrupt` (or
/// `error.OutOfMemory`), the mandatory fuzz obligation (B-bisect-15).
pub fn parse(gpa: std.mem.Allocator, raw: []const u8) StateError!Session {
if (raw.len < magic.len + 1 + 4) return error.Corrupt;
if (!std.mem.eql(u8, raw[0..magic.len], magic)) return error.Corrupt;
// crc covers every byte before the trailing 4-byte crc field.
const body = raw[0 .. raw.len - 4];
const stored = std.mem.readInt(u32, raw[raw.len - 4 ..][0..4], .little);
if (crc32.Crc32.hash(body) != stored) return error.Corrupt;
var cur = Cursor{ .bytes = body, .pos = magic.len };
if (try cur.u8v() != fmt_version) return error.Corrupt;
var arena = std.heap.ArenaAllocator.init(gpa);
errdefer arena.deinit();
const a = arena.allocator();
const start = try parseStr16(a, &cur);
const bad = try parseList(a, &cur);
const good = try parseList(a, &cur);
const skipped = try parseList(a, &cur);
if (cur.pos != body.len) return error.Corrupt; // exact consumption, no trailing bytes
return .{ .arena = arena, .start = start, .bad = bad, .good = good, .skipped = skipped };
}
fn parseList(a: std.mem.Allocator, cur: *Cursor) StateError![]const []const u8 {
const count = try cur.u32v();
if (count > max_marks) return error.Corrupt;
if (count == 0) return &.{};
const items = a.alloc([]const u8, count) catch return error.OutOfMemory;
for (items) |*it| it.* = try parseStr16(a, cur);
return items;
}
fn parseStr16(a: std.mem.Allocator, cur: *Cursor) StateError![]const u8 {
const len = try cur.u16v();
if (len > max_str) return error.Corrupt;
const bytes = try cur.take(len);
return a.dupe(u8, bytes) catch return error.OutOfMemory;
}
// --- tests --------------------------------------------------------------------
const t = std.testing;
test "bisect state: round-trips start and the mark sets" {
const bad = [_][]const u8{ repeat("a", 64), repeat("b", 64) };
const good = [_][]const u8{repeat("c", 64)};
const skipped = [_][]const u8{};
const bytes = try encode(t.allocator, repeat("d", 64), &bad, &good, &skipped);
defer t.allocator.free(bytes);
var s = try parse(t.allocator, bytes);
defer s.deinit();
try t.expectEqualStrings(repeat("d", 64), s.start);
try t.expectEqual(@as(usize, 2), s.bad.len);
try t.expectEqualStrings(repeat("a", 64), s.bad[0]);
try t.expectEqualStrings(repeat("b", 64), s.bad[1]);
try t.expectEqual(@as(usize, 1), s.good.len);
try t.expectEqualStrings(repeat("c", 64), s.good[0]);
try t.expectEqual(@as(usize, 0), s.skipped.len);
}
test "bisect state: an empty session round-trips" {
const bytes = try encode(t.allocator, "", &.{}, &.{}, &.{});
defer t.allocator.free(bytes);
var s = try parse(t.allocator, bytes);
defer s.deinit();
try t.expectEqualStrings("", s.start);
try t.expectEqual(@as(usize, 0), s.bad.len);
}
test "bisect state: a flipped byte, wrong magic, or truncation is Corrupt" {
const good = [_][]const u8{repeat("a", 64)};
const bytes = try encode(t.allocator, repeat("b", 64), &good, &.{}, &.{});
defer t.allocator.free(bytes);
// A one-byte payload flip fails the crc.
const flipped = try t.allocator.dupe(u8, bytes);
defer t.allocator.free(flipped);
flipped[magic.len + 3] ^= 0xff;
try t.expectError(error.Corrupt, parse(t.allocator, flipped));
// A corrupted magic is rejected before the crc.
const bad_magic = try t.allocator.dupe(u8, bytes);
defer t.allocator.free(bad_magic);
bad_magic[0] = 'X';
try t.expectError(error.Corrupt, parse(t.allocator, bad_magic));
// A truncated record is rejected (crc field missing / cursor over-read).
try t.expectError(error.Corrupt, parse(t.allocator, bytes[0 .. bytes.len - 1]));
try t.expectError(error.Corrupt, parse(t.allocator, bytes[0..3]));
}
test "bisect state: parser never crashes on adversarial bytes (seeded fuzz)" {
// B-bisect-15: a declared error or a valid session, same seed byte-identical.
const seed: u64 = 0xB15EC7;
var pass: usize = 0;
while (pass < 2) : (pass += 1) {
var prng = std.Random.DefaultPrng.init(seed);
const rand = prng.random();
var round: usize = 0;
while (round < 4096) : (round += 1) {
var buf: [96]u8 = undefined;
const n = rand.uintLessThan(usize, buf.len + 1);
for (buf[0..n]) |*b| b.* = rand.int(u8);
// Bias some rounds toward a valid frame so parsing reaches deep.
if (rand.boolean() and n >= magic.len) @memcpy(buf[0..magic.len], magic);
if (parse(t.allocator, buf[0..n])) |*s| {
var sess = s.*;
sess.deinit();
} else |err| {
try t.expect(err == error.Corrupt or err == error.OutOfMemory);
}
}
}
}