Work on SPACK-41: Optional dependencies work for simple conditions.

- Can depend conditionally based on variant, compiler, arch, deps, etc
  - normalize() is not iterative yet: no chaining depends_ons
  - really need a SAT solver, but iterative will at least handle
    simple cases.

- Added "strict" option to Spec.satisfies()
  - strict checks that ALL of other's constraints are met (not just
    the ones self shares)
  - Consider splitting these out into two methods: could_satisfy() and
    satisfies()
    - didn't do this yet as it would require changing code that uses
      satisfies()

- Changed semantics of __contains__ to use strict satisfaction (SPACK-56)

- Added tests for optional dependencies.

- The constrain() method on Specs, compilers, versions, etc. now
  returns whether the spec changed as a result of the call.

14 files changed, 397 insertions, 159 deletions

diff --git a/lib/spack/spack/directives.py b/lib/spack/spack/directives.py
index 5c17fe4044..9297d6dac3 100644
--- a/lib/spack/spack/directives.py
+++ b/lib/spack/spack/directives.py
@@ -115,10 +115,7 @@ class directive(object):
 
     """
 
-    def __init__(self, **kwargs):
-        # dict argument allows directives to have storage on the package.
-        dicts = kwargs.get('dicts', None)
-
+    def __init__(self, dicts=None):
         if isinstance(dicts, basestring):
             dicts = (dicts,)
         elif type(dicts) not in (list, tuple):
@@ -154,13 +151,14 @@ class directive(object):
         return wrapped
 
 
-@directive(dicts='versions')
+@directive('versions')
 def version(pkg, ver, checksum=None, **kwargs):
     """Adds a version and metadata describing how to fetch it.
        Metadata is just stored as a dict in the package's versions
        dictionary.  Package must turn it into a valid fetch strategy
        later.
     """
+    # TODO: checksum vs md5 distinction is confusing -- fix this.
     # special case checksum for backward compatibility
     if checksum:
         kwargs['md5'] = checksum
@@ -169,18 +167,29 @@ def version(pkg, ver, checksum=None, **kwargs):
     pkg.versions[Version(ver)] = kwargs
 
 
-@directive(dicts='dependencies')
-def depends_on(pkg, *specs):
-    """Adds a dependencies local variable in the locals of
-       the calling class, based on args. """
-    for string in specs:
-        for spec in spack.spec.parse(string):
-            if pkg.name == spec.name:
-                raise CircularReferenceError('depends_on', pkg.name)
-            pkg.dependencies[spec.name] = spec
+def _depends_on(pkg, spec, when=None):
+    if when is None:
+        when = pkg.name
+    when_spec = parse_anonymous_spec(when, pkg.name)
+
+    dep_spec = Spec(spec)
+    if pkg.name == dep_spec.name:
+        raise CircularReferenceError('depends_on', pkg.name)
 
+    conditions = pkg.dependencies.setdefault(dep_spec.name, {})
+    if when_spec in conditions:
+        conditions[when_spec].constrain(dep_spec, deps=False)
+    else:
+        conditions[when_spec] = dep_spec
 
-@directive(dicts=('extendees', 'dependencies'))
+
+@directive('dependencies')
+def depends_on(pkg, spec, when=None):
+    """Creates a dict of deps with specs defining when they apply."""
+    _depends_on(pkg, spec, when=when)
+
+
+@directive(('extendees', 'dependencies'))
 def extends(pkg, spec, **kwargs):
     """Same as depends_on, but dependency is symlinked into parent prefix.
 
@@ -198,14 +207,12 @@ def extends(pkg, spec, **kwargs):
     if pkg.extendees:
         raise DirectiveError("Packages can extend at most one other package.")
 
