Refactor Package dependency metadata

- Previously, dependencies and dependency_types were stored as separate
  dicts on Package.
  - This means a package can only depend on another in one specific way,
    which is usually but not always true.
  - Prior code unioned dependency types statically across dependencies on
    the same package.

- New code stores dependency relationships as their own object, with a
  spec constraint and a set of dependency types per relationship.
  - Dependency types are now more precise
  - There is now room to add more information to dependency relationships.

- New Dependency class lives in dependency.py, along with deptype
  definitions that used to live in spack.spec.

Move deptype definitions to spack.dependency

14 files changed, 217 insertions, 123 deletions

diff --git a/lib/spack/spack/__init__.py b/lib/spack/spack/__init__.py
index 3a613e1fd0..3b614b0482 100644
--- a/lib/spack/spack/__init__.py
+++ b/lib/spack/spack/__init__.py
@@ -207,8 +207,11 @@ __all__ += [
 from spack.version import Version, ver
 __all__ += ['Version', 'ver']
 
-from spack.spec import Spec, alldeps
-__all__ += ['Spec', 'alldeps']
+from spack.spec import Spec
+__all__ += ['Spec']
+
+from spack.dependency import all_deptypes
+__all__ += ['all_deptypes']
 
 from spack.multimethod import when
 __all__ += ['when']
diff --git a/lib/spack/spack/cmd/fetch.py b/lib/spack/spack/cmd/fetch.py
index 971cd00af5..52caf7e80d 100644
--- a/lib/spack/spack/cmd/fetch.py
+++ b/lib/spack/spack/cmd/fetch.py
@@ -57,7 +57,7 @@ def fetch(parser, args):
     specs = spack.cmd.parse_specs(args.packages, concretize=True)
     for spec in specs:
         if args.missing or args.dependencies:
-            for s in spec.traverse(deptype_query=spack.alldeps):
+            for s in spec.traverse(deptype_query=all):
                 package = spack.repo.get(s)
                 if args.missing and package.installed:
                     continue
diff --git a/lib/spack/spack/cmd/graph.py b/lib/spack/spack/cmd/graph.py
index a258d5faac..e17d33f8b4 100644
--- a/lib/spack/spack/cmd/graph.py
+++ b/lib/spack/spack/cmd/graph.py
@@ -31,6 +31,7 @@ import spack
 import spack.cmd
 import spack.store
 from spack.spec import *
+from spack.dependency import *
 from spack.graph import *
 
 description = "generate graphs of package dependency relationships"
@@ -64,7 +65,7 @@ def setup_parser(subparser):
     subparser.add_argument(
         '-t', '--deptype', action='store',
         help="comma-separated list of deptypes to traverse. default=%s"
-        % ','.join(alldeps))
+        % ','.join(all_deptypes))
 
     subparser.add_argument(
         'specs', nargs=argparse.REMAINDER,
@@ -87,7 +88,7 @@ def graph(parser, args):
         setup_parser.parser.print_help()
         return 1
 
-    deptype = alldeps
+    deptype = all_deptypes
     if args.deptype:
         deptype = tuple(args.deptype.split(','))
         if deptype == ('all',):
diff --git a/lib/spack/spack/cmd/list.py b/lib/spack/spack/cmd/list.py
index 2550a6d052..6720ca3493 100644
--- a/lib/spack/spack/cmd/list.py
+++ b/lib/spack/spack/cmd/list.py
@@ -170,7 +170,7 @@ def rst(pkgs):
                                    reversed(sorted(pkg.versions))))
             print()
 
-        for deptype in spack.alldeps:
+        for deptype in spack.all_deptypes:
             deps = pkg.dependencies_of_type(deptype)
             if deps:
                 print('%s Dependencies' % deptype.capitalize())
