Merge pull request #549 from LLNL/bugfix/gh538-less-greedy-concretize

Bugfix/gh538 less greedy concretize

6 files changed, 222 insertions, 120 deletions

diff --git a/lib/spack/llnl/util/lang.py b/lib/spack/llnl/util/lang.py
index 1c4d1ed623..13d301f84e 100644
--- a/lib/spack/llnl/util/lang.py
+++ b/lib/spack/llnl/util/lang.py
@@ -235,11 +235,11 @@ def key_ordering(cls):
     if not has_method(cls, '_cmp_key'):
         raise TypeError("'%s' doesn't define _cmp_key()." % cls.__name__)
 
-    setter('__eq__', lambda s,o: o is not None and s._cmp_key() == o._cmp_key())
+    setter('__eq__', lambda s,o: (s is o) or (o is not None and s._cmp_key() == o._cmp_key()))
     setter('__lt__', lambda s,o: o is not None and s._cmp_key() <  o._cmp_key())
     setter('__le__', lambda s,o: o is not None and s._cmp_key() <= o._cmp_key())
 
-    setter('__ne__', lambda s,o: o is None or s._cmp_key() != o._cmp_key())
+    setter('__ne__', lambda s,o: (s is not o) and (o is None or s._cmp_key() != o._cmp_key()))
     setter('__gt__', lambda s,o: o is None or s._cmp_key() >  o._cmp_key())
     setter('__ge__', lambda s,o: o is None or s._cmp_key() >= o._cmp_key())
 
