Rev 6025: Implement something that seems to work for limited search recipies. in http://bazaar.launchpad.net/~jameinel/bzr/2.4-too-much-walking-388269

[John Arbash Meinel]

At http://bazaar.launchpad.net/~jameinel/bzr/2.4-too-much-walking-388269

------------------------------------------------------------
revno: 6025
revision-id: john at arbash-meinel.com-20110811134907-6ii5l1skpu3deawm
parent: john at arbash-meinel.com-20110726141058-9lmlw4tzr693e10x
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 2.4-too-much-walking-388269
timestamp: Thu 2011-08-11 15:49:07 +0200
message:
  Implement something that seems to work for limited search recipies.
-------------- next part --------------
=== modified file 'bzrlib/graph.py'
--- a/bzrlib/graph.py	2011-07-26 14:10:58 +0000
+++ b/bzrlib/graph.py	2011-08-11 13:49:07 +0000
@@ -1933,8 +1933,8 @@
     return child_map
 
 
-def search_result_from_parent_map_with_keys(parent_map, missing_keys,
-                                            tip_keys, depth):
+def limited_search_result_from_parent_map(parent_map, missing_keys, tip_keys,
+                                          depth):
     """Transform a parent_map that is searching 'tip_keys' into an
     approximate SearchResult.
 
@@ -1964,32 +1964,37 @@
     :param depth: How far back to walk.
     """
     child_map = invert_parent_map(parent_map)
-    current_tips = set(tip_keys)
-    walked = set(current_tips)
-    while current_tips and depth:
+    exclude_keys = set(tip_keys)
+    heads = set()
+    current_roots = set(tip_keys)
+    walked = set(current_roots)
+    while current_roots and depth:
         depth -= 1
         children = set()
-        for p in current_tips:
+        for p in current_roots:
             # Is it better to pre- or post- filter the children?
-            children.update[child_map[p]]
+            try:
+                children.update(child_map[p])
+            except KeyError:
+                heads.add(p)
         # TODO: Use the right set notation here since 'walked' grows large,
         #       while 'children' should usually be small
         # Don't walk keys we've already walked
         children.difference_update(walked)
         walked.update(children)
-        ### if not children:
-        ###     # We walked off the graph
-        ###     break
-        current_tips = children
-    start_keys = current_tips
+        current_roots = children
+    if current_roots:
+        heads.update(current_roots)
+    start_keys = current_roots
     g = Graph(DictParentsProvider(parent_map))
-    s = g._make_breadth_first_searcher(start_keys)
+    s = g._make_breadth_first_searcher(heads)
     while True:
         try:
-            s.next_with_ghosts()
+            next_revs = s.next()
         except StopIteration:
             break
-    return s.get_result().get_recipe()
+        s.stop_searching_any(exclude_keys.intersection(next_revs))
+    return s.get_result().get_recipe()[1:]
 
 
 def search_result_from_parent_map(parent_map, missing_keys):

=== modified file 'bzrlib/tests/test_graph.py'
--- a/bzrlib/tests/test_graph.py	2011-07-26 13:28:49 +0000
+++ b/bzrlib/tests/test_graph.py	2011-08-11 13:49:07 +0000
@@ -1785,3 +1785,22 @@
         parent_map['b'] = extended_history_shortcut['b']
         self.assertSearchResult(['e', 'f'], [], 7,
                                 parent_map, missing_keys=[NULL_REVISION])
+
+
+class TestLimitedSearchResultFromParentMap(TestGraphBase):
+
+    def assertSearchResult(self, start_keys, stop_keys, key_count, parent_map,
+                           missing_keys, tip_keys, depth):
+        (start, stop, count) = _mod_graph.limited_search_result_from_parent_map(
+            parent_map, missing_keys, tip_keys, depth)
+        self.assertEqual((sorted(start_keys), sorted(stop_keys), key_count),
+                         (sorted(start), sorted(stop), count))
+
+    def test_ancestry_1(self):
+        self.assertSearchResult(['rev4'], ['rev1'], 4,
+                                ancestry_1, (), ['rev1'], 10)
+        self.assertSearchResult(['rev2a', 'rev2b'], ['rev1'], 2,
+                                ancestry_1, (), ['rev1'], 1)
+
+    # TODO: Test heads that go nowhere
+    # TODO: Test heads that converge