loader: Move sort_dependencies to loadelement as a cython methodbschubert/optimize-loader

2 files changed, 78 insertions, 75 deletions

diff --git a/src/buildstream/_loader/loadelement.pyx b/src/buildstream/_loader/loadelement.pyx
index f68d8615a..867de6f29 100644
--- a/src/buildstream/_loader/loadelement.pyx
+++ b/src/buildstream/_loader/loadelement.pyx
@@ -17,9 +17,12 @@
 #  Authors:
 #        Tristan Van Berkom <tristan.vanberkom@codethink.co.uk>
 
+from functools import cmp_to_key
+
 from pyroaring import BitMap, FrozenBitMap  # pylint: disable=no-name-in-module
 
 from ..node cimport MappingNode
+from .types import Symbol
 
 
 # Counter to get ids to LoadElements
@@ -45,7 +48,7 @@ cdef class Dependency:
     cdef readonly LoadElement element
     cdef readonly str dep_type
 
-    def __init__(self, element, dep_type):
+    def __cinit__(self, LoadElement element, str dep_type):
         self.element = element
         self.dep_type = dep_type
 
@@ -72,7 +75,7 @@ cdef class LoadElement:
     cdef object _dep_cache
     cdef readonly list dependencies
 
-    def __init__(self, MappingNode node, str filename, object loader):
+    def __cinit__(self, MappingNode node, str filename, object loader):
 
         #
         # Public members
@@ -152,3 +155,74 @@ cdef class LoadElement:
             self._dep_cache.update(elt._dep_cache)
 
         self._dep_cache = FrozenBitMap(self._dep_cache)
+
+
+def _dependency_cmp(Dependency dep_a, Dependency dep_b):
+    cdef LoadElement element_a = dep_a.element
+    cdef LoadElement element_b = dep_b.element
+
+    # Sort on inter element dependency first
+    if element_a.depends(element_b):
+        return 1
+    elif element_b.depends(element_a):
+        return -1
+
+    # If there are no inter element dependencies, place
+    # runtime only dependencies last
+    if dep_a.dep_type != dep_b.dep_type:
+        if dep_a.dep_type == Symbol.RUNTIME:
+            return 1
+        elif dep_b.dep_type == Symbol.RUNTIME:
+            return -1
+
+    # All things being equal, string comparison.
+    if element_a.name > element_b.name:
+        return 1
+    elif element_a.name < element_b.name:
+        return -1
+
+    # Sort local elements before junction elements
+    # and use string comparison between junction elements
+    if element_a.junction and element_b.junction:
+        if element_a.junction > element_b.junction:
+            return 1
+        elif element_a.junction < element_b.junction:
+            return -1
+    elif element_a.junction:
+        return -1
+    elif element_b.junction:
+        return 1
+
+    # This wont ever happen
+    return 0
+
+
+# sort_dependencies():
+#
+# Sort dependencies of each element by their dependencies,
+# so that direct dependencies which depend on other direct
+# dependencies (directly or indirectly) appear later in the
+# list.
+#
+# This avoids the need for performing multiple topological
+# sorts throughout the build process.
+#
+# Args:
+#    element (LoadElement): The element to sort
+#
+def sort_dependencies(LoadElement element):
+    cdef list working_elements = [element]
+    cdef set visited = set(working_elements)
+    cdef Dependency dep
+
+    # 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.
+    while working_elements:
+        element = working_elements.pop()
+        for dep in element.dependencies:
+            if dep.element not in visited:
+                visited.add(dep.element)
+                working_elements.append(dep.element)
+
+        element.dependencies.sort(key=cmp_to_key(_dependency_cmp))
diff --git a/src/buildstream/_loader/loader.py b/src/buildstream/_loader/loader.py
index 337d25844..6108f10b8 100644
--- a/src/buildstream/_loader/loader.py
+++ b/src/buildstream/_loader/loader.py
@@ -18,7 +18,6 @@
 #        Tristan Van Berkom <tristan.vanberkom@codethink.co.uk>
 
 import os
-from functools import cmp_to_key
 
 from .._exceptions import LoadError, LoadErrorReason
 from .. import Consistency
@@ -30,6 +29,7 @@ from .._includes import Includes
 
 from ._loader import valid_chars_name
 from .types import Symbol, extract_depends_from_node
+from . import loadelement
 from .loadelement import Dependency, LoadElement
 from .metaelement import MetaElement
 from .metasource import MetaSource
@@ -137,7 +137,7 @@ class Loader():
         for element in target_elements:
             loader = element._loader
             with PROFILER.profile(Topics.SORT_DEPENDENCIES, element.name):
-                loader._sort_dependencies(element)
+                loadelement.sort_dependencies(element)
 
             # Finally, wrap what we have into LoadElements and return the target
             #
@@ -405,77 +405,6 @@ class Loader():
                 check_elements.remove(this_element)
                 validated.add(this_element)
 
-    # _sort_dependencies():
-    #
-    # Sort dependencies of each element by their dependencies,
-    # so that direct dependencies which depend on other direct
-    # dependencies (directly or indirectly) appear later in the
-    # list.
-    #
-    # This avoids the need for performing multiple topological
-    # sorts throughout the build process.
-    #
-    # Args:
-    #    element (LoadElement): The element to sort
-    #
-    @staticmethod
-    def _sort_dependencies(element):
-
-        working_elements = [element]
-        visited = set(working_elements)
-
-        def dependency_cmp(dep_a, dep_b):
-            element_a = dep_a.element
-            element_b = dep_b.element
-
-            # Sort on inter element dependency first
-            if element_a.depends(element_b):
-                return 1
-            elif element_b.depends(element_a):
-                return -1
-
-            # If there are no inter element dependencies, place
-            # runtime only dependencies last
-            if dep_a.dep_type != dep_b.dep_type:
-                if dep_a.dep_type == Symbol.RUNTIME:
-                    return 1
-                elif dep_b.dep_type == Symbol.RUNTIME:
-                    return -1
-
-            # All things being equal, string comparison.
-            if element_a.name > element_b.name:
-                return 1
-            elif element_a.name < element_b.name:
-                return -1
-
-            # Sort local elements before junction elements
-            # and use string comparison between junction elements
-            if element_a.junction and element_b.junction:
-                if element_a.junction > element_b.junction:
-                    return 1
-                elif element_a.junction < element_b.junction:
-                    return -1
-            elif element_a.junction:
-                return -1
-            elif element_b.junction:
-                return 1
-
-            # 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.
-        while working_elements:
-            element = working_elements.pop()
-            for dep in element.dependencies:
-                dep_element = dep.element
-                if dep_element not in visited:
-                    visited.add(dep_element)
-                    working_elements.append(dep_element)
-
-            element.dependencies.sort(key=cmp_to_key(dependency_cmp))
-
     # _collect_element_no_deps()
     #
     # Collect a single element, without its dependencies, into a meta_element