Re: [PATCH v4] rev-list: refuse --first-parent combined with --bisect

Kevin Daudt <me@ikke.info> writes:

Because the history is not linear in Git, bisection works by shrinking a subgraph of the history DAG that contains "yet to be tested, suspected to have introduced a badness" commits. The subgraph is defined as anything reachable from _the_ "bad" commit (initially, the one you give to the command when you start) that are not reachable from any of the "good" commits.

Suppose you started from this graph. Time flows left to right as usual.

  ---0---2---4---6---8---9
      \             /
       1---3---5---7

Then mark the initial good and bad commits as G and B.

  ---G---2---4---6---8---B
      \             /
       1---3---5---7

And imagine that you are asked to check 4, which turns out to be good. We do not _move_ G to 4; we mark 4 as good, while keeping 0 also as good.

  ---G---2---G---6---8---B
      \             /
       1---3---5---7

And if you are next asked to check 5, and mark it as good, the graph will become like this:

  ---G---2---G---6---8---B
      \             /
       1---3---G---7

Of course, at this point, the subgraph of suspects are 6, 7, 8 and 9, and the subgraph no longer is affected by the fact that 0 is good. But it is crucial to keep 0 marked as good in the step before this one, before you tested 5, as that is what allows us not having to test any ancestors of 0 at all.

Now, one may wonder why we need multiple "good" commits but we do not need multiple "bad" commits. This comes from the nature of "bisection", which is a tool to find a _single_ breakage [*1*], and a fundamental assumption is that a breakage does not fix itself.

Hence, if you have a history that looks like this:

   G...1---2---3---4---6---8---B
                    \
                     5---7---B

it follows that 4 must also be "bad". It used to be good long time ago somewhere before 1, and somewhere along way on the history, there was a single breakage event that we are hunting for. That single event cannot be 5, 6, 7 or 8 because breakage at say 5 would not explain why the tip of the upper branch is broken---its breakage has no way to propagate there. The breakage must have happened at 4 or before that commit.

Which means that if you marked the child of 8 (the tip of the upper branch) as bad, there is no reason for us to even look at the lower branch. As soon as you mark the tip of the upper branch "bad", the bisection can become

   G...1---2---3---4---6---8---B

and without looking at the lower branch, it can find the single breakage.

[Footnote]

*1* You may be hunting for a single _fix_, and flipping the meaning
    of "good" and "bad", say "It used to be broken but somewhere we
    seem to have fixed that bug.  Where did we do that?", marking
    the ones that still has the bug "good" and the ones that no
    longer has the bug "bad".  In that context, you would be looking
    for a single fix.  A more neutral term might be

    - we look for a single event that changes some state.

    - old state before that single event is spelled G O O D, but it
      is pronounced "not yet".

    - new state before that single event is spelled B A D, but it is
      pronounced "already".