Bisect Over a Rewritten History

Bisect answers a question that neither the log nor the diff can: which commit first introduced a behaviour. It does so by testing commits rather than reading them, and its correctness depends entirely on an assumption that history rewriting quietly violates — that the commits it walks form a single ordered sequence in which the property under test is monotone.

The set being searched

git bisect start <bad> <good> establishes two commits and computes the set of candidates: commits reachable from the bad commit but not from any good one. That set is the search space, and it is not necessarily a path. On a linear history it is a chain and the search is an ordinary binary search over it. On a merge-heavy history it is a subgraph, and the first thing bisect does is count its size.

git bisect start without arguments uses HEAD as bad and asks for a good commit. The candidate count is printed so that the number of remaining steps is predictable: bisect reports roughly log2(n) steps, and it reports a running estimate after each test.

A good commit need not be an ancestor of the bad one in the graph sense that a naive reader assumes. What matters is reachability: if a commit is marked good, every commit reachable from it is excluded from the candidate set, which is how a single good mark can eliminate an entire branch that was merged in.

The search is over commits, weighted so that each step halves the number of candidates. With a linear history the midpoint is unique. With a graph the midpoint is chosen to balance the two sides, which sometimes means selecting a commit that is not on the first-parent line at all.

Monotonicity and why merges break it

The premise of bisect is that there is a threshold: all commits before it are good, all after are bad. Binary search is only correct under that premise. On a graph, “before” and “after” are partial orders, and the property can hold on one branch and fail on another in ways that have no single threshold.

A concrete shape: a regression is introduced on a feature branch and fixed before that branch is merged. The merge commit is good, the branch’s tip is good, and the intermediate commits on the branch are bad. No linear order makes this monotone, and bisect will report one of the intermediate commits — correctly, in the sense that it is the first commit where the property fails along some path, but not usefully, because the regression never reached the main line.

The usual mitigation is --first-parent. Restricting the search to the first-parent chain treats each merged branch as a single unit, so the search finds the merge that introduced the regression rather than the commit inside the branch. The result names the integration, and the follow-up is to bisect within that branch, which is a much smaller set. git bisect start --first-parent applies this from the beginning.

The trade is that the first-parent restriction cannot find a regression that was introduced by a commit which was later amended in place during a merge resolution. The resolution lives in the merge commit, so the merge is the answer, and the individual commit that caused the problem is not recoverable by bisect at all.

Rewritten history and the stale-commit problem

A rebase replaces commits. The old ones remain reachable through the reflog for a while, and any bisect started before the rebase holds ids that are no longer in the branch’s ancestry.

Three failures follow. A bisect session stores its state in files under the git directory, including the bad and good ids; if the branch is rebased mid-session, the ids still resolve as objects but they are no longer connected to the current tip, so the search proceeds over a graph that the branch no longer has. Checking out those commits produces a working tree that does not correspond to any state the branch ever had after the rewrite. The result is a commit id that does not exist in the branch’s current history.

The second failure is subtler. A commit that was rebased had its conflict resolutions folded into it, and those resolutions were never part of the original commit. If a regression came from a resolution rather than from the authored change, bisecting the rewritten history finds the rewritten commit, and its diff includes the resolution. That is arguably the right answer, since the rewritten commit is what actually landed, but it means the commit’s author did not write the change that caused the problem, and any investigation that starts from the author’s intent will go wrong.

The third is that a squash collapses boundaries. If ten commits became one, bisect over the result can only point at the single squashed commit, and the sub-change responsible is not separable without reading the diff. The information needed to narrow further was destroyed by the squash, which is the strongest practical argument against collapsing a series before it is known to be correct.

Testing commits that cannot build

A bisect step checks out a commit and runs a test. Not every commit in the range can be tested: a commit in the middle of a refactor may not compile, or may depend on a change that arrived later in the series. Marking such commits skip removes them from the candidate set without asserting anything about the property, and the search continues over the remainder.

Skips degrade the search. Each skip reduces the candidate count by one rather than by half, so a range with many untestable commits approaches a linear scan. A bisect that reports “roughly N steps remaining” will understate the real count once skips begin.

The remedy is to make commits individually testable, which is a property of how history was authored rather than of bisect. A series in which each commit builds and passes its own tests allows a full binary search; a series in which only the tip builds forces a scan or a guess. This is the same requirement that makes a bisect result attributable: if the commits are not independently meaningful, the commit the search lands on is not a meaningful unit of cause.

git bisect run <command> automates the loop. The command’s exit status decides the mark: zero is good, 125 is skip, and any other non-zero value is bad. The 125 convention exists precisely for the untestable case, and a script that returns an arbitrary failure code for a build error will be interpreted as evidence that the commit is bad, poisoning the search. Distinguishing “the test failed” from “the test could not run” is the entire discipline of a bisect script.

#!/bin/sh
# exit 125 means "cannot decide", never "bad"
make -s || exit 125
./run-target-test || exit 1
exit 0

Cost and termination

The number of tests is bounded by the candidate count: about log2(n) for a clean run, and up to n in the worst case with skips. Each test costs a checkout plus whatever the verification costs, so the wall-clock time is dominated by the verification, not by the search. A test that takes minutes makes a thirty-step bisect take an hour; a test that takes seconds makes it trivial. Reducing the test to the smallest reproduction is therefore the highest-leverage step, and it is usually done before the bisect rather than during it.

Checkout cost is not negligible on large repositories. Checking out a commit rewrites the working tree to match its tree, touching every file that differs from the previous checkout. A bisect over a range that changes many files performs a large amount of filesystem work per step, and on a repository with a slow filesystem this can dominate. Keeping the working tree small, or bisecting in a separate worktree, changes the constant substantially without changing the algorithm.

A partial clone adds a different cost: a checkout that needs blobs the clone does not have triggers a fetch per missing object unless the fetch is batched. Bisecting in a blob-less clone is possible but the network traffic per step can exceed the local work by orders of magnitude, which is why the usual arrangement is a full clone for the bisect and a filtered clone for routine browsing.

Reading the result

Bisect terminates when the candidate set has one element, and reports it as the first bad commit. The claim is narrower than it sounds: the commit is the first one in the searched set, along a path the algorithm chose, at which the test fails. It is not necessarily the commit that introduced the defect in a causal sense. If the test is flaky, the answer is noise. If the test’s failure depends on two commits jointly, no single commit is the cause and the search will still name one.

Two checks make the result usable. First, verify the reported commit in isolation: check it out, apply the test, confirm it fails, then check out its parent and confirm the test passes. Bisect performs an equivalent check internally, but a manual confirmation on a clean tree rules out local state. Second, read the diff. The commit’s change is the candidate cause, and the diff either explains the failure or reveals that the cause is elsewhere — typically in an interaction the test does not isolate.

The git bisect visualize command, and the log it prints when no visualiser is configured, shows the remaining candidates with the tested ones marked. When the search ends on a merge or on a commit whose diff looks unrelated, that view is what reveals the monotonicity assumption was violated.

Bisect also composes with the storage layer in a way that matters for reproducibility. The search assumes the objects it checks out are the ones the branch had; a history that was rewritten, squashed, or filtered changes what is available. The identity rules that make a rewritten commit a different object are set out in what a commit contains, and the way missing objects surface as fetch-on-demand behaviour is covered in packfiles, delta chains, and garbage collection. A bisect is only as trustworthy as the history it is given, and that history is a product of every composition and rewriting decision made before it ran.