Merge branch 'tristan/backport-update-state-changes-1.2' into 'bst-1.2'

Tristan/backport update state changes 1.2

See merge request BuildStream/buildstream!1256

36 files changed, 440 insertions, 88 deletions

diff --git a/buildstream/_context.py b/buildstream/_context.py
index a94d374cf..8dde091d3 100644
--- a/buildstream/_context.py
+++ b/buildstream/_context.py
@@ -31,7 +31,7 @@ from ._message import Message, MessageType
 from ._profile import Topics, profile_start, profile_end
 from ._artifactcache import ArtifactCache
 from ._workspaces import Workspaces
-from .plugin import _plugin_lookup
+from .plugin import Plugin
 
 
 # Context()
@@ -524,7 +524,7 @@ class Context():
         plugin_name = ""
         if message.unique_id:
             template += " {plugin}"
-            plugin = _plugin_lookup(message.unique_id)
+            plugin = Plugin._lookup(message.unique_id)
             plugin_name = plugin.name
 
         template += ": {message}"
diff --git a/buildstream/_frontend/app.py b/buildstream/_frontend/app.py
index f89202154..53a342899 100644
--- a/buildstream/_frontend/app.py
+++ b/buildstream/_frontend/app.py
@@ -531,7 +531,7 @@ class App():
                 queue = job.queue
 
                 # Get the last failure message for additional context
-                failure = self._fail_messages.get(element._get_unique_id())
+                failure = self._fail_messages.get(element._unique_id)
 
                 # XXX This is dangerous, sometimes we get the job completed *before*
                 # the failure message reaches us ??
diff --git a/buildstream/_frontend/widget.py b/buildstream/_frontend/widget.py
index b67c0e16c..3a41e1052 100644
--- a/buildstream/_frontend/widget.py
+++ b/buildstream/_frontend/widget.py
@@ -32,7 +32,7 @@ from .. import _yaml
 from .. import __version__ as bst_version
 from .._exceptions import ImplError
 from .._message import MessageType
-from ..plugin import _plugin_lookup
+from ..plugin import Plugin
 
 
 # These messages are printed a bit differently
@@ -187,7 +187,7 @@ class ElementName(Widget):
         if element_id is None:
             return ""
 
-        plugin = _plugin_lookup(element_id)
+        plugin = Plugin._lookup(element_id)
         name = plugin._get_full_name()
 
         # Sneak the action name in with the element name
@@ -224,7 +224,7 @@ class CacheKey(Widget):
 
         missing = False
         key = ' ' * self._key_length
-        plugin = _plugin_lookup(element_id)
+        plugin = Plugin._lookup(element_id)
         if isinstance(plugin, Element):
             _, key, missing = plugin._get_display_key()
 
@@ -586,7 +586,7 @@ class LogLine(Widget):
         # Track logfiles for later use
         element_id = message.task_id or message.unique_id
         if message.message_type in ERROR_MESSAGES and element_id is not None:
-            plugin = _plugin_lookup(element_id)
+            plugin = Plugin._lookup(element_id)
             self._failure_messages[plugin].append(message)
 
         return self._render(message)
diff --git a/buildstream/_scheduler/jobs/elementjob.py b/buildstream/_scheduler/jobs/elementjob.py
index 8ce5c062f..4d53a9d3d 100644
--- a/buildstream/_scheduler/jobs/elementjob.py
+++ b/buildstream/_scheduler/jobs/elementjob.py
@@ -73,7 +73,7 @@ class ElementJob(Job):
         self._complete_cb = complete_cb        # The complete callable function
 
         # Set the task wide ID for logging purposes
-        self.set_task_id(element._get_unique_id())
+        self.set_task_id(element._unique_id)
 
     @property
     def element(self):
