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

[John A Meinel]

Robert Collins wrote:

>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.
>
>
Doesn't that tend to get really expensive for large trees? I mean, if I
have a large tree, and I'm slowly improving it, that means that
potentially you would start a search for each.

I can see how you could have two fairly long-lived branches, which
happen to both merge a short-term branch, and then when they try to
merge eachother they would pick the short-term branch, rather than the
original split.

With bzr there is a slight difference between the main development line
(revision-history) and merges. I was thinking about looking for common
entries along there, since that indicates a more 'primary' role of the
revisions.

You could consider the primary tree and their immediate ancestors, but
not the entire ancestry.

I'm just thinking, I certainly have spent as much time thinking about it
as you have.
John
=:->

>Rob
>
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 253 bytes
Desc: OpenPGP digital signature
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20050704/5ab041dc/attachment.pgp