[MERGE] LCA Merge resolution for tree-shape

[John Arbash Meinel]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Attached is a patch which updates our tree-shape logic when a
criss-cross merge is encountered.

Specifically, instead of using a simple 3-way merge algorithm and
falling back to a very old BASE, it uses an LCA-style algorithm. There
are 2 bits that are interesting here.

1) As much as possible, we try to collapse the values for multiple
ancestors into a single value, which allows us to use a simple 3-way
merge, just with newer values. We can do this on 2 conditions:

~  a) All the LCA values are the same. This may happen because this file
~     has not been changed in an interesting way in a while. However, it
~     could still have been changed between BASE an the LCAs (if the LCAs
~     have their own common ancestors before BASE)

~  b) If one LCA value is a head(). We don't use a perfect test for this,
~     but we use some simple checks that work (comparing with BASE). This
~     handles when only one side would have made a change.

This by itself reduces a lot of the conflicts. Because it allows you to
use "recent" common ancestors rather than old ones.

2) There is also a bit of code to handle when THIS or OTHER is an lca
value, but the other one is not. In the documentation I discuss this,
and why I think it is valid.

I disable this check for file contents, because I feel it is valid for
scalars, but not as much for mergable contents.


This comes into play dramatically for the mysql tree, as without it I
get XX path conflicts, and with it, I get only 6 (one of which is
definitely relevant, and I think the other ones are, too.) The majority
of problems where files that were cleanly deleted, but had differing
values in the LCAs, which caused the very old BASE to make it look like
THIS had modified a file which it had not.


There are a few edge cases that I could come up with, which I don't
think are worth handling yet, which I added as XFAIL tests. This is
already significantly better than what we have.


Unfortunately, this patch is built on top of 2-other patches that I have
submitted for review, which haven't been reviewed yet. The problem is
that they are independent patches (but I need both). So I don't have a
clean base to use "bzr send -r X..-1".

The patches are (Branch Builder supporting rename):
http://bundlebuggy.aaronbentley.com/project/bzr/request/%3C488F45FF.1060702%40arbash-meinel.com%3E

and MultiWalker:
http://bundlebuggy.aaronbentley.com/project/bzr/request/%3C4880F75F.10702%40arbash-meinel.com%3E

So if someone wants to review those separately, I'll get them merged
into bzr.dev, and then re-submit this patch for review. (I suppose this
is a use-case for Aaron's stacking PreviewTree.)


I'm planning on trying to switch the default 3-way algorithm into using
this algorithm, and see if any tests break. It should be identical to
the 3-way algorithm for everything but when there is a criss-cross
merge. So I would expect everything to still pass.

This would be very helpful to the MySQL guys, so it would be nice to
sneak into a 1.6 release, but I realize it is a bigger patch, so it may
be something we want to postpone until 1.7.

John
=:->
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Cygwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAkiSGEoACgkQJdeBCYSNAAMwqwCcDIPq4olbuKIvPBBRMO+P7Bog
RqUAniwy3QUYt7ukCFcgRVIrABNkpPvg
=+WlQ
-----END PGP SIGNATURE-----
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: merge_lca_multi.patch
Url: https://lists.ubuntu.com/archives/bazaar/attachments/20080731/dd8a0854/attachment-0001.diff