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

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

[Christian Couder]

Before this patch "git bisect" doesn't really work when it is given
some good revs that are siblings of the bad rev.

For example if there is the following history:

A-B-C-D
   \E-F

and we launch "git bisect start D F" then only C and D will be
considered as possible first bad commit. This is wrong because A, B and
E may be bad too if the bug exists everywhere except in F that fixes it.

Maybe there is a way to make the above work, but for now the purpose of
this patch is to fix the problem by checking that all good revs are
ancestor of the bad rev and by erroring out if this is not the case.

To do that we run "git rev-list ^bad good" and we check that it outputs
nothing.

This check will also catch the case where good and bad have been
mistaken. This means that we can remove the check that was done latter
on the output of "git rev-list --bisect-vars". The downside of that is
that now we can't tell between a mistake and a "siblings" case.

Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
---
 git-bisect.sh               |   32 +++++++++++++++-----------------
 t/t6030-bisect-porcelain.sh |   19 +++++++++++++++++++
 2 files changed, 34 insertions(+), 17 deletions(-)

	Maybe we can improve on this patch by trying to tell between
	a mistake and a "siblings" case to give a better error
	message.

diff --git a/git-bisect.sh b/git-bisect.sh
index 991b2ef..90a9d74 100755
--- a/git-bisect.sh
+++ b/git-bisect.sh
@@ -242,33 +242,18 @@ bisect_auto_next() {
 	bisect_next_check && bisect_next || :
 }
 
-eval_rev_list() {
-	_eval="$1"
-
-	eval $_eval
-	res=$?
-
-	if [ $res -ne 0 ]; then
-		echo >&2 "'git rev-list --bisect-vars' failed:"
-		echo >&2 "maybe you mistake good and bad revs?"
-		exit $res
-	fi
-
-	return $res
-}
-
 filter_skipped() {
 	_eval="$1"
 	_skip="$2"
 
 	if [ -z "$_skip" ]; then
-		eval_rev_list "$_eval"
+		eval "$_eval"
 		return
 	fi
 
 	# Let's parse the output of:
 	# "git rev-list --bisect-vars --bisect-all ..."
-	eval_rev_list "$_eval" | while read hash line
+	eval "$_eval" | while read hash line
 	do
 		case "$VARS,$FOUND,$TRIED,$hash" in
 			# We display some vars.
@@ -331,6 +316,18 @@ exit_if_skipped_commits () {
 	fi
 }
 
+check_good_are_ancestor_of_bad() {
+	_bad="^$1"
+	_good=$(echo $2 | sed -e 's/\^//g')
+	_side=$(git rev-list $_good $_bad)
+	if test -n "$_side"; then
+		echo >&2 "Some good revs are not ancestor of the bad rev."
+		echo >&2 "git bisect cannot work properly in this case."
+		echo >&2 "Maybe you mistake good and bad revs?"
+		return 1
+	fi
+}
+
 bisect_next() {
 	case "$#" in 0) ;; *) usage ;; esac
 	bisect_autostart
