diff options
-rw-r--r-- | buildstream/_loader/loadelement.py | 1 | ||||
-rw-r--r-- | buildstream/_loader/loader.py | 55 |
2 files changed, 27 insertions, 29 deletions
diff --git a/buildstream/_loader/loadelement.py b/buildstream/_loader/loadelement.py index 17154ee64..9e47c062e 100644 --- a/buildstream/_loader/loadelement.py +++ b/buildstream/_loader/loadelement.py @@ -69,6 +69,7 @@ class LoadElement(): self.full_name = None # The element full name (with associated junction) self.deps = None # The list of Dependency objects self.node_id = next(self._counter) + self.has_sorted_dependencies = False # Whether the element had his dependencies sorted already # # Private members diff --git a/buildstream/_loader/loader.py b/buildstream/_loader/loader.py index fc946d50b..75dc9ab15 100644 --- a/buildstream/_loader/loader.py +++ b/buildstream/_loader/loader.py @@ -19,6 +19,7 @@ import os from functools import cmp_to_key +from collections import deque from collections.abc import Mapping import tempfile import shutil @@ -144,20 +145,12 @@ class Loader(): self._check_circular_deps(dummy_target) profile_end(Topics.CIRCULAR_CHECK, profile_key) - ret = [] - # - # Sort direct dependencies of elements by their dependency ordering - # - for element in target_elements: - loader = element._loader - profile_start(Topics.SORT_DEPENDENCIES, element.name) - loader._sort_dependencies(element) - profile_end(Topics.SORT_DEPENDENCIES, element.name) - # Finally, wrap what we have into LoadElements and return the target - # - ret.append(loader._collect_element(element)) + self._sort_dependencies(target_elements) - return ret + return [ + element._loader._collect_element(element) + for element in target_elements + ] # cleanup(): # @@ -337,18 +330,9 @@ class Loader(): # sorts throughout the build process. # # Args: - # element (LoadElement): The element to sort + # element (list[LoadElement]): The elements to sort # - def _sort_dependencies(self, element, visited=None): - if visited is None: - visited = set() - - if element in visited: - return - - for dep in element.dependencies: - dep.element._loader._sort_dependencies(dep.element, visited=visited) - + def _sort_dependencies(self, elements): def dependency_cmp(dep_a, dep_b): element_a = dep_a.element element_b = dep_b.element @@ -388,12 +372,25 @@ class Loader(): # This wont ever happen return 0 - # Now dependency sort, we ensure that if any direct dependency - # directly or indirectly depends on another direct dependency, - # it is found later in the list. - element.dependencies.sort(key=cmp_to_key(dependency_cmp)) + elements_to_treat = deque(elements) + sort_key = cmp_to_key(dependency_cmp) + + profile_start(Topics.SORT_DEPENDENCIES, "_".join(e.name.replace(os.sep, '-') for e in elements)) + while elements_to_treat: + elem = elements_to_treat.pop() + + if elem.has_sorted_dependencies: + continue + + elem.dependencies.sort(key=sort_key) + elements_to_treat.extend( + dep.element + for dep in elem.dependencies + if not dep.element.has_sorted_dependencies + ) + elem.has_sorted_dependencies = True - visited.add(element) + profile_end(Topics.SORT_DEPENDENCIES, "_".join(e.name.replace(os.sep, '-') for e in elements)) # _collect_element() # |