resolvers.py 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474
  1. import collections
  2. import operator
  3. from .providers import AbstractResolver
  4. from .structs import DirectedGraph, IteratorMapping, build_iter_view
  5. RequirementInformation = collections.namedtuple(
  6. "RequirementInformation", ["requirement", "parent"]
  7. )
  8. class ResolverException(Exception):
  9. """A base class for all exceptions raised by this module.
  10. Exceptions derived by this class should all be handled in this module. Any
  11. bubbling pass the resolver should be treated as a bug.
  12. """
  13. class RequirementsConflicted(ResolverException):
  14. def __init__(self, criterion):
  15. super(RequirementsConflicted, self).__init__(criterion)
  16. self.criterion = criterion
  17. def __str__(self):
  18. return "Requirements conflict: {}".format(
  19. ", ".join(repr(r) for r in self.criterion.iter_requirement()),
  20. )
  21. class InconsistentCandidate(ResolverException):
  22. def __init__(self, candidate, criterion):
  23. super(InconsistentCandidate, self).__init__(candidate, criterion)
  24. self.candidate = candidate
  25. self.criterion = criterion
  26. def __str__(self):
  27. return "Provided candidate {!r} does not satisfy {}".format(
  28. self.candidate,
  29. ", ".join(repr(r) for r in self.criterion.iter_requirement()),
  30. )
  31. class Criterion(object):
  32. """Representation of possible resolution results of a package.
  33. This holds three attributes:
  34. * `information` is a collection of `RequirementInformation` pairs.
  35. Each pair is a requirement contributing to this criterion, and the
  36. candidate that provides the requirement.
  37. * `incompatibilities` is a collection of all known not-to-work candidates
  38. to exclude from consideration.
  39. * `candidates` is a collection containing all possible candidates deducted
  40. from the union of contributing requirements and known incompatibilities.
  41. It should never be empty, except when the criterion is an attribute of a
  42. raised `RequirementsConflicted` (in which case it is always empty).
  43. .. note::
  44. This class is intended to be externally immutable. **Do not** mutate
  45. any of its attribute containers.
  46. """
  47. def __init__(self, candidates, information, incompatibilities):
  48. self.candidates = candidates
  49. self.information = information
  50. self.incompatibilities = incompatibilities
  51. def __repr__(self):
  52. requirements = ", ".join(
  53. "({!r}, via={!r})".format(req, parent)
  54. for req, parent in self.information
  55. )
  56. return "Criterion({})".format(requirements)
  57. def iter_requirement(self):
  58. return (i.requirement for i in self.information)
  59. def iter_parent(self):
  60. return (i.parent for i in self.information)
  61. class ResolutionError(ResolverException):
  62. pass
  63. class ResolutionImpossible(ResolutionError):
  64. def __init__(self, causes):
  65. super(ResolutionImpossible, self).__init__(causes)
  66. # causes is a list of RequirementInformation objects
  67. self.causes = causes
  68. class ResolutionTooDeep(ResolutionError):
  69. def __init__(self, round_count):
  70. super(ResolutionTooDeep, self).__init__(round_count)
  71. self.round_count = round_count
  72. # Resolution state in a round.
  73. State = collections.namedtuple("State", "mapping criteria")
  74. class Resolution(object):
  75. """Stateful resolution object.
  76. This is designed as a one-off object that holds information to kick start
  77. the resolution process, and holds the results afterwards.
  78. """
  79. def __init__(self, provider, reporter):
  80. self._p = provider
  81. self._r = reporter
  82. self._states = []
  83. @property
  84. def state(self):
  85. try:
  86. return self._states[-1]
  87. except IndexError:
  88. raise AttributeError("state")
  89. def _push_new_state(self):
  90. """Push a new state into history.
  91. This new state will be used to hold resolution results of the next
  92. coming round.
  93. """
  94. base = self._states[-1]
  95. state = State(
  96. mapping=base.mapping.copy(),
  97. criteria=base.criteria.copy(),
  98. )
  99. self._states.append(state)
  100. def _merge_into_criterion(self, requirement, parent):
  101. self._r.adding_requirement(requirement=requirement, parent=parent)
  102. identifier = self._p.identify(requirement_or_candidate=requirement)
  103. criterion = self.state.criteria.get(identifier)
  104. if criterion:
  105. incompatibilities = list(criterion.incompatibilities)
  106. else:
  107. incompatibilities = []
  108. matches = self._p.find_matches(
  109. identifier=identifier,
  110. requirements=IteratorMapping(
  111. self.state.criteria,
  112. operator.methodcaller("iter_requirement"),
  113. {identifier: [requirement]},
  114. ),
  115. incompatibilities=IteratorMapping(
  116. self.state.criteria,
  117. operator.attrgetter("incompatibilities"),
  118. {identifier: incompatibilities},
  119. ),
  120. )
  121. if criterion:
  122. information = list(criterion.information)
  123. information.append(RequirementInformation(requirement, parent))
  124. else:
  125. information = [RequirementInformation(requirement, parent)]
  126. criterion = Criterion(
  127. candidates=build_iter_view(matches),
  128. information=information,
  129. incompatibilities=incompatibilities,
  130. )
  131. if not criterion.candidates:
  132. raise RequirementsConflicted(criterion)
  133. return identifier, criterion
  134. def _get_preference(self, name):
  135. return self._p.get_preference(
  136. identifier=name,
  137. resolutions=self.state.mapping,
  138. candidates=IteratorMapping(
  139. self.state.criteria,
  140. operator.attrgetter("candidates"),
  141. ),
  142. information=IteratorMapping(
  143. self.state.criteria,
  144. operator.attrgetter("information"),
  145. ),
  146. )
  147. def _is_current_pin_satisfying(self, name, criterion):
  148. try:
  149. current_pin = self.state.mapping[name]
  150. except KeyError:
  151. return False
  152. return all(
  153. self._p.is_satisfied_by(requirement=r, candidate=current_pin)
  154. for r in criterion.iter_requirement()
  155. )
  156. def _get_criteria_to_update(self, candidate):
  157. criteria = {}
  158. for r in self._p.get_dependencies(candidate=candidate):
  159. name, crit = self._merge_into_criterion(r, parent=candidate)
  160. criteria[name] = crit
  161. return criteria
  162. def _attempt_to_pin_criterion(self, name):
  163. criterion = self.state.criteria[name]
  164. causes = []
  165. for candidate in criterion.candidates:
  166. try:
  167. criteria = self._get_criteria_to_update(candidate)
  168. except RequirementsConflicted as e:
  169. causes.append(e.criterion)
  170. continue
  171. # Check the newly-pinned candidate actually works. This should
  172. # always pass under normal circumstances, but in the case of a
  173. # faulty provider, we will raise an error to notify the implementer
  174. # to fix find_matches() and/or is_satisfied_by().
  175. satisfied = all(
  176. self._p.is_satisfied_by(requirement=r, candidate=candidate)
  177. for r in criterion.iter_requirement()
  178. )
  179. if not satisfied:
  180. raise InconsistentCandidate(candidate, criterion)
  181. # Put newly-pinned candidate at the end. This is essential because
  182. # backtracking looks at this mapping to get the last pin.
  183. self._r.pinning(candidate=candidate)
  184. self.state.mapping.pop(name, None)
  185. self.state.mapping[name] = candidate
  186. self.state.criteria.update(criteria)
  187. return []
  188. # All candidates tried, nothing works. This criterion is a dead
  189. # end, signal for backtracking.
  190. return causes
  191. def _backtrack(self):
  192. """Perform backtracking.
  193. When we enter here, the stack is like this::
  194. [ state Z ]
  195. [ state Y ]
  196. [ state X ]
  197. .... earlier states are irrelevant.
  198. 1. No pins worked for Z, so it does not have a pin.
  199. 2. We want to reset state Y to unpinned, and pin another candidate.
  200. 3. State X holds what state Y was before the pin, but does not
  201. have the incompatibility information gathered in state Y.
  202. Each iteration of the loop will:
  203. 1. Discard Z.
  204. 2. Discard Y but remember its incompatibility information gathered
  205. previously, and the failure we're dealing with right now.
  206. 3. Push a new state Y' based on X, and apply the incompatibility
  207. information from Y to Y'.
  208. 4a. If this causes Y' to conflict, we need to backtrack again. Make Y'
  209. the new Z and go back to step 2.
  210. 4b. If the incompatibilities apply cleanly, end backtracking.
  211. """
  212. while len(self._states) >= 3:
  213. # Remove the state that triggered backtracking.
  214. del self._states[-1]
  215. # Retrieve the last candidate pin and known incompatibilities.
  216. broken_state = self._states.pop()
  217. name, candidate = broken_state.mapping.popitem()
  218. incompatibilities_from_broken = [
  219. (k, list(v.incompatibilities))
  220. for k, v in broken_state.criteria.items()
  221. ]
  222. # Also mark the newly known incompatibility.
  223. incompatibilities_from_broken.append((name, [candidate]))
  224. self._r.backtracking(candidate=candidate)
  225. # Create a new state from the last known-to-work one, and apply
  226. # the previously gathered incompatibility information.
  227. def _patch_criteria():
  228. for k, incompatibilities in incompatibilities_from_broken:
  229. if not incompatibilities:
  230. continue
  231. try:
  232. criterion = self.state.criteria[k]
  233. except KeyError:
  234. continue
  235. matches = self._p.find_matches(
  236. identifier=k,
  237. requirements=IteratorMapping(
  238. self.state.criteria,
  239. operator.methodcaller("iter_requirement"),
  240. ),
  241. incompatibilities=IteratorMapping(
  242. self.state.criteria,
  243. operator.attrgetter("incompatibilities"),
  244. {k: incompatibilities},
  245. ),
  246. )
  247. candidates = build_iter_view(matches)
  248. if not candidates:
  249. return False
  250. incompatibilities.extend(criterion.incompatibilities)
  251. self.state.criteria[k] = Criterion(
  252. candidates=candidates,
  253. information=list(criterion.information),
  254. incompatibilities=incompatibilities,
  255. )
  256. return True
  257. self._push_new_state()
  258. success = _patch_criteria()
  259. # It works! Let's work on this new state.
  260. if success:
  261. return True
  262. # State does not work after applying known incompatibilities.
  263. # Try the still previous state.
  264. # No way to backtrack anymore.
  265. return False
  266. def resolve(self, requirements, max_rounds):
  267. if self._states:
  268. raise RuntimeError("already resolved")
  269. self._r.starting()
  270. # Initialize the root state.
  271. self._states = [State(mapping=collections.OrderedDict(), criteria={})]
  272. for r in requirements:
  273. try:
  274. name, crit = self._merge_into_criterion(r, parent=None)
  275. except RequirementsConflicted as e:
  276. raise ResolutionImpossible(e.criterion.information)
  277. self.state.criteria[name] = crit
  278. # The root state is saved as a sentinel so the first ever pin can have
  279. # something to backtrack to if it fails. The root state is basically
  280. # pinning the virtual "root" package in the graph.
  281. self._push_new_state()
  282. for round_index in range(max_rounds):
  283. self._r.starting_round(index=round_index)
  284. unsatisfied_names = [
  285. key
  286. for key, criterion in self.state.criteria.items()
  287. if not self._is_current_pin_satisfying(key, criterion)
  288. ]
  289. # All criteria are accounted for. Nothing more to pin, we are done!
  290. if not unsatisfied_names:
  291. self._r.ending(state=self.state)
  292. return self.state
  293. # Choose the most preferred unpinned criterion to try.
  294. name = min(unsatisfied_names, key=self._get_preference)
  295. failure_causes = self._attempt_to_pin_criterion(name)
  296. if failure_causes:
  297. # Backtrack if pinning fails. The backtrack process puts us in
  298. # an unpinned state, so we can work on it in the next round.
  299. success = self._backtrack()
  300. # Dead ends everywhere. Give up.
  301. if not success:
  302. causes = [i for c in failure_causes for i in c.information]
  303. raise ResolutionImpossible(causes)
  304. else:
  305. # Pinning was successful. Push a new state to do another pin.
  306. self._push_new_state()
  307. self._r.ending_round(index=round_index, state=self.state)
  308. raise ResolutionTooDeep(max_rounds)
  309. def _has_route_to_root(criteria, key, all_keys, connected):
  310. if key in connected:
  311. return True
  312. if key not in criteria:
  313. return False
  314. for p in criteria[key].iter_parent():
  315. try:
  316. pkey = all_keys[id(p)]
  317. except KeyError:
  318. continue
  319. if pkey in connected:
  320. connected.add(key)
  321. return True
  322. if _has_route_to_root(criteria, pkey, all_keys, connected):
  323. connected.add(key)
  324. return True
  325. return False
  326. Result = collections.namedtuple("Result", "mapping graph criteria")
  327. def _build_result(state):
  328. mapping = state.mapping
  329. all_keys = {id(v): k for k, v in mapping.items()}
  330. all_keys[id(None)] = None
  331. graph = DirectedGraph()
  332. graph.add(None) # Sentinel as root dependencies' parent.
  333. connected = {None}
  334. for key, criterion in state.criteria.items():
  335. if not _has_route_to_root(state.criteria, key, all_keys, connected):
  336. continue
  337. if key not in graph:
  338. graph.add(key)
  339. for p in criterion.iter_parent():
  340. try:
  341. pkey = all_keys[id(p)]
  342. except KeyError:
  343. continue
  344. if pkey not in graph:
  345. graph.add(pkey)
  346. graph.connect(pkey, key)
  347. return Result(
  348. mapping={k: v for k, v in mapping.items() if k in connected},
  349. graph=graph,
  350. criteria=state.criteria,
  351. )
  352. class Resolver(AbstractResolver):
  353. """The thing that performs the actual resolution work."""
  354. base_exception = ResolverException
  355. def resolve(self, requirements, max_rounds=100):
  356. """Take a collection of constraints, spit out the resolution result.
  357. The return value is a representation to the final resolution result. It
  358. is a tuple subclass with three public members:
  359. * `mapping`: A dict of resolved candidates. Each key is an identifier
  360. of a requirement (as returned by the provider's `identify` method),
  361. and the value is the resolved candidate.
  362. * `graph`: A `DirectedGraph` instance representing the dependency tree.
  363. The vertices are keys of `mapping`, and each edge represents *why*
  364. a particular package is included. A special vertex `None` is
  365. included to represent parents of user-supplied requirements.
  366. * `criteria`: A dict of "criteria" that hold detailed information on
  367. how edges in the graph are derived. Each key is an identifier of a
  368. requirement, and the value is a `Criterion` instance.
  369. The following exceptions may be raised if a resolution cannot be found:
  370. * `ResolutionImpossible`: A resolution cannot be found for the given
  371. combination of requirements. The `causes` attribute of the
  372. exception is a list of (requirement, parent), giving the
  373. requirements that could not be satisfied.
  374. * `ResolutionTooDeep`: The dependency tree is too deeply nested and
  375. the resolver gave up. This is usually caused by a circular
  376. dependency, but you can try to resolve this by increasing the
  377. `max_rounds` argument.
  378. """
  379. resolution = Resolution(self.provider, self.reporter)
  380. state = resolution.resolve(requirements, max_rounds=max_rounds)
  381. return _build_result(state)