Re: Bisect marking new commits incorrectly

From: Junio C Hamano <gitster@pobox.com>
Date: Nov 24, 2017, 05:29 UTC
Message-ID: <xmqq8tewp7mg.fsf@gitster.mtv.corp.google.com>
In-Reply-To: <20171122213751.GC2854@sigill>

Jeff King <peff@peff.net> writes:

Show 9 quoted lines

> Yeah, I really would have expected this to work, too. Should we be
> taking the merge base of the set of "new" commits, and using that as the
> true "new"?
> ...
> So maybe that's not workable.
>
> (I've never really dug into the bisect algorithm, and this is written
> largely off the cuff, so I'm fine if the response is "nope, you have no
> idea what you are talking about").

You reached the right conclusion, I think.

A single merge-base case still might be worth optimizing for (and IIRC, unlike the "git log A..B" traversal that could be fooled by clock skew, merge-base reliably rejects falsely independent bases in the presence of clock skew, so it should be safe to do), but in a scenario your second illustration depicts, the merge-bases would not help us that much.

When starting from D and F, both of which are known to be "bad", all we know is that some of the merge bases between them are "bad", while other bases are not "bad" as they do not inherit the badness in the common ancestor of those "bad" bases.

And taking a merge base of these multiple merge-bases recursively would not help us there. We started from "all of these, i.e. D and F, are known to be bad", which is different from "some of these among multiple bases are bad, but we do not know which ones", so even if we were to go recursive, the first step needs to be "now let's see which one of these multiple bases are bad, so that we can take merge-base across them".