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