Checkpoint commit: much-improved spec class.

Still organizing things.

26 files changed, 1403 insertions, 361 deletions

diff --git a/lib/spack/spack/cmd/clean.py b/lib/spack/spack/cmd/clean.py
index d827768e6e..52eaf2893f 100644
--- a/lib/spack/spack/cmd/clean.py
+++ b/lib/spack/spack/cmd/clean.py
@@ -14,7 +14,8 @@ def setup_parser(subparser):
                            help="delete and re-expand the entire stage directory")
     subparser.add_argument('-d', "--dist", action="store_true", dest='dist',
                            help="delete the downloaded archive.")
-    subparser.add_argument('packages', nargs=argparse.REMAINDER, help="specs of packages to clean")
+    subparser.add_argument('packages', nargs=argparse.REMAINDER,
+                           help="specs of packages to clean")
 
 
 def clean(parser, args):
diff --git a/lib/spack/spack/cmd/compilers.py b/lib/spack/spack/cmd/compilers.py
new file mode 100644
index 0000000000..50457550d3
--- /dev/null
+++ b/lib/spack/spack/cmd/compilers.py
@@ -0,0 +1,9 @@
+import spack.compilers
+import spack.tty as tty
+from spack.colify import colify
+
+description = "List available compilers"
+
+def compilers(parser, args):
+    tty.msg("Supported compilers")
+    colify(spack.compilers.supported_compilers(), indent=4)
diff --git a/lib/spack/spack/cmd/create.py b/lib/spack/spack/cmd/create.py
index e0d087bb9d..79cd9c6b17 100644
--- a/lib/spack/spack/cmd/create.py
+++ b/lib/spack/spack/cmd/create.py
@@ -57,13 +57,13 @@ def create(parser, args):
 
     # make a stage and fetch the archive.
     try:
-        stage = Stage("%s-%s" % (name, version), url)
+        stage = Stage("spack-create/%s-%s" % (name, version), url)
         archive_file = stage.fetch()
     except spack.FailedDownloadException, e:
         tty.die(e.message)
 
     md5 = spack.md5(archive_file)
-    class_name = packages.class_for(name)
+    class_name = packages.class_name_for_package_name(name)
 
     # Write outa template for the file
     tty.msg("Editing %s." % path)
diff --git a/lib/spack/spack/cmd/list.py b/lib/spack/spack/cmd/list.py
index 49ba7a113d..89ea5d82d8 100644
--- a/lib/spack/spack/cmd/list.py
+++ b/lib/spack/spack/cmd/list.py
@@ -9,53 +9,15 @@ from spack.colify import colify
 import spack.url as url
 import spack.tty as tty
 
-
 description ="List spack packages"
 
 def setup_parser(subparser):
-    subparser.add_argument('-v', '--versions', metavar="PACKAGE", dest='version_package',
-                           help='List available versions of a package (experimental).')
     subparser.add_argument('-i', '--installed', action='store_true', dest='installed',
                            help='List installed packages for each platform along with versions.')
 
 
 def list(parser, args):
     if args.installed:
-        pkgs = packages.installed_packages()
-        for sys_type in pkgs:
-            print "%s:" % sys_type
-            package_vers = []
-            for pkg in pkgs[sys_type]:
-                pv = [pkg.name + "@" + v for v in pkg.installed_versions]
-                package_vers.extend(pv)
-            colify(sorted(package_vers), indent=4)
-
-    elif args.version_package:
-        pkg = packages.get(args.version_package)
-
-        # Run curl but grab the mime type from the http headers
-        try:
-            listing = spack.curl('-s', '-L', pkg.list_url, return_output=True)
-        except CalledProcessError:
-            tty.die("Fetching %s failed." % pkg.list_url,
-                    "'list -v' requires an internet connection.")
-
-        url_regex = os.path.basename(url.wildcard_version(pkg.url))
-        strings = re.findall(url_regex, listing)
-
-        versions = []
-        wildcard = pkg.version.wildcard()
-        for s in strings:
-            match = re.search(wildcard, s)
-            if match:
-                versions.append(ver(match.group(0)))
-
-        if not versions:
-            tty.die("Found no versions for %s" % pkg.name,
-                    "Listing versions is experimental.  You may need to add the list_url",
-                    "attribute to the package to tell Spack where to look for versions.")
-
-        colify(str(v) for v in reversed(sorted(set(versions))))
-
+        colify(str(pkg) for pkg in packages.installed_packages())
     else:
         colify(packages.all_package_names())
diff --git a/lib/spack/spack/cmd/spec.py b/lib/spack/spack/cmd/spec.py
new file mode 100644
index 0000000000..5c389bd04a
--- /dev/null
+++ b/lib/spack/spack/cmd/spec.py
@@ -0,0 +1,17 @@
+import argparse
+import spack.cmd
+
+import spack.tty as tty
+import spack
+
+description = "parse specs and print them out to the command line."
+
+def setup_parser(subparser):
+    subparser.add_argument('specs', nargs=argparse.REMAINDER, help="specs of packages")
+
+def spec(parser, args):
+    specs = spack.cmd.parse_specs(args.specs)
+    for spec in specs:
+        print spec.colorized()
+        print "  --> ", spec.concretized().colorized()
+        print spec.concretized().concrete()
diff --git a/lib/spack/spack/cmd/versions.py b/lib/spack/spack/cmd/versions.py
new file mode 100644
index 0000000000..9d0b1df55a
--- /dev/null
+++ b/lib/spack/spack/cmd/versions.py
@@ -0,0 +1,20 @@
+import os
+import re
+from subprocess import CalledProcessError
+
+import spack
+import spack.packages as packages
+import spack.url as url
+import spack.tty as tty
+from spack.colify import colify
+from spack.version import ver
+
+description ="List available versions of a package"
+
+def setup_parser(subparser):
+    subparser.add_argument('package', metavar='PACKAGE', help='Package to list versions for')
+
+
+def versions(parser, args):
+    pkg = packages.get(args.package)
+    colify(reversed(pkg.available_versions))
diff --git a/lib/spack/spack/colify.py b/lib/spack/spack/colify.py
index 0016b708b6..0ab2159197 100644
--- a/lib/spack/spack/colify.py
+++ b/lib/spack/spack/colify.py
@@ -94,9 +94,10 @@ def colify(elts, **options):
     indent       = options.get("indent", 0)
     padding      = options.get("padding", 2)
 
-    # elts needs to be in an array so we can count the elements
-    if not type(elts) == list:
-        elts = list(elts)
+    # elts needs to be an array of strings so we can count the elements
+    elts = [str(elt) for elt in elts]
+    if not elts:
+        return
 
     if not output.isatty():
         for elt in elts:
diff --git a/lib/spack/spack/color.py b/lib/spack/spack/color.py
index f84ba626c3..b426c3eaa1 100644
--- a/lib/spack/spack/color.py
+++ b/lib/spack/spack/color.py
@@ -97,9 +97,11 @@ class match_to_ansi(object):
         elif m == '@.':
             return self.escape(0)
         elif m == '@' or (style and not color):
-            raise ColorParseError("Incomplete color format: '%s'" % m)
+            raise ColorParseError("Incomplete color format: '%s' in %s"
+                                  % (m, match.string))
         elif color not in colors:
-            raise ColorParseError("invalid color specifier: '%s'" % color)
+            raise ColorParseError("invalid color specifier: '%s' in '%s'"
+                                  % (color, match.string))
 
         colored_text = ''
         if text:
@@ -141,6 +143,10 @@ def cprint(string, stream=sys.stdout, color=None):
     """Same as cwrite, but writes a trailing newline to the stream."""
     cwrite(string + "\n", stream, color)
 
+def cescape(string):
+    """Replace all @ with @@ in the string provided."""
+    return str(string).replace('@', '@@')
+
 
 class ColorStream(object):
     def __init__(self, stream, color=None):
