Fix for SPACK-13, and satisfies() now handles deps.

Added more test cases for multimethods.  In doing so, (re)discovered that
satisfies() really needs to handle dependencies properly.

Implemented support for dependencies in satisfies, but constrain() now
isn't consistent (as we do not currently constrain deps), so need to
implement that.

Virtual dependency support probably needs some deeper thought.  i.e.,
there is probably an intermediate DAG form that would make the needed
checks easier.  Right now we have to build ProviderIndexes to figure out
how virtual dependencies are set up.  If the vdep were preserved in the DAG,
then we could just check for things like incompatible providers directly.

11 files changed, 419 insertions, 121 deletions

diff --git a/lib/spack/spack/compilers/__init__.py b/lib/spack/spack/compilers/__init__.py
index ad2260d58a..51aafc2112 100644
--- a/lib/spack/spack/compilers/__init__.py
+++ b/lib/spack/spack/compilers/__init__.py
@@ -11,6 +11,10 @@ def supported_compilers():
     return [c for c in list_modules(spack.compilers_path)]
 
 
+def supported(compiler):
+    return compiler in supported_compilers()
+
+
 @memoized
 def default_compiler():
     from spack.spec import Compiler
diff --git a/lib/spack/spack/multimethod.py b/lib/spack/spack/multimethod.py
index 6ea040916f..4e23938748 100644
--- a/lib/spack/spack/multimethod.py
+++ b/lib/spack/spack/multimethod.py
@@ -26,7 +26,7 @@ import collections
 import spack.architecture
 import spack.error
 from spack.util.lang import *
-from spack.spec import parse_local_spec
+from spack.spec import parse_local_spec, Spec
 
 
 class SpecMultiMethod(object):
@@ -94,19 +94,37 @@ class SpecMultiMethod(object):
         spec = package_self.spec
         matching_specs = [s for s in self.method_map if s.satisfies(spec)]
 
