<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>LCA Tree Merging — Bazaar 2.6.0 documentation</title>
<link rel="stylesheet" href="_static/default.css" type="text/css" />
<link rel="stylesheet" href="_static/pygments.css" type="text/css" />
<script type="text/javascript">
var DOCUMENTATION_OPTIONS = {
URL_ROOT: './',
VERSION: '2.6.0',
COLLAPSE_INDEX: false,
FILE_SUFFIX: '.html',
HAS_SOURCE: true
};
</script>
<script type="text/javascript" src="_static/jquery.js"></script>
<script type="text/javascript" src="_static/underscore.js"></script>
<script type="text/javascript" src="_static/doctools.js"></script>
<link rel="shortcut icon" href="_static/bzr.ico"/>
<link rel="top" title="Bazaar 2.6.0 documentation" href="index.html" />
<link rel="up" title="Implementation notes" href="implementation-notes.html" />
<link rel="next" title="Miscellaneous notes" href="miscellaneous-notes.html" />
<link rel="prev" title="Content Filtering" href="content-filtering.html" />
<link rel="stylesheet" href="_static/bzr-doc.css" type="text/css" />
</head>
<body>
<div class="related">
<h3>Navigation</h3>
<ul>
<li class="right" style="margin-right: 10px">
<a href="miscellaneous-notes.html" title="Miscellaneous notes"
accesskey="N">next</a></li>
<li class="right" >
<a href="content-filtering.html" title="Content Filtering"
accesskey="P">previous</a> |</li>
<li><a href="http://bazaar.canonical.com/">
<img src="_static/bzr icon 16.png" /> Home</a> | </li>
<a href="http://doc.bazaar.canonical.com/en/">Documentation</a> | </li>
<li><a href="index.html">Developer Document Catalog (2.6.0)</a> »</li>
<li><a href="implementation-notes.html" accesskey="U">Implementation notes</a> »</li>
</ul>
</div>
<div class="document">
<div class="documentwrapper">
<div class="bodywrapper">
<div class="body">
<div class="section" id="lca-tree-merging">
<h1>LCA Tree Merging<a class="headerlink" href="#lca-tree-merging" title="Permalink to this headline">¶</a></h1>
<p>There are 2 ways that you get LCA merge resolution in bzr. First, if you use
<tt class="docutils literal"><span class="pre">bzr</span> <span class="pre">merge</span> <span class="pre">--lca</span></tt>, the <em>content</em> of files will be resolved using a Least Common
Ancestors algorithm. That is described in <lca-merge.html> not here.</p>
<p>This document describes how we handle merging tree-shape when there is not
a single unique ancestor (criss-cross merge). With a single LCA, we use
simple 3-way-merge logic.</p>
<p>When there are multiple possible LCAs, we use a different algorithm for
handling tree-shape merging. Described here.</p>
<p>As a simple example, here is a revision graph which we will refer to often:</p>
<div class="highlight-python"><div class="highlight"><pre>. BASE
. / \
. LCA1 LCA2
. | \ / |
. | X |
. | / \ |
. THIS OTHER
</pre></div>
</div>
<p>In this graph, <tt class="docutils literal"><span class="pre">THIS</span></tt> and <tt class="docutils literal"><span class="pre">OTHER</span></tt> both have <tt class="docutils literal"><span class="pre">LCA1</span></tt> and <tt class="docutils literal"><span class="pre">LCA2</span></tt> in their
ancestry but neither is an ancestor of the other, so we have 2 least common
ancestors. The unique common ancestor is <tt class="docutils literal"><span class="pre">BASE</span></tt>. (It should be noted that in
this text we will talk directly about <tt class="docutils literal"><span class="pre">LCA1</span></tt> and <tt class="docutils literal"><span class="pre">LCA2</span></tt>, but the algorithms
are designed to cope with more than 2 LCAs.)</p>
<div class="section" id="scalars">
<h2>Scalars<a class="headerlink" href="#scalars" title="Permalink to this headline">¶</a></h2>
<div class="section" id="definition">
<h3>Definition<a class="headerlink" href="#definition" title="Permalink to this headline">¶</a></h3>
<p>I’m defining scalar values as ones that cannot be ‘merged’ on their own. For
example, the name of a file is “scalar”. If one person changes “foo.txt” to
“foo.c” and someone else changes “foo.txt” to “bar.txt” we don’t merge the
changes to be “bar.c”, we simply conflict and expect the user to sort it out.</p>
<p>We use a slightly different algorithm for scalars.</p>
</div>
<div class="section" id="resolution-algorithm">
<h3>Resolution Algorithm<a class="headerlink" href="#resolution-algorithm" title="Permalink to this headline">¶</a></h3>
<p>(This can be seen as <tt class="docutils literal"><span class="pre">bzrlib.merge.Merge3Merger._lca_multi_way`</span></tt></p>
<ol class="arabic">
<li><p class="first">If <tt class="docutils literal"><span class="pre">THIS</span></tt> and <tt class="docutils literal"><span class="pre">OTHER</span></tt> have the same value, use it. There is no need to
inspect any other values in this case. Either nothing was changed (all
interesting nodes would have the same value), or we have “accidental
convergence” (both sides made the same change.).</p>
</li>
<li><p class="first">Find the values from <tt class="docutils literal"><span class="pre">LCA1</span></tt> and <tt class="docutils literal"><span class="pre">LCA2</span></tt> which are not the same as
<tt class="docutils literal"><span class="pre">BASE</span></tt>. The idea here is to provide a rudimentary “heads” comparison.
Often, the whole tree graph will have a criss-cross, but the per-file
(per-scalar) graph would be linear, and the value in one LCA strictly
dominates the other. It is possible to construct a scenario where one side
dominates the other, but the dominated value is not <tt class="docutils literal"><span class="pre">BASE</span></tt>, but a second
intermediate value. Most scalars are rarely changed, so this is unlikely to
be an issue. The trade-off is having to generate and inspect the
per-scalar graph.</p>
<p>If there are no LCA values that are different from <tt class="docutils literal"><span class="pre">BASE</span></tt>, we use a simple
3-way merge with <tt class="docutils literal"><span class="pre">BASE</span></tt> as the base value.</p>
</li>
<li><p class="first">Find the unique set of LCA values that do not include the <tt class="docutils literal"><span class="pre">BASE</span></tt> value.
If there is only one unique LCA value, we again use three-way merge logic
using that unique value as the base.</p>
</li>
<li><p class="first">At this point, we have determined that we have at least 2 unique values in
our LCAs which means that <tt class="docutils literal"><span class="pre">THIS</span></tt> and <tt class="docutils literal"><span class="pre">OTHER</span></tt> would both have to resolve
the conflict. If they resolved it in the same way, we would have caught that
in step 1. So they either both picked a different LCA value, or one (or
both) chose a new value to use.</p>
<p>If <tt class="docutils literal"><span class="pre">OTHER</span></tt> and <tt class="docutils literal"><span class="pre">THIS</span></tt> both picked a different LCA value, we conflict.</p>
<p>If <tt class="docutils literal"><span class="pre">OTHER</span></tt> and <tt class="docutils literal"><span class="pre">THIS</span></tt> both have values that are not LCA values, we also
conflict. (Same as 3-way, both sides modified a value in different ways.)</p>
</li>
<li><p class="first">(optional) The only tricky part is this: if <tt class="docutils literal"><span class="pre">OTHER</span></tt> has a LCA value, but
<tt class="docutils literal"><span class="pre">THIS</span></tt> does not, then we go with <tt class="docutils literal"><span class="pre">THIS</span></tt>, and conversely if <tt class="docutils literal"><span class="pre">THIS</span></tt> has
an LCA value, but <tt class="docutils literal"><span class="pre">OTHER</span></tt> does not, then we go with <tt class="docutils literal"><span class="pre">OTHER</span></tt>. The idea is
that <tt class="docutils literal"><span class="pre">THIS</span></tt> and <tt class="docutils literal"><span class="pre">OTHER</span></tt> may have resolved things in the same way, and
then later changed the value to something newer. (They could have also
resolved it differently, and then one side updated again.)</p>
</li>
</ol>
</div>
<div class="section" id="inventoryentry-revision">
<h3><tt class="docutils literal"><span class="pre">InventoryEntry.revision</span></tt><a class="headerlink" href="#inventoryentry-revision" title="Permalink to this headline">¶</a></h3>
<p>The last-modified revision for an entry gets treated differently. This is
because how it is generated allows us to infer more information. Specifically,
any time there is a change to an entry (rename, or content change) the last
modified revision is updated. Further, if we are merging, and both sides
updated the entry, then we update the last-modified revision at the merge
point.</p>
<p>For a picture example:</p>
<div class="highlight-python"><div class="highlight"><pre>. A
. / \
. B C
. \ /
. D
</pre></div>
</div>
<p>For a single entry, the last modified revision in <tt class="docutils literal"><span class="pre">D</span></tt> is:</p>
<ol class="arabic simple">
<li><tt class="docutils literal"><span class="pre">A</span></tt> if neither <tt class="docutils literal"><span class="pre">B</span></tt> or <tt class="docutils literal"><span class="pre">C</span></tt> modified it</li>
<li><tt class="docutils literal"><span class="pre">B</span></tt> if <tt class="docutils literal"><span class="pre">B</span></tt> modified and <tt class="docutils literal"><span class="pre">C</span></tt> did not</li>
<li><tt class="docutils literal"><span class="pre">C</span></tt> if <tt class="docutils literal"><span class="pre">C</span></tt> modified and <tt class="docutils literal"><span class="pre">B</span></tt> did not</li>
<li><tt class="docutils literal"><span class="pre">D</span></tt> if <tt class="docutils literal"><span class="pre">B</span></tt> and <tt class="docutils literal"><span class="pre">C</span></tt> modified it</li>
</ol>
<p>This means that if the last modified revision is the same, there have been no
changes in the intermediate time. If <tt class="docutils literal"><span class="pre">OTHER</span></tt> also has the same last modified
revision as <em>any</em> LCA, then we know that all other LCAs’ last-modified
revisions are in the ancestry of that value. (Otherwise, when <tt class="docutils literal"><span class="pre">OTHER</span></tt> would
need to create a new last modified revision as part of the merge.)</p>
</div>
</div>
</div>
</div>
</div>
</div>
<div class="sphinxsidebar">
<div class="sphinxsidebarwrapper">
<h3><a href="index.html">Table Of Contents</a></h3>
<ul>
<li><a class="reference internal" href="#">LCA Tree Merging</a><ul>
<li><a class="reference internal" href="#scalars">Scalars</a><ul>
<li><a class="reference internal" href="#definition">Definition</a></li>
<li><a class="reference internal" href="#resolution-algorithm">Resolution Algorithm</a></li>
<li><a class="reference internal" href="#inventoryentry-revision"><tt class="docutils literal"><span class="pre">InventoryEntry.revision</span></tt></a></li>
</ul>
</li>
</ul>
</li>
</ul>
<h4>Previous topic</h4>
<p class="topless"><a href="content-filtering.html"
title="previous chapter">Content Filtering</a></p>
<h4>Next topic</h4>
<p class="topless"><a href="miscellaneous-notes.html"
title="next chapter">Miscellaneous notes</a></p>
<h3>This Page</h3>
<ul class="this-page-menu">
<li><a href="_sources/lca_tree_merging.txt"
rel="nofollow">Show Source</a></li>
</ul>
<div id="searchbox" style="display: none">
<h3>Quick search</h3>
<form class="search" action="search.html" method="get">
<input type="text" name="q" />
<input type="submit" value="Go" />
<input type="hidden" name="check_keywords" value="yes" />
<input type="hidden" name="area" value="default" />
</form>
<p class="searchtip" style="font-size: 90%">
Enter search terms or a module, class or function name.
</p>
</div>
<script type="text/javascript">$('#searchbox').show(0);</script>
</div>
</div>
<div class="clearer"></div>
</div>
<div class="related">
<h3>Navigation</h3>
<ul>
<li class="right" style="margin-right: 10px">
<a href="miscellaneous-notes.html" title="Miscellaneous notes"
>next</a></li>
<li class="right" >
<a href="content-filtering.html" title="Content Filtering"
>previous</a> |</li>
<li><a href="http://bazaar.canonical.com/">
<img src="_static/bzr icon 16.png" /> Home</a> | </li>
<a href="http://doc.bazaar.canonical.com/en/">Documentation</a> | </li>
<li><a href="index.html">Developer Document Catalog (2.6.0)</a> »</li>
<li><a href="implementation-notes.html" >Implementation notes</a> »</li>
</ul>
</div>
<div class="footer">
© Copyright 2009-2011 Canonical Ltd.
Created using <a href="http://sphinx-doc.org/">Sphinx</a> 1.2.3.
</div>
</body>
</html>