diff --git a/lib/spack/spack/concretize.py b/lib/spack/spack/concretize.py
index 8d29a03f93..8083f91982 100644
--- a/lib/spack/spack/concretize.py
+++ b/lib/spack/spack/concretize.py
@@ -51,10 +51,10 @@ class DefaultConcretizer(object):
     """
 
     def _valid_virtuals_and_externals(self, spec):
-        """Returns a list of spec/external-path pairs for both virtuals and externals
-           that can concretize this spec."""
-        # Get a list of candidate packages that could satisfy this spec
-        packages = []
+        """Returns a list of candidate virtual dep providers and external
+           packages that coiuld be used to concretize a spec."""
+        # First construct a list of concrete candidates to replace spec with.
+        candidates = [spec]
         if spec.virtual:
             providers = spack.repo.providers_for(spec)
             if not providers:
@@ -64,96 +64,72 @@ class DefaultConcretizer(object):
             if not spec_w_preferred_providers:
                 spec_w_preferred_providers = spec
             provider_cmp = partial(spack.pkgsort.provider_compare, spec_w_preferred_providers.name, spec.name)
-            packages = sorted(providers, cmp=provider_cmp)
-        else:
-            packages = [spec]
-
-        # For each candidate package, if it has externals add those to the candidates
-        # if it's not buildable, then only add the externals.
-        candidates = []
-        all_compilers = spack.compilers.all_compilers()
-        for pkg in packages:
-            externals = spec_externals(pkg)
-            buildable = is_spec_buildable(pkg)
-            if buildable:
-                candidates.append((pkg, None))
+            candidates = sorted(providers, cmp=provider_cmp)
+
+        # For each candidate package, if it has externals, add those to the usable list.
+        # if it's not buildable, then *only* add the externals.
+        usable = []
+        for cspec in candidates:
+            if is_spec_buildable(cspec):
+                usable.append(cspec)
+            externals = spec_externals(cspec)
             for ext in externals:
-                if ext[0].satisfies(spec):
-                    candidates.append(ext)
-        if not candidates:
+                if ext.satisfies(spec):
+                    usable.append(ext)
+
+        # If nothing is in the usable list now, it's because we aren't
+        # allowed to build anything.
+        if not usable:
             raise NoBuildError(spec)
 
         def cmp_externals(a, b):
-            if a[0].name != b[0].name:
-                #We're choosing between different providers. Maintain order from above sort
+            if a.name != b.name:
+                # We're choosing between different providers, so
+                # maintain order from provider sort
                 return candidates.index(a) - candidates.index(b)
-            result = cmp_specs(a[0], b[0])
+
+            result = cmp_specs(a, b)
             if result != 0:
                 return result
-            if not a[1] and b[1]:
-                return 1
-            if not b[1] and a[1]:
-                return -1
-            return cmp(a[1], b[1])
 
-        candidates = sorted(candidates, cmp=cmp_externals)
-        return candidates
+            # prefer external packages to internal packages.
+            if a.external is None or b.external is None:
+                return -cmp(a.external, b.external)
+            else:
+                return cmp(a.external, b.external)
+
+        usable.sort(cmp=cmp_externals)
+        return usable
 
 
-    def concretize_virtual_and_external(self, spec):
-        """From a list of candidate virtual and external packages, concretize to one that
-           is ABI compatible with the rest of the DAG."""
+    def choose_virtual_or_external(self, spec):
+        """Given a list of candidate virtual and external packages, try to
+           find one that is most ABI compatible.
+        """
         candidates = self._valid_virtuals_and_externals(spec)
         if not candidates:
-            return False
-
-        # Find the nearest spec in the dag that has a compiler.  We'll use that
-        # spec to test compiler compatibility.
-        other_spec = find_spec(spec, lambda(x): x.compiler)
-        if not other_spec:
-            other_spec = spec.root
-
-        # Choose an ABI-compatible candidate, or the first match otherwise.
-        candidate = None
-        if other_spec:
-            candidate = next((c for c in candidates if spack.abi.compatible(c[0], other_spec)), None)
-            if not candidate:
-                # Try a looser ABI matching
-                candidate = next((c for c in candidates if spack.abi.compatible(c[0], other_spec, loose=True)), None)
-        if not candidate:
-            # No ABI matches. Pick the top choice based on the orignal preferences.
-            candidate = candidates[0]
-        candidate_spec = candidate[0]
-        external = candidate[1]
-        changed = False
-
-        # If we're external then trim the dependencies
-        if external:
-            if (spec.dependencies):
-                changed = True
-            spec.dependencies = DependencyMap()
-            candidate_spec.dependencies = DependencyMap()
-
-        def fequal(candidate_field, spec_field):
-            return (not candidate_field) or (candidate_field == spec_field)
-        if (fequal(candidate_spec.name, spec.name) and
-            fequal(candidate_spec.versions, spec.versions) and
-            fequal(candidate_spec.compiler, spec.compiler) and
-            fequal(candidate_spec.architecture, spec.architecture) and
-            fequal(candidate_spec.dependencies, spec.dependencies) and
-            fequal(candidate_spec.variants, spec.variants) and
-            fequal(external, spec.external)):
-            return changed
-
-        # Refine this spec to the candidate.
-        if spec.virtual:
-            spec._replace_with(candidate_spec)
-            changed = True
-        if spec._dup(candidate_spec, deps=False, cleardeps=False):
-            changed = True
-        spec.external = external
-
-        return changed
+            return candidates
+
+        # Find the nearest spec in the dag that has a compiler.  We'll
+        # use that spec to calibrate compiler compatibility.
+        abi_exemplar = find_spec(spec, lambda(x): x.compiler)
+        if not abi_exemplar:
+            abi_exemplar = spec.root
+
+        # Make a list including ABI compatibility of specs with the exemplar.
+        strict = [spack.abi.compatible(c, abi_exemplar) for c in candidates]
+        loose  = [spack.abi.compatible(c, abi_exemplar, loose=True) for c in candidates]
+        keys = zip(strict, loose, candidates)
+
+        # Sort candidates from most to least compatibility.
+        # Note:
+        #   1. We reverse because True > False.
+        #   2. Sort is stable, so c's keep their order.
+        keys.sort(key=lambda k:k[:2], reverse=True)
+
+        # Pull the candidates back out and return them in order
+        candidates = [c for s,l,c in keys]
+        return candidates
 
 
     def concretize_version(self, spec):
@@ -238,7 +214,7 @@ class DefaultConcretizer(object):
            the default variants from the package specification.
         """
         changed = False
-        for name, variant in spec.package.variants.items():
+        for name, variant in spec.package_class.variants.items():
             if name not in spec.variants:
                 spec.variants[name] = spack.spec.VariantSpec(name, variant.default)
                 changed = True
diff --git a/lib/spack/spack/config.py b/lib/spack/spack/config.py
index a21dd6dbe1..6afd69b3ac 100644
--- a/lib/spack/spack/config.py
+++ b/lib/spack/spack/config.py
@@ -539,22 +539,25 @@ def print_section(section):
 
 
 def spec_externals(spec):
