criteria compatibility check while backtracking includes dependencies for version we're backtracking on

[sanderr]

Context

While using pip, which makes use of this library, I noticed that pip install flake8 flake8-isort resulted in backtracking over all flake8's versions, not finding a suitable candidate, followed by backtracking over flake8-isort's versions until a suitable (but very old) candidate was found there. When I looked at these projects I didn't see any reason why none of the flake8 versions would be compatible with the latest flake8-isort. Indeed, reversing the order (pip install flake8-isort) installs the latest flake8-isort and a compatible flake8 as expected, only having to backtrack once on flake8. When I noticed this seemingly inconsistent behavior I added some breakpoints to this library's code and tried to get a grasp of what was going on. I should note as a disclaimer that I haven't worked with this code before, so I might just be missing something.

Concrete

Here's a timeline of what I believe happens for pip install flake8 flake8-isort:

1. The latest flake8 (4.0.1 at the time of writing) gets selected.
2. The latest flake8-isort gets selected
3. The flake8-isort candidate requires flake8<4, which isn't compatible with the flake8 candidate, so we backtrack on flake8.
4. For each flake8 version, we check if its dependencies are compatible with the current criteria: https://github.com/sarugaku/resolvelib/blob/62c56b587c69a42c8f006e032bbf17a63df54d45/src/resolvelib/resolvers.py#L203-L204
5. This fails with

   > /home/sander/.virtualenvs/temp/lib/python3.9/site-packages/pip/_vendor/resolvelib/resolvers.py(218)_attempt_to_pin_criterion()
   -> continue
   (Pdb) l
   213                 try:
   214                     criteria = self._get_updated_criteria(candidate)
   215                 except RequirementsConflicted as e:
   216                     causes.append(e.criterion)
   217                     breakpoint()
   218  ->                 continue
   219     
   220                 # Check the newly-pinned candidate actually works. This should
   221                 # always pass under normal circumstances, but in the case of a
   222                 # faulty provider, we will raise an error to notify the implementer
   223                 # to fix find_matches() and/or is_satisfied_by().
   (Pdb) e.criterion
   Criterion((SpecifierRequirement('pyflakes<2.5.0,>=2.4.0'), via=LinkCandidate('https://files.pythonhosted.org/packages/34/39/cde2c8a227abb4f9ce62fe55586b920f438f1d2903a1a22514d0b982c333/flake8-4.0.1-py2.py3-none-any.whl#sha256=479b1304f72536a55948cb40a32dce8bb0ffe3501e26eaf292c7e60eb5e0428d (from https://pypi.org/simple/flake8/) (requires-python:>=3.6)')), (SpecifierRequirement('pyflakes<2.4.0,>=2.3.0'), via=LinkCandidate('https://files.pythonhosted.org/packages/fc/80/35a0716e5d5101e643404dabd20f07f5528a21f3ef4032d31a49c913237b/flake8-3.9.2-py2.py3-none-any.whl#sha256=bf8fd333346d844f616e8d47905ef3a3384edae6b4e9beb0c5101e25e3110907 (from https://pypi.org/simple/flake8/) (requires-python:!=3.0.*,!=3.1.*,!=3.2.*,!=3.3.*,!=3.4.*,>=2.7)')))

This seems to indicate that the dependency compatibility check includes the dependencies of the version we're backtracking on. Since the currently selected flake8 has a dependency constraint which is incompatible with the constraints for all older versions, backtracking fails. In practice, the latest flake8<4 is compatible with the rest of the current criteria.

[pradyunsg]

This came up first in https://github.com/pypa/pip/issues/10568, which OP seems to have not found prior to opening this issue.

Closing as per https://github.com/pypa/pip/issues/10568#issuecomment-940422100, since there isn't much more that pip / resolvelib can do here; not unless someone comes up with a breakthrough idea that the folks who've worked on this problem for over 5 years combined haven't come up with yet.

[sanderr]

I see this is indeed a duplicate, my apologies, I hadn't though to search for flake8, as I considered it specific to my example, not the actual issue.

[sanderr]

