Rev 3109: Switch back to using BFS for find_seen_ancestors. 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: 3109
revision-id:john at arbash-meinel.com-20071220182020-einbxflfmn2bi8jy
parent: john at arbash-meinel.com-20071220160509-tdn1gp49n31zyf4e
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: graph_update
timestamp: Thu 2007-12-20 12:20:20 -0600
message:
  Switch back to using BFS for find_seen_ancestors.
  Also, cull the ancestor list by nodes that are already seen by
  the common searcher. If we saw them there, then we know they cannot
  be part of our search tips.
modified:
  bzrlib/graph.py                graph_walker.py-20070525030359-y852guab65d4wtn0-1
-------------- next part --------------
=== modified file 'bzrlib/graph.py'
--- a/bzrlib/graph.py	2007-12-20 16:05:09 +0000
+++ b/bzrlib/graph.py	2007-12-20 18:20:20 +0000
@@ -376,7 +376,7 @@
             parent_map = self.get_parent_map(next_to_search)
             ancestors = set()
             # advance searches
-            new_common = common_walker.step(parent_map)
+            common_walker.step(parent_map)
             for candidate in active_searchers.keys():
                 try:
                     searcher = active_searchers[candidate]
@@ -391,6 +391,7 @@
                 else:
                     del active_searchers[candidate]
             # process found nodes
+            new_common = set()
             for ancestor in ancestors:
                 if ancestor in candidate_heads:
                     candidate_heads.remove(ancestor)
@@ -420,12 +421,15 @@
             # going to be, so we can preload them
             next_to_search = set()
             if new_common:
+                known_common = common_walker.seen - new_common
                 for searcher in searchers.itervalues():
-                    seen_ancestors = searcher.find_seen_ancestors(new_common)
-                    searcher.stop_searching_any(seen_ancestors)
+                    seen_ancestors = searcher.find_seen_ancestors(new_common,
+                                                                  known_common)
+                    stopped = searcher.stop_searching_any(seen_ancestors)
                     # Make sure to put all seen ancestors into the common set. This
                     # will allow the common_walker to jump past them.
-                    new_common.update(seen_ancestors)
+                    new_common.update(stopped)
+                    common_walker.seen.update(seen_ancestors)
             for searcher in searchers.itervalues():
                 next_to_search.update(searcher.will_search())
             common_walker.start_searching(new_common)
@@ -785,24 +789,22 @@
     def __iter__(self):
         return self
 
-    def find_seen_ancestors(self, revisions):
-        """Find ancestors of these revisions that have already been seen."""
-        revisions = self.seen.intersection(revisions)
+    def find_seen_ancestors(self, revisions, ignore_common=None):
+        """Find ancestors of this revision that have already been seen."""
+        if ignore_common is None:
+            ignore_common = frozenset()
+        searcher = _BreadthFirstSearcher(revisions, self._parents_provider)
         seen_ancestors = set()
-        while revisions:
-            seen_ancestors.update(revisions)
-            next_revisions = set()
-            # TODO: couldn't we just iterate the parent_map, since if a key
-            #       isn't present, that means we would skip anyway
-            #       It depends if parent_map can ever contain keys that weren't
-            #       requested.
-            parent_map = self._parents_provider.get_parent_map(revisions)
-            for revision_id in revisions:
-                parents = parent_map.get(revision_id, None)
-                if parents is None:
-                    continue
-                next_revisions.update(self.seen.intersection(parents))
-            revisions = next_revisions
+        for ancestors in searcher:
+            stop_nodes = set()
+            for ancestor in ancestors:
+                if ancestor not in self.seen:
+                    stop_nodes.add(ancestor)
+                else:
+                    seen_ancestors.add(ancestor)
+                    if ancestor in ignore_common:
+                        stop_nodes.add(ancestor)
+            searcher.stop_searching_any(stop_nodes)
         return seen_ancestors
 
     def stop_searching_any(self, revisions):