-        if not matching_specs and self.default is None:
-            raise NoSuchMethodVersionError(type(package_self), self.__name__,
-                                           spec, self.method_map.keys())
-        elif len(matching_specs) > 1:
-            raise AmbiguousMethodVersionError(type(package_self), self.__name__,
+        # from pprint import pprint
+
+        # print "========"
+        # print "called with " + str(spec)
+        # print spec, matching_specs
+        # pprint(self.method_map)
+        # print "SATISFIES: ", [Spec('multimethod%gcc').satisfies(s) for s in self.method_map]
+        # print [spec.satisfies(s) for s in self.method_map]
+        # print
+
+        num_matches = len(matching_specs)
+        if num_matches == 0:
+            if self.default is None:
+                raise NoSuchMethodError(type(package_self), self.__name__,
+                                        spec, self.method_map.keys())
+            else:
+                method = self.default
+
+        elif num_matches == 1:
+            method = self.method_map[matching_specs[0]]
+
+        else:
+            raise AmbiguousMethodError(type(package_self), self.__name__,
                                               spec, matching_specs)
 
-        method = self.method_map[matching_specs[0]]
         return method(package_self, *args, **kwargs)
 
 
     def __str__(self):
-        return "<%s, %s>" % (self.default, self.method_map)
+        return "SpecMultiMethod {\n\tdefault: %s,\n\tspecs: %s\n}" % (
+            self.default, self.method_map)
 
 
 class when(object):
@@ -193,19 +211,19 @@ class MultiMethodError(spack.error.SpackError):
         super(MultiMethodError, self).__init__(message)
 
 
-class NoSuchMethodVersionError(spack.error.SpackError):
+class NoSuchMethodError(spack.error.SpackError):
     """Raised when we can't find a version of a multi-method."""
     def __init__(self, cls, method_name, spec, possible_specs):
-        super(NoSuchMethodVersionError, self).__init__(
+        super(NoSuchMethodError, self).__init__(
             "Package %s does not support %s called with %s.  Options are: %s"
             % (cls.__name__, method_name, spec,
                ", ".join(str(s) for s in possible_specs)))
 
 
-class AmbiguousMethodVersionError(spack.error.SpackError):
+class AmbiguousMethodError(spack.error.SpackError):
     """Raised when we can't find a version of a multi-method."""
     def __init__(self, cls, method_name, spec, matching_specs):
-        super(AmbiguousMethodVersionError, self).__init__(
+        super(AmbiguousMethodError, self).__init__(
             "Package %s has multiple versions of %s that match %s: %s"
             % (cls.__name__, method_name, spec,
                ",".join(str(s) for s in matching_specs)))
diff --git a/lib/spack/spack/packages/__init__.py b/lib/spack/spack/packages/__init__.py
index e3046d8957..d0513b8c4c 100644
--- a/lib/spack/spack/packages/__init__.py
+++ b/lib/spack/spack/packages/__init__.py
@@ -45,7 +45,7 @@ class ProviderIndex(object):
            { mpi@:1.1 : mpich,
              mpi@:2.3 : mpich2@1.9: } }
 
-       Calling find_provider(spec) will find a package that provides a
+       Calling providers_for(spec) will find specs that provide a
        matching implementation of MPI.
     """
     def __init__(self, specs, **kwargs):
@@ -61,7 +61,7 @@ class ProviderIndex(object):
 
             pkg = spec.package
             for provided_spec, provider_spec in pkg.provided.iteritems():
-                if provider_spec.satisfies(spec):
+                if provider_spec.satisfies(spec, deps=False):
                     provided_name = provided_spec.name
                     if provided_name not in self.providers:
                         self.providers[provided_name] = {}
@@ -79,8 +79,8 @@ class ProviderIndex(object):
 
 
     def providers_for(self, *vpkg_specs):
-        """Gives names of all packages that provide virtual packages
-           with the supplied names."""
+        """Gives specs of all packages that provide virtual packages
+           with the supplied specs."""
         providers = set()
         for vspec in vpkg_specs:
             # Allow string names to be passed as input, as well as specs
@@ -90,13 +90,46 @@ class ProviderIndex(object):
             # Add all the providers that satisfy the vpkg spec.
             if vspec.name in self.providers:
                 for provider_spec, spec in self.providers[vspec.name].items():
-                    if provider_spec.satisfies(vspec):
+                    if provider_spec.satisfies(vspec, deps=False):
                         providers.add(spec)
 
         # Return providers in order
         return sorted(providers)
 
 
+    # TODO: this is pretty darned nasty, and inefficient.
+    def _cross_provider_maps(self, lmap, rmap):
+        result = {}
+        for lspec in lmap:
+            for rspec in rmap:
+                try:
+                    constrained = lspec.copy().constrain(rspec)
+                    if lmap[lspec].name != rmap[rspec].name:
+                        continue
+                    result[constrained] = lmap[lspec].copy().constrain(rmap[rspec])
+                except spack.spec.UnsatisfiableSpecError:
+                    continue
+        return result
+
+
+    def satisfies(self, other):
+        """Check that providers of virtual specs are compatible."""
+        common = set(self.providers.keys())
+        common.intersection_update(other.providers.keys())
+
+        if not common:
+            return True
+
+        result = {}
+        for name in common:
+            crossed = self._cross_provider_maps(self.providers[name],
+                                                other.providers[name])
+            if crossed:
+                result[name] = crossed
+
+        return bool(result)
+
+
 @autospec
 def get(spec):
     if spec.virtual:
diff --git a/lib/spack/spack/spec.py b/lib/spack/spack/spec.py
index 088da7bd98..74bb698833 100644
--- a/lib/spack/spack/spec.py
+++ b/lib/spack/spack/spec.py
@@ -67,15 +67,16 @@ specs to avoid ambiguity.  Both are provided because ~ can cause shell
 expansion when it is the first character in an id typed on the command line.
 """
 import sys
+import itertools
+import hashlib
 from StringIO import StringIO
 
-import tty
-import hashlib
 import spack.parse
 import spack.error
 import spack.compilers
 import spack.compilers.gcc
 import spack.packages as packages
+import spack.tty as tty
 
 from spack.version import *
 from spack.color import *
@@ -102,7 +103,11 @@ color_formats = {'%' : compiler_color,
                  '^' : dependency_color }
 
 """Regex used for splitting by spec field separators."""
-separators = '[%s]' % ''.join(color_formats.keys())
+_separators = '[%s]' % ''.join(color_formats.keys())
+
+"""Versionlist constant so we don't have to build a list
+   every time we call str()"""
+_any_version = VersionList([':'])
 
 
 def index_specs(specs):
@@ -134,7 +139,7 @@ def colorize_spec(spec):
 
             return '%s%s' % (color_formats[sep], cescape(sep))
 
-    return colorize(re.sub(separators, insert_color(), str(spec)) + '@.')
+    return colorize(re.sub(_separators, insert_color(), str(spec)) + '@.')
 
 
 @key_ordering
@@ -143,9 +148,6 @@ class Compiler(object):
        versions that a package should be built with.  Compilers have a
        name and a version list. """
     def __init__(self, name, version=None):
-        if name not in spack.compilers.supported_compilers():
-            raise UnknownCompilerError(name)
-
         self.name = name
         self.versions = VersionList()
         if version:
@@ -193,7 +195,7 @@ class Compiler(object):
 
     def __str__(self):
         out = self.name
-        if self.versions:
+        if self.versions and self.versions != _any_version:
             vlist = ",".join(str(v) for v in self.versions)
             out += "@%s" % vlist
         return out
@@ -242,11 +244,6 @@ class DependencyMap(HashableMap):
         return all(d.concrete for d in self.values())
 
 
-    def satisfies(self, other):
-        return all(self[name].satisfies(other[name]) for name in self
-                   if name in other)
-
-
     def sha1(self):
         sha = hashlib.sha1()
         sha.update(str(self))
@@ -656,8 +653,8 @@ class Spec(object):
            TODO: normalize should probably implement some form of cycle detection,
            to ensure that the spec is actually a DAG.
         """
-        # Ensure first that all packages in the DAG exist.
-        self.validate_package_names()
+        # Ensure first that all packages & compilers in the DAG exist.
+        self.validate_names()
 
         # Then ensure that the packages referenced are sane, that the
         # provided spec is sane, and that all dependency specs are in the
@@ -689,12 +686,29 @@ class Spec(object):
                 self.name + " does not depend on " + comma_or(extra))
 
 
-    def validate_package_names(self):
+    def normalized(self):
+        """Return a normalized copy of this spec without modifying this spec."""
+        clone = self.copy()
+        clone.normalized()
+        return clone
+
+
+    def validate_names(self):
+        """This checks that names of packages and compilers in this spec are real.
+           If they're not, it will raise either UnknownPackageError or
+           UnknownCompilerError.
+        """
         for spec in self.preorder_traversal():
             # Don't get a package for a virtual name.
             if not spec.virtual:
                 packages.get(spec.name)
 
+            # validate compiler name in addition to the package name.
+            if spec.compiler:
+                compiler_name = spec.compiler.name
+                if not spack.compilers.supported(compiler_name):
+                    raise UnknownCompilerError(compiler_name)
+
 
     def constrain(self, other):
         if not self.versions.overlaps(other.versions):
@@ -720,21 +734,63 @@ class Spec(object):
         self.variants.update(other.variants)
         self.architecture = self.architecture or other.architecture
 
+        # TODO: constrain dependencies, too.
 
-    def satisfies(self, other):
+
+    def satisfies(self, other, **kwargs):
         if not isinstance(other, Spec):
             other = Spec(other)
 
-        def sat(attribute):
+        # First thing we care about is whether the name matches
+        if self.name != other.name:
+            return False
+
+        # This function simplifies null checking below
+        def check(attribute, op):
             s = getattr(self, attribute)
             o = getattr(other, attribute)
-            return not s or not o or s.satisfies(o)
+            return not s or not o or op(s,o)
 
-        return (self.name == other.name and
-                all(sat(attr) for attr in
-                    ('versions', 'variants', 'compiler', 'architecture')) and
-                # TODO: what does it mean to satisfy deps?
-                self.dependencies.satisfies(other.dependencies))
+        # All these attrs have satisfies criteria of their own
+        for attr in ('versions', 'variants', 'compiler'):
+            if not check(attr, lambda s, o: s.satisfies(o)):
+                return False
+
+        # Architecture is just a string
+        # TODO: inviestigate making an Architecture class for symmetry
+        if not check('architecture', lambda s,o: s == o):
+            return False
+
+        if kwargs.get('deps', True):
+            return self.satisfies_dependencies(other)
+        else:
+            return True
+
+
+    def satisfies_dependencies(self, other):
+        """This checks constraints on common dependencies against each other."""
+        # if either spec doesn't restrict dependencies then both are compatible.
+        if not self.dependencies or not other.dependencies:
+            return True
+
+        common = set(s.name for s in self.preorder_traversal(root=False))
+        common.intersection_update(s.name for s in other.preorder_traversal(root=False))
+
+        # Handle first-order constraints directly
+        for name in common:
+            if not self[name].satisfies(other[name]):
+                return False
+
+        # For virtual dependencies, we need to dig a little deeper.
+        self_index = packages.ProviderIndex(self.preorder_traversal())
+        other_index = packages.ProviderIndex(other.preorder_traversal())
+
+        return self_index.satisfies(other_index)
+
+
+    def virtual_dependencies(self):
+        """Return list of any virtual deps in this spec."""
+        return [spec for spec in self.preorder_traversal() if spec.virtual]
 
 
     def _dup(self, other, **kwargs):
@@ -848,7 +904,7 @@ class Spec(object):
                 if c == '_':
                     out.write(self.name)
                 elif c == '@':
-                    if self.versions and self.versions != VersionList([':']):
+                    if self.versions and self.versions != _any_version:
                         write(c + str(self.versions), c)
                 elif c == '%':
                     if self.compiler:
@@ -1078,6 +1134,8 @@ class SpecParser(spack.parse.Parser):
             vlist = self.version_list()
             for version in vlist:
                 compiler._add_version(version)
+        else:
+            compiler.versions = VersionList(':')
         return compiler
 
 
diff --git a/lib/spack/spack/test/__init__.py b/lib/spack/spack/test/__init__.py
index 242ddc0991..c36035e40c 100644
--- a/lib/spack/spack/test/__init__.py
+++ b/lib/spack/spack/test/__init__.py
@@ -10,6 +10,7 @@ test_names = ['versions',
               'url_parse',
               'stage',
               'spec_syntax',
+              'spec_semantics',
               'spec_dag',
               'concretize',
               'multimethod']
diff --git a/lib/spack/spack/test/mock_packages/multimethod.py b/lib/spack/spack/test/mock_packages/multimethod.py
index 7e152f6911..fa8497eafc 100644
--- a/lib/spack/spack/test/mock_packages/multimethod.py
+++ b/lib/spack/spack/test/mock_packages/multimethod.py
@@ -37,3 +37,65 @@ class Multimethod(Package):
     def version_overlap(self):
         pass
 
+
+
+    #
+    # Use these to test whether the default method is called when no
+    # match is found.  This also tests whether we can switch methods
+    # on compilers
+    #
+    def has_a_default(self):
+        return 'default'
+
+    @when('%gcc')
+    def has_a_default(self):
+        return 'gcc'
+
+    @when('%intel')
+    def has_a_default(self):
+        return 'intel'
+
+
+
+    #
+    # Make sure we can switch methods on different architectures
+    #
+    @when('=x86_64')
+    def different_by_architecture(self):
+        return 'x86_64'
+
+    @when('=ppc64')
+    def different_by_architecture(self):
+        return 'ppc64'
+
+    @when('=ppc32')
+    def different_by_architecture(self):
+        return 'ppc32'
+
+    @when('=arm64')
+    def different_by_architecture(self):
+        return 'arm64'
+
+
+    #
+    # Make sure we can switch methods on different dependencies
+    #
+    @when('^mpich')
+    def different_by_dep(self):
+        return 'mpich'
+
+    @when('^zmpi')
+    def different_by_dep(self):
+        return 'zmpi'
+
+
+    #
+    # Make sure we can switch on virtual dependencies
+    #
+    @when('^mpi@2:')
+    def different_by_virtual_dep(self):
+        return 'mpi@2:'
+
+    @when('^mpi@:1')
+    def different_by_virtual_dep(self):
+        return 'mpi@:1'
diff --git a/lib/spack/spack/test/mock_packages/zmpi.py b/lib/spack/spack/test/mock_packages/zmpi.py
index 98231b6837..93b6193eec 100644
--- a/lib/spack/spack/test/mock_packages/zmpi.py
+++ b/lib/spack/spack/test/mock_packages/zmpi.py
@@ -8,7 +8,7 @@ class Zmpi(Package):
 
     versions = { '1.0' : 'foobarbaz' }
 
-    provides('mpi@10.0:')
+    provides('mpi@:10.0')
     depends_on('fake')
 
     def install(self, prefix):
diff --git a/lib/spack/spack/test/multimethod.py b/lib/spack/spack/test/multimethod.py
index 8f63e0bad3..4627e06142 100644
--- a/lib/spack/spack/test/multimethod.py
+++ b/lib/spack/spack/test/multimethod.py
@@ -15,7 +15,8 @@ class MultiMethodTest(MockPackagesTest):
 
     def test_no_version_match(self):
         pkg = packages.get('multimethod@2.0')
-        self.assertRaises(NoSuchMethodVersionError, pkg.no_version_2)
+        self.assertRaises(NoSuchMethodError, pkg.no_version_2)
+
 
     def test_one_version_match(self):
         pkg = packages.get('multimethod@1.0')
@@ -28,7 +29,56 @@ class MultiMethodTest(MockPackagesTest):
         self.assertEqual(pkg.no_version_2(), 4)
 
 
-    def test_multiple_matches(self):
+    def test_version_overlap(self):
         pkg = packages.get('multimethod@3.0')
-        self.assertRaises(AmbiguousMethodVersionError, pkg.version_overlap)
+        self.assertRaises(AmbiguousMethodError, pkg.version_overlap)
+
+
+    def test_default_works(self):
+        pkg = packages.get('multimethod%gcc')
+        self.assertEqual(pkg.has_a_default(), 'gcc')
+
+        pkg = packages.get('multimethod%intel')
+        self.assertEqual(pkg.has_a_default(), 'intel')
+
+        pkg = packages.get('multimethod%pgi')
+        self.assertEqual(pkg.has_a_default(), 'default')
+
+
+    def test_architecture_match(self):
+        pkg = packages.get('multimethod=x86_64')
+        self.assertEqual(pkg.different_by_architecture(), 'x86_64')
+
+        pkg = packages.get('multimethod=ppc64')
+        self.assertEqual(pkg.different_by_architecture(), 'ppc64')
+
+        pkg = packages.get('multimethod=ppc32')
+        self.assertEqual(pkg.different_by_architecture(), 'ppc32')
+
+        pkg = packages.get('multimethod=arm64')
+        self.assertEqual(pkg.different_by_architecture(), 'arm64')
+
+        pkg = packages.get('multimethod=macos')
+        self.assertRaises(NoSuchMethodError, pkg.different_by_architecture)
+
+
+    def test_dependency_match(self):
+        pkg = packages.get('multimethod^zmpi')
+        self.assertEqual(pkg.different_by_dep(), 'zmpi')
+
+        pkg = packages.get('multimethod^mpich')
+        self.assertEqual(pkg.different_by_dep(), 'mpich')
+
+
+    def test_ambiguous_dep(self):
+        """If we try to switch on some entirely different dep, it's ambiguous"""
+        pkg = packages.get('multimethod^foobar')
+        self.assertRaises(AmbiguousMethodError, pkg.different_by_dep)
+
+
+    def test_one_dep_match(self):
+        pass
+
 
+    def test_one_dep_match(self):
+        pass
diff --git a/lib/spack/spack/test/spec_dag.py b/lib/spack/spack/test/spec_dag.py
index d662dd00e1..fe477bf6f9 100644
--- a/lib/spack/spack/test/spec_dag.py
+++ b/lib/spack/spack/test/spec_dag.py
@@ -1,10 +1,8 @@
 """
-These tests check validation of dummy packages.  You can find the dummy
-packages directories that these tests use in:
+These tests check Spec DAG operations using dummy packages.
+You can find the dummy packages here::
 
     spack/lib/spack/spack/test/mock_packages
-
-Each test validates conditions with the packages in those directories.
 """
 import spack
 import spack.package
@@ -15,7 +13,7 @@ from spack.spec import Spec
 from spack.test.mock_packages_test import *
 
 
-class ValidationTest(MockPackagesTest):
+class SpecDagTest(MockPackagesTest):
 
     def test_conflicting_package_constraints(self):
         set_pkg_dep('mpileaks', 'mpich@1.0')
@@ -279,6 +277,8 @@ class ValidationTest(MockPackagesTest):
 
     def test_contains(self):
         spec = Spec('mpileaks ^mpi ^libelf@1.8.11 ^libdwarf')
+
+        print [s for s in spec.preorder_traversal()]
         self.assertIn(Spec('mpi'), spec)
         self.assertIn(Spec('libelf'), spec)
         self.assertIn(Spec('libelf@1.8.11'), spec)
diff --git a/lib/spack/spack/test/spec_semantics.py b/lib/spack/spack/test/spec_semantics.py
new file mode 100644
index 0000000000..7ed5ae90b0
--- /dev/null
+++ b/lib/spack/spack/test/spec_semantics.py
@@ -0,0 +1,141 @@
+import unittest
+from spack.spec import *
+from spack.test.mock_packages_test import *
+
+class SpecSematicsTest(MockPackagesTest):
+    """This tests satisfies(), constrain() and other semantic operations
+       on specs."""
+
+    # ================================================================================
+    # Utility functions to set everything up.
+    # ================================================================================
+    def check_satisfies(self, lspec, rspec):
+        l, r = Spec(lspec), Spec(rspec)
+        self.assertTrue(l.satisfies(r))
+        self.assertTrue(r.satisfies(l))
+
+        try:
+            l.constrain(r)
+            r.constrain(l)
+        except SpecError, e:
+            self.fail("Got a SpecError in constrain!", e.message)
+
+
+    def check_unsatisfiable(self, lspec, rspec):
+        l, r = Spec(lspec), Spec(rspec)
+        self.assertFalse(l.satisfies(r))
+        self.assertFalse(r.satisfies(l))
+
+        self.assertRaises(UnsatisfiableSpecError, l.constrain, r)
+        self.assertRaises(UnsatisfiableSpecError, r.constrain, l)
+
+
+    def check_constrain(self, expected, constrained, constraint):
+        exp = Spec(expected)
+        constrained = Spec(constrained)
+        constraint = Spec(constraint)
+        constrained.constrain(constraint)
+        self.assertEqual(exp, constrained)
+
+
+    def check_invalid_constraint(self, constrained, constraint):
+        constrained = Spec(constrained)
+        constraint = Spec(constraint)
+        self.assertRaises(UnsatisfiableSpecError, constrained.constrain, constraint)
+
+
+    # ================================================================================
+    # Satisfiability and constraints
+    # ================================================================================
+    def test_satisfies(self):
+        self.check_satisfies('libelf@0.8.13', 'libelf@0:1')
+        self.check_satisfies('libdwarf^libelf@0.8.13', 'libdwarf^libelf@0:1')
+
+
+    def test_satisfies_compiler(self):
+        self.check_satisfies('foo%gcc', 'foo%gcc')
+        self.check_satisfies('foo%intel', 'foo%intel')
+        self.check_unsatisfiable('foo%intel', 'foo%gcc')
+        self.check_unsatisfiable('foo%intel', 'foo%pgi')
+
+
+    def test_satisfies_compiler_version(self):
+        self.check_satisfies('foo%gcc', 'foo%gcc@4.7.2')
+        self.check_satisfies('foo%intel', 'foo%intel@4.7.2')
+
+        self.check_satisfies('foo%pgi@4.5', 'foo%pgi@4.4:4.6')
+        self.check_satisfies('foo@2.0%pgi@4.5', 'foo@1:3%pgi@4.4:4.6')
+
+        self.check_unsatisfiable('foo%pgi@4.3', 'foo%pgi@4.4:4.6')
+        self.check_unsatisfiable('foo@4.0%pgi', 'foo@1:3%pgi')
+        self.check_unsatisfiable('foo@4.0%pgi@4.5', 'foo@1:3%pgi@4.4:4.6')
+
+
+    def test_satisfies_architecture(self):
+        self.check_satisfies('foo=chaos_5_x86_64_ib', 'foo=chaos_5_x86_64_ib')
+        self.check_satisfies('foo=bgqos_0', 'foo=bgqos_0')
+
+        self.check_unsatisfiable('foo=bgqos_0', 'foo=chaos_5_x86_64_ib')
+        self.check_unsatisfiable('foo=chaos_5_x86_64_ib', 'foo=bgqos_0')
+
+
+    def test_satisfies_dependencies(self):
+#        self.check_satisfies('mpileaks^mpich', 'mpileaks^mpich')
+#        self.check_satisfies('mpileaks^zmpi', 'mpileaks^zmpi')
+        self.check_unsatisfiable('mpileaks^mpich', 'mpileaks^zmpi')
+        self.check_unsatisfiable('mpileaks^zmpi', 'mpileaks^mpich')
+
+
+    def ztest_satisfies_dependency_versions(self):
+        self.check_satisfies('mpileaks^mpich@2.0', 'mpileaks^mpich@1:3')
+        self.check_unsatisfiable('mpileaks^mpich@1.2', 'mpileaks^mpich@2.0')
+
+        self.check_satisfies('mpileaks^mpich@2.0^callpath@1.5', 'mpileaks^mpich@1:3^callpath@1.4:1.6')
+        self.check_unsatisfiable('mpileaks^mpich@4.0^callpath@1.5', 'mpileaks^mpich@1:3^callpath@1.4:1.6')
+        self.check_unsatisfiable('mpileaks^mpich@2.0^callpath@1.7', 'mpileaks^mpich@1:3^callpath@1.4:1.6')
+        self.check_unsatisfiable('mpileaks^mpich@4.0^callpath@1.7', 'mpileaks^mpich@1:3^callpath@1.4:1.6')
+
+
+    def ztest_satisfies_virtual_dependencies(self):
+        self.check_satisfies('mpileaks^mpi', 'mpileaks^mpi')
+        self.check_satisfies('mpileaks^mpi', 'mpileaks^mpich')
+
+        self.check_satisfies('mpileaks^mpi', 'mpileaks^zmpi')
+        self.check_unsatisfiable('mpileaks^mpich', 'mpileaks^zmpi')
+
+
+    def ztest_satisfies_virtual_dependency_versions(self):
+        self.check_satisfies('mpileaks^mpi@1.5', 'mpileaks^mpi@1.2:1.6')
+        self.check_unsatisfiable('mpileaks^mpi@3', 'mpileaks^mpi@1.2:1.6')
+
+        self.check_satisfies('mpileaks^mpi@2:', 'mpileaks^mpich')
+        self.check_satisfies('mpileaks^mpi@2:', 'mpileaks^mpich@3.0.4')
+        self.check_satisfies('mpileaks^mpi@2:', 'mpileaks^mpich2@1.4')
+
+        self.check_unsatisfiable('mpileaks^mpi@3:', 'mpileaks^mpich2@1.4')
+        self.check_unsatisfiable('mpileaks^mpi@3:', 'mpileaks^mpich@1.0')
+
+
+    def test_constrain(self):
+        self.check_constrain('libelf@2.1:2.5', 'libelf@0:2.5', 'libelf@2.1:3')
+        self.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')
+
+        self.check_constrain('libelf+debug+foo', 'libelf+debug', 'libelf+foo')
+        self.check_constrain('libelf+debug+foo', 'libelf+debug', 'libelf+debug+foo')
+
+        self.check_constrain('libelf+debug~foo', 'libelf+debug', 'libelf~foo')
+        self.check_constrain('libelf+debug~foo', 'libelf+debug', 'libelf+debug~foo')
+
+        self.check_constrain('libelf=bgqos_0', 'libelf=bgqos_0', 'libelf=bgqos_0')
+        self.check_constrain('libelf=bgqos_0', 'libelf', 'libelf=bgqos_0')
+
+
+    def test_invalid_constraint(self):
+        self.check_invalid_constraint('libelf@0:2.0', 'libelf@2.1:3')
+        self.check_invalid_constraint('libelf@0:2.5%gcc@4.8:4.9', 'libelf@2.1:3%gcc@4.5:4.7')
+
+        self.check_invalid_constraint('libelf+debug', 'libelf~debug')
+        self.check_invalid_constraint('libelf+debug~foo', 'libelf+debug+foo')
+
+        self.check_invalid_constraint('libelf=bgqos_0', 'libelf=x86_54')
diff --git a/lib/spack/spack/test/spec_syntax.py b/lib/spack/spack/test/spec_syntax.py
index 33534a4c1d..6e430873e2 100644
--- a/lib/spack/spack/test/spec_syntax.py
+++ b/lib/spack/spack/test/spec_syntax.py
@@ -29,7 +29,7 @@ complex_lex = [Token(ID, 'mvapich_foo'),
                Token(ID, '8.1_1e')]
 
 
-class SpecTest(unittest.TestCase):
+class SpecSyntaxTest(unittest.TestCase):
     # ================================================================================
     # Parse checks
     # ================================================================================
@@ -59,42 +59,6 @@ class SpecTest(unittest.TestCase):
                 # Only check the type for non-identifiers.
                 self.assertEqual(tok.type, spec_tok.type)
 
-
-    def check_satisfies(self, lspec, rspec):
-        l, r = Spec(lspec), Spec(rspec)
-        self.assertTrue(l.satisfies(r))
-        self.assertTrue(r.satisfies(l))
-
-        try:
-            l.constrain(r)
-            r.constrain(l)
-        except SpecError, e:
-            self.fail("Got a SpecError in constrain!", e.message)
-
-
-    def assert_unsatisfiable(lspec, rspec):
-        l, r = Spec(lspec), Spec(rspec)
-        self.assertFalse(l.satisfies(r))
-        self.assertFalse(r.satisfies(l))
-
-        self.assertRaises(l.constrain, r)
-        self.assertRaises(r.constrain, l)
-
-
-    def check_constrain(self, expected, constrained, constraint):
-        exp = Spec(expected)
-        constrained = Spec(constrained)
-        constraint = Spec(constraint)
-        constrained.constrain(constraint)
-        self.assertEqual(exp, constrained)
-
-
-    def check_invalid_constraint(self, constrained, constraint):
-        constrained = Spec(constrained)
-        constraint = Spec(constraint)
-        self.assertRaises(UnsatisfiableSpecError, constrained.constrain, constraint)
-
-
     # ================================================================================
     # Parse checks
     # ===============================================================================
@@ -154,39 +118,6 @@ class SpecTest(unittest.TestCase):
 
 
     # ================================================================================
-    # Satisfiability and constraints
-    # ================================================================================
-    def test_satisfies(self):
-        self.check_satisfies('libelf@0.8.13', 'libelf@0:1')
-        self.check_satisfies('libdwarf^libelf@0.8.13', 'libdwarf^libelf@0:1')
-
-
-    def test_constrain(self):
-        self.check_constrain('libelf@2.1:2.5', 'libelf@0:2.5', 'libelf@2.1:3')
-        self.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')
-
-        self.check_constrain('libelf+debug+foo', 'libelf+debug', 'libelf+foo')
-        self.check_constrain('libelf+debug+foo', 'libelf+debug', 'libelf+debug+foo')
-
-        self.check_constrain('libelf+debug~foo', 'libelf+debug', 'libelf~foo')
-        self.check_constrain('libelf+debug~foo', 'libelf+debug', 'libelf+debug~foo')
-
-        self.check_constrain('libelf=bgqos_0', 'libelf=bgqos_0', 'libelf=bgqos_0')
-        self.check_constrain('libelf=bgqos_0', 'libelf', 'libelf=bgqos_0')
-
-
-    def test_invalid_constraint(self):
-        self.check_invalid_constraint('libelf@0:2.0', 'libelf@2.1:3')
-        self.check_invalid_constraint('libelf@0:2.5%gcc@4.8:4.9', 'libelf@2.1:3%gcc@4.5:4.7')
-
-        self.check_invalid_constraint('libelf+debug', 'libelf~debug')
-        self.check_invalid_constraint('libelf+debug~foo', 'libelf+debug+foo')
-
-        self.check_invalid_constraint('libelf=bgqos_0', 'libelf=x86_54')
-
-
-    # ================================================================================
     # Lex checks
     # ================================================================================
     def test_ambiguous(self):