However, the discussion on that ticket or the comment you linked however don't go into why it rejects flake8-3.9.2 in the first place. I fully agree that there are multiple solutions to the dependency resolution problem, and that the one found by pip/resolvelib is a valid one. The concern I'm raising here is that it considers another valid option which it then rejects as being invalid. Doesn't that, combined with the criterion in the exception I posted above, indicate that there is indeed a bug? I believe this hypothesis gets strengthened by the fact that pip install "flake8<4" flake8-isort does find flake8-3.9.2 a valid candidate. It seems to indicate to me that the only reason it doesn't without the constraint is that it takes flake8-4.0.1's constraints on its dependencies into account. If you disagree, would you mind elaborating on that?

[wouterdb]

@pradyunsg I think the suggested solution of removing the item being back-tracked-on from the set of criteria may indeed be 'the breakthrough solution`, if the analysis of the situation is correct.

It would seem to me that the very essence of backtracking is to replace the item being back-tracked on by an alternative, not merely adding an alternative while maintaining the original?

[jaap3]

I'm also very interested in this, and was about to comment on my original report of this issue when I saw this.

PIP is downloading 24 versions of flake8 and then discarding them all because of "reasons". It seems worthwhile to figure out what those reasons are, because it seems wasteful and the resulting conflict resolution is far from ideal.

I don't dispute that the dependency resolving is technically valid. It's just that pip seems to skip a much easier/quicker/better solution in favor of a much more convoluted/worse one.

[uranusjr]

One thing I think we potentially can do is to add a final phase after everything is picked up to try to "maximise" the chosen version of each package, by going back to those candidates previously marked as incompatible and try if they can actually be individually upgraded without affecting any other packages. This should probably not be done by default (for the vast majority of cases it is just wasting time), but the user can opt into it if they are fine with that additional overhead.

This also ties back to the conversation where I proposed we might want to add some "resolution strategy" flags to pip so people can tweak the behaviour for specific situations, e.g. choosing minimum version instead of maximum.

[sanderr]

@uranusjr while I see how your suggestion could be useful, I'm not sure it applies to the issue I'm trying to highlight. As far as I'm concerned, this issue is not about optimizing the chosen state among all candidates. It is about correctness when determining whether a certain candidate version is compatible with the current criteria. The examples along with the exception snippet I provided very much seem to indicate that the current implementation rejects some valid states. As my original post states, the exception that gets raised contains the following:

(Pdb) e.criterion
Criterion((SpecifierRequirement('pyflakes<2.5.0,>=2.4.0'), via=LinkCandidate('https://files.pythonhosted.org/packages/34/39/cde2c8a227abb4f9ce62fe55586b920f438f1d2903a1a22514d0b982c333/flake8-4.0.1-py2.py3-none-any.whl#sha256=479b1304f72536a55948cb40a32dce8bb0ffe3501e26eaf292c7e60eb5e0428d (from https://pypi.org/simple/flake8/) (requires-python:>=3.6)')), (SpecifierRequirement('pyflakes<2.4.0,>=2.3.0'), via=LinkCandidate('https://files.pythonhosted.org/packages/fc/80/35a0716e5d5101e643404dabd20f07f5528a21f3ef4032d31a49c913237b/flake8-3.9.2-py2.py3-none-any.whl#sha256=bf8fd333346d844f616e8d47905ef3a3384edae6b4e9beb0c5101e25e3110907 (from https://pypi.org/simple/flake8/) (requires-python:!=3.0.*,!=3.1.*,!=3.2.*,!=3.3.*,!=3.4.*,>=2.7)')))

If I interpret this correctly this means that the flake8-3.9.2 candidate gets rejected because it isn't compatible with the current criteria, namely the dependencies of flake8-4.0.1. I'm arguing that this check is not relevant and may easily leads to false negatives on the compatibility check. When checking if flake8-3.9.2 is compatible with the current criteria, this criteria should not include any of flake-4.0.1's dependencies, yet it does.

