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