Multi-valued variants (#2386)

Modifications:
- added support for multi-valued variants
- refactored code related to variants into variant.py
- added new generic features to AutotoolsPackage that leverage multi-valued variants
- modified openmpi to use new features
- added unit tests for the new semantics

16 files changed, 1703 insertions, 187 deletions

diff --git a/lib/spack/llnl/util/lang.py b/lib/spack/llnl/util/lang.py
index 4943c9df67..9821ec7416 100644
--- a/lib/spack/llnl/util/lang.py
+++ b/lib/spack/llnl/util/lang.py
@@ -266,10 +266,28 @@ def key_ordering(cls):
 
 
 @key_ordering
-class HashableMap(dict):
+class HashableMap(collections.MutableMapping):
     """This is a hashable, comparable dictionary.  Hash is performed on
        a tuple of the values in the dictionary."""
 
+    def __init__(self):
+        self.dict = {}
+
+    def __getitem__(self, key):
+        return self.dict[key]
+
+    def __setitem__(self, key, value):
+        self.dict[key] = value
+
+    def __iter__(self):
+        return iter(self.dict)
+
+    def __len__(self):
+        return len(self.dict)
+
+    def __delitem__(self, key):
+        del self.dict[key]
+
     def _cmp_key(self):
         return tuple(sorted(self.values()))
 
diff --git a/lib/spack/llnl/util/tty/__init__.py b/lib/spack/llnl/util/tty/__init__.py
index e5c3ba8110..b28ac22c1f 100644
--- a/lib/spack/llnl/util/tty/__init__.py
+++ b/lib/spack/llnl/util/tty/__init__.py
@@ -22,22 +22,22 @@
 # License along with this program; if not, write to the Free Software
 # Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 ##############################################################################
-import sys
-import os
-import textwrap
 import fcntl
-import termios
+import os
 import struct
+import sys
+import termios
+import textwrap
 import traceback
 from six import StringIO
 from six.moves import input
 
 from llnl.util.tty.color import *
 
-_debug   = False
+_debug = False
 _verbose = False
 _stacktrace = False
-indent  = "  "
+indent = "  "
 
 
 def is_verbose():
@@ -100,7 +100,7 @@ def msg(message, *args, **kwargs):
 def info(message, *args, **kwargs):
     format = kwargs.get('format', '*b')
     stream = kwargs.get('stream', sys.stdout)
-    wrap   = kwargs.get('wrap', False)
+    wrap = kwargs.get('wrap', False)
     break_long_words = kwargs.get('break_long_words', False)
     st_countback = kwargs.get('countback', 3)
 
@@ -218,7 +218,7 @@ def hline(label=None, **kwargs):
         char (str): Char to draw the line with.  Default '-'
         max_width (int): Maximum width of the line.  Default is 64 chars.
     """
-    char      = kwargs.pop('char', '-')
+    char = kwargs.pop('char', '-')
     max_width = kwargs.pop('max_width', 64)
     if kwargs:
         raise TypeError(
diff --git a/lib/spack/spack/build_systems/autotools.py b/lib/spack/spack/build_systems/autotools.py
index ffd00e7f69..2e4c86ea3e 100644
--- a/lib/spack/spack/build_systems/autotools.py
+++ b/lib/spack/spack/build_systems/autotools.py
@@ -289,6 +289,51 @@ class AutotoolsPackage(PackageBase):
             self._if_make_target_execute('test')
             self._if_make_target_execute('check')
 
+    def _activate_or_not(self, active, inactive, name, active_parameters=None):
+        spec = self.spec
+        args = []
+        # For each allowed value in the list of values
+        for value in self.variants[name].values:
+            # Check if the value is active in the current spec
+            condition = '{name}={value}'.format(name=name, value=value)
+            activated = condition in spec
+            # Search for an override in the package for this value
+            override_name = '{0}_or_{1}_{2}'.format(active, inactive, value)
+            line_generator = getattr(self, override_name, None)
+            # If not available use a sensible default
+            if line_generator is None:
+                def _default_generator(is_activated):
+                    if is_activated:
+                        line = '--{0}-{1}'.format(active, value)
+                        if active_parameters is not None and active_parameters(value):  # NOQA=ignore=E501
+                            line += '={0}'.format(active_parameters(value))
+                        return line
+                    return '--{0}-{1}'.format(inactive, value)
+                line_generator = _default_generator
+            args.append(line_generator(activated))
+        return args
+
+    def with_or_without(self, name, active_parameters=None):
+        """Inspects the multi-valued variant 'name' and returns the configure
+        arguments that activate / deactivate the selected feature.
+
+        :param str name: name of a valid multi-valued variant
+        :param callable active_parameters: if present accepts a single value
+            and returns the parameter to be used leading to an entry of the
+            type '--with-{name}={parameter}
+        """
+        return self._activate_or_not(
+            'with', 'without', name, active_parameters
+        )
+
+    def enable_or_disable(self, name, active_parameters=None):
+        """Inspects the multi-valued variant 'name' and returns the configure
+        arguments that activate / deactivate the selected feature.
+        """
+        return self._activate_or_not(
+            'enable', 'disable', name, active_parameters
+        )
+
     run_after('install')(PackageBase._run_default_install_time_test_callbacks)
 
     def installcheck(self):
diff --git a/lib/spack/spack/cmd/info.py b/lib/spack/spack/cmd/info.py
index 799471ffcc..86ec839b90 100644
--- a/lib/spack/spack/cmd/info.py
+++ b/lib/spack/spack/cmd/info.py
@@ -25,7 +25,7 @@
 from __future__ import print_function
 
 import textwrap
-
+import itertools
 from llnl.util.tty.colify import *
 import spack
 import spack.fetch_strategy as fs
@@ -49,6 +49,81 @@ def setup_parser(subparser):
         'name', metavar="PACKAGE", help="name of package to get info for")
 
 
+class VariantFormatter(object):
+    def __init__(self, variants, max_widths=(25, 20, 35)):
+        self.variants = variants
+        self.headers = ('Name [Default]', 'Allowed values', 'Description')
+        # Set max headers lengths
+        self.max_column_widths = max_widths
+
+        # Formats
+        fmt_name = '{0} [{1}]'
+
+        # Initialize column widths with the length of the
+        # corresponding headers, as they cannot be shorter
+        # than that
+        self.column_widths = [len(x) for x in self.headers]
+
+        # Update according to line lengths
+        for k, v in variants.items():
+            candidate_max_widths = (
+                len(fmt_name.format(k, self.default(v))),  # Name [Default]
+                len(v.allowed_values),  # Allowed values
+                len(v.description)  # Description
+            )
+
+            self.column_widths = (
+                max(self.column_widths[0], candidate_max_widths[0]),
+                max(self.column_widths[1], candidate_max_widths[1]),
+                max(self.column_widths[2], candidate_max_widths[2])
+            )
+
+        # Reduce to at most the maximum allowed
+        self.column_widths = (
+            min(self.column_widths[0], self.max_column_widths[0]),
+            min(self.column_widths[1], self.max_column_widths[1]),
+            min(self.column_widths[2], self.max_column_widths[2])
+        )
+
+        # Compute the format
+        self.fmt = "%%-%ss%%-%ss%%s" % (
+            self.column_widths[0] + 4,
+            self.column_widths[1] + 4
+        )
+
+    def default(self, v):
+        s = 'on' if v.default is True else 'off'
+        if not isinstance(v.default, bool):
+            s = v.default
+        return s
+
+    @property
+    def lines(self):
+        if not self.variants:
+            yield "    None"
+        else:
+            yield "    " + self.fmt % self.headers
+            yield '\n'
+            for k, v in sorted(self.variants.items()):
+                name = textwrap.wrap(
+                    '{0} [{1}]'.format(k, self.default(v)),
+                    width=self.column_widths[0]
+                )
+                allowed = textwrap.wrap(
+                    v.allowed_values,
+                    width=self.column_widths[1]
+                )
+                description = textwrap.wrap(
+                    v.description,
+                    width=self.column_widths[2]
+                )
+                for t in itertools.izip_longest(
+                        name, allowed, description, fillvalue=''
+                ):
+                    yield "    " + self.fmt % t
+                yield ''  # Trigger a new line
+
+
 def print_text_info(pkg):
     """Print out a plain text description of a package."""
     header = "{0}:   ".format(pkg.build_system_class)
@@ -70,25 +145,10 @@ def print_text_info(pkg):
 
     print()
     print("Variants:")
-    if not pkg.variants:
-        print("    None")
-    else:
-        pad = padder(pkg.variants, 4)
-
-        maxv = max(len(v) for v in sorted(pkg.variants))
-        fmt = "%%-%ss%%-10s%%s" % (maxv + 4)
-
-        print("    " + fmt % ('Name',   'Default',   'Description'))
-        print()
-        for name in sorted(pkg.variants):
-            v = pkg.variants[name]
-            default = 'on' if v.default else 'off'
-
-            lines = textwrap.wrap(v.description)
-            lines[1:] = ["      " + (" " * maxv) + l for l in lines[1:]]
-            desc = "\n".join(lines)
 
-            print("    " + fmt % (name, default, desc))
+    formatter = VariantFormatter(pkg.variants)
+    for line in formatter.lines:
+        print(line)
 
     print()
     print("Installation Phases:")
diff --git a/lib/spack/spack/cmd/spec.py b/lib/spack/spack/cmd/spec.py
index d89707f230..2e917d2ee3 100644
--- a/lib/spack/spack/cmd/spec.py
+++ b/lib/spack/spack/cmd/spec.py
@@ -69,7 +69,8 @@ def spec(parser, args):
     for spec in spack.cmd.parse_specs(args.specs):
         # With -y, just print YAML to output.
         if args.yaml:
-            spec.concretize()
+            if spec.name in spack.repo:
+                spec.concretize()
             print(spec.to_yaml())
             continue
 
diff --git a/lib/spack/spack/concretize.py b/lib/spack/spack/concretize.py
index 5507b599ff..d7f21e8c81 100644
--- a/lib/spack/spack/concretize.py
+++ b/lib/spack/spack/concretize.py
@@ -245,14 +245,15 @@ class DefaultConcretizer(object):
         """
         changed = False
         preferred_variants = PackagePrefs.preferred_variants(spec.name)
-        for name, variant in spec.package_class.variants.items():
+        pkg_cls = spec.package_class
+        for name, variant in pkg_cls.variants.items():
             if name not in spec.variants:
                 changed = True
                 if name in preferred_variants:
                     spec.variants[name] = preferred_variants.get(name)
                 else:
-                    spec.variants[name] = spack.spec.VariantSpec(
-                        name, variant.default)
+                    spec.variants[name] = variant.make_default()
+
         return changed
 
     def concretize_compiler(self, spec):
diff --git a/lib/spack/spack/directives.py b/lib/spack/spack/directives.py
index 7a245f606c..43ac71c679 100644
--- a/lib/spack/spack/directives.py
+++ b/lib/spack/spack/directives.py
@@ -368,9 +368,37 @@ def patch(url_or_filename, level=1, when=None, **kwargs):
 
 
 @directive('variants')
-def variant(name, default=False, description=""):
+def variant(
+        name,
+        default=None,
+        description='',
+        values=(True, False),
+        multi=False,
+        validator=None
+):
     """Define a variant for the package. Packager can specify a default
-    value (on or off) as well as a text description."""
+    value as well as a text description.
+
+    Args:
+        name (str): name of the variant
+        default (str or bool): default value for the variant, if not
+            specified otherwise the default will be False for a boolean
+            variant and 'nothing' for a multi-valued variant
+        description (str): description of the purpose of the variant
+        values (tuple or callable): either a tuple of strings containing the
+            allowed values, or a callable accepting one value and returning
+            True if it is valid
+        multi (bool): if False only one value per spec is allowed for
+            this variant
+        validator (callable): optional group validator to enforce additional
+            logic. It receives a tuple of values and should raise an instance
+            of SpackError if the group doesn't meet the additional constraints
+    """
+
+    if default is None:
+        default = False if values == (True, False) else ''
+
+    default = default
     description = str(description).strip()
 
     def _execute(pkg):
@@ -379,7 +407,9 @@ def variant(name, default=False, description=""):
             msg = "Invalid variant name in {0}: '{1}'"
             raise DirectiveError(directive, msg.format(pkg.name, name))
 
-        pkg.variants[name] = Variant(default, description)
+        pkg.variants[name] = Variant(
+            name, default, description, values, multi, validator
+        )
     return _execute
 
 
diff --git a/lib/spack/spack/error.py b/lib/spack/spack/error.py
index cd1ae5b25c..09969b2b41 100644
--- a/lib/spack/spack/error.py
+++ b/lib/spack/spack/error.py
@@ -100,3 +100,18 @@ class NoNetworkConnectionError(SpackError):
             "No network connection: " + str(message),
             "URL was: " + str(url))
         self.url = url
+
+
+class SpecError(SpackError):
+    """Superclass for all errors that occur while constructing specs."""
+
+
+class UnsatisfiableSpecError(SpecError):
+    """Raised when a spec conflicts with package constraints.
+       Provide the requirement that was violated when raising."""
+    def __init__(self, provided, required, constraint_type):
+        super(UnsatisfiableSpecError, self).__init__(
+            "%s does not satisfy %s" % (provided, required))
+        self.provided = provided
+        self.required = required
+        self.constraint_type = constraint_type
diff --git a/lib/spack/spack/spec.py b/lib/spack/spack/spec.py
index 0d8fb2893b..0cf392a7ce 100644
--- a/lib/spack/spack/spec.py
+++ b/lib/spack/spack/spec.py
@@ -121,12 +121,14 @@ from llnl.util.filesystem import find_headers, find_libraries, is_exe
 from llnl.util.lang import *
 from llnl.util.tty.color import *
 from spack.build_environment import get_path_from_module, load_module
+from spack.error import SpecError, UnsatisfiableSpecError
 from spack.provider_index import ProviderIndex
 from spack.util.crypto import prefix_bits
 from spack.util.executable import Executable
 from spack.util.prefix import Prefix
 from spack.util.spack_yaml import syaml_dict
 from spack.util.string import *
+from spack.variant import *
 from spack.version import *
 from yaml.error import MarkedYAMLError
 
@@ -606,81 +608,6 @@ class DependencySpec(object):
                                 self.spec.name if self.spec else None)
 
 
-@key_ordering
-class VariantSpec(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, value):
-        self.name = name
-        self.value = value
-
-    def _cmp_key(self):
-        return (self.name, self.value)
-
-    def copy(self):
-        return VariantSpec(self.name, self.value)
-
-    def __str__(self):
-        if type(self.value) == bool:
-            return '{0}{1}'.format('+' if self.value else '~', self.name)
-        else:
-            return ' {0}={1} '.format(self.name, self.value)
-
-
-class VariantMap(HashableMap):
-
-    def __init__(self, spec):
-        super(VariantMap, self).__init__()
-        self.spec = spec
-
-    def satisfies(self, other, strict=False):
-        if strict or self.spec._concrete:
-            return all(k in self and self[k].value == other[k].value
-                       for k in other)
-        else:
-            return all(self[k].value == other[k].value
-                       for k in other if k in self)
-
-    def constrain(self, other):
-        """Add all variants in other that aren't in self to self.
-
-        Raises an error if any common variants don't match.
-        Return whether the spec changed.
-        """
-        if other.spec._concrete:
-            for k in self:
-                if k not in other:
-                    raise UnsatisfiableVariantSpecError(self[k], '<absent>')
-
-        changed = False
-        for k in other:
-            if k in self:
-                if self[k].value != other[k].value:
-                    raise UnsatisfiableVariantSpecError(self[k], other[k])
-            else:
-                self[k] = other[k].copy()
-                changed = True
-        return changed
-
-    @property
-    def concrete(self):
-        return self.spec._concrete or all(
-            v in self for v in self.spec.package_class.variants)
-
-    def copy(self):
-        clone = VariantMap(None)
-        for name, variant in self.items():
-            clone[name] = variant.copy()
-        return clone
-
-    def __str__(self):
-        sorted_keys = sorted(self.keys())
-        return ''.join(str(self[key]) for key in sorted_keys)
-
-
 _valid_compiler_flags = [
     'cflags', 'cxxflags', 'fflags', 'ldflags', 'ldlibs', 'cppflags']
 
@@ -1094,17 +1021,6 @@ class Spec(object):
         """Called by the parser to add an allowable version."""
         self.versions.add(version)
 
-    def _add_variant(self, name, value):
-        """Called by the parser to add a variant."""
-        if name in self.variants:
-            raise DuplicateVariantError(
-                "Cannot specify variant '%s' twice" % name)
-        if isinstance(value, string_types) and value.upper() == 'TRUE':
-            value = True
-        elif isinstance(value, string_types) and value.upper() == 'FALSE':
-            value = False
-        self.variants[name] = VariantSpec(name, value)
-
     def _add_flag(self, name, value):
         """Called by the parser to add a known flag.
         Known flags currently include "arch"
@@ -1124,7 +1040,13 @@ class Spec(object):
             assert(self.compiler_flags is not None)
             self.compiler_flags[name] = value.split()
         else:
-            self._add_variant(name, value)
+            # All other flags represent variants. 'foo=true' and 'foo=false'
+            # map to '+foo' and '~foo' respectively. As such they need a
+            # BoolValuedVariant instance.
+            if str(value).upper() == 'TRUE' or str(value).upper() == 'FALSE':
+                self.variants[name] = BoolValuedVariant(name, value)
+            else:
+                self.variants[name] = MultiValuedVariant(name, value)
 
     def _set_architecture(self, **kwargs):
         """Called by the parser to set the architecture."""
@@ -1424,8 +1346,11 @@ class Spec(object):
         if self.namespace:
             d['namespace'] = self.namespace
 
-        params = syaml_dict(sorted(
-            (name, v.value) for name, v in self.variants.items()))
+        params = syaml_dict(
+            sorted(
+                v.yaml_entry() for _, v in self.variants.items()
+            )
+        )
         params.update(sorted(self.compiler_flags.items()))
         if params:
             d['parameters'] = params
@@ -1491,11 +1416,14 @@ class Spec(object):
                 if name in _valid_compiler_flags:
                     spec.compiler_flags[name] = value
                 else:
-                    spec.variants[name] = VariantSpec(name, value)
-
+                    spec.variants[name] = MultiValuedVariant.from_node_dict(
+                        name, value
+                    )
         elif 'variants' in node:
             for name, value in node['variants'].items():
-                spec.variants[name] = VariantSpec(name, value)
+                spec.variants[name] = MultiValuedVariant.from_node_dict(
+                    name, value
+                )
             for name in FlagMap.valid_compiler_flags():
                 spec.compiler_flags[name] = []
 
@@ -2076,7 +2004,7 @@ class Spec(object):
             self._mark_concrete(False)
 
         # Ensure first that all packages & compilers in the DAG exist.
-        self.validate_names()
+        self.validate_or_raise()
         # Get all the dependencies into one DependencyMap
         spec_deps = self.flat_dependencies(copy=False, deptype_query=alldeps)
 
@@ -2110,11 +2038,13 @@ class Spec(object):
         clone.normalize()
         return clone
 
-    def validate_names(self):
-        """This checks that names of packages and compilers in this spec are real.
-           If they're not, it will raise either UnknownPackageError or
-           UnsupportedCompilerError.
+    def validate_or_raise(self):
+        """Checks that names and values in this spec are real. If they're not,
+        it will raise an appropriate exception.
         """
+        # FIXME: this function should be lazy, and collect all the errors
+        # FIXME: before raising the exceptions, instead of being greedy and
+        # FIXME: raise just the first one encountered
         for spec in self.traverse():
             # raise an UnknownPackageError if the spec's package isn't real.
             if (not spec.virtual) and spec.name:
@@ -2125,16 +2055,44 @@ class Spec(object):
                 if not compilers.supported(spec.compiler):
                     raise UnsupportedCompilerError(spec.compiler.name)
 
-            # Ensure that variants all exist.
-            for vname, variant in spec.variants.items():
-                if vname not in spec.package_class.variants:
-                    raise UnknownVariantError(spec.name, vname)
+            # FIXME: Move the logic below into the variant.py module
+            # Ensure correctness of variants (if the spec is not virtual)
+            if not spec.virtual:
+                pkg_cls = spec.package_class
+                pkg_variants = pkg_cls.variants
+                not_existing = set(spec.variants) - set(pkg_variants)
+                if not_existing:
+                    raise UnknownVariantError(spec.name, not_existing)
+
+                for name, v in [(x, y) for (x, y) in spec.variants.items()]:
+                    # When parsing a spec every variant of the form
+                    # 'foo=value' will be interpreted by default as a
+                    # multi-valued variant. During validation of the
+                    # variants we use the information in the package
+                    # to turn any variant that needs it to a single-valued
+                    # variant.
+                    pkg_variant = pkg_variants[name]
+                    pkg_variant.validate_or_raise(v, pkg_cls)
+                    spec.variants.substitute(
+                        pkg_variant.make_variant(v._original_value)
+                    )
 
     def constrain(self, other, deps=True):
         """Merge the constraints of other with self.
 
         Returns True if the spec changed as a result, False if not.
         """
+        # If we are trying to constrain a concrete spec, either the spec
+        # already satisfies the constraint (and the method returns False)
+        # or it raises an exception
+        if self.concrete:
+            if self.satisfies(other):
+                return False
+            else:
+                raise UnsatisfiableSpecError(
+                    self, other, 'constrain a concrete spec'
+                )
+
         other = self._autospec(other)
 
         if not (self.name == other.name or
@@ -2150,11 +2108,11 @@ class Spec(object):
         if not self.versions.overlaps(other.versions):
             raise UnsatisfiableVersionSpecError(self.versions, other.versions)
 
-        for v in other.variants:
-            if (v in self.variants and
-                    self.variants[v].value != other.variants[v].value):
-                raise UnsatisfiableVariantSpecError(self.variants[v],
-                                                    other.variants[v])
+        for v in [x for x in other.variants if x in self.variants]:
+            if not self.variants[v].compatible(other.variants[v]):
+                raise UnsatisfiableVariantSpecError(
+                    self.variants[v], other.variants[v]
+                )
 
         # TODO: Check out the logic here
         sarch, oarch = self.architecture, other.architecture
@@ -2328,6 +2286,30 @@ class Spec(object):
         elif strict and (other.compiler and not self.compiler):
             return False
 
+        # If self is a concrete spec, and other is not virtual, then we need
+        # to substitute every multi-valued variant that needs it with a
+        # single-valued variant.
+        if self.concrete:
+            for name, v in [(x, y) for (x, y) in other.variants.items()]:
+                # When parsing a spec every variant of the form
+                # 'foo=value' will be interpreted by default as a
+                # multi-valued variant. During validation of the
+                # variants we use the information in the package
+                # to turn any variant that needs it to a single-valued
+                # variant.
+                pkg_cls = type(other.package)
+                try:
+                    pkg_variant = other.package.variants[name]
+                    pkg_variant.validate_or_raise(v, pkg_cls)
+                except (SpecError, KeyError):
+                    # Catch the two things that could go wrong above:
+                    # 1. name is not a valid variant (KeyError)
+                    # 2. the variant is not validated (SpecError)
+                    return False
+                other.variants.substitute(
+                    pkg_variant.make_variant(v._original_value)
+                )
+
         var_strict = strict
         if (not self.name) or (not other.name):
             var_strict = True
@@ -3118,10 +3100,12 @@ class SpecParser(spack.parse.Parser):
                 added_version = True
 
             elif self.accept(ON):
-                spec._add_variant(self.variant(), True)
+                name = self.variant()
+                spec.variants[name] = BoolValuedVariant(name, True)
 
             elif self.accept(OFF):
-                spec._add_variant(self.variant(), False)
+                name = self.variant()
+                spec.variants[name] = BoolValuedVariant(name, False)
 
             elif self.accept(PCT):
                 spec._set_compiler(self.compiler())
@@ -3275,10 +3259,6 @@ def base32_prefix_bits(hash_string, bits):
     return prefix_bits(hash_bytes, bits)
 
 
-class SpecError(spack.error.SpackError):
-    """Superclass for all errors that occur while constructing specs."""
-
-
 class SpecParseError(SpecError):
     """Wrapper for ParseError for when we're parsing specs."""
     def __init__(self, parse_error):
@@ -3291,10 +3271,6 @@ class DuplicateDependencyError(SpecError):
     """Raised when the same dependency occurs in a spec twice."""
 
 
-class DuplicateVariantError(SpecError):
-    """Raised when the same variant occurs in a spec twice."""
-
-
 class DuplicateCompilerSpecError(SpecError):
     """Raised when the same compiler occurs in a spec twice."""
 
@@ -3306,13 +3282,6 @@ class UnsupportedCompilerError(SpecError):
             "The '%s' compiler is not yet supported." % compiler_name)
 
 
