Use dominator for common ancestor? Weave merge?
Aaron Bentley
aaron.bentley at utoronto.ca
Tue Feb 7 17:50:14 GMT 2006
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
A problem that can occur with DVCS is criss-cross merges. These were a
source of much excitement on the Gnu Arch development list. We have
already encountered some criss-cross situations in bzr development, and
I think the problem will only increase now that we have three
integration branches.
(for more discussion of criss-cross merges, see
http://revctrl.org/CrissCrossMerge)
Here is an example criss-cross scenario:
A
/ \
B C
|\ /|
| X |
|/ \|
D E
\ /
?
In this scenario, B and C are derived from A. B-D and C-E represent two
independent branches. They merge from each other roughly simultaneously
(they may be offline when they do this, for example).
The problem is that this produces incorrect clean merges. If a change
is introduced in B, and we select B as a base, then by three-way logic,
a conflicting change in C will override the change in B. The reverse is
true if we select C as a base.
Since neither B or C can be used as a base, perhaps the correct approach
is to ignore these merges entirely-- to pretend they never happened, and
that D and E are just normal edits of B and C respectively. This means
that we will choose A as a base.
The result will be more conflicts, but they will be correct conflicts,
because D and E resolved the merge of B and C differently, and that
differing resolution must be addressed somehow. Where the resultant
texts are the same, three-way merge will not produce a conflict.
The property of A that makes it suitable in this scenario is that it is
a unique common ancestor-- the dominator of D and E. So it seems to me
that we should use the dominator as the merge base, which is also done
by Monotone.
In non-criss-cross scenarios, the dominator will be identical to the
current common ancestor picker (the common ancestor furthest from the
origin). In criss-cross scenarios, it will be a better base. So it
seems reasonable to use the dominator all the time.
Using the dominator instead of the current algorithm should also be
faster, because the dominator can be determined by walking only the
portion of the graph between the two revisions. In contrast, the
current algorithm must traverse the entire graph.
So:
1. Does anyone disagree with this analysis?
2. Does anyone feel like implementing dominator detection?
Additionally, weave merge should handle criss-cross merge better than
three-way. We still need a base to perform non-text merges, however.
3. Should we make weave merge the default?
4. Should we make weave merge dump BASE as well as THIS and OTHER?
5. Does anyone feel like reimplementing --reprocess to support weave merge?
Aaron
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org
iD8DBQFD6N3V0F+nu1YWqI0RAi00AJ9EFnxiIBUiDmpGLr3fPQTd3E/U5wCfbjvb
rhH91ttjFrS25vTHCZY+2yo=
=oAM+
-----END PGP SIGNATURE-----
More information about the bazaar
mailing list