@@ -345,6 +342,7 @@ bisect_next() {
 	bad=$(git rev-parse --verify refs/bisect/bad) &&
 	good=$(git for-each-ref --format='^%(objectname)' \
 		"refs/bisect/good-*" | tr '\012' ' ') &&
+	check_good_are_ancestor_of_bad "$bad" "$good" &&
 	eval="git rev-list --bisect-vars $BISECT_OPT $good $bad --" &&
 	eval="$eval $(cat "$GIT_DIR/BISECT_NAMES")" &&
 	eval=$(filter_skipped "$eval" "$skip") &&
diff --git a/t/t6030-bisect-porcelain.sh b/t/t6030-bisect-porcelain.sh
index 0626544..b3f3869 100755
--- a/t/t6030-bisect-porcelain.sh
+++ b/t/t6030-bisect-porcelain.sh
@@ -350,6 +350,25 @@ test_expect_success 'bisect does not create a "bisect" branch' '
 	git branch -D bisect
 '
 
+# This creates a "side" branch to test "siblings" cases.
+test_expect_success 'bisect errors out when good and bad are siblings' '
+	git bisect reset &&
+	git checkout -b side $HASH4 &&
+	add_line_into_file "5(side): first line on a side branch" hello &&
+	SIDE_HASH5=$(git rev-parse --verify HEAD) &&
+	add_line_into_file "6(side): second line on a side branch" hello &&
+	SIDE_HASH6=$(git rev-parse --verify HEAD) &&
+	add_line_into_file "7(side): third line on a side branch" hello &&
+	SIDE_HASH7=$(git rev-parse --verify HEAD) &&
+	test_must_fail git bisect start "$HASH7" "$SIDE_HASH7" &&
+	test_must_fail git bisect start "$SIDE_HASH7" "$HASH7" &&
+	test_must_fail git bisect start "$HASH7" HEAD &&
+	test_must_fail git bisect start "$SIDE_HASH5" "$HASH7" &&
+	test_must_fail test -e .git/BISECT_START &&
+	test -z "$(git for-each-ref "refs/bisect/*")" &&
+	test "$(git rev-parse --verify HEAD)" = "$SIDE_HASH7"
+'
+
 #
 #
 test_done
-- 
1.5.6.7.g5b8fa.dirty

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

[Junio C Hamano]

Christian Couder <chriscool@tuxfamily.org> writes:

> Before this patch "git bisect" doesn't really work when it is given
> some good revs that are siblings of the bad rev.
>
> For example if there is the following history:
>
> A-B-C-D
>    \E-F
>
> and we launch "git bisect start D F" then only C and D will be
> considered as possible first bad commit. This is wrong because A, B and
> E may be bad too if the bug exists everywhere except in F that fixes it.

Please don't.

bisect is about finding a single regression by partitioning the graph into
older good section and newer bad section with a *single* "first bad
commit".

For your "this could also be possible" scenario is already outside the
realm.  You are assuming A, B and F is good, and D is bad.  But if E is
bad, then that breakage cannot possibly affect the transition between B
and D from good to bad (E cannot break D), so C must *also* be bad.

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

[Junio C Hamano]

Junio C Hamano <gitster@pobox.com> writes:

> Christian Couder <chriscool@tuxfamily.org> writes:
>
>> Before this patch "git bisect" doesn't really work when it is given
>> some good revs that are siblings of the bad rev.
>>
>> For example if there is the following history:
>>
>> A-B-C-D
>>    \E-F
>>
>> and we launch "git bisect start D F" then only C and D will be
>> considered as possible first bad commit. This is wrong because A, B and
>> E may be bad too if the bug exists everywhere except in F that fixes it.
>
> Please don't.
>
> bisect is about finding a single regression by partitioning the graph into
> older good section and newer bad section with a *single* "first bad
> commit".
>
> Your "this could also be possible" scenario is already outside the
> realm.  You are assuming A, B and F is good, and D is bad.  But if E is
> bad, then that breakage cannot possibly affect the transition between B
> and D from good to bad (E cannot break D), so C must *also* be bad.

... which means you are dealing with *two* breakages.  That's outside what
bisect deals with.

And this does not need to have forked development.  If the graph were like
this:

  A-B-C-D-E-F

and if F is bad and B is good, with your logic, after checking that D is
already bad, we cannot discount E --- after somehow fixing D, we _might_
also be introducing another breakage with E.  You cannot even check for
that anyway, but the logic is the same.

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

[Christian Couder]

Le mardi 1 juillet 2008, Junio C Hamano a écrit :
> Christian Couder <chriscool@tuxfamily.org> writes:
> > Before this patch "git bisect" doesn't really work when it is given
> > some good revs that are siblings of the bad rev.
> >
> > For example if there is the following history:
> >
> > A-B-C-D
> >    \E-F
> >
> > and we launch "git bisect start D F" then only C and D will be
> > considered as possible first bad commit. This is wrong because A, B and
> > E may be bad too if the bug exists everywhere except in F that fixes
> > it.
>
> Please don't.
>
> bisect is about finding a single regression by partitioning the graph
> into older good section and newer bad section with a *single* "first bad
> commit".
>
> For your "this could also be possible" scenario is already outside the
> realm.  You are assuming A, B and F is good, and D is bad.

I am assuming the first bad commit in the graph is A and it is fixed by F.

> But if E is 
> bad, then that breakage cannot possibly affect the transition between B
> and D from good to bad (E cannot break D), so C must *also* be bad.

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.

> And this does not need to have forked development.  If the graph were
> like this:
>
>   A-B-C-D-E-F
>
> and if F is bad and B is good, with your logic, after checking that D is
> already bad, we cannot discount E --- after somehow fixing D, we _might_
> also be introducing another breakage with E.  You cannot even check for
> that anyway, but the logic is the same.

I don't think the logic is the same because in your case git bisect will 
report one first bad commit anyway even if this bad commit has been fixed 
latter.

In my case above, git bisect currently considers C and D as the only 
possible bad commits because when it is told that F is good, it assumes 
that all the ancestors or F are good too. And this means that B is 
considered good so C will be found as the first bad commit. I think this 
can be really misleading because there is no good->bad transition between B 
and C.

Regards,
Christian.

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

[Junio C Hamano]

Christian Couder <chriscool@tuxfamily.org> 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.

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

[Junio C Hamano]

Christian Couder <chriscool@tuxfamily.org> writes:

> Le mardi 1 juillet 2008, Junio C Hamano a écrit :
>> Christian Couder <chriscool@tuxfamily.org> writes:
>> > Before this patch "git bisect" doesn't really work when it is given
>> > some good revs that are siblings of the bad rev.
>> >
>> > For example if there is the following history:
>> >
>> > A-B-C-D
>> >    \E-F
>> >
>> > and we launch "git bisect start D F" then only C and D will be
>> > considered as possible first bad commit.
>
> I am assuming the first bad commit in the graph is A and it is fixed by F.

Ah, I see your confusion here.  bisect is about finding regressions.
"Older ones were good, and now there is a breakage.  Who broke it?"

If F fixed it, that is already outside the bisection's scope.  The user
needs to know that by saying F is good, he is saying he knows everything
that leads to F is good.

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

[Junio C Hamano]

Junio C Hamano <gitster@pobox.com> writes:

> Christian Couder <chriscool@tuxfamily.org> writes:
>
>> Le mardi 1 juillet 2008, Junio C Hamano a écrit :
>>> Christian Couder <chriscool@tuxfamily.org> writes:
>>> > Before this patch "git bisect" doesn't really work when it is given
>>> > some good revs that are siblings of the bad rev.
>>> >
>>> > For example if there is the following history:
>>> >
>>> > A-B-C-D
>>> >    \E-F
>>> >
>>> > and we launch "git bisect start D F" then only C and D will be
>>> > considered as possible first bad commit.
>>
>> I am assuming the first bad commit in the graph is A and it is fixed by F.
>
> Ah, I see your confusion here.  bisect is about finding regressions.
> "Older ones were good, and now there is a breakage.  Who broke it?"
>
> If F fixed it, that is already outside the bisection's scope.  The user
> needs to know that by saying F is good, he is saying he knows everything
> that leads to F is good.

Ok, I wasn't thinking straight.

The tricky part is that the user does not know.

Until we somehow can check B is bad, we cannot tell that the original
bisection was done incorrectly (in the sense that it was not finding
regression, but what the user could find is which commit fixed it).

If we perform a test merge between D and F and test that tree, and if that
turns out to be Ok, that would be a good indication of existence of a fix
(i.e. the topology is not "old good code was broken somewhere", but "old
broken code was fixed somewhere").  I am not sure how applicable that
approach would be in practice, though.

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

[Christian Couder]

Le mardi 1 juillet 2008, Junio C Hamano a écrit :
> Christian Couder <chriscool@tuxfamily.org> writes:
> > Le mardi 1 juillet 2008, Junio C Hamano a écrit :
> >> Christian Couder <chriscool@tuxfamily.org> writes:
> >> > Before this patch "git bisect" doesn't really work when it is given
> >> > some good revs that are siblings of the bad rev.
> >> >
> >> > For example if there is the following history:
> >> >
> >> > A-B-C-D
> >> >    \E-F
> >> >
> >> > and we launch "git bisect start D F" then only C and D will be
> >> > considered as possible first bad commit.
> >
> > I am assuming the first bad commit in the graph is A and it is fixed by
> > F.
>
> Ah, I see your confusion here.  bisect is about finding regressions.
> "Older ones were good, and now there is a breakage.  Who broke it?"
>
> If F fixed it, that is already outside the bisection's scope.  The user
> needs to know that by saying F is good, he is saying he knows everything
> that leads to F is good.

Yes, but the fact is that the user may wrongly think that F is an ancestor 
of D or he may not remember/know about the rule that saying "F is good" 
means "everything from A to F is good". That's why this patch adds a safety 
net by detecting end erroring out in this case.

Regards,
Christian.

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

[Junio C Hamano]

Christian Couder <chriscool@tuxfamily.org> writes:

> Yes, but the fact is that the user may wrongly think that F is an ancestor 
> of D or he may not remember/know about the rule that saying "F is good" 
> means "everything from A to F is good". That's why this patch adds a safety 
> net by detecting end erroring out in this case.

Yeah, sorry about the confusion earlier.

But I do not think forbidding forked topology very early in bisection
process is a very good idea.  The user would be at loss when told:

	echo >&2 "Maybe you mistake good and bad revs?"

Aside from the "test a trial merge" idea I floated in the other message,
when we detect such a fork, perhaps we can suggest testing the merge base
version (B in your picture) first?  We would immediately know as the user
would say "B is bad" if the topology is problematic.

Then, we can suggest the user that breakage at D may not be a regression
but a longstanding bug that was recently fixed somewhere between B and F.

The user then can decide to bisect to find the fix (so that it can be
cherry picked on top of D) or merge F into D to propagate the fix forward
if it is not important to find out which exact commit fixed the issue.

Hmm?

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

[Christian Couder]

Le mardi 1 juillet 2008, Junio C Hamano a écrit :
> Christian Couder <chriscool@tuxfamily.org> writes:
> > Yes, but the fact is that the user may wrongly think that F is an
> > ancestor of D or he may not remember/know about the rule that saying "F
> > is good" means "everything from A to F is good". That's why this patch
> > adds a safety net by detecting end erroring out in this case.
>
> Yeah, sorry about the confusion earlier.
>
> But I do not think forbidding forked topology very early in bisection
> process is a very good idea.  The user would be at loss when told:
>
> 	echo >&2 "Maybe you mistake good and bad revs?"

Yeah, perhaps we should then check that it can be a mistake by testing if 
bad is an ancestor of good. If bad is indeed an ancestor of good, it's 
probably a mistake and we may even ask if the user wants good and bad to be 
swaped (assuming he gave only one good rev of course).

> Aside from the "test a trial merge" idea I floated in the other message,
> when we detect such a fork, perhaps we can suggest testing the merge base
> version (B in your picture) first?  We would immediately know as the user
> would say "B is bad" if the topology is problematic.

Yes this can be a good idea, if the user gave only one good rev. It maybe 
more tricky if he gave many good revs, but in this case we may perhaps drop 
siblings good revs as long as one good rev is an ancestor of the bad rev.

> Then, we can suggest the user that breakage at D may not be a regression
> but a longstanding bug that was recently fixed somewhere between B and F.
>
> The user then can decide to bisect to find the fix (so that it can be
> cherry picked on top of D) or merge F into D to propagate the fix forward
> if it is not important to find out which exact commit fixed the issue.
>
> Hmm?

Yeah that might be a plan.

Another option is to introduce a switch to "git bisect start", 
perhaps --strict, to please people who always want to use good revs that 
are ancestor of the bad revs, so they get a nice error when this is not the 
case.

Thanks,
Christian.

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

[Junio C Hamano]

Christian Couder <chriscool@tuxfamily.org> writes:

> Another option is to introduce a switch to "git bisect start", 
> perhaps --strict, to please people who always want to use good revs that 
> are ancestor of the bad revs, so they get a nice error when this is not the 
> case.

I do not see much niceness value to such an option, though.  I think such
a switch is going the opposite way from improving usability.

You cannot bisect the history with such a draconian switch when you learn
from somebody that 'maint' is Ok but 'master' is broken, and you already
know it is a regression somewhere introduced in 'master', because you know
you did _not_ fix it (or at least you do not remember fixing it) only for
'maint'.