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