Add virtual information on DAG edges (#34821)

* DependencySpec: add virtuals attribute on edges

This works for both the new and the old concretizer. Also,
added type hints to involved functions.

* Improve virtual reconstruction from old format

* Reconstruct virtuals when reading from Cray manifest

* Reconstruct virtual information on test dependencies

18 files changed, 290 insertions, 136 deletions

diff --git a/lib/spack/spack/build_systems/python.py b/lib/spack/spack/build_systems/python.py
index 3a49639fdc..f365fefe0f 100644
--- a/lib/spack/spack/build_systems/python.py
+++ b/lib/spack/spack/build_systems/python.py
@@ -223,7 +223,7 @@ class PythonExtension(spack.package_base.PackageBase):
 
                     python.external_path = self.spec.external_path
                     python._mark_concrete()
-            self.spec.add_dependency_edge(python, deptypes=("build", "link", "run"))
+            self.spec.add_dependency_edge(python, deptypes=("build", "link", "run"), virtuals=())
 
 
 class PythonPackage(PythonExtension):
diff --git a/lib/spack/spack/cray_manifest.py b/lib/spack/spack/cray_manifest.py
index 13a7fc43f0..664e4bd064 100644
--- a/lib/spack/spack/cray_manifest.py
+++ b/lib/spack/spack/cray_manifest.py
@@ -164,7 +164,10 @@ def entries_to_specs(entries):
                     continue
                 parent_spec = spec_dict[entry["hash"]]
                 dep_spec = spec_dict[dep_hash]
-                parent_spec._add_dependency(dep_spec, deptypes=deptypes)
+                parent_spec._add_dependency(dep_spec, deptypes=deptypes, virtuals=())
+
+    for spec in spec_dict.values():
+        spack.spec.reconstruct_virtuals_on_edges(spec)
 
     return spec_dict
 
diff --git a/lib/spack/spack/database.py b/lib/spack/spack/database.py
index 47cdb51774..5b557192b8 100644
--- a/lib/spack/spack/database.py
+++ b/lib/spack/spack/database.py
@@ -60,7 +60,7 @@ _db_dirname = ".spack-db"
 # DB version.  This is stuck in the DB file to track changes in format.
 # Increment by one when the database format changes.
 # Versions before 5 were not integers.
-_db_version = vn.Version("6")
+_db_version = vn.Version("7")
 
 # For any version combinations here, skip reindex when upgrading.
 # Reindexing can take considerable time and is not always necessary.
@@ -72,6 +72,7 @@ _skip_reindex = [
     # version is saved to disk the first time the DB is written.
     (vn.Version("0.9.3"), vn.Version("5")),
     (vn.Version("5"), vn.Version("6")),
+    (vn.Version("6"), vn.Version("7")),
 ]
 
 # Default timeout for spack database locks in seconds or None (no timeout).
@@ -105,7 +106,11 @@ default_install_record_fields = [
 
 
 def reader(version):
-    reader_cls = {vn.Version("5"): spack.spec.SpecfileV1, vn.Version("6"): spack.spec.SpecfileV3}
+    reader_cls = {
+        vn.Version("5"): spack.spec.SpecfileV1,
+        vn.Version("6"): spack.spec.SpecfileV3,
+        vn.Version("7"): spack.spec.SpecfileV4,
+    }
     return reader_cls[version]
 
 
@@ -743,7 +748,9 @@ class Database(object):
             spec_node_dict = spec_node_dict[spec.name]
         if "dependencies" in spec_node_dict:
             yaml_deps = spec_node_dict["dependencies"]
-            for dname, dhash, dtypes, _ in spec_reader.read_specfile_dep_specs(yaml_deps):
+            for dname, dhash, dtypes, _, virtuals in spec_reader.read_specfile_dep_specs(
+                yaml_deps
+            ):
                 # It is important that we always check upstream installations
                 # in the same order, and that we always check the local
                 # installation first: if a downstream Spack installs a package
@@ -766,7 +773,7 @@ class Database(object):
                     tty.warn(msg)
                     continue
 
-                spec._add_dependency(child, deptypes=dtypes)
+                spec._add_dependency(child, deptypes=dtypes, virtuals=virtuals)
 
     def _read_from_file(self, filename):
         """Fill database from file, do not maintain old data.
@@ -1172,7 +1179,7 @@ class Database(object):
             for dep in spec.edges_to_dependencies(deptype=_tracked_deps):
                 dkey = dep.spec.dag_hash()
                 upstream, record = self.query_by_spec_hash(dkey)
-                new_spec._add_dependency(record.spec, deptypes=dep.deptypes)
+                new_spec._add_dependency(record.spec, deptypes=dep.deptypes, virtuals=dep.virtuals)
                 if not upstream:
                     record.ref_count += 1
 
diff --git a/lib/spack/spack/environment/environment.py b/lib/spack/spack/environment/environment.py
index 82810e3b7d..3091a79848 100644
--- a/lib/spack/spack/environment/environment.py
+++ b/lib/spack/spack/environment/environment.py
@@ -125,7 +125,7 @@ spack:
 valid_environment_name_re = r"^\w[\w-]*$"
 
 #: version of the lockfile format. Must increase monotonically.
-lockfile_format_version = 4
+lockfile_format_version = 5
 
 
 READER_CLS = {
@@ -133,6 +133,7 @@ READER_CLS = {
     2: spack.spec.SpecfileV1,
     3: spack.spec.SpecfileV2,
     4: spack.spec.SpecfileV3,
+    5: spack.spec.SpecfileV4,
 }
 
 
@@ -1548,12 +1549,13 @@ class Environment:
             for h in self.specs_by_hash:
                 current_spec, computed_spec = self.specs_by_hash[h], by_hash[h]
                 for node in computed_spec.traverse():
-                    test_deps = node.dependencies(deptype="test")
-                    for test_dependency in test_deps:
+                    test_edges = node.edges_to_dependencies(deptype="test")
+                    for current_edge in test_edges:
+                        test_dependency = current_edge.spec
                         if test_dependency in current_spec[node.name]:
                             continue
                         current_spec[node.name].add_dependency_edge(
-                            test_dependency.copy(), deptypes="test"
+                            test_dependency.copy(), deptypes="test", virtuals=current_edge.virtuals
                         )
 
         results = [
@@ -2184,9 +2186,9 @@ class Environment:
         # and add them to the spec
         for lockfile_key, node_dict in json_specs_by_hash.items():
             name, data = reader.name_and_data(node_dict)
-            for _, dep_hash, deptypes, _ in reader.dependencies_from_node_dict(data):
+            for _, dep_hash, deptypes, _, virtuals in reader.dependencies_from_node_dict(data):
                 specs_by_hash[lockfile_key]._add_dependency(
-                    specs_by_hash[dep_hash], deptypes=deptypes
+                    specs_by_hash[dep_hash], deptypes=deptypes, virtuals=virtuals
                 )
 
         # Traverse the root specs one at a time in the order they appear.
diff --git a/lib/spack/spack/graph.py b/lib/spack/spack/graph.py
index e52cc64fdc..73fffaeaa6 100644
--- a/lib/spack/spack/graph.py
+++ b/lib/spack/spack/graph.py
@@ -544,6 +544,7 @@ def _static_edges(specs, deptype):
                     spack.spec.Spec(parent_name),
                     spack.spec.Spec(dependency_name),
                     deptypes=deptype,
+                    virtuals=(),
                 )
 
 
diff --git a/lib/spack/spack/installer.py b/lib/spack/spack/installer.py
index 3329b1a1ca..b178d30a71 100644
--- a/lib/spack/spack/installer.py
+++ b/lib/spack/spack/installer.py
@@ -231,7 +231,9 @@ def _packages_needed_to_bootstrap_compiler(compiler, architecture, pkgs):
     dep.concretize()
     # mark compiler as depended-on by the packages that use it
     for pkg in pkgs:
-        dep._dependents.add(spack.spec.DependencySpec(pkg.spec, dep, deptypes=("build",)))
+        dep._dependents.add(
+            spack.spec.DependencySpec(pkg.spec, dep, deptypes=("build",), virtuals=())
+        )
     packages = [(s.package, False) for s in dep.traverse(order="post", root=False)]
 
     packages.append((dep.package, True))
diff --git a/lib/spack/spack/parser.py b/lib/spack/spack/parser.py
index 6f94722e30..3416f2540b 100644
--- a/lib/spack/spack/parser.py
+++ b/lib/spack/spack/parser.py
@@ -291,7 +291,7 @@ class SpecParser:
                 if root_spec.concrete:
                     raise spack.spec.RedundantSpecError(root_spec, "^" + str(dependency))
 
-                root_spec._add_dependency(dependency, deptypes=())
+                root_spec._add_dependency(dependency, deptypes=(), virtuals=())
 
             else:
                 break
diff --git a/lib/spack/spack/provider_index.py b/lib/spack/spack/provider_index.py
index 6de661a02a..33a13eeeee 100644
--- a/lib/spack/spack/provider_index.py
+++ b/lib/spack/spack/provider_index.py
@@ -292,8 +292,8 @@ class ProviderIndex(_IndexBase):
         index.providers = _transform(
             providers,
             lambda vpkg, plist: (
-                spack.spec.SpecfileV3.from_node_dict(vpkg),
-                set(spack.spec.SpecfileV3.from_node_dict(p) for p in plist),
+                spack.spec.SpecfileV4.from_node_dict(vpkg),
+                set(spack.spec.SpecfileV4.from_node_dict(p) for p in plist),
             ),
         )
         return index
diff --git a/lib/spack/spack/solver/asp.py b/lib/spack/spack/solver/asp.py
index 90849aaf8f..d8d058b7f0 100644
--- a/lib/spack/spack/solver/asp.py
+++ b/lib/spack/spack/solver/asp.py
@@ -2500,10 +2500,15 @@ class SpecBuilder(object):
         assert len(dependencies) < 2, msg
 
         if not dependencies:
-            self._specs[pkg].add_dependency_edge(self._specs[dep], deptypes=(type,))
+            self._specs[pkg].add_dependency_edge(self._specs[dep], deptypes=(type,), virtuals=())
         else:
             # TODO: This assumes that each solve unifies dependencies
-            dependencies[0].add_type(type)
+            dependencies[0].update_deptypes(deptypes=(type,))
+
+    def virtual_on_edge(self, pkg, provider, virtual):
+        dependencies = self._specs[pkg].edges_to_dependencies(name=provider)
+        assert len(dependencies) == 1
+        dependencies[0].update_virtuals((virtual,))
 
     def reorder_flags(self):
         """Order compiler flags on specs in predefined order.
@@ -2581,6 +2586,8 @@ class SpecBuilder(object):
             return (-2, 0)
         elif name == "external_spec_selected":
             return (0, 0)  # note out of order so this goes last
+        elif name == "virtual_on_edge":
+            return (1, 0)
         else:
             return (-1, 0)
 
diff --git a/lib/spack/spack/solver/concretize.lp b/lib/spack/spack/solver/concretize.lp
index 0821b68f72..f90aa872f8 100644
--- a/lib/spack/spack/solver/concretize.lp
+++ b/lib/spack/spack/solver/concretize.lp
@@ -300,6 +300,11 @@ attr("depends_on", Package, Provider, Type)
      provider(Provider, Virtual),
      not external(Package).
 
+attr("virtual_on_edge", Package, Provider, Virtual)
+  :- dependency_holds(Package, Virtual, Type),
+     provider(Provider, Virtual),
+     not external(Package).
+
 % dependencies on virtuals also imply that the virtual is a virtual node
 attr("virtual_node", Virtual)
   :- dependency_holds(Package, Virtual, Type),
diff --git a/lib/spack/spack/spec.py b/lib/spack/spack/spec.py
index e29e3b2f85..3e52af1bcc 100644
--- a/lib/spack/spack/spec.py
+++ b/lib/spack/spack/spec.py
@@ -170,7 +170,7 @@ CLEARSIGN_FILE_REGEX = re.compile(
 )
 
 #: specfile format version. Must increase monotonically
-SPECFILE_FORMAT_VERSION = 3
+SPECFILE_FORMAT_VERSION = 4
 
 
 def colorize_spec(spec):
@@ -714,47 +714,81 @@ class DependencySpec:
         parent: starting node of the edge
         spec: ending node of the edge.
         deptypes: list of strings, representing dependency relationships.
+        virtuals: virtual packages provided from child to parent node.
     """
 
-    __slots__ = "parent", "spec", "deptypes"
+    __slots__ = "parent", "spec", "parameters"
 
-    def __init__(self, parent: "Spec", spec: "Spec", *, deptypes: dp.DependencyArgument):
+    def __init__(
+        self,
+        parent: "Spec",
+        spec: "Spec",
+        *,
+        deptypes: dp.DependencyArgument,
+        virtuals: Tuple[str, ...],
+    ):
         self.parent = parent
         self.spec = spec
-        self.deptypes = dp.canonical_deptype(deptypes)
+        self.parameters = {
+            "deptypes": dp.canonical_deptype(deptypes),
+            "virtuals": tuple(sorted(set(virtuals))),
+        }
 
-    def update_deptypes(self, deptypes: dp.DependencyArgument) -> bool:
-        deptypes = set(deptypes)
-        deptypes.update(self.deptypes)
-        deptypes = tuple(sorted(deptypes))
-        changed = self.deptypes != deptypes
+    @property
+    def deptypes(self) -> Tuple[str, ...]:
+        return self.parameters["deptypes"]
 
-        self.deptypes = deptypes
-        return changed
+    @property
+    def virtuals(self) -> Tuple[str, ...]:
+        return self.parameters["virtuals"]
+
+    def _update_edge_multivalued_property(
+        self, property_name: str, value: Tuple[str, ...]
+    ) -> bool:
+        current = self.parameters[property_name]
+        update = set(current) | set(value)
+        update = tuple(sorted(update))
+        changed = current != update
+
+        if not changed:
+            return False
 
-    def copy(self) -> "DependencySpec":
-        return DependencySpec(self.parent, self.spec, deptypes=self.deptypes)
+        self.parameters[property_name] = update
+        return True
+
+    def update_deptypes(self, deptypes: Tuple[str, ...]) -> bool:
+        """Update the current dependency types"""
+        return self._update_edge_multivalued_property("deptypes", deptypes)
 
-    def add_type(self, type: dp.DependencyArgument):
-        self.deptypes = dp.canonical_deptype(self.deptypes + dp.canonical_deptype(type))
+    def update_virtuals(self, virtuals: Tuple[str, ...]) -> bool:
+        """Update the list of provided virtuals"""
+        return self._update_edge_multivalued_property("virtuals", virtuals)
+
+    def copy(self) -> "DependencySpec":
+        """Return a copy of this edge"""
+        return DependencySpec(
+            self.parent, self.spec, deptypes=self.deptypes, virtuals=self.virtuals
+        )
 
     def _cmp_iter(self):
         yield self.parent.name if self.parent else None
         yield self.spec.name if self.spec else None
         yield self.deptypes
+        yield self.virtuals
 
     def __str__(self) -> str:
-        return "%s %s--> %s" % (
-            self.parent.name if self.parent else None,
-            self.deptypes,
-            self.spec.name if self.spec else None,
-        )
+        parent = self.parent.name if self.parent else None
+        child = self.spec.name if self.spec else None
+        return f"{parent} {self.deptypes}[virtuals={','.join(self.virtuals)}] --> {child}"
 
-    def canonical(self) -> Tuple[str, str, Tuple[str, ...]]:
-        return self.parent.dag_hash(), self.spec.dag_hash(), self.deptypes
+    def canonical(self) -> Tuple[str, str, Tuple[str, ...], Tuple[str, ...]]:
+        return self.parent.dag_hash(), self.spec.dag_hash(), self.deptypes, self.virtuals
 
     def flip(self) -> "DependencySpec":
-        return DependencySpec(parent=self.spec, spec=self.parent, deptypes=self.deptypes)
+        """Flip the dependency, and drop virtual information"""
+        return DependencySpec(
+            parent=self.spec, spec=self.parent, deptypes=self.deptypes, virtuals=()
+        )
 
 
 class CompilerFlag(str):
@@ -1575,10 +1609,12 @@ class Spec(object):
             )
         self.compiler = compiler
 
-    def _add_dependency(self, spec: "Spec", *, deptypes: dp.DependencyArgument):
+    def _add_dependency(
+        self, spec: "Spec", *, deptypes: dp.DependencyArgument, virtuals: Tuple[str, ...]
+    ):
         """Called by the parser to add another spec as a dependency."""
         if spec.name not in self._dependencies or not spec.name:
-            self.add_dependency_edge(spec, deptypes=deptypes)
+            self.add_dependency_edge(spec, deptypes=deptypes, virtuals=virtuals)
             return
 
         # Keep the intersection of constraints when a dependency is added
@@ -1596,34 +1632,58 @@ class Spec(object):
                 "Cannot depend on incompatible specs '%s' and '%s'" % (dspec.spec, spec)
             )
 
-    def add_dependency_edge(self, dependency_spec: "Spec", *, deptypes: dp.DependencyArgument):
+    def add_dependency_edge(
+        self,
+        dependency_spec: "Spec",
+        *,
+        deptypes: dp.DependencyArgument,
+        virtuals: Tuple[str, ...],
+    ):
         """Add a dependency edge to this spec.
 
         Args:
             dependency_spec: spec of the dependency
             deptypes: dependency types for this edge
+            virtuals: virtuals provided by this edge
         """
         deptypes = dp.canonical_deptype(deptypes)
 
         # Check if we need to update edges that are already present
         selected = self._dependencies.select(child=dependency_spec.name)
         for edge in selected:
+            has_errors, details = False, []
+            msg = f"cannot update the edge from {edge.parent.name} to {edge.spec.name}"
             if any(d in edge.deptypes for d in deptypes):
-                msg = (
-                    'cannot add a dependency on "{0.spec}" of {1} type '
-                    'when the "{0.parent}" has the edge {0!s} already'
+                has_errors = True
+                details.append(
+                    (
+                        f"{edge.parent.name} has already an edge matching any"
+                        f" of these types {str(deptypes)}"
+                    )
+                )
+
+            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 {str(virtuals)}"
+                    )
                 )
-                raise spack.error.SpecError(msg.format(edge, deptypes))
+
+            if has_errors:
+                raise spack.error.SpecError(msg, "\n".join(details))
 
         for edge in selected:
             if id(dependency_spec) == id(edge.spec):
                 # If we are here, it means the edge object was previously added to
                 # both the parent and the child. When we update this object they'll
                 # both see the deptype modification.
-                edge.add_type(deptypes)
+                edge.update_deptypes(deptypes=deptypes)
+                edge.update_virtuals(virtuals=virtuals)
                 return
 
-        edge = DependencySpec(self, dependency_spec, deptypes=deptypes)
+        edge = DependencySpec(self, dependency_spec, deptypes=deptypes, virtuals=virtuals)
         self._dependencies.add(edge)
         dependency_spec._dependents.add(edge)
 
@@ -1896,12 +1956,12 @@ class Spec(object):
         for node in self.traverse(root=False):
             if node.abstract_hash:
                 new = node._lookup_hash()
-                spec._add_dependency(new, deptypes=())
+                spec._add_dependency(new, deptypes=(), virtuals=())
 
         # reattach nodes that were not otherwise satisfied by new dependencies
         for node in self.traverse(root=False):
             if not any(n._satisfies(node) for n in spec.traverse()):
-                spec._add_dependency(node.copy(), deptypes=())
+                spec._add_dependency(node.copy(), deptypes=(), virtuals=())
 
         return spec
 
@@ -2036,8 +2096,14 @@ class Spec(object):
                 name_tuple = ("name", name)
                 for dspec in edges_for_name:
                     hash_tuple = (hash.name, dspec.spec._cached_hash(hash))
-                    type_tuple = ("type", sorted(str(s) for s in dspec.deptypes))
-                    deps_list.append(syaml.syaml_dict([name_tuple, hash_tuple, type_tuple]))
+                    parameters_tuple = (
+                        "parameters",
+                        syaml.syaml_dict(
+                            (key, dspec.parameters[key]) for key in sorted(dspec.parameters)
+                        ),
+                    )
+                    ordered_entries = [name_tuple, hash_tuple, parameters_tuple]
+                    deps_list.append(syaml.syaml_dict(ordered_entries))
             d["dependencies"] = deps_list
 
         # Name is included in case this is replacing a virtual.
@@ -2361,7 +2427,7 @@ class Spec(object):
                     dag_node, dependency_types = spec_and_dependency_types(s)
 
                 dependency_spec = spec_builder({dag_node: s_dependencies})
-                spec._add_dependency(dependency_spec, deptypes=dependency_types)
+                spec._add_dependency(dependency_spec, deptypes=dependency_types, virtuals=())
 
             return spec
 
@@ -2379,8 +2445,10 @@ class Spec(object):
             spec = SpecfileV1.load(data)
         elif int(data["spec"]["_meta"]["version"]) == 2:
             spec = SpecfileV2.load(data)
-        else:
+        elif int(data["spec"]["_meta"]["version"]) == 3:
             spec = SpecfileV3.load(data)
+        else:
+            spec = SpecfileV4.load(data)
 
         # Any git version should
         for s in spec.traverse():
@@ -2529,6 +2597,7 @@ class Spec(object):
     def _replace_with(self, concrete):
         """Replace this virtual spec with a concrete spec."""
         assert self.virtual
+        virtuals = (self.name,)
         for dep_spec in itertools.chain.from_iterable(self._dependents.values()):
             dependent = dep_spec.parent
             deptypes = dep_spec.deptypes
@@ -2539,7 +2608,11 @@ class Spec(object):
 
             # add the replacement, unless it is already a dep of dependent.
             if concrete.name not in dependent._dependencies:
-                dependent._add_dependency(concrete, deptypes=deptypes)
+                dependent._add_dependency(concrete, deptypes=deptypes, virtuals=virtuals)
+            else:
+                dependent.edges_to_dependencies(name=concrete.name)[0].update_virtuals(
+                    virtuals=virtuals
+                )
 
     def _expand_virtual_packages(self, concretizer):
         """Find virtual packages in this spec, replace them with providers,
@@ -3180,7 +3253,9 @@ class Spec(object):
 
         # If it's a virtual dependency, try to find an existing
         # provider in the spec, and merge that.
+        virtuals = ()
         if spack.repo.path.is_virtual_safe(dep.name):
+            virtuals = (dep.name,)
             visited.add(dep.name)
             provider = self._find_provider(dep, provider_index)
             if provider:
@@ -3236,7 +3311,7 @@ class Spec(object):
         # Add merged spec to my deps and recurse
         spec_dependency = spec_deps[dep.name]
         if dep.name not in self._dependencies:
-            self._add_dependency(spec_dependency, deptypes=dependency.type)
+            self._add_dependency(spec_dependency, deptypes=dependency.type, virtuals=virtuals)
 
         changed |= spec_dependency._normalize_helper(visited, spec_deps, provider_index, tests)
         return changed
@@ -3573,15 +3648,20 @@ class Spec(object):
                 changed |= edges_from_name[0].update_deptypes(
                     other._dependencies[name][0].deptypes
                 )
+                changed |= edges_from_name[0].update_virtuals(
+                    other._dependencies[name][0].virtuals
+                )
 
         # Update with additional constraints from other spec
         # operate on direct dependencies only, because a concrete dep
         # represented by hash may have structure that needs to be preserved
         for name in other.direct_dep_difference(self):
             dep_spec_copy = other._get_dependency(name)
-            dep_copy = dep_spec_copy.spec
-            deptypes = dep_spec_copy.deptypes
-            self._add_dependency(dep_copy.copy(), deptypes=deptypes)
+            self._add_dependency(
+                dep_spec_copy.spec.copy(),
+                deptypes=dep_spec_copy.deptypes,
+                virtuals=dep_spec_copy.virtuals,
+            )
             changed = True
 
         return changed
@@ -3965,7 +4045,7 @@ class Spec(object):
                 new_specs[spid(edge.spec)] = edge.spec.copy(deps=False)
 
             new_specs[spid(edge.parent)].add_dependency_edge(
-                new_specs[spid(edge.spec)], deptypes=edge.deptypes
+                new_specs[spid(edge.spec)], deptypes=edge.deptypes, virtuals=edge.virtuals
             )
 
     def copy(self, deps=True, **kwargs):
@@ -4635,12 +4715,16 @@ class Spec(object):
             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], deptypes=edge.deptypes)
