[MERGE] Modify test_tsort_partial to accept multiple valid orderings.

[Maarten Bosmans]

The list returned by tsort.topo_sort is not garantueed to be specific
order other than the partial topological order. So the
test_tsort_partial testcase should not assert any specific ordering,
but only check if parents come before their childs.

That the current implementation of TopoSorter passes the test is
merely by coincidence. It relies on the order nodes are popped of the
graph with popitem(), which is not necessarily fixed. This can be seen
by replacing line 109 of bzrlib/tsort.py:
-            node_name, parents = self._graph.popitem()
+            node_name = self._graph.keys()[-1]
+            parents = self._graph.pop(node_name)
This could very well be another order in which items are popped in
another Python implementation. The resulting list is still in
topological order, but the test fails.

Below a patch to fix the test.

Maarten Bosmans


# Bazaar merge directive format 2 (Bazaar 0.90)
# revision_id: maarten_bosmans-20090730125532-kze3aeorvinh3icd
# target_branch: ../bzr.dev
# testament_sha1: c177de26f1b366289d8127d4380fe12af2319042
# timestamp: 2009-07-30 15:15:10 +0200
# source_branch: lp:~mkbosmans/bzr/topo_sort
# base_revision_id: pqm at pqm.ubuntu.com-20090729225922-ct2n8v4ebyr46xwq
#
# Begin patch
=== modified file 'bzrlib/tests/test_tsort.py'
--- bzrlib/tests/test_tsort.py 2009-03-23 14:59:43 +0000
+++ bzrlib/tests/test_tsort.py 2009-07-30 12:55:32 +0000
@@ -39,6 +39,20 @@
                          list,
                          TopoSorter(graph).iter_topo_order())

+    def assertSortAndIterateOrder(self, graph):
+        """Check that sorting and iter_topo_order on graph really
results in topological order.
+
+        For every child in the graph, check if it comes after all of
it's parents.
+        """
+        sort_result = topo_sort(graph)
+        iter_result = list(TopoSorter(graph).iter_topo_order())
+        for (node, parents) in graph:
+            for parent in parents:
+                self.assertTrue(sort_result.index(node) >
sort_result.index(parent),
+                    "parent %s must come before child %s:\n%s" %
(parent, node, sort_result))
+                self.assertTrue(iter_result.index(node) >
iter_result.index(parent),
+                    "parent %s must come before child %s:\n%s" %
(parent, node, iter_result))
+
    def test_tsort_empty(self):
        """TopoSort empty list"""
        self.assertSortAndIterate([], [])
@@ -72,10 +86,10 @@
    def test_tsort_partial(self):
        """Topological sort with partial ordering.

-        If the graph does not give an order between two nodes, they are
-        returned in lexicographical order.
+        Multiple correct orderings are possible, so test for
+        correctness, not for exact match on the resulting list.
        """
-        self.assertSortAndIterate(([(0, []),
+        self.assertSortAndIterateOrder([(0, []),
                                   (1, [0]),
                                   (2, [0]),
                                   (3, [0]),
@@ -83,8 +97,7 @@
                                   (5, [1, 2]),
                                   (6, [1, 2]),
                                   (7, [2, 3]),
-                                   (8, [0, 1, 4, 5, 6])]),
-                                  [0, 1, 2, 3, 4, 5, 6, 7, 8])
+                                   (8, [0, 1, 4, 5, 6])])

    def test_tsort_unincluded_parent(self):
        """Sort nodes, but don't include some parents in the output"""

