Make sorting dependencies non recursivebschubert/non-recursive-sort

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()
     #