[PLUGIN] Alternative merge pulls history, and finds best base.

[Robert Collins]

On Mon, 2005-07-04 at 20:04 -0500, John Arbash Meinel wrote:
> I created a new plugin, available at:
> http://bzr.arbash-meinel.com/plugins/merge/
> 
> 
> To start with, I created a RevisionPuller() class. It should handle
> branching history (since each revision can now have multiple parents).
> This might just be future alternate to the current
> branch.update_revisions (though that adds the revisions to the history).
> 
> The unfortunate side effect of multiple parents is that now you can't
> just trust branch.revision_history().
> 
> Anyway, I think I've implemented a method which uses a breadth-first
> search through the ancestry, looking for the first common ancestor. It
> is probably fairly expensive, especially if you have a very large tree,
> but I think it will give you the best answer, and for now, I'm working
> on correctness.
> 
> I'm trying to write the tests for it now so please forgive me if it is a
> little bit buggy.
> 
> Basically, it changes the merge code so that it pulls in all of the
> history from other, which doesn't exist in local, and then uses
> breadth-first-search to go through the ancestry, looking for a common
> revision. This revision is then used as base, and a normal merge is done.

This is what baz merge does - breadth first until you find a common
ancestor. It regularly does the wrong thing with trees that are not
balanced (large merges provide very short paths past many revisions. and
you end up with an extremely not-closest ancestor for some files, even
though the full trees are arguably close).

I think that a much better approach is per-file graph searches - for
each file that has a different last-modifying revision between the two
trees, decide on a base using a similar algorithm. This will give much
better results because two files that may provide mutually exclusive
'best' results can both be satisfied.

Rob




-- 
GPG key available at: <http://www.robertcollins.net/keys.txt>.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: This is a digitally signed message part
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20050705/83a59bb5/attachment.pgp