diff --git a/lib/spack/spack/cmd/mirror.py b/lib/spack/spack/cmd/mirror.py
index 08b6603da4..a24cf6b25d 100644
--- a/lib/spack/spack/cmd/mirror.py
+++ b/lib/spack/spack/cmd/mirror.py
@@ -182,7 +182,7 @@ def mirror_create(args):
         new_specs = set()
         for spec in specs:
             spec.concretize()
-            for s in spec.traverse(deptype_query=spack.alldeps):
+            for s in spec.traverse(deptype_query=all):
                 new_specs.add(s)
         specs = list(new_specs)
 
diff --git a/lib/spack/spack/concretize.py b/lib/spack/spack/concretize.py
index 39566ab061..1aed7d8eb1 100644
--- a/lib/spack/spack/concretize.py
+++ b/lib/spack/spack/concretize.py
@@ -401,7 +401,7 @@ def find_spec(spec, condition, default=None):
         visited.add(id(relative))
 
     # Then search all other relatives in the DAG *except* spec
-    for relative in spec.root.traverse(deptypes=spack.alldeps):
+    for relative in spec.root.traverse(deptypes=all):
         if relative is spec:
             continue
         if id(relative) in visited:
diff --git a/lib/spack/spack/dependency.py b/lib/spack/spack/dependency.py
new file mode 100644
index 0000000000..996dfa20c4
--- /dev/null
+++ b/lib/spack/spack/dependency.py
@@ -0,0 +1,90 @@
+##############################################################################
+# Copyright (c) 2013-2017, Lawrence Livermore National Security, LLC.
+# Produced at the Lawrence Livermore National Laboratory.
+#
+# This file is part of Spack.
+# Created by Todd Gamblin, tgamblin@llnl.gov, All rights reserved.
+# LLNL-CODE-647188
+#
+# For details, see https://github.com/llnl/spack
+# Please also see the NOTICE and LICENSE files 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 Lesser General Public License (as
+# published by the Free Software Foundation) version 2.1, 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 Lesser 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
+##############################################################################
+"""Data structures that represent Spack's dependency relationships.
+"""
+from six import string_types
+
+#: The types of dependency relationships that Spack understands.
+all_deptypes = ('build', 'link', 'run', 'test')
+
+#: Default dependency type if none is specified
+default_deptype = ('build', 'link')
+
+
+def canonical_deptype(deptype):
+    """Convert deptype to a canonical sorted tuple, or raise ValueError.
+
+    Args:
+        deptype (str or list or tuple): string representing dependency
+            type, or a list/tuple of such strings.  Can also be the
+            builtin function ``all`` or the string 'all', which result in
+            a tuple of all dependency types known to Spack.
+    """
+    if deptype in ('all', all):
+        return all_deptypes
+
+    elif isinstance(deptype, string_types):
+        if deptype not in all_deptypes:
+            raise ValueError('Invalid dependency type: %s' % deptype)
+        return (deptype,)
+
+    elif isinstance(deptype, (tuple, list)):
+        bad = [d for d in deptype if d not in all_deptypes]
+        if bad:
+            raise ValueError(
+                'Invalid dependency types: %s' % ','.join(str(t) for t in bad))
+        return tuple(sorted(deptype))
+
+    elif deptype is None:
+        raise ValueError('Invalid dependency type: None')
+
+    return deptype
+
+
+class Dependency(object):
+    """Class representing metadata for a dependency on a package.
+
+    This class differs from ``spack.spec.DependencySpec`` because it
+    represents metadata at the ``Package`` level.
+    ``spack.spec.DependencySpec`` is a descriptor for an actual package
+    confiuguration, while ``Dependency`` is a descriptor for a package's
+    dependency *requirements*.
+
+    A dependency is a requirement for a configuration of another package
+    that satisfies a particular spec.  The dependency can have *types*,
+    which determine *how* that package configuration is required,
+    e.g. whether it is required for building the package, whether it
+    needs to be linked to, or whether it is needed at runtime so that
+    Spack can call commands from it.
+    """
+    def __init__(self, spec, type=default_deptype):
+        """Create a new Dependency.
+
+        Args:
+            spec (Spec): Spec indicating dependency requirements
+            type (sequence): strings describing dependency relationship
+        """
+        self.spec = spec
+        self.type = set(type)
diff --git a/lib/spack/spack/directives.py b/lib/spack/spack/directives.py
index 05014fb31f..db07d2b4c1 100644
--- a/lib/spack/spack/directives.py
+++ b/lib/spack/spack/directives.py
@@ -54,11 +54,13 @@ import re
 from six import string_types
 
 import llnl.util.lang
