Re: Comments on recursive merge..

On Wed, 9 Nov 2005, Junio C Hamano wrote:

As you pointed out, still_interesting means "after we are done
with this commit, do we still have something interesting to be
processed?", and the later "extra < 0" check compensates for
this.  After I pop the last interesting commit, I still look at
its parents and push them back into the list.

That "extra" check only helps once. If we ever hit the "extra--", it's 
gone.

In other words, follow this:

 - we start out with "extra = 0" (default value)
 - we've got one "interesting" commit left, and we just popped it.
 - we now have "still_interesting = 0"
 - the commit has just one parent, and it's not something we've seen 
   before, so we add it to the seen list and decrement "extra", which is 
   now -1. We then insert it back to the list.
 - we go back up, pop the thing we just got, and now there are again no 
   interesting commits on the list any more, so "still_interesting = 0".
 - now "extra" is -1, and we break out of the loop without ever 
   percolating the flags of this commit to its parents.

No?

It seems to be doing the right thing after all.  I hate to admit it, but 
I have been having hard time figuring out how this thing works X-<.  In 
the meantime, I've checked commits from linux-2.6 history that have more 
than one merge-base candidates.

I'm not very impressed by "it works for the seven cases I tried".

It's entirely possible that there _is_ some reason it always works, but if 
so, I'd like to understand it. More likely, it works in _practice_ because 
the only way to trigger anything else is likely such a perverse commit 
history that you'd never see it, but hey..

Also, I don't think this has necessarily anything to do with "multiple 
merge bases". As far as I can tell, we can find a potential "merge base" 
that starts the culling of uniniteresting things, but some other branch 
(that we haven't followed yet - perhaps the one we just broke out of 
early) may end up causing an _earlier_ commit to turn out to also be a 
merge-base, and the merge-base we found originally turns out to be a 
parent of the new one, and thus totally uninteresting.

See what I'm saying? Even with just _one_ well-defined merge base, we 
might hit it.

It so happens that because we traverse the commit history in date order, 
we almost never (but the keyword here is _almost_) hit the case where a 
child of a commit ends up being parsed _after_ the commit that is its 
parent. That only happens when there are non-synchronized clocks etc, and 
there are very few cases of that in the kernel tree.

Just to see how rare that is, do this:

	git-rev-list --pretty=raw HEAD |
		grep '^committer' |
		cut -d'>' -f2 |
		cut -d' ' -f2 > date-list

which basically generates the list of dates of commits in the kernel tree, 
sorted in the natural order that we always traverse the commits in.

Now, do

	sort -nr date-list | diff -u date-list -

to see how often the dates are off. I'm seeing only _three_ commits that 
have time-warps (ie they were "earlier" than one of their parents). Out of 
13,000+.

So walking things in date order _almost_ always does the right thing just 
by mistake (well, it's not "mistake", of course. It's by design: it's the 
closest we can get to a nice balanced walk. But the point is that it's 
still just a heuristic, not something we can absolutely depend on).

And THAT was the reason for the problem with the original git-merge-base 
algorithm. Not multiple merge-bases (which was admittedly another 
problem), but the fact that it didn't give the right merge-base at all due 
to time warps.

(Again - it may be that there's something in show-branch that makes the 
optimization valid, but I just don't understand it).

			Linus