Bisect

Submitted by sle on Sat, 07/28/2012 - 11:25

Update

The "run" command in per version control bisect commands such as "git bisect" and "svn-bisect" are probably what you want if searching for version control revision numbers.

Overview

Bisect is a small shell script that performs an arbitrary binary search given a command that fails or succeeds as a function of a number passed to it. Bisect finds the boundary between success and failure as a function of that number. Bisect is similar to utilities such as svn-bisect, but is not specialized.

You can download it here.

Examples

Given the range [1, 100] and the following if statement:

bisect -v 1 100 '(if [[ $num -ge 50 ]]; then exit 0; else exit 1; fi)'

bisect outputs that lo is 49 and hi is 50 meaning that between 49 and 50 there is an inflection point where the command changes from failing to succeeding.

The same solution is found if the return of the if statement is reversed:

bisect -v 1 100 '(if [[ $num -ge 50 ]]; then exit 1; else exit 0; fi)'

A more useful example is finding the revision of a file that meets some criteria. For example to find the SVN revision that introduced a particular string in a file something like the following could be done:

bisect -v 1 $(svn info JCols.java | grep ^Revision: | awk '{print $2}') 'svn cat -r $num JCols.java | grep -q "Read from an input file"'

In the above the goal is to find the SVN revision where Read from an input file is introduced, which is tested by grep, in file JCols.java. The arguments to bisect in this case are:

 -v               Verbose.
 1                The lower bound of the search.  This is the lowest possible SVN revision.
 $( ... )         Command that expands to the current SVN revision.  This is the highest possible SVN revision.
 'svn cat ... '   Command that either fails or succeeds as a function of $num passed to it.  In this case it succeeds if 
                  "Read from  an input file" is in JCols.java for revision $num.

It's possible to use svn blame for the above in many cases, but often subsequent revisions make it difficult. The above can also be extended to performing arbitrary tests on the file.