I am definitely willing to accept that I'm missing something, I'm not as familiar with this logic or this code base as you are after all. But up till now I get the impression I'm just not getting my point across. For me this is not about optimization, it is about correctness, and to me the current compatibility check seems to be incorrect in cases where the older versions' dependency constraints do not overlap with the version being backtracked on. The flake8, flake8-isort issue is just what brought this to light. As you've previously stated, the chosen set is a vaild one and does not present an issue on itself (though improvements might be possible, but that's beside the point here). The path to get to that chosen set however passes through a couple of rejections of other states that are perfectly valid as well, and this is a consequence of what I believe to be this bug in the compatibility check.

Does the above help in clarifying what exactly I mean and in differentiating between the optimization problem and the correctness of validating a given candidate given the current criteria?

[pfmoore]

@sanderr Personally, I get what you're saying, but I feel that if things were as incorrect as you suggest, we'd have hit more problems. So I suspect there's a flaw in your logic, I just don't know what it is yet. I'm willing to do some digging, but it's hard to find the time to work through the example you give, which involves pip and some quite long lists of candidates.

If you were able to trim your example down to something smaller, preferably not using pip but with a standalone bit of code that "drives" resolvelib directly (there are examples in the examples directory and the tests) then it might be easier to understand what exactly you're demonstrating here. Otherwise you'll be waiting until someone can analyze the whole pip interaction in this case.

[sanderr]

All right, I'll have a look at that. I'm not sure when I'll find the time to do so though, perhaps this weekend. Thanks for your suggestion.

[jaap3]

Add me to the list of people that wants to look into how exactly this is triggered.

I'd also like to look into the following example. When pip (or resolvelib, I'm not sure who exactly is responsible for what) is instructed to install flake8 (at any version) and flake8-isort>=4 there's still a lot of backtracking over, and downloading of, older flake8 versions:

$ pip install --no-cache-dir --progress-bar off flake8 'flake8-isort>=4'
Collecting flake8
  Downloading flake8-4.0.1-py2.py3-none-any.whl (64 kB)
Collecting flake8-isort>=4
  Downloading flake8_isort-4.0.0-py2.py3-none-any.whl (14 kB)
Collecting pyflakes<2.5.0,>=2.4.0
  Downloading pyflakes-2.4.0-py2.py3-none-any.whl (69 kB)
Collecting pycodestyle<2.9.0,>=2.8.0
  Downloading pycodestyle-2.8.0-py2.py3-none-any.whl (42 kB)
Collecting mccabe<0.7.0,>=0.6.0
  Downloading mccabe-0.6.1-py2.py3-none-any.whl (8.6 kB)
Collecting isort<6,>=4.3.5
  Downloading isort-5.9.3-py3-none-any.whl (106 kB)
Collecting flake8
  Downloading flake8-3.9.2-py2.py3-none-any.whl (73 kB)
Collecting testfixtures<7,>=6.8.0
  Downloading testfixtures-6.18.3-py2.py3-none-any.whl (95 kB)
Collecting flake8
  Downloading flake8-3.9.1-py2.py3-none-any.whl (73 kB)
  Downloading flake8-3.9.0-py2.py3-none-any.whl (73 kB)
  Downloading flake8-3.8.4-py2.py3-none-any.whl (72 kB)
  Downloading flake8-3.8.3-py2.py3-none-any.whl (72 kB)
  Downloading flake8-3.8.2-py2.py3-none-any.whl (72 kB)
  Downloading flake8-3.8.1-py2.py3-none-any.whl (72 kB)
  Downloading flake8-3.8.0-py2.py3-none-any.whl (72 kB)
  Downloading flake8-3.7.9-py2.py3-none-any.whl (69 kB)
Collecting entrypoints<0.4.0,>=0.3.0
  Downloading entrypoints-0.3-py2.py3-none-any.whl (11 kB)
