Merge pull request #9771 from uranusjr/resolvelib-060

12 files changed, 193 insertions, 97 deletions

diff --git a/news/resolvelib.vendor.rst b/news/resolvelib.vendor.rst
index 4f102fc0d..ebad91f25 100644
--- a/news/resolvelib.vendor.rst
+++ b/news/resolvelib.vendor.rst
@@ -1 +1 @@
-Upgrade vendored resolvelib to 0.5.5.
+Upgrade vendored resolvelib to 0.6.0.
diff --git a/src/pip/_internal/resolution/resolvelib/factory.py b/src/pip/_internal/resolution/resolvelib/factory.py
index dd747198f..6cada5be0 100644
--- a/src/pip/_internal/resolution/resolvelib/factory.py
+++ b/src/pip/_internal/resolution/resolvelib/factory.py
@@ -7,6 +7,7 @@ from typing import (
     Iterable,
     Iterator,
     List,
+    Mapping,
     Optional,
     Sequence,
     Set,
@@ -104,6 +105,9 @@ class Factory:
         self._installed_candidate_cache = (
             {}
         )  # type: Dict[str, AlreadyInstalledCandidate]
+        self._extras_candidate_cache = (
+            {}
+        )  # type: Dict[Tuple[int, FrozenSet[str]], ExtrasCandidate]
 
         if not ignore_installed:
             self._installed_dists = {
@@ -118,6 +122,16 @@ class Factory:
         # type: () -> bool
         return self._force_reinstall
 
+    def _make_extras_candidate(self, base, extras):
+        # type: (BaseCandidate, FrozenSet[str]) -> ExtrasCandidate
+        cache_key = (id(base), extras)
+        try:
+            candidate = self._extras_candidate_cache[cache_key]
+        except KeyError:
+            candidate = ExtrasCandidate(base, extras)
+            self._extras_candidate_cache[cache_key] = candidate
+        return candidate
+
     def _make_candidate_from_dist(
         self,
         dist,  # type: Distribution
@@ -130,9 +144,9 @@ class Factory:
         except KeyError:
             base = AlreadyInstalledCandidate(dist, template, factory=self)
             self._installed_candidate_cache[dist.key] = base
-        if extras:
-            return ExtrasCandidate(base, extras)
-        return base
+        if not extras:
+            return base
+        return self._make_extras_candidate(base, extras)
 
     def _make_candidate_from_link(
         self,
@@ -182,18 +196,18 @@ class Factory:
                     return None
             base = self._link_candidate_cache[link]
 
-        if extras:
-            return ExtrasCandidate(base, extras)
-        return base
+        if not extras:
+            return base
+        return self._make_extras_candidate(base, extras)
 
     def _iter_found_candidates(
         self,
-        ireqs,  # type: Sequence[InstallRequirement]
-        specifier,  # type: SpecifierSet
-        hashes,  # type: Hashes
-        prefers_installed,  # type: bool
-    ):
-        # type: (...) -> Iterable[Candidate]
+        ireqs: Sequence[InstallRequirement],
+        specifier: SpecifierSet,
+        hashes: Hashes,
+        prefers_installed: bool,
+        incompatible_ids: Set[int],
+    ) -> Iterable[Candidate]:
         if not ireqs:
             return ()
 
@@ -257,20 +271,27 @@ class Factory:
             iter_index_candidate_infos,
             installed_candidate,
             prefers_installed,
+            incompatible_ids,
         )
 
     def find_candidates(
         self,
-        requirements,  # type: Sequence[Requirement]
-        constraint,  # type: Constraint
-        prefers_installed,  # type: bool
-    ):
-        # type: (...) -> Iterable[Candidate]
+        identifier: str,
+        requirements: Mapping[str, Iterator[Requirement]],
+        incompatibilities: Mapping[str, Iterator[Candidate]],
+        constraint: Constraint,
+        prefers_installed: bool,
+    ) -> Iterable[Candidate]:
+
+        # Since we cache all the candidates, incompatibility identification
+        # can be made quicker by comparing only the id() values.
+        incompat_ids = {id(c) for c in incompatibilities.get(identifier, ())}
+
         explicit_candidates = set()  # type: Set[Candidate]
         ireqs = []  # type: List[InstallRequirement]
-        for req in requirements:
+        for req in requirements[identifier]:
             cand, ireq = req.get_candidate_lookup()
-            if cand is not None:
+            if cand is not None and id(cand) not in incompat_ids:
                 explicit_candidates.add(cand)
             if ireq is not None:
                 ireqs.append(ireq)
@@ -283,13 +304,14 @@ class Factory:
                 constraint.specifier,
                 constraint.hashes,
                 prefers_installed,
+                incompat_ids,
             )
 
         return (
             c
             for c in explicit_candidates
             if constraint.is_satisfied_by(c)
-            and all(req.is_satisfied_by(c) for req in requirements)
+            and all(req.is_satisfied_by(c) for req in requirements[identifier])
         )
 
     def make_requirement_from_install_req(self, ireq, requested_extras):
