[MERGE] LCA Merge resolution for tree-shape

[John Arbash Meinel]

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

I'm leaving the original message to keep context about how to review this patch.
I did some testing by switching _entries3 for _entries_lca in *all* code
paths, which showed a couple edges that I was missing. Mostly tree-reference,
and using get_symlink_target() rather than ie.symlink_target since WTs don't
give correct values in InventoryEntries. text_sha1, revision, and
symlink_target are always None.

Anyway, the attached patch adds tests for all the edge cases I found
(interestingly get_file_sha1() will return None for anything that isn't a
file, but get_symlink_target() will raise IO/OSErrors if it isn't a symlink.)


John Arbash Meinel wrote:
> 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
> 

This is still pending, and in this bundle.

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

Ian was kind enough to review this, but PQM has failed to merge it 2 times so
far. (AFAICT it passes the test suite, and the PQM fails to send a
success/failure message, and I get no more feedback.)

So this is still mixed into this patch.

> 
> 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 is done, and OTHER,BASE,LCA as a working tree and tree-reference handling
were needed to get everything to pass. But it does all pass now, and I tried
hard not to implement anything without a test that would fail without it.

I know 2k line patches are not fun to review. But if it makes you feel better,
only about 600 lines are actual content changes, the rest are the tests making
sure the content is correct. :)

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

iD8DBQFIk2VgJdeBCYSNAAMRAu76AKDUBYHruAA8wl24VYmEHaaHJJZHBwCguZY7
OsyB5m9e2zPeQUrqCpr2Fjo=
=m5im
-----END PGP SIGNATURE-----
-------------- next part --------------
A non-text attachment was scrubbed...
Name: merge_lca_multi_3561.patch
Type: text/x-diff
Size: 188507 bytes
Desc: not available
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20080801/eda7159e/attachment-0001.bin