diff --git a/lib/spack/spack/compilers/__init__.py b/lib/spack/spack/compilers/__init__.py
new file mode 100644
index 0000000000..04e084b6ed
--- /dev/null
+++ b/lib/spack/spack/compilers/__init__.py
@@ -0,0 +1,16 @@
+#
+# This needs to be expanded for full compiler support.
+#
+
+import spack
+import spack.compilers.gcc
+from spack.utils import list_modules, memoized
+
+
+@memoized
+def supported_compilers():
+    return [c for c in list_modules(spack.compilers_path)]
+
+
+def get_compiler():
+    return Compiler('gcc', spack.compilers.gcc.get_version())
diff --git a/lib/spack/spack/compilers/gcc.py b/lib/spack/spack/compilers/gcc.py
new file mode 100644
index 0000000000..fa9da36be7
--- /dev/null
+++ b/lib/spack/spack/compilers/gcc.py
@@ -0,0 +1,15 @@
+#
+# This is a stub module.  It should be expanded when we implement full
+# compiler support.
+#
+
+import subprocess
+from spack.version import Version
+
+cc = 'gcc'
+cxx = 'g++'
+fortran = 'gfortran'
+
+def get_version():
+    v = subprocess.check_output([cc, '-dumpversion'])
+    return Version(v)
diff --git a/lib/spack/spack/compilers/intel.py b/lib/spack/spack/compilers/intel.py
new file mode 100644
index 0000000000..7fa8efb654
--- /dev/null
+++ b/lib/spack/spack/compilers/intel.py
@@ -0,0 +1,15 @@
+#
+# This is a stub module.  It should be expanded when we implement full
+# compiler support.
+#
+
+import subprocess
+from spack.version import Version
+
+cc = 'icc'
+cxx = 'icc'
+fortran = 'ifort'
+
+def get_version():
+    v = subprocess.check_output([cc, '-dumpversion'])
+    return Version(v)
diff --git a/lib/spack/spack/dependency.py b/lib/spack/spack/dependency.py
deleted file mode 100644
index 7b8517b035..0000000000
--- a/lib/spack/spack/dependency.py
+++ /dev/null
@@ -1,20 +0,0 @@
-"""
-This file defines the dependence relation in spack.
-
-"""
-
-import packages
-
-
-class Dependency(object):
-    """Represents a dependency from one package to another.
-    """
-    def __init__(self, name):
-        self.name = name
-
-    @property
-    def package(self):
-        return packages.get(self.name)
-
-    def __str__(self):
-        return "<dep: %s>" % self.name
diff --git a/lib/spack/spack/directory_layout.py b/lib/spack/spack/directory_layout.py
new file mode 100644
index 0000000000..55abb6d4b5
--- /dev/null
+++ b/lib/spack/spack/directory_layout.py
@@ -0,0 +1,98 @@
+import exceptions
+import re
+import os
+
+import spack.spec as spec
+from spack.utils import *
+from spack.error import SpackError
+
+
+class DirectoryLayout(object):
+    """A directory layout is used to associate unique paths with specs.
+       Different installations are going to want differnet layouts for their
+       install, and they can use this to customize the nesting structure of
+       spack installs.
+    """
+    def __init__(self, root):
+        self.root = root
+
+
+    def all_specs(self):
+        """To be implemented by subclasses to traverse all specs for which there is
+           a directory within the root.
+        """
+        raise NotImplementedError()
+
+
+    def relative_path_for_spec(self, spec):
+        """Implemented by subclasses to return a relative path from the install
+           root to a unique location for the provided spec."""
+        raise NotImplementedError()
+
+
+    def path_for_spec(self, spec):
+        """Return an absolute path from the root to a directory for the spec."""
+        if not spec.concrete:
+            raise ValueError("path_for_spec requires a concrete spec.")
+
+        path = self.relative_path_for_spec(spec)
+        assert(not path.startswith(self.root))
+        return os.path.join(self.root, path)
+
+
+    def remove_path_for_spec(self, spec):
+        """Removes a prefix and any empty parent directories from the root."""
+        path = self.path_for_spec(spec)
+        assert(path.startswith(self.root))
+
+        if os.path.exists(path):
+            shutil.rmtree(path, True)
+
+        path = os.path.dirname(path)
+        while not os.listdir(path) and path != self.root:
+            os.rmdir(path)
+            path = os.path.dirname(path)
+
+
+def traverse_dirs_at_depth(root, depth, path_tuple=(), curdepth=0):
+    """For each directory at <depth> within <root>, return a tuple representing
+       the ancestors of that directory.
+    """
+    if curdepth == depth and curdepth != 0:
+        yield path_tuple
+    elif depth > curdepth:
+        for filename in os.listdir(root):
+            child = os.path.join(root, filename)
+            if os.path.isdir(child):
+                child_tuple = path_tuple + (filename,)
+                for tup in traverse_dirs_at_depth(
+                        child, depth, child_tuple, curdepth+1):
+                    yield tup
+
+
+class DefaultDirectoryLayout(DirectoryLayout):
+    def __init__(self, root):
+        super(DefaultDirectoryLayout, self).__init__(root)
+
+
+    def relative_path_for_spec(self, spec):
+        if not spec.concrete:
+            raise ValueError("relative_path_for_spec requires a concrete spec.")
+
+        return new_path(
+            spec.architecture,
+            spec.compiler,
+            "%s@%s%s%s" % (spec.name,
+                           spec.version,
+                           spec.variants,
+                           spec.dependencies))
+
+
+    def all_specs(self):
+        if not os.path.isdir(self.root):
+            return
+
+        for path in traverse_dirs_at_depth(self.root, 3):
+            arch, compiler, last_dir = path
+            spec_str = "%s%%%s=%s" % (last_dir, compiler, arch)
+            yield spec.parse(spec_str)
diff --git a/lib/spack/spack/globals.py b/lib/spack/spack/globals.py
index 34b9be5713..2001f4dacd 100644
--- a/lib/spack/spack/globals.py
+++ b/lib/spack/spack/globals.py
@@ -2,6 +2,7 @@ import os
 from version import Version
 from utils import *
 import arch
+from directory_layout import DefaultDirectoryLayout
 
 # This lives in $prefix/lib/spac/spack/__file__
 prefix = ancestor(__file__, 4)
@@ -10,16 +11,23 @@ prefix = ancestor(__file__, 4)
 spack_file = new_path(prefix, "bin", "spack")
 
 # spack directory hierarchy
-lib_path      = new_path(prefix, "lib", "spack")
-env_path      = new_path(lib_path, "env")
-module_path   = new_path(lib_path, "spack")
-packages_path = new_path(module_path, "packages")
-test_path     = new_path(module_path, "test")
+lib_path       = new_path(prefix, "lib", "spack")
+env_path       = new_path(lib_path, "env")
+module_path    = new_path(lib_path, "spack")
+packages_path  = new_path(module_path, "packages")
+compilers_path = new_path(module_path, "compilers")
+test_path      = new_path(module_path, "test")
 
-var_path      = new_path(prefix, "var", "spack")
-stage_path    = new_path(var_path, "stage")
+var_path       = new_path(prefix, "var", "spack")
+stage_path     = new_path(var_path, "stage")
 
-install_path  = new_path(prefix, "opt")
+install_path   = new_path(prefix, "opt")
+
+#
+# This controls how spack lays out install prefixes and
+# stage directories.
+#
+install_layout = DefaultDirectoryLayout(install_path)
 
 # Version information
 spack_version = Version("0.2")
diff --git a/lib/spack/spack/multi_function.py b/lib/spack/spack/multi_function.py
index 7d21b02f80..abceb156c0 100644
--- a/lib/spack/spack/multi_function.py
+++ b/lib/spack/spack/multi_function.py
@@ -61,6 +61,7 @@ class PlatformMultiFunction(object):
            If none is found, call the default function that this was
            initialized with.  If there is no default, raise an error.
         """
+        # TODO: make this work with specs.
         sys_type = package_self.sys_type
         function = self.function_map.get(sys_type, self.default)
         if function:
diff --git a/lib/spack/spack/none_compare.py b/lib/spack/spack/none_compare.py
new file mode 100644
index 0000000000..67a00b8a40
--- /dev/null
+++ b/lib/spack/spack/none_compare.py
@@ -0,0 +1,60 @@
+"""
+Functions for comparing values that may potentially be None.
+Functions prefixed with 'none_low_' treat None as less than all other values.
+Functions prefixed with 'none_high_' treat None as greater than all other values.
+"""
+
+def none_low_lt(lhs, rhs):
+    """Less-than comparison.  None is lower than any value."""
+    return lhs != rhs and (lhs == None or (rhs != None and lhs < rhs))
+
+
+def none_low_le(lhs, rhs):
+    """Less-than-or-equal comparison.  None is less than any value."""
+    return lhs == rhs or none_low_lt(lhs, rhs)
+
+
+def none_low_gt(lhs, rhs):
+    """Greater-than comparison.  None is less than any value."""
+    return lhs != rhs and not none_low_lt(lhs, rhs)
+
+
+def none_low_ge(lhs, rhs):
+    """Greater-than-or-equal comparison.  None is less than any value."""
+    return lhs == rhs or none_low_gt(lhs, rhs)
+
+
+def none_low_min(lhs, rhs):
+    """Minimum function where None is less than any value."""
+    if lhs == None or rhs == None:
+        return None
+    else:
+        return min(lhs, rhs)
+
+
+def none_high_lt(lhs, rhs):
+    """Less-than comparison.  None is greater than any value."""
+    return lhs != rhs and (rhs == None or (lhs != None and lhs < rhs))
+
+
+def none_high_le(lhs, rhs):
+    """Less-than-or-equal comparison.  None is greater than any value."""
+    return lhs == rhs or none_high_lt(lhs, rhs)
+
+
+def none_high_gt(lhs, rhs):
+    """Greater-than comparison.  None is greater than any value."""
+    return lhs != rhs and not none_high_lt(lhs, rhs)
+
+
+def none_high_ge(lhs, rhs):
+    """Greater-than-or-equal comparison.  None is greater than any value."""
+    return lhs == rhs or none_high_gt(lhs, rhs)
+
+
+def none_high_max(lhs, rhs):
+    """Maximum function where None is greater than any value."""
+    if lhs == None or rhs == None:
+        return None
+    else:
+        return max(lhs, rhs)
diff --git a/lib/spack/spack/package.py b/lib/spack/spack/package.py
index dbe54fa765..0611d005db 100644
--- a/lib/spack/spack/package.py
+++ b/lib/spack/spack/package.py
@@ -9,7 +9,6 @@ Homebrew makes it very easy to create packages.  For a complete
 rundown on spack and how it differs from homebrew, look at the
 README.
 """
-import sys
 import inspect
 import os
 import re
@@ -18,18 +17,18 @@ import platform as py_platform
 import shutil
 
 from spack import *
+import spack.spec
 import packages
 import tty
 import attr
 import validate
 import url
-import arch
+
 
 from spec import Compiler
-from version import Version
+from version import *
 from multi_function import platform
 from stage import Stage
-from dependency import *
 
 
 class Package(object):
@@ -106,6 +105,21 @@ class Package(object):
         install()  This function tells spack how to build and install the
                    software it downloaded.
 
+    Optional Attributes
+    ---------------------
+    You can also optionally add these attributes, if needed:
+        list_url
+            Webpage to scrape for available version strings. Default is the
+            directory containing the tarball; use this if the default isn't
+            correct so that invoking 'spack versions' will work for this
+            package.
+
+        url_version(self, version)
+            When spack downloads packages at particular versions, it just
+            converts version to string with str(version).  Override this if
+            your package needs special version formatting in its URL.  boost
+            is an example of a package that needs this.
+
     Creating Packages
     ===================
     As a package creator, you can probably ignore most of the preceding
@@ -209,7 +223,7 @@ class Package(object):
 
     A package's lifecycle over a run of Spack looks something like this:
 
-        packge p = new Package()  # Done for you by spack
+        p = Package()             # Done for you by spack
 
         p.do_fetch()              # called by spack commands in spack/cmd.
         p.do_stage()              # see spack.stage.Stage docs.