Collecting flake8
  Downloading flake8-3.7.8-py2.py3-none-any.whl (70 kB)
  Downloading flake8-3.7.7-py2.py3-none-any.whl (68 kB)
  Downloading flake8-3.7.6-py2.py3-none-any.whl (68 kB)
  Downloading flake8-3.7.5-py2.py3-none-any.whl (68 kB)
  Downloading flake8-3.7.4-py2.py3-none-any.whl (69 kB)
  Downloading flake8-3.7.3-py2.py3-none-any.whl (69 kB)
  Downloading flake8-3.7.2-py2.py3-none-any.whl (68 kB)
  Downloading flake8-3.7.1-py2.py3-none-any.whl (70 kB)
  Downloading flake8-3.7.0-py2.py3-none-any.whl (68 kB)
  Downloading flake8-3.6.0-py2.py3-none-any.whl (68 kB)
  Downloading flake8-3.5.0-py2.py3-none-any.whl (69 kB)
  Downloading flake8-3.4.1-py2.py3-none-any.whl (68 kB)
  Downloading flake8-3.4.0-py2.py3-none-any.whl (67 kB)
  Downloading flake8-3.3.0-py2.py3-none-any.whl (66 kB)
  Downloading flake8-3.2.1-py2.py3-none-any.whl (66 kB)
INFO: pip is looking at multiple versions of flake8-isort to determine which version is compatible with other requirements. This could take a while.
INFO: pip is looking at multiple versions of <Python from Requires-Python> to determine which version is compatible with other requirements. This could take a while.
INFO: pip is looking at multiple versions of flake8 to determine which version is compatible with other requirements. This could take a while.
  Downloading flake8-4.0.0-py2.py3-none-any.whl (64 kB)
INFO: pip is looking at multiple versions of pyflakes to determine which version is compatible with other requirements. This could take a while.
INFO: pip is looking at multiple versions of pycodestyle to determine which version is compatible with other requirements. This could take a while.
Collecting pycodestyle<2.8.0,>=2.7.0
  Downloading pycodestyle-2.7.0-py2.py3-none-any.whl (41 kB)
Collecting pyflakes<2.4.0,>=2.3.0
  Downloading pyflakes-2.3.1-py2.py3-none-any.whl (68 kB)
Installing collected packages: pyflakes, pycodestyle, mccabe, testfixtures, isort, flake8, flake8-isort
Successfully installed flake8-3.9.2 flake8-isort-4.0.0 isort-5.9.3 mccabe-0.6.1 pycodestyle-2.7.0 pyflakes-2.3.1 testfixtures-6.18.3

[pradyunsg]

Reopening, since there seems to be active discussion.

[sanderr]

The following test case reproduces the behavior I'm seeing with a simple Provider. Not the cleanest implementation (but it will do for a POC) and it doesn't prove the presence of a bug yet, it just provides a simpler, more direct reproduction of the situation.

from pkg_resources import Requirement

from resolvelib import (
    AbstractProvider,
    BaseReporter,
    Resolver,
)

def test_poc():
    all_candidates = {
        "parent": [("parent", "1", ["child<2"])],
        "child": [
            ("child", "2", ["grandchild>=2"]),
            ("child", "1", ["grandchild<2"]),
        ],
        "grandchild": [
            ("grandchild", "2", []),
            ("grandchild", "1", []),
        ],
    }

    class Provider(AbstractProvider):
        def identify(self, requirement_or_candidate):
            req = Requirement.parse(requirement_or_candidate)
            assert req.key in all_candidates
            return req.key

        def get_preference(self, *, identifier, **_):
            # prefer child over parent (alphabetically)
            return identifier

        def get_dependencies(self, candidate):
            return candidate[2]

        def find_matches(self, identifier, requirements, incompatibilities):
            return (
                candidate
                for candidate in all_candidates[identifier]
                if all(
                    candidate[1] in Requirement.parse(req)
                    for req in requirements[identifier]
                )
                if candidate not in incompatibilities[identifier]
            )

        def is_satisfied_by(self, requirement, candidate):
            return candidate[1] in Requirement.parse(requirement)

    resolver = Resolver(Provider(), BaseReporter())
    result = resolver.resolve(["child", "parent"])

    assert set(result.mapping) == {"parent", "child", "grandchild"}
    assert result.mapping["parent"][1] == "1"
    assert result.mapping["child"][1] == "1"
    assert result.mapping["grandchild"][1] == "1"

The test succeeds because there are no assertions against this behavior yet. It does manage to install the expected versions, but at some point it rejects a valid version. I believe it eventually backtracks and accepts that version then, but I believe the initial rejection is incorrect.

Like I said, this needs some refinement still. At the moment, if you want to observe the rejection, I'd suggest adding a breakpoint at https://github.com/sarugaku/resolvelib/blob/62c56b587c69a42c8f006e032bbf17a63df54d45/src/resolvelib/resolvers.py#L215

