Subject: Re: git-rev-list: "--bisect" flag

From: Jon Seymour <[email-masked]>
Date: Sun, 19 Jun 2005 14:07:15 +1000

On 6/19/05, Jan Harkes <[email-masked]> wrote:
> On Sun, Jun 19, 2005 at 10:18:45AM +1000, Jon Seymour wr
> A was known good, parallel development for commits B and C, finally
> merged into D. A bug got introduced in B, which we discover by the time
> we have a checked out copy of D.
> 
>      .--- B ---.
>     /           \
>    A             D
>     \           /
>      `--- C ---'
> 
> git-rev-list E ^A shows this as BCD. Pick the halfway point C, and this

I assume you mean git-rev-list D ^A

> one checks out ok. So at this point we would decide that the bug got
> introduced by the C->D change.

I think you misunderstood the intent of my original question which was
implicitly referring to the implementation of the bisection algorithm,
not to the bug blatt algorithm that makes use of the bisection
algorithm.

My actual question was: "Why is the bisection algorithm itself the way it is? "

A simple bisection algorithm which simply chooses the middle of the
git-rev-list output chooses a point which one could in principle argue
is as good as the one chosen by the current bisection algorithm.
However, I must admit that I don't quite understand the subtleties of
Linus' bisection algorithm, hence the question - why is his bisection
algorithm better than simply choosing the literal middle?

I'll post a patch that I have already sent to Linus which demonstrates
an implementation of --bisect that chooses the literal middle. This
patch also includes a demonstration of Linus' binary bug blatting
technique (see t/t6001-rev-list-merge-order.sh)

jon.