Rev 3518: Refactor, move the parent map function into a helper (helps with lsprof) in http://bzr.arbash-meinel.com/branches/bzr/1.6-dev/lazy_revno

[John Arbash Meinel]

At http://bzr.arbash-meinel.com/branches/bzr/1.6-dev/lazy_revno

------------------------------------------------------------
revno: 3518
revision-id: john at arbash-meinel.com-20080806185548-f5nhw6w2xmhzekcq
parent: john at arbash-meinel.com-20080806182124-kpoz5s5os608bbgx
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: lazy_revno
timestamp: Wed 2008-08-06 13:55:48 -0500
message:
  Refactor, move the parent map function into a helper (helps with lsprof)
-------------- next part --------------
=== modified file 'bzrlib/graph.py'
--- a/bzrlib/graph.py	2008-08-06 18:21:24 +0000
+++ b/bzrlib/graph.py	2008-08-06 18:55:48 +0000
@@ -1585,6 +1585,7 @@
             # load the whole graph, and do a regular 'merge_sort' on the whole
             # thing. Note that this is *very* inefficient when we already have
             # a decent portion of the graph numbered
+            trace.note('falling back to _number_all for %s', node.revision_id)
             self._number_all()
             return node.dotted_revno
 
@@ -1964,24 +1965,17 @@
                     next_nodes[descended_from] = this_next
             nodes = next_nodes
 
-    def _number(self, node):
-        """We've done all the background work, number this node."""
-        assert node.parent_ids is not None
-        assert node.mainline_revno is not None
-        assert node.merged_into is not None
-
-        orig_node = node
+    def _find_relevant_parent_map(self, node):
+        """Recurse the parents to find interesting nodes."""
         mainline_revno = node.mainline_revno
         merged_into = node.merged_into
         merged_into_node = self._get_node(self._mainline_nodes[merged_into])
 
-        # TODO: I think we can do better than this by being smart about what
-        #       nodes get added and what nodes don't. However, rather than
-        #       re-implement all of the logic...
         mainline_revision_id = self._mainline_nodes[mainline_revno]
         interesting_parent_map = {mainline_revision_id: ()}
 
         search_stack = [merged_into_node]
+        # Nodes that are either in the queue, or have already been processed
         searching = set([merged_into_node.revision_id,
                          revision.NULL_REVISION, mainline_revision_id])
         while search_stack:
@@ -2003,10 +1997,29 @@
         # TODO: We might also want to _prune_tails (from bzrlib.merge),
         #       to remove more nodes that don't effect our numbering, and whose
         #       numbers we cannot trust.
-        culled_parent_map = {}
-        for revision_id, parent_ids in interesting_parent_map.iteritems():
-            culled_parent_map[revision_id] = [p for p in parent_ids
-                                              if p in interesting_parent_map]
+        def cull_parent_map():
+            culled_parent_map = {}
+            for revision_id, parent_ids in interesting_parent_map.iteritems():
+                culled_parent_map[revision_id] = [p for p in parent_ids
+                                            if p in interesting_parent_map]
+            return culled_parent_map
+        return cull_parent_map()
+
+    def _number(self, node):
+        """We've done all the background work, number this node."""
+        assert node.parent_ids is not None
+        assert node.mainline_revno is not None
+        assert node.merged_into is not None
+
+        orig_node = node
+        mainline_revno = node.mainline_revno
+        merged_into = node.merged_into
+        merged_into_node = self._get_node(self._mainline_nodes[merged_into])
+
+        # TODO: I think we can do better than this by being smart about what
+        #       nodes get added and what nodes don't. However, rather than
+        #       re-implement all of the logic...
+        culled_parent_map = self._find_relevant_parent_map(node)
 
         for (seq_num, rev_id, depth, dotted_revno,
              end_of_merge) in tsort.merge_sort(culled_parent_map,