+from llnl.util.filesystem import join_path
+
 import spack
 import spack.error
 import spack.spec
 import spack.url
-from llnl.util.filesystem import join_path
+from spack.dependency import *
 from spack.fetch_strategy import from_kwargs
 from spack.patch import Patch
 from spack.resource import Resource
@@ -68,6 +70,9 @@ from spack.version import Version
 
 __all__ = []
 
+#: These are variant names used by Spack internally; packages can't use them
+reserved_names = ['patches']
+
 
 class DirectiveMetaMixin(type):
     """Flushes the directives that were temporarily stored in the staging
@@ -224,7 +229,7 @@ def version(ver, checksum=None, **kwargs):
     return _execute
 
 
-def _depends_on(pkg, spec, when=None, type=None):
+def _depends_on(pkg, spec, when=None, type=default_deptype):
     # If when is False do nothing
     if when is False:
         return
@@ -233,33 +238,18 @@ def _depends_on(pkg, spec, when=None, type=None):
         when = pkg.name
     when_spec = parse_anonymous_spec(when, pkg.name)
 
-    if type is None:
-        # The default deptype is build and link because the common case is to
-        # build against a library which then turns into a runtime dependency
-        # due to the linker.
-        # XXX(deptype): Add 'run' to this? It's an uncommon dependency type,
-        #               but is most backwards-compatible.
-        type = ('build', 'link')
-
-    type = spack.spec.canonical_deptype(type)
-
-    for deptype in type:
-        if deptype not in spack.spec.alldeps:
-            raise UnknownDependencyTypeError('depends_on', pkg.name, deptype)
-
     dep_spec = Spec(spec)
     if pkg.name == dep_spec.name:
         raise CircularReferenceError('depends_on', pkg.name)
 
-    pkg_deptypes = pkg.dependency_types.setdefault(dep_spec.name, set())
-    for deptype in type:
-        pkg_deptypes.add(deptype)
-
+    type = canonical_deptype(type)
     conditions = pkg.dependencies.setdefault(dep_spec.name, {})
-    if when_spec in conditions:
-        conditions[when_spec].constrain(dep_spec, deps=False)
+    if when_spec not in conditions:
+        conditions[when_spec] = Dependency(dep_spec, type)
     else:
-        conditions[when_spec] = dep_spec
+        dependency = conditions[when_spec]
+        dependency.spec.constrain(dep_spec, deps=False)
+        dependency.type |= set(type)
 
 
 @directive('conflicts')
@@ -293,8 +283,8 @@ def conflicts(conflict_spec, when=None, msg=None):
     return _execute
 
 
-@directive(('dependencies', 'dependency_types'))
-def depends_on(spec, when=None, type=None):
+@directive(('dependencies'))
+def depends_on(spec, when=None, type=default_deptype):
     """Creates a dict of deps with specs defining when they apply.
     This directive is to be used inside a Package definition to declare
     that the package requires other packages to be built first.
@@ -304,7 +294,7 @@ def depends_on(spec, when=None, type=None):
     return _execute
 
 
