3.19 Bisecting

Bisecting is an efficient means of finding the earliest revision that introduced a bug known to exist in some later revision. Given a set of “good” earlier revisions that do not contain the bug and a set of “bad” later revisions that do contain the bug bisect performs a binary search over the set of revisions between these two sets to identify the specific revision that introduced the bug.

Bisection is started by marking revisions with the bisect good and bisect bad commands. Once both good and bad revisions have been specified the set of candidate revisions between the good and bad revisions is determined. The midpoint of this set is selected as the next revision to be tested and the workspace is updated to this selected revision. After the selected revision has been tested bisection continues when the revision is marked with bisect good or bisect bad. If the selected revision is marked as good, it and all of its ancestors are considered to be good and excluded from the remaining search set. If the selected revision is marked as bad, all of its descendants are considered to be bad and excluded from the remaining search set. After each selected revision is marked as good or bad the size of the remaining search set is halved.

Revisions that are untestable for some reason (e.g. they don’t compile) may be ignored with the bisect skip command. This excludes the specified revisions from the candidate set and allows the bisection operation to continue. Skipping revisions may cause the search to fail or end on the wrong revision if the revision being searched for is skipped.

If the workspace is updated to some unrelated revision during a bisection operation the bisect update command can be used to update back to the next revision selected for bisection. This command can also be used if a previous bisect good, bisect bad or bisect skip command fails to update the workspace due to the existence of conflicting unversioned paths.

The current status of the bisection operation and the next revision to be tested is reported by the bisect status command. This command can be run at any stage of the bisection operation to see how many revisions remain to be tested and how many revisions have been ruled out.

Currently bisect updates the workspace but does not update the workspace branch option. This may leave the workspace at a revision that is not in the branch specified by the workspace branch option and cause subsequent commits to be made to the wrong branch. To help avoid this error the status command will indicate when the workspace branch does not match any of the parent revision branches. Take care when committing new revisions during a bisection operation and be sure to use the bisect reset command once the bisection is complete to update the workspace back to the revision from which the bisection started.

The bisection operation completes successfully when the last remaining revision is marked as “bad”. If the last remaining revision is marked as “good” the bisection fails without finding the initial bad revision.

Once bisection is complete the workspace can be updated back to the starting revision with the bisect reset command. This command also removes all stored bisection information in preparation for future bisect operations.