@@ -231,9 +245,15 @@ class Package(object):
     clean() (some of them do this), and others to provide custom behavior.
     """
 
+    #
+    # These variables are per-package metadata will be defined by subclasses.
+    #
     """By default a package has no dependencies."""
     dependencies = []
 
+    #
+    # These are default values for instance variables.
+    #
     """By default we build in parallel.  Subclasses can override this."""
     parallel = True
 
@@ -243,19 +263,14 @@ class Package(object):
     """Controls whether install and uninstall check deps before running."""
     ignore_dependencies = False
 
-    # TODO: multi-compiler support
-    """Default compiler for this package"""
-    compiler = Compiler('gcc')
-
-
-    def __init__(self, sys_type = arch.sys_type()):
-        # Check for attributes that derived classes must set.
+    def __init__(self, spec):
+        # These attributes are required for all packages.
         attr.required(self, 'homepage')
         attr.required(self, 'url')
         attr.required(self, 'md5')
 
-        # Architecture for this package.
-        self.sys_type = sys_type
+        # this determines how the package should be built.
+        self.spec = spec
 
         # Name of package is the name of its module (the file that contains it)
         self.name = inspect.getmodulename(self.module.__file__)
@@ -277,16 +292,16 @@ class Package(object):
         elif type(self.version) == string:
             self.version = Version(self.version)
 
-        # This adds a bunch of convenience commands to the package's module scope.
-        self.add_commands_to_module()
-
-        # Empty at first; only compute dependents if necessary
+        # Empty at first; only compute dependent packages if necessary
         self._dependents = None
 
+        # This is set by scraping a web page.
+        self._available_versions = None
+
         # stage used to build this package.
-        self.stage = Stage(self.stage_name, self.url)
+        self.stage = Stage("%s-%s" % (self.name, self.version), self.url)
 
-        # Set a default list URL (place to find lots of versions)
+        # Set a default list URL (place to find available versions)
         if not hasattr(self, 'list_url'):
             self.list_url = os.path.dirname(self.url)
 
@@ -356,6 +371,24 @@ class Package(object):
         return tuple(self._dependents)
 
 
+    def sanity_check(self):
+        """Ensure that this package and its dependencies don't have conflicting
+           requirements."""
+        deps = sorted(self.all_dependencies, key=lambda d: d.name)
+
+
+
+    @property
+    @memoized
+    def all_dependencies(self):
+        """Set of all transitive dependencies of this package."""
+        all_deps = set(self.dependencies)
+        for dep in self.dependencies:
+            dep_pkg = packages.get(dep.name)
+            all_deps = all_deps.union(dep_pkg.all_dependencies)
+        return all_deps
+
+
     @property
     def installed(self):
         return os.path.exists(self.prefix)
@@ -380,34 +413,9 @@ class Package(object):
 
 
     @property
-    def stage_name(self):
-        return "%s-%s" % (self.name, self.version)
-
-    #
-    # Below properties determine the path where this package is installed.
-    #
-    @property
-    def platform_path(self):
-        """Directory for binaries for the current platform."""
-        return new_path(install_path, self.sys_type)
-
-
-    @property
-    def package_path(self):
-        """Directory for different versions of this package.  Lives just above prefix."""
-        return new_path(self.platform_path, self.name)
-
-
-    @property
-    def installed_versions(self):
-        return [ver for ver in os.listdir(self.package_path)
-                if os.path.isdir(new_path(self.package_path, ver))]
-
-
-    @property
     def prefix(self):
-        """Packages are installed in $spack_prefix/opt/<sys_type>/<name>/<version>"""
-        return new_path(self.package_path, self.version)
+        """Get the prefix into which this package should be installed."""
+        return spack.install_layout.path_for_spec(self.spec)
 
 
     def url_version(self, version):
@@ -417,24 +425,14 @@ class Package(object):
            override this, e.g. for boost versions where you need to ensure that there
            are _'s in the download URL.
         """
-        return version.string
+        return str(version)
 
 
     def remove_prefix(self):
         """Removes the prefix for a package along with any empty parent directories."""
         if self.dirty:
             return
-
-        if os.path.exists(self.prefix):
-            shutil.rmtree(self.prefix, True)
-
-        for dir in (self.package_path, self.platform_path):
-            if not os.path.isdir(dir):
-                continue
-            if not os.listdir(dir):
-                os.rmdir(dir)
-            else:
-                break
+        spack.install_layout.remove_path_for_spec(self.spec)
 
 
     def do_fetch(self):
@@ -469,6 +467,9 @@ class Package(object):
         """This class should call this version of the install method.
            Package implementations should override install().
         """
+        if not self.spec.concrete:
+            raise ValueError("Can only install concrete packages.")
+
         if os.path.exists(self.prefix):
             tty.msg("%s is already installed." % self.name)
             tty.pkg(self.prefix)
@@ -480,6 +481,10 @@ class Package(object):
         self.do_stage()
         self.setup_install_environment()
 
+        # Add convenience commands to the package's module scope to
+        # make building easier.
+        self.add_commands_to_module()
+
         tty.msg("Building %s." % self.name)
         try:
             self.install(self.prefix)
@@ -599,6 +604,34 @@ class Package(object):
         tty.msg("Successfully cleaned %s" % self.name)
 
 