(Pdb) e.criterion
Criterion(('grandchild>=2', via=('child', '2', ['grandchild>=2'])), ('grandchild<2', via=('child', '1', ['grandchild<2'])))

Interesting to note is that in this scenario (like with the flake8, flake8-isort issue), the rejection does not occur when you revert preference order.

I'll expand on this, making the test provide more valuable information to definitely prove/refute the presence of undesired behavior, perhaps digging a bit more into Resolution._add_to_criteria(). I thought I'd share this now even though it's not complete because

1. it's simpler and more direct than the example using pip
2. flake8-isort appears to have released a patched version, making the initial issue more difficult to reproduce.

If anything's unclear, please let me know.

[pfmoore]

Many thanks for putting this together. I'll take a proper look at it in the next few days.

[pradyunsg]

Attached the debugging reporter from inside pip. Here's the output of that.

Reporter.starting()
Reporter.adding_requirement('child', None)
Reporter.adding_requirement('parent', None)
Reporter.starting_round(0)
Reporter.adding_requirement('grandchild>=2', ('child', '2', ['grandchild>=2']))
Reporter.pinning(('child', '2', ['grandchild>=2']))
Reporter.ending_round(0, state)
Reporter.starting_round(1)
Reporter.pinning(('grandchild', '2', []))
Reporter.ending_round(1, state)
Reporter.starting_round(2)
Reporter.adding_requirement('child<2', ('parent', '1', ['child<2']))
Reporter.pinning(('parent', '1', ['child<2']))
Reporter.ending_round(2, state)
Reporter.starting_round(3)
Reporter.adding_requirement('grandchild<2', ('child', '1', ['grandchild<2']))
Reporter.backtracking(('parent', '1', ['child<2']))
Reporter.backtracking(('grandchild', '2', []))
Reporter.backtracking(('child', '2', ['grandchild>=2']))
Reporter.ending_round(3, state)
Reporter.starting_round(4)
Reporter.adding_requirement('grandchild<2', ('child', '1', ['grandchild<2']))
Reporter.pinning(('child', '1', ['grandchild<2']))
Reporter.ending_round(4, state)
Reporter.starting_round(5)
Reporter.pinning(('grandchild', '1', []))
Reporter.ending_round(5, state)
Reporter.starting_round(6)
Reporter.adding_requirement('child<2', ('parent', '1', ['child<2']))
Reporter.pinning(('parent', '1', ['child<2']))
Reporter.ending_round(6, state)
Reporter.starting_round(7)
Reporter.ending(State(mapping=OrderedDict([('child', ('child', '1', ['grandchild<2'])), ('grandchild', ('grandchild', '1', [])), ('parent', ('parent', '1', ['child<2']))]), criteria={'child': Criterion(('child', via=None), ('child<2', via=('parent', '1', ['child<2']))), 'parent': Criterion(('parent', via=None)), 'grandchild': Criterion(('grandchild<2', via=('child', '1', ['grandchild<2'])))}, backtrack_causes=[RequirementInformation(requirement='grandchild>=2', parent=('child', '2', ['grandchild>=2'])), RequirementInformation(requirement='grandchild<2', parent=('child', '1', ['grandchild<2']))]))

To be clear, could you clarify which of parent/child/grandchild is analogous to flake8/flake8-isort?

[sanderr]

Thanks for that. I'll have a look at that soon. parent, child and grandchild are representative of flake8-isort, flake8 and pyflakes respectively. child has two versions, each with their own, non-overlapping dependency on grandchild. The test is set up so that child-2 gets selected first, which then turns out to be incompatible with parent, so child-1 is tried. This initially gets rejected, seemingly (I guess this is the part I'm most uncertain of in my reasoning) because its constraint on grandchild conflicts with the constraint the previously selected child-2 has on it.

[pradyunsg]

AFAICT, the backtracking here is happening since the resolver is creating a state of (child=2, parent=1, grandchild=2) -- something that's clearly invalid -- in the first three rounds.

