Make concretization less greedy: add backtracking for virtuals.

- `_expand_virtual_packages` now gets a candidate list and will try
  all the candidates.

  - Good news: If the first virtual in the list conflicts with something else in
               the spec, we'll keep trying until we find a good one.

  - Bad news: Only looks as far as the next normalize(); can't see
              conflicts further ahead than that if they're inevitable
              some other virtual expansion.

- Refactor `concretize.py` to keep all the nasty spec graph stitching in
  `spec.py`. This is more similar to before externals support.

  - `concretize.py` now just returns a list of candidates sorted by
    ABI compatibility to `_expand_virtual_packages`, and `spec.py`
    handles testing the candidates.

- Refactor the way external paths are handled in `config.py` and `concretize.py`:

  - previously, `spec_externals` returned spec/path pairs.  Now it
    returns specs with `external` set. Makes code in `concretize.py`
    more natural.

3 files changed, 174 insertions, 112 deletions

diff --git a/lib/spack/spack/concretize.py b/lib/spack/spack/concretize.py
index 445ecd8896..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):
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/spec.py b/lib/spack/spack/spec.py
index 573e288d17..d04135860e 100644
--- a/lib/spack/spack/spec.py
+++ b/lib/spack/spack/spec.py
@@ -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
@@ -794,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]
-            dependent._add_dependency(concrete)
+
+            # 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(replacement)
+
+        for name, dep in self.dependencies.items():
+            del dep.dependents[self.name]
+            del self.dependencies[dep.name]
 
 
     def _expand_virtual_packages(self):
@@ -815,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
+
+                self_index.update(spec)
+                done=False
+                break
 
-        # If there are duplicate providers or duplicate provider deps, this
-        # consolidates them and merge constraints.
-        changed |= self.normalize(force=True)
         return changed
 
 
@@ -850,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)
@@ -976,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)
@@ -1018,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):
@@ -1125,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.
@@ -1410,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.