-class UnknownVariantError(SpecError):
-    """Raised when the same variant occurs in a spec twice."""
-    def __init__(self, pkg, variant):
-        super(UnknownVariantError, self).__init__(
-            "Package %s has no variant %s!" % (pkg, variant))
-
-
 class DuplicateArchitectureError(SpecError):
     """Raised when the same architecture occurs in a spec twice."""
 
@@ -3354,17 +3323,6 @@ class MultipleProviderError(SpecError):
         self.providers = providers
 
 
-class UnsatisfiableSpecError(SpecError):
-    """Raised when a spec conflicts with package constraints.
-       Provide the requirement that was violated when raising."""
-    def __init__(self, provided, required, constraint_type):
-        super(UnsatisfiableSpecError, self).__init__(
-            "%s does not satisfy %s" % (provided, required))
-        self.provided = provided
-        self.required = required
-        self.constraint_type = constraint_type
-
-
 class UnsatisfiableSpecNameError(UnsatisfiableSpecError):
     """Raised when two specs aren't even for the same package."""
     def __init__(self, provided, required):
@@ -3386,13 +3344,6 @@ class UnsatisfiableCompilerSpecError(UnsatisfiableSpecError):
             provided, required, "compiler")
 
 
-class UnsatisfiableVariantSpecError(UnsatisfiableSpecError):
-    """Raised when a spec variant conflicts with package constraints."""
-    def __init__(self, provided, required):
-        super(UnsatisfiableVariantSpecError, self).__init__(
-            provided, required, "variant")
-
-
 class UnsatisfiableCompilerFlagSpecError(UnsatisfiableSpecError):
     """Raised when a spec variant conflicts with package constraints."""
     def __init__(self, provided, required):
