Re: [RFC, PATCH] A new merge algorithm (EXPERIMENTAL)

From: Daniel Barkalow <barkalow@iabervon.org>
Date: Aug 26, 2005, 20:48 UTC
Message-ID: <Pine.LNX.4.63.0508261558550.23242@iabervon.org>
In-Reply-To: <20050826184731.GA13629@c165.ib.student.liu.se>

On Fri, 26 Aug 2005, Fredrik Kuivinen wrote:

Show 8 quoted lines

> I will try to describe how the algorithm works. The problem with the
> usual 3-way merge algorithm is that we sometimes do not have a unique
> common ancestor. In [1] B and C seems to be equally good. What this
> algorithm does is to _merge_ the common ancestors, in this case B and
> C, into a temporary tree lets call it T. It does then use this
> temporary tree T as the common ancestor for D and E to produce the
> final merge result. In the case described in [1] this will work out
> fine and we get a clean merge with the expected result.

The only problem I can see with this is that it's likely to generate conflicts between the shared heads, and the user is going to be confused trying to resolve them, because the files with the conflicts will be missing all of the more recent changes. Other than that, I think it should give the right answer, although it will presumably involve a lot of ancient history doing the internal merge. (Which would probably be really painful if you've got two branches that cross-merge regularly and never actually completely sync)

I'm getting pretty close to having a version of read-tree that does the trivial merge portion based comparing the sides against all of the shared heads. I think yours will be better for the cases we've identified, giving the correct answer for Tony's case rather than reporting a conflict, but it's clearly more complicated. I think my changes are worthwhile anyway, since they make the merging logic more central, but obviously insufficient.

I've been thinking that could be useful to have read-tree figure out the history itself, instead of being passed ancestors, in which case it could use your method, except more efficiently (and only look further at the history when needed).

	-Daniel
*This .sig left intentionally blank*