64 files changed, 554 insertions, 486 deletions
diff --git a/bin/spack b/bin/spack
index ac9cd5738f..60a2ef4c3a 100755
--- a/bin/spack
+++ b/bin/spack
@@ -74,9 +74,10 @@ args = parser.parse_args()
 spack.verbose = args.verbose
 spack.debug = args.debug
 if args.mock:
-    from spack.util.filesystem import new_path
-    mock_path = new_path(spack.module_path, 'test', 'mock_packages')
-    spack.packages_path = mock_path
+    from llnl.util.filesystem import join_path
+    from spack.packages import PackageDB
+    mock_path = join_path(spack.module_path, 'test', 'mock_packages')
+    spack.db = PackageDB(mock_path)
 
 # If the user asked for it, don't check ssl certs.
 if args.insecure:
diff --git a/lib/spack/spack/cmd/checksum.py b/lib/spack/spack/cmd/checksum.py
index 4867d1b520..97ce91386b 100644
--- a/lib/spack/spack/cmd/checksum.py
+++ b/lib/spack/spack/cmd/checksum.py
@@ -34,7 +34,6 @@ from llnl.util.tty.colify import colify
 
 import spack
 import spack.cmd
-import spack.packages as packages
 import spack.util.crypto
 from spack.stage import Stage, FailedDownloadError
 from spack.version import *
@@ -81,7 +80,7 @@ def get_checksums(versions, urls, **kwargs):
 
 def checksum(parser, args):
     # get the package we're going to generate checksums for
-    pkg = packages.get(args.package)
+    pkg = spack.db.get(args.package)
 
     # If the user asked for specific versions, use those.
     versions = [ver(v) for v in args.versions]
diff --git a/lib/spack/spack/cmd/clean.py b/lib/spack/spack/cmd/clean.py
index d54b529d3c..6091cae6c8 100644
--- a/lib/spack/spack/cmd/clean.py
+++ b/lib/spack/spack/cmd/clean.py
@@ -26,8 +26,8 @@ import argparse
 
 import llnl.util.tty as tty
 
+import spack
 import spack.cmd
-import spack.packages as packages
 import spack.stage as stage
 
 description = "Remove staged files for packages"
@@ -49,7 +49,7 @@ def clean(parser, args):
 
     specs = spack.cmd.parse_specs(args.packages, concretize=True)
     for spec in specs:
-        package = packages.get(spec)
+        package = spack.db.get(spec)
         if args.dist:
             package.do_clean_dist()
         elif args.work:
diff --git a/lib/spack/spack/cmd/create.py b/lib/spack/spack/cmd/create.py
index 236485f9a1..e8fbb46d7a 100644
--- a/lib/spack/spack/cmd/create.py
+++ b/lib/spack/spack/cmd/create.py
@@ -33,7 +33,6 @@ import llnl.util.tty as tty
 import spack
 import spack.cmd
 import spack.package
-import spack.packages as packages
 import spack.url
 import spack.util.crypto as crypto
 import spack.cmd.checksum
@@ -131,7 +130,7 @@ def create(parser, args):
         tty.msg("Couldn't guess a name for this package.")
         while not name:
             new_name = raw_input("Name: ")
-            if packages.valid_name(name):
+            if spack.db.valid_name(name):
                 name = new_name
             else:
                 print "Package name can only contain A-Z, a-z, 0-9, '_' and '-'"
@@ -141,11 +140,11 @@ def create(parser, args):
 
     tty.msg("Creating template for package %s" % name)
 
-    pkg_path = packages.filename_for_package_name(name)
+    pkg_path = spack.db.filename_for_package_name(name)
     if os.path.exists(pkg_path) and not args.force:
         tty.die("%s already exists." % pkg_path)
 
-    class_name = packages.class_name_for_package_name(name)
+    class_name = spack.db.class_name_for_package_name(name)
     versions = list(reversed(spack.package.find_versions_of_archive(url)))
 
     archives_to_fetch = 1
diff --git a/lib/spack/spack/cmd/edit.py b/lib/spack/spack/cmd/edit.py
index b6373872c0..8a22567099 100644
--- a/lib/spack/spack/cmd/edit.py
+++ b/lib/spack/spack/cmd/edit.py
@@ -29,7 +29,6 @@ from contextlib import closing
 import llnl.util.tty as tty
 
 import spack
-import spack.packages as packages
 
 description = "Open package files in $EDITOR"
 
@@ -67,7 +66,7 @@ def edit(parser, args):
     if not name:
         path = spack.packages_path
     else:
-        path = packages.filename_for_package_name(name)
+        path = spack.db.filename_for_package_name(name)
 
         if os.path.exists(path):
             if not os.path.isfile(path):
@@ -78,7 +77,7 @@ def edit(parser, args):
             tty.die("No package '%s'.  Use spack create, or supply -f/--force "
                     "to edit a new file." % name)
         else:
