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

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