[BUG] Git bisect not finding the right commit

[BUG] Git bisect not finding the right commit

[Andreas J. Koenig]

My git versions
---------------
1.7.9.rc2 and 1.7.8.3 and 1.7.2.5

The example output below was produced with 1.7.8.3 as provided by debian
"git/unstable uptodate 1:1.7.8.3-1"

The result looks the same on all three versions. I did not do a
byte-by-byte comparison, but the outcome is the same.

The repository
--------------
http://perl5.git.perl.org/perl.git

Problem description
-------------------
After v5.15.5-20-gfd76d40 a merge happened and v5.15.4-110-g27b29ec
through v5.15.4-169-g3582575 were inserted. The code was developed
before v5.15.5 but merged after v5.15.5.

	- A -> B      ->     C - D ->
	         \         /
	          - E - F -

A v5.15.5
B v5.15.5-20-gfd76d40
C v5.15.5-81-gcfe287a
D v5.15.5-159-ga71d67b
E v5.15.4-110-g27b29ec
F v5.15.4-169-g3582575

The change in perl I tried to locate was v5.15.5-13-gff0cf12, between A
and B. Bisect did not find it, it returned me E instead. Here the wrong
bisect output:

% git bisect start v5.15.5-159-ga71d67b v5.15.5
Already on 'blead'
Bisecting: 77 revisions left to test after this (roughly 6 steps)
[cfe287a06b2ed98c25aebb477f6b400409f1fc85] Merge remote-tracking branch 'p5p/smoke-me/gsoc-pod' into blead
% git describe
v5.15.5-81-gcfe287a
% git bisect bad
Bisecting: 40 revisions left to test after this (roughly 5 steps)
[baf7658bacfa659cdab08050470b20ebd5973384] Update htmlview.t for new Pod::Html
% git describe
v5.15.4-149-gbaf7658
% git bisect bad
Bisecting: 19 revisions left to test after this (roughly 4 steps)
[fbf24e084f7e43d3caa066f3520b4c32ebbb2e3a] Start modifying test cases to suit new Pod::Html
% git describe
v5.15.4-129-gfbf24e0
% git bisect bad
Bisecting: 9 revisions left to test after this (roughly 3 steps)
[9949917516c8bca1036187e3e878ed8869558a65] Finish skeleton version of Pod::Html
% git describe
v5.15.4-119-g9949917
% git bisect bad
Bisecting: 4 revisions left to test after this (roughly 2 steps)
[953c3c52c300d440cb8e0811a812e78c12d45695] Remove spurious code after start of parser switch
% git describe
v5.15.4-114-g953c3c5
% git bisect bad
Bisecting: 2 revisions left to test after this (roughly 1 step)
[2618a74b5307cde59d3b3111031637fbe4bfe0cf] Remove cache feature for simplicity
% git describe
v5.15.4-111-g2618a74
% git bisect bad
Bisecting: 0 revisions left to test after this (roughly 0 steps)
[27b29ec338b08496d21538c0db7377d446529f8b] Remove deprecated --netscape flag
% git describe
v5.15.4-110-g27b29ec
% git bisect bad
27b29ec338b08496d21538c0db7377d446529f8b is the first bad commit
commit 27b29ec338b08496d21538c0db7377d446529f8b
Author: Marc Green <marcgreen@cpan.org>
Date:   Mon May 16 23:46:07 2011 -0400

 deprecated --netscape flag

:040000 040000 6759c516ef91450c73a01c5695051f31b787171e 080d58438a5c00aaaa6464f4c3a42c2ffd5f7ee0 M      ext
% git version
git version 1.7.8.3


What I expected
---------------
The above result is wrong, git should have found v5.15.5-13-gff0cf12.
Git seemingly did not consider the revisions between v5.15.5 and
v5.15.5-20-gfd76d40.

Let me know if you need further informations. (I'm not subscribed to the
mailing list.)

Thanks && Regards,
-- 
andreas

Re: [BUG] Git bisect not finding the right commit

[Junio C Hamano]

andreas.koenig.7os6VVqR@franz.ak.mind.de (Andreas J. Koenig) writes:

> A v5.15.5
> B v5.15.5-20-gfd76d40
> C v5.15.5-81-gcfe287a
> D v5.15.5-159-ga71d67b
> E v5.15.4-110-g27b29ec
> F v5.15.4-169-g3582575
>
> The change in perl I tried to locate was v5.15.5-13-gff0cf12, between A
> and B. Bisect did not find it, it returned me E instead. Here the wrong
> bisect output:

Just for the sake of simplicity, I'll call ff0cf12 "Q" (the Questionable
one).

> % git bisect start v5.15.5-159-ga71d67b v5.15.5

You start by telling Git that D is bad and A is good.

I can see that D does contain Q (i.e. "git log D..Q" gives nothing), which
you should read as "D is _contaminated_ by the breakage Q introduced", so
D is indeed bad.

