[MERGE] Common dominator ancestor picker

[John A Meinel]

Aaron Bentley wrote:
> Hi all,
> 
> I've implemented an ancestor picker based on the closest common
> dominator.  This speeds up find-merge-base by a factor of 10 on the bzr
> source tree, and is likely to do even better as the bzr ancestry gets
> bigger.
> 
> The old algorithm scaled linearly with the number of nodes in the
> ancestry.  This algorithm scales linearly with the number of nodes
> between each revision and their closest common dominator.  I invented it
> myself, so let me know if there's anything wrong with the theory.
> 
> Not only is this algorithm faster, but it's also more correct, as it
> will handle criss-cross merges better.
> 
> Monotone's is slightly fancier; they find the common merge that is a
> dominator of one.  I don't think the difference will be significant, and
> we can always implement it later.
> 
> Could someone give me a review?  If approved, I'll stick it in my
> integration.
> 
> Aaron

I don't have time to do a full review, but I found at least 1 bug.


------------------------------------------------------------------------

=== modified file 'bzrlib/revision.py'
--- bzrlib/revision.py	
+++ bzrlib/revision.py	
@@ -279,20 +279,6 @@
     return root, ancestors, descendants, common


-def common_ancestor(revision_a, revision_b, revision_source):
-    try:
-        root, ancestors, descendants, common = \
-            combined_graph(revision_a, revision_b, revision_source)
-    except bzrlib.errors.NoCommonRoot:
-        raise bzrlib.errors.NoCommonAncestor(revision_a, revision_b)
-
-    distances = node_distances (descendants, ancestors, root)
-    farthest = select_farthest(distances, common)
-    if farthest is None or farthest == NULL_REVISION:
-        raise bzrlib.errors.NoCommonAncestor(revision_a, revision_b)
-    return farthest
-
-
 class MultipleRevisionSources(object):
     """Proxy that looks in multiple branches for revisions."""
     def __init__(self, *args):
@@ -350,3 +336,94 @@
         next = best_ancestor(next)
     path.reverse()
     return path
+
+
+def dominators(revision_id, revision_source):
+    """Return the dominators of a revision.
+    This is based on the observation that in a DAG, the dominators of x
+    are x + common_dominators(parents(x)).  This applies recursively,
of course.
+    """
+    while True:
+        yield revision_id
+        if revision_id is NULL_REVISION:
+            return
+        try:
+            revision = revision_source.get_revision(revision_id)
+        except NoSuchRevision:
+            return
+
+        if len(revision.parent_ids) == 0:
+            revision_id = NULL_REVISION
+        elif len(revision.parent_ids) == 1:
+            (revision_id,) = revision.parent_ids
+        else:
+            revision_id = common_dominator(*revision.parent_ids)
+

Here you aren't passing the 'revision_source' to the 'common_dominator'
algorithm.

Make sure you have test cases to exercise this code path.

John
=:->


-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 249 bytes
Desc: OpenPGP digital signature
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20060217/4b9897ba/attachment.pgp