constrain() now consistent with satisfies()

- Added checks to constrain() so that it is consistent with satisfies()
- Added many more test cases for satisfiability and constraints on deps
- Virtual packages are handled properly in satisfies() and constrain()
	- bugfix: mpileaks^mpich2 would satisfy mpileaks^mpi@3:
	- this case is now handled.

5 files changed, 103 insertions, 32 deletions

diff --git a/lib/spack/spack/multimethod.py b/lib/spack/spack/multimethod.py
index 4e23938748..8a9bd3696f 100644
--- a/lib/spack/spack/multimethod.py
+++ b/lib/spack/spack/multimethod.py
@@ -93,17 +93,6 @@ class SpecMultiMethod(object):
         """
         spec = package_self.spec
         matching_specs = [s for s in self.method_map if s.satisfies(spec)]
-
-        # 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:
diff --git a/lib/spack/spack/packages/__init__.py b/lib/spack/spack/packages/__init__.py
index d0513b8c4c..0caf195308 100644
--- a/lib/spack/spack/packages/__init__.py
+++ b/lib/spack/spack/packages/__init__.py
@@ -49,7 +49,11 @@ class ProviderIndex(object):
        matching implementation of MPI.
     """
     def __init__(self, specs, **kwargs):
+        # TODO: come up with another name for this.  This "restricts" values to
+        # the verbatim impu specs (i.e., it doesn't pre-apply package's constraints, and
+        # keeps things as broad as possible, so it's really the wrong name)
         restrict = kwargs.setdefault('restrict', False)
+
         self.providers = {}
 
         for spec in specs:
@@ -106,17 +110,21 @@ class ProviderIndex(object):
                     constrained = lspec.copy().constrain(rspec)
                     if lmap[lspec].name != rmap[rspec].name:
                         continue
-                    result[constrained] = lmap[lspec].copy().constrain(rmap[rspec])
+                    result[constrained] = lmap[lspec].copy().constrain(
+                        rmap[rspec], deps=False)
                 except spack.spec.UnsatisfiableSpecError:
                     continue
         return result
 
 
+    def __contains__(self, name):
+        """Whether a particular vpkg name is in the index."""
+        return name in self.providers
+
+
     def satisfies(self, other):
         """Check that providers of virtual specs are compatible."""
-        common = set(self.providers.keys())
-        common.intersection_update(other.providers.keys())
-
+        common = set(self.providers) & set(other.providers)
         if not common:
             return True
 
@@ -130,6 +138,7 @@ class ProviderIndex(object):
         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 74bb698833..c27203f05e 100644
--- a/lib/spack/spack/spec.py
+++ b/lib/spack/spack/spec.py
@@ -710,7 +710,10 @@ class Spec(object):
                     raise UnknownCompilerError(compiler_name)
 
 
-    def constrain(self, other):
+    def constrain(self, other, **kwargs):
+        if not self.name == other.name:
+            raise UnsatisfiableSpecNameError(self.name, other.name)
+
         if not self.versions.overlaps(other.versions):
             raise UnsatisfiableVersionSpecError(self.versions, other.versions)
 
@@ -734,7 +737,45 @@ class Spec(object):
         self.variants.update(other.variants)
         self.architecture = self.architecture or other.architecture
 
-        # TODO: constrain dependencies, too.
+        if kwargs.get('deps', True):
+            self.constrain_dependencies(other)
+
+
+    def constrain_dependencies(self, other):
+        """Apply constraints of other spec's dependencies to this spec."""
+        if not self.dependencies or not other.dependencies:
+            return
+
+        # 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 specici about what's wrong.
+        if not self.satisfies_dependencies(other):
+            raise UnsatisfiableDependencySpecError(self, other)
+
+        # Handle common first-order constraints directly
+        for name in self.common_dependencies(other):
+            self[name].constrain(other[name], deps=False)
+
+        # Update with additional constraints from other spec
+        for name in other.dep_difference(self):
+            self._add_dependency(other[name].copy())
+
+
+    def common_dependencies(self, other):
+        """Return names of dependencies that self an other have in common."""
+        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))
+        return common
+
+
+    def dep_difference(self, other):
+        """Returns dependencies in self that are not in other."""
+        mine = set(s.name for s in self.preorder_traversal(root=False))
+        mine.difference_update(
+            s.name for s in other.preorder_traversal(root=False))
+        return mine
 
 
     def satisfies(self, other, **kwargs):
@@ -773,19 +814,33 @@ class Spec(object):
         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:
+        for name in self.common_dependencies(other):
             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())