# Begin bundle
IyBCYXphYXIgcmV2aXNpb24gYnVuZGxlIHY0CiMKQlpoOTFBWSZTWYSuZgQAAiz/gERUQADS5//3
eyLMDr/v//BQBde7F3btUs7WW2mlXYVnCUmqbQAjFNqehiQ9IxNND1AAADQSiEwEZTTVNP0kzSPS
ZGhoAAyAAJEQkyFMzUyNNNTZFNlPQnigHqGR6TTyQ5piZMmjCYJiaYBMAhgjAjAJJNTTIieTENRq
ej1DSaPU9TINGgaGgCCIVtxrpvkrdj+z2G7VX75TrIhte1aDo1RgqSXkhRvqjNki2fNy0PD8Zc9H
feAeLIQTALsCo1E5cpE79zbR/f9BN7yY6amgmo6xHPNKBsxvNhlxwPp67oxPlBq7sIQYLRJtIM7Z
sV2Gq/XWUnxmxj1jak2xo2i5ZFeaNOt8EmWnJPtgsawxKXHpBryUoy8F5yoxK0ml6F454xgRzdkE
MC7KZ4YrjCJxflmvPbWrr8FfPpFsg6ubnJdww2hoGY/Tb8/jSW68vqQxkzu837Xy0Nnjg3cx4V5H
6Lt/JG4/lkiJFRTMZ95GiXFjNCBDibAyqyV6VPxSCemCOJYlei73I4onYysYNUNuyjkvDUMI1ic3
4VIL0WK0wsgZJUQ+ckh92m2VFoghqpfQ+FuFBH5btryBPqH3xIh18ZSBgUNofvx7MVzTJEf7kF+z
RStLKl5Y6hhQUzdWqAtOnJTrwjIUK2SjbUaji7TXQfI9A1EzLCc988JvZabhSZxmZB72G5G3FRQX
n8WvS5iWa3rO0qc7n2lQtkCqYpwgqris2XL9XRXikdxJIc3LgVKJkyKMkqKXNJogwc4VpQiimw2E
6cuHDLQpiFqw0TQod0qaJa1dggy0RrrI9UqDBO9ystOvLK5jOTlQxxKhTM4U9y52F7GNBu5Kj3vO
auUJe3yO7GawWykTSOxZSmdjb+V10/lmJ45uK5D8Mk76Dk9xt+G3QguwRgROqG229PRHI7BUUjGh
qLS0yFIpu+MokFe3WUaBG0EwTaB82MdfpKXkxnSgg8/fRYAOkxwdinEYJEzf1nG3A4dnkI3SsUaU
fwmrPemmpGIkRzxFkJUwTaQWYMZWsyD0hLiOdUR76Fa6lFbzwJHfFnFFD0Y++TsPAuVk8iGdp0HM
if49nSloaigPqLS+BU09TY3HTBOw0ArGXyk5rE2QFztuAbhlOQ4a2cCSuBNPhRUU7680Jdjp6iE4
l5vQ9toyWx0F5vUAOUVdsoAzBrggrlMLwyX8ZrguQ2ZUjI9zQQEGeiru474h9lgZgLQnLrtRYQnX
x4Zxmlh5SCplxRwvo1okyl4xFcNuxjQ+mRTO0OY9GjNTzdvtCdbPETuZuv6/duFFM/jv1+CHgclF
rvXQ2VK8TS1A/AJdM7Z1i2e212EhkqYD5mZwLBzj5oVsZ91ctiLMA9QuaOkJJ1nY+uCDNvRZwQdr
4QgvYbcJuqvgvNryO1O5LQsxcZi8i23iOSluooZE8lSrltsaZ9iD496gsJgkSUg/IyIxydC432k2
ZaKkpiUmAxTuunAxjYl0c6P1y5ltrZpYFOEQDS74uRbuzpRmX1ZIU9AyHRmLQP8MhmngKa+G4VGB
jdwys6RtgMHDhwRukC9A5AFqOGAdELLv6EtUdlkLLH10Tz+1TEVizTOOIFizyTSkNdfEChReo0qc
XA5YiQCSWJrLo750tThZrTgtfRXAKFGIsDRlSbIIGdRAoa54txyX/U/H0p00HXhArp5nUwgfLFxv
8fQ376gzUR7AIyLVilzUVAbwnKzOtYXZCS9tUoCoIuaP8hiPWOHI/pNYsg6kZOjAkDGjQi0GuEXj
FZo/QuM7oVKMvsl970yL1NBXVG+IOJgbrqwcajMMXUGIx5fGF4XhJkVMpXHVC+RENMiSzLocfCQj
t3wyTRuwiR+avsVmcTIHORQDawnomMdJFxOo44yJN1XiJSRf4u5IpwoSEJXMwIA=