-    spec = Spec(spec)
-    if pkg.name == spec.name:
-        raise CircularReferenceError('extends', pkg.name)
-    pkg.dependencies[spec.name] = spec
-    pkg.extendees[spec.name] = (spec, kwargs)
+    when = kwargs.pop('when', pkg.name)
+    _depends_on(pkg, spec, when=when)
+    pkg.extendees[spec] = (Spec(spec), kwargs)
 
 
-@directive(dicts='provided')
+@directive('provided')
 def provides(pkg, *specs, **kwargs):
     """Allows packages to provide a virtual dependency.  If a package provides
        'mpi', other packages can declare that they depend on "mpi", and spack
@@ -221,17 +228,17 @@ def provides(pkg, *specs, **kwargs):
             pkg.provided[provided_spec] = provider_spec
 
 
-@directive(dicts='patches')
-def patch(pkg, url_or_filename, **kwargs):
+@directive('patches')
+def patch(pkg, url_or_filename, level=1, when=None):
     """Packages can declare patches to apply to source.  You can
        optionally provide a when spec to indicate that a particular
        patch should only be applied when the package's spec meets
        certain conditions (e.g. a particular version).
     """
-    level = kwargs.get('level', 1)
-    when  = kwargs.get('when', pkg.name)
-
+    if when is None:
+        when = pkg.name
     when_spec = parse_anonymous_spec(when, pkg.name)
+
     if when_spec not in pkg.patches:
         pkg.patches[when_spec] = [Patch(pkg.name, url_or_filename, level)]
     else:
@@ -240,13 +247,13 @@ def patch(pkg, url_or_filename, **kwargs):
         pkg.patches[when_spec].append(Patch(pkg.name, url_or_filename, level))
 
 
-@directive(dicts='variants')
-def variant(pkg, name, **kwargs):
+@directive('variants')
+def variant(pkg, name, default=False, description=""):
     """Define a variant for the package. Packager can specify a default
     value (on or off) as well as a text description."""
 
-    default     = bool(kwargs.get('default', False))
-    description = str(kwargs.get('description', "")).strip()
+    default     = bool(default)
+    description = str(description).strip()
 
     if not re.match(spack.spec.identifier_re, name):
         raise DirectiveError("Invalid variant name in %s: '%s'" % (pkg.name, name))
diff --git a/lib/spack/spack/package.py b/lib/spack/spack/package.py
index ea3b46088a..452544be49 100644
--- a/lib/spack/spack/package.py
+++ b/lib/spack/spack/package.py
@@ -50,7 +50,6 @@ from llnl.util.filesystem import *
 from llnl.util.lang import *
 
 import spack
-import spack.spec
 import spack.error
 import spack.compilers
 import spack.mirror
@@ -540,41 +539,6 @@ class Package(object):
                 yield pkg
 
 
-    def validate_dependencies(self):
-        """Ensure that this package and its dependencies all have consistent
-           constraints on them.
-
-           NOTE that this will NOT find sanity problems through a virtual
-           dependency.  Virtual deps complicate the problem because we
-           don't know in advance which ones conflict with others in the
-           dependency DAG. If there's more than one virtual dependency,
-           it's a full-on SAT problem, so hold off on this for now.
-           The vdeps are actually skipped in preorder_traversal, so see
-           that for details.
-
-           TODO: investigate validating virtual dependencies.
-        """
-        # This algorithm just attempts to merge all the constraints on the same
-        # package together, loses information about the source of the conflict.
-        # What we'd really like to know is exactly which two constraints
-        # conflict, but that algorithm is more expensive, so we'll do it
-        # the simple, less informative way for now.
-        merged = spack.spec.DependencyMap()
-
-        try:
-            for pkg in self.preorder_traversal():
-                for name, spec in pkg.dependencies.iteritems():
-                    if name not in merged:
-                        merged[name] = spec.copy()
-                    else:
-                        merged[name].constrain(spec)
-
-        except spack.spec.UnsatisfiableSpecError, e:
-            raise InvalidPackageDependencyError(
-                "Package %s has inconsistent dependency constraints: %s"
-                % (self.name, e.message))
-
-
     def provides(self, vpkg_name):
         """True if this package provides a virtual package with the specified name."""
         return vpkg_name in self.provided
@@ -1198,13 +1162,6 @@ class PackageError(spack.error.SpackError):
         super(PackageError, self).__init__(message, long_msg)
 
 
-class InvalidPackageDependencyError(PackageError):
-    """Raised when package specification is inconsistent with requirements of
-       its dependencies."""
-    def __init__(self, message):
-        super(InvalidPackageDependencyError, self).__init__(message)
-
-
 class PackageVersionError(PackageError):
     """Raised when a version URL cannot automatically be determined."""
     def __init__(self, version):
diff --git a/lib/spack/spack/spec.py b/lib/spack/spack/spec.py
index f2625ae596..69b0a70445 100644
--- a/lib/spack/spack/spec.py
+++ b/lib/spack/spack/spec.py
@@ -222,20 +222,24 @@ class CompilerSpec(object):
         return CompilerSpec(compiler_spec_like)
 
 
-    def satisfies(self, other):
+    def satisfies(self, other, strict=False):
         other = self._autospec(other)
         return (self.name == other.name and
-                self.versions.satisfies(other.versions))
+                self.versions.satisfies(other.versions, strict=strict))
 
 
     def constrain(self, other):
+        """Intersect self's versions with other.
+
+        Return whether the CompilerSpec changed.
+        """
         other = self._autospec(other)
 
         # ensure that other will actually constrain this spec.
         if not other.satisfies(self):
             raise UnsatisfiableCompilerSpecError(other, self)
 
-        self.versions.intersect(other.versions)
+        return self.versions.intersect(other.versions)
 
 
     @property
@@ -316,8 +320,8 @@ class VariantMap(HashableMap):
         self.spec = spec
 
 
-    def satisfies(self, other):
-        if self.spec._concrete:
+    def satisfies(self, other, strict=False):
+        if strict or self.spec._concrete:
             return all(k in self and self[k].enabled == other[k].enabled
                        for k in other)
         else:
@@ -326,17 +330,25 @@ class VariantMap(HashableMap):
 
 
     def constrain(self, other):
+        """Add all variants in other that aren't in self to self.
+
+        Raises an error if any common variants don't match.
+        Return whether the spec changed.
+        """
         if other.spec._concrete:
             for k in self:
                 if k not in other:
                     raise UnsatisfiableVariantSpecError(self[k], '<absent>')
 
+        changed = False
         for k in other:
             if k in self:
                 if self[k].enabled != other[k].enabled:
                     raise UnsatisfiableVariantSpecError(self[k], other[k])
             else:
                 self[k] = other[k].copy()
+                changed =True
+        return changed
 
     @property
     def concrete(self):
@@ -867,6 +879,59 @@ class Spec(object):
             self._add_dependency(dep)
 
 
+    def _evaluate_dependency_conditions(self, name):
+        """Evaluate all the conditions on a dependency with this name.
+
+        If the package depends on <name> in this configuration, return
+        the dependency.  If no conditions are True (and we don't
+        depend on it), return None.
+        """
+        pkg = spack.db.get(self.name)
+        conditions = pkg.dependencies[name]
+
+        # evaluate when specs to figure out constraints on the dependency.
+        dep = None
+        for when_spec, dep_spec in conditions.items():
+            sat = self.satisfies(when_spec, strict=True)
+#                print self, "satisfies", when_spec, ":", sat
+            if sat:
+                if dep is None:
+                    dep = Spec(name)
+                try:
+                    dep.constrain(dep_spec)
+                except UnsatisfiableSpecError, e:
+                    e.message = ("Conflicting conditional dependencies on package "
+                                 "%s for spec %s" % (self.name, self))
+                    raise e
+        return dep
+
+
+    def _find_provider(self, vdep, provider_index):
+        """Find provider for a virtual spec in the provider index.
+        Raise an exception if there is a conflicting virtual
+        dependency already in this spec.
+        """
+        assert(vdep.virtual)
+        providers = provider_index.providers_for(vdep)
+
+        # If there is a provider for the vpkg, then use that instead of
+        # the virtual package.
+        if providers:
+            # Can't have multiple providers for the same thing in one spec.
+            if len(providers) > 1:
+                raise MultipleProviderError(vdep, providers)
+            return providers[0]
+        else:
+            # The user might have required something insufficient for
+            # pkg_dep -- so we'll get a conflict.  e.g., user asked for
+            # mpi@:1.1 but some package required mpi@2.1:.
+            required = provider_index.providers_for(vdep.name)
+            if len(required) > 1:
+                raise MultipleProviderError(vdep, required)
+            elif required:
+                raise UnsatisfiableProviderSpecError(required[0], vdep)
+
+
     def _normalize_helper(self, visited, spec_deps, provider_index):
         """Recursive helper function for _normalize."""
         if self.name in visited:
@@ -881,34 +946,22 @@ class Spec(object):
         # Combine constraints from package dependencies with
         # constraints on the spec's dependencies.
         pkg = spack.db.get(self.name)
-        for name, pkg_dep in self.package.dependencies.items():
+        for name in pkg.dependencies:
+            # If pkg_dep is None, no conditions matched and we don't depend on this.
+            pkg_dep = self._evaluate_dependency_conditions(name)
+            if not pkg_dep:
+                continue
+
             # If it's a virtual dependency, try to find a provider
             if pkg_dep.virtual:
-                providers = provider_index.providers_for(pkg_dep)
-
-                # If there is a provider for the vpkg, then use that instead of
-                # the virtual package.
-                if providers:
-                    # Can't have multiple providers for the same thing in one spec.
-                    if len(providers) > 1:
-                        raise MultipleProviderError(pkg_dep, providers)
-
-                    pkg_dep = providers[0]
-                    name    = pkg_dep.name
-
-                else:
-                    # The user might have required something insufficient for
-                    # pkg_dep -- so we'll get a conflict.  e.g., user asked for
-                    # mpi@:1.1 but some package required mpi@2.1:.
-                    required = provider_index.providers_for(name)
-                    if len(required) > 1:
-                        raise MultipleProviderError(pkg_dep, required)
-                    elif required:
-                        raise UnsatisfiableProviderSpecError(
-                            required[0], pkg_dep)
+                visited.add(pkg_dep.name)
+                provider = self._find_provider(pkg_dep, provider_index)
+                if provider:
+                    pkg_dep = provider
+                    name = provider.name
             else:
-                # if it's a real dependency, check whether it provides something
-                # already required in the spec.
+                # if it's a real dependency, check whether it provides
+                # something already required in the spec.
                 index = ProviderIndex([pkg_dep], restrict=True)
                 for vspec in (v for v in spec_deps.values() if v.virtual):
                     if index.providers_for(vspec):
@@ -966,19 +1019,14 @@ class Spec(object):
         # Ensure first that all packages & compilers in the DAG exist.
         self.validate_names()
 
-        # Ensure that the package & dep descriptions are consistent & sane
-        if not self.virtual:
-            self.package.validate_dependencies()
-
         # Get all the dependencies into one DependencyMap
         spec_deps = self.flat_dependencies(copy=False)
 
-        # Figure out which of the user-provided deps provide virtual deps.
-        # Remove virtual deps that are already provided by something in the spec
-        spec_packages = [d.package for d in spec_deps.values() if not d.virtual]
-
+        # Initialize index of virtual dependency providers
         index = ProviderIndex(spec_deps.values(), restrict=True)
 
+        # traverse the package DAG and fill out dependencies according
+        # to package files & their 'when' specs
         visited = set()
         self._normalize_helper(visited, spec_deps, index)
 
@@ -986,12 +1034,6 @@ class Spec(object):
         # actually deps of this package.  Raise an error.
         extra = set(spec_deps.keys()).difference(visited)
 
-        # Also subtract out all the packags that provide a needed vpkg
-        vdeps = [v for v in self.package.virtual_dependencies()]
-
-        vpkg_providers = index.providers_for(*vdeps)
-        extra.difference_update(p.name for p in vpkg_providers)
-
         # Anything left over is not a valid part of the spec.
         if extra:
             raise InvalidDependencyException(
@@ -1030,6 +1072,10 @@ class Spec(object):
 
 
     def constrain(self, other, **kwargs):
+        """Merge the constraints of other with self.
+
+        Returns True if the spec changed as a result, False if not.
+        """
         other = self._autospec(other)
         constrain_deps = kwargs.get('deps', True)
 
@@ -1055,18 +1101,22 @@ class Spec(object):
         elif self.compiler is None:
             self.compiler = other.compiler
 
-        self.versions.intersect(other.versions)
-        self.variants.constrain(other.variants)
+        changed = False
+        changed |= self.versions.intersect(other.versions)
+        changed |= self.variants.constrain(other.variants)
+        changed |= bool(self.architecture)
         self.architecture = self.architecture or other.architecture
 
         if constrain_deps:
-            self._constrain_dependencies(other)
+            changed |= self._constrain_dependencies(other)
+
+        return changed
 
 
     def _constrain_dependencies(self, other):
         """Apply constraints of other spec's dependencies to this spec."""
         if not self.dependencies or not other.dependencies:
