threads / patch / 14233

patchbisect: error out when given any good rev that is not an ancestor of the bad rev

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

## tl;dr

11 messages between Jun 30, 2008 and Jul 1, 2008. Diffs are folded; open one to read it.

replies: 10people: 2as markdown or json

Christian Couder· Jun 30, 2008, 22:42 UTC · lore

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.
Show changes to 2 files +34 −17

git-bisect.sh, t/t6030-bisect-porcelain.sh

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
Junio C Hamano· Jun 30, 2008, 22:44 UTC · re: Christian Couder · lore

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

Christian Couder <chriscool@tuxfamily.org> writes:
Show 11 quoted lines
> 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.

Junio C Hamano· Jun 30, 2008, 22:48 UTC · re: Junio C Hamano · lore

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

Junio C Hamano <gitster@pobox.com> writes:
Show 24 quoted lines
> 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.

Christian Couder· Jun 30, 2008, 23:16 UTC · re: Junio C Hamano · lore

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

Le mardi 1 juillet 2008, Junio C Hamano a écrit :
Show 22 quoted lines
> 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.
Show 9 quoted lines
> 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.

Junio C Hamano· Jun 30, 2008, 23:27 UTC · re: Christian Couder · lore

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

Christian Couder <chriscool@tuxfamily.org> writes:
Show 6 quoted lines
> 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.

Junio C Hamano· Jun 30, 2008, 23:32 UTC · re: Christian Couder · lore

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

Christian Couder <chriscool@tuxfamily.org> writes:
Show 14 quoted lines
> 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.

Junio C Hamano· Jun 30, 2008, 23:42 UTC · re: Junio C Hamano · lore

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

Junio C Hamano <gitster@pobox.com> writes:
Show 23 quoted lines
> 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.

Christian Couder· Jun 30, 2008, 23:46 UTC · re: Junio C Hamano · lore

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

Le mardi 1 juillet 2008, Junio C Hamano a écrit :
Show 23 quoted lines
> 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.

Junio C Hamano· Jun 30, 2008, 23:52 UTC · re: Christian Couder · lore

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

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?
Christian Couder· Jul 1, 2008, 00:20 UTC · re: Junio C Hamano · lore

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

Le mardi 1 juillet 2008, Junio C Hamano a écrit :
Show 12 quoted lines
> 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.

Show 8 quoted lines
> 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.

Junio C Hamano· Jul 1, 2008, 01:13 UTC · re: Christian Couder · lore

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

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

← back to recent threads