@@ -100,7 +100,7 @@ class ElementJob(Job):
         args = dict(kwargs)
         args['scheduler'] = True
         self._scheduler.context.message(
-            Message(self._element._get_unique_id(),
+            Message(self._element._unique_id,
                     message_type,
                     message,
                     **args))
diff --git a/buildstream/_scheduler/queues/buildqueue.py b/buildstream/_scheduler/queues/buildqueue.py
index e63475f05..05e6f7a8b 100644
--- a/buildstream/_scheduler/queues/buildqueue.py
+++ b/buildstream/_scheduler/queues/buildqueue.py
@@ -35,9 +35,6 @@ class BuildQueue(Queue):
         return element._assemble()
 
     def status(self, element):
-        # state of dependencies may have changed, recalculate element state
-        element._update_state()
-
         if not element._is_required():
             # Artifact is not currently required but it may be requested later.
             # Keep it in the queue.
diff --git a/buildstream/_scheduler/queues/fetchqueue.py b/buildstream/_scheduler/queues/fetchqueue.py
index 114790c05..c5595e14a 100644
--- a/buildstream/_scheduler/queues/fetchqueue.py
+++ b/buildstream/_scheduler/queues/fetchqueue.py
@@ -44,9 +44,6 @@ class FetchQueue(Queue):
             source._fetch()
 
     def status(self, element):
-        # state of dependencies may have changed, recalculate element state
-        element._update_state()
-
         if not element._is_required():
             # Artifact is not currently required but it may be requested later.
             # Keep it in the queue.
@@ -72,7 +69,7 @@ class FetchQueue(Queue):
         if not success:
             return
 
-        element._update_state()
+        element._fetch_done()
 
         # Successful fetch, we must be CACHED now
         assert element._get_consistency() == Consistency.CACHED
diff --git a/buildstream/_scheduler/queues/pullqueue.py b/buildstream/_scheduler/queues/pullqueue.py
index 2842c5e21..e4868953e 100644
--- a/buildstream/_scheduler/queues/pullqueue.py
+++ b/buildstream/_scheduler/queues/pullqueue.py
@@ -38,9 +38,6 @@ class PullQueue(Queue):
             raise SkipJob(self.action_name)
 
     def status(self, element):
-        # state of dependencies may have changed, recalculate element state
-        element._update_state()
-
         if not element._is_required():
             # Artifact is not currently required but it may be requested later.
             # Keep it in the queue.
diff --git a/buildstream/_scheduler/queues/queue.py b/buildstream/_scheduler/queues/queue.py
index af4698350..ec1f1405b 100644
--- a/buildstream/_scheduler/queues/queue.py
+++ b/buildstream/_scheduler/queues/queue.py
@@ -348,7 +348,7 @@ class Queue():
     # a message for the element they are processing
     def _message(self, element, message_type, brief, **kwargs):
         context = element._get_context()
-        message = Message(element._get_unique_id(), message_type, brief, **kwargs)
+        message = Message(element._unique_id, message_type, brief, **kwargs)
         context.message(message)
 
     def _element_log_path(self, element):
diff --git a/buildstream/_scheduler/queues/trackqueue.py b/buildstream/_scheduler/queues/trackqueue.py
index 133655e14..c9011edb9 100644
--- a/buildstream/_scheduler/queues/trackqueue.py
+++ b/buildstream/_scheduler/queues/trackqueue.py
@@ -19,8 +19,7 @@
 #        Jürg Billeter <juerg.billeter@codethink.co.uk>
 
 # BuildStream toplevel imports
-from ...plugin import _plugin_lookup
-from ... import SourceError
+from ...plugin import Plugin
 
 # Local imports
 from . import Queue, QueueStatus
@@ -55,7 +54,7 @@ class TrackQueue(Queue):
 
         # Set the new refs in the main process one by one as they complete
         for unique_id, new_ref in result:
-            source = _plugin_lookup(unique_id)
+            source = Plugin._lookup(unique_id)
             source._save_ref(new_ref)
 
         element._tracking_done()
diff --git a/buildstream/_stream.py b/buildstream/_stream.py
index 5d862de91..de3ae464c 100644
--- a/buildstream/_stream.py
+++ b/buildstream/_stream.py
@@ -28,7 +28,7 @@ import tarfile
 from contextlib import contextmanager
 from tempfile import TemporaryDirectory
 
-from ._exceptions import StreamError, ImplError, BstError, set_last_task_error
+from ._exceptions import StreamError, ImplError, BstError
 from ._message import Message, MessageType
 from ._scheduler import Scheduler, SchedStatus, TrackQueue, FetchQueue, BuildQueue, PullQueue, PushQueue
 from ._pipeline import Pipeline, PipelineSelection
@@ -1007,17 +1007,6 @@ class Stream():
 
         _, status = self._scheduler.run(self.queues)
 
-        # Force update element states after a run, such that the summary
-        # is more coherent
-        try:
-            for element in self.total_elements:
-                element._update_state()
-        except BstError as e:
-            self._message(MessageType.ERROR, "Error resolving final state", detail=str(e))
-            set_last_task_error(e.domain, e.reason)
-        except Exception as e:   # pylint: disable=broad-except
-            self._message(MessageType.BUG, "Unhandled exception while resolving final state", detail=str(e))
-
         if status == SchedStatus.ERROR:
             raise StreamError()
         elif status == SchedStatus.TERMINATED:
diff --git a/buildstream/element.py b/buildstream/element.py
index bc939bc92..7be27cb2a 100644
--- a/buildstream/element.py
+++ b/buildstream/element.py
@@ -88,6 +88,7 @@ from ._variables import Variables
 from ._versions import BST_CORE_ARTIFACT_VERSION
 from ._exceptions import BstError, LoadError, LoadErrorReason, ImplError, ErrorDomain
 from .utils import UtilError
+from .types import _UniquePriorityQueue
 from . import Plugin, Consistency
 from . import SandboxFlags
 from . import utils
@@ -214,6 +215,8 @@ class Element(Plugin):
 
         self.__runtime_dependencies = []        # Direct runtime dependency Elements
         self.__build_dependencies = []          # Direct build dependency Elements
+        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
         self.__weak_cache_key = None            # Our cached weak cache key
         self.__strict_cache_key = None          # Our cached cache key for strict builds
@@ -924,9 +927,12 @@ class Element(Plugin):
         for meta_dep in meta.dependencies:
             dependency = Element._new_from_meta(meta_dep, artifacts)
             element.__runtime_dependencies.append(dependency)
+            dependency.__reverse_dependencies.add(element)
+
         for meta_dep in meta.build_dependencies:
             dependency = Element._new_from_meta(meta_dep, artifacts)
             element.__build_dependencies.append(dependency)
+            dependency.__reverse_dependencies.add(element)
 
         return element
 
@@ -1143,6 +1149,10 @@ class Element(Plugin):
                 # Strong cache key could not be calculated yet
                 return
 
+        if not self.__ready_for_runtime and self.__cache_key is not None:
+            self.__ready_for_runtime = all(
+                dep.__ready_for_runtime for dep in self.__runtime_dependencies)
+
     # _get_display_key():
     #
     # Returns cache keys for display purposes
@@ -1245,7 +1255,7 @@ class Element(Plugin):
         self.__tracking_scheduled = False
         self.__tracking_done = True
 
-        self._update_state()
+        self.__update_state_recursively()
 
     # _track():
     #
@@ -1262,7 +1272,7 @@ class Element(Plugin):
         for source in self.__sources:
             old_ref = source.get_ref()
             new_ref = source._track()
-            refs.append((source._get_unique_id(), new_ref))
+            refs.append((source._unique_id, new_ref))
 
             # Complimentary warning that the new ref will be unused.
             if old_ref != new_ref and self._get_workspace():
@@ -1421,7 +1431,7 @@ class Element(Plugin):
         self.__assemble_scheduled = False
         self.__assemble_done = True
 
-        self._update_state()
+        self.__update_state_recursively()
 
         if self._get_workspace() and self._cached():
             #
@@ -1592,6 +1602,15 @@ class Element(Plugin):
 
         return artifact_size
 
+    # _fetch_done()
+    #
+    # Indicates that fetching the sources for this element has been done.
+    #
+    def _fetch_done(self):
+        # We are not updating the state recursively here since fetching can
+        # never end up in updating them.
+        self._update_state()
+
     # _pull_pending()
     #
     # Check whether the artifact will be pulled.
@@ -1625,7 +1644,7 @@ class Element(Plugin):
     def _pull_done(self):
         self.__pull_done = True
 
-        self._update_state()
+        self.__update_state_recursively()
 
     def _pull_strong(self, *, progress=None):
         weak_key = self._get_cache_key(strength=_KeyStrength.WEAK)
@@ -2504,6 +2523,24 @@ class Element(Plugin):
 
         return utils._deduplicate(keys)
 
+    # __update_state_recursively()
+    #
+    # Update the state of all reverse dependencies, recursively.
+    #
+    def __update_state_recursively(self):
+        queue = _UniquePriorityQueue()
+        queue.push(self._unique_id, self)
+
+        while queue:
+            element = queue.pop()
+
+            old_ready_for_runtime = element.__ready_for_runtime
+            element._update_state()
+
+            if element.__ready_for_runtime != old_ready_for_runtime:
+                for rdep in element.__reverse_dependencies:
+                    queue.push(rdep._unique_id, rdep)
+
 
 def _overlap_error_detail(f, forbidden_overlap_elements, elements):
     if forbidden_overlap_elements:
diff --git a/buildstream/plugin.py b/buildstream/plugin.py
index f57c0e15c..2c94c212c 100644
--- a/buildstream/plugin.py
+++ b/buildstream/plugin.py
@@ -92,6 +92,7 @@ Class Reference
 ---------------
 """
 
+import itertools
 import os
 import subprocess
 from contextlib import contextmanager
@@ -145,6 +146,23 @@ class Plugin():
        core format version :ref:`core format version <project_format_version>`.
     """
 
+    # Unique id generator for Plugins
+    #
+    # Each plugin gets a unique id at creation.
+    # Ids are a monotically increasing integer
+    __id_generator = itertools.count()
+
+    # Hold on to a lookup table by counter of all instantiated plugins.
+    # We use this to send the id back from child processes so we can lookup
+    # corresponding element/source in the master process.
+    #
+    # Use WeakValueDictionary() so the map we use to lookup objects does not
+    # keep the plugins alive after pipeline destruction.
+    #
+    # Note that Plugins can only be instantiated in the main process before
+    # scheduling tasks.
+    __TABLE = WeakValueDictionary()
+
     def __init__(self, name, context, project, provenance, type_tag):
 
         self.name = name
@@ -157,11 +175,24 @@ class Plugin():
         For sources this is for display purposes only.
         """
 
+        # Unique ID
+        #
+        # This id allows to uniquely identify a plugin.
+        #
+        # /!\ the unique id must be an increasing value /!\
+        # This is because we are depending on it in buildstream.element.Element
+        # to give us a topological sort over all elements.
+        # Modifying how we handle ids here will modify the behavior of the
+        # Element's state handling.
+        self._unique_id = next(self.__id_generator)
+
+        # register ourself in the table containing all existing plugins
+        self.__TABLE[self._unique_id] = self
+
         self.__context = context        # The Context object
         self.__project = project        # The Project object
         self.__provenance = provenance  # The Provenance information
         self.__type_tag = type_tag      # The type of plugin (element or source)
-        self.__unique_id = _plugin_register(self)  # Unique ID
         self.__configuring = False      # Whether we are currently configuring
 
         # Infer the kind identifier
@@ -519,7 +550,7 @@ class Plugin():
               self.call(... command which takes time ...)
         """
         with self.__context.timed_activity(activity_name,
-                                           unique_id=self.__unique_id,
+                                           unique_id=self._unique_id,
                                            detail=detail,
                                            silent_nested=silent_nested):
             yield
@@ -611,6 +642,23 @@ class Plugin():
     #            Private Methods used in BuildStream            #
     #############################################################
 
+    # _lookup():
+    #
+    # Fetch a plugin in the current process by its
+    # unique identifier
+    #
+    # Args:
+    #    unique_id: The unique identifier as returned by
+    #               plugin._unique_id
+    #
+    # Returns:
+    #    (Plugin): The plugin for the given ID, or None
+    #
+    @classmethod
+    def _lookup(cls, unique_id):
+        assert unique_id in cls.__TABLE, "Could not find plugin with ID {}".format(unique_id)
+        return cls.__TABLE[unique_id]
+
     # _get_context()
     #
     # Fetches the invocation context
@@ -625,13 +673,6 @@ class Plugin():
     def _get_project(self):
         return self.__project
 
-    # _get_unique_id():
-    #
-    # Fetch the plugin's unique identifier
-    #
-    def _get_unique_id(self):
-        return self.__unique_id
-
     # _get_provenance():
     #
     # Fetch bst file, line and column of the entity
@@ -716,7 +757,7 @@ class Plugin():
         return (exit_code, output)
 
     def __message(self, message_type, brief, **kwargs):
-        message = Message(self.__unique_id, message_type, brief, **kwargs)
+        message = Message(self._unique_id, message_type, brief, **kwargs)
         self.__context.message(message)
 
     def __note_command(self, output, *popenargs, **kwargs):
@@ -734,42 +775,3 @@ class Plugin():
             return '{}:{}'.format(project.junction.name, self.name)
         else:
             return self.name
-
-
-# Hold on to a lookup table by counter of all instantiated plugins.
-# We use this to send the id back from child processes so we can lookup
-# corresponding element/source in the master process.
-#
-# Use WeakValueDictionary() so the map we use to lookup objects does not
-# keep the plugins alive after pipeline destruction.
-#
-# Note that Plugins can only be instantiated in the main process before
-# scheduling tasks.
-__PLUGINS_UNIQUE_ID = 0
-__PLUGINS_TABLE = WeakValueDictionary()
-
-
-# _plugin_lookup():
-#
-# Fetch a plugin in the current process by its
-# unique identifier
-#
-# Args:
-#    unique_id: The unique identifier as returned by
-#               plugin._get_unique_id()
-#
-# Returns:
-#    (Plugin): The plugin for the given ID, or None
-#
-def _plugin_lookup(unique_id):
-    assert unique_id in __PLUGINS_TABLE, "Could not find plugin with ID {}".format(unique_id)
-    return __PLUGINS_TABLE[unique_id]
-
-
-# No need for unregister, WeakValueDictionary() will remove entries
-# in itself when the referenced plugins are garbage collected.
-def _plugin_register(plugin):
-    global __PLUGINS_UNIQUE_ID                # pylint: disable=global-statement
-    __PLUGINS_UNIQUE_ID += 1
-    __PLUGINS_TABLE[__PLUGINS_UNIQUE_ID] = plugin
-    return __PLUGINS_UNIQUE_ID
diff --git a/buildstream/types.py b/buildstream/types.py
new file mode 100644
index 000000000..d54bf0b6e
--- /dev/null
+++ b/buildstream/types.py
@@ -0,0 +1,177 @@
+#
+#  Copyright (C) 2018 Bloomberg LP
+#
+#  This program is free software; you can redistribute it and/or
+#  modify it under the terms of the GNU Lesser General Public
+#  License as published by the Free Software Foundation; either
+#  version 2 of the License, or (at your option) any later version.
+#
+#  This library is distributed in the hope that it will be useful,
+#  but WITHOUT ANY WARRANTY; without even the implied warranty of
+#  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.	 See the GNU
+#  Lesser General Public License for more details.
+#
+#  You should have received a copy of the GNU Lesser General Public
+#  License along with this library. If not, see <http://www.gnu.org/licenses/>.
+#
+#  Authors:
+#        Tristan Van Berkom <tristan.vanberkom@codethink.co.uk>
+#        Jim MacArthur <jim.macarthur@codethink.co.uk>
+#        Benjamin Schubert <bschubert15@bloomberg.net>
+
+"""
+Foundation types
+================
+
+"""
+
+from enum import Enum
+import heapq
+
+
+class Scope(Enum):
+    """Defines the scope of dependencies to include for a given element
+    when iterating over the dependency graph in APIs like
+    :func:`Element.dependencies() <buildstream.element.Element.dependencies>`
+    """
+
+    ALL = 1
+    """All elements which the given element depends on, following
+    all elements required for building. Including the element itself.
+    """
+
+    BUILD = 2
+    """All elements required for building the element, including their
+    respective run dependencies. Not including the given element itself.
+    """
+
+    RUN = 3
+    """All elements required for running the element. Including the element
+    itself.
+    """
+
+    NONE = 4
+    """Just the element itself, no dependencies.
+
+    *Since: 1.4*
+    """
+
+
+class Consistency():
+    """Defines the various consistency states of a :class:`.Source`.
+    """
+
+    INCONSISTENT = 0
+    """Inconsistent
+
+    Inconsistent sources have no explicit reference set. They cannot
+    produce a cache key, be fetched or staged. They can only be tracked.
+    """
+
+    RESOLVED = 1
+    """Resolved
+
+    Resolved sources have a reference and can produce a cache key and
+    be fetched, however they cannot be staged.
+    """
+
+    CACHED = 2
+    """Cached
+
+    Sources have a cached unstaged copy in the source directory.
+    """
+
+
+class CoreWarnings():
+    """CoreWarnings()
+
+    Some common warnings which are raised by core functionalities within BuildStream are found in this class.
+    """
+
+    OVERLAPS = "overlaps"
+    """
+    This warning will be produced when buildstream detects an overlap on an element
+        which is not whitelisted. See :ref:`Overlap Whitelist <public_overlap_whitelist>`
+    """
+
+    REF_NOT_IN_TRACK = "ref-not-in-track"
+    """
+    This warning will be produced when a source is configured with a reference
+    which is found to be invalid based on the configured track
+    """
+
+    BAD_ELEMENT_SUFFIX = "bad-element-suffix"
+    """
+    This warning will be produced when an element whose name does not end in .bst
+    is referenced either on the command line or by another element
+    """
+
+    BAD_CHARACTERS_IN_NAME = "bad-characters-in-name"
+    """
+    This warning will be produces when filename for a target contains invalid
+    characters in its name.
+    """
+
+
+# _KeyStrength():
+#
+# Strength of cache key
+#
+class _KeyStrength(Enum):
+
+    # Includes strong cache keys of all build dependencies and their
+    # runtime dependencies.
+    STRONG = 1
+
+    # Includes names of direct build dependencies but does not include
+    # cache keys of dependencies.
+    WEAK = 2
+
+
+# _UniquePriorityQueue():
+#
+# Implements a priority queue that adds only each key once.
+#
+# The queue will store and priority based on a tuple (key, item).
+#
+class _UniquePriorityQueue:
+
+    def __init__(self):
+        self._items = set()
+        self._heap = []
+
+    # push():
+    #
+    # Push a new item in the queue.
+    #
+    # If the item is already present in the queue as identified by the key,
+    # this is a noop.
+    #
+    # Args:
+    #     key (hashable, comparable): unique key to use for checking for
+    #                                 the object's existence and used for
+    #                                 ordering
+    #     item (any): item to push to the queue
+    #
+    def push(self, key, item):
+        if key not in self._items:
+            self._items.add(key)
+            heapq.heappush(self._heap, (key, item))
+
+    # pop():
+    #
+    # Pop the next item from the queue, by priority order.
+    #
+    # Returns:
+    #     (any): the next item
+    #
+    # Throw:
+    #     IndexError: when the list is empty
+    #
+    def pop(self):
+        key, item = heapq.heappop(self._heap)
+        self._items.remove(key)
+        return item
+
+    def __len__(self):
+        return len(self._heap)
diff --git a/tests/frontend/workspace.py b/tests/frontend/workspace.py
index 8799362e8..1009ad3d8 100644
--- a/tests/frontend/workspace.py
+++ b/tests/frontend/workspace.py
@@ -782,3 +782,54 @@ def test_cache_key_workspace_in_dependencies(cli, tmpdir, datafiles, strict):
 
     # Check that the original /usr/bin/hello is not in the checkout
     assert not os.path.exists(os.path.join(checkout, 'usr', 'bin', 'hello'))
+
+
+# This strange test tests against a regression raised in issue #919,
+# where opening a workspace on a runtime dependency of a build only
+# dependency causes `bst build` to not build the specified target
+# but just successfully builds the workspaced element and happily
+# exits without completing the build.
+#
+TEST_DIR = os.path.join(
+    os.path.dirname(os.path.realpath(__file__))
+)
+
+
+@pytest.mark.datafiles(TEST_DIR)
+@pytest.mark.parametrize(
+    ["case", "non_workspaced_elements_state"],
+    [
+        ("workspaced-build-dep", ["waiting", "waiting", "waiting", "waiting", "waiting"]),
+        ("workspaced-runtime-dep", ["buildable", "buildable", "waiting", "waiting", "waiting"])
+    ],
+)
+@pytest.mark.parametrize("strict", [("strict"), ("non-strict")])
+def test_build_all(cli, tmpdir, datafiles, case, strict, non_workspaced_elements_state):
+    project = os.path.join(str(datafiles), case)
+    workspace = os.path.join(str(tmpdir), 'workspace')
+    non_leaf_elements = ["elem2.bst", "elem3.bst", "stack.bst", "elem4.bst", "elem5.bst"]
+    all_elements = ["elem1.bst", *non_leaf_elements]
+
+    # Configure strict mode
+    strict_mode = True
+    if strict != 'strict':
+        strict_mode = False
+    cli.configure({
+        'projects': {
+            'test': {
+                'strict': strict_mode
+            }
+        }
+    })
+
+    # First open the workspace
+    result = cli.run(project=project, args=['workspace', 'open', 'elem1.bst', workspace])
+    result.assert_success()
+
+    # Now build the targets elem4.bst and elem5.bst
+    result = cli.run(project=project, args=['build', 'elem4.bst', 'elem5.bst'])
+    result.assert_success()
+
+    # Assert that the target is built
+    for element in all_elements:
+        assert cli.get_element_state(project, element) == 'cached'
diff --git a/tests/frontend/workspaced-build-dep/elements/elem1.bst b/tests/frontend/workspaced-build-dep/elements/elem1.bst
new file mode 100644
index 000000000..eed39a95a
--- /dev/null
+++ b/tests/frontend/workspaced-build-dep/elements/elem1.bst
@@ -0,0 +1,5 @@
+kind: import
+
+sources:
+- kind: local
+  path: files/file1
diff --git a/tests/frontend/workspaced-build-dep/elements/elem2.bst b/tests/frontend/workspaced-build-dep/elements/elem2.bst
new file mode 100644
index 000000000..52f03f8aa
--- /dev/null
+++ b/tests/frontend/workspaced-build-dep/elements/elem2.bst
@@ -0,0 +1,9 @@
+kind: import
+
+depends:
+- filename: elem1.bst
+  type: build
+
+sources:
+- kind: local
+  path: files/file2
diff --git a/tests/frontend/workspaced-build-dep/elements/elem3.bst b/tests/frontend/workspaced-build-dep/elements/elem3.bst
new file mode 100644
index 000000000..a49b4bded
--- /dev/null
+++ b/tests/frontend/workspaced-build-dep/elements/elem3.bst
@@ -0,0 +1,9 @@
+kind: import
+
+depends:
+- filename: elem2.bst
+  type: build
+
+sources:
+- kind: local
+  path: files/file3
diff --git a/tests/frontend/workspaced-build-dep/elements/elem4.bst b/tests/frontend/workspaced-build-dep/elements/elem4.bst
new file mode 100644
index 000000000..9aa3432de
--- /dev/null
+++ b/tests/frontend/workspaced-build-dep/elements/elem4.bst
@@ -0,0 +1,9 @@
+kind: import
+
+depends:
+- filename: stack.bst
+  type: build
+
+sources:
+- kind: local
+  path: files/file4
diff --git a/tests/frontend/workspaced-build-dep/elements/elem5.bst b/tests/frontend/workspaced-build-dep/elements/elem5.bst
new file mode 100644
index 000000000..4fe2dcf58
--- /dev/null
+++ b/tests/frontend/workspaced-build-dep/elements/elem5.bst
@@ -0,0 +1,9 @@
+kind: import
+
+depends:
+- filename: elem3.bst
+  type: build
+
+sources:
+- kind: local
+  path: files/file4
diff --git a/tests/frontend/workspaced-build-dep/elements/stack.bst b/tests/frontend/workspaced-build-dep/elements/stack.bst
new file mode 100644
index 000000000..b4c6002f0
--- /dev/null
+++ b/tests/frontend/workspaced-build-dep/elements/stack.bst
@@ -0,0 +1,4 @@
+kind: stack
+
+depends:
+- elem3.bst
diff --git a/tests/frontend/workspaced-build-dep/files/file1 b/tests/frontend/workspaced-build-dep/files/file1
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/frontend/workspaced-build-dep/files/file1
diff --git a/tests/frontend/workspaced-build-dep/files/file2 b/tests/frontend/workspaced-build-dep/files/file2
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/frontend/workspaced-build-dep/files/file2
diff --git a/tests/frontend/workspaced-build-dep/files/file3 b/tests/frontend/workspaced-build-dep/files/file3
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/frontend/workspaced-build-dep/files/file3
diff --git a/tests/frontend/workspaced-build-dep/files/file4 b/tests/frontend/workspaced-build-dep/files/file4
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/frontend/workspaced-build-dep/files/file4
diff --git a/tests/frontend/workspaced-build-dep/project.conf b/tests/frontend/workspaced-build-dep/project.conf
new file mode 100644
index 000000000..e017957da
--- /dev/null
+++ b/tests/frontend/workspaced-build-dep/project.conf
@@ -0,0 +1,8 @@
+# Unique project name
+name: test
+
+# Required BuildStream format version
+format-version: 12
+
+# Subdirectory where elements are stored
+element-path: elements
diff --git a/tests/frontend/workspaced-runtime-dep/elements/elem1.bst b/tests/frontend/workspaced-runtime-dep/elements/elem1.bst
new file mode 100644
index 000000000..eed39a95a
--- /dev/null
+++ b/tests/frontend/workspaced-runtime-dep/elements/elem1.bst
@@ -0,0 +1,5 @@
+kind: import
+
+sources:
+- kind: local
+  path: files/file1
diff --git a/tests/frontend/workspaced-runtime-dep/elements/elem2.bst b/tests/frontend/workspaced-runtime-dep/elements/elem2.bst
new file mode 100644
index 000000000..5fb90dfc0
--- /dev/null
+++ b/tests/frontend/workspaced-runtime-dep/elements/elem2.bst
@@ -0,0 +1,9 @@
+kind: import
+
+depends:
+- filename: elem1.bst
+  type: runtime
+
+sources:
+- kind: local
+  path: files/file2
diff --git a/tests/frontend/workspaced-runtime-dep/elements/elem3.bst b/tests/frontend/workspaced-runtime-dep/elements/elem3.bst
new file mode 100644
index 000000000..c429c329f
--- /dev/null
+++ b/tests/frontend/workspaced-runtime-dep/elements/elem3.bst
@@ -0,0 +1,9 @@
+kind: import
+
+depends:
+- filename: elem2.bst
+  type: runtime
+
+sources:
+- kind: local
+  path: files/file3
diff --git a/tests/frontend/workspaced-runtime-dep/elements/elem4.bst b/tests/frontend/workspaced-runtime-dep/elements/elem4.bst
new file mode 100644
index 000000000..9aa3432de
--- /dev/null
+++ b/tests/frontend/workspaced-runtime-dep/elements/elem4.bst
@@ -0,0 +1,9 @@
+kind: import
+
+depends:
+- filename: stack.bst
+  type: build
+
+sources:
+- kind: local
+  path: files/file4
diff --git a/tests/frontend/workspaced-runtime-dep/elements/elem5.bst b/tests/frontend/workspaced-runtime-dep/elements/elem5.bst
new file mode 100644
index 000000000..4fe2dcf58
--- /dev/null
+++ b/tests/frontend/workspaced-runtime-dep/elements/elem5.bst
@@ -0,0 +1,9 @@
+kind: import
+
+depends:
+- filename: elem3.bst
+  type: build
+
+sources:
+- kind: local
+  path: files/file4
diff --git a/tests/frontend/workspaced-runtime-dep/elements/stack.bst b/tests/frontend/workspaced-runtime-dep/elements/stack.bst
new file mode 100644
index 000000000..b4c6002f0
--- /dev/null
+++ b/tests/frontend/workspaced-runtime-dep/elements/stack.bst
@@ -0,0 +1,4 @@
+kind: stack
+
+depends:
+- elem3.bst
diff --git a/tests/frontend/workspaced-runtime-dep/files/file1 b/tests/frontend/workspaced-runtime-dep/files/file1
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/frontend/workspaced-runtime-dep/files/file1
diff --git a/tests/frontend/workspaced-runtime-dep/files/file2 b/tests/frontend/workspaced-runtime-dep/files/file2
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/frontend/workspaced-runtime-dep/files/file2
diff --git a/tests/frontend/workspaced-runtime-dep/files/file3 b/tests/frontend/workspaced-runtime-dep/files/file3
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/frontend/workspaced-runtime-dep/files/file3
diff --git a/tests/frontend/workspaced-runtime-dep/files/file4 b/tests/frontend/workspaced-runtime-dep/files/file4
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/tests/frontend/workspaced-runtime-dep/files/file4
diff --git a/tests/frontend/workspaced-runtime-dep/project.conf b/tests/frontend/workspaced-runtime-dep/project.conf
new file mode 100644
index 000000000..e017957da
--- /dev/null
+++ b/tests/frontend/workspaced-runtime-dep/project.conf
@@ -0,0 +1,8 @@
+# Unique project name
+name: test
+
+# Required BuildStream format version
+format-version: 12
+
+# Subdirectory where elements are stored
+element-path: elements