-@directive(('extendees', 'dependencies', 'dependency_types'))
+@directive(('extendees', 'dependencies'))
 def extends(spec, **kwargs):
     """Same as depends_on, but dependency is symlinked into parent prefix.
 
@@ -372,10 +362,12 @@ def patch(url_or_filename, level=1, when=None, **kwargs):
     def _execute(pkg):
         constraint = pkg.name if when is None else when
         when_spec = parse_anonymous_spec(constraint, pkg.name)
-        cur_patches = pkg.patches.setdefault(when_spec, [])
+
         # if this spec is identical to some other, then append this
         # patch to the existing list.
+        cur_patches = pkg.patches.setdefault(when_spec, [])
         cur_patches.append(Patch.create(pkg, url_or_filename, level, **kwargs))
+
     return _execute
 
 
@@ -406,6 +398,9 @@ def variant(
             logic. It receives a tuple of values and should raise an instance
             of SpackError if the group doesn't meet the additional constraints
     """
+    if name in reserved_names:
+        raise ValueError("The variant name '%s' is reserved by Spack" % name)
+
     if values is None:
         if default in (True, False) or (type(default) is str and
                                         default.upper() in ('TRUE', 'FALSE')):
diff --git a/lib/spack/spack/graph.py b/lib/spack/spack/graph.py
index 4f4ef9a304..994a0297b6 100644
--- a/lib/spack/spack/graph.py
+++ b/lib/spack/spack/graph.py
@@ -69,11 +69,12 @@ from llnl.util.lang import *
 from llnl.util.tty.color import *
 
 from spack.spec import *
+from spack.dependency import *
 
 __all__ = ['topological_sort', 'graph_ascii', 'AsciiGraph', 'graph_dot']
 
 
-def topological_sort(spec, reverse=False, deptype=None):
+def topological_sort(spec, reverse=False, deptype='all'):
     """Topological sort for specs.
 
     Return a list of dependency specs sorted topologically.  The spec
@@ -142,7 +143,7 @@ class AsciiGraph(object):
         self.node_character = 'o'
         self.debug = False
         self.indent = 0
-        self.deptype = alldeps
+        self.deptype = all_deptypes
 
         # These are colors in the order they'll be used for edges.
         # See llnl.util.tty.color for details on color characters.
@@ -494,7 +495,7 @@ class AsciiGraph(object):
 
 
 def graph_ascii(spec, node='o', out=None, debug=False,
-                indent=0, color=None, deptype=None):
+                indent=0, color=None, deptype='all'):
     graph = AsciiGraph()
     graph.debug = debug
     graph.indent = indent
@@ -505,7 +506,7 @@ def graph_ascii(spec, node='o', out=None, debug=False,
     graph.write(spec, color=color, out=out)
 
 
-def graph_dot(specs, deptype=None, static=False, out=None):
+def graph_dot(specs, deptype='all', static=False, out=None):
     """Generate a graph in dot format of all provided specs.
 
     Print out a dot formatted graph of all the dependencies between