-            return
+            return False
 
         # TODO: might want more detail than this, e.g. specific deps
         # in violation. if this becomes a priority get rid of this
@@ -1075,12 +1125,17 @@ class Spec(object):
             raise UnsatisfiableDependencySpecError(other, self)
 
         # Handle common first-order constraints directly
+        changed = False
         for name in self.common_dependencies(other):
-            self[name].constrain(other[name], deps=False)
+            changed |= 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())
+            changed = True
+
+        return changed
 
 
     def common_dependencies(self, other):
@@ -1114,46 +1169,72 @@ class Spec(object):
             return parse_anonymous_spec(spec_like, self.name)
 
 
-    def satisfies(self, other, **kwargs):
+    def satisfies(self, other, deps=True, strict=False):
+        """Determine if this spec satisfies all constraints of another.
+
+        There are two senses for satisfies:
+
+          * `loose` (default): the absence of a constraint in self
+            implies that it *could* be satisfied by other, so we only
+            check that there are no conflicts with other for
+            constraints that this spec actually has.
+
+          * `strict`: strict means that we *must* meet all the
+            constraints specified on other.
+        """
         other = self._autospec(other)
-        satisfy_deps = kwargs.get('deps', True)
 
         # First thing we care about is whether the name matches
         if self.name != other.name:
             return False
 
