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

From: Jon Seymour <jon.seymour@gmail.com>
Date: Jun 19, 2005, 04:07 UTC
Message-ID: <2cfc40320506182107755d1b3e@mail.gmail.com>
In-Reply-To: <20050619033821.GB24982@delft.aura.cs.cmu.edu>

On 6/19/05, Jan Harkes <jaharkes@cs.cmu.edu> wrote:

Show 12 quoted lines

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