Rev 4643: Get ready to move the tests into KnownGraph implementation tests. in http://bazaar.launchpad.net/~jameinel/bzr/2.0b1-stable-groupcompress-order

[John Arbash Meinel]

At http://bazaar.launchpad.net/~jameinel/bzr/2.0b1-stable-groupcompress-order

------------------------------------------------------------
revno: 4643
revision-id: john at arbash-meinel.com-20090824204524-2mu3dv6wtbyxlt4d
parent: john at arbash-meinel.com-20090824203414-v2p7z5efvcnia865
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 2.0b1-stable-groupcompress-order
timestamp: Mon 2009-08-24 15:45:24 -0500
message:
  Get ready to move the tests into KnownGraph implementation tests.
-------------- next part --------------
=== modified file 'bzrlib/_known_graph_py.py'
--- a/bzrlib/_known_graph_py.py	2009-08-17 20:41:26 +0000
+++ b/bzrlib/_known_graph_py.py	2009-08-24 20:45:24 +0000
@@ -218,6 +218,18 @@
         # We started from the parents, so we don't need to do anymore work
         return topo_order
 
+    def gc_sort(self):
+        """Return a reverse topological ordering which is 'stable'.
+
+        There are a few constraints:
+          1) Reverse topological (all children before all parents)
+          2) Grouped by prefix
+          3) 'stable' sorting, so that we get the same result, independent of
+             machine, or extra data.
+        To do this, we use the same basic algorithm as topo_sort, but when we
+        aren't sure what node to access next, we sort them lexicographically.
+        """
+
     def merge_sort(self, tip_key):
         """Compute the merge sorted graph output."""
         from bzrlib import tsort

=== modified file 'bzrlib/tests/test__known_graph.py'
--- a/bzrlib/tests/test__known_graph.py	2009-08-18 21:41:08 +0000
+++ b/bzrlib/tests/test__known_graph.py	2009-08-24 20:45:24 +0000
@@ -754,3 +754,48 @@
                 },
                 'E',
                 [])
+
+
+class TestKnownGraphStableReverseTopoSort(TestCaseWithKnownGraph):
+    """Test the sort order returned by gc_sort."""
+
+    def assertSorted(self, expected, parent_map):
+        graph = self.make_known_graph(parent_map)
+        value = graph.gc_sort()
+        if expected != value:
+            self.assertEqualDiff(pprint.pformat(expected),
+                                 pprint.pformat(value))
+
+    def test_empty(self):
+        self.assertSorted([], {})
+
+    def test_single(self):
+        self.assertSorted(['a'], {'a':()})
+        self.assertSorted([('a',)], {('a',):()})
+        self.assertSorted([('F', 'a')], {('F', 'a'):()})
+
+    def test_linear(self):
+        self.assertSorted(['c', 'b', 'a'], {'a':(), 'b':('a',), 'c':('b',)})
+        self.assertSorted([('c',), ('b',), ('a',)],
+                          {('a',):(), ('b',): (('a',),), ('c',): (('b',),)})
+        self.assertSorted([('F', 'c'), ('F', 'b'), ('F', 'a')],
+                          {('F', 'a'):(), ('F', 'b'): (('F', 'a'),),
+                           ('F', 'c'): (('F', 'b'),)})
+
+    def test_mixed_ancestries(self):
+        # Each prefix should be sorted separately
+        self.assertSorted([('F', 'c'), ('F', 'b'), ('F', 'a'),
+                           ('G', 'c'), ('G', 'b'), ('G', 'a'),
+                           ('Q', 'c'), ('Q', 'b'), ('Q', 'a'),
+                          ],
+                          {('F', 'a'):(), ('F', 'b'): (('F', 'a'),),
+                           ('F', 'c'): (('F', 'b'),),
+                           ('G', 'a'):(), ('G', 'b'): (('G', 'a'),),
+                           ('G', 'c'): (('G', 'b'),),
+                           ('Q', 'a'):(), ('Q', 'b'): (('Q', 'a'),),
+                           ('Q', 'c'): (('Q', 'b'),),
+                          })
+
+    def test_stable_sorting(self):
+        # the sort order should be stable even when extra nodes are added
+        pass

=== modified file 'bzrlib/tests/test_groupcompress.py'
--- a/bzrlib/tests/test_groupcompress.py	2009-08-24 20:34:14 +0000
+++ b/bzrlib/tests/test_groupcompress.py	2009-08-24 20:45:24 +0000
@@ -866,41 +866,3 @@
             self.assertEqual(('key4',), record.key)
             self.assertEqual(self._texts[record.key],
                              record.get_bytes_as('fulltext'))
-
-
-class TestSortGCOptimal(tests.TestCase):
-    """Test the sort order returned by sort_gc_optimal."""
-
-    def assertSorted(self, expected, parent_map):
-        as_sorted = groupcompress.sort_gc_optimal(parent_map)
-        self.assertEqual(expected, as_sorted)
-
-    def test_empty(self):
-        self.assertSorted([], {})
-
-    def test_single(self):
-        self.assertSorted(['a'], {'a':()})
-        self.assertSorted([('a',)], {('a',):()})
-        self.assertSorted([('F', 'a')], {('F', 'a'):()})
-
-    def test_linear(self):
-        self.assertSorted(['c', 'b', 'a'], {'a':(), 'b':('a',), 'c':('b',)})
-        self.assertSorted([('c',), ('b',), ('a',)],
-                          {('a',):(), ('b',): (('a',),), ('c',): (('b',),)})
-        self.assertSorted([('F', 'c'), ('F', 'b'), ('F', 'a')],
-                          {('F', 'a'):(), ('F', 'b'): (('F', 'a'),),
-                           ('F', 'c'): (('F', 'b'),)})
-
-    def test_mixed_ancestries(self):
-        # Each prefix should be sorted separately
-        self.assertSorted([('F', 'c'), ('F', 'b'), ('F', 'a'),
-                           ('G', 'c'), ('G', 'b'), ('G', 'a'),
-                           ('Q', 'c'), ('Q', 'b'), ('Q', 'a'),
-                          ],
-                          {('F', 'a'):(), ('F', 'b'): (('F', 'a'),),
-                           ('F', 'c'): (('F', 'b'),),
-                           ('G', 'a'):(), ('G', 'b'): (('G', 'a'),),
-                           ('G', 'c'): (('G', 'b'),),
-                           ('Q', 'a'):(), ('Q', 'b'): (('Q', 'a'),),
-                           ('Q', 'c'): (('Q', 'b'),),
-                          })