-            class_name = packages.class_name_for_package_name(name)
+            class_name = spack.db.class_name_for_package_name(name)
 
             with closing(open(path, "w")) as pkg_file:
                 pkg_file.write(
diff --git a/lib/spack/spack/cmd/fetch.py b/lib/spack/spack/cmd/fetch.py
index 86bc9cdef3..1dd8703daf 100644
--- a/lib/spack/spack/cmd/fetch.py
+++ b/lib/spack/spack/cmd/fetch.py
@@ -24,8 +24,8 @@
 ##############################################################################
 import argparse
 
+import spack
 import spack.cmd
-import spack.packages as packages
 
 description = "Fetch archives for packages"
 
@@ -46,5 +46,5 @@ def fetch(parser, args):
 
     specs = spack.cmd.parse_specs(args.packages, concretize=True)
     for spec in specs:
-        package = packages.get(spec)
+        package = spack.db.get(spec)
         package.do_fetch()
diff --git a/lib/spack/spack/cmd/find.py b/lib/spack/spack/cmd/find.py
index 3db0608d6b..9e8bf190a8 100644
--- a/lib/spack/spack/cmd/find.py
+++ b/lib/spack/spack/cmd/find.py
@@ -31,7 +31,7 @@ from llnl.util.tty.color import *
 
 import spack
 import spack.spec
-import spack.packages as packages
+import spack
 
 
 description ="Find installed spack packages"
@@ -83,7 +83,7 @@ def find(parser, args):
 
     # Make a dict with specs keyed by architecture and compiler.
     index = hasher()
-    for spec in packages.installed_package_specs():
+    for spec in spack.db.installed_package_specs():
         if query_specs and not any(spec.satisfies(q) for q in query_specs):
             continue
 
diff --git a/lib/spack/spack/cmd/graph.py b/lib/spack/spack/cmd/graph.py
index 07fe67ca4b..39dbfbb150 100644
--- a/lib/spack/spack/cmd/graph.py
+++ b/lib/spack/spack/cmd/graph.py
@@ -23,9 +23,8 @@
 # Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 ##############################################################################
 import spack
-import spack.packages as packages
 
 description = "Write out inter-package dependencies in dot graph format"
 
 def graph(parser, args):
-    packages.graph_dependencies()
+    spack.db.graph_dependencies()
diff --git a/lib/spack/spack/cmd/info.py b/lib/spack/spack/cmd/info.py
index 3a17b2ce3c..648dbf905a 100644
--- a/lib/spack/spack/cmd/info.py
+++ b/lib/spack/spack/cmd/info.py
@@ -26,7 +26,6 @@ import re
 import textwrap
 from llnl.util.tty.colify import colify
 import spack
-import spack.packages as packages
 
 description = "Get detailed information on a particular package"
 
@@ -35,7 +34,7 @@ def setup_parser(subparser):
 
 
 def info(parser, args):
-    package = packages.get(args.name)
+    package = spack.db.get(args.name)
     print "Package:   ", package.name
     print "Homepage:  ", package.homepage
     print "Download:  ", package.url
diff --git a/lib/spack/spack/cmd/install.py b/lib/spack/spack/cmd/install.py
index f80baf0ad6..02194c1b3f 100644
--- a/lib/spack/spack/cmd/install.py
+++ b/lib/spack/spack/cmd/install.py
@@ -26,7 +26,6 @@ import sys
 import argparse
 
 import spack
-import spack.packages as packages
 import spack.cmd
 
 description = "Build and install packages"
@@ -56,6 +55,6 @@ def install(parser, args):
     specs = spack.cmd.parse_specs(args.packages, concretize=True)
 
     for spec in specs:
-        package = packages.get(spec)
+        package = spack.db.get(spec)
         package.dirty = args.dirty
         package.do_install()
diff --git a/lib/spack/spack/cmd/list.py b/lib/spack/spack/cmd/list.py
index 15e1581868..2b996371ea 100644
--- a/lib/spack/spack/cmd/list.py
+++ b/lib/spack/spack/cmd/list.py
@@ -22,8 +22,8 @@
 # along with this program; if not, write to the Free Software Foundation,
 # Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 ##############################################################################
-import spack.packages as packages
 from llnl.util.tty.colify import colify
+import spack
 
 description ="List available spack packages"
 
@@ -33,4 +33,4 @@ def setup_parser(subparser):
 
 def list(parser, args):
     # Print all the package names in columns
-    colify(packages.all_package_names())
+    colify(spack.db.all_package_names())
diff --git a/lib/spack/spack/cmd/mirror.py b/lib/spack/spack/cmd/mirror.py
index 91fe38fe67..94e40557ff 100644
--- a/lib/spack/spack/cmd/mirror.py
+++ b/lib/spack/spack/cmd/mirror.py
@@ -29,9 +29,8 @@ import argparse
 import llnl.util.tty as tty
 from llnl.util.filesystem import mkdirp, join_path
 
-import spack.packages as packages
+import spack
 import spack.cmd
-
 from spack.stage import Stage
 
 
@@ -46,7 +45,7 @@ def setup_parser(subparser):
 
 def mirror(parser, args):
     if not args.packages:
-        args.packages = [p for p in packages.all_package_names()]
+        args.packages = [p for p in spack.db.all_package_names()]
 
     if os.path.isfile(args.directory):
         tty.error("%s already exists and is a file." % args.directory)
@@ -59,7 +58,7 @@ def mirror(parser, args):
 
     # Iterate through packages and download all the safe tarballs for each of them
     for pkg_name in args.packages:
-        pkg = packages.get(pkg_name)
+        pkg = spack.db.get(pkg_name)
 
         # Skip any package that has no checksummed versions.
         if not pkg.versions:
diff --git a/lib/spack/spack/cmd/patch.py b/lib/spack/spack/cmd/patch.py
index cc790df56e..2356583b07 100644
--- a/lib/spack/spack/cmd/patch.py
+++ b/lib/spack/spack/cmd/patch.py
@@ -25,7 +25,7 @@
 import argparse
 
 import spack.cmd
-import spack.packages as packages
+import spack
 
 
 description="Patch expanded archive sources in preparation for install"
@@ -47,5 +47,5 @@ def patch(parser, args):
 
     specs = spack.cmd.parse_specs(args.packages, concretize=True)
     for spec in specs:
-        package = packages.get(spec)
+        package = spack.db.get(spec)
         package.do_patch()
diff --git a/lib/spack/spack/cmd/providers.py b/lib/spack/spack/cmd/providers.py
index b59950aeb3..1a652c82d1 100644
--- a/lib/spack/spack/cmd/providers.py
+++ b/lib/spack/spack/cmd/providers.py
@@ -27,8 +27,8 @@ import argparse
 
 from llnl.util.tty.colify import colify
 
+import spack
 import spack.cmd
-import spack.packages
 
 description ="List packages that provide a particular virtual package"
 
@@ -39,4 +39,4 @@ def setup_parser(subparser):
 
 def providers(parser, args):
     for spec in spack.cmd.parse_specs(args.vpkg_spec):
-        colify(sorted(spack.packages.providers_for(spec)), indent=4)
+        colify(sorted(spack.db.providers_for(spec)), indent=4)
diff --git a/lib/spack/spack/cmd/stage.py b/lib/spack/spack/cmd/stage.py
index 2ce3d66bcb..1bf1f93c2f 100644
--- a/lib/spack/spack/cmd/stage.py
+++ b/lib/spack/spack/cmd/stage.py
@@ -24,9 +24,8 @@
 ##############################################################################
 import argparse
 
+import spack
 import spack.cmd
-import spack.packages as packages
-
 
 description="Expand downloaded archive in preparation for install"
 
@@ -47,5 +46,5 @@ def stage(parser, args):
 
     specs = spack.cmd.parse_specs(args.packages, concretize=True)
     for spec in specs:
-        package = packages.get(spec)
+        package = spack.db.get(spec)
         package.do_stage()
diff --git a/lib/spack/spack/cmd/test.py b/lib/spack/spack/cmd/test.py
index 16d693aa21..b1418ac2f1 100644
--- a/lib/spack/spack/cmd/test.py
+++ b/lib/spack/spack/cmd/test.py
@@ -28,7 +28,6 @@ from llnl.util.tty.colify import colify
 from llnl.util.lang import list_modules
 
 import spack
-import spack.packages as packages
 import spack.test
 
 description ="Run unit tests"
diff --git a/lib/spack/spack/cmd/uninstall.py b/lib/spack/spack/cmd/uninstall.py
index e47b4d7f7a..7982892d81 100644
--- a/lib/spack/spack/cmd/uninstall.py
+++ b/lib/spack/spack/cmd/uninstall.py
@@ -26,8 +26,8 @@ import argparse
 
 import llnl.util.tty as tty
 
+import spack
 import spack.cmd
-import spack.packages as packages
 
 description="Remove an installed package"
 
@@ -49,7 +49,7 @@ def uninstall(parser, args):
     # Fail and ask user to be unambiguous if it doesn't
     pkgs = []
     for spec in specs:
-        matching_specs = packages.get_installed(spec)
+        matching_specs = spack.db.get_installed(spec)
         if len(matching_specs) > 1:
             tty.die("%s matches multiple packages.  Which one did you mean?"
                     % spec, *matching_specs)
@@ -58,7 +58,7 @@ def uninstall(parser, args):
             tty.die("%s does not match any installed packages." % spec)
 
         installed_spec = matching_specs[0]
-        pkgs.append(packages.get(installed_spec))
+        pkgs.append(spack.db.get(installed_spec))
 
     # Sort packages to be uninstalled by the number of installed dependents
     # This ensures we do things in the right order
diff --git a/lib/spack/spack/cmd/versions.py b/lib/spack/spack/cmd/versions.py
index 1f0da9fbd8..c545035279 100644
--- a/lib/spack/spack/cmd/versions.py
+++ b/lib/spack/spack/cmd/versions.py
@@ -24,7 +24,7 @@
 ##############################################################################
 import os
 from llnl.util.tty.colify import colify
-import spack.packages as packages
+import spack
 
 description ="List available versions of a package"
 
@@ -33,5 +33,5 @@ def setup_parser(subparser):
 
 
 def versions(parser, args):
-    pkg = packages.get(args.package)
+    pkg = spack.db.get(args.package)
     colify(reversed(pkg.fetch_available_versions()))
diff --git a/lib/spack/spack/concretize.py b/lib/spack/spack/concretize.py
index 790d67cac8..fc360d59ba 100644
--- a/lib/spack/spack/concretize.py
+++ b/lib/spack/spack/concretize.py
@@ -35,7 +35,6 @@ TODO: make this customizable and allow users to configure
 """
 import spack.architecture
 import spack.compilers
-import spack.packages
 import spack.spec
 from spack.version import *
 
diff --git a/lib/spack/spack/globals.py b/lib/spack/spack/globals.py
index 2cf2761362..20801447fa 100644
--- a/lib/spack/spack/globals.py
+++ b/lib/spack/spack/globals.py
@@ -30,6 +30,7 @@ from spack.version import Version
 from spack.util.executable import *
 from spack.directory_layout import SpecHashDirectoryLayout
 from spack.concretize import DefaultConcretizer
+from spack.packages import PackageDB
 
 # This lives in $prefix/lib/spac/spack/__file__
 prefix = ancestor(__file__, 4)
@@ -41,7 +42,6 @@ spack_file = join_path(prefix, "bin", "spack")
 lib_path       = join_path(prefix, "lib", "spack")
 env_path       = join_path(lib_path, "env")
 module_path    = join_path(lib_path, "spack")
-packages_path  = join_path(module_path, "packages")
 compilers_path = join_path(module_path, "compilers")
 test_path      = join_path(module_path, "test")
 
@@ -51,6 +51,12 @@ stage_path     = join_path(var_path, "stage")
 install_path   = join_path(prefix, "opt")
 
 #
+# Set up the packages database.
+#
+db = PackageDB(join_path(module_path, "packages"))
+
+
+#
 # This controls how spack lays out install prefixes and
 # stage directories.
 #
diff --git a/lib/spack/spack/package.py b/lib/spack/spack/package.py
index 68e4e30b3b..ff020fb44c 100644
--- a/lib/spack/spack/package.py
+++ b/lib/spack/spack/package.py
@@ -44,19 +44,19 @@ from urlparse import urlparse
 
 import llnl.util.tty as tty
 from llnl.util.tty.color import cwrite
-from llnl.util.filesystem import touch
+from llnl.util.filesystem import *
 from llnl.util.lang import *
 
-from spack import *
+import spack
 import spack.spec
 import spack.error
-import spack.packages as packages
 import spack.url as url
 import spack.util.crypto as crypto
 from spack.version import *
 from spack.stage import Stage
 from spack.util.web import get_pages
 from spack.util.environment import *
+from spack.util.executable import Executable, which
 from spack.util.compression import allowed_archive
 
 """Allowed URL schemes for spack packages."""
@@ -480,7 +480,7 @@ class Package(object):
                     yield spec
                 continue
 
-            for pkg in packages.get(name).preorder_traversal(visited, **kwargs):
+            for pkg in spack.db.get(name).preorder_traversal(visited, **kwargs):
                 yield pkg
 
 
@@ -539,7 +539,7 @@ class Package(object):
         """Return a list of the specs of all installed packages that depend
            on this one."""
         dependents = []
-        for spec in packages.installed_package_specs():
+        for spec in spack.db.installed_package_specs():
             if self.name in spec.dependencies:
                 dep_spec = spec.dependencies[self.name]
                 if self.spec == dep_spec:
@@ -594,7 +594,7 @@ class Package(object):
 
         self.stage.fetch()
 
-        if self.version in self.versions:
+        if spack.do_checksum and self.version in self.versions:
             digest = self.versions[self.version]
             checker = crypto.Checker(digest)
             if checker.check(self.stage.archive_file):
@@ -720,28 +720,28 @@ class Package(object):
 
         # Add spack environment at front of path and pass the
         # lib location along so the compiler script can find spack
-        os.environ[SPACK_LIB] = lib_path
+        os.environ[spack.SPACK_LIB] = spack.lib_path
 
         # Fix for case-insensitive file systems.  Conflicting links are
         # in directories called "case*" within the env directory.
-        env_paths = [env_path]
-        for file in os.listdir(env_path):
-            path = join_path(env_path, file)
+        env_paths = [spack.env_path]
+        for file in os.listdir(spack.env_path):
+            path = join_path(spack.env_path, file)
             if file.startswith("case") and os.path.isdir(path):
                 env_paths.append(path)
         path_put_first("PATH", env_paths)
-        path_set(SPACK_ENV_PATH, env_paths)
+        path_set(spack.SPACK_ENV_PATH, env_paths)
 
         # Pass along prefixes of dependencies here
         path_set(
-            SPACK_DEPENDENCIES,
+            spack.SPACK_DEPENDENCIES,
             [dep.package.prefix for dep in self.spec.dependencies.values()])
 
         # Install location
-        os.environ[SPACK_PREFIX] = self.prefix
+        os.environ[spack.SPACK_PREFIX] = self.prefix
 
         # Build root for logging.
-        os.environ[SPACK_BUILD_ROOT] = self.stage.expanded_archive_path
+        os.environ[spack.SPACK_BUILD_ROOT] = self.stage.expanded_archive_path
 
 
     def do_install_dependencies(self):
@@ -887,7 +887,7 @@ class MakeExecutable(Executable):
 
     def __call__(self, *args, **kwargs):
         parallel = kwargs.get('parallel', self.parallel)
-        disable_parallel = env_flag(SPACK_NO_PARALLEL_MAKE)
+        disable_parallel = env_flag(spack.SPACK_NO_PARALLEL_MAKE)
 
         if parallel and not disable_parallel:
             jobs = "-j%d" % multiprocessing.cpu_count()
diff --git a/lib/spack/spack/packages/__init__.py b/lib/spack/spack/packages/__init__.py
index 5731fb0d99..beb8ecf6ab 100644
--- a/lib/spack/spack/packages/__init__.py
+++ b/lib/spack/spack/packages/__init__.py
@@ -28,14 +28,22 @@ import sys
 import string
 import inspect
 import glob
+import imp
 
 import llnl.util.tty as tty
 from llnl.util.filesystem import join_path
-from llnl.util.lang import list_modules
+from llnl.util.lang import memoized
 
 import spack
 import spack.error
 import spack.spec
+from spack.virtual import ProviderIndex
+
+# Name of module under which packages are imported
+_imported_packages_module = 'spack.packages'
+
+# Name of the package file inside a package directory
+_package_file_name = 'package.py'
 
 # Valid package names can contain '-' but can't start with it.
 valid_package_re = r'^\w[\w-]*$'
@@ -43,323 +51,216 @@ valid_package_re = r'^\w[\w-]*$'
 # Don't allow consecutive [_-] in package names
 invalid_package_re = r'[_-][_-]+'
 
-instances = {}
-
-
-def _autospec(function):
-    """Decorator that automatically converts the argument of a single-arg
-       function to a Spec."""
-    def converter(arg):
-        if not isinstance(arg, spack.spec.Spec):
-            arg = spack.spec.Spec(arg)
-        return function(arg)
-    return converter
-
-
-class ProviderIndex(object):
-    """This is a dict of dicts used for finding providers of particular
-       virtual dependencies. The dict of dicts looks like:
-
-       { vpkg name :
-           { full vpkg spec : package providing spec } }
-
-       Callers can use this to first find which packages provide a vpkg,
-       then find a matching full spec.  e.g., in this scenario:
-
-       { 'mpi' :
-           { mpi@:1.1 : mpich,
-             mpi@:2.3 : mpich2@1.9: } }
-
-       Calling providers_for(spec) will find specs that provide a
-       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)
-        self.restrict = kwargs.setdefault('restrict', False)
-
-        self.providers = {}
-
-        for spec in specs:
-            if not isinstance(spec, spack.spec.Spec):
-                spec = spack.spec.Spec(spec)
-
-            if spec.virtual:
-                continue
-
-            self.update(spec)
-
-
-    def update(self, spec):
-        if type(spec) != spack.spec.Spec:
-            spec = spack.spec.Spec(spec)
-
-        assert(not spec.virtual)
-
-        pkg = spec.package
-        for provided_spec, provider_spec in pkg.provided.iteritems():
-            if provider_spec.satisfies(spec, deps=False):
-                provided_name = provided_spec.name
-                if provided_name not in self.providers:
-                    self.providers[provided_name] = {}
-
-                if self.restrict:
-                    self.providers[provided_name][provided_spec] = spec
-
-                else:
-                    # Before putting the spec in the map, constrain it so that
-                    # it provides what was asked for.
-                    constrained = spec.copy()
-                    constrained.constrain(provider_spec)
-                    self.providers[provided_name][provided_spec] = constrained
-
-
-    def providers_for(self, *vpkg_specs):
-        """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
-            if type(vspec) == str:
-                vspec = spack.spec.Spec(vspec)
-
-            # 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, 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], 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) & set(other.providers)
-        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:
-        raise UnknownPackageError(spec.name)
-
-    if not spec in instances:
-        package_class = get_class_for_package_name(spec.name)
-        instances[spec.name] = package_class(spec)
-
-    return instances[spec.name]
-
-
-@_autospec
-def get_installed(spec):
-    return [s for s in installed_package_specs() if s.satisfies(spec)]
-
-
-@_autospec
-def providers_for(vpkg_spec):
-    if not hasattr(providers_for, 'index'):
-        providers_for.index = ProviderIndex(all_package_names())
-
-    providers = providers_for.index.providers_for(vpkg_spec)
-    if not providers:
-        raise UnknownPackageError("No such virtual package: %s" % vpkg_spec)
-    return providers
-
 
 def valid_package_name(pkg_name):
+    """Return whether the pkg_name is valid for use in Spack."""
     return (re.match(valid_package_re, pkg_name) and
             not re.search(invalid_package_re, pkg_name))
 
 
 def validate_package_name(pkg_name):
+    """Raise an exception if pkg_name is not valid."""
     if not valid_package_name(pkg_name):
         raise InvalidPackageNameError(pkg_name)
 
 
-def dirname_for_package_name(pkg_name):
-    """Get the directory name for a particular package would use, even if it's a
-       foo.py package and not a directory with a foo/__init__.py file."""
-    return join_path(spack.packages_path, pkg_name)
+def class_name_for_package_name(pkg_name):
+    """Get a name for the class the package file should contain.  Note that
+       conflicts don't matter because the classes are in different modules.
+    """
+    validate_package_name(pkg_name)
 
+    class_name = pkg_name.replace('_', '-')
+    class_name = string.capwords(class_name, '-')
+    class_name = class_name.replace('-', '')
 
-def filename_for_package_name(pkg_name):
-    """Get the filename for the module we should load for a particular package.
-       The package can be either in a standalone .py file, or it can be in
-       a directory with an __init__.py file.
+    # If a class starts with a number, prefix it with Number_ to make it a valid
+    # Python class name.
+    if re.match(r'^[0-9]', class_name):
+        class_name = "Num_%s" % class_name
 