+    @property
+    def available_versions(self):
+        if not self._available_versions:
+            self._available_versions = VersionList()
+            try:
+                # Run curl but grab the mime type from the http headers
+                listing = spack.curl('-s', '-L', self.list_url, return_output=True)
+                url_regex = os.path.basename(url.wildcard_version(self.url))
+                strings = re.findall(url_regex, listing)
+                wildcard = self.version.wildcard()
+                for s in strings:
+                    match = re.search(wildcard, s)
+                    if match:
+                        self._available_versions.add(ver(match.group(0)))
+
+            except CalledProcessError:
+                tty.warn("Fetching %s failed." % self.list_url,
+                         "Package.available_versions requires an internet connection.",
+                         "Version list may be incomplete.")
+
+            if not self._available_versions:
+                tty.warn("Found no versions for %s" % self.name,
+                         "Packate.available_versions may require adding the list_url attribute",
+                         "to the package to tell Spack where to look for versions.")
+                self._available_versions = [self.version]
+        return self._available_versions
+
+
 class MakeExecutable(Executable):
     """Special Executable for make so the user can specify parallel or
        not on a per-invocation basis.  Using 'parallel' as a kwarg will
diff --git a/lib/spack/spack/packages/__init__.py b/lib/spack/spack/packages/__init__.py
index 16cf556621..f189e4c3bc 100644
--- a/lib/spack/spack/packages/__init__.py
+++ b/lib/spack/spack/packages/__init__.py
@@ -7,68 +7,51 @@ import glob
 
 import spack
 import spack.error
+import spack.spec
 from spack.utils import *
 import spack.arch as arch
 
-
-# Valid package names -- can contain - but can't start with it.
-valid_package = r'^\w[\w-]*$'
+# Valid package names can contain '-' but can't start with it.
+valid_package_re = r'^\w[\w-]*$'
 
 # Don't allow consecutive [_-] in package names
-invalid_package = r'[_-][_-]+'
+invalid_package_re = r'[_-][_-]+'
 
 instances = {}
 
+def get(spec):
+    spec = spack.spec.make_spec(spec)
+    if not spec in instances:
+        package_class = get_class_for_package_name(spec.name)
+        instances[spec] = package_class(spec)
 
-def get(pkg, arch=arch.sys_type()):
-    key = (pkg, arch)
-    if not key in instances:
-        package_class = get_class(pkg)
-        instances[key] = package_class(arch)
-    return instances[key]
-
-
-class InvalidPackageNameError(spack.error.SpackError):
-    """Raised when we encounter a bad package name."""
-    def __init__(self, name):
-        super(InvalidPackageNameError, self).__init__(
-            "Invalid package name: " + name)
-        self.name = name
+    return instances[spec]
 
 
-def valid_name(pkg):
-    return re.match(valid_package, pkg) and not re.search(invalid_package, pkg)
+def valid_package_name(pkg_name):
+    return (re.match(valid_package_re, pkg_name) and
+            not re.search(invalid_package_re, pkg_name))
 
 
-def validate_name(pkg):
-    if not valid_name(pkg):
-        raise InvalidPackageNameError(pkg)
+def validate_package_name(pkg_name):
+    if not valid_package_name(pkg_name):
+        raise InvalidPackageNameError(pkg_name)
 
 
-def filename_for(pkg):
+def filename_for_package_name(pkg_name):
     """Get the filename where a package name should be stored."""
-    validate_name(pkg)
-    return new_path(spack.packages_path, "%s.py" % pkg)
+    validate_package_name(pkg_name)
+    return new_path(spack.packages_path, "%s.py" % pkg_name)
 
 
-def installed_packages(**kwargs):
-    """Returns a dict from systype strings to lists of Package objects."""
-    pkgs = {}
-    if not os.path.isdir(spack.install_path):
-        return pkgs
-
-    for sys_type in os.listdir(spack.install_path):
-        sys_type = sys_type
-        sys_path = new_path(spack.install_path, sys_type)
-        pkgs[sys_type] = [get(pkg) for pkg in os.listdir(sys_path)
-                          if os.path.isdir(new_path(sys_path, pkg))]
-    return pkgs
+def installed_packages():
+    return spack.install_layout.all_specs()
 
 
 def all_package_names():
     """Generator function for all packages."""
-    for mod in list_modules(spack.packages_path):
-        yield mod
+    for module in list_modules(spack.packages_path):
+        yield module
 
 
 def all_packages():
@@ -76,12 +59,12 @@ def all_packages():
         yield get(name)
 
 
-def class_for(pkg):
+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_name(pkg)
-    class_name = string.capwords(pkg.replace('_', '-'), '-')
+    validate_package_name(pkg_name)
+    class_name = string.capwords(pkg_name.replace('_', '-'), '-')
 
     # If a class starts with a number, prefix it with Number_ to make it a valid
     # Python class name.
@@ -91,25 +74,27 @@ def class_for(pkg):
     return class_name
 
 
-def get_class(pkg):
-    file = filename_for(pkg)
+def get_class_for_package_name(pkg_name):
+    file_name = filename_for_package_name(pkg_name)
 
-    if os.path.exists(file):
-        if not os.path.isfile(file):
-            tty.die("Something's wrong. '%s' is not a file!" % file)
-        if not os.access(file, os.R_OK):
-            tty.die("Cannot read '%s'!" % file)
+    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)
 
-    class_name = pkg.capitalize()
+    class_name = pkg_name.capitalize()
     try:
-        module_name = "%s.%s" % (__name__, pkg)
+        module_name = "%s.%s" % (__name__, pkg_name)
         module = __import__(module_name, fromlist=[class_name])
     except ImportError, e:
-        tty.die("Error while importing %s.%s:\n%s" % (pkg, class_name, e.message))
+        tty.die("Error while importing %s.%s:\n%s" % (pkg_name, class_name, e.message))
 
     klass = getattr(module, class_name)
     if not inspect.isclass(klass):
-        tty.die("%s.%s is not a class" % (pkg, class_name))
+        tty.die("%s.%s is not a class" % (pkg_name, class_name))
 
     return klass
 
@@ -152,3 +137,19 @@ def graph_dependencies(out=sys.stdout):
     for pair in deps:
         out.write('  "%s" -> "%s"\n' % pair)
     out.write('}\n')
+
+
+
+class InvalidPackageNameError(spack.error.SpackError):
+    """Raised when we encounter a bad package name."""
+    def __init__(self, name):
+        super(InvalidPackageNameError, self).__init__(
+            "Invalid package name: " + name)
+        self.name = name
+
+
+class UnknownPackageError(spack.error.SpackError):
+    """Raised when we encounter a package spack doesn't have."""
+    def __init__(self, name):
+        super(UnknownPackageError, self).__init__("Package %s not found." % name)
+        self.name = name
diff --git a/lib/spack/spack/relations.py b/lib/spack/spack/relations.py
index 0442314e5e..8eb4e2d1a2 100644
--- a/lib/spack/spack/relations.py
+++ b/lib/spack/spack/relations.py
@@ -45,18 +45,19 @@ provides
         spack install mpileaks ^mpich
 """
 import sys
-from dependency import Dependency
+import spack.spec
 
 
-def depends_on(*args):
+def depends_on(*specs):
     """Adds a dependencies local variable in the locals of
        the calling class, based on args.
     """
     # Get the enclosing package's scope and add deps to it.
     locals = sys._getframe(1).f_locals
     dependencies = locals.setdefault("dependencies", [])
-    for name in args:
-        dependencies.append(Dependency(name))
+    for string in specs:
+        for spec in spack.spec.parse(string):
+            dependencies.append(spec)
 
 
 def provides(*args):
diff --git a/lib/spack/spack/spec.py b/lib/spack/spack/spec.py
index d46eb33201..d7998a8fb1 100644
--- a/lib/spack/spack/spec.py
+++ b/lib/spack/spack/spec.py
@@ -68,101 +68,275 @@ from StringIO import StringIO
 import tty
 import spack.parse
 import spack.error
-from spack.version import Version, VersionRange
-from spack.color import ColorStream
-
-# Color formats for various parts of specs when using color output.
-compiler_fmt         = '@g'
-version_fmt          = '@c'
-architecture_fmt     = '@m'
-variant_enabled_fmt  = '@B'
-variant_disabled_fmt = '@r'
+import spack.compilers
+import spack.compilers.gcc
+import spack.packages as packages
+import spack.arch as arch
+from spack.version import *
+from spack.color import *
+
+"""This map determines the coloring of specs when using color output.
+   We make the fields different colors to enhance readability.
+   See spack.color for descriptions of the color codes.
+"""
+color_formats = {'%' : '@g',   # compiler
+                 '@' : '@c',   # version
+                 '=' : '@m',   # architecture
+                 '+' : '@B',   # enable variant
+                 '~' : '@r',   # disable variant
+                 '^' : '@.'}   # dependency
 
+"""Regex used for splitting by spec field separators."""
+separators = '[%s]' % ''.join(color_formats.keys())
 
-class SpecError(spack.error.SpackError):
-    """Superclass for all errors that occur while constructing specs."""
-    def __init__(self, message):
-        super(SpecError, self).__init__(message)
 
-class DuplicateDependencyError(SpecError):
-    """Raised when the same dependency occurs in a spec twice."""
-    def __init__(self, message):
-        super(DuplicateDependencyError, self).__init__(message)
+def colorize_spec(spec):
+    """Returns a spec colorized according to the colors specified in
+       color_formats."""
+    class insert_color:
+        def __init__(self):
+            self.last = None
 
-class DuplicateVariantError(SpecError):
-    """Raised when the same variant occurs in a spec twice."""
-    def __init__(self, message):
-        super(DuplicateVariantError, self).__init__(message)
+        def __call__(self, match):
+            # ignore compiler versions (color same as compiler)
+            sep = match.group(0)
+            if self.last == '%' and sep == '@':
+                return cescape(sep)
+            self.last = sep
 
-class DuplicateCompilerError(SpecError):
-    """Raised when the same compiler occurs in a spec twice."""
-    def __init__(self, message):
-        super(DuplicateCompilerError, self).__init__(message)
+            return '%s%s' % (color_formats[sep], cescape(sep))
 
-class DuplicateArchitectureError(SpecError):
-    """Raised when the same architecture occurs in a spec twice."""
-    def __init__(self, message):
-        super(DuplicateArchitectureError, self).__init__(message)
+    return colorize(re.sub(separators, insert_color(), str(spec)) + '@.')
 
 
 class Compiler(object):
-    def __init__(self, name):
+    """The Compiler field represents the compiler or range of compiler
+       versions that a package should be built with.  Compilers have a
+       name and a version list.
+    """
+    def __init__(self, name, version=None):
+        if name not in spack.compilers.supported_compilers():
+            raise UnknownCompilerError(name)
+
         self.name = name
-        self.versions = []
+        self.versions = VersionList()
+        if version:
+            self.versions.add(version)
 
-    def add_version(self, version):
-        self.versions.append(version)
 
-    def stringify(self, **kwargs):
-        color = kwargs.get("color", False)
+    def _add_version(self, version):
+        self.versions.add(version)
 
-        out = StringIO()
-        out.write("%s{%%%s}" % (compiler_fmt, self.name))
 
+    @property
+    def concrete(self):
+        return self.versions.concrete
+
+
+    def _concretize(self):
+        """If this spec could describe more than one version, variant, or build
+           of a package, this will resolve it to be concrete.
+        """
+        # TODO: support compilers other than GCC.
+        if self.concrete:
+            return
+        gcc_version = spack.compilers.gcc.get_version()
+        self.versions = VersionList([gcc_version])
+
+
+    def concretized(self):
+        clone = self.copy()
+        clone._concretize()
+        return clone
+
+
+    @property
+    def version(self):
+        if not self.concrete:
+            raise SpecError("Spec is not concrete: " + str(self))
+        return self.versions[0]
+
+
+    def copy(self):
+        clone = Compiler(self.name)
+        clone.versions = self.versions.copy()
+        return clone
+
+
+    def __eq__(self, other):
+        return (self.name, self.versions) == (other.name, other.versions)
+
+
+    def __ne__(self, other):
+        return not (self == other)
+
+
+    def __hash__(self):
+        return hash((self.name, self.versions))
+
+
+    def __str__(self):
+        out = self.name
         if self.versions:
             vlist = ",".join(str(v) for v in sorted(self.versions))
-            out.write("%s{@%s}" % (compiler_fmt, vlist))
-        return out.getvalue()
+            out += "@%s" % vlist
+        return out
+
+
+@total_ordering
+class Variant(object):
+    """Variants are named, build-time options for a package.  Names depend
+       on the particular package being built, and each named variant can
+       be enabled or disabled.
+    """
+    def __init__(self, name, enabled):
+        self.name = name
+        self.enabled = enabled
+
+
+    def __eq__(self, other):
+        return self.name == other.name and self.enabled == other.enabled
+
+
+    def __ne__(self, other):
+        return not (self == other)
+
+
+    @property
+    def tuple(self):
+        return (self.name, self.enabled)
+
+
+    def __hash__(self):
+        return hash(self.tuple)
+
+
+    def __lt__(self, other):
+        return self.tuple < other.tuple
+
 
     def __str__(self):
-        return self.stringify()
+        out = '+' if self.enabled else '~'
+        return out + self.name
+
+
+
+@total_ordering
+class HashableMap(dict):
+    """This is a hashable, comparable dictionary.  Hash is performed on
+       a tuple of the values in the dictionary."""
+    def __eq__(self, other):
+        return (len(self) == len(other) and
+                sorted(self.values()) == sorted(other.values()))
+
+
+    def __ne__(self, other):
+        return not (self == other)
+
+
+    def __lt__(self, other):
+        return tuple(sorted(self.values())) < tuple(sorted(other.values()))
+
+
+    def __hash__(self):
+        return hash(tuple(sorted(self.values())))
+
+
+    def copy(self):
+        """Type-agnostic clone method.  Preserves subclass type."""
+        # Construct a new dict of my type
+        T = type(self)
+        clone = T()
 
+        # Copy everything from this dict into it.
+        for key in self:
+            clone[key] = self[key]
+        return clone
 
+
+class VariantMap(HashableMap):
+    def __str__(self):
+        sorted_keys = sorted(self.keys())
+        return ''.join(str(self[key]) for key in sorted_keys)
+
+
+class DependencyMap(HashableMap):
+    """Each spec has a DependencyMap containing specs for its dependencies.
+       The DependencyMap is keyed by name. """
+    @property
+    def concrete(self):
+        return all(d.concrete for d in self.values())
+
+
+    def __str__(self):
+        sorted_keys = sorted(self.keys())
+        return ''.join(
+            ["^" + str(self[name]) for name in sorted_keys])
+
+
+@total_ordering
 class Spec(object):
     def __init__(self, name):
         self.name = name
-        self._package = None
-        self.versions = []
-        self.variants = {}
+        self.versions = VersionList()
+        self.variants = VariantMap()
         self.architecture = None
         self.compiler = None
-        self.dependencies = {}
+        self.dependencies = DependencyMap()
+
+    #
+    # Private routines here are called by the parser when building a spec.
+    #
+    def _add_version(self, version):
+        """Called by the parser to add an allowable version."""
+        self.versions.add(version)
 
-    def add_version(self, version):
-        self.versions.append(version)
 
-    def add_variant(self, name, enabled):
+    def _add_variant(self, name, enabled):
+        """Called by the parser to add a variant."""
         if name in self.variants: raise DuplicateVariantError(
                 "Cannot specify variant '%s' twice" % name)
-        self.variants[name] = enabled
+        self.variants[name] = Variant(name, enabled)
+
 
-    def add_compiler(self, compiler):
+    def _set_compiler(self, compiler):
+        """Called by the parser to set the compiler."""
         if self.compiler: raise DuplicateCompilerError(
                 "Spec for '%s' cannot have two compilers." % self.name)
         self.compiler = compiler
 
-    def add_architecture(self, architecture):
+
+    def _set_architecture(self, architecture):
+        """Called by the parser to set the architecture."""
         if self.architecture: raise DuplicateArchitectureError(
                 "Spec for '%s' cannot have two architectures." % self.name)
         self.architecture = architecture
 
-    def add_dependency(self, dep):
+
+    def _add_dependency(self, dep):
+        """Called by the parser to add another spec as a dependency."""
         if dep.name in self.dependencies:
             raise DuplicateDependencyError("Cannot depend on '%s' twice" % dep)
         self.dependencies[dep.name] = dep
 
-    def canonicalize(self):
-        """Ensures that the spec is in canonical form.
+
+    @property
+    def concrete(self):
+        return (self.versions.concrete
+                # TODO: support variants
+                and self.architecture
+                and self.compiler and self.compiler.concrete
+                and self.dependencies.concrete)
+
+
+    def _concretize(self):
+        """A spec is concrete if it describes one build of a package uniquely.
+           This will ensure that this spec is concrete.
+
+           If this spec could describe more than one version, variant, or build
+           of a package, this will resolve it to be concrete.
+
+           Ensures that the spec is in canonical form.
 
            This means:
            1. All dependencies of this package and of its dependencies are
@@ -173,49 +347,164 @@ class Spec(object):
            that each package exists an that spec criteria don't violate package
            criteria.
         """
