Split `satisfies(..., strict=True/False)` into two functions (#35681)

This commit formalizes `satisfies(lhs, rhs, strict=True/False)`
and splits it into two functions: `satisfies(lhs, rhs)` and
`intersects(lhs, rhs)`.

- `satisfies(lhs, rhs)` means: all concrete specs matching the
   left hand side also match the right hand side
- `intersects(lhs, rhs)` means: there exist concrete specs
   matching both lhs and rhs.

`intersects` now has the property that it's commutative,
which previously was not guaranteed.

For abstract specs, `intersects(lhs, rhs)` implies that
`constrain(lhs, rhs)` works.

What's *not* done in this PR is ensuring that
`intersects(concrete, abstract)` returns false when the
abstract spec has additional properties not present in the
concrete spec, but `constrain(concrete, abstract)` will
raise an error.

To accomplish this, some semantics have changed, as well
as bugfixes to ArchSpec:
- GitVersion is now interpreted as a more constrained
  version
- Compiler flags are interpreted as strings since their
  order is important
- Abstract specs respect variant type (bool / multivalued)

33 files changed, 1030 insertions, 850 deletions

diff --git a/lib/spack/spack/abi.py b/lib/spack/spack/abi.py
index 42fa6b82c8..6281551c4e 100644
--- a/lib/spack/spack/abi.py
+++ b/lib/spack/spack/abi.py
@@ -25,7 +25,7 @@ class ABI(object):
         return (
             not target.architecture
             or not constraint.architecture
-            or target.architecture.satisfies(constraint.architecture)
+            or target.architecture.intersects(constraint.architecture)
         )
 
     @memoized
@@ -104,7 +104,7 @@ class ABI(object):
             for cversion in child.compiler.versions:
                 # For a few compilers use specialized comparisons.
                 # Otherwise match on version match.
-                if pversion.satisfies(cversion):
+                if pversion.intersects(cversion):
                     return True
                 elif parent.compiler.name == "gcc" and self._gcc_compiler_compare(
                     pversion, cversion
diff --git a/lib/spack/spack/audit.py b/lib/spack/spack/audit.py
index 441ec33136..a8bbf3f5c5 100644
--- a/lib/spack/spack/audit.py
+++ b/lib/spack/spack/audit.py
@@ -721,7 +721,7 @@ def _version_constraints_are_satisfiable_by_some_version_in_repo(pkgs, error_cls
             dependency_pkg_cls = None
             try:
                 dependency_pkg_cls = spack.repo.path.get_pkg_class(s.name)
-                assert any(v.satisfies(s.versions) for v in list(dependency_pkg_cls.versions))
+                assert any(v.intersects(s.versions) for v in list(dependency_pkg_cls.versions))
             except Exception:
                 summary = (
                     "{0}: dependency on {1} cannot be satisfied " "by known versions of {1.name}"
diff --git a/lib/spack/spack/bootstrap/core.py b/lib/spack/spack/bootstrap/core.py
index 2021171a38..3fd1efbc3f 100644
--- a/lib/spack/spack/bootstrap/core.py
+++ b/lib/spack/spack/bootstrap/core.py
@@ -208,7 +208,7 @@ class BuildcacheBootstrapper(Bootstrapper):
                 # This will be None for things that don't depend on python
                 python_spec = item.get("python", None)
                 # Skip specs which are not compatible
-                if not abstract_spec.satisfies(candidate_spec):
+                if not abstract_spec.intersects(candidate_spec):
                     continue
 
                 if python_spec is not None and python_spec not in abstract_spec:
diff --git a/lib/spack/spack/ci.py b/lib/spack/spack/ci.py
index 7afda4babf..13b97c0e0a 100644
--- a/lib/spack/spack/ci.py
+++ b/lib/spack/spack/ci.py
@@ -361,7 +361,7 @@ def _compute_spec_deps(spec_list, check_index_only=False, mirrors_to_check=None)
 
 
 def _spec_matches(spec, match_string):
-    return spec.satisfies(match_string)
+    return spec.intersects(match_string)
 
 
 def _remove_attributes(src_dict, dest_dict):
@@ -938,7 +938,7 @@ def generate_gitlab_ci_yaml(
                         bs_arch = c_spec.architecture
                         bs_arch_family = bs_arch.target.microarchitecture.family
                         if (
-                            c_spec.satisfies(compiler_pkg_spec)
+                            c_spec.intersects(compiler_pkg_spec)
                             and bs_arch_family == spec_arch_family
                         ):
                             # We found the bootstrap compiler this release spec
diff --git a/lib/spack/spack/cmd/buildcache.py b/lib/spack/spack/cmd/buildcache.py
index 7532271054..685b27baf4 100644
--- a/lib/spack/spack/cmd/buildcache.py
+++ b/lib/spack/spack/cmd/buildcache.py
@@ -498,11 +498,11 @@ def list_fn(args):
 
     if not args.allarch:
         arch = spack.spec.Spec.default_arch()
-        specs = [s for s in specs if s.satisfies(arch)]
+        specs = [s for s in specs if s.intersects(arch)]
 
     if args.specs:
         constraints = set(args.specs)
-        specs = [s for s in specs if any(s.satisfies(c) for c in constraints)]
+        specs = [s for s in specs if any(s.intersects(c) for c in constraints)]
     if sys.stdout.isatty():
         builds = len(specs)
         tty.msg("%s." % plural(builds, "cached build"))
diff --git a/lib/spack/spack/cmd/info.py b/lib/spack/spack/cmd/info.py
index 76fb99422e..9e9ae219cc 100644
--- a/lib/spack/spack/cmd/info.py
+++ b/lib/spack/spack/cmd/info.py
@@ -283,7 +283,7 @@ def print_tests(pkg):
     c_names = ("gcc", "intel", "intel-parallel-studio", "pgi")
     if pkg.name in c_names:
         v_names.extend(["c", "cxx", "fortran"])
-    if pkg.spec.satisfies("llvm+clang"):
+    if pkg.spec.intersects("llvm+clang"):
         v_names.extend(["c", "cxx"])
     # TODO Refactor END
 
diff --git a/lib/spack/spack/cmd/mirror.py b/lib/spack/spack/cmd/mirror.py
index 8ad10b1a6c..582627cbe2 100644
--- a/lib/spack/spack/cmd/mirror.py
+++ b/lib/spack/spack/cmd/mirror.py
@@ -335,7 +335,7 @@ def not_excluded_fn(args):
         exclude_specs.extend(spack.cmd.parse_specs(str(args.exclude_specs).split()))
 
     def not_excluded(x):
-        return not any(x.satisfies(y, strict=True) for y in exclude_specs)
+        return not any(x.satisfies(y) for y in exclude_specs)
 
     return not_excluded
 
diff --git a/lib/spack/spack/concretize.py b/lib/spack/spack/concretize.py
index fe876b0632..41a23994e3 100644
--- a/lib/spack/spack/concretize.py
+++ b/lib/spack/spack/concretize.py
@@ -134,7 +134,7 @@ class Concretizer(object):
 
             externals = spec_externals(cspec)
             for ext in externals:
-                if ext.satisfies(spec):
+                if ext.intersects(spec):
                     usable.append(ext)
 
         # If nothing is in the usable list now, it's because we aren't
@@ -200,7 +200,7 @@ class Concretizer(object):
 
         # List of versions we could consider, in sorted order
         pkg_versions = spec.package_class.versions
-        usable = [v for v in pkg_versions if any(v.satisfies(sv) for sv in spec.versions)]
+        usable = [v for v in pkg_versions if any(v.intersects(sv) for sv in spec.versions)]
 
         yaml_prefs = PackagePrefs(spec.name, "version")
 
@@ -344,7 +344,7 @@ class Concretizer(object):
                     new_target_arch = spack.spec.ArchSpec((None, None, str(new_target)))
                     curr_target_arch = spack.spec.ArchSpec((None, None, str(curr_target)))
 
-                    if not new_target_arch.satisfies(curr_target_arch):
+                    if not new_target_arch.intersects(curr_target_arch):
                         # new_target is an incorrect guess based on preferences
                         # and/or default
                         valid_target_ranges = str(curr_target).split(",")
diff --git a/lib/spack/spack/database.py b/lib/spack/spack/database.py
index 2e012a67d5..af321323c9 100644
--- a/lib/spack/spack/database.py
+++ b/lib/spack/spack/database.py
@@ -1525,7 +1525,7 @@ class Database(object):
                 if not (start_date < inst_date < end_date):
                     continue
 
-            if query_spec is any or rec.spec.satisfies(query_spec, strict=True):
+            if query_spec is any or rec.spec.satisfies(query_spec):
                 results.append(rec.spec)
 
         return results
diff --git a/lib/spack/spack/environment/environment.py b/lib/spack/spack/environment/environment.py
index cabb255e23..f91ea2f051 100644
--- a/lib/spack/spack/environment/environment.py
+++ b/lib/spack/spack/environment/environment.py
@@ -349,7 +349,8 @@ def _is_dev_spec_and_has_changed(spec):
 
 def _spec_needs_overwrite(spec, changed_dev_specs):
     """Check whether the current spec needs to be overwritten because either it has
-    changed itself or one of its dependencies have changed"""
+    changed itself or one of its dependencies have changed
+    """
     # if it's not installed, we don't need to overwrite it
     if not spec.installed:
         return False
@@ -2313,7 +2314,7 @@ def _concretize_from_constraints(spec_constraints, tests=False):
             invalid_deps = [
                 c
                 for c in spec_constraints
-                if any(c.satisfies(invd, strict=True) for invd in invalid_deps_string)
+                if any(c.satisfies(invd) for invd in invalid_deps_string)
             ]
             if len(invalid_deps) != len(invalid_deps_string):
                 raise e
diff --git a/lib/spack/spack/fetch_strategy.py b/lib/spack/spack/fetch_strategy.py
index 7034d7cf73..07d6a99966 100644
--- a/lib/spack/spack/fetch_strategy.py
+++ b/lib/spack/spack/fetch_strategy.py
@@ -1501,7 +1501,7 @@ def _from_merged_attrs(fetcher, pkg, version):
     return fetcher(**attrs)
 
 
-def for_package_version(pkg, version):
+def for_package_version(pkg, version=None):
     """Determine a fetch strategy based on the arguments supplied to
     version() in the package description."""
 
@@ -1512,8 +1512,18 @@ def for_package_version(pkg, version):
 
     check_pkg_attributes(pkg)
 
-    if not isinstance(version, spack.version.VersionBase):
-        version = spack.version.Version(version)
+    if version is not None:
+        assert not pkg.spec.concrete, "concrete specs should not pass the 'version=' argument"
+        # Specs are initialized with the universe range, if no version information is given,
+        # so here we make sure we always match the version passed as argument
+        if not isinstance(version, spack.version.VersionBase):
+            version = spack.version.Version(version)
+
+        version_list = spack.version.VersionList()
+        version_list.add(version)
+        pkg.spec.versions = version_list
+    else:
+        version = pkg.version
 
     # if it's a commit, we must use a GitFetchStrategy
     if isinstance(version, spack.version.GitVersion):
diff --git a/lib/spack/spack/mirror.py b/lib/spack/spack/mirror.py
index 1a839e0639..c74b68a43b 100644
--- a/lib/spack/spack/mirror.py
+++ b/lib/spack/spack/mirror.py
@@ -492,7 +492,7 @@ def get_matching_versions(specs, num_versions=1):
                 break
 
             # Generate only versions that satisfy the spec.
-            if spec.concrete or v.satisfies(spec.versions):
+            if spec.concrete or v.intersects(spec.versions):
                 s = spack.spec.Spec(pkg.name)
                 s.versions = VersionList([v])
                 s.variants = spec.variants.copy()
diff --git a/lib/spack/spack/modules/common.py b/lib/spack/spack/modules/common.py
index e2eda7982c..7329e05455 100644
--- a/lib/spack/spack/modules/common.py
+++ b/lib/spack/spack/modules/common.py
@@ -207,7 +207,7 @@ def merge_config_rules(configuration, spec):
     # evaluated in order of appearance in the module file
     spec_configuration = module_specific_configuration.pop("all", {})
     for constraint, action in module_specific_configuration.items():
-        if spec.satisfies(constraint, strict=True):
+        if spec.satisfies(constraint):
             if hasattr(constraint, "override") and constraint.override:
                 spec_configuration = {}
             update_dictionary_extending_lists(spec_configuration, action)
diff --git a/lib/spack/spack/package_base.py b/lib/spack/spack/package_base.py
index 4d41727eb4..470a41c460 100644
--- a/lib/spack/spack/package_base.py
+++ b/lib/spack/spack/package_base.py
@@ -1197,7 +1197,7 @@ class PackageBase(WindowsRPath, PackageViewMixin, metaclass=PackageMeta):
         # one element (the root package). In case there are resources
         # associated with the package, append their fetcher to the
         # composite.
-        root_fetcher = fs.for_package_version(self, self.version)
+        root_fetcher = fs.for_package_version(self)
         fetcher = fs.FetchStrategyComposite()  # Composite fetcher
         fetcher.append(root_fetcher)  # Root fetcher is always present
         resources = self._get_needed_resources()
@@ -1308,7 +1308,7 @@ class PackageBase(WindowsRPath, PackageViewMixin, metaclass=PackageMeta):
         True if this package provides a virtual package with the specified name
         """
         return any(
-            any(self.spec.satisfies(c) for c in constraints)
+            any(self.spec.intersects(c) for c in constraints)
             for s, constraints in self.provided.items()
             if s.name == vpkg_name
         )
@@ -1614,7 +1614,7 @@ class PackageBase(WindowsRPath, PackageViewMixin, metaclass=PackageMeta):
         # TODO: resources
         if self.spec.versions.concrete:
             try:
-                source_id = fs.for_package_version(self, self.version).source_id()
+                source_id = fs.for_package_version(self).source_id()
             except (fs.ExtrapolationError, fs.InvalidArgsError):
                 # ExtrapolationError happens if the package has no fetchers defined.
                 # InvalidArgsError happens when there are version directives with args,
@@ -1777,7 +1777,7 @@ class PackageBase(WindowsRPath, PackageViewMixin, metaclass=PackageMeta):
                 # conflict with the spec, so we need to invoke
                 # when_spec.satisfies(self.spec) vs.
                 # self.spec.satisfies(when_spec)
-                if when_spec.satisfies(self.spec, strict=False):
+                if when_spec.intersects(self.spec):
                     resources.extend(resource_list)
         # Sorts the resources by the length of the string representing their
         # destination. Since any nested resource must contain another
diff --git a/lib/spack/spack/package_prefs.py b/lib/spack/spack/package_prefs.py
index e3a8799f6b..c0bc52b239 100644
--- a/lib/spack/spack/package_prefs.py
+++ b/lib/spack/spack/package_prefs.py
@@ -73,7 +73,7 @@ class PackagePrefs(object):
         # integer is the index of the first spec in order that satisfies
         # spec, or it's a number larger than any position in the order.
         match_index = next(
-            (i for i, s in enumerate(spec_order) if spec.satisfies(s)), len(spec_order)
+            (i for i, s in enumerate(spec_order) if spec.intersects(s)), len(spec_order)
         )
         if match_index < len(spec_order) and spec_order[match_index] == spec:
             # If this is called with multiple specs that all satisfy the same
@@ -185,7 +185,7 @@ def spec_externals(spec):
                 ),
                 extra_attributes=entry.get("extra_attributes", {}),
             )
-            if external_spec.satisfies(spec):
+            if external_spec.intersects(spec):
                 external_specs.append(external_spec)
 
     # Defensively copy returned specs
diff --git a/lib/spack/spack/projections.py b/lib/spack/spack/projections.py
index db1ee83548..58f7b9bb71 100644
--- a/lib/spack/spack/projections.py
+++ b/lib/spack/spack/projections.py
@@ -10,7 +10,7 @@ def get_projection(projections, spec):
     """
     all_projection = None
     for spec_like, projection in projections.items():
-        if spec.satisfies(spec_like, strict=True):
+        if spec.satisfies(spec_like):
             return projection
         elif spec_like == "all":
             all_projection = projection
diff --git a/lib/spack/spack/provider_index.py b/lib/spack/spack/provider_index.py
index 526a7dc762..6de661a02a 100644
--- a/lib/spack/spack/provider_index.py
+++ b/lib/spack/spack/provider_index.py
@@ -72,7 +72,7 @@ class _IndexBase(object):
         # Add all the providers that satisfy the vpkg spec.
         if virtual_spec.name in self.providers:
             for p_spec, spec_set in self.providers[virtual_spec.name].items():
-                if p_spec.satisfies(virtual_spec, deps=False):
+                if p_spec.intersects(virtual_spec, deps=False):
                     result.update(spec_set)
 
         # Return providers in order. Defensively copy.
@@ -186,7 +186,7 @@ class ProviderIndex(_IndexBase):
                 provider_spec = provider_spec_readonly.copy()
                 provider_spec.compiler_flags = spec.compiler_flags.copy()
 
-                if spec.satisfies(provider_spec, deps=False):
+                if spec.intersects(provider_spec, deps=False):
                     provided_name = provided_spec.name
 
                     provider_map = self.providers.setdefault(provided_name, {})
diff --git a/lib/spack/spack/solver/asp.py b/lib/spack/spack/solver/asp.py
index c808a183c6..3537a5e2df 100644
--- a/lib/spack/spack/solver/asp.py
+++ b/lib/spack/spack/solver/asp.py
@@ -501,7 +501,7 @@ class Result(object):
                 key = providers[0]
             candidate = answer.get(key)
 
-            if candidate and candidate.satisfies(input_spec):
+            if candidate and candidate.intersects(input_spec):
                 self._concrete_specs.append(answer[key])
                 self._concrete_specs_by_input[input_spec] = answer[key]
             else:
@@ -1878,7 +1878,7 @@ class SpackSolverSetup(object):
         for pkg_name, versions in sorted(self.version_constraints):
             # version must be *one* of the ones the spec allows.
             allowed_versions = [
-                v for v in sorted(self.possible_versions[pkg_name]) if v.satisfies(versions)
+                v for v in sorted(self.possible_versions[pkg_name]) if v.intersects(versions)
             ]
 
             # This is needed to account for a variable number of
diff --git a/lib/spack/spack/spec.py b/lib/spack/spack/spec.py
index 5ca015e43a..ced35d5c7d 100644
--- a/lib/spack/spack/spec.py
+++ b/lib/spack/spack/spec.py
@@ -191,9 +191,7 @@ def colorize_spec(spec):
 
 @lang.lazy_lexicographic_ordering
 class ArchSpec(object):
-    """Aggregate the target platform, the operating system and the target
-    microarchitecture into an architecture spec..
-    """
+    """Aggregate the target platform, the operating system and the target microarchitecture."""
 
     @staticmethod
     def _return_arch(os_tag, target_tag):
@@ -362,17 +360,32 @@ class ArchSpec(object):
 
         self._target = value
 
-    def satisfies(self, other, strict=False):
-        """Predicate to check if this spec satisfies a constraint.
+    def satisfies(self, other: "ArchSpec") -> bool:
+        """Return True if all concrete specs matching self also match other, otherwise False.
 
         Args:
-            other (ArchSpec or str): constraint on the current instance
-            strict (bool): if ``False`` the function checks if the current
-                instance *might* eventually satisfy the constraint. If
-                ``True`` it check if the constraint is satisfied right now.
+            other: spec to be satisfied
+        """
+        other = self._autospec(other)
 
-        Returns:
-            True if the constraint is satisfied, False otherwise.
+        # Check platform and os
+        for attribute in ("platform", "os"):
+            other_attribute = getattr(other, attribute)
+            self_attribute = getattr(self, attribute)
+            if other_attribute and self_attribute != other_attribute:
+                return False
+
+        return self._target_satisfies(other, strict=True)
+
+    def intersects(self, other: "ArchSpec") -> bool:
+        """Return True if there exists at least one concrete spec that matches both
+        self and other, otherwise False.
+
+        This operation is commutative, and if two specs intersect it means that one
+        can constrain the other.
+
+        Args:
+            other: spec to be checked for compatibility
         """
         other = self._autospec(other)
 
@@ -380,47 +393,48 @@ class ArchSpec(object):
         for attribute in ("platform", "os"):
             other_attribute = getattr(other, attribute)
             self_attribute = getattr(self, attribute)
-            if strict or self.concrete:
-                if other_attribute and self_attribute != other_attribute:
-                    return False
-            else:
-                if other_attribute and self_attribute and self_attribute != other_attribute:
-                    return False
+            if other_attribute and self_attribute and self_attribute != other_attribute:
+                return False
 
-        # Check target
-        return self.target_satisfies(other, strict=strict)
+        return self._target_satisfies(other, strict=False)
 
-    def target_satisfies(self, other, strict):
-        need_to_check = (
-            bool(other.target) if strict or self.concrete else bool(other.target and self.target)
-        )
+    def _target_satisfies(self, other: "ArchSpec", strict: bool) -> bool:
+        if strict is True:
+            need_to_check = bool(other.target)
+        else:
+            need_to_check = bool(other.target and self.target)
 
-        # If there's no need to check we are fine
         if not need_to_check:
             return True
 
-        # self is not concrete, but other_target is there and strict=True
+        # other_target is there and strict=True
         if self.target is None:
             return False
 
-        return bool(self.target_intersection(other))
+        return bool(self._target_intersection(other))
 
-    def target_constrain(self, other):
-        if not other.target_satisfies(self, strict=False):
+    def _target_constrain(self, other: "ArchSpec") -> bool:
+        if not other._target_satisfies(self, strict=False):
             raise UnsatisfiableArchitectureSpecError(self, other)
 
         if self.target_concrete:
             return False
+
         elif other.target_concrete:
             self.target = other.target
             return True
 
         # Compute the intersection of every combination of ranges in the lists
-        results = self.target_intersection(other)
-        # Do we need to dedupe here?
-        self.target = ",".join(results)
+        results = self._target_intersection(other)
+        attribute_str = ",".join(results)
+
+        if self.target == attribute_str:
+            return False
 
-    def target_intersection(self, other):
+        self.target = attribute_str
+        return True
+
+    def _target_intersection(self, other):
         results = []
 
         if not self.target or not other.target:
@@ -464,7 +478,7 @@ class ArchSpec(object):
                         results.append("%s:%s" % (n_min, n_max))
         return results
 
-    def constrain(self, other):
+    def constrain(self, other: "ArchSpec") -> bool:
         """Projects all architecture fields that are specified in the given
         spec onto the instance spec if they're missing from the instance
         spec.
@@ -479,7 +493,7 @@ class ArchSpec(object):
         """
         other = self._autospec(other)
 
-        if not other.satisfies(self):
+        if not other.intersects(self):
             raise UnsatisfiableArchitectureSpecError(other, self)
 
         constrained = False
@@ -489,7 +503,7 @@ class ArchSpec(object):
                 setattr(self, attr, ovalue)
                 constrained = True
 
-        self.target_constrain(other)
+        constrained |= self._target_constrain(other)
 
         return constrained
 
@@ -505,7 +519,9 @@ class ArchSpec(object):
     @property
     def target_concrete(self):
         """True if the target is not a range or list."""
-        return ":" not in str(self.target) and "," not in str(self.target)
+        return (
+            self.target is not None and ":" not in str(self.target) and "," not in str(self.target)
+        )
 
     def to_dict(self):
         d = syaml.syaml_dict(
@@ -591,11 +607,31 @@ class CompilerSpec(object):
             return compiler_spec_like
         return CompilerSpec(compiler_spec_like)
 
-    def satisfies(self, other, strict=False):
+    def intersects(self, other: "CompilerSpec") -> bool:
+        """Return True if all concrete specs matching self also match other, otherwise False.
+
+        For compiler specs this means that the name of the compiler must be the same for
+        self and other, and that the versions ranges should intersect.
+
+        Args:
+            other: spec to be satisfied
+        """
         other = self._autospec(other)
-        return self.name == other.name and self.versions.satisfies(other.versions, strict=strict)
+        return self.name == other.name and self.versions.intersects(other.versions)
 
-    def constrain(self, other):
+    def satisfies(self, other: "CompilerSpec") -> bool:
+        """Return True if all concrete specs matching self also match other, otherwise False.
+
+        For compiler specs this means that the name of the compiler must be the same for
+        self and other, and that the version range of self is a subset of that of other.
+
+        Args:
+            other: spec to be satisfied
+        """
+        other = self._autospec(other)
+        return self.name == other.name and self.versions.satisfies(other.versions)
+
+    def constrain(self, other: "CompilerSpec") -> bool:
         """Intersect self's versions with other.
 
         Return whether the CompilerSpec changed.
@@ -603,7 +639,7 @@ class CompilerSpec(object):
         other = self._autospec(other)
 
         # ensure that other will actually constrain this spec.
-        if not other.satisfies(self):
+        if not other.intersects(self):
             raise UnsatisfiableCompilerSpecError(other, self)
 
         return self.versions.intersect(other.versions)
@@ -736,24 +772,25 @@ class FlagMap(lang.HashableMap):
         super(FlagMap, self).__init__()
         self.spec = spec
 
-    def satisfies(self, other, strict=False):
-        if strict or (self.spec and self.spec._concrete):
-            return all(f in self and set(self[f]) == set(other[f]) for f in other)
-        else:
+    def satisfies(self, other):
+        return all(f in self and self[f] == other[f] for f in other)
+
+    def intersects(self, other):
+        common_types = set(self) & set(other)
+        for flag_type in common_types:
+            if not self[flag_type] or not other[flag_type]:
+                # At least one of the two is empty
+                continue
+
+            if self[flag_type] != other[flag_type]:
+                return False
+
             if not all(
-                set(self[f]) == set(other[f]) for f in other if (other[f] != [] and f in self)
+                f1.propagate == f2.propagate for f1, f2 in zip(self[flag_type], other[flag_type])
             ):
+                # At least one propagation flag didn't match
                 return False
-
-            # Check that the propagation values match
-            for flag_type in other:
-                if not all(
-                    other[flag_type][i].propagate == self[flag_type][i].propagate
-                    for i in range(len(other[flag_type]))
-                    if flag_type in self
-                ):
-                    return False
-            return True
+        return True
 
     def constrain(self, other):
         """Add all flags in other that aren't in self to self.
@@ -2611,9 +2648,9 @@ class Spec(object):
                 # it's possible to build that configuration with Spack
                 continue
             for conflict_spec, when_list in x.package_class.conflicts.items():
-                if x.satisfies(conflict_spec, strict=True):
+                if x.satisfies(conflict_spec):
                     for when_spec, msg in when_list:
-                        if x.satisfies(when_spec, strict=True):
+                        if x.satisfies(when_spec):
                             when = when_spec.copy()
                             when.name = x.name
                             matches.append((x, conflict_spec, when, msg))
@@ -2665,7 +2702,7 @@ class Spec(object):
             # Add any patches from the package to the spec.
             patches = []
             for cond, patch_list in s.package_class.patches.items():
-                if s.satisfies(cond, strict=True):
+                if s.satisfies(cond):
                     for patch in patch_list:
                         patches.append(patch)
             if patches:
@@ -2683,7 +2720,7 @@ class Spec(object):
             patches = []
             for cond, dependency in pkg_deps[dspec.spec.name].items():
                 for pcond, patch_list in dependency.patches.items():
-                    if dspec.parent.satisfies(cond, strict=True) and dspec.spec.satisfies(pcond):
+                    if dspec.parent.satisfies(cond) and dspec.spec.satisfies(pcond):
                         patches.extend(patch_list)
             if patches:
                 all_patches = spec_to_patches.setdefault(id(dspec.spec), [])
@@ -2941,7 +2978,7 @@ class Spec(object):
         # evaluate when specs to figure out constraints on the dependency.
         dep = None
         for when_spec, dependency in conditions.items():
-            if self.satisfies(when_spec, strict=True):
+            if self.satisfies(when_spec):
                 if dep is None:
                     dep = dp.Dependency(self.name, Spec(name), type=())
                 try:
@@ -2976,7 +3013,7 @@ class Spec(object):
             # result.
             for provider in providers:
                 for spec in providers:
-                    if spec is not provider and provider.satisfies(spec):
+                    if spec is not provider and provider.intersects(spec):
                         providers.remove(spec)
             # Can't have multiple providers for the same thing in one spec.
             if len(providers) > 1:
@@ -3293,9 +3330,15 @@ class Spec(object):
         pkg_variant.validate_or_raise(self.variants[variant_name], pkg_cls)
 
     def constrain(self, other, deps=True):
-        """Merge the constraints of other with self.
+        """Intersect self with other in-place. Return True if self changed, False otherwise.
 
-        Returns True if the spec changed as a result, False if not.
+        Args:
+            other: constraint to be added to self
+            deps: if False, constrain only the root node, otherwise constrain dependencies
+                as well.
+
+        Raises:
+             spack.error.UnsatisfiableSpecError: when self cannot be constrained
         """
         # If we are trying to constrain a concrete spec, either the spec
         # already satisfies the constraint (and the method returns False)
@@ -3375,6 +3418,9 @@ class Spec(object):
         if deps:
             changed |= self._constrain_dependencies(other)
 
+        if other.concrete and not self.concrete and other.satisfies(self):
+            self._finalize_concretization()
+
         return changed
 
     def _constrain_dependencies(self, other):
@@ -3387,7 +3433,7 @@ class Spec(object):
         # TODO: might want more detail than this, e.g. specific deps
         # in violation. if this becomes a priority get rid of this
         # check and be more specific about what's wrong.
-        if not other.satisfies_dependencies(self):
+        if not other._intersects_dependencies(self):
             raise UnsatisfiableDependencySpecError(other, self)
 
         if any(not d.name for d in other.traverse(root=False)):
@@ -3449,58 +3495,49 @@ class Spec(object):
             return spec_like
         return Spec(spec_like)
 
-    def satisfies(self, other, deps=True, strict=False):
-        """Determine if this spec satisfies all constraints of another.
-
-        There are two senses for satisfies, depending on the ``strict``
-        argument.
+    def intersects(self, other: "Spec", deps: bool = True) -> bool:
+        """Return True if there exists at least one concrete spec that matches both
+        self and other, otherwise False.
 
-          * ``strict=False``: the left-hand side and right-hand side have
-            non-empty intersection. For example ``zlib`` satisfies
-            ``zlib@1.2.3`` and ``zlib@1.2.3`` satisfies ``zlib``. In this
-            sense satisfies is a commutative operation: ``x.satisfies(y)``
-            if and only if ``y.satisfies(x)``.
+        This operation is commutative, and if two specs intersect it means that one
+        can constrain the other.
 
-          * ``strict=True``: the left-hand side is a subset of the right-hand
-            side. For example ``zlib@1.2.3`` satisfies ``zlib``, but ``zlib``
-            does not satisfy ``zlib@1.2.3``. In this sense satisfies is not
-            commutative: the left-hand side should be at least as constrained
-            as the right-hand side.
+        Args:
+            other: spec to be checked for compatibility
+            deps: if True check compatibility of dependency nodes too, if False only check root
         """
-
         other = self._autospec(other)
 
-        # Optimizations for right-hand side concrete:
-        # 1. For subset (strict=True) tests this means the left-hand side must
-        # be the same singleton with identical hash. Notice that package hashes
-        # can be different for otherwise indistinguishable concrete Spec objects.
-        # 2. For non-empty intersection (strict=False) we only have a fast path
-        # when the left-hand side is also concrete.
-        if other.concrete:
-            if strict:
-                return self.concrete and self.dag_hash() == other.dag_hash()
-            elif self.concrete:
-                return self.dag_hash() == other.dag_hash()
+        if other.concrete and self.concrete:
+            return self.dag_hash() == other.dag_hash()
 
         # If the names are different, we need to consider virtuals
         if self.name != other.name and self.name and other.name:
-            # A concrete provider can satisfy a virtual dependency.
-            if not self.virtual and other.virtual:
+            if self.virtual and other.virtual:
+                # Two virtual specs intersect only if there are providers for both
+                lhs = spack.repo.path.providers_for(str(self))
+                rhs = spack.repo.path.providers_for(str(other))
+                intersection = [s for s in lhs if any(s.intersects(z) for z in rhs)]
+                return bool(intersection)
+
+            # A provider can satisfy a virtual dependency.
+            elif self.virtual or other.virtual:
+                virtual_spec, non_virtual_spec = (self, other) if self.virtual else (other, self)
                 try:
                     # Here we might get an abstract spec
-                    pkg_cls = spack.repo.path.get_pkg_class(self.fullname)
-                    pkg = pkg_cls(self)
+                    pkg_cls = spack.repo.path.get_pkg_class(non_virtual_spec.fullname)
+                    pkg = pkg_cls(non_virtual_spec)
                 except spack.repo.UnknownEntityError:
                     # If we can't get package info on this spec, don't treat
                     # it as a provider of this vdep.
                     return False
 
-                if pkg.provides(other.name):
+                if pkg.provides(virtual_spec.name):
                     for provided, when_specs in pkg.provided.items():
                         if any(
-                            self.satisfies(when, deps=False, strict=strict) for when in when_specs
+                            non_virtual_spec.intersects(when, deps=False) for when in when_specs
                         ):
-                            if provided.satisfies(other):
+                            if provided.intersects(virtual_spec):
                                 return True
             return False
 
@@ -3511,75 +3548,41 @@ class Spec(object):
             and self.namespace != other.namespace
         ):
             return False
+
         if self.versions and other.versions:
-            if not self.versions.satisfies(other.versions, strict=strict):
+            if not self.versions.intersects(other.versions):
                 return False
-        elif strict and (self.versions or other.versions):
-            return False
 
-        # None indicates no constraints when not strict.
         if self.compiler and other.compiler:
-            if not self.compiler.satisfies(other.compiler, strict=strict):
+            if not self.compiler.intersects(other.compiler):
                 return False
-        elif strict and (other.compiler and not self.compiler):
-            return False
 
-        var_strict = strict
-        if (not self.name) or (not other.name):
-            var_strict = True
-        if not self.variants.satisfies(other.variants, strict=var_strict):
+        if not self.variants.intersects(other.variants):
             return False
 
-        # Architecture satisfaction is currently just string equality.
-        # If not strict, None means unconstrained.
         if self.architecture and other.architecture:
-            if not self.architecture.satisfies(other.architecture, strict):
+            if not self.architecture.intersects(other.architecture):
                 return False
-        elif strict and (other.architecture and not self.architecture):
-            return False
 
-        if not self.compiler_flags.satisfies(other.compiler_flags, strict=strict):
+        if not self.compiler_flags.intersects(other.compiler_flags):
             return False
 
         # If we need to descend into dependencies, do it, otherwise we're done.
         if deps:
-            deps_strict = strict
-            if self._concrete and not other.name:
-                # We're dealing with existing specs
-                deps_strict = True
-            return self.satisfies_dependencies(other, strict=deps_strict)
+            return self._intersects_dependencies(other)
         else:
             return True
 
-    def satisfies_dependencies(self, other, strict=False):
-        """
-        This checks constraints on common dependencies against each other.
-        """
+    def _intersects_dependencies(self, other):
         other = self._autospec(other)
 
-        # If there are no constraints to satisfy, we're done.
-        if not other._dependencies:
-            return True
-
-        if strict:
-            # if we have no dependencies, we can't satisfy any constraints.
-            if not self._dependencies:
-                return False
-
-            # use list to prevent double-iteration
-            selfdeps = list(self.traverse(root=False))
-            otherdeps = list(other.traverse(root=False))
-            if not all(any(d.satisfies(dep, strict=True) for d in selfdeps) for dep in otherdeps):
-                return False
-
-        elif not self._dependencies:
-            # if not strict, this spec *could* eventually satisfy the
-            # constraints on other.
+        if not other._dependencies or not self._dependencies:
+            # one spec *could* eventually satisfy the other
             return True
 
         # Handle first-order constraints directly
         for name in self.common_dependencies(other):
-            if not self[name].satisfies(other[name], deps=False):
+            if not self[name].intersects(other[name], deps=False):
                 return False
 
         # For virtual dependencies, we need to dig a little deeper.
@@ -3607,6 +3610,89 @@ class Spec(object):
 
         return True
 
+    def satisfies(self, other: "Spec", deps: bool = True) -> bool:
+        """Return True if all concrete specs matching self also match other, otherwise False.
+
+        Args:
+            other: spec to be satisfied
+            deps: if True descend to dependencies, otherwise only check root node
+        """
+        other = self._autospec(other)
+
+        if other.concrete:
+            # The left-hand side must be the same singleton with identical hash. Notice that
+            # package hashes can be different for otherwise indistinguishable concrete Spec
+            # objects.
+            return self.concrete and self.dag_hash() == other.dag_hash()
+
+        # If the names are different, we need to consider virtuals
+        if self.name != other.name and self.name and other.name:
+            # A concrete provider can satisfy a virtual dependency.
+            if not self.virtual and other.virtual:
+                try:
+                    # Here we might get an abstract spec
+                    pkg_cls = spack.repo.path.get_pkg_class(self.fullname)
+                    pkg = pkg_cls(self)
+                except spack.repo.UnknownEntityError:
+                    # If we can't get package info on this spec, don't treat
+                    # it as a provider of this vdep.
+                    return False
+
+                if pkg.provides(other.name):
+                    for provided, when_specs in pkg.provided.items():
+                        if any(self.satisfies(when, deps=False) for when in when_specs):
+                            if provided.intersects(other):
+                                return True
+            return False
+
+        # namespaces either match, or other doesn't require one.
+        if (
+            other.namespace is not None
+            and self.namespace is not None
+            and self.namespace != other.namespace
+        ):
+            return False
+
+        if not self.versions.satisfies(other.versions):
+            return False
+
+        if self.compiler and other.compiler:
+            if not self.compiler.satisfies(other.compiler):
+                return False
+        elif other.compiler and not self.compiler:
+            return False
+
+        if not self.variants.satisfies(other.variants):
+            return False
+
+        if self.architecture and other.architecture:
+            if not self.architecture.satisfies(other.architecture):
+                return False
+        elif other.architecture and not self.architecture:
+            return False
+
+        if not self.compiler_flags.satisfies(other.compiler_flags):
+            return False
+
+        # If we need to descend into dependencies, do it, otherwise we're done.
+        if not deps:
+            return True
+
+        # If there are no constraints to satisfy, we're done.
+        if not other._dependencies:
+            return True
+
+        # If we have no dependencies, we can't satisfy any constraints.
+        if not self._dependencies:
+            return False
+
+        # If we arrived here, then rhs is abstract. At the moment we don't care about the edge
+        # structure of an abstract DAG - hence the deps=False parameter.
+        return all(
+            any(lhs.satisfies(rhs, deps=False) for lhs in self.traverse(root=False))
+            for rhs in other.traverse(root=False)
+        )
+
     def virtual_dependencies(self):
         """Return list of any virtual deps in this spec."""
         return [spec for spec in self.traverse() if spec.virtual]
diff --git a/lib/spack/spack/test/architecture.py b/lib/spack/spack/test/architecture.py
index 3b6c53c426..7aba886375 100644
--- a/lib/spack/spack/test/architecture.py
+++ b/lib/spack/spack/test/architecture.py
@@ -183,7 +183,7 @@ def test_optimization_flags_with_custom_versions(
 def test_satisfy_strict_constraint_when_not_concrete(architecture_tuple, constraint_tuple):
     architecture = spack.spec.ArchSpec(architecture_tuple)
     constraint = spack.spec.ArchSpec(constraint_tuple)
-    assert not architecture.satisfies(constraint, strict=True)
+    assert not architecture.satisfies(constraint)
 
 
 @pytest.mark.parametrize(
diff --git a/lib/spack/spack/test/cmd/env.py b/lib/spack/spack/test/cmd/env.py
index ce7862cd12..8fb16e8322 100644
--- a/lib/spack/spack/test/cmd/env.py
+++ b/lib/spack/spack/test/cmd/env.py
@@ -82,8 +82,8 @@ def test_change_match_spec():
 
         change("--match-spec", "mpileaks@2.2", "mpileaks@2.3")
 
-    assert not any(x.satisfies("mpileaks@2.2") for x in e.user_specs)
-    assert any(x.satisfies("mpileaks@2.3") for x in e.user_specs)
+    assert not any(x.intersects("mpileaks@2.2") for x in e.user_specs)
+    assert any(x.intersects("mpileaks@2.3") for x in e.user_specs)
 
 
 def test_change_multiple_matches():
@@ -97,8 +97,8 @@ def test_change_multiple_matches():
 
         change("--match-spec", "mpileaks", "-a", "mpileaks%gcc")
 
-    assert all(x.satisfies("%gcc") for x in e.user_specs if x.name == "mpileaks")
-    assert any(x.satisfies("%clang") for x in e.user_specs if x.name == "libelf")
+    assert all(x.intersects("%gcc") for x in e.user_specs if x.name == "mpileaks")
+    assert any(x.intersects("%clang") for x in e.user_specs if x.name == "libelf")
 
 
 def test_env_add_virtual():
@@ -111,7 +111,7 @@ def test_env_add_virtual():
     hashes = e.concretized_order
     assert len(hashes) == 1
     spec = e.specs_by_hash[hashes[0]]
-    assert spec.satisfies("mpi")
+    assert spec.intersects("mpi")
 
 
 def test_env_add_nonexistant_fails():
@@ -687,7 +687,7 @@ env:
     with e:
         e.concretize()
 
-    assert any(x.satisfies("mpileaks@2.2") for x in e._get_environment_specs())
+    assert any(x.intersects("mpileaks@2.2") for x in e._get_environment_specs())
 
 
 def test_with_config_bad_include():
@@ -1630,9 +1630,9 @@ env:
             assert concrete.concrete
             assert not user.concrete
             if user.name == "libelf":
-                assert not concrete.satisfies("^mpi", strict=True)
+                assert not concrete.satisfies("^mpi")
             elif user.name == "mpileaks":
-                assert concrete.satisfies("^mpi", strict=True)
+                assert concrete.satisfies("^mpi")
 
 
 def test_stack_concretize_extraneous_variants(tmpdir, config, mock_packages):
diff --git a/lib/spack/spack/test/cmd/install.py b/lib/spack/spack/test/cmd/install.py
index 8074cfe0dc..bdc73596b2 100644
--- a/lib/spack/spack/test/cmd/install.py
+++ b/lib/spack/spack/test/cmd/install.py
@@ -276,7 +276,7 @@ def test_install_commit(mock_git_version_info, install_mockery, mock_packages, m
     assert filename in installed
     with open(spec.prefix.bin.join(filename), "r") as f:
         content = f.read().strip()
-    assert content == "[]"  # contents are weird for another test
+    assert content == "[0]"  # contents are weird for another test
 
 
 def test_install_overwrite_multiple(
diff --git a/lib/spack/spack/test/concretize.py b/lib/spack/spack/test/concretize.py
index 785b7ca166..11393ba8c3 100644
--- a/lib/spack/spack/test/concretize.py
+++ b/lib/spack/spack/test/concretize.py
@@ -293,11 +293,11 @@ class TestConcretize(object):
         we ask for some advanced version.
         """
         repo = spack.repo.path
-        assert not any(s.satisfies("mpich2@:1.0") for s in repo.providers_for("mpi@2.1"))
-        assert not any(s.satisfies("mpich2@:1.1") for s in repo.providers_for("mpi@2.2"))
-        assert not any(s.satisfies("mpich@:1") for s in repo.providers_for("mpi@2"))
-        assert not any(s.satisfies("mpich@:1") for s in repo.providers_for("mpi@3"))
-        assert not any(s.satisfies("mpich2") for s in repo.providers_for("mpi@3"))
+        assert not any(s.intersects("mpich2@:1.0") for s in repo.providers_for("mpi@2.1"))
+        assert not any(s.intersects("mpich2@:1.1") for s in repo.providers_for("mpi@2.2"))
+        assert not any(s.intersects("mpich@:1") for s in repo.providers_for("mpi@2"))
+        assert not any(s.intersects("mpich@:1") for s in repo.providers_for("mpi@3"))
+        assert not any(s.intersects("mpich2") for s in repo.providers_for("mpi@3"))
 
     def test_provides_handles_multiple_providers_of_same_version(self):
         """ """
@@ -1462,7 +1462,7 @@ class TestConcretize(object):
         with spack.config.override("concretizer:reuse", True):
             s = spack.spec.Spec(spec_str).concretized()
         assert s.installed is expect_installed
-        assert s.satisfies(spec_str, strict=True)
+        assert s.satisfies(spec_str)
 
     @pytest.mark.regression("26721,19736")
     def test_sticky_variant_in_package(self):
diff --git a/lib/spack/spack/test/conftest.py b/lib/spack/spack/test/conftest.py
index 08b9b2c903..1badc88019 100644
--- a/lib/spack/spack/test/conftest.py
+++ b/lib/spack/spack/test/conftest.py
@@ -157,7 +157,9 @@ def mock_git_version_info(git, tmpdir, override_git_repos_cache_path):
             return git("rev-list", "-n1", "HEAD", output=str, error=str).strip()
 
         # Add two commits on main branch
-        write_file(filename, "[]")
+
+        # A commit without a previous version counts as "0"
+        write_file(filename, "[0]")
         git("add", filename)
         commit("first commit")
         commits.append(latest_commit())
diff --git a/lib/spack/spack/test/env.py b/lib/spack/spack/test/env.py
index 8614a92813..7f9a2c0485 100644
--- a/lib/spack/spack/test/env.py
+++ b/lib/spack/spack/test/env.py
@@ -86,13 +86,13 @@ def test_env_change_spec_in_definition(tmpdir, mock_packages, config, mutable_mo
     e.concretize()
     e.write()
 
-    assert any(x.satisfies("mpileaks@2.1%gcc") for x in e.user_specs)
+    assert any(x.intersects("mpileaks@2.1%gcc") for x in e.user_specs)
 
     e.change_existing_spec(spack.spec.Spec("mpileaks@2.2"), list_name="desired_specs")
     e.write()
 
-    assert any(x.satisfies("mpileaks@2.2%gcc") for x in e.user_specs)
-    assert not any(x.satisfies("mpileaks@2.1%gcc") for x in e.user_specs)
+    assert any(x.intersects("mpileaks@2.2%gcc") for x in e.user_specs)
+    assert not any(x.intersects("mpileaks@2.1%gcc") for x in e.user_specs)
 
 
 def test_env_change_spec_in_matrix_raises_error(
diff --git a/lib/spack/spack/test/packages.py b/lib/spack/spack/test/packages.py
index 6687df23c6..45c8111c75 100644
--- a/lib/spack/spack/test/packages.py
+++ b/lib/spack/spack/test/packages.py
@@ -16,6 +16,12 @@ from spack.util.naming import mod_to_class
 from spack.version import VersionChecksumError
 
 
+def pkg_factory(name):
+    """Return a package object tied to an abstract spec"""
+    pkg_cls = spack.repo.path.get_pkg_class(name)
+    return pkg_cls(Spec(name))
+
+
 @pytest.mark.usefixtures("config", "mock_packages")
 class TestPackage(object):
     def test_load_package(self):
@@ -184,8 +190,7 @@ def test_url_for_version_with_only_overrides_with_gaps(mock_packages, config):
 )
 def test_fetcher_url(spec_str, expected_type, expected_url):
     """Ensure that top-level git attribute can be used as a default."""
-    s = Spec(spec_str).concretized()
-    fetcher = spack.fetch_strategy.for_package_version(s.package, "1.0")
+    fetcher = spack.fetch_strategy.for_package_version(pkg_factory(spec_str), "1.0")
     assert isinstance(fetcher, expected_type)
     assert fetcher.url == expected_url
 
@@ -204,8 +209,7 @@ def test_fetcher_url(spec_str, expected_type, expected_url):
 def test_fetcher_errors(spec_str, version_str, exception_type):
     """Verify that we can't extrapolate versions for non-URL packages."""
     with pytest.raises(exception_type):
-        s = Spec(spec_str).concretized()
-        spack.fetch_strategy.for_package_version(s.package, version_str)
+        spack.fetch_strategy.for_package_version(pkg_factory(spec_str), version_str)
 
 
 @pytest.mark.usefixtures("mock_packages", "config")
@@ -220,11 +224,12 @@ def test_fetcher_errors(spec_str, version_str, exception_type):
 )
 def test_git_url_top_level_url_versions(version_str, expected_url, digest):
     """Test URL fetch strategy inference when url is specified with git."""
-    s = Spec("git-url-top-level").concretized()
     # leading 62 zeros of sha256 hash
     leading_zeros = "0" * 62
 
-    fetcher = spack.fetch_strategy.for_package_version(s.package, version_str)
+    fetcher = spack.fetch_strategy.for_package_version(
+        pkg_factory("git-url-top-level"), version_str
+    )
     assert isinstance(fetcher, spack.fetch_strategy.URLFetchStrategy)
     assert fetcher.url == expected_url
     assert fetcher.digest == leading_zeros + digest
@@ -245,9 +250,9 @@ def test_git_url_top_level_url_versions(version_str, expected_url, digest):
 )
 def test_git_url_top_level_git_versions(version_str, tag, commit, branch):
     """Test git fetch strategy inference when url is specified with git."""
-    s = Spec("git-url-top-level").concretized()
-
-    fetcher = spack.fetch_strategy.for_package_version(s.package, version_str)
+    fetcher = spack.fetch_strategy.for_package_version(
+        pkg_factory("git-url-top-level"), version_str
+    )
     assert isinstance(fetcher, spack.fetch_strategy.GitFetchStrategy)
     assert fetcher.url == "https://example.com/some/git/repo"
     assert fetcher.tag == tag
@@ -259,9 +264,8 @@ def test_git_url_top_level_git_versions(version_str, tag, commit, branch):
 @pytest.mark.parametrize("version_str", ["1.0", "1.1", "1.2", "1.3"])
 def test_git_url_top_level_conflicts(version_str):
     """Test git fetch strategy inference when url is specified with git."""
-    s = Spec("git-url-top-level").concretized()
     with pytest.raises(spack.fetch_strategy.FetcherConflict):
-        spack.fetch_strategy.for_package_version(s.package, version_str)
+        spack.fetch_strategy.for_package_version(pkg_factory("git-url-top-level"), version_str)
 
 
 def test_rpath_args(mutable_database):
@@ -301,9 +305,8 @@ def test_bundle_patch_directive(mock_directive_bundle, clear_directive_functions
 )
 def test_fetch_options(version_str, digest_end, extra_options):
     """Test fetch options inference."""
-    s = Spec("fetch-options").concretized()
     leading_zeros = "000000000000000000000000000000"
-    fetcher = spack.fetch_strategy.for_package_version(s.package, version_str)
+    fetcher = spack.fetch_strategy.for_package_version(pkg_factory("fetch-options"), version_str)
     assert isinstance(fetcher, spack.fetch_strategy.URLFetchStrategy)
     assert fetcher.digest == leading_zeros + digest_end
     assert fetcher.extra_options == extra_options
diff --git a/lib/spack/spack/test/spec_semantics.py b/lib/spack/spack/test/spec_semantics.py
index dd086fd632..63e2253b68 100644
--- a/lib/spack/spack/test/spec_semantics.py
+++ b/lib/spack/spack/test/spec_semantics.py
@@ -9,280 +9,348 @@ import spack.directives
 import spack.error
 from spack.error import SpecError, UnsatisfiableSpecError
 from spack.spec import (
+    ArchSpec,
+    CompilerSpec,
     Spec,
     SpecFormatSigilError,
     SpecFormatStringError,
-    UnconstrainableDependencySpecError,
     UnsupportedCompilerError,
 )
 from spack.variant import (
     InvalidVariantValueError,
     MultipleValuesInExclusiveVariantError,
     UnknownVariantError,
-    substitute_abstract_variants,
 )
 
 
-def make_spec(spec_like, concrete):
-    if isinstance(spec_like, Spec):
-        return spec_like
-
-    spec = Spec(spec_like)
-    if concrete:
-        spec._mark_concrete()
-        substitute_abstract_variants(spec)
-    return spec
-
-
-def _specify(spec_like):
-    if isinstance(spec_like, Spec):
-        return spec_like
-
-    return Spec(spec_like)
-
-
-def check_satisfies(target_spec, constraint_spec, target_concrete=False):
-    target = make_spec(target_spec, target_concrete)
-    constraint = _specify(constraint_spec)
-
-    # Satisfies is one-directional.
-    assert target.satisfies(constraint)
-
-    # If target satisfies constraint, then we should be able to constrain
-    # constraint by target.  Reverse is not always true.
-    constraint.copy().constrain(target)
-
-
-def check_unsatisfiable(target_spec, constraint_spec, target_concrete=False):
-    target = make_spec(target_spec, target_concrete)
-    constraint = _specify(constraint_spec)
-
-    assert not target.satisfies(constraint)
-
-    with pytest.raises(UnsatisfiableSpecError):
-        constraint.copy().constrain(target)
+@pytest.mark.usefixtures("config", "mock_packages")
+class TestSpecSemantics(object):
+    """Test satisfies(), intersects(), constrain() and other semantic operations on specs."""
 
+    @pytest.mark.parametrize(
+        "lhs,rhs,expected",
+        [
+            ("libelf@0.8.13", "@0:1", "libelf@0.8.13"),
+            ("libdwarf^libelf@0.8.13", "^libelf@0:1", "libdwarf^libelf@0.8.13"),
+            ("libelf", Spec(), "libelf"),
+            ("libdwarf", Spec(), "libdwarf"),
+            ("%intel", Spec(), "%intel"),
+            ("^mpi", Spec(), "^mpi"),
+            ("+debug", Spec(), "+debug"),
+            ("@3:", Spec(), "@3:"),
+            # Versions
+            ("libelf@0:2.5", "libelf@2.1:3", "libelf@2.1:2.5"),
+            ("libelf@0:2.5%gcc@2:4.6", "libelf@2.1:3%gcc@4.5:4.7", "libelf@2.1:2.5%gcc@4.5:4.6"),
+            # Namespaces
+            ("builtin.mpich", "mpich", "builtin.mpich"),
+            ("builtin.mock.mpich", "mpich", "builtin.mock.mpich"),
+            ("builtin.mpich", "builtin.mpich", "builtin.mpich"),
+            ("mpileaks ^builtin.mock.mpich", "^mpich", "mpileaks ^builtin.mock.mpich"),
+            # Virtual dependencies are fully resolved during concretization, so we can constrain
+            # abstract specs but that would result in a new node
+            ("mpileaks ^builtin.mock.mpich", "^mpi", "mpileaks ^mpi ^builtin.mock.mpich"),
+            (
+                "mpileaks ^builtin.mock.mpich",
+                "^builtin.mock.mpich",
+                "mpileaks ^builtin.mock.mpich",
+            ),
+            # Compilers
+            ("foo%gcc", "%gcc", "foo%gcc"),
+            ("foo%intel", "%intel", "foo%intel"),
+            ("foo%gcc", "%gcc@4.7.2", "foo%gcc@4.7.2"),
+            ("foo%intel", "%intel@4.7.2", "foo%intel@4.7.2"),
+            ("foo%pgi@4.5", "%pgi@4.4:4.6", "foo%pgi@4.5"),
+            ("foo@2.0%pgi@4.5", "@1:3%pgi@4.4:4.6", "foo@2.0%pgi@4.5"),
+            ("foo %gcc@4.7.3", "%gcc@4.7", "foo %gcc@4.7.3"),
+            ("libelf %gcc@4.4.7", "libelf %gcc@4.4.7", "libelf %gcc@4.4.7"),
+            ("libelf", "libelf %gcc@4.4.7", "libelf %gcc@4.4.7"),
+            # Architecture
+            ("foo platform=test", "platform=test", "foo platform=test"),
+            ("foo platform=linux", "platform=linux", "foo platform=linux"),
+            (
+                "foo platform=test",
+                "platform=test target=frontend",
+                "foo platform=test target=frontend",
+            ),
+            (
+                "foo platform=test",
+                "platform=test os=frontend target=frontend",
+                "foo platform=test os=frontend target=frontend",
+            ),
+            (
+                "foo platform=test os=frontend target=frontend",
+                "platform=test",
+                "foo platform=test os=frontend target=frontend",
+            ),
+            ("foo arch=test-None-None", "platform=test", "foo platform=test"),
+            (
+                "foo arch=test-None-frontend",
+                "platform=test target=frontend",
+                "foo platform=test target=frontend",
+            ),
+            (
+                "foo arch=test-frontend-frontend",
+                "platform=test os=frontend target=frontend",
+                "foo platform=test os=frontend target=frontend",
+            ),
+            (
+                "foo arch=test-frontend-frontend",
+                "platform=test",
+                "foo platform=test os=frontend target=frontend",
+            ),
+            (
+                "foo platform=test target=backend os=backend",
+                "platform=test target=backend os=backend",
+                "foo platform=test target=backend os=backend",
+            ),
+            (
+                "libelf target=default_target os=default_os",
+                "libelf target=default_target os=default_os",
+                "libelf target=default_target os=default_os",
+            ),
+            # Dependencies
+            ("mpileaks ^mpich", "^mpich", "mpileaks ^mpich"),
+            ("mpileaks ^mpich@2.0", "^mpich@1:3", "mpileaks ^mpich@2.0"),
+            (
+                "mpileaks ^mpich@2.0 ^callpath@1.5",
+                "^mpich@1:3 ^callpath@1.4:1.6",
+                "mpileaks^mpich@2.0^callpath@1.5",
+            ),
+            ("mpileaks ^mpi", "^mpi", "mpileaks ^mpi"),
+            ("mpileaks ^mpi", "^mpich", "mpileaks ^mpi ^mpich"),
+            ("mpileaks^mpi@1.5", "^mpi@1.2:1.6", "mpileaks^mpi@1.5"),
+            ("mpileaks^mpi@2:", "^mpich", "mpileaks^mpi@2: ^mpich"),
+            ("mpileaks^mpi@2:", "^mpich@3.0.4", "mpileaks^mpi@2: ^mpich@3.0.4"),
+            # Variants
+            ("mpich+foo", "mpich+foo", "mpich+foo"),
+            ("mpich++foo", "mpich++foo", "mpich++foo"),
+            ("mpich~foo", "mpich~foo", "mpich~foo"),
+            ("mpich~~foo", "mpich~~foo", "mpich~~foo"),
+            ("mpich foo=1", "mpich foo=1", "mpich foo=1"),
+            ("mpich foo==1", "mpich foo==1", "mpich foo==1"),
+            ("mpich+foo", "mpich foo=True", "mpich+foo"),
+            ("mpich++foo", "mpich foo=True", "mpich+foo"),
+            ("mpich foo=true", "mpich+foo", "mpich+foo"),
+            ("mpich foo==true", "mpich++foo", "mpich+foo"),
+            ("mpich~foo", "mpich foo=FALSE", "mpich~foo"),
+            ("mpich~~foo", "mpich foo=FALSE", "mpich~foo"),
+            ("mpich foo=False", "mpich~foo", "mpich~foo"),
+            ("mpich foo==False", "mpich~foo", "mpich~foo"),
+            ("mpich foo=*", "mpich~foo", "mpich~foo"),
+            ("mpich+foo", "mpich foo=*", "mpich+foo"),
+            (
+                'multivalue-variant foo="bar,baz"',
+                "multivalue-variant foo=bar,baz",
+                "multivalue-variant foo=bar,baz",
+            ),
+            (
+                'multivalue-variant foo="bar,baz"',
+                "multivalue-variant foo=*",
+                "multivalue-variant foo=bar,baz",
+            ),
+            (
+                'multivalue-variant foo="bar,baz"',
+                "multivalue-variant foo=bar",
+                "multivalue-variant foo=bar,baz",
+            ),
+            (
+                'multivalue-variant foo="bar,baz"',
+                "multivalue-variant foo=baz",
+                "multivalue-variant foo=bar,baz",
+            ),
+            (
+                'multivalue-variant foo="bar,baz,barbaz"',
+                "multivalue-variant foo=bar,baz",
+                "multivalue-variant foo=bar,baz,barbaz",
+            ),
+            (
+                'multivalue-variant foo="bar,baz"',
+                'foo="baz,bar"',  # Order of values doesn't matter
+                "multivalue-variant foo=bar,baz",
+            ),
+            ("mpich+foo", "mpich", "mpich+foo"),
+            ("mpich~foo", "mpich", "mpich~foo"),
+            ("mpich foo=1", "mpich", "mpich foo=1"),
+            ("mpich", "mpich++foo", "mpich+foo"),
+            ("libelf+debug", "libelf+foo", "libelf+debug+foo"),
+            ("libelf+debug", "libelf+debug+foo", "libelf+debug+foo"),
+            ("libelf debug=2", "libelf foo=1", "libelf debug=2 foo=1"),
+            ("libelf debug=2", "libelf debug=2 foo=1", "libelf debug=2 foo=1"),
+            ("libelf+debug", "libelf~foo", "libelf+debug~foo"),
+            ("libelf+debug", "libelf+debug~foo", "libelf+debug~foo"),
+            ("libelf++debug", "libelf+debug+foo", "libelf++debug++foo"),
+            ("libelf debug==2", "libelf foo=1", "libelf debug==2 foo==1"),
+            ("libelf debug==2", "libelf debug=2 foo=1", "libelf debug==2 foo==1"),
+            ("libelf++debug", "libelf++debug~foo", "libelf++debug~~foo"),
+            ("libelf foo=bar,baz", "libelf foo=*", "libelf foo=bar,baz"),
+            ("libelf foo=*", "libelf foo=bar,baz", "libelf foo=bar,baz"),
+            (
+                'multivalue-variant foo="bar"',
+                'multivalue-variant foo="baz"',
+                'multivalue-variant foo="bar,baz"',
+            ),
+            (
+                'multivalue-variant foo="bar,barbaz"',
+                'multivalue-variant foo="baz"',
+                'multivalue-variant foo="bar,baz,barbaz"',
+            ),
+            # Flags
+            ("mpich ", 'mpich cppflags="-O3"', 'mpich cppflags="-O3"'),
+            (
+                'mpich cppflags="-O3 -Wall"',
+                'mpich cppflags="-O3 -Wall"',
+                'mpich cppflags="-O3 -Wall"',
+            ),
+            ('mpich cppflags=="-O3"', 'mpich cppflags=="-O3"', 'mpich cppflags=="-O3"'),
+            (
+                'libelf cflags="-O3"',
+                'libelf cppflags="-Wall"',
+                'libelf cflags="-O3" cppflags="-Wall"',
+            ),
+            (
+                'libelf cflags="-O3"',
+                'libelf cppflags=="-Wall"',
+                'libelf cflags="-O3" cppflags=="-Wall"',
+            ),
+            (
+                'libelf cflags=="-O3"',
+                'libelf cppflags=="-Wall"',
+                'libelf cflags=="-O3" cppflags=="-Wall"',
+            ),
+            (
+                'libelf cflags="-O3"',
+                'libelf cflags="-O3" cppflags="-Wall"',
+                'libelf cflags="-O3" cppflags="-Wall"',
+            ),
+        ],
+    )
+    def test_abstract_specs_can_constrain_each_other(self, lhs, rhs, expected):
+        """Test that lhs and rhs intersect with each other, and that they can be constrained
+        with each other. Also check that the constrained result match the expected spec.
+        """
+        lhs, rhs, expected = Spec(lhs), Spec(rhs), Spec(expected)
 
-def check_constrain(expected, spec, constraint):
-    exp = Spec(expected)
-    spec = Spec(spec)
-    constraint = Spec(constraint)
-    spec.constrain(constraint)
-    assert exp == spec
+        assert lhs.intersects(rhs)
+        assert rhs.intersects(lhs)
 
+        c1, c2 = lhs.copy(), rhs.copy()
+        c1.constrain(rhs)
+        c2.constrain(lhs)
+        assert c1 == c2
+        assert c1 == expected
 
-def check_constrain_changed(spec, constraint):
-    spec = Spec(spec)
-    assert spec.constrain(constraint)
+    @pytest.mark.parametrize(
+        "lhs,rhs", [("libelf", Spec()), ("libelf", "@0:1"), ("libelf", "@0:1 %gcc")]
+    )
+    def test_concrete_specs_which_satisfies_abstract(self, lhs, rhs, default_mock_concretization):
+        """Test that constraining an abstract spec by a compatible concrete one makes the
+        abstract spec concrete, and equal to the one it was constrained with.
+        """
+        lhs, rhs = default_mock_concretization(lhs), Spec(rhs)
 
+        assert lhs.intersects(rhs)
+        assert rhs.intersects(lhs)
+        assert lhs.satisfies(rhs)
+        assert not rhs.satisfies(lhs)
 
-def check_constrain_not_changed(spec, constraint):
-    spec = Spec(spec)
-    assert not spec.constrain(constraint)
+        assert lhs.constrain(rhs) is False
+        assert rhs.constrain(lhs) is True
 
+        assert rhs.concrete
+        assert lhs.satisfies(rhs)
+        assert rhs.satisfies(lhs)
+        assert lhs == rhs
 
-def check_invalid_constraint(spec, constraint):
-    spec = Spec(spec)
-    constraint = Spec(constraint)
-    with pytest.raises((UnsatisfiableSpecError, UnconstrainableDependencySpecError)):
-        spec.constrain(constraint)
+    @pytest.mark.parametrize(
+        "lhs,rhs",
+        [
+            ("foo platform=linux", "platform=test os=redhat6 target=x86"),
+            ("foo os=redhat6", "platform=test os=debian6 target=x86_64"),
+            ("foo target=x86_64", "platform=test os=redhat6 target=x86"),
+            ("foo arch=test-frontend-frontend", "platform=test os=frontend target=backend"),
+            ("foo%intel", "%gcc"),
+            ("foo%intel", "%pgi"),
+            ("foo%pgi@4.3", "%pgi@4.4:4.6"),
+            ("foo@4.0%pgi", "@1:3%pgi"),
+            ("foo@4.0%pgi@4.5", "@1:3%pgi@4.4:4.6"),
+            ("builtin.mock.mpich", "builtin.mpich"),
+            ("mpileaks ^builtin.mock.mpich", "^builtin.mpich"),
+            ("mpileaks^mpich", "^zmpi"),
+            ("mpileaks^zmpi", "^mpich"),
+            ("mpileaks^mpich@1.2", "^mpich@2.0"),
+            ("mpileaks^mpich@4.0^callpath@1.5", "^mpich@1:3^callpath@1.4:1.6"),
+            ("mpileaks^mpich@2.0^callpath@1.7", "^mpich@1:3^callpath@1.4:1.6"),
+            ("mpileaks^mpich@4.0^callpath@1.7", "^mpich@1:3^callpath@1.4:1.6"),
+            ("mpileaks^mpich", "^zmpi"),
+            ("mpileaks^mpi@3", "^mpi@1.2:1.6"),
+            ("mpileaks^mpi@3:", "^mpich2@1.4"),
+            ("mpileaks^mpi@3:", "^mpich2"),
+            ("mpileaks^mpi@3:", "^mpich@1.0"),
+            ("mpich~foo", "mpich+foo"),
+            ("mpich+foo", "mpich~foo"),
+            ("mpich foo=True", "mpich foo=False"),
+            ("mpich~~foo", "mpich++foo"),
+            ("mpich++foo", "mpich~~foo"),
+            ("mpich foo==True", "mpich foo==False"),
+            ('mpich cppflags="-O3"', 'mpich cppflags="-O2"'),
+            ('mpich cppflags="-O3"', 'mpich cppflags=="-O3"'),
+            ("libelf@0:2.0", "libelf@2.1:3"),
+            ("libelf@0:2.5%gcc@4.8:4.9", "libelf@2.1:3%gcc@4.5:4.7"),
+            ("libelf+debug", "libelf~debug"),
+            ("libelf+debug~foo", "libelf+debug+foo"),
+            ("libelf debug=True", "libelf debug=False"),
+            ('libelf cppflags="-O3"', 'libelf cppflags="-O2"'),
+            ("libelf platform=test target=be os=be", "libelf target=fe os=fe"),
+        ],
+    )
+    def test_constraining_abstract_specs_with_empty_intersection(self, lhs, rhs):
+        """Check that two abstract specs with an empty intersection cannot be constrained
+        with each other.
+        """
+        lhs, rhs = Spec(lhs), Spec(rhs)
 
+        assert not lhs.intersects(rhs)
+        assert not rhs.intersects(lhs)
 
-@pytest.mark.usefixtures("config", "mock_packages")
-class TestSpecSematics(object):
-    """This tests satisfies(), constrain() and other semantic operations
-    on specs.
-    """
+        with pytest.raises(UnsatisfiableSpecError):
+            lhs.constrain(rhs)
 
-    def test_satisfies(self):
-        check_satisfies("libelf@0.8.13", "@0:1")
-        check_satisfies("libdwarf^libelf@0.8.13", "^libelf@0:1")
-
-    def test_empty_satisfies(self):
-        # Basic satisfaction
-        check_satisfies("libelf", Spec())
-        check_satisfies("libdwarf", Spec())
-        check_satisfies("%intel", Spec())
-        check_satisfies("^mpi", Spec())
-        check_satisfies("+debug", Spec())
-        check_satisfies("@3:", Spec())
-
-        # Concrete (strict) satisfaction
-        check_satisfies("libelf", Spec(), True)
-        check_satisfies("libdwarf", Spec(), True)
-        check_satisfies("%intel", Spec(), True)
-        check_satisfies("^mpi", Spec(), True)
-        # TODO: Variants can't be called concrete while anonymous
-        # check_satisfies('+debug', Spec(), True)
-        check_satisfies("@3:", Spec(), True)
-
-        # Reverse (non-strict) satisfaction
-        check_satisfies(Spec(), "libelf")
-        check_satisfies(Spec(), "libdwarf")
-        check_satisfies(Spec(), "%intel")
-        check_satisfies(Spec(), "^mpi")
-        # TODO: Variant matching is auto-strict
-        # we should rethink this
-        # check_satisfies(Spec(), '+debug')
-        check_satisfies(Spec(), "@3:")
-
-    def test_satisfies_namespace(self):
-        check_satisfies("builtin.mpich", "mpich")
-        check_satisfies("builtin.mock.mpich", "mpich")
-
-        # TODO: only works for deps now, but shouldn't we allow for root spec?
-        # check_satisfies('builtin.mock.mpich', 'mpi')
-
-        check_satisfies("builtin.mock.mpich", "builtin.mock.mpich")
-
-        check_unsatisfiable("builtin.mock.mpich", "builtin.mpich")
-
-    def test_satisfies_namespaced_dep(self):
-        """Ensure spec from same or unspecified namespace satisfies namespace
-        constraint."""
-        check_satisfies("mpileaks ^builtin.mock.mpich", "^mpich")
-
-        check_satisfies("mpileaks ^builtin.mock.mpich", "^mpi")
-        check_satisfies("mpileaks ^builtin.mock.mpich", "^builtin.mock.mpich")
-
-        check_unsatisfiable("mpileaks ^builtin.mock.mpich", "^builtin.mpich")
-
-    def test_satisfies_compiler(self):
-        check_satisfies("foo%gcc", "%gcc")
-        check_satisfies("foo%intel", "%intel")
-        check_unsatisfiable("foo%intel", "%gcc")
-        check_unsatisfiable("foo%intel", "%pgi")
-
-    def test_satisfies_compiler_version(self):
-        check_satisfies("foo%gcc", "%gcc@4.7.2")
-        check_satisfies("foo%intel", "%intel@4.7.2")
-
-        check_satisfies("foo%pgi@4.5", "%pgi@4.4:4.6")
-        check_satisfies("foo@2.0%pgi@4.5", "@1:3%pgi@4.4:4.6")
-
-        check_unsatisfiable("foo%pgi@4.3", "%pgi@4.4:4.6")
-        check_unsatisfiable("foo@4.0%pgi", "@1:3%pgi")
-        check_unsatisfiable("foo@4.0%pgi@4.5", "@1:3%pgi@4.4:4.6")
-
-        check_satisfies("foo %gcc@4.7.3", "%gcc@4.7")
-        check_unsatisfiable("foo %gcc@4.7", "%gcc@4.7.3")
-
-    def test_satisfies_architecture(self):
-        check_satisfies("foo platform=test", "platform=test")
-        check_satisfies("foo platform=linux", "platform=linux")
-        check_satisfies("foo platform=test", "platform=test target=frontend")
-        check_satisfies("foo platform=test", "platform=test os=frontend target=frontend")
-        check_satisfies("foo platform=test os=frontend target=frontend", "platform=test")
-
-        check_unsatisfiable("foo platform=linux", "platform=test os=redhat6 target=x86")
-        check_unsatisfiable("foo os=redhat6", "platform=test os=debian6 target=x86_64")
-        check_unsatisfiable("foo target=x86_64", "platform=test os=redhat6 target=x86")
-
-        check_satisfies("foo arch=test-None-None", "platform=test")
-        check_satisfies("foo arch=test-None-frontend", "platform=test target=frontend")
-        check_satisfies(
-            "foo arch=test-frontend-frontend", "platform=test os=frontend target=frontend"
-        )
-        check_satisfies("foo arch=test-frontend-frontend", "platform=test")
-        check_unsatisfiable(
-            "foo arch=test-frontend-frontend", "platform=test os=frontend target=backend"
-        )
+        with pytest.raises(UnsatisfiableSpecError):
+            rhs.constrain(lhs)
 
-        check_satisfies(
-            "foo platform=test target=frontend os=frontend",
-            "platform=test target=frontend os=frontend",
-        )
-        check_satisfies(
-            "foo platform=test target=backend os=backend",
-            "platform=test target=backend os=backend",
-        )
-        check_satisfies(
-            "foo platform=test target=default_target os=default_os", "platform=test os=default_os"
-        )
-        check_unsatisfiable(
-            "foo platform=test target=x86 os=redhat6", "platform=linux target=x86 os=redhat6"
-        )
+    @pytest.mark.parametrize(
+        "lhs,rhs,intersection_expected",
+        [
+            ("mpich", "mpich +foo", True),
+            ("mpich", "mpich~foo", True),
+            ("mpich", "mpich foo=1", True),
+            ("mpich", "mpich++foo", True),
+            ("mpich", "mpich~~foo", True),
+            ("mpich", "mpich foo==1", True),
+            # Flags semantics is currently different from other variant
+            ("mpich", 'mpich cflags="-O3"', True),
+            ("mpich cflags=-O3", 'mpich cflags="-O3 -Ofast"', False),
+            ("mpich cflags=-O2", 'mpich cflags="-O3"', False),
+            ("multivalue-variant foo=bar", "multivalue-variant +foo", False),
+            ("multivalue-variant foo=bar", "multivalue-variant ~foo", False),
+            ("multivalue-variant fee=bar", "multivalue-variant fee=baz", False),
+        ],
+    )
+    def test_concrete_specs_which_do_not_satisfy_abstract(
+        self, lhs, rhs, intersection_expected, default_mock_concretization
+    ):
+        lhs, rhs = default_mock_concretization(lhs), Spec(rhs)
 
-    def test_satisfies_dependencies(self):
-        check_satisfies("mpileaks^mpich", "^mpich")
-        check_satisfies("mpileaks^zmpi", "^zmpi")
-
-        check_unsatisfiable("mpileaks^mpich", "^zmpi")
-        check_unsatisfiable("mpileaks^zmpi", "^mpich")
-
-    def test_satisfies_dependency_versions(self):
-        check_satisfies("mpileaks^mpich@2.0", "^mpich@1:3")
-        check_unsatisfiable("mpileaks^mpich@1.2", "^mpich@2.0")
-
-        check_satisfies("mpileaks^mpich@2.0^callpath@1.5", "^mpich@1:3^callpath@1.4:1.6")
-        check_unsatisfiable("mpileaks^mpich@4.0^callpath@1.5", "^mpich@1:3^callpath@1.4:1.6")
-        check_unsatisfiable("mpileaks^mpich@2.0^callpath@1.7", "^mpich@1:3^callpath@1.4:1.6")
-        check_unsatisfiable("mpileaks^mpich@4.0^callpath@1.7", "^mpich@1:3^callpath@1.4:1.6")
-
-    def test_satisfies_virtual_dependencies(self):
-        check_satisfies("mpileaks^mpi", "^mpi")
-        check_satisfies("mpileaks^mpi", "^mpich")
-
-        check_satisfies("mpileaks^mpi", "^zmpi")
-        check_unsatisfiable("mpileaks^mpich", "^zmpi")
-
-    def test_satisfies_virtual_dependency_versions(self):
-        check_satisfies("mpileaks^mpi@1.5", "^mpi@1.2:1.6")
-        check_unsatisfiable("mpileaks^mpi@3", "^mpi@1.2:1.6")
-
-        check_satisfies("mpileaks^mpi@2:", "^mpich")
-        check_satisfies("mpileaks^mpi@2:", "^mpich@3.0.4")
-        check_satisfies("mpileaks^mpi@2:", "^mpich2@1.4")
-
-        check_satisfies("mpileaks^mpi@1:", "^mpich2")
-        check_satisfies("mpileaks^mpi@2:", "^mpich2")
-
-        check_unsatisfiable("mpileaks^mpi@3:", "^mpich2@1.4")
-        check_unsatisfiable("mpileaks^mpi@3:", "^mpich2")
-        check_unsatisfiable("mpileaks^mpi@3:", "^mpich@1.0")
-
-    def test_satisfies_matching_variant(self):
-        check_satisfies("mpich+foo", "mpich+foo")
-        check_satisfies("mpich++foo", "mpich++foo")
-        check_satisfies("mpich~foo", "mpich~foo")
-        check_satisfies("mpich~~foo", "mpich~~foo")
-        check_satisfies("mpich foo=1", "mpich foo=1")
-        check_satisfies("mpich foo==1", "mpich foo==1")
-
-        # confirm that synonymous syntax works correctly
-        check_satisfies("mpich+foo", "mpich foo=True")
-        check_satisfies("mpich++foo", "mpich foo=True")
-        check_satisfies("mpich foo=true", "mpich+foo")
-        check_satisfies("mpich foo==true", "mpich++foo")
-        check_satisfies("mpich~foo", "mpich foo=FALSE")
-        check_satisfies("mpich~~foo", "mpich foo=FALSE")
-        check_satisfies("mpich foo=False", "mpich~foo")
-        check_satisfies("mpich foo==False", "mpich~foo")
-        check_satisfies("mpich foo=*", "mpich~foo")
-        check_satisfies("mpich+foo", "mpich foo=*")
-
-    def test_satisfies_multi_value_variant(self):
-        # Check quoting
-        check_satisfies('multivalue-variant foo="bar,baz"', 'multivalue-variant foo="bar,baz"')
-        check_satisfies("multivalue-variant foo=bar,baz", "multivalue-variant foo=bar,baz")
-        check_satisfies('multivalue-variant foo="bar,baz"', "multivalue-variant foo=bar,baz")
-
-        # A more constrained spec satisfies a less constrained one
-        check_satisfies('multivalue-variant foo="bar,baz"', "multivalue-variant foo=*")
-
-        check_satisfies("multivalue-variant foo=*", 'multivalue-variant foo="bar,baz"')
-
-        check_satisfies('multivalue-variant foo="bar,baz"', 'multivalue-variant foo="bar"')
-
-        check_satisfies('multivalue-variant foo="bar,baz"', 'multivalue-variant foo="baz"')
-
-        check_satisfies(
-            'multivalue-variant foo="bar,baz,barbaz"', 'multivalue-variant foo="bar,baz"'
-        )
+        assert lhs.intersects(rhs) is intersection_expected
+        assert rhs.intersects(lhs) is intersection_expected
+        assert not lhs.satisfies(rhs)
+        assert not rhs.satisfies(lhs)
 
-        check_satisfies('multivalue-variant foo="bar,baz"', 'foo="bar,baz"')
+        with pytest.raises(UnsatisfiableSpecError):
+            assert lhs.constrain(rhs)
 
-        check_satisfies('multivalue-variant foo="bar,baz"', 'foo="bar"')
+        with pytest.raises(UnsatisfiableSpecError):
+            assert rhs.constrain(lhs)
 
     def test_satisfies_single_valued_variant(self):
         """Tests that the case reported in
@@ -322,11 +390,11 @@ class TestSpecSematics(object):
         spec.concretize()
         assert "a@1.0" not in spec
 
-    def test_unsatisfiable_multi_value_variant(self):
+    def test_unsatisfiable_multi_value_variant(self, default_mock_concretization):
         # Semantics for a multi-valued variant is different
         # Depending on whether the spec is concrete or not
 
-        a = make_spec('multivalue-variant foo="bar"', concrete=True)
+        a = default_mock_concretization('multivalue-variant foo="bar"')
         spec_str = 'multivalue-variant foo="bar,baz"'
         b = Spec(spec_str)
         assert not a.satisfies(b)
@@ -344,7 +412,7 @@ class TestSpecSematics(object):
         # An abstract spec can instead be constrained
         assert a.constrain(b)
 
-        a = make_spec('multivalue-variant foo="bar,baz"', concrete=True)
+        a = default_mock_concretization('multivalue-variant foo="bar,baz"')
         spec_str = 'multivalue-variant foo="bar,baz,quux"'
         b = Spec(spec_str)
         assert not a.satisfies(b)
@@ -357,8 +425,8 @@ class TestSpecSematics(object):
         spec_str = 'multivalue-variant foo="bar,baz,quux"'
         b = Spec(spec_str)
         # The specs are abstract and they **could** be constrained
-        assert a.satisfies(b)
-        assert a.satisfies(spec_str)
+        assert a.intersects(b)
+        assert a.intersects(spec_str)
         # An abstract spec can instead be constrained
         assert a.constrain(b)
         # ...but will fail during concretization if there are
@@ -373,8 +441,8 @@ class TestSpecSematics(object):
         # The specs are abstract and they **could** be constrained,
         # as before concretization I don't know which type of variant
         # I have (if it is not a BV)
-        assert a.satisfies(b)
-        assert a.satisfies(spec_str)
+        assert a.intersects(b)
+        assert a.intersects(spec_str)
         # A variant cannot be parsed as single-valued until we try to
         # concretize. This means that we can constrain the variant above
         assert a.constrain(b)
@@ -383,81 +451,6 @@ class TestSpecSematics(object):
         with pytest.raises(MultipleValuesInExclusiveVariantError):
             a.concretize()
 
-    def test_unsatisfiable_variant_types(self):
-        # These should fail due to incompatible types
-
-        # FIXME: these needs to be checked as the new relaxed
-        # FIXME: semantic makes them fail (constrain does not raise)
-        # check_unsatisfiable('multivalue-variant +foo',
-        #                     'multivalue-variant foo="bar"')
-        # check_unsatisfiable('multivalue-variant ~foo',
-        #                     'multivalue-variant foo="bar"')
-
-        check_unsatisfiable(
-            target_spec='multivalue-variant foo="bar"',
-            constraint_spec="multivalue-variant +foo",
-            target_concrete=True,
-        )
-
-        check_unsatisfiable(
-            target_spec='multivalue-variant foo="bar"',
-            constraint_spec="multivalue-variant ~foo",
-            target_concrete=True,
-        )
-
-    def test_satisfies_unconstrained_variant(self):
-        # only asked for mpich, no constraints.  Either will do.
-        check_satisfies("mpich+foo", "mpich")
-        check_satisfies("mpich~foo", "mpich")
-        check_satisfies("mpich foo=1", "mpich")
-
-    def test_unsatisfiable_variants(self):
-        # This case is different depending on whether the specs are concrete.
-
-        # 'mpich' is not concrete:
-        check_satisfies("mpich", "mpich+foo", False)
-        check_satisfies("mpich", "mpich~foo", False)
-        check_satisfies("mpich", "mpich foo=1", False)
-        check_satisfies("mpich", "mpich++foo", False)
-        check_satisfies("mpich", "mpich~~foo", False)
-        check_satisfies("mpich", "mpich foo==1", False)
-
-        # 'mpich' is concrete:
-        check_unsatisfiable("mpich", "mpich+foo", True)
-        check_unsatisfiable("mpich", "mpich~foo", True)
-        check_unsatisfiable("mpich", "mpich foo=1", True)
-        check_unsatisfiable("mpich", "mpich++foo", True)
-        check_unsatisfiable("mpich", "mpich~~foo", True)
-        check_unsatisfiable("mpich", "mpich foo==1", True)
-
-    def test_unsatisfiable_variant_mismatch(self):
-        # No matchi in specs
-        check_unsatisfiable("mpich~foo", "mpich+foo")
-        check_unsatisfiable("mpich+foo", "mpich~foo")
-        check_unsatisfiable("mpich foo=True", "mpich foo=False")
-        check_unsatisfiable("mpich~~foo", "mpich++foo")
-        check_unsatisfiable("mpich++foo", "mpich~~foo")
-        check_unsatisfiable("mpich foo==True", "mpich foo==False")
-
-    def test_satisfies_matching_compiler_flag(self):
-        check_satisfies('mpich cppflags="-O3"', 'mpich cppflags="-O3"')
-        check_satisfies('mpich cppflags="-O3 -Wall"', 'mpich cppflags="-O3 -Wall"')
-        check_satisfies('mpich cppflags=="-O3"', 'mpich cppflags=="-O3"')
-        check_satisfies('mpich cppflags=="-O3 -Wall"', 'mpich cppflags=="-O3 -Wall"')
-
-    def test_satisfies_unconstrained_compiler_flag(self):
-        # only asked for mpich, no constraints.  Any will do.
-        check_satisfies('mpich cppflags="-O3"', "mpich")
-
-    def test_unsatisfiable_compiler_flag(self):
-        # This case is different depending on whether the specs are concrete.
-
-        # 'mpich' is not concrete:
-        check_satisfies("mpich", 'mpich cppflags="-O3"', False)
-
-        # 'mpich' is concrete:
-        check_unsatisfiable("mpich", 'mpich cppflags="-O3"', True)
-
     def test_copy_satisfies_transitive(self):
         spec = Spec("dttop")
         spec.concretize()
@@ -466,33 +459,25 @@ class TestSpecSematics(object):
             assert s.satisfies(copy[s.name])
             assert copy[s.name].satisfies(s)
 
-    def test_unsatisfiable_compiler_flag_mismatch(self):
-        # No match in specs
-        check_unsatisfiable('mpich cppflags="-O3"', 'mpich cppflags="-O2"')
-        check_unsatisfiable('mpich cppflags="-O3"', 'mpich cppflags=="-O3"')
-
-    def test_satisfies_virtual(self):
-        # Don't use check_satisfies: it checks constrain() too, and
-        # you can't constrain a non-virtual by a virtual.
-        assert Spec("mpich").satisfies(Spec("mpi"))
-        assert Spec("mpich2").satisfies(Spec("mpi"))
-        assert Spec("zmpi").satisfies(Spec("mpi"))
-
-    def test_satisfies_virtual_dep_with_virtual_constraint(self):
-        """Ensure we can satisfy virtual constraints when there are multiple
-        vdep providers in the specs."""
-        assert Spec("netlib-lapack ^openblas").satisfies("netlib-lapack ^openblas")
-        assert not Spec("netlib-lapack ^netlib-blas").satisfies("netlib-lapack ^openblas")
-        assert not Spec("netlib-lapack ^openblas").satisfies("netlib-lapack ^netlib-blas")
-        assert Spec("netlib-lapack ^netlib-blas").satisfies("netlib-lapack ^netlib-blas")
-
-    def test_satisfies_same_spec_with_different_hash(self):
+    def test_intersects_virtual(self):
+        assert Spec("mpich").intersects(Spec("mpi"))
+        assert Spec("mpich2").intersects(Spec("mpi"))
+        assert Spec("zmpi").intersects(Spec("mpi"))
+
+    def test_intersects_virtual_dep_with_virtual_constraint(self):
+        assert Spec("netlib-lapack ^openblas").intersects("netlib-lapack ^openblas")
+        assert not Spec("netlib-lapack ^netlib-blas").intersects("netlib-lapack ^openblas")
+        assert not Spec("netlib-lapack ^openblas").intersects("netlib-lapack ^netlib-blas")
+        assert Spec("netlib-lapack ^netlib-blas").intersects("netlib-lapack ^netlib-blas")
+
+    def test_intersectable_concrete_specs_must_have_the_same_hash(self):
         """Ensure that concrete specs are matched *exactly* by hash."""
         s1 = Spec("mpileaks").concretized()
         s2 = s1.copy()
 
         assert s1.satisfies(s2)
         assert s2.satisfies(s1)
+        assert s1.intersects(s2)
 
         # Simulate specs that were installed before and after a change to
         # Spack's hashing algorithm.  This just reverses s2's hash.
@@ -500,6 +485,7 @@ class TestSpecSematics(object):
 
         assert not s1.satisfies(s2)
         assert not s2.satisfies(s1)
+        assert not s1.intersects(s2)
 
     # ========================================================================
     # Indexing specs
@@ -553,155 +539,67 @@ class TestSpecSematics(object):
         for spec in [s, s_mpich, s_mpich2, s_zmpi]:
             assert "mpi" in spec
 
-    # ========================================================================
-    # Constraints
-    # ========================================================================
-    def test_constrain_variants(self):
-        check_constrain("libelf@2.1:2.5", "libelf@0:2.5", "libelf@2.1:3")
-        check_constrain(
-            "libelf@2.1:2.5%gcc@4.5:4.6", "libelf@0:2.5%gcc@2:4.6", "libelf@2.1:3%gcc@4.5:4.7"
-        )
-        check_constrain("libelf+debug+foo", "libelf+debug", "libelf+foo")
-        check_constrain("libelf+debug+foo", "libelf+debug", "libelf+debug+foo")
-        check_constrain("libelf debug=2 foo=1", "libelf debug=2", "libelf foo=1")
-        check_constrain("libelf debug=2 foo=1", "libelf debug=2", "libelf debug=2 foo=1")
-
-        check_constrain("libelf+debug~foo", "libelf+debug", "libelf~foo")
-        check_constrain("libelf+debug~foo", "libelf+debug", "libelf+debug~foo")
-
-        check_constrain("libelf++debug++foo", "libelf++debug", "libelf+debug+foo")
-        check_constrain("libelf debug==2 foo==1", "libelf debug==2", "libelf foo=1")
-        check_constrain("libelf debug==2 foo==1", "libelf debug==2", "libelf debug=2 foo=1")
-
-        check_constrain("libelf++debug~~foo", "libelf++debug", "libelf++debug~foo")
-
-    def test_constrain_multi_value_variant(self):
-        check_constrain(
-            'multivalue-variant foo="bar,baz"',
-            'multivalue-variant foo="bar"',
-            'multivalue-variant foo="baz"',
-        )
-
-        check_constrain(
-            'multivalue-variant foo="bar,baz,barbaz"',
-            'multivalue-variant foo="bar,barbaz"',
-            'multivalue-variant foo="baz"',
-        )
-
-        check_constrain("libelf foo=bar,baz", "libelf foo=bar,baz", "libelf foo=*")
-        check_constrain("libelf foo=bar,baz", "libelf foo=*", "libelf foo=bar,baz")
-
-    def test_constrain_compiler_flags(self):
-        check_constrain(
-            'libelf cflags="-O3" cppflags="-Wall"',
-            'libelf cflags="-O3"',
-            'libelf cppflags="-Wall"',
-        )
-        check_constrain(
-            'libelf cflags="-O3" cppflags="-Wall"',
-            'libelf cflags="-O3"',
-            'libelf cflags="-O3" cppflags="-Wall"',
-        )
+    @pytest.mark.parametrize(
+        "lhs,rhs",
+        [
+            ("libelf", "@1.0"),
+            ("libelf", "@1.0:5.0"),
+            ("libelf", "%gcc"),
+            ("libelf%gcc", "%gcc@4.5"),
+            ("libelf", "+debug"),
+            ("libelf", "debug=*"),
+            ("libelf", "~debug"),
+            ("libelf", "debug=2"),
+            ("libelf", 'cppflags="-O3"'),
+            ("libelf", 'cppflags=="-O3"'),
+            ("libelf^foo", "libelf^foo@1.0"),
+            ("libelf^foo", "libelf^foo@1.0:5.0"),
+            ("libelf^foo", "libelf^foo%gcc"),
+            ("libelf^foo%gcc", "libelf^foo%gcc@4.5"),
+            ("libelf^foo", "libelf^foo+debug"),
+            ("libelf^foo", "libelf^foo~debug"),
+            ("libelf", "^foo"),
+        ],
+    )
+    def test_lhs_is_changed_when_constraining(self, lhs, rhs):
+        lhs, rhs = Spec(lhs), Spec(rhs)
 
-        check_constrain(
-            'libelf cflags="-O3" cppflags=="-Wall"',
-            'libelf cppflags=="-Wall"',
-            'libelf cflags="-O3"',
-        )
-        check_constrain(
-            'libelf cflags=="-O3" cppflags=="-Wall"',
-            'libelf cflags=="-O3"',
-            'libelf cflags=="-O3" cppflags=="-Wall"',
-        )
+        assert lhs.intersects(rhs)
+        assert rhs.intersects(lhs)
+        assert not lhs.satisfies(rhs)
 
-    def test_constrain_architecture(self):
-        check_constrain(
-            "libelf target=default_target os=default_os",
-            "libelf target=default_target os=default_os",
-            "libelf target=default_target os=default_os",
-        )
-        check_constrain(
-            "libelf target=default_target os=default_os",
-            "libelf",
-            "libelf target=default_target os=default_os",
-        )
+        assert lhs.constrain(rhs) is True
+        assert lhs.satisfies(rhs)
 
-    def test_constrain_compiler(self):
-        check_constrain("libelf %gcc@4.4.7", "libelf %gcc@4.4.7", "libelf %gcc@4.4.7")
-        check_constrain("libelf %gcc@4.4.7", "libelf", "libelf %gcc@4.4.7")
-
-    def test_invalid_constraint(self):
-        check_invalid_constraint("libelf@0:2.0", "libelf@2.1:3")
-        check_invalid_constraint("libelf@0:2.5%gcc@4.8:4.9", "libelf@2.1:3%gcc@4.5:4.7")
-
-        check_invalid_constraint("libelf+debug", "libelf~debug")
-        check_invalid_constraint("libelf+debug~foo", "libelf+debug+foo")
-        check_invalid_constraint("libelf debug=True", "libelf debug=False")
-
-        check_invalid_constraint('libelf cppflags="-O3"', 'libelf cppflags="-O2"')
-        check_invalid_constraint("libelf platform=test target=be os=be", "libelf target=fe os=fe")
-        check_invalid_constraint("libdwarf", "^%gcc")
-
-    def test_constrain_changed(self):
-        check_constrain_changed("libelf", "@1.0")
-        check_constrain_changed("libelf", "@1.0:5.0")
-        check_constrain_changed("libelf", "%gcc")
-        check_constrain_changed("libelf%gcc", "%gcc@4.5")
-        check_constrain_changed("libelf", "+debug")
-        check_constrain_changed("libelf", "debug=*")
-        check_constrain_changed("libelf", "~debug")
-        check_constrain_changed("libelf", "debug=2")
-        check_constrain_changed("libelf", 'cppflags="-O3"')
-        check_constrain_changed("libelf", 'cppflags=="-O3"')
-
-        platform = spack.platforms.host()
-        check_constrain_changed("libelf", "target=" + platform.target("default_target").name)
-        check_constrain_changed("libelf", "os=" + platform.operating_system("default_os").name)
-
-    def test_constrain_not_changed(self):
-        check_constrain_not_changed("libelf", "libelf")
-        check_constrain_not_changed("libelf@1.0", "@1.0")
-        check_constrain_not_changed("libelf@1.0:5.0", "@1.0:5.0")
-        check_constrain_not_changed("libelf%gcc", "%gcc")
-        check_constrain_not_changed("libelf%gcc@4.5", "%gcc@4.5")
-        check_constrain_not_changed("libelf+debug", "+debug")
-        check_constrain_not_changed("libelf~debug", "~debug")
-        check_constrain_not_changed("libelf debug=2", "debug=2")
-        check_constrain_not_changed("libelf debug=2", "debug=*")
-        check_constrain_not_changed('libelf cppflags="-O3"', 'cppflags="-O3"')
-        check_constrain_not_changed('libelf cppflags=="-O3"', 'cppflags=="-O3"')
-
-        platform = spack.platforms.host()
-        default_target = platform.target("default_target").name
-        check_constrain_not_changed("libelf target=" + default_target, "target=" + default_target)
-
-    def test_constrain_dependency_changed(self):
-        check_constrain_changed("libelf^foo", "libelf^foo@1.0")
-        check_constrain_changed("libelf^foo", "libelf^foo@1.0:5.0")
-        check_constrain_changed("libelf^foo", "libelf^foo%gcc")
-        check_constrain_changed("libelf^foo%gcc", "libelf^foo%gcc@4.5")
-        check_constrain_changed("libelf^foo", "libelf^foo+debug")
-        check_constrain_changed("libelf^foo", "libelf^foo~debug")
-        check_constrain_changed("libelf", "^foo")
-
-        platform = spack.platforms.host()
-        default_target = platform.target("default_target").name
-        check_constrain_changed("libelf^foo", "libelf^foo target=" + default_target)
-
-    def test_constrain_dependency_not_changed(self):
-        check_constrain_not_changed("libelf^foo@1.0", "libelf^foo@1.0")
-        check_constrain_not_changed("libelf^foo@1.0:5.0", "libelf^foo@1.0:5.0")
-        check_constrain_not_changed("libelf^foo%gcc", "libelf^foo%gcc")
-        check_constrain_not_changed("libelf^foo%gcc@4.5", "libelf^foo%gcc@4.5")
-        check_constrain_not_changed("libelf^foo+debug", "libelf^foo+debug")
-        check_constrain_not_changed("libelf^foo~debug", "libelf^foo~debug")
-        check_constrain_not_changed('libelf^foo cppflags="-O3"', 'libelf^foo cppflags="-O3"')
-
-        platform = spack.platforms.host()
-        default_target = platform.target("default_target").name
-        check_constrain_not_changed(
-            "libelf^foo target=" + default_target, "libelf^foo target=" + default_target
-        )
+    @pytest.mark.parametrize(
+        "lhs,rhs",
+        [
+            ("libelf", "libelf"),
+            ("libelf@1.0", "@1.0"),
+            ("libelf@1.0:5.0", "@1.0:5.0"),
+            ("libelf%gcc", "%gcc"),
+            ("libelf%gcc@4.5", "%gcc@4.5"),
+            ("libelf+debug", "+debug"),
+            ("libelf~debug", "~debug"),
+            ("libelf debug=2", "debug=2"),
+            ("libelf debug=2", "debug=*"),
+            ('libelf cppflags="-O3"', 'cppflags="-O3"'),
+            ('libelf cppflags=="-O3"', 'cppflags=="-O3"'),
+            ("libelf^foo@1.0", "libelf^foo@1.0"),
+            ("libelf^foo@1.0:5.0", "libelf^foo@1.0:5.0"),
+            ("libelf^foo%gcc", "libelf^foo%gcc"),
+            ("libelf^foo%gcc@4.5", "libelf^foo%gcc@4.5"),
+            ("libelf^foo+debug", "libelf^foo+debug"),
+            ("libelf^foo~debug", "libelf^foo~debug"),
+            ('libelf^foo cppflags="-O3"', 'libelf^foo cppflags="-O3"'),
+        ],
+    )
+    def test_lhs_is_not_changed_when_constraining(self, lhs, rhs):
+        lhs, rhs = Spec(lhs), Spec(rhs)
+        assert lhs.intersects(rhs)
+        assert rhs.intersects(lhs)
+        assert lhs.satisfies(rhs)
+        assert lhs.constrain(rhs) is False
 
     def test_exceptional_paths_for_constructor(self):
         with pytest.raises(TypeError):
@@ -1093,7 +991,7 @@ class TestSpecSematics(object):
     @pytest.mark.regression("13111")
     def test_target_constraints(self, spec, constraint, expected_result):
         s = Spec(spec)
-        assert s.satisfies(constraint) is expected_result
+        assert s.intersects(constraint) is expected_result
 
     @pytest.mark.regression("13124")
     def test_error_message_unknown_variant(self):
@@ -1106,7 +1004,7 @@ class TestSpecSematics(object):
         d = Spec("zmpi ^fake")
         s = Spec("mpileaks")
         s._add_dependency(d, deptypes=())
-        assert s.satisfies("mpileaks ^zmpi ^fake", strict=True)
+        assert s.satisfies("mpileaks ^zmpi ^fake")
 
     @pytest.mark.parametrize("transitive", [True, False])
     def test_splice_swap_names(self, default_mock_concretization, transitive):
@@ -1295,14 +1193,131 @@ def test_package_hash_affects_dunder_and_dag_hash(mock_packages, default_mock_co
     assert a1.process_hash() != a2.process_hash()
 
 
-def test_satisfies_is_commutative_with_concrete_specs(mock_packages, default_mock_concretization):
+def test_intersects_and_satisfies_on_concretized_spec(default_mock_concretization):
+    """Test that a spec obtained by concretizing an abstract spec, satisfies the abstract spec
+    but not vice-versa.
+    """
     a1 = default_mock_concretization("a@1.0")
     a2 = Spec("a@1.0")
 
-    # strict=False means non-empty intersection, which is commutative.
+    assert a1.intersects(a2)
+    assert a2.intersects(a1)
     assert a1.satisfies(a2)
-    assert a2.satisfies(a1)
+    assert not a2.satisfies(a1)
+
+
+@pytest.mark.parametrize(
+    "abstract_spec,spec_str",
+    [
+        ("v1-provider", "v1-consumer ^conditional-provider+disable-v1"),
+        ("conditional-provider", "v1-consumer ^conditional-provider+disable-v1"),
+        ("^v1-provider", "v1-consumer ^conditional-provider+disable-v1"),
+        ("^conditional-provider", "v1-consumer ^conditional-provider+disable-v1"),
+    ],
+)
+@pytest.mark.regression("35597")
+def test_abstract_provider_in_spec(abstract_spec, spec_str, default_mock_concretization):
+    s = default_mock_concretization(spec_str)
+    assert abstract_spec in s
+
+
+@pytest.mark.parametrize(
+    "lhs,rhs,expected", [("a", "a", True), ("a", "a@1.0", True), ("a@1.0", "a", False)]
+)
+def test_abstract_contains_semantic(lhs, rhs, expected, mock_packages):
+    s, t = Spec(lhs), Spec(rhs)
+    result = s in t
+    assert result is expected
+
 
-    # strict=True means set inclusion, which is not commutative.
-    assert a1.satisfies(a2, strict=True)
-    assert not a2.satisfies(a1, strict=True)
+@pytest.mark.parametrize(
+    "factory,lhs_str,rhs_str,results",
+    [
+        # Architecture
+        (ArchSpec, "None-ubuntu20.04-None", "None-None-x86_64", (True, False, False)),
+        (ArchSpec, "None-ubuntu20.04-None", "linux-None-x86_64", (True, False, False)),
+        (ArchSpec, "None-None-x86_64:", "linux-None-haswell", (True, False, True)),
+        (ArchSpec, "None-None-x86_64:haswell", "linux-None-icelake", (False, False, False)),
+        (ArchSpec, "linux-None-None", "linux-None-None", (True, True, True)),
+        (ArchSpec, "darwin-None-None", "linux-None-None", (False, False, False)),
+        (ArchSpec, "None-ubuntu20.04-None", "None-ubuntu20.04-None", (True, True, True)),
+        (ArchSpec, "None-ubuntu20.04-None", "None-ubuntu22.04-None", (False, False, False)),
+        # Compiler
+        (CompilerSpec, "gcc", "clang", (False, False, False)),
+        (CompilerSpec, "gcc", "gcc@5", (True, False, True)),
+        (CompilerSpec, "gcc@5", "gcc@5.3", (True, False, True)),
+        (CompilerSpec, "gcc@5", "gcc@5-tag", (True, False, True)),
+        # Flags (flags are a map, so for convenience we initialize a full Spec)
+        # Note: the semantic is that of sv variants, not mv variants
+        (Spec, "cppflags=-foo", "cppflags=-bar", (False, False, False)),
+        (Spec, "cppflags='-bar -foo'", "cppflags=-bar", (False, False, False)),
+        (Spec, "cppflags=-foo", "cppflags=-foo", (True, True, True)),
+        (Spec, "cppflags=-foo", "cflags=-foo", (True, False, False)),
+        # Versions
+        (Spec, "@0.94h", "@:0.94i", (True, True, False)),
+        # Different virtuals intersect if there is at least package providing both
+        (Spec, "mpi", "lapack", (True, False, False)),
+        (Spec, "mpi", "pkgconfig", (False, False, False)),
+    ],
+)
+def test_intersects_and_satisfies(factory, lhs_str, rhs_str, results):
+    lhs = factory(lhs_str)
+    rhs = factory(rhs_str)
+
+    intersects, lhs_satisfies_rhs, rhs_satisfies_lhs = results
+
+    assert lhs.intersects(rhs) is intersects
+    assert rhs.intersects(lhs) is lhs.intersects(rhs)
+
+    assert lhs.satisfies(rhs) is lhs_satisfies_rhs
+    assert rhs.satisfies(lhs) is rhs_satisfies_lhs
+
+
+@pytest.mark.parametrize(
+    "factory,lhs_str,rhs_str,result,constrained_str",
+    [
+        # Architecture
+        (ArchSpec, "None-ubuntu20.04-None", "None-None-x86_64", True, "None-ubuntu20.04-x86_64"),
+        (ArchSpec, "None-None-x86_64", "None-None-x86_64", False, "None-None-x86_64"),
+        (
+            ArchSpec,
+            "None-None-x86_64:icelake",
+            "None-None-x86_64:icelake",
+            False,
+            "None-None-x86_64:icelake",
+        ),
+        (ArchSpec, "None-ubuntu20.04-None", "linux-None-x86_64", True, "linux-ubuntu20.04-x86_64"),
+        (
+            ArchSpec,
+            "None-ubuntu20.04-nocona:haswell",
+            "None-None-x86_64:icelake",
+            False,
+            "None-ubuntu20.04-nocona:haswell",
+        ),
+        (
+            ArchSpec,
+            "None-ubuntu20.04-nocona,haswell",
+            "None-None-x86_64:icelake",
+            False,
+            "None-ubuntu20.04-nocona,haswell",
+        ),
+        # Compiler
+        (CompilerSpec, "gcc@5", "gcc@5-tag", True, "gcc@5-tag"),
+        (CompilerSpec, "gcc@5", "gcc@5", False, "gcc@5"),
+        # Flags
+        (Spec, "cppflags=-foo", "cppflags=-foo", False, "cppflags=-foo"),
+        (Spec, "cppflags=-foo", "cflags=-foo", True, "cppflags=-foo cflags=-foo"),
+    ],
+)
+def test_constrain(factory, lhs_str, rhs_str, result, constrained_str):
+    lhs = factory(lhs_str)
+    rhs = factory(rhs_str)
+
+    assert lhs.constrain(rhs) is result
+    assert lhs == factory(constrained_str)
+
+    # The intersection must be the same, so check that invariant too
+    lhs = factory(lhs_str)
+    rhs = factory(rhs_str)
+    rhs.constrain(lhs)
+    assert rhs == factory(constrained_str)
diff --git a/lib/spack/spack/test/spec_syntax.py b/lib/spack/spack/test/spec_syntax.py
index 62396d57ef..87d1c7b8e0 100644
--- a/lib/spack/spack/test/spec_syntax.py
+++ b/lib/spack/spack/test/spec_syntax.py
@@ -1040,18 +1040,44 @@ def test_compare_abstract_specs():
         assert a <= b or b < a
 
 
-def test_git_ref_spec_equivalences(mock_packages):
-    spec_hash_fmt = "develop-branch-version@git.{hash}=develop"
-    s1 = SpecParser(spec_hash_fmt.format(hash="a" * 40)).next_spec()
-    s2 = SpecParser(spec_hash_fmt.format(hash="b" * 40)).next_spec()
-    s3 = SpecParser("develop-branch-version@git.0.2.15=develop").next_spec()
-    s_no_git = SpecParser("develop-branch-version@develop").next_spec()
-
-    assert s1.satisfies(s_no_git)
-    assert s2.satisfies(s_no_git)
-    assert not s_no_git.satisfies(s1)
-    assert not s2.satisfies(s1)
-    assert not s3.satisfies(s1)
+@pytest.mark.parametrize(
+    "lhs_str,rhs_str,expected",
+    [
+        # Git shasum vs generic develop
+        (
+            f"develop-branch-version@git.{'a' * 40}=develop",
+            "develop-branch-version@develop",
+            (True, True, False),
+        ),
+        # Two different shasums
+        (
+            f"develop-branch-version@git.{'a' * 40}=develop",
+            f"develop-branch-version@git.{'b' * 40}=develop",
+            (False, False, False),
+        ),
+        # Git shasum vs. git tag
+        (
+            f"develop-branch-version@git.{'a' * 40}=develop",
+            "develop-branch-version@git.0.2.15=develop",
+            (False, False, False),
+        ),
+        # Git tag vs. generic develop
+        (
+            "develop-branch-version@git.0.2.15=develop",
+            "develop-branch-version@develop",
+            (True, True, False),
+        ),
+    ],
+)
+def test_git_ref_spec_equivalences(mock_packages, lhs_str, rhs_str, expected):
+    lhs = SpecParser(lhs_str).next_spec()
+    rhs = SpecParser(rhs_str).next_spec()
+    intersect, lhs_sat_rhs, rhs_sat_lhs = expected
+
+    assert lhs.intersects(rhs) is intersect
+    assert rhs.intersects(lhs) is intersect
+    assert lhs.satisfies(rhs) is lhs_sat_rhs
+    assert rhs.satisfies(lhs) is rhs_sat_lhs
 
 
 @pytest.mark.regression("32471")
diff --git a/lib/spack/spack/test/variant.py b/lib/spack/spack/test/variant.py
index 18daec359f..89c2c72de6 100644
--- a/lib/spack/spack/test/variant.py
+++ b/lib/spack/spack/test/variant.py
@@ -638,11 +638,11 @@ class TestVariantMapTest(object):
         b["foobar"] = SingleValuedVariant("foobar", "fee")
         b["shared"] = BoolValuedVariant("shared", True)
 
-        assert not a.satisfies(b)
-        assert b.satisfies(a)
+        assert a.intersects(b)
+        assert b.intersects(a)
 
-        assert not a.satisfies(b, strict=True)
-        assert not b.satisfies(a, strict=True)
+        assert not a.satisfies(b)
+        assert not b.satisfies(a)
 
         # foo=bar,baz foobar=fee feebar=foo shared=True
         c = VariantMap(None)
diff --git a/lib/spack/spack/test/versions.py b/lib/spack/spack/test/versions.py
index 586908b791..f39340c529 100644
--- a/lib/spack/spack/test/versions.py
+++ b/lib/spack/spack/test/versions.py
@@ -600,6 +600,7 @@ def test_versions_from_git(git, mock_git_version_info, monkeypatch, mock_package
 
         with working_dir(repo_path):
             git("checkout", commit)
+
         with open(os.path.join(repo_path, filename), "r") as f:
             expected = f.read()
 
@@ -607,30 +608,38 @@ def test_versions_from_git(git, mock_git_version_info, monkeypatch, mock_package
 
 
 @pytest.mark.skipif(sys.platform == "win32", reason="Not supported on Windows (yet)")
-def test_git_hash_comparisons(mock_git_version_info, install_mockery, mock_packages, monkeypatch):
+@pytest.mark.parametrize(
+    "commit_idx,expected_satisfies,expected_not_satisfies",
+    [
+        # Spec based on earliest commit
+        (-1, ("@:0",), ("@1.0",)),
+        # Spec based on second commit (same as version 1.0)
+        (-2, ("@1.0",), ("@1.1:",)),
+        # Spec based on 4th commit (in timestamp order)
+        (-4, ("@1.1", "@1.0:1.2"), tuple()),
+    ],
+)
+def test_git_hash_comparisons(
+    mock_git_version_info,
+    install_mockery,
+    mock_packages,
+    monkeypatch,
+    commit_idx,
+    expected_satisfies,
+    expected_not_satisfies,
+):
     """Check that hashes compare properly to versions"""
     repo_path, filename, commits = mock_git_version_info
     monkeypatch.setattr(
         spack.package_base.PackageBase, "git", "file://%s" % repo_path, raising=False
     )
 
-    # Spec based on earliest commit
-    spec0 = spack.spec.Spec("git-test-commit@%s" % commits[-1])
-    spec0.concretize()
-    assert spec0.satisfies("@:0")
-    assert not spec0.satisfies("@1.0")
-
-    # Spec based on second commit (same as version 1.0)
-    spec1 = spack.spec.Spec("git-test-commit@%s" % commits[-2])
-    spec1.concretize()
-    assert spec1.satisfies("@1.0")
-    assert not spec1.satisfies("@1.1:")
+    spec = spack.spec.Spec(f"git-test-commit@{commits[commit_idx]}").concretized()
+    for item in expected_satisfies:
+        assert spec.satisfies(item)
 
-    # Spec based on 4th commit (in timestamp order)
-    spec4 = spack.spec.Spec("git-test-commit@%s" % commits[-4])
-    spec4.concretize()
-    assert spec4.satisfies("@1.1")
-    assert spec4.satisfies("@1.0:1.2")
+    for item in expected_not_satisfies:
+        assert not spec.satisfies(item)
 
 
 @pytest.mark.skipif(sys.platform == "win32", reason="Not supported on Windows (yet)")
@@ -738,3 +747,27 @@ def test_git_ref_can_be_assigned_a_version(vstring, eq_vstring, is_commit):
     assert v.is_ref
     assert not v._ref_lookup
     assert v_equivalent.version == v.ref_version
+
+
+@pytest.mark.parametrize(
+    "lhs_str,rhs_str,expected",
+    [
+        # VersionBase
+        ("4.7.3", "4.7.3", (True, True, True)),
+        ("4.7.3", "4.7", (True, True, False)),
+        ("4.7.3", "4", (True, True, False)),
+        ("4.7.3", "4.8", (False, False, False)),
+        # GitVersion
+        (f"git.{'a' * 40}=develop", "develop", (True, True, False)),
+        (f"git.{'a' * 40}=develop", f"git.{'a' * 40}=develop", (True, True, True)),
+        (f"git.{'a' * 40}=develop", f"git.{'b' * 40}=develop", (False, False, False)),
+    ],
+)
+def test_version_intersects_satisfies_semantic(lhs_str, rhs_str, expected):
+    lhs, rhs = ver(lhs_str), ver(rhs_str)
+    intersect, lhs_sat_rhs, rhs_sat_lhs = expected
+
+    assert lhs.intersects(rhs) is intersect
+    assert lhs.intersects(rhs) is rhs.intersects(lhs)
+    assert lhs.satisfies(rhs) is lhs_sat_rhs
+    assert rhs.satisfies(lhs) is rhs_sat_lhs
diff --git a/lib/spack/spack/util/package_hash.py b/lib/spack/spack/util/package_hash.py
index b60a576674..9343b1f689 100644
--- a/lib/spack/spack/util/package_hash.py
+++ b/lib/spack/spack/util/package_hash.py
@@ -178,7 +178,7 @@ class TagMultiMethods(ast.NodeVisitor):
                         conditions.append(None)
                     else:
                         # Check statically whether spec satisfies the condition
-                        conditions.append(self.spec.satisfies(cond_spec, strict=True))
+                        conditions.append(self.spec.satisfies(cond_spec))
 
                 except AttributeError:
                     # In this case the condition for the 'when' decorator is
diff --git a/lib/spack/spack/variant.py b/lib/spack/spack/variant.py
index 93211b8ccc..658edf48f1 100644
--- a/lib/spack/spack/variant.py
+++ b/lib/spack/spack/variant.py
@@ -203,8 +203,7 @@ def implicit_variant_conversion(method):
 
     @functools.wraps(method)
     def convert(self, other):
-        # We don't care if types are different as long as I can convert
-        # other to type(self)
+        # We don't care if types are different as long as I can convert other to type(self)
         try:
             other = type(self)(other.name, other._original_value)
         except (error.SpecError, ValueError):
@@ -349,7 +348,12 @@ class AbstractVariant(object):
         # (`foo=bar` will never satisfy `baz=bar`)
         return other.name == self.name
 
-    @implicit_variant_conversion
+    def intersects(self, other):
+        """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):
         """Returns True if self and other are compatible, False otherwise.
 
@@ -364,7 +368,7 @@ class AbstractVariant(object):
         """
         # If names are different then `self` is not compatible with `other`
         # (`foo=bar` is incompatible with `baz=bar`)
-        return other.name == self.name
+        return self.intersects(other)
 
     @implicit_variant_conversion
     def constrain(self, other):
@@ -475,6 +479,9 @@ class SingleValuedVariant(AbstractVariant):
             self.value == other.value or other.value == "*" or self.value == "*"
         )
 
+    def intersects(self, other):
+        return self.satisfies(other)
+
     def compatible(self, other):
         return self.satisfies(other)
 
@@ -575,29 +582,11 @@ class VariantMap(lang.HashableMap):
         # Set the item
         super(VariantMap, self).__setitem__(vspec.name, vspec)
 
-    def satisfies(self, other, strict=False):
-        """Returns True if this VariantMap is more constrained than other,
-        False otherwise.
-
-        Args:
-            other (VariantMap): VariantMap instance to satisfy
-            strict (bool): if True return False if a key is in other and
-                not in self, otherwise discard that key and proceed with
-                evaluation
-
-        Returns:
-            bool: True or False
-        """
-        to_be_checked = [k for k in other]
-
-        strict_or_concrete = strict
-        if self.spec is not None:
-            strict_or_concrete |= self.spec._concrete
-
-        if not strict_or_concrete:
-            to_be_checked = filter(lambda x: x in self, to_be_checked)
+    def satisfies(self, other):
+        return all(k in self and self[k].satisfies(other[k]) for k in other)
 
-        return all(k in self and self[k].satisfies(other[k]) for k in to_be_checked)
+    def intersects(self, other):
+        return all(self[k].intersects(other[k]) for k in other if k in self)
 
     def constrain(self, other):
         """Add all variants in other that aren't in self to self. Also
diff --git a/lib/spack/spack/version.py b/lib/spack/spack/version.py
index 2048e794cc..53093d9459 100644
--- a/lib/spack/spack/version.py
+++ b/lib/spack/spack/version.py
@@ -133,6 +133,9 @@ class VersionStrComponent(object):
     def __str__(self):
         return self.data
 
+    def __repr__(self):
+        return f"VersionStrComponent('{self.data}')"
+
     def __eq__(self, other):
         if isinstance(other, VersionStrComponent):
             return self.data == other.data
@@ -242,9 +245,9 @@ class VersionBase(object):
         if string and not VALID_VERSION.match(string):
             raise ValueError("Bad characters in version string: %s" % string)
 
-        self.separators, self.version = self._generate_seperators_and_components(string)
+        self.separators, self.version = self._generate_separators_and_components(string)
 
-    def _generate_seperators_and_components(self, string):
+    def _generate_separators_and_components(self, string):
         segments = SEGMENT_REGEX.findall(string)
         components = tuple(int(m[0]) if m[0] else VersionStrComponent(m[1]) for m in segments)
         separators = tuple(m[2] for m in segments)
@@ -348,11 +351,26 @@ class VersionBase(object):
         return False
 
     @coerced
-    def satisfies(self, other):
-        """A Version 'satisfies' another if it is at least as specific and has
-        a common prefix.  e.g., we want gcc@4.7.3 to satisfy a request for
-        gcc@4.7 so that when a user asks to build with gcc@4.7, we can find
-        a suitable compiler.
+    def intersects(self, other: "VersionBase") -> bool:
+        """Return True if self intersects with other, False otherwise.
+
+        Two versions intersect if one can be constrained by the other. For instance
+        @4.7 and @4.7.3 intersect (the intersection being @4.7.3).
+
+        Arg:
+            other: version to be checked for intersection
+        """
+        n = min(len(self.version), len(other.version))
+        return self.version[:n] == other.version[:n]
+
+    @coerced
+    def satisfies(self, other: "VersionBase") -> bool:
+        """Return True if self is at least as specific and share a common prefix with other.
+
+        For instance, @4.7.3 satisfies @4.7 but not vice-versa.
+
+        Arg:
+            other: version to be checked for intersection
         """
         nself = len(self.version)
         nother = len(other.version)
@@ -466,9 +484,8 @@ class VersionBase(object):
     def is_successor(self, other):
         return other.is_predecessor(self)
 
-    @coerced
     def overlaps(self, other):
-        return self in other or other in self
+        return self.intersects(other)
 
     @coerced
     def union(self, other):
@@ -548,7 +565,7 @@ class GitVersion(VersionBase):
 
         if "=" in pruned_string:
             self.ref, self.ref_version_str = pruned_string.split("=")
-            _, self.ref_version = self._generate_seperators_and_components(self.ref_version_str)
+            _, self.ref_version = self._generate_separators_and_components(self.ref_version_str)
             self.user_supplied_reference = True
         else:
             self.ref = pruned_string
@@ -578,6 +595,9 @@ class GitVersion(VersionBase):
             if ref_info:
                 prev_version, distance = ref_info
 
+                if prev_version is None:
+                    prev_version = "0"
+
                 # Extend previous version by empty component and distance
                 # If commit is exactly a known version, no distance suffix
                 prev_tuple = VersionBase(prev_version).version if prev_version else ()
@@ -588,13 +608,21 @@ class GitVersion(VersionBase):
         return self.version
 
     @coerced
+    def intersects(self, other):
+        # If they are both references, they must match exactly
+        if self.is_ref and other.is_ref:
+            return self.version == other.version
+
+        # Otherwise the ref_version of the reference must intersect with the version of the other
+        v1 = self.ref_version if self.is_ref else self.version
+        v2 = other.ref_version if other.is_ref else other.version
+        n = min(len(v1), len(v2))
+        return v1[:n] == v2[:n]
+
+    @coerced
     def satisfies(self, other):
-        """A Version 'satisfies' another if it is at least as specific and has
-        a common prefix.  e.g., we want gcc@4.7.3 to satisfy a request for
-        gcc@4.7 so that when a user asks to build with gcc@4.7, we can find
-        a suitable compiler. In the case of two GitVersions we require the ref_versions
-        to satisfy one another and the versions to be an exact match.
-        """
+        # In the case of two GitVersions we require the ref_versions
+        # to satisfy one another and the versions to be an exact match.
 
         self_cmp = self._cmp(other.ref_lookup)
         other_cmp = other._cmp(self.ref_lookup)
@@ -731,7 +759,7 @@ class VersionRange(object):
         # means the range [1.2.3, 1.3), which is non-empty.
         min_len = min(len(start), len(end))
         if end.up_to(min_len) < start.up_to(min_len):
-            raise ValueError("Invalid Version range: %s" % self)
+            raise ValueError(f"Invalid Version range: {self}")
 
     def lowest(self):
         return self.start
@@ -805,27 +833,33 @@ class VersionRange(object):
         )
         return in_upper
 
-    @coerced
-    def satisfies(self, other):
-        """
-        x.satisfies(y) in general means that x and y have a
-        non-zero intersection. For VersionRange this means they overlap.
+    def intersects(self, other) -> bool:
+        """Return two if two version ranges overlap with each other, False otherwise.
 
-        `satisfies` is a commutative binary operator, meaning that
-        x.satisfies(y) if and only if y.satisfies(x).
+        This is a commutative operation.
 
-        Note: in some cases we have the keyword x.satisfies(y, strict=True)
-        to mean strict set inclusion, which is not commutative. However, this
-        lacks in VersionRange for unknown reasons.
-
-        Examples
+        Examples:
         - 1:3 satisfies 2:4, as their intersection is 2:3.
         - 1:2 does not satisfy 3:4, as their intersection is empty.
         - 4.5:4.7 satisfies 4.7.2:4.8, as their intersection is 4.7.2:4.7
+
+        Args:
+            other: version range to be checked for intersection
         """
         return self.overlaps(other)
 
     @coerced
+    def satisfies(self, other):
+        """A version range satisfies another if it is a subset of the other.
+
+        Examples:
+        - 1:2 does not satisfy 3:4, as their intersection is empty.
+        - 1:3 does not satisfy 2:4, as they overlap but neither is a subset of the other
+        - 1:3 satisfies 1:4.
+        """
+        return self.intersection(other) == self
+
+    @coerced
     def overlaps(self, other):
         return (
             self.start is None
@@ -882,33 +916,32 @@ class VersionRange(object):
 
     @coerced
     def intersection(self, other):
-        if self.overlaps(other):
-            if self.start is None:
-                start = other.start
-            else:
-                start = self.start
-                if other.start is not None:
-                    if other.start > start or other.start in start:
-                        start = other.start
+        if not self.overlaps(other):
+            return VersionList()
 
-            if self.end is None:
-                end = other.end
-            else:
-                end = self.end
-                # TODO: does this make sense?
-                # This is tricky:
-                #     1.6.5 in 1.6 = True  (1.6.5 is more specific)
-                #     1.6 < 1.6.5  = True  (lexicographic)
-                # Should 1.6 NOT be less than 1.6.5?  Hmm.
-                # Here we test (not end in other.end) first to avoid paradox.
-                if other.end is not None and end not in other.end:
-                    if other.end < end or other.end in end:
-                        end = other.end
-
-            return VersionRange(start, end)
+        if self.start is None:
+            start = other.start
+        else:
+            start = self.start
+            if other.start is not None:
+                if other.start > start or other.start in start:
+                    start = other.start
 
+        if self.end is None:
+            end = other.end
         else:
-            return VersionList()
+            end = self.end
+            # TODO: does this make sense?
+            # This is tricky:
+            #     1.6.5 in 1.6 = True  (1.6.5 is more specific)
+            #     1.6 < 1.6.5  = True  (lexicographic)
+            # Should 1.6 NOT be less than 1.6.5?  Hmm.
+            # Here we test (not end in other.end) first to avoid paradox.
+            if other.end is not None and end not in other.end:
+                if other.end < end or other.end in end:
+                    end = other.end
+
+        return VersionRange(start, end)
 
     def __hash__(self):
         return hash((self.start, self.end))
@@ -1022,6 +1055,9 @@ class VersionList(object):
                 o += 1
         return False
 
+    def intersects(self, other):
+        return self.overlaps(other)
+
     def to_dict(self):
         """Generate human-readable dict for YAML."""
         if self.concrete:
@@ -1040,31 +1076,10 @@ class VersionList(object):
             raise ValueError("Dict must have 'version' or 'versions' in it.")
 
     @coerced
-    def satisfies(self, other, strict=False):
-        """A VersionList satisfies another if some version in the list
-        would satisfy some version in the other list.  This uses
-        essentially the same algorithm as overlaps() does for
-        VersionList, but it calls satisfies() on member Versions
-        and VersionRanges.
-
-        If strict is specified, this version list must lie entirely
-        *within* the other in order to satisfy it.
-        """
-        if not other or not self:
-            return False
-
-        if strict:
-            return self in other
-
-        s = o = 0
-        while s < len(self) and o < len(other):
-            if self[s].satisfies(other[o]):
-                return True
-            elif self[s] < other[o]:
-                s += 1
-            else:
-                o += 1
-        return False
+    def satisfies(self, other) -> bool:
+        # This exploits the fact that version lists are "reduced" and normalized, so we can
+        # never have a list like [1:3, 2:4] since that would be normalized to [1:4]
+        return all(any(lhs.satisfies(rhs) for rhs in other) for lhs in self)
 
     @coerced
     def update(self, other):