-       Package "foo" in standalone .py file:
-         packages/foo.py
+    return class_name
 
-       Package "foo" in directory:
-         packages/foo/__init__.py
 
-       The second form is used when there are files (like patches) that need
-       to be stored along with the package.
+def _autospec(function):
+    """Decorator that automatically converts the argument of a single-arg
+       function to a Spec."""
+    def converter(self, spec_like):
+        if not isinstance(spec_like, spack.spec.Spec):
+            spec_like = spack.spec.Spec(spec_like)
+        return function(self, spec_like)
+    return converter
 
-       If the package doesn't exist yet, this will just return the name
-       of the standalone .py file.
-    """
-    validate_package_name(pkg_name)
-    pkg_dir = dirname_for_package_name(pkg_name)
 
-    if os.path.isdir(pkg_dir):
-        init_file = join_path(pkg_dir, '__init__.py')
-        return init_file
-    else:
-        pkg_file  = "%s.py" % pkg_dir
-        return pkg_file
+class PackageDB(object):
+    def __init__(self, root):
+        """Construct a new package database from a root directory."""
+        self.root = root
+        self.instances = {}
+        self.provider_index = None
 
 
-def installed_package_specs():
-    return spack.install_layout.all_specs()
+    @_autospec
+    def get(self, spec):
+        if spec.virtual:
+            raise UnknownPackageError(spec.name)
 
+        if not spec in self.instances:
+            package_class = self.get_class_for_package_name(spec.name)
+            self.instances[spec.name] = package_class(spec)
 
-def all_package_names():
-    """Generator function for all packages."""
-    for module in list_modules(spack.packages_path):
-        yield module
+        return self.instances[spec.name]
 
 
-def all_packages():
-    for name in all_package_names():
-        yield get(name)
+    @_autospec
+    def get_installed(self, spec):
+        return [s for s in self.installed_package_specs() if s.satisfies(spec)]
 
 
-def class_name_for_package_name(pkg_name):
-    """Get a name for the class the package file should contain.  Note that
-       conflicts don't matter because the classes are in different modules.
-    """
-    validate_package_name(pkg_name)
+    @_autospec
+    def providers_for(self, vpkg_spec):
+        if self.provider_index is None:
+            self.provider_index = ProviderIndex(self.all_package_names())
 
-    class_name = pkg_name.replace('_', '-')
-    class_name = string.capwords(class_name, '-')
-    class_name = class_name.replace('-', '')
+        providers = self.provider_index.providers_for(vpkg_spec)
+        if not providers:
+            raise UnknownPackageError("No such virtual package: %s" % vpkg_spec)
+        return providers
 
-    # If a class starts with a number, prefix it with Number_ to make it a valid
-    # Python class name.
-    if re.match(r'^[0-9]', class_name):
-        class_name = "Num_%s" % class_name
 
-    return class_name
+    def dirname_for_package_name(self, pkg_name):
+        """Get the directory name for a particular package.  This is the
+           directory that contains its package.py file."""
+        return join_path(self.root, pkg_name)
 
 
-def exists(pkg_name):
-    """Whether a package with the supplied name exists ."""
-    return os.path.exists(filename_for_package_name(pkg_name))
+    def filename_for_package_name(self, pkg_name):
+        """Get the filename for the module we should load for a particular
+           package.  Packages for a pacakge DB live in
+           ``$root/<package_name>/package.py``
 
