[BUG] Git bisect not finding the right commit

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.koenig.7os6VVqR@franz.ak.mind.de (Andreas J. Koenig) writes:

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

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

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

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

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.

 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> [...]

 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.koenig.7os6VVqR@franz.ak.mind.de (Andreas J. Koenig) writes:

(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?

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

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

Am 1/19/2012 4:29, schrieb Andreas J. Koenig:

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