Rev 3521: Change _propagate_descended_from to do what I thought I was doing :) 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: 3521
revision-id: john at arbash-meinel.com-20080807174956-38x3ffhebvvn27ov
parent: john at arbash-meinel.com-20080806224535-nw726e1khk08fsd3
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: lazy_revno
timestamp: Thu 2008-08-07 12:49:56 -0500
message:
  Change _propagate_descended_from to do what I thought I was doing :)
  I thought I was doing a depth-first, but it turned out I was just stepping breadth-wise.
  Doesn't change the problems, but should be a small improvement to prevent re-walking
  the same nodes repeatedly.
-------------- next part --------------
=== modified file 'bzrlib/graph.py'
--- a/bzrlib/graph.py	2008-08-06 22:45:35 +0000
+++ b/bzrlib/graph.py	2008-08-07 17:49:56 +0000
@@ -1936,21 +1936,21 @@
         This will set descended_from for all known_children that have this as a
         left-hand ancestor.
         """
-        nodes = {}
+        desc_from_nodes = {}
         for revision_id in revision_ids:
             node = self._get_node(revision_id)
             # Make sure we have a value to propagate for this node
             descended_from = node.descended_from
             # TODO: Test this
             if descended_from is not None:
-                nodes.setdefault(descended_from, []).append(node)
+                desc_from_nodes.setdefault(descended_from, []).append(node)
 
-        while nodes:
-            # We want to do nodes with the greatest descended_from first
-            next_nodes = {}
-            for descended_from in sorted(nodes.keys(), reverse=True):
-                this_next = []
-                for node in nodes[descended_from]:
+        # We want to do nodes with the greatest descended_from first
+        for descended_from, nodes in sorted(desc_from_nodes.iteritems(),
+                                            reverse=True):
+            while nodes:
+                next_nodes = []
+                for node in nodes:
                     mainline_revno = node.mainline_revno
                     for child in node.known_children:
                         child_node = self._get_node(child)
@@ -1959,19 +1959,17 @@
                         if (child_node.descended_from is None
                             or child_node.descended_from < descended_from):
                             child_node.descended_from = descended_from
-                            this_next.append(child_node)
+                            next_nodes.append(child_node)
                         if (child_node.parent_ids[0] == node.revision_id
                             and child_node.mainline_revno is None):
                             child_node.mainline_revno = mainline_revno
-                            # TODO: Should we track this node? or is the above
-                            #       method good enough?
-                    # TODO: We could track left-hand nodes at the same time.
-                    #     if child_node.descended_from is None:
-                    #         child_node.descended_from = descended_from
-                    #         next_nodes.append(child_node)
-                if this_next:
-                    next_nodes[descended_from] = this_next
-            nodes = next_nodes
+                        # TODO: Should we track this node? or is the above
+                        #       method good enough?
+                nodes = next_nodes
+                # TODO: We could track left-hand nodes at the same time.
+                #     if child_node.descended_from is None:
+                #         child_node.descended_from = descended_from
+                #         next_nodes.append(child_node)
 
     def _find_relevant_parent_map(self, node):
         """Recurse the parents to find interesting nodes."""