+        # TODO: modularize the process of selecting concrete versions.
+        # There should be a set of user-configurable policies for these decisions.
+        self.check_sanity()
+
+        # take the system's architecture for starters
+        if not self.architecture:
+             self.architecture = arch.sys_type()
+
+        if self.compiler:
+            self.compiler._concretize()
+
+        # TODO: handle variants.
+
+        pkg = packages.get(self.name)
+
+        # Take the highest version in a range
+        if not self.versions.concrete:
+            preferred = self.versions.highest() or pkg.version
+            self.versions = VersionList([preferred])
+
+        # Ensure dependencies have right versions
+
+
+
+    def check_sanity(self):
+        """Check names of packages and dependency validity."""
+        self.check_package_name_sanity()
+        self.check_dependency_sanity()
+        self.check_dependence_constraint_sanity()
+
+
+    def check_package_name_sanity(self):
+        """Ensure that all packages mentioned in the spec exist."""
+        packages.get(self.name)
+        for dep in self.dependencies.values():
+            packages.get(dep.name)
+
+
+    def check_dependency_sanity(self):
+        """Ensure that dependencies specified on the spec are actual
+           dependencies of the package it represents.
+        """
+        pkg = packages.get(self.name)
+        dep_names = set(dep.name for dep in pkg.all_dependencies)
+        invalid_dependencies = [d.name for d in self.dependencies.values()
+                                if d.name not in dep_names]
+        if invalid_dependencies:
+            raise InvalidDependencyException(
+                "The packages (%s) are not dependencies of %s" %
+                (','.join(invalid_dependencies), self.name))
+
+
+    def check_dependence_constraint_sanity(self):
+        """Ensure that package's dependencies have consistent constraints on
+           their dependencies.
+        """
+        pkg = packages.get(self.name)
+        specs = {}
+        for spec in pkg.all_dependencies:
+            if not spec.name in specs:
+                specs[spec.name] = spec
+                continue
+
+            merged = specs[spec.name]
+
+            # Specs in deps can't be disjoint.
+            if not spec.versions.overlaps(merged.versions):
+                raise InvalidConstraintException(
+                    "One package %s, version constraint %s conflicts with %s"
+                    % (pkg.name, spec.versions, merged.versions))
+
+
+    def merge(self, other):
+        """Considering these specs as constraints, attempt to merge.
+           Raise an exception if specs are disjoint.
+        """
         pass
 
+
+    def concretized(self):
+        clone = self.copy()
+        clone._concretize()
+        return clone
+
+
+    def copy(self):
+        clone = Spec(self.name)
+        clone.versions = self.versions.copy()
+        clone.variants = self.variants.copy()
+        clone.architecture = self.architecture
+        clone.compiler = None
+        if self.compiler:
+            clone.compiler = self.compiler.copy()
+        clone.dependencies = self.dependencies.copy()
+        return clone
+
+
     @property
-    def package(self):
-        if self._package == None:
-            self._package = packages.get(self.name)
-        return self._package
+    def version(self):
+        if not self.concrete:
+            raise SpecError("Spec is not concrete: " + str(self))
+        return self.versions[0]
 
-    def stringify(self, **kwargs):
-        color = kwargs.get("color", False)
 
-        out = ColorStream(StringIO(), color)
-        out.write("%s" % self.name)
+    @property
+    def tuple(self):
+        return (self.name, self.versions, self.variants,
+                self.architecture, self.compiler, self.dependencies)
 
-        if self.versions:
-            vlist = ",".join(str(v) for v in sorted(self.versions))
-            out.write("%s{@%s}" % (version_fmt, vlist))
 
-        if self.compiler:
-            out.write(self.compiler.stringify(color=color))
+    @property
+    def tuple(self):
+        return (self.name, self.versions, self.variants, self.architecture,
+                self.compiler, self.dependencies)
 
-        for name in sorted(self.variants.keys()):
-            enabled = self.variants[name]
-            if enabled:
-                out.write('%s{+%s}' % (variant_enabled_fmt, name))
-            else:
-                out.write('%s{~%s}' % (variant_disabled_fmt, name))
 
-        if self.architecture:
-            out.write("%s{=%s}" % (architecture_fmt, self.architecture))
+    def __eq__(self, other):
+        return self.tuple == other.tuple
+
+
+    def __ne__(self, other):
+        return not (self == other)
+
+
+    def __lt__(self, other):
+        return self.tuple < other.tuple
 
-        for name in sorted(self.dependencies.keys()):
-            dep = " ^" + self.dependencies[name].stringify(color=color)
-            out.write(dep, raw=True)
 
-        return out.getvalue()
+    def __hash__(self):
+        return hash(self.tuple)
+
+
+    def colorized(self):
+        return colorize_spec(self)
+
+
+    def __repr__(self):
+        return str(self)
 
-    def write(self, stream=sys.stdout):
-        isatty = stream.isatty()
-        stream.write(self.stringify(color=isatty))
 
     def __str__(self):
-        return self.stringify()
+        out = self.name
+
+        # If the version range is entirely open, omit it
+        if self.versions and self.versions != VersionList([':']):
+            out += "@%s" % self.versions
+
+        if self.compiler:
+            out += "%%%s" % self.compiler
+
+        out += str(self.variants)
+
+        if self.architecture:
+            out += "=%s" % self.architecture
+
+        out += str(self.dependencies)
+        return out
+
 
 #
 # These are possible token types in the spec grammar.
@@ -254,7 +543,7 @@ class SpecParser(spack.parse.Parser):
                 if not specs:
                     self.last_token_error("Dependency has no package")
                 self.expect(ID)
-                specs[-1].add_dependency(self.spec())
+                specs[-1]._add_dependency(self.spec())
 
             else:
                 self.unexpected_token()
@@ -265,28 +554,34 @@ class SpecParser(spack.parse.Parser):
     def spec(self):
         self.check_identifier()
         spec = Spec(self.token.value)
+        added_version = False
 
         while self.next:
             if self.accept(AT):
                 vlist = self.version_list()
                 for version in vlist:
-                    spec.add_version(version)
+                    spec._add_version(version)
+                added_version = True
 
             elif self.accept(ON):
-                spec.add_variant(self.variant(), True)
+                spec._add_variant(self.variant(), True)
 
             elif self.accept(OFF):
-                spec.add_variant(self.variant(), False)
+                spec._add_variant(self.variant(), False)
 
             elif self.accept(PCT):
-                spec.add_compiler(self.compiler())
+                spec._set_compiler(self.compiler())
 
             elif self.accept(EQ):
-                spec.add_architecture(self.architecture())
+                spec._set_architecture(self.architecture())
 
             else:
                 break
 
+        # If there was no version in the spec, consier it an open range
+        if not added_version:
+            spec.versions = VersionList([':'])
+
         return spec
 
 
@@ -318,12 +613,9 @@ class SpecParser(spack.parse.Parser):
             # No colon and no id: invalid version.
             self.next_token_error("Invalid version specifier")
 
-        if not start and not end:
-            self.next_token_error("Lone colon: version range needs a version")
-        else:
-            if start: start = Version(start)
-            if end: end = Version(end)
-            return VersionRange(start, end)
+        if start: start = Version(start)
+        if end: end = Version(end)
+        return VersionRange(start, end)
 
 
     def version_list(self):
@@ -341,7 +633,7 @@ class SpecParser(spack.parse.Parser):
         if self.accept(AT):
             vlist = self.version_list()
             for version in vlist:
-                compiler.add_version(version)
+                compiler._add_version(version)
         return compiler
 
 
@@ -357,3 +649,79 @@ class SpecParser(spack.parse.Parser):
 def parse(string):
     """Returns a list of specs from an input string."""
     return SpecParser().parse(string)
