← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to doc/developers/lca_tree_merging.txt

  • Committer: John Arbash Meinel
  • Date: 2008-09-05 02:29:34 UTC
  • mto: (3697.7.4 1.7)
  • mto: This revision was merged to the branch mainline in revision 3748.
  • Revision ID: john@arbash-meinel.com-20080905022934-s8692mbwpkdwi106
Cleanups to the algorithm documentation.

Show diffs side-by-side

added added

removed removed

Lines of Context:
doc/developers/lca_tree_merging.txt
1
 
====================
2
 
LCA Merge Resolution
3
 
====================
 
1
================
 
2
LCA Tree Merging
 
3
================
4
4
 
5
5
There are 2 ways that you get LCA merge resolution in bzr. First, if you use
6
 
``bzr merge --lca``, the content of files will be resolved using a Least Common
7
 
Ancestors algorithm. That is not being described here.
 
6
``bzr merge --lca``, the *content* of files will be resolved using a Least Common
 
7
Ancestors algorithm. That is described in <lca-merge.html> not here.
8
8
 
9
 
This is describing how we handle merging tree-shape when there is not a single
10
 
unique ancestor (criss-cross merge). With a single LCA, we use simple
11
 
3-way-merge logic.
 
9
This document describes how we handle merging tree-shape when there is not
 
10
a single unique ancestor (criss-cross merge). With a single LCA, we use
 
11
simple 3-way-merge logic.
12
12
 
13
13
When there are multiple possible LCAs, we use a different algorithm for
14
14
handling tree-shape merging. Described here.
57
57
2. Find the values from ``LCA1`` and ``LCA2`` which are not the same as
58
58
   ``BASE``. The idea here is to provide a rudimentary "heads" comparison.
59
59
   Often, the whole tree graph will have a criss-cross, but the per-file
60
 
   (per-scalar) graph would be linear. And the value in one LCA strictly
 
60
   (per-scalar) graph would be linear, and the value in one LCA strictly
61
61
   dominates the other. It is possible to construct a scenario where one side
62
62
   dominates the other, but the dominated value is not ``BASE``, but a second
63
63
   intermediate value. Most scalars are rarely changed, so this is unlikely to
64
 
   be an issue. And the trade-off is having to generate and inspect the
 
64
   be an issue. The trade-off is having to generate and inspect the
65
65
   per-scalar graph.
66
66
 
67
67
   If there are no LCA values that are different from ``BASE``, we use a simple
71
71
   If there is only one unique LCA value, we again use three-way merge logic
72
72
   using that unique value as the base.
73
73
 
74
 
4. At this point we have determined that we have at least 2 unique values in
 
74
4. At this point, we have determined that we have at least 2 unique values in
75
75
   our LCAs which means that ``THIS`` and ``OTHER`` would both have to resolve
76
76
   the conflict. If they resolved it in the same way, we would have caught that
77
77
   in step 1. So they either both picked a different LCA value, or one (or
78
78
   both) chose a new value to use.
79
79
 
80
 
   So at this point, if ``OTHER`` and ``THIS`` both picked a different LCA
81
 
   value, we conflict.
 
80
   If ``OTHER`` and ``THIS`` both picked a different LCA value, we conflict.
82
81
 
83
82
   If ``OTHER`` and ``THIS`` both have values that are not LCA values, we also
84
83
   conflict. (Same as 3-way, both sides modified a value in different ways.)
85
84
 
86
 
5. (optional) The only tricky part is this, if ``OTHER`` has a LCA value, but
 
85
5. (optional) The only tricky part is this: if ``OTHER`` has a LCA value, but
87
86
   ``THIS`` does not, then we go with ``THIS``, and conversely if ``THIS`` has
88
87
   an LCA value, but ``OTHER`` does not, then we go with ``OTHER``. The idea is
89
88
   that ``THIS`` and ``OTHER`` may have resolved things in the same way, and
118
117
4) ``D`` if ``B`` and ``C`` modified it
119
118
 
120
119
This means that if the last modified revision is the same, there have been no
121
 
changes in the intermediate time. And if ``OTHER`` has the same last modified
 
120
changes in the intermediate time. If ``OTHER`` also has the same last modified
122
121
revision as *any* LCA, then we know that all other LCAs' last-modified
123
122
revisions are in the ancestry of that value. (Otherwise, when ``OTHER`` would
124
123
need to create a new last modified revision as part of the merge.)