+        self_index = packages.ProviderIndex(
+            self.preorder_traversal(), restrict=True)
+        other_index = packages.ProviderIndex(
+            other.preorder_traversal(), restrict=True)
+
+        # This handles cases where there are already providers for both vpkgs
+        if not self_index.satisfies(other_index):
+            return False
+
+        # These two loops handle cases where there is an overly restrictive vpkg
+        # in one spec for a provider in the other (e.g., mpi@3: is not compatible
+        # with mpich2)
+        for spec in self.virtual_dependencies():
+            if spec.name in other_index and not other_index.providers_for(spec):
+                return False
+
+        for spec in other.virtual_dependencies():
+            if spec.name in self_index and not self_index.providers_for(spec):
+                return False
 
-        return self_index.satisfies(other_index)
+        return True
 
 
     def virtual_dependencies(self):
@@ -840,7 +895,7 @@ class Spec(object):
 
 
     def __getitem__(self, name):
-        """TODO: does the way this is written make sense?"""
+        """TODO: reconcile __getitem__, _add_dependency, __contains__"""
         for spec in self.preorder_traversal():
             if spec.name == name:
                 return spec
@@ -1268,6 +1323,13 @@ class UnsatisfiableSpecError(SpecError):
         self.constraint_type = constraint_type
 
 
+class UnsatisfiableSpecNameError(UnsatisfiableSpecError):
+    """Raised when two specs aren't even for the same package."""
+    def __init__(self, provided, required):
+        super(UnsatisfiableVersionSpecError, self).__init__(
+            provided, required, "name")
+
+
 class UnsatisfiableVersionSpecError(UnsatisfiableSpecError):
     """Raised when a spec version conflicts with package constraints."""
     def __init__(self, provided, required):
@@ -1302,3 +1364,11 @@ class UnsatisfiableProviderSpecError(UnsatisfiableSpecError):
     def __init__(self, provided, required):
         super(UnsatisfiableProviderSpecError, self).__init__(
             provided, required, "provider")
+
+# TODO: get rid of this and be more specific about particular incompatible
+# dep constraints
+class UnsatisfiableDependencySpecError(UnsatisfiableSpecError):
+    """Raised when some dependency of constrained specs are incompatible"""
+    def __init__(self, provided, required):
+        super(UnsatisfiableDependencySpecError, self).__init__(
+            provided, required, "dependency")
diff --git a/lib/spack/spack/test/spec_dag.py b/lib/spack/spack/test/spec_dag.py
index fe477bf6f9..efce8d8659 100644
--- a/lib/spack/spack/test/spec_dag.py
+++ b/lib/spack/spack/test/spec_dag.py
@@ -277,8 +277,6 @@ class SpecDagTest(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
index 7ed5ae90b0..3c6351c074 100644
--- a/lib/spack/spack/test/spec_semantics.py
+++ b/lib/spack/spack/test/spec_semantics.py
@@ -80,13 +80,14 @@ class SpecSematicsTest(MockPackagesTest):
 
 
     def test_satisfies_dependencies(self):
-#        self.check_satisfies('mpileaks^mpich', 'mpileaks^mpich')
-#        self.check_satisfies('mpileaks^zmpi', 'mpileaks^zmpi')
+        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):
+    def test_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')
 
@@ -96,7 +97,7 @@ class SpecSematicsTest(MockPackagesTest):
         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):
+    def test_satisfies_virtual_dependencies(self):
         self.check_satisfies('mpileaks^mpi', 'mpileaks^mpi')
         self.check_satisfies('mpileaks^mpi', 'mpileaks^mpich')
 
@@ -104,7 +105,7 @@ class SpecSematicsTest(MockPackagesTest):
         self.check_unsatisfiable('mpileaks^mpich', 'mpileaks^zmpi')
 
 
-    def ztest_satisfies_virtual_dependency_versions(self):
+    def test_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')
 
@@ -112,7 +113,11 @@ class SpecSematicsTest(MockPackagesTest):
         self.check_satisfies('mpileaks^mpi@2:', 'mpileaks^mpich@3.0.4')
         self.check_satisfies('mpileaks^mpi@2:', 'mpileaks^mpich2@1.4')
 
+        self.check_satisfies('mpileaks^mpi@1:', 'mpileaks^mpich2')
+        self.check_satisfies('mpileaks^mpi@2:', 'mpileaks^mpich2')
+
         self.check_unsatisfiable('mpileaks^mpi@3:', 'mpileaks^mpich2@1.4')
+        self.check_unsatisfiable('mpileaks^mpi@3:', 'mpileaks^mpich2')
         self.check_unsatisfiable('mpileaks^mpi@3:', 'mpileaks^mpich@1.0')