Initial implementation of package specs, including parser.

spec.py can parse full dependence specs like this:
	openmpi@1.4.3:1.4.5%intel+debug ^hwloc@1.2

These will be used to specify how to install packages and their dependencies,
as well as to specify restrictions (e.g., on particular versions) for
dependencies.  e.g.:

class SomePackage(Package):
	depends_on('boost@1.46,1.49')

This would require either of those two versions of boost.

This also moves depends_on out to relations.py and adds
"provides", which will allow packages to provide virtual
dependences.

This is just initial implementation of the parsing and objects
to represent specs.  They're not integrated with packages yet.

10 files changed, 821 insertions, 76 deletions

diff --git a/lib/spack/spack/__init__.py b/lib/spack/spack/__init__.py
index 02af7db4f3..54a3e92a57 100644
--- a/lib/spack/spack/__init__.py
+++ b/lib/spack/spack/__init__.py
@@ -2,5 +2,6 @@ from globals import *
 from utils import *
 from error import *
 
-from package import Package, depends_on
+from package import Package
+from relations import depends_on, provides
 from multi_function import platform
diff --git a/lib/spack/spack/dependency.py b/lib/spack/spack/dependency.py
new file mode 100644
index 0000000000..ef87de7ce1
--- /dev/null
+++ b/lib/spack/spack/dependency.py
@@ -0,0 +1,20 @@
+"""
+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, version):
+        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/package.py b/lib/spack/spack/package.py
index 63bcf7a630..13da76c934 100644
--- a/lib/spack/spack/package.py
+++ b/lib/spack/spack/package.py
@@ -27,6 +27,7 @@ import arch
 
 from multi_function import platform
 from stage import Stage
+from dependency import *
 
 
 class Package(object):
@@ -228,14 +229,24 @@ class Package(object):
     clean() (some of them do this), and others to provide custom behavior.
     """
 
-    def __init__(self, sys_type=arch.sys_type()):
+    """By default a package has no dependencies."""
+    dependencies = []
+
+    """By default we build in parallel.  Subclasses can override this."""
+    parallel = True
+
+    """Remove tarball and build by default.  If this is true, leave them."""
+    dirty = False
+
+    """Controls whether install and uninstall check deps before running."""
+    ignore_dependencies = False
+
+    def __init__(self, sys_type = arch.sys_type()):
+        # Check for attributes that derived classes must set.
         attr.required(self, 'homepage')
         attr.required(self, 'url')
         attr.required(self, 'md5')
 
-        attr.setdefault(self, 'dependencies', [])
-        attr.setdefault(self, 'parallel', True)
-
         # Architecture for this package.
         self.sys_type = sys_type
 
@@ -258,15 +269,9 @@ class Package(object):
         # This adds a bunch of convenience commands to the package's module scope.
         self.add_commands_to_module()
 
-        # Controls whether install and uninstall check deps before acting.
-        self.ignore_dependencies = False
-
         # Empty at first; only compute dependents if necessary
         self._dependents = None
 
-        # Whether to remove intermediate build/install when things go wrong.
-        self.dirty = False
-
         # stage used to build this package.
         self.stage = Stage(self.stage_name, self.url)
 
@@ -569,37 +574,6 @@ class Package(object):
         tty.msg("Successfully cleaned %s" % self.name)
 
 
-class Dependency(object):
-    """Represents a dependency from one package to another."""
-    def __init__(self, name, **kwargs):
-        self.name = name
-        for key in kwargs:
-            setattr(self, key, kwargs[key])
-
-    @property
-    def package(self):
-        return packages.get(self.name)
-
-    def __repr__(self):
-        return "<dep: %s>" % self.name
-
-    def __str__(self):
-        return self.__repr__()
-
-
-def depends_on(*args, **kwargs):
-    """Adds a dependencies local variable in the locals of
-       the calling class, based on args.
-    """
-    # This gets the calling frame so we can pop variables into it
-    locals = sys._getframe(1).f_locals
-
-    # Put deps into the dependencies variable
-    dependencies = locals.setdefault("dependencies", [])
-    for name in args:
-        dependencies.append(Dependency(name))
-
-
 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 7a43fcb52f..d74bedb3a0 100644
