Rev 4644: a few more implementations of the interface. 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: 4644
revision-id: john at arbash-meinel.com-20090817220821-wzul2cdupe88xi7t
parent: john at arbash-meinel.com-20090817210105-k1ejuqmyaz4u2zfs
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.19-known-graph-sorted
timestamp: Mon 2009-08-17 17:08:21 -0500
message:
  a few more implementations of the interface.
-------------- next part --------------
=== modified file 'bzrlib/btree_index.py'
--- a/bzrlib/btree_index.py	2009-08-13 19:56:26 +0000
+++ b/bzrlib/btree_index.py	2009-08-17 22:08:21 +0000
@@ -444,6 +444,22 @@
             return iterators[0]
         return self._iter_smallest(iterators)
 
+    def find_ancestry(self, keys, ref_list_num):
+        """See CombinedGraphIndex.find_ancestry()"""
+        pending = set(keys)
+        parent_map = {}
+        missing_keys = set()
+        while pending:
+            next_pending = set()
+            for _, key, value, ref_lists in self.iter_entries(pending):
+                parent_keys = ref_lists[ref_list_num]
+                parent_map[key] = parent_keys
+                next_pending.update([p for p in parent_keys if p not in
+                                     parent_map])
+                missing_keys.update(pending.difference(parent_map))
+            pending = next_pending
+        return parent_map, missing_keys
+
     def iter_entries(self, keys):
         """Iterate over keys within the index.
 

=== modified file 'bzrlib/knit.py'
--- a/bzrlib/knit.py	2009-08-17 21:01:05 +0000
+++ b/bzrlib/knit.py	2009-08-17 22:08:21 +0000
@@ -1192,7 +1192,7 @@
 
     def get_known_graph_ancestry(self, keys):
         """Get a KnownGraph instance with the ancestry of keys."""
-        parent_map, missing_keys = self._index.find_ancestry(keys, 0)
+        parent_map, missing_keys = self._index.find_ancestry(keys)
         kg = _mod_graph.KnownGraph(parent_map)
         return kg
 

=== modified file 'bzrlib/tests/per_versionedfile.py'
--- a/bzrlib/tests/per_versionedfile.py	2009-08-17 21:01:05 +0000
+++ b/bzrlib/tests/per_versionedfile.py	2009-08-17 22:08:21 +0000
@@ -1740,6 +1740,8 @@
 
     def test_get_known_graph_ancestry(self):
         f = self.get_versionedfiles()
+        if not self.graph:
+            raise TestNotApplicable('ancestry info only relevant with graph.')
         key_a = self.get_simple_key('a')
         key_b = self.get_simple_key('b')
         key_c = self.get_simple_key('c')

=== modified file 'bzrlib/versionedfile.py'
--- a/bzrlib/versionedfile.py	2009-08-16 17:22:08 +0000
+++ b/bzrlib/versionedfile.py	2009-08-17 22:08:21 +0000
@@ -32,6 +32,7 @@
 from bzrlib import (
     annotate,
     errors,
+    graph as _mod_graph,
     groupcompress,
     index,
     knit,
@@ -228,10 +229,6 @@
         """Copy this versioned file to name on transport."""
         raise NotImplementedError(self.copy_to)
 
-    def get_known_graph_ancestry(self, keys):
-        """Get a KnownGraph instance with the ancestry of keys."""
-        raise NotImplementedError(self.get_known_graph_ancestry)
-
     def get_record_stream(self, versions, ordering, include_delta_closure):
         """Get a stream of records for versions.
 
@@ -945,6 +942,20 @@
             if '\n' in line[:-1]:
                 raise errors.BzrBadParameterContainsNewline("lines")
 
+    def get_known_graph_ancestry(self, keys):
+        """Get a KnownGraph instance with the ancestry of keys."""
+        # most basic implementation is a loop around get_parent_map
+        pending = set(keys)
+        parent_map = {}
+        while pending:
+            this_parent_map = self.get_parent_map(pending)
+            parent_map.update(this_parent_map)
+            pending = set()
+            map(pending.update, this_parent_map.itervalues())
+            pending = pending.difference(parent_map)
+        kg = _mod_graph.KnownGraph(parent_map)
+        return kg
+
     def get_parent_map(self, keys):
         """Get a map of the parents of keys.