Rewrite dependency resolution

Closes #1028

1 files changed, 58 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