On the other hand, A does _not_ contain Q (i.e. "git log A..Q" gives
output), which you should read as "A is _not_ contaminated by the breakage
Q introduced", so A is indeed good.

So far so good...

> Already on 'blead'
> Bisecting: 77 revisions left to test after this (roughly 6 steps)
> [cfe287a06b2ed98c25aebb477f6b400409f1fc85] Merge remote-tracking branch 'p5p/smoke-me/gsoc-pod' into blead
> % git describe
> v5.15.5-81-gcfe287a

This is your "C", and "git log C..Q" does not give anything. C is
contaminated by Q, hence it is bad.

> % git bisect bad
> Bisecting: 40 revisions left to test after this (roughly 5 steps)
> [baf7658bacfa659cdab08050470b20ebd5973384] Update htmlview.t for new Pod::Html
> % git describe
> v5.15.4-149-gbaf7658

Here, baf7658 does not contain Q, so you are supposed to answer it is
GOOD.

> % git bisect bad

But you answered that it is BAD.

Why?

What caused you to say "bad" here to a commit that could not possibly have
inherited the breakage Q introduced?

One plausible explanation is that whatever symptom you are seeing in Perl
at version Q that you call "bad" may not be caused by a single root cause,
and a similar (or the same) symptom somehow appears at this version that
is _NOT_ contaminated by Q.

Another plausible scenario is that the symptom you are chasing may not be
reliably reproducible.

"bisection" by nature is an optimization technique applicable only when
you are chasing a reliably reproducible symptom that is caused by a single
cause, a breakage that existed in a single old version that is inherited
to all its descendants, and the "bad" symptom did not appear in any
version that does not inherit the breakage from that single problematic
commit.  If you have a history A--B--C--D--E, in which B breaks something,
C fixes its breakage and then D reintroduces another breakage that shows
the same symptom, you can not optimize the search for a problem using
bisect. You need to check each and every version.

Of course, people sometimes simply get confused and mistakenly say BAD
when they wanted to say GOOD. That may be a simpler explanation of what
happened to your bisection.

Anyway, the remainder of your bisect sequence is GiGo, so I'll snip them
and will not quote.

Re: [BUG] Git bisect not finding the right commit

[Johannes Sixt]

Am 1/19/2012 4:29, schrieb Andreas J. Koenig:
> 	- A -> B      ->     C - D ->
> 	         \         /
> 	          - E - F -
> 
> A v5.15.5
> B v5.15.5-20-gfd76d40
> C v5.15.5-81-gcfe287a
> D v5.15.5-159-ga71d67b
> E v5.15.4-110-g27b29ec
> F v5.15.4-169-g3582575

I haven't looked at the actual history, but given the names of the commits
as produced by git-describe, I doubt that your history graph sketched
above is correct. Doesn't it look more like this:

      A -- B -- C -- D --
     /         /
 -- X -- E -- F

where X is v5.15.4?

To find a commit between A and B, you must declare F as "good".

-- Hannes

Re: [BUG] Git bisect not finding the right commit

[Andreas J. Koenig]

>>>>> On Thu, 19 Jan 2012 00:20:08 -0800, Junio C Hamano <gitster@pobox.com> said:

 jch> andreas.koenig.7os6VVqR@franz.ak.mind.de (Andreas J. Koenig) writes:
 >> A v5.15.5
 >> B v5.15.5-20-gfd76d40
 >> C v5.15.5-81-gcfe287a
 >> D v5.15.5-159-ga71d67b
 >> E v5.15.4-110-g27b29ec
 >> F v5.15.4-169-g3582575
 >> 
 >> The change in perl I tried to locate was v5.15.5-13-gff0cf12, between A
 >> and B. Bisect did not find it, it returned me E instead. Here the wrong
 >> bisect output:

 jch> Just for the sake of simplicity, I'll call ff0cf12 "Q" (the Questionable
 jch> one).

 >> % git bisect start v5.15.5-159-ga71d67b v5.15.5

 jch> You start by telling Git that D is bad and A is good.

 jch> I can see that D does contain Q (i.e. "git log D..Q" gives nothing), which
 jch> you should read as "D is _contaminated_ by the breakage Q introduced", so
 jch> D is indeed bad.

 jch> On the other hand, A does _not_ contain Q (i.e. "git log A..Q" gives
 jch> output), which you should read as "A is _not_ contaminated by the breakage
 jch> Q introduced", so A is indeed good.

 jch> So far so good...

 >> Already on 'blead'
 >> Bisecting: 77 revisions left to test after this (roughly 6 steps)
 >> [cfe287a06b2ed98c25aebb477f6b400409f1fc85] Merge remote-tracking branch 'p5p/smoke-me/gsoc-pod' into blead
 >> % git describe
 >> v5.15.5-81-gcfe287a

 jch> This is your "C", and "git log C..Q" does not give anything. C is
 jch> contaminated by Q, hence it is bad.

 >> % git bisect bad
 >> Bisecting: 40 revisions left to test after this (roughly 5 steps)
 >> [baf7658bacfa659cdab08050470b20ebd5973384] Update htmlview.t for new Pod::Html
 >> % git describe
 >> v5.15.4-149-gbaf7658

 jch> Here, baf7658 does not contain Q, so you are supposed to answer it is
 jch> GOOD.

 >> % git bisect bad

 jch> But you answered that it is BAD.

 jch> Why?

