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

From: Junio C Hamano <[email-masked]>
Date: Mon, 30 Jun 2008 16:27:27 -0700

Christian Couder <[email-masked]> writes:

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