diff --git a/lib/spack/spack/test/build_systems.py b/lib/spack/spack/test/build_systems.py
index 2cafba0333..8e771c8a68 100644
--- a/lib/spack/spack/test/build_systems.py
+++ b/lib/spack/spack/test/build_systems.py
@@ -24,6 +24,8 @@
 ##############################################################################
 
 import spack
+import pytest
+
 from spack.build_environment import get_std_cmake_args
 from spack.spec import Spec
 
@@ -40,3 +42,31 @@ def test_cmake_std_args(config, builtin_mock):
     s.concretize()
     pkg = spack.repo.get(s)
     assert get_std_cmake_args(pkg)
+
+
+@pytest.mark.usefixtures('config', 'builtin_mock')
+class TestAutotoolsPackage(object):
+
+    def test_with_or_without(self):
+        s = Spec('a')
+        s.concretize()
+        pkg = spack.repo.get(s)
+
+        # Called without parameters
+        l = pkg.with_or_without('foo')
+        assert '--with-bar' in l
+        assert '--without-baz' in l
+        assert '--no-fee' in l
+
+        def activate(value):
+            return 'something'
+
+        l = pkg.with_or_without('foo', active_parameters=activate)
+        assert '--with-bar=something' in l
+        assert '--without-baz' in l
+        assert '--no-fee' in l
+
+        l = pkg.enable_or_disable('foo')
+        assert '--enable-bar' in l
+        assert '--disable-baz' in l
+        assert '--disable-fee' in l
diff --git a/lib/spack/spack/test/concretize.py b/lib/spack/spack/test/concretize.py
index 2063088184..779d4f8816 100644
--- a/lib/spack/spack/test/concretize.py
+++ b/lib/spack/spack/test/concretize.py
@@ -75,7 +75,7 @@ def check_concretize(abstract_spec):
         # dag
         'callpath', 'mpileaks', 'libelf',
         # variant
-        'mpich+debug', 'mpich~debug', 'mpich debug=2', 'mpich',
+        'mpich+debug', 'mpich~debug', 'mpich debug=True', 'mpich',
         # compiler flags
         'mpich cppflags="-O3"',
         # with virtual
