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

From: Junio C Hamano <gitster@pobox.com>
Date: Jan 17, 2017, 19:58 UTC
Message-ID: <xmqq37ghfoh9.fsf@gitster.mtv.corp.google.com>
In-Reply-To: <vpqfukjpdnp.fsf@anie.imag.fr>

Matthieu Moy <Matthieu.Moy@grenoble-inp.fr> writes:

Show 29 quoted lines

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