[PATCH] bisect: test merge base if good rev is not an ancestor of bad rev

[PATCH] bisect: test merge base if good rev is not an ancestor of bad rev

[Christian Couder]

Before this patch, "git bisect", when it was given some good revs that
are not ancestor of the bad rev, didn't check if the merge bases were
good. "git bisect" just supposed that the user knew what he was doing,
and that, when he said the revs were good, he knew that it meant that
all the revs in the history leading to the good revs were also
considered good.

But in pratice, the user may not know that a good rev is not an
ancestor of the bad rev, or he may not know/remember that all revs
leading to the good rev will be considered good. So he may give a good
rev that is a sibling, instead of an ancestor, of the bad rev, when in
fact there can be one rev becoming good in the branch of the good rev
(because the bug was already fixed there for example) instead of one
rev becoming bad in the branch 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 would have been
considered as possible first bad commit before this patch. This may be
wrong because A, B and E may be bad too if the bug exists everywhere
except in F that fixes it.

The purpose of this patch is to detect when "git bisect" is passed
some good revs that are not ancestor of the bad rev, and then to first
ask the user to test the merge bases between the good and bad revs.

If the merge bases are good then all is fine, we can continue
bisecting. Otherwise, if one merge base is bad, it means that the
assumption that all revs leading to the good one are good too is
wrong and we error out. In the case where one merge base is skipped we
issue a warning and then continue bisecting anyway.

These checks 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".

In the current implementation though, only one merge base between a
good and a bad rev is tested.

Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
---
 git-bisect.sh               |  137 +++++++++++++++++++++++++++++++++++--------
 t/t6030-bisect-porcelain.sh |   41 +++++++++++++
 2 files changed, 153 insertions(+), 25 deletions(-)

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

	Here is a patch to do that.

diff --git a/git-bisect.sh b/git-bisect.sh
index 991b2ef..50f912f 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,20 +316,122 @@ exit_if_skipped_commits () {
 	fi
 }
 
+checkout() {
+	_rev="$1"
+	_msg="$2"
+	echo "Bisecting: $_msg"
+	git checkout -q "$_rev" || exit
+	git show-branch "$_rev"
+}
+
+is_among() {
+	_rev="$1"
+	_list="$2"
+	case "$_list" in *$_rev*) return 0 ;; esac
+	return 1
+}
+
+is_merge_base_ok() {
+	grep "^$1 $2 ok$" "$GIT_DIR/BISECT_MERGE_BASES" >/dev/null 2>&1
+}
+
+mark_merge_base_ok() {
+	echo "$1 $2 ok" >> "$GIT_DIR/BISECT_MERGE_BASES"
+}
+
+is_testing_merge_base() {
+	grep "^testing $1$" "$GIT_DIR/BISECT_MERGE_BASES" >/dev/null 2>&1
+}
+
+mark_testing_merge_base() {
+	echo "testing $1" >> "$GIT_DIR/BISECT_MERGE_BASES"
+}
+
+handle_bad_merge_base() {
+	_badmb="$1"
+	_g="$2"
+	if is_testing_merge_base "$_badmb"; then
+		cat >&2 <<EOF
+The merge base $_badmb is bad.
+This means the bug has been fixed between $_badmb and $_g.
+EOF
+		exit 3
+	else
+		cat >&2 <<EOF
+Some good revs are not ancestor of the bad rev.
+git bisect cannot work properly in this case.
+Maybe you mistake good and bad revs?
+EOF
+		exit 1
+	fi
+}
+
+handle_skipped_merge_base() {
+	_bad="$1"
+	_g="$2"
+	_mb="$3"
+	cat >&2 <<EOF
+Warning: the merge base between $_bad and $_g must be skipped.
+So we cannot be sure the first bad commit is between $_mb and $_bad.
+We continue anyway.
+EOF
+	mark_merge_base_ok "$_bad" "$_g"
+}
+
+check_merge_bases() {
+	_bad="$1"
+	_good="$2"
+	_skip="$3"
+	for _g in $_good; do
+		is_merge_base_ok "$_bad" "$_g" && continue
+		_mb=$(git merge-base $_g $_bad)
+		if test "$_mb" = "$_g" || is_among "$_mb" "$_good"; then
+			mark_merge_base_ok "$_bad" "$_g"
+		elif test "$_mb" = "$_bad"; then
+			handle_bad_merge_base "$_bad" "$_g"
+		elif is_among "$_mb" "$_skip"; then
+			handle_skipped_merge_base "$_bad" "$_g" "_mb"
+		else
+			mark_testing_merge_base "$_mb"
+			checkout "$_mb" "a merge base must be tested"
+			checkout_done=1
+			break
+		fi
+	done
+}
+
+check_good_are_ancestors_of_bad() {
+	test -f "$GIT_DIR/BISECT_ANCESTORS_OK" && return
+	_bad="$1"
+	_good=$(echo $2 | sed -e 's/\^//g')
+	_skip="$3"
+	_side=$(git rev-list $_good ^$_bad)
+	if test -n "$_side"; then
+		check_merge_bases "$_bad" "$_good" "$_skip" || return
+		test "$checkout_done" -eq "1" && return
+	fi
+	: > "$GIT_DIR/BISECT_ANCESTORS_OK"
+}
+
 bisect_next() {
 	case "$#" in 0) ;; *) usage ;; esac
 	bisect_autostart
 	bisect_next_check good
 
