From f2761270f3c0506a689b484b0e12d7d6e9f4300d Mon Sep 17 00:00:00 2001 From: Todd Gamblin Date: Mon, 14 Mar 2016 05:04:01 -0700 Subject: 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. --- lib/spack/spack/concretize.py | 140 +++++++++++++++++------------------------- lib/spack/spack/config.py | 17 ++--- lib/spack/spack/spec.py | 129 +++++++++++++++++++++++++++++++------- 3 files changed, 174 insertions(+), 112 deletions(-) (limited to 'lib') 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. -- cgit v1.2.3-70-g09d2