1"""Dependency Resolution 2 3The dependency resolution in pip is performed as follows: 4 5for top-level requirements: 6 a. only one spec allowed per project, regardless of conflicts or not. 7 otherwise a "double requirement" exception is raised 8 b. they override sub-dependency requirements. 9for sub-dependencies 10 a. "first found, wins" (where the order is breadth first) 11""" 12 13# The following comment should be removed at some point in the future. 14# mypy: strict-optional=False 15# mypy: disallow-untyped-defs=False 16 17import logging 18import sys 19from collections import defaultdict 20from itertools import chain 21 22from pip._vendor.packaging import specifiers 23 24from pip._internal.exceptions import ( 25 BestVersionAlreadyInstalled, 26 DistributionNotFound, 27 HashError, 28 HashErrors, 29 UnsupportedPythonVersion, 30) 31from pip._internal.req.req_install import check_invalid_constraint_type 32from pip._internal.req.req_set import RequirementSet 33from pip._internal.resolution.base import BaseResolver 34from pip._internal.utils.compatibility_tags import get_supported 35from pip._internal.utils.logging import indent_log 36from pip._internal.utils.misc import dist_in_usersite, normalize_version_info 37from pip._internal.utils.packaging import ( 38 check_requires_python, 39 get_requires_python, 40) 41from pip._internal.utils.typing import MYPY_CHECK_RUNNING 42 43if MYPY_CHECK_RUNNING: 44 from typing import DefaultDict, List, Optional, Set, Tuple 45 from pip._vendor import pkg_resources 46 47 from pip._internal.cache import WheelCache 48 from pip._internal.distributions import AbstractDistribution 49 from pip._internal.index.package_finder import PackageFinder 50 from pip._internal.models.link import Link 51 from pip._internal.operations.prepare import RequirementPreparer 52 from pip._internal.req.req_install import InstallRequirement 53 from pip._internal.resolution.base import InstallRequirementProvider 54 55 DiscoveredDependencies = DefaultDict[str, List[InstallRequirement]] 56 57logger = logging.getLogger(__name__) 58 59 60def _check_dist_requires_python( 61 dist, # type: pkg_resources.Distribution 62 version_info, # type: Tuple[int, int, int] 63 ignore_requires_python=False, # type: bool 64): 65 # type: (...) -> None 66 """ 67 Check whether the given Python version is compatible with a distribution's 68 "Requires-Python" value. 69 70 :param version_info: A 3-tuple of ints representing the Python 71 major-minor-micro version to check. 72 :param ignore_requires_python: Whether to ignore the "Requires-Python" 73 value if the given Python version isn't compatible. 74 75 :raises UnsupportedPythonVersion: When the given Python version isn't 76 compatible. 77 """ 78 requires_python = get_requires_python(dist) 79 try: 80 is_compatible = check_requires_python( 81 requires_python, version_info=version_info, 82 ) 83 except specifiers.InvalidSpecifier as exc: 84 logger.warning( 85 "Package %r has an invalid Requires-Python: %s", 86 dist.project_name, exc, 87 ) 88 return 89 90 if is_compatible: 91 return 92 93 version = '.'.join(map(str, version_info)) 94 if ignore_requires_python: 95 logger.debug( 96 'Ignoring failed Requires-Python check for package %r: ' 97 '%s not in %r', 98 dist.project_name, version, requires_python, 99 ) 100 return 101 102 raise UnsupportedPythonVersion( 103 'Package {!r} requires a different Python: {} not in {!r}'.format( 104 dist.project_name, version, requires_python, 105 )) 106 107 108class Resolver(BaseResolver): 109 """Resolves which packages need to be installed/uninstalled to perform \ 110 the requested operation without breaking the requirements of any package. 111 """ 112 113 _allowed_strategies = {"eager", "only-if-needed", "to-satisfy-only"} 114 115 def __init__( 116 self, 117 preparer, # type: RequirementPreparer 118 finder, # type: PackageFinder 119 wheel_cache, # type: Optional[WheelCache] 120 make_install_req, # type: InstallRequirementProvider 121 use_user_site, # type: bool 122 ignore_dependencies, # type: bool 123 ignore_installed, # type: bool 124 ignore_requires_python, # type: bool 125 force_reinstall, # type: bool 126 upgrade_strategy, # type: str 127 py_version_info=None, # type: Optional[Tuple[int, ...]] 128 ): 129 # type: (...) -> None 130 super(Resolver, self).__init__() 131 assert upgrade_strategy in self._allowed_strategies 132 133 if py_version_info is None: 134 py_version_info = sys.version_info[:3] 135 else: 136 py_version_info = normalize_version_info(py_version_info) 137 138 self._py_version_info = py_version_info 139 140 self.preparer = preparer 141 self.finder = finder 142 self.wheel_cache = wheel_cache 143 144 self.upgrade_strategy = upgrade_strategy 145 self.force_reinstall = force_reinstall 146 self.ignore_dependencies = ignore_dependencies 147 self.ignore_installed = ignore_installed 148 self.ignore_requires_python = ignore_requires_python 149 self.use_user_site = use_user_site 150 self._make_install_req = make_install_req 151 152 self._discovered_dependencies = \ 153 defaultdict(list) # type: DiscoveredDependencies 154 155 def resolve(self, root_reqs, check_supported_wheels): 156 # type: (List[InstallRequirement], bool) -> RequirementSet 157 """Resolve what operations need to be done 158 159 As a side-effect of this method, the packages (and their dependencies) 160 are downloaded, unpacked and prepared for installation. This 161 preparation is done by ``pip.operations.prepare``. 162 163 Once PyPI has static dependency metadata available, it would be 164 possible to move the preparation to become a step separated from 165 dependency resolution. 166 """ 167 requirement_set = RequirementSet( 168 check_supported_wheels=check_supported_wheels 169 ) 170 for req in root_reqs: 171 if req.constraint: 172 check_invalid_constraint_type(req) 173 requirement_set.add_requirement(req) 174 175 # Actually prepare the files, and collect any exceptions. Most hash 176 # exceptions cannot be checked ahead of time, because 177 # _populate_link() needs to be called before we can make decisions 178 # based on link type. 179 discovered_reqs = [] # type: List[InstallRequirement] 180 hash_errors = HashErrors() 181 for req in chain(requirement_set.all_requirements, discovered_reqs): 182 try: 183 discovered_reqs.extend(self._resolve_one(requirement_set, req)) 184 except HashError as exc: 185 exc.req = req 186 hash_errors.append(exc) 187 188 if hash_errors: 189 raise hash_errors 190 191 return requirement_set 192 193 def _is_upgrade_allowed(self, req): 194 # type: (InstallRequirement) -> bool 195 if self.upgrade_strategy == "to-satisfy-only": 196 return False 197 elif self.upgrade_strategy == "eager": 198 return True 199 else: 200 assert self.upgrade_strategy == "only-if-needed" 201 return req.user_supplied or req.constraint 202 203 def _set_req_to_reinstall(self, req): 204 # type: (InstallRequirement) -> None 205 """ 206 Set a requirement to be installed. 207 """ 208 # Don't uninstall the conflict if doing a user install and the 209 # conflict is not a user install. 210 if not self.use_user_site or dist_in_usersite(req.satisfied_by): 211 req.should_reinstall = True 212 req.satisfied_by = None 213 214 def _check_skip_installed(self, req_to_install): 215 # type: (InstallRequirement) -> Optional[str] 216 """Check if req_to_install should be skipped. 217 218 This will check if the req is installed, and whether we should upgrade 219 or reinstall it, taking into account all the relevant user options. 220 221 After calling this req_to_install will only have satisfied_by set to 222 None if the req_to_install is to be upgraded/reinstalled etc. Any 223 other value will be a dist recording the current thing installed that 224 satisfies the requirement. 225 226 Note that for vcs urls and the like we can't assess skipping in this 227 routine - we simply identify that we need to pull the thing down, 228 then later on it is pulled down and introspected to assess upgrade/ 229 reinstalls etc. 230 231 :return: A text reason for why it was skipped, or None. 232 """ 233 if self.ignore_installed: 234 return None 235 236 req_to_install.check_if_exists(self.use_user_site) 237 if not req_to_install.satisfied_by: 238 return None 239 240 if self.force_reinstall: 241 self._set_req_to_reinstall(req_to_install) 242 return None 243 244 if not self._is_upgrade_allowed(req_to_install): 245 if self.upgrade_strategy == "only-if-needed": 246 return 'already satisfied, skipping upgrade' 247 return 'already satisfied' 248 249 # Check for the possibility of an upgrade. For link-based 250 # requirements we have to pull the tree down and inspect to assess 251 # the version #, so it's handled way down. 252 if not req_to_install.link: 253 try: 254 self.finder.find_requirement(req_to_install, upgrade=True) 255 except BestVersionAlreadyInstalled: 256 # Then the best version is installed. 257 return 'already up-to-date' 258 except DistributionNotFound: 259 # No distribution found, so we squash the error. It will 260 # be raised later when we re-try later to do the install. 261 # Why don't we just raise here? 262 pass 263 264 self._set_req_to_reinstall(req_to_install) 265 return None 266 267 def _find_requirement_link(self, req): 268 # type: (InstallRequirement) -> Optional[Link] 269 upgrade = self._is_upgrade_allowed(req) 270 best_candidate = self.finder.find_requirement(req, upgrade) 271 if not best_candidate: 272 return None 273 274 # Log a warning per PEP 592 if necessary before returning. 275 link = best_candidate.link 276 if link.is_yanked: 277 reason = link.yanked_reason or '<none given>' 278 msg = ( 279 # Mark this as a unicode string to prevent 280 # "UnicodeEncodeError: 'ascii' codec can't encode character" 281 # in Python 2 when the reason contains non-ascii characters. 282 u'The candidate selected for download or install is a ' 283 'yanked version: {candidate}\n' 284 'Reason for being yanked: {reason}' 285 ).format(candidate=best_candidate, reason=reason) 286 logger.warning(msg) 287 288 return link 289 290 def _populate_link(self, req): 291 # type: (InstallRequirement) -> None 292 """Ensure that if a link can be found for this, that it is found. 293 294 Note that req.link may still be None - if the requirement is already 295 installed and not needed to be upgraded based on the return value of 296 _is_upgrade_allowed(). 297 298 If preparer.require_hashes is True, don't use the wheel cache, because 299 cached wheels, always built locally, have different hashes than the 300 files downloaded from the index server and thus throw false hash 301 mismatches. Furthermore, cached wheels at present have undeterministic 302 contents due to file modification times. 303 """ 304 if req.link is None: 305 req.link = self._find_requirement_link(req) 306 307 if self.wheel_cache is None or self.preparer.require_hashes: 308 return 309 cache_entry = self.wheel_cache.get_cache_entry( 310 link=req.link, 311 package_name=req.name, 312 supported_tags=get_supported(), 313 ) 314 if cache_entry is not None: 315 logger.debug('Using cached wheel link: %s', cache_entry.link) 316 if req.link is req.original_link and cache_entry.persistent: 317 req.original_link_is_in_wheel_cache = True 318 req.link = cache_entry.link 319 320 def _get_abstract_dist_for(self, req): 321 # type: (InstallRequirement) -> AbstractDistribution 322 """Takes a InstallRequirement and returns a single AbstractDist \ 323 representing a prepared variant of the same. 324 """ 325 if req.editable: 326 return self.preparer.prepare_editable_requirement(req) 327 328 # satisfied_by is only evaluated by calling _check_skip_installed, 329 # so it must be None here. 330 assert req.satisfied_by is None 331 skip_reason = self._check_skip_installed(req) 332 333 if req.satisfied_by: 334 return self.preparer.prepare_installed_requirement( 335 req, skip_reason 336 ) 337 338 # We eagerly populate the link, since that's our "legacy" behavior. 339 self._populate_link(req) 340 abstract_dist = self.preparer.prepare_linked_requirement(req) 341 342 # NOTE 343 # The following portion is for determining if a certain package is 344 # going to be re-installed/upgraded or not and reporting to the user. 345 # This should probably get cleaned up in a future refactor. 346 347 # req.req is only avail after unpack for URL 348 # pkgs repeat check_if_exists to uninstall-on-upgrade 349 # (#14) 350 if not self.ignore_installed: 351 req.check_if_exists(self.use_user_site) 352 353 if req.satisfied_by: 354 should_modify = ( 355 self.upgrade_strategy != "to-satisfy-only" or 356 self.force_reinstall or 357 self.ignore_installed or 358 req.link.scheme == 'file' 359 ) 360 if should_modify: 361 self._set_req_to_reinstall(req) 362 else: 363 logger.info( 364 'Requirement already satisfied (use --upgrade to upgrade):' 365 ' %s', req, 366 ) 367 368 return abstract_dist 369 370 def _resolve_one( 371 self, 372 requirement_set, # type: RequirementSet 373 req_to_install, # type: InstallRequirement 374 ): 375 # type: (...) -> List[InstallRequirement] 376 """Prepare a single requirements file. 377 378 :return: A list of additional InstallRequirements to also install. 379 """ 380 # Tell user what we are doing for this requirement: 381 # obtain (editable), skipping, processing (local url), collecting 382 # (remote url or package name) 383 if req_to_install.constraint or req_to_install.prepared: 384 return [] 385 386 req_to_install.prepared = True 387 388 abstract_dist = self._get_abstract_dist_for(req_to_install) 389 390 # Parse and return dependencies 391 dist = abstract_dist.get_pkg_resources_distribution() 392 # This will raise UnsupportedPythonVersion if the given Python 393 # version isn't compatible with the distribution's Requires-Python. 394 _check_dist_requires_python( 395 dist, version_info=self._py_version_info, 396 ignore_requires_python=self.ignore_requires_python, 397 ) 398 399 more_reqs = [] # type: List[InstallRequirement] 400 401 def add_req(subreq, extras_requested): 402 sub_install_req = self._make_install_req( 403 str(subreq), 404 req_to_install, 405 ) 406 parent_req_name = req_to_install.name 407 to_scan_again, add_to_parent = requirement_set.add_requirement( 408 sub_install_req, 409 parent_req_name=parent_req_name, 410 extras_requested=extras_requested, 411 ) 412 if parent_req_name and add_to_parent: 413 self._discovered_dependencies[parent_req_name].append( 414 add_to_parent 415 ) 416 more_reqs.extend(to_scan_again) 417 418 with indent_log(): 419 # We add req_to_install before its dependencies, so that we 420 # can refer to it when adding dependencies. 421 if not requirement_set.has_requirement(req_to_install.name): 422 # 'unnamed' requirements will get added here 423 # 'unnamed' requirements can only come from being directly 424 # provided by the user. 425 assert req_to_install.user_supplied 426 requirement_set.add_requirement( 427 req_to_install, parent_req_name=None, 428 ) 429 430 if not self.ignore_dependencies: 431 if req_to_install.extras: 432 logger.debug( 433 "Installing extra requirements: %r", 434 ','.join(req_to_install.extras), 435 ) 436 missing_requested = sorted( 437 set(req_to_install.extras) - set(dist.extras) 438 ) 439 for missing in missing_requested: 440 logger.warning( 441 "%s does not provide the extra '%s'", 442 dist, missing 443 ) 444 445 available_requested = sorted( 446 set(dist.extras) & set(req_to_install.extras) 447 ) 448 for subreq in dist.requires(available_requested): 449 add_req(subreq, extras_requested=available_requested) 450 451 if not req_to_install.editable and not req_to_install.satisfied_by: 452 # XXX: --no-install leads this to report 'Successfully 453 # downloaded' for only non-editable reqs, even though we took 454 # action on them. 455 req_to_install.successfully_downloaded = True 456 457 return more_reqs 458 459 def get_installation_order(self, req_set): 460 # type: (RequirementSet) -> List[InstallRequirement] 461 """Create the installation order. 462 463 The installation order is topological - requirements are installed 464 before the requiring thing. We break cycles at an arbitrary point, 465 and make no other guarantees. 466 """ 467 # The current implementation, which we may change at any point 468 # installs the user specified things in the order given, except when 469 # dependencies must come earlier to achieve topological order. 470 order = [] 471 ordered_reqs = set() # type: Set[InstallRequirement] 472 473 def schedule(req): 474 if req.satisfied_by or req in ordered_reqs: 475 return 476 if req.constraint: 477 return 478 ordered_reqs.add(req) 479 for dep in self._discovered_dependencies[req.name]: 480 schedule(dep) 481 order.append(req) 482 483 for install_req in req_set.requirements.values(): 484 schedule(install_req) 485 return order 486