Merge algorithms

[John Arbash Meinel]

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


...

> Specifically, when you have a criss-cross merge, you have two cases
> where X was merged with Y.  These may be different, primarily because
> you have two different users resolving the conflicts, but also because
> of differences in merge algorithms.
> 
> When there are two possible outputs of merging X with Y, LCA merge
> considers this a conflict.  weave silently resolves in favour of the
> tree being merged into.
> 
> Whether that's better or worse is a judgement call.
> 
> Aaron

That is true of some cases, but there *are* other cases that Weave
actually gets better. Specifically repeated criss-cross, especially with
more than 3 possible ancestors.


?
|\
A B
|X|\
C D |
|X /
F G
|/
H

In that case, LCA finds A & B and only uses them as the base. However, F
& G are also non-simple ancestors. If a line from G was superseded in C,
Weave can detect that, while LCA will simply see that A & B differ in
that location.

Weave takes into account all the revisions from the globally unique
ancestor (the base that merge3 uses) to the LCAs. You don't need the
revisions before or after that. You also don't need *all* of the
intermediate ones, but determining that is tricky (especially when
dealing with more than 2 simple LCAs.)

I actually read a really good algorithm describing the needs in the
Veracity source code. Marking what are interesting and non interesting
revisions.

So yes, Weave acts differently here:

?
|\
A B
|X|
C D
|/
E

IF A picks C and B picks D, then ? is a bit arbitrary depending on
whether you are merging A => B or B => A, and that is a case where LCA
choses to conflict rather than silently pick one. (Probably correctly so).

However, w/ > 2 LCAs and repeated merging and partial merging, Weave
generally does a better job. (I've found a lot of those edge cases
working through the MySQL issues.)

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

iEYEARECAAYFAkyKUNcACgkQJdeBCYSNAAOibwCeNEkeWgWiaqGBDP/yXwsjCvne
7KgAnR/1edbo1oFhjQmnjzSLu7oP8QPb
=IrGh
-----END PGP SIGNATURE-----