Rev 3405: Try using _find_any_seen_ancestors, in http://bzr.arbash-meinel.com/branches/bzr/1.4-dev/find_unique_ancestors

[John Arbash Meinel]

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

------------------------------------------------------------
revno: 3405
revision-id: john at arbash-meinel.com-20080425015422-k2xb2p6k6sgxwt5s
parent: john at arbash-meinel.com-20080425004033-y7p8ol60qntr1pyn
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: find_unique_ancestors
timestamp: Thu 2008-04-24 20:54:22 -0500
message:
  Try using _find_any_seen_ancestors,
  which pulls out the loop around find_seen_ancestors.
  This may not be a net win yet.
modified:
  bzrlib/graph.py                graph_walker.py-20070525030359-y852guab65d4wtn0-1
-------------- next part --------------
=== modified file 'bzrlib/graph.py'
--- a/bzrlib/graph.py	2008-04-25 00:40:33 +0000
+++ b/bzrlib/graph.py	2008-04-25 01:54:22 +0000
@@ -159,6 +159,52 @@
     def __repr__(self):
         return 'Graph(%r)' % self._parents_provider
 
+    def _find_any_seen_ancestors(self, revisions, searchers):
+        """Find any revisions that are seen by any of the searchers."""
+        # This will actually return more nodes than just aggregating
+        # find_seen_ancestors() across the searchers, because it can bridge
+        # 1-node gaps inline.
+
+        # seen contains what nodes have been returned, not what nodes
+        # have been queried. We don't want to probe for nodes that haven't
+        # been searched yet.
+        all_seen = set()
+        not_searched_yet = set()
+        for searcher in searchers:
+            all_seen.update(searcher.seen)
+
+            not_searched = set(searcher._next_query)
+            # Have these nodes been searched in any other searcher?
+            for other_searcher in searchers:
+                if other_searcher is searcher:
+                    continue
+                # This other searcher claims to have seen these nodes
+                maybe_searched = not_searched.intersection(other_searcher.seen)
+                searched = maybe_searched.difference(other_searcher._next_query)
+                not_searched.difference_update(searched)
+
+            # Now we know the real ones that haven't been searched
+            not_searched_yet.update(not_searched)
+
+        pending = set(revisions).intersection(all_seen)
+        seen_ancestors = set(pending)
+
+        pending.difference_update(not_searched_yet)
+        get_parent_map = self._parents_provider.get_parent_map
+        while pending:
+            parent_map = get_parent_map(pending)
+            all_parents = []
+            # We don't care if it is a ghost, since it can't be seen if it is
+            # a ghost
+            for parent_ids in parent_map.itervalues():
+                all_parents.extend(parent_ids)
+            next_pending = all_seen.intersection(all_parents).difference(seen_ancestors)
+            seen_ancestors.update(next_pending)
+            next_pending.difference_update(not_searched_yet)
+            pending = next_pending
+
+        return seen_ancestors
+
     def find_lca(self, *revisions):
         """Determine the lowest common ancestors of the provided revisions
 
@@ -253,9 +299,8 @@
             unique_are_common_nodes.update(
                 next_common_nodes.intersection(unique_searcher.seen))
             if unique_are_common_nodes:
-                ancestors = unique_searcher.find_seen_ancestors(
-                                unique_are_common_nodes)
-                ancestors.update(common_searcher.find_seen_ancestors(ancestors))
+                ancestors = self._find_any_seen_ancestors(unique_are_common_nodes,
+                    [unique_searcher, common_searcher])
                 unique_searcher.stop_searching_any(ancestors)
                 common_searcher.start_searching(ancestors)
 
@@ -265,7 +310,6 @@
         unique_tips = self._remove_simple_descendants(unique_nodes,
                         self.get_parent_map(unique_nodes))
 
-        # TODO: setup the unique searchers, and keep searching until done
         unique_searchers = []
         for tip in unique_tips:
             revs_to_search = unique_searcher.find_seen_ancestors([tip])
@@ -284,7 +328,7 @@
 
         # Stop any search tips that are already known as ancestors of the
         # unique nodes
-        stopped = common_searcher.stop_searching_any(
+        common_searcher.stop_searching_any(
             common_searcher.find_seen_ancestors(ancestor_all_unique))
 
         # While we still have common nodes to search
@@ -306,13 +350,10 @@
                     ancestor_all_unique.intersection(newly_seen_common))
             if unique_are_common_nodes:
                 # We have new common-to-all-unique-searchers nodes
-                for searcher in unique_searchers:
-                    unique_are_common_nodes.update(
-                        searcher.find_seen_ancestors(unique_are_common_nodes))
-                # Since these are common, we can grab another set of ancestors
-                # that we have seen
+                # Which also means we can check in the common_searcher
                 unique_are_common_nodes.update(
-                    common_searcher.find_seen_ancestors(unique_are_common_nodes))
+                    self._find_any_seen_ancestors(unique_are_common_nodes,
+                        [common_searcher] + unique_searchers))
 
                 # We can tell all of the unique searchers to start at these
                 # nodes, and tell all of the common searchers to *stop*