Part of resolving a bug is finding where and when that bug was introduced into your code. Not so much for blaming a specific person, but more for an understanding of how and maybe why the bug was introduced; and more over which versions of your app are affected.
Most of the time the bug was recently introduced and your CI notified you that stuff has been broken.
In order to find out when, how and by whom the build was broken, you’ll have to dig into your git history and run your specs to see if they pass or not.
Running your specs for every commit in your history manually is very time consuming and boring. Luckily there are better ways, using plain old git.
Binary search#
Before I dive into git, it’s important you understand how binary search works. If you already know this stuff, skip right to the next section.
You have a sorted array. This means there is some order to the elements you have. Presume you have an array of ints:
a = [1, 3, 4, 7, 33, 42, 54, 76, 89, 91]
Now, we want to find the position (n) of 7 in this array using binary search so that a[n] == 7.
Binary search uses a divide and conquer strategy. You split the array in the middle. We have 10 elements, so a logical place would be to split the array at position n = 5, which has the value 42.
Comparing 7 <=> 42 tells us that, because we have an ordered array, the value 7 should be in the first half of the array.
We can ignore the right half of the array for searching, and repeat this step for the left part, specifically:
[1, 3, 4, 7, 33]
So, let’s split this part up again. We get 4. This is less than 7, so if we continue looking we should take the right part.
[7, 33]
Okay, again, we continue our search. We know have to split the array one way or the other, and we end up picking n = 4. We hit 33. Surely the value of 7 must be on the left part of this.
Note that although I don’t show the whole array, I’m still using the index positions for the entire a array.
[7]
Now, there’s not much to pick for us. This is 7. Right here at n = 3. Done!
Notice that the last step does not involve checking the value of the last element. We only have 1 element left, so we’re finished.
If we had been looking for a value of 18, we would have also found n = 3. This means that we can search for non-existing values, which then return the index right before where that number should be inserted. This works because the array was ordered, so we can safely make such assumptions. Nice, huh?
How does binary search relate to finding bugs?#
Well, in the example above we were looking for an integer value. The test we use to evaluate is simple:
value <=> a[n]
When we want to find the commit that broke our build we need a more clever way of comparing values.
This is where your test suite comes in. You have a failing spec now, so basically we’re looking for the point in git history where that spec failed for the first time.
Git bisect#
Because it’s not feasible to do a linear search over your entire commit history, we’ll have to start by marking a good and a bad commit.
First we’ll have to find a location in your git history where you know the app did not exhibit this bug.
More than likely, this place is your last stable release. If you used git tag to tag your release, you should be able to find out quickly if that release contains the bug.
git checkout v1.2.1
rspec spec/features/fancy_spec.rb
=> 0 failures
Good. We now our latest commit was broken, so let’s get started with that binary search!
You don’t have to keep track of the git history and binary search position all by yourself: git does this for you. All you have to do is compare each commit that is presented to you with an expected result. E.g. does the fancy_spec.rb spec pass or not?
Bisecting steps#
First, let git know you want to do a binary search.
git bisect start
Next, let git know which commit is good, and which one is bad.
git bisect good v1.2.1
git bisect bad e8ab31
Git will respond with something like this:
Bisecting: 19 revisions left to test after this (roughly 4 steps)
[0e70ee6aefe428fa897ec7e48273c3fe4d0bf7fb] Did some funky stuff in `config/application.rb`.
Git has determined that commit 0e70ee is right in between v1.2.1 and ebab31. Check if this revision is broken and report back to git.
rspec spec/features/fancy_spec.rb
> 1 failure
git bisect bad
And git will respond:
Bisecting: 9 revisions left to test after this (roughly 3 steps)
You can continue this until git tells you the commit that first broke this spec.
When you’re done bisecting (or if you just feel like doing something else), just tell git:
git bisect reset
Usage in the field#
Git bisect is a very powerful tool to find specific points in your code.
In this example we were looking for a commit that broke a specific test. You can look for all kinds of things:
- When did the layout on that page break?
- At what point did we upgrade that gem to a buggy release?
- Who added this ugly piece of code?!
Doing a binary search over your git history is a fast and efficient way of finding these kind of things out.