--- a/lib/spack/spack/packages/__init__.py
+++ b/lib/spack/spack/packages/__init__.py
@@ -12,8 +12,8 @@ import spack.version as version
 import spack.attr as attr
 import spack.error as serr
 
-# Valid package names
-valid_package = r'^[a-zA-Z0-9_-]*$'
+# Valid package names -- can contain - but can't start with it.
+valid_package = r'^\w[\w-]*$'
 
 # Don't allow consecutive [_-] in package names
 invalid_package = r'[_-][_-]+'
diff --git a/lib/spack/spack/parse.py b/lib/spack/spack/parse.py
new file mode 100644
index 0000000000..f39def022f
--- /dev/null
+++ b/lib/spack/spack/parse.py
@@ -0,0 +1,95 @@
+import re
+import spack.error as err
+import itertools
+
+class UnlexableInputError(err.SpackError):
+    """Raised when we don't know how to lex something."""
+    def __init__(self, message):
+        super(UnlexableInputError, self).__init__(message)
+
+
+class ParseError(err.SpackError):
+    """Raised when we don't hit an error while parsing."""
+    def __init__(self, message):
+        super(ParseError, self).__init__(message)
+
+
+class Token:
+    """Represents tokens; generated from input by lexer and fed to parse()."""
+    def __init__(self, type, value=''):
+        self.type = type
+        self.value = value
+
+    def __repr__(self):
+        return str(self)
+
+    def __str__(self):
+        return "'%s'" % self.value
+
+    def is_a(self, type):
+        return self.type == type
+
+    def __cmp__(self, other):
+        return cmp((self.type, self.value),
+                   (other.type, other.value))
+
+class Lexer(object):
+    """Base class for Lexers that keep track of line numbers."""
+    def __init__(self, lexicon):
+        self.scanner = re.Scanner(lexicon)
+
+    def token(self, type, value=''):
+        return Token(type, value)
+
+    def lex(self, text):
+        tokens, remainder = self.scanner.scan(text)
+        if remainder:
+            raise UnlexableInputError("Unlexable input:\n%s\n" % remainder)
+        return tokens
+
+
+class Parser(object):
+    """Base class for simple recursive descent parsers."""
+    def __init__(self, lexer):
+        self.tokens = iter([]) # iterators over tokens, handled in order.  Starts empty.
+        self.token = None      # last accepted token
+        self.next = None       # next token
+        self.lexer = lexer
+
+    def gettok(self):
+        """Puts the next token in the input stream into self.next."""
+        try:
+            self.next = self.tokens.next()
+        except StopIteration:
+            self.next = None
+
+    def push_tokens(self, iterable):
+        """Adds all tokens in some iterable to the token stream."""
+        self.tokens = itertools.chain(iter(iterable), iter([self.next]), self.tokens)
+        self.gettok()
+
+    def accept(self, id):
+        """Puts the next symbol in self.token if we like it.  Then calls gettok()"""
+        if self.next and self.next.is_a(id):
+            self.token = self.next
+            self.gettok()
+            return True
+        return False
+
+    def unexpected_token(self):
+        raise ParseError("Unexpected token: %s." % self.next)
+
+    def expect(self, id):
+        """Like accept(), but fails if we don't like the next token."""
+        if self.accept(id):
+            return True
+        else:
+            if self.next:
+                self.unexpected_token()
+            else:
+                raise ParseError("Unexpected end of file.")
+            sys.exit(1)
+
+    def parse(self, text):
+        self.push_tokens(self.lexer.lex(text))
+        return self.do_parse()
diff --git a/lib/spack/spack/relations.py b/lib/spack/spack/relations.py
new file mode 100644
index 0000000000..052a509cb7
--- /dev/null
+++ b/lib/spack/spack/relations.py
@@ -0,0 +1,70 @@
+"""
+This package contains relationships that can be defined among packages.
+Relations are functions that can be called inside a package definition,
+for example:
+
+    class OpenMPI(Package):
+        depends_on("hwloc")
+        provides("mpi")
+        ...
+
+The available relations are:
+
+depends_on
+    Above, the OpenMPI package declares that it "depends on" hwloc.  This means
+    that the hwloc package needs to be installed before OpenMPI can be
+    installed.  When a user runs 'spack install openmpi', spack will fetch
+    hwloc and install it first.
+
+provides
+    This is useful when more than one package can satisfy a dependence.  Above,
+    OpenMPI declares that it "provides" mpi.  Other implementations of the MPI
+    interface, like mvapich and mpich, also provide mpi, e.g.:
+
+        class Mvapich(Package):
+            provides("mpi")
+            ...
+
+        class Mpich(Package):
+            provides("mpi")
+            ...
+
+    Instead of depending on openmpi, mvapich, or mpich, another package can
+    declare that it depends on "mpi":
+
+        class Mpileaks(Package):
+            depends_on("mpi")
+            ...
+
+    Now the user can pick which MPI they would like to build with when they
+    install mpileaks.  For example, the user could install 3 instances of
+    mpileaks, one for each MPI version, by issuing these three commands:
+
+        spack install mpileaks ^openmpi
+        spack install mpileaks ^mvapich
+        spack install mpileaks ^mpich
+"""
+from dependency import Dependency
+
+
+def depends_on(*args):
+    """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))
+
+
+def provides(*args):
+    """Allows packages to provide a virtual dependency.  If a package provides
+       "mpi", other packages can declare that they depend on "mpi", and spack
+       can use the providing package to satisfy the dependency.
+    """
+    # Get the enclosing package's scope and add deps to it.
+    locals = sys._getframe(1).f_locals
+    provides = locals.setdefault("provides", [])
+    for name in args:
+        provides.append(name)
diff --git a/lib/spack/spack/spec.py b/lib/spack/spack/spec.py
new file mode 100644
index 0000000000..a04d397e50
--- /dev/null
+++ b/lib/spack/spack/spec.py
@@ -0,0 +1,235 @@
+"""
+Spack allows very fine-grained control over how packages are installed and
+over how they are built and configured.  To make this easy, it has its own
+syntax for declaring a dependence.  We call a descriptor of a particular
+package configuration a "spec".
+
+The syntax looks like this:
+
+    spack install mpileaks ^openmpi @1.2:1.4 +debug %intel @12.1
+                  0        1        2        3      4      5
+
+The first part of this is the command, 'spack install'.  The rest of the
+line is a spec for a particular installation of the mpileaks package.
+
+0. The package to install
+
+1. A dependency of the package, prefixed by ^
+
+2. A version descriptor for the package.  This can either be a specific
+   version, like "1.2", or it can be a range of versions, e.g. "1.2:1.4".
+   If multiple specific versions or multiple ranges are acceptable, they
+   can be separated by commas, e.g. if a package will only build with
+   versions 1.0, 1.2-1.4, and 1.6-1.8 of mavpich, you could say:
+
+       depends_on("mvapich@1.0,1.2:1.4,1.6:1.8")
+
+3. A compile-time variant of the package.  If you need openmpi to be
+   built in debug mode for your package to work, you can require it by
+   adding +debug to the openmpi spec when you depend on it.  If you do
+   NOT want the debug option to be enabled, then replace this with -debug.
+
+4. The name of the compiler to build with.
+
+5. The versions of the compiler to build with.  Note that the identifier
+   for a compiler version is the same '@' that is used for a package version.
+   A version list denoted by '@' is associated with the compiler only if
+   if it comes immediately after the compiler name.  Otherwise it will be
+   associated with the current package spec.
+"""
+from functools import total_ordering
+
+import spack.parse
+from spack.version import Version, VersionRange
+import spack.error
+
+
+class DuplicateDependenceError(spack.error.SpackError):
+    """Raised when the same dependence occurs in a spec twice."""
+    def __init__(self, message):
+        super(DuplicateDependenceError, self).__init__(message)
+
+class DuplicateVariantError(spack.error.SpackError):
+    """Raised when the same variant occurs in a spec twice."""
+    def __init__(self, message):
+        super(VariantVariantError, self).__init__(message)
+
+class DuplicateCompilerError(spack.error.SpackError):
+    """Raised when the same compiler occurs in a spec twice."""
+    def __init__(self, message):
+        super(DuplicateCompilerError, self).__init__(message)
+
+
+class Compiler(object):
+    def __init__(self, name):
+        self.name = name
+        self.versions = []
+
+    def add_version(self, version):
+        self.versions.append(version)
+
+    def __str__(self):
+        out = "%%%s" % self.name
+        if self.versions:
+            vlist = ",".join(str(v) for v in sorted(self.versions))
+            out += "@%s" % vlist
+        return out
+
+
+class Spec(object):
+    def __init__(self, name):
+        self.name = name
+        self.versions = []
+        self.variants = {}
+        self.compiler = None
+        self.dependencies = {}
+
+    def add_version(self, version):
+        self.versions.append(version)
+
+    def add_variant(self, name, enabled):
+        self.variants[name] = enabled
+
+    def add_compiler(self, compiler):
+        self.compiler = compiler
+
+    def add_dependency(self, dep):
+        if dep.name in self.dependencies:
+            raise ValueError("Cannot depend on %s twice" % dep)
+        self.dependencies[dep.name] = dep
+
+    def __str__(self):
+        out = self.name
+
+        if self.versions:
+            vlist = ",".join(str(v) for v in sorted(self.versions))
+            out += "@%s" % vlist
+
+        if self.compiler:
+            out += str(self.compiler)
+
+        for name in sorted(self.variants.keys()):
+            enabled = self.variants[name]
+            if enabled:
+                out += '+%s' % name
+            else:
+                out += '~%s' % name
+
+        for name in sorted(self.dependencies.keys()):
+            out += " ^%s" % str(self.dependencies[name])
+
+        return out
+
+#
+# These are possible token types in the spec grammar.
+#
+DEP, AT, COLON, COMMA, ON, OFF, PCT, ID = range(8)
+
+class SpecLexer(spack.parse.Lexer):
+    """Parses tokens that make up spack specs."""
+    def __init__(self):
+        super(SpecLexer, self).__init__([
+            (r'\^',        lambda scanner, val: self.token(DEP,   val)),
+            (r'\@',        lambda scanner, val: self.token(AT,    val)),
+            (r'\:',        lambda scanner, val: self.token(COLON, val)),
+            (r'\,',        lambda scanner, val: self.token(COMMA, val)),
+            (r'\+',        lambda scanner, val: self.token(ON,    val)),
+            (r'\-',        lambda scanner, val: self.token(OFF,   val)),
+            (r'\~',        lambda scanner, val: self.token(OFF,   val)),
+            (r'\%',        lambda scanner, val: self.token(PCT,   val)),
+            (r'\w[\w.-]*', lambda scanner, val: self.token(ID,    val)),
+            (r'\s+',       lambda scanner, val: None)])
+
+class SpecParser(spack.parse.Parser):
+    def __init__(self):
+        super(SpecParser, self).__init__(SpecLexer())
+
+    def spec(self):
+        self.expect(ID)
+        self.check_identifier()
+
+        spec = Spec(self.token.value)
+        while self.next:
+            if self.accept(DEP):
+                dep = self.spec()
+                spec.add_dependency(dep)
+
+            elif self.accept(AT):
+                vlist = self.version_list()
+                for version in vlist:
+                    spec.add_version(version)
+
+            elif self.accept(ON):
+                self.expect(ID)
+                self.check_identifier()
+                spec.add_variant(self.token.value, True)
+
+            elif self.accept(OFF):
+                self.expect(ID)
+                self.check_identifier()
+                spec.add_variant(self.token.value, False)
+
+            elif self.accept(PCT):
+                spec.add_compiler(self.compiler())
+
+            else:
+                self.unexpected_token()
+
+        return spec
+
+
+    def version(self):
+        start = None
+        end = None
+        if self.accept(ID):
+            start = self.token.value
+
+        if self.accept(COLON):
+            if self.accept(ID):
+                end = self.token.value
+        else:
+            return Version(start)
+
+        if not start and not end:
+            raise ParseError("Lone colon: version range needs at least one version.")
+        else:
+            if start: start = Version(start)
+            if end: end = Version(end)
+            return VersionRange(start, end)
+
+
+    def version_list(self):
+        vlist = []
+        while True:
+            vlist.append(self.version())
+            if not self.accept(COMMA):
+                break
+        return vlist
+
+
+    def compiler(self):
+        self.expect(ID)
+        self.check_identifier()
+        compiler = Compiler(self.token.value)
+        if self.accept(AT):
+            vlist = self.version_list()
+            for version in vlist:
+                compiler.add_version(version)
+        return compiler
+
+
+    def check_identifier(self):
+        """The only identifiers that can contain '.' are versions, but version
+           ids are context-sensitive so we have to check on a case-by-case
+           basis. Call this if we detect a version id where it shouldn't be.
+        """
+        if '.' in self.token.value:
+            raise spack.parse.ParseError(
+                "Non-version identifier cannot contain '.'")
+
+
+    def do_parse(self):
+        specs = []
+        while self.next:
+            specs.append(self.spec())
+        return specs
diff --git a/lib/spack/spack/test/compare_versions.py b/lib/spack/spack/test/compare_versions.py
new file mode 100644
index 0000000000..5513da6915
--- /dev/null
+++ b/lib/spack/spack/test/compare_versions.py
@@ -0,0 +1,140 @@
+"""
+These version tests were taken from the RPM source code.
+We try to maintain compatibility with RPM's version semantics
+where it makes sense.
+"""
+import unittest
+from spack.version import *
+
+
+class CompareVersionsTest(unittest.TestCase):
+
+    def assert_ver_lt(self, a, b):
+        a, b = ver(a), ver(b)
+        self.assertTrue(a < b)
+        self.assertTrue(a <= b)
+        self.assertTrue(a != b)
+        self.assertFalse(a == b)
+        self.assertFalse(a > b)
+        self.assertFalse(a >= b)
+
+
+    def assert_ver_gt(self, a, b):
+        a, b = ver(a), ver(b)
+        self.assertTrue(a > b)
+        self.assertTrue(a >= b)
+        self.assertTrue(a != b)
+        self.assertFalse(a == b)
+        self.assertFalse(a < b)
+        self.assertFalse(a <= b)
+
+
+    def assert_ver_eq(self, a, b):
+        a, b = ver(a), ver(b)
+        self.assertFalse(a > b)
+        self.assertTrue(a >= b)
+        self.assertFalse(a != b)
+        self.assertTrue(a == b)
+        self.assertFalse(a < b)
+        self.assertTrue(a <= b)
+
+
+    def test_two_segments(self):
+        self.assert_ver_eq('1.0', '1.0')
+        self.assert_ver_lt('1.0', '2.0')
+        self.assert_ver_gt('2.0', '1.0')
+
+
+    def test_three_segments(self):
+        self.assert_ver_eq('2.0.1', '2.0.1')
+        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
+        # TODO: comparison complicated.  See version.py
+        self.assert_ver_eq('2.0.1a', '2.0.1a')
+        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')
+        self.assert_ver_gt('5.5p2',  '5.5p1')
+        self.assert_ver_eq('5.5p10', '5.5p10')
+        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')
+        self.assert_ver_eq('xyz10',   'xyz10')
+        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')
+        self.assert_ver_gt('8',     'xyz.4')
+        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')
+        self.assert_ver_eq('10.1',    '10.0001')
+        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')
+        self.assert_ver_gt('1.fc17',  '1b.fc17')
+        self.assert_ver_eq('1g.fc17', '1g.fc17')
+        self.assert_ver_gt('1g.fc17', '1.fc17')
+        self.assert_ver_lt('1.fc17',  '1g.fc17')
+
+
+    # Stuff below here is not taken from RPM's tests.
+    def test_version_ranges(self):
+        self.assert_ver_lt('1.2:1.4', '1.6')
+        self.assert_ver_gt('1.6', '1.2:1.4')
+        self.assert_ver_eq('1.2:1.4', '1.2:1.4')
+        self.assertNotEqual(ver('1.2:1.4'), ver('1.2:1.6'))
+
+        self.assert_ver_lt('1.2:1.4', '1.5:1.6')
+        self.assert_ver_gt('1.5:1.6', '1.2:1.4')
diff --git a/lib/spack/spack/test/specs.py b/lib/spack/spack/test/specs.py
new file mode 100644
index 0000000000..89c7844a71
--- /dev/null
+++ b/lib/spack/spack/test/specs.py
@@ -0,0 +1,126 @@
+import unittest
+from spack.spec import *
+from spack.parse import *
+
+# Sample output for a complex lexing.
+complex_lex = [Token(ID, 'mvapich_foo'),
+               Token(DEP),
+               Token(ID, '_openmpi'),
+               Token(AT),
+               Token(ID, '1.2'),
+               Token(COLON),
+               Token(ID, '1.4'),
+               Token(COMMA),
+               Token(ID, '1.6'),
+               Token(PCT),
+               Token(ID, 'intel'),
+               Token(AT),
+               Token(ID, '12.1'),
+               Token(COLON),
+               Token(ID, '12.6'),
+               Token(ON),
+               Token(ID, 'debug'),
+               Token(OFF),
+               Token(ID, 'qt_4'),
+               Token(DEP),
+               Token(ID, 'stackwalker'),
+               Token(AT),
+               Token(ID, '8.1_1e')]
+
+
+class SpecTest(unittest.TestCase):
+    def setUp(self):
+        self.parser = SpecParser()
+        self.lexer = SpecLexer()
+
+    # ================================================================================
+    # Parse checks
+    # ================================================================================
+    def check_parse(self, expected, spec=None):
+        """Assert that the provided spec is able to be parsed.
+           If this is called with one argument, it assumes that the string is
+           canonical (i.e., no spaces and ~ instead of - for variants) and that it
+           will convert back to the string it came from.
+
+           If this is called with two arguments, the first argument is the expected
+           canonical form and the second is a non-canonical input to be parsed.
+        """
+        if spec == None:
+            spec = expected
+        output = self.parser.parse(spec)
+        self.assertEqual(len(output), 1)
+        self.assertEqual(str(output[0]), spec)
+
+
+    def check_lex(self, tokens, spec):
+        """Check that the provided spec parses to the provided list of tokens."""
+        lex_output = self.lexer.lex(spec)
+        for tok, spec_tok in zip(tokens, lex_output):
+            if tok.type == ID:
+                self.assertEqual(tok, spec_tok)
+            else:
+                # Only check the type for non-identifiers.
+                self.assertEqual(tok.type, spec_tok.type)
+
+    # ================================================================================
+    # Parse checks
+    # ===============================================================================
+    def test_package_names(self):
+        self.check_parse("mvapich")
+        self.check_parse("mvapich_foo")
+        self.check_parse("_mvapich_foo")
+
+    def test_simple_dependence(self):
+        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")
+
+    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")
+
+    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")
+
+    # ================================================================================
+    # Lex checks
+    # ================================================================================
+    def test_ambiguous(self):
+        # This first one is ambiguous because - can be in an identifier AND
+        # indicate disabling an option.
+        self.assertRaises(
+            AssertionError, self.check_lex, complex_lex,
+            "mvapich_foo^_openmpi@1.2:1.4,1.6%intel@12.1:12.6+debug-qt_4^stackwalker@8.1_1e")
+
+    # The following lexes are non-ambiguous (add a space before -qt_4) and should all
+    # result in the tokens in complex_lex
+    def test_minimal_spaces(self):
+        self.check_lex(
+            complex_lex,
+            "mvapich_foo^_openmpi@1.2:1.4,1.6%intel@12.1:12.6+debug -qt_4^stackwalker@8.1_1e")
+        self.check_lex(
+            complex_lex,
+            "mvapich_foo^_openmpi@1.2:1.4,1.6%intel@12.1:12.6+debug~qt_4^stackwalker@8.1_1e")
+
+    def test_spaces_between_dependences(self):
+        self.check_lex(
+            complex_lex,
+            "mvapich_foo ^_openmpi@1.2:1.4,1.6%intel@12.1:12.6+debug -qt_4 ^stackwalker @ 8.1_1e")
+        self.check_lex(
+            complex_lex,
+            "mvapich_foo ^_openmpi@1.2:1.4,1.6%intel@12.1:12.6+debug~qt_4 ^stackwalker @ 8.1_1e")
+
+    def test_spaces_between_options(self):
+        self.check_lex(
+            complex_lex,
+            "mvapich_foo ^_openmpi @1.2:1.4,1.6 %intel @12.1:12.6 +debug -qt_4 ^stackwalker @8.1_1e")
+
+    def test_way_too_many_spaces(self):
+        self.check_lex(
+            complex_lex,
+            "mvapich_foo ^ _openmpi @ 1.2 : 1.4 , 1.6 % intel @ 12.1 : 12.6 + debug - qt_4 ^ stackwalker @ 8.1_1e")
diff --git a/lib/spack/spack/version.py b/lib/spack/spack/version.py
index e35dfe7297..14e1083722 100644
--- a/lib/spack/spack/version.py
+++ b/lib/spack/spack/version.py
@@ -1,37 +1,38 @@
 import os
 import re
+from functools import total_ordering
 
 import utils
 import spack.error as serr
 
 
-class Version(object):
-    """Class to represent versions"""
-    def __init__(self, version_string):
-        self.version_string = version_string
-        self.version = canonical(version_string)
+def int_if_int(string):
+    """Convert a string to int if possible.  Otherwise, return a string."""
+    try:
+        return int(string)
+    except:
+        return string
 
-    def __cmp__(self, other):
-        return cmp(self.version, other.version)
 
-    @property
-    def major(self):
-        return self.component(0)
+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))
+    else:
+        return Version(string)
 
-    @property
-    def minor(self):
-        return self.component(1)
 
-    @property
-    def patch(self):
-        return self.component(2)
+@total_ordering
+class Version(object):
+    """Class to represent versions"""
+    def __init__(self, version_string):
+        # preserve the original string
+        self.version_string = version_string
 
-    def component(self, i):
-        """Returns the ith version component"""
-        if len(self.version) > i:
-            return self.version[i]
-        else:
-            return None
+        # Split version into alphabetical and numeric segments
+        segments = re.findall(r'[a-zA-Z]+|[0-9]+', version_string)
+        self.version = tuple(int_if_int(seg) for seg in segments)
 
     def up_to(self, index):
         """Return a version string up to the specified component, exclusive.