+           This will return a proper package.py path even if the
+           package doesn't exist yet, so callers will need to ensure
+           the package exists before importing.
+        """
+        validate_package_name(pkg_name)
+        pkg_dir = self.dirname_for_package_name(pkg_name)
+        return join_path(pkg_dir, _package_file_name)
 
-def packages_module():
-    # TODO: replace this with a proper package DB class, instead of this hackiness.
-    packages_path = re.sub(spack.module_path + '\/+', 'spack.', spack.packages_path)
-    packages_module = re.sub(r'/', '.', packages_path)
-    return packages_module
 
+    def installed_package_specs(self):
+        """Read installed package names straight from the install directory
+           layout.
+        """
+        return spack.install_layout.all_specs()
 
-def get_class_for_package_name(pkg_name):
-    file_name = filename_for_package_name(pkg_name)
 
-    if os.path.exists(file_name):
-        if not os.path.isfile(file_name):
-            tty.die("Something's wrong. '%s' is not a file!" % file_name)
-        if not os.access(file_name, os.R_OK):
-            tty.die("Cannot read '%s'!" % file_name)
-    else:
-        raise UnknownPackageError(pkg_name)
+    @memoized
+    def all_package_names(self):
+        """Generator function for all packages.  This looks for
+           ``<pkg_name>/package.py`` files within the root direcotry"""
+        all_package_names = []
+        for pkg_name in os.listdir(self.root):
+            pkg_dir  = join_path(self.root, pkg_name)
+            pkg_file = join_path(pkg_dir, _package_file_name)
+            if os.path.isfile(pkg_file):
+                all_package_names.append(pkg_name)
+            all_package_names.sort()
+        return all_package_names
 
-    # Figure out pacakges module from spack.packages_path
-    # This allows us to change the module path.
-    if not re.match(r'%s' % spack.module_path, spack.packages_path):
-        raise RuntimeError("Packages path is not a submodule of spack.")
 
-    class_name = class_name_for_package_name(pkg_name)
-    try:
-        module_name = "%s.%s" % (packages_module(), pkg_name)
-        module = __import__(module_name, fromlist=[class_name])
-    except ImportError, e:
-        tty.die("Error while importing %s.%s:\n%s" % (pkg_name, class_name, e.message))
+    def all_packages(self):
+        for name in self.all_package_names():
+            yield get(name)
 
-    cls = getattr(module, class_name)
-    if not inspect.isclass(cls):
-        tty.die("%s.%s is not a class" % (pkg_name, class_name))
 
-    return cls
+    def exists(self, pkg_name):
+        """Whether a package with the supplied name exists ."""
+        return os.path.exists(self.filename_for_package_name(pkg_name))
 
 
-def compute_dependents():
-    """Reads in all package files and sets dependence information on
-       Package objects in memory.
-    """
-    if not hasattr(compute_dependents, index):
-        compute_dependents.index = {}
-
-    for pkg in all_packages():
-        if pkg._dependents is None:
-            pkg._dependents = []
-
-        for name, dep in pkg.dependencies.iteritems():
-            dpkg = get(name)
-            if dpkg._dependents is None:
-                dpkg._dependents = []
-            dpkg._dependents.append(pkg.name)
-
-
-def graph_dependencies(out=sys.stdout):
-    """Print out a graph of all the dependencies between package.
-       Graph is in dot format."""
-    out.write('digraph G {\n')
-    out.write('  label = "Spack Dependencies"\n')
-    out.write('  labelloc = "b"\n')
-    out.write('  rankdir = "LR"\n')
-    out.write('  ranksep = "5"\n')
-    out.write('\n')
-
-    def quote(string):
-        return '"%s"' % string
-
-    deps = []
-    for pkg in all_packages():
-        out.write('  %-30s [label="%s"]\n' % (quote(pkg.name), pkg.name))
-        for dep_name, dep in pkg.dependencies.iteritems():
-            deps.append((pkg.name, dep_name))
-    out.write('\n')
-
-    for pair in deps:
-        out.write('  "%s" -> "%s"\n' % pair)
-    out.write('}\n')
+    @memoized
+    def get_class_for_package_name(self, pkg_name):
+        """Get an instance of the class for a particular package.
+
+           This method uses Python's ``imp`` package to load python
+           source from a Spack package's ``package.py`` file.  A
+           normal python import would only load each package once, but
+           because we do this dynamically, the method needs to be
+           memoized to ensure there is only ONE package class
+           instance, per package, per database.
+        """
+        file_path = self.filename_for_package_name(pkg_name)
+
+        if os.path.exists(file_path):
+            if not os.path.isfile(file_path):
+                tty.die("Something's wrong. '%s' is not a file!" % file_path)
+            if not os.access(file_path, os.R_OK):
+                tty.die("Cannot read '%s'!" % file_path)
+        else:
+            raise UnknownPackageError(pkg_name)
+
+        # Figure out pacakges module based on self.root
+        if not re.match(r'%s' % spack.module_path, self.root):
+            raise RuntimeError("Packages path is not a submodule of spack.")
+
+        class_name = class_name_for_package_name(pkg_name)
+        try:
+            module_name = _imported_packages_module + '.' + pkg_name
+            module = imp.load_source(module_name, file_path)
+
+        except ImportError, e:
+            tty.die("Error while importing %s from %s:\n%s" % (
+                pkg_name, file_path, e.message))
+
+        cls = getattr(module, class_name)
+        if not inspect.isclass(cls):
+            tty.die("%s.%s is not a class" % (pkg_name, class_name))
+
+        return cls
+
+
+    def compute_dependents(self):
+        """Reads in all package files and sets dependence information on
+           Package objects in memory.
+        """
+        if not hasattr(compute_dependents, index):
+            compute_dependents.index = {}
+
+        for pkg in all_packages():
+            if pkg._dependents is None:
+                pkg._dependents = []
+
+            for name, dep in pkg.dependencies.iteritems():
+                dpkg = get(name)
+                if dpkg._dependents is None:
+                    dpkg._dependents = []
+                dpkg._dependents.append(pkg.name)
+
+
+    def graph_dependencies(self, out=sys.stdout):
+        """Print out a graph of all the dependencies between package.
+           Graph is in dot format."""
+        out.write('digraph G {\n')
+        out.write('  label = "Spack Dependencies"\n')
+        out.write('  labelloc = "b"\n')
+        out.write('  rankdir = "LR"\n')
+        out.write('  ranksep = "5"\n')
+        out.write('\n')
+
+        def quote(string):
+            return '"%s"' % string
+
+        deps = []
+        for pkg in all_packages():
+            out.write('  %-30s [label="%s"]\n' % (quote(pkg.name), pkg.name))
+            for dep_name, dep in pkg.dependencies.iteritems():
+                deps.append((pkg.name, dep_name))
+        out.write('\n')
+
+        for pair in deps:
+            out.write('  "%s" -> "%s"\n' % pair)
+        out.write('}\n')
 
 
 class InvalidPackageNameError(spack.error.SpackError):
diff --git a/lib/spack/spack/packages/callpath.py b/lib/spack/spack/packages/callpath/package.py
index 5d92d77302..5d92d77302 100644
--- a/lib/spack/spack/packages/callpath.py
+++ b/lib/spack/spack/packages/callpath/package.py
diff --git a/lib/spack/spack/packages/cmake.py b/lib/spack/spack/packages/cmake/package.py
index 70406610b6..70406610b6 100644
--- a/lib/spack/spack/packages/cmake.py
+++ b/lib/spack/spack/packages/cmake/package.py
diff --git a/lib/spack/spack/packages/dyninst.py b/lib/spack/spack/packages/dyninst/package.py
index 2318317de5..2318317de5 100644
--- a/lib/spack/spack/packages/dyninst.py
+++ b/lib/spack/spack/packages/dyninst/package.py
diff --git a/lib/spack/spack/packages/graphlib.py b/lib/spack/spack/packages/graphlib/package.py
index c959135147..c959135147 100644
--- a/lib/spack/spack/packages/graphlib.py
+++ b/lib/spack/spack/packages/graphlib/package.py
diff --git a/lib/spack/spack/packages/launchmon/__init__.py b/lib/spack/spack/packages/launchmon/package.py
index e2b82610fd..e2b82610fd 100644
--- a/lib/spack/spack/packages/launchmon/__init__.py
+++ b/lib/spack/spack/packages/launchmon/package.py
diff --git a/lib/spack/spack/packages/libdwarf.py b/lib/spack/spack/packages/libdwarf/package.py
index 657e84705a..657e84705a 100644
--- a/lib/spack/spack/packages/libdwarf.py
+++ b/lib/spack/spack/packages/libdwarf/package.py
diff --git a/lib/spack/spack/packages/libelf.py b/lib/spack/spack/packages/libelf/package.py
index f663ba750d..f663ba750d 100644
--- a/lib/spack/spack/packages/libelf.py
+++ b/lib/spack/spack/packages/libelf/package.py
diff --git a/lib/spack/spack/packages/libunwind.py b/lib/spack/spack/packages/libunwind/package.py
index c93b5b2c98..c93b5b2c98 100644
--- a/lib/spack/spack/packages/libunwind.py
+++ b/lib/spack/spack/packages/libunwind/package.py
diff --git a/lib/spack/spack/packages/mpich.py b/lib/spack/spack/packages/mpich/package.py
index af9e8266dc..af9e8266dc 100644
--- a/lib/spack/spack/packages/mpich.py
+++ b/lib/spack/spack/packages/mpich/package.py
diff --git a/lib/spack/spack/packages/mpileaks.py b/lib/spack/spack/packages/mpileaks/package.py
index 3307b9fdee..3307b9fdee 100644
--- a/lib/spack/spack/packages/mpileaks.py
+++ b/lib/spack/spack/packages/mpileaks/package.py
diff --git a/lib/spack/spack/packages/mrnet.py b/lib/spack/spack/packages/mrnet/package.py
index 15d851f83e..15d851f83e 100644
--- a/lib/spack/spack/packages/mrnet.py
+++ b/lib/spack/spack/packages/mrnet/package.py
diff --git a/lib/spack/spack/packages/mvapich2/__init__.py b/lib/spack/spack/packages/mvapich2/package.py
index f372679f49..f372679f49 100644
--- a/lib/spack/spack/packages/mvapich2/__init__.py
+++ b/lib/spack/spack/packages/mvapich2/package.py
diff --git a/lib/spack/spack/packages/openmpi/__init__.py b/lib/spack/spack/packages/openmpi/package.py
index f24a66c12e..f24a66c12e 100644
--- a/lib/spack/spack/packages/openmpi/__init__.py
+++ b/lib/spack/spack/packages/openmpi/package.py
diff --git a/lib/spack/spack/packages/pmgr_collective.py b/lib/spack/spack/packages/pmgr_collective/package.py
index 0874e2d17b..0874e2d17b 100644
--- a/lib/spack/spack/packages/pmgr_collective.py
+++ b/lib/spack/spack/packages/pmgr_collective/package.py
diff --git a/lib/spack/spack/packages/scr.py b/lib/spack/spack/packages/scr/package.py
index cb908e830e..cb908e830e 100644
--- a/lib/spack/spack/packages/scr.py
+++ b/lib/spack/spack/packages/scr/package.py
diff --git a/lib/spack/spack/packages/spindle.py b/lib/spack/spack/packages/spindle/package.py
index 0d106221d8..0d106221d8 100644
--- a/lib/spack/spack/packages/spindle.py
+++ b/lib/spack/spack/packages/spindle/package.py
diff --git a/lib/spack/spack/packages/stat.py b/lib/spack/spack/packages/stat/package.py
index d621bcef01..d621bcef01 100644
--- a/lib/spack/spack/packages/stat.py
+++ b/lib/spack/spack/packages/stat/package.py
diff --git a/lib/spack/spack/patch.py b/lib/spack/spack/patch.py
index 2638000b27..42d49b15e5 100644
--- a/lib/spack/spack/patch.py
+++ b/lib/spack/spack/patch.py
@@ -30,7 +30,6 @@ from llnl.util.filesystem import join_path
 import spack
 import spack.stage
 import spack.error
-import spack.packages as packages
 
 from spack.util.executable import which
 
@@ -55,7 +54,7 @@ class Patch(object):
         if '://' in path_or_url:
             self.url = path_or_url
         else:
-            pkg_dir = packages.dirname_for_package_name(pkg_name)
+            pkg_dir = spack.db.dirname_for_package_name(pkg_name)
             self.path = join_path(pkg_dir, path_or_url)
             if not os.path.isfile(self.path):
                 raise NoSuchPatchFileError(pkg_name, self.path)
diff --git a/lib/spack/spack/relations.py b/lib/spack/spack/relations.py
index 3950bd1a20..f46b7dfc84 100644
--- a/lib/spack/spack/relations.py
+++ b/lib/spack/spack/relations.py
@@ -80,7 +80,6 @@ import spack.error
 
 from spack.patch import Patch
 from spack.spec import Spec, parse_anonymous_spec
-from spack.packages import packages_module
 
 
 """Adds a dependencies local variable in the locals of