+                    nodes[name].add_dependency_edge(
+                        nodes[dep_name], deptypes=edge.deptypes, 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], deptypes=edge.deptypes)
+                    nodes[name].add_dependency_edge(
+                        nodes[edge.spec.name], deptypes=edge.deptypes, virtuals=edge.virtuals
+                    )
                 if any(dep not in other_nodes for dep in other[name]._dependencies):
                     nodes[name].build_spec = other[name].build_spec
 
@@ -4730,11 +4814,40 @@ def merge_abstract_anonymous_specs(*abstract_specs: Spec):
         # Update with additional constraints from other spec
         for name in current_spec_constraint.direct_dep_difference(merged_spec):
             edge = next(iter(current_spec_constraint.edges_to_dependencies(name)))
-            merged_spec._add_dependency(edge.spec.copy(), deptypes=edge.deptypes)
+            merged_spec._add_dependency(
+                edge.spec.copy(), deptypes=edge.deptypes, virtuals=edge.virtuals
+            )
 
     return merged_spec
 
 
+def reconstruct_virtuals_on_edges(spec):
+    """Reconstruct virtuals on edges. Used to read from old DB and reindex.
+
+    Args:
+        spec: spec on which we want to reconstruct virtuals
+    """
+    # Collect all possible virtuals
+    possible_virtuals = set()
+    for node in spec.traverse():
+        try:
+            possible_virtuals.update({x for x in node.package.dependencies if Spec(x).virtual})
+        except Exception as e:
+            warnings.warn(f"cannot reconstruct virtual dependencies on package {node.name}: {e}")
+            continue
+
+    # Assume all incoming edges to provider are marked with virtuals=
+    for vspec in possible_virtuals:
+        try:
+            provider = spec[vspec]
+        except KeyError:
+            # Virtual not in the DAG
+            continue
+
+        for edge in provider.edges_from_dependents():
+            edge.update_virtuals([vspec])
+
+
 class SpecfileReaderBase:
     @classmethod
     def from_node_dict(cls, node):