@@ -516,9 +517,7 @@ def graph_dot(specs, deptype=None, static=False, out=None):
     """
     if out is None:
         out = sys.stdout
-
-    if deptype is None:
-        deptype = alldeps
+    deptype = canonical_deptype(deptype)
 
     out.write('digraph G {\n')
     out.write('  labelloc = "b"\n')
diff --git a/lib/spack/spack/package.py b/lib/spack/spack/package.py
index 3bfee0a0b6..0bebb48387 100644
--- a/lib/spack/spack/package.py
+++ b/lib/spack/spack/package.py
@@ -820,9 +820,18 @@ class PackageBase(with_metaclass(PackageMeta, object)):
         self._fetcher = f
 
     def dependencies_of_type(self, *deptypes):
-        """Get subset of the dependencies with certain types."""
-        return dict((name, conds) for name, conds in self.dependencies.items()
-                    if any(d in self.dependency_types[name] for d in deptypes))
+        """Get dependencies that can possibly have these deptypes.
+
+        This analyzes the package and determines which dependencies *can*
+        be a certain kind of dependency. Note that they may not *always*
+        be this kind of dependency, since dependencies can be optional,
+        so something may be a build dependency in one configuration and a
+        run dependency in another.
+        """
+        return dict(
+            (name, conds) for name, conds in self.dependencies.items()
+            if any(dt in self.dependencies[name][cond].type
+                   for cond in conds for dt in deptypes))
 
     @property
     def extendee_spec(self):
@@ -1954,7 +1963,7 @@ def dump_packages(spec, path):
     # Note that we copy them in as they are in the *install* directory
     # NOT as they are in the repository, because we want a snapshot of
     # how *this* particular build was done.
-    for node in spec.traverse(deptype=spack.alldeps):
+    for node in spec.traverse(deptype=all):
         if node is not spec:
             # Locate the dependency package in the install tree and find
             # its provenance information.
diff --git a/lib/spack/spack/patch.py b/lib/spack/spack/patch.py
index e542744bbe..3f0596b23a 100644
--- a/lib/spack/spack/patch.py
+++ b/lib/spack/spack/patch.py
@@ -97,7 +97,6 @@ class Patch(object):
             patch('-s', '-p', str(self.level), '-i', self.path)
 
 
-
 class FilePatch(Patch):
     """Describes a patch that is retrieved from a file in the repository"""
     def __init__(self, pkg, path_or_url, level):
diff --git a/lib/spack/spack/spec.py b/lib/spack/spack/spec.py
index 584396e82d..dc2042a7f4 100644
--- a/lib/spack/spack/spec.py
+++ b/lib/spack/spack/spec.py
@@ -121,6 +121,7 @@ import spack.store
 import spack.util.spack_json as sjson
 import spack.util.spack_yaml as syaml
 
+from spack.dependency import *
 from spack.util.module_cmd import get_path_from_module, load_module
 from spack.error import SpecError, UnsatisfiableSpecError
 from spack.provider_index import ProviderIndex
@@ -135,8 +136,6 @@ from yaml.error import MarkedYAMLError
 
 __all__ = [
     'Spec',
-    'alldeps',
-    'canonical_deptype',
     'parse',
     'parse_anonymous_spec',
     'SpecError',
@@ -196,31 +195,10 @@ _separators = '[\\%s]' % '\\'.join(color_formats.keys())
 #: every time we call str()
 _any_version = VersionList([':'])
 
-#: Types of dependencies that Spack understands.
-alldeps = ('build', 'link', 'run', 'test')
-
 #: Max integer helps avoid passing too large a value to cyaml.
 maxint = 2 ** (ctypes.sizeof(ctypes.c_int) * 8 - 1) - 1
 
 
-def canonical_deptype(deptype):
-    if deptype in (None, 'all', all):
-        return alldeps
-
-    elif isinstance(deptype, string_types):
-        if deptype not in alldeps:
-            raise ValueError('Invalid dependency type: %s' % deptype)
-        return (deptype,)
-
-    elif isinstance(deptype, (tuple, list)):
-        invalid = next((d for d in deptype if d not in alldeps), None)
-        if invalid:
-            raise ValueError('Invalid dependency type: %s' % invalid)
-        return tuple(sorted(deptype))
-
-    return deptype
-
-
 def colorize_spec(spec):
     """Returns a spec colorized according to the colors specified in
        color_formats."""
@@ -1098,19 +1076,19 @@ class Spec(object):
                 if deptype and (not dep.deptypes or
                                 any(d in deptype for d in dep.deptypes))]
 
-    def dependencies(self, deptype=None):
+    def dependencies(self, deptype='all'):
         return [d.spec
                 for d in self._find_deps(self._dependencies, deptype)]
 
-    def dependents(self, deptype=None):
+    def dependents(self, deptype='all'):
         return [d.parent
                 for d in self._find_deps(self._dependents, deptype)]
 
-    def dependencies_dict(self, deptype=None):
+    def dependencies_dict(self, deptype='all'):
         return dict((d.spec.name, d)
                     for d in self._find_deps(self._dependencies, deptype))
 
-    def dependents_dict(self, deptype=None):
+    def dependents_dict(self, deptype='all'):
         return dict((d.parent.name, d)
                     for d in self._find_deps(self._dependents, deptype))
 
@@ -1271,8 +1249,8 @@ class Spec(object):
             for dspec in self.traverse_edges(**kwargs):
                 yield get_spec(dspec)
 
-    def traverse_edges(self, visited=None, d=0, deptype=None,
-                       deptype_query=None, dep_spec=None, **kwargs):
+    def traverse_edges(self, visited=None, d=0, deptype='all',
+                       deptype_query=default_deptype, dep_spec=None, **kwargs):
         """Generic traversal of the DAG represented by this spec.
            This will yield each node in the spec.  Options:
 
