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