resolver.py 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305
  1. import functools
  2. import logging
  3. import os
  4. from typing import TYPE_CHECKING, Dict, List, Optional, Set, Tuple, cast
  5. from pip._vendor.packaging.utils import canonicalize_name
  6. from pip._vendor.packaging.version import parse as parse_version
  7. from pip._vendor.resolvelib import BaseReporter, ResolutionImpossible
  8. from pip._vendor.resolvelib import Resolver as RLResolver
  9. from pip._vendor.resolvelib.structs import DirectedGraph
  10. from pip._internal.cache import WheelCache
  11. from pip._internal.exceptions import InstallationError
  12. from pip._internal.index.package_finder import PackageFinder
  13. from pip._internal.operations.prepare import RequirementPreparer
  14. from pip._internal.req.req_install import (
  15. InstallRequirement,
  16. check_invalid_constraint_type,
  17. )
  18. from pip._internal.req.req_set import RequirementSet
  19. from pip._internal.resolution.base import BaseResolver, InstallRequirementProvider
  20. from pip._internal.resolution.resolvelib.provider import PipProvider
  21. from pip._internal.resolution.resolvelib.reporter import (
  22. PipDebuggingReporter,
  23. PipReporter,
  24. )
  25. from pip._internal.utils.deprecation import deprecated
  26. from pip._internal.utils.filetypes import is_archive_file
  27. from pip._internal.utils.misc import dist_is_editable
  28. from .base import Candidate, Constraint, Requirement
  29. from .factory import Factory
  30. if TYPE_CHECKING:
  31. from pip._vendor.resolvelib.resolvers import Result as RLResult
  32. Result = RLResult[Requirement, Candidate, str]
  33. logger = logging.getLogger(__name__)
  34. class Resolver(BaseResolver):
  35. _allowed_strategies = {"eager", "only-if-needed", "to-satisfy-only"}
  36. def __init__(
  37. self,
  38. preparer, # type: RequirementPreparer
  39. finder, # type: PackageFinder
  40. wheel_cache, # type: Optional[WheelCache]
  41. make_install_req, # type: InstallRequirementProvider
  42. use_user_site, # type: bool
  43. ignore_dependencies, # type: bool
  44. ignore_installed, # type: bool
  45. ignore_requires_python, # type: bool
  46. force_reinstall, # type: bool
  47. upgrade_strategy, # type: str
  48. py_version_info=None, # type: Optional[Tuple[int, ...]]
  49. ):
  50. super().__init__()
  51. assert upgrade_strategy in self._allowed_strategies
  52. self.factory = Factory(
  53. finder=finder,
  54. preparer=preparer,
  55. make_install_req=make_install_req,
  56. wheel_cache=wheel_cache,
  57. use_user_site=use_user_site,
  58. force_reinstall=force_reinstall,
  59. ignore_installed=ignore_installed,
  60. ignore_requires_python=ignore_requires_python,
  61. py_version_info=py_version_info,
  62. )
  63. self.ignore_dependencies = ignore_dependencies
  64. self.upgrade_strategy = upgrade_strategy
  65. self._result = None # type: Optional[Result]
  66. def resolve(self, root_reqs, check_supported_wheels):
  67. # type: (List[InstallRequirement], bool) -> RequirementSet
  68. constraints = {} # type: Dict[str, Constraint]
  69. user_requested = {} # type: Dict[str, int]
  70. requirements = []
  71. for i, req in enumerate(root_reqs):
  72. if req.constraint:
  73. # Ensure we only accept valid constraints
  74. problem = check_invalid_constraint_type(req)
  75. if problem:
  76. raise InstallationError(problem)
  77. if not req.match_markers():
  78. continue
  79. assert req.name, "Constraint must be named"
  80. name = canonicalize_name(req.name)
  81. if name in constraints:
  82. constraints[name] &= req
  83. else:
  84. constraints[name] = Constraint.from_ireq(req)
  85. else:
  86. if req.user_supplied and req.name:
  87. canonical_name = canonicalize_name(req.name)
  88. if canonical_name not in user_requested:
  89. user_requested[canonical_name] = i
  90. r = self.factory.make_requirement_from_install_req(
  91. req, requested_extras=()
  92. )
  93. if r is not None:
  94. requirements.append(r)
  95. provider = PipProvider(
  96. factory=self.factory,
  97. constraints=constraints,
  98. ignore_dependencies=self.ignore_dependencies,
  99. upgrade_strategy=self.upgrade_strategy,
  100. user_requested=user_requested,
  101. )
  102. if "PIP_RESOLVER_DEBUG" in os.environ:
  103. reporter = PipDebuggingReporter() # type: BaseReporter
  104. else:
  105. reporter = PipReporter()
  106. resolver = RLResolver(
  107. provider,
  108. reporter,
  109. ) # type: RLResolver[Requirement, Candidate, str]
  110. try:
  111. try_to_avoid_resolution_too_deep = 2000000
  112. result = self._result = resolver.resolve(
  113. requirements, max_rounds=try_to_avoid_resolution_too_deep
  114. )
  115. except ResolutionImpossible as e:
  116. error = self.factory.get_installation_error(
  117. cast("ResolutionImpossible[Requirement, Candidate]", e),
  118. constraints,
  119. )
  120. raise error from e
  121. req_set = RequirementSet(check_supported_wheels=check_supported_wheels)
  122. for candidate in result.mapping.values():
  123. ireq = candidate.get_install_requirement()
  124. if ireq is None:
  125. continue
  126. # Check if there is already an installation under the same name,
  127. # and set a flag for later stages to uninstall it, if needed.
  128. installed_dist = self.factory.get_dist_to_uninstall(candidate)
  129. if installed_dist is None:
  130. # There is no existing installation -- nothing to uninstall.
  131. ireq.should_reinstall = False
  132. elif self.factory.force_reinstall:
  133. # The --force-reinstall flag is set -- reinstall.
  134. ireq.should_reinstall = True
  135. elif parse_version(installed_dist.version) != candidate.version:
  136. # The installation is different in version -- reinstall.
  137. ireq.should_reinstall = True
  138. elif candidate.is_editable or dist_is_editable(installed_dist):
  139. # The incoming distribution is editable, or different in
  140. # editable-ness to installation -- reinstall.
  141. ireq.should_reinstall = True
  142. elif candidate.source_link and candidate.source_link.is_file:
  143. # The incoming distribution is under file://
  144. if candidate.source_link.is_wheel:
  145. # is a local wheel -- do nothing.
  146. logger.info(
  147. "%s is already installed with the same version as the "
  148. "provided wheel. Use --force-reinstall to force an "
  149. "installation of the wheel.",
  150. ireq.name,
  151. )
  152. continue
  153. looks_like_sdist = (
  154. is_archive_file(candidate.source_link.file_path)
  155. and candidate.source_link.ext != ".zip"
  156. )
  157. if looks_like_sdist:
  158. # is a local sdist -- show a deprecation warning!
  159. reason = (
  160. "Source distribution is being reinstalled despite an "
  161. "installed package having the same name and version as "
  162. "the installed package."
  163. )
  164. replacement = "use --force-reinstall"
  165. deprecated(
  166. reason=reason,
  167. replacement=replacement,
  168. gone_in="21.2",
  169. issue=8711,
  170. )
  171. # is a local sdist or path -- reinstall
  172. ireq.should_reinstall = True
  173. else:
  174. continue
  175. link = candidate.source_link
  176. if link and link.is_yanked:
  177. # The reason can contain non-ASCII characters, Unicode
  178. # is required for Python 2.
  179. msg = (
  180. "The candidate selected for download or install is a "
  181. "yanked version: {name!r} candidate (version {version} "
  182. "at {link})\nReason for being yanked: {reason}"
  183. ).format(
  184. name=candidate.name,
  185. version=candidate.version,
  186. link=link,
  187. reason=link.yanked_reason or "<none given>",
  188. )
  189. logger.warning(msg)
  190. req_set.add_named_requirement(ireq)
  191. reqs = req_set.all_requirements
  192. self.factory.preparer.prepare_linked_requirements_more(reqs)
  193. return req_set
  194. def get_installation_order(self, req_set):
  195. # type: (RequirementSet) -> List[InstallRequirement]
  196. """Get order for installation of requirements in RequirementSet.
  197. The returned list contains a requirement before another that depends on
  198. it. This helps ensure that the environment is kept consistent as they
  199. get installed one-by-one.
  200. The current implementation creates a topological ordering of the
  201. dependency graph, while breaking any cycles in the graph at arbitrary
  202. points. We make no guarantees about where the cycle would be broken,
  203. other than they would be broken.
  204. """
  205. assert self._result is not None, "must call resolve() first"
  206. graph = self._result.graph
  207. weights = get_topological_weights(
  208. graph,
  209. expected_node_count=len(self._result.mapping) + 1,
  210. )
  211. sorted_items = sorted(
  212. req_set.requirements.items(),
  213. key=functools.partial(_req_set_item_sorter, weights=weights),
  214. reverse=True,
  215. )
  216. return [ireq for _, ireq in sorted_items]
  217. def get_topological_weights(graph, expected_node_count):
  218. # type: (DirectedGraph[Optional[str]], int) -> Dict[Optional[str], int]
  219. """Assign weights to each node based on how "deep" they are.
  220. This implementation may change at any point in the future without prior
  221. notice.
  222. We take the length for the longest path to any node from root, ignoring any
  223. paths that contain a single node twice (i.e. cycles). This is done through
  224. a depth-first search through the graph, while keeping track of the path to
  225. the node.
  226. Cycles in the graph result would result in node being revisited while also
  227. being it's own path. In this case, take no action. This helps ensure we
  228. don't get stuck in a cycle.
  229. When assigning weight, the longer path (i.e. larger length) is preferred.
  230. """
  231. path = set() # type: Set[Optional[str]]
  232. weights = {} # type: Dict[Optional[str], int]
  233. def visit(node):
  234. # type: (Optional[str]) -> None
  235. if node in path:
  236. # We hit a cycle, so we'll break it here.
  237. return
  238. # Time to visit the children!
  239. path.add(node)
  240. for child in graph.iter_children(node):
  241. visit(child)
  242. path.remove(node)
  243. last_known_parent_count = weights.get(node, 0)
  244. weights[node] = max(last_known_parent_count, len(path))
  245. # `None` is guaranteed to be the root node by resolvelib.
  246. visit(None)
  247. # Sanity checks
  248. assert weights[None] == 0
  249. assert len(weights) == expected_node_count
  250. return weights
  251. def _req_set_item_sorter(
  252. item, # type: Tuple[str, InstallRequirement]
  253. weights, # type: Dict[Optional[str], int]
  254. ):
  255. # type: (...) -> Tuple[int, str]
  256. """Key function used to sort install requirements for installation.
  257. Based on the "weight" mapping calculated in ``get_installation_order()``.
  258. The canonical package name is returned as the second member as a tie-
  259. breaker to ensure the result is predictable, which is useful in tests.
  260. """
  261. name = canonicalize_name(item[0])
  262. return weights[name], name