The reason turned out to be that a perl module that was involved in the
testing had been upgraded in the meantime (YAML-0.77 to 0.78). So your
whole answer was correctly describing the situation. From this point
GiGo started to happen because the rest of the tests involved also used
the newer version of that module while some other tests were done with
the older version.

So thank you for clearing that up!

 jch> [...]

>>>>> On Thu, 19 Jan 2012 09:23:01 +0100, Johannes Sixt <j.sixt@viscovery.net> said:

 js> Am 1/19/2012 4:29, schrieb Andreas J. Koenig:
 >> - A -> B      ->     C - D ->
 >>          \         /
 >>           - E - F -
 >> 
 >> A v5.15.5
 >> B v5.15.5-20-gfd76d40
 >> C v5.15.5-81-gcfe287a
 >> D v5.15.5-159-ga71d67b
 >> E v5.15.4-110-g27b29ec
 >> F v5.15.4-169-g3582575

 js> I haven't looked at the actual history, but given the names of the commits
 js> as produced by git-describe, I doubt that your history graph sketched
 js> above is correct. Doesn't it look more like this:

 js>       A -- B -- C -- D --
 js>      /         /
 js>  -- X -- E -- F

 js> where X is v5.15.4?

Yes, thank you for finding that out. X is actually v5.15.4-109-g3ea0c58
and since there was a long timespan between the start of the development
of the code and the merge (May-Nov), the gitk presentation got a bit
complex to read.

 js> To find a commit between A and B, you must declare F as "good".

Correct! The reason it happened described above.

Thank you folks for taking the time and making such a careful assessment!
-- 
andreas

Re: [BUG] Git bisect not finding the right commit

[Junio C Hamano]

andreas.koenig.7os6VVqR@franz.ak.mind.de (Andreas J. Koenig) writes:

>>>>>> On Thu, 19 Jan 2012 09:23:01 +0100, Johannes Sixt <j.sixt@viscovery.net> said:
>
>  js> Am 1/19/2012 4:29, schrieb Andreas J. Koenig:
>  >> - A -> B      ->     C - D ->
>  >>          \         /
>  >>           - E - F -
>  >> 
>  >> A v5.15.5
>  >> B v5.15.5-20-gfd76d40
>  >> C v5.15.5-81-gcfe287a
>  >> D v5.15.5-159-ga71d67b
>  >> E v5.15.4-110-g27b29ec
>  >> F v5.15.4-169-g3582575
>
>  js> I haven't looked at the actual history, but given the names of the commits
>  js> as produced by git-describe, I doubt that your history graph sketched
>  js> above is correct. Doesn't it look more like this:
>
>  js>       A -- B -- C -- D --
>  js>      /         /
>  js>  -- X -- E -- F
>
>  js> where X is v5.15.4?
>
> Yes, thank you for finding that out. X is actually v5.15.4-109-g3ea0c58
> and since there was a long timespan between the start of the development
> of the code and the merge (May-Nov), the gitk presentation got a bit
> complex to read.

(This is somewhat off-topic, so Andreas is on Cc: and the list is on To:)

I doubt --simplify-by-decoration alone would make it easier to view such a
complex and long history, but I wonder if we can use the same logic to
help users in a case like this. Instead of only keeping tagged versions in
the result to show topology, perhaps we can allow the user to feed a list
of "key points in history" as command line arguments and apply the same
kind of simplification to help visualizing the topology?

Re: [BUG] Git bisect not finding the right commit

[Jeff King]

On Fri, Jan 20, 2012 at 10:09:51AM -0800, Junio C Hamano wrote:

> > Yes, thank you for finding that out. X is actually v5.15.4-109-g3ea0c58
> > and since there was a long timespan between the start of the development
> > of the code and the merge (May-Nov), the gitk presentation got a bit
> > complex to read.
> 
> (This is somewhat off-topic, so Andreas is on Cc: and the list is on To:)
> 
> I doubt --simplify-by-decoration alone would make it easier to view such a
> complex and long history, but I wonder if we can use the same logic to
> help users in a case like this. Instead of only keeping tagged versions in
> the result to show topology, perhaps we can allow the user to feed a list
> of "key points in history" as command line arguments and apply the same
> kind of simplification to help visualizing the topology?

This is something I think I've wanted in the past. But unfortunately, I
can't remember the exact details, so I'm not sure how workable it would
have been. In particular, how painful is it in practice to come up with
the list of "key points" to make the graph sensible?

So I'll add my vague "yeah, that sounds good" and try to pay attention
next time the situation comes up as to whether such a feature would
actually help in practice.

-Peff