+
+
+def parse_one(string):
+    """Parses a string containing only one spec, then returns that
+       spec.  If more than one spec is found, raises a ValueError.
+    """
+    spec_list = parse(string)
+    if len(spec_list) > 1:
+        raise ValueError("string contains more than one spec!")
+    elif len(spec_list) < 1:
+        raise ValueError("string contains no specs!")
+    return spec_list[0]
+
+
+def make_spec(spec_like):
+    if type(spec_like) == str:
+        specs = parse(spec_like)
+        if len(specs) != 1:
+            raise ValueError("String contains multiple specs: '%s'" % spec_like)
+        return specs[0]
+
+    elif type(spec_like) == Spec:
+        return spec_like
+
+    else:
+        raise TypeError("Can't make spec out of %s" % type(spec_like))
+
+
+class SpecError(spack.error.SpackError):
+    """Superclass for all errors that occur while constructing specs."""
+    def __init__(self, message):
+        super(SpecError, self).__init__(message)
+
+
+class DuplicateDependencyError(SpecError):
+    """Raised when the same dependency occurs in a spec twice."""
+    def __init__(self, message):
+        super(DuplicateDependencyError, self).__init__(message)
+
+
+class DuplicateVariantError(SpecError):
+    """Raised when the same variant occurs in a spec twice."""
+    def __init__(self, message):
+        super(DuplicateVariantError, self).__init__(message)
+
+
+class DuplicateCompilerError(SpecError):
+    """Raised when the same compiler occurs in a spec twice."""
+    def __init__(self, message):
+        super(DuplicateCompilerError, self).__init__(message)
+
+
+class UnknownCompilerError(SpecError):
+    """Raised when the user asks for a compiler spack doesn't know about."""
+    def __init__(self, compiler_name):
+        super(UnknownCompilerError, self).__init__(
+            "Unknown compiler: %s" % compiler_name)
+
+
+class DuplicateArchitectureError(SpecError):
+    """Raised when the same architecture occurs in a spec twice."""
+    def __init__(self, message):
+        super(DuplicateArchitectureError, self).__init__(message)
+
+
+class InvalidDependencyException(SpecError):
+    """Raised when a dependency in a spec is not actually a dependency
+       of the package."""
+    def __init__(self, message):
+        super(InvalidDependencyException, self).__init__(message)
+
+
+class InvalidConstraintException(SpecError):
+    """Raised when a package dependencies conflict."""
+    def __init__(self, message):
+        super(InvalidConstraintException, self).__init__(message)
diff --git a/lib/spack/spack/stage.py b/lib/spack/spack/stage.py
index 9145fa5371..9bf9584f57 100644
--- a/lib/spack/spack/stage.py
+++ b/lib/spack/spack/stage.py
@@ -18,8 +18,8 @@ class FailedDownloadError(serr.SpackError):
 
 class Stage(object):
     """A Stage object manaages a directory where an archive is downloaded,
-       expanded, and built before being installed.  A stage's lifecycle looks
-       like this:
+       expanded, and built before being installed.  It also handles downloading
+       the archive.  A stage's lifecycle looks like this:
 
        setup()           Create the stage directory.
        fetch()           Fetch a source archive into the stage.
@@ -32,21 +32,16 @@ class Stage(object):
        in a tmp directory.  Otherwise, stages are created directly in
        spack.stage_path.
     """
-
-    def __init__(self, stage_name, url):
+    def __init__(self, path, url):
         """Create a stage object.
            Parameters:
-             stage_name   Name of the stage directory that will be created.
-             url          URL of the archive to be downloaded into this stage.
+             path    Relative path from the stage root to where the stage will
+                     be created.
+             url     URL of the archive to be downloaded into this stage.
         """
-        self.stage_name = stage_name
+        self.path = os.path.join(spack.stage_path, path)
         self.url = url
 
-    @property
-    def path(self):
-        """Absolute path to the stage directory."""
-        return spack.new_path(spack.stage_path, self.stage_name)
-
 
     def setup(self):
         """Creates the stage directory.
@@ -103,8 +98,7 @@ class Stage(object):
                 if username:
                     tmp_dir = spack.new_path(tmp_dir, username)
                 spack.mkdirp(tmp_dir)
-                tmp_dir = tempfile.mkdtemp(
-                    '.stage', self.stage_name + '-', tmp_dir)
+                tmp_dir = tempfile.mkdtemp('.stage', 'spack-stage-', tmp_dir)
 
                 os.symlink(tmp_dir, self.path)
 
diff --git a/lib/spack/spack/test/concretize.py b/lib/spack/spack/test/concretize.py
new file mode 100644
index 0000000000..05a2f4811c
--- /dev/null
+++ b/lib/spack/spack/test/concretize.py
@@ -0,0 +1,13 @@
+import unittest
+import spack.spec
+
+
+class ConcretizeTest(unittest.TestCase):
+
+    def check_concretize(self, abstract_spec):
+        abstract = spack.spec.parse_one(abstract_spec)
+        self.assertTrue(abstract.concretized().concrete)
+
+
+    def test_packages(self):
+        self.check_concretize("libelf")
diff --git a/lib/spack/spack/test/specs.py b/lib/spack/spack/test/specs.py
index cbc88fa315..f495738a72 100644
--- a/lib/spack/spack/test/specs.py
+++ b/lib/spack/spack/test/specs.py
@@ -1,6 +1,7 @@
 import unittest
+import spack.spec
 from spack.spec import *
-from spack.parse import *
+from spack.parse import Token, ParseError
 
 # Sample output for a complex lexing.
 complex_lex = [Token(ID, 'mvapich_foo'),
@@ -29,10 +30,6 @@ complex_lex = [Token(ID, 'mvapich_foo'),
 
 
 class SpecTest(unittest.TestCase):
-    def setUp(self):
-        self.parser = SpecParser()
-        self.lexer = SpecLexer()
-
     # ================================================================================
     # Parse checks
     # ================================================================================
@@ -47,14 +44,14 @@ class SpecTest(unittest.TestCase):
         """
         if spec == None:
             spec = expected
-        output = self.parser.parse(spec)
+        output = spack.spec.parse(spec)
         parsed = (" ".join(str(spec) for spec in output))
         self.assertEqual(expected, parsed)
 
 
     def check_lex(self, tokens, spec):
         """Check that the provided spec parses to the provided list of tokens."""
-        lex_output = self.lexer.lex(spec)
+        lex_output = SpecLexer().lex(spec)
         for tok, spec_tok in zip(tokens, lex_output):
             if tok.type == ID:
                 self.assertEqual(tok, spec_tok)
@@ -71,31 +68,33 @@ class SpecTest(unittest.TestCase):
         self.check_parse("_mvapich_foo")
 
     def test_simple_dependence(self):
-        self.check_parse("openmpi ^hwloc")
-        self.check_parse("openmpi ^hwloc ^libunwind")
+        self.check_parse("openmpi^hwloc")
+        self.check_parse("openmpi^hwloc^libunwind")
 
     def test_dependencies_with_versions(self):
-        self.check_parse("openmpi ^hwloc@1.2e6")
-        self.check_parse("openmpi ^hwloc@1.2e6:")
-        self.check_parse("openmpi ^hwloc@:1.4b7-rc3")
-        self.check_parse("openmpi ^hwloc@1.2e6:1.4b7-rc3")
+        self.check_parse("openmpi^hwloc@1.2e6")
+        self.check_parse("openmpi^hwloc@1.2e6:")
+        self.check_parse("openmpi^hwloc@:1.4b7-rc3")
+        self.check_parse("openmpi^hwloc@1.2e6:1.4b7-rc3")
 
     def test_full_specs(self):
-        self.check_parse("mvapich_foo ^_openmpi@1.2:1.4,1.6%intel@12.1+debug~qt_4 ^stackwalker@8.1_1e")
+        self.check_parse("mvapich_foo^_openmpi@1.2:1.4,1.6%intel@12.1+debug~qt_4^stackwalker@8.1_1e")
 
     def test_canonicalize(self):
         self.check_parse(
-            "mvapich_foo ^_openmpi@1.2:1.4,1.6%intel@12.1:12.6+debug~qt_4 ^stackwalker@8.1_1e",
+            "mvapich_foo^_openmpi@1.2:1.4,1.6%intel@12.1:12.6+debug~qt_4^stackwalker@8.1_1e",
             "mvapich_foo ^_openmpi@1.6,1.2:1.4%intel@12.1:12.6+debug~qt_4 ^stackwalker@8.1_1e")
 
         self.check_parse(
-            "mvapich_foo ^_openmpi@1.2:1.4,1.6%intel@12.1:12.6+debug~qt_4 ^stackwalker@8.1_1e",
+            "mvapich_foo^_openmpi@1.2:1.4,1.6%intel@12.1:12.6+debug~qt_4^stackwalker@8.1_1e",
             "mvapich_foo ^stackwalker@8.1_1e ^_openmpi@1.6,1.2:1.4%intel@12.1:12.6~qt_4+debug")
 
         self.check_parse(
-            "x ^y@1,2:3,4%intel@1,2,3,4+a~b+c~d+e~f",
+            "x^y@1,2:3,4%intel@1,2,3,4+a~b+c~d+e~f",
             "x ^y~f+e~d+c~b+a@4,2:3,1%intel@4,3,2,1")
 
+        self.check_parse("x^y", "x@: ^y@:")
+
     def test_parse_errors(self):
         self.assertRaises(ParseError, self.check_parse, "x@@1.2")
         self.assertRaises(ParseError, self.check_parse, "x ^y@@1.2")
@@ -111,11 +110,11 @@ class SpecTest(unittest.TestCase):
 
     def test_duplicate_compiler(self):
         self.assertRaises(DuplicateCompilerError, self.check_parse, "x%intel%intel")
-        self.assertRaises(DuplicateCompilerError, self.check_parse, "x%intel%gnu")
-        self.assertRaises(DuplicateCompilerError, self.check_parse, "x%gnu%intel")
+        self.assertRaises(DuplicateCompilerError, self.check_parse, "x%intel%gcc")
+        self.assertRaises(DuplicateCompilerError, self.check_parse, "x%gcc%intel")
         self.assertRaises(DuplicateCompilerError, self.check_parse, "x ^y%intel%intel")
-        self.assertRaises(DuplicateCompilerError, self.check_parse, "x ^y%intel%gnu")
-        self.assertRaises(DuplicateCompilerError, self.check_parse, "x ^y%gnu%intel")
+        self.assertRaises(DuplicateCompilerError, self.check_parse, "x ^y%intel%gcc")
+        self.assertRaises(DuplicateCompilerError, self.check_parse, "x ^y%gcc%intel")
 
 
     # ================================================================================
diff --git a/lib/spack/spack/test/versions.py b/lib/spack/spack/test/versions.py
index 96666b36db..09d74549ef 100644
--- a/lib/spack/spack/test/versions.py
+++ b/lib/spack/spack/test/versions.py
@@ -39,6 +39,26 @@ class VersionsTest(unittest.TestCase):
         self.assertTrue(a <= b)
 
 
+    def assert_in(self, needle, haystack):
+        self.assertTrue(ver(needle) in ver(haystack))
+
+
+    def assert_not_in(self, needle, haystack):
+        self.assertFalse(ver(needle) in ver(haystack))
+
+
+    def assert_canonical(self, canonical_list, version_list):
+        self.assertEqual(ver(canonical_list), ver(version_list))
+
+
+    def assert_overlaps(self, v1, v2):
+        self.assertTrue(ver(v1).overlaps(ver(v2)))
+
+
+    def assert_no_overlap(self, v1, v2):
+        self.assertFalse(ver(v1).overlaps(ver(v2)))
+
+
     def test_two_segments(self):
         self.assert_ver_eq('1.0', '1.0')
         self.assert_ver_lt('1.0', '2.0')
@@ -50,6 +70,7 @@ class VersionsTest(unittest.TestCase):
         self.assert_ver_lt('2.0',   '2.0.1')
         self.assert_ver_gt('2.0.1', '2.0')
 
