Tropical Software Observations

25 February 2013

Posted by Heath Basurto

at 2:26 PM



git bisect finds code that introduced regressions

From time to time while developing software, especially on a large project, you find a regression some time after it was introduced. Maybe introduced by someone else on the team. Maybe 50 or 100 commits after it was introduced. For example, perhaps Internet Explorer is buggy and one of our stylesheet changes broke it.  We just don't know when the regression was introduced, or exactly what code is causing it. In an ideal world we would have had adequate tests in place to reach that coveted '100% test coverage.' But back in the real world we often have to work with software that doesn't have tests in place, or is minimally tested, or just can't be easily tested.  Like the browser example.

One thing we could do is use git blame. Git blame basically allows us to know who and which commit added what to which file.

$ git blame Gemfile
^c4edf42 (Paul  2013-02-13 10:31:24 +0900  1) source :rubygems
1517dfc4 (Heath 2013-02-13 11:43:05 +0800  2) 
1517dfc4 (Heath 2013-02-13 11:43:05 +0800  3) gem "sinatra", :require => "sinatra/base"
1517dfc4 (Heath 2013-02-13 11:43:05 +0800  4) gem "sinatra-contrib"
git blame shows you which commits contributed to the final outcome of a file.

This is indeed useful in many situations, but in the course of development we find that sometimes we can observe the behavior changing, but we don't know what code caused the behavior change. In this case git blame will do us little good.

In more advanced cases, specifically when these two conditions are met:
  1. You can identify the functionality that is broken.
  2. You can not identify the code that was changed in the past that broke the functionality.

What we could do is blindly revert back to a previous commit, not knowing how far back it goes, one by one, until we uncover where the commit is that causes the regression to disappear.
Though consider this, in large projects where commits are small you will have many. Not a handful. You may have hundreds or even thousands of commits to sift through! Your database has to be migrated to match the new commit each time. There may be other setup required, like old services and externals that your software relied on. You want to reduce your O(n) search down. The best we're going to get here is a binary search. O(log n)

So if we implemented the search ourselves we would need to divide the search space in half and put one half on a different branch from the other half. Then continue to divide each branch into smaller branches and repeat until there's a single commit at the end of the tree. Then we'd follow the tree either down the left or right side depending on if we can see the functionality changes. For example, we go to commit #50 of 100. We run our app and we see that the functionality is fixed. So now we know the commit is greater than #50. We continue to #75 and test again. We see the functionality is buggy again at this point. We know now it's between #50 and #75. We could repeat until we find the commit which will show us exactly the causative link. Continue reading for a better solution.

Because this is exactly what git bisect is for. It automates the process by checking out specific commits and performing a binary search on your commit history. To use git bisect first use git bisect start

$ git bisect start
Next we should specify the most recent commit where the functionality was bad with git bisect bad
$ git bisect bad
git bisect bad should generally be used on the head of the branch the issue is on

Now mark the earliest commit known to not have the software defect with git bisect good [SHA]

$ git bisect good 5d1f0ddc72b791b391bce2df1fa59f55a7a25129
Bisecting: 3 revisions left to test after this (roughly 2 steps)
[3a278003eade29adf10f3dc8357b70f51cd6c9cf] Merge remote-tracking branch 'origin/master'
You can also use tags and if you've been tagging your software correctly could specify the version number, or milestone without needing to look up the SHA

git bisect gives us information on how many more times it estimates it'll need to test using the binary search, and which commit is currently being tested. Each step along the way you'll need to either issue a git bisect good or git bisect bad to specify that the problem either is resolved at this commit or it's still there. After issuing this command for the last time you'll see this:

$ git bisect good
d0fd1a64162b4bcc49f5f8d0e81f73a4da3b736f is the first bad commit
That's all there is to it. We now know exactly which commit caused the issue. We can examine the code there and we know the causative change that caused the defect in our software. Oh, and you'll need to issue git bisect reset after you're finished.