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

[Junio C Hamano <gitster@pobox.com>]

Kevin Daudt <me@ikke.info> writes:

> So this ref changes to the bad commit.
>
> For refs/bisect/good-*, I could only find an example snippet:
>
>> GOOD=$(git for-each-ref "--format=%(objectname)" refs/bisect/good-*)
>
> But it's not really clear what * might be expanded to, nor what they
> mean. I guess this could use some clarrification in the documentation.

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".