From: Johannes Schindelin Date: Tue, 10 Jan 2006 19:38:40 GMT Subject: Re: git pull on Linux/ACPI release tree Message-ID: In-Reply-To: Hi, [cut down the Cc: list, since this is getting special] On Tue, 10 Jan 2006, Linus Torvalds wrote: > > 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. > 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. > > 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. > > 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