Rev 4643: Start working on a per-vf implementation test of find_ancestry. in http://bazaar.launchpad.net/~jameinel/bzr/1.19-known-graph-sorted

[John Arbash Meinel]

At http://bazaar.launchpad.net/~jameinel/bzr/1.19-known-graph-sorted

------------------------------------------------------------
revno: 4643
revision-id: john at arbash-meinel.com-20090817210105-k1ejuqmyaz4u2zfs
parent: john at arbash-meinel.com-20090817204126-fokcicx22mwsgud0
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.19-known-graph-sorted
timestamp: Mon 2009-08-17 16:01:05 -0500
message:
  Start working on a per-vf implementation test of find_ancestry.
  
  Turns out we need to do a bit more implementation to get that working.
  We also need to implement the find_ancestry() code on the Builder objects.
-------------- next part --------------
=== modified file 'bzrlib/knit.py'
--- a/bzrlib/knit.py	2009-08-16 17:22:08 +0000
+++ b/bzrlib/knit.py	2009-08-17 21:01:05 +0000
@@ -1192,8 +1192,7 @@
 
     def get_known_graph_ancestry(self, keys):
         """Get a KnownGraph instance with the ancestry of keys."""
-        parent_map, missing_keys = self._index._graph_index.find_ancestry(keys,
-                                                                          0)
+        parent_map, missing_keys = self._index.find_ancestry(keys, 0)
         kg = _mod_graph.KnownGraph(parent_map)
         return kg
 
@@ -2567,6 +2566,33 @@
         except KeyError:
             raise RevisionNotPresent(key, self)
 
+    def find_ancestry(self, keys):
+        """See CombinedGraphIndex.find_ancestry()"""
+        prefixes = set(key[:-1] for key in keys)
+        self._load_prefixes(prefixes)
+        result = {}
+        parent_map = {}
+        missing_keys = set()
+        pending_keys = list(keys)
+        # This assumes that keys will not reference parents in a different
+        # prefix, which is accurate so far.
+        while pending_keys:
+            key = pending_keys.pop()
+            if key in parent_map:
+                continue
+            prefix = key[:-1]
+            try:
+                suffix_parents = self._kndx_cache[prefix][0][key[-1]][4]
+            except KeyError:
+                missing_keys.add(key)
+            else:
+                parent_keys = tuple([prefix + (suffix,)
+                                     for suffix in suffix_parents])
+                parent_map[key] = parent_keys
+                pending_keys.extend([p for p in parent_keys
+                                        if p not in parent_map])
+        return parent_map, missing_keys
+
     def get_parent_map(self, keys):
         """Get a map of the parents of keys.
 
@@ -3056,6 +3082,10 @@
             options.append('no-eol')
         return options
 
+    def find_ancestry(self, keys):
+        """See CombinedGraphIndex.find_ancestry()"""
+        return self._graph_index.find_ancestry(keys, 0)
+
     def get_parent_map(self, keys):
         """Get a map of the parents of keys.
 

=== modified file 'bzrlib/tests/__init__.py'
--- a/bzrlib/tests/__init__.py	2009-08-15 11:14:43 +0000
+++ b/bzrlib/tests/__init__.py	2009-08-17 21:01:05 +0000
@@ -3431,6 +3431,7 @@
                    'bzrlib.tests.per_repository',
                    'bzrlib.tests.per_repository_chk',
                    'bzrlib.tests.per_repository_reference',
+                   'bzrlib.tests.per_versionedfile',
                    'bzrlib.tests.per_workingtree',
                    'bzrlib.tests.test__annotator',
                    'bzrlib.tests.test__chk_map',
@@ -3582,7 +3583,6 @@
                    'bzrlib.tests.test_urlutils',
                    'bzrlib.tests.test_version',
                    'bzrlib.tests.test_version_info',
-                   'bzrlib.tests.test_versionedfile',
                    'bzrlib.tests.test_weave',
                    'bzrlib.tests.test_whitebox',
                    'bzrlib.tests.test_win32utils',

=== renamed file 'bzrlib/tests/test_versionedfile.py' => 'bzrlib/tests/per_versionedfile.py'
--- a/bzrlib/tests/test_versionedfile.py	2009-08-04 04:36:34 +0000
+++ b/bzrlib/tests/per_versionedfile.py	2009-08-17 21:01:05 +0000
@@ -26,6 +26,7 @@
 
 from bzrlib import (
     errors,
+    graph as _mod_graph,
     groupcompress,
     knit as _mod_knit,
     osutils,
@@ -1737,6 +1738,23 @@
             f.get_record_stream([key_b], 'unordered', True
                 ).next().get_bytes_as('fulltext'))
 
+    def test_get_known_graph_ancestry(self):
+        f = self.get_versionedfiles()
+        key_a = self.get_simple_key('a')
+        key_b = self.get_simple_key('b')
+        key_c = self.get_simple_key('c')
+        # A
+        # |\
+        # | B
+        # |/
+        # C
+        f.add_lines(key_a, [], ['\n'])
+        f.add_lines(key_b, [key_a], ['\n'])
+        f.add_lines(key_c, [key_a, key_b], ['\n'])
+        kg = f.get_known_graph_ancestry([key_c])
+        self.assertIsInstance(kg, _mod_graph.KnownGraph)
+        self.assertEqual([key_a, key_b, key_c], list(kg.topo_sort()))
+
     def test_get_record_stream_empty(self):
         """An empty stream can be requested without error."""
         f = self.get_versionedfiles()