-        # All these attrs have satisfies criteria of their own,
-        # but can be None to indicate no constraints.
-        for s, o in ((self.versions, other.versions),
-                     (self.compiler, other.compiler)):
-            if s and o and not s.satisfies(o):
+        if self.versions and other.versions:
+            if not self.versions.satisfies(other.versions, strict=strict):
                 return False
+        elif strict and (self.versions or other.versions):
+            return False
 
-        if not self.variants.satisfies(other.variants):
+        # None indicates no constraints when not strict.
+        if self.compiler and other.compiler:
+            if not self.compiler.satisfies(other.compiler, strict=strict):
+                return False
+        elif strict and (other.compiler and not self.compiler):
+            return False
+
+        if not self.variants.satisfies(other.variants, strict=strict):
             return False
 
         # Architecture satisfaction is currently just string equality.
-        # Can be None for unconstrained, though.
-        if (self.architecture and other.architecture and
-            self.architecture != other.architecture):
+        # If not strict, None means unconstrained.
+        if self.architecture and other.architecture:
+            if self.architecture != other.architecture:
+                return False
+        elif strict and (other.architecture and not self.architecture):
             return False
 
         # If we need to descend into dependencies, do it, otherwise we're done.
-        if satisfy_deps:
-            return self.satisfies_dependencies(other)
+        if deps:
+            return self.satisfies_dependencies(other, strict=strict)
         else:
             return True
 
 
