Skip to content
zit Artifact [70a0b35613]
Login

Artifact [70a0b35613]

Check-ins Using Download Hex

Artifact 70a0b3561380f216a0cea9ee9419bb1cd1b77d9b6a73786f41992dfd70ceb04a:

//! Checkout-local bisection state (`.zit-bisect`) — the `undo.zig` state-file
//! tier applied to `zit bisect`. No RFC governs it; like `.zit-undo` it is a
//! settled checkout-layer decision, never repository state, never synced, never
//! a tag. It joins the never-tracked set and the extras exclusion (`extras.zig`).
//!
//! 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 crc32 = @import("crc32.zig");

/// The single-component root name; a STRICT member of the never-tracked set
/// (`extras.isControlName`) and the extras exclusion.
pub const filename: []const u8 = ".zit-bisect";

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 `.zit-bisect` exists (no bisect in
/// progress). A damaged file 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 = root.readFileAlloc(io, filename, gpa, .limited(read_cap)) catch |e| switch (e) {
        error.FileNotFound => return null,
        error.OutOfMemory => return error.OutOfMemory,
        else => return error.Storage,
    };
    defer gpa.free(raw);
    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);
    var af = root.createFileAtomic(io, filename, .{ .replace = true }) catch return error.Storage;
    defer af.deinit(io);
    af.file.writePositionalAll(io, bytes, 0) catch return error.Storage;
    af.file.sync(io) catch return error.Storage; // fsync before the rename
    af.replace(io) catch return error.Storage;
}

/// End the session: best-effort delete of `.zit-bisect` (a missing file is not
/// an error). Mirrors `undo.clear`.
pub fn clear(io: std.Io, root: std.Io.Dir) void {
    root.deleteFile(io, filename) 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{ "a" ** 64, "b" ** 64 };
    const good = [_][]const u8{"c" ** 64};
    const skipped = [_][]const u8{};
    const bytes = try encode(t.allocator, "d" ** 64, &bad, &good, &skipped);
    defer t.allocator.free(bytes);

    var s = try parse(t.allocator, bytes);
    defer s.deinit();
    try t.expectEqualStrings("d" ** 64, s.start);
    try t.expectEqual(@as(usize, 2), s.bad.len);
    try t.expectEqualStrings("a" ** 64, s.bad[0]);
    try t.expectEqualStrings("b" ** 64, s.bad[1]);
    try t.expectEqual(@as(usize, 1), s.good.len);
    try t.expectEqualStrings("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{"a" ** 64};
    const bytes = try encode(t.allocator, "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);
            }
        }
    }
}