+
     def test_alpha(self):
         # TODO: not sure whether I like this.  2.0.1a is *usually*
         # TODO: less than 2.0.1, but special-casing it makes version
@@ -58,6 +79,7 @@ class VersionsTest(unittest.TestCase):
         self.assert_ver_gt('2.0.1a', '2.0.1')
         self.assert_ver_lt('2.0.1',  '2.0.1a')
 
+
     def test_patch(self):
         self.assert_ver_eq('5.5p1',  '5.5p1')
         self.assert_ver_lt('5.5p1',  '5.5p2')
@@ -66,6 +88,7 @@ class VersionsTest(unittest.TestCase):
         self.assert_ver_lt('5.5p1',  '5.5p10')
         self.assert_ver_gt('5.5p10', '5.5p1')
 
+
     def test_num_alpha_with_no_separator(self):
         self.assert_ver_lt('10xyz',   '10.1xyz')
         self.assert_ver_gt('10.1xyz', '10xyz')
@@ -73,6 +96,7 @@ class VersionsTest(unittest.TestCase):
         self.assert_ver_lt('xyz10',   'xyz10.1')
         self.assert_ver_gt('xyz10.1', 'xyz10')
 
+
     def test_alpha_with_dots(self):
         self.assert_ver_eq('xyz.4', 'xyz.4')
         self.assert_ver_lt('xyz.4', '8')
@@ -80,25 +104,30 @@ class VersionsTest(unittest.TestCase):
         self.assert_ver_lt('xyz.4', '2')
         self.assert_ver_gt('2',     'xyz.4')
 
+
     def test_nums_and_patch(self):
         self.assert_ver_lt('5.5p2', '5.6p1')
         self.assert_ver_gt('5.6p1', '5.5p2')
         self.assert_ver_lt('5.6p1', '6.5p1')
         self.assert_ver_gt('6.5p1', '5.6p1')
 
+
     def test_rc_versions(self):
         self.assert_ver_gt('6.0.rc1', '6.0')
         self.assert_ver_lt('6.0',     '6.0.rc1')
 
+
     def test_alpha_beta(self):
         self.assert_ver_gt('10b2', '10a1')
         self.assert_ver_lt('10a2', '10b2')
 
+
     def test_double_alpha(self):
         self.assert_ver_eq('1.0aa', '1.0aa')
         self.assert_ver_lt('1.0a',  '1.0aa')
         self.assert_ver_gt('1.0aa', '1.0a')
 
+
     def test_padded_numbers(self):
         self.assert_ver_eq('10.0001', '10.0001')
         self.assert_ver_eq('10.0001', '10.1')
@@ -106,20 +135,24 @@ class VersionsTest(unittest.TestCase):
         self.assert_ver_lt('10.0001', '10.0039')
         self.assert_ver_gt('10.0039', '10.0001')
 
+
     def test_close_numbers(self):
         self.assert_ver_lt('4.999.9', '5.0')
         self.assert_ver_gt('5.0',     '4.999.9')
 
+
     def test_date_stamps(self):
         self.assert_ver_eq('20101121', '20101121')
         self.assert_ver_lt('20101121', '20101122')
         self.assert_ver_gt('20101122', '20101121')
 
+
     def test_underscores(self):
         self.assert_ver_eq('2_0', '2_0')
         self.assert_ver_eq('2.0', '2_0')
         self.assert_ver_eq('2_0', '2.0')
 
+
     def test_rpm_oddities(self):
         self.assert_ver_eq('1b.fc17', '1b.fc17')
         self.assert_ver_lt('1b.fc17', '1.fc17')
@@ -139,3 +172,89 @@ class VersionsTest(unittest.TestCase):
 
         self.assert_ver_lt('1.2:1.4', '1.5:1.6')
         self.assert_ver_gt('1.5:1.6', '1.2:1.4')
+
+
+    def test_contains(self):
+        self.assert_in('1.3', '1.2:1.4')
+        self.assert_in('1.2.5', '1.2:1.4')
+        self.assert_in('1.3.5', '1.2:1.4')
+        self.assert_in('1.3.5-7', '1.2:1.4')
+        self.assert_not_in('1.1', '1.2:1.4')
+        self.assert_not_in('1.5', '1.2:1.4')
+        self.assert_not_in('1.4.2', '1.2:1.4')
+
+        self.assert_in('1.2.8', '1.2.7:1.4')
+        self.assert_in('1.2.7:1.4', ':')
+        self.assert_not_in('1.2.5', '1.2.7:1.4')
+        self.assert_not_in('1.4.1', '1.2.7:1.4')
+
+
+    def test_in_list(self):
+        self.assert_in('1.2', ['1.5', '1.2', '1.3'])
+        self.assert_in('1.2.5', ['1.5', '1.2:1.3'])
+        self.assert_in('1.5', ['1.5', '1.2:1.3'])
+        self.assert_not_in('1.4', ['1.5', '1.2:1.3'])
+
+        self.assert_in('1.2.5:1.2.7', [':'])
+        self.assert_in('1.2.5:1.2.7', ['1.5', '1.2:1.3'])
+        self.assert_not_in('1.2.5:1.5', ['1.5', '1.2:1.3'])
+        self.assert_not_in('1.1:1.2.5', ['1.5', '1.2:1.3'])
+
+
+    def test_ranges_overlap(self):
+        self.assert_overlaps('1.2', '1.2')
+        self.assert_overlaps('1.2.1', '1.2.1')
+        self.assert_overlaps('1.2.1b', '1.2.1b')
+
+        self.assert_overlaps('1.2:1.7', '1.6:1.9')
+        self.assert_overlaps(':1.7', '1.6:1.9')
+        self.assert_overlaps(':1.7', ':1.9')
+        self.assert_overlaps(':1.7', '1.6:')
+        self.assert_overlaps('1.2:', '1.6:1.9')
+        self.assert_overlaps('1.2:', ':1.9')
+        self.assert_overlaps('1.2:', '1.6:')
+        self.assert_overlaps(':', ':')
+        self.assert_overlaps(':', '1.6:1.9')
+
+
+    def test_lists_overlap(self):
+        self.assert_overlaps('1.2b:1.7,5', '1.6:1.9,1')
+        self.assert_overlaps('1,2,3,4,5', '3,4,5,6,7')
+        self.assert_overlaps('1,2,3,4,5', '5,6,7')
+        self.assert_overlaps('1,2,3,4,5', '5:7')
+        self.assert_overlaps('1,2,3,4,5', '3, 6:7')
+        self.assert_overlaps('1, 2, 4, 6.5', '3, 6:7')
+        self.assert_overlaps('1, 2, 4, 6.5', ':, 5, 8')
+        self.assert_overlaps('1, 2, 4, 6.5', ':')
+        self.assert_no_overlap('1, 2, 4', '3, 6:7')
+        self.assert_no_overlap('1,2,3,4,5', '6,7')
+        self.assert_no_overlap('1,2,3,4,5', '6:7')
+
+
+    def test_canonicalize_list(self):
+        self.assert_canonical(['1.2', '1.3', '1.4'],
+                              ['1.2', '1.3', '1.3', '1.4'])
+
+        self.assert_canonical(['1.2', '1.3:1.4'],
+                              ['1.2', '1.3', '1.3:1.4'])
+
+        self.assert_canonical(['1.2', '1.3:1.4'],
+                              ['1.2', '1.3:1.4', '1.4'])
+
+        self.assert_canonical(['1.3:1.4'],
+                              ['1.3:1.4', '1.3', '1.3.1', '1.3.9', '1.4'])
+
+        self.assert_canonical(['1.3:1.4'],
+                              ['1.3', '1.3.1', '1.3.9', '1.4', '1.3:1.4'])
+
+        self.assert_canonical(['1.3:1.5'],
+                              ['1.3', '1.3.1', '1.3.9', '1.4:1.5', '1.3:1.4'])
+
+        self.assert_canonical(['1.3:1.5'],
+                              ['1.3, 1.3.1,1.3.9,1.4:1.5,1.3:1.4'])
+
+        self.assert_canonical(['1.3:1.5'],
+                              ['1.3, 1.3.1,1.3.9,1.4 : 1.5 , 1.3 : 1.4'])
+
+        self.assert_canonical([':'],
+                              [':,1.3, 1.3.1,1.3.9,1.4 : 1.5 , 1.3 : 1.4'])
diff --git a/lib/spack/spack/tty.py b/lib/spack/spack/tty.py
index 531f5660f7..d6f64f7203 100644
--- a/lib/spack/spack/tty.py
+++ b/lib/spack/spack/tty.py
@@ -1,18 +1,18 @@
 import sys
 import spack
-from spack.color import cprint
+from spack.color import *
 
 indent = "  "
 
 def msg(message, *args):
-    cprint("@*b{==>} @*w{%s}" % str(message))
+    cprint("@*b{==>} @*w{%s}" % cescape(message))
     for arg in args:
         print indent + str(arg)
 
 
 def info(message, *args, **kwargs):
     format = kwargs.get('format', '*b')
-    cprint("@%s{==>} %s" % (format, str(message)))
+    cprint("@%s{==>} %s" % (format, cescape(message)))
     for arg in args:
         print indent + str(arg)
 
diff --git a/lib/spack/spack/version.py b/lib/spack/spack/version.py
index e905756c9e..b3ebed3952 100644
--- a/lib/spack/spack/version.py
+++ b/lib/spack/spack/version.py
@@ -1,29 +1,83 @@
+"""
+This file implements Version and version-ish objects.  These are:
+
+  Version
+      A single version of a package.
+  VersionRange
+      A range of versions of a package.
+  VersionList
+      A list of Versions and VersionRanges.
+
+All of these types support the following operations, which can
+be called on any of the types:
+
+  __eq__, __ne__, __lt__, __gt__, __ge__, __le__, __hash__
+  __contains__
+  overlaps
+  merge
+  concrete
+      True if the Version, VersionRange or VersionList represents
+      a single version.
+"""
 import os
+import sys
 import re
+from bisect import bisect_left
 from functools import total_ordering
 
 import utils
+from none_compare import *
 import spack.error
 
 # Valid version characters
 VALID_VERSION = r'[A-Za-z0-9_.-]'
 
-
 def int_if_int(string):
     """Convert a string to int if possible.  Otherwise, return a string."""
     try:
         return int(string)
