1# coding: utf-8 2from __future__ import absolute_import, division, print_function, unicode_literals 3 4import copy 5from functools import partial 6from itertools import chain, count, groupby 7 8from pip._internal.req.constructors import install_req_from_line 9from pip._internal.req.req_tracker import update_env_context_manager 10 11from . import click 12from .logging import log 13from .utils import ( 14 UNSAFE_PACKAGES, 15 format_requirement, 16 format_specifier, 17 is_pinned_requirement, 18 is_url_requirement, 19 key_from_ireq, 20) 21 22green = partial(click.style, fg="green") 23magenta = partial(click.style, fg="magenta") 24 25 26class RequirementSummary(object): 27 """ 28 Summary of a requirement's properties for comparison purposes. 29 """ 30 31 def __init__(self, ireq): 32 self.req = ireq.req 33 self.key = key_from_ireq(ireq) 34 self.extras = frozenset(ireq.extras) 35 self.specifier = ireq.specifier 36 37 def __eq__(self, other): 38 return ( 39 self.key == other.key 40 and self.specifier == other.specifier 41 and self.extras == other.extras 42 ) 43 44 def __hash__(self): 45 return hash((self.key, self.specifier, self.extras)) 46 47 def __str__(self): 48 return repr((self.key, str(self.specifier), sorted(self.extras))) 49 50 51def combine_install_requirements(repository, ireqs): 52 """ 53 Return a single install requirement that reflects a combination of 54 all the inputs. 55 """ 56 # We will store the source ireqs in a _source_ireqs attribute; 57 # if any of the inputs have this, then use those sources directly. 58 source_ireqs = [] 59 for ireq in ireqs: 60 source_ireqs.extend(getattr(ireq, "_source_ireqs", [ireq])) 61 62 # Optimization. Don't bother with combination logic. 63 if len(source_ireqs) == 1: 64 return source_ireqs[0] 65 66 # deepcopy the accumulator so as to not modify the inputs 67 combined_ireq = copy.deepcopy(source_ireqs[0]) 68 repository.copy_ireq_dependencies(source_ireqs[0], combined_ireq) 69 70 for ireq in source_ireqs[1:]: 71 # NOTE we may be losing some info on dropped reqs here 72 combined_ireq.req.specifier &= ireq.req.specifier 73 if combined_ireq.constraint: 74 # We don't find dependencies for constraint ireqs, so copy them 75 # from non-constraints: 76 repository.copy_ireq_dependencies(ireq, combined_ireq) 77 combined_ireq.constraint &= ireq.constraint 78 # Return a sorted, de-duped tuple of extras 79 combined_ireq.extras = tuple( 80 sorted(set(tuple(combined_ireq.extras) + tuple(ireq.extras))) 81 ) 82 83 # InstallRequirements objects are assumed to come from only one source, and 84 # so they support only a single comes_from entry. This function breaks this 85 # model. As a workaround, we deterministically choose a single source for 86 # the comes_from entry, and add an extra _source_ireqs attribute to keep 87 # track of multiple sources for use within pip-tools. 88 if len(source_ireqs) > 1: 89 if any(ireq.comes_from is None for ireq in source_ireqs): 90 # None indicates package was directly specified. 91 combined_ireq.comes_from = None 92 else: 93 # Populate the comes_from field from one of the sources. 94 # Requirement input order is not stable, so we need to sort: 95 # We choose the shortest entry in order to keep the printed 96 # representation as concise as possible. 97 combined_ireq.comes_from = min( 98 (ireq.comes_from for ireq in source_ireqs), 99 key=lambda x: (len(str(x)), str(x)), 100 ) 101 combined_ireq._source_ireqs = source_ireqs 102 return combined_ireq 103 104 105class Resolver(object): 106 def __init__( 107 self, 108 constraints, 109 repository, 110 cache, 111 prereleases=False, 112 clear_caches=False, 113 allow_unsafe=False, 114 ): 115 """ 116 This class resolves a given set of constraints (a collection of 117 InstallRequirement objects) by consulting the given Repository and the 118 DependencyCache. 119 """ 120 self.our_constraints = set(constraints) 121 self.their_constraints = set() 122 self.repository = repository 123 self.dependency_cache = cache 124 self.prereleases = prereleases 125 self.clear_caches = clear_caches 126 self.allow_unsafe = allow_unsafe 127 self.unsafe_constraints = set() 128 129 @property 130 def constraints(self): 131 return set( 132 self._group_constraints(chain(self.our_constraints, self.their_constraints)) 133 ) 134 135 def resolve_hashes(self, ireqs): 136 """ 137 Finds acceptable hashes for all of the given InstallRequirements. 138 """ 139 log.debug("") 140 log.debug("Generating hashes:") 141 with self.repository.allow_all_wheels(), log.indentation(): 142 return {ireq: self.repository.get_hashes(ireq) for ireq in ireqs} 143 144 def resolve(self, max_rounds=10): 145 """ 146 Finds concrete package versions for all the given InstallRequirements 147 and their recursive dependencies. The end result is a flat list of 148 (name, version) tuples. (Or an editable package.) 149 150 Resolves constraints one round at a time, until they don't change 151 anymore. Protects against infinite loops by breaking out after a max 152 number rounds. 153 """ 154 if self.clear_caches: 155 self.dependency_cache.clear() 156 self.repository.clear_caches() 157 158 # Ignore existing packages 159 # NOTE: str() wrapping necessary for Python 2/3 compat 160 with update_env_context_manager(PIP_EXISTS_ACTION=str("i")): 161 for current_round in count(start=1): # pragma: no branch 162 if current_round > max_rounds: 163 raise RuntimeError( 164 "No stable configuration of concrete packages " 165 "could be found for the given constraints after " 166 "{max_rounds} rounds of resolving.\n" 167 "This is likely a bug.".format(max_rounds=max_rounds) 168 ) 169 170 log.debug("") 171 log.debug(magenta("{:^60}".format("ROUND {}".format(current_round)))) 172 # If a package version (foo==2.0) was built in a previous round, 173 # and in this round a different version of foo needs to be built 174 # (i.e. foo==1.0), the directory will exist already, which will 175 # cause a pip build failure. The trick is to start with a new 176 # build cache dir for every round, so this can never happen. 177 with self.repository.freshen_build_caches(): 178 has_changed, best_matches = self._resolve_one_round() 179 log.debug("-" * 60) 180 log.debug( 181 "Result of round {}: {}".format( 182 current_round, 183 "not stable" if has_changed else "stable, done", 184 ) 185 ) 186 if not has_changed: 187 break 188 189 # Only include hard requirements and not pip constraints 190 results = {req for req in best_matches if not req.constraint} 191 192 # Filter out unsafe requirements. 193 self.unsafe_constraints = set() 194 if not self.allow_unsafe: 195 # reverse_dependencies is used to filter out packages that are only 196 # required by unsafe packages. This logic is incomplete, as it would 197 # fail to filter sub-sub-dependencies of unsafe packages. None of the 198 # UNSAFE_PACKAGES currently have any dependencies at all (which makes 199 # sense for installation tools) so this seems sufficient. 200 reverse_dependencies = self.reverse_dependencies(results) 201 for req in results.copy(): 202 required_by = reverse_dependencies.get(req.name.lower(), []) 203 if req.name in UNSAFE_PACKAGES or ( 204 required_by and all(name in UNSAFE_PACKAGES for name in required_by) 205 ): 206 self.unsafe_constraints.add(req) 207 results.remove(req) 208 209 return results 210 211 def _group_constraints(self, constraints): 212 """ 213 Groups constraints (remember, InstallRequirements!) by their key name, 214 and combining their SpecifierSets into a single InstallRequirement per 215 package. For example, given the following constraints: 216 217 Django<1.9,>=1.4.2 218 django~=1.5 219 Flask~=0.7 220 221 This will be combined into a single entry per package: 222 223 django~=1.5,<1.9,>=1.4.2 224 flask~=0.7 225 226 """ 227 constraints = list(constraints) 228 for ireq in constraints: 229 if ireq.name is None: 230 # get_dependencies has side-effect of assigning name to ireq 231 # (so we can group by the name below). 232 self.repository.get_dependencies(ireq) 233 234 # Sort first by name, i.e. the groupby key. Then within each group, 235 # sort editables first. 236 # This way, we don't bother with combining editables, since the first 237 # ireq will be editable, if one exists. 238 for _, ireqs in groupby( 239 sorted(constraints, key=(lambda x: (key_from_ireq(x), not x.editable))), 240 key=key_from_ireq, 241 ): 242 yield combine_install_requirements(self.repository, ireqs) 243 244 def _resolve_one_round(self): 245 """ 246 Resolves one level of the current constraints, by finding the best 247 match for each package in the repository and adding all requirements 248 for those best package versions. Some of these constraints may be new 249 or updated. 250 251 Returns whether new constraints appeared in this round. If no 252 constraints were added or changed, this indicates a stable 253 configuration. 254 """ 255 # Sort this list for readability of terminal output 256 constraints = sorted(self.constraints, key=key_from_ireq) 257 258 log.debug("Current constraints:") 259 with log.indentation(): 260 for constraint in constraints: 261 log.debug(str(constraint)) 262 263 log.debug("") 264 log.debug("Finding the best candidates:") 265 with log.indentation(): 266 best_matches = {self.get_best_match(ireq) for ireq in constraints} 267 268 # Find the new set of secondary dependencies 269 log.debug("") 270 log.debug("Finding secondary dependencies:") 271 272 their_constraints = [] 273 with log.indentation(): 274 for best_match in best_matches: 275 their_constraints.extend(self._iter_dependencies(best_match)) 276 # Grouping constraints to make clean diff between rounds 277 theirs = set(self._group_constraints(their_constraints)) 278 279 # NOTE: We need to compare RequirementSummary objects, since 280 # InstallRequirement does not define equality 281 diff = {RequirementSummary(t) for t in theirs} - { 282 RequirementSummary(t) for t in self.their_constraints 283 } 284 removed = {RequirementSummary(t) for t in self.their_constraints} - { 285 RequirementSummary(t) for t in theirs 286 } 287 288 has_changed = len(diff) > 0 or len(removed) > 0 289 if has_changed: 290 log.debug("") 291 log.debug("New dependencies found in this round:") 292 with log.indentation(): 293 for new_dependency in sorted(diff, key=key_from_ireq): 294 log.debug("adding {}".format(new_dependency)) 295 log.debug("Removed dependencies in this round:") 296 with log.indentation(): 297 for removed_dependency in sorted(removed, key=key_from_ireq): 298 log.debug("removing {}".format(removed_dependency)) 299 300 # Store the last round's results in the their_constraints 301 self.their_constraints = theirs 302 return has_changed, best_matches 303 304 def get_best_match(self, ireq): 305 """ 306 Returns a (pinned or editable) InstallRequirement, indicating the best 307 match to use for the given InstallRequirement (in the form of an 308 InstallRequirement). 309 310 Example: 311 Given the constraint Flask>=0.10, may return Flask==0.10.1 at 312 a certain moment in time. 313 314 Pinned requirements will always return themselves, i.e. 315 316 Flask==0.10.1 => Flask==0.10.1 317 318 """ 319 if ireq.editable or is_url_requirement(ireq): 320 # NOTE: it's much quicker to immediately return instead of 321 # hitting the index server 322 best_match = ireq 323 elif is_pinned_requirement(ireq): 324 # NOTE: it's much quicker to immediately return instead of 325 # hitting the index server 326 best_match = ireq 327 elif ireq.constraint: 328 # NOTE: This is not a requirement (yet) and does not need 329 # to be resolved 330 best_match = ireq 331 else: 332 best_match = self.repository.find_best_match( 333 ireq, prereleases=self.prereleases 334 ) 335 336 # Format the best match 337 log.debug( 338 "found candidate {} (constraint was {})".format( 339 format_requirement(best_match), format_specifier(ireq) 340 ) 341 ) 342 best_match.comes_from = ireq.comes_from 343 if hasattr(ireq, "_source_ireqs"): 344 best_match._source_ireqs = ireq._source_ireqs 345 return best_match 346 347 def _iter_dependencies(self, ireq): 348 """ 349 Given a pinned, url, or editable InstallRequirement, collects all the 350 secondary dependencies for them, either by looking them up in a local 351 cache, or by reaching out to the repository. 352 353 Editable requirements will never be looked up, as they may have 354 changed at any time. 355 """ 356 # Pip does not resolve dependencies of constraints. We skip handling 357 # constraints here as well to prevent the cache from being polluted. 358 # Constraints that are later determined to be dependencies will be 359 # marked as non-constraints in later rounds by 360 # `combine_install_requirements`, and will be properly resolved. 361 # See https://github.com/pypa/pip/ 362 # blob/6896dfcd831330c13e076a74624d95fa55ff53f4/src/pip/_internal/ 363 # legacy_resolve.py#L325 364 if ireq.constraint: 365 return 366 367 if ireq.editable or is_url_requirement(ireq): 368 for dependency in self.repository.get_dependencies(ireq): 369 yield dependency 370 return 371 elif not is_pinned_requirement(ireq): 372 raise TypeError( 373 "Expected pinned or editable requirement, got {}".format(ireq) 374 ) 375 376 # Now, either get the dependencies from the dependency cache (for 377 # speed), or reach out to the external repository to 378 # download and inspect the package version and get dependencies 379 # from there 380 if ireq not in self.dependency_cache: 381 log.debug( 382 "{} not in cache, need to check index".format(format_requirement(ireq)), 383 fg="yellow", 384 ) 385 dependencies = self.repository.get_dependencies(ireq) 386 self.dependency_cache[ireq] = sorted(str(ireq.req) for ireq in dependencies) 387 388 # Example: ['Werkzeug>=0.9', 'Jinja2>=2.4'] 389 dependency_strings = self.dependency_cache[ireq] 390 log.debug( 391 "{:25} requires {}".format( 392 format_requirement(ireq), 393 ", ".join(sorted(dependency_strings, key=lambda s: s.lower())) or "-", 394 ) 395 ) 396 for dependency_string in dependency_strings: 397 yield install_req_from_line( 398 dependency_string, constraint=ireq.constraint, comes_from=ireq 399 ) 400 401 def reverse_dependencies(self, ireqs): 402 non_editable = [ 403 ireq for ireq in ireqs if not (ireq.editable or is_url_requirement(ireq)) 404 ] 405 return self.dependency_cache.reverse_dependencies(non_editable) 406