partition tests to perform resource ordering optimisation into strongly connected sets of tests, reducing optimisation passes to cases where some resources are actually reused.

5 files changed, 151 insertions, 23 deletions

diff --git a/NEWS b/NEWS
index 971a6d1..f508bbd 100644
--- a/NEWS
+++ b/NEWS
@@ -13,6 +13,10 @@ IMPROVEMENTS
 * Rename TestResource to TestResourceManager leaving TestResource as an alias.
   Fixes bug #520769.
 
+* Test sorting no longer performs N! work on tests that can never benefit from
+  order optimisations (when resources are not shared an arbitrary order is
+  sufficient). Partial fix for bug #522338.
+
 0.2.3
 -----
 
diff --git a/lib/testresources/__init__.py b/lib/testresources/__init__.py
index d8988e1..52e53c2 100644
--- a/lib/testresources/__init__.py
+++ b/lib/testresources/__init__.py
@@ -28,6 +28,29 @@ def test_suite():
     return testresources.tests.test_suite()
 
 
+def _resource_graph(resource_sets):
+    """Convert an iterable of resource_sets into a graph.
+
+    Each resource_set in the iterable is treated as a node, and each resource
+    in that resource_set is used as an edge to other nodes.
+    """
+    nodes = {}
+    edges = {}
+    for resource_set in resource_sets:
+        # put node in nodes
+        node = frozenset(resource_set)
+        nodes[node] = set()
+        # put its contents in as edges
+        for resource in resource_set:
+            edges.setdefault(resource, []).append(node)
+    # populate the adjacent members of nodes
+    for node, connected in nodes.iteritems():
+        for resource in node:
+            connected.update(edges[resource])
+        connected.discard(node)
+    return nodes
+
+
 def split_by_resources(tests):
     """Split a list of tests by the resources that the tests use.
 
@@ -132,30 +155,48 @@ class OptimisingTestSuite(unittest.TestSuite):
         # since there will usually be fewer resource combinations than
         # actual tests and there can never be more.
         resource_set_tests = split_by_resources(self._tests)
-
-        graph = self._getGraph(resource_set_tests.keys())
+        # Partition into separate sets of resources, there is no ordering
+        # preference between sets that do not share members.
+        resource_set_graph = _resource_graph(resource_set_tests)
         no_resources = frozenset()
-        # 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 graph[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((graph[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), [])
+        # A list of resource_set_tests, all containing no_resources at minimum.
+        partitions = []
+        while resource_set_graph:
+            node, pending = resource_set_graph.popitem()
+            current_partition = set([no_resources, node])
+            while pending:
+                # add all the nodes connected to a connected node to pending.
+                node = pending.pop()
+                current_partition.add(node)
+                pending.update(resource_set_graph.pop(node, []))
+                # don't try to process things we've allready processed.
+                pending.difference_update(current_partition)
+            partitions.append(current_partition)
+        result = []
+        for partition in partitions:
+            graph = self._getGraph(partition)
+            # 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 graph[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((graph[from_set][to_set] + child_cost,
+                                  [to_set] + child_order))
+                return min(costs)
+            _, order = cost(no_resources, partition - set([no_resources]))
+            # Spit this partition out into result
+            for resource_set in order:
+                result.extend(resource_set_tests[resource_set])
+        result.extend(resource_set_tests[no_resources])
+        self._tests = result
 
     def _getGraph(self, resource_sets):
         """Build a graph of the resource-using nodes.
diff --git a/lib/testresources/tests/__init__.py b/lib/testresources/tests/__init__.py
index c7ab9e7..fe4958f 100644
--- a/lib/testresources/tests/__init__.py
+++ b/lib/testresources/tests/__init__.py
@@ -28,10 +28,12 @@ def test_suite():
     import testresources.tests.test_resourced_test_case
     import testresources.tests.test_test_loader
     import testresources.tests.test_test_resource
+    import testresources.tests.test_resource_graph
     result = TestUtil.TestSuite()
     result.addTest(testresources.tests.test_test_loader.test_suite())
     result.addTest(testresources.tests.test_test_resource.test_suite())
     result.addTest(testresources.tests.test_resourced_test_case.test_suite())