@@ -4818,7 +4931,7 @@ class SpecfileReaderBase:
 
         # Pass 0: Determine hash type
         for node in nodes:
-            for _, _, _, dhash_type in cls.dependencies_from_node_dict(node):
+            for _, _, _, dhash_type, _ in cls.dependencies_from_node_dict(node):
                 any_deps = True
                 if dhash_type:
                     hash_type = dhash_type
@@ -4849,8 +4962,10 @@ class SpecfileReaderBase:
         # Pass 2: Finish construction of all DAG edges (including build specs)
         for node_hash, node in hash_dict.items():
             node_spec = node["node_spec"]
-            for _, dhash, dtypes, _ in cls.dependencies_from_node_dict(node):
-                node_spec._add_dependency(hash_dict[dhash]["node_spec"], deptypes=dtypes)
+            for _, dhash, dtypes, _, virtuals in cls.dependencies_from_node_dict(node):
+                node_spec._add_dependency(
+                    hash_dict[dhash]["node_spec"], deptypes=dtypes, virtuals=virtuals
+                )
             if "build_spec" in node.keys():
                 _, bhash, _ = cls.build_spec_from_node_dict(node, hash_type=hash_type)
                 node_spec._build_spec = hash_dict[bhash]["node_spec"]
@@ -4884,9 +4999,10 @@ class SpecfileV1(SpecfileReaderBase):
         for node in nodes:
             # get dependency dict from the node.
             name, data = cls.name_and_data(node)