diff --git a/lib/spack/spack/spec.py b/lib/spack/spack/spec.py
index a660e840d0..a4f585b28a 100644
--- a/lib/spack/spack/spec.py
+++ b/lib/spack/spack/spec.py
@@ -99,16 +99,16 @@ import llnl.util.tty as tty
 from llnl.util.lang import *
 from llnl.util.tty.color import *
 
+import spack
 import spack.parse
 import spack.error
 import spack.compilers
 import spack.compilers.gcc
-import spack.packages as packages
 
 from spack.version import *
 from spack.util.string import *
 from spack.util.prefix import Prefix
-
+from spack.virtual import ProviderIndex
 
 # Convenient names for color formats so that other things can use them
 compiler_color         = '@g'
@@ -379,7 +379,7 @@ class Spec(object):
 
     @property
     def package(self):
-        return packages.get(self)
+        return spack.db.get(self)
 
 
     @property
@@ -391,7 +391,7 @@ class Spec(object):
            Possible idea: just use conventin and make virtual deps all
            caps, e.g., MPI vs mpi.
         """
-        return not packages.exists(self.name)
+        return not spack.db.exists(self.name)
 
 
     @property
@@ -532,7 +532,7 @@ class Spec(object):
                 return
 
             for spec in virtuals:
-                providers = packages.providers_for(spec)
+                providers = spack.db.providers_for(spec)
                 concrete = spack.concretizer.choose_provider(spec, providers)
                 concrete = concrete.copy()
                 spec._replace_with(concrete)
@@ -624,7 +624,7 @@ class Spec(object):
 
         # Combine constraints from package dependencies with
         # constraints on the spec's dependencies.
-        pkg = packages.get(self.name)
+        pkg = spack.db.get(self.name)
         for name, pkg_dep in self.package.dependencies.items():
             # If it's a virtual dependency, try to find a provider
             if pkg_dep.virtual:
@@ -653,7 +653,7 @@ class Spec(object):
             else:
                 # if it's a real dependency, check whether it provides something
                 # already required in the spec.
-                index = packages.ProviderIndex([pkg_dep], restrict=True)
+                index = ProviderIndex([pkg_dep], restrict=True)
                 for vspec in (v for v in spec_deps.values() if v.virtual):
                     if index.providers_for(vspec):
                         vspec._replace_with(pkg_dep)
@@ -718,7 +718,7 @@ class Spec(object):
         # 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]
 
-        index = packages.ProviderIndex(spec_deps.values(), restrict=True)
+        index = ProviderIndex(spec_deps.values(), restrict=True)
 
         visited = set()
         self._normalize_helper(visited, spec_deps, index)
@@ -754,7 +754,7 @@ class Spec(object):
         for spec in self.preorder_traversal():
             # Don't get a package for a virtual name.
             if not spec.virtual:
-                packages.get(spec.name)
+                spack.db.get(spec.name)
 
             # validate compiler name in addition to the package name.
             if spec.compiler:
@@ -888,10 +888,8 @@ class Spec(object):
                 return False
 
         # For virtual dependencies, we need to dig a little deeper.
-        self_index = packages.ProviderIndex(
-            self.preorder_traversal(), restrict=True)
-        other_index = packages.ProviderIndex(
-            other.preorder_traversal(), restrict=True)
+        self_index = ProviderIndex(self.preorder_traversal(), restrict=True)
+        other_index = ProviderIndex(other.preorder_traversal(), restrict=True)
 
         # This handles cases where there are already providers for both vpkgs
         if not self_index.satisfies(other_index):
diff --git a/lib/spack/spack/test/__init__.py b/lib/spack/spack/test/__init__.py
index 2aadf40382..271b915479 100644
--- a/lib/spack/spack/test/__init__.py
+++ b/lib/spack/spack/test/__init__.py
@@ -30,6 +30,8 @@ from llnl.util.tty.colify import colify
 
 import spack
 
+import spack.test.install
+
 
 """Names of tests to be included in Spack's test suite"""
 test_names = ['versions',
@@ -40,7 +42,8 @@ test_names = ['versions',
               'spec_semantics',
               'spec_dag',
               'concretize',
-              'multimethod']
+              'multimethod',
+              'install']
 
 
 def list_tests():