-    except:
+    except ValueError:
         return string
 
 
-def ver(string):
-    """Parses either a version or version range from a string."""
-    if ':' in string:
-        start, end = string.split(':')
-        return VersionRange(Version(start), Version(end))
+def coerce_versions(a, b):
+    """Convert both a and b to the 'greatest' type between them, in this order:
+           Version < VersionRange < VersionList
+       This is used to simplify comparison operations below so that we're always
+       comparing things that are of the same type.
+    """
+    order = (Version, VersionRange, VersionList)
+    ta, tb = type(a), type(b)
+
+    def check_type(t):
+        if t not in order:
+            raise TypeError("coerce_versions cannot be called on %s" % t)
+    check_type(ta)
+    check_type(tb)
+
+    if ta == tb:
+        return (a, b)
+    elif order.index(ta) > order.index(tb):
+        if ta == VersionRange:
+            return (a, VersionRange(b, b))
+        else:
+            return (a, VersionList([b]))
     else:
-        return Version(string)
+        if tb == VersionRange:
+            return (VersionRange(a, a), b)
+        else:
+            return (VersionList([a]), b)
+
+
+def coerced(method):
+    """Decorator that ensures that argument types of a method are coerced."""
+    def coercing_method(a, b):
+        if type(a) == type(b) or a is None or b is None:
+            return method(a, b)
+        else:
+            ca, cb = coerce_versions(a, b)
+            return getattr(ca, method.__name__)(cb)
+    return coercing_method
 
 
 @total_ordering
@@ -33,7 +87,8 @@ class Version(object):
         if not re.match(VALID_VERSION, string):
             raise ValueError("Bad characters in version string: %s" % string)
 
-        # preserve the original string
+        # preserve the original string, but trimmed.
+        string = string.strip()
         self.string = string
 
         # Split version into alphabetical and numeric segments
@@ -52,6 +107,15 @@ class Version(object):
         """
         return '.'.join(str(x) for x in self[:index])
 
+
+    def lowest(self):
+        return self
+
+
+    def highest(self):
+        return self
+
+
     def wildcard(self):
         """Create a regex that will match variants of this version string."""
         def a_or_n(seg):
@@ -75,31 +139,39 @@ class Version(object):
         wc += ')?' * (len(seg_res) - 1)
         return wc
 
+
     def __iter__(self):
         for v in self.version:
             yield v
 
+
     def __getitem__(self, idx):
         return tuple(self.version[idx])
 
+
     def __repr__(self):
         return self.string
 
+
     def __str__(self):
         return self.string
 
+
+    @property
+    def concrete(self):
+        return self
+
+    @coerced
     def __lt__(self, other):
         """Version comparison is designed for consistency with the way RPM
            does things.  If you need more complicated versions in installed
            packages, you should override your package's version string to
            express it more sensibly.
         """
-        assert(other is not None)
-
-        # Let VersionRange do all the range-based comparison
-        if type(other) == VersionRange:
-            return not other < self
+        if other is None:
+            return False
 
+        # Coerce if other is not a Version
         # simple equality test first.
         if self.version == other.version:
             return False
@@ -121,22 +193,42 @@ class Version(object):
         # If the common prefix is equal, the one with more segments is bigger.
         return len(self.version) < len(other.version)
 
+
+    @coerced
     def __eq__(self, other):
-        """Implemented to match __lt__.  See __lt__."""
-        if type(other) != Version:
-            return False
-        return self.version == other.version
+        return (other is not None and
+                type(other) == Version and self.version == other.version)
+
 
     def __ne__(self, other):
         return not (self == other)
 
+
     def __hash__(self):
         return hash(self.version)
 
 
+    @coerced
+    def __contains__(self, other):
+        return self == other
+
+
+    @coerced
+    def overlaps(self, other):
+        return self == other
+
+
+    @coerced
+    def merge(self, other):
+        if self == other:
+            return self
+        else:
+            return VersionList([self, other])
+
+
 @total_ordering
 class VersionRange(object):
-    def __init__(self, start, end=None):
+    def __init__(self, start, end):
         if type(start) == str:
             start = Version(start)
         if type(end) == str:
@@ -148,37 +240,74 @@ class VersionRange(object):
             raise ValueError("Invalid Version range: %s" % self)
 
 
-    def __lt__(self, other):
-        if type(other) == Version:
-            return self.end and self.end < other
-        elif type(other) == VersionRange:
-            return self.end and other.start and self.end < other.start
-        else:
-            raise TypeError("Can't compare VersionRange to %s" % type(other))
+    def lowest(self):
+        return self.start
 
 
-    def __gt__(self, other):
-        if type(other) == Version:
-            return self.start and self.start > other
-        elif type(other) == VersionRange:
-            return self.start and other.end and self.start > other.end
-        else:
-            raise TypeError("Can't compare VersionRange to %s" % type(other))
+    def highest(self):
+        return self.end
+
+
+    @coerced
+    def __lt__(self, other):
+        """Sort VersionRanges lexicographically so that they are ordered first
+           by start and then by end.  None denotes an open range, so None in
+           the start position is less than everything except None, and None in
+           the end position is greater than everything but None.
+        """
+        if other is None:
+            return False
 
+        return (none_low_lt(self.start, other.start) or
+                (self.start == other.start and
+                 none_high_lt(self.end, other.end)))
 
+
+    @coerced
     def __eq__(self, other):
-        return (type(other) == VersionRange
-                and self.start == other.start
-                and self.end == other.end)
+        return (other is not None and
+                type(other) == VersionRange and
+                self.start == other.start and self.end == other.end)
 
 
     def __ne__(self, other):
         return not (self == other)
 
 
+    @property
+    def concrete(self):
+        return self.start if self.start == self.end else None
+
+
+    @coerced
+    def __contains__(self, other):
+        return (none_low_ge(other.start, self.start) and
+                none_high_le(other.end, self.end))
+
+
+    @coerced
+    def overlaps(self, other):
+        return (other in self or self in other or
+                ((self.start == None or other.end == None or
+                  self.start <= other.end) and
+                 (other.start == None or self.end == None or
+                  other.start <= self.end)))
+
+
+    @coerced
+    def merge(self, other):
+        return VersionRange(none_low_min(self.start, other.start),
+                            none_high_max(self.end, other.end))
+
+
+    def __hash__(self):
+        return hash((self.start, self.end))
+
+
     def __repr__(self):
         return self.__str__()
 
+
     def __str__(self):
         out = ""
         if self.start:
@@ -187,3 +316,179 @@ class VersionRange(object):
         if self.end:
             out += str(self.end)
         return out
+
+
+@total_ordering
+class VersionList(object):
+    """Sorted, non-redundant list of Versions and VersionRanges."""
+    def __init__(self, vlist=None):
+        self.versions = []
+        if vlist != None:
+            vlist = list(vlist)
+            for v in vlist:
+                self.add(ver(v))
+
+
+    def add(self, version):
+        if type(version) in (Version, VersionRange):
+            # This normalizes single-value version ranges.
+            if version.concrete:
+                version = version.concrete
+
+            i = bisect_left(self, version)
+
+            while i-1 >= 0 and version.overlaps(self[i-1]):
+                version = version.merge(self[i-1])
+                del self.versions[i-1]
+                i -= 1
+
+            while i < len(self) and version.overlaps(self[i]):
+                version = version.merge(self[i])
+                del self.versions[i]
+
+            self.versions.insert(i, version)
+
+        elif type(version) == VersionList:
+            for v in version:
+                self.add(v)
+
+        else:
+            raise TypeError("Can't add %s to VersionList" % type(version))
+
+
+    @property
+    def concrete(self):
+        if len(self) == 1:
+            return self[0].concrete
+        else:
+            return None
+
+
+    def copy(self):
+        return VersionList(self)
+
+
+    def lowest(self):
+        """Get the lowest version in the list."""
+        if not self:
+            return None
+        else:
+            return self[0].lowest()
+
+
+    def highest(self):
+        """Get the highest version in the list."""
+        if not self:
+            return None
+        else:
+            return self[-1].highest()
+
+
+    @coerced
+    def overlaps(self, other):
+        if not other or not self:
+            return False
+
+        i = o = 0
+        while i < len(self) and o < len(other):
+            if self[i].overlaps(other[o]):
+                return True
+            elif self[i] < other[o]:
+                i += 1
+            else:
+                o += 1
+        return False
+
+
+    @coerced
+    def merge(self, other):
+        return VersionList(self.versions + other.versions)
+
+
+    @coerced
+    def __contains__(self, other):
+        if len(self) == 0:
+            return False
+
+        for version in other:
+            i = bisect_left(self, other)
+            if i == 0:
+                if version not in self[0]:
+                    return False
+            elif all(version not in v for v in self[i-1:]):
+                return False
+
+        return True
+
+
+    def __getitem__(self, index):
+        return self.versions[index]
+
+
+    def __iter__(self):
+        for v in self.versions:
+            yield v
+
+
+    def __len__(self):
+        return len(self.versions)
+
+
+    @coerced
+    def __eq__(self, other):
+        return other is not None and self.versions == other.versions
+
+
+    def __ne__(self, other):
+        return not (self == other)
+
+
+    @coerced
+    def __lt__(self, other):
+        return other is not None and self.versions < other.versions
+
+
+    def __hash__(self):
+        return hash(tuple(self.versions))
+
+
+    def __str__(self):
+        return ",".join(str(v) for v in self.versions)
+
+
+    def __repr__(self):
+        return str(self.versions)
+
+
+def _string_to_version(string):
+    """Converts a string to a Version, VersionList, or VersionRange.
+       This is private.  Client code should use ver().
+    """
+    string = string.replace(' ','')
+
+    if ',' in string:
+        return VersionList(string.split(','))
+
+    elif ':' in string:
+        s, e = string.split(':')
+        start = Version(s) if s else None
+        end   = Version(e) if e else None
+        return VersionRange(start, end)
+
+    else:
+        return Version(string)
+
+
+def ver(obj):
+    """Parses a Version, VersionRange, or VersionList from a string
+       or list of strings.
+    """
+    t = type(obj)
+    if t == list:
+        return VersionList(obj)
+    elif t == str:
+        return _string_to_version(obj)
+    elif t in (Version, VersionRange, VersionList):
+        return obj
+    else:
+        raise TypeError("ver() can't convert %s to version!" % t)