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