element.py: Introduce __update_strict_cache_key_of_rdeps()

Once an Element's strict cache key is determined, we should
attempt to update the strict cache key of it's reverse
dependencies. The state of a reverse dependency will be
updated once all of its dependencies have strict cache keys

This patch introduces the potential for a RecursionError because
_update_state() can now trigger further _update_state calls (on
reverse dependencies). Therefore, the maximum recursion limit
for our "test_max_recursion_depth" test has been lowered.

If this becomes a problem, we can always consider setting a
larger recursion limit, for now, this change has been tested
with the Debian stack and works as expected.

3 files changed, 45 insertions, 3 deletions

diff --git a/src/buildstream/_pipeline.py b/src/buildstream/_pipeline.py
index a96a3f731..a9d88befd 100644
--- a/src/buildstream/_pipeline.py
+++ b/src/buildstream/_pipeline.py
@@ -124,6 +124,11 @@ class Pipeline():
     #
     def resolve_elements(self, targets):
         with self._context.messenger.timed_activity("Resolving cached state", silent_nested=True):
+            # XXX: Now that Element._update_state() can trigger recursive update_state calls
+            # it is possible that we could get a RecursionError. However, this is unlikely
+            # to happen, even for large projects (tested with the Debian stack). Although,
+            # if it does become a problem we may have to set the recursion limit to a
+            # greater value.
             for element in self.dependencies(targets, Scope.ALL):
                 # Determine initial element state.
                 element._update_state()
diff --git a/src/buildstream/element.py b/src/buildstream/element.py
index faf97a52e..25f18c351 100644
--- a/src/buildstream/element.py
+++ b/src/buildstream/element.py
@@ -209,8 +209,11 @@ class Element(Plugin):
         self.__build_dependencies = []          # Direct build dependency Elements
         self.__reverse_build_deps = set()       # Direct reverse build dependency Elements
         self.__reverse_runtime_deps = set()     # Direct reverse runtime dependency Elements
+        self.__build_deps_without_strict_cache_key = None    # Number of build dependencies without a strict key
+        self.__runtime_deps_without_strict_cache_key = None  # Number of runtime dependencies without a strict key
         self.__build_deps_uncached = None    # Build dependencies which are not yet cached
         self.__runtime_deps_uncached = None  # Runtime dependencies which are not yet cached
+        self.__updated_strict_cache_keys_of_rdeps = False  # Whether we've updated strict cache keys of rdeps
         self.__ready_for_runtime = False        # Whether the element has all dependencies ready and has a cache key
         self.__ready_for_runtime_and_cached = False  # Whether all runtime deps are cached, as well as the element
         self.__sources = []                     # List of Sources
@@ -962,13 +965,17 @@ class Element(Plugin):
             dependency = Element._new_from_meta(meta_dep)
             element.__runtime_dependencies.append(dependency)
             dependency.__reverse_runtime_deps.add(element)
-        element.__runtime_deps_uncached = len(element.__runtime_dependencies)
+        no_of_runtime_deps = len(element.__runtime_dependencies)
+        element.__runtime_deps_without_strict_cache_key = no_of_runtime_deps
+        element.__runtime_deps_uncached = no_of_runtime_deps
 
         for meta_dep in meta.build_dependencies:
             dependency = Element._new_from_meta(meta_dep)
             element.__build_dependencies.append(dependency)
             dependency.__reverse_build_deps.add(element)
-        element.__build_deps_uncached = len(element.__build_dependencies)
+        no_of_build_deps = len(element.__build_dependencies)
+        element.__build_deps_without_strict_cache_key = no_of_build_deps
+        element.__build_deps_uncached = no_of_build_deps
 
         element.__preflight()
 
@@ -3042,6 +3049,9 @@ class Element(Plugin):
             ]
             self.__strict_cache_key = self._calculate_cache_key(dependencies)
 
+            if self.__strict_cache_key is not None:
+                self.__update_strict_cache_key_of_rdeps()
+
             # In strict mode, the strong cache key always matches the strict cache key
             if context.get_strict():
                 self.__cache_key = self.__strict_cache_key
@@ -3131,6 +3141,33 @@ class Element(Plugin):
             # Now we have the strong cache key, update the Artifact
             self.__artifact._cache_key = self.__cache_key
 
+    # __update_strict_cache_key_of_rdeps()
+    #
+    # Once an Element is given its strict cache key, immediately inform
+    # its reverse dependencies and see if their strict cache key can be
+    # obtained
+    #
+    def __update_strict_cache_key_of_rdeps(self):
+        if not self.__updated_strict_cache_keys_of_rdeps:
+            if self.__runtime_deps_without_strict_cache_key == 0 and \
+               self.__strict_cache_key is not None and not self.__cache_keys_unstable:
+                self.__updated_strict_cache_keys_of_rdeps = True
+
+                # Notify reverse dependencies
+                for rdep in self.__reverse_runtime_deps:
+                    rdep.__runtime_deps_without_strict_cache_key -= 1
+                    assert not rdep.__runtime_deps_without_strict_cache_key < 0
+
+                    if rdep.__runtime_deps_without_strict_cache_key == 0:
+                        rdep.__update_strict_cache_key_of_rdeps()
+
+                for rdep in self.__reverse_build_deps:
+                    rdep.__build_deps_without_strict_cache_key -= 1
+                    assert not rdep.__build_deps_without_strict_cache_key < 0
+
+                    if rdep.__build_deps_without_strict_cache_key == 0:
+                        rdep._update_state()
+
 
 def _overlap_error_detail(f, forbidden_overlap_elements, elements):
     if forbidden_overlap_elements:
diff --git a/tests/frontend/show.py b/tests/frontend/show.py
index 55691a5c6..d173fd80a 100644
--- a/tests/frontend/show.py
+++ b/tests/frontend/show.py
@@ -390,7 +390,7 @@ def test_fetched_junction(cli, tmpdir, datafiles, element_name, workspaced):
 ###############################################################
 #                   Testing recursion depth                   #
 ###############################################################
-@pytest.mark.parametrize("dependency_depth", [100, 500, 1200])
+@pytest.mark.parametrize("dependency_depth", [100, 150, 1200])
 def test_exceed_max_recursion_depth(cli, tmpdir, dependency_depth):
     project_name = "recursion-test"
     path = str(tmpdir)