Feature: Allow variants to propagate if not available in source pkg (#42931)

Variants can now be propagated from a dependent package to (transitive) dependencies, 
even if the source or transitive dependencies have the propagated variants.

For example, here `zlib` doesn't have a `guile` variant, but `gmake` does:
```
$ spack spec zlib++guile
 -   zlib@1.3%gcc@12.2.0+optimize+pic+shared build_system=makefile arch=linux-rhel8-broadwell
 -       ^gcc-runtime@12.2.0%gcc@12.2.0 build_system=generic arch=linux-rhel8-broadwell
 -       ^gmake@4.4.1%gcc@12.2.0+guile build_system=generic arch=linux-rhel8-broadwell
```

Adding this property has some strange ramifications for `satisfies()`. In particular:
* The abstract specs `pkg++variant` and `pkg+variant`  do not intersect, because `+variant`
  implies that `pkg` *has* the variant, but `++variant` does not.
* This means that `spec.satisfies("++foo")` is `True` if:
    * for concrete specs: `spec` and its dependencies all have `foo` set if it exists
    * for abstract specs: no dependency of `spec`  has `~foo` (i.e. no dependency contradicts `++foo`).
* This also means that `Spec("++foo").satisfies("+foo")` is `False` -- we only know after concretization.

The `satisfies()` semantics may be surprising, but this is the cost of introducing non-subset
semantics (which are more useful than proper subsets here).

- [x] Change checks for variants
- [x] Resolve conflicts
- [x] Add tests
- [x] Add documentation

---------

Co-authored-by: Gregory Becker <becker33@llnl.gov>
Co-authored-by: Massimiliano Culpo <massimiliano.culpo@gmail.com>

7 files changed, 332 insertions, 35 deletions

diff --git a/lib/spack/docs/basic_usage.rst b/lib/spack/docs/basic_usage.rst
index 171a82b6ea..21733a2566 100644
--- a/lib/spack/docs/basic_usage.rst
+++ b/lib/spack/docs/basic_usage.rst
@@ -1359,6 +1359,10 @@ For example, for the ``stackstart`` variant:
     mpileaks stackstart==4   # variant will be propagated to dependencies
     mpileaks stackstart=4    # only mpileaks will have this variant value
 
+Spack also allows variants to be propagated from a package that does
+not have that variant.
+
+
 ^^^^^^^^^^^^^^
 Compiler Flags
 ^^^^^^^^^^^^^^
diff --git a/lib/spack/spack/solver/asp.py b/lib/spack/spack/solver/asp.py
index cb4799a45f..56014717dd 100644
--- a/lib/spack/spack/solver/asp.py
+++ b/lib/spack/spack/solver/asp.py
@@ -2032,9 +2032,12 @@ class SpackSolverSetup:
                     for variant_def in variant_defs:
                         self.variant_values_from_specs.add((spec.name, id(variant_def), value))
 
-                clauses.append(f.variant_value(spec.name, vname, value))
                 if variant.propagate:
                     clauses.append(f.propagate(spec.name, fn.variant_value(vname, value)))
+                    if self.pkg_class(spec.name).has_variant(vname):
+                        clauses.append(f.variant_value(spec.name, vname, value))
+                else:
+                    clauses.append(f.variant_value(spec.name, vname, value))
 
         # compiler and compiler version
         if spec.compiler:
diff --git a/lib/spack/spack/solver/concretize.lp b/lib/spack/spack/solver/concretize.lp
index 2195cd6b08..f4695be9b9 100644
--- a/lib/spack/spack/solver/concretize.lp
+++ b/lib/spack/spack/solver/concretize.lp
@@ -57,6 +57,12 @@
    internal_error("provider with no virtual node").
 :- provider(PackageNode, _), not attr("node", PackageNode),
    internal_error("provider with no real node").
+:- node_has_variant(PackageNode, _, _), not attr("node", PackageNode),
+   internal_error("node has variant for a non-node").
+:- attr("variant_set", PackageNode, _, _), not attr("node", PackageNode),
+   internal_error("variant_set for a non-node").
+:- variant_is_propagated(PackageNode, _), not attr("node", PackageNode),
+   internal_error("variant_is_propagated for a non-node").
 
 :- attr("root", node(ID, PackageNode)), ID > min_dupe_id,
    internal_error("root with a non-minimal duplicate ID").
@@ -575,7 +581,8 @@ attr("virtual_on_edge", PackageNode, ProviderNode, Virtual)
 % or used somewhere
 :- attr("virtual_node", node(_, Virtual)),
    not attr("virtual_on_incoming_edges", _, Virtual),
-   not attr("virtual_root", node(_, Virtual)).
+   not attr("virtual_root", node(_, Virtual)),
+   internal_error("virtual node does not match incoming edge").
 
 attr("virtual_on_incoming_edges", ProviderNode, Virtual)
   :- attr("virtual_on_edge", _, ProviderNode, Virtual).
@@ -629,7 +636,8 @@ do_not_impose(EffectID, node(X, Package))
    virtual_condition_holds(_, PossibleProvider, Virtual),
    PossibleProvider != ProviderNode,
    explicitly_requested_root(PossibleProvider),
-   not explicitly_requested_root(ProviderNode).
+   not explicitly_requested_root(ProviderNode),
+   internal_error("If a root can provide a virtual, it must be the provider").
 
 % A package cannot be the actual provider for a virtual if it does not
 % fulfill the conditions to provide that virtual
@@ -772,7 +780,8 @@ required_provider(Provider, Virtual)
      pkg_fact(Virtual, condition_effect(ConditionID, EffectID)),
      imposed_constraint(EffectID, "node", Provider).
 
-:- provider(node(Y, Package), node(X, Virtual)), required_provider(Provider, Virtual), Package != Provider.
+:- provider(node(Y, Package), node(X, Virtual)), required_provider(Provider, Virtual), Package != Provider,
+   internal_error("If a provider is required the concretizer must use it").
 
 % TODO: the following choice rule allows the solver to add compiler
 % flags if their only source is from a requirement. This is overly-specific
@@ -852,7 +861,8 @@ variant_defined(PackageNode, Name) :- variant_definition(PackageNode, Name, _).
 % for two or more variant definitions, this prefers the last one defined.
 :- node_has_variant(node(NodeID, Package), Name, SelectedVariantID),
    variant_definition(node(NodeID, Package), Name, VariantID),
-   VariantID > SelectedVariantID.
+   VariantID > SelectedVariantID,
+   internal_error("If the solver picks a variant descriptor it must use that variant descriptor").
 
 % B: Associating applicable package rules with nodes
 
@@ -969,6 +979,7 @@ error(100, "{0} variant '{1}' cannot have values '{2}' and '{3}' as they come fr
 
 :- attr("variant_set", node(ID, Package), Variant, Value),
    not attr("variant_value", node(ID, Package), Variant, Value).
+   internal_error("If a variant is set to a value it must have that value").
 
 % The rules below allow us to prefer default values for variants
 % whenever possible. If a variant is set in a spec, or if it is
@@ -979,7 +990,7 @@ variant_not_default(node(ID, Package), Variant, Value)
     % variants set explicitly on the CLI don't count as non-default
     not attr("variant_set", node(ID, Package), Variant, Value),
     % variant values forced by propagation don't count as non-default
-    not propagate(node(ID, Package), variant_value(Variant, Value)),
+    not propagate(node(ID, Package), variant_value(Variant, Value, _)),
     % variants set on externals that we could use don't count as non-default
     % this makes spack prefer to use an external over rebuilding with the
     % default configuration
@@ -991,7 +1002,7 @@ variant_default_not_used(node(ID, Package), Variant, Value)
   :- variant_default_value(node(ID, Package), Variant, Value),
      node_has_variant(node(ID, Package), Variant, _),
      not attr("variant_value", node(ID, Package), Variant, Value),
-     not propagate(node(ID, Package), variant_value(Variant, _)),
+     not propagate(node(ID, Package), variant_value(Variant, _, _)),
      attr("node", node(ID, Package)).
 
 % The variant is set in an external spec
@@ -1036,10 +1047,14 @@ variant_single_value(PackageNode, Variant)
 % Propagation semantics
 %-----------------------------------------------------------------------------
 
+non_default_propagation(variant_value(Name, Value)) :- attr("propagate", RootNode, variant_value(Name, Value)).
+
 % Propagation roots have a corresponding attr("propagate", ...)
-propagate(RootNode, PropagatedAttribute) :- attr("propagate", RootNode, PropagatedAttribute).
+propagate(RootNode, PropagatedAttribute) :- attr("propagate", RootNode, PropagatedAttribute), not non_default_propagation(PropagatedAttribute).
 propagate(RootNode, PropagatedAttribute, EdgeTypes) :- attr("propagate", RootNode, PropagatedAttribute, EdgeTypes).
 
+% Special case variants, to inject the source node in the propagated attribute
+propagate(RootNode, variant_value(Name, Value, RootNode)) :- attr("propagate", RootNode, variant_value(Name, Value)).
 
 % Propagate an attribute along edges to child nodes
 propagate(ChildNode, PropagatedAttribute) :-
@@ -1061,21 +1076,53 @@ propagate(ChildNode, PropagatedAttribute, edge_types(DepType1, DepType2)) :-
 
 % If a variant is propagated, and can be accepted, set its value
 attr("variant_selected", PackageNode, Variant, Value, VariantType, VariantID) :-
-  propagate(PackageNode, variant_value(Variant, Value)),
+  propagate(PackageNode, variant_value(Variant, Value, _)),
   node_has_variant(PackageNode, Variant, VariantID),
   variant_type(VariantID, VariantType),
-  variant_possible_value(PackageNode, Variant, Value),
-  not attr("variant_set", PackageNode, Variant).
+  variant_possible_value(PackageNode, Variant, Value).
 
 % If a variant is propagated, we cannot have extraneous values
 variant_is_propagated(PackageNode, Variant) :-
   attr("variant_value", PackageNode, Variant, Value),
-  propagate(PackageNode, variant_value(Variant, Value)),
+  propagate(PackageNode, variant_value(Variant, Value, _)),
   not attr("variant_set", PackageNode, Variant).
 
 :- variant_is_propagated(PackageNode, Variant),
    attr("variant_selected", PackageNode, Variant, Value, _, _),
-   not propagate(PackageNode, variant_value(Variant, Value)).
+   not propagate(PackageNode, variant_value(Variant, Value, _)).
+
+error(100, "{0} and {1} cannot both propagate variant '{2}' to the shared dependency: {3}",
+  Package1, Package2, Variant, Dependency) :-
+  % The variant is a singlevalued variant
+  variant_single_value(node(X, Package1), Variant),
+  % Dependency is trying to propagate Variant with different values and is not the source package
+  propagate(node(Z, Dependency), variant_value(Variant, Value1, node(X, Package1))),
+  propagate(node(Z, Dependency), variant_value(Variant, Value2, node(Y, Package2))),
+  % Package1 and Package2 and their values are different
+  Package1 > Package2,  Value1 != Value2,
+  not propagate(node(Z, Dependency), variant_value(Variant, _, node(Z, Dependency))).
+
+% Cannot propagate the same variant from two different packages if one is a dependency of the other
+error(100, "{0} and {1} cannot both propagate variant '{2}'", Package1, Package2, Variant) :-
+  % The variant is a single-valued variant
+  variant_single_value(node(X, Package1), Variant),
+  % Package1 and Package2 and their values are different
+  Package1 != Package2,  Value1 != Value2,
+  % Package2 is set to propagate the value from Package1
+  propagate(node(Y, Package2), variant_value(Variant, Value2, node(X, Package2))),
+  propagate(node(Y, Package2), variant_value(Variant, Value1, node(X, Package1))),
+  variant_is_propagated(node(Y, Package2), Variant).
+
+% Cannot propagate a variant if a different value was set for it in a dependency
+error(100, "Cannot propagate the variant '{0}' from the package: {1} because package: {2} is set to exclude it", Variant, Source, Package) :-
+  % Package has a Variant and Source is propagating Variant
+  attr("variant_set", node(X, Package), Variant, Value1),
+  % The packages and values are different
+  Source != Package,  Value1 != Value2,
+  % The variant is a single-valued variant
+  variant_single_value(node(X, Package1), Variant),
+  % A different value is being propagated from somewhere else
+  propagate(node(X, Package), variant_value(Variant, Value2, node(Y, Source))).
 
 %----
 % Flags
diff --git a/lib/spack/spack/spec.py b/lib/spack/spack/spec.py
index ba3a0f9c37..3d92879484 100644
--- a/lib/spack/spack/spec.py
+++ b/lib/spack/spack/spec.py
@@ -3020,7 +3020,12 @@ class Spec:
         pkg_variants = pkg_cls.variant_names()
         # reserved names are variants that may be set on any package
         # but are not necessarily recorded by the package's class
-        not_existing = set(spec.variants) - (set(pkg_variants) | set(vt.reserved_names))
+        propagate_variants = [name for name, variant in spec.variants.items() if variant.propagate]
+
+        not_existing = set(spec.variants) - (
+            set(pkg_variants) | set(vt.reserved_names) | set(propagate_variants)
+        )
+
         if not_existing:
             raise vt.UnknownVariantError(
                 f"No such variant {not_existing} for spec: '{spec}'", list(not_existing)
@@ -3047,6 +3052,10 @@ class Spec:
                 raise spack.error.UnsatisfiableSpecError(self, other, "constrain a concrete spec")
 
         other = self._autospec(other)
+        if other.concrete and other.satisfies(self):
+            self._dup(other)
+            return True
+
         if other.abstract_hash:
             if not self.abstract_hash or other.abstract_hash.startswith(self.abstract_hash):
                 self.abstract_hash = other.abstract_hash
@@ -4525,8 +4534,69 @@ class VariantMap(lang.HashableMap):
         # Set the item
         super().__setitem__(vspec.name, vspec)
 
-    def satisfies(self, other):
-        return all(k in self and self[k].satisfies(other[k]) for k in other)
+    def partition_variants(self):
+        non_prop, prop = lang.stable_partition(self.values(), lambda x: not x.propagate)
+        # Just return the names
+        non_prop = [x.name for x in non_prop]
+        prop = [x.name for x in prop]
+        return non_prop, prop
+
+    def satisfies(self, other: "VariantMap") -> bool:
+        if self.spec.concrete:
+            return self._satisfies_when_self_concrete(other)
+        return self._satisfies_when_self_abstract(other)
+
+    def _satisfies_when_self_concrete(self, other: "VariantMap") -> bool:
+        non_propagating, propagating = other.partition_variants()
+        result = all(
+            name in self and self[name].satisfies(other[name]) for name in non_propagating
+        )
+        if not propagating:
+            return result
+
+        for node in self.spec.traverse():
+            if not all(
+                node.variants[name].satisfies(other[name])
+                for name in propagating
+                if name in node.variants
+            ):
+                return False
+        return result
+
+    def _satisfies_when_self_abstract(self, other: "VariantMap") -> bool:
+        other_non_propagating, other_propagating = other.partition_variants()
+        self_non_propagating, self_propagating = self.partition_variants()
+
+        # First check variants without propagation set
+        result = all(
+            name in self_non_propagating
+            and (self[name].propagate or self[name].satisfies(other[name]))
+            for name in other_non_propagating
+        )
+        if result is False or (not other_propagating and not self_propagating):
+            return result
+
+        # Check that self doesn't contradict variants propagated by other
+        if other_propagating:
+            for node in self.spec.traverse():
+                if not all(
+                    node.variants[name].satisfies(other[name])
+                    for name in other_propagating
+                    if name in node.variants
+                ):
+                    return False
+
+        # Check that other doesn't contradict variants propagated by self
+        if self_propagating:
+            for node in other.spec.traverse():
+                if not all(
+                    node.variants[name].satisfies(self[name])
+                    for name in self_propagating
+                    if name in node.variants
+                ):
+                    return False
+
+        return result
 
     def intersects(self, other):
         return all(self[k].intersects(other[k]) for k in other if k in self)
diff --git a/lib/spack/spack/test/concretize.py b/lib/spack/spack/test/concretize.py
index bf96311d44..dd2444df0a 100644
--- a/lib/spack/spack/test/concretize.py
+++ b/lib/spack/spack/test/concretize.py
@@ -540,21 +540,17 @@ class TestConcretize:
     @pytest.mark.parametrize(
         "spec_str,expected_propagation",
         [
-            ("hypre~~shared ^openblas+shared", [("hypre", "~shared"), ("openblas", "+shared")]),
             # Propagates past a node that doesn't have the variant
             ("hypre~~shared ^openblas", [("hypre", "~shared"), ("openblas", "~shared")]),
+            # Propagates from root node to all nodes
             (
                 "ascent~~shared +adios2",
                 [("ascent", "~shared"), ("adios2", "~shared"), ("bzip2", "~shared")],
             ),
-            # Propagates below a node that uses the other value explicitly
+            # Propagate from a node that is not the root node
             (
-                "ascent~~shared +adios2 ^adios2+shared",
-                [("ascent", "~shared"), ("adios2", "+shared"), ("bzip2", "~shared")],
-            ),
-            (
-                "ascent++shared +adios2 ^adios2~shared",
-                [("ascent", "+shared"), ("adios2", "~shared"), ("bzip2", "+shared")],
+                "ascent +adios2 ^adios2~~shared",
+                [("ascent", "+shared"), ("adios2", "~shared"), ("bzip2", "~shared")],
             ),
         ],
     )
@@ -564,21 +560,109 @@ class TestConcretize:
         for key, expected_satisfies in expected_propagation:
             spec[key].satisfies(expected_satisfies)
 
-    def test_concretize_propagated_variant_is_not_passed_to_dependent(self):
-        """Test a package variant value was passed from its parent."""
-        spec = Spec("ascent~~shared +adios2 ^adios2+shared")
+    def test_concretize_propagate_variant_not_dependencies(self):
+        """Test that when propagating a variant it is not propagated to dependencies that
+        do not have that variant"""
+        spec = Spec("quantum-espresso~~invino")
         spec.concretize()
 
-        assert spec.satisfies("^adios2+shared")
-        assert spec.satisfies("^bzip2~shared")
+        for dep in spec.traverse(root=False):
+            assert "invino" not in dep.variants.keys()
+
+    def test_concretize_propagate_variant_exclude_dependency_fail(self):
+        """Tests that a propagating variant cannot be allowed to be excluded by any of
+        the source package's dependencies"""
+        spec = Spec("hypre ~~shared ^openblas +shared")
+        with pytest.raises(spack.error.UnsatisfiableSpecError):
+            spec.concretize()
+
+    def test_concretize_propagate_same_variant_from_direct_dep_fail(self):
+        """Test that when propagating a variant from the source package and a direct
+        dependency also propagates the same variant with a different value. Raises error"""
+        spec = Spec("ascent +adios2 ++shared ^adios2 ~~shared")
+        with pytest.raises(spack.error.UnsatisfiableSpecError):
+            spec.concretize()
+
+    def test_concretize_propagate_same_variant_in_dependency_fail(self):
+        """Test that when propagating a variant from the source package, none of it's
+        dependencies can propagate that variant with a different value. Raises error."""
+        spec = Spec("ascent +adios2 ++shared ^bzip2 ~~shared")
+        with pytest.raises(spack.error.UnsatisfiableSpecError):
+            spec.concretize()
+
+    def test_concretize_propagate_same_variant_virtual_dependency_fail(self):
+        """Test that when propagating a variant from the source package and a direct
+        dependency (that is a virtual pkg) also propagates the same variant with a
+        different value. Raises error"""
+        spec = Spec("hypre ++shared ^openblas ~~shared")
+        with pytest.raises(spack.error.UnsatisfiableSpecError):
+            spec.concretize()
+
+    def test_concretize_propagate_same_variant_multiple_sources_diamond_dep_fail(self):
+        """Test that fails when propagating the same variant with different values from multiple
+        sources that share a dependency"""
+        spec = Spec("parent-foo-bar ^dependency-foo-bar++bar ^direct-dep-foo-bar~~bar")
+        with pytest.raises(spack.error.UnsatisfiableSpecError):
+            spec.concretize()
 
     def test_concretize_propagate_specified_variant(self):
         """Test that only the specified variant is propagated to the dependencies"""
         spec = Spec("parent-foo-bar ~~foo")
         spec.concretize()
 
-        assert spec.satisfies("~foo") and spec.satisfies("^dependency-foo-bar~foo")
-        assert spec.satisfies("+bar") and not spec.satisfies("^dependency-foo-bar+bar")
+        assert spec.satisfies("^dependency-foo-bar~foo")
+        assert spec.satisfies("^second-dependency-foo-bar-fee~foo")
+        assert spec.satisfies("^direct-dep-foo-bar~foo")
+
+        assert not spec.satisfies("^dependency-foo-bar+bar")
+        assert not spec.satisfies("^second-dependency-foo-bar-fee+bar")
+        assert not spec.satisfies("^direct-dep-foo-bar+bar")
+
+    def test_concretize_propagate_one_variant(self):
+        """Test that you can specify to propagate one variant and not all"""
+        spec = Spec("parent-foo-bar ++bar ~foo")
+        spec.concretize()
+
+        assert spec.satisfies("~foo") and not spec.satisfies("^dependency-foo-bar~foo")
+        assert spec.satisfies("+bar") and spec.satisfies("^dependency-foo-bar+bar")
+
+    def test_concretize_propagate_through_first_level_deps(self):
+        """Test that boolean valued variants can be propagated past first level
+        dependecies even if the first level dependency does have the variant"""
+        spec = Spec("parent-foo-bar-fee ++fee")
+        spec.concretize()
+
+        assert spec.satisfies("+fee") and not spec.satisfies("dependency-foo-bar+fee")
+        assert spec.satisfies("^second-dependency-foo-bar-fee+fee")
+
+    def test_concretize_propagate_multiple_variants(self):
+        """Test that multiple boolean valued variants can be propagated from
+        the same source package"""
+        spec = Spec("parent-foo-bar-fee ~~foo ++bar")
+        spec.concretize()
+
+        assert spec.satisfies("~foo") and spec.satisfies("+bar")
+        assert spec.satisfies("^dependency-foo-bar ~foo +bar")
+        assert spec.satisfies("^second-dependency-foo-bar-fee ~foo +bar")
+
+    def test_concretize_propagate_multiple_variants_mulitple_sources(self):
+        """Test the propagates multiple different variants for multiple sources
+        in a diamond dependency"""
+        spec = Spec("parent-foo-bar ^dependency-foo-bar++bar ^direct-dep-foo-bar~~foo")
+        spec.concretize()
+
+        assert spec.satisfies("^second-dependency-foo-bar-fee+bar")
+        assert spec.satisfies("^second-dependency-foo-bar-fee~foo")
+        assert not spec.satisfies("^dependency-foo-bar~foo")
+        assert not spec.satisfies("^direct-dep-foo-bar+bar")
+
+    def test_concretize_propagate_single_valued_variant(self):
+        """Test propagation for single valued variants"""
+        spec = Spec("multivalue-variant libs==static")
+        spec.concretize()
+
+        assert spec.satisfies("libs=static")
+        assert spec.satisfies("^pkg-a libs=static")
 
     def test_concretize_propagate_multivalue_variant(self):
         """Test that multivalue variants are propagating the specified value(s)
@@ -591,6 +675,46 @@ class TestConcretize:
         assert not spec.satisfies("^pkg-a foo=bar")
         assert not spec.satisfies("^pkg-b foo=bar")
 
+    def test_concretize_propagate_multiple_multivalue_variant(self):
+        """Tests propagating the same mulitvalued variant from different sources allows
+        the dependents to accept all propagated values"""
+        spec = Spec("multivalue-variant foo==bar ^pkg-a foo==baz")
+        spec.concretize()
+
+        assert spec.satisfies("multivalue-variant foo=bar")
+        assert spec.satisfies("^pkg-a foo=bar,baz")
+        assert spec.satisfies("^pkg-b foo=bar,baz")
+
+    def test_concretize_propagate_variant_not_in_source(self):
+        """Test that variant is still propagated even if the source pkg
+        doesn't have the variant"""
+        spec = Spec("callpath++debug")
+        spec.concretize()
+
+        assert spec.satisfies("^mpich+debug")
+        assert not spec.satisfies("callpath+debug")
+        assert not spec.satisfies("^dyninst+debug")
+
+    def test_concretize_propagate_variant_multiple_deps_not_in_source(self):
+        """Test that a variant can be propagated to multiple dependencies
+        when the variant is not in the source package"""
+        spec = Spec("netlib-lapack++shared")
+        spec.concretize()
+
+        assert spec.satisfies("^openblas+shared")
+        assert spec.satisfies("^perl+shared")
+        assert not spec.satisfies("netlib-lapack+shared")
+
+    def test_concretize_propagate_variant_second_level_dep_not_in_source(self):
+        """Test that a variant can be propagated past first level dependencies
+        when the variant is not in the source package or any of the first level
+        dependencies"""
+        spec = Spec("parent-foo-bar ++fee")
+        spec.concretize()
+
+        assert spec.satisfies("^second-dependency-foo-bar-fee +fee")
+        assert not spec.satisfies("parent-foo-bar +fee")
+
     def test_no_matching_compiler_specs(self, mock_low_high_config):
         # only relevant when not building compilers as needed
         with spack.concretize.enable_compiler_existence_check():
diff --git a/lib/spack/spack/test/spec_semantics.py b/lib/spack/spack/test/spec_semantics.py
index 1b12a8a803..6342325364 100644
--- a/lib/spack/spack/test/spec_semantics.py
+++ b/lib/spack/spack/test/spec_semantics.py
@@ -512,9 +512,6 @@ class TestSpecSemantics:
             ("mpich", "mpich +foo"),
             ("mpich", "mpich~foo"),
             ("mpich", "mpich foo=1"),
-            ("mpich", "mpich++foo"),
-            ("mpich", "mpich~~foo"),
-            ("mpich", "mpich foo==1"),
             ("multivalue-variant foo=bar", "multivalue-variant +foo"),
             ("multivalue-variant foo=bar", "multivalue-variant ~foo"),
             ("multivalue-variant fee=bar", "multivalue-variant fee=baz"),
@@ -536,6 +533,58 @@ class TestSpecSemantics:
         with pytest.raises(UnsatisfiableSpecError):
             assert rhs.constrain(lhs)
 
+    @pytest.mark.parametrize(
+        "lhs,rhs", [("mpich", "mpich++foo"), ("mpich", "mpich~~foo"), ("mpich", "mpich foo==1")]
+    )
+    def test_concrete_specs_which_satisfy_abstract(self, lhs, rhs, default_mock_concretization):
+        lhs, rhs = default_mock_concretization(lhs), Spec(rhs)
+
+        assert lhs.intersects(rhs)
+        assert rhs.intersects(lhs)
+        assert lhs.satisfies(rhs)
+
+        s1 = lhs.copy()
+        s1.constrain(rhs)
+        assert s1 == lhs and s1.satisfies(lhs)
+
+        s2 = rhs.copy()
+        s2.constrain(lhs)
+        assert s2 == lhs and s2.satisfies(lhs)
+
+    @pytest.mark.parametrize(
+        "lhs,rhs,expected,constrained",
+        [
+            # hdf5++mpi satisfies hdf5, and vice versa, because of the non-contradiction semantic
+            ("hdf5++mpi", "hdf5", True, "hdf5++mpi"),
+            ("hdf5", "hdf5++mpi", True, "hdf5++mpi"),
+            # Same holds true for arbitrary propagated variants
+            ("hdf5++mpi", "hdf5++shared", True, "hdf5++mpi++shared"),
+            # Here hdf5+mpi satisfies hdf5++mpi but not vice versa
+            ("hdf5++mpi", "hdf5+mpi", False, "hdf5+mpi"),
+            ("hdf5+mpi", "hdf5++mpi", True, "hdf5+mpi"),
+            # Non contradiction is violated
+            ("hdf5 ^foo~mpi", "hdf5++mpi", False, "hdf5++mpi ^foo~mpi"),
+            ("hdf5++mpi", "hdf5 ^foo~mpi", False, "hdf5++mpi ^foo~mpi"),
+        ],
+    )
+    def test_abstract_specs_with_propagation(self, lhs, rhs, expected, constrained):
+        """Tests (and documents) behavior of variant propagation on abstract specs.
+
+        Propagated variants do not comply with subset semantic, making it difficult to give
+        precise definitions. Here we document the behavior that has been decided for the
+        practical cases we face.
+        """
+        lhs, rhs, constrained = Spec(lhs), Spec(rhs), Spec(constrained)
+        assert lhs.satisfies(rhs) is expected
+
+        c = lhs.copy()
+        c.constrain(rhs)
+        assert c == constrained
+
+        c = rhs.copy()
+        c.constrain(lhs)
+        assert c == constrained
+
     def test_satisfies_single_valued_variant(self):
         """Tests that the case reported in
         https://github.com/spack/spack/pull/2386#issuecomment-282147639
diff --git a/lib/spack/spack/variant.py b/lib/spack/spack/variant.py
index 3cc5ba2e0b..bce2015c12 100644
--- a/lib/spack/spack/variant.py
+++ b/lib/spack/spack/variant.py
@@ -830,7 +830,7 @@ def prevalidate_variant_value(
         only if the variant is a reserved variant.
     """
     # don't validate wildcards or variants with reserved names
-    if variant.value == ("*",) or variant.name in reserved_names:
+    if variant.value == ("*",) or variant.name in reserved_names or variant.propagate:
         return []
 
     # raise if there is no definition at all