It realises that the choices are all wrong, and then moves on to another combination -- which is an older version of child, leading to (child=1, parent=1, grandchild=1) which it creates over the next three rounds, succeeds and is returned in the 7th round.

It's unclear to me what the issue here is? Is it the fact that it rejected a set of requirements containing parent=1 in the first round? The problem there isn't parent=1 alone, but that in combination with the other choices, it does not make sense.

[pradyunsg]

So... consider me nerd-sniped for looking into this. Here's a consistent reproducer that should work for the forseeable future, that (with pip 21.3) has enough debug logging to tell you what the resolver's doing.

Run it in a clean environment, ideally; so that you don't need the pip uninstall.

pip uninstall flake8 pyflakes pycodestyle isort mccabe testfixtures flake8-isort --yes
PIP_RESOLVER_DEBUG=1 pip install "flake8 <= 4.0.1" "flake8-isort < 4.1.0"

In case anyone couldn't be arsed to run this but is still interested in looking at a very verbose log of the resolver's operation, see: https://gist.github.com/pradyunsg/070a7fefb7eaefa5ecf5523279b0f503

[sanderr]

As far as I can tell, the state that gets rejected is the same as the final one. It is child=1 that is considered as a candidate, and it appears to fail because it is considered in combination with the criteria set by child=2. At least, that's how I interpret the criterion attached to the exception. (I haven't had the time to look at the pip reporter output in more detail yet, so that's not taken into consideratiom for the above.)

[sanderr]

So, I've been thinking about the possible implications of this some more. The example I gave above does not result in an undesired end state, so it might not be best suited to illustrate the undesired behavior that I think is going on. I've made one small adjustment that makes this come more to the foreground. If we add a third child version, lowest of all, which depends on grandchild without constraining it, child=2 will be selected first, deemed incompatible with parent=1, child=1 is tried and rejected, so then child=0.1 is tried and accepted. In this case we don't end up with the desired end state, albeit a valid one. The state being valid doesn't mean there isn't an issue though: another valid, arguably more suitable, state gets rejected, which leads to an older than necessary state being reached. This way, the latest compatible child will always be skipped in preference of the second latest.

def test_poc():
    all_candidates = {
        "parent": [("parent", "1", ["child<2"])],
        "child": [
            ("child", "2", ["grandchild>=2"]),
            ("child", "1", ["grandchild<2"]),
            ("child", "0.1", ["grandchild"]),
        ],
        "grandchild": [
            ("grandchild", "2", []),
            ("grandchild", "1", []),
        ],
    }

    class Provider(AbstractProvider):
        def identify(self, requirement_or_candidate):
            req = Requirement.parse(requirement_or_candidate)
            assert req.key in all_candidates
            return req.key

        def get_preference(self, *, identifier, **_):
            # prefer child over parent (alphabetically)
            return identifier

        def get_dependencies(self, candidate):
            return candidate[2]

        def find_matches(self, identifier, requirements, incompatibilities):
            return (
                candidate
                for candidate in all_candidates[identifier]
                if all(
                    candidate[1] in Requirement.parse(req)
                    for req in requirements[identifier]
                )
                if candidate not in incompatibilities[identifier]
            )

        def is_satisfied_by(self, requirement, candidate):
            return candidate[1] in Requirement.parse(requirement)

    resolver = Resolver(Provider(), BaseReporter())
    result = resolver.resolve(["child", "parent"])

    assert set(result.mapping) == {"parent", "child", "grandchild"}
    assert result.mapping["parent"][1] == "1"
    assert result.mapping["child"][1] == "1"
    assert result.mapping["grandchild"][1] == "1"

(The test fails now.)

[sanderr]

This way, the latest compatible child will always be skipped in preference of the second latest.

Actually, it's even worse: suppose there exist many newer versions of child between 1 and 2 (with the same constraint on grandchild), all of those will get rejected, always selecting 0.1 over any of the 1.*. While you could argue this is just about optimization, this state isn't even pareto optimal, which I would argue is an actual issue.

[sanderr]