diff --git a/lib/spack/spack/test/conftest.py b/lib/spack/spack/test/conftest.py
index 120425794f..3c725e229b 100644
--- a/lib/spack/spack/test/conftest.py
+++ b/lib/spack/spack/test/conftest.py
@@ -55,7 +55,7 @@ import spack.util.pattern
 @pytest.fixture(autouse=True)
 def no_stdin_duplication(monkeypatch):
     """Duplicating stdin (or any other stream) returns an empty
-    cStringIO object.
+    StringIO object.
     """
     monkeypatch.setattr(llnl.util.lang, 'duplicate_stream',
                         lambda x: StringIO())
diff --git a/lib/spack/spack/test/spec_semantics.py b/lib/spack/spack/test/spec_semantics.py
index f071bcc833..306a6ad98f 100644
--- a/lib/spack/spack/test/spec_semantics.py
+++ b/lib/spack/spack/test/spec_semantics.py
@@ -24,7 +24,9 @@
 ##############################################################################
 import spack.architecture
 import pytest
+
 from spack.spec import *
+from spack.variant import *
 
 
 def check_satisfies(spec, anon_spec, concrete=False):
@@ -243,6 +245,128 @@ class TestSpecSematics(object):
         check_satisfies('mpich~foo', 'mpich foo=FALSE')
         check_satisfies('mpich foo=False', 'mpich~foo')
 
+    def test_satisfies_multi_value_variant(self):
+        # Check quoting
+        check_satisfies('multivalue_variant foo="bar,baz"',
+                        'multivalue_variant foo="bar,baz"')
+        check_satisfies('multivalue_variant foo=bar,baz',
+                        'multivalue_variant foo=bar,baz')
+        check_satisfies('multivalue_variant foo="bar,baz"',
+                        'multivalue_variant foo=bar,baz')
+
+        # A more constrained spec satisfies a less constrained one
+        check_satisfies('multivalue_variant foo="bar,baz"',
+                        'multivalue_variant foo="bar"')
+
+        check_satisfies('multivalue_variant foo="bar,baz"',
+                        'multivalue_variant foo="baz"')
+
+        check_satisfies('multivalue_variant foo="bar,baz,barbaz"',
+                        'multivalue_variant foo="bar,baz"')
+
+        check_satisfies('multivalue_variant foo="bar,baz"',
+                        'foo="bar,baz"')
+
+        check_satisfies('multivalue_variant foo="bar,baz"',
+                        'foo="bar"')
+
+    def test_satisfies_single_valued_variant(self):
+        """Tests that the case reported in
+        https://github.com/LLNL/spack/pull/2386#issuecomment-282147639
+        is handled correctly.
+        """
+        a = Spec('a foobar=bar')
+        a.concretize()
+
+        assert a.satisfies('foobar=bar')
+
+    def test_unsatisfiable_multi_value_variant(self):
+
+        # Semantics for a multi-valued variant is different
+        # Depending on whether the spec is concrete or not
+
+        a = Spec('multivalue_variant foo="bar"', concrete=True)
+        spec_str = 'multivalue_variant foo="bar,baz"'
+        b = Spec(spec_str)
+        assert not a.satisfies(b)
+        assert not a.satisfies(spec_str)
+        # A concrete spec cannot be constrained further
+        with pytest.raises(UnsatisfiableSpecError):
+            a.constrain(b)
+
+        a = Spec('multivalue_variant foo="bar"')
+        spec_str = 'multivalue_variant foo="bar,baz"'
+        b = Spec(spec_str)
+        assert not a.satisfies(b)
+        assert not a.satisfies(spec_str)
+        # An abstract spec can instead be constrained
+        assert a.constrain(b)
+
+        a = Spec('multivalue_variant foo="bar,baz"', concrete=True)
+        spec_str = 'multivalue_variant foo="bar,baz,quux"'
+        b = Spec(spec_str)
+        assert not a.satisfies(b)
+        assert not a.satisfies(spec_str)
+        # A concrete spec cannot be constrained further
+        with pytest.raises(UnsatisfiableSpecError):
+            a.constrain(b)
+
+        a = Spec('multivalue_variant foo="bar,baz"')
+        spec_str = 'multivalue_variant foo="bar,baz,quux"'
+        b = Spec(spec_str)
+        assert not a.satisfies(b)
+        assert not a.satisfies(spec_str)
+        # An abstract spec can instead be constrained
+        assert a.constrain(b)
+        # ...but will fail during concretization if there are
+        # values in the variant that are not allowed
+        with pytest.raises(InvalidVariantValueError):
+            a.concretize()
+
+        # This time we'll try to set a single-valued variant
+        a = Spec('multivalue_variant fee="bar"')
+        spec_str = 'multivalue_variant fee="baz"'
+        b = Spec(spec_str)
+        assert not a.satisfies(b)
+        assert not a.satisfies(spec_str)
+        # A variant cannot be parsed as single-valued until we try to
+        # concretize. This means that we can constrain the variant above
+        assert a.constrain(b)
+        # ...but will fail during concretization if there are
+        # multiple values set
+        with pytest.raises(MultipleValuesInExclusiveVariantError):
+            a.concretize()
+
+        # FIXME: remove after having checked the correctness of the semantics
+        # check_unsatisfiable('multivalue_variant foo="bar,baz"',
+        #                     'multivalue_variant foo="bar,baz,quux"',
+        #                     concrete=True)
+        # check_unsatisfiable('multivalue_variant foo="bar,baz"',
+        #                     'multivalue_variant foo="bar,baz,quux"',
+        #                     concrete=True)
+
+        # but succeed for abstract ones (b/c they COULD satisfy the
+        # constraint if constrained)
+        # check_satisfies('multivalue_variant foo="bar"',
+        #                 'multivalue_variant foo="bar,baz"')
+
+        # check_satisfies('multivalue_variant foo="bar,baz"',
+        #                 'multivalue_variant foo="bar,baz,quux"')
+
+    def test_unsatisfiable_variant_types(self):
+        # These should fail due to incompatible types
+        check_unsatisfiable('multivalue_variant +foo',
+                            'multivalue_variant foo="bar"')
+
+        check_unsatisfiable('multivalue_variant ~foo',
+                            'multivalue_variant foo="bar"')
+
+        check_unsatisfiable('multivalue_variant foo="bar"',
+                            'multivalue_variant +foo')
+
+        check_unsatisfiable('multivalue_variant foo="bar"',
+                            'multivalue_variant ~foo')
+
     def test_satisfies_unconstrained_variant(self):
         # only asked for mpich, no constraints.  Either will do.
         check_satisfies('mpich+foo', 'mpich')
@@ -266,7 +390,7 @@ class TestSpecSematics(object):
         # No matchi in specs
         check_unsatisfiable('mpich~foo', 'mpich+foo')
         check_unsatisfiable('mpich+foo', 'mpich~foo')
-        check_unsatisfiable('mpich foo=1', 'mpich foo=2')
+        check_unsatisfiable('mpich foo=True', 'mpich foo=False')
 
     def test_satisfies_matching_compiler_flag(self):
         check_satisfies('mpich cppflags="-O3"', 'mpich cppflags="-O3"')
@@ -416,6 +540,19 @@ class TestSpecSematics(object):
             'libelf+debug~foo', 'libelf+debug', 'libelf+debug~foo'
         )
 
