testimage: sort modules based on dependencies

TEST_SUITES="auto" is useful to run all suitable tests without
having to hard-code the list. However, it did not take test
dependencies into account, which can be an issue for tests
which really depend on some other test to run first.

To fix this, modules get loaded in the order determined by
TESTS_SUITES, but then get re-ordered based on dependencies
derived from @skipUnlessPassed before running them. The original
order is used to break ties when there are no dependencies, so
reordering only occurs when really necessary.

@skipUnlessPassed gets extended such that it makes the test name
a method depends on available for inspection by the test loader
in oetest.py.

Unfortunately Python's unittest offers no API to inspect tests
in a TestSuite, so the code has to rely on implementation details
to find all tests. The worst that can happen when the implementation
changes is that tests are not found and reordering does not happen.

Signed-off-by: Patrick Ohly <patrick.ohly@intel.com>
Signed-off-by: Richard Purdie <richard.purdie@linuxfoundation.org>

3 files changed, 59 insertions, 4 deletions

diff --git a/meta/classes/testimage.bbclass b/meta/classes/testimage.bbclass
index 683173854d..dc163c7313 100644
--- a/meta/classes/testimage.bbclass
+++ b/meta/classes/testimage.bbclass
@@ -16,7 +16,11 @@
 # The test names are the module names in meta/lib/oeqa/runtime.
 # Each name in TEST_SUITES represents a required test for the image. (no skipping allowed)
 # Appending "auto" means that it will try to run all tests that are suitable for the image (each test decides that on it's own).
-# Note that order in TEST_SUITES is important (it's the order tests run) and it influences tests dependencies.
+# Note that order in TEST_SUITES is relevant: tests are run in an order such that
+# tests mentioned in @skipUnlessPassed run before the tests that depend on them,
+# but without such dependencies, tests run in the order in which they are listed
+# in TEST_SUITES.
+#
 # A layer can add its own tests in lib/oeqa/runtime, provided it extends BBPATH as normal in its layer.conf.
 
 # TEST_LOG_DIR contains a command ssh log and may contain infromation about what command is running, output and return codes and for qemu a boot log till login.
diff --git a/meta/lib/oeqa/oetest.py b/meta/lib/oeqa/oetest.py
index a3c5c1d358..da9556a6da 100644
--- a/meta/lib/oeqa/oetest.py
+++ b/meta/lib/oeqa/oetest.py
@@ -27,9 +27,59 @@ def loadTests(tc, type="runtime"):
         setattr(oeTest, "tc", tc)
     testloader = unittest.TestLoader()
     testloader.sortTestMethodsUsing = None
-    suite = testloader.loadTestsFromNames(tc.testslist)
-
-    return suite
+    suites = [testloader.loadTestsFromName(name) for name in tc.testslist]
+
+    def getTests(test):
+        '''Return all individual tests executed when running the suite.'''
+        # Unfortunately unittest does not have an API for this, so we have
+        # to rely on implementation details. This only needs to work
+        # for TestSuite containing TestCase.
+        method = getattr(test, '_testMethodName', None)
+        if method:
+            # leaf case: a TestCase
+            yield test
+        else:
+            # Look into TestSuite.
+            tests = getattr(test, '_tests', [])
+            for t1 in tests:
+                for t2 in getTests(t1):
+                    yield t2
+
+    # Determine dependencies between suites by looking for @skipUnlessPassed
+    # method annotations. Suite A depends on suite B if any method in A
+    # depends on a method on B.
+    for suite in suites:
+        suite.dependencies = []
+        suite.depth = 0
+        for test in getTests(suite):
+            methodname = getattr(test, '_testMethodName', None)
+            if methodname:
+                method = getattr(test, methodname)
+                depends_on = getattr(method, '_depends_on', None)
+                if depends_on:
+                    for dep_suite in suites:
+                        if depends_on in [getattr(t, '_testMethodName', None) for t in getTests(dep_suite)]:
+                            if dep_suite not in suite.dependencies and \
+                               dep_suite is not suite:
+                                suite.dependencies.append(dep_suite)
+                            break
+                    else:
+                        bb.warn("Test %s was declared as @skipUnlessPassed('%s') but that test is either not defined or not active. Will run the test anyway." %
+                                (test, depends_on))
+    # Use brute-force topological sort to determine ordering. Sort by
+    # depth (higher depth = must run later), with original ordering to
+    # break ties.
+    def set_suite_depth(suite):
+        for dep in suite.dependencies:
+            new_depth = set_suite_depth(dep) + 1
+            if new_depth > suite.depth:
+                suite.depth = new_depth
+        return suite.depth
+    for index, suite in enumerate(suites):
+        set_suite_depth(suite)
+        suite.index = index
+    suites.sort(cmp=lambda a,b: cmp((a.depth, a.index), (b.depth, b.index)))
+    return testloader.suiteClass(suites)
 
 def runTests(tc, type="runtime"):
 
diff --git a/meta/lib/oeqa/utils/decorators.py b/meta/lib/oeqa/utils/decorators.py
index ff5f278bc1..1e5a890fdd 100644
--- a/meta/lib/oeqa/utils/decorators.py
+++ b/meta/lib/oeqa/utils/decorators.py
@@ -85,6 +85,7 @@ class skipUnlessPassed(object):
                 raise unittest.SkipTest("Testcase dependency not met: %s" % self.testcase)
             return f(*args)
         wrapped_f.__name__ = f.__name__
+        wrapped_f._depends_on = self.testcase
         return wrapped_f
 
 class testcase(object):