diff --git a/src/pip/_internal/resolution/resolvelib/found_candidates.py b/src/pip/_internal/resolution/resolvelib/found_candidates.py
index e8b72e660..21fa08ec9 100644
--- a/src/pip/_internal/resolution/resolvelib/found_candidates.py
+++ b/src/pip/_internal/resolution/resolvelib/found_candidates.py
@@ -100,13 +100,15 @@ class FoundCandidates(collections_abc.Sequence):
 
     def __init__(
         self,
-        get_infos,  # type: Callable[[], Iterator[IndexCandidateInfo]]
-        installed,  # type: Optional[Candidate]
-        prefers_installed,  # type: bool
+        get_infos: Callable[[], Iterator[IndexCandidateInfo]],
+        installed: Optional[Candidate],
+        prefers_installed: bool,
+        incompatible_ids: Set[int],
     ):
         self._get_infos = get_infos
         self._installed = installed
         self._prefers_installed = prefers_installed
+        self._incompatible_ids = incompatible_ids
 
     def __getitem__(self, index):
         # type: (int) -> Candidate
@@ -119,10 +121,12 @@ class FoundCandidates(collections_abc.Sequence):
         # type: () -> Iterator[Candidate]
         infos = self._get_infos()
         if not self._installed:
-            return _iter_built(infos)
-        if self._prefers_installed:
-            return _iter_built_with_prepended(self._installed, infos)
-        return _iter_built_with_inserted(self._installed, infos)
+            iterator = _iter_built(infos)
+        elif self._prefers_installed:
+            iterator = _iter_built_with_prepended(self._installed, infos)
+        else:
+            iterator = _iter_built_with_inserted(self._installed, infos)
+        return (c for c in iterator if id(c) not in self._incompatible_ids)
 
     def __len__(self):
         # type: () -> int
diff --git a/src/pip/_internal/resolution/resolvelib/provider.py b/src/pip/_internal/resolution/resolvelib/provider.py
index cd2ccfa60..32597f7e0 100644
--- a/src/pip/_internal/resolution/resolvelib/provider.py
+++ b/src/pip/_internal/resolution/resolvelib/provider.py
@@ -1,4 +1,13 @@
-from typing import TYPE_CHECKING, Dict, Iterable, Optional, Sequence, Union
+from typing import (
+    TYPE_CHECKING,
+    Dict,
+    Iterable,
+    Iterator,
+    Mapping,
+    Optional,
+    Sequence,
+    Union,
+)
 
 from pip._vendor.resolvelib.providers import AbstractProvider
 
@@ -134,12 +143,12 @@ class PipProvider(_ProviderBase):
 
         return (delay_this, restrictive, order, key)
 