-            for dname, _, dtypes, _ in cls.dependencies_from_node_dict(data):
-                deps[name]._add_dependency(deps[dname], deptypes=dtypes)
+            for dname, _, dtypes, _, virtuals in cls.dependencies_from_node_dict(data):
+                deps[name]._add_dependency(deps[dname], deptypes=dtypes, virtuals=virtuals)
 
+        reconstruct_virtuals_on_edges(result)
         return result
 
     @classmethod
@@ -4915,18 +5031,20 @@ class SpecfileV1(SpecfileReaderBase):
                     if h.name in elt:
                         dep_hash, deptypes = elt[h.name], elt["type"]
                         hash_type = h.name
+                        virtuals = []
                         break
                 else:  # We never determined a hash type...
                     raise spack.error.SpecError("Couldn't parse dependency spec.")
             else:
                 raise spack.error.SpecError("Couldn't parse dependency types in spec.")
-            yield dep_name, dep_hash, list(deptypes), hash_type
+            yield dep_name, dep_hash, list(deptypes), hash_type, list(virtuals)
 
 
 class SpecfileV2(SpecfileReaderBase):
     @classmethod
     def load(cls, data):
         result = cls._load(data)
+        reconstruct_virtuals_on_edges(result)
         return result
 
     @classmethod
