Rev 3095: Update the _find_border_ancestors code. in http://bzr.arbash-meinel.com/branches/bzr/0.93-dev/graph_update

[John Arbash Meinel]

At http://bzr.arbash-meinel.com/branches/bzr/0.93-dev/graph_update

------------------------------------------------------------
revno: 3095
revision-id:john at arbash-meinel.com-20071207222622-wrglvu7ydcwnjh3r
parent: john at arbash-meinel.com-20071207201053-p3emvva8std6r4b3
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: graph_update
timestamp: Fri 2007-12-07 16:26:22 -0600
message:
  Update the _find_border_ancestors code.
  Delay removing new common revisions from the searchers so that
  they are removed in bulk at the end.
  Any nodes found by the common_searcher are not border ancestors,
  as they are descended from another common revision.
  This may eliminate the need for the final heads() check.
modified:
  bzrlib/graph.py                graph_walker.py-20070525030359-y852guab65d4wtn0-1
  bzrlib/tests/test_graph.py     test_graph_walker.py-20070525030405-enq4r60hhi9xrujc-1
-------------- next part --------------
=== modified file 'bzrlib/graph.py'
--- a/bzrlib/graph.py	2007-12-07 20:10:53 +0000
+++ b/bzrlib/graph.py	2007-12-07 22:26:22 +0000
@@ -245,6 +245,10 @@
                 common_ancestors.update(new_common)
                 for searcher in active_searchers:
                     update_common(searcher, new_common)
+                # All the revisions found by the common_searcher are not
+                # borders, because they are descended from another common
+                # ancestor
+                border_ancestors.difference_update(new_common)
 
             newly_seen = set()
             new_active_searchers = []
@@ -254,18 +258,23 @@
                     newly_seen.update(new_ancestors)
                     new_active_searchers.append(searcher)
             active_searchers = new_active_searchers
+            new_common = set()
             for revision in newly_seen:
                 if revision in common_ancestors:
-                    for searcher in searchers:
-                        update_common(searcher, [revision])
+                    # Not a border ancestor because it was seen as common
+                    # already
+                    new_common.add(revision)
                     continue
                 for searcher in searchers:
                     if revision not in searcher.seen:
                         break
                 else:
+                    # This is a border because it is a first common that we see
+                    # after walking for a while.
                     border_ancestors.add(revision)
-                    for searcher in searchers:
-                        update_common(searcher, [revision])
+                    new_common.add(revision)
+            for searcher in searchers:
+                update_common(searcher, new_common)
             next_to_search = set(common_searcher.will_search())
             for searcher in active_searchers:
                 next_to_search.update(searcher.will_search())

=== modified file 'bzrlib/tests/test_graph.py'
--- a/bzrlib/tests/test_graph.py	2007-12-07 17:32:16 +0000
+++ b/bzrlib/tests/test_graph.py	2007-12-07 22:26:22 +0000
@@ -141,6 +141,26 @@
                              'f': ['a', 'd'],
                             }
 
+# Double shortcut
+# Both sides will see 'A' first, even though it is actually a decendent of a
+# different common revision.
+#
+#  NULL_REVISION
+#       |
+#       a
+#      /|\
+#     / b \
+#    /  |  \
+#   |   c   |
+#   |  / \  |
+#   | d   e |
+#   |/     \|
+#   f       g
+
+double_shortcut = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'],
+                   'd':['c'], 'e':['c'], 'f':['a', 'd'],
+                   'g':['a', 'e']}
+
 #  NULL_REVISION
 #       |
 #       f
@@ -282,6 +302,10 @@
         self.assertEqual(NULL_REVISION,
                          graph.find_unique_lca('rev4a', 'rev1b'))
 
+    def test_lca_double_shortcut(self):
+        graph = self.make_graph(double_shortcut)
+        self.assertEqual('c', graph.find_unique_lca('f', 'g'))
+
     def test_common_ancestor_two_repos(self):
         """Ensure we do unique_lca using data from two repos"""
         mainline_tree = self.prepare_memory_tree('mainline')