Spec.splice: Allow splices when multiples nodes in the DAG share a name (#46382)

The current `Spec.splice` model is very limited by the inability to splice specs that
contain multiple nodes with the same name.  This is an artifact of the original
algorithm design predating the separate concretization of build dependencies,
which was the first feature to allow multiple specs in a DAG to share a name.

This PR provides a complete reimplementation of `Spec.splice` to avoid that
limitation. At the same time, the new algorithm ensures that build dependencies
for spliced specs are not changed, since the splice by definition cannot change
the build-time information of the spec. This is handled by splitting the dependency
edges and link/run edges into separate dependencies as needed.

Signed-off-by: Gregory Becker <becker33@llnl.gov>

6 files changed, 514 insertions, 136 deletions

diff --git a/lib/spack/spack/deptypes.py b/lib/spack/spack/deptypes.py
index df965a87f1..53e138e1c2 100644
--- a/lib/spack/spack/deptypes.py
+++ b/lib/spack/spack/deptypes.py
@@ -43,6 +43,31 @@ NONE: DepFlag = 0
 ALL_FLAGS: Tuple[DepFlag, DepFlag, DepFlag, DepFlag] = (BUILD, LINK, RUN, TEST)
 
 
+def compatible(flag1: DepFlag, flag2: DepFlag) -> bool:
+    """Returns True if two depflags can be dependencies from a Spec to deps of the same name.
+
+    The only allowable separated dependencies are a build-only dependency, combined with a
+    non-build dependency. This separates our two process spaces, build time and run time.
+
+    These dependency combinations are allowed:
+        single dep on name: [b], [l], [r], [bl], [br], [blr]
+        two deps on name: [b, l], [b, r], [b, lr]
+
+    but none of these make any sense:
+        two build deps: [b, b], [b, br], [b, bl], [b, blr]
+        any two deps that both have an l or an r, i.e. [l, l], [r, r], [l, r], [bl, l], [bl, r]"""
+    # Cannot have overlapping build types to two different dependencies
+    if flag1 & flag2:
+        return False
+
+    # Cannot have two different link/run dependencies for the same name
+    link_run = LINK | RUN
+    if flag1 & link_run and flag2 & link_run:
+        return False
+
+    return True
+
+
 def flag_from_string(s: str) -> DepFlag:
     if s == "build":
         return BUILD
diff --git a/lib/spack/spack/spec.py b/lib/spack/spack/spec.py
index eac51b0f46..030bb50913 100644
--- a/lib/spack/spack/spec.py
+++ b/lib/spack/spack/spec.py
@@ -1739,19 +1739,28 @@ class Spec:
             self.add_dependency_edge(spec, depflag=depflag, virtuals=virtuals)
             return
 
-        # Keep the intersection of constraints when a dependency is added multiple times.
-        # The only restriction, currently, is keeping the same dependency type
+        # Keep the intersection of constraints when a dependency is added multiple times with
+        # the same deptype. Add a new dependency if it is added with a compatible deptype
+        # (for example, a build-only dependency is compatible with a link-only dependenyc).
+        # The only restrictions, currently, are that we cannot add edges with overlapping
+        # dependency types and we cannot add multiple edges that have link/run dependency types.
+        # See ``spack.deptypes.compatible``.
         orig = self._dependencies[spec.name]
         try:
             dspec = next(dspec for dspec in orig if depflag == dspec.depflag)
         except StopIteration:
-            edge_attrs = f"deptypes={dt.flag_to_chars(depflag).strip()}"
-            required_dep_str = f"^[{edge_attrs}] {str(spec)}"
+            # Error if we have overlapping or incompatible deptypes
+            if any(not dt.compatible(dspec.depflag, depflag) for dspec in orig):
+                edge_attrs = f"deptypes={dt.flag_to_chars(depflag).strip()}"
+                required_dep_str = f"^[{edge_attrs}] {str(spec)}"
+
+                raise DuplicateDependencyError(
+                    f"{spec.name} is a duplicate dependency, with conflicting dependency types\n"
+                    f"\t'{str(self)}' cannot depend on '{required_dep_str}'"
+                )
 
-            raise DuplicateDependencyError(
-                f"{spec.name} is a duplicate dependency, with conflicting dependency types\n"
-                f"\t'{str(self)}' cannot depend on '{required_dep_str}'"
-            )
+            self.add_dependency_edge(spec, depflag=depflag, virtuals=virtuals)
+            return
 
         try:
             dspec.spec.constrain(spec)
@@ -1776,7 +1785,10 @@ class Spec:
         for edge in selected:
             has_errors, details = False, []
             msg = f"cannot update the edge from {edge.parent.name} to {edge.spec.name}"
-            if edge.depflag & depflag:
+
+            # If the dependency is to an existing spec, we can update dependency
+            # types. If it is to a new object, check deptype compatibility.
+            if id(edge.spec) != id(dependency_spec) and not dt.compatible(edge.depflag, depflag):
                 has_errors = True
                 details.append(
                     (
@@ -1785,14 +1797,13 @@ class Spec:
                     )
                 )
 
-            if any(v in edge.virtuals for v in virtuals):
-                has_errors = True
-                details.append(
-                    (
-                        f"{edge.parent.name} has already an edge matching any"
-                        f" of these virtuals {virtuals}"
+                if any(v in edge.virtuals for v in virtuals):
+                    details.append(
+                        (
+                            f"{edge.parent.name} has already an edge matching any"
+                            f" of these virtuals {virtuals}"
+                        )
                     )
-                )
 
             if has_errors:
                 raise spack.error.SpecError(msg, "\n".join(details))
@@ -4168,6 +4179,144 @@ class Spec:
                         new_dependencies.add(edge)
             spec._dependencies = new_dependencies
 
+    def _virtuals_provided(self, root):
+        """Return set of virtuals provided by self in the context of root"""
+        if root is self:
+            # Could be using any virtual the package can provide
+            return set(self.package.virtuals_provided)
+
+        hashes = [s.dag_hash() for s in root.traverse()]
+        in_edges = set(
+            [edge for edge in self.edges_from_dependents() if edge.parent.dag_hash() in hashes]
+        )
+        return set().union(*[edge.virtuals for edge in in_edges])
+
+    def _splice_match(self, other, self_root, other_root):
+        """Return True if other is a match for self in a splice of other_root into self_root
+
+        Other is a splice match for self if it shares a name, or if self is a virtual provider
+        and other provides a superset of the virtuals provided by self. Virtuals provided are
+        evaluated in the context of a root spec (self_root for self, other_root for other).
+
+        This is a slight oversimplification. Other could be a match for self in the context of
+        one edge in self_root and not in the context of another edge. This method could be
+        expanded in the future to account for these cases.
+        """
+        if other.name == self.name:
+            return True
+
+        return bool(
+            self._virtuals_provided(self_root)
+            and self._virtuals_provided(self_root) <= other._virtuals_provided(other_root)
+        )
+
+    def _splice_detach_and_add_dependents(self, replacement, context):
+        """Helper method for Spec._splice_helper.
+
+        replacement is a node to splice in, context is the scope of dependents to consider relevant
+        to this splice."""
+        # Update build_spec attributes for all transitive dependents
+        # before we start changing their dependencies
+        ancestors_in_context = [
+            a
+            for a in self.traverse(root=False, direction="parents")
+            if a in context.traverse(deptype=dt.LINK | dt.RUN)
+        ]
+        for ancestor in ancestors_in_context:
+            # Only set it if it hasn't been spliced before
+            ancestor._build_spec = ancestor._build_spec or ancestor.copy()
+            ancestor.clear_cached_hashes(ignore=(ht.package_hash.attr,))
+
+        # For each direct dependent in the link/run graph, replace the dependency on
+        # node with one on replacement
+        # For each build dependent, restrict the edge to build-only
+        for edge in self.edges_from_dependents():
+            if edge.parent not in ancestors_in_context:
+                continue
+            build_dep = edge.depflag & dt.BUILD
+            other_dep = edge.depflag & ~dt.BUILD
+            if build_dep:
+                parent_edge = [e for e in edge.parent._dependencies[self.name] if e.spec is self]
+                assert len(parent_edge) == 1
+
+                edge.depflag = dt.BUILD
+                parent_edge[0].depflag = dt.BUILD
+            else:
+                edge.parent._dependencies.edges[self.name].remove(edge)
+                self._dependents.edges[edge.parent.name].remove(edge)
+
+            if other_dep:
+                edge.parent._add_dependency(replacement, depflag=other_dep, virtuals=edge.virtuals)
+
+    def _splice_helper(self, replacement, self_root, other_root):
+        """Main loop of a transitive splice.
+
+        The while loop around a traversal of self ensures that changes to self from previous
+        iterations are reflected in the traversal. This avoids evaluating irrelevant nodes
+        using topological traversal (all incoming edges traversed before any outgoing edge).
+        If any node will not be in the end result, its parent will be spliced and it will not
+        ever be considered.
+        For each node in self, find any analogous node in replacement and swap it in.
+        We assume all build deps are handled outside of this method
+
+        Arguments:
+            replacement: The node that will replace any equivalent node in self
+            self_root: The root of the spec that self comes from. This provides the context for
+                evaluating whether ``replacement`` is a match for each node of ``self``. See
+                ``Spec._splice_match`` and ``Spec._virtuals_provided`` for details.
+            other_root: The root of the spec that replacement comes from. This provides the context
+                for evaluating whether ``replacement`` is a match for each node of ``self``. See
+                ``Spec._splice_match`` and ``Spec._virtuals_provided`` for details.
+        """
+        ids = set(id(s) for s in replacement.traverse())
+
+        # Sort all possible replacements by name and virtual for easy access later
+        replacements_by_name = collections.defaultdict(list)
+        for node in replacement.traverse():
+            replacements_by_name[node.name].append(node)
+            virtuals = node._virtuals_provided(root=replacement)
+            for virtual in virtuals:
+                # Virtual may be spec or str, get name or return str
+                replacements_by_name[getattr(virtual, "name", virtual)].append(node)
+
+        changed = True
+        while changed:
+            changed = False
+
+            # Intentionally allowing traversal to change on each iteration
+            # using breadth-first traversal to ensure we only reach nodes that will
+            # be in final result
+            for node in self.traverse(root=False, order="topo", deptype=dt.ALL & ~dt.BUILD):
+                # If this node has already been swapped in, don't consider it again
+                if id(node) in ids:
+                    continue
+
+                analogs = replacements_by_name[node.name]
+                if not analogs:
+                    # If we have to check for matching virtuals, then we need to check that it
+                    # matches all virtuals. Use `_splice_match` to validate possible matches
+                    for virtual in node._virtuals_provided(root=self):
+                        analogs += [
+                            r
+                            for r in replacements_by_name[getattr(virtual, "name", virtual)]
+                            if r._splice_match(node, self_root=self_root, other_root=other_root)
+                        ]
+
+                    # No match, keep iterating over self
+                    if not analogs:
+                        continue
+
+                # If there are multiple analogs, this package must satisfy the constraint
+                # that a newer version can always replace a lesser version.
+                analog = max(analogs, key=lambda s: s.version)
+
+                # No splice needed here, keep checking
+                if analog == node:
+                    continue
+                node._splice_detach_and_add_dependents(analog, context=self)
+                changed = True
+                break
+
     def splice(self, other, transitive):
         """Splices dependency "other" into this ("target") Spec, and return the
         result as a concrete Spec.
@@ -4188,134 +4337,70 @@ class Spec:
         the same way it was built, any such changes are tracked by setting the
         build_spec to point to the corresponding dependency from the original
         Spec.
-        TODO: Extend this for non-concrete Specs.
         """
         assert self.concrete
         assert other.concrete
 
-        virtuals_to_replace = [v.name for v in other.package.virtuals_provided if v in self]
-        if virtuals_to_replace:
-            deps_to_replace = dict((self[v], other) for v in virtuals_to_replace)
-            # deps_to_replace = [self[v] for v in virtuals_to_replace]
-        else:
-            # TODO: sanity check and error raise here for other.name not in self
-            deps_to_replace = {self[other.name]: other}
-            # deps_to_replace = [self[other.name]]
-
-        for d in deps_to_replace:
-            if not all(
-                v in other.package.virtuals_provided or v not in self
-                for v in d.package.virtuals_provided
-            ):
-                # There was something provided by the original that we don't
-                # get from its replacement.
-                raise SpliceError(
-                    ("Splice between {0} and {1} will not provide " "the same virtuals.").format(
-                        self.name, other.name
-                    )
+        if not any(
+            node._splice_match(other, self_root=self, other_root=other)
+            for node in self.traverse(root=False, deptype=dt.LINK | dt.RUN)
+        ):
+            other_str = other.format("{name}/{hash:7}")
+            self_str = self.format("{name}/{hash:7}")
+            msg = f"Cannot splice {other_str} into {self_str}."
+            msg += f" Either {self_str} cannot depend on {other_str},"
+            msg += f" or {other_str} fails to provide a virtual used in {self_str}"
+            raise SpliceError(msg)
+
+        # Copies of all non-build deps, build deps will get added at the end
+        spec = self.copy(deps=dt.ALL & ~dt.BUILD)
+        replacement = other.copy(deps=dt.ALL & ~dt.BUILD)
+
+        def make_node_pairs(orig_spec, copied_spec):
+            return list(
+                zip(
+                    orig_spec.traverse(deptype=dt.ALL & ~dt.BUILD),
+                    copied_spec.traverse(deptype=dt.ALL & ~dt.BUILD),
                 )
-            for n in d.traverse(root=False):
-                if not all(
-                    any(
-                        v in other_n.package.virtuals_provided
-                        for other_n in other.traverse(root=False)
-                    )
-                    or v not in self
-                    for v in n.package.virtuals_provided
-                ):
-                    raise SpliceError(
-                        (
-                            "Splice between {0} and {1} will not provide " "the same virtuals."
-                        ).format(self.name, other.name)
-                    )
-
-        # For now, check that we don't have DAG with multiple specs from the
-        # same package
-        def multiple_specs(root):
-            counter = collections.Counter([node.name for node in root.traverse()])
-            _, max_number = counter.most_common()[0]
-            return max_number > 1
-
-        if multiple_specs(self) or multiple_specs(other):
-            msg = (
-                'Either "{0}" or "{1}" contain multiple specs from the same '
-                "package, which cannot be handled by splicing at the moment"
             )
-            raise ValueError(msg.format(self, other))
 
-        # Multiple unique specs with the same name will collide, so the
-        # _dependents of these specs should not be trusted.
-        # Variants may also be ignored here for now...
-
-        # Keep all cached hashes because we will invalidate the ones that need
-        # invalidating later, and we don't want to invalidate unnecessarily
-
-        def from_self(name, transitive):
-            if transitive:
-                if name in other:
-                    return False
-                if any(v in other for v in self[name].package.virtuals_provided):
-                    return False
-                return True
-            else:
-                if name == other.name:
-                    return False
-                if any(
-                    v in other.package.virtuals_provided
-                    for v in self[name].package.virtuals_provided
-                ):
-                    return False
-                return True
-
-        self_nodes = dict(
-            (s.name, s.copy(deps=False))
-            for s in self.traverse(root=True)
-            if from_self(s.name, transitive)
-        )
+        def mask_build_deps(in_spec):
+            for edge in in_spec.traverse_edges(cover="edges"):
+                edge.depflag &= ~dt.BUILD
 
         if transitive:
-            other_nodes = dict((s.name, s.copy(deps=False)) for s in other.traverse(root=True))
-        else:
-            # NOTE: Does not fully validate providers; loader races possible
-            other_nodes = dict(
-                (s.name, s.copy(deps=False))
-                for s in other.traverse(root=True)
-                if s is other or s.name not in self
-            )
-
-        nodes = other_nodes.copy()
-        nodes.update(self_nodes)
+            # These pairs will allow us to reattach all direct build deps
+            # We need the list of pairs while the two specs still match
+            node_pairs = make_node_pairs(self, spec)
 
-        for name in nodes:
-            if name in self_nodes:
-                for edge in self[name].edges_to_dependencies():
-                    dep_name = deps_to_replace.get(edge.spec, edge.spec).name
-                    nodes[name].add_dependency_edge(
-                        nodes[dep_name], depflag=edge.depflag, virtuals=edge.virtuals
-                    )
-                if any(dep not in self_nodes for dep in self[name]._dependencies):
-                    nodes[name].build_spec = self[name].build_spec
-            else:
-                for edge in other[name].edges_to_dependencies():
-                    nodes[name].add_dependency_edge(
-                        nodes[edge.spec.name], depflag=edge.depflag, virtuals=edge.virtuals
-                    )
-                if any(dep not in other_nodes for dep in other[name]._dependencies):
-                    nodes[name].build_spec = other[name].build_spec
+            # Ignore build deps in the modified spec while doing the splice
+            # They will be added back in at the end
+            mask_build_deps(spec)
 
-        ret = nodes[self.name]
-
-        # Clear cached hashes for all affected nodes
-        # Do not touch unaffected nodes
-        for dep in ret.traverse(root=True, order="post"):
-            opposite = other_nodes if dep.name in self_nodes else self_nodes
-            if any(name in dep for name in opposite.keys()):
-                # package hash cannot be affected by splice
-                dep.clear_cached_hashes(ignore=["package_hash"])
-
-                dep.dag_hash()
+            # Transitively splice any relevant nodes from new into base
+            # This handles all shared dependencies between self and other
+            spec._splice_helper(replacement, self_root=self, other_root=other)
+        else:
+            # Do the same thing as the transitive splice, but reversed
+            node_pairs = make_node_pairs(other, replacement)
+            mask_build_deps(replacement)
+            replacement._splice_helper(spec, self_root=other, other_root=self)
+
+            # Intransitively splice replacement into spec
+            # This is very simple now that all shared dependencies have been handled
+            for node in spec.traverse(order="topo", deptype=dt.LINK | dt.RUN):
+                if node._splice_match(other, self_root=spec, other_root=other):
+                    node._splice_detach_and_add_dependents(replacement, context=spec)
+
+        # Set up build dependencies for modified nodes
+        # Also modify build_spec because the existing ones had build deps removed
+        for orig, copy in node_pairs:
+            for edge in orig.edges_to_dependencies(depflag=dt.BUILD):
+                copy._add_dependency(edge.spec, depflag=dt.BUILD, virtuals=edge.virtuals)
+            if copy._build_spec:
+                copy._build_spec = orig.build_spec.copy()
 
-        return nodes[self.name]
+        return spec
 
     def clear_cached_hashes(self, ignore=()):
         """
diff --git a/lib/spack/spack/test/cmd/pkg.py b/lib/spack/spack/test/cmd/pkg.py
index bbe5b61462..d1f0ed139e 100644
--- a/lib/spack/spack/test/cmd/pkg.py
+++ b/lib/spack/spack/test/cmd/pkg.py
@@ -311,7 +311,7 @@ def test_pkg_grep(mock_packages, capfd):
     output, _ = capfd.readouterr()
     assert output.strip() == "\n".join(
         spack.repo.PATH.get_pkg_class(name).module.__file__
-        for name in ["splice-a", "splice-h", "splice-t", "splice-vh", "splice-z"]
+        for name in ["splice-a", "splice-h", "splice-t", "splice-vh", "splice-vt", "splice-z"]
     )
 
     # ensure that this string isn't fouhnd
diff --git a/lib/spack/spack/test/rewiring.py b/lib/spack/spack/test/rewiring.py
index 523ae5325b..4c770e1988 100644
--- a/lib/spack/spack/test/rewiring.py
+++ b/lib/spack/spack/test/rewiring.py
@@ -47,7 +47,7 @@ def test_rewire_db(mock_fetch, install_mockery, transitive):
         text_file_path = os.path.join(node.prefix, node.name)
         with open(text_file_path, "r") as f:
             text = f.read()
-            for modded_spec in node.traverse(root=True):
+            for modded_spec in node.traverse(root=True, deptype=("link", "run")):
                 assert modded_spec.prefix in text
 
 
@@ -59,6 +59,7 @@ def test_rewire_bin(mock_fetch, install_mockery, transitive):
     dep = Spec("garply cflags=-g").concretized()
     PackageInstaller([spec.package, dep.package], explicit=True).install()
     spliced_spec = spec.splice(dep, transitive=transitive)
+
     assert spec.dag_hash() != spliced_spec.dag_hash()
 
     spack.rewiring.rewire(spliced_spec)
@@ -99,6 +100,8 @@ def test_rewire_writes_new_metadata(mock_fetch, install_mockery):
         )
         assert os.path.exists(manifest_file_path)
         orig_node = spec[node.name]
+        if node == orig_node:
+            continue
         orig_manifest_file_path = os.path.join(
             orig_node.prefix,
             spack.store.STORE.layout.metadata_dir,
diff --git a/lib/spack/spack/test/spec_semantics.py b/lib/spack/spack/test/spec_semantics.py
index dc7f72c331..5ecec98db9 100644
--- a/lib/spack/spack/test/spec_semantics.py
+++ b/lib/spack/spack/test/spec_semantics.py
@@ -7,6 +7,7 @@ import pathlib
 
 import pytest
 
+import spack.deptypes as dt
 import spack.directives
 import spack.error
 import spack.parser
@@ -15,6 +16,7 @@ import spack.solver.asp
 import spack.spec
 import spack.store
 import spack.variant
+import spack.version as vn
 from spack.error import SpecError, UnsatisfiableSpecError
 from spack.spec import (
     ArchSpec,
@@ -32,6 +34,95 @@ from spack.variant import (
 )
 
 
+@pytest.fixture()
+def setup_complex_splice(monkeypatch):
+    r"""Fixture to set up splicing for two complex specs.
+
+    a_red is a spec in which every node has the variant color=red
+    c_blue is a spec in which every node has the variant color=blue
+
+    a_red structure:
+                     a -
+                    / \ \
+                   b   c \
+                  /|\ / \ |
+                 e | d   g@2
+                  \|/
+                  g@1
+
+    c_blue structure:
+                    c
+                   /|\
+                  d f \
+                 /  |\ \
+               g@2  e \ \
+                     \| /
+                     g@3
+
+    This is not intended for use in tests that use virtuals, so ``_splice_match`` is monkeypatched
+    to avoid needing package files for each spec.
+    """
+
+    def splice_match(self, other, self_root, other_root):
+        return self.name == other.name
+
+    def virtuals_provided(self, root):
+        return []
+
+    monkeypatch.setattr(Spec, "_splice_match", splice_match)
+    monkeypatch.setattr(Spec, "_virtuals_provided", virtuals_provided)
+
+    g1_red = Spec("g color=red")
+    g1_red.versions = vn.VersionList([vn.Version("1")])
+    g2_red = Spec("g color=red")
+    g2_red.versions = vn.VersionList([vn.Version("2")])
+    g2_blue = Spec("g color=blue")
+    g2_blue.versions = vn.VersionList([vn.Version("2")])
+    g3_blue = Spec("g color=blue")
+    g3_blue.versions = vn.VersionList([vn.Version("3")])
+
+    depflag = dt.LINK | dt.BUILD
+    e_red = Spec("e color=red")
+    e_red._add_dependency(g1_red, depflag=depflag, virtuals=())
+    e_blue = Spec("e color=blue")
+    e_blue._add_dependency(g3_blue, depflag=depflag, virtuals=())
+
+    d_red = Spec("d color=red")
+    d_red._add_dependency(g1_red, depflag=depflag, virtuals=())
+    d_blue = Spec("d color=blue")
+    d_blue._add_dependency(g2_blue, depflag=depflag, virtuals=())
+
+    b_red = Spec("b color=red")
+    b_red._add_dependency(e_red, depflag=depflag, virtuals=())
+    b_red._add_dependency(d_red, depflag=depflag, virtuals=())
+    b_red._add_dependency(g1_red, depflag=depflag, virtuals=())
+
+    f_blue = Spec("f color=blue")
+    f_blue._add_dependency(e_blue, depflag=depflag, virtuals=())
+    f_blue._add_dependency(g3_blue, depflag=depflag, virtuals=())
+
+    c_red = Spec("c color=red")
+    c_red._add_dependency(d_red, depflag=depflag, virtuals=())
+    c_red._add_dependency(g2_red, depflag=depflag, virtuals=())
+    c_blue = Spec("c color=blue")
+    c_blue._add_dependency(d_blue, depflag=depflag, virtuals=())
+    c_blue._add_dependency(f_blue, depflag=depflag, virtuals=())
+    c_blue._add_dependency(g3_blue, depflag=depflag, virtuals=())
+
+    a_red = Spec("a color=red")
+    a_red._add_dependency(b_red, depflag=depflag, virtuals=())
+    a_red._add_dependency(c_red, depflag=depflag, virtuals=())
+    a_red._add_dependency(g2_red, depflag=depflag, virtuals=())
+
+    for spec in [e_red, e_blue, d_red, d_blue, b_red, f_blue, c_red, c_blue, a_red]:
+        spec.versions = vn.VersionList([vn.Version("1")])
+
+        a_red._mark_concrete()
+        c_blue._mark_concrete()
+
+    return a_red, c_blue
+
+
 @pytest.mark.usefixtures("config", "mock_packages")
 class TestSpecSemantics:
     """Test satisfies(), intersects(), constrain() and other semantic operations on specs."""
@@ -959,6 +1050,164 @@ class TestSpecSemantics:
         # Finally, the spec should know it's been spliced:
         assert out.spliced
 
+    def test_splice_intransitive_complex(self, setup_complex_splice):
+        a_red, c_blue = setup_complex_splice
+
+        spliced = a_red.splice(c_blue, transitive=False)
+        assert spliced.satisfies(
+            "a color=red ^b color=red ^c color=blue "
+            "^d color=red ^e color=red ^f color=blue ^g@3 color=blue"
+        )
+        assert set(spliced.dependencies(deptype=dt.BUILD)) == set(
+            a_red.dependencies(deptype=dt.BUILD)
+        )
+        assert spliced.build_spec == a_red
+        # We cannot check spliced["b"].build_spec is spliced["b"] because Spec.__getitem__ creates
+        # a new wrapper object on each invocation. So we select once and check on that object
+        # For the rest of the unchanged specs we will just check the s._build_spec is None.
+        b = spliced["b"]
+        assert b == a_red["b"]
+        assert b.build_spec is b
+        assert set(b.dependents()) == {spliced}
+
+        assert spliced["c"].satisfies(
+            "c color=blue ^d color=red ^e color=red ^f color=blue ^g@3 color=blue"
+        )
+        assert set(spliced["c"].dependencies(deptype=dt.BUILD)) == set(
+            c_blue.dependencies(deptype=dt.BUILD)
+        )
+        assert spliced["c"].build_spec == c_blue
+        assert set(spliced["c"].dependents()) == {spliced}
+
+        assert spliced["d"] == a_red["d"]
+        assert spliced["d"]._build_spec is None
+        # Since D had a parent changed, it has a split edge for link vs build dependent
+        # note: spliced["b"] == b_red, referenced differently to preserve logic
+        assert set(spliced["d"].dependents()) == {spliced["b"], spliced["c"], a_red["c"]}
+        assert set(spliced["d"].dependents(deptype=dt.BUILD)) == {a_red["b"], a_red["c"]}
+
+        assert spliced["e"] == a_red["e"]
+        assert spliced["e"]._build_spec is None
+        # Because a copy of e is used, it does not have dependnets in the original specs
+        assert set(spliced["e"].dependents()) == {spliced["b"], spliced["f"]}
+        # Build dependent edge to f because f originally dependended on the e this was copied from
+        assert set(spliced["e"].dependents(deptype=dt.BUILD)) == {spliced["b"]}
+
+        assert spliced["f"].satisfies("f color=blue ^e color=red ^g@3 color=blue")
+        assert set(spliced["f"].dependencies(deptype=dt.BUILD)) == set(
+            c_blue["f"].dependencies(deptype=dt.BUILD)
+        )
+        assert spliced["f"].build_spec == c_blue["f"]
+        assert set(spliced["f"].dependents()) == {spliced["c"]}
+
+        # spliced["g"] is g3, but spliced["b"]["g"] is g1
+        assert spliced["g"] == a_red["g"]
+        assert spliced["g"]._build_spec is None
+        assert set(spliced["g"].dependents(deptype=dt.LINK)) == {
+            spliced,
+            spliced["c"],
+            spliced["f"],
+            a_red["c"],
+        }
+        assert set(spliced["g"].dependents(deptype=dt.BUILD)) == {spliced, a_red["c"]}
+
+        assert spliced["b"]["g"] == a_red["b"]["g"]
+        assert spliced["b"]["g"]._build_spec is None
+        assert set(spliced["b"]["g"].dependents()) == {spliced["b"], spliced["d"], spliced["e"]}
+
+        for edge in spliced.traverse_edges(cover="edges", deptype=dt.LINK | dt.RUN):
+            # traverse_edges creates a synthetic edge with no deptypes to the root
+            if edge.depflag:
+                depflag = dt.LINK
+                if (edge.parent.name, edge.spec.name) not in [
+                    ("a", "c"),  # These are the spliced edges
+                    ("c", "d"),
+                    ("f", "e"),
+                    ("c", "g"),
+                    ("f", "g"),
+                    ("c", "f"),  # ancestor to spliced edge
+                ]:
+                    depflag |= dt.BUILD
+                assert edge.depflag == depflag
+
+    def test_splice_transitive_complex(self, setup_complex_splice):
+        a_red, c_blue = setup_complex_splice
+
+        spliced = a_red.splice(c_blue, transitive=True)
+        assert spliced.satisfies(
+            "a color=red ^b color=red"
+            "^c color=blue ^d color=blue ^e color=blue ^f color=blue ^g@3 color=blue"
+        )
+        assert set(spliced.dependencies(deptype=dt.BUILD)) == set(
+            a_red.dependencies(deptype=dt.BUILD)
+        )
+        assert spliced.build_spec == a_red
+
+        assert spliced["b"].satisfies("b color=red ^d color=blue ^e color=blue ^g@2 color=blue")
+        assert set(spliced["b"].dependencies(deptype=dt.BUILD)) == set(
+            a_red["b"].dependencies(deptype=dt.BUILD)
+        )
+        assert spliced["b"].build_spec == a_red["b"]
+        assert set(spliced["b"].dependents()) == {spliced}
+
+        # We cannot check spliced["b"].build_spec is spliced["b"] because Spec.__getitem__ creates
+        # a new wrapper object on each invocation. So we select once and check on that object
+        # For the rest of the unchanged specs we will just check the s._build_spec is None.
+        c = spliced["c"]
+        assert c == c_blue
+        assert c.build_spec is c
+        assert set(c.dependents()) == {spliced}
+
+        assert spliced["d"] == c_blue["d"]
+        assert spliced["d"]._build_spec is None
+        assert set(spliced["d"].dependents()) == {spliced["b"], spliced["c"]}
+
+        assert spliced["e"] == c_blue["e"]
+        assert spliced["e"]._build_spec is None
+        assert set(spliced["e"].dependents()) == {spliced["b"], spliced["f"]}
+
+        assert spliced["f"] == c_blue["f"]
+        assert spliced["f"]._build_spec is None
+        assert set(spliced["f"].dependents()) == {spliced["c"]}
+
+        # spliced["g"] is g3, but spliced["d"]["g"] is g1
+        assert spliced["g"] == c_blue["g"]
+        assert spliced["g"]._build_spec is None
+        assert set(spliced["g"].dependents(deptype=dt.LINK)) == {
+            spliced,
+            spliced["b"],
+            spliced["c"],
+            spliced["e"],
+            spliced["f"],
+        }
+        # Because a copy of g3 is used, it does not have dependents in the original specs
+        # It has build dependents on these spliced specs because it is an unchanged dependency
+        # for them
+        assert set(spliced["g"].dependents(deptype=dt.BUILD)) == {
+            spliced["c"],
+            spliced["e"],
+            spliced["f"],
+        }
+
+        assert spliced["d"]["g"] == c_blue["d"]["g"]
+        assert spliced["d"]["g"]._build_spec is None
+        assert set(spliced["d"]["g"].dependents()) == {spliced["d"]}
+
+        for edge in spliced.traverse_edges(cover="edges", deptype=dt.LINK | dt.RUN):
+            # traverse_edges creates a synthetic edge with no deptypes to the root
+            if edge.depflag:
+                depflag = dt.LINK
+                if (edge.parent.name, edge.spec.name) not in [
+                    ("a", "c"),  # These are the spliced edges
+                    ("a", "g"),
+                    ("b", "d"),
+                    ("b", "e"),
+                    ("b", "g"),
+                    ("a", "b"),  # This edge not spliced, but b was spliced invalidating edge
+                ]:
+                    depflag |= dt.BUILD
+                assert edge.depflag == depflag
+
     @pytest.mark.parametrize("transitive", [True, False])
     def test_splice_with_cached_hashes(self, default_mock_concretization, transitive):
         spec = default_mock_concretization("splice-t")
@@ -1091,7 +1340,7 @@ class TestSpecSemantics:
 
     @pytest.mark.parametrize("transitive", [True, False])
     def test_splice_swap_names(self, default_mock_concretization, transitive):
-        spec = default_mock_concretization("splice-t")
+        spec = default_mock_concretization("splice-vt")
         dep = default_mock_concretization("splice-a+foo")
         out = spec.splice(dep, transitive)
         assert dep.name in out
@@ -1101,7 +1350,7 @@ class TestSpecSemantics:
     def test_splice_swap_names_mismatch_virtuals(self, default_mock_concretization, transitive):
         spec = default_mock_concretization("splice-t")
         dep = default_mock_concretization("splice-vh+foo")
-        with pytest.raises(spack.spec.SpliceError, match="will not provide the same virtuals."):
+        with pytest.raises(spack.spec.SpliceError, match="virtual"):
             spec.splice(dep, transitive)
 
     def test_spec_override(self):
diff --git a/lib/spack/spack/test/spec_syntax.py b/lib/spack/spack/test/spec_syntax.py
index 7a1bd3b3cd..22942862eb 100644
--- a/lib/spack/spack/test/spec_syntax.py
+++ b/lib/spack/spack/test/spec_syntax.py
@@ -552,6 +552,20 @@ def specfile_for(default_mock_concretization):
             "^[deptypes=build,link] zlib",
         ),
         (
+            "^[deptypes=link] zlib ^[deptypes=build] zlib",
+            [
+                Token(TokenType.START_EDGE_PROPERTIES, value="^["),
+                Token(TokenType.KEY_VALUE_PAIR, value="deptypes=link"),
+                Token(TokenType.END_EDGE_PROPERTIES, value="]"),
+                Token(TokenType.UNQUALIFIED_PACKAGE_NAME, value="zlib"),
+                Token(TokenType.START_EDGE_PROPERTIES, value="^["),
+                Token(TokenType.KEY_VALUE_PAIR, value="deptypes=build"),
+                Token(TokenType.END_EDGE_PROPERTIES, value="]"),
+                Token(TokenType.UNQUALIFIED_PACKAGE_NAME, value="zlib"),
+            ],
+            "^[deptypes=link] zlib ^[deptypes=build] zlib",
+        ),
+        (
             "git-test@git.foo/bar",
             [
                 Token(TokenType.UNQUALIFIED_PACKAGE_NAME, "git-test"),
@@ -992,6 +1006,8 @@ def test_disambiguate_hash_by_spec(spec1, spec2, constraint, mock_packages, monk
         ("x target=be platform=test os=be os=fe", "'platform'"),
         # Dependencies
         ("^[@foo] zlib", "edge attributes"),
+        ("x ^[deptypes=link]foo ^[deptypes=run]foo", "conflicting dependency types"),
+        ("x ^[deptypes=build,link]foo ^[deptypes=link]foo", "conflicting dependency types"),
         # TODO: Remove this as soon as use variants are added and we can parse custom attributes
         ("^[foo=bar] zlib", "edge attributes"),
         # Propagating reserved names generates a parse error