Repository: pypa/pip
File: src/pip/_internal/resolution/resolvelib/found_candidates.py (Python)

Code before:
    This iterator is used when the resolver prefers to upgrade an
    already-installed package. Candidates from index are returned in their
    normal ordering, except replaced when the version is already installed.

    The implementation iterates through and yields other candidates, inserting
    the installed candidate exactly once before we start yielding older or
    equivalent candidates, or after all other candidates if they are all newer.
    """
    installed_yielded = False
    for candidate in others:
        # If the installed candidate is better, yield it first.
        if not installed_yielded and installed.version >= candidate.version:
            yield installed
            installed_yielded = True
        yield candidate

    # If the installed candidate is older than all other candidates.
    if not installed_yielded:
        yield installed


class FoundCandidates(collections_abc.Sequence):
    """A lazy sequence to provide candidates to the resolver.

    The intended usage is to return this from `find_matches()` so the resolver
    can iterate through the sequence multiple times, but only access the index
    page when remote packages are actually needed. This improve performances
    when suitable candidates are already installed on disk.
    """
    def __init__(
        self,
        get_others,  # type: Callable[[], Iterator[Candidate]]
        installed,  # type: Optional[Candidate]
        prefers_installed,  # type: bool
    ):
        self._get_others = get_others
        self._installed = installed
        self._prefers_installed = prefers_installed

    def __getitem__(self, index):
        # type: (int) -> Candidate
        # Implemented to satisfy the ABC check. This is not needed by the
        # resolver, and should not be used by the provider either (for
        # performance reasons).
        raise NotImplementedError("don't do this")

    def __iter__(self):
        # type: () -> Iterator[Candidate]
        if not self._installed:
            candidates = self._get_others()
        elif self._prefers_installed:

Review comment (bug):
So the key problem with #9264 was that the `sorted(...)` approach didn't work, correct? I assume that was because the assumption "candidates from index are already sorted by reverse version order" was somehow incorrect - is that right?

The logic here seems fine, but so does the original logic - so I'm a bit reluctant to approve without understanding how this fixes the problem that caused #9264 to be reverted. Can you explain a bit more? I assume it was the "upgrading pip goes into an infinite loop" thing, but I don't see how this change improves that situation.

Sorry if I'm being dense here...

Code after:
        if candidate.version in returned:
            continue
        returned.add(candidate.version)
        yield candidate


def _insert_installed(installed, others):
    # type: (Candidate, Iterator[Candidate]) -> Iterator[Candidate]
    """Iterator for ``FoundCandidates``.

    This iterator is used when the resolver prefers to upgrade an
    already-installed package. Candidates from index are returned in their
    normal ordering, except replaced when the version is already installed.

    The implementation iterates through and yields other candidates, inserting
    the installed candidate exactly once before we start yielding older or
    equivalent candidates, or after all other candidates if they are all newer.
    """
    installed_yielded = False
    for candidate in others:
        # If the installed candidate is better, yield it first.
        if not installed_yielded and installed.version >= candidate.version:
            yield installed
            installed_yielded = True
        yield candidate

    # If the installed candidate is older than all other candidates.
    if not installed_yielded:
        yield installed


class FoundCandidates(collections_abc.Sequence):
    """A lazy sequence to provide candidates to the resolver.

    The intended usage is to return this from `find_matches()` so the resolver
    can iterate through the sequence multiple times, but only access the index
    page when remote packages are actually needed. This improve performances
    when suitable candidates are already installed on disk.
    """
    def __init__(
        self,
        get_others,  # type: Callable[[], Iterator[Candidate]]
        installed,  # type: Optional[Candidate]
        prefers_installed,  # type: bool
    ):
        self._get_others = get_others
        self._installed = installed
        self._prefers_installed = prefers_installed

    def __getitem__(self, index):
        # type: (int) -> Candidate