@@ -48,16 +49,99 @@ class Version(object):
     def __str__(self):
         return self.version_string
 
+    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
+
+        # simple equality test first.
+        if self.version == other.version:
+            return False
+
+        for a, b in zip(self.version, other.version):
+            if a == b:
+                continue
+            else:
+                # Numbers are always "newer" than letters.  This is for
+                # consistency with RPM.  See patch #60884 (and details)
+                # from bugzilla #50977 in the RPM project at rpm.org.
+                # Or look at rpmvercmp.c if you want to see how this is
+                # implemented there.
+                if type(a) != type(b):
+                    return type(b) == int
+                else:
+                    return a < b
+
+        # If the common prefix is equal, the one with more segments is bigger.
+        return len(self.version) < len(other.version)
+
+    def __eq__(self, other):
+        """Implemented to match __lt__.  See __lt__."""
+        if type(other) == VersionRange:
+            return False
+        return self.version == other.version
+
+    def __ne__(self, other):
+        return not (self == other)
+
+
+@total_ordering
+class VersionRange(object):
+    def __init__(self, start, end=None):
+        if type(start) == str:
+            start = Version(start)
+        if type(end) == str:
+            end = Version(end)
+
+        self.start = start
+        self.end = end
+        if start and end and  end < start:
+            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 __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 canonical(v):
-    """Get a "canonical" version of a version string, as a tuple."""
-    def intify(part):
-        try:
-            return int(part)
-        except:
-            return part
+    def __eq__(self, other):
+        return (type(other) == VersionRange
+                and self.start == other.start
+                and self.end == other.end)
 
-    return tuple(intify(v) for v in re.split(r'[_.-]+', v))
+
+    def __ne__(self, other):
+        return not (self == other)
+
+
+    def __str__(self):
+        out = ""
+        if self.start:
+            out += str(self.start)
+        out += ":"
+        if self.end:
+            out += str(self.end)
+        return out
 
 
 class VersionParseError(serr.SpackError):
@@ -158,7 +242,7 @@ def parse_version_string_with_indices(spec):
 
 
 def parse_version(spec):
-    """Given a URL or archive name, extract a versino from it and return
+    """Given a URL or archive name, extract a version from it and return
        a version object.
     """
     ver, start, end = parse_version_string_with_indices(spec)
@@ -175,7 +259,7 @@ def create_version_format(spec):
 
 def replace_version(spec, new_version):
     version = create_version_format(spec)
-
+    # TODO: finish this function.
 
 def parse_name(spec, ver=None):
     if ver is None: