Rather than sorting the entire list of tests, sort groups of tests that

share the same set of resources.  There are usually relatively few such 
combinations in a test suite compared to the number of tests and there 
can never be more.

Within a group of tests with the same resource requirements, the tests 
maintain their relative order from before sorting.

2 files changed, 63 insertions, 34 deletions

diff --git a/lib/testresources/__init__.py b/lib/testresources/__init__.py
index 27170ef..b935ee8 100644
--- a/lib/testresources/__init__.py
+++ b/lib/testresources/__init__.py
@@ -118,31 +118,38 @@ class OptimisingTestSuite(unittest.TestSuite):
 
         Feel free to override to improve the sort behaviour.
         """
-        # quick hack on the plane. Need to lookup graph textbook.
-        order = []
-        legacy, tests_with_resources = split_by_resources(self._tests)
-        if len(tests_with_resources) > 0:
-            # Recursive visit-all-nodes all-permutations.
-            def cost(from_resources, tests):
-                """Get the cost of resource traversal for tests.
-
-                :return: cost, order
-                """
-                if not tests:
-                    # tear down last resources
-                    return (sum(resource.tearDownCost for resource in
-                        from_resources), [])
-                costs = []
-                for test in tests:
-                    resources = frozenset([resource for _, resource in
-                        test.resources])
-                    child_cost, child_order = cost(resources, tests - set([test]))
-                    costs.append(
-                        (self.cost_of_switching(from_resources, resources) +
-                         child_cost, [test] + child_order))
-                return min(costs)
-            _, order = cost(frozenset(), set(tests_with_resources))
-        self._tests = order + legacy
+        # Build a map from sets of resources to the tests that require
+        # those resources.  There will usually be far fewer resource
+        # combinations than tests and there can never be more.
+        no_resources = frozenset()
+        resource_set_tests = {no_resources: []}
+        for test in self._tests:
+            resource_set = frozenset(
+                resource for name, resource in getattr(test, "resources", ()))
+            resource_set_tests.setdefault(resource_set, []).append(test)
+
+        # Recursive visit-all-nodes all-permutations.
+        def cost(from_set, resource_sets):
+            """Get the cost of resource traversal for resource sets.
+
+            :return: cost, order
+            """
+            if not resource_sets:
+                # tear down last resources
+                return self.cost_of_switching(from_set, no_resources), []
+            costs = []
+            for to_set in resource_sets:
+                child_cost, child_order = cost(
+                    to_set, resource_sets - set([to_set]))
+                costs.append(
+                    (self.cost_of_switching(from_set, to_set) + child_cost,
+                     [to_set] + child_order))
+            return min(costs)
+        _, order = cost(no_resources,
+                        set(resource_set_tests) - set([no_resources]))
+        order.append(no_resources)
+        self._tests = sum(
+            (resource_set_tests[resource_set] for resource_set in order), [])
 
     def _getGraph(self, tests_with_resources):
         """Build a graph of the resource-using nodes.
diff --git a/lib/testresources/tests/test_optimising_test_suite.py b/lib/testresources/tests/test_optimising_test_suite.py
index 2d988cb..80a10bb 100644
--- a/lib/testresources/tests/test_optimising_test_suite.py
+++ b/lib/testresources/tests/test_optimising_test_suite.py
@@ -312,6 +312,12 @@ class TestGraphStuff(testtools.TestCase):
         self.cases.append(self.case3)
         self.cases.append(self.case4)
 
+    def sortTests(self, tests):
+        suite = testresources.OptimisingTestSuite()
+        suite.addTests(tests)
+        suite.sortTests()
+        return suite._tests
+
     def _permute_four(self, cases):
         case1, case2, case3, case4 = cases
         permutations = []
@@ -343,7 +349,7 @@ class TestGraphStuff(testtools.TestCase):
         permutations.append([case4, case1, case2, case3])
         permutations.append([case4, case1, case3, case2])
         return permutations
-    
+
     def testBasicSortTests(self):
         # Test every permutation of inputs, with equal cost resources and
         # legacy tests.
@@ -361,11 +367,8 @@ class TestGraphStuff(testtools.TestCase):
         # 3, 2, 1, 4
 
         for permutation in self._permute_four(self.cases):
-            suite = testresources.OptimisingTestSuite()
-            suite.addTests(permutation)
-            suite.sortTests()
             self.assertIn(
-                suite._tests, [
+                self.sortTests(permutation), [
                     [self.case1, self.case2, self.case3, self.case4],
                 [self.case3, self.case2, self.case1, self.case4]])
 
@@ -422,7 +425,26 @@ class TestGraphStuff(testtools.TestCase):
         self.case3.resources = [("_two", resource_two),
             ("_three", resource_three)]
         for permutation in self._permute_four(self.cases):
-            suite = testresources.OptimisingTestSuite()
-            suite.addTests(permutation)
-            suite.sortTests()
-            self.assertIn( suite._tests, acceptable_orders)
+            self.assertIn(self.sortTests(permutation), acceptable_orders)
+
+    def testSortIsStableWithinGroups(self):
+        """Tests with the same resources maintain their relative order."""
+        resource_one = testresources.TestResource()
+        resource_two = testresources.TestResource()
+
+        self.case1.resources = [("_one", resource_one)]
+        self.case2.resources = [("_one", resource_one)]
+        self.case3.resources = [("_one", resource_one), ("_two", resource_two)]
+        self.case4.resources = [("_one", resource_one), ("_two", resource_two)]
+
+        tests = self.sortTests([self.case1, self.case2, self.case3, self.case4])
+        self.assertTrue(tests.index(self.case1) < tests.index(self.case2))
+        self.assertTrue(tests.index(self.case3) < tests.index(self.case4))
+
+        tests = self.sortTests([self.case2, self.case1, self.case3, self.case4])
+        self.assertTrue(tests.index(self.case2) < tests.index(self.case1))
+        self.assertTrue(tests.index(self.case3) < tests.index(self.case4))
+
+        tests = self.sortTests([self.case4, self.case3, self.case2, self.case1])
+        self.assertTrue(tests.index(self.case2) < tests.index(self.case1))
+        self.assertTrue(tests.index(self.case4) < tests.index(self.case3))