Re: [PATCH] bisect: error out when given any good rev that is not an ancestor of the bad rev

From: Junio C Hamano <gitster@pobox.com>
Date: Jun 30, 2008, 23:27 UTC
Message-ID: <7vtzfatsf4.fsf@gitster.siamese.dyndns.org>
In-Reply-To: <200807010116.30214.chriscool@tuxfamily.org>

Christian Couder <chriscool@tuxfamily.org> writes:

Show 6 quoted lines

> Yes, I assume C is also bad.
>
>> ... which means you are dealing with *two* breakages.  That's outside
>> what bisect deals with.
>
> Sorry, I don't understand why I am assuming 2 breakages.

Your topology is

>> > A-B-C-D
>> >    \E-F

and you start with "D F" so D is bad and F is good, right?

bisect operates on a history with a single breakage that separates older good ones and newer bad ones.

Now D is bad, so there must be somewhere in

	A--B--C--D

that broke D. It could be D itself, or it may have been broken at A already.

But if A or B were bad, then, because F is good, this part of the picture:

	A--B--E--F

does not deal with "old good followed by new bad sparated by a single breakage point". Maybe E or F have fixed it, but then before that is bad and after that is good. That's not what bisect deals with.

Going back to the original picture, then:

>> > A-B-C-D
>> >    \E-F

For F to be good, all of its ancestors are by definition good (that is the basic assumption of bisection). A and B are good. If D is broken, C or D must be broken.

So we do not decend into B nor its ancestor.

The logic is the same if the history is linear.

	A--B--C--D--E--F

If B is good and F is bad, and if you check D and find out that D is still good, then we can ignore everything behind D, and that is what lets us limit the search space and suspect only E or F. This is exactly the same "Everything that leads to a good one is good" principle upon which bisection works.