//! `zit bisect`: binary-search the check-in DAG for the check-in that
//! introduced a defect.
const std = @import("std");
const cli = @import("zit").cli;
const logstore = @import("zit").logstore;
const update = @import("zit").update;
const checkout = @import("zit").checkout;
const bisect = @import("zit").bisect;
const Repository = @import("zit").Repository;
const diagnostics = @import("../diagnostics.zig");
const help_pages = @import("../help.zig");
const checkin_display = @import("checkin_display.zig");
const stateOom = diagnostics.stateOom;
const repoOpenFail = diagnostics.repoOpenFail;
const openRepo = diagnostics.openRepo;
const firstCommentLine = checkin_display.firstCommentLine;
const timeline_hash_display = checkin_display.timeline_hash_display;
const bisect_help = help_pages.bisect_help;
const cmd_commit = @import("commit.zig");
const commitMapCapture = cmd_commit.commitMapCapture;
// ==========================================================================
// `zit bisect SUBCOMMAND [NAME]` — binary-search the check-in DAG for the
// defect-introducing check-in (contracts/bisect.md B-bisect-1..20). The span
// math is ONE general-purpose repostate query (`Repository.bisectSpan`,
// ambiguities.md bisect-midpoint); moves ride the shipped update engine
// (`update.applyCheckin`, journal-armed); the session lives in `.zit-bisect`
// (the `undo.zig` state-file tier). This layer only orchestrates: parse, resolve,
// refuse, persist-then-move, announce.
// ==========================================================================
/// The 12-character display prefix of an artifact hash (timeline parity).
fn bisectShort(hash: []const u8) []const u8 {
return hash[0..@min(hash.len, timeline_hash_display)];
}
fn bisectDiag(s: cli.Streams, msg: []const u8) cli.Exit {
s.err.print("zit bisect: {s}\n", .{msg}) catch {};
return .failure;
}
fn bisectOom(s: cli.Streams) cli.Exit {
return bisectDiag(s, "out of memory");
}
fn bisectNoSession(s: cli.Streams) cli.Exit {
return bisectDiag(s, "no bisect in progress");
}
fn bisectInconsistent(s: cli.Streams) cli.Exit {
return bisectDiag(s, "bisect state names a check-in not in this repository; run 'zit bisect reset'");
}
/// Map a `.zit-bisect` read/write fault to its diagnostic. A corrupt file names
/// `reset` as the recovery (B-bisect-6), matching the `.zit-managed` parity.
fn bisectStateFail(s: cli.Streams, err: bisect.StateError) cli.Exit {
switch (err) {
error.OutOfMemory => return bisectOom(s),
error.Storage => return bisectDiag(s, "cannot read bisect state: input/output error"),
error.Corrupt => return bisectDiag(s, "cannot read bisect state: .zit-checkout is corrupt; run 'zit bisect reset' to recover"),
}
}
/// Map an update-engine move fault to its diagnostic. The check-in id and
/// baseline arms are unreachable for a check-in this view already resolved, so
/// they fold into the generic corrupt-repository message.
///
/// Exhaustive over `update.ApplyError` with NO `else`: bisect drives the same
/// engine as update, open and merge, so it reaches the same errors they do, and
/// a blanket `else` here silently answered `StateRecordInvalid` — reachable on
/// an intact clone — with a corruption claim. A new variant must fail this
/// compile and force a decision, as it does at the other three mappers.
fn bisectMoveFail(s: cli.Streams, err: update.ApplyError) cli.Exit {
switch (err) {
// applyCheckin never emits this: only applyMerge's cross-cone guard
// does, and bisect moves are checkin materializations. The unreachable
// IS the assertion; a future emitter trips it in tests immediately.
error.SparseMergeUnsupported => unreachable,
error.OutOfMemory => return bisectOom(s),
error.FileContentMissing => {
var b: [512]u8 = undefined;
return bisectDiag(s, update.stageFaultReason(&b));
},
error.WorktreeNotClean => return bisectDiag(s, "working tree is not clean"),
error.UnmanagedCollision => return bisectDiag(s, "an untracked file or directory is in the way"),
error.Storage => return bisectDiag(s, "cannot update working tree: input/output error"),
error.TransactionUnavailable => return bisectDiag(s, "cannot create a transaction directory"),
error.RollbackFailed => return bisectDiag(s, "move failed and could not be rolled back; the previous working-tree state is retained for recovery"),
error.CleanupFailed => return bisectDiag(s, "move committed, but the transaction directory could not be removed"),
error.StateRecordInvalid => return bisectDiag(s, "cannot read repository: " ++ update.state_record_invalid_reason),
error.CurrentStateInvalid => return bisectDiag(s, "current working-tree state is invalid"),
error.InvalidPath => return bisectDiag(s, "the check-in names an invalid file path"),
error.ReservedPath => return bisectDiag(s, "the check-in names a reserved file path"),
error.SymlinkUnsupported => return bisectDiag(s, "the check-in contains an unsupported symlink entry"),
error.Corrupt,
error.InvalidCheckinId,
error.CheckinNotFound,
error.CheckinContentMissing,
error.CheckinNameMismatch,
error.AggregateChecksumMismatch,
error.TargetNotManifest,
error.BaselineNotFound,
error.BaselineContentMissing,
error.BaselineNameMismatch,
error.BaselineNotManifest,
=> return bisectDiag(s, "cannot read repository: repository is corrupt"),
}
}
/// Resolve every stored mark hash to its rid. `Missing` == the session names a
/// hash this view never interned (an inconsistent state).
fn bisectRids(gpa: std.mem.Allocator, repo: *Repository, hashes: []const []const u8) error{ OutOfMemory, Missing }![]Repository.Rid {
const out = gpa.alloc(Repository.Rid, hashes.len) catch return error.OutOfMemory;
errdefer gpa.free(out);
for (hashes, out) |h, *r| r.* = repo.lookup(h) orelse return error.Missing;
return out;
}
/// Drop every occurrence of `hash` from `list` (content compare), so re-marking a
/// check-in moves it between the good/bad/skip sets rather than duplicating it.
fn bisectRemove(list: *std.ArrayList([]const u8), hash: []const u8) void {
var i: usize = 0;
while (i < list.items.len) {
if (std.mem.eql(u8, list.items[i], hash)) {
_ = list.orderedRemove(i);
} else i += 1;
}
}
pub fn runBisect(
gpa: std.mem.Allocator,
io: std.Io,
arena: std.mem.Allocator,
verb_args: []const []const u8,
streams: cli.Streams,
) cli.Exit {
const parsed = switch (cli.parseBisectArgs(verb_args)) {
.ok => |p| p,
.unknown_option => |tok| return cli.usageError(streams, "bisect", .unknown_option, tok),
.extra_argument => |tok| return cli.usageError(streams, "bisect", .extra_argument, tok),
.bad_subcommand => |tok| return cli.usageError(streams, "bisect", .bad_subcommand, tok),
.missing_name => return cli.usageError(streams, "bisect", .no_name, ""),
};
if (parsed.help) {
streams.out.writeAll(bisect_help) catch {};
return .ok;
}
var repo: Repository = undefined;
var root_dir: std.Io.Dir = undefined;
const rc = openRepo(gpa, io, arena, streams, "bisect", null, false, true, &repo, &root_dir);
if (rc != .ok) return rc;
defer root_dir.close(io);
defer repo.deinit(gpa);
return switch (parsed.sub) {
.bad => bisectMark(gpa, io, &repo, root_dir, streams, parsed.name.?, .bad),
.good => bisectMark(gpa, io, &repo, root_dir, streams, parsed.name.?, .good),
.next => bisectNext(gpa, io, &repo, root_dir, streams),
.status => bisectStatus(gpa, io, &repo, root_dir, streams),
.reset => bisectReset(gpa, io, &repo, root_dir, streams),
};
}
/// `zit bisect bad|good NAME`: record the mark, then — once both a bad and a good
/// endpoint exist — narrow the span and move the checkout to the next probe
/// (B-bisect-1/3). A lone endpoint is recorded and confirmed without moving.
fn bisectMark(
gpa: std.mem.Allocator,
io: std.Io,
repo: *Repository,
root_dir: std.Io.Dir,
streams: cli.Streams,
name: []const u8,
kind: cli.BisectSub,
) cli.Exit {
const rid = repo.resolve(name, .checkin) catch |e| switch (e) {
error.NotFound => {
streams.err.print("zit bisect: check-in '{s}' not found\n", .{name}) catch {};
cli.horizonNameHint(gpa, io, root_dir, streams, "bisect");
return .failure;
},
error.Ambiguous => {
streams.err.print("zit bisect: name '{s}' is ambiguous\n", .{name}) catch {};
return .failure;
},
error.OutOfMemory => return stateOom(streams, "bisect"),
};
const hash = repo.hashOf(rid);
var sess_opt = bisect.read(gpa, io, root_dir) catch |e| return bisectStateFail(streams, e);
defer if (sess_opt) |*s| s.deinit();
var work = std.heap.ArenaAllocator.init(gpa);
defer work.deinit();
const a = work.allocator();
var bad_list: std.ArrayList([]const u8) = .empty;
var good_list: std.ArrayList([]const u8) = .empty;
var skip_list: std.ArrayList([]const u8) = .empty;
var start: []const u8 = "";
if (sess_opt) |s| {
start = s.start;
for (s.bad) |x| bad_list.append(a, x) catch return bisectOom(streams);
for (s.good) |x| good_list.append(a, x) catch return bisectOom(streams);
for (s.skipped) |x| skip_list.append(a, x) catch return bisectOom(streams);
} else {
// Fresh session: the current checkout is the restore point for `reset`.
var ck_buf: [checkout.max_ck_payload + 1]u8 = undefined;
if (checkout.read(io, root_dir, &ck_buf) catch null) |ck| {
start = a.dupe(u8, ck.version) catch return bisectOom(streams);
}
}
const dh = a.dupe(u8, hash) catch return bisectOom(streams);
bisectRemove(&bad_list, dh);
bisectRemove(&good_list, dh);
bisectRemove(&skip_list, dh);
switch (kind) {
.bad => bad_list.append(a, dh) catch return bisectOom(streams),
.good => good_list.append(a, dh) catch return bisectOom(streams),
else => unreachable,
}
const has_both = bad_list.items.len != 0 and good_list.items.len != 0;
if (!has_both) {
// Record the lone endpoint; no move (B-bisect-1 first half).
bisect.write(gpa, io, root_dir, start, bad_list.items, good_list.items, skip_list.items) catch |e|
return bisectStateFail(streams, e);
streams.out.print("bisect: marked {s} {s}\n", .{ bisectShort(hash), @tagName(kind) }) catch {};
const other = if (kind == .bad) "good" else "bad";
streams.out.print("bisect: mark a {s} check-in to begin bisecting\n", .{other}) catch {};
return .ok;
}
return bisectAdvance(gpa, io, repo, root_dir, streams, start, bad_list.items, good_list.items, skip_list.items, true);
}
/// Derive the span, refuse over a dirty tree / inverted / unrelated marks
/// (mutating nothing), then — only on success — persist the state and move the
/// checkout to the probe (or the culprit when the span is exhausted). Shared by
/// marking (persist == true) and `next` (persist == true, idempotent rewrite).
fn bisectAdvance(
gpa: std.mem.Allocator,
io: std.Io,
repo: *Repository,
root_dir: std.Io.Dir,
streams: cli.Streams,
start: []const u8,
bad_hashes: []const []const u8,
good_hashes: []const []const u8,
skip_hashes: []const []const u8,
persist: bool,
) cli.Exit {
// Precondition: both endpoints exist — a caller only advances once a bad AND a
// good mark are present (`bisectMark`'s `has_both`, `bisectNext`'s guard), and
// `bisectSpan` needs both to bound the span.
std.debug.assert(bad_hashes.len != 0 and good_hashes.len != 0);
// Dirty-tree refusal first — the shipped update discipline (B-bisect-9),
// mutating nothing.
const log = repo.logStore(gpa) catch |e| return repoOpenFail(streams, "bisect", e);
update.requireCleanTree(gpa, io, root_dir, log) catch |e| switch (e) {
error.WorktreeNotClean => return bisectDiag(streams, "working tree is not clean"),
else => return bisectMoveFail(streams, e),
};
const bad_rids = bisectRids(gpa, repo, bad_hashes) catch |e| switch (e) {
error.OutOfMemory => return bisectOom(streams),
error.Missing => return bisectInconsistent(streams),
};
defer gpa.free(bad_rids);
const good_rids = bisectRids(gpa, repo, good_hashes) catch |e| switch (e) {
error.OutOfMemory => return bisectOom(streams),
error.Missing => return bisectInconsistent(streams),
};
defer gpa.free(good_rids);
const skip_rids = bisectRids(gpa, repo, skip_hashes) catch |e| switch (e) {
error.OutOfMemory => return bisectOom(streams),
error.Missing => return bisectInconsistent(streams),
};
defer gpa.free(skip_rids);
const out = repo.bisectSpan(gpa, bad_rids, good_rids, skip_rids) catch |e| switch (e) {
error.OutOfMemory => return bisectOom(streams),
error.InvertedMarks => return bisectDiag(streams, "the bad check-in is an ancestor of a good check-in; the marks are inverted"),
error.UnrelatedHistories => return bisectDiag(streams, "the good and bad marks share no common history"),
};
// Persist the validated state durably BEFORE the move (B-bisect-6): a crash
// leaves the marks recorded and the probe re-derivable.
if (persist) {
bisect.write(gpa, io, root_dir, start, bad_hashes, good_hashes, skip_hashes) catch |e|
return bisectStateFail(streams, e);
}
if (out.probe) |probe| {
const target = repo.hashOf(probe);
update.applyCheckin(gpa, io, root_dir, log, target, .inherit, .inherit) catch |e| return bisectMoveFail(streams, e);
streams.out.print(
"bisect: {d} untested candidate(s) remain; testing {s}\n",
.{ out.untested, bisectShort(target) },
) catch {};
return .ok;
}
return bisectAnnounceCulprit(gpa, io, repo, root_dir, log, streams, out.culprit);
}
/// Termination (B-bisect-4): move the checkout to the culprit and announce it
/// with its comment line. The session stays recorded until `reset`.
fn bisectAnnounceCulprit(
gpa: std.mem.Allocator,
io: std.Io,
repo: *Repository,
root_dir: std.Io.Dir,
log: *logstore.LogStore,
streams: cli.Streams,
culprit: Repository.Rid,
) cli.Exit {
const target = repo.hashOf(culprit);
update.applyCheckin(gpa, io, root_dir, log, target, .inherit, .inherit) catch |e| return bisectMoveFail(streams, e);
// The comment borrows the manifest bytes, so print before it is freed; the
// override value borrows tagxref bytes valid for the repo's lifetime.
var maybe = repo.manifest(gpa, culprit) catch |e| switch (e) {
error.OutOfMemory => return bisectOom(streams),
else => return bisectDiag(streams, "cannot read repository: repository is corrupt"),
};
defer if (maybe) |*m| m.deinit(gpa);
const manifest_comment: []const u8 = if (maybe) |m|
(if (m.manifest.c) |c| firstCommentLine(c.comment) else "")
else
"";
const comment = repo.override(culprit, .comment, manifest_comment);
streams.out.print("bisect: {s} is the first bad check-in\n", .{bisectShort(target)}) catch {};
streams.out.print(" {s}\n", .{comment}) catch {};
return .ok;
}
/// `zit bisect next`: re-derive and re-announce the current probe, moving the
/// checkout to it. Refuses with no session or with only one endpoint (B-bisect-13).
fn bisectNext(
gpa: std.mem.Allocator,
io: std.Io,
repo: *Repository,
root_dir: std.Io.Dir,
streams: cli.Streams,
) cli.Exit {
var sess_opt = bisect.read(gpa, io, root_dir) catch |e| return bisectStateFail(streams, e);
defer if (sess_opt) |*s| s.deinit();
const s = sess_opt orelse return bisectNoSession(streams);
if (s.bad.len == 0 or s.good.len == 0) {
const missing = if (s.bad.len == 0) "bad" else "good";
streams.err.print("zit bisect: mark a {s} check-in before running 'zit bisect next'\n", .{missing}) catch {};
return .failure;
}
return bisectAdvance(gpa, io, repo, root_dir, streams, s.start, s.bad, s.good, s.skipped, false);
}
/// `zit bisect status`: report the marks, the current probe, and the remaining
/// count without moving (B-bisect-7). Never refuses on a dirty tree; with no
/// session it is exit 1, nothing mutated.
fn bisectStatus(
gpa: std.mem.Allocator,
io: std.Io,
repo: *Repository,
root_dir: std.Io.Dir,
streams: cli.Streams,
) cli.Exit {
var sess_opt = bisect.read(gpa, io, root_dir) catch |e| return bisectStateFail(streams, e);
defer if (sess_opt) |*s| s.deinit();
const s = sess_opt orelse return bisectNoSession(streams);
for (s.bad) |h| streams.out.print("bisect: bad {s}\n", .{bisectShort(h)}) catch {};
for (s.good) |h| streams.out.print("bisect: good {s}\n", .{bisectShort(h)}) catch {};
for (s.skipped) |h| streams.out.print("bisect: skip {s}\n", .{bisectShort(h)}) catch {};
if (s.bad.len == 0 or s.good.len == 0) {
const other = if (s.bad.len == 0) "bad" else "good";
streams.out.print("bisect: mark a {s} check-in to begin bisecting\n", .{other}) catch {};
return .ok;
}
const bad_rids = bisectRids(gpa, repo, s.bad) catch |e| switch (e) {
error.OutOfMemory => return bisectOom(streams),
error.Missing => return bisectInconsistent(streams),
};
defer gpa.free(bad_rids);
const good_rids = bisectRids(gpa, repo, s.good) catch |e| switch (e) {
error.OutOfMemory => return bisectOom(streams),
error.Missing => return bisectInconsistent(streams),
};
defer gpa.free(good_rids);
const skip_rids = bisectRids(gpa, repo, s.skipped) catch |e| switch (e) {
error.OutOfMemory => return bisectOom(streams),
error.Missing => return bisectInconsistent(streams),
};
defer gpa.free(skip_rids);
const out = repo.bisectSpan(gpa, bad_rids, good_rids, skip_rids) catch |e| switch (e) {
error.OutOfMemory => return bisectOom(streams),
error.InvertedMarks => return bisectDiag(streams, "the bad check-in is an ancestor of a good check-in; the marks are inverted"),
error.UnrelatedHistories => return bisectDiag(streams, "the good and bad marks share no common history"),
};
if (out.probe) |probe| {
streams.out.print(
"bisect: testing {s} ({d} untested candidate(s) remain)\n",
.{ bisectShort(repo.hashOf(probe)), out.untested },
) catch {};
} else {
streams.out.print("bisect: {s} is the first bad check-in\n", .{bisectShort(repo.hashOf(out.culprit))}) catch {};
}
return .ok;
}
/// `zit bisect reset`: restore the starting check-in, remove `.zit-bisect`, exit 0
/// (B-bisect-8). No session is exit 1; a corrupt file is cleared (reset is the
/// advertised recovery, B-bisect-6). The restore move rides the update engine and
/// is refused over a dirty tree (B-bisect-9).
fn bisectReset(
gpa: std.mem.Allocator,
io: std.Io,
repo: *Repository,
root_dir: std.Io.Dir,
streams: cli.Streams,
) cli.Exit {
var sess_opt = bisect.read(gpa, io, root_dir) catch |e| switch (e) {
error.Corrupt => {
// reset IS the recovery: clear the damaged file rather than deadlock.
bisect.clear(io, root_dir);
streams.out.writeAll("bisect: cleared corrupt bisect state (working tree not restored)\n") catch {};
return .ok;
},
else => return bisectStateFail(streams, e),
};
defer if (sess_opt) |*s| s.deinit();
const s = sess_opt orelse return bisectNoSession(streams);
const log = repo.logStore(gpa) catch |e| return repoOpenFail(streams, "bisect", e);
update.requireCleanTree(gpa, io, root_dir, log) catch |e| switch (e) {
error.WorktreeNotClean => return bisectDiag(streams, "working tree is not clean"),
else => return bisectMoveFail(streams, e),
};
if (s.start.len != 0) {
update.applyCheckin(gpa, io, root_dir, log, s.start, .inherit, .inherit) catch |e| return bisectMoveFail(streams, e);
bisect.clear(io, root_dir);
streams.out.print("bisect: reset; working tree restored to {s}\n", .{bisectShort(s.start)}) catch {};
} else {
bisect.clear(io, root_dir);
streams.out.writeAll("bisect: reset\n") catch {};
}
return .ok;
}
/// Render one `ApplyError` through `bisectMoveFail` into `buf`.
fn bisectFailText(buf: []u8, err: update.ApplyError) []const u8 {
const rendered = commitMapCapture(bisectMoveFail, .{err}).err;
std.debug.assert(rendered.len <= buf.len);
@memcpy(buf[0..rendered.len], rendered);
return buf[0..rendered.len];
}
// `zit bisect` moves the working tree through the SAME `update.applyCheckin`
// engine as update, open and merge, so it reaches `StateRecordInvalid` on the
// same intact-clone artifacts they do. It is the fourth mapper of that one
// error set and must make the same distinction they make.
test "bisect: the two read-path failures do not share a diagnostic" {
var a: [256]u8 = undefined;
var b: [256]u8 = undefined;
const corrupt = bisectFailText(&a, error.Corrupt);
const state = bisectFailText(&b, error.StateRecordInvalid);
try std.testing.expect(!std.mem.eql(u8, corrupt, state));
try std.testing.expect(std.mem.indexOf(u8, corrupt, "corrupt") != null);
try std.testing.expect(std.mem.indexOf(u8, state, "corrupt") == null);
}