-    """Return a list of spec, directory pairs for each external location for spec"""
+    """Return a list of external specs (with external directory path filled in),
+       one for each known external installation."""
     allpkgs = get_config('packages')
     name = spec.name
-    spec_locations = []
 
+    external_specs = []
     pkg_paths = allpkgs.get(name, {}).get('paths', None)
     if not pkg_paths:
         return []
 
-    for pkg,path in pkg_paths.iteritems():
-        if not spec.satisfies(pkg):
-            continue
+    for external_spec, path in pkg_paths.iteritems():
         if not path:
+            # skip entries without paths (avoid creating extra Specs)
             continue
-        spec_locations.append( (spack.spec.Spec(pkg), path) )
-    return spec_locations
+
+        external_spec = spack.spec.Spec(external_spec, external=path)
+        if external_spec.satisfies(spec):
+            external_specs.append(external_spec)
+    return external_specs
 
 
 def is_spec_buildable(spec):
diff --git a/lib/spack/spack/repository.py b/lib/spack/spack/repository.py
index 3c3ba08bcc..d2fdc937f7 100644
--- a/lib/spack/spack/repository.py
+++ b/lib/spack/spack/repository.py
@@ -316,6 +316,11 @@ class RepoPath(object):
         return self.repo_for_pkg(spec).get(spec)
 
 
+    def get_pkg_class(self, pkg_name):
+        """Find a class for the spec's package and return the class object."""
+        return self.repo_for_pkg(pkg_name).get_pkg_class(pkg_name)
+
+
     @_autospec
     def dump_provenance(self, spec, path):
         """Dump provenance information for a spec to a particular path.
@@ -550,7 +555,7 @@ class Repo(object):
 
         key = hash(spec)
         if new or key not in self._instances:
-            package_class = self._get_pkg_class(spec.name)
+            package_class = self.get_pkg_class(spec.name)
             try:
                 copy = spec.copy() # defensive copy.  Package owns its spec.
                 self._instances[key] = package_class(copy)
@@ -715,7 +720,7 @@ class Repo(object):
         return self._modules[pkg_name]
 
 
-    def _get_pkg_class(self, pkg_name):
+    def get_pkg_class(self, pkg_name):
         """Get the class for the package out of its module.
 
         First loads (or fetches from cache) a module for the
diff --git a/lib/spack/spack/spec.py b/lib/spack/spack/spec.py
index c045e80365..d04135860e 100644
--- a/lib/spack/spack/spec.py
+++ b/lib/spack/spack/spec.py
@@ -353,7 +353,7 @@ class VariantMap(HashableMap):
     @property
     def concrete(self):
         return self.spec._concrete or all(
-            v in self for v in self.spec.package.variants)
+            v in self for v in self.spec.package_class.variants)
 
 
     def copy(self):
@@ -418,9 +418,11 @@ class Spec(object):
         # cases we've read them from a file want to assume normal.
         # This allows us to manipulate specs that Spack doesn't have
         # package.py files for.
-        self._normal = kwargs.get('normal', False)
+        self._normal   = kwargs.get('normal', False)
         self._concrete = kwargs.get('concrete', False)
-        self.external = None
+
+        # Allow a spec to be constructed with an external path.
+        self.external  = kwargs.get('external', None)
 
         # This allows users to construct a spec DAG with literals.
         # Note that given two specs a and b, Spec(a) copies a, but
@@ -499,6 +501,14 @@ class Spec(object):
 
 
     @property
+    def package_class(self):
+        """Internal package call gets only the class object for a package.
+           Use this to just get package metadata.
+        """
+        return spack.repo.get_pkg_class(self.name)
+
+
+    @property
     def virtual(self):
         """Right now, a spec is virtual if no package exists with its name.
 
@@ -786,8 +796,30 @@ class Spec(object):
         """Replace this virtual spec with a concrete spec."""
         assert(self.virtual)
         for name, dependent in self.dependents.items():
+            # remove self from all dependents.
+            del dependent.dependencies[self.name]
+
+            # add the replacement, unless it is already a dep of dependent.
+            if concrete.name not in dependent.dependencies:
+                dependent._add_dependency(concrete)
+
+
+    def _replace_node(self, replacement):
+        """Replace this spec with another.
+
+        Connects all dependents of this spec to its replacement, and
+        disconnects this spec from any dependencies it has. New spec
+        will have any dependencies the replacement had, and may need
+        to be normalized.
+
+        """
+        for name, dependent in self.dependents.items():
             del dependent.dependencies[self.name]
-            dependent._add_dependency(concrete)
+            dependent._add_dependency(replacement)
+
+        for name, dep in self.dependencies.items():
+            del dep.dependents[self.name]
+            del self.dependencies[dep.name]
 
 
     def _expand_virtual_packages(self):
@@ -807,18 +839,80 @@ class Spec(object):
               this are infrequent, but should implement this before it is
               a problem.
         """