-    def satisfies_dependencies(self, other):
+    def satisfies_dependencies(self, other, strict=False):
         """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:
+        if strict:
+            if other.dependencies and not self.dependencies:
+                return False
+
+            if not all(dep in self.dependencies for dep in other.dependencies):
+                return False
+
+        elif not self.dependencies or not other.dependencies:
+            # if either spec doesn't restrict dependencies then both are compatible.
             return True
 
         # Handle first-order constraints directly
         for name in self.common_dependencies(other):
-            if not self[name].satisfies(other[name]):
+            if not self[name].satisfies(other[name], deps=False):
                 return False
 
         # For virtual dependencies, we need to dig a little deeper.
@@ -1255,7 +1336,7 @@ class Spec(object):
         """
         spec = self._autospec(spec)
         for s in self.traverse():
-            if s.satisfies(spec):
+            if s.satisfies(spec, strict=True):
                 return True
         return False
 
@@ -1411,7 +1492,8 @@ class Spec(object):
 
             elif compiler:
                 if c == '@':
-                    if self.compiler and self.compiler.versions:
+                    if (self.compiler and self.compiler.versions and
+                        self.compiler.versions != _any_version):
                         write(c + str(self.compiler.versions), '%')
                 elif c == '$':
                     escape = True
diff --git a/lib/spack/spack/test/__init__.py b/lib/spack/spack/test/__init__.py
index 77c8bd3191..7ff512c370 100644
--- a/lib/spack/spack/test/__init__.py
+++ b/lib/spack/spack/test/__init__.py
@@ -53,7 +53,8 @@ test_names = ['versions',
               'url_extrapolate',
               'cc',
               'link_tree',
-              'spec_yaml']
+              'spec_yaml',
+              'optional_deps']
 
 
 def list_tests():
