Subject: Re: [PATCH] Documentation/bisect: improve on (bad|new) and (good|bad)

From: Junio C Hamano <[email-masked]>
Date: Tue, 17 Jan 2017 11:58:10 -0800

Matthieu Moy <[email-masked]> writes:

>> But what if bad-A and bad-B have more than one merge bases?  We
>> won't know which side the badness came from.
>>
>>                           o---o---o---bad-A
>>                          /     \ / 
>>     -----Good---o---o---o       / 
>>                          \     / \
>>                           o---o---o---bad-B
>>
>> Being able to bisect the region of DAG bound by "^Good bad-A bad-B"
>> may have value in such a case.  I dunno.
>
> I could help finding several guilty commits, but anyway you can't
> guarantee you'll find them all as soon as you use a binary search: if
> the history looks like
>
> --- Good --- Bad --- Good --- Good --- Bad --- Good --- Bad
>
> then without examining all commits, you can't tell how many good->bad
> switches occured.
>
> But keeping several bad commits wouldn't help keeping the set of
> potentially guilty commits small: bad commits appear on the positive
> side in "^Good bad-A bad-B", so having more bad commits mean having a
> larger DAG to explore (which is a bit counter-intuitive: without
> thinking about it I'd have said "more info => less commits to explore").
>
> So, if finding all guilty commits is not possible, I'm not sure how
> valuable it is to try to find several of them.

The criss-cross merge example, is not trying to find multiple
sources of badness.  It still assumes [*1*] that there is only one
event that introduced the badness observed at bad-A and bad-B, both
of which inherited the badness from the same such event.  Unlike a
case with a single/unique merge-base, we cannot say "we can start
from the merge-base, as their common badness must be coming from the
same place".  The badness may exist in the first 'o' on the same
line as bad-A in the above picture, which is an ancestor of one
merge-base on that line and does not break the other merge base on
the same line as bad-B, for example.

> OTOH, keeping several good commits is needed to find a commit for which
> all parents are good and the commit is bad.

Yes, that is correct.

[Footnote]

*1* The assumption is what makes "bisect" workable.  If the
    assumption does not hold, then "bisect" would not give a useful
    answer "where did I screw up?".  It gives a fairly useless "I
    found one bad commit whose parent is good---there is no
    guarantee if that has anything to do with the badness you are
    seeing at the tip".