I've extended the test case a bit more, adding a check for what I believe to be the undesired behavior. I've also added a POC fix. I can't comment on the stability of the fix yet but I believe it's quite naive at the moment. In any case, it makes the test succeed and I hope it will help illustrate exactly what I think is going wrong. I'll post both below. If you'd prefer me to open a draft pull request instead I could do that as well, thought that could decentralize the discussion. One thing I'm unsure on is if I've interpreted Provider.identify correctly? If we take the test case as an example, is it meant to accept both the full candidate object (("child", "2", ["grandchild>=2"])) and the requirement object ("grandchild>=2")?

from pkg_resources import Requirement
from typing import List, Sequence, Set

from resolvelib import (
    AbstractProvider,
    BaseReporter,
)
from resolvelib.resolvers import (
    Criterion,
    Resolution,
    Resolver,
    RequirementInformation,
    RequirementsConflicted,
)

def test_poc(monkeypatch):
    all_candidates = {
        "parent": [("parent", "1", ["child<2"])],
        "child": [
            ("child", "2", ["grandchild>=2"]),
            ("child", "1", ["grandchild<2"]),
            ("child", "0.1", ["grandchild"]),
        ],
        "grandchild": [
            ("grandchild", "2", []),
            ("grandchild", "1", []),
        ],
    }

    class Provider(AbstractProvider):
        def identify(self, requirement_or_candidate):
            result: str = (
                Requirement.parse(requirement_or_candidate).key
                if isinstance(requirement_or_candidate, str)
                else requirement_or_candidate[0]
            )
            assert result in all_candidates
            return result

        def get_preference(self, *, identifier, **_):
            # prefer child over parent (alphabetically)
            return identifier

        def get_dependencies(self, candidate):
            return candidate[2]

        def find_matches(self, identifier, requirements, incompatibilities):
            return (
                candidate
                for candidate in all_candidates[identifier]
                if all(
                    candidate[1] in Requirement.parse(req)
                    for req in requirements[identifier]
                )
                if candidate not in incompatibilities[identifier]
            )

        def is_satisfied_by(self, requirement, candidate):
            return candidate[1] in Requirement.parse(requirement)

    # patch Resolution._get_updated_criteria to collect rejected states
    rejected_criteria: List[Criterion] = []
    get_updated_criterion_orig = Resolution._get_updated_criteria

    def get_updated_criterion_patch(self, candidate) -> None:
        try:
            return get_updated_criterion_orig(self, candidate)
        except RequirementsConflicted as e:
            rejected_criteria.append(e.criterion)
            raise

    monkeypatch.setattr(
        Resolution, "_get_updated_criteria", get_updated_criterion_patch
    )

    resolver = Resolver(Provider(), BaseReporter())
    result = resolver.resolve(["child", "parent"])

    def get_child_versions(information: Sequence[RequirementInformation]) -> Set[str]:
        return {
            inf[1][1]
            for inf in information
            if inf[1][0] == "child"
        }

    # verify that none of the rejected criteria are based on more than one candidate for
    # child
    # this check fails without the patch below
    assert not any(
        len(get_child_versions(criterion.information)) > 1
        for criterion in rejected_criteria
    )

    assert set(result.mapping) == {"parent", "child", "grandchild"}
    assert result.mapping["parent"][1] == "1"
    # this check fails without the patch below
    assert result.mapping["child"][1] == "1"
    assert result.mapping["grandchild"][1] == "1"

diff --git a/src/resolvelib/resolvers.py b/src/resolvelib/resolvers.py
index 787681b..458c2c8 100644
--- a/src/resolvelib/resolvers.py
+++ b/src/resolvelib/resolvers.py
@@ -199,7 +199,23 @@ class Resolution(object):
         )

     def _get_updated_criteria(self, candidate):
-        criteria = self.state.criteria.copy()
+        # copy current state's criteria, filtering out any information with this
+        # candidate's other versions as parent
+        criteria = {
+            name: Criterion(
+                criterion.candidates,
+                [
+                    information
+                    for information in criterion.information
+                    if (
+                        information[1] is None
+                        or self._p.identify(information[1]) != self._p.identify(candidate)
+                    )
+                ],
+                criterion.incompatibilities,
+            )
+            for name, criterion in self.state.criteria.items()
+        }
         for requirement in self._p.get_dependencies(candidate=candidate):
             self._add_to_criteria(criteria, requirement, parent=candidate)
         return criteria