-    def find_matches(self, requirements):
-        # type: (Sequence[Requirement]) -> Iterable[Candidate]
-        if not requirements:
-            return []
-        name = requirements[0].project_name
-
+    def find_matches(
+        self,
+        identifier: str,
+        requirements: Mapping[str, Iterator[Requirement]],
+        incompatibilities: Mapping[str, Iterator[Candidate]],
+    ) -> Iterable[Candidate]:
         def _eligible_for_upgrade(name):
             # type: (str) -> bool
             """Are upgrades allowed for this project?
@@ -159,9 +168,11 @@ class PipProvider(_ProviderBase):
             return False
 
         return self._factory.find_candidates(
-            requirements,
-            constraint=self._constraints.get(name, Constraint.empty()),
-            prefers_installed=(not _eligible_for_upgrade(name)),
+            identifier=identifier,
+            requirements=requirements,
+            constraint=self._constraints.get(identifier, Constraint.empty()),
+            prefers_installed=(not _eligible_for_upgrade(identifier)),
+            incompatibilities=incompatibilities,
         )
 
     def is_satisfied_by(self, requirement, candidate):
diff --git a/src/pip/_vendor/resolvelib/__init__.py b/src/pip/_vendor/resolvelib/__init__.py
index 63ee53446..34be7ee0f 100644
--- a/src/pip/_vendor/resolvelib/__init__.py
+++ b/src/pip/_vendor/resolvelib/__init__.py
@@ -11,7 +11,7 @@ __all__ = [
     "ResolutionTooDeep",
 ]
 
-__version__ = "0.5.5"
+__version__ = "0.6.0"
 
 
 from .providers import AbstractProvider, AbstractResolver
diff --git a/src/pip/_vendor/resolvelib/compat/collections_abc.py b/src/pip/_vendor/resolvelib/compat/collections_abc.py
index 366cc5e2e..1becc5093 100644
--- a/src/pip/_vendor/resolvelib/compat/collections_abc.py
+++ b/src/pip/_vendor/resolvelib/compat/collections_abc.py
@@ -1,6 +1,6 @@
-__all__ = ["Sequence"]
+__all__ = ["Mapping", "Sequence"]
 
 try:
-    from collections.abc import Sequence
+    from collections.abc import Mapping, Sequence
 except ImportError:
-    from collections import Sequence
+    from collections import Mapping, Sequence
diff --git a/src/pip/_vendor/resolvelib/providers.py b/src/pip/_vendor/resolvelib/providers.py
index 8ef700cc0..852ee8f48 100644
--- a/src/pip/_vendor/resolvelib/providers.py
+++ b/src/pip/_vendor/resolvelib/providers.py
@@ -50,8 +50,18 @@ class AbstractProvider(object):
         """
         raise NotImplementedError
 
-    def find_matches(self, requirements):
-        """Find all possible candidates that satisfy the given requirements.
+    def find_matches(self, identifier, requirements, incompatibilities):
+        """Find all possible candidates that satisfy given constraints.
+
+        :param identifier: An identifier as returned by ``identify()``. This
+            identifies the dependency matches of which should be returned.
+        :param requirements: A mapping of requirements that all returned
+            candidates must satisfy. Each key is an identifier, and the value
+            an iterator of requirements for that dependency.
+        :param incompatibilities: A mapping of known incompatibilities of
+            each dependency. Each key is an identifier, and the value an
+            iterator of incompatibilities known to the resolver. All
+            incompatibilities *must* be excluded from the return value.
 
         This should try to get candidates based on the requirements' types.
         For VCS, local, and archive requirements, the one-and-only match is
@@ -66,10 +76,6 @@ class AbstractProvider(object):
         * An collection of candidates.
         * An iterable of candidates. This will be consumed immediately into a
           list of candidates.
