-------------

And it is possible to replay it using:

-------------
$ git bisect replay bisect_log.txt
-------------


"git bisect" details
--------------------

Bisection algorithm
~~~~~~~~~~~~~~~~~~~

As the Git commits form a directed acyclic graph (DAG), finding the
best bisection commit to test at each step is not so simple. Anyway
Linus found and implemented a "truly stupid" algorithm, later improved
by Junio Hamano, that works quite well.

So the algorithm used by "git bisect" to find the best bisection
commit when there are no skipped commits is the following:

1) keep only the commits that:

a) are ancestor of the "bad" commit (including the "bad" commit itself),
b) are not ancestor of a "good" commit (excluding the "good" commits).

This means that we get rid of the uninteresting commits in the DAG.

For example if we start with a graph like this:

-------------
G-Y-G-W-W-W-X-X-X-X
	   \ /
	    W-W-B
	   /
Y---G-W---W
 \ /   \
Y-Y     X-X-X-X

-> time goes this way ->
-------------

where B is the "bad" commit, "G" are "good" commits and W, X, and Y
are other commits, we will get the following graph after this first
step:

-------------
W-W-W
     \
      W-W-B
     /
W---W
-------------

So only the W and B commits will be kept. Because commits X and Y will
have been removed by rules a) and b) respectively, and because commits
G are removed by rule b) too.

Note for Git users, that it is equivalent as keeping only the commit
given by:

-------------
git rev-list BAD --not GOOD1 GOOD2...
-------------

Also note that we don't require the commits that are kept to be
descendants of a "good" commit. So in the following example, commits W
and Z will be kept:

-------------
G-W-W-W-B
   /
Z-Z
-------------

2) starting from the "good" ends of the graph, associate to each
   commit the number of ancestors it has plus one

For example with the following graph where H is the "bad" commit and A
and D are some parents of some "good" commits:

-------------
A-B-C
     \
      F-G-H
     /
D---E
-------------

this will give:

-------------
1 2 3
A-B-C
     \6 7 8
      F-G-H
1   2/
D---E
-------------

3) associate to each commit: min(X, N - X)

where X is the value associated to the commit in step 2) and N is the
total number of commits in the graph.

In the above example we have N = 8, so this will give:

-------------
1 2 3
A-B-C
     \2 1 0
      F-G-H
1   2/
D---E
-------------

4) the best bisection point is the commit with the highest associated
   number

So in the above example the best bisection point is commit C.

5) note that some shortcuts are implemented to speed up the algorithm

As we know N from the beginning, we know that min(X, N - X) can't be
greater than N/2. So during steps 2) and 3), if we would associate N/2
to a commit, then we know this is the best bisection point. So in this
case we can just stop processing any other commit and return the
current commit.

Bisection algorithm debugging
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

For any commit graph, you can see the number associated with each
commit using "git rev-list --bisect-all".

For example, for the above graph, a command like:

-------------
$ git rev-list --bisect-all BAD --not GOOD1 GOOD2
-------------

would output something like:

-------------
e15b73ad3db9b48d7d1ade32f8cd23a751fe0ace (dist=3)
15722f2fa328eaba97022898a305ffc8172db6b1 (dist=2)
78e86cf3e850bd755bb71831f42e200626fbd1e0 (dist=2)
a1939d9a142de972094af4dde9a544e577ddef0e (dist=2)
070eab2303024706f2924822bfec8b9847e4ac1b (dist=1)
a3864d4f32a3bf5ed177ddef598490a08760b70d (dist=1)
a41baa717dd74f1180abf55e9341bc7a0bb9d556 (dist=1)
9e622a6dad403b71c40979743bb9d5be17b16bd6 (dist=0)
-------------

Bisection algorithm discussed
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

First let's define "best bisection point". We will say that a commit X
is a best bisection point or a best bisection commit if knowing its
state ("good" or "bad") gives as much information as possible whether
the state of the commit happens to be