[PATCH] Fix path-limited "rev-list --bisect" termination condition.

[PATCH] Fix path-limited "rev-list --bisect" termination condition.

[Junio C Hamano]

In a path-limited bisection, when the $bad commit is not
changing the limited path, and the number of suspects is 1, the
code miscounted and returned $bad from find_bisection(), which
is not marked with TREECHANGE.  This is of course filtered by
the output routine, resulting in an empty output, in turn
causing git-bisect driver to say "$bad was both good and bad".

Illustration.  Suppose you have these four commits, and only C
changes path P.  You know D is bad and A is good.

	A---B---C*--D

git-bisect driver runs this to find a bisection point:

	$ git rev-list --bisect A..D -- P

which calls find_bisection() with B, C and D.  The set of
commits that is given to this function is the same set of
commits as rev-list without --bisect option and pathspec
returns.  Among them, only C is marked with TREECHANGE.  Let's
call the set of commits given to find_bisection() that are
marked with TREECHANGE (or all of them if no path limiter is in
effect) "the bisect set".  In the above example, the size of the
bisect set is 1 (contains only "C").

For each commit in its input, find_bisection() computes the
number of commits it can reach in the bisect set.  For a commit
in the bisect set, this number includes itself, so the number is
1 or more.  This number is called "depth", and computed by
count_distance() function.

When you have a bisect set of N commits, and a commit has depth
D, how good is your bisection if you returned that commit?  How
good this bisection is can be measured by how many commits are
effectively tested "together" by testing one commit.

Currently you have (N-1) untested commits (the tip of the bisect
set, although it is included in the bisect set, is already known
to be bad).  If the commit with depth D turns out to be bad,
then your next bisect set will have D commits and you will have
(D-1) untested commits left, which means you tested (N-1)-(D-1)
= (N-D) commits with this bisection.  If it turns out to be good, then
your next bisect set will have (N-D) commits, and you will have
(N-D-1) untested commits left, which means you tested
(N-1)-(N-D-1) = D commits with this bisection.

Therefore, the goodness of this bisection is is min(N-D, D), and
find_bisection() function tries to find a commit that maximizes
this, by initializing "closest" variable to 0 and whenever a
commit with the goodness that is larger than the current
"closest" is found, that commit and its goodness are remembered
by updating "closest" variable.  The "the commit with the best
goodness so far" is kept in "best" variable, and is initialized
to a commit that happens to be at the beginning of the list of
commits given to this function (which may or may not be in the
bisect set when path-limit is in use).

However, when N is 1, then the sole tree-changing commit has
depth of 1, and min(N-D, D) computes to 0.  This is not larger
than the initial value of "closest", and the "so far the best
one" commit is never replaced in the loop.

When path-limit is not in use, this is not a problem, as any
commit in the input set is tree-changing.  But when path-limit
is in use, and when the starting "bad" commit does not change
the specified path, it is not correct.  This is the first
bug the patch fixes with a one-liner.

How many lines did I spend to describe this one-liner?

Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 builtin-rev-list.c |    3 ++-
 1 files changed, 2 insertions(+), 1 deletions(-)

diff --git a/builtin-rev-list.c b/builtin-rev-list.c
index c2db5a5..4f4b1d2 100644
--- a/builtin-rev-list.c
+++ b/builtin-rev-list.c
@@ -180,7 +180,8 @@ static struct commit_list *find_bisection(struct commit_list *list)
 			nr++;
 		p = p->next;
 	}
-	closest = 0;
+
+	closest = -1;
 	best = list;
 
 	for (p = list; p; p = p->next) {
-- 
1.5.1.rc1.651.g2ca06

Re: [PATCH] Fix path-limited "rev-list --bisect" termination condition.

[Linus Torvalds]

On Fri, 23 Mar 2007, Junio C Hamano wrote:
> 
> How many lines did I spend to describe this one-liner?

Heh. Looks good to me.

		Linus

Re: [PATCH] Fix path-limited "rev-list --bisect" termination condition.

[Junio C Hamano]

Is this the only issue you know about with respect to the
BISECT_NAMES?  You earlier said it was broken and suggested to
remove it,...

Re: [PATCH] Fix path-limited "rev-list --bisect" termination condition.

[Linus Torvalds]

On Fri, 23 Mar 2007, Junio C Hamano wrote:
>
> Is this the only issue you know about with respect to the
> BISECT_NAMES?  You earlier said it was broken and suggested to
> remove it,...

That ending condition was the only one I knew about. If you have checked 
that it works now, I say "keep it". At worst, it just points to the wrong 
commit because people gave the wrong list of filenames, but hey, let's 
burn that bridge when we get to it.

		Linus