+        # Make an index of stuff this spec already provides
+        self_index = ProviderIndex(self.traverse(), restrict=True)
+
         changed = False
         done = False
         while not done:
             done = True
             for spec in list(self.traverse()):
-                if spack.concretizer.concretize_virtual_and_external(spec):
-                    done = False
+                replacement = None
+                if spec.virtual:
+                    replacement = self._find_provider(spec, self_index)
+                    if replacement:
+                        # TODO: may break if in-place on self but
+                        # shouldn't happen if root is traversed first.
+                        spec._replace_with(replacement)
+                        done=False
+                        break
+
+                if not replacement:
+                    # Get a list of possible replacements in order of preference.
+                    candidates = spack.concretizer.choose_virtual_or_external(spec)
+
+                    # Try the replacements in order, skipping any that cause
+                    # satisfiability problems.
+                    for replacement in candidates:
+                        if replacement is spec:
+                            break
+
+                        # Replace spec with the candidate and normalize
+                        copy = self.copy()
+                        copy[spec.name]._dup(replacement.copy(deps=False))
+
+                        try:
+                            # If there are duplicate providers or duplicate provider
+                            # deps, consolidate them and merge constraints.
+                            copy.normalize(force=True)
+                            break
+                        except SpecError as e:
+                            # On error, we'll try the next replacement.
+                            continue
+
+                # If replacement is external then trim the dependencies
+                if replacement.external:
+                    if (spec.dependencies):
+                        changed = True
+                        spec.dependencies = DependencyMap()
+                    replacement.dependencies = DependencyMap()
+
+                # TODO: could this and the stuff in _dup be cleaned up?
+                def feq(cfield, sfield):
+                    return (not cfield) or (cfield == sfield)
+
+                if replacement is spec or (feq(replacement.name, spec.name) and
+                    feq(replacement.versions, spec.versions) and
+                    feq(replacement.compiler, spec.compiler) and
+                    feq(replacement.architecture, spec.architecture) and
+                    feq(replacement.dependencies, spec.dependencies) and
+                    feq(replacement.variants, spec.variants) and
+                    feq(replacement.external, spec.external)):
+                    continue
+
+                # Refine this spec to the candidate. This uses
+                # replace_with AND dup so that it can work in
+                # place. TODO: make this more efficient.
+                if spec.virtual:
+                    spec._replace_with(replacement)
+                    changed = True
+                if spec._dup(replacement, deps=False, cleardeps=False):
                     changed = True
 
-        # If there are duplicate providers or duplicate provider deps, this
-        # consolidates them and merge constraints.
-        changed |= self.normalize(force=True)
+                self_index.update(spec)
+                done=False
+                break
+
         return changed
 
 
@@ -842,7 +936,7 @@ class Spec(object):
         force = False
 
         while changed:
