Bisect

bisect <bitstring>

Print a subset of the lines on the stardard input based on the bitstring argument. The bitstring should be any number of '0' or '1' characters. The first character will print half the lines of STDIN (the first half for 0, or the second half for 1). Each additional digit will "add in" half of the remaining lines, with a 0 or 1 indicating which half.

By progressively adding digits you can bisectively rebuild the original input, excluding a smaller subset each time.

This can be useful for debugging: for example including progressively larger subsets of a test suite, included libraries, or other list where an unknown element of the list is causing a problem.

Example

Consider this eight-line text file: $ cat testfile 01-alpha 02-bravo 03-charlie 04-delta 05-echo 06-foxtrot 07-golf 08-hotel

Running bisect 0 < testfile will print the first half of the input: $ bisect 0 < testfile 01-alfa 02-bravo 03-charlie 04-delta

Suppose that worked, and you want to try including two more lines.

Running bisect 00 < testfile will print the first quarter of the file: $ bisect 00 < testfile 01-alfa 02-bravo

If that didn't work, you might try:

bisect 01 < testfile

which prints the second quarter:

$ bisect 01 < testfile 03-charlie 04-delta

Proceeding to bisect 010 < testfile would print the 3rd 8th (just line 3, in this case): $ bisect 010 < testfile 03-charlie

If that works, you have identified 03-foxtrot as the "problematic" entry in your original list.

The general principle is to use bisect in some kind of shell one liner or throwaway script and run it successively, adding 0s when things work, and toggling the last 0 to a 1 when they break.

Experimenting

The behavior of bisect can be unintuitive at first. To get a feel for it, it can help to run through a sample file, building up the selection string to see what gets selected.

For a long list, the comm (common entries) command combines well with bisect to help identify the excluded line(s).

$ comm testfile2 <(bisect 101 < testfile2)` abrupt clam cloth eggs elfin fanatical future giants glow group guess messy object puncture replace silk special sticks store thoughtless troubled unable zippy zoom

Invert

Because the case of needing a growing list of test entries is a common one, bisect has an --invert flag, which simply suppresses the selected lines, rather than selectively printing them.

Compare $ bisect 01 < testfile 03-charlie 04-delta

with

$ bisect -i 01 < testfile 01-alfa 02-bravo 05-echo 06-foxtrot 07-golf 08-hotel

Motivation

Including progressively larger inputs until a bug is reproduced is often a useful way to isolate bugs. bisect can be used to take a list of inputs and quickly search through them until the problem input is located.

In extreme cases, bugs might only be exhibited when 2 particular inputs appear together. In this case, bisect can be used to isolate one of the inputs, and then used in concert with cat to find its troubled companion.

Specifically, the author has had trouble with test cases in Ruby, where a single test fails when run with the whole suite but not in isolation, because another test alters some global state. bisect can be used to identify another test that manipulates the state which can be instructive as to what's being changed and needs to be properly isolated.

The motivating case for bisect was a game that shipped with pre-built libraries, without which, it crashed, but with all included also crashed. bisect helped identify the subset of shipped libraries that had to be in LD_LIBRARY_PATH to run the game.