Rewrite dependency resolution

Closes #1028

3 files changed, 242 insertions, 28 deletions

diff --git a/configure.py b/configure.py
index 0dced7a07..ea209d7dd 100755
--- a/configure.py
+++ b/configure.py
@@ -2078,43 +2078,73 @@ class ModulesChooser(object):
 
         return False
 
-    def _resolve_dependencies(self, modname):
-        for dependency in self._modules[modname].dependencies():
+    @staticmethod
+    def resolve_dependencies(available_modules, dependency_table, module, loaded_modules=None):
+        """
+        Parameters
+        - available_modules: modules to choose from. Constant.
+        - dependency_table: module to dependencies map. Constant.
+        - module: name of the module to resolve dependencies. Constant.
+        - loaded_modules: modules already loaded. Defensive copy in order to not change value for caller.
+        """
+        if loaded_modules is None:
+            loaded_modules = set([])
+        else:
+            loaded_modules = copy.deepcopy(loaded_modules)
+
+        if module not in available_modules:
+            return False, None
+
+        loaded_modules.add(module)
+        for dependency in dependency_table[module]:
             dependency_choices = set(dependency.split('|'))
 
             dependency_met = False
-            new_loaded_mod = None
 
-            # Prefer what we already loaded
-            if not set(dependency_choices).isdisjoint(self._to_load):
+            if not set(dependency_choices).isdisjoint(loaded_modules):
                 dependency_met = True
             else:
-                possible_mods = dependency_choices.intersection(self._maybe_dep)
-                if possible_mods:
-                    new_loaded_mod = possible_mods.pop()
-                    dependency_met = True
-
-            if dependency_met:
-                if new_loaded_mod:
-                    self._maybe_dep.remove(new_loaded_mod)
-                    self._to_load.add(new_loaded_mod)
-                    # Added new_loaded_mod, now resolve its dependencies
-                    self._resolve_dependencies(new_loaded_mod)
-            else:
-                if modname in self._to_load:
-                    self._to_load.remove(modname)
-                if modname in self._maybe_dep:
-                    self._maybe_dep.remove(modname)
-                self._not_using_because['dependency failure'].add(modname)
+                possible_mods = dependency_choices.intersection(available_modules)
+
+                for mod in possible_mods:
+                    ok, dependency_modules = ModulesChooser.resolve_dependencies(
+                        available_modules, dependency_table, mod, loaded_modules)
+                    if ok:
+                        dependency_met = True
+                        loaded_modules.add(mod)
+                        loaded_modules.update(dependency_modules)
+                        break
 
-                # `modname` is kicked out, no need to check more further dependencies
-                return
+            if not dependency_met:
+                return False, None
+
+        return True, loaded_modules
+
+    def _modules_dependency_table(self):
+        out = {}
+        for modname in self._modules:
+            out[modname] = self._modules[modname].dependencies()
+        return out
 
     def _resolve_dependencies_for_all_modules(self):
-        for modname in self._to_load.copy():
-            # This will recusively load all dependencies if modname
-            # or mark those with dependency failures as unused
-            self._resolve_dependencies(modname)
+        available_modules = set(self._to_load) | set(self._maybe_dep)
+        dependency_table = self._modules_dependency_table()
+
+        successfully_loaded = set()
+
+        for modname in self._to_load:
+            # This will try to recusively load all dependencies of modname
+            ok, modules = self.resolve_dependencies(available_modules, dependency_table, modname)
+            if ok:
+                successfully_loaded.add(modname)
+                successfully_loaded.update(modules)
+            else:
+                # Skip this module
+                pass
+
+        self._not_using_because['dependency failure'].update(self._to_load - successfully_loaded)
+        self._to_load = successfully_loaded
+        self._maybe_dep -= successfully_loaded
 
     def _handle_by_load_on(self, module): # pylint: disable=too-many-branches
         modname = module.basename
diff --git a/src/scripts/ci/travis/lint.sh b/src/scripts/ci/travis/lint.sh
index 16d7e5fc0..0e5fcc18f 100755
--- a/src/scripts/ci/travis/lint.sh
+++ b/src/scripts/ci/travis/lint.sh
@@ -11,6 +11,10 @@ python3 -m pylint configure.py
 python2 -m pylint --disable=superfluous-parens,too-many-locals configure.py
 echo "travis_fold:end:pylint_configure"
 
+echo "travis_fold:start:pylint_python_unittests"
+python3 -m pylint src/scripts/python_uniitests.py
+echo "travis_fold:end:pylint_python_unittests"
+
 echo "travis_fold:start:pylint_botanpy"
 python3 -m pylint src/python/botan2.py || true
 python2 -m pylint --disable=superfluous-parens,too-many-locals src/python/botan2.py || true
