Rev 3390: Change _search_for_extra_common slightly. in http://bzr.arbash-meinel.com/branches/bzr/1.4-dev/find_differences

[John Arbash Meinel]

At http://bzr.arbash-meinel.com/branches/bzr/1.4-dev/find_differences

------------------------------------------------------------
revno: 3390
revision-id: john at arbash-meinel.com-20080423203341-4qlndx8u2zu21yz0
parent: john at arbash-meinel.com-20080423022725-rtmlxj6nt36xn79q
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: find_differences
timestamp: Wed 2008-04-23 15:33:41 -0500
message:
  Change _search_for_extra_common slightly.
  
  The official statement is that you can stop searching common nodes
  once all common tips are ancestors of *all* unique nodes.
  We need to make sure that we stop the common searchers once
  they find nodes that are ancestors, and then we can only
  exit the common search loop when they have finished.
  
  All tests pass, need to see if it is still 'efficient'.
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	2008-04-23 02:27:25 +0000
+++ b/bzrlib/graph.py	2008-04-23 20:33:41 +0000
@@ -573,6 +573,18 @@
                     newly_seen_common.update(searcher.find_seen_ancestors(newly_seen_common))
                 for searcher in common_searchers:
                     searcher.start_searching(newly_seen_common)
+
+                # If a 'common' node has been found by a unique searcher, we
+                # can stop searching it.
+                stop_searching_common = None
+                for searcher in unique_searchers:
+                    if stop_searching_common is None:
+                        stop_searching_common = searcher.find_seen_ancestors(newly_seen_common)
+                    else:
+                        stop_searching_common = stop_searching_common.intersection(searcher.find_seen_ancestors(newly_seen_common))
+                if stop_searching_common:
+                    for searcher in common_searchers:
+                        searcher.stop_searching_any(stop_searching_common)
             if new_common_unique:
                 # We found some ancestors that are common, jump all the way to
                 # their most ancestral node that we have already seen.
@@ -593,13 +605,13 @@
                 for searcher in common_searchers:
                     searcher.stop_searching_any(new_common_unique)
                 common_ancestors_unique.update(new_common_unique)
-            for searcher in unique_searchers:
-                if searcher._next_query:
-                    # We have something to look for
-                    break
-            else:
-                # All unique_searchers have stopped searching
-                break
+            # for searcher in unique_searchers:
+            #     if searcher._next_query:
+            #         # We have something to look for
+            #         break
+            # else:
+            #     # All unique_searchers have stopped searching
+            #     break
             for searcher in common_searchers:
                 if searcher._next_query:
                     break

=== modified file 'bzrlib/tests/test_graph.py'
--- a/bzrlib/tests/test_graph.py	2008-04-22 18:48:21 +0000
+++ b/bzrlib/tests/test_graph.py	2008-04-23 20:33:41 +0000
@@ -205,25 +205,40 @@
 #     |
 #     d
 #     |\
-#     e f
+#     e |
+#     | |
+#     f |
+#     | |
+#     g h
 #     | |\
-#     i | h
+#     i | j
 #     |\| |
-#     | g |
-#     | | |
-#     | j |
-#     | | |
 #     | k |
 #     | | |
 #     | l |
+#     | | |
+#     | m |
+#     | | |
+#     | n |
+#     | | |
+#     | o |
+#     | | |
+#     | p |
+#     | | |
+#     | q |
+#     | | |
+#     | r |
+#     | | |
+#     | s |
+#     | | |
 #     |/|/
-#     m n
-complex_shortcut2 = {'d':[NULL_REVISION],
-                    'x':['d'], 'y':['x'],
-                    'e':['y'], 'f':['d'], 'g':['f', 'i'], 'h':['f'],
-                    'i':['e'], 'j':['g'], 'k':['j'],
-                    'l':['k'], 'm':['i', 's'], 'n':['s', 'h'],
-                    'o':['l'], 'p':['o'], 'q':['p'],
+#     t u
+complex_shortcut2 = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'],
+                    'e':['d'], 'f':['e'],
+                    'g':['f'], 'h':['d'], 'k':['h', 'i'], 'j':['h'],
+                    'i':['g'], 'l':['k'], 'm':['l'],
+                    'n':['m'], 't':['i', 's'], 'u':['s', 'j'],
+                    'o':['n'], 'p':['o'], 'q':['p'],
                     'r':['q'], 's':['r'],
                     }
 
@@ -505,8 +520,8 @@
 
     def test_graph_difference_complex_shortcut2(self):
         graph = self.make_graph(complex_shortcut2)
-        self.assertEqual((set(['m']), set(['h', 'n'])),
-                         graph.find_difference('m', 'n'))
+        self.assertEqual((set(['t']), set(['j', 'u'])),
+                         graph.find_difference('t', 'u'))
 
     def test_graph_difference_shortcut_extra_root(self):
         graph = self.make_graph(shortcut_extra_root)