Rev 3103: change the _remove_simple_descendants api a bit, make it better for 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: 3103
revision-id:john at arbash-meinel.com-20071214184807-af9dw18c6qonpj2t
parent: john at arbash-meinel.com-20071213230136-urdk4t2045id09so
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: graph_update
timestamp: Fri 2007-12-14 12:48:07 -0600
message:
  change the _remove_simple_descendants api a bit, make it better for
  using multiple times on different sets of data.
modified:
  bzrlib/graph.py                graph_walker.py-20070525030359-y852guab65d4wtn0-1
  bzrlib/tests/test_graph.py     test_graph_walker.py-20070525030405-enq4r60hhi9xrujc-1
-------------- next part --------------
=== modified file 'bzrlib/graph.py'
--- a/bzrlib/graph.py	2007-12-13 23:01:36 +0000
+++ b/bzrlib/graph.py	2007-12-14 18:48:07 +0000
@@ -481,7 +481,7 @@
         return set([candidate_descendant]) == self.heads(
             [candidate_ancestor, candidate_descendant])
 
-    def _remove_simple_descendants(self, revisions):
+    def _remove_simple_descendants(self, revisions, parents):
         """remove revisions which are children of other ones in the set
 
         This doesn't do any graph searching, it just checks the immediate
@@ -490,9 +490,29 @@
         :param revisions: A set of revision_ids
         :return: A set of revision_ids with the children removed
         """
-        parents = self.get_parent_map(revisions)
         simple_ancestors = revisions.copy()
+        # TODO: jam 20071214 we *could* restrict it to searching only the
+        #       parents of revisions already present in 'revisions', but
+        #       considering the general use case, I think this is actually
+        #       better.
+
+        # This is the same as the following loop. I don't know that it is any
+        # faster.
+        ## simple_ancestors.difference_update(r for r, p_ids in parents.iteritems()
+        ##     if p_ids is not None and revisions.intersection(p_ids))
+        ## return simple_ancestors
+
+        # Yet Another Way, invert the parent map (which can be cached)
+        ## descendants = {}
+        ## for revision_id, parent_ids in parents.iteritems():
+        ##   for p_id in parent_ids:
+        ##       descendants.setdefault(p_id, []).append(revision_id)
+        ## for revision in revisions.intersection(descendants):
+        ##   simple_ancestors.difference_update(descendants[revision])
+        ## return simple_ancestors
         for revision, parent_ids in parents.iteritems():
+            if parent_ids is None:
+                continue
             for parent_id in parent_ids:
                 if parent_id in revisions:
                     # This node has a parent present in the set, so we can

=== modified file 'bzrlib/tests/test_graph.py'
--- a/bzrlib/tests/test_graph.py	2007-12-13 23:01:36 +0000
+++ b/bzrlib/tests/test_graph.py	2007-12-14 18:48:07 +0000
@@ -414,26 +414,30 @@
                          graph.find_unique_lca('rev2a', 'rev2b',
                          count_steps=True))
 
+    def assertRemoveDescendants(self, expected, graph, revisions):
+        parents = graph.get_parent_map(revisions)
+        self.assertEqual(expected,
+                         graph._remove_simple_descendants(revisions, parents))
+
     def test__remove_simple_descendants(self):
         graph = self.make_graph(ancestry_1)
-        all_revisions = set(['rev1', 'rev2a', 'rev2b', 'rev3', 'rev4'])
-        self.assertEqual(set(['rev1']),
-                         graph._remove_simple_descendants(all_revisions))
+        self.assertRemoveDescendants(set(['rev1']), graph,
+            set(['rev1', 'rev2a', 'rev2b', 'rev3', 'rev4']))
 
     def test__remove_simple_descendants_disjoint(self):
         graph = self.make_graph(ancestry_1)
-        self.assertEqual(set(['rev1', 'rev3']),
-            graph._remove_simple_descendants(set(['rev1', 'rev3'])))
+        self.assertRemoveDescendants(set(['rev1', 'rev3']), graph,
+            set(['rev1', 'rev3']))
 
     def test__remove_simple_descendants_chain(self):
         graph = self.make_graph(ancestry_1)
-        self.assertEqual(set(['rev1']),
-            graph._remove_simple_descendants(set(['rev1', 'rev2a', 'rev3'])))
+        self.assertRemoveDescendants(set(['rev1']), graph,
+            set(['rev1', 'rev2a', 'rev3']))
 
     def test__remove_simple_descendants_siblings(self):
         graph = self.make_graph(ancestry_1)
-        self.assertEqual(set(['rev2a', 'rev2b']),
-            graph._remove_simple_descendants(set(['rev2a', 'rev2b', 'rev3'])))
+        self.assertRemoveDescendants(set(['rev2a', 'rev2b']), graph,
+            set(['rev2a', 'rev2b', 'rev3']))
 
     def test_unique_lca_criss_cross(self):
         """Ensure we don't pick non-unique lcas in a criss-cross"""