resolver.py 24 KB

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