[MERGE][1.6] Real --weave merge

[John Arbash Meinel]

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

John Arbash Meinel wrote:

...

> 4b) There is another problem with the 'grab all the ancestors' case.
> 
> ~    A
> ~   / \
> ~  B   C
> ~  |\ /|
> ~  D E F
> ~  |/ \|
> ~  G   H
> ~  |\ /|
> ~  | X |
> ~  |/ \|
> ~  I   J
> 
> In this case, grabbing all revisions which are ancestors of G & H, but
> are not ancestors of E, would include nodes 'D & F'. However, a lot of
> the lines in D & F are actually common to E, because they come from the
> ancestors A, B & C.
> At the moment, I solve this by grabbing the lca *again* between D,F and
> E. I cheat a bit, because I'm not willing to track down the rabbit whole
> forever.
> 
> Though I've also come up with a realization. We actually could prune D &
> F from the graph. It is the same argument about "we don't care *how*
> things changed E => G, just *what* changed". It just happens that adding
> common lines to a weave gets things confused, as we don't allow lines to
> converge. (Note that the codeville weave merge always uses all lines
> that have ever existed, so it *might* do better with them.)
> 
> If I was to implement this, I would walk the ancestors of G & H,
> stopping when I reach an ancestor of E. At the same time, I would keep
> track of the parent => child relationships. I would then walk the
> limited subset of the children of E, and prune anything that is an
> ancestor of G & H but not a child of E.
> 
> This would probably be a good solution, I'm just tired of walking graphs
> and merging weaves.
> 

I decided to go ahead and do this, and the code is written, and works quite
well. With some nice side effects that the merge is overall faster, etc.

The only thing I don't really like is that the helper functions are members of
_PlanMerge, when they sort of seem more like Graph functions. Though the
specifics of what gets returned and how they are used is fairly specific to
PlanMerge. (Pruning non-members in the parent_map is fairly common, but
needing the tails and child map is not, and then removing the base key and
pruning tails is fairly specific here as well.)

Anyway, this produces better results (theoretically) than the other patch, and
does so faster.

John
=:->

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

iD8DBQFIeoMSJdeBCYSNAAMRApJEAKClK2t5Ul0OsiHE9XTIgDLq/fARAACeIaBa
X4OqnvOXY0dHojQ0E32t0tg=
=Nvu1
-----END PGP SIGNATURE-----
-------------- next part --------------
A non-text attachment was scrubbed...
Name: weave_merge.patch
Type: text/x-diff
Size: 75571 bytes
Desc: not available
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20080713/a2684f06/attachment-0001.bin