Rev 2630: Implement get_ancestry/get_ancestry_with_ghosts for KnitGraphIndex. in http://people.ubuntu.com/~robertc/baz2.0/repository

[Robert Collins]

At http://people.ubuntu.com/~robertc/baz2.0/repository

------------------------------------------------------------
revno: 2630
revision-id: robertc at robertcollins.net-20070713171003-7ivoysxi2sdabzcq
parent: robertc at robertcollins.net-20070713164209-1p6ng85f0ca9r4b4
committer: Robert Collins <robertc at robertcollins.net>
branch nick: repository
timestamp: Sat 2007-07-14 03:10:03 +1000
message:
  Implement get_ancestry/get_ancestry_with_ghosts for KnitGraphIndex.
modified:
  bzrlib/knit.py                 knit.py-20051212171256-f056ac8f0fbe1bd9
  bzrlib/tests/test_knit.py      test_knit.py-20051212171302-95d4c00dd5f11f2b
=== modified file 'bzrlib/knit.py'
--- a/bzrlib/knit.py	2007-07-13 15:46:54 +0000
+++ b/bzrlib/knit.py	2007-07-13 17:10:03 +0000
@@ -1329,6 +1329,55 @@
         """
         self._graph_index = graph_index
 
+    def get_ancestry(self, versions, topo_sorted=True):
+        """See VersionedFile.get_ancestry."""
+        # XXX: This will do len(history) index calls - perhaps
+        # it should be altered to be a index core feature?
+        # get a graph of all the mentioned versions:
+        graph = {}
+        pending = set(versions)
+        while pending:
+            # get all pending nodes
+            this_iteration = pending
+            new_nodes = self._graph_index.iter_entries(this_iteration)
+            pending = set()
+            for (key, node_refs, value) in new_nodes:
+                graph[key] = node_refs[0]
+                # queue parents 
+                pending.update(graph[key])
+            missing_versions = this_iteration.difference(graph)
+            if missing_versions:
+                raise RevisionNotPresent(missing_versions.pop(), self)
+            # dont examine known nodes
+            pending.difference_update(graph)
+        if not topo_sorted:
+            return graph.keys()
+        return topo_sort(graph.items())
+
+    def get_ancestry_with_ghosts(self, versions):
+        """See VersionedFile.get_ancestry."""
+        # XXX: This will do len(history) index calls - perhaps
+        # it should be altered to be a index core feature?
+        # get a graph of all the mentioned versions:
+        graph = {}
+        pending = set(versions)
+        while pending:
+            # get all pending nodes
+            this_iteration = pending
+            new_nodes = self._graph_index.iter_entries(this_iteration)
+            pending = set()
+            for (key, node_refs, value) in new_nodes:
+                graph[key] = node_refs[0]
+                # queue parents 
+                pending.update(graph[key])
+            missing_versions = this_iteration.difference(graph)
+            for missing_version in missing_versions:
+                # add a key, no parents
+                graph[missing_version] = []
+            # dont examine known nodes
+            pending.difference_update(graph)
+        return topo_sort(graph.items())
+
     def get_graph(self):
         """Return a list of the node:parents lists from this knit index."""
         return [(key, refs[0]) for (key, refs, value) in 

=== modified file 'bzrlib/tests/test_knit.py'
--- a/bzrlib/tests/test_knit.py	2007-07-13 15:46:54 +0000
+++ b/bzrlib/tests/test_knit.py	2007-07-13 17:10:03 +0000
@@ -1541,7 +1541,7 @@
         trans.put_file(name, stream)
         return GraphIndex(trans, name)
 
-    def test_get_graph(self):
+    def two_graph_index(self):
         # build a complex graph across several indices.
         index1 = self.make_g_index('1', 1, [
             ('tip', (['parent'], ), ''),
@@ -1550,10 +1550,73 @@
             ('parent', (['tail', 'ghost'], ), ''),
             ('separate', ([], ), '')])
         combined_index = CombinedGraphIndex([index1, index2])
-        index = KnitGraphIndex(combined_index)
+        return KnitGraphIndex(combined_index)
+
+    def two_graph_index_no_ghosts(self):
+        # build a complex graph across several indices.
+        index1 = self.make_g_index('1', 1, [
+            ('tip', (['parent'], ), ''),
+            ('tail', ([], ), '')])
+        index2 = self.make_g_index('2', 1, [
+            ('parent', (['tail'], ), ''),
+            ('separate', ([], ), '')])
+        combined_index = CombinedGraphIndex([index1, index2])
+        return KnitGraphIndex(combined_index)
+
+    def test_get_graph(self):
+        index = self.two_graph_index()
         self.assertEqual(set([
             ('tip', ('parent', )),
             ('tail', ()),
             ('parent', ('tail', 'ghost')),
             ('separate', ()),
             ]), set(index.get_graph()))
+
+    def test_get_ancestry(self):
+        index = self.two_graph_index_no_ghosts()
+        self.assertEqual([], index.get_ancestry([]))
+        self.assertEqual(['separate'], index.get_ancestry(['separate']))
+        self.assertEqual(['tail'], index.get_ancestry(['tail']))
+        self.assertEqual(['tail', 'parent'], index.get_ancestry(['parent']))
+        self.assertEqual(['tail', 'parent', 'tip'], index.get_ancestry(['tip']))
+        self.assertTrue(index.get_ancestry(['tip', 'separate']) in
+            (['tail', 'parent', 'tip', 'separate'],
+             ['separate', 'tail', 'parent', 'tip'],
+            ))
+        # and without topo_sort
+        self.assertEqual(set(['separate']),
+            set(index.get_ancestry(['separate'], topo_sorted=False)))
+        self.assertEqual(set(['tail']),
+            set(index.get_ancestry(['tail'], topo_sorted=False)))
+        self.assertEqual(set(['tail', 'parent']),
+            set(index.get_ancestry(['parent'], topo_sorted=False)))
+        self.assertEqual(set(['tail', 'parent', 'tip']),
+            set(index.get_ancestry(['tip'], topo_sorted=False)))
+        self.assertEqual(set(['separate', 'tail', 'parent', 'tip']),
+            set(index.get_ancestry(['tip', 'separate'])))
+        # with ghosts it blows up early
+        index = self.two_graph_index()
+        self.assertEqual([], index.get_ancestry([]))
+        self.assertEqual(['separate'], index.get_ancestry(['separate']))
+        self.assertEqual(['tail'], index.get_ancestry(['tail']))
+        self.assertRaises(errors.RevisionNotPresent, index.get_ancestry, ['parent'])
+
+    def test_get_ancestry_with_ghosts(self):
+        index = self.two_graph_index()
+        self.assertEqual([], index.get_ancestry_with_ghosts([]))
+        self.assertEqual(['separate'], index.get_ancestry_with_ghosts(['separate']))
+        self.assertEqual(['tail'], index.get_ancestry_with_ghosts(['tail']))
+        self.assertTrue(index.get_ancestry_with_ghosts(['parent']) in
+            (['tail', 'ghost', 'parent'],
+             ['ghost', 'tail', 'parent'],
+            ))
+        self.assertTrue(index.get_ancestry_with_ghosts(['tip']) in
+            (['tail', 'ghost', 'parent', 'tip'],
+             ['ghost', 'tail', 'parent', 'tip'],
+            ))
+        self.assertTrue(index.get_ancestry_with_ghosts(['tip', 'separate']) in
+            (['tail', 'ghost', 'parent', 'tip', 'separate'],
+             ['ghost', 'tail', 'parent', 'tip', 'separate'],
+             ['separate', 'tail', 'ghost', 'parent', 'tip'],
+             ['separate', 'ghost', 'tail', 'parent', 'tip'],
+            ))