@@ -4960,7 +5078,7 @@ class SpecfileV2(SpecfileReaderBase):
                     raise spack.error.SpecError("Couldn't parse dependency spec.")
             else:
                 raise spack.error.SpecError("Couldn't parse dependency types in spec.")
-            result.append((dep_name, dep_hash, list(deptypes), hash_type))
+            result.append((dep_name, dep_hash, list(deptypes), hash_type, list(virtuals)))
         return result
 
     @classmethod
@@ -4980,6 +5098,20 @@ class SpecfileV3(SpecfileV2):
     pass
 
 
+class SpecfileV4(SpecfileV2):
+    @classmethod
+    def extract_info_from_dep(cls, elt, hash):
+        dep_hash = elt[hash.name]
+        deptypes = elt["parameters"]["deptypes"]
+        hash_type = hash.name
+        virtuals = elt["parameters"]["virtuals"]
+        return dep_hash, deptypes, hash_type, virtuals
+
+    @classmethod
+    def load(cls, data):
+        return cls._load(data)
+
+
 class LazySpecCache(collections.defaultdict):
     """Cache for Specs that uses a spec_like as key, and computes lazily
     the corresponding value ``Spec(spec_like``.
diff --git a/lib/spack/spack/test/concretize.py b/lib/spack/spack/test/concretize.py
index f1b4ceba6a..69af2d7f8f 100644
--- a/lib/spack/spack/test/concretize.py
+++ b/lib/spack/spack/test/concretize.py
@@ -2170,3 +2170,14 @@ class TestConcretize(object):
         with spack.config.override("compilers", compiler_configuration):
             s = spack.spec.Spec("a").concretized()
         assert s.satisfies("%gcc@12.1.0")
+
+    @pytest.mark.parametrize("spec_str", ["mpileaks", "mpileaks ^mpich"])
+    def test_virtuals_are_annotated_on_edges(self, spec_str, default_mock_concretization):
+        """Tests that information on virtuals is annotated on DAG edges"""
+        spec = default_mock_concretization(spec_str)
+        mpi_provider = spec["mpi"].name
+
+        edges = spec.edges_to_dependencies(name=mpi_provider)
+        assert len(edges) == 1 and edges[0].virtuals == ("mpi",)
+        edges = spec.edges_to_dependencies(name="callpath")
+        assert len(edges) == 1 and edges[0].virtuals == ()
diff --git a/lib/spack/spack/test/data/specfiles/hdf5.v020.json.gz b/lib/spack/spack/test/data/specfiles/hdf5.v020.json.gz
new file mode 100644
index 0000000000..3b2fa4d830
--- /dev/null
+++ b/lib/spack/spack/test/data/specfiles/hdf5.v020.json.gz
diff --git a/lib/spack/spack/test/spec_dag.py b/lib/spack/spack/test/spec_dag.py
index 177deba6c2..4071a74722 100644
--- a/lib/spack/spack/test/spec_dag.py
+++ b/lib/spack/spack/test/spec_dag.py
@@ -125,7 +125,7 @@ def test_installed_deps(monkeypatch, mock_packages):
     # use the installed C.  It should *not* force A to use the installed D
     # *if* we're doing a fresh installation.
     a_spec = Spec(a)
-    a_spec._add_dependency(c_spec, deptypes=("build", "link"))
+    a_spec._add_dependency(c_spec, deptypes=("build", "link"), virtuals=())
     a_spec.concretize()
     assert spack.version.Version("2") == a_spec[c][d].version
     assert spack.version.Version("2") == a_spec[e].version
@@ -148,7 +148,7 @@ def test_specify_preinstalled_dep(tmpdir, monkeypatch):
         monkeypatch.setattr(Spec, "installed", property(lambda x: x.name != "a"))
 
         a_spec = Spec("a")
-        a_spec._add_dependency(b_spec, deptypes=("build", "link"))
+        a_spec._add_dependency(b_spec, deptypes=("build", "link"), virtuals=())
         a_spec.concretize()
 
         assert set(x.name for x in a_spec.traverse()) == set(["a", "b", "c"])
@@ -989,9 +989,9 @@ def test_synthetic_construction_of_split_dependencies_from_same_package(mock_pac
     link_run_spec = Spec("c@=1.0").concretized()
     build_spec = Spec("c@=2.0").concretized()
 
-    root.add_dependency_edge(link_run_spec, deptypes="link")
-    root.add_dependency_edge(link_run_spec, deptypes="run")
-    root.add_dependency_edge(build_spec, deptypes="build")
+    root.add_dependency_edge(link_run_spec, deptypes="link", virtuals=())
+    root.add_dependency_edge(link_run_spec, deptypes="run", virtuals=())
+    root.add_dependency_edge(build_spec, deptypes="build", virtuals=())
 
     # Check dependencies from the perspective of root
     assert len(root.dependencies()) == 2
@@ -1017,7 +1017,7 @@ def test_synthetic_construction_bootstrapping(mock_packages, config):
     root = Spec("b@=2.0").concretized()
     bootstrap = Spec("b@=1.0").concretized()
 
-    root.add_dependency_edge(bootstrap, deptypes="build")
+    root.add_dependency_edge(bootstrap, deptypes="build", virtuals=())
 
     assert len(root.dependencies()) == 1
     assert root.dependencies()[0].name == "b"
@@ -1036,7 +1036,7 @@ def test_addition_of_different_deptypes_in_multiple_calls(mock_packages, config)
     bootstrap = Spec("b@=1.0").concretized()
 
     for current_deptype in ("build", "link", "run"):
-        root.add_dependency_edge(bootstrap, deptypes=current_deptype)
+        root.add_dependency_edge(bootstrap, deptypes=current_deptype, virtuals=())
 
         # Check edges in dependencies
         assert len(root.edges_to_dependencies()) == 1
@@ -1063,9 +1063,9 @@ def test_adding_same_deptype_with_the_same_name_raises(
     c1 = Spec("b@=1.0").concretized()
     c2 = Spec("b@=2.0").concretized()
 
-    p.add_dependency_edge(c1, deptypes=c1_deptypes)
+    p.add_dependency_edge(c1, deptypes=c1_deptypes, virtuals=())
     with pytest.raises(spack.error.SpackError):
-        p.add_dependency_edge(c2, deptypes=c2_deptypes)
+        p.add_dependency_edge(c2, deptypes=c2_deptypes, virtuals=())
 
 
 @pytest.mark.regression("33499")
@@ -1084,16 +1084,16 @@ def test_indexing_prefers_direct_or_transitive_link_deps():
     z3_flavor_1 = Spec("z3 +through_a1")
     z3_flavor_2 = Spec("z3 +through_z1")
 
-    root.add_dependency_edge(a1, deptypes=("build", "run", "test"))
+    root.add_dependency_edge(a1, deptypes=("build", "run", "test"), virtuals=())
 
     # unique package as a dep of a build/run/test type dep.
-    a1.add_dependency_edge(a2, deptypes="all")
-    a1.add_dependency_edge(z3_flavor_1, deptypes="all")
+    a1.add_dependency_edge(a2, deptypes="all", virtuals=())
+    a1.add_dependency_edge(z3_flavor_1, deptypes="all", virtuals=())
 
     # chain of link type deps root -> z1 -> z2 -> z3
-    root.add_dependency_edge(z1, deptypes="link")
-    z1.add_dependency_edge(z2, deptypes="link")
-    z2.add_dependency_edge(z3_flavor_2, deptypes="link")
+    root.add_dependency_edge(z1, deptypes="link", virtuals=())
+    z1.add_dependency_edge(z2, deptypes="link", virtuals=())
+    z2.add_dependency_edge(z3_flavor_2, deptypes="link", virtuals=())
 
     # Indexing should prefer the link-type dep.
     assert "through_z1" in root["z3"].variants
diff --git a/lib/spack/spack/test/spec_semantics.py b/lib/spack/spack/test/spec_semantics.py
index 1a6a08b41e..076f24dfa5 100644
--- a/lib/spack/spack/test/spec_semantics.py
+++ b/lib/spack/spack/test/spec_semantics.py
@@ -971,7 +971,7 @@ class TestSpecSemantics(object):
     def test_satisfies_dependencies_ordered(self):
         d = Spec("zmpi ^fake")
         s = Spec("mpileaks")
-        s._add_dependency(d, deptypes=())
+        s._add_dependency(d, deptypes=(), virtuals=())
         assert s.satisfies("mpileaks ^zmpi ^fake")
 
     @pytest.mark.parametrize("transitive", [True, False])
@@ -1018,6 +1018,7 @@ def test_is_extension_after_round_trip_to_dict(config, mock_packages, spec_str):
 
 
 def test_malformed_spec_dict():
+    # FIXME: This test was really testing the specific implementation with an ad-hoc test
     with pytest.raises(SpecError, match="malformed"):
         Spec.from_dict(
             {"spec": {"_meta": {"version": 2}, "nodes": [{"dependencies": {"name": "foo"}}]}}
@@ -1025,6 +1026,7 @@ def test_malformed_spec_dict():
 
 
 def test_spec_dict_hashless_dep():
+    # FIXME: This test was really testing the specific implementation with an ad-hoc test
     with pytest.raises(SpecError, match="Couldn't parse"):
         Spec.from_dict(
             {
@@ -1118,7 +1120,7 @@ def test_concretize_partial_old_dag_hash_spec(mock_packages, config):
 
     # add it to an abstract spec as a dependency
     top = Spec("dt-diamond")
-    top.add_dependency_edge(bottom, deptypes=())
+    top.add_dependency_edge(bottom, deptypes=(), virtuals=())
 
     # concretize with the already-concrete dependency
     top.concretize()
diff --git a/lib/spack/spack/test/spec_yaml.py b/lib/spack/spack/test/spec_yaml.py
index a9d850a890..b6c72ce76e 100644
--- a/lib/spack/spack/test/spec_yaml.py
+++ b/lib/spack/spack/test/spec_yaml.py
@@ -43,12 +43,6 @@ def check_json_round_trip(spec):
     assert spec.eq_dag(spec_from_json)
 
 
-def test_simple_spec():
-    spec = Spec("mpileaks")
-    check_yaml_round_trip(spec)
-    check_json_round_trip(spec)
-
-
 def test_read_spec_from_signed_json():
     spec_dir = os.path.join(spack.paths.test_path, "data", "mirrors", "signed_json")
     file_name = (
@@ -70,13 +64,6 @@ def test_read_spec_from_signed_json():
         check_spec(s)
 
 
-def test_normal_spec(mock_packages):
-    spec = Spec("mpileaks+debug~opt")
-    spec.normalize()
-    check_yaml_round_trip(spec)
-    check_json_round_trip(spec)
-
-
 @pytest.mark.parametrize(
     "invalid_yaml", ["playing_playlist: {{ action }} playlist {{ playlist_name }}"]
 )
@@ -95,37 +82,28 @@ def test_invalid_json_spec(invalid_json, error_message):
     assert error_message in exc_msg
 
 
-def test_external_spec(config, mock_packages):
-    spec = Spec("externaltool")
-    spec.concretize()
-    check_yaml_round_trip(spec)
-    check_json_round_trip(spec)
-
-    spec = Spec("externaltest")
-    spec.concretize()
-    check_yaml_round_trip(spec)
-    check_json_round_trip(spec)
-
-
-def test_ambiguous_version_spec(mock_packages):
-    spec = Spec("mpileaks@1.0:5.0,6.1,7.3+debug~opt")
-    spec.normalize()
-    check_yaml_round_trip(spec)
-    check_json_round_trip(spec)
-
-
-def test_concrete_spec(config, mock_packages):
-    spec = Spec("mpileaks+debug~opt")
-    spec.concretize()
-    check_yaml_round_trip(spec)
-    check_json_round_trip(spec)
-
-
-def test_yaml_multivalue(config, mock_packages):
-    spec = Spec('multivalue-variant foo="bar,baz"')
-    spec.concretize()
-    check_yaml_round_trip(spec)
-    check_json_round_trip(spec)
+@pytest.mark.parametrize(
+    "abstract_spec",
+    [
+        # Externals
+        "externaltool",
+        "externaltest",
+        # Ambiguous version spec
+        "mpileaks@1.0:5.0,6.1,7.3+debug~opt",
+        # Variants
+        "mpileaks+debug~opt",
+        'multivalue-variant foo="bar,baz"',
+        # Virtuals on edges
+        "callpath",
+        "mpileaks",
+    ],
+)
+def test_roundtrip_concrete_specs(abstract_spec, default_mock_concretization):
+    check_yaml_round_trip(Spec(abstract_spec))
+    check_json_round_trip(Spec(abstract_spec))
+    concrete_spec = default_mock_concretization(abstract_spec)
+    check_yaml_round_trip(concrete_spec)
+    check_json_round_trip(concrete_spec)
 
 
 def test_yaml_subdag(config, mock_packages):
@@ -506,6 +484,8 @@ ordered_spec = collections.OrderedDict(
         ("specfiles/hdf5.v017.json.gz", "xqh5iyjjtrp2jw632cchacn3l7vqzf3m", spack.spec.SpecfileV2),
         # Use "full hash" everywhere, see https://github.com/spack/spack/pull/28504
         ("specfiles/hdf5.v019.json.gz", "iulacrbz7o5v5sbj7njbkyank3juh6d3", spack.spec.SpecfileV3),
+        # Add properties on edges, see https://github.com/spack/spack/pull/34821
+        ("specfiles/hdf5.v020.json.gz", "vlirlcgazhvsvtundz4kug75xkkqqgou", spack.spec.SpecfileV4),
     ],
 )
 def test_load_json_specfiles(specfile, expected_hash, reader_cls):
diff --git a/lib/spack/spack/test/traverse.py b/lib/spack/spack/test/traverse.py
index dae944ffc3..2d9679d6ce 100644
--- a/lib/spack/spack/test/traverse.py
+++ b/lib/spack/spack/test/traverse.py
@@ -19,7 +19,7 @@ def create_dag(nodes, edges):
     """
     specs = {name: Spec(name) for name in nodes}
     for parent, child, deptypes in edges:
-        specs[parent].add_dependency_edge(specs[child], deptypes=deptypes)
+        specs[parent].add_dependency_edge(specs[child], deptypes=deptypes, virtuals=())
     return specs
 
 
diff --git a/lib/spack/spack/traverse.py b/lib/spack/spack/traverse.py
index 9690191aab..f3eb70416d 100644
--- a/lib/spack/spack/traverse.py
+++ b/lib/spack/spack/traverse.py
@@ -211,7 +211,9 @@ def get_visitor_from_args(cover, direction, deptype, key=id, visited=None, visit
 def with_artificial_edges(specs):
     """Initialize a list of edges from an imaginary root node to the root specs."""
     return [
-        EdgeAndDepth(edge=spack.spec.DependencySpec(parent=None, spec=s, deptypes=()), depth=0)
+        EdgeAndDepth(
+            edge=spack.spec.DependencySpec(parent=None, spec=s, deptypes=(), virtuals=()), depth=0
+        )
         for s in specs
     ]