Find the first line in the input file which causes the given command to fail. This assumes that there is a single insertion point, where running the command with any line before the insertion point will succeed, and running with the insertion point line or any subsequent line causes it to fail.

This is a general tool similar to git bisect, a Git built-in which can be used to determine which commit introduced a bug.

Since bisect.bash runs a binary search it should finish looking for the offending line in at most log_2(N)+2 tries (see tests).

./bisect.bash COMMAND FILE

COMMAND should reference a variable called ENTRY, referring to the piece of the input currently being processed.

FILE should be the path to a normal file with entries, each terminated by a newline character.

Prints the insertion point, if there is one:

$ printf '%s\n' 0 1 2 > input.txt
$ ./bisect.bash '(( "$ENTRY" == 0 ))' input.txt
1

Fails if there is no insertion point:

$ printf '%s\n' 0 1 2 > input.txt
$ ./bisect.bash '(( "$ENTRY" < 5 ))' input.txt
No insertion point found.
$ echo $?
3

Enable debug mode with DEBUG=1:

$ printf '%s\n' 0 1 2 > input.txt
$ DEBUG=1 ./bisect.bash '(( "$ENTRY" == 0 ))' input.txt >/dev/null
Remaining entry count: 3.
Remaining entry count: 2.
Remaining entry count: 1.
Number of entries checked: 3.

Enable trace mode with DEBUG=2:

$ printf '%s\n' 0 1 2 > input.txt
$ DEBUG=2 ./bisect.bash '(( "$ENTRY" == 0 ))' input.txt >/dev/null
Remaining entry count: 3.
First split file entry count: 2.
Second split file entry count: 1.
Checking entry: “1”.
Command failed.
Remaining entry count: 2.
First split file entry count: 1.
Second split file entry count: 1.
Checking entry: “0”.
Command successful.
Remaining entry count: 1.
First split file entry count: 1.
Checking entry: “1”.
Command failed.
Number of entries checked: 3.

Consider a situation where you have a reference to a commit in another repository, and you want to bump that commit to the latest version of the upstream repository. But HEAD of the upstream repository breaks your build, so you have to figure out which commit in the other repository broke things for your repository.

First, get a list of the commits from the current working one to a known bad one (typically HEAD of the default branch). For example, if the bad commit was ID abc123 according to the Git log, you could run git log --format=%H --reverse abc123.. > commits.txt in the upstream repo to get a file with the relevant commit IDs.

Then you need to figure out a test command, like nix-build --attr foo tests/default.nix, npm test, pytest test_foo.py::test_name, or something else entirely. If this command is fast, all the better, since it’ll run up to log_2(N)+2 times to check through $N$ commits.

At this point you can run /path/to/bisect.bash COMMAND /path/to/commits.txt to find the first offending commit.

As a concrete example of this, I wrote bisect.bash to bump nixpkgs in poetry2nix, since HEAD of nixpkgs master was breaking the nixops package build. To figure out which commit broke things, starting from the HEAD of the default branch in all the repos:

$ cd /path/to/poetry2nix
$ good="$(jq --raw-output .nixpkgs.rev nix/sources.json)"
$ cd /path/to/nixpkgs
$ git log --format=%H --reverse "$good".. > commits.txt
$ cd -
$ /path/to/bisect/bisect.bash 'niv update --rev="$ENTRY" nixpkgs && nix-build --attr nixops tests/default.nix' /path/to/nixpkgs/commits.txt

After building 15 out of the 32,683 commits in that range, the command finished successfully, determining that commit ceab3fb5f4ae430845e93c457b5353dc8b019e2b of nixpkgs broke the nixops build in poetry2nix.