diff --git a/lib/spack/spack/test/concretize.py b/lib/spack/spack/test/concretize.py
index 538c13f2cd..62e2732749 100644
--- a/lib/spack/spack/test/concretize.py
+++ b/lib/spack/spack/test/concretize.py
@@ -24,7 +24,7 @@
 ##############################################################################
 import unittest
 
-import spack.packages as packages
+import spack
 from spack.spec import Spec
 from spack.test.mock_packages_test import *
 
@@ -113,22 +113,22 @@ class ConcretizeTest(MockPackagesTest):
            we ask for some advanced version.
         """
         self.assertTrue(not any(spec.satisfies('mpich2@:1.0')
-                                for spec in packages.providers_for('mpi@2.1')))
+                                for spec in spack.db.providers_for('mpi@2.1')))
 
         self.assertTrue(not any(spec.satisfies('mpich2@:1.1')
-                                for spec in packages.providers_for('mpi@2.2')))
+                                for spec in spack.db.providers_for('mpi@2.2')))
 
         self.assertTrue(not any(spec.satisfies('mpich2@:1.1')
-                                for spec in packages.providers_for('mpi@2.2')))
+                                for spec in spack.db.providers_for('mpi@2.2')))
 
         self.assertTrue(not any(spec.satisfies('mpich@:1')
-                                for spec in packages.providers_for('mpi@2')))
+                                for spec in spack.db.providers_for('mpi@2')))
 
         self.assertTrue(not any(spec.satisfies('mpich@:1')
-                                for spec in packages.providers_for('mpi@3')))
+                                for spec in spack.db.providers_for('mpi@3')))
 
         self.assertTrue(not any(spec.satisfies('mpich2')
-                                for spec in packages.providers_for('mpi@3')))
+                                for spec in spack.db.providers_for('mpi@3')))
 
 
     def test_virtual_is_fully_expanded_for_callpath(self):
@@ -162,8 +162,4 @@ class ConcretizeTest(MockPackagesTest):
     def test_my_dep_depends_on_provider_of_my_virtual_dep(self):
         spec = Spec('indirect_mpich')
         spec.normalize()
-
-        print
-        print spec.tree(color=True)
-
         spec.concretize()
diff --git a/lib/spack/spack/test/install.py b/lib/spack/spack/test/install.py
new file mode 100644
index 0000000000..e567f6f9b5
--- /dev/null
+++ b/lib/spack/spack/test/install.py
@@ -0,0 +1,98 @@
+##############################################################################
+# Copyright (c) 2013, 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 shutil
+from contextlib import closing
+
+from llnl.util.filesystem import *
+
+import spack
+from spack.stage import Stage
+from spack.util.executable import which
+from spack.test.mock_packages_test import *
+
+dir_name = 'trivial-1.0'
+archive_name = 'trivial-1.0.tar.gz'
+install_test_package = 'trivial_install_test_package'
+
+class InstallTest(MockPackagesTest):
+    """Tests install and uninstall on a trivial package."""
+
+    def setUp(self):
+        super(InstallTest, self).setUp()
+
+        self.stage = Stage('not_a_real_url')
+        archive_dir = join_path(self.stage.path, dir_name)
+        dummy_configure = join_path(archive_dir, 'configure')
+
+        mkdirp(archive_dir)
+        with closing(open(dummy_configure, 'w')) as configure:
+            configure.write(
+                "#!/bin/sh\n"
+                "prefix=$(echo $1 | sed 's/--prefix=//')\n"
+                "cat > Makefile <<EOF\n"
+                "all:\n"
+                "\techo Building...\n\n"
+                "install:\n"
+                "\tmkdir -p $prefix\n"
+                "\ttouch $prefix/dummy_file\n"
+                "EOF\n")
+        os.chmod(dummy_configure, 0755)
+
+        with working_dir(self.stage.path):
+            tar = which('tar')
+            tar('-czf', archive_name, dir_name)
+
+        # We use a fake pacakge, so skip the checksum.
+        spack.do_checksum = False
+
+    def tearDown(self):
+        super(InstallTest, self).tearDown()
+
+        if self.stage is not None:
+            self.stage.destroy()
+
+        # Turn checksumming back on
+        spack.do_checksum = True
+
+
+    def test_install_and_uninstall(self):
+        # Get a basic concrete spec for the trivial install package.
+        spec = Spec(install_test_package)
+        spec.concretize()
+
+        # Get the package
+        pkg = spack.db.get(spec)
+
+        # Fake some values
+        archive_path = join_path(self.stage.path, archive_name)
+        pkg.url = 'file://' + archive_path
+
+        try:
+            pkg.do_install()
+            pkg.do_uninstall()
+        except:
+            if pkg: pkg.remove_prefix()
+            raise
diff --git a/lib/spack/spack/test/mock_packages/__init__.py b/lib/spack/spack/test/mock_packages/__init__.py
deleted file mode 100644
index 1c388f31c5..0000000000
--- a/lib/spack/spack/test/mock_packages/__init__.py
+++ /dev/null
@@ -1,24 +0,0 @@
-##############################################################################
-# Copyright (c) 2013, 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
-##############################################################################
diff --git a/lib/spack/spack/test/mock_packages/callpath.py b/lib/spack/spack/test/mock_packages/callpath/package.py
index b4fd0f4482..b4fd0f4482 100644
--- a/lib/spack/spack/test/mock_packages/callpath.py
+++ b/lib/spack/spack/test/mock_packages/callpath/package.py
diff --git a/lib/spack/spack/test/mock_packages/direct_mpich.py b/lib/spack/spack/test/mock_packages/direct_mpich/package.py
index d702e4481b..d702e4481b 100644
--- a/lib/spack/spack/test/mock_packages/direct_mpich.py
+++ b/lib/spack/spack/test/mock_packages/direct_mpich/package.py
diff --git a/lib/spack/spack/test/mock_packages/dyninst.py b/lib/spack/spack/test/mock_packages/dyninst/package.py
index d32c4b5504..d32c4b5504 100644
--- a/lib/spack/spack/test/mock_packages/dyninst.py
+++ b/lib/spack/spack/test/mock_packages/dyninst/package.py
diff --git a/lib/spack/spack/test/mock_packages/fake.py b/lib/spack/spack/test/mock_packages/fake/package.py
index 88bc6d8669..88bc6d8669 100644
--- a/lib/spack/spack/test/mock_packages/fake.py
+++ b/lib/spack/spack/test/mock_packages/fake/package.py
diff --git a/lib/spack/spack/test/mock_packages/indirect_mpich.py b/lib/spack/spack/test/mock_packages/indirect_mpich/package.py
index a53cb9330c..a53cb9330c 100644
--- a/lib/spack/spack/test/mock_packages/indirect_mpich.py
+++ b/lib/spack/spack/test/mock_packages/indirect_mpich/package.py
diff --git a/lib/spack/spack/test/mock_packages/libdwarf.py b/lib/spack/spack/test/mock_packages/libdwarf/package.py
index 0f4d55fd88..0f4d55fd88 100644
--- a/lib/spack/spack/test/mock_packages/libdwarf.py
+++ b/lib/spack/spack/test/mock_packages/libdwarf/package.py
diff --git a/lib/spack/spack/test/mock_packages/libelf.py b/lib/spack/spack/test/mock_packages/libelf/package.py
index 5ac07de4e3..5ac07de4e3 100644
--- a/lib/spack/spack/test/mock_packages/libelf.py
+++ b/lib/spack/spack/test/mock_packages/libelf/package.py
diff --git a/lib/spack/spack/test/mock_packages/mpich.py b/lib/spack/spack/test/mock_packages/mpich/package.py
index 2a8e1cebe3..2a8e1cebe3 100644
--- a/lib/spack/spack/test/mock_packages/mpich.py
+++ b/lib/spack/spack/test/mock_packages/mpich/package.py
diff --git a/lib/spack/spack/test/mock_packages/mpich2.py b/lib/spack/spack/test/mock_packages/mpich2/package.py
index 84dce4cccb..84dce4cccb 100644
--- a/lib/spack/spack/test/mock_packages/mpich2.py
+++ b/lib/spack/spack/test/mock_packages/mpich2/package.py
diff --git a/lib/spack/spack/test/mock_packages/mpileaks.py b/lib/spack/spack/test/mock_packages/mpileaks/package.py
index c34d5991e6..c34d5991e6 100644
--- a/lib/spack/spack/test/mock_packages/mpileaks.py
+++ b/lib/spack/spack/test/mock_packages/mpileaks/package.py
diff --git a/lib/spack/spack/test/mock_packages/multimethod.py b/lib/spack/spack/test/mock_packages/multimethod/package.py
index 75b1606ffc..75b1606ffc 100644
--- a/lib/spack/spack/test/mock_packages/multimethod.py
+++ b/lib/spack/spack/test/mock_packages/multimethod/package.py
diff --git a/lib/spack/spack/test/mock_packages/directory-pkg/__init__.py b/lib/spack/spack/test/mock_packages/trivial_install_test_package/package.py
index aa53bb1f36..b665825b32 100644
--- a/lib/spack/spack/test/mock_packages/directory-pkg/__init__.py
+++ b/lib/spack/spack/test/mock_packages/trivial_install_test_package/package.py
@@ -24,16 +24,15 @@
 ##############################################################################
 from spack import *
 
-class DirectoryPkg(Package):
-    """This is a fake package that tests spack's ability to load packages in
-       directories with __init__.py files.
-    """
-    homepage = "http://www.example.com"
-    url      = "http://www.example.com/directory-pkg-1.0.tar.gz"
+class TrivialInstallTestPackage(Package):
+    """This package is a stub with a trivial install method.  It allows us
+       to test the install and uninstall logic of spack."""
+    homepage = "http://www.example.com/trivial_install"
+    url      = "http://www.unit-test-should-replace-this-url/trivial_install-1.0.tar.gz"
 
-    versions = { '1.0' : '0123456789abcdef0123456789abcdef' }
+    versions = { '1.0' : 'foobarbaz' }
 
-    this_is_a_directory_pkg = True
-
-    def install(self):
-        pass
+    def install(self, spec, prefix):
+        configure('--prefix=%s' % prefix)
+        make()
+        make('install')
diff --git a/lib/spack/spack/test/mock_packages/zmpi.py b/lib/spack/spack/test/mock_packages/zmpi/package.py
index a86bd706bb..a86bd706bb 100644
--- a/lib/spack/spack/test/mock_packages/zmpi.py
+++ b/lib/spack/spack/test/mock_packages/zmpi/package.py
diff --git a/lib/spack/spack/test/mock_packages_test.py b/lib/spack/spack/test/mock_packages_test.py
index 69bd120c58..f300995d7e 100644
--- a/lib/spack/spack/test/mock_packages_test.py
+++ b/lib/spack/spack/test/mock_packages_test.py
@@ -28,54 +28,31 @@ from llnl.util.lang import list_modules
 from llnl.util.filesystem import join_path
 
 import spack
-import spack.packages as packages
+from spack.packages import PackageDB
 from spack.spec import Spec
 
 mock_packages_path = join_path(spack.module_path, 'test', 'mock_packages')
-original_deps = None
-
 
 def set_pkg_dep(pkg, spec):
     """Alters dependence information for a pacakge.
        Use this to mock up constraints.
     """
     spec = Spec(spec)
-    packages.get(pkg).dependencies[spec.name] = spec
-
-
-def restore_dependencies():
-    # each time through restore original dependencies & constraints
-    global original_deps
-    for pkg_name, deps in original_deps.iteritems():
-        packages.get(pkg_name).dependencies.clear()
-        for dep in deps:
-            set_pkg_dep(pkg_name, dep)
+    spack.db.get(pkg).dependencies[spec.name] = spec
 
 
 class MockPackagesTest(unittest.TestCase):
     @classmethod
-    def setUpClass(cls):
-        # Use a different packages directory for these tests.  We want to use
-        # mocked up packages that don't interfere with the real ones.
-        cls.real_packages_path = spack.packages_path
-        spack.packages_path = mock_packages_path
-
-        # First time through, record original relationships bt/w packages
-        global original_deps
-        original_deps = {}
-        for name in list_modules(mock_packages_path):
-            pkg = packages.get(name)
-            original_deps[name] = [
-                spec for spec in pkg.dependencies.values()]
+    def setUp(self):
+        # Use the mock packages database for these tests.  This allows
+        # us to set up contrived packages that don't interfere with
+        # real ones.
+        self.real_db = spack.db
+        spack.db = PackageDB(mock_packages_path)
 
 
     @classmethod
-    def tearDownClass(cls):
+    def tearDown(self):
         """Restore the real packages path after any test."""
-        restore_dependencies()
-        spack.packages_path = cls.real_packages_path
-
-
-    def setUp(self):
-        """Before each test, restore deps between packages to original state."""
-        restore_dependencies()
+        #restore_dependencies()
+        spack.db = self.real_db
diff --git a/lib/spack/spack/test/multimethod.py b/lib/spack/spack/test/multimethod.py
index 79b55bf73e..d773113426 100644
--- a/lib/spack/spack/test/multimethod.py
+++ b/lib/spack/spack/test/multimethod.py
@@ -27,7 +27,7 @@ Test for multi_method dispatch.
 """
 import unittest
 