+    def test_constrain_multi_value_variant(self):
+        check_constrain(
+            'multivalue_variant foo="bar,baz"',
+            'multivalue_variant foo="bar"',
+            'multivalue_variant foo="baz"'
+        )
+
+        check_constrain(
+            'multivalue_variant foo="bar,baz,barbaz"',
+            'multivalue_variant foo="bar,barbaz"',
+            'multivalue_variant foo="baz"'
+        )
+
     def test_constrain_compiler_flags(self):
         check_constrain(
             'libelf cflags="-O3" cppflags="-Wall"',
@@ -455,7 +592,7 @@ class TestSpecSematics(object):
 
         check_invalid_constraint('libelf+debug', 'libelf~debug')
         check_invalid_constraint('libelf+debug~foo', 'libelf+debug+foo')
-        check_invalid_constraint('libelf debug=2', 'libelf debug=1')
+        check_invalid_constraint('libelf debug=True', 'libelf debug=False')
 
         check_invalid_constraint(
             'libelf cppflags="-O3"', 'libelf cppflags="-O2"')
diff --git a/lib/spack/spack/test/spec_yaml.py b/lib/spack/spack/test/spec_yaml.py
index adf262a60e..866cdebd26 100644
--- a/lib/spack/spack/test/spec_yaml.py
+++ b/lib/spack/spack/test/spec_yaml.py
@@ -74,6 +74,12 @@ def test_concrete_spec(config, builtin_mock):
     check_yaml_round_trip(spec)
 
 
+def test_yaml_multivalue():
+    spec = Spec('multivalue_variant foo="bar,baz"')
+    spec.concretize()
+    check_yaml_round_trip(spec)
+
+
 def test_yaml_subdag(config, builtin_mock):
     spec = Spec('mpileaks^mpich+debug')
     spec.concretize()
diff --git a/lib/spack/spack/test/variant.py b/lib/spack/spack/test/variant.py
new file mode 100644
index 0000000000..0c546a5dac
--- /dev/null
+++ b/lib/spack/spack/test/variant.py
@@ -0,0 +1,656 @@
+##############################################################################
+# Copyright (c) 2013-2016, Lawrence Livermore National Security, LLC.
+# Produced at the Lawrence Livermore National Laboratory.
+#
+# This file is part of Spack.
+# Created by Todd Gamblin, tgamblin@llnl.gov, All rights reserved.
+# LLNL-CODE-647188
+#
+# For details, see https://github.com/llnl/spack
+# Please also see the LICENSE file for our notice and the LGPL.
+#
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU Lesser General Public License (as
+# published by the Free Software Foundation) version 2.1, February 1999.
+#
+# This program is distributed in the hope that it will be useful, but
+# WITHOUT ANY WARRANTY; without even the IMPLIED WARRANTY OF
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the terms and
+# conditions of the GNU Lesser General Public License for more details.
+#
+# You should have received a copy of the GNU Lesser General Public
+# License along with this program; if not, write to the Free Software
+# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+##############################################################################
+
+import pytest
+import numbers
+
+from spack.variant import *
+
+
+class TestMultiValuedVariant(object):
+
+    def test_initialization(self):
+
+        # Basic properties
+        a = MultiValuedVariant('foo', 'bar,baz')
+        assert repr(a) == "MultiValuedVariant('foo', 'bar,baz')"
+        assert str(a) == 'foo=bar,baz'
+        assert a.value == ('bar', 'baz')
+        assert 'bar' in a
+        assert 'baz' in a
+        assert eval(repr(a)) == a
+
+        # Spaces are trimmed
+        b = MultiValuedVariant('foo', 'bar, baz')
+        assert repr(b) == "MultiValuedVariant('foo', 'bar, baz')"
+        assert str(b) == 'foo=bar,baz'
+        assert b.value == ('bar', 'baz')
+        assert 'bar' in b
+        assert 'baz' in b
+        assert a == b
+        assert hash(a) == hash(b)
+        assert eval(repr(b)) == a
+
+        # Order is not important
+        c = MultiValuedVariant('foo', 'baz, bar')
+        assert repr(c) == "MultiValuedVariant('foo', 'baz, bar')"
+        assert str(c) == 'foo=bar,baz'
+        assert c.value == ('bar', 'baz')
+        assert 'bar' in c
+        assert 'baz' in c
+        assert a == c
+        assert hash(a) == hash(c)
+        assert eval(repr(c)) == a
+
+        # Check the copy
+        d = a.copy()
+        assert repr(a) == repr(d)
+        assert str(a) == str(d)
+        assert d.value == ('bar', 'baz')
+        assert 'bar' in d
+        assert 'baz' in d
+        assert a == d
+        assert a is not d
+        assert hash(a) == hash(d)
+        assert eval(repr(d)) == a
+
+    def test_satisfies(self):
+
+        a = MultiValuedVariant('foo', 'bar,baz')
+        b = MultiValuedVariant('foo', 'bar')
+        c = MultiValuedVariant('fee', 'bar,baz')
+        d = MultiValuedVariant('foo', 'True')
+
+        # 'foo=bar,baz' satisfies 'foo=bar'
+        assert a.satisfies(b)
+
+        # 'foo=bar' does not satisfy 'foo=bar,baz'
+        assert not b.satisfies(a)
+
+        # 'foo=bar,baz' does not satisfy 'foo=bar,baz' and vice-versa
+        assert not a.satisfies(c)
+        assert not c.satisfies(a)
+
+        # Cannot satisfy the constraint with an object of
+        # another type
+        b_sv = SingleValuedVariant('foo', 'bar')
+        assert not b.satisfies(b_sv)
+
+        d_bv = BoolValuedVariant('foo', 'True')
+        assert not d.satisfies(d_bv)
+
+    def test_compatible(self):
+
+        a = MultiValuedVariant('foo', 'bar,baz')
+        b = MultiValuedVariant('foo', 'True')
+        c = MultiValuedVariant('fee', 'bar,baz')
+        d = MultiValuedVariant('foo', 'bar,barbaz')
+
+        # If the name of two multi-valued variants is the same,
+        # they are compatible
+        assert a.compatible(b)
+        assert not a.compatible(c)
+        assert a.compatible(d)
+
+        assert b.compatible(a)
+        assert not b.compatible(c)
+        assert b.compatible(d)
+
+        assert not c.compatible(a)
+        assert not c.compatible(b)
+        assert not c.compatible(d)
+
+        assert d.compatible(a)
+        assert d.compatible(b)
+        assert not d.compatible(c)
+
+        # Can't be compatible with other types
+        b_bv = BoolValuedVariant('foo', 'True')
+        assert not b.compatible(b_bv)
+
+        b_sv = SingleValuedVariant('foo', 'True')
+        assert not b.compatible(b_sv)
+
+    def test_constrain(self):
+
+        # Try to constrain on a value with less constraints than self
+        a = MultiValuedVariant('foo', 'bar,baz')
+        b = MultiValuedVariant('foo', 'bar')
+
+        changed = a.constrain(b)
+        assert not changed
+        t = MultiValuedVariant('foo', 'bar,baz')
+        assert a == t
+
+        # Try to constrain on a value with more constraints than self
+        a = MultiValuedVariant('foo', 'bar,baz')
+        b = MultiValuedVariant('foo', 'bar')
+
+        changed = b.constrain(a)
+        assert changed
+        t = MultiValuedVariant('foo', 'bar,baz')
+        assert a == t
+
+        # Try to constrain on the same value
+        a = MultiValuedVariant('foo', 'bar,baz')
+        b = a.copy()
+
+        changed = a.constrain(b)
+        assert not changed
+        t = MultiValuedVariant('foo', 'bar,baz')
+        assert a == t
+
+        # Try to constrain on a different name
+        a = MultiValuedVariant('foo', 'bar,baz')
+        b = MultiValuedVariant('fee', 'bar')
+
+        with pytest.raises(ValueError):
+            a.constrain(b)
+
+        # Try to constrain on other types
+        a = MultiValuedVariant('foo', 'bar,baz')
+        sv = SingleValuedVariant('foo', 'bar')
+        bv = BoolValuedVariant('foo', 'True')
+        for v in (sv, bv):
+            with pytest.raises(TypeError):
+                a.constrain(v)
+
+    def test_yaml_entry(self):
+
+        a = MultiValuedVariant('foo', 'bar,baz,barbaz')
+        b = MultiValuedVariant('foo', 'bar, baz,  barbaz')
+        expected = ('foo', sorted(['bar', 'baz', 'barbaz']))
+
+        assert a.yaml_entry() == expected
+        assert b.yaml_entry() == expected
+
+        a = MultiValuedVariant('foo', 'bar')
+        expected = ('foo', sorted(['bar']))
+
+        assert a.yaml_entry() == expected
+
+
+class TestSingleValuedVariant(object):
+
+    def test_initialization(self):
+
+        # Basic properties
+        a = SingleValuedVariant('foo', 'bar')
+        assert repr(a) == "SingleValuedVariant('foo', 'bar')"
+        assert str(a) == 'foo=bar'
+        assert a.value == 'bar'
+        assert 'bar' in a
+        assert eval(repr(a)) == a
+
+        # Raise if multiple values are passed
+        with pytest.raises(ValueError):
+            SingleValuedVariant('foo', 'bar, baz')
+
+        # Check the copy
+        b = a.copy()
+        assert repr(a) == repr(b)
+        assert str(a) == str(b)
+        assert b.value == 'bar'
+        assert 'bar' in b
+        assert a == b
+        assert a is not b
+        assert hash(a) == hash(b)
+        assert eval(repr(b)) == a
+
+    def test_satisfies(self):
+        a = SingleValuedVariant('foo', 'bar')
+        b = SingleValuedVariant('foo', 'bar')
+        c = SingleValuedVariant('foo', 'baz')
+        d = SingleValuedVariant('fee', 'bar')
+        e = SingleValuedVariant('foo', 'True')
+
+        # 'foo=bar' can only satisfy 'foo=bar'
+        assert a.satisfies(b)
+        assert not a.satisfies(c)
+        assert not a.satisfies(d)
+
+        assert b.satisfies(a)
+        assert not b.satisfies(c)
+        assert not b.satisfies(d)
+
+        assert not c.satisfies(a)
+        assert not c.satisfies(b)
+        assert not c.satisfies(d)
+
+        # Cannot satisfy the constraint with an object of
+        # another type
+        a_mv = MultiValuedVariant('foo', 'bar')
+        assert not a.satisfies(a_mv)
+
+        e_bv = BoolValuedVariant('foo', 'True')
+        assert not e.satisfies(e_bv)
+
+    def test_compatible(self):
+
+        a = SingleValuedVariant('foo', 'bar')
+        b = SingleValuedVariant('fee', 'bar')
+        c = SingleValuedVariant('foo', 'baz')
+        d = SingleValuedVariant('foo', 'bar')
+
+        # If the name of two multi-valued variants is the same,
+        # they are compatible
+        assert not a.compatible(b)
+        assert not a.compatible(c)
+        assert a.compatible(d)
+
+        assert not b.compatible(a)
+        assert not b.compatible(c)
+        assert not b.compatible(d)
+
+        assert not c.compatible(a)
+        assert not c.compatible(b)
+        assert not c.compatible(d)
+
+        assert d.compatible(a)
+        assert not d.compatible(b)
+        assert not d.compatible(c)
+
+        # Can't be compatible with other types
+        a_mv = MultiValuedVariant('foo', 'bar')
+        assert not a.compatible(a_mv)
+
+        e = SingleValuedVariant('foo', 'True')
+        e_bv = BoolValuedVariant('foo', 'True')
+        assert not e.compatible(e_bv)
+
+    def test_constrain(self):
+
+        # Try to constrain on a value equal to self
+        a = SingleValuedVariant('foo', 'bar')
+        b = SingleValuedVariant('foo', 'bar')
+
+        changed = a.constrain(b)
+        assert not changed
+        t = SingleValuedVariant('foo', 'bar')
+        assert a == t
+
+        # Try to constrain on a value with a different value
+        a = SingleValuedVariant('foo', 'bar')
+        b = SingleValuedVariant('foo', 'baz')
+
+        with pytest.raises(UnsatisfiableVariantSpecError):
+            b.constrain(a)
+
+        # Try to constrain on a value with a different value
+        a = SingleValuedVariant('foo', 'bar')
+        b = SingleValuedVariant('fee', 'bar')
+
+        with pytest.raises(ValueError):
+            b.constrain(a)
+
+        # Try to constrain on the same value
+        a = SingleValuedVariant('foo', 'bar')
+        b = a.copy()
+
+        changed = a.constrain(b)
+        assert not changed
+        t = SingleValuedVariant('foo', 'bar')
+        assert a == t
+
+        # Try to constrain on other values
+        a = SingleValuedVariant('foo', 'True')
+        mv = MultiValuedVariant('foo', 'True')
+        bv = BoolValuedVariant('foo', 'True')
+        for v in (mv, bv):
+            with pytest.raises(TypeError):
+                a.constrain(v)
+
+    def test_yaml_entry(self):
+        a = SingleValuedVariant('foo', 'bar')
+        expected = ('foo', 'bar')
+
+        assert a.yaml_entry() == expected
+
+
+class TestBoolValuedVariant(object):
+
+    def test_initialization(self):
+        # Basic properties - True value
+        for v in (True, 'True', 'TRUE', 'TrUe'):
+            a = BoolValuedVariant('foo', v)
+            assert repr(a) == "BoolValuedVariant('foo', {0})".format(repr(v))
+            assert str(a) == '+foo'
+            assert a.value is True
+            assert True in a
+            assert eval(repr(a)) == a
+
+        # Copy - True value
+        b = a.copy()
+        assert repr(a) == repr(b)
+        assert str(a) == str(b)
+        assert b.value is True
+        assert True in b
+        assert a == b
+        assert a is not b
+        assert hash(a) == hash(b)
+        assert eval(repr(b)) == a
+
+        # Basic properties - False value
+        for v in (False, 'False', 'FALSE', 'FaLsE'):
+            a = BoolValuedVariant('foo', v)
+            assert repr(a) == "BoolValuedVariant('foo', {0})".format(repr(v))
+            assert str(a) == '~foo'
+            assert a.value is False
+            assert False in a
+            assert eval(repr(a)) == a
+
+        # Copy - True value
+        b = a.copy()
+        assert repr(a) == repr(b)
+        assert str(a) == str(b)
+        assert b.value is False
+        assert False in b
+        assert a == b
+        assert a is not b
+        assert eval(repr(b)) == a
+
+        # Invalid values
+        for v in ('bar', 'bar,baz'):
+            with pytest.raises(ValueError):
+                BoolValuedVariant('foo', v)
+
+    def test_satisfies(self):
+        a = BoolValuedVariant('foo', True)
+        b = BoolValuedVariant('foo', False)
+        c = BoolValuedVariant('fee', False)
+        d = BoolValuedVariant('foo', 'True')
+
+        assert not a.satisfies(b)
+        assert not a.satisfies(c)
+        assert a.satisfies(d)
+
+        assert not b.satisfies(a)
+        assert not b.satisfies(c)
+        assert not b.satisfies(d)
+
+        assert not c.satisfies(a)
+        assert not c.satisfies(b)
+        assert not c.satisfies(d)
+
+        assert d.satisfies(a)
+        assert not d.satisfies(b)
+        assert not d.satisfies(c)
+
+        # Cannot satisfy the constraint with an object of
+        # another type
+        d_mv = MultiValuedVariant('foo', 'True')
+        assert not d.satisfies(d_mv)
+
+        d_sv = SingleValuedVariant('foo', 'True')
+        assert not d.satisfies(d_sv)
+
+    def test_compatible(self):
+
+        a = BoolValuedVariant('foo', True)
+        b = BoolValuedVariant('fee', True)
+        c = BoolValuedVariant('foo', False)
+        d = BoolValuedVariant('foo', 'True')
+
+        # If the name of two multi-valued variants is the same,
+        # they are compatible
+        assert not a.compatible(b)
+        assert not a.compatible(c)
+        assert a.compatible(d)
+
+        assert not b.compatible(a)
+        assert not b.compatible(c)
+        assert not b.compatible(d)
+
+        assert not c.compatible(a)
+        assert not c.compatible(b)
+        assert not c.compatible(d)
+
+        assert d.compatible(a)
+        assert not d.compatible(b)
+        assert not d.compatible(c)
+
+        # Can't be compatible with other types
+        d_mv = MultiValuedVariant('foo', 'True')
+        assert not d.compatible(d_mv)
+
+        d_sv = SingleValuedVariant('foo', 'True')
+        assert not d.compatible(d_sv)
+
+    def test_constrain(self):
+        # Try to constrain on a value equal to self
+        a = BoolValuedVariant('foo', 'True')
+        b = BoolValuedVariant('foo', True)
+
+        changed = a.constrain(b)
+        assert not changed
+        t = BoolValuedVariant('foo', True)
+        assert a == t
+
+        # Try to constrain on a value with a different value
+        a = BoolValuedVariant('foo', True)
+        b = BoolValuedVariant('foo', False)
+
+        with pytest.raises(UnsatisfiableVariantSpecError):
+            b.constrain(a)
+
+        # Try to constrain on a value with a different value
+        a = BoolValuedVariant('foo', True)
+        b = BoolValuedVariant('fee', True)
+
+        with pytest.raises(ValueError):
+            b.constrain(a)
+
+        # Try to constrain on the same value
+        a = BoolValuedVariant('foo', True)
+        b = a.copy()
+
+        changed = a.constrain(b)
+        assert not changed
+        t = BoolValuedVariant('foo', True)
+        assert a == t
+
+        # Try to constrain on other values
+        a = BoolValuedVariant('foo', 'True')
+        sv = SingleValuedVariant('foo', 'True')
+        mv = MultiValuedVariant('foo', 'True')
+        for v in (sv, mv):
+            with pytest.raises(TypeError):
+                a.constrain(v)
+
+    def test_yaml_entry(self):
+
+        a = BoolValuedVariant('foo', 'True')
+        expected = ('foo', True)
+        assert a.yaml_entry() == expected
+
+        a = BoolValuedVariant('foo', 'False')
+        expected = ('foo', False)
+        assert a.yaml_entry() == expected
+
+
+def test_from_node_dict():
+    a = MultiValuedVariant.from_node_dict('foo', ['bar'])
+    assert type(a) == MultiValuedVariant
+
+    a = MultiValuedVariant.from_node_dict('foo', 'bar')
+    assert type(a) == SingleValuedVariant
+
+    a = MultiValuedVariant.from_node_dict('foo', 'true')
+    assert type(a) == BoolValuedVariant
+
+
+class TestVariant(object):
+
+    def test_validation(self):
+        a = Variant(
+            'foo',
+            default='',
+            description='',
+            values=('bar', 'baz', 'foobar'),
+            multi=False
+        )
+        # Valid vspec, shouldn't raise
+        vspec = a.make_variant('bar')
+        a.validate_or_raise(vspec)
+
+        # Multiple values are not allowed
+        with pytest.raises(MultipleValuesInExclusiveVariantError):
+            vspec.value = 'bar,baz'
+
+        # Inconsistent vspec
+        vspec.name = 'FOO'
+        with pytest.raises(InconsistentValidationError):
+            a.validate_or_raise(vspec)
+
+        # Valid multi-value vspec
+        a.multi = True
+        vspec = a.make_variant('bar,baz')
+        a.validate_or_raise(vspec)
+        # Add an invalid value
+        vspec.value = 'bar,baz,barbaz'
+        with pytest.raises(InvalidVariantValueError):
+            a.validate_or_raise(vspec)
+
+    def test_callable_validator(self):
+
+        def validator(x):
+            try:
+                return isinstance(int(x), numbers.Integral)
+            except ValueError:
+                return False
+
+        a = Variant(
+            'foo',
+            default=1024,
+            description='',
+            values=validator,
+            multi=False
+        )
+        vspec = a.make_default()
+        a.validate_or_raise(vspec)
+        vspec.value = 2056
+        a.validate_or_raise(vspec)
+        vspec.value = 'foo'
+        with pytest.raises(InvalidVariantValueError):
+            a.validate_or_raise(vspec)
+
+    def test_representation(self):
+        a = Variant(
+            'foo',
+            default='',
+            description='',
+            values=('bar', 'baz', 'foobar'),
+            multi=False
+        )
+        assert a.allowed_values == 'bar, baz, foobar'
+
+
+class TestVariantMapTest(object):
+
+    def test_invalid_values(self):
+        # Value with invalid type
+        a = VariantMap(None)
+        with pytest.raises(TypeError):
+            a['foo'] = 2
+
+        # Duplicate variant
+        a['foo'] = MultiValuedVariant('foo', 'bar,baz')
+        with pytest.raises(DuplicateVariantError):
+            a['foo'] = MultiValuedVariant('foo', 'bar')
+
+        with pytest.raises(DuplicateVariantError):
+            a['foo'] = SingleValuedVariant('foo', 'bar')
+
+        with pytest.raises(DuplicateVariantError):
+            a['foo'] = BoolValuedVariant('foo', True)
+
+        # Non matching names between key and vspec.name
+        with pytest.raises(KeyError):
+            a['bar'] = MultiValuedVariant('foo', 'bar')
+
+    def test_set_item(self):
+        # Check that all the three types of variants are accepted
+        a = VariantMap(None)
+
+        a['foo'] = BoolValuedVariant('foo', True)
+        a['bar'] = SingleValuedVariant('bar', 'baz')
+        a['foobar'] = MultiValuedVariant('foobar', 'a, b, c, d, e')
+
+    def test_substitute(self):
+        # Check substitution of a key that exists
+        a = VariantMap(None)
+        a['foo'] = BoolValuedVariant('foo', True)
+        a.substitute(SingleValuedVariant('foo', 'bar'))
+
+        # Trying to substitute something that is not
+        # in the map will raise a KeyError
+        with pytest.raises(KeyError):
+            a.substitute(BoolValuedVariant('bar', True))
+
+    def test_satisfies_and_constrain(self):
+        # foo=bar foobar=fee feebar=foo
+        a = VariantMap(None)
+        a['foo'] = MultiValuedVariant('foo', 'bar')
+        a['foobar'] = SingleValuedVariant('foobar', 'fee')
+        a['feebar'] = SingleValuedVariant('feebar', 'foo')
+
+        # foo=bar,baz foobar=fee shared=True
+        b = VariantMap(None)
+        b['foo'] = MultiValuedVariant('foo', 'bar, baz')
+        b['foobar'] = SingleValuedVariant('foobar', 'fee')
+        b['shared'] = BoolValuedVariant('shared', True)
+
+        assert not a.satisfies(b)
+        assert b.satisfies(a)
+
+        assert not a.satisfies(b, strict=True)
+        assert not b.satisfies(a, strict=True)
+
+        # foo=bar,baz foobar=fee feebar=foo shared=True
+        c = VariantMap(None)
+        c['foo'] = MultiValuedVariant('foo', 'bar, baz')
+        c['foobar'] = SingleValuedVariant('foobar', 'fee')
+        c['feebar'] = SingleValuedVariant('feebar', 'foo')
+        c['shared'] = BoolValuedVariant('shared', True)
+
+        assert a.constrain(b)
+        assert a == c
+
+    def test_copy(self):
+        a = VariantMap(None)
+        a['foo'] = BoolValuedVariant('foo', True)
+        a['bar'] = SingleValuedVariant('bar', 'baz')
+        a['foobar'] = MultiValuedVariant('foobar', 'a, b, c, d, e')
+
+        c = a.copy()
+        assert a == c
+
+    def test_str(self):
+        c = VariantMap(None)
+        c['foo'] = MultiValuedVariant('foo', 'bar, baz')
+        c['foobar'] = SingleValuedVariant('foobar', 'fee')
+        c['feebar'] = SingleValuedVariant('feebar', 'foo')
+        c['shared'] = BoolValuedVariant('shared', True)
+        assert str(c) == ' feebar=foo foo=bar,baz foobar=fee +shared'
diff --git a/lib/spack/spack/variant.py b/lib/spack/spack/variant.py
index b2c1a73489..7102676b69 100644
--- a/lib/spack/spack/variant.py
+++ b/lib/spack/spack/variant.py
@@ -22,17 +22,583 @@
 # License along with this program; if not, write to the Free Software
 # Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 ##############################################################################
-"""Variant is a class describing flags on builds, or "variants".
+"""The variant module contains data structures that are needed to manage
+variants both in packages and in specs.
+"""
 
-Could be generalized later to describe aribitrary parameters, but
-currently variants are just flags.
+import inspect
+import re
 
-"""
+import llnl.util.lang as lang
+import spack.error as error
+from six import StringIO
 
 
 class Variant(object):
-    """Represents a variant on a build.  Can be either on or off."""
+    """Represents a variant in a package, as declared in the
+    variant directive.
+    """
 
-    def __init__(self, default, description):
-        self.default     = default
+    def __init__(
+            self,
+            name,
+            default,
+            description,
+            values=(True, False),
+            multi=False,
+            validator=None
+    ):
+        """Initialize a package variant.
+
+        Args:
+            name (str): name of the variant
+            default (str): default value for the variant in case
+                nothing has been specified
+            description (str): purpose of the variant
+            values (sequence): sequence of allowed values or a callable
+                accepting a single value as argument and returning True if the
+                value is good, False otherwise
+            multi (bool): whether multiple CSV are allowed
+            validator (callable): optional callable used to enforce
+                additional logic on the set of values being validated
+        """
+        self.name = name
+        self.default = default
         self.description = str(description)
+
+        if callable(values):
+            # If 'values' is a callable, assume it is a single value
+            # validator and reset the values to be explicit during debug
+            self.single_value_validator = values
+            self.values = None
+        else:
+            # Otherwise assume values is the set of allowed explicit values
+            self.values = tuple(values)
+            allowed = self.values + (self.default,)
+            self.single_value_validator = lambda x: x in allowed
+
+        self.multi = multi
+        self.group_validator = validator
+
+    def validate_or_raise(self, vspec, pkg=None):
+        """Validate a variant spec against this package variant. Raises an
+        exception if any error is found.
+
+        Args:
+            vspec (VariantSpec): instance to be validated
+            pkg (Package): the package that required the validation,
+                if available
+
+        Raises:
+            InconsistentValidationError: if ``vspec.name != self.name``
+
+            MultipleValuesInExclusiveVariantError: if ``vspec`` has
+                multiple values but ``self.multi == False``
+
+            InvalidVariantValueError: if ``vspec.value`` contains
+                invalid values
+        """
+        # Check the name of the variant
+        if self.name != vspec.name:
+            raise InconsistentValidationError(vspec, self)
+
+        # Check the values of the variant spec
+        value = vspec.value
+        if isinstance(vspec.value, (bool, str)):
+            value = (vspec.value,)
+
+        # If the value is exclusive there must be at most one
+        if not self.multi and len(value) != 1:
+            raise MultipleValuesInExclusiveVariantError(vspec, pkg)
+
+        # Check and record the values that are not allowed
+        not_allowed_values = [
+            x for x in value if not self.single_value_validator(x)
+        ]
+        if not_allowed_values:
+            raise InvalidVariantValueError(self, not_allowed_values, pkg)
+
+        # Validate the group of values if needed
+        if self.group_validator is not None:
+            self.group_validator(value)
+
+    @property
+    def allowed_values(self):
+        """Returns a string representation of the allowed values for
+        printing purposes
+
+        Returns:
+            str: representation of the allowed values
+        """
+        # Join an explicit set of allowed values
+        if self.values is not None:
+            v = tuple(str(x) for x in self.values)
+            return ', '.join(v)
+        # In case we were given a single-value validator
+        # print the docstring
+        docstring = inspect.getdoc(self.single_value_validator)
+        v = docstring if docstring else ''
+        return v
+
+    def make_default(self):
+        """Factory that creates a variant holding the default value.
+
+        Returns:
+            MultiValuedVariant or SingleValuedVariant or BoolValuedVariant:
+                instance of the proper variant
+        """
+        return self.make_variant(self.default)
+
+    def make_variant(self, value):
+        """Factory that creates a variant holding the value passed as
+        a parameter.
+
+        Args:
+            value: value that will be hold by the variant
+
+        Returns:
+            MultiValuedVariant or SingleValuedVariant or BoolValuedVariant:
+                instance of the proper variant
+        """
+        return self.variant_cls(self.name, value)
+
+    @property
+    def variant_cls(self):
+        """Proper variant class to be used for this configuration."""
+        if self.multi:
+            return MultiValuedVariant
+        elif self.values == (True, False):
+            return BoolValuedVariant
+        return SingleValuedVariant
+
+
+@lang.key_ordering
+class MultiValuedVariant(object):
+    """A variant that can hold multiple values at once."""
+
+    @staticmethod
+    def from_node_dict(name, value):
+        """Reconstruct a variant from a node dict."""
+        if isinstance(value, list):
+            value = ','.join(value)
+            return MultiValuedVariant(name, value)
+        elif str(value).upper() == 'TRUE' or str(value).upper() == 'FALSE':
+            return BoolValuedVariant(name, value)
+        return SingleValuedVariant(name, value)
+
+    def __init__(self, name, value):
+        self.name = name
+
+        # Stores 'value' after a bit of massaging
+        # done by the property setter
+        self._value = None
+        self._original_value = None
+
+        # Invokes property setter
+        self.value = value
+
+    @property
+    def value(self):
+        """Returns a tuple of strings containing the values stored in
+        the variant.
+
+        Returns:
+            tuple of str: values stored in the variant
+        """
+        return self._value
+
+    @value.setter
+    def value(self, value):
+        self._value_setter(value)
+
+    def _value_setter(self, value):
+        # Store the original value
+        self._original_value = value
+
+        # Store a tuple of CSV string representations
+        # Tuple is necessary here instead of list because the
+        # values need to be hashed
+        t = re.split(r'\s*,\s*', str(value))
+
+        # With multi-value variants it is necessary
+        # to remove duplicates and give an order
+        # to a set
+        self._value = tuple(sorted(set(t)))
+
+    def _cmp_key(self):
+        return self.name, self.value
+
+    def copy(self):
+        """Returns an instance of a variant equivalent to self
+
+        Returns:
+            any variant type: a copy of self
+
+        >>> a = MultiValuedVariant('foo', True)
+        >>> b = a.copy()
+        >>> assert a == b
+        >>> assert a is not b
+        """
+        return type(self)(self.name, self._original_value)
+
+    def satisfies(self, other):
+        """Returns true if ``other.name == self.name`` and ``other.value`` is
+        a strict subset of self. Does not try to validate.
+
+        Args:
+            other: constraint to be met for the method to return True
+
+        Returns:
+            bool: True or False
+        """
+        # If types are different the constraint is not satisfied
+        if type(other) != type(self):
+            return False
+
+        # If names are different then `self` does not satisfy `other`
+        # (`foo=bar` does not satisfy `baz=bar`)
+        if other.name != self.name:
+            return False
+
+        # Otherwise we want all the values in `other` to be also in `self`
+        return all(v in self.value for v in other.value)
+
+    def compatible(self, other):
+        """Returns True if self and other are compatible, False otherwise.
+
+        As there is no semantic check, two VariantSpec are compatible if
+        either they contain the same value or they are both multi-valued.
+
+        Args:
+            other: instance against which we test compatibility
+
+        Returns:
+            bool: True or False
+        """
+        # If types are different they are not compatible
+        if type(other) != type(self):
+            return False
+
+        # If names are different then they are not compatible
+        return other.name == self.name
+
+    def constrain(self, other):
+        """Modify self to match all the constraints for other if both
+        instances are multi-valued. Returns True if self changed,
+        False otherwise.
+
+        Args:
+            other: instance against which we constrain self
+
+        Returns:
+            bool: True or False
+        """
+        # If types are different they are not compatible
+        if type(other) != type(self):
+            msg = 'other must be of type \'{0.__name__}\''
+            raise TypeError(msg.format(type(self)))
+
+        if self.name != other.name:
+            raise ValueError('variants must have the same name')
+        old_value = self.value
+        self.value = ','.join(sorted(set(self.value + other.value)))
+        return old_value != self.value
+
+    def yaml_entry(self):
+        """Returns a key, value tuple suitable to be an entry in a yaml dict.
+
+        Returns:
+            tuple: (name, value_representation)
+        """
+        return self.name, list(self.value)
+
+    def __contains__(self, item):
+        return item in self._value
+
+    def __repr__(self):
+        cls = type(self)
+        return '{0.__name__}({1}, {2})'.format(
+            cls, repr(self.name), repr(self._original_value)
+        )
+
+    def __str__(self):
+        return '{0}={1}'.format(
+            self.name, ','.join(str(x) for x in self.value)
+        )
+
+
+class SingleValuedVariant(MultiValuedVariant):
+    """A variant that can hold multiple values, but one at a time."""
+
+    def _value_setter(self, value):
+        # Treat the value as a multi-valued variant
+        super(SingleValuedVariant, self)._value_setter(value)
+
+        # Then check if there's only a single value
+        if len(self._value) != 1:
+            raise MultipleValuesInExclusiveVariantError(self, None)
+        self._value = str(self._value[0])
+
+    def __str__(self):
+        return '{0}={1}'.format(self.name, self.value)
+
+    def satisfies(self, other):
+        # If types are different the constraint is not satisfied
+        if type(other) != type(self):
+            return False
+
+        # If names are different then `self` does not satisfy `other`
+        # (`foo=bar` does not satisfy `baz=bar`)
+        if other.name != self.name:
+            return False
+
+        return self.value == other.value
+
+    def compatible(self, other):
+        return self.satisfies(other)
+
+    def constrain(self, other):
+        if type(other) != type(self):
+            msg = 'other must be of type \'{0.__name__}\''
+            raise TypeError(msg.format(type(self)))
+
+        if self.name != other.name:
+            raise ValueError('variants must have the same name')
+
+        if self.value != other.value:
+            raise UnsatisfiableVariantSpecError(other.value, self.value)
+        return False
+
+    def __contains__(self, item):
+        return item == self.value
+
+    def yaml_entry(self):
+        return self.name, self.value
+
+
+class BoolValuedVariant(SingleValuedVariant):
+    """A variant that can hold either True or False."""
+
+    def _value_setter(self, value):
+        # Check the string representation of the value and turn
+        # it to a boolean
+        if str(value).upper() == 'TRUE':
+            self._original_value = value
+            self._value = True
+        elif str(value).upper() == 'FALSE':
+            self._original_value = value
+            self._value = False
+        else:
+            msg = 'cannot construct a BoolValuedVariant from '
+            msg += 'a value that does not represent a bool'
+            raise ValueError(msg)
+
+    def __contains__(self, item):
+        return item is self.value
+
+    def __str__(self):
+        return '{0}{1}'.format('+' if self.value else '~', self.name)
+
+
+class VariantMap(lang.HashableMap):
+    """Map containing variant instances. New values can be added only
+    if the key is not already present.
+    """
+
+    def __init__(self, spec):
+        super(VariantMap, self).__init__()
+        self.spec = spec
+
+    def __setitem__(self, name, vspec):
+        # Raise a TypeError if vspec is not of the right type
+        if not isinstance(vspec, MultiValuedVariant):
+            msg = 'VariantMap accepts only values of type VariantSpec'
+            raise TypeError(msg)
+
+        # Raise an error if the variant was already in this map
+        if name in self.dict:
+            msg = 'Cannot specify variant "{0}" twice'.format(name)
+            raise DuplicateVariantError(msg)
+
+        # Raise an error if name and vspec.name don't match
+        if name != vspec.name:
+            msg = 'Inconsistent key "{0}", must be "{1}" to match VariantSpec'
+            raise KeyError(msg.format(name, vspec.name))
+
+        # Set the item
+        super(VariantMap, self).__setitem__(name, vspec)
+
+    def substitute(self, vspec):
+        """Substitutes the entry under ``vspec.name`` with ``vspec``.
+
+        Args:
+            vspec: variant spec to be substituted
+        """
+        if vspec.name not in self:
+            msg = 'cannot substitute a key that does not exist [{0}]'
+            raise KeyError(msg.format(vspec.name))
+
+        # Set the item
+        super(VariantMap, self).__setitem__(vspec.name, vspec)
+
+    def satisfies(self, other, strict=False):
+        """Returns True if this VariantMap is more constrained than other,
+        False otherwise.
+
+        Args:
+            other (VariantMap): VariantMap instance to satisfy
+            strict (bool): if True return False if a key is in other and
+                not in self, otherwise discard that key and proceed with
+                evaluation
+
+        Returns:
+            bool: True or False
+        """
+        to_be_checked = [k for k in other]
+
+        strict_or_concrete = strict
+        if self.spec is not None:
+            strict_or_concrete |= self.spec._concrete
+
+        if not strict_or_concrete:
+            to_be_checked = filter(lambda x: x in self, to_be_checked)
+
+        return all(k in self and self[k].satisfies(other[k])
+                   for k in to_be_checked)
+
+    def constrain(self, other):
+        """Add all variants in other that aren't in self to self. Also
+        constrain all multi-valued variants that are already present.
+        Return True if self changed, False otherwise
+
+        Args:
+            other (VariantMap): instance against which we constrain self
+
+        Returns:
+            bool: True or False
+        """
+        if other.spec is not None and other.spec._concrete:
+            for k in self:
+                if k not in other:
+                    raise UnsatisfiableVariantSpecError(self[k], '<absent>')
+
+        changed = False
+        for k in other:
+            if k in self:
+                # If they are not compatible raise an error
+                if not self[k].compatible(other[k]):
+                    raise UnsatisfiableVariantSpecError(self[k], other[k])
+                # If they are compatible merge them
+                changed |= self[k].constrain(other[k])
+            else:
+                # If it is not present copy it straight away
+                self[k] = other[k].copy()
+                changed = True
+
+        return changed
+
+    @property
+    def concrete(self):
+        """Returns True if the spec is concrete in terms of variants.
+
+        Returns:
+            bool: True or False
+        """
+        return self.spec._concrete or all(
+            v in self for v in self.spec.package_class.variants
+        )
+
+    def copy(self):
+        """Return an instance of VariantMap equivalent to self.
+
+        Returns:
+            VariantMap: a copy of self
+        """
+        clone = VariantMap(self.spec)
+        for name, variant in self.items():
+            clone[name] = variant.copy()
+        return clone
+
+    def __str__(self):
+        # print keys in order
+        sorted_keys = sorted(self.keys())
+
+        # add spaces before and after key/value variants.
+        string = StringIO()
+
+        kv = False
+        for key in sorted_keys:
+            vspec = self[key]
+
+            if not isinstance(vspec.value, bool):
+                # add space before all kv pairs.
+                string.write(' ')
+                kv = True
+            else:
+                # not a kv pair this time
+                if kv:
+                    # if it was LAST time, then pad after.
+                    string.write(' ')
+                kv = False
+
+            string.write(str(vspec))
+
+        return string.getvalue()
+
+
+class DuplicateVariantError(error.SpecError):
+    """Raised when the same variant occurs in a spec twice."""
+
+
+class UnknownVariantError(error.SpecError):
+    """Raised when an unknown variant occurs in a spec."""
+
+    def __init__(self, pkg, variant):
+        super(UnknownVariantError, self).__init__(
+            'Package {0} has no variant {1}!'.format(pkg, variant)
+        )
+
+
+class InconsistentValidationError(error.SpecError):
+    """Raised if the wrong validator is used to validate a variant."""
+    def __init__(self, vspec, variant):
+        msg = ('trying to validate variant "{0.name}" '
+               'with the validator of "{1.name}"')
+        super(InconsistentValidationError, self).__init__(
+            msg.format(vspec, variant)
+        )
+
+
+class MultipleValuesInExclusiveVariantError(error.SpecError, ValueError):
+    """Raised when multiple values are present in a variant that wants
+    only one.
+    """
+    def __init__(self, variant, pkg):
+        msg = 'multiple values are not allowed for variant "{0.name}"{1}'
+        pkg_info = ''
+        if pkg is not None:
+            pkg_info = ' in package "{0}"'.format(pkg.name)
+        super(MultipleValuesInExclusiveVariantError, self).__init__(
+            msg.format(variant, pkg_info)
+        )
+
+
+class InvalidVariantValueError(error.SpecError):
+    """Raised when a valid variant has at least an invalid value."""
+
+    def __init__(self, variant, invalid_values, pkg):
+        msg = 'invalid values for variant "{0.name}"{2}: {1}\n'
+        pkg_info = ''
+        if pkg is not None:
+            pkg_info = ' in package "{0}"'.format(pkg.name)
+        super(InvalidVariantValueError, self).__init__(
+            msg.format(variant, invalid_values, pkg_info)
+        )
+
+
+class UnsatisfiableVariantSpecError(error.UnsatisfiableSpecError):
+    """Raised when a spec variant conflicts with package constraints."""
+
+    def __init__(self, provided, required):
+        super(UnsatisfiableVariantSpecError, self).__init__(
+            provided, required, "variant")