concretizer: simplify handling of virtual version constraints

Previously, the concretizer handled version constraints by comparing all
pairs of constraints and ensuring they satisfied each other. This led to
INCONSISTENT ressults from clingo, due to ambiguous semantics like:

    version_constraint_satisfies("mpi", ":1", ":3")
    version_constraint_satisfies("mpi", ":3", ":1")

To get around this, we introduce possible (fake) versions for virtuals,
based on their constraints. Essentially, we add any Versions,
VersionRange endpoints, and all such Versions and endpoints from
VersionLists to the constraint. Virtuals will have one of these synthetic
versions "picked" by the solver. This also allows us to remove a special
case from handling of `version_satisfies/3` -- virtuals now work just
like regular packages.

2 files changed, 29 insertions, 18 deletions

diff --git a/lib/spack/spack/solver/asp.py b/lib/spack/spack/solver/asp.py
index 9e4eb54930..26a6552240 100644
--- a/lib/spack/spack/solver/asp.py
+++ b/lib/spack/spack/solver/asp.py
@@ -37,7 +37,7 @@ import spack.package
 import spack.package_prefs
 import spack.repo
 import spack.variant
-from spack.version import ver
+import spack.version
 
 
 class Timer(object):
@@ -451,7 +451,7 @@ class SpackSolverSetup(object):
         if spec.concrete:
             return [fn.version(spec.name, spec.version)]
 
-        if spec.versions == ver(":"):
+        if spec.versions == spack.version.ver(":"):
             return []
 
         # record all version constraints for later
@@ -1175,6 +1175,10 @@ class SpackSolverSetup(object):
             self.gen.newline()
 
     def define_virtual_constraints(self):
+        """Define versions for constraints on virtuals.
+
+        Must be called before define_version_constraints().
+        """
         # aggregate constraints into per-virtual sets
         constraint_map = collections.defaultdict(lambda: set())
         for pkg_name, versions in self.version_constraints:
@@ -1182,13 +1186,28 @@ class SpackSolverSetup(object):
                 continue
             constraint_map[pkg_name].add(versions)
 
+        # extract all the real versions mentioned in version ranges
+        def versions_for(v):
+            if isinstance(v, spack.version.Version):
+                return [v]
+            elif isinstance(v, spack.version.VersionRange):
+                result = [v.start] if v.start else []
+                result += [v.end] if v.end else []
+                return result
+            elif isinstance(v, spack.version.VersionList):
+                return sum((versions_for(e) for e in v), [])
+            else:
+                raise TypeError("expected version type, found: %s" % type(v))
+
+        # define a set of synthetic possible versions for virtuals, so
+        # that `version_satisfies(Package, Constraint, Version)` has the
+        # same semantics for virtuals as for regular packages.
         for pkg_name, versions in sorted(constraint_map.items()):
-            for v1 in sorted(versions):
-                for v2 in sorted(versions):
-                    if v1.satisfies(v2):
-                        self.gen.fact(
-                            fn.version_constraint_satisfies(pkg_name, v1, v2)
-                        )
+            possible_versions = set(
+                sum([versions_for(v) for v in versions], [])
+            )
+            for version in sorted(possible_versions):
+                self.possible_versions[pkg_name].add(version)
 
     def define_compiler_version_constraints(self):
         compiler_list = spack.compilers.all_compiler_specs()
@@ -1401,7 +1420,7 @@ class SpecBuilder(object):
         self._specs[pkg].update_variant_validate(name, value)
 
     def version(self, pkg, version):
-        self._specs[pkg].versions = ver([version])
+        self._specs[pkg].versions = spack.version.ver([version])
 
     def node_compiler(self, pkg, compiler):
         self._specs[pkg].compiler = spack.spec.CompilerSpec(compiler)
diff --git a/lib/spack/spack/solver/concretize.lp b/lib/spack/spack/solver/concretize.lp
index 4bd3752132..bbc09bde64 100644
--- a/lib/spack/spack/solver/concretize.lp
+++ b/lib/spack/spack/solver/concretize.lp
@@ -24,8 +24,7 @@ version_weight(Package, Weight)
 % version_satisfies implies that exactly one of the satisfying versions
 % is the package's version, and vice versa.
 1 { version(Package, Version) : version_satisfies(Package, Constraint, Version) } 1
-  :- version_satisfies(Package, Constraint),
-  not virtual(Package).   % TODO: fix this and handle versionless virtuals separately
+  :- version_satisfies(Package, Constraint).
 version_satisfies(Package, Constraint)
   :- version(Package, Version), version_satisfies(Package, Constraint, Version).
 
@@ -159,12 +158,6 @@ dependency_conditions_hold(ID, Provider, Virtual) :-
   virtual(Virtual);
   provider_condition(ID, Provider, Virtual).
 
-% virtuals do not have well defined possible versions, so just ensure
-% that all constraints on versions are consistent
-:- virtual_node(Virtual),
-   version_satisfies(Virtual, V1), version_satisfies(Virtual, V2),
-   not version_constraint_satisfies(Virtual, V1, V2).
-
 % The provider provides the virtual if some provider condition holds.
 provides_virtual(Provider, Virtual) :-
    provider_condition(ID, Provider, Virtual),
@@ -231,7 +224,6 @@ provider_weight(Package, 100)
 #defined required_provider_condition/3.
 #defined required_provider_condition/4.
 #defined required_provider_condition/5.
-#defined version_constraint_satisfies/3.
 
 %-----------------------------------------------------------------------------
 % Spec Attributes