-import spack.packages as packages
+import spack
 from spack.multimethod import *
 from spack.version import *
 from spack.spec import Spec
@@ -38,37 +38,37 @@ from spack.test.mock_packages_test import *
 class MultiMethodTest(MockPackagesTest):
 
     def test_no_version_match(self):
-        pkg = packages.get('multimethod@2.0')
+        pkg = spack.db.get('multimethod@2.0')
         self.assertRaises(NoSuchMethodError, pkg.no_version_2)
 
 
     def test_one_version_match(self):
-        pkg = packages.get('multimethod@1.0')
+        pkg = spack.db.get('multimethod@1.0')
         self.assertEqual(pkg.no_version_2(), 1)
 
-        pkg = packages.get('multimethod@3.0')
+        pkg = spack.db.get('multimethod@3.0')
         self.assertEqual(pkg.no_version_2(), 3)
 
-        pkg = packages.get('multimethod@4.0')
+        pkg = spack.db.get('multimethod@4.0')
         self.assertEqual(pkg.no_version_2(), 4)
 
 
     def test_version_overlap(self):
-        pkg = packages.get('multimethod@2.0')
+        pkg = spack.db.get('multimethod@2.0')
         self.assertEqual(pkg.version_overlap(), 1)
 
-        pkg = packages.get('multimethod@5.0')
+        pkg = spack.db.get('multimethod@5.0')
         self.assertEqual(pkg.version_overlap(), 2)
 
 
     def test_mpi_version(self):