I might be willing to work on an actual fix (I'll need to make sure I can find the time for it first) but for now I'll await some response on the above. I think it should provide sufficient input for you to determine with some confidence whether you agree with my assessment of the situation and the general direction of the fix or whether I'm way off.

[pradyunsg]

is it meant to accept both the full candidate object (("child", "2", ["grandchild>=2"])) and the requirement object ("grandchild>=2")?

Yes.

[pfmoore]

So the resolution goes:

1. pin child 2 (latest version of the first requirement in the input list)
2. this pins grandchild 2 (only thing it can pin)
3. nothing more to do on child, now look at parent - pins parent 1 (latest/only version of parent)
4. now the child requirement of parent is unsatisfied, so look at that - we need child<2
5. our options are child 1 and child 0.1
6. we look at child 1 (which has constraint grandchild<2)
7. that conflicts with the constraint for child 2, so we fail to pin

I agree that looks weird. We're looking for conflicts, but we should never be able to have child 1 and child 2 in the resolution together, so conflicts between them can't be relevant. And the approach you're proposing to fix this seems reasonable.

I think it should provide sufficient input for you to determine with some confidence whether you agree with my assessment of the situation and the general direction of the fix or whether I'm way off.

It does, and I do agree with your assessment here. Thanks for your patience in explaining what you'd spotted.

[notatallshaw]

I was trying to test the patch given in https://github.com/sarugaku/resolvelib/issues/91#issuecomment-944902295

But one thing I found when running python -m pip download apache-airflow[all]==1.10.13 -d downloads using Python 3.7 on Linux is I get the error:

ERROR: Exception:
Traceback (most recent call last):
  File "/home/damian/incompat/pip/src/pip/_internal/cli/base_command.py", line 164, in exc_logging_wrapper
    status = run_func(*args)
  File "/home/damian/incompat/pip/src/pip/_internal/cli/req_command.py", line 205, in wrapper
    return func(self, options, args)
  File "/home/damian/incompat/pip/src/pip/_internal/commands/download.py", line 128, in run
    requirement_set = resolver.resolve(reqs, check_supported_wheels=True)
  File "/home/damian/incompat/pip/src/pip/_internal/resolution/resolvelib/resolver.py", line 93, in resolve
    collected.requirements, max_rounds=try_to_avoid_resolution_too_deep
  File "/home/damian/incompat/pip/src/pip/_vendor/resolvelib/resolvers.py", line 498, in resolve
    state = resolution.resolve(requirements, max_rounds=max_rounds)
  File "/home/damian/incompat/pip/src/pip/_vendor/resolvelib/resolvers.py", line 389, in resolve
    name = min(unsatisfied_names, key=self._get_preference)
  File "/home/damian/incompat/pip/src/pip/_vendor/resolvelib/resolvers.py", line 189, in _get_preference
    backtrack_causes=self.state.backtrack_causes,
  File "/home/damian/incompat/pip/src/pip/_internal/resolution/resolvelib/provider.py", line 96, in get_preference
    candidate, ireqs = zip(*lookups)
ValueError: not enough values to unpack (expected 2, got 0)

I dug a little deeper and found that for some reason when assessing charset-normalizer it has an empty Criterion(). Maybe there's some edge case that is not accounted for.

[uranusjr]

when assessing charset-normalizer it has an empty Criterion()

Oh no. We should probably fix that and add a test to make sure that doesn't happen. Maybe we should also add a check in Criterion to make sure no empty objects are possible (tidbit—this used to be possible but I switched away from the design because checking for an empty Criterion creates all sorts of difficulties in the implementation, it's better to not push them into the state in the first place).

[sanderr]

I'm cleaning up my fix to open up a pull request. I'm wondering about the last two comments. If I understand the situation correctly pip fails here because in its implementation of get_preference it assumes information[identifier] will have at least one element. As far as I can see this is not part of the contract in AbstractProvider.

@uranusjr are you suggesting we should not have Criterion objects with an empty information list? We shouldn't just discard such criteria either, should we? I would think we'd lose valuable candidates and incompatibilities data. Could you shed some more light on this?