loader.py: Make _collect_element() iterative

To reduce stack usage during load, make the LoadElement to MetaElement
conversion be iterative.

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

1 files changed, 41 insertions, 14 deletions

diff --git a/src/buildstream/_loader/loader.py b/src/buildstream/_loader/loader.py
index 13b2d1213..161a8cc08 100644
--- a/src/buildstream/_loader/loader.py
+++ b/src/buildstream/_loader/loader.py
@@ -449,18 +449,17 @@ class Loader():
 
             element.dependencies.sort(key=cmp_to_key(dependency_cmp))
 
-
-    # _collect_element()
+    # _collect_element_no_deps()
     #
-    # Collect the toplevel elements we have
+    # Collect a single element, without its dependencies, into a meta_element
     #
     # Args:
     #    element (LoadElement): The element for which to load a MetaElement
     #
     # Returns:
-    #    (MetaElement): A recursively loaded MetaElement
+    #    (MetaElement): A partially loaded MetaElement
     #
-    def _collect_element(self, element):
+    def _collect_element_no_deps(self, element):
         # Return the already built one, if we already built it
         meta_element = self._meta_elements.get(element.name)
         if meta_element:
@@ -502,17 +501,45 @@ class Loader():
         # Cache it now, make sure it's already there before recursing
         self._meta_elements[element.name] = meta_element
 
-        # Descend
-        for dep in element.dependencies:
-            loader = dep.element._loader
-            meta_dep = loader._collect_element(dep.element)
-            if dep.dep_type != 'runtime':
-                meta_element.build_dependencies.append(meta_dep)
-            if dep.dep_type != 'build':
-                meta_element.dependencies.append(meta_dep)
-
         return meta_element
 
+    # _collect_element()
+    #
+    # Collect the toplevel elements we have
+    #
+    # Args:
+    #    top_element (LoadElement): The element for which to load a MetaElement
+    #
+    # Returns:
+    #    (MetaElement): A fully loaded MetaElement
+    #
+    def _collect_element(self, top_element):
+        element_queue = [top_element]
+        meta_element_queue = [self._collect_element_no_deps(top_element)]
+
+        while element_queue:
+            element = element_queue.pop()
+            meta_element = meta_element_queue.pop()
+
+            for dep in element.dependencies:
+
+                loader = dep.element._loader
+                name = dep.element.name
+
+                if name not in loader._meta_elements:
+                    meta_dep = loader._collect_element_no_deps(dep.element)
+                    element_queue.append(dep.element)
+                    meta_element_queue.append(meta_dep)
+                else:
+                    meta_dep = loader._meta_elements[name]
+
+                if dep.dep_type != 'runtime':
+                    meta_element.build_dependencies.append(meta_dep)
+                if dep.dep_type != 'build':
+                    meta_element.dependencies.append(meta_dep)
+
+        return self._meta_elements[top_element.name]
+
     # _get_loader():
     #
     # Return loader for specified junction