-        pkg = packages.get('multimethod^mpich@3.0.4')
+        pkg = spack.db.get('multimethod^mpich@3.0.4')
         self.assertEqual(pkg.mpi_version(), 3)
 
-        pkg = packages.get('multimethod^mpich2@1.2')
+        pkg = spack.db.get('multimethod^mpich2@1.2')
         self.assertEqual(pkg.mpi_version(), 2)
 
-        pkg = packages.get('multimethod^mpich@1.0')
+        pkg = spack.db.get('multimethod^mpich@1.0')
         self.assertEqual(pkg.mpi_version(), 1)
 
 
@@ -76,54 +76,54 @@ class MultiMethodTest(MockPackagesTest):
         # This currently fails because provides() doesn't do
         # the right thing undefined version ranges.
         # TODO: fix this.
-        pkg = packages.get('multimethod^mpich@0.4')
+        pkg = spack.db.get('multimethod^mpich@0.4')
         self.assertEqual(pkg.mpi_version(), 0)
 
 
     def test_default_works(self):
-        pkg = packages.get('multimethod%gcc')
+        pkg = spack.db.get('multimethod%gcc')
         self.assertEqual(pkg.has_a_default(), 'gcc')
 
-        pkg = packages.get('multimethod%intel')
+        pkg = spack.db.get('multimethod%intel')
         self.assertEqual(pkg.has_a_default(), 'intel')
 
-        pkg = packages.get('multimethod%pgi')
+        pkg = spack.db.get('multimethod%pgi')
         self.assertEqual(pkg.has_a_default(), 'default')
 
 
     def test_architecture_match(self):
-        pkg = packages.get('multimethod=x86_64')
+        pkg = spack.db.get('multimethod=x86_64')
         self.assertEqual(pkg.different_by_architecture(), 'x86_64')
 
-        pkg = packages.get('multimethod=ppc64')
+        pkg = spack.db.get('multimethod=ppc64')
         self.assertEqual(pkg.different_by_architecture(), 'ppc64')
 
-        pkg = packages.get('multimethod=ppc32')
+        pkg = spack.db.get('multimethod=ppc32')
         self.assertEqual(pkg.different_by_architecture(), 'ppc32')
 
-        pkg = packages.get('multimethod=arm64')
+        pkg = spack.db.get('multimethod=arm64')
         self.assertEqual(pkg.different_by_architecture(), 'arm64')
 
-        pkg = packages.get('multimethod=macos')
+        pkg = spack.db.get('multimethod=macos')
         self.assertRaises(NoSuchMethodError, pkg.different_by_architecture)
 
 
     def test_dependency_match(self):
-        pkg = packages.get('multimethod^zmpi')
+        pkg = spack.db.get('multimethod^zmpi')
         self.assertEqual(pkg.different_by_dep(), 'zmpi')
 
-        pkg = packages.get('multimethod^mpich')
+        pkg = spack.db.get('multimethod^mpich')
         self.assertEqual(pkg.different_by_dep(), 'mpich')
 
         # If we try to switch on some entirely different dep, it's ambiguous,
         # but should take the first option
-        pkg = packages.get('multimethod^foobar')
+        pkg = spack.db.get('multimethod^foobar')
         self.assertEqual(pkg.different_by_dep(), 'mpich')
 
 
     def test_virtual_dep_match(self):
-        pkg = packages.get('multimethod^mpich2')
+        pkg = spack.db.get('multimethod^mpich2')
         self.assertEqual(pkg.different_by_virtual_dep(), 2)
 
-        pkg = packages.get('multimethod^mpich@1.0')
+        pkg = spack.db.get('multimethod^mpich@1.0')
         self.assertEqual(pkg.different_by_virtual_dep(), 1)
diff --git a/lib/spack/spack/test/packages.py b/lib/spack/spack/test/packages.py
index 1a1f9c9bf4..e23df23723 100644
--- a/lib/spack/spack/test/packages.py
+++ b/lib/spack/spack/test/packages.py
@@ -25,45 +25,29 @@
 import unittest
 
 from spack.test.mock_packages_test import *
-import spack.packages as packages
+import spack
 
 class PackagesTest(MockPackagesTest):
 
-    def test_load_regular_package(self):
-        pkg = packages.get('mpich')
+    def test_load_package(self):
+        pkg = spack.db.get('mpich')
 
 
-    def test_regular_package_name(self):
-        pkg = packages.get('mpich')
+    def test_package_name(self):
+        pkg = spack.db.get('mpich')
         self.assertEqual(pkg.name, 'mpich')
 
 
-    def test_regular_package_filename(self):
-        filename = packages.filename_for_package_name('mpich')
-        self.assertEqual(filename, join_path(mock_packages_path, 'mpich.py'))
+    def test_package_filename(self):
+        filename = spack.db.filename_for_package_name('mpich')
+        self.assertEqual(filename, join_path(mock_packages_path, 'mpich', 'package.py'))
 
 
-    def test_regular_package_name(self):
-        pkg = packages.get('mpich')
+    def test_package_name(self):
+        pkg = spack.db.get('mpich')
         self.assertEqual(pkg.name, 'mpich')
 
 
-    def test_load_directory_package(self):
-        pkg = packages.get('directory-pkg')
-        self.assertTrue(hasattr(pkg, 'this_is_a_directory_pkg'))
-        self.assertTrue(pkg.this_is_a_directory_pkg)
-
-
-    def test_directory_package_name(self):
-        pkg = packages.get('directory-pkg')
-        self.assertEqual(pkg.name, 'directory-pkg')
-
-
-    def test_directory_package_filename(self):
-        filename = packages.filename_for_package_name('directory-pkg')
-        self.assertEqual(filename, join_path(mock_packages_path, 'directory-pkg/__init__.py'))
-
-
     def test_nonexisting_package_filename(self):
-        filename = packages.filename_for_package_name('some-nonexisting-package')
-        self.assertEqual(filename, join_path(mock_packages_path, 'some-nonexisting-package.py'))
+        filename = spack.db.filename_for_package_name('some-nonexisting-package')
+        self.assertEqual(filename, join_path(mock_packages_path, 'some-nonexisting-package', 'package.py'))
diff --git a/lib/spack/spack/test/spec_dag.py b/lib/spack/spack/test/spec_dag.py
index d03d146310..0c0b214ab7 100644
--- a/lib/spack/spack/test/spec_dag.py
+++ b/lib/spack/spack/test/spec_dag.py
@@ -30,7 +30,6 @@ You can find the dummy packages here::
 """
 import spack
 import spack.package
-import spack.packages as packages
 
 from llnl.util.lang import list_modules
 
diff --git a/lib/spack/spack/virtual.py b/lib/spack/spack/virtual.py
new file mode 100644
index 0000000000..960212eba9
--- /dev/null
+++ b/lib/spack/spack/virtual.py
@@ -0,0 +1,142 @@
+##############################################################################
+# Copyright (c) 2013, 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
+##############################################################################
+"""
+The ``virtual`` module contains utility classes for virtual dependencies.
+"""
+import spack.spec
+
+class ProviderIndex(object):
+    """This is a dict of dicts used for finding providers of particular
+       virtual dependencies. The dict of dicts looks like:
+
+       { vpkg name :
+           { full vpkg spec : package providing spec } }
+
+       Callers can use this to first find which packages provide a vpkg,
+       then find a matching full spec.  e.g., in this scenario:
+
+       { 'mpi' :
+           { mpi@:1.1 : mpich,
+             mpi@:2.3 : mpich2@1.9: } }
+
+       Calling providers_for(spec) will find specs that provide a
+       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)
+        self.restrict = kwargs.setdefault('restrict', False)
+
+        self.providers = {}
+
+        for spec in specs:
+            if not isinstance(spec, spack.spec.Spec):
+                spec = spack.spec.Spec(spec)
+
+            if spec.virtual:
+                continue
+
+            self.update(spec)
+
+
+    def update(self, spec):
+        if type(spec) != spack.spec.Spec:
+            spec = spack.spec.Spec(spec)
+
+        assert(not spec.virtual)
+
+        pkg = spec.package
+        for provided_spec, provider_spec in pkg.provided.iteritems():
+            if provider_spec.satisfies(spec, deps=False):
+                provided_name = provided_spec.name
+                if provided_name not in self.providers:
+                    self.providers[provided_name] = {}
+
+                if self.restrict:
+                    self.providers[provided_name][provided_spec] = spec
+
+                else:
+                    # Before putting the spec in the map, constrain it so that
+                    # it provides what was asked for.
+                    constrained = spec.copy()
+                    constrained.constrain(provider_spec)
+                    self.providers[provided_name][provided_spec] = constrained
+
+
+    def providers_for(self, *vpkg_specs):
+        """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
+            if type(vspec) == str:
+                vspec = spack.spec.Spec(vspec)
+
+            # 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, 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], 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) & set(other.providers)
+        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)