+    result.addTest(testresources.tests.test_resource_graph.test_suite())
     result.addTest(
         testresources.tests.test_optimising_test_suite.test_suite())
     return result
diff --git a/lib/testresources/tests/test_optimising_test_suite.py b/lib/testresources/tests/test_optimising_test_suite.py
index bd09d42..af9c7cb 100644
--- a/lib/testresources/tests/test_optimising_test_suite.py
+++ b/lib/testresources/tests/test_optimising_test_suite.py
@@ -584,6 +584,24 @@ class TestGraphStuff(testtools.TestCase):
                 permutation.index(self.case3) < permutation.index(self.case4),
                 sorted.index(self.case3) < sorted.index(self.case4))
 
+    def testSortingTwelveIndependentIsFast(self):
+        # Given twelve independent resource sets, my patience is not exhausted.
+        managers = []
+        for pos in range(12):
+            managers.append(testresources.TestResourceManager())
+        # Add more sample tests
+        cases = [self.case1, self.case2, self.case3, self.case4]
+        for pos in range(5,13):
+            cases.append(
+                testtools.clone_test_with_new_id(cases[0], 'case%d' % pos))
+        # We care that this is fast in this test, so we don't need to have
+        # overlapping resource usage
+        for case, manager in zip(cases, managers):
+            case.resources = [('_resource', manager)]
+        # Any sort is ok, as long as its the right length :)
+        result = self.sortTests(cases)
+        self.assertEqual(12, len(result))
+
     def testSortConsidersDependencies(self):
         """Tests with different dependencies are sorted together."""
         # We test this by having two resources (one and two) that share a very
diff --git a/lib/testresources/tests/test_resource_graph.py b/lib/testresources/tests/test_resource_graph.py
new file mode 100644
index 0000000..640dd24
--- /dev/null
+++ b/lib/testresources/tests/test_resource_graph.py
@@ -0,0 +1,63 @@
+#
+#  testresources: extensions to python unittest to allow declaritive use
+#  of resources by test cases.
+#  Copyright (C) 2010  Robert Collins <robertc@robertcollins.net>
+#
+#  This program is free software; you can redistribute it and/or modify
+#  it under the terms of the GNU General Public License as published by
+#  the Free Software Foundation; either version 2 of the License, or
+#  (at your option) any later version.
+#
+#  This program is distributed in the hope that it will be useful,
+#  but WITHOUT ANY WARRANTY; without even the implied warranty of
+#  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+#  GNU General Public License for more details.
+#
+#  You should have received a copy of the GNU General Public License
+#  along with this program; if not, write to the Free Software
+#  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+#
+
+"""Test _resource_graph(resource_sets)."""
+
+import testtools
+import testresources
+from testresources import split_by_resources, _resource_graph
+from testresources.tests import ResultWithResourceExtensions
+import unittest
+
+
+def test_suite():
+    from testresources.tests import TestUtil
+    loader = TestUtil.TestLoader()
+    result = loader.loadTestsFromName(__name__)
+    return result
+
+
+class TestResourceGraph(testtools.TestCase):
+
+    def test_empty(self):
+        no_resources = frozenset()
+        resource_sets = [no_resources]
+        self.assertEqual({no_resources:set([])}, _resource_graph(resource_sets))
+
+    def test_discrete(self):
+        resset1 = frozenset([testresources.TestResourceManager()])
+        resset2 = frozenset([testresources.TestResourceManager()])
+        resource_sets = [resset1, resset2]
+        result = _resource_graph(resource_sets)
+        self.assertEqual({resset1:set([]), resset2:set([])}, result)
+
+    def test_overlapping(self):
+        res1 = testresources.TestResourceManager()
+        res2 = testresources.TestResourceManager()
+        resset1 = frozenset([res1])
+        resset2 = frozenset([res2])
+        resset3 = frozenset([res1, res2])
+        resource_sets = [resset1, resset2, resset3]
+        result = _resource_graph(resource_sets)
+        self.assertEqual(
+            {resset1:set([resset3]),
+             resset2:set([resset3]),
+             resset3:set([resset1, resset2])},
+            result)