@@ -1325,8 +1303,7 @@ class Spec(object):
         order = kwargs.get('order', 'pre')
 
         deptype = canonical_deptype(deptype)
-        if deptype_query is None:
-            deptype_query = ('link', 'run')
+        deptype_query = canonical_deptype(deptype_query)
 
         # Make sure kwargs have legal values; raise ValueError if not.
         def validate(name, val, allowed_values):
@@ -1817,7 +1794,7 @@ class Spec(object):
             changed = any(changes)
             force = True
 
-        for s in self.traverse(deptype_query=alldeps):
+        for s in self.traverse(deptype_query=all):
             # After concretizing, assign namespaces to anything left.
             # Note that this doesn't count as a "change".  The repository
             # configuration is constant throughout a spack run, and
@@ -1864,7 +1841,7 @@ class Spec(object):
         Only for internal use -- client code should use "concretize"
         unless there is a need to force a spec to be concrete.
         """
-        for s in self.traverse(deptype_query=alldeps):
+        for s in self.traverse(deptype_query=all):
             s._normal = value
             s._concrete = value
 
@@ -1887,7 +1864,7 @@ class Spec(object):
            returns them.
         """
         copy = kwargs.get('copy', True)
-        deptype_query = kwargs.get('deptype_query')
+        deptype_query = kwargs.get('deptype_query', 'all')
 
         flat_deps = {}
         try:
@@ -1916,7 +1893,7 @@ class Spec(object):
             # parser doesn't allow it. Spack must be broken!
             raise InconsistentSpecError("Invalid Spec DAG: %s" % e.message)
 
-    def index(self, deptype=None):
+    def index(self, deptype='all'):
         """Return DependencyMap that points to all the dependencies in this
            spec."""
         dm = DependencyMap()
@@ -1927,28 +1904,39 @@ class Spec(object):
     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.
+        Args:
+            name (str): name of dependency to evaluate conditions on.
+
+        Returns:
+            (tuple): tuple of ``Spec`` and tuple of ``deptypes``.
+
+        If the package depends on <name> in the current spec
+        configuration, return the constrained dependency and
+        corresponding dependency types.
+
+        If no conditions are True (and we don't depend on it), return
+        ``(None, None)``.
         """
         pkg = spack.repo.get(self.fullname)
         conditions = pkg.dependencies[name]
 
         substitute_abstract_variants(self)
         # 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)
-            if sat:
+        dep, deptypes = None, None
+        for when_spec, dependency in conditions.items():
+            if self.satisfies(when_spec, strict=True):
                 if dep is None:
                     dep = Spec(name)
+                    deptypes = set()
                 try:
-                    dep.constrain(dep_spec)
+                    dep.constrain(dependency.spec)
+                    deptypes |= dependency.type
                 except UnsatisfiableSpecError as e:
                     e.message = ("Conflicting conditional dependencies on"
                                  "package %s for spec %s" % (self.name, self))
                     raise e
-        return dep
+
+        return dep, deptypes
 
     def _find_provider(self, vdep, provider_index):
         """Find provider for a virtual spec in the provider index.
@@ -2086,13 +2074,12 @@ class Spec(object):
             changed = False
             for dep_name in pkg.dependencies:
                 # Do we depend on dep_name?  If so pkg_dep is not None.
-                pkg_dep = self._evaluate_dependency_conditions(dep_name)
-                deptypes = pkg.dependency_types[dep_name]
-                # If pkg_dep is a dependency, merge it.
-                if pkg_dep and (spack.package_testing.check(self.name) or
-                                set(deptypes) - set(['test'])):
+                dep, deptypes = self._evaluate_dependency_conditions(dep_name)
+                # If dep is a needed dependency, merge it.
+                if dep and (spack.package_testing.check(self.name) or
+                            set(deptypes) - set(['test'])):
                     changed |= self._merge_dependency(
-                        pkg_dep, deptypes, visited, spec_deps, provider_index)
+                        dep, deptypes, visited, spec_deps, provider_index)
             any_change |= changed
 
         return any_change
