variants: Unify metadata dictionaries to index by `when` (#44425)

Continuing the work started in #40326, his changes the structure
of Variant metadata on Packages from a single variant definition
per name with a list of `when` specs:

```
name: (Variant, [when_spec, ...])
```

to a Variant definition per `when_spec` per name:

```
when_spec: { name: Variant }
```

With this change, everything on a package *except* versions is
 keyed by `when` spec. This:

1. makes things consistent, in that conditional things are (nearly)
   all modeled in the same way; and

2. fixes an issue where we would lose information about multiple
   variant definitions in a package (see #38302). We can now have,
   e.g., different defaults for the same variant in different
   versions of a package.

Some notes:

1. This required some pretty deep changes to the solver. Previously,
   the solver's job was to select value(s) for a single variant definition
   per name per package. Now, the solver needs to:

   a. Determine which variant definition should be used for a given node,
      which can depend on the node's version, compiler, target, other variants, etc.
   b. Select valid value(s) for variants for each node based on the selected
      variant definition.

   When multiple variant definitions are enabled via their `when=` clause, we will
   always prefer the *last* matching definition, by declaration order in packages. This
   is implemented by adding a `precedence` to each variant at definition time, and we
   ensure they are added to the solver in order of precedence.

   This has the effect that variant definitions from derived classes are preferred over
   definitions from superclasses, and the last definition within the same class sticks.
   This matches python semantics. Some examples:

    ```python
    class ROCmPackage(PackageBase):
        variant("amdgpu_target", ..., when="+rocm")

    class Hipblas(ROCmPackage):
        variant("amdgpu_target", ...)
    ```

   The global variant in `hipblas` will always supersede the `when="+rocm"` variant in
   `ROCmPackage`. If `hipblas`'s variant was also conditional on `+rocm` (as it probably
   should be), we would again filter out the definition from `ROCmPackage` because it
   could never be activated. If you instead have:

    ```python
    class ROCmPackage(PackageBase):
        variant("amdgpu_target", ..., when="+rocm")

    class Hipblas(ROCmPackage):
        variant("amdgpu_target", ..., when="+rocm+foo")
    ```

   The variant on `hipblas` will win for `+rocm+foo` but the one on `ROCmPackage` will
   win with `rocm~foo`.

   So, *if* we can statically determine if a variant is overridden, we filter it out.
   This isn't strictly necessary, as the solver can handle many definitions fine, but
   this reduces the complexity of the problem instance presented to `clingo`, and
   simplifies output in `spack info` for derived packages. e.g., `spack info hipblas`
   now shows only one definition of `amdgpu_target` where before it showed two, one of
   which would never be used.

2. Nearly all access to the `variants` dictionary on packages has been refactored to
   use the following class methods on `PackageBase`:
    * `variant_names(cls) -> List[str]`: get all variant names for a package
    * `has_variant(cls, name) -> bool`: whether a package has a variant with a given name
    * `variant_definitions(cls, name: str) -> List[Tuple[Spec, Variant]]`: all definitions
      of variant `name` that are possible, along with their `when` specs.
    * `variant_items() -> `: iterate over `pkg.variants.items()`, with impossible variants
      filtered out.

   Consolidating to these methods seems to simplify the code a lot.

3. The solver does a lot more validation on variant values at setup time now. In
   particular, it checks whether a variant value on a spec is valid given the other
   constraints on that spec. This allowed us to remove the crufty logic in
   `update_variant_validate`, which was needed because we previously didn't *know* after
   a solve which variant definition had been used. Now, variant values from solves are
   constructed strictly based on which variant definition was selected -- no more
   heuristics.

4. The same prevalidation can now be done in package audits, and you can run:

   ```
   spack audit packages --strict-variants
   ```

   This turns up around 18 different places where a variant specification isn't valid
   given the conditions on variant definitions in packages. I haven't fixed those here
   but will open a separate PR to iterate on them. I plan to make strict checking the
   defaults once all existing package issues are resolved. It's not clear to me that
   strict checking should be the default for the prevalidation done at solve time.

There are a few other changes here that might be of interest:

  1. The `generator` variant in `CMakePackage` is now only defined when `build_system=cmake`.
  2. `spack info` has been updated to support the new metadata layout.
  3.  split out variant propagation into its own `.lp` file in the `solver` code.
  4. Add better typing and clean up code for variant types in `variant.py`.
  5. Add tests for new variant behavior.

19 files changed, 1122 insertions, 633 deletions

diff --git a/lib/spack/spack/audit.py b/lib/spack/spack/audit.py
index 486e3c3d65..6b441c6965 100644
--- a/lib/spack/spack/audit.py
+++ b/lib/spack/spack/audit.py
@@ -282,7 +282,7 @@ def _avoid_mismatched_variants(error_cls):
             pkg_cls = spack.repo.PATH.get_pkg_class(pkg_name)
             for variant in current_spec.variants.values():
                 # Variant does not exist at all
-                if variant.name not in pkg_cls.variants:
+                if variant.name not in pkg_cls.variant_names():
                     summary = (
                         f"Setting a preference for the '{pkg_name}' package to the "
                         f"non-existing variant '{variant.name}'"
@@ -291,9 +291,8 @@ def _avoid_mismatched_variants(error_cls):
                     continue
 
                 # Variant cannot accept this value
-                s = spack.spec.Spec(pkg_name)
                 try:
-                    s.update_variant_validate(variant.name, variant.value)
+                    spack.variant.prevalidate_variant_value(pkg_cls, variant, strict=True)
                 except Exception:
                     summary = (
                         f"Setting the variant '{variant.name}' of the '{pkg_name}' package "
@@ -663,9 +662,15 @@ def _ensure_env_methods_are_ported_to_builders(pkgs, error_cls):
     errors = []
     for pkg_name in pkgs:
         pkg_cls = spack.repo.PATH.get_pkg_class(pkg_name)
-        buildsystem_variant, _ = pkg_cls.variants["build_system"]
-        buildsystem_names = [getattr(x, "value", x) for x in buildsystem_variant.values]
-        builder_cls_names = [spack.builder.BUILDER_CLS[x].__name__ for x in buildsystem_names]
+
+        # values are either Value objects (for conditional values) or the values themselves
+        build_system_names = set(
+            v.value if isinstance(v, spack.variant.Value) else v
+            for _, variant in pkg_cls.variant_definitions("build_system")
+            for v in variant.values
+        )
+        builder_cls_names = [spack.builder.BUILDER_CLS[x].__name__ for x in build_system_names]
+
         module = pkg_cls.module
         has_builders_in_package_py = any(
             getattr(module, name, False) for name in builder_cls_names
@@ -932,20 +937,22 @@ def _issues_in_depends_on_directive(pkgs, error_cls):
 
                 # check variants
                 dependency_variants = dep.spec.variants
-                for name, value in dependency_variants.items():
+                for name, variant in dependency_variants.items():
                     try:
-                        v, _ = dependency_pkg_cls.variants[name]
-                        v.validate_or_raise(value, pkg_cls=dependency_pkg_cls)
+                        spack.variant.prevalidate_variant_value(
+                            dependency_pkg_cls, variant, dep.spec, strict=True
+                        )
                     except Exception as e:
                         summary = (
                             f"{pkg_name}: wrong variant used for dependency in 'depends_on()'"
                         )
 
+                        error_msg = str(e)
                         if isinstance(e, KeyError):
                             error_msg = (
                                 f"variant {str(e).strip()} does not exist in package {dep_name}"
+                                f" in package '{dep_name}'"
                             )
-                        error_msg += f" in package '{dep_name}'"
 
                         errors.append(
                             error_cls(summary=summary, details=[error_msg, f"in {filename}"])
@@ -957,39 +964,38 @@ def _issues_in_depends_on_directive(pkgs, error_cls):
 @package_directives
 def _ensure_variant_defaults_are_parsable(pkgs, error_cls):
     """Ensures that variant defaults are present and parsable from cli"""
-    errors = []
-    for pkg_name in pkgs:
-        pkg_cls = spack.repo.PATH.get_pkg_class(pkg_name)
-        for variant_name, entry in pkg_cls.variants.items():
-            variant, _ = entry
-            default_is_parsable = (
-                # Permitting a default that is an instance on 'int' permits
-                # to have foo=false or foo=0. Other falsish values are
-                # not allowed, since they can't be parsed from cli ('foo=')
-                isinstance(variant.default, int)
-                or variant.default
-            )
-            if not default_is_parsable:
-                error_msg = "Variant '{}' of package '{}' has a bad default value"
-                errors.append(error_cls(error_msg.format(variant_name, pkg_name), []))
-                continue
 
-            try:
-                vspec = variant.make_default()
-            except spack.variant.MultipleValuesInExclusiveVariantError:
-                error_msg = "Cannot create a default value for the variant '{}' in package '{}'"
-                errors.append(error_cls(error_msg.format(variant_name, pkg_name), []))
-                continue
+    def check_variant(pkg_cls, variant, vname):
+        # bool is a subclass of int in python. Permitting a default that is an instance
+        # of 'int' means both foo=false and foo=0 are accepted. Other falsish values are
+        # not allowed, since they can't be parsed from CLI ('foo=')
+        default_is_parsable = isinstance(variant.default, int) or variant.default
 
-            try:
-                variant.validate_or_raise(vspec, pkg_cls=pkg_cls)
-            except spack.variant.InvalidVariantValueError:
-                error_msg = (
-                    "The default value of the variant '{}' in package '{}' failed validation"
-                )
-                question = "Is it among the allowed values?"
-                errors.append(error_cls(error_msg.format(variant_name, pkg_name), [question]))
+        if not default_is_parsable:
+            msg = f"Variant '{vname}' of package '{pkg_cls.name}' has an unparsable default value"
+            return [error_cls(msg, [])]
+
+        try:
+            vspec = variant.make_default()
+        except spack.variant.MultipleValuesInExclusiveVariantError:
+            msg = f"Can't create default value for variant '{vname}' in package '{pkg_cls.name}'"
+            return [error_cls(msg, [])]
+
+        try:
+            variant.validate_or_raise(vspec, pkg_cls.name)
+        except spack.variant.InvalidVariantValueError:
+            msg = "Default value of variant '{vname}' in package '{pkg.name}' is invalid"
+            question = "Is it among the allowed values?"
+            return [error_cls(msg, [question])]
+
+        return []
 
+    errors = []
+    for pkg_name in pkgs:
+        pkg_cls = spack.repo.PATH.get_pkg_class(pkg_name)
+        for vname in pkg_cls.variant_names():
+            for _, variant_def in pkg_cls.variant_definitions(vname):
+                errors.extend(check_variant(pkg_cls, variant_def, vname))
     return errors
 
 
@@ -999,11 +1005,11 @@ def _ensure_variants_have_descriptions(pkgs, error_cls):
     errors = []
     for pkg_name in pkgs:
         pkg_cls = spack.repo.PATH.get_pkg_class(pkg_name)
-        for variant_name, entry in pkg_cls.variants.items():
-            variant, _ = entry
-            if not variant.description:
-                error_msg = "Variant '{}' in package '{}' is missing a description"
-                errors.append(error_cls(error_msg.format(variant_name, pkg_name), []))
+        for name in pkg_cls.variant_names():
+            for when, variant in pkg_cls.variant_definitions(name):
+                if not variant.description:
+                    msg = f"Variant '{name}' in package '{pkg_name}' is missing a description"
+                    errors.append(error_cls(msg, []))
 
     return errors
 
@@ -1060,29 +1066,26 @@ def _version_constraints_are_satisfiable_by_some_version_in_repo(pkgs, error_cls
 
 
 def _analyze_variants_in_directive(pkg, constraint, directive, error_cls):
-    variant_exceptions = (
-        spack.variant.InconsistentValidationError,
-        spack.variant.MultipleValuesInExclusiveVariantError,
-        spack.variant.InvalidVariantValueError,
-        KeyError,
-    )
     errors = []
-    for name, v in constraint.variants.items():
-        try:
-            variant, _ = pkg.variants[name]
-            variant.validate_or_raise(v, pkg_cls=pkg)
-        except variant_exceptions as e:
-            summary = pkg.name + ': wrong variant in "{0}" directive'
-            summary = summary.format(directive)
-            filename = spack.repo.PATH.filename_for_package_name(pkg.name)
-
-            error_msg = str(e).strip()
-            if isinstance(e, KeyError):
-                error_msg = "the variant {0} does not exist".format(error_msg)
+    variant_names = pkg.variant_names()
+    summary = f"{pkg.name}: wrong variant in '{directive}' directive"
+    filename = spack.repo.PATH.filename_for_package_name(pkg.name)
 
-            err = error_cls(summary=summary, details=[error_msg, "in " + filename])
+    for name, v in constraint.variants.items():
+        if name not in variant_names:
+            msg = f"variant {name} does not exist in {pkg.name}"
+            errors.append(error_cls(summary=summary, details=[msg, f"in {filename}"]))
+            continue
 
-            errors.append(err)
+        try:
+            spack.variant.prevalidate_variant_value(pkg, v, constraint, strict=True)
+        except (
+            spack.variant.InconsistentValidationError,
+            spack.variant.MultipleValuesInExclusiveVariantError,
+            spack.variant.InvalidVariantValueError,
+        ) as e:
+            msg = str(e).strip()
+            errors.append(error_cls(summary=summary, details=[msg, f"in {filename}"]))
 
     return errors
 
@@ -1120,9 +1123,10 @@ def _named_specs_in_when_arguments(pkgs, error_cls):
                 for dname in dnames
             )
 
-        for vname, (variant, triggers) in pkg_cls.variants.items():
-            summary = f"{pkg_name}: wrong 'when=' condition for the '{vname}' variant"
-            errors.extend(_extracts_errors(triggers, summary))
+        for when, variants_by_name in pkg_cls.variants.items():
+            for vname, variant in variants_by_name.items():
+                summary = f"{pkg_name}: wrong 'when=' condition for the '{vname}' variant"
+                errors.extend(_extracts_errors([when], summary))
 
         for when, providers, details in _error_items(pkg_cls.provided):
             errors.extend(
diff --git a/lib/spack/spack/build_systems/autotools.py b/lib/spack/spack/build_systems/autotools.py
index d5ddcea11a..47911271fe 100644
--- a/lib/spack/spack/build_systems/autotools.py
+++ b/lib/spack/spack/build_systems/autotools.py
@@ -687,9 +687,8 @@ To resolve this problem, please try the following:
 
         variant = variant or name
 
-        # Defensively look that the name passed as argument is among
-        # variants
-        if variant not in self.pkg.variants:
+        # Defensively look that the name passed as argument is among variants
+        if not self.pkg.has_variant(variant):
             msg = '"{0}" is not a variant of "{1}"'
             raise KeyError(msg.format(variant, self.pkg.name))
 
@@ -698,27 +697,19 @@ To resolve this problem, please try the following:
 
         # Create a list of pairs. Each pair includes a configuration
         # option and whether or not that option is activated
-        variant_desc, _ = self.pkg.variants[variant]
-        if set(variant_desc.values) == set((True, False)):
+        vdef = self.pkg.get_variant(variant)
+        if set(vdef.values) == set((True, False)):
             # BoolValuedVariant carry information about a single option.
             # Nonetheless, for uniformity of treatment we'll package them
             # in an iterable of one element.
-            condition = "+{name}".format(name=variant)
-            options = [(name, condition in spec)]
+            options = [(name, f"+{variant}" in spec)]
         else:
-            condition = "{variant}={value}"
             # "feature_values" is used to track values which correspond to
             # features which can be enabled or disabled as understood by the
             # package's build system. It excludes values which have special
             # meanings and do not correspond to features (e.g. "none")
-            feature_values = (
-                getattr(variant_desc.values, "feature_values", None) or variant_desc.values
-            )
-
-            options = [
-                (value, condition.format(variant=variant, value=value) in spec)
-                for value in feature_values
-            ]
+            feature_values = getattr(vdef.values, "feature_values", None) or vdef.values
+            options = [(value, f"{variant}={value}" in spec) for value in feature_values]
 
         # For each allowed value in the list of values
         for option_value, activated in options:
diff --git a/lib/spack/spack/build_systems/cached_cmake.py b/lib/spack/spack/build_systems/cached_cmake.py
index aff54d7559..3706943704 100644
--- a/lib/spack/spack/build_systems/cached_cmake.py
+++ b/lib/spack/spack/build_systems/cached_cmake.py
@@ -89,7 +89,7 @@ class CachedCMakeBuilder(CMakeBuilder):
         if variant is None:
             variant = cmake_var.lower()
 
-        if variant not in self.pkg.variants:
+        if not self.pkg.has_variant(variant):
             raise KeyError('"{0}" is not a variant of "{1}"'.format(variant, self.pkg.name))
 
         if variant not in self.pkg.spec.variants:
diff --git a/lib/spack/spack/build_systems/cmake.py b/lib/spack/spack/build_systems/cmake.py
index dc833a10a6..93d3485ae0 100644
--- a/lib/spack/spack/build_systems/cmake.py
+++ b/lib/spack/spack/build_systems/cmake.py
@@ -146,6 +146,7 @@ def generator(*names: str, default: Optional[str] = None):
         default=default,
         values=_values,
         description="the build system generator to use",
+        when="build_system=cmake",
     )
     for x in not_used:
         conflicts(f"generator={x}")
@@ -505,7 +506,7 @@ class CMakeBuilder(BaseBuilder):
         if variant is None:
             variant = cmake_var.lower()
 
-        if variant not in self.pkg.variants:
+        if not self.pkg.has_variant(variant):
             raise KeyError('"{0}" is not a variant of "{1}"'.format(variant, self.pkg.name))
 
         if variant not in self.pkg.spec.variants:
diff --git a/lib/spack/spack/cmd/config.py b/lib/spack/spack/cmd/config.py
index 5c2a02f042..aef2d7a541 100644
--- a/lib/spack/spack/cmd/config.py
+++ b/lib/spack/spack/cmd/config.py
@@ -536,11 +536,11 @@ def config_prefer_upstream(args):
         # Get and list all the variants that differ from the default.
         variants = []
         for var_name, variant in spec.variants.items():
-            if var_name in ["patches"] or var_name not in spec.package.variants:
+            if var_name in ["patches"] or not spec.package.has_variant(var_name):
                 continue
 
-            variant_desc, _ = spec.package.variants[var_name]
-            if variant.value != variant_desc.default:
+            vdef = spec.package.get_variant(var_name)
+            if variant.value != vdef.default:
                 variants.append(str(variant))
         variants.sort()
         variants = " ".join(variants)
diff --git a/lib/spack/spack/cmd/info.py b/lib/spack/spack/cmd/info.py
index 5ea99caa3a..a7cdf608a2 100644
--- a/lib/spack/spack/cmd/info.py
+++ b/lib/spack/spack/cmd/info.py
@@ -334,26 +334,6 @@ def _fmt_variant(variant, max_name_default_len, indent, when=None, out=None):
     out.write("\n")
 
 
-def _variants_by_name_when(pkg):
-    """Adaptor to get variants keyed by { name: { when: { [Variant...] } }."""
-    # TODO: replace with pkg.variants_by_name(when=True) when unified directive dicts are merged.
-    variants = {}
-    for name, (variant, whens) in sorted(pkg.variants.items()):
-        for when in whens:
-            variants.setdefault(name, {}).setdefault(when, []).append(variant)
-    return variants
-
-
-def _variants_by_when_name(pkg):
-    """Adaptor to get variants keyed by { when: { name: Variant } }"""
-    # TODO: replace with pkg.variants when unified directive dicts are merged.
-    variants = {}
-    for name, (variant, whens) in pkg.variants.items():
-        for when in whens:
-            variants.setdefault(when, {})[name] = variant
-    return variants
-
-
 def _print_variants_header(pkg):
     """output variants"""
 
@@ -364,32 +344,22 @@ def _print_variants_header(pkg):
     color.cprint("")
     color.cprint(section_title("Variants:"))
 
-    variants_by_name = _variants_by_name_when(pkg)
-
     # Calculate the max length of the "name [default]" part of the variant display
     # This lets us know where to print variant values.
     max_name_default_len = max(
         color.clen(_fmt_name_and_default(variant))
-        for name, when_variants in variants_by_name.items()
-        for variants in when_variants.values()
-        for variant in variants
+        for name in pkg.variant_names()
+        for _, variant in pkg.variant_definitions(name)
     )
 
-    return max_name_default_len, variants_by_name
-
-
-def _unconstrained_ver_first(item):
-    """sort key that puts specs with open version ranges first"""
-    spec, _ = item
-    return (spack.version.any_version not in spec.versions, spec)
+    return max_name_default_len
 
 
 def print_variants_grouped_by_when(pkg):
-    max_name_default_len, _ = _print_variants_header(pkg)
+    max_name_default_len = _print_variants_header(pkg)
 
     indent = 4
-    variants = _variants_by_when_name(pkg)
-    for when, variants_by_name in sorted(variants.items(), key=_unconstrained_ver_first):
+    for when, variants_by_name in pkg.variant_items():
         padded_values = max_name_default_len + 4
         start_indent = indent
 
@@ -407,15 +377,14 @@ def print_variants_grouped_by_when(pkg):
 
 
 def print_variants_by_name(pkg):
-    max_name_default_len, variants_by_name = _print_variants_header(pkg)
+    max_name_default_len = _print_variants_header(pkg)
     max_name_default_len += 4
 
     indent = 4
-    for name, when_variants in variants_by_name.items():
-        for when, variants in sorted(when_variants.items(), key=_unconstrained_ver_first):
-            for variant in variants:
-                _fmt_variant(variant, max_name_default_len, indent, when, out=sys.stdout)
-                sys.stdout.write("\n")
+    for name in pkg.variant_names():
+        for when, variant in pkg.variant_definitions(name):
+            _fmt_variant(variant, max_name_default_len, indent, when, out=sys.stdout)
+            sys.stdout.write("\n")
 
 
 def print_variants(pkg, args):
diff --git a/lib/spack/spack/cray_manifest.py b/lib/spack/spack/cray_manifest.py
index f71cf272b6..41767bdf06 100644
--- a/lib/spack/spack/cray_manifest.py
+++ b/lib/spack/spack/cray_manifest.py
@@ -132,7 +132,7 @@ def spec_from_entry(entry):
         variant_strs = list()
         for name, value in entry["parameters"].items():
             # TODO: also ensure that the variant value is valid?
-            if not (name in pkg_cls.variants):
+            if not pkg_cls.has_variant(name):
                 tty.debug(
                     "Omitting variant {0} for entry {1}/{2}".format(
                         name, entry["name"], entry["hash"][:7]
diff --git a/lib/spack/spack/directives.py b/lib/spack/spack/directives.py
index 7119339d5a..8f9e43bf8b 100644
--- a/lib/spack/spack/directives.py
+++ b/lib/spack/spack/directives.py
@@ -78,7 +78,6 @@ __all__ = [
     "redistribute",
 ]
 
-
 _patch_order_index = 0
 
 
@@ -674,22 +673,25 @@ def variant(
 
     def _execute_variant(pkg):
         when_spec = _make_when_spec(when)
-        when_specs = [when_spec]
 
         if not re.match(spack.spec.IDENTIFIER_RE, name):
             directive = "variant"
             msg = "Invalid variant name in {0}: '{1}'"
             raise DirectiveError(directive, msg.format(pkg.name, name))
 
-        if name in pkg.variants:
-            # We accumulate when specs, but replace the rest of the variant
-            # with the newer values
-            _, orig_when = pkg.variants[name]
-            when_specs += orig_when
-
-        pkg.variants[name] = (
-            spack.variant.Variant(name, default, description, values, multi, validator, sticky),
-            when_specs,
+        # variants are stored by condition then by name (so only the last variant of a
+        # given name takes precedence *per condition*).
+        # NOTE: variant defaults and values can conflict if when conditions overlap.
+        variants_by_name = pkg.variants.setdefault(when_spec, {})
+        variants_by_name[name] = spack.variant.Variant(
+            name=name,
+            default=default,
+            description=description,
+            values=values,
+            multi=multi,
+            validator=validator,
+            sticky=sticky,
+            precedence=pkg.num_variant_definitions(),
         )
 
     return _execute_variant
diff --git a/lib/spack/spack/package_base.py b/lib/spack/spack/package_base.py
index c539cf1e0e..5be23ff124 100644
--- a/lib/spack/spack/package_base.py
+++ b/lib/spack/spack/package_base.py
@@ -451,10 +451,11 @@ def _by_name(
             else:
                 all_by_name.setdefault(name, []).append(value)
 
+    # this needs to preserve the insertion order of whens
     return dict(sorted(all_by_name.items()))
 
 
-def _names(when_indexed_dictionary):
+def _names(when_indexed_dictionary: WhenDict) -> List[str]:
     """Get sorted names from dicts keyed by when/name."""
     all_names = set()
     for when, by_name in when_indexed_dictionary.items():
@@ -464,6 +465,45 @@ def _names(when_indexed_dictionary):
     return sorted(all_names)
 
 
+WhenVariantList = List[Tuple["spack.spec.Spec", "spack.variant.Variant"]]
+
+
+def _remove_overridden_vdefs(variant_defs: WhenVariantList) -> None:
+    """Remove variant defs from the list if their when specs are satisfied by later ones.
+
+    Any such variant definitions are *always* overridden by their successor, as it will
+    match everything the predecessor matches, and the solver will prefer it because of
+    its higher precedence.
+
+    We can just remove these defs from variant definitions and avoid putting them in the
+    solver. This is also useful for, e.g., `spack info`, where we don't want to show a
+    variant from a superclass if it is always overridden by a variant defined in a
+    subclass.
+
+    Example::
+
+        class ROCmPackage:
+            variant("amdgpu_target", ..., when="+rocm")
+
+        class Hipblas:
+            variant("amdgpu_target", ...)
+
+    The subclass definition *always* overrides the superclass definition here, but they
+    have different when specs and the subclass def won't just replace the one in the
+    superclass. In this situation, the subclass should *probably* also have
+    ``when="+rocm"``, but we can't guarantee that will always happen when a vdef is
+    overridden. So we use this method to remove any overrides we can know statically.
+
+    """
+    i = 0
+    while i < len(variant_defs):
+        when, vdef = variant_defs[i]
+        if any(when.satisfies(successor) for successor, _ in variant_defs[i + 1 :]):
+            del variant_defs[i]
+        else:
+            i += 1
+
+
 class RedistributionMixin:
     """Logic for determining whether a Package is source/binary
     redistributable.
@@ -596,7 +636,7 @@ class PackageBase(WindowsRPath, PackageViewMixin, RedistributionMixin, metaclass
     provided: Dict["spack.spec.Spec", Set["spack.spec.Spec"]]
     provided_together: Dict["spack.spec.Spec", List[Set[str]]]
     patches: Dict["spack.spec.Spec", List["spack.patch.Patch"]]
-    variants: Dict[str, Tuple["spack.variant.Variant", "spack.spec.Spec"]]
+    variants: Dict["spack.spec.Spec", Dict[str, "spack.variant.Variant"]]
     languages: Dict["spack.spec.Spec", Set[str]]
 
     #: By default, packages are not virtual
@@ -750,6 +790,72 @@ class PackageBase(WindowsRPath, PackageViewMixin, RedistributionMixin, metaclass
     def dependencies_by_name(cls, when: bool = False):
         return _by_name(cls.dependencies, when=when)
 
+    # Accessors for variants
+    # External code workingw with Variants should go through the methods below
+
+    @classmethod
+    def variant_names(cls) -> List[str]:
+        return _names(cls.variants)
+
+    @classmethod
+    def has_variant(cls, name) -> bool:
+        return any(name in dictionary for dictionary in cls.variants.values())
+
+    @classmethod
+    def num_variant_definitions(cls) -> int:
+        """Total number of variant definitions in this class so far."""
+        return sum(len(variants_by_name) for variants_by_name in cls.variants.values())
+
+    @classmethod
+    def variant_definitions(cls, name: str) -> WhenVariantList:
+        """Iterator over (when_spec, Variant) for all variant definitions for a particular name."""
+        # construct a list of defs sorted by precedence
+        defs: WhenVariantList = []
+        for when, variants_by_name in cls.variants.items():
+            variant_def = variants_by_name.get(name)
+            if variant_def:
+                defs.append((when, variant_def))
+
+        # With multiple definitions, ensure precedence order and simplify overrides
+        if len(defs) > 1:
+            defs.sort(key=lambda v: v[1].precedence)
+            _remove_overridden_vdefs(defs)
+
+        return defs
+
+    @classmethod
+    def variant_items(
+        cls,
+    ) -> Iterable[Tuple["spack.spec.Spec", Dict[str, "spack.variant.Variant"]]]:
+        """Iterate over ``cls.variants.items()`` with overridden definitions removed."""
+        # Note: This is quadratic in the average number of variant definitions per name.
+        # That is likely close to linear in practice, as there are few variants with
+        # multiple definitions (but it matters when they are there).
+        exclude = {
+            name: [id(vdef) for _, vdef in cls.variant_definitions(name)]
+            for name in cls.variant_names()
+        }
+
+        for when, variants_by_name in cls.variants.items():
+            filtered_variants_by_name = {
+                name: vdef for name, vdef in variants_by_name.items() if id(vdef) in exclude[name]
+            }
+
+            if filtered_variants_by_name:
+                yield when, filtered_variants_by_name
+
+    def get_variant(self, name: str) -> "spack.variant.Variant":
+        """Get the highest precedence variant definition matching this package's spec.
+
+        Arguments:
+            name: name of the variant definition to get
+        """
+        try:
+            highest_to_lowest = reversed(self.variant_definitions(name))
+            return next(vdef for when, vdef in highest_to_lowest if self.spec.satisfies(when))
+        except StopIteration:
+            raise ValueError(f"No variant '{name}' on spec: {self.spec}")
+
     @classmethod
     def possible_dependencies(
         cls,
diff --git a/lib/spack/spack/package_prefs.py b/lib/spack/spack/package_prefs.py
index f655fbb885..0204e156f1 100644
--- a/lib/spack/spack/package_prefs.py
+++ b/lib/spack/spack/package_prefs.py
@@ -149,10 +149,12 @@ class PackagePrefs:
 
         # Only return variants that are actually supported by the package
         pkg_cls = spack.repo.PATH.get_pkg_class(pkg_name)
-        spec = spack.spec.Spec("%s %s" % (pkg_name, variants))
-        return dict(
-            (name, variant) for name, variant in spec.variants.items() if name in pkg_cls.variants
-        )
+        spec = spack.spec.Spec(f"{pkg_name} {variants}")
+        return {
+            name: variant
+            for name, variant in spec.variants.items()
+            if name in pkg_cls.variant_names()
+        }
 
 
 def is_spec_buildable(spec):
diff --git a/lib/spack/spack/solver/asp.py b/lib/spack/spack/solver/asp.py
index 62557d311a..d8d052f311 100644
--- a/lib/spack/spack/solver/asp.py
+++ b/lib/spack/spack/solver/asp.py
@@ -44,7 +44,7 @@ import spack.util.crypto
 import spack.util.libc
 import spack.util.path
 import spack.util.timer
-import spack.variant
+import spack.variant as vt
 import spack.version as vn
 import spack.version.git_ref_lookup
 from spack import traverse
@@ -127,8 +127,14 @@ class Provenance(enum.IntEnum):
 
 
 @contextmanager
-def spec_with_name(spec, name):
+def named_spec(
+    spec: Optional["spack.spec.Spec"], name: Optional[str]
+) -> Iterator[Optional["spack.spec.Spec"]]:
     """Context manager to temporarily set the name of a spec"""
+    if spec is None or name is None:
+        yield spec
+        return
+
     old_name = spec.name
     spec.name = name
     try:
@@ -1128,6 +1134,7 @@ class SpackSolverSetup:
         self.default_targets: List = []
         self.compiler_version_constraints: Set = set()
         self.post_facts: List = []
+        self.variant_ids_by_def_id: Dict[int, int] = {}
 
         self.reusable_and_possible: ConcreteSpecsByHash = ConcreteSpecsByHash()
 
@@ -1218,7 +1225,7 @@ class SpackSolverSetup:
     def conflict_rules(self, pkg):
         for when_spec, conflict_specs in pkg.conflicts.items():
             when_spec_msg = "conflict constraint %s" % str(when_spec)
-            when_spec_id = self.condition(when_spec, name=pkg.name, msg=when_spec_msg)
+            when_spec_id = self.condition(when_spec, required_name=pkg.name, msg=when_spec_msg)
 
             for conflict_spec, conflict_msg in conflict_specs:
                 conflict_spec = spack.spec.Spec(conflict_spec)
@@ -1234,7 +1241,9 @@ class SpackSolverSetup:
                     spec_for_msg = spack.spec.Spec(pkg.name)
                 conflict_spec_msg = f"conflict is triggered when {str(spec_for_msg)}"
                 conflict_spec_id = self.condition(
-                    conflict_spec, name=conflict_spec.name or pkg.name, msg=conflict_spec_msg
+                    conflict_spec,
+                    required_name=conflict_spec.name or pkg.name,
+                    msg=conflict_spec_msg,
                 )
                 self.gen.fact(
                     fn.pkg_fact(
@@ -1248,7 +1257,7 @@ class SpackSolverSetup:
             condition_msg = f"{pkg.name} needs the {', '.join(sorted(languages))} language"
             if when_spec != spack.spec.Spec():
                 condition_msg += f" when {when_spec}"
-            condition_id = self.condition(when_spec, name=pkg.name, msg=condition_msg)
+            condition_id = self.condition(when_spec, required_name=pkg.name, msg=condition_msg)
             for language in sorted(languages):
                 self.gen.fact(fn.pkg_fact(pkg.name, fn.language(condition_id, language)))
         self.gen.newline()
@@ -1363,96 +1372,116 @@ class SpackSolverSetup:
                 self.gen.newline()
         self._effect_cache.clear()
 
-    def variant_rules(self, pkg):
-        for name, entry in sorted(pkg.variants.items()):
-            variant, when = entry
+    def define_variant(
+        self,
+        pkg: "Type[spack.package_base.PackageBase]",
+        name: str,
+        when: spack.spec.Spec,
+        variant_def: vt.Variant,
+    ):
+        pkg_fact = lambda f: self.gen.fact(fn.pkg_fact(pkg.name, f))
 
-            if spack.spec.Spec() in when:
-                # unconditional variant
-                self.gen.fact(fn.pkg_fact(pkg.name, fn.variant(name)))
-            else:
-                # conditional variant
-                for w in when:
-                    msg = "%s has variant %s" % (pkg.name, name)
-                    if str(w):
-                        msg += " when %s" % w
-
-                    cond_id = self.condition(w, name=pkg.name, msg=msg)
-                    self.gen.fact(fn.pkg_fact(pkg.name, fn.conditional_variant(cond_id, name)))
-
-            single_value = not variant.multi
-            if single_value:
-                self.gen.fact(fn.pkg_fact(pkg.name, fn.variant_single_value(name)))
-                self.gen.fact(
-                    fn.pkg_fact(
-                        pkg.name, fn.variant_default_value_from_package_py(name, variant.default)
-                    )
+        # Every variant id has a unique definition (conditional or unconditional), and
+        # higher variant id definitions take precedence when variants intersect.
+        vid = next(self._id_counter)
+
+        # used to find a variant id from its variant definition (for variant values on specs)
+        self.variant_ids_by_def_id[id(variant_def)] = vid
+
+        if when == spack.spec.Spec():
+            # unconditional variant
+            pkg_fact(fn.variant_definition(name, vid))
+        else:
+            # conditional variant
+            msg = f"Package {pkg.name} has variant '{name}' when {when}"
+            cond_id = self.condition(when, required_name=pkg.name, msg=msg)
+            pkg_fact(fn.variant_condition(name, vid, cond_id))
+
+        # record type so we can construct the variant when we read it back in
+        self.gen.fact(fn.variant_type(vid, variant_def.variant_type.value))
+
+        if variant_def.sticky:
+            pkg_fact(fn.variant_sticky(vid))
+
+        # define defaults for this variant definition
+        defaults = variant_def.make_default().value if variant_def.multi else [variant_def.default]
+        for val in sorted(defaults):
+            pkg_fact(fn.variant_default_value_from_package_py(vid, val))
+
+        # define possible values for this variant definition
+        values = variant_def.values
+        if values is None:
+            values = []
+
+        elif isinstance(values, vt.DisjointSetsOfValues):
+            union = set()
+            for sid, s in enumerate(values.sets):
+                for value in s:
+                    pkg_fact(fn.variant_value_from_disjoint_sets(vid, value, sid))
+                union.update(s)
+            values = union
+
+        # ensure that every variant has at least one possible value.
+        if not values:
+            values = [variant_def.default]
+
+        for value in sorted(values):
+            pkg_fact(fn.variant_possible_value(vid, value))
+
+            # when=True means unconditional, so no need for conditional values
+            if getattr(value, "when", True) is True:
+                continue
+
+            # now we have to handle conditional values
+            quoted_value = spack.parser.quote_if_needed(str(value))
+            vstring = f"{name}={quoted_value}"
+            variant_has_value = spack.spec.Spec(vstring)
+
+            if value.when:
+                # the conditional value is always "possible", but it imposes its when condition as
+                # a constraint if the conditional value is taken. This may seem backwards, but it
+                # ensures that the conditional can only occur when its condition holds.
+                self.condition(
+                    required_spec=variant_has_value,
+                    imposed_spec=value.when,
+                    required_name=pkg.name,
+                    imposed_name=pkg.name,
+                    msg=f"{pkg.name} variant {name} has value '{quoted_value}' when {value.when}",
                 )
             else:
-                spec_variant = variant.make_default()
-                defaults = spec_variant.value
-                for val in sorted(defaults):
-                    self.gen.fact(
-                        fn.pkg_fact(pkg.name, fn.variant_default_value_from_package_py(name, val))
-                    )
+                # We know the value is never allowed statically (when was false), but we can't just
+                # ignore it b/c it could come in as a possible value and we need a good error msg.
+                # So, it's a conflict -- if the value is somehow used, it'll trigger an error.
+                trigger_id = self.condition(
+                    variant_has_value,
+                    required_name=pkg.name,
+                    msg=f"invalid variant value: {vstring}",
+                )
+                constraint_id = self.condition(
+                    spack.spec.Spec(),
+                    required_name=pkg.name,
+                    msg="empty (total) conflict constraint",
+                )
+                msg = f"variant value {vstring} is conditionally disabled"
+                pkg_fact(fn.conflict(trigger_id, constraint_id, msg))
 
-            values = variant.values
-            if values is None:
-                values = []
-            elif isinstance(values, spack.variant.DisjointSetsOfValues):
-                union = set()
-                # Encode the disjoint sets in the logic program
-                for sid, s in enumerate(values.sets):
-                    for value in s:
-                        self.gen.fact(
-                            fn.pkg_fact(
-                                pkg.name, fn.variant_value_from_disjoint_sets(name, value, sid)
-                            )
-                        )
-                    union.update(s)
-                values = union
-
-            # make sure that every variant has at least one possible value
-            if not values:
-                values = [variant.default]
-
-            for value in sorted(values):
-                if getattr(value, "when", True) is not True:  # when=True means unconditional
-                    condition_spec = spack.spec.Spec("{0}={1}".format(name, value))
-                    if value.when is False:
-                        # This value is a conflict
-                        # Cannot just prevent listing it as a possible value because it could
-                        # also come in as a possible value from the command line
-                        trigger_id = self.condition(
-                            condition_spec,
-                            name=pkg.name,
-                            msg="invalid variant value {0}={1}".format(name, value),
-                        )
-                        constraint_id = self.condition(
-                            spack.spec.Spec(),
-                            name=pkg.name,
-                            msg="empty (total) conflict constraint",
-                        )
-                        msg = "variant {0}={1} is conditionally disabled".format(name, value)
-                        self.gen.fact(
-                            fn.pkg_fact(pkg.name, fn.conflict(trigger_id, constraint_id, msg))
-                        )
-                    else:
-                        imposed = spack.spec.Spec(value.when)
-                        imposed.name = pkg.name
-
-                        self.condition(
-                            required_spec=condition_spec,
-                            imposed_spec=imposed,
-                            name=pkg.name,
-                            msg="%s variant %s value %s when %s" % (pkg.name, name, value, when),
-                        )
-                self.gen.fact(fn.pkg_fact(pkg.name, fn.variant_possible_value(name, value)))
+        self.gen.newline()
 
-            if variant.sticky:
-                self.gen.fact(fn.pkg_fact(pkg.name, fn.variant_sticky(name)))
+    def define_auto_variant(self, name: str, multi: bool):
+        self.gen.h3(f"Special variant: {name}")
+        vid = next(self._id_counter)
+        self.gen.fact(fn.auto_variant(name, vid))
+        self.gen.fact(
+            fn.variant_type(
+                vid, vt.VariantType.MULTI.value if multi else vt.VariantType.SINGLE.value
+            )
+        )
 
-            self.gen.newline()
+    def variant_rules(self, pkg: "Type[spack.package_base.PackageBase]"):
+        for name in pkg.variant_names():
+            self.gen.h3(f"Variant {name} in package {pkg.name}")
+            for when, variant_def in pkg.variant_definitions(name):
+                self.define_variant(pkg, name, when, variant_def)
 
     def _get_condition_id(
         self,
@@ -1490,7 +1519,9 @@ class SpackSolverSetup:
         self,
         required_spec: spack.spec.Spec,
         imposed_spec: Optional[spack.spec.Spec] = None,
-        name: Optional[str] = None,
+        *,
+        required_name: Optional[str] = None,
+        imposed_name: Optional[str] = None,
         msg: Optional[str] = None,
         context: Optional[ConditionContext] = None,
     ):
@@ -1499,22 +1530,30 @@ class SpackSolverSetup:
         Arguments:
             required_spec: the constraints that triggers this condition
             imposed_spec: the constraints that are imposed when this condition is triggered
-            name: name for `required_spec` (required if required_spec is anonymous, ignored if not)
+            required_name: name for ``required_spec``
+                (required if required_spec is anonymous, ignored if not)
+            imposed_name: name for ``imposed_spec``
+                (required if imposed_spec is anonymous, ignored if not)
             msg: description of the condition
             context: if provided, indicates how to modify the clause-sets for the required/imposed
                 specs based on the type of constraint they are generated for (e.g. `depends_on`)
         Returns:
             int: id of the condition created by this function
         """
-        name = required_spec.name or name
-        if not name:
+        required_name = required_spec.name or required_name
+        if not required_name:
             raise ValueError(f"Must provide a name for anonymous condition: '{required_spec}'")
 
         if not context:
             context = ConditionContext()
             context.transform_imposed = remove_node
 
-        with spec_with_name(required_spec, name):
+        if imposed_spec:
+            imposed_name = imposed_spec.name or imposed_name
+            if not imposed_name:
+                raise ValueError(f"Must provide a name for imposed constraint: '{imposed_spec}'")
+
+        with named_spec(required_spec, required_name), named_spec(imposed_spec, imposed_name):
             # Check if we can emit the requirements before updating the condition ID counter.
             # In this way, if a condition can't be emitted but the exception is handled in the
             # caller, we won't emit partial facts.
@@ -1562,7 +1601,7 @@ class SpackSolverSetup:
                     continue
 
                 msg = f"{pkg.name} provides {vpkg} when {when}"
-                condition_id = self.condition(when, vpkg, pkg.name, msg)
+                condition_id = self.condition(when, vpkg, required_name=pkg.name, msg=msg)
                 self.gen.fact(
                     fn.pkg_fact(when.name, fn.provider_condition(condition_id, vpkg.name))
                 )
@@ -1570,7 +1609,7 @@ class SpackSolverSetup:
 
         for when, sets_of_virtuals in pkg.provided_together.items():
             condition_id = self.condition(
-                when, name=pkg.name, msg="Virtuals are provided together"
+                when, required_name=pkg.name, msg="Virtuals are provided together"
             )
             for set_id, virtuals_together in enumerate(sets_of_virtuals):
                 for name in virtuals_together:
@@ -1622,7 +1661,7 @@ class SpackSolverSetup:
                 context.transform_required = track_dependencies
                 context.transform_imposed = dependency_holds
 
-                self.condition(cond, dep.spec, name=pkg.name, msg=msg, context=context)
+                self.condition(cond, dep.spec, required_name=pkg.name, msg=msg, context=context)
 
                 self.gen.newline()
 
@@ -1671,7 +1710,9 @@ class SpackSolverSetup:
             if rule.condition != spack.spec.Spec():
                 msg = f"condition to activate requirement {requirement_grp_id}"
                 try:
-                    main_condition_id = self.condition(rule.condition, name=pkg_name, msg=msg)
+                    main_condition_id = self.condition(
+                        rule.condition, required_name=pkg_name, msg=msg
+                    )
                 except Exception as e:
                     if rule.kind != RequirementKind.DEFAULT:
                         raise RuntimeError(
@@ -1712,7 +1753,7 @@ class SpackSolverSetup:
                     member_id = self.condition(
                         required_spec=when_spec,
                         imposed_spec=spec,
-                        name=pkg_name,
+                        required_name=pkg_name,
                         msg=f"{input_spec} is a requirement for package {pkg_name}",
                         context=context,
                     )
@@ -1765,8 +1806,8 @@ class SpackSolverSetup:
             if pkg_name == "all":
                 continue
 
-            # This package does not appear in any repository
-            if pkg_name not in spack.repo.PATH:
+            # package isn't a possible dependency and can't be in the solution
+            if pkg_name not in self.pkgs:
                 continue
 
             # This package is not among possible dependencies
@@ -1846,23 +1887,19 @@ class SpackSolverSetup:
 
         for variant_name in sorted(preferred_variants):
             variant = preferred_variants[variant_name]
-            values = variant.value
-
-            if not isinstance(values, tuple):
-                values = (values,)
 
             # perform validation of the variant and values
-            spec = spack.spec.Spec(pkg_name)
             try:
-                spec.update_variant_validate(variant_name, values)
-            except (spack.variant.InvalidVariantValueError, KeyError, ValueError) as e:
+                variant_defs = vt.prevalidate_variant_value(self.pkg_class(pkg_name), variant)
+            except (vt.InvalidVariantValueError, KeyError, ValueError) as e:
                 tty.debug(
                     f"[SETUP]: rejected {str(variant)} as a preference for {pkg_name}: {str(e)}"
                 )
                 continue
 
-            for value in values:
-                self.variant_values_from_specs.add((pkg_name, variant.name, value))
+            for value in variant.value_as_tuple:
+                for variant_def in variant_defs:
+                    self.variant_values_from_specs.add((pkg_name, id(variant_def), value))
                 self.gen.fact(
                     fn.variant_default_value_from_packages_yaml(pkg_name, variant.name, value)
                 )
@@ -1968,38 +2005,28 @@ class SpackSolverSetup:
 
         # variants
         for vname, variant in sorted(spec.variants.items()):
-            values = variant.value
-            if not isinstance(values, (list, tuple)):
-                values = [values]
+            # TODO: variant="*" means 'variant is defined to something', which used to
+            # be meaningless in concretization, as all variants had to be defined. But
+            # now that variants can be conditional, it should force a variant to exist.
+            if variant.value == ("*",):
+                continue
 
-            for value in values:
-                # * is meaningless for concretization -- just for matching
-                if value == "*":
-                    continue
+            for value in variant.value_as_tuple:
+                # ensure that the value *can* be valid for the spec
+                if spec.name and not spec.concrete and not spec.virtual:
+                    variant_defs = vt.prevalidate_variant_value(
+                        self.pkg_class(spec.name), variant, spec
+                    )
 
-                # validate variant value only if spec not concrete
-                if not spec.concrete:
-                    if not spec.virtual and vname not in spack.variant.reserved_names:
-                        pkg_cls = self.pkg_class(spec.name)
-                        try:
-                            variant_def, _ = pkg_cls.variants[vname]
-                        except KeyError:
-                            msg = 'variant "{0}" not found in package "{1}"'
-                            raise RuntimeError(msg.format(vname, spec.name))
-                        else:
-                            variant_def.validate_or_raise(
-                                variant, spack.repo.PATH.get_pkg_class(spec.name)
-                            )
+                    # Record that that this is a valid possible value. Accounts for
+                    # int/str/etc., where valid values can't be listed in the package
+                    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)))
 
-                # Tell the concretizer that this is a possible value for the
-                # variant, to account for things like int/str values where we
-                # can't enumerate the valid values
-                self.variant_values_from_specs.add((spec.name, vname, value))
-
         # compiler and compiler version
         if spec.compiler:
             clauses.append(f.node_compiler(spec.name, spec.compiler.name))
@@ -2467,15 +2494,15 @@ class SpackSolverSetup:
     def define_variant_values(self):
         """Validate variant values from the command line.
 
-        Also add valid variant values from the command line to the
-        possible values for a variant.
+        Add valid variant values from the command line to the possible values for
+        variant definitions.
 
         """
-        # Tell the concretizer about possible values from specs we saw in
-        # spec_clauses(). We might want to order these facts by pkg and name
-        # if we are debugging.
-        for pkg, variant, value in self.variant_values_from_specs:
-            self.gen.fact(fn.pkg_fact(pkg, fn.variant_possible_value(variant, value)))
+        # Tell the concretizer about possible values from specs seen in spec_clauses().
+        # We might want to order these facts by pkg and name if we are debugging.
+        for pkg_name, variant_def_id, value in self.variant_values_from_specs:
+            vid = self.variant_ids_by_def_id[variant_def_id]
+            self.gen.fact(fn.pkg_fact(pkg_name, fn.variant_possible_value(vid, value)))
 
     def register_concrete_spec(self, spec, possible):
         # tell the solver about any installed packages that could
@@ -2644,6 +2671,10 @@ class SpackSolverSetup:
             self.gen.h2("Package preferences: %s" % pkg)
             self.preferred_variants(pkg)
 
+        self.gen.h1("Special variants")
+        self.define_auto_variant("dev_path", multi=False)
+        self.define_auto_variant("patches", multi=True)
+
         self.gen.h1("Develop specs")
         # Inject dev_path from environment
         for ds in dev_specs:
@@ -2917,6 +2948,9 @@ class ProblemInstanceBuilder:
     def h2(self, header: str) -> None:
         self.title(header, "-")
 
+    def h3(self, header: str):
+        self.asp_problem.append(f"% {header}\n")
+
     def newline(self):
         self.asp_problem.append("\n")
 
@@ -3466,15 +3500,19 @@ class SpecBuilder:
         """
         return NodeArgument(id="0", pkg=pkg)
 
-    def __init__(self, specs, hash_lookup=None):
-        self._specs = {}
+    def __init__(
+        self, specs: List[spack.spec.Spec], *, hash_lookup: Optional[ConcreteSpecsByHash] = None
+    ):
+        self._specs: Dict[NodeArgument, spack.spec.Spec] = {}
         self._result = None
         self._command_line_specs = specs
-        self._flag_sources = collections.defaultdict(lambda: set())
+        self._flag_sources: Dict[Tuple[NodeArgument, str], Set[str]] = collections.defaultdict(
+            lambda: set()
+        )
 
         # Pass in as arguments reusable specs and plug them in
         # from this dictionary during reconstruction
-        self._hash_lookup = hash_lookup or {}
+        self._hash_lookup = hash_lookup or ConcreteSpecsByHash()
 
     def hash(self, node, h):
         if node not in self._specs:
@@ -3505,21 +3543,17 @@ class SpecBuilder:
     def node_target(self, node, target):
         self._arch(node).target = target
 
-    def variant_value(self, node, name, value):
-        # FIXME: is there a way not to special case 'dev_path' everywhere?
-        if name == "dev_path":
-            self._specs[node].variants.setdefault(
-                name, spack.variant.SingleValuedVariant(name, value)
-            )
-            return
-
-        if name == "patches":
-            self._specs[node].variants.setdefault(
-                name, spack.variant.MultiValuedVariant(name, value)
+    def variant_selected(self, node, name, value, variant_type, variant_id):
+        spec = self._specs[node]
+        variant = spec.variants.get(name)
+        if not variant:
+            spec.variants[name] = vt.VariantType(variant_type).variant_class(name, value)
+        else:
+            assert variant_type == vt.VariantType.MULTI.value, (
+                f"Can't have multiple values for single-valued variant: "
+                f"{node}, {name}, {value}, {variant_type}, {variant_id}"
             )
-            return
-
-        self._specs[node].update_variant_validate(name, value)
+            variant.append(value)
 
     def version(self, node, version):
         self._specs[node].versions = vn.VersionList([vn.Version(version)])
@@ -3680,7 +3714,7 @@ class SpecBuilder:
         tty.warn(f'using "{node.pkg}@{version}" which is a deprecated version')
 
     @staticmethod
-    def sort_fn(function_tuple):
+    def sort_fn(function_tuple) -> Tuple[int, int]:
         """Ensure attributes are evaluated in the correct order.
 
         hash attributes are handled first, since they imply entire concrete specs
@@ -3799,7 +3833,7 @@ def _develop_specs_from_env(spec, env):
 
         assert spec.variants["dev_path"].value == path, error_msg
     else:
-        spec.variants.setdefault("dev_path", spack.variant.SingleValuedVariant("dev_path", path))
+        spec.variants.setdefault("dev_path", vt.SingleValuedVariant("dev_path", path))
 
     assert spec.satisfies(dev_info["spec"])
 
diff --git a/lib/spack/spack/solver/concretize.lp b/lib/spack/spack/solver/concretize.lp
index 44e9e213be..2195cd6b08 100644
--- a/lib/spack/spack/solver/concretize.lp
+++ b/lib/spack/spack/solver/concretize.lp
@@ -819,58 +819,132 @@ error(10, Message) :-
 %-----------------------------------------------------------------------------
 % Variant semantics
 %-----------------------------------------------------------------------------
-% a variant is a variant of a package if it is a variant under some condition
-% and that condition holds
-node_has_variant(node(NodeID, Package), Variant) :-
-  pkg_fact(Package, conditional_variant(ID, Variant)),
-  condition_holds(ID, node(NodeID, Package)).
+% Packages define potentially several definitions for each variant, and depending
+% on their attibutes, duplicate nodes for the same package may use different
+% definitions. So the variant logic has several jobs:
+% A. Associate a variant definition with a node, by VariantID
+% B. Associate defaults and attributes (sticky, etc.) for the selected variant ID with the node.
+% C. Once these rules are established for a node, select variant value(s) based on them.
+
+% A: Selecting a variant definition
+
+% Variant definitions come from package facts in two ways:
+% 1. unconditional variants are always defined on all nodes for a given package
+variant_definition(node(NodeID, Package), Name, VariantID) :-
+  pkg_fact(Package, variant_definition(Name, VariantID)),
+  attr("node", node(NodeID, Package)).
+
+% 2. conditional variants are only defined if the conditions hold for the node
+variant_definition(node(NodeID, Package), Name, VariantID) :-
+  pkg_fact(Package, variant_condition(Name, VariantID, ConditionID)),
+  condition_holds(ConditionID, node(NodeID, Package)).
+
+% If there are any definitions for a variant on a node, the variant is "defined".
+variant_defined(PackageNode, Name) :- variant_definition(PackageNode, Name, _).
+
+% We must select one definition for each defined variant on a node.
+1 {
+  node_has_variant(PackageNode, Name, VariantID) : variant_definition(PackageNode, Name, VariantID)
+} 1 :-
+  variant_defined(PackageNode, Name).
+
+% Solver must pick the variant definition with the highest id. When conditions hold
+% 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.
+
+% B: Associating applicable package rules with nodes
 
-node_has_variant(node(ID, Package), Variant) :-
-  pkg_fact(Package, variant(Variant)),
-  attr("node", node(ID, Package)).
+% The default value for a variant in a package is what is prescribed:
+% 1. On the command line
+% 2. In packages.yaml (if there's no command line settings)
+% 3. In the package.py file (if there are no settings in packages.yaml and the command line)
+
+% -- Associate the definition's default values with the node
+% note that the package.py variant defaults are associated with a particular definition, but
+% packages.yaml and CLI are associated with just the variant name.
+% Also, settings specified on the CLI apply to all duplicates, but always have
+% `min_dupe_id` as their node id.
+variant_default_value(node(NodeID, Package), VariantName, Value) :-
+  node_has_variant(node(NodeID, Package), VariantName, VariantID),
+  pkg_fact(Package, variant_default_value_from_package_py(VariantID, Value)),
+  not variant_default_value_from_packages_yaml(Package, VariantName, _),
+  not attr("variant_default_value_from_cli", node(min_dupe_id, Package), VariantName, _).
+
+variant_default_value(node(NodeID, Package), VariantName, Value) :-
+  node_has_variant(node(NodeID, Package), VariantName, _),
+  variant_default_value_from_packages_yaml(Package, VariantName, Value),
+  not attr("variant_default_value_from_cli", node(min_dupe_id, Package), VariantName, _).
+
+variant_default_value(node(NodeID, Package), VariantName, Value) :-
+    node_has_variant(node(NodeID, Package), VariantName, _),
+    attr("variant_default_value_from_cli", node(min_dupe_id, Package), VariantName, Value).
+
+% -- Associate the definition's possible values with the node
+variant_possible_value(node(NodeID, Package), VariantName, Value) :-
+  node_has_variant(node(NodeID, Package), VariantName, VariantID),
+  pkg_fact(Package, variant_possible_value(VariantID, Value)).
+
+variant_value_from_disjoint_sets(node(NodeID, Package), VariantName, Value1, Set1) :-
+  node_has_variant(node(NodeID, Package), VariantName, VariantID),
+  pkg_fact(Package, variant_value_from_disjoint_sets(VariantID, Value1, Set1)).
+
+% -- Associate definition's arity with the node
+variant_single_value(node(NodeID, Package), VariantName) :-
+  node_has_variant(node(NodeID, Package), VariantName, VariantID),
+  not variant_type(VariantID, "multi").
+
+% C: Determining variant values on each node
+
+% if a variant is sticky, but not set, its value is the default value
+attr("variant_selected", node(ID, Package), Variant, Value, VariantType, VariantID) :-
+  node_has_variant(node(ID, Package), Variant, VariantID),
+  variant_default_value(node(ID, Package), Variant, Value),
+  pkg_fact(Package, variant_sticky(VariantID)),
+  variant_type(VariantID, VariantType),
+  not attr("variant_set", node(ID, Package), Variant),
+  build(node(ID, Package)).
+
+% we can choose variant values from all the possible values for the node
+{
+  attr("variant_selected", node(ID, Package), Variant, Value, VariantType, VariantID)
+  : variant_possible_value(node(ID, Package), Variant, Value)
+} :-
+  attr("node", node(ID, Package)),
+  node_has_variant(node(ID, Package), Variant, VariantID),
+  variant_type(VariantID, VariantType),
+  build(node(ID, Package)).
+
+% variant_selected is only needed for reconstruction on the python side, so we can ignore it here
+attr("variant_value", PackageNode, Variant, Value) :-
+  attr("variant_selected", PackageNode, Variant, Value, VariantType, VariantID).
 
 % a variant cannot be set if it is not a variant on the package
 error(100, "Cannot set variant '{0}' for package '{1}' because the variant condition cannot be satisfied for the given spec", Variant, Package)
-  :- attr("variant_set", node(X, Package), Variant),
-     not node_has_variant(node(X, Package), Variant),
-     build(node(X, Package)).
+  :- attr("variant_set", node(ID, Package), Variant),
+     not node_has_variant(node(ID, Package), Variant, _),
+     build(node(ID, Package)).
 
 % a variant cannot take on a value if it is not a variant of the package
 error(100, "Cannot set variant '{0}' for package '{1}' because the variant condition cannot be satisfied for the given spec", Variant, Package)
-  :- attr("variant_value", node(X, Package), Variant, _),
-     not node_has_variant(node(X, Package), Variant),
-     build(node(X, Package)).
-
-% if a variant is sticky and not set its value is the default value
-attr("variant_value", node(ID, Package), Variant, Value) :-
-  node_has_variant(node(ID, Package), Variant),
-  not attr("variant_set", node(ID, Package), Variant),
-  pkg_fact(Package, variant_sticky(Variant)),
-  variant_default_value(Package, Variant, Value),
-  build(node(ID, Package)).
+  :- attr("variant_value", node(ID, Package), Variant, _),
+     not node_has_variant(node(ID, Package), Variant, _),
+     build(node(ID, Package)).
 
 % at most one variant value for single-valued variants.
-{
-  attr("variant_value", node(ID, Package), Variant, Value)
-  : pkg_fact(Package, variant_possible_value(Variant, Value))
-}
- :- attr("node", node(ID, Package)),
-    node_has_variant(node(ID, Package), Variant),
-    build(node(ID, Package)).
-
-
 error(100, "'{0}' required multiple values for single-valued variant '{1}'", Package, Variant)
   :- attr("node", node(ID, Package)),
-     node_has_variant(node(ID, Package), Variant),
-     pkg_fact(Package, variant_single_value(Variant)),
+     node_has_variant(node(ID, Package), Variant, _),
+     variant_single_value(node(ID, Package), Variant),
      build(node(ID, Package)),
      2 { attr("variant_value", node(ID, Package), Variant, Value) }.
 
 error(100, "No valid value for variant '{1}' of package '{0}'", Package, Variant)
-  :- attr("node", node(X, Package)),
-     node_has_variant(node(X, Package), Variant),
-     build(node(X, Package)),
-     not attr("variant_value", node(X, Package), Variant, _).
+  :- attr("node", node(ID, Package)),
+     node_has_variant(node(ID, Package), Variant, _),
+     build(node(ID, Package)),
+     not attr("variant_value", node(ID, Package), Variant, _).
 
 % if a variant is set to anything, it is considered 'set'.
 attr("variant_set", PackageNode, Variant) :- attr("variant_set", PackageNode, Variant, _).
@@ -880,17 +954,16 @@ attr("variant_set", PackageNode, Variant) :- attr("variant_set", PackageNode, Va
 % have been built w/different variants from older/different package versions.
 error(10, "'Spec({1}={2})' is not a valid value for '{0}' variant '{1}'", Package, Variant, Value)
  :- attr("variant_value", node(ID, Package), Variant, Value),
-    not pkg_fact(Package, variant_possible_value(Variant, Value)),
+    not variant_possible_value(node(ID, Package), Variant, Value),
     build(node(ID, Package)).
 
-% Some multi valued variants accept multiple values from disjoint sets.
-% Ensure that we respect that constraint and we don't pick values from more
-% than one set at once
+% Some multi valued variants accept multiple values from disjoint sets. Ensure that we
+% respect that constraint and we don't pick values from more than one set at once
 error(100, "{0} variant '{1}' cannot have values '{2}' and '{3}' as they come from disjoint value sets", Package, Variant, Value1, Value2)
   :- attr("variant_value", node(ID, Package), Variant, Value1),
      attr("variant_value", node(ID, Package), Variant, Value2),
-     pkg_fact(Package, variant_value_from_disjoint_sets(Variant, Value1, Set1)),
-     pkg_fact(Package, variant_value_from_disjoint_sets(Variant, Value2, Set2)),
+     variant_value_from_disjoint_sets(node(ID, Package), Variant, Value1, Set1),
+     variant_value_from_disjoint_sets(node(ID, Package), Variant, Value2, Set2),
      Set1 < Set2, % see[1]
      build(node(ID, Package)).
 
@@ -902,7 +975,7 @@ error(100, "{0} variant '{1}' cannot have values '{2}' and '{3}' as they come fr
 % specified in an external, we score it as if it was a default value.
 variant_not_default(node(ID, Package), Variant, Value)
  :- attr("variant_value", node(ID, Package), Variant, Value),
-    not variant_default_value(Package, Variant, Value),
+    not variant_default_value(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
@@ -913,11 +986,10 @@ variant_not_default(node(ID, Package), Variant, Value)
     not external_with_variant_set(node(ID, Package), Variant, Value),
     attr("node", node(ID, Package)).
 
-
 % A default variant value that is not used
 variant_default_not_used(node(ID, Package), Variant, Value)
-  :- variant_default_value(Package, Variant, Value),
-     node_has_variant(node(ID, Package), Variant),
+  :- 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, _)),
      attr("node", node(ID, Package)).
@@ -931,25 +1003,6 @@ external_with_variant_set(node(NodeID, Package), Variant, Value)
     external(node(NodeID, Package)),
     attr("node", node(NodeID, Package)).
 
-% The default value for a variant in a package is what is prescribed:
-%
-% 1. On the command line
-% 2. In packages.yaml (if there's no command line settings)
-% 3. In the package.py file (if there are no settings in
-%    packages.yaml and the command line)
-%
-variant_default_value(Package, Variant, Value)
- :- pkg_fact(Package, variant_default_value_from_package_py(Variant, Value)),
-    not variant_default_value_from_packages_yaml(Package, Variant, _),
-    not attr("variant_default_value_from_cli", node(min_dupe_id, Package), Variant, _).
-
-variant_default_value(Package, Variant, Value)
- :- variant_default_value_from_packages_yaml(Package, Variant, Value),
-    not attr("variant_default_value_from_cli", node(min_dupe_id, Package), Variant, _).
-
-variant_default_value(Package, Variant, Value) :-
-    attr("variant_default_value_from_cli", node(min_dupe_id, Package), Variant, Value).
-
 % Treat 'none' in a special way - it cannot be combined with other
 % values even if the variant is multi-valued
 error(100, "{0} variant '{1}' cannot have values '{2}' and 'none'", Package, Variant, Value)
@@ -958,23 +1011,26 @@ error(100, "{0} variant '{1}' cannot have values '{2}' and 'none'", Package, Var
     Value != "none",
     build(node(X, Package)).
 
-% patches and dev_path are special variants -- they don't have to be
-% declared in the package, so we just allow them to spring into existence
-% when assigned a value.
-auto_variant("dev_path").
-auto_variant("patches").
+% -- Auto variants
+% These don't have to be declared in the package. We allow them to spring into
+% existence when assigned a value.
+variant_possible_value(PackageNode, Variant, Value)
+  :- attr("variant_set", PackageNode, Variant, Value), auto_variant(Variant, _).
 
-node_has_variant(PackageNode, Variant)
-  :- attr("variant_set", PackageNode, Variant, _), auto_variant(Variant).
+node_has_variant(PackageNode, Variant, VariantID)
+  :- attr("variant_set", PackageNode, Variant, _), auto_variant(Variant, VariantID).
 
-pkg_fact(Package, variant_single_value("dev_path"))
-  :- attr("variant_set", node(ID, Package), "dev_path", _).
+variant_single_value(PackageNode, Variant)
+  :- node_has_variant(PackageNode, Variant, VariantID),
+     auto_variant(Variant, VariantID),
+     not variant_type(VariantID, "multi").
 
 % suppress warnings about this atom being unset.  It's only set if some
 % spec or some package sets it, and without this, clingo will give
 % warnings like 'info: atom does not occur in any rule head'.
 #defined variant_default_value/3.
 #defined variant_default_value_from_packages_yaml/3.
+#defined variant_default_value_from_package_py/3.
 
 %-----------------------------------------------------------------------------
 % Propagation semantics
@@ -1004,11 +1060,12 @@ propagate(ChildNode, PropagatedAttribute, edge_types(DepType1, DepType2)) :-
 %----
 
 % If a variant is propagated, and can be accepted, set its value
-attr("variant_value", node(ID, Package), Variant, Value) :-
-  propagate(node(ID, Package), variant_value(Variant, Value)),
-  node_has_variant(node(ID, Package), Variant),
-  pkg_fact(Package, variant_possible_value(Variant, Value)),
-  not attr("variant_set", node(ID, Package), Variant).
+attr("variant_selected", PackageNode, Variant, Value, VariantType, VariantID) :-
+  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).
 
 % If a variant is propagated, we cannot have extraneous values
 variant_is_propagated(PackageNode, Variant) :-
@@ -1017,7 +1074,7 @@ variant_is_propagated(PackageNode, Variant) :-
   not attr("variant_set", PackageNode, Variant).
 
 :- variant_is_propagated(PackageNode, Variant),
-   attr("variant_value", PackageNode, Variant, Value),
+   attr("variant_selected", PackageNode, Variant, Value, _, _),
    not propagate(PackageNode, variant_value(Variant, Value)).
 
 %----
diff --git a/lib/spack/spack/solver/display.lp b/lib/spack/spack/solver/display.lp
index fb3b2c41df..675a9d17d2 100644
--- a/lib/spack/spack/solver/display.lp
+++ b/lib/spack/spack/solver/display.lp
@@ -14,6 +14,7 @@
 #show attr/3.
 #show attr/4.
 #show attr/5.
+#show attr/6.
 
 % names of optimization criteria
 #show opt_criterion/2.
@@ -39,7 +40,7 @@
 #show condition_requirement/4.
 #show condition_requirement/5.
 #show condition_requirement/6.
-#show node_has_variant/2.
+#show node_has_variant/3.
 #show build/1.
 #show external/1.
 #show external_version/3.
@@ -49,5 +50,6 @@
 #show condition_nodes/3.
 #show trigger_node/3.
 #show imposed_nodes/3.
+#show variant_single_value/2.
 
 % debug
diff --git a/lib/spack/spack/solver/error_messages.lp b/lib/spack/spack/solver/error_messages.lp
index 79a9b4b7eb..7bc9ed2e93 100644
--- a/lib/spack/spack/solver/error_messages.lp
+++ b/lib/spack/spack/solver/error_messages.lp
@@ -5,6 +5,10 @@
 
 %=============================================================================
 % This logic program adds detailed error messages to Spack's concretizer
+%
+% Note that functions used in rule bodies here need to have a corresponding
+% #show line in display.lp, otherwise they won't be passed through to the
+% error solve.
 %=============================================================================
 
 #program error_messages.
@@ -113,12 +117,11 @@ error(0, "Cannot find a valid provider for virtual {0}", Virtual, startcauses, C
      pkg_fact(TriggerPkg, condition_effect(Cause, EID)),
      condition_holds(Cause, node(CID, TriggerPkg)).
 
-
 % At most one variant value for single-valued variants
 error(0, "'{0}' required multiple values for single-valued variant '{1}'\n    Requested 'Spec({1}={2})' and 'Spec({1}={3})'", Package, Variant, Value1, Value2, startcauses, Cause1, X, Cause2, X)
   :- attr("node", node(X, Package)),
-     node_has_variant(node(X, Package), Variant),
-     pkg_fact(Package, variant_single_value(Variant)),
+     node_has_variant(node(X, Package), Variant, VariantID),
+     variant_single_value(node(X, Package), Variant),
      build(node(X, Package)),
      attr("variant_value", node(X, Package), Variant, Value1),
      imposed_constraint(EID1, "variant_set", Package, Variant, Value1),
@@ -216,6 +219,11 @@ error(0, Msg, startcauses, TriggerID, ID1, ConstraintID, ID2)
 #defined error/4.
 #defined error/5.
 #defined error/6.
+#defined error/7.
+#defined error/8.
+#defined error/9.
+#defined error/10.
+#defined error/11.
 #defined attr/2.
 #defined attr/3.
 #defined attr/4.
@@ -225,6 +233,7 @@ error(0, Msg, startcauses, TriggerID, ID1, ConstraintID, ID2)
 #defined imposed_constraint/4.
 #defined imposed_constraint/5.
 #defined imposed_constraint/6.
+#defined condition_cause/4.
 #defined condition_requirement/3.
 #defined condition_requirement/4.
 #defined condition_requirement/5.
@@ -234,6 +243,7 @@ error(0, Msg, startcauses, TriggerID, ID1, ConstraintID, ID2)
 #defined external/1.
 #defined trigger_and_effect/3.
 #defined build/1.
-#defined node_has_variant/2.
+#defined node_has_variant/3.
 #defined provider/2.
 #defined external_version/3.
+#defined variant_single_value/2.
diff --git a/lib/spack/spack/spec.py b/lib/spack/spack/spec.py
index 492841f81a..28e11d68b8 100644
--- a/lib/spack/spack/spec.py
+++ b/lib/spack/spack/spec.py
@@ -2367,14 +2367,16 @@ class Spec:
         package_cls = spack.repo.PATH.get_pkg_class(new_spec.name)
         if change_spec.versions and not change_spec.versions == vn.any_version:
             new_spec.versions = change_spec.versions
-        for variant, value in change_spec.variants.items():
-            if variant in package_cls.variants:
-                if variant in new_spec.variants:
+
+        for vname, value in change_spec.variants.items():
+            if vname in package_cls.variant_names():
+                if vname in new_spec.variants:
                     new_spec.variants.substitute(value)
                 else:
-                    new_spec.variants[variant] = value
+                    new_spec.variants[vname] = value
             else:
-                raise ValueError("{0} is not a variant of {1}".format(variant, new_spec.name))
+                raise ValueError("{0} is not a variant of {1}".format(vname, new_spec.name))
+
         if change_spec.compiler:
             new_spec.compiler = change_spec.compiler
         if change_spec.compiler_flags:
@@ -2962,48 +2964,14 @@ class Spec:
             return
 
         pkg_cls = spec.package_class
-        pkg_variants = pkg_cls.variants
+        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))
         if not_existing:
-            raise vt.UnknownVariantError(spec, not_existing)
-
-    def update_variant_validate(self, variant_name, values):
-        """If it is not already there, adds the variant named
-        `variant_name` to the spec `spec` based on the definition
-        contained in the package metadata. Validates the variant and
-        values before returning.
-
-        Used to add values to a variant without being sensitive to the
-        variant being single or multi-valued. If the variant already
-        exists on the spec it is assumed to be multi-valued and the
-        values are appended.
-
-        Args:
-           variant_name: the name of the variant to add or append to
-           values: the value or values (as a tuple) to add/append
-                   to the variant
-        """
-        if not isinstance(values, tuple):
-            values = (values,)
-
-        pkg_variant, _ = self.package_class.variants[variant_name]
-
-        for value in values:
-            if self.variants.get(variant_name):
-                msg = (
-                    f"cannot append the new value '{value}' to the single-valued "
-                    f"variant '{self.variants[variant_name]}'"
-                )
-                assert pkg_variant.multi, msg
-                self.variants[variant_name].append(value)
-            else:
-                variant = pkg_variant.make_variant(value)
-                self.variants[variant_name] = variant
-
-        pkg_cls = spack.repo.PATH.get_pkg_class(self.name)
-        pkg_variant.validate_or_raise(self.variants[variant_name], pkg_cls)
+            raise vt.UnknownVariantError(
+                f"No such variant {not_existing} for spec: '{spec}'", list(not_existing)
+            )
 
     def constrain(self, other, deps=True):
         """Intersect self with other in-place. Return True if self changed, False otherwise.
@@ -4447,7 +4415,9 @@ class VariantMap(lang.HashableMap):
         Returns:
             bool: True or False
         """
-        return self.spec._concrete or all(v in self for v in self.spec.package_class.variants)
+        return self.spec._concrete or all(
+            v in self for v in self.spec.package_class.variant_names()
+        )
 
     def copy(self) -> "VariantMap":
         clone = VariantMap(self.spec)
@@ -4485,7 +4455,7 @@ class VariantMap(lang.HashableMap):
 
 def substitute_abstract_variants(spec: Spec):
     """Uses the information in `spec.package` to turn any variant that needs
-    it into a SingleValuedVariant.
+    it into a SingleValuedVariant or BoolValuedVariant.
 
     This method is best effort. All variants that can be substituted will be
     substituted before any error is raised.
@@ -4493,26 +4463,45 @@ def substitute_abstract_variants(spec: Spec):
     Args:
         spec: spec on which to operate the substitution
     """
-    # This method needs to be best effort so that it works in matrix exlusion
+    # This method needs to be best effort so that it works in matrix exclusion
     # in $spack/lib/spack/spack/spec_list.py
-    failed = []
+    unknown = []
     for name, v in spec.variants.items():
         if name == "dev_path":
             spec.variants.substitute(vt.SingleValuedVariant(name, v._original_value))
             continue
         elif name in vt.reserved_names:
             continue
-        elif name not in spec.package_class.variants:
-            failed.append(name)
+
+        variant_defs = spec.package_class.variant_definitions(name)
+        valid_defs = []
+        for when, vdef in variant_defs:
+            if when.intersects(spec):
+                valid_defs.append(vdef)
+
+        if not valid_defs:
+            if name not in spec.package_class.variant_names():
+                unknown.append(name)
+            else:
+                whens = [str(when) for when, _ in variant_defs]
+                raise InvalidVariantForSpecError(v.name, f"({', '.join(whens)})", spec)
+            continue
+
+        pkg_variant, *rest = valid_defs
+        if rest:
             continue
-        pkg_variant, _ = spec.package_class.variants[name]
+
         new_variant = pkg_variant.make_variant(v._original_value)
-        pkg_variant.validate_or_raise(new_variant, spec.package_class)
+        pkg_variant.validate_or_raise(new_variant, spec.name)
         spec.variants.substitute(new_variant)
 
-    # Raise all errors at once
-    if failed:
-        raise vt.UnknownVariantError(spec, failed)
+    if unknown:
+        variants = llnl.string.plural(len(unknown), "variant")
+        raise vt.UnknownVariantError(
+            f"Tried to set {variants} {llnl.string.comma_and(unknown)}. "
+            f"{spec.name} has no such {variants}",
+            unknown_variants=unknown,
+        )
 
 
 def parse_with_version_concrete(spec_like: Union[str, Spec], compiler: bool = False):
@@ -4942,6 +4931,15 @@ class SpecParseError(spack.error.SpecError):
         )
 
 
+class InvalidVariantForSpecError(spack.error.SpecError):
+    """Raised when an invalid conditional variant is specified."""
+
+    def __init__(self, variant, when, spec):
+        msg = f"Invalid variant {variant} for spec {spec}.\n"
+        msg += f"{variant} is only available for {spec.name} when satisfying one of {when}."
+        super().__init__(msg)
+
+
 class UnsupportedPropagationError(spack.error.SpecError):
     """Raised when propagation (==) is used with reserved variant names."""
 
diff --git a/lib/spack/spack/test/concretize.py b/lib/spack/spack/test/concretize.py
index 7aaa2bc7f5..ef004272a7 100644
--- a/lib/spack/spack/test/concretize.py
+++ b/lib/spack/spack/test/concretize.py
@@ -53,7 +53,7 @@ def check_spec(abstract, concrete):
             cflag = concrete.compiler_flags[flag]
             assert set(aflag) <= set(cflag)
 
-    for name in spack.repo.PATH.get_pkg_class(abstract.name).variants:
+    for name in spack.repo.PATH.get_pkg_class(abstract.name).variant_names():
         assert name in concrete.variants
 
     for flag in concrete.compiler_flags.valid_compiler_flags():
@@ -931,7 +931,9 @@ class TestConcretize:
         ],
     )
     def test_conditional_variants_fail(self, bad_spec):
-        with pytest.raises((spack.error.UnsatisfiableSpecError, vt.InvalidVariantForSpecError)):
+        with pytest.raises(
+            (spack.error.UnsatisfiableSpecError, spack.spec.InvalidVariantForSpecError)
+        ):
             _ = Spec("conditional-variant-pkg" + bad_spec).concretized()
 
     @pytest.mark.parametrize(
@@ -1374,7 +1376,7 @@ class TestConcretize:
     )
     def test_error_message_for_inconsistent_variants(self, spec_str):
         s = Spec(spec_str)
-        with pytest.raises(RuntimeError, match="not found in package"):
+        with pytest.raises(vt.UnknownVariantError):
             s.concretize()
 
     @pytest.mark.regression("22533")
diff --git a/lib/spack/spack/test/spec_semantics.py b/lib/spack/spack/test/spec_semantics.py
index a7f4383bc6..d6e7e168af 100644
--- a/lib/spack/spack/test/spec_semantics.py
+++ b/lib/spack/spack/test/spec_semantics.py
@@ -234,6 +234,16 @@ class TestSpecSemantics:
                 'libelf cflags="-O3" cppflags="-Wall"',
                 'libelf cflags="-O3" cppflags="-Wall"',
             ),
+            (
+                "libelf patches=ba5e334fe247335f3a116decfb5284100791dc302b5571ff5e664d8f9a6806c2",
+                "libelf patches=ba5e3",  # constrain by a patch sha256 prefix
+                # TODO: the result below is not ideal. Prefix satisfies() works for patches, but
+                # constrain() isn't similarly special-cased to do the same thing
+                (
+                    "libelf patches=ba5e3,"
+                    "ba5e334fe247335f3a116decfb5284100791dc302b5571ff5e664d8f9a6806c2"
+                ),
+            ),
         ],
     )
     def test_abstract_specs_can_constrain_each_other(self, lhs, rhs, expected):
@@ -1076,7 +1086,7 @@ class TestSpecSemantics:
     @pytest.mark.regression("13124")
     def test_error_message_unknown_variant(self):
         s = Spec("mpileaks +unknown")
-        with pytest.raises(UnknownVariantError, match=r"package has no such"):
+        with pytest.raises(UnknownVariantError):
             s.concretize()
 
     @pytest.mark.regression("18527")
@@ -1115,6 +1125,20 @@ class TestSpecSemantics:
         assert new_spec.compiler_flags["cflags"] == ["-O2"]
         assert new_spec.compiler_flags["cxxflags"] == ["-O1"]
 
+    def test_spec_override_with_nonexisting_variant(self):
+        init_spec = Spec("pkg-a foo=baz foobar=baz cflags=-O3 cxxflags=-O1")
+        change_spec = Spec("pkg-a baz=fee")
+        with pytest.raises(ValueError):
+            Spec.override(init_spec, change_spec)
+
+    def test_spec_override_with_variant_not_in_init_spec(self):
+        init_spec = Spec("pkg-a foo=baz foobar=baz cflags=-O3 cxxflags=-O1")
+        change_spec = Spec("pkg-a +bvv ~lorem_ipsum")
+        new_spec = Spec.override(init_spec, change_spec)
+        new_spec.concretize()
+        assert "+bvv" in new_spec
+        assert "~lorem_ipsum" in new_spec
+
     @pytest.mark.parametrize(
         "spec_str,specs_in_dag",
         [
diff --git a/lib/spack/spack/test/variant.py b/lib/spack/spack/test/variant.py
index d44aacee5e..c4c439b86f 100644
--- a/lib/spack/spack/test/variant.py
+++ b/lib/spack/spack/test/variant.py
@@ -7,9 +7,12 @@ import numbers
 import pytest
 
 import spack.error
+import spack.repo
+import spack.spec
 import spack.variant
-from spack.spec import VariantMap
+from spack.spec import Spec, VariantMap
 from spack.variant import (
+    AbstractVariant,
     BoolValuedVariant,
     DuplicateVariantError,
     InconsistentValidationError,
@@ -541,7 +544,7 @@ class TestVariant:
         )
         # Valid vspec, shouldn't raise
         vspec = a.make_variant("bar")
-        a.validate_or_raise(vspec)
+        a.validate_or_raise(vspec, "test-package")
 
         # Multiple values are not allowed
         with pytest.raises(MultipleValuesInExclusiveVariantError):
@@ -550,16 +553,16 @@ class TestVariant:
         # Inconsistent vspec
         vspec.name = "FOO"
         with pytest.raises(InconsistentValidationError):
-            a.validate_or_raise(vspec)
+            a.validate_or_raise(vspec, "test-package")
 
         # Valid multi-value vspec
         a.multi = True
         vspec = a.make_variant("bar,baz")
-        a.validate_or_raise(vspec)
+        a.validate_or_raise(vspec, "test-package")
         # Add an invalid value
         vspec.value = "bar,baz,barbaz"
         with pytest.raises(InvalidVariantValueError):
-            a.validate_or_raise(vspec)
+            a.validate_or_raise(vspec, "test-package")
 
     def test_callable_validator(self):
         def validator(x):
@@ -570,12 +573,12 @@ class TestVariant:
 
         a = Variant("foo", default=1024, description="", values=validator, multi=False)
         vspec = a.make_default()
-        a.validate_or_raise(vspec)
+        a.validate_or_raise(vspec, "test-package")
         vspec.value = 2056
-        a.validate_or_raise(vspec)
+        a.validate_or_raise(vspec, "test-package")
         vspec.value = "foo"
         with pytest.raises(InvalidVariantValueError):
-            a.validate_or_raise(vspec)
+            a.validate_or_raise(vspec, "test-package")
 
     def test_representation(self):
         a = Variant(
@@ -583,11 +586,22 @@ class TestVariant:
         )
         assert a.allowed_values == "bar, baz, foobar"
 
+    def test_str(self):
+        string = str(
+            Variant(
+                "foo", default="", description="", values=("bar", "baz", "foobar"), multi=False
+            )
+        )
+        assert "'foo'" in string
+        assert "default=''" in string
+        assert "description=''" in string
+        assert "values=('foo', 'bar', 'baz') in string"
+
 
 class TestVariantMapTest:
-    def test_invalid_values(self):
+    def test_invalid_values(self) -> None:
         # Value with invalid type
-        a = VariantMap(None)
+        a = VariantMap(Spec())
         with pytest.raises(TypeError):
             a["foo"] = 2
 
@@ -606,17 +620,17 @@ class TestVariantMapTest:
         with pytest.raises(KeyError):
             a["bar"] = MultiValuedVariant("foo", "bar")
 
-    def test_set_item(self):
+    def test_set_item(self) -> None:
         # Check that all the three types of variants are accepted
-        a = VariantMap(None)
+        a = VariantMap(Spec())
 
         a["foo"] = BoolValuedVariant("foo", True)
         a["bar"] = SingleValuedVariant("bar", "baz")
         a["foobar"] = MultiValuedVariant("foobar", "a, b, c, d, e")
 
-    def test_substitute(self):
+    def test_substitute(self) -> None:
         # Check substitution of a key that exists
-        a = VariantMap(None)
+        a = VariantMap(Spec())
         a["foo"] = BoolValuedVariant("foo", True)
         a.substitute(SingleValuedVariant("foo", "bar"))
 
@@ -625,15 +639,15 @@ class TestVariantMapTest:
         with pytest.raises(KeyError):
             a.substitute(BoolValuedVariant("bar", True))
 
-    def test_satisfies_and_constrain(self):
+    def test_satisfies_and_constrain(self) -> None:
         # foo=bar foobar=fee feebar=foo
-        a = VariantMap(None)
+        a = VariantMap(Spec())
         a["foo"] = MultiValuedVariant("foo", "bar")
         a["foobar"] = SingleValuedVariant("foobar", "fee")
         a["feebar"] = SingleValuedVariant("feebar", "foo")
 
         # foo=bar,baz foobar=fee shared=True
-        b = VariantMap(None)
+        b = VariantMap(Spec())
         b["foo"] = MultiValuedVariant("foo", "bar, baz")
         b["foobar"] = SingleValuedVariant("foobar", "fee")
         b["shared"] = BoolValuedVariant("shared", True)
@@ -645,7 +659,7 @@ class TestVariantMapTest:
         assert not b.satisfies(a)
 
         # foo=bar,baz foobar=fee feebar=foo shared=True
-        c = VariantMap(None)
+        c = VariantMap(Spec())
         c["foo"] = MultiValuedVariant("foo", "bar, baz")
         c["foobar"] = SingleValuedVariant("foobar", "fee")
         c["feebar"] = SingleValuedVariant("feebar", "foo")
@@ -654,8 +668,8 @@ class TestVariantMapTest:
         assert a.constrain(b)
         assert a == c
 
-    def test_copy(self):
-        a = VariantMap(None)
+    def test_copy(self) -> None:
+        a = VariantMap(Spec())
         a["foo"] = BoolValuedVariant("foo", True)
         a["bar"] = SingleValuedVariant("bar", "baz")
         a["foobar"] = MultiValuedVariant("foobar", "a, b, c, d, e")
@@ -663,14 +677,31 @@ class TestVariantMapTest:
         c = a.copy()
         assert a == c
 
-    def test_str(self):
-        c = VariantMap(None)
+    def test_str(self) -> None:
+        c = VariantMap(Spec())
         c["foo"] = MultiValuedVariant("foo", "bar, baz")
         c["foobar"] = SingleValuedVariant("foobar", "fee")
         c["feebar"] = SingleValuedVariant("feebar", "foo")
         c["shared"] = BoolValuedVariant("shared", True)
         assert str(c) == "+shared feebar=foo foo=bar,baz foobar=fee"
 
+    def test_concrete(self, mock_packages, config) -> None:
+        spec = Spec("pkg-a")
+        vm = VariantMap(spec)
+        assert not vm.concrete
+
+        # concrete if associated spec is concrete
+        spec.concretize()
+        assert vm.concrete
+
+        # concrete if all variants are present (even if spec not concrete)
+        spec._mark_concrete(False)
+        assert spec.variants.concrete
+
+        # remove a variant to test the condition
+        del spec.variants["foo"]
+        assert not spec.variants.concrete
+
 
 def test_disjoint_set_initialization_errors():
     # Constructing from non-disjoint sets should raise an exception
@@ -765,9 +796,154 @@ def test_wild_card_valued_variants_equivalent_to_str():
     several_arbitrary_values = ("doe", "re", "mi")
     # "*" case
     wild_output = wild_var.make_variant(several_arbitrary_values)
-    wild_var.validate_or_raise(wild_output)
+    wild_var.validate_or_raise(wild_output, "test-package")
     # str case
     str_output = str_var.make_variant(several_arbitrary_values)
-    str_var.validate_or_raise(str_output)
+    str_var.validate_or_raise(str_output, "test-package")
     # equivalence each instance already validated
     assert str_output.value == wild_output.value
+
+
+def test_variant_definitions(mock_packages):
+    pkg = spack.repo.PATH.get_pkg_class("variant-values")
+
+    # two variant names
+    assert len(pkg.variant_names()) == 2
+    assert "build_system" in pkg.variant_names()
+    assert "v" in pkg.variant_names()
+
+    # this name doesn't exist
+    assert len(pkg.variant_definitions("no-such-variant")) == 0
+
+    # there are 4 definitions but one is completely shadowed by another
+    assert len(pkg.variants) == 4
+
+    # variant_items ignores the shadowed definition
+    assert len(list(pkg.variant_items())) == 3
+
+    # variant_definitions also ignores the shadowed definition
+    defs = [vdef for _, vdef in pkg.variant_definitions("v")]
+    assert len(defs) == 2
+    assert defs[0].default == "foo"
+    assert defs[0].values == ("foo",)
+
+    assert defs[1].default == "bar"
+    assert defs[1].values == ("foo", "bar")
+
+
+@pytest.mark.parametrize(
+    "pkg_name,value,spec,def_ids",
+    [
+        ("variant-values", "foo", "", [0, 1]),
+        ("variant-values", "bar", "", [1]),
+        ("variant-values", "foo", "@1.0", [0]),
+        ("variant-values", "foo", "@2.0", [1]),
+        ("variant-values", "foo", "@3.0", [1]),
+        ("variant-values", "foo", "@4.0", []),
+        ("variant-values", "bar", "@2.0", [1]),
+        ("variant-values", "bar", "@3.0", [1]),
+        ("variant-values", "bar", "@4.0", []),
+        # now with a global override
+        ("variant-values-override", "bar", "", [0]),
+        ("variant-values-override", "bar", "@1.0", [0]),
+        ("variant-values-override", "bar", "@2.0", [0]),
+        ("variant-values-override", "bar", "@3.0", [0]),
+        ("variant-values-override", "bar", "@4.0", [0]),
+        ("variant-values-override", "baz", "", [0]),
+        ("variant-values-override", "baz", "@2.0", [0]),
+        ("variant-values-override", "baz", "@3.0", [0]),
+        ("variant-values-override", "baz", "@4.0", [0]),
+    ],
+)
+def test_prevalidate_variant_value(mock_packages, pkg_name, value, spec, def_ids):
+    pkg = spack.repo.PATH.get_pkg_class(pkg_name)
+
+    all_defs = [vdef for _, vdef in pkg.variant_definitions("v")]
+
+    valid_defs = spack.variant.prevalidate_variant_value(
+        pkg, SingleValuedVariant("v", value), spack.spec.Spec(spec)
+    )
+    assert len(valid_defs) == len(def_ids)
+
+    for vdef, i in zip(valid_defs, def_ids):
+        assert vdef is all_defs[i]
+
+
+@pytest.mark.parametrize(
+    "pkg_name,value,spec",
+    [
+        ("variant-values", "baz", ""),
+        ("variant-values", "bar", "@1.0"),
+        ("variant-values", "bar", "@4.0"),
+        ("variant-values", "baz", "@3.0"),
+        ("variant-values", "baz", "@4.0"),
+        # and with override
+        ("variant-values-override", "foo", ""),
+        ("variant-values-override", "foo", "@1.0"),
+        ("variant-values-override", "foo", "@2.0"),
+        ("variant-values-override", "foo", "@3.0"),
+        ("variant-values-override", "foo", "@4.0"),
+    ],
+)
+def test_strict_invalid_variant_values(mock_packages, pkg_name, value, spec):
+    pkg = spack.repo.PATH.get_pkg_class(pkg_name)
+
+    with pytest.raises(spack.variant.InvalidVariantValueError):
+        spack.variant.prevalidate_variant_value(
+            pkg, SingleValuedVariant("v", value), spack.spec.Spec(spec), strict=True
+        )
+
+
+@pytest.mark.parametrize(
+    "pkg_name,spec,satisfies,def_id",
+    [
+        ("variant-values", "@1.0", "v=foo", 0),
+        ("variant-values", "@2.0", "v=bar", 1),
+        ("variant-values", "@3.0", "v=bar", 1),
+        ("variant-values-override", "@1.0", "v=baz", 0),
+        ("variant-values-override", "@2.0", "v=baz", 0),
+        ("variant-values-override", "@3.0", "v=baz", 0),
+    ],
+)
+def test_concretize_variant_default_with_multiple_defs(
+    mock_packages, config, pkg_name, spec, satisfies, def_id
+):
+    pkg = spack.repo.PATH.get_pkg_class(pkg_name)
+    pkg_defs = [vdef for _, vdef in pkg.variant_definitions("v")]
+
+    spec = spack.spec.Spec(f"{pkg_name}{spec}").concretized()
+    assert spec.satisfies(satisfies)
+    assert spec.package.get_variant("v") is pkg_defs[def_id]
+
+
+@pytest.mark.parametrize(
+    "spec,variant_name,after",
+    [
+        # dev_path is a special case
+        ("foo dev_path=/path/to/source", "dev_path", SingleValuedVariant),
+        # reserved name: won't be touched
+        ("foo patches=2349dc44", "patches", AbstractVariant),
+        # simple case -- one definition applies
+        ("variant-values@1.0 v=foo", "v", SingleValuedVariant),
+        # simple, but with bool valued variant
+        ("pkg-a bvv=true", "bvv", BoolValuedVariant),
+        # variant doesn't exist at version
+        ("variant-values@4.0 v=bar", "v", spack.spec.InvalidVariantForSpecError),
+        # multiple definitions, so not yet knowable
+        ("variant-values@2.0 v=bar", "v", AbstractVariant),
+    ],
+)
+def test_substitute_abstract_variants(mock_packages, spec, variant_name, after):
+    spec = Spec(spec)
+
+    # all variants start out as AbstractVariant
+    assert isinstance(spec.variants[variant_name], AbstractVariant)
+
+    if issubclass(after, Exception):
+        # if we're checking for an error, use pytest.raises
+        with pytest.raises(after):
+            spack.spec.substitute_abstract_variants(spec)
+    else:
+        # ensure that the type of the variant on the spec has been narrowed (or not)
+        spack.spec.substitute_abstract_variants(spec)
+        assert isinstance(spec.variants[variant_name], after)
diff --git a/lib/spack/spack/variant.py b/lib/spack/spack/variant.py
index 83f3ecca83..e0ef7c0e30 100644
--- a/lib/spack/spack/variant.py
+++ b/lib/spack/spack/variant.py
@@ -7,17 +7,20 @@
 variants both in packages and in specs.
 """
 import collections.abc
+import enum
 import functools
 import inspect
 import itertools
 import re
+from typing import Any, Callable, Collection, Iterable, List, Optional, Tuple, Type, Union
 
 import llnl.util.lang as lang
 import llnl.util.tty.color
-from llnl.string import comma_or
 
 import spack.error as error
 import spack.parser
+import spack.repo
+import spack.spec
 
 #: These are variant names used by Spack internally; packages can't use them
 reserved_names = [
@@ -35,36 +38,68 @@ reserved_names = [
 special_variant_values = [None, "none", "*"]
 
 
+class VariantType(enum.Enum):
+    """Enum representing the three concrete variant types."""
+
+    MULTI = "multi"
+    BOOL = "bool"
+    SINGLE = "single"
+
+    @property
+    def variant_class(self) -> Type:
+        if self is self.MULTI:
+            return MultiValuedVariant
+        elif self is self.BOOL:
+            return BoolValuedVariant
+        else:
+            return SingleValuedVariant
+
+
 class Variant:
-    """Represents a variant in a package, as declared in the
-    variant directive.
+    """Represents a variant definition, created by the ``variant()`` directive.
+
+    There can be multiple definitions of the same variant, and they are given precedence
+    by order of appearance in the package. Later definitions have higher precedence.
+    Similarly, definitions in derived classes have higher precedence than those in their
+    superclasses.
+
     """
 
+    name: str
+    default: Any
+    description: str
+    values: Optional[Collection]  #: if None, valid values are defined only by validators
+    multi: bool
+    single_value_validator: Callable
+    group_validator: Optional[Callable]
+    sticky: bool
+    precedence: int
+
     def __init__(
         self,
-        name,
-        default,
-        description,
-        values=(True, False),
-        multi=False,
-        validator=None,
-        sticky=False,
+        name: str,
+        *,
+        default: Any,
+        description: str,
+        values: Union[Collection, Callable] = (True, False),
+        multi: bool = False,
+        validator: Optional[Callable] = None,
+        sticky: bool = False,
+        precedence: int = 0,
     ):
         """Initialize a package variant.
 
         Args:
-            name (str): name of the variant
-            default (str): default value for the variant in case
-                nothing has been specified
-            description (str): purpose of the variant
-            values (sequence): sequence of allowed values or a callable
-                accepting a single value as argument and returning True if the
-                value is good, False otherwise
-            multi (bool): whether multiple CSV are allowed
-            validator (callable): optional callable used to enforce
-                additional logic on the set of values being validated
-            sticky (bool): if true the variant is set to the default value at
-                concretization time
+            name: name of the variant
+            default: default value for the variant, used when nothing is explicitly specified
+            description: purpose of the variant
+            values: sequence of allowed values or a callable accepting a single value as argument
+                and returning True if the value is good, False otherwise
+            multi: whether multiple values are allowed
+            validator: optional callable that can be used to perform additional validation
+            sticky: if true the variant is set to the default value at concretization time
+            precedence: int indicating precedence of this variant definition in the solve
+                (definition with highest precedence is used when multiple definitions are possible)
         """
         self.name = name
         self.default = default
@@ -73,7 +108,7 @@ class Variant:
         self.values = None
         if values == "*":
             # wildcard is a special case to make it easy to say any value is ok
-            self.single_value_validator = lambda x: True
+            self.single_value_validator = lambda v: True
 
         elif isinstance(values, type):
             # supplying a type means any value *of that type*
@@ -92,21 +127,22 @@ class Variant:
             self.single_value_validator = values
         else:
             # Otherwise, assume values is the set of allowed explicit values
-            self.values = _flatten(values)
-            self.single_value_validator = lambda x: x in tuple(self.values)
+            values = _flatten(values)
+            self.values = values
+            self.single_value_validator = lambda v: v in values
 
         self.multi = multi
         self.group_validator = validator
         self.sticky = sticky
+        self.precedence = precedence
 
-    def validate_or_raise(self, vspec, pkg_cls=None):
+    def validate_or_raise(self, vspec: "AbstractVariant", pkg_name: str):
         """Validate a variant spec against this package variant. Raises an
         exception if any error is found.
 
         Args:
-            vspec (Variant): instance to be validated
-            pkg_cls (spack.package_base.PackageBase): the package class
-                that required the validation, if available
+            vspec: variant spec to be validated
+            pkg_name: the name of the package class that required this validation (for errors)
 
         Raises:
             InconsistentValidationError: if ``vspec.name != self.name``
@@ -121,25 +157,23 @@ class Variant:
         if self.name != vspec.name:
             raise InconsistentValidationError(vspec, self)
 
-        # Check the values of the variant spec
-        value = vspec.value
-        if isinstance(vspec.value, (bool, str)):
-            value = (vspec.value,)
-
         # If the value is exclusive there must be at most one
+        value = vspec.value_as_tuple
         if not self.multi and len(value) != 1:
-            raise MultipleValuesInExclusiveVariantError(vspec, pkg_cls)
+            raise MultipleValuesInExclusiveVariantError(vspec, pkg_name)
 
         # Check and record the values that are not allowed
-        not_allowed_values = [
-            x for x in value if x != "*" and self.single_value_validator(x) is False
-        ]
-        if not_allowed_values:
-            raise InvalidVariantValueError(self, not_allowed_values, pkg_cls)
+        invalid_vals = ", ".join(
+            f"'{v}'" for v in value if v != "*" and self.single_value_validator(v) is False
+        )
+        if invalid_vals:
+            raise InvalidVariantValueError(
+                f"invalid values for variant '{self.name}' in package {pkg_name}: {invalid_vals}\n"
+            )
 
         # Validate the group of values if needed
         if self.group_validator is not None and value != ("*",):
-            self.group_validator(pkg_cls.name, self.name, value)
+            self.group_validator(pkg_name, self.name, value)
 
     @property
     def allowed_values(self):
@@ -168,7 +202,7 @@ class Variant:
         """
         return self.make_variant(self.default)
 
-    def make_variant(self, value):
+    def make_variant(self, value) -> "AbstractVariant":
         """Factory that creates a variant holding the value passed as
         a parameter.
 
@@ -179,30 +213,31 @@ class Variant:
             MultiValuedVariant or SingleValuedVariant or BoolValuedVariant:
                 instance of the proper variant
         """
-        return self.variant_cls(self.name, value)
+        return self.variant_type.variant_class(self.name, value)
 
     @property
-    def variant_cls(self):
-        """Proper variant class to be used for this configuration."""
+    def variant_type(self) -> VariantType:
+        """String representation of the type of this variant (single/multi/bool)"""
         if self.multi:
-            return MultiValuedVariant
+            return VariantType.MULTI
         elif self.values == (True, False):
-            return BoolValuedVariant
-        return SingleValuedVariant
+            return VariantType.BOOL
+        else:
+            return VariantType.SINGLE
 
-    def __eq__(self, other):
+    def __str__(self):
         return (
-            self.name == other.name
-            and self.default == other.default
-            and self.values == other.values
-            and self.multi == other.multi
-            and self.single_value_validator == other.single_value_validator
-            and self.group_validator == other.group_validator
+            f"Variant('{self.name}', "
+            f"default='{self.default}', "
+            f"description='{self.description}', "
+            f"values={self.values}, "
+            f"multi={self.multi}, "
+            f"single_value_validator={self.single_value_validator}, "
+            f"group_validator={self.group_validator}, "
+            f"sticky={self.sticky}, "
+            f"precedence={self.precedence})"
         )
 
-    def __ne__(self, other):
-        return not self == other
-
 
 def implicit_variant_conversion(method):
     """Converts other to type(self) and calls method(self, other)
@@ -225,12 +260,12 @@ def implicit_variant_conversion(method):
     return convert
 
 
-def _flatten(values):
+def _flatten(values) -> Collection:
     """Flatten instances of _ConditionalVariantValues for internal representation"""
     if isinstance(values, DisjointSetsOfValues):
         return values
 
-    flattened = []
+    flattened: List = []
     for item in values:
         if isinstance(item, _ConditionalVariantValues):
             flattened.extend(item)
@@ -241,6 +276,13 @@ def _flatten(values):
     return tuple(flattened)
 
 
+#: Type for value of a variant
+ValueType = Union[str, bool, Tuple[Union[str, bool], ...]]
+
+#: Type of variant value when output for JSON, YAML, etc.
+SerializedValueType = Union[str, bool, List[Union[str, bool]]]
+
+
 @lang.lazy_lexicographic_ordering
 class AbstractVariant:
     """A variant that has not yet decided who it wants to be. It behaves like
@@ -253,20 +295,20 @@ class AbstractVariant:
     values.
     """
 
-    def __init__(self, name, value, propagate=False):
+    name: str
+    propagate: bool
+    _value: ValueType
+    _original_value: Any
+
+    def __init__(self, name: str, value: Any, propagate: bool = False):
         self.name = name
         self.propagate = propagate
 
-        # Stores 'value' after a bit of massaging
-        # done by the property setter
-        self._value = None
-        self._original_value = None
-
         # Invokes property setter
         self.value = value
 
     @staticmethod
-    def from_node_dict(name, value):
+    def from_node_dict(name: str, value: Union[str, List[str]]) -> "AbstractVariant":
         """Reconstruct a variant from a node dict."""
         if isinstance(value, list):
             # read multi-value variants in and be faithful to the YAML
@@ -280,16 +322,26 @@ class AbstractVariant:
 
         return SingleValuedVariant(name, value)
 
-    def yaml_entry(self):
+    def yaml_entry(self) -> Tuple[str, SerializedValueType]:
         """Returns a key, value tuple suitable to be an entry in a yaml dict.
 
         Returns:
             tuple: (name, value_representation)
         """
-        return self.name, list(self.value)
+        return self.name, list(self.value_as_tuple)
+
+    @property
+    def value_as_tuple(self) -> Tuple[Union[bool, str], ...]:
+        """Getter for self.value that always returns a Tuple (even for single valued variants).
+
+        This makes it easy to iterate over possible values.
+        """
+        if isinstance(self._value, (bool, str)):
+            return (self._value,)
+        return self._value
 
     @property
-    def value(self):
+    def value(self) -> ValueType:
         """Returns a tuple of strings containing the values stored in
         the variant.
 
@@ -299,10 +351,10 @@ class AbstractVariant:
         return self._value
 
     @value.setter
-    def value(self, value):
+    def value(self, value: ValueType) -> None:
         self._value_setter(value)
 
-    def _value_setter(self, value):
+    def _value_setter(self, value: ValueType) -> None:
         # Store the original value
         self._original_value = value
 
@@ -310,7 +362,7 @@ class AbstractVariant:
             # Store a tuple of CSV string representations
             # Tuple is necessary here instead of list because the
             # values need to be hashed
-            value = re.split(r"\s*,\s*", str(value))
+            value = tuple(re.split(r"\s*,\s*", str(value)))
 
         for val in special_variant_values:
             if val in value and len(value) > 1:
@@ -323,16 +375,11 @@ class AbstractVariant:
         # to a set
         self._value = tuple(sorted(set(value)))
 
-    def _cmp_iter(self):
+    def _cmp_iter(self) -> Iterable:
         yield self.name
+        yield from (str(v) for v in self.value_as_tuple)
 
-        value = self._value
-        if not isinstance(value, tuple):
-            value = (value,)
-        value = tuple(str(x) for x in value)
-        yield value
-
-    def copy(self):
+    def copy(self) -> "AbstractVariant":
         """Returns an instance of a variant equivalent to self
 
         Returns:
@@ -346,7 +393,7 @@ class AbstractVariant:
         return type(self)(self.name, self._original_value, self.propagate)
 
     @implicit_variant_conversion
-    def satisfies(self, other):
+    def satisfies(self, other: "AbstractVariant") -> bool:
         """Returns true if ``other.name == self.name``, because any value that
         other holds and is not in self yet **could** be added.
 
@@ -360,13 +407,13 @@ class AbstractVariant:
         # (`foo=bar` will never satisfy `baz=bar`)
         return other.name == self.name
 
-    def intersects(self, other):
+    def intersects(self, other: "AbstractVariant") -> bool:
         """Returns True if there are variant matching both self and other, False otherwise."""
         if isinstance(other, (SingleValuedVariant, BoolValuedVariant)):
             return other.intersects(self)
         return other.name == self.name
 
-    def compatible(self, other):
+    def compatible(self, other: "AbstractVariant") -> bool:
         """Returns True if self and other are compatible, False otherwise.
 
         As there is no semantic check, two VariantSpec are compatible if
@@ -383,7 +430,7 @@ class AbstractVariant:
         return self.intersects(other)
 
     @implicit_variant_conversion
-    def constrain(self, other):
+    def constrain(self, other: "AbstractVariant") -> bool:
         """Modify self to match all the constraints for other if both
         instances are multi-valued. Returns True if self changed,
         False otherwise.
@@ -399,23 +446,23 @@ class AbstractVariant:
 
         old_value = self.value
 
-        values = list(sorted(set(self.value + other.value)))
+        values = list(sorted(set(self.value_as_tuple + other.value_as_tuple)))
         # If we constraint wildcard by another value, just take value
         if "*" in values and len(values) > 1:
             values.remove("*")
 
-        self.value = ",".join(values)
+        self._value_setter(",".join(str(v) for v in values))
         return old_value != self.value
 
-    def __contains__(self, item):
-        return item in self._value
+    def __contains__(self, item: Union[str, bool]) -> bool:
+        return item in self.value_as_tuple
 
-    def __repr__(self):
+    def __repr__(self) -> str:
         return f"{type(self).__name__}({repr(self.name)}, {repr(self._original_value)})"
 
-    def __str__(self):
+    def __str__(self) -> str:
         delim = "==" if self.propagate else "="
-        values = spack.parser.quote_if_needed(",".join(str(v) for v in self.value))
+        values = spack.parser.quote_if_needed(",".join(str(v) for v in self.value_as_tuple))
         return f"{self.name}{delim}{values}"
 
 
@@ -423,7 +470,7 @@ class MultiValuedVariant(AbstractVariant):
     """A variant that can hold multiple values at once."""
 
     @implicit_variant_conversion
-    def satisfies(self, other):
+    def satisfies(self, other: AbstractVariant) -> bool:
         """Returns true if ``other.name == self.name`` and ``other.value`` is
         a strict subset of self. Does not try to validate.
 
@@ -443,22 +490,25 @@ class MultiValuedVariant(AbstractVariant):
 
         # allow prefix find on patches
         if self.name == "patches":
-            return all(any(w.startswith(v) for w in self.value) for v in other.value)
+            return all(
+                any(str(w).startswith(str(v)) for w in self.value_as_tuple)
+                for v in other.value_as_tuple
+            )
 
         # Otherwise we want all the values in `other` to be also in `self`
-        return all(v in self.value for v in other.value)
+        return all(v in self for v in other.value_as_tuple)
 
-    def append(self, value):
+    def append(self, value: Union[str, bool]) -> None:
         """Add another value to this multi-valued variant."""
-        self._value = tuple(sorted((value,) + self._value))
-        self._original_value = ",".join(self._value)
+        self._value = tuple(sorted((value,) + self.value_as_tuple))
+        self._original_value = ",".join(str(v) for v in self._value)
 
-    def __str__(self):
+    def __str__(self) -> str:
         # Special-case patches to not print the full 64 character sha256
         if self.name == "patches":
-            values_str = ",".join(x[:7] for x in self.value)
+            values_str = ",".join(str(x)[:7] for x in self.value_as_tuple)
         else:
-            values_str = ",".join(str(x) for x in self.value)
+            values_str = ",".join(str(x) for x in self.value_as_tuple)
 
         delim = "==" if self.propagate else "="
         return f"{self.name}{delim}{spack.parser.quote_if_needed(values_str)}"
@@ -467,35 +517,33 @@ class MultiValuedVariant(AbstractVariant):
 class SingleValuedVariant(AbstractVariant):
     """A variant that can hold multiple values, but one at a time."""
 
-    def _value_setter(self, value):
+    def _value_setter(self, value: ValueType) -> None:
         # Treat the value as a multi-valued variant
         super()._value_setter(value)
 
         # Then check if there's only a single value
-        if len(self._value) != 1:
-            raise MultipleValuesInExclusiveVariantError(self, None)
-        self._value = str(self._value[0])
+        values = self.value_as_tuple
+        if len(values) != 1:
+            raise MultipleValuesInExclusiveVariantError(self)
 
-    def __str__(self):
-        delim = "==" if self.propagate else "="
-        return f"{self.name}{delim}{spack.parser.quote_if_needed(self.value)}"
+        self._value = values[0]
 
     @implicit_variant_conversion
-    def satisfies(self, other):
+    def satisfies(self, other: "AbstractVariant") -> bool:
         abstract_sat = super().satisfies(other)
 
         return abstract_sat and (
             self.value == other.value or other.value == "*" or self.value == "*"
         )
 
-    def intersects(self, other):
+    def intersects(self, other: "AbstractVariant") -> bool:
         return self.satisfies(other)
 
-    def compatible(self, other):
+    def compatible(self, other: "AbstractVariant") -> bool:
         return self.satisfies(other)
 
     @implicit_variant_conversion
-    def constrain(self, other):
+    def constrain(self, other: "AbstractVariant") -> bool:
         if self.name != other.name:
             raise ValueError("variants must have the same name")
 
@@ -510,12 +558,17 @@ class SingleValuedVariant(AbstractVariant):
             raise UnsatisfiableVariantSpecError(other.value, self.value)
         return False
 
-    def __contains__(self, item):
+    def __contains__(self, item: ValueType) -> bool:
         return item == self.value
 
-    def yaml_entry(self):
+    def yaml_entry(self) -> Tuple[str, SerializedValueType]:
+        assert isinstance(self.value, (bool, str))
         return self.name, self.value
 
+    def __str__(self) -> str:
+        delim = "==" if self.propagate else "="
+        return f"{self.name}{delim}{spack.parser.quote_if_needed(str(self.value))}"
+
 
 class BoolValuedVariant(SingleValuedVariant):
     """A variant that can hold either True or False.
@@ -523,7 +576,7 @@ class BoolValuedVariant(SingleValuedVariant):
     BoolValuedVariant can also hold the value '*', for coerced
     comparisons between ``foo=*`` and ``+foo`` or ``~foo``."""
 
-    def _value_setter(self, value):
+    def _value_setter(self, value: ValueType) -> None:
         # Check the string representation of the value and turn
         # it to a boolean
         if str(value).upper() == "TRUE":
@@ -540,13 +593,14 @@ class BoolValuedVariant(SingleValuedVariant):
             msg += "a value that does not represent a bool"
             raise ValueError(msg.format(self.name))
 
-    def __contains__(self, item):
+    def __contains__(self, item: ValueType) -> bool:
         return item is self.value
 
-    def __str__(self):
+    def __str__(self) -> str:
+        sigil = "+" if self.value else "~"
         if self.propagate:
-            return "{0}{1}".format("++" if self.value else "~~", self.name)
-        return "{0}{1}".format("+" if self.value else "~", self.name)
+            sigil *= 2
+        return f"{sigil}{self.name}"
 
 
 # The class below inherit from Sequence to disguise as a tuple and comply
@@ -720,12 +774,15 @@ def disjoint_sets(*sets):
 class Value:
     """Conditional value that might be used in variants."""
 
-    def __init__(self, value, when):
+    value: Any
+    when: Optional["spack.spec.Spec"]  # optional b/c we need to know about disabled values
+
+    def __init__(self, value: Any, when: Optional["spack.spec.Spec"]):
         self.value = value
         self.when = when
 
     def __repr__(self):
-        return "Value({0.value}, when={0.when})".format(self)
+        return f"Value({self.value}, when={self.when})"
 
     def __str__(self):
         return str(self.value)
@@ -745,15 +802,92 @@ class Value:
         return self.value < other.value
 
 
+def prevalidate_variant_value(
+    pkg_cls: "Type[spack.package_base.PackageBase]",
+    variant: AbstractVariant,
+    spec: Optional["spack.spec.Spec"] = None,
+    strict: bool = False,
+) -> List[Variant]:
+    """Do as much validation of a variant value as is possible before concretization.
+
+    This checks that the variant value is valid for *some* definition of the variant, and
+    it raises if we know *before* concretization that the value cannot occur. On success
+    it returns the variant definitions for which the variant is valid.
+
+    Arguments:
+        pkg_cls: package in which variant is (potentially multiply) defined
+        variant: variant spec with value to validate
+        spec: optionally restrict validation only to variants defined for this spec
+        strict: if True, raise an exception if no variant definition is valid for any
+            constraint on the spec.
+
+    Return:
+        list of variant definitions that will accept the given value. List will be empty
+        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:
+        return []
+
+    # raise if there is no definition at all
+    if not pkg_cls.has_variant(variant.name):
+        raise UnknownVariantError(
+            f"No such variant '{variant.name}' in package {pkg_cls.name}", [variant.name]
+        )
+
+    # do as much prevalidation as we can -- check only those
+    # variants whose when constraint intersects this spec
+    errors = []
+    possible_definitions = []
+    valid_definitions = []
+
+    for when, pkg_variant_def in pkg_cls.variant_definitions(variant.name):
+        if spec and not spec.intersects(when):
+            continue
+        possible_definitions.append(pkg_variant_def)
+
+        try:
+            pkg_variant_def.validate_or_raise(variant, pkg_cls.name)
+            valid_definitions.append(pkg_variant_def)
+        except spack.error.SpecError as e:
+            errors.append(e)
+
+    # value is valid for at least one definition -- return them all
+    if valid_definitions:
+        return valid_definitions
+
+    # no when spec intersected, so no possible definition for the variant in this configuration
+    if strict and not possible_definitions:
+        when_clause = f" when {spec}" if spec else ""
+        raise InvalidVariantValueError(
+            f"variant '{variant.name}' does not exist for '{pkg_cls.name}'{when_clause}"
+        )
+
+    # There are only no errors if we're not strict and there are no possible_definitions.
+    # We are strict for audits but not for specs on the CLI or elsewhere. Being strict
+    # in these cases would violate our rule of being able to *talk* about any configuration,
+    # regardless of what the package.py currently says.
+    if not errors:
+        return []
+
+    # if there is just one error, raise the specific error
+    if len(errors) == 1:
+        raise errors[0]
+
+    # otherwise combine all the errors and raise them together
+    raise InvalidVariantValueError(
+        "multiple variant issues:", "\n".join(e.message for e in errors)
+    )
+
+
 class _ConditionalVariantValues(lang.TypedMutableSequence):
     """A list, just with a different type"""
 
 
-def conditional(*values, **kwargs):
+def conditional(*values: List[Any], when: Optional["spack.directives.WhenType"] = None):
     """Conditional values that can be used in variant declarations."""
-    if len(kwargs) != 1 and "when" not in kwargs:
-        raise ValueError('conditional statement expects a "when=" parameter only')
-    when = kwargs["when"]
+    # _make_when_spec returns None when the condition is statically false.
+    when = spack.directives._make_when_spec(when)
     return _ConditionalVariantValues([Value(x, when=when) for x in values])
 
 
@@ -764,15 +898,9 @@ class DuplicateVariantError(error.SpecError):
 class UnknownVariantError(error.SpecError):
     """Raised when an unknown variant occurs in a spec."""
 
-    def __init__(self, spec, variants):
-        self.unknown_variants = variants
-        variant_str = "variant" if len(variants) == 1 else "variants"
-        msg = (
-            'trying to set {0} "{1}" in package "{2}", but the package'
-            " has no such {0} [happened when validating '{3}']"
-        )
-        msg = msg.format(variant_str, comma_or(variants), spec.name, spec.root)
+    def __init__(self, msg: str, unknown_variants: List[str]):
         super().__init__(msg)
+        self.unknown_variants = unknown_variants
 
 
 class InconsistentValidationError(error.SpecError):
@@ -788,11 +916,10 @@ class MultipleValuesInExclusiveVariantError(error.SpecError, ValueError):
     only one.
     """
 
-    def __init__(self, variant, pkg):
-        msg = 'multiple values are not allowed for variant "{0.name}"{1}'
-        pkg_info = ""
-        if pkg is not None:
-            pkg_info = ' in package "{0}"'.format(pkg.name)
+    def __init__(self, variant: AbstractVariant, pkg_name: Optional[str] = None):
+        pkg_info = "" if pkg_name is None else f" in package '{pkg_name}'"
+        msg = f"multiple values are not allowed for variant '{variant.name}'{pkg_info}"
+
         super().__init__(msg.format(variant, pkg_info))
 
 
@@ -801,23 +928,7 @@ class InvalidVariantValueCombinationError(error.SpecError):
 
 
 class InvalidVariantValueError(error.SpecError):
-    """Raised when a valid variant has at least an invalid value."""
-
-    def __init__(self, variant, invalid_values, pkg):
-        msg = 'invalid values for variant "{0.name}"{2}: {1}\n'
-        pkg_info = ""
-        if pkg is not None:
-            pkg_info = ' in package "{0}"'.format(pkg.name)
-        super().__init__(msg.format(variant, invalid_values, pkg_info))
-
-
-class InvalidVariantForSpecError(error.SpecError):
-    """Raised when an invalid conditional variant is specified."""
-
-    def __init__(self, variant, when, spec):
-        msg = "Invalid variant {0} for spec {1}.\n"
-        msg += "{0} is only available for {1.name} when satisfying one of {2}."
-        super().__init__(msg.format(variant, spec, when))
+    """Raised when variants have invalid values."""
 
 
 class UnsatisfiableVariantSpecError(error.UnsatisfiableSpecError):