-            changes = (self.normalize(force=force),
+            changes = (self.normalize(force),
                        self._expand_virtual_packages(),
                        self._concretize_helper())
             changed = any(changes)
@@ -968,8 +1062,8 @@ class Spec(object):
 
     def _find_provider(self, vdep, provider_index):
         """Find provider for a virtual spec in the provider index.
-        Raise an exception if there is a conflicting virtual
-        dependency already in this spec.
+           Raise an exception if there is a conflicting virtual
+           dependency already in this spec.
         """
         assert(vdep.virtual)
         providers = provider_index.providers_for(vdep)
@@ -1010,17 +1104,14 @@ class Spec(object):
         """
         changed = False
 
-        # If it's a virtual dependency, try to find a provider and
-        # merge that.
+        # If it's a virtual dependency, try to find an existing
+        # provider in the spec, and merge that.
         if dep.virtual:
             visited.add(dep.name)
             provider = self._find_provider(dep, provider_index)
             if provider:
                 dep = provider
-
         else:
-            # if it's a real dependency, check whether it provides
-            # something already required in the spec.
             index = ProviderIndex([dep], restrict=True)
             for vspec in (v for v in spec_deps.values() if v.virtual):
                 if index.providers_for(vspec):
@@ -1117,13 +1208,14 @@ class Spec(object):
         # Get all the dependencies into one DependencyMap
         spec_deps = self.flat_dependencies(copy=False)
 
-        # Initialize index of virtual dependency providers
-        index = ProviderIndex(spec_deps.values(), restrict=True)
+        # Initialize index of virtual dependency providers if
+        # concretize didn't pass us one already
+        provider_index = ProviderIndex(spec_deps.values(), restrict=True)
 
         # traverse the package DAG and fill out dependencies according
         # to package files & their 'when' specs
         visited = set()
-        any_change = self._normalize_helper(visited, spec_deps, index)
+        any_change = self._normalize_helper(visited, spec_deps, provider_index)
 
         # If there are deps specified but not visited, they're not
         # actually deps of this package.  Raise an error.
@@ -1161,7 +1253,7 @@ class Spec(object):
 
             # Ensure that variants all exist.
             for vname, variant in spec.variants.items():
-                if vname not in spec.package.variants:
+                if vname not in spec.package_class.variants:
                     raise UnknownVariantError(spec.name, vname)
 
 
@@ -1402,13 +1494,12 @@ class Spec(object):
                Whether deps should be copied too.  Set to false to copy a
                spec but not its dependencies.
         """
-
         # We don't count dependencies as changes here
         changed = True
         if hasattr(self, 'name'):
-            changed = (self.name != other.name and self.versions != other.versions and \
-                       self.architecture != other.architecture and self.compiler != other.compiler and \
-                       self.variants != other.variants and self._normal != other._normal and \
+            changed = (self.name != other.name and self.versions != other.versions and
+                       self.architecture != other.architecture and self.compiler != other.compiler and
+                       self.variants != other.variants and self._normal != other._normal and
                        self.concrete != other.concrete and self.external != other.external)
 
         # Local node attributes get copied first.
diff --git a/lib/spack/spack/test/concretize.py b/lib/spack/spack/test/concretize.py
index 07828d8ea6..f264faf17a 100644
--- a/lib/spack/spack/test/concretize.py
+++ b/lib/spack/spack/test/concretize.py
@@ -142,6 +142,34 @@ class ConcretizeTest(MockPackagesTest):
                                 for spec in spack.repo.providers_for('mpi@3')))
 
 
+    def test_concretize_two_virtuals(self):
+        """Test a package with multiple virtual dependencies."""
+        s = Spec('hypre').concretize()
+
+
+    def test_concretize_two_virtuals_with_one_bound(self):
+        """Test a package with multiple virtual dependencies and one preset."""
+        s = Spec('hypre ^openblas').concretize()
+
+
+    def test_concretize_two_virtuals_with_two_bound(self):
+        """Test a package with multiple virtual dependencies and two of them preset."""
+        s = Spec('hypre ^openblas ^netlib-lapack').concretize()
+
+
+    def test_concretize_two_virtuals_with_dual_provider(self):
+        """Test a package with multiple virtual dependencies and force a provider
+           that provides both."""
+        s = Spec('hypre ^openblas-with-lapack').concretize()
+
+
+    def test_concretize_two_virtuals_with_dual_provider_and_a_conflict(self):
+        """Test a package with multiple virtual dependencies and force a provider
+           that provides both, and another conflicting package that provides one."""
+        s = Spec('hypre ^openblas-with-lapack ^netlib-lapack')
+        self.assertRaises(spack.spec.MultipleProviderError, s.concretize)
+
+
     def test_virtual_is_fully_expanded_for_callpath(self):
         # force dependence on fake "zmpi" by asking for MPI 10.0
         spec = Spec('callpath ^mpi@10.0')
@@ -281,4 +309,3 @@ class ConcretizeTest(MockPackagesTest):
                       Spec('d')),
                  Spec('e'))
         self.assertEqual(None, find_spec(s['b'], lambda s: '+foo' in s))
-