diff --git a/src/scripts/python_uniitests.py b/src/scripts/python_uniitests.py
new file mode 100755
index 000000000..10d465fea
--- /dev/null
+++ b/src/scripts/python_uniitests.py
@@ -0,0 +1,180 @@
+#!/usr/bin/env python3
+
+"""
+Unittests for Botan Python scripts.
+
+Requires Python 3.
+
+(C) 2017 Simon Warta (Kullo GmbH)
+
+Botan is released under the Simplified BSD License (see license.txt)
+"""
+
+import sys
+import unittest
+
+sys.path.append("../..") # Botan repo root
+from configure import ModulesChooser # pylint: disable=wrong-import-position
+
+
+class ModulesChooserResolveDependencies(unittest.TestCase):
+    def test_base(self):
+        available_modules = set(["A", "B"])
+        table = {
+            "A": [],
+        }
+        ok, modules = ModulesChooser.resolve_dependencies(available_modules, table, "A")
+        self.assertTrue(ok)
+        self.assertEqual(modules, set(["A"]))
+
+    def test_no_dependencies_defined(self):
+        available_modules = set(["A", "B"])
+        table = {
+            "A": [],
+        }
+        with self.assertRaises(KeyError):
+            ModulesChooser.resolve_dependencies(available_modules, table, "B")
+
+        available_modules = set(["A", "B"])
+        table = {
+            "A": ["B"],
+        }
+        with self.assertRaises(KeyError):
+            ModulesChooser.resolve_dependencies(available_modules, table, "A")
+
+    def test_add_dependency(self):
+        available_modules = set(["A", "B"])
+        table = {
+            "A": ["B"],
+            "B": []
+        }
+        ok, modules = ModulesChooser.resolve_dependencies(available_modules, table, "A")
+        self.assertTrue(ok)
+        self.assertEqual(modules, set(["A", "B"]))
+
+    def test_add_dependencies_two_levels(self):
+        available_modules = set(["A", "B", "C"])
+        table = {
+            "A": ["B"],
+            "B": ["C"],
+            "C": []
+        }
+        ok, modules = ModulesChooser.resolve_dependencies(available_modules, table, "A")
+        self.assertTrue(ok)
+        self.assertEqual(modules, set(["A", "B", "C"]))
+
+    def test_circular(self):
+        available_modules = set(["A", "B", "C"])
+        table = {
+            "A": ["B"],
+            "B": ["C"],
+            "C": ["A"]
+        }
+        ok, modules = ModulesChooser.resolve_dependencies(available_modules, table, "A")
+        self.assertTrue(ok)
+        self.assertEqual(modules, set(["A", "B", "C"]))
+
+    def test_not_available(self):
+        available_modules = set(["A", "C"])
+        table = {
+            "A": ["B"],
+            "B": ["C"],
+            "C": ["A"]
+        }
+        ok, _ = ModulesChooser.resolve_dependencies(available_modules, table, "B")
+        self.assertFalse(ok)
+
+    def test_dependency_not_available(self):
+        available_modules = set(["A", "C"])
+        table = {
+            "A": ["B"],
+            "B": ["C"],
+            "C": ["A"]
+        }
+        ok, _ = ModulesChooser.resolve_dependencies(available_modules, table, "A")
+        self.assertFalse(ok)
+
+    def test_dependency2_not_available(self):
+        available_modules = set(["A", "B"])
+        table = {
+            "A": ["B"],
+            "B": ["C"],
+            "C": ["A"]
+        }
+        ok, _ = ModulesChooser.resolve_dependencies(available_modules, table, "A")
+        self.assertFalse(ok)
+
+    def test_dependency_choices(self):
+        available_modules = set(["A", "B", "C"])
+        table = {
+            "A": ["B|C"],
+            "B": [],
+            "C": []
+        }
+        ok, modules = ModulesChooser.resolve_dependencies(available_modules, table, "A")
+        self.assertTrue(ok)
+        self.assertTrue(modules == set(["A", "B"]) or modules == set(["A", "C"]))
+
+    def test_dependency_prefer_existing(self):
+        available_modules = set(["A", "B", "C"])
+        table = {
+            "A": ["C", "B|C"],
+            "B": [],
+            "C": []
+        }
+        ok, modules = ModulesChooser.resolve_dependencies(available_modules, table, "A")
+        self.assertTrue(ok)
+        self.assertEqual(modules, set(["A", "C"]))
+
+    def test_dependency_prefer_existing2(self):
+        available_modules = set(["A", "B", "C"])
+        table = {
+            "A": ["B", "B|C"],
+            "B": [],
+            "C": []
+        }
+        ok, modules = ModulesChooser.resolve_dependencies(available_modules, table, "A")
+        self.assertTrue(ok)
+        self.assertEqual(modules, set(["A", "B"]))
+
+    def test_dependency_choices_impossible(self):
+        available_modules = set(["A", "C"])
+        table = {
+            "A": ["B|C"],
+            "B": [],
+            "C": []
+        }
+        ok, modules = ModulesChooser.resolve_dependencies(available_modules, table, "A")
+        self.assertTrue(ok)
+        self.assertEqual(modules, set(["A", "C"]))
+
+    def test_dependency_choices_impossible2(self):
+        available_modules = set(["A", "B"])
+        table = {
+            "A": ["B|C"],
+            "B": [],
+            "C": []
+        }
+        ok, modules = ModulesChooser.resolve_dependencies(available_modules, table, "A")
+        self.assertTrue(ok)
+        self.assertEqual(modules, set(["A", "B"]))
+
+    def test_deep(self):
+        available_modules = set(["A", "B", "C", "E", "G"])
+        table = {
+            "A": ["B|C"],
+            "B": ["D"],
+            "C": ["E"],
+            "D": [],
+            "E": ["F|G"],
+            "F": ["A", "B"],
+            "G": ["A", "G"]
+        }
+        ok, modules = ModulesChooser.resolve_dependencies(available_modules, table, "G")
+        self.assertTrue(ok)
+        self.assertEqual(modules, set(["G", "A", "C", "E"]))
+
+
+if __name__ == '__main__':
+    unittest.TestCase.longMessage = True
+    unittest.main()