# -*- coding: utf-8 -*- # Copyright (C) 2012 Anaconda, Inc # SPDX-License-Identifier: BSD-3-Clause from __future__ import absolute_import, division, print_function, unicode_literals from collections import defaultdict, OrderedDict from logging import DEBUG, getLogger from ._vendor.auxlib.collection import frozendict from ._vendor.auxlib.decorators import memoize, memoizemethod from ._vendor.toolz import concat, groupby from .base.constants import ChannelPriority, MAX_CHANNEL_PRIORITY from .base.context import context from .common.compat import iteritems, iterkeys, itervalues, odict, on_win, text_type from .common.io import time_recorder from .common.logic import Clauses, get_sat_solver_cls, minimal_unsatisfiable_subset from .common.toposort import toposort from .exceptions import InvalidSpec, ResolvePackageNotFound, UnsatisfiableError from .models.channel import Channel, MultiChannel from .models.enums import NoarchType from .models.match_spec import MatchSpec from .models.records import PackageRecord from .models.version import VersionOrder log = getLogger(__name__) stdoutlog = getLogger('conda.stdoutlog') # used in conda build Unsatisfiable = UnsatisfiableError ResolvePackageNotFound = ResolvePackageNotFound get_sat_solver_cls = memoize(get_sat_solver_cls) def dashlist(iterable, indent=2): return ''.join('\n' + ' ' * indent + '- ' + str(x) for x in iterable) class Resolve(object): def __init__(self, index, processed=False, channels=()): self.index = index self.channels = channels self._channel_priorities_map = self._make_channel_priorities(channels) if channels else {} self._channel_priority = context.channel_priority self._solver_ignore_timestamps = context.solver_ignore_timestamps groups = groupby("name", itervalues(index)) trackers = defaultdict(list) for name in groups: unmanageable_precs = [prec for prec in groups[name] if prec.is_unmanageable] if unmanageable_precs: log.debug("restricting to unmanageable packages: %s", name) groups[name] = unmanageable_precs tf_precs = (prec for prec in groups[name] if prec.track_features) for prec in tf_precs: for feature_name in prec.track_features: trackers[feature_name].append(prec) self.groups = groups # Dict[package_name, List[PackageRecord]] self.trackers = trackers # Dict[track_feature, Set[PackageRecord]] self._cached_find_matches = {} # Dict[MatchSpec, Set[PackageRecord]] self.ms_depends_ = {} # Dict[PackageRecord, List[MatchSpec]] self._reduced_index_cache = {} self._strict_channel_cache = {} # sorting these in reverse order is effectively prioritizing # contstraint behavior from newer packages. It is applying broadening # reduction based on the latest packages, which may reduce the space # more, because more modern packages utilize constraints in more sane # ways (for example, using run_exports in conda-build 3) for name, group in self.groups.items(): self.groups[name] = sorted(group, key=self.version_key, reverse=True) def __hash__(self): return (super(Resolve, self).__hash__() ^ hash(frozenset(self.channels)) ^ hash(frozendict(self._channel_priorities_map)) ^ hash(self._channel_priority) ^ hash(self._solver_ignore_timestamps) ^ hash(frozendict((k, tuple(v)) for k, v in self.groups.items())) ^ hash(frozendict((k, tuple(v)) for k, v in self.trackers.items())) ^ hash(frozendict((k, tuple(v)) for k, v in self.ms_depends_.items())) ) def default_filter(self, features=None, filter=None): # TODO: fix this import; this is bad from .core.subdir_data import make_feature_record if filter is None: filter = {} else: filter.clear() filter.update({make_feature_record(fstr): False for fstr in iterkeys(self.trackers)}) if features: filter.update({make_feature_record(fstr): True for fstr in features}) return filter def valid(self, spec_or_prec, filter, optional=True): """Tests if a package, MatchSpec, or a list of both has satisfiable dependencies, assuming cyclic dependencies are always valid. Args: spec_or_prec: a package record, a MatchSpec, or an iterable of these. filter: a dictionary of (fkey,valid) pairs, used to consider a subset of dependencies, and to eliminate repeated searches. optional: if True (default), do not enforce optional specifications when considering validity. If False, enforce them. Returns: True if the full set of dependencies can be satisfied; False otherwise. If filter is supplied and update is True, it will be updated with the search results. """ def v_(spec): return v_ms_(spec) if isinstance(spec, MatchSpec) else v_fkey_(spec) def v_ms_(ms): return (optional and ms.optional or any(v_fkey_(fkey) for fkey in self.find_matches(ms))) def v_fkey_(prec): val = filter.get(prec) if val is None: filter[prec] = True try: depends = self.ms_depends(prec) except InvalidSpec: val = filter[prec] = False else: val = filter[prec] = all(v_ms_(ms) for ms in depends) return val result = v_(spec_or_prec) return result def valid2(self, spec_or_prec, filter_out, optional=True): def is_valid(_spec_or_prec): if isinstance(_spec_or_prec, MatchSpec): return is_valid_spec(_spec_or_prec) else: return is_valid_prec(_spec_or_prec) def is_valid_spec(_spec): return optional and _spec.optional or any( is_valid_prec(_prec) for _prec in self.find_matches(_spec) ) def is_valid_prec(prec): val = filter_out.get(prec) if val is None: filter_out[prec] = False try: has_valid_deps = all(is_valid_spec(ms) for ms in self.ms_depends(prec)) except InvalidSpec: val = filter_out[prec] = "invalid dep specs" else: val = filter_out[prec] = False if has_valid_deps else "invalid depends specs" return not val return is_valid(spec_or_prec) def invalid_chains(self, spec, filter, optional=True): """Constructs a set of 'dependency chains' for invalid specs. A dependency chain is a tuple of MatchSpec objects, starting with the requested spec, proceeding down the dependency tree, ending at a specification that cannot be satisfied. Uses self.valid_ as a filter, both to prevent chains and to allow other routines to prune the list of valid packages with additional criteria. Args: spec: a package key or MatchSpec filter: a dictionary of (prec, valid) pairs to be used when testing for package validity. optional: if True (default), do not enforce optional specifications when considering validity. If False, enforce them. Returns: A generator of tuples, empty if the MatchSpec is valid. """ def chains_(spec, names): if spec.name in names: return names.add(spec.name) if self.valid(spec, filter, optional): return precs = self.find_matches(spec) found = False for prec in precs: for m2 in self.ms_depends(prec): for x in chains_(m2, names): found = True yield (spec,) + x if not found: yield (spec,) return chains_(spec, set()) def invalid_chains2(self, spec, filter_out, optional=True): def chains_(spec, names): if spec.name in names: return names.add(spec.name) if self.valid2(spec, filter_out, optional): return precs = self.find_matches(spec) found = False for prec in precs: for m2 in self.ms_depends(prec): for x in chains_(m2, names): found = True yield (spec,) + x if not found: yield (spec,) return chains_(spec, set()) def verify_specs(self, specs): """Perform a quick verification that specs and dependencies are reasonable. Args: specs: An iterable of strings or MatchSpec objects to be tested. Returns: Nothing, but if there is a conflict, an error is thrown. Note that this does not attempt to resolve circular dependencies. """ non_tf_specs = [] bad_deps = [] feature_names = set() for ms in specs: _feature_names = ms.get_exact_value('track_features') if _feature_names: feature_names.update(_feature_names) else: non_tf_specs.append(ms) filter = self.default_filter(feature_names) for ms in non_tf_specs: bad_deps.extend(self.invalid_chains(ms, filter.copy())) if bad_deps: raise ResolvePackageNotFound(bad_deps) return non_tf_specs, feature_names def find_conflicts(self, specs): """Perform a deeper analysis on conflicting specifications, by attempting to find the common dependencies that might be the cause of conflicts. Args: specs: An iterable of strings or MatchSpec objects to be tested. It is assumed that the specs conflict. Returns: Nothing, because it always raises an UnsatisfiableError. Strategy: If we're here, we know that the specs conflict. This could be because: - One spec conflicts with another; e.g. ['numpy 1.5*', 'numpy >=1.6'] - One spec conflicts with a dependency of another; e.g. ['numpy 1.5*', 'scipy 0.12.0b1'] - Each spec depends on *the same package* but in a different way; e.g., ['A', 'B'] where A depends on numpy 1.5, and B on numpy 1.6. Technically, all three of these cases can be boiled down to the last one if we treat the spec itself as one of the "dependencies". There might be more complex reasons for a conflict, but this code only considers the ones above. The purpose of this code, then, is to identify packages (like numpy above) that all of the specs depend on *but in different ways*. We then identify the dependency chains that lead to those packages. """ sdeps = {} # For each spec, assemble a dictionary of dependencies, with package # name as key, and all of the matching packages as values. for ms in specs: rec = sdeps.setdefault(ms, {}) slist = [ms] while slist: ms2 = slist.pop() deps = rec.setdefault(ms2.name, set()) for fkey in self.find_matches(ms2): if fkey not in deps: deps.add(fkey) slist.extend(ms3 for ms3 in self.ms_depends(fkey) if ms3.name != ms.name) # Find the list of dependencies they have in common. And for each of # *those*, find the individual packages that they all share. Those need # to be removed as conflict candidates. commkeys = set.intersection(*(set(s.keys()) for s in sdeps.values())) commkeys = {k: set.intersection(*(v[k] for v in sdeps.values())) for k in commkeys} # and find the dependency chains that lead to them. bad_deps = [] for ms, sdep in iteritems(sdeps): filter = {} for mn, v in sdep.items(): if mn != ms.name and mn in commkeys: # Mark this package's "unique" dependencies as invalid for fkey in v - commkeys[mn]: filter[fkey] = False # Find the dependencies that lead to those invalid choices ndeps = set(self.invalid_chains(ms, filter, False)) # This may produce some additional invalid chains that we # don't care about. Select only those that terminate in our # predetermined set of "common" keys. ndeps = [nd for nd in ndeps if nd[-1].name in commkeys] if ndeps: bad_deps.extend(ndeps) else: # This means the package *itself* was the common conflict. bad_deps.append((ms,)) raise UnsatisfiableError(bad_deps) def _get_strict_channel(self, package_name): try: channel_name = self._strict_channel_cache[package_name] except KeyError: all_channel_names = set(prec.channel.name for prec in self.groups[package_name]) by_cp = {self._channel_priorities_map.get(cn, 1): cn for cn in all_channel_names} highest_priority = sorted(by_cp)[0] # highest priority is the lowest number channel_name = self._strict_channel_cache[package_name] = by_cp[highest_priority] return channel_name @memoizemethod def _broader(self, ms, specs_by_name): """prevent introduction of matchspecs that broaden our selection of choices""" if ms.name not in specs_by_name: return False matching_specs = specs_by_name[ms.name] # is there a version constraint defined for any existing spec, but not ms? if any('version' in _ for _ in matching_specs) and 'version' not in ms: return True # is there a build constraint defined for any of the specs, but not on ms? if any('build' in _ for _ in matching_specs) and 'build' not in ms: return True return False @time_recorder(module_name=__name__) def get_reduced_index(self, specs): # TODO: fix this import; this is bad from .core.subdir_data import make_feature_record strict_channel_priority = context.channel_priority == ChannelPriority.STRICT cache_key = strict_channel_priority, frozenset(specs) if cache_key in self._reduced_index_cache: return self._reduced_index_cache[cache_key] if log.isEnabledFor(DEBUG): log.debug('Retrieving packages for: %s', dashlist(sorted(text_type(s) for s in specs))) specs, features = self.verify_specs(specs) filter_out = {prec: False if val else "feature not enabled" for prec, val in iteritems(self.default_filter(features))} snames = set() top_level_spec = None cp_filter_applied = set() # values are package names def filter_group(_specs): # all _specs should be for the same package name name = next(iter(_specs)).name group = self.groups.get(name, ()) # implement strict channel priority if strict_channel_priority and name not in cp_filter_applied: sole_source_channel_name = self._get_strict_channel(name) for prec in group: if prec.channel.name != sole_source_channel_name: filter_out[prec] = "removed due to strict channel priority" cp_filter_applied.add(name) # Prune packages that don't match any of the patterns # or which have unsatisfiable dependencies nold = nnew = 0 for prec in group: if not filter_out.setdefault(prec, False): nold += 1 if not self.match_any(_specs, prec): filter_out[prec] = "incompatible with required spec %s" % top_level_spec continue unsatisfiable_dep_specs = tuple( ms for ms in self.ms_depends(prec) if not any(not filter_out.get(rec, False) for rec in self.find_matches(ms)) ) if unsatisfiable_dep_specs: filter_out[prec] = "unsatisfiable dependencies %s" % " ".join( str(s) for s in unsatisfiable_dep_specs ) continue filter_out[prec] = False nnew += 1 reduced = nnew < nold if reduced: log.debug('%s: pruned from %d -> %d' % (name, nold, nnew)) if any(ms.optional for ms in _specs): return reduced elif nnew == 0: # Indicates that a conflict was found; we can exit early return None # Perform the same filtering steps on any dependencies shared across # *all* packages in the group. Even if just one of the packages does # not have a particular dependency, it must be ignored in this pass. # Otherwise, we might do more filtering than we should---and it is # better to have extra packages here than missing ones. if reduced or name not in snames: snames.add(name) _dep_specs = groupby(lambda s: s.name, ( dep_spec for prec in group if not filter_out.get(prec, False) for dep_spec in self.ms_depends(prec) if not dep_spec.optional )) _dep_specs.pop("*", None) # discard track_features specs for deps in itervalues(_dep_specs): if len(deps) >= nnew: res = filter_group(set(deps)) if res: reduced = True elif res is None: # Indicates that a conflict was found; we can exit early return None return reduced # Iterate on pruning until no progress is made. We've implemented # what amounts to "double-elimination" here; packages get one additional # chance after their first "False" reduction. This catches more instances # where one package's filter affects another. But we don't have to be # perfect about this, so performance matters. for _ in range(2): snames.clear() slist = list(specs) reduced = False while slist: s = slist.pop() top_level_spec = s reduced = filter_group([s]) if reduced: slist.append(s) elif reduced is None: break if reduced is None: # This filter reset means that unsatisfiable indexes leak through. filter_out = {prec: False if val else "feature not enabled" for prec, val in iteritems(self.default_filter(features))} # TODO: raise unsatisfiable exception here # Messaging to users should be more descriptive. # 1. Are there no direct matches? # 2. Are there no matches for first-level dependencies? # 3. Have the first level dependencies been invalidated? break # Determine all valid packages in the dependency graph reduced_index2 = {prec: prec for prec in (make_feature_record(fstr) for fstr in features)} explicit_spec_list = set(specs) for explicit_spec in explicit_spec_list: add_these_precs2 = tuple( prec for prec in self.find_matches(explicit_spec) if prec not in reduced_index2 and self.valid2(prec, filter_out)) if strict_channel_priority and add_these_precs2: strict_channel_name = self._get_strict_channel(add_these_precs2[0].name) add_these_precs2 = tuple( prec for prec in add_these_precs2 if prec.channel.name == strict_channel_name ) reduced_index2.update((prec, prec) for prec in add_these_precs2) for pkg in add_these_precs2: # what we have seen is only relevant within the context of a single package # that is picked up because of an explicit spec. We don't want the # broadening check to apply across packages at the explicit level; only # at the level of deps below that explicit package. seen_specs = set() specs_by_name = {} dep_specs = set(self.ms_depends(pkg)) this_pkg_constraints = {} for dep in dep_specs: specs = specs_by_name.get(dep.name, set()) specs.add(dep) specs_by_name[dep.name] = specs this_pkg_constraints = frozendict( {k: frozenset(v) for k, v in specs_by_name.items()}) while(dep_specs): # used for debugging # size_index = len(reduced_index2) # specs_added = [] ms = dep_specs.pop() seen_specs.add(ms) for dep_pkg in (_ for _ in self.find_matches(ms) if _ not in reduced_index2): if not self.valid2(dep_pkg, filter_out): continue # expand the reduced index if not using strict channel priority, # or if using it and this package is in the appropriate channel if (not strict_channel_priority or (self._get_strict_channel(dep_pkg.name) == dep_pkg.channel.name)): reduced_index2[dep_pkg] = dep_pkg # recurse to deps of this dep new_specs = set(self.ms_depends(dep_pkg)) - seen_specs for new_ms in new_specs: # We do not pull packages into the reduced index due # to a track_features dependency. Remember, a feature # specifies a "soft" dependency: it must be in the # environment, but it is not _pulled_ in. The SAT # logic doesn't do a perfect job of capturing this # behavior, but keeping these packags out of the # reduced index helps. Of course, if _another_ # package pulls it in by dependency, that's fine. if ('track_features' not in new_ms and not self._broader(new_ms, this_pkg_constraints)): dep_specs.add(new_ms) # if new_ms not in dep_specs: # specs_added.append(new_ms) else: seen_specs.add(new_ms) # debugging info - see what specs are bringing in the largest blobs # if size_index != len(reduced_index2): # print("MS {} added {} pkgs to index".format(ms, # len(reduced_index2) - size_index)) # if specs_added: # print("MS {} added {} specs to further examination".format(ms, # specs_added)) reduced_index2 = frozendict(reduced_index2) self._reduced_index_cache[cache_key] = reduced_index2 return reduced_index2 def match_any(self, mss, prec): return any(ms.match(prec) for ms in mss) def find_matches(self, spec): # type: (MatchSpec) -> Set[PackageRecord] res = self._cached_find_matches.get(spec, None) if res is not None: return res spec_name = spec.get_exact_value('name') if spec_name: candidate_precs = self.groups.get(spec_name, ()) elif spec.get_exact_value('track_features'): feature_names = spec.get_exact_value('track_features') candidate_precs = concat( self.trackers.get(feature_name, ()) for feature_name in feature_names ) else: candidate_precs = itervalues(self.index) res = tuple(p for p in candidate_precs if spec.match(p)) self._cached_find_matches[spec] = res return res def ms_depends(self, prec): # type: (PackageRecord) -> List[MatchSpec] deps = self.ms_depends_.get(prec) if deps is None: deps = [MatchSpec(d) for d in prec.combined_depends] deps.extend(MatchSpec(track_features=feat) for feat in prec.features) self.ms_depends_[prec] = deps return deps def version_key(self, prec, vtype=None): channel = prec.channel channel_priority = self._channel_priorities_map.get(channel.name, 1) # TODO: ask @mcg1969 why the default value is 1 here # NOQA valid = 1 if channel_priority < MAX_CHANNEL_PRIORITY else 0 version_comparator = VersionOrder(prec.get('version', '')) build_number = prec.get('build_number', 0) build_string = prec.get('build') if self._channel_priority != ChannelPriority.DISABLED: vkey = [valid, -channel_priority, version_comparator, build_number] else: vkey = [valid, version_comparator, -channel_priority, build_number] if self._solver_ignore_timestamps: vkey.append(build_string) else: vkey.extend((prec.get('timestamp', 0), build_string)) return vkey @staticmethod def _make_channel_priorities(channels): priorities_map = odict() for priority_counter, chn in enumerate(concat( (Channel(cc) for cc in c._channels) if isinstance(c, MultiChannel) else (c,) for c in (Channel(c) for c in channels) )): channel_name = chn.name if channel_name in priorities_map: continue priorities_map[channel_name] = min(priority_counter, MAX_CHANNEL_PRIORITY - 1) return priorities_map def get_pkgs(self, ms, emptyok=False): # pragma: no cover # legacy method for conda-build ms = MatchSpec(ms) precs = self.find_matches(ms) if not precs and not emptyok: raise ResolvePackageNotFound([(ms,)]) return sorted(precs, key=self.version_key) @staticmethod def to_sat_name(val): # val can be a PackageRecord or MatchSpec if isinstance(val, PackageRecord): return val.dist_str() elif isinstance(val, MatchSpec): return '@s@' + text_type(val) + ('?' if val.optional else '') else: raise NotImplementedError() @staticmethod def to_feature_metric_id(prec_dist_str, feat): return '@fm@%s@%s' % (prec_dist_str, feat) def push_MatchSpec(self, C, spec): spec = MatchSpec(spec) sat_name = self.to_sat_name(spec) m = C.from_name(sat_name) if m is not None: # the spec has already been pushed onto the clauses stack return sat_name simple = spec._is_single() nm = spec.get_exact_value('name') tf = frozenset(_tf for _tf in ( f.strip() for f in spec.get_exact_value('track_features') or () ) if _tf) if nm: tgroup = libs = self.groups.get(nm, []) elif tf: assert len(tf) == 1 k = next(iter(tf)) tgroup = libs = self.trackers.get(k, []) else: tgroup = libs = self.index.keys() simple = False if not simple: libs = [fkey for fkey in tgroup if spec.match(fkey)] if len(libs) == len(tgroup): if spec.optional: m = True elif not simple: ms2 = MatchSpec(track_features=tf) if tf else MatchSpec(nm) m = C.from_name(self.push_MatchSpec(C, ms2)) if m is None: sat_names = [self.to_sat_name(prec) for prec in libs] if spec.optional: ms2 = MatchSpec(track_features=tf) if tf else MatchSpec(nm) sat_names.append('!' + self.to_sat_name(ms2)) m = C.Any(sat_names) C.name_var(m, sat_name) return sat_name @time_recorder(module_name=__name__) def gen_clauses(self): C = Clauses(sat_solver_cls=get_sat_solver_cls(context.sat_solver)) for name, group in iteritems(self.groups): group = [self.to_sat_name(prec) for prec in group] # Create one variable for each package for sat_name in group: C.new_var(sat_name) # Create one variable for the group m = C.new_var(self.to_sat_name(MatchSpec(name))) # Exactly one of the package variables, OR # the negation of the group variable, is true C.Require(C.ExactlyOne, group + [C.Not(m)]) # If a package is installed, its dependencies must be as well for prec in itervalues(self.index): nkey = C.Not(self.to_sat_name(prec)) for ms in self.ms_depends(prec): C.Require(C.Or, nkey, self.push_MatchSpec(C, ms)) if log.isEnabledFor(DEBUG): log.debug("gen_clauses returning with clause count: %d", C.get_clause_count()) return C def generate_spec_constraints(self, C, specs): result = [(self.push_MatchSpec(C, ms),) for ms in specs] if log.isEnabledFor(DEBUG): log.debug( "generate_spec_constraints returning with clause count: %d", C.get_clause_count()) return result def generate_feature_count(self, C): result = {self.push_MatchSpec(C, MatchSpec(track_features=name)): 1 for name in iterkeys(self.trackers)} if log.isEnabledFor(DEBUG): log.debug( "generate_feature_count returning with clause count: %d", C.get_clause_count()) return result def generate_update_count(self, C, specs): return {'!'+ms.target: 1 for ms in specs if ms.target and C.from_name(ms.target)} def generate_feature_metric(self, C): eq = {} # a C.minimize() objective: Dict[varname, coeff] # Given a pair (prec, feature), assign a "1" score IF: # - The prec is installed # - The prec does NOT require the feature # - At least one package in the group DOES require the feature # - A package that tracks the feature is installed for name, group in iteritems(self.groups): prec_feats = {self.to_sat_name(prec): set(prec.features) for prec in group} active_feats = set.union(*prec_feats.values()).intersection(self.trackers) for feat in active_feats: clause_id_for_feature = self.push_MatchSpec(C, MatchSpec(track_features=feat)) for prec_sat_name, features in prec_feats.items(): if feat not in features: feature_metric_id = self.to_feature_metric_id(prec_sat_name, feat) C.name_var(C.And(prec_sat_name, clause_id_for_feature), feature_metric_id) eq[feature_metric_id] = 1 return eq def generate_removal_count(self, C, specs): return {'!'+self.push_MatchSpec(C, ms.name): 1 for ms in specs} def generate_install_count(self, C, specs): return {self.push_MatchSpec(C, ms.name): 1 for ms in specs if ms.optional} def generate_package_count(self, C, missing): return {self.push_MatchSpec(C, nm): 1 for nm in missing} def generate_version_metrics(self, C, specs, include0=False): # each of these are weights saying how well packages match the specs # format for each: a C.minimize() objective: Dict[varname, coeff] eqc = {} # channel eqv = {} # version eqb = {} # build number eqt = {} # timestamp sdict = {} # Dict[package_name, PackageRecord] for s in specs: s = MatchSpec(s) # needed for testing sdict.setdefault(s.name, []) # # TODO: this block is important! can't leave it commented out # rec = sdict.setdefault(s.name, []) # if s.target: # dist = Dist(s.target) # if dist in self.index: # if self.index[dist].get('priority', 0) < MAX_CHANNEL_PRIORITY: # rec.append(dist) for name, targets in iteritems(sdict): pkgs = [(self.version_key(p), p) for p in self.groups.get(name, [])] pkey = None # keep in mind that pkgs is already sorted according to version_key (a tuple, # so composite sort key). Later entries in the list are, by definition, # greater in some way, so simply comparing with != suffices. for version_key, prec in pkgs: if targets and any(prec == t for t in targets): continue if pkey is None: ic = iv = ib = it = 0 # valid package, channel priority elif pkey[0] != version_key[0] or pkey[1] != version_key[1]: ic += 1 iv = ib = it = 0 # version elif pkey[2] != version_key[2]: iv += 1 ib = it = 0 # build number elif pkey[3] != version_key[3]: ib += 1 it = 0 elif not self._solver_ignore_timestamps and pkey[4] != version_key[4]: it += 1 prec_sat_name = self.to_sat_name(prec) if ic or include0: eqc[prec_sat_name] = ic if iv or include0: eqv[prec_sat_name] = iv if ib or include0: eqb[prec_sat_name] = ib if it or include0: eqt[prec_sat_name] = it pkey = version_key return eqc, eqv, eqb, eqt def dependency_sort(self, must_have): # type: (Dict[package_name, PackageRecord]) -> List[PackageRecord] assert isinstance(must_have, dict) digraph = {} # Dict[package_name, Set[dependent_package_names]] for package_name, prec in iteritems(must_have): if prec in self.index: digraph[package_name] = set(ms.name for ms in self.ms_depends(prec)) # There are currently at least three special cases to be aware of. # 1. The `toposort()` function, called below, contains special case code to remove # any circular dependency between python and pip. # 2. conda/plan.py has special case code for menuinst # Always link/unlink menuinst first/last on windows in case a subsequent # package tries to import it to create/remove a shortcut # 3. On windows, python noarch packages need an implicit dependency on conda added, if # conda is in the list of packages for the environment. Python noarch packages # that have entry points use conda's own conda.exe python entry point binary. If conda # is going to be updated during an operation, the unlink / link order matters. # See issue #6057. if on_win and 'conda' in digraph: for package_name, dist in iteritems(must_have): record = self.index.get(prec) if hasattr(record, 'noarch') and record.noarch == NoarchType.python: digraph[package_name].add('conda') sorted_keys = toposort(digraph) must_have = must_have.copy() # Take all of the items in the sorted keys # Don't fail if the key does not exist result = [must_have.pop(key) for key in sorted_keys if key in must_have] # Take any key that were not sorted result.extend(must_have.values()) return result def environment_is_consistent(self, installed): log.debug('Checking if the current environment is consistent') if not installed: return None, [] sat_name_map = {} # Dict[sat_name, PackageRecord] specs = [] for prec in installed: sat_name_map[self.to_sat_name(prec)] = prec specs.append(MatchSpec('%s %s %s' % (prec.name, prec.version, prec.build))) r2 = Resolve(OrderedDict((prec, prec) for prec in installed), True, channels=self.channels) C = r2.gen_clauses() constraints = r2.generate_spec_constraints(C, specs) solution = C.sat(constraints) return bool(solution) def get_conflicting_specs(self, specs): if not specs: return () reduced_index = self.get_reduced_index(specs) # Check if satisfiable def mysat(specs, add_if=False): constraints = r2.generate_spec_constraints(C, specs) return C.sat(constraints, add_if) r2 = Resolve(reduced_index, True, channels=self.channels) C = r2.gen_clauses() solution = mysat(specs, True) if solution: return () else: # This first result is just a single unsatisfiable core. There may be several. unsat_specs = list(minimal_unsatisfiable_subset(specs, sat=mysat)) satisfiable_specs = set(specs) - set(unsat_specs) # In this loop, we test each unsatisfiable spec individually against the satisfiable # specs to ensure there are no other unsatisfiable specs in the set. final_unsat_specs = set() while unsat_specs: this_spec = unsat_specs.pop(0) final_unsat_specs.add(this_spec) test_specs = satisfiable_specs | {this_spec} C = r2.gen_clauses() # TODO: wasteful call, but Clauses() needs refactored solution = mysat(test_specs, True) if not solution: these_unsat = minimal_unsatisfiable_subset(test_specs, sat=mysat) if len(these_unsat) > 1: unsat_specs.extend(these_unsat) satisfiable_specs -= set(unsat_specs) return tuple(final_unsat_specs) def bad_installed(self, installed, new_specs): log.debug('Checking if the current environment is consistent') if not installed: return None, [] sat_name_map = {} # Dict[sat_name, PackageRecord] specs = [] for prec in installed: sat_name_map[self.to_sat_name(prec)] = prec specs.append(MatchSpec('%s %s %s' % (prec.name, prec.version, prec.build))) new_index = {prec: prec for prec in itervalues(sat_name_map)} name_map = {p.name: p for p in new_index} if 'python' in name_map and 'pip' not in name_map: python_prec = new_index[name_map['python']] if 'pip' in python_prec.depends: # strip pip dependency from python if not installed in environment new_deps = [d for d in python_prec.depends if d != 'pip'] python_prec.depends = new_deps r2 = Resolve(new_index, True, channels=self.channels) C = r2.gen_clauses() constraints = r2.generate_spec_constraints(C, specs) solution = C.sat(constraints) limit = xtra = None if not solution or xtra: def get_(name, snames): if name not in snames: snames.add(name) for fn in self.groups.get(name, []): for ms in self.ms_depends(fn): get_(ms.name, snames) # New addition: find the largest set of installed packages that # are consistent with each other, and include those in the # list of packages to maintain consistency with snames = set() eq_optional_c = r2.generate_removal_count(C, specs) solution, _ = C.minimize(eq_optional_c, C.sat()) snames.update(sat_name_map[sat_name]['name'] for sat_name in (C.from_index(s) for s in solution) if sat_name and sat_name[0] != '!' and '@' not in sat_name) # Existing behavior: keep all specs and their dependencies for spec in new_specs: get_(MatchSpec(spec).name, snames) if len(snames) < len(sat_name_map): limit = snames xtra = [rec for sat_name, rec in iteritems(sat_name_map) if rec['name'] not in snames] log.debug('Limiting solver to the following packages: %s', ', '.join(limit)) if xtra: log.debug('Packages to be preserved: %s', xtra) return limit, xtra def restore_bad(self, pkgs, preserve): if preserve: sdict = {prec.name: prec for prec in pkgs} pkgs.extend(p for p in preserve if p.name not in sdict) def install_specs(self, specs, installed, update_deps=True): specs = set(map(MatchSpec, specs)) snames = {s.name for s in specs} log.debug('Checking satisfiability of current install') limit, preserve = self.bad_installed(installed, specs) for prec in installed: if prec not in self.index: continue name, version, build = prec.name, prec.version, prec.build schannel = prec.channel.canonical_name if name in snames or limit is not None and name not in limit: continue # If update_deps=True, set the target package in MatchSpec so that # the solver can minimize the version change. If update_deps=False, # fix the version and build so that no change is possible. if update_deps: # TODO: fix target here spec = MatchSpec(name=name, target=prec.dist_str()) else: spec = MatchSpec(name=name, version=version, build=build, channel=schannel) specs.add(spec) return frozenset(specs), preserve def install(self, specs, installed=None, update_deps=True, returnall=False): specs, preserve = self.install_specs(specs, installed or [], update_deps) pkgs = self.solve(specs, returnall=returnall, _remove=False) self.restore_bad(pkgs, preserve) return pkgs def remove_specs(self, specs, installed): nspecs = [] # There's an imperfect thing happening here. "specs" nominally contains # a list of package names or track_feature values to be removed. But # because of add_defaults_to_specs it may also contain version contraints # like "python 2.7*", which are *not* asking for python to be removed. # We need to separate these two kinds of specs here. for s in map(MatchSpec, specs): # Since '@' is an illegal version number, this ensures that all of # these matches will never match an actual package. Combined with # optional=True, this has the effect of forcing their removal. if s._is_single(): nspecs.append(MatchSpec(s, version='@', optional=True)) else: nspecs.append(MatchSpec(s, optional=True)) snames = set(s.name for s in nspecs if s.name) limit, _ = self.bad_installed(installed, nspecs) preserve = [] for prec in installed: nm, ver = prec.name, prec.version if nm in snames: continue elif limit is not None: preserve.append(prec) else: # TODO: fix target here nspecs.append(MatchSpec(name=nm, version='>='+ver if ver else None, optional=True, target=prec.dist_str())) return nspecs, preserve def remove(self, specs, installed): specs, preserve = self.remove_specs(specs, installed) pkgs = self.solve(specs, _remove=True) self.restore_bad(pkgs, preserve) return pkgs @time_recorder(module_name=__name__) def solve(self, specs, returnall=False, _remove=False): # type: (List[str], bool) -> List[PackageRecord] if log.isEnabledFor(DEBUG): log.debug('Solving for: %s', dashlist(sorted(text_type(s) for s in specs))) # Find the compliant packages log.debug("Solve: Getting reduced index of compliant packages") len0 = len(specs) specs = frozenset(map(MatchSpec, specs)) reduced_index = self.get_reduced_index(specs) if not reduced_index: return False if reduced_index is None else ([[]] if returnall else []) # Check if satisfiable log.debug("Solve: determining satisfiability") def mysat(specs, add_if=False): constraints = r2.generate_spec_constraints(C, specs) return C.sat(constraints, add_if) # Return a solution of packages def clean(sol): return [q for q in (C.from_index(s) for s in sol) if q and q[0] != '!' and '@' not in q] def is_converged(solution): """ Determine if the SAT problem has converged to a single solution. This is determined by testing for a SAT solution with the current clause set and a clause in which at least one of the packages in the current solution is excluded. If a solution exists the problem has not converged as multiple solutions still exist. """ psolution = clean(solution) nclause = tuple(C.Not(C.from_name(q)) for q in psolution) if C.sat((nclause,), includeIf=False) is None: return True return False r2 = Resolve(reduced_index, True, channels=self.channels) C = r2.gen_clauses() solution = mysat(specs, True) if not solution: specs = minimal_unsatisfiable_subset(specs, sat=mysat) self.find_conflicts(specs) speco = [] # optional packages specr = [] # requested packages speca = [] # all other packages specm = set(r2.groups) # missing from specs for k, s in enumerate(specs): if s.name in specm: specm.remove(s.name) if not s.optional: (speca if s.target or k >= len0 else specr).append(s) elif any(r2.find_matches(s)): s = MatchSpec(s.name, optional=True, target=s.target) speco.append(s) speca.append(s) speca.extend(MatchSpec(s) for s in specm) # Removed packages: minimize count log.debug("Solve: minimize removed packages") if _remove: eq_optional_c = r2.generate_removal_count(C, speco) solution, obj7 = C.minimize(eq_optional_c, solution) log.debug('Package removal metric: %d', obj7) # Requested packages: maximize versions log.debug("Solve: maximize versions of requested packages") eq_req_c, eq_req_v, eq_req_b, eq_req_t = r2.generate_version_metrics(C, specr) solution, obj3a = C.minimize(eq_req_c, solution) solution, obj3 = C.minimize(eq_req_v, solution) log.debug('Initial package channel/version metric: %d/%d', obj3a, obj3) # Track features: minimize feature count log.debug("Solve: minimize track_feature count") eq_feature_count = r2.generate_feature_count(C) solution, obj1 = C.minimize(eq_feature_count, solution) log.debug('Track feature count: %d', obj1) # Featured packages: minimize number of featureless packages # installed when a featured alternative is feasible. # For example, package name foo exists with two built packages. One with # 'track_features: 'feat1', and one with 'track_features': 'feat2'. # The previous "Track features" minimization pass has chosen 'feat1' for the # environment, but not 'feat2'. In this case, the 'feat2' version of foo is # considered "featureless." eq_feature_metric = r2.generate_feature_metric(C) solution, obj2 = C.minimize(eq_feature_metric, solution) log.debug('Package misfeature count: %d', obj2) # Requested packages: maximize builds log.debug("Solve: maximize build numbers of requested packages") solution, obj4 = C.minimize(eq_req_b, solution) log.debug('Initial package build metric: %d', obj4) # Optional installations: minimize count if not _remove: log.debug("Solve: minimize number of optional installations") eq_optional_install = r2.generate_install_count(C, speco) solution, obj49 = C.minimize(eq_optional_install, solution) log.debug('Optional package install metric: %d', obj49) # Dependencies: minimize the number of packages that need upgrading log.debug("Solve: minimize number of necessary upgrades") eq_u = r2.generate_update_count(C, speca) solution, obj50 = C.minimize(eq_u, solution) log.debug('Dependency update count: %d', obj50) # Remaining packages: maximize versions, then builds log.debug("Solve: maximize versions and builds of indirect dependencies") eq_c, eq_v, eq_b, eq_t = r2.generate_version_metrics(C, speca) solution, obj5a = C.minimize(eq_c, solution) solution, obj5 = C.minimize(eq_v, solution) solution, obj6 = C.minimize(eq_b, solution) log.debug('Additional package channel/version/build metrics: %d/%d/%d', obj5a, obj5, obj6) # Prune unnecessary packages log.debug("Solve: prune unnecessary packages") eq_c = r2.generate_package_count(C, specm) solution, obj7 = C.minimize(eq_c, solution, trymax=True) log.debug('Weak dependency count: %d', obj7) converged = is_converged(solution) if not converged: # Maximize timestamps eq_t.update(eq_req_t) solution, obj6t = C.minimize(eq_t, solution) log.debug('Timestamp metric: %d', obj6t) log.debug('Looking for alternate solutions') nsol = 1 psolutions = [] psolution = clean(solution) psolutions.append(psolution) while True: nclause = tuple(C.Not(C.from_name(q)) for q in psolution) solution = C.sat((nclause,), True) if solution is None: break nsol += 1 if nsol > 10: log.debug('Too many solutions; terminating') break psolution = clean(solution) psolutions.append(psolution) if nsol > 1: psols2 = list(map(set, psolutions)) common = set.intersection(*psols2) diffs = [sorted(set(sol) - common) for sol in psols2] if not context.json: stdoutlog.info( '\nWarning: %s possible package resolutions ' '(only showing differing packages):%s%s' % ('>10' if nsol > 10 else nsol, dashlist(', '.join(diff) for diff in diffs), '\n ... and others' if nsol > 10 else '')) # def stripfeat(sol): # return sol.split('[')[0] new_index = {self.to_sat_name(prec): prec for prec in itervalues(self.index)} if returnall: if len(psolutions) > 1: raise RuntimeError() # TODO: clean up this mess # return [sorted(Dist(stripfeat(dname)) for dname in psol) for psol in psolutions] # return [sorted((new_index[sat_name] for sat_name in psol), key=lambda x: x.name) # for psol in psolutions] # return sorted(Dist(stripfeat(dname)) for dname in psolutions[0]) return sorted((new_index[sat_name] for sat_name in psolutions[0]), key=lambda x: x.name)