+	# Get bad, good and skipped revs
+	bad=$(git rev-parse --verify refs/bisect/bad) &&
+	good=$(git for-each-ref --format='^%(objectname)' \
+		"refs/bisect/good-*" | tr '\012' ' ') &&
 	skip=$(git for-each-ref --format='%(objectname)' \
-		"refs/bisect/skip-*" | tr '\012' ' ') || exit
+		"refs/bisect/skip-*" | tr '\012' ' ') &&
 
+	# Maybe some merge bases must be tested first
+	check_good_are_ancestors_of_bad "$bad" "$good" "$skip" || exit
+	test "$checkout_done" -eq "1" && checkout_done='' && return
+
+	# Get bisection information
 	BISECT_OPT=''
 	test -n "$skip" && BISECT_OPT='--bisect-all'
-
-	bad=$(git rev-parse --verify refs/bisect/bad) &&
-	good=$(git for-each-ref --format='^%(objectname)' \
-		"refs/bisect/good-*" | tr '\012' ' ') &&
 	eval="git rev-list --bisect-vars $BISECT_OPT $good $bad --" &&
 	eval="$eval $(cat "$GIT_DIR/BISECT_NAMES")" &&
 	eval=$(filter_skipped "$eval" "$skip") &&
@@ -365,9 +452,7 @@ bisect_next() {
 	# commit is also a "skip" commit (see above).
 	exit_if_skipped_commits "$bisect_rev"
 
-	echo "Bisecting: $bisect_nr revisions left to test after this"
-	git checkout -q "$bisect_rev" || exit
-	git show-branch "$bisect_rev"
+	checkout "$bisect_rev" "$bisect_nr revisions left to test after this"
 }
 
 bisect_visualize() {
@@ -414,6 +499,8 @@ bisect_clean_state() {
 	do
 		git update-ref -d $ref $hash || exit
 	done
+	rm -f "$GIT_DIR/BISECT_MERGE_BASES" &&
+	rm -f "$GIT_DIR/BISECT_ANCESTORS_OK" &&
 	rm -f "$GIT_DIR/BISECT_LOG" &&
 	rm -f "$GIT_DIR/BISECT_NAMES" &&
 	rm -f "$GIT_DIR/BISECT_RUN" &&
diff --git a/t/t6030-bisect-porcelain.sh b/t/t6030-bisect-porcelain.sh
index 0626544..bf24b9a 100755
--- a/t/t6030-bisect-porcelain.sh
+++ b/t/t6030-bisect-porcelain.sh
@@ -350,6 +350,47 @@ 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 'side branch creation' '
+	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_expect_success 'good merge base when good and bad are siblings' '
+	git bisect start "$HASH7" "$SIDE_HASH7" > my_bisect_log.txt &&
+	grep "merge base must be tested" my_bisect_log.txt &&
+	grep $HASH4 my_bisect_log.txt &&
+	git bisect good > my_bisect_log.txt &&
+	test_must_fail grep "merge base must be tested" my_bisect_log.txt &&
+	grep $HASH6 my_bisect_log.txt &&
+	git bisect reset
+'
+test_expect_success 'skipped merge base when good and bad are siblings' '
+	git bisect start "$SIDE_HASH7" "$HASH7" > my_bisect_log.txt &&
+	grep "merge base must be tested" my_bisect_log.txt &&
+	grep $HASH4 my_bisect_log.txt &&
+	git bisect skip > my_bisect_log.txt 2>&1 &&
+	grep "Warning" my_bisect_log.txt &&
+	grep $SIDE_HASH6 my_bisect_log.txt &&
+	git bisect reset
+'
+
+test_expect_success 'bad merge base when good and bad are siblings' '
+	git bisect start "$HASH7" HEAD > my_bisect_log.txt &&
+	grep "merge base must be tested" my_bisect_log.txt &&
+	grep $HASH4 my_bisect_log.txt &&
+	test_must_fail git bisect bad > my_bisect_log.txt 2>&1 &&
+	grep "merge base $HASH4 is bad" my_bisect_log.txt &&
+	grep "fixed between $HASH4 and $SIDE_HASH7" my_bisect_log.txt &&
+	git bisect reset
+'
+
 #
 #
 test_done
-- 
1.5.6.2.221.g6ad9a

Re: [PATCH] bisect: test merge base if good rev is not an ancestor of bad rev

[Johannes Schindelin]

Hi,

On Thu, 10 Jul 2008, Christian Couder wrote:

> Before this patch, "git bisect", when it was given some good revs that 
> are not ancestor of the bad rev, didn't check if the merge bases were 
> good. "git bisect" just supposed that the user knew what he was doing, 
> and that, when he said the revs were good, he knew that it meant that 
> all the revs in the history leading to the good revs were also 
> considered good.

Well, it is not completely relying on the user.

The common scenario before a bisect is this: something used to work _all 
the time_, and all of a sudden, it does not anymore.

So it is expected that there is no fix in the history.  Not in the current 
branch, not in the "good" branch, not wherever.

In that case, you are literally guaranteed that all ancestors of a good 
commit are good, too, because if there was a bad one, there would be a 
fix, too.

The whole idea of "bisect" relies on that idea, that any ancestor of a 
good commit is good.  Otherwise you'd have to check the commits one by 
one, not in a bisecting manner.

Ciao,
Dscho

Re: [PATCH] bisect: test merge base if good rev is not an ancestor of bad rev

[Christian Couder]

Hi,

Le jeudi 10 juillet 2008, Johannes Schindelin a écrit :
> Hi,
>
> On Thu, 10 Jul 2008, Christian Couder wrote:
> > Before this patch, "git bisect", when it was given some good revs that
> > are not ancestor of the bad rev, didn't check if the merge bases were
> > good. "git bisect" just supposed that the user knew what he was doing,
> > and that, when he said the revs were good, he knew that it meant that
> > all the revs in the history leading to the good revs were also
> > considered good.
>
> Well, it is not completely relying on the user.

Yeah it's relying on statistics too.

> The common scenario before a bisect is this: something used to work _all
> the time_, and all of a sudden, it does not anymore.

I agree that it is the most common scenario, perhaps 95% or perhaps even 99% 
or more. But mistakes and special cases happens too.

For example people can forget to apply in the trunk a fix that is in a side 
branch. Or they can revert in a side branch a big buggy feature just before 
making a minor release; but in the trunk the big buggy feature is still 
there and may very well have introduced regressions.

> So it is expected that there is no fix in the history.  Not in the
> current branch, not in the "good" branch, not wherever.
>
> In that case, you are literally guaranteed that all ancestors of a good
> commit are good, too, because if there was a bad one, there would be a
> fix, too.

Yeah, in that case...

> The whole idea of "bisect" relies on that idea, that any ancestor of a
> good commit is good.  Otherwise you'd have to check the commits one by
> one, not in a bisecting manner.

No, you just need to check that the merge bases between the bad rev on one 
side and each good rev on the other side are good too. And if that is the 
case, then you can be sure that bisection will point to a first bad commit.

So the choice is between a simple and fast but not fully reliable bisect, or 
a more complex and slower but fully reliable bisect.

Regards,
Christian.

Re: [PATCH] bisect: test merge base if good rev is not an ancestor of bad rev

[Junio C Hamano]

Christian Couder <chriscool@tuxfamily.org> writes:

> Yeah, in that case...
>
>> The whole idea of "bisect" relies on that idea, that any ancestor of a
>> good commit is good.  Otherwise you'd have to check the commits one by
>> one, not in a bisecting manner.

Didn't we already discuss this at length?

> No, you just need to check that the merge bases between the bad rev on one 
> side and each good rev on the other side are good too. And if that is the 
> case, then you can be sure that bisection will point to a first bad commit.
>
> So the choice is between a simple and fast but not fully reliable bisect, or 
> a more complex and slower but fully reliable bisect.

I have not looked at your implementation, but I do not think:

 - The current one is not "fully reliable"; the user needs to know what
   he is doing.  You might call it "prone to user errors".

 - "Test this merge-base before going forward, please" will add typically
   only one round of check (if you have more merge bases between good and
   bad, you need to test all of them are good to be sure), so it is not
   "slower nor more complex".

Re: [PATCH] bisect: test merge base if good rev is not an ancestor of bad rev

[Junio C Hamano]

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

> I have not looked at your implementation, but I do not think:

Sheesh.  "I *do* think"...

>  - The current one is not "fully reliable"; the user needs to know what
>    he is doing.  You might call it "prone to user errors".
>
>  - "Test this merge-base before going forward, please" will add typically
>    only one round of check (if you have more merge bases between good and
>    bad, you need to test all of them are good to be sure), so it is not
>    "slower nor more complex".

and I think it is a reasonable thing to do.

Re: [PATCH] bisect: test merge base if good rev is not an ancestor of bad rev

[Christian Couder]

Le jeudi 10 juillet 2008, Junio C Hamano a écrit :
> Christian Couder <chriscool@tuxfamily.org> writes:
> > Yeah, in that case...
> >
> >> The whole idea of "bisect" relies on that idea, that any ancestor of a
> >> good commit is good.  Otherwise you'd have to check the commits one by
> >> one, not in a bisecting manner.
>
> Didn't we already discuss this at length?

Yes, the thread is there:

http://thread.gmane.org/gmane.comp.version-control.git/86951

> > No, you just need to check that the merge bases between the bad rev on
> > one side and each good rev on the other side are good too. And if that
> > is the case, then you can be sure that bisection will point to a first
> > bad commit.
> >
> > So the choice is between a simple and fast but not fully reliable
> > bisect, or a more complex and slower but fully reliable bisect.
>
> I have not looked at your implementation, but I do think:
>
>  - The current one is not "fully reliable"; the user needs to know what
>    he is doing.  You might call it "prone to user errors".

I agree.

>  - "Test this merge-base before going forward, please" will add typically
>    only one round of check (if you have more merge bases between good and
>    bad, you need to test all of them are good to be sure), so it is not
>    "slower nor more complex".

By "slower" I meant that it would need more rounds of check on average.
By "more complex" I meant that more code is needed.

And I think you are right, all the merge bases need to be tested so I will 
send a patch on top of the patch discussed here.

Another idea to fix the problem, might be to bisect as usual and at the end 
before saying "X is first bad commit" to check if some of X parents are 
merge bases between the bad rev and a good rev. If that is the case, then 
we could ask the user to check that these parents are all good. On average 
this would probably reduce the number of revs the user must check.

Regards,
Christian.

 

Re: [PATCH] bisect: test merge base if good rev is not an ancestor of bad rev

[Johannes Schindelin]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 1178 bytes --]

Hi,

On Fri, 11 Jul 2008, Christian Couder wrote:

> Le jeudi 10 juillet 2008, Junio C Hamano a écrit :
>
> >  - "Test this merge-base before going forward, please" will add 
> >    typically only one round of check (if you have more merge bases 
> >    between good and bad, you need to test all of them are good to be 
> >    sure), so it is not "slower nor more complex".
> 
> By "slower" I meant that it would need more rounds of check on average. 
> By "more complex" I meant that more code is needed.
> 
> And I think you are right, all the merge bases need to be tested so I 
> will send a patch on top of the patch discussed here.

Good luck.  This will open the scenario where people use a proper ancestor 
as "good" revision.  In this case, you test that.  If it is "bad" you 
report that it is the _first_ one.

You are opening a can of worms here, and I doubt that this is a good idea.

git-bisect as-is has very precise, and _simple_ semantics, and users 
should really know what they are doing (i.e. not marking something as 
"good" which is on a branch containing a fix).

Trying to be too clever here might just make the whole tool rather 
useless.

Ciao,
Dscho

Re: [PATCH] bisect: test merge base if good rev is not an ancestor of bad rev

[Christian Couder]

Le vendredi 11 juillet 2008, Johannes Schindelin a écrit :
> Hi,
>
> On Fri, 11 Jul 2008, Christian Couder wrote:
> > Le jeudi 10 juillet 2008, Junio C Hamano a écrit :
> > >  - "Test this merge-base before going forward, please" will add
> > >    typically only one round of check (if you have more merge bases
> > >    between good and bad, you need to test all of them are good to be
> > >    sure), so it is not "slower nor more complex".
> >
> > By "slower" I meant that it would need more rounds of check on average.
> > By "more complex" I meant that more code is needed.
> >
> > And I think you are right, all the merge bases need to be tested so I
> > will send a patch on top of the patch discussed here.
>
> Good luck.  This will open the scenario where people use a proper
> ancestor as "good" revision.  In this case, you test that.

If a proper ancestor is used as good rev, then the merge base between this 
good rev and the bad rev is this good rev, and as it is known to be good it 
doesn't need to be tested by the user. I think my patch handles this well.

> If it is 
> "bad" you report that it is the _first_ one.
>
> You are opening a can of worms here, and I doubt that this is a good
> idea.
>
> git-bisect as-is has very precise, and _simple_ semantics, and users
> should really know what they are doing (i.e. not marking something as
> "good" which is on a branch containing a fix).

I think that users don't and can't always know what they are doing. If there 
is a revert in a branch for example, how can they know all the bugs that it 
fixes?

> Trying to be too clever here might just make the whole tool rather
> useless.

I don't think so. I think that if user can trust "git bisect" more, they 
will use it more, and in more automated ways and everyone will win in the 
end.

Regards,
Christian.

Re: [PATCH] bisect: test merge base if good rev is not an ancestor of bad rev

[Junio C Hamano]

Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:

> You are opening a can of worms here, and I doubt that this is a good idea.
>
> git-bisect as-is has very precise, and _simple_ semantics, and users 
> should really know what they are doing (i.e. not marking something as 
> "good" which is on a branch containing a fix).
>
> Trying to be too clever here might just make the whole tool rather 
> useless.

Have you read the original thread yet?  I do not think this is trying to
be clever at all, but trying to be helpful.

As you explained, bisection *requires* that Good is ancestor of Bad.

     ---o---?---?---?---x
        Good            Bad

But in real life, things are more like "Today's master does not work, but
I am sure it used to work at 1.5.6.2".  I happen to always merge all of
'maint' to 'master' before pushing them out, so a good topology is
guaranteed, but not everybody does this (it takes careful planning what to
apply to 'maint' and where to fork topics from, and maintainers are not
perfect):

              Good
          ?---o (maint)
         /
     ---?---?---?---?---x (master)
        MB              Bad

People _will_ face such a topology.  If the users Know Better, they will
test MB=$(merge-base master maint) first to see if it is broken, and then
the world will have two possibilities:

    (1)       Good
          ?---o (maint)
         /
     ---o---?---?---?---x (master)
        Good            Bad

    (2)       Good
          ?---o (maint)
         /
     ---x---?---?---?---x (master)
        Bad             Bad


If (1), you go ahead with the usual bisection.  If (2), you cannot even
bisect.  Instead, you flip good and bad to find the "fix" in the side
branch (the answer has to be either the tip of maint or one previous in
the picture) to forward port to, either by merging 'maint' to 'master' or
cherry-picking.

The idea to check merge-base first is about automating this process (I
admit I still haven't looked at Christian's patch text yet).

Re: [PATCH] bisect: test merge base if good rev is not an ancestor of bad rev

[Christian Couder]

Le vendredi 11 juillet 2008, Junio C Hamano a écrit :
>
> But in real life, things are more like "Today's master does not work, but
> I am sure it used to work at 1.5.6.2".  I happen to always merge all of
> 'maint' to 'master' before pushing them out, so a good topology is
> guaranteed, but not everybody does this (it takes careful planning what
> to apply to 'maint' and where to fork topics from, and maintainers are
> not perfect):
>
>               Good
>           ?---o (maint)
>          /
>      ---?---?---?---?---x (master)
>         MB              Bad
>
> People _will_ face such a topology.  If the users Know Better, they will
> test MB=$(merge-base master maint) first to see if it is broken, and then
> the world will have two possibilities:
>
>     (1)       Good
>           ?---o (maint)
>          /
>      ---o---?---?---?---x (master)
>         Good            Bad
>
>     (2)       Good
>           ?---o (maint)
>          /
>      ---x---?---?---?---x (master)
>         Bad             Bad
>
>
> If (1), you go ahead with the usual bisection.  If (2), you cannot even
> bisect.  Instead, you flip good and bad to find the "fix" in the side
> branch (the answer has to be either the tip of maint or one previous in
> the picture) to forward port to, either by merging 'maint' to 'master' or
> cherry-picking.
>
> The idea to check merge-base first is about automating this process (I
> admit I still haven't looked at Christian's patch text yet).

Well in case (2) my patch does:

-------
		cat >&2 <<EOF
The merge base $_badmb is bad.
This means the bug has been fixed between $_badmb and $_g.
EOF
		exit 3
-------

but this can be improved upon in some latter patches.

Thanks,
Christian.

Re: [PATCH] bisect: test merge base if good rev is not an ancestor of bad rev

[Junio C Hamano]

Christian Couder <chriscool@tuxfamily.org> writes:

> Le vendredi 11 juillet 2008, Junio C Hamano a écrit :
>>
>>     (2)       Good
>>           ?---o (maint)
>>          /
>>      ---x---?---?---?---x (master)
>>         Bad             Bad
>>
>>
>> If (1), you go ahead with the usual bisection.  If (2), you cannot even
>> bisect.  Instead, you flip good and bad to find the "fix" in the side
>> branch (the answer has to be either the tip of maint or one previous in
>> the picture) to forward port to, either by merging 'maint' to 'master' or
>> cherry-picking.
>>
>> The idea to check merge-base first is about automating this process (I
>> admit I still haven't looked at Christian's patch text yet).
>
> Well in case (2) my patch does:
>
> -------
> 		cat >&2 <<EOF
> The merge base $_badmb is bad.
> This means the bug has been fixed between $_badmb and $_g.
> EOF
> 		exit 3
> -------
>
> but this can be improved upon in some latter patches.

I think such an "improvement" is getting close to being too clever.  I
should have worded my description on what you would do in (2) a bit more
carefully.

    If (2), you cannot even bisect.

    Instead, you may decide to merge 'maint' to 'master' to get that fix.
    In which case you do not have to worry about it; you do not do
    anything further.

    If you cannot afford to merge 'maint' to 'master' but somehow need to
    forward port the fix by cherry-picking, you need to flip good and bad
    to find the "fix" in the side branch (the answer has to be either the
    tip of maint or one previous in the picture).

Re: [PATCH] bisect: test merge base if good rev is not an ancestor of bad rev

[Johannes Schindelin]

Hi,

On Thu, 10 Jul 2008, Junio C Hamano wrote:

> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:
> 
> > You are opening a can of worms here, and I doubt that this is a good idea.
> >
> > git-bisect as-is has very precise, and _simple_ semantics, and users 
> > should really know what they are doing (i.e. not marking something as 
> > "good" which is on a branch containing a fix).
> >
> > Trying to be too clever here might just make the whole tool rather 
> > useless.
> 
> Have you read the original thread yet?  I do not think this is trying to
> be clever at all, but trying to be helpful.
> 
> As you explained, bisection *requires* that Good is ancestor of Bad.

Thanks, I got that already.

Of course it can be that the user commits a pilot error and says "but that 
unrelated version was good", while the fork point(s) between good and bad 
was bad (and this might be even the intention of the user, to find _one_ 
commit that introduced the bug).

Speaking of plural, what if some of the merge bases are good, some are 
bad?

Without carefully thinking it through, you might even _break_ the tool.

All I was proposing is keeping the current semantics, keeping the 
mechanism simple, and therefore reliable.

Ciao,
Dscho

Re: [PATCH] bisect: test merge base if good rev is not an ancestor of bad rev

[Junio C Hamano]

Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:

> On Thu, 10 Jul 2008, Junio C Hamano wrote:
>
>> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:
>> 
> Of course it can be that the user commits a pilot error and says "but that 
> unrelated version was good", while the fork point(s) between good and bad 
> was bad (and this might be even the intention of the user, to find _one_ 
> commit that introduced the bug).
>
> Speaking of plural, what if some of the merge bases are good, some are 
> bad?
>
> Without carefully thinking it through, you might even _break_ the tool.

And you think it is better to make all of your _users_ think it through
every time?  Isn't it more error prone?

> All I was proposing is keeping the current semantics, keeping the 
> mechanism simple, and therefore reliable.

What I suggested to Christian (sorry, I've been busy and I still haven't
checked if that is what was implemented in the patch -- that is why I
suggested you to read the original thread) was:

	- check good and bad to see if they are forked

        - iff they are,

          - have the user check merge bases and make sure they are all
            good.  otherwise, the initial good/bad pair is unsuitable for
            bisection, so explain the situation and quit [*1*];

	  - otherwise, keep these good markers.

	- do the usual bisection --- from this point on it is "simple and
          reliable as it has always been".

And I do not think adding the "pre-check" stage before going into the main
part of the processing that we have always done is against "keeping the
mechanism simple and reliable".

[Footnote]

*1* We _could_ make things more complex by offering to swap good and bad
at this point and then continue bisecting to find a commit to cherry-pick
to forward port the fix.  Arguably, that step would be a new code and
could start out to be buggy --- it _could_ be called destabilizing what
has been reliable, but even then, it would be a separate codepath and a
new bug will be something that triggers only when the user accepts that
offer.  I do not see what the big deal is that you seem to be worried
about.

Re: [PATCH] bisect: test merge base if good rev is not an ancestor of bad rev

[Johannes Schindelin]

Hi,

On Thu, 10 Jul 2008, Junio C Hamano wrote:

> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:
> 
> > On Thu, 10 Jul 2008, Junio C Hamano wrote:
> >
> >> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:
> >> 
> > Of course it can be that the user commits a pilot error and says "but 
> > that unrelated version was good", while the fork point(s) between good 
> > and bad was bad (and this might be even the intention of the user, to 
> > find _one_ commit that introduced the bug).
> >
> > Speaking of plural, what if some of the merge bases are good, some are 
> > bad?
> >
> > Without carefully thinking it through, you might even _break_ the tool.
> 
> And you think it is better to make all of your _users_ think it through
> every time?  Isn't it more error prone?

Maybe I am alone here, but except for that occasion that triggered my 
"fixed/unfixed" patch, I did have to think, in order to use git-bisect.  I 
said "git bisect start && git bisect bad HEAD && git bisect good 
HEAD@{1.day.ago}", and then follow the instructions.

> > All I was proposing is keeping the current semantics, keeping the 
> > mechanism simple, and therefore reliable.
> 
> What I suggested to Christian (sorry, I've been busy and I still haven't 
> checked if that is what was implemented in the patch -- that is why I 
> suggested you to read the original thread) was:
> 
> 	- check good and bad to see if they are forked
> 
>         - iff they are,
> 
>           - have the user check merge bases and make sure they are all
>             good.  otherwise, the initial good/bad pair is unsuitable for
>             bisection, so explain the situation and quit [*1*];
> 
> 	  - otherwise, keep these good markers.
> 
> 	- do the usual bisection --- from this point on it is "simple and
>           reliable as it has always been".

Okay, that seems like a trivial and good patch.

> *1* We _could_ make things more complex by offering to swap good and bad
> at this point and then continue bisecting to find a commit to cherry-pick
> to forward port the fix.  Arguably, that step would be a new code and
> could start out to be buggy --- it _could_ be called destabilizing what
> has been reliable, but even then, it would be a separate codepath and a
> new bug will be something that triggers only when the user accepts that
> offer.  I do not see what the big deal is that you seem to be worried
> about.

That is what I am actually scared off.  That in the wake of a nice and 
trivial patch, things get muddied and complicated like back when "rebase 
-i -m" was made unusable for the layman.

Ciao,
Dscho

Re: [PATCH] bisect: test merge base if good rev is not an ancestor of bad rev

[Junio C Hamano]

Christian Couder <chriscool@tuxfamily.org> writes:

> Another idea to fix the problem, might be to bisect as usual and at the end 
> before saying "X is first bad commit" to check if some of X parents are 
> merge bases between the bad rev and a good rev. If that is the case, then 
> we could ask the user to check that these parents are all good. On average 
> this would probably reduce the number of revs the user must check.

I do not think that would fly well.  After spending long bisection cycle,
you will be telling the user that it was a wild goose chase (iow, the user
did an invalid bisection and what we stopped at was not the first
breakage).  If the bisection topology is invalid, we should tell the user
before he wastes too much time.

The sad part is that the biesction log from such an initial round would
not be very useful for reusing even if the user then chooses to hunt for
the "fix" on the side branch to forward port, in which case the meaning of
good and bad needs to be swapped from the beginning.

Re: [PATCH] bisect: test merge base if good rev is not an ancestor of bad rev

[Christian Couder]

Le vendredi 11 juillet 2008, Christian Couder a écrit :
> Le jeudi 10 juillet 2008, Junio C Hamano a écrit :
> > Christian Couder <chriscool@tuxfamily.org> writes:
> > > Yeah, in that case...
> > >
> > >> The whole idea of "bisect" relies on that idea, that any ancestor of
> > >> a good commit is good.  Otherwise you'd have to check the commits
> > >> one by one, not in a bisecting manner.
> >
> > Didn't we already discuss this at length?
>
> Yes, the thread is there:
>
> http://thread.gmane.org/gmane.comp.version-control.git/86951
>
> > > No, you just need to check that the merge bases between the bad rev
> > > on one side and each good rev on the other side are good too. And if
> > > that is the case, then you can be sure that bisection will point to a
> > > first bad commit.
> > >
> > > So the choice is between a simple and fast but not fully reliable
> > > bisect, or a more complex and slower but fully reliable bisect.
> >
> > I have not looked at your implementation, but I do think:
> >
> >  - The current one is not "fully reliable"; the user needs to know what
> >    he is doing.  You might call it "prone to user errors".
>
> I agree.
>
> >  - "Test this merge-base before going forward, please" will add
> > typically only one round of check (if you have more merge bases between
> > good and bad, you need to test all of them are good to be sure), so it
> > is not "slower nor more complex".
>
> By "slower" I meant that it would need more rounds of check on average.
> By "more complex" I meant that more code is needed.
>
> And I think you are right, all the merge bases need to be tested so I
> will send a patch on top of the patch discussed here.

Ok, here is an untested patch that should check all merge bases. I don't 
have time right now to add tests and a good commit message but I will do 
that when I come back from vacancy in about one week. So please consider it 
as just a RFC.

Thanks,
Christian.

-----8<------------

[PATCH] bisect: check all merge bases instead of only one


Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
---
 git-bisect.sh |   29 +++++++++++++++--------------
 1 files changed, 15 insertions(+), 14 deletions(-)

diff --git a/git-bisect.sh b/git-bisect.sh
index 50f912f..ca16609 100755
--- a/git-bisect.sh
+++ b/git-bisect.sh
@@ -375,7 +375,6 @@ Warning: the merge base between $_bad and $_g must be 
skipped.
 So we cannot be sure the first bad commit is between $_mb and $_bad.
 We continue anyway.
 EOF
-	mark_merge_base_ok "$_bad" "$_g"
 }
 
 check_merge_bases() {
@@ -384,19 +383,21 @@ check_merge_bases() {
 	_skip="$3"
 	for _g in $_good; do
 		is_merge_base_ok "$_bad" "$_g" && continue
-		_mb=$(git merge-base $_g $_bad)
-		if test "$_mb" = "$_g" || is_among "$_mb" "$_good"; then
-			mark_merge_base_ok "$_bad" "$_g"
-		elif test "$_mb" = "$_bad"; then
-			handle_bad_merge_base "$_bad" "$_g"
-		elif is_among "$_mb" "$_skip"; then
-			handle_skipped_merge_base "$_bad" "$_g" "_mb"
-		else
-			mark_testing_merge_base "$_mb"
-			checkout "$_mb" "a merge base must be tested"
-			checkout_done=1
-			break
-		fi
+		for _mb in $(git merge-base --all $_g $_bad); do
+			if test "$_mb" = "$_g" || is_among "$_mb" "$_good"; then
+				continue
+			elif test "$_mb" = "$_bad"; then
+				handle_bad_merge_base "$_bad" "$_g"
+			elif is_among "$_mb" "$_skip"; then
+				handle_skipped_merge_base "$_bad" "$_g" "_mb"
+			else
+				mark_testing_merge_base "$_mb"
+				checkout "$_mb" "a merge base must be tested"
+				checkout_done=1
+				return
+			fi
+		done
+		mark_merge_base_ok "$_bad" "$_g"
 	done
 }
 
-- 
1.5.6.2.221.gf54e0.dirty

Re: [PATCH] bisect: test merge base if good rev is not an ancestor of bad rev

[Johannes Schindelin]

Hi,

On Sun, 13 Jul 2008, Christian Couder wrote:

> [PATCH] bisect: check all merge bases instead of only one

It would have been so much nicer to squash the two patches into one, as we 
generally frown upon "let's submit one patch that we know is faulty, and 
then another that fixes it".  That's so CVS/SVN.

> @@ -384,19 +383,21 @@ check_merge_bases() {
>  	_skip="$3"
>  	for _g in $_good; do

I really wonder if we can be blessed with less ugly variable names.  Maybe 
some that do not start with an underscore for no apparent reason, and 
maybe some that are longer than one letter, so that you have a chance to 
understand later what it is supposed to contain.  I.e. something like:

	for good in $good_revisions
	do

(You see that I also broke up the "for" and "do" into two lines, as is 
common practice in the rest of Git's shell code.)

>  		is_merge_base_ok "$_bad" "$_g" && continue
> -		_mb=$(git merge-base $_g $_bad)
> -		if test "$_mb" = "$_g" || is_among "$_mb" "$_good"; then
> -			mark_merge_base_ok "$_bad" "$_g"
> -		elif test "$_mb" = "$_bad"; then
> -			handle_bad_merge_base "$_bad" "$_g"
> -		elif is_among "$_mb" "$_skip"; then
> -			handle_skipped_merge_base "$_bad" "$_g" "_mb"
> -		else
> -			mark_testing_merge_base "$_mb"
> -			checkout "$_mb" "a merge base must be tested"
> -			checkout_done=1
> -			break
> -		fi
> +		for _mb in $(git merge-base --all $_g $_bad); do
> +			if test "$_mb" = "$_g" || is_among "$_mb" "$_good"; then
> +				continue
> +			elif test "$_mb" = "$_bad"; then
> +				handle_bad_merge_base "$_bad" "$_g"
> +			elif is_among "$_mb" "$_skip"; then
> +				handle_skipped_merge_base "$_bad" "$_g" "_mb"
> +			else
> +				mark_testing_merge_base "$_mb"
> +				checkout "$_mb" "a merge base must be tested"
> +				checkout_done=1
> +				return
> +			fi
> +		done
> +		mark_merge_base_ok "$_bad" "$_g"
>  	done
>  }

I really wonder if we cannot do better than that, in terms of code 
complexity.

For example, I wonder if we should special-case the start, and not just 
check everytime if there are unchecked merge bases instead.  If there are, 
check the first.

But that can wait until you come back from your vacation...

Have fun,
Dscho

Re: [PATCH] bisect: test merge base if good rev is not an ancestor of bad rev

[Christian Couder]

Hi,

Le dimanche 13 juillet 2008, Johannes Schindelin a écrit :
> Hi,
>
> On Sun, 13 Jul 2008, Christian Couder wrote:
> > [PATCH] bisect: check all merge bases instead of only one
>
> It would have been so much nicer to squash the two patches into one, as
> we generally frown upon "let's submit one patch that we know is faulty,
> and then another that fixes it".  That's so CVS/SVN.

I didn't think the first one was "faulty". It just didn't fix everything.

> > @@ -384,19 +383,21 @@ check_merge_bases() {
> >  	_skip="$3"
> >  	for _g in $_good; do
>
> I really wonder if we can be blessed with less ugly variable names. 
> Maybe some that do not start with an underscore for no apparent reason,

There is a reason though. It's because in "bisect_next", variables with 
those names ("good", "bad" and "skip") are already used, so reusing the 
same name is not easily possible.

> and maybe some that are longer than one letter, so that you have a chance
> to understand later what it is supposed to contain.  I.e. something like:
>
> 	for good in $good_revisions
> 	do
>
> (You see that I also broke up the "for" and "do" into two lines, as is
> common practice in the rest of Git's shell code.)

There are other places in git-bisect.sh where "for" and "do" are in the same 
line. Perhaps one day I will submit a patch to fix these.

> >  		is_merge_base_ok "$_bad" "$_g" && continue
> > -		_mb=$(git merge-base $_g $_bad)
> > -		if test "$_mb" = "$_g" || is_among "$_mb" "$_good"; then
> > -			mark_merge_base_ok "$_bad" "$_g"
> > -		elif test "$_mb" = "$_bad"; then
> > -			handle_bad_merge_base "$_bad" "$_g"
> > -		elif is_among "$_mb" "$_skip"; then
> > -			handle_skipped_merge_base "$_bad" "$_g" "_mb"
> > -		else
> > -			mark_testing_merge_base "$_mb"
> > -			checkout "$_mb" "a merge base must be tested"
> > -			checkout_done=1
> > -			break
> > -		fi
> > +		for _mb in $(git merge-base --all $_g $_bad); do
> > +			if test "$_mb" = "$_g" || is_among "$_mb" "$_good"; then
> > +				continue
> > +			elif test "$_mb" = "$_bad"; then
> > +				handle_bad_merge_base "$_bad" "$_g"
> > +			elif is_among "$_mb" "$_skip"; then
> > +				handle_skipped_merge_base "$_bad" "$_g" "_mb"
> > +			else
> > +				mark_testing_merge_base "$_mb"
> > +				checkout "$_mb" "a merge base must be tested"
> > +				checkout_done=1
> > +				return
> > +			fi
> > +		done
> > +		mark_merge_base_ok "$_bad" "$_g"
> >  	done
> >  }
>
> I really wonder if we cannot do better than that, in terms of code
> complexity.
>
> For example, I wonder if we should special-case the start, and not just
> check everytime if there are unchecked merge bases instead.  If there
> are, check the first.

In fact, there was such a thing in my patch, search 
for "$GIT_DIR/BISECT_ANCESTORS_OK". But it was a little bit broken if 
people didn't test the commit that "git bisect" suggested.

In the next version I will post just after this mail, this is in the 2/2 
patch (and hopefully fixed).

> But that can wait until you come back from your vacation...
>
> Have fun,
> Dscho

Thanks,
Christian.