Re: Comments on recursive merge..

From: Linus Torvalds <torvalds@osdl.org>
Date: Nov 8, 2005, 23:05 UTC
Message-ID: <Pine.LNX.4.64.0511081450080.3247@g5.osdl.org>
In-Reply-To: <20051108223609.GA4805@c165.ib.student.liu.se>

On Tue, 8 Nov 2005, Fredrik Kuivinen wrote:

Show 7 quoted lines

> 
> The problem is in the multiple-common-ancestors case. If we have three
> common ancestors, A, B and C, we will start with merging A with B. The
> result is a new 'virtual' commit object (not stored in the object
> database), lets call it V. We are then going to merge V with C. To do
> that we need to get the common ancestor(s) of V and C, and as V
> doesn't exist in the database we can't use git-merge-base.

Hmm. That's really the same as the merge-base of "C _and_ (A _or_ B)", isn't it?

So we should be able to do that even without ever seeing the virtual merge. In fact, it really is pretty trivial from a technical standpoint: the "A _or_ B" part is really just inserting both A and B with the same "flags" value (see the "merge_base()" function in merge-base.c).

So in general, "merge-base" could trivially be extended to have any number of "OR commits" on either side, as long as there is just one "and".

It could also be extended to have multiple "and" cases, but that has actually already been done by "git-show-branch", I think. It's all the same logic, except it uses more than just two bits.

So _technically_ it should be easy to do, it would just need some sane command line syntax to specify the grouping.

Show 6 quoted lines

> I haven't given it a lot of thought though, it might be possible to
> use git-merge-base in some way and get the same results as we get now.
> 
> It would certainly be possible to use git-merge-base in the first
> iteration and use the python code only when we actually have any
> 'virtual' commit objects.

Just handling the first case specially would be sufficient for 99% of all uses. And if the multi-parent cases are slightly slower, I don't think anybody cares.

In fact, we _always_ do the first git-merge-base in git-merge.sh anyway (actually, not git-merge-base, but "git-show-branch --merge-base"). So that's really done already for the "test if it's trivial" case..

Junio, that points out that "git-merge-base" is another program that could just be removed, since it's really supreceded by git-show-branch. Or did I miss something?

			Linus