Large, complex, cross-platform applications with multiple developers sometimes have bugs. Some of those bugs never appear on your own machine; they lurk for a while until someone else builds and tests the software on a different platform, in different circumstances.

Tracing that bad behavior back to a particular checkin can be frustrating, even if you have a huge smoke farm that rigorously tests every configuration of every checkin on every important platform.

Parrot meets all of those criteria, except for the huge smoke farm. (Smokers welcome.) When I want to pinpoint a regression to a likely checkin culprit, I use a binary search. Will Coleda’s App::SVNBinarySearch promises to automate that process. Here’s what I found.

Usage

Installation is reasonably easy, from the CPAN shell. There are a few dependencies. Also note that you must have a Subversion client installed on your machine, along with read access to the repository which you want to search.

The module itself mostly exists to install the program svn_binary_search, which does the real work.

Within a pristine Subversion checkout of the project you wish to search (I recommend a clean checkout in its own directory), run svn_binary_search with a range of revision numbers to search and the path to a shell script to build and test the checkout.

I know that sounds a bit confusing. It’s actually pretty simple.

The program checks all of the revisions within the range you give it with a binary search. Think of this as the number guessing game. If I think of a number between 1 and 128, you guess 64 and ask me if your guess is equal to or higher or lower than my number. If it’s higher, guess 96 (halfway between 64 and 128). If it’s lower, guess 32 (halfway between 64 and 1). Continue guessing the halfway point until you find the exact number.

Of course, identifying the exact number in a Subversion checkout is somewhat trickier. That’s the purpose of the shell script. All this script has to do is give a true or false exit code. Everything else depends on the question you’re asking. In my case, that question was “Does this Parrot checkout pass a particular test?”, as that test recently started to segfault on one machine and I couldn’t easily figure out why.

I created a shell script that cleaned up from any previous build, re-configured and rebuilt Parrot, and ran the test. svn_binary_search works best when there’s a single state transition within the revision range; either the test started to pass at a single point in that range or it started to fail.

The results were interesting. At first, I had strange error messages. My command line looked like:

$ svn_binary_search -r 19000:19700 -c find_shootout_failure.sh

After a few moments of confusion, I changed the final argument to include a path to my shell script:

$ svn_binary_search -r 19000:19700 -c ./find_shootout_failure.sh

After that, the program runs along, hopefully finally finding the single revision where the test script’s exit code changes.

Problems can occur, however. If there were a lot of additions or deletions or moves, sometimes the underlying Subversion application can get confused and decide not to continue. (The error message will say something about trying to add a file where one exists.) It would be nice if the program could delete these files, or always create new checkouts (time- and network-consuming), or at least detect this condition and offer the chance to restart after human intervention to fix the problem.

I ran into that in a couple of cases. However, having such a wide range of checkouts may not have helped. Ideally, I wouldn’t have to search more than a hundred revisions at once. Note that performing a binary search of a hundred revisions is easier and faster than performing a binary search of a thousand.

If you do use this application to search a project that requires a compiler, I highly recommend the use of ccache, especially if you’ve already used it to build the software you’re searching. The faster the compile, the easier it is to narrow down the problem.

Overall, the time it took to install and understand how to use this program paid off in the time it saved by using it only once. Despite a few fixable points, I highly recommend it for developers trying to track down that one little bug. In particular, the flexibility of writing a shell script (or other executable program) is impressively useful.