bisect

Find the interesting item in a list of items.

Ever needed to find a file that silently breaks your build? Ever wanted git bisect outside git? This tool performs binary search on a list of items. Also related to the concept of "shrinking" in property based testing.

Currently supports searching:

Other kinds of searches to be implemented.

Installation

git clone https://github.com/kaukas/bisect
cd bisect
shards build --release

Usage

Interactive

./bin/bisect

For example

$ ./bin/bisect
Enter the list of items, one per line, and an empty line at the end:
1
2
3

Consider this list of items:
1
2
3

Are they interesting? Enter + or -: +
Consider this list of items:
1
2

Are they interesting? Enter + or -: +
Consider this item:
1

Is it interesting? Enter + or -: -
Consider this item:
2

Is it interesting? Enter + or -: +
The interesting item:
2

Automatic

If there are arguments after -- they are treated as a command that is to be automatically executed to verify if a list of items is interesting. The items to be verified are supplied as standard input. A 0 exit code means "not interesting" while any other exit code (e.g. a failing test suite) means it is interesting. Standard output is ignored while standard error is redirected to the bisect standard error.

cat items | ./bin/bisect -- <verifier commmand>

For example

$ echo -e "1\n2\n3" | ./bin/bisect -- bash -c "! grep 3"
The interesting item:
3

Mode "one"

This is the default mode. The algorithm looks for one interesting item in a list ("the needle in the haystack"). At each step a sublist is presented and a user interactively or a command automatically (see examples above) decide if the sublist contains the interesting item.

Trust

By default every subset is checked for presence of the interesting item. Say, if we are looking for 2 in [1, 2, 3] it will check items [1, 2, 3] (yes), then [1, 2] (yes), then [1] (no), then [2] (yes). However, if we are sure there is one interesting item then some of the checks are redundant. It would be enough to check [1, 2] (yes) and [1] (no), and [2] can be inferred. To skip the redundant checks pass --trust.

$ ./bin/bisect --trust
Enter the list of items, one per line, and an empty line at the end:
1
2
3

Consider this list of items:
1
2

Are they interesting? Enter + or -: +
Consider this item:
1

Is it interesting? Enter + or -: -
The interesting item:
2

Mode "first"

The algorithm assumes that a list starts with uninteresting items and ends with interesting items, and looks for the first interesting item. At each step one item is presented. If the item is determined to be interesting then the algorithm looks at the part of the list preceding that item. Otherwise it looks at the part of the list after the item. This is equivalent to git bisect (albeit simplified because forks and merges are not taken into account).

Trust

By default the algorithm verifies that the first item is uninteresting and the last item is interesting before checking the items in the middle. If you are sure that the list always ends up with an interesting item (e.g. the last commit is broken) pass --trust, and the right boundary check will be skipped.

Development

Install with

shards install

Run tests with

crystal spec

Contributing

  1. Fork it (https://github.com/kaukas/bisect/fork)
  2. Create your feature branch (git checkout -b my-new-feature)
  3. Commit your changes (git commit -am 'Add some feature')
  4. Push to the branch (git push origin my-new-feature)
  5. Create a new Pull Request

Contributors