diff --git a/lib/spack/spack/test/mock_packages_test.py b/lib/spack/spack/test/mock_packages_test.py
index e948376039..09fb9ebe30 100644
--- a/lib/spack/spack/test/mock_packages_test.py
+++ b/lib/spack/spack/test/mock_packages_test.py
@@ -35,7 +35,7 @@ def set_pkg_dep(pkg, spec):
        Use this to mock up constraints.
     """
     spec = Spec(spec)
-    spack.db.get(pkg).dependencies[spec.name] = spec
+    spack.db.get(pkg).dependencies[spec.name] = { Spec(pkg) : spec }
 
 
 class MockPackagesTest(unittest.TestCase):
diff --git a/lib/spack/spack/test/optional_deps.py b/lib/spack/spack/test/optional_deps.py
new file mode 100644
index 0000000000..4d8f86a33e
--- /dev/null
+++ b/lib/spack/spack/test/optional_deps.py
@@ -0,0 +1,86 @@
+##############################################################################
+# Copyright (c) 2013-2015, Lawrence Livermore National Security, LLC.
+# Produced at the Lawrence Livermore National Laboratory.
+#
+# This file is part of Spack.
+# Written by Todd Gamblin, tgamblin@llnl.gov, All rights reserved.
+# LLNL-CODE-647188
+#
+# For details, see https://scalability-llnl.github.io/spack
+# Please also see the LICENSE file for our notice and the LGPL.
+#
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License (as published by
+# the Free Software Foundation) version 2.1 dated February 1999.
+#
+# This program is distributed in the hope that it will be useful, but
+# WITHOUT ANY WARRANTY; without even the IMPLIED WARRANTY OF
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the terms and
+# conditions of the GNU General Public License for more details.
+#
+# You should have received a copy of the GNU Lesser General Public License
+# along with this program; if not, write to the Free Software Foundation,
+# Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+##############################################################################
+import unittest
+
+import spack
+from spack.spec import Spec, CompilerSpec
+from spack.test.mock_packages_test import *
+
+class ConcretizeTest(MockPackagesTest):
+
+    def check_normalize(self, spec_string, expected):
+        spec = Spec(spec_string)
+        spec.normalize()
+        self.assertEqual(spec, expected)
+        self.assertTrue(spec.eq_dag(expected))
+
+
+    def test_normalize_simple_conditionals(self):
+        self.check_normalize('optional-dep-test', Spec('optional-dep-test'))
+        self.check_normalize('optional-dep-test~a', Spec('optional-dep-test~a'))
+
+        self.check_normalize('optional-dep-test+a',
+                             Spec('optional-dep-test+a', Spec('a')))
+
+        self.check_normalize('optional-dep-test@1.1',
+                             Spec('optional-dep-test@1.1', Spec('b')))
+
+        self.check_normalize('optional-dep-test%intel',
+                             Spec('optional-dep-test%intel', Spec('c')))
+
+        self.check_normalize('optional-dep-test%intel@64.1',
+                             Spec('optional-dep-test%intel@64.1', Spec('c'), Spec('d')))
+
+        self.check_normalize('optional-dep-test%intel@64.1.2',
+                             Spec('optional-dep-test%intel@64.1.2', Spec('c'), Spec('d')))
+
+        self.check_normalize('optional-dep-test%clang@35',
+                             Spec('optional-dep-test%clang@35', Spec('e')))
+
+
+    def test_multiple_conditionals(self):
+        self.check_normalize('optional-dep-test+a@1.1',
+                             Spec('optional-dep-test+a@1.1', Spec('a'), Spec('b')))
+
+        self.check_normalize('optional-dep-test+a%intel',
+                             Spec('optional-dep-test+a%intel', Spec('a'), Spec('c')))
+
+        self.check_normalize('optional-dep-test@1.1%intel',
+                             Spec('optional-dep-test@1.1%intel', Spec('b'), Spec('c')))
+
+        self.check_normalize('optional-dep-test@1.1%intel@64.1.2+a',
+                             Spec('optional-dep-test@1.1%intel@64.1.2+a',
+                                  Spec('b'), Spec('a'), Spec('c'), Spec('d')))
+
+        self.check_normalize('optional-dep-test@1.1%clang@36.5+a',
+                             Spec('optional-dep-test@1.1%clang@36.5+a',
+                                  Spec('b'), Spec('a'), Spec('e')))
+
+
+    def test_chained_mpi(self):
+        self.check_normalize('optional-dep-test-2+mpi',
+                             Spec('optional-dep-test-2+mpi',
+                                  Spec('optional-dep-test+mpi',
+                                       Spec('mpi'))))
diff --git a/lib/spack/spack/test/spec_dag.py b/lib/spack/spack/test/spec_dag.py
index ecbc46981c..549f829d3e 100644
--- a/lib/spack/spack/test/spec_dag.py
+++ b/lib/spack/spack/test/spec_dag.py
@@ -44,8 +44,11 @@ class SpecDagTest(MockPackagesTest):
         set_pkg_dep('callpath', 'mpich@2.0')
 
         spec = Spec('mpileaks ^mpich ^callpath ^dyninst ^libelf ^libdwarf')
-        self.assertRaises(spack.package.InvalidPackageDependencyError,
-                          spec.package.validate_dependencies)
+
+        # TODO: try to do something to showt that the issue was with
+        # TODO: the user's input or with package inconsistencies.
+        self.assertRaises(spack.spec.UnsatisfiableVersionSpecError,
+                          spec.normalize)
 
 
     def test_preorder_node_traversal(self):
@@ -140,11 +143,6 @@ class SpecDagTest(MockPackagesTest):
 
     def test_conflicting_spec_constraints(self):
         mpileaks = Spec('mpileaks ^mpich ^callpath ^dyninst ^libelf ^libdwarf')
-        try:
-            mpileaks.package.validate_dependencies()
-        except spack.package.InvalidPackageDependencyError, e:
-            self.fail("validate_dependencies raised an exception: %s"
-                      % e.message)
 
         # Normalize then add conflicting constraints to the DAG (this is an
         # extremely unlikely scenario, but we test for it anyway)
diff --git a/lib/spack/spack/version.py b/lib/spack/spack/version.py
index 61b1e328ce..35db05e018 100644
--- a/lib/spack/spack/version.py
+++ b/lib/spack/spack/version.py
@@ -93,12 +93,12 @@ def coerce_versions(a, b):
 def coerced(method):
     """Decorator that ensures that argument types of a method are coerced."""
     @wraps(method)
-    def coercing_method(a, b):
+    def coercing_method(a, b, *args, **kwargs):
         if type(a) == type(b) or a is None or b is None:
-            return method(a, b)
+            return method(a, b, *args, **kwargs)
         else:
             ca, cb = coerce_versions(a, b)
-            return getattr(ca, method.__name__)(cb)
+            return getattr(ca, method.__name__)(cb, *args, **kwargs)
     return coercing_method
 
 
@@ -607,15 +607,22 @@ class VersionList(object):
 
 
     @coerced
-    def satisfies(self, other):
-        """A VersionList satisfies another if some version in the list would
-           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.
+    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]):
@@ -652,9 +659,14 @@ class VersionList(object):
 
     @coerced
     def intersect(self, other):
