Rev 3401: For some reason find_unique_ancestors is much slower than it should be. 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: 3401
revision-id: john at arbash-meinel.com-20080424230555-h2alm4wl2zc7e5l9
parent: john at arbash-meinel.com-20080424221718-gaa2txy3xinmvh6m
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: find_unique_ancestors
timestamp: Thu 2008-04-24 18:05:55 -0500
message:
  For some reason find_unique_ancestors is much slower than it should be.
  Start trying to assert that it doesn't access more ancestry than
  it needs to.
modified:
  bzrlib/tests/test_graph.py     test_graph_walker.py-20070525030405-enq4r60hhi9xrujc-1
-------------- next part --------------
=== modified file 'bzrlib/tests/test_graph.py'
--- a/bzrlib/tests/test_graph.py	2008-04-24 17:06:42 +0000
+++ b/bzrlib/tests/test_graph.py	2008-04-24 23:05:55 +0000
@@ -1060,6 +1060,18 @@
     def make_graph(self, ancestors):
         return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
 
+    def make_breaking_graph(self, ancestors, break_on):
+        """Make a Graph that raises an exception if we hit a node."""
+        g = self.make_graph(ancestors)
+        orig_parent_map = g.get_parent_map
+        def get_parent_map(keys):
+            bad_keys = set(keys).intersection(break_on)
+            if bad_keys:
+                self.fail('key(s) %s was accessed' % (sorted(bad_keys),))
+            return orig_parent_map(keys)
+        g.get_parent_map = get_parent_map
+        return g
+
     def assertFindUniqueAncestors(self, graph, expected, node, common):
         actual = graph.find_unique_ancestors(node, common)
         self.assertEqual(expected, sorted(actual))
@@ -1076,6 +1088,11 @@
         self.assertFindUniqueAncestors(graph, ['rev2b'], 'rev2b', ['rev1'])
         self.assertFindUniqueAncestors(graph, ['rev3'], 'rev3', ['rev2a'])
 
+    def test_minimal_ancestry(self):
+        graph = self.make_breaking_graph(extended_history_shortcut,
+                                         [NULL_REVISION, 'a', 'b'])
+        self.assertFindUniqueAncestors(graph, ['e'], 'e', ['d'])
+
     def test_in_ancestry(self):
         graph = self.make_graph(ancestry_1)
         self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev3'])