-
-        :param requirements: A collection of requirements which all of the
-            returned candidates must match. All requirements are guaranteed to
-            have the same identifier. The collection is never empty.
         """
         raise NotImplementedError
 
diff --git a/src/pip/_vendor/resolvelib/providers.pyi b/src/pip/_vendor/resolvelib/providers.pyi
index 3c8ff24d4..42c19c95f 100644
--- a/src/pip/_vendor/resolvelib/providers.pyi
+++ b/src/pip/_vendor/resolvelib/providers.pyi
@@ -3,10 +3,10 @@ from typing import (
     Collection,
     Generic,
     Iterable,
+    Iterator,
     Mapping,
     Optional,
     Protocol,
-    Sequence,
     Union,
 )
 
@@ -31,7 +31,12 @@ class AbstractProvider(Generic[RT, CT, KT]):
         candidates: IterableView[CT],
         information: Collection[RequirementInformation[RT, CT]],
     ) -> Preference: ...
-    def find_matches(self, requirements: Sequence[RT]) -> Matches: ...
+    def find_matches(
+        self,
+        identifier: KT,
+        requirements: Mapping[KT, Iterator[RT]],
+        incompatibilities: Mapping[KT, Iterator[CT]],
+    ) -> Matches: ...
     def is_satisfied_by(self, requirement: RT, candidate: CT) -> bool: ...
     def get_dependencies(self, candidate: CT) -> Iterable[RT]: ...
 
diff --git a/src/pip/_vendor/resolvelib/resolvers.py b/src/pip/_vendor/resolvelib/resolvers.py
index 60a30ee4f..c79ccc451 100644
--- a/src/pip/_vendor/resolvelib/resolvers.py
+++ b/src/pip/_vendor/resolvelib/resolvers.py
@@ -1,7 +1,8 @@
 import collections
+import operator
 
 from .providers import AbstractResolver
-from .structs import DirectedGraph, build_iter_view
+from .structs import DirectedGraph, IteratorMapping, build_iter_view
 
 
 RequirementInformation = collections.namedtuple(
@@ -73,45 +74,12 @@ class Criterion(object):
         )
         return "Criterion({})".format(requirements)
 
-    @classmethod
-    def from_requirement(cls, provider, requirement, parent):
-        """Build an instance from a requirement."""
-        matches = provider.find_matches(requirements=[requirement])
-        cands = build_iter_view(matches)
-        infos = [RequirementInformation(requirement, parent)]
-        criterion = cls(cands, infos, incompatibilities=[])
-        if not cands:
-            raise RequirementsConflicted(criterion)
-        return criterion
-
     def iter_requirement(self):
         return (i.requirement for i in self.information)
 
     def iter_parent(self):
         return (i.parent for i in self.information)
 
-    def merged_with(self, provider, requirement, parent):
-        """Build a new instance from this and a new requirement."""
-        infos = list(self.information)
-        infos.append(RequirementInformation(requirement, parent))
-        matches = provider.find_matches([r for r, _ in infos])
-        cands = build_iter_view(matches)
-        criterion = type(self)(cands, infos, list(self.incompatibilities))
-        if not cands:
-            raise RequirementsConflicted(criterion)
-        return criterion
-
-    def excluded_of(self, candidates):
-        """Build a new instance from this, but excluding specified candidates.
-
-        Returns the new instance, or None if we still have no valid candidates.
-        """
-        cands = self.candidates.excluding(candidates)
-        if not cands:
-            return None
-        incompats = self.incompatibilities + candidates
-        return type(self)(cands, list(self.information), incompats)
-
 
 class ResolutionError(ResolverException):
     pass
@@ -168,13 +136,42 @@ class Resolution(object):
 
     def _merge_into_criterion(self, requirement, parent):
         self._r.adding_requirement(requirement=requirement, parent=parent)
-        name = self._p.identify(requirement_or_candidate=requirement)
-        if name in self.state.criteria:
-            crit = self.state.criteria[name]
-            crit = crit.merged_with(self._p, requirement, parent)
+
+        identifier = self._p.identify(requirement_or_candidate=requirement)
+        criterion = self.state.criteria.get(identifier)
+        if criterion:
+            incompatibilities = list(criterion.incompatibilities)
+        else:
+            incompatibilities = []
+
+        matches = self._p.find_matches(
+            identifier=identifier,
+            requirements=IteratorMapping(
+                self.state.criteria,
+                operator.methodcaller("iter_requirement"),
+                {identifier: [requirement]},
+            ),
+            incompatibilities=IteratorMapping(
+                self.state.criteria,
+                operator.attrgetter("incompatibilities"),
+                {identifier: incompatibilities},
+            ),
+        )
+
+        if criterion:
+            information = list(criterion.information)
+            information.append(RequirementInformation(requirement, parent))
         else:
-            crit = Criterion.from_requirement(self._p, requirement, parent)
-        return name, crit
+            information = [RequirementInformation(requirement, parent)]
+
+        criterion = Criterion(
+            candidates=build_iter_view(matches),
+            information=information,
+            incompatibilities=incompatibilities,
+        )
+        if not criterion.candidates:
+            raise RequirementsConflicted(criterion)
+        return identifier, criterion
 
     def _get_criterion_item_preference(self, item):
         name, criterion = item
@@ -268,7 +265,7 @@ class Resolution(object):
             broken_state = self._states.pop()
             name, candidate = broken_state.mapping.popitem()
             incompatibilities_from_broken = [
-                (k, v.incompatibilities)
+                (k, list(v.incompatibilities))
                 for k, v in broken_state.criteria.items()
             ]
 
@@ -287,10 +284,27 @@ class Resolution(object):
                         criterion = self.state.criteria[k]
                     except KeyError:
                         continue
-                    criterion = criterion.excluded_of(incompatibilities)
-                    if criterion is None:
+                    matches = self._p.find_matches(
+                        identifier=k,
+                        requirements=IteratorMapping(
+                            self.state.criteria,
+                            operator.methodcaller("iter_requirement"),
+                        ),
+                        incompatibilities=IteratorMapping(
+                            self.state.criteria,
+                            operator.attrgetter("incompatibilities"),
+                            {k: incompatibilities},
+                        ),
+                    )
+                    candidates = build_iter_view(matches)
+                    if not candidates:
                         return False
-                    self.state.criteria[k] = criterion
+                    incompatibilities.extend(criterion.incompatibilities)
+                    self.state.criteria[k] = Criterion(
+                        candidates=candidates,
+                        information=list(criterion.information),
+                        incompatibilities=incompatibilities,
+                    )
                 return True
 
             self._push_new_state()
diff --git a/src/pip/_vendor/resolvelib/structs.py b/src/pip/_vendor/resolvelib/structs.py
index c4542f08a..72f2e6042 100644
--- a/src/pip/_vendor/resolvelib/structs.py
+++ b/src/pip/_vendor/resolvelib/structs.py
@@ -1,3 +1,4 @@
+import itertools
 from .compat import collections_abc
 
 
@@ -67,6 +68,31 @@ class DirectedGraph(object):
         return iter(self._backwards[key])
 
 
+class IteratorMapping(collections_abc.Mapping):
+    def __init__(self, mapping, accessor, appends=None):
+        self._mapping = mapping
+        self._accessor = accessor
+        self._appends = appends or {}
+
+    def __contains__(self, key):
+        return key in self._mapping or key in self._appends
+
+    def __getitem__(self, k):
+        try:
+            v = self._mapping[k]
+        except KeyError:
+            return iter(self._appends[k])
+        return itertools.chain(self._accessor(v), self._appends.get(k, ()))
+
+    def __iter__(self):
+        more = (k for k in self._appends if k not in self._mapping)
+        return itertools.chain(self._mapping, more)
+
+    def __len__(self):
+        more = len(k for k in self._appends if k not in self._mapping)
+        return len(self._mapping) + more
+
+
 class _FactoryIterableView(object):
     """Wrap an iterator factory returned by `find_matches()`.
 