@@ -2127,7 +2114,7 @@ class Spec(object):
         # Ensure first that all packages & compilers in the DAG exist.
         self.validate_or_raise()
         # Get all the dependencies into one DependencyMap
-        spec_deps = self.flat_dependencies(copy=False, deptype_query=alldeps)
+        spec_deps = self.flat_dependencies(copy=False, deptype_query=all)
 
         # Initialize index of virtual dependency providers if
         # concretize didn't pass us one already
@@ -2536,13 +2523,15 @@ class Spec(object):
         # If we preserved the original structure, we can copy them
         # safely. If not, they need to be recomputed.
         if caches is None:
-            caches = (deps is True or deps == alldeps)
+            caches = (deps is True or deps == all_deptypes)
 
         # If we copy dependencies, preserve DAG structure in the new spec
         if deps:
             # If caller restricted deptypes to be copied, adjust that here.
             # By default, just copy all deptypes
-            deptypes = deps if isinstance(deps, (tuple, list)) else alldeps
+            deptypes = all_deptypes
+            if isinstance(deps, (tuple, list)):
+                deptypes = deps
             self._dup_deps(other, deptypes, caches)
 
         if caches:
@@ -3013,10 +3002,10 @@ class Spec(object):
             if show_types:
                 out += '['
                 if dep_spec.deptypes:
-                    for t in alldeps:
+                    for t in all_deptypes:
                         out += ''.join(t[0] if t in dep_spec.deptypes else ' ')
                 else:
-                    out += ' ' * len(alldeps)
+                    out += ' ' * len(all_deptypes)
                 out += ']  '
 
             out += ("    " * d)
diff --git a/lib/spack/spack/test/conftest.py b/lib/spack/spack/test/conftest.py
index e19729e717..16ac5dfe86 100644
--- a/lib/spack/spack/test/conftest.py
+++ b/lib/spack/spack/test/conftest.py
@@ -42,6 +42,7 @@ import spack.repository
 import spack.stage
 import spack.util.executable
 import spack.util.pattern
+from spack.dependency import *
 from spack.package import PackageBase
 from spack.fetch_strategy import *
 from spack.spec import Spec
@@ -567,20 +568,22 @@ class MockPackage(object):
                  versions=None):
         self.name = name
         self.spec = None
-        dep_to_conditions = ordereddict_backport.OrderedDict()
-        for dep in dependencies:
+        self.dependencies = ordereddict_backport.OrderedDict()
+
+        assert len(dependencies) == len(dependency_types)
+        for dep, dtype in zip(dependencies, dependency_types):
+            d = Dependency(Spec(dep.name), type=dtype)
             if not conditions or dep.name not in conditions:
-                dep_to_conditions[dep.name] = {name: dep.name}
+                self.dependencies[dep.name] = {Spec(name): d}
             else:
