The git bisect command is an excellent tool to find which commit caused a bug in the repository. The tool is particularly useful if you are looking at a long list of commits that may contain the bug. The bisect command performs a binary search through the commit history to find the commit that introduced the bug as fast as possible. The binary search method, or bisection method as it is also called, is a search method where an algorithm finds the position of a key in a sorted array. In each step of the algorithm, the key is compared to the middle value of the array and if they match, the position is returned. Otherwise, the algorithm repeats its search in the subarray to the right or left of the middle value, depending on whether the middle value was greater or lower than the key. In the Git context, the list of commits in the history makes up for the array of values to be tested, and the key can be a test if the code can be complied successfully at the given commit. The binary search algorithm has a performance of 
.
We'll use the same repository as seen in the last example, but from a clean state:
$ git clone https://github.com/dvaske/cookbook-tips-tricks.git $ cd cookbook-tips-tricks $ git checkout bug_hunting
The bug_hunting branch contains 23 commits since it branched off from the master branch. We know that the tip of the bug_hunting branch contains the bug and it was introduced in some commit since it branched off from master. The bug was introduced in the following commit:
commit 83c22a39955ec10ac1a2a5e7e69fe7ca354129af Author: HAL 9000 <[email protected]> Date: Tue May 13 09:53:45 2014 +0200 Bugs...
The bug is easily seen in the map.txt file in the middle of Australia. The following snippet of the file shows the bug:
_,__ .: Darwin <* / | .-./ |. : :, / '-._/ \_ / ' .' \__/ *: Brisbane .-' (oo) ; | //||\ | / | / Perth * __.--._ / _.' :. | >__,-' \_/*_.-' Melbourne snd :--, '/
Now, all we need is some way to reproduce/detect the bug so we can test the different commits. This could, for example, simply be to compile the code, run tests, and so on. For this example, we'll create a test script to check for bugs in the code (a simple grep for oo should do it in this example; see for yourself if you can find the bug in the map.txt file):
echo "! grep -q oo map.txt" > ../test.sh chmod +x ../test.sh
It is best to create this test script outside the repository to prevent interactions between checkouts, compilation, and so on in the repository.
To begin bisecting, we simply type:
$ git bisect start
To mark the current commit (HEAD -> bug_hunting) as bad, we type:
$ git bisect bad
We also want to mark the last known good commit (master) as good:
$ git bisect good master Bisecting: 11 revisions left to test after this (roughly 4 steps) [9d2cd13d4574429dd0dcfeeb90c47a2d43a9b6ef] Build map part 11
This time, something happened. Git did a checkout of 9d2cd13, which it wants us to test and mark as good or bad. It also tells us there are 11 revisions to test after this and it can be done in approximately four steps. This is how the bisecting algorithm works; every time a commit is marked as good or bad, Git will checkout the middle one between the just marked one and the current one of opposite value. In this way, Git quickly narrows down the number of commits to check. It also knows that there are approximately four steps, and this makes sense since with 11 revisions left, the maximum number of tries is 
before the faulty commit is found.
We can test with the test.sh script we created previously, and based on the return value, mark the commit as good or bad:
$ ../test.sh; test $? -eq 0 && git bisect good || git bisect bad # git bisect good Bisecting: 5 revisions left to test after this (roughly 3 steps) [c45cb51752a4fe41f52d40e0b2873350b95a9d7c] Build map part 16
The test marks the commit as good and Git checks out the next commit to be marked, until we hit the commit that introduces the bug:
$ ../test.sh; test $? -eq 0 && git bisect good || git bisect bad # git bisect bad Bisecting: 2 revisions left to test after this (roughly 2 steps) [83c22a39955ec10ac1a2a5e7e69fe7ca354129af] Bugs... $ ../test.sh; test $? -eq 0 && git bisect good || git bisect bad # git bisect bad Bisecting: 0 revisions left to test after this (roughly 1 step) [670ab8c42a6cb1c730c7c4aa0cc26e5cc31c9254] Build map part 13 $ ../test.sh; test $? -eq 0 && git bisect good || git bisect bad # git bisect good 83c22a39955ec10ac1a2a5e7e69fe7ca354129afis the first bad commit commit 83c22a39955ec10ac1a2a5e7e69fe7ca354129af Author: HAL 9000 <[email protected]> Date: Tue May 13 09:53:45 2014 +0200 Bugs... :100644 100644 8a13f6bd858aefb70ea0a7d8f601701339c28bb0 1afeaaa370a2e4656551a6d44053ee0ce5c3a237 M map.txt
After four steps, Git has identified the 1981eac1 commit as the first bad commit. We can end the bisect session and take a closer look at the commit:
$ git bisect reset Previous HEAD position was 670ab8c... Build map part 13 Switched to branch 'bug_hunting' Your branch is up-to-date with 'origin/bug_hunting'. $ git show 83c22a39955ec10ac1a2a5e7e69fe7ca354129af commit 83c22a39955ec10ac1a2a5e7e69fe7ca354129af Author: HAL 9000 <[email protected]> Date: Tue May 13 09:53:45 2014 +0200 Bugs... diff --git a/map.txt b/map.txt index 8a13f6b..1afeaaa 100644 --- a/map.txt +++ b/map.txt @@ -34,6 +34,6 @@ Australia: .-./ |. : :, / '-._/ \_ / ' - .' *: Brisbane - .-' ; - | | + .' \__/ *: Brisbane + .-' (oo) ; + | //||\ |
Clearly, there is a bug introduced with this commit.
The following annotated screenshot shows the steps taken by the bisect session:
Note that the bisection algorithm actually hits the faulty commit in the third step, but it needs to look further to make sure that the commit isn't just a child commit of the faulty commit, and in fact is the commit that introduced the bug.
Instead of running all the bisecting steps manually, it is possible to do it automatically by passing Git a script, makefile, or test to run on each commit. The script needs to exit with a zero-status to mark a commit as good and a non-zero status to mark it as bad. We can use the test.sh script we created at the beginning of this chapter for this. First, we set up the good and bad commits:
$ git bisect start HEAD master Bisecting: 11 revisions left to test after this (roughly 4 steps) [9d2cd13d4574429dd0dcfeeb90c47a2d43a9b6ef] Build map part 11 Then we tell Git to run the test.sh script and automatically mark the commits: $ git bisect run ../test.sh running ../test.sh Bisecting: 5 revisions left to test after this (roughly 3 steps) [c45cb51752a4fe41f52d40e0b2873350b95a9d7c] Build map part 16 running ../test.sh Bisecting: 2 revisions left to test after this (roughly 2 steps) [83c22a39955ec10ac1a2a5e7e69fe7ca354129af] Bugs... running ../test.sh Bisecting: 0 revisions left to test after this (roughly 1 step) [670ab8c42a6cb1c730c7c4aa0cc26e5cc31c9254] Build map part 13 running ../test.sh 83c22a39955ec10ac1a2a5e7e69fe7ca354129afis the first bad commit commit 83c22a39955ec10ac1a2a5e7e69fe7ca354129af Author: HAL 9000 <[email protected]> Date: Tue May 13 09:53:45 2014 +0200 Bugs... :100644 100644 8a13f6bd858aefb70ea0a7d8f601701339c28bb0 1afeaaa370a2e4656551a6d44053ee0ce5c3a237 M map.txt bisect run success
Git found the same commit and we can now exit the bisecting session:
$ git bisect reset Previous HEAD position was 670ab8c... Build map part 13 Switched to branch 'bug_hunting'