_loader/loader.py: Rewrite _load_file() semi-iterativelydanielsilverstone-ct/iterative-loader

In order to reduce the cost of recursion in loading a project,
this commit makes a semi-iterative treatment of the _load_file()
pathway.  It's only semi-iterative in the sense that whenever we
cross a loader boundary (junctions) we recurse.  This should mean
that high-depth projects load more safely.

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

1 files changed, 93 insertions, 35 deletions

diff --git a/src/buildstream/_loader/loader.py b/src/buildstream/_loader/loader.py
index 5bd048707..483671629 100644
--- a/src/buildstream/_loader/loader.py
+++ b/src/buildstream/_loader/loader.py
@@ -167,30 +167,23 @@ class Loader():
     #            Private Methods              #
     ###########################################
 
-    # _load_file():
+    # _load_file_no_deps():
+    #
+    # Load a bst file as a LoadElement
     #
-    # Recursively load bst files
+    # This loads a bst file into a LoadElement but does no work to resolve
+    # the element's dependencies.  The dependencies must be resolved properly
+    # before the LoadElement makes its way out of the loader.
     #
     # Args:
     #    filename (str): The element-path relative bst file
     #    rewritable (bool): Whether we should load in round trippable mode
-    #    ticker (callable): A callback to report loaded filenames to the frontend
-    #    fetch_subprojects (bool): Whether to fetch subprojects while loading
     #    provenance (Provenance): The location from where the file was referred to, or None
     #
     # Returns:
-    #    (LoadElement): A loaded LoadElement
+    #    (LoadElement): A partially-loaded LoadElement
     #
-    def _load_file(self, filename, rewritable, ticker, fetch_subprojects, provenance=None):
-
-        # Silently ignore already loaded files
-        if filename in self._elements:
-            return self._elements[filename]
-
-        # Call the ticker
-        if ticker:
-            ticker(filename)
-
+    def _load_file_no_deps(self, filename, rewritable, provenance=None):
         # Load the data and process any conditional statements therein
         fullpath = os.path.join(self._basedir, filename)
         try:
@@ -248,31 +241,96 @@ class Loader():
 
         self._elements[filename] = element
 
-        dependencies = _extract_depends_from_node(node)
-
-        # Load all dependency files for the new LoadElement
-        for dep in dependencies:
-            if dep.junction:
-                self._load_file(dep.junction, rewritable, ticker, fetch_subprojects, dep.provenance)
-                loader = self._get_loader(dep.junction, rewritable=rewritable, ticker=ticker,
-                                          fetch_subprojects=fetch_subprojects, provenance=dep.provenance)
-            else:
-                loader = self
+        return element
 
-            dep_element = loader._load_file(dep.name, rewritable, ticker,
-                                            fetch_subprojects, dep.provenance)
+    # _load_file():
+    #
+    # Semi-Iteratively load bst files
+    #
+    # The "Semi-" qualification is because where junctions get involved there
+    # is a measure of recursion, though this is limited only to the points at
+    # which junctions are crossed.
+    #
+    # Args:
+    #    filename (str): The element-path relative bst file
+    #    rewritable (bool): Whether we should load in round trippable mode
+    #    ticker (callable): A callback to report loaded filenames to the frontend
+    #    fetch_subprojects (bool): Whether to fetch subprojects while loading
+    #    provenance (Provenance): The location from where the file was referred to, or None
+    #
+    # Returns:
+    #    (LoadElement): A loaded LoadElement
+    #
+    def _load_file(self, filename, rewritable, ticker, fetch_subprojects, provenance=None):
 
-            if _yaml.node_get(dep_element.node, str, Symbol.KIND) == 'junction':
-                raise LoadError(LoadErrorReason.INVALID_DATA,
-                                "{}: Cannot depend on junction"
-                                .format(dep.provenance))
+        # Silently ignore already loaded files
+        if filename in self._elements:
+            return self._elements[filename]
 
-            element.dependencies.append(LoadElement.Dependency(dep_element, dep.dep_type))
+        # Call the ticker
+        if ticker:
+            ticker(filename)
 
-        deps_names = [dep.name for dep in dependencies]
-        self._warn_invalid_elements(deps_names)
+        top_element = self._load_file_no_deps(filename, rewritable, provenance)
+        dependencies = _extract_depends_from_node(top_element.node)
+        # The loader queue is a stack of tuples
+        # [0] is the LoadElement instance
+        # [1] is a stack of dependencies to load
+        # [2] is a list of dependency names used to warn when all deps are loaded
+        loader_queue = [(top_element, list(reversed(dependencies)), [])]
 
-        return element
+        # Load all dependency files for the new LoadElement
+        while loader_queue:
+            if loader_queue[-1][1]:
+                # We have deps to process, so look at the next one to do
+                dep = loader_queue[-1][1][-1]
+                if dep.junction:
+                    self._load_file(dep.junction, rewritable, ticker,
+                                    fetch_subprojects, dep.provenance)
+                    loader = self._get_loader(dep.junction,
+                                              rewritable=rewritable,
+                                              ticker=ticker,
+                                              fetch_subprojects=fetch_subprojects,
+                                              provenance=dep.provenance)
+                else:
+                    loader = self
+
+                if loader._elements.get(dep.name) is None:
+                    # The loader does not have this available so we need to
+                    # either recursively cause it to be loaded, or else we
+                    # need to push this onto the loader queue in this loader
+                    if loader is self:
+                        dep_element = self._load_file_no_deps(dep.name, rewritable, dep.provenance)
+                        dep_deps = _extract_depends_from_node(dep_element.node)
+                        loader_queue.append((dep_element, list(reversed(dep_deps)), []))
+                    else:
+                        # We discard the return value since we'll catch it
+                        # next time around the loop
+                        loader._load_file(dep.name, rewritable, ticker,
+                                          fetch_subprojects, dep.provenance)
+                else:
+                    dep_element = loader._elements[dep.name]
+                    if _yaml.node_get(dep_element.node, str, Symbol.KIND) == 'junction':
+                        raise LoadError(LoadErrorReason.INVALID_DATA,
+                                        "{}: Cannot depend on junction"
+                                        .format(dep.provenance))
+
+                    # All is well, push the dependency onto the LoadElement
+                    loader_queue[-1][0].dependencies.append(
+                        LoadElement.Dependency(dep_element, dep.dep_type))
+                    # Pop it off the queue
+                    loader_queue[-1][1].pop()
+                    # And record its name for checking later
+                    loader_queue[-1][2].append(dep.name)
+            else:
+                # We do not have any more dependencies to load for this
+                # element on the queue, report any invalid dep names
+                self._warn_invalid_elements(loader_queue[-1][2])
+                # And pop the element off the queue
+                loader_queue.pop()
+
+        # Nothing more in the queue, return the top level element we loaded.
+        return top_element
 
     # _check_circular_deps():
     #