diff --git a/src/pip/_vendor/vendor.txt b/src/pip/_vendor/vendor.txt
index c5d1b643e..59d41e50f 100644
--- a/src/pip/_vendor/vendor.txt
+++ b/src/pip/_vendor/vendor.txt
@@ -14,7 +14,7 @@ requests==2.25.1
     chardet==4.0.0
     idna==2.10
     urllib3==1.26.4
-resolvelib==0.5.5
+resolvelib==0.6.0
 setuptools==44.0.0
 six==1.15.0
 tenacity==6.3.1
diff --git a/tests/unit/resolution_resolvelib/test_requirement.py b/tests/unit/resolution_resolvelib/test_requirement.py
index 6149fd1ae..1f7b0c53d 100644
--- a/tests/unit/resolution_resolvelib/test_requirement.py
+++ b/tests/unit/resolution_resolvelib/test_requirement.py
@@ -59,7 +59,11 @@ def test_new_resolver_correct_number_of_matches(test_cases, factory):
     for spec, _, match_count in test_cases:
         req = factory.make_requirement_from_spec(spec, comes_from=None)
         matches = factory.find_candidates(
-            [req], Constraint.empty(), prefers_installed=False,
+            req.name,
+            {req.name: [req]},
+            {},
+            Constraint.empty(),
+            prefers_installed=False,
         )
         assert sum(1 for _ in matches) == match_count
 
@@ -70,7 +74,11 @@ def test_new_resolver_candidates_match_requirement(test_cases, factory):
     for spec, _, _ in test_cases:
         req = factory.make_requirement_from_spec(spec, comes_from=None)
         candidates = factory.find_candidates(
-            [req], Constraint.empty(), prefers_installed=False,
+            req.name,
+            {req.name: [req]},
+            {},
+            Constraint.empty(),
+            prefers_installed=False,
         )
         for c in candidates:
             assert isinstance(c, Candidate)