_project.py, element.py: Add support for caching depsdanielsilverstone-ct/runtime-deps-cache

To speed up various dependency walks, cache, bottom-up, the case
of recursive build and runtime dependencies where nothing has
been visited before.

Signed-off-by: Daniel Silverstone <daniel.silverstone@codethink.co.uk>

2 files changed, 47 insertions, 4 deletions

diff --git a/src/buildstream/_project.py b/src/buildstream/_project.py
index 1fdc84acb..beadb9829 100644
--- a/src/buildstream/_project.py
+++ b/src/buildstream/_project.py
@@ -474,6 +474,10 @@ class Project():
             self._context.message(
                 Message(None, MessageType.WARN, "Ignoring redundant source references", detail=detail))
 
+        with self._context.timed_activity("Resolving element dependency graph"):
+            for element in elements:
+                element._prep_dependency_caches()
+
         return elements
 
     # ensure_fully_loaded()
diff --git a/src/buildstream/element.py b/src/buildstream/element.py
index 909a0e851..f77411b82 100644
--- a/src/buildstream/element.py
+++ b/src/buildstream/element.py
@@ -206,6 +206,8 @@ class Element(Plugin):
 
         self.__runtime_dependencies = []        # Direct runtime dependency Elements
         self.__build_dependencies = []          # Direct build dependency Elements
+        self.__build_dependency_cache = None    # Sorted deduplicated build dependencies
+        self.__runtime_dependency_cache = None  # Sorted deduplicated runtime dependencies
         self.__reverse_dependencies = set()     # Direct reverse dependency Elements
         self.__ready_for_runtime = False        # Wether the element has all its dependencies ready and has a cache key
         self.__sources = []                     # List of Sources
@@ -1040,6 +1042,43 @@ class Element(Plugin):
         cls.__instantiated_elements = {}
         cls.__redundant_source_refs = []
 
+    # _prep_dependency_caches()
+    #
+    # Prepare the runtime and build dependency caches for this element and its
+    # runtime and build dependencies.
+    #
+    def _prep_dependency_caches(self):
+        work_stack = [self]
+        while work_stack:
+            ele = work_stack.pop()
+            if ele.__runtime_dependency_cache is not None:
+                continue
+            unresolved = [e for e in ele.__runtime_dependencies if e.__runtime_dependency_cache is None]
+            unresolved.extend(e for e in ele.__build_dependencies if e.__runtime_dependency_cache is None)
+            if unresolved:
+                work_stack.append(ele)
+                work_stack.extend(unresolved)
+            else:
+                ele_set = BitMap()
+                ele_set.add(ele._unique_id)
+                full_rundeps = []
+                for rdep in ele.__runtime_dependencies:
+                    for e in rdep.__runtime_dependency_cache:
+                        if e._unique_id not in ele_set:
+                            ele_set.add(e._unique_id)
+                            full_rundeps.append(e)
+                full_rundeps.append(ele)
+                ele.__runtime_dependency_cache = full_rundeps
+
+                ele_set = BitMap()
+                full_bdeps = []
+                for bdep in ele.__build_dependencies:
+                    for e in bdep.__runtime_dependency_cache:
+                        if e._unique_id not in ele_set:
+                            ele_set.add(e._unique_id)
+                            full_bdeps.append(e)
+                ele.__build_dependency_cache = full_bdeps
+
     # _get_consistency()
     #
     # Returns cached consistency state
@@ -1120,7 +1159,7 @@ class Element(Plugin):
                 not self._source_cached():
             return False
 
-        for dependency in self.dependencies(Scope.BUILD):
+        for dependency in self.__build_dependency_cache:  # pylint: disable=not-an-iterable
             # In non-strict mode an element's strong cache key may not be available yet
             # even though an artifact is available in the local cache. This can happen
             # if the pull job is still pending as the remote cache may have an artifact
@@ -2924,7 +2963,7 @@ class Element(Plugin):
             if self.BST_STRICT_REBUILD:
                 dependencies = [
                     e._get_cache_key(strength=_KeyStrength.WEAK)
-                    for e in self.dependencies(Scope.BUILD)
+                    for e in self.__build_dependency_cache  # pylint: disable=not-an-iterable
                 ]
             else:
                 dependencies = [
@@ -2940,7 +2979,7 @@ class Element(Plugin):
 
         if self.__strict_cache_key is None:
             dependencies = [
-                e.__strict_cache_key for e in self.dependencies(Scope.BUILD)
+                e.__strict_cache_key for e in self.__build_dependency_cache  # pylint: disable=not-an-iterable
             ]
             self.__strict_cache_key = self._calculate_cache_key(dependencies)
 
@@ -3006,7 +3045,7 @@ class Element(Plugin):
             elif self.__assemble_scheduled or self.__assemble_done:
                 # Artifact will or has been built, not downloaded
                 dependencies = [
-                    e._get_cache_key() for e in self.dependencies(Scope.BUILD)
+                    e._get_cache_key() for e in self.__build_dependency_cache  # pylint: disable=not-an-iterable
                 ]
                 self.__cache_key = self._calculate_cache_key(dependencies)