+        """Intersect this spec's list with other.
+
+        Return True if the spec changed as a result; False otherwise
+        """
         isection = self.intersection(other)
+        changed = (isection.versions != self.versions)
         self.versions = isection.versions
-
+        return changed
 
     @coerced
     def __contains__(self, other):
diff --git a/var/spack/mock_packages/a/package.py b/var/spack/mock_packages/a/package.py
new file mode 100644
index 0000000000..fa63c08df0
--- /dev/null
+++ b/var/spack/mock_packages/a/package.py
@@ -0,0 +1,12 @@
+from spack import *
+
+class A(Package):
+    """Simple package with no dependencies"""
+
+    homepage = "http://www.example.com"
+    url      = "http://www.example.com/a-1.0.tar.gz"
+
+    version('1.0', '0123456789abcdef0123456789abcdef')
+
+    def install(self, spec, prefix):
+        pass
diff --git a/var/spack/mock_packages/b/package.py b/var/spack/mock_packages/b/package.py
new file mode 100644
index 0000000000..cb88aa2157
--- /dev/null
+++ b/var/spack/mock_packages/b/package.py
@@ -0,0 +1,12 @@
+from spack import *
+
+class B(Package):
+    """Simple package with no dependencies"""
+
+    homepage = "http://www.example.com"
+    url      = "http://www.example.com/b-1.0.tar.gz"
+
+    version('1.0', '0123456789abcdef0123456789abcdef')
+
+    def install(self, spec, prefix):
+        pass
diff --git a/var/spack/mock_packages/c/package.py b/var/spack/mock_packages/c/package.py
new file mode 100644
index 0000000000..f51b913fa9
--- /dev/null
+++ b/var/spack/mock_packages/c/package.py
@@ -0,0 +1,12 @@
+from spack import *
+
+class C(Package):
+    """Simple package with no dependencies"""
+
+    homepage = "http://www.example.com"
+    url      = "http://www.example.com/c-1.0.tar.gz"
+
+    version('1.0', '0123456789abcdef0123456789abcdef')
+
+    def install(self, spec, prefix):
+        pass
diff --git a/var/spack/mock_packages/e/package.py b/var/spack/mock_packages/e/package.py
new file mode 100644
index 0000000000..76c6b64c7f
--- /dev/null
+++ b/var/spack/mock_packages/e/package.py
@@ -0,0 +1,12 @@
+from spack import *
+
+class E(Package):
+    """Simple package with no dependencies"""
+
+    homepage = "http://www.example.com"
+    url      = "http://www.example.com/e-1.0.tar.gz"
+
+    version('1.0', '0123456789abcdef0123456789abcdef')
+
+    def install(self, spec, prefix):
+        pass
diff --git a/var/spack/mock_packages/optional-dep-test-2/package.py b/var/spack/mock_packages/optional-dep-test-2/package.py
new file mode 100644
index 0000000000..ef0587588e
--- /dev/null
+++ b/var/spack/mock_packages/optional-dep-test-2/package.py
@@ -0,0 +1,18 @@
+from spack import *
+
+class OptionalDepTest2(Package):
+    """Depends on the optional-dep-test package"""
+
+    homepage = "http://www.example.com"
+    url      = "http://www.example.com/optional-dep-test-2-1.0.tar.gz"
+
+    version('1.0', '0123456789abcdef0123456789abcdef')
+
+    variant('odt', default=False)
+    variant('mpi', default=False)
+
+    depends_on('optional-dep-test', when='+odt')
+    depends_on('optional-dep-test+mpi', when='+mpi')
+
+    def install(self, spec, prefix):
+        pass
diff --git a/var/spack/mock_packages/optional-dep-test/package.py b/var/spack/mock_packages/optional-dep-test/package.py
new file mode 100644
index 0000000000..bb57576ca9
--- /dev/null
+++ b/var/spack/mock_packages/optional-dep-test/package.py
@@ -0,0 +1,29 @@
+from spack import *
+
+class OptionalDepTest(Package):
+    """Description"""
+
+    homepage = "http://www.example.com"
+    url      = "http://www.example.com/optional_dep_test-1.0.tar.gz"
+
+    version('1.0', '0123456789abcdef0123456789abcdef')
+    version('1.1', '0123456789abcdef0123456789abcdef')
+
+    variant('a',   default=False)
+    variant('f',   default=False)
+    variant('mpi', default=False)
+
+    depends_on('a', when='+a')
+    depends_on('b', when='@1.1')
+    depends_on('c', when='%intel')
+    depends_on('d', when='%intel@64.1')
+    depends_on('e', when='%clang@34:40')
+
+    depends_on('f', when='+f')
+    depends_on('g', when='^f')
+    depends_on('mpi', when='^g')
+
+    depends_on('mpi', when='+mpi')
+
+    def install(self, spec, prefix):
+        pass