Re: git pull on Linux/ACPI release tree

From: Johannes Schindelin <johannes.schindelin@gmx.de>
Date: Jan 10, 2006, 19:38 UTC
Message-ID: <Pine.LNX.4.63.0601102010100.27199@wbgn013.biozentrum.uni-wuerzburg.de>
In-Reply-To: <Pine.LNX.4.64.0601101048440.4939@g5.osdl.org>

Hi,

[cut down the Cc: list, since this is getting special]

On Tue, 10 Jan 2006, Linus Torvalds wrote:

Show 5 quoted lines

> > If you bisect, you test a commit. If the commit is bad, you assume *all* 
> > commits before that as bad. If it is good, you assume *all* commits after 
> > that as good.
> 
> No, that's not how bisect works at all.

Okay, so I got that wrong. But for a good reason: this is not the meaning of bisection in my lectures. Doesn't matter.

Show 9 quoted lines

> It's true that if a commit is bad, then all the commits _reachable_ from 
> that commit are considered bad. 
> 
> And it's true that if a commit is good, then all commits that _reach_ that 
> commit are considered good.
> 
> But that doesn't mean that there is an ordering. The commits that fall 
> into the camp of being "neither good nor bad" are _not_ ordered. There are 
> commits in there that are not directly reachable from the good commit.

Those commits not reachable from the good commit are of no interest. Let's just ignore them.

Show 13 quoted lines

> > Now, if you have a 2-dimensional surface, you don't have a *point*, but 
> > typically a *line* separating good from bad.
> 
> Exactly. 
> 
> And a git graph is not really a two-dimensional surface, but exactly was 
> with a 2-dimensional surface, it is _not_ enough to have a *point* to 
> separate the good from bad.
> 
> You need to have a _set of points_ to separate the good from the bad. You 
> can think of it as a line that bisects the surface: if you were to print 
> out the development graph, the set of points literally _do_ form a virtual 
> line across the development surface.

Okay, so there is a cut: Every directed path from good to bad has a single commit which is the first bad. Let's call the set of all such bad commits the cut set.

Is git-bisect capable of identifying all of the cut set, or just a single one?

> > Further, the comparison with 2 dimensions is particularly bad.
> 
> No it is not. It's a very good comparison.

>From your explanation I understand now why you like that comparison.

Show 6 quoted lines

> > So, how is bisect supposed to work if you don't have one straight 
> > development line from bad to good?
> 
> Read the code.
> 
> I'm pretty proud of it.

I bet nobody can tell ;-)

Well, I read the code. And I answer my own question from 18--19 lines ago:

git-bisect is not capable of identifying the cut set, but pretends that there really is only one bad commit (see bisect_bad()).

That may be the best choice if all commits in the cut set except one are merges. (It is the best if the cut set contains only one element.)

But I see two problems with that:

- a problem can be introduced independently in two different branches, and
  occur in both of them before the merge (in which case bisect only 
  catches one of the commits), and

- AFAICT if the cut set is one merge and one regular commit, bisect could
  identify the merge by error.

Of course, all this makes only a difference if the bisect has to cross a merge.

BTW I think there is a thinko in git-rev-list.txt:

> Thus, if 'git-rev-list --bisect foo ^bar ^baz' outputs 'midpoint', the 
> output of 'git-rev-list foo ^midpoint' and 'git-rev-list midpoint ^bar

             ^ this should be
	'git-rev-list foo ^midpoint ^bar ^baz'

> ^baz' would be of roughly the same length

Ciao, Dscho