-                dep_to_conditions[dep.name] = conditions[dep.name]
-        self.dependencies = dep_to_conditions
-        self.dependency_types = dict(
-            (x.name, y) for x, y in zip(dependencies, dependency_types))
+                self.dependencies[dep.name] = {Spec(conditions[dep.name]): d}
+
         if versions:
             self.versions = versions
         else:
             versions = list(Version(x) for x in [1, 2, 3])
             self.versions = dict((x, {'preferred': False}) for x in versions)
+
         self.variants = {}
         self.provided = {}
         self.conflicts = {}
@@ -589,18 +592,18 @@ class MockPackage(object):
 class MockPackageMultiRepo(object):
 
     def __init__(self, packages):
-        self.specToPkg = dict((x.name, x) for x in packages)
+        self.spec_to_pkg = dict((x.name, x) for x in packages)
 
     def get(self, spec):
         if not isinstance(spec, spack.spec.Spec):
             spec = Spec(spec)
-        return self.specToPkg[spec.name]
+        return self.spec_to_pkg[spec.name]
 
     def get_pkg_class(self, name):
-        return self.specToPkg[name]
+        return self.spec_to_pkg[name]
 
     def exists(self, name):
-        return name in self.specToPkg
+        return name in self.spec_to_pkg
 
     def is_virtual(self, name):
         return False
diff --git a/lib/spack/spack/test/spec_dag.py b/lib/spack/spack/test/spec_dag.py
index 648a49de9a..719b3a2569 100644
--- a/lib/spack/spack/test/spec_dag.py
+++ b/lib/spack/spack/test/spec_dag.py
@@ -30,8 +30,9 @@ import spack
 import spack.architecture
 import spack.package
 
+from spack.spec import Spec
+from spack.dependency import *
 from spack.test.conftest import MockPackage, MockPackageMultiRepo
-from spack.spec import Spec, canonical_deptype, alldeps
 
 
 def check_links(spec_to_check):
@@ -54,7 +55,7 @@ def set_dependency(saved_deps):
     """Returns a function that alters the dependency information
     for a package.
     """
-    def _mock(pkg_name, spec, deptypes=spack.alldeps):
+    def _mock(pkg_name, spec, deptypes=all_deptypes):
         """Alters dependence information for a package.
 
         Adds a dependency on <spec> to pkg. Use this to mock up constraints.
@@ -65,8 +66,9 @@ def set_dependency(saved_deps):
         if pkg_name not in saved_deps:
             saved_deps[pkg_name] = (pkg, pkg.dependencies.copy())
 
-        pkg.dependencies[spec.name] = {Spec(pkg_name): spec}
-        pkg.dependency_types[spec.name] = set(deptypes)
+        cond = Spec(pkg.name)
+        dependency = Dependency(spec, deptypes)
+        pkg.dependencies[spec.name] = {cond: dependency}
     return _mock
 
 
@@ -592,7 +594,7 @@ class TestSpecDag(object):
                  'dtlink1', 'dtlink3', 'dtlink4', 'dtrun1', 'dtlink5',
                  'dtrun3', 'dtbuild3']
 
-        traversal = dag.traverse(deptype=spack.alldeps)
+        traversal = dag.traverse(deptype=all)
         assert [x.name for x in traversal] == names
 
     def test_deptype_traversal_run(self):
@@ -841,12 +843,16 @@ class TestSpecDag(object):
 
     def test_canonical_deptype(self):
         # special values
-        assert canonical_deptype(all) == alldeps
-        assert canonical_deptype('all') == alldeps
-        assert canonical_deptype(None) == alldeps
+        assert canonical_deptype(all) == all_deptypes
+        assert canonical_deptype('all') == all_deptypes
 
-        # everything in alldeps is canonical
-        for v in alldeps:
+        with pytest.raises(ValueError):
+            canonical_deptype(None)
+        with pytest.raises(ValueError):
+            canonical_deptype([None])
+
+        # everything in all_deptypes is canonical
+        for v in all_deptypes:
             assert canonical_deptype(v) == (v,)
 
         # tuples