AttributeError: 'NoneType' object has no attribute 'excluded_of' on pip 20.3

[rcjsuen]

Environment

• pip version: 20.3
• Python version: 3.9.0
• OS: Linux

This error has happened locally on my computer, in CircleCI, and in Docker.

Description
Some combination of dependencies seems to cause an AttributeError to be thrown.

ERROR: Exception:
Traceback (most recent call last):
  File "/usr/local/lib/python3.9/site-packages/pip/_internal/cli/base_command.py", line 210, in _main
    status = self.run(options, args)
  File "/usr/local/lib/python3.9/site-packages/pip/_internal/cli/req_command.py", line 180, in wrapper
    return func(self, options, args)
  File "/usr/local/lib/python3.9/site-packages/pip/_internal/commands/install.py", line 318, in run
    requirement_set = resolver.resolve(
  File "/usr/local/lib/python3.9/site-packages/pip/_internal/resolution/resolvelib/resolver.py", line 121, in resolve
    self._result = resolver.resolve(
  File "/usr/local/lib/python3.9/site-packages/pip/_vendor/resolvelib/resolvers.py", line 445, in resolve
    state = resolution.resolve(requirements, max_rounds=max_rounds)
  File "/usr/local/lib/python3.9/site-packages/pip/_vendor/resolvelib/resolvers.py", line 344, in resolve
    success = self._backtrack()
  File "/usr/local/lib/python3.9/site-packages/pip/_vendor/resolvelib/resolvers.py", line 287, in _backtrack
    criterion = self.state.criteria[name].excluded_of([candidate])
AttributeError: 'NoneType' object has no attribute 'excluded_of'

Expected behavior
I would expect pip to complete (noting the dependency issue between redis-log-handler and redis) but at least not dying due to an exçeption.

How to Reproduce

1. Create this Dockerfile.

FROM python:3.9.0
RUN pip install --upgrade pip
RUN pip install celery==5.0.2 kombu==5.0.2 "billiard<4.0,>=3.6.0" redis==3.5.3 redis-log-handler==0.0.1.dev32

2. Run docker build .
3. Alternatively, you can also just run pip install celery==5.0.2 kombu==5.0.2 "billiard<4.0,>=3.6.0" redis==3.5.3 redis-log-handler==0.0.1.dev32 in your virtual environment and you should be able to reproduce the error.

Output

$ docker build .
Sending build context to Docker daemon  7.122MB
Step 1/3 : FROM python:3.9.0
 ---> a3fe352c5377
Step 2/3 : RUN pip install --upgrade pip
 ---> Running in 1587f59e4cdd
Collecting pip
  Downloading pip-20.3-py2.py3-none-any.whl (1.5 MB)
Installing collected packages: pip
  Attempting uninstall: pip
    Found existing installation: pip 20.2.4
    Uninstalling pip-20.2.4:
      Successfully uninstalled pip-20.2.4
Successfully installed pip-20.3
Removing intermediate container 1587f59e4cdd
 ---> 81b286c9cca5
Step 3/3 : RUN pip install celery==5.0.2 kombu==5.0.2 "billiard<4.0,>=3.6.0" redis==3.5.3 redis-log-handler==0.0.1.dev32
 ---> Running in c6c759d04b82
Collecting billiard<4.0,>=3.6.0
  Downloading billiard-3.6.3.0-py3-none-any.whl (89 kB)
Collecting celery==5.0.2
  Downloading celery-5.0.2-py3-none-any.whl (392 kB)
Collecting kombu==5.0.2
  Downloading kombu-5.0.2-py2.py3-none-any.whl (180 kB)
Collecting redis==3.5.3
  Downloading redis-3.5.3-py2.py3-none-any.whl (72 kB)
Collecting redis-log-handler==0.0.1.dev32
  Downloading redis_log_handler-0.0.1.dev32-py2.py3-none-any.whl (5.1 kB)
INFO: pip is looking at multiple versions of redis to determine which version is compatible with other requirements. This could take a while.
INFO: pip is looking at multiple versions of kombu to determine which version is compatible with other requirements. This could take a while.
INFO: pip is looking at multiple versions of celery to determine which version is compatible with other requirements. This could take a while.
INFO: pip is looking at multiple versions of billiard to determine which version is compatible with other requirements. This could take a while.
Collecting billiard<4.0,>=3.6.0
  Downloading billiard-3.6.2.0-py3-none-any.whl (89 kB)
ERROR: Exception:
Traceback (most recent call last):
  File "/usr/local/lib/python3.9/site-packages/pip/_internal/cli/base_command.py", line 210, in _main
    status = self.run(options, args)
  File "/usr/local/lib/python3.9/site-packages/pip/_internal/cli/req_command.py", line 180, in wrapper
    return func(self, options, args)
  File "/usr/local/lib/python3.9/site-packages/pip/_internal/commands/install.py", line 318, in run
    requirement_set = resolver.resolve(
  File "/usr/local/lib/python3.9/site-packages/pip/_internal/resolution/resolvelib/resolver.py", line 121, in resolve
    self._result = resolver.resolve(
  File "/usr/local/lib/python3.9/site-packages/pip/_vendor/resolvelib/resolvers.py", line 445, in resolve
    state = resolution.resolve(requirements, max_rounds=max_rounds)
  File "/usr/local/lib/python3.9/site-packages/pip/_vendor/resolvelib/resolvers.py", line 344, in resolve
    success = self._backtrack()
  File "/usr/local/lib/python3.9/site-packages/pip/_vendor/resolvelib/resolvers.py", line 287, in _backtrack
    criterion = self.state.criteria[name].excluded_of([candidate])
AttributeError: 'NoneType' object has no attribute 'excluded_of'
The command '/bin/sh -c pip install celery==5.0.2 kombu==5.0.2 "billiard<4.0,>=3.6.0" redis==3.5.3 redis-log-handler==0.0.1.dev32' returned a non-zero code: 2

[pradyunsg]

@uranusjr ^

[uranusjr]

Thanks for the report! I am able to reproduce without kombu (i.e. celery==5.0.2 "billiard<4.0,>=3.6.0" redis==3.5.3 redis-log-handler==0.0.1.dev32).

[uranusjr]

(For maintainers) So the issue is in the new backtracking code:

incompatibilities_from_broken = [
    (k, v.incompatibilities)
    for k, v in broken_state.criteria.items()
]

# Snipped.

for k, incompatibilities in incompatibilities_from_broken:
    try:
        crit = self.state.criteria[k]
    except KeyError:
        continue
    self.state.criteria[k] = crit.excluded_of(incompatibilities)

excluded_of() returns None if the added incompatibilities would exhaut the criterion’s candidate set. I thought it’s impossible for this to happen here (since all incompatibilites applied here were also in effect in the broken state). This isn’t difficult to fix (just add a clause to trigger further backtracking when that happens), but I’m a bit worried since I am not sure why it’s possible.

[pradyunsg]

If I use the commit before the resolvelib update:

ERROR: Cannot install redis==3.5.3 and redis-log-handler 0.0.1.dev32 because these package versions have conflicting dependencies.

The conflict is caused by:
    The user requested redis==3.5.3
    redis-log-handler 0.0.1.dev32 depends on redis==3.0.1

To fix this you could try to:
1. loosen the range of package versions you've specified
2. remove package versions to allow pip attempt to solve the dependency conflict

ERROR: ResolutionImpossible: for help visit https://pip.pypa.io/en/latest/user_guide/#fixing-conflicting-dependencies

IIUC, the criterion being empty is what we should expect in this case? And I think we should be backtracking in that case?

[uranusjr]

I was not expecting it to happen because at this point we are re-applying the incompatibilities from the broken state, but not the final incompatibility that broke the broken state. Those incompatibilities should therefore not break the new state either, since the broken state should not reach the point it is in in the first place if that’s the case. The newly-added incompatibility (which will be added later) should be the only one that may break the new state, if my reasoning is correct.

Assuming my reasoning in wrong, yes, we should bactrack in this case.

[pradyunsg]

Maybe? I'm gonna step through a debugger for this.

[brainwane]

@rcjsuen I just want to say: Hello and thank you for your bug report! I'm sorry you're having trouble right now. Thank you for sharing your report with us.

I'll mention here one useful troubleshooting and workaround tip from the documentation: If you need a temporary workaround, you can choose the old resolver behavior using the flag --use-deprecated=legacy-resolver. This will work until we release pip 21.0 (see Deprecation timeline).

(If you don't mind, please also tell us what could have happened differently so you could have tested and caught and reported this during the pip resolver beta period.)

[rcjsuen]

@rcjsuen I just want to say: Hello and thank you for your bug report! I'm sorry you're having trouble right now. Thank you for sharing your report with us.

@brainwane No worries, happy to help.

I'll mention here one useful troubleshooting and workaround tip from the documentation: If you need a temporary workaround, you can choose the old resolver behavior using the flag --use-deprecated=legacy-resolver. This will work until we release pip 21.0 (see Deprecation timeline).

We worked around the issue by pinning our dependencies so that they do not cause a conflict. Thank you for suggesting this workaround though as I'm sure others reading this issue may get some use out of it.

(If you don't mind, please also tell us what could have happened differently so you could have tested and caught and reported this during the pip resolver beta period.)

Honestly, I don't think there was any way I could have caught this earlier. Our builds just run pip install --upgrade pip and I have no interest in installing a beta version of pip on my system so I don't think I would have caught this until the day 20.3 went live.

[ardila]

I'm also running into this issue. I don't think pip should be crashing for any set of dependencies right? It should just error out. I expect many people will soon run into this issue as more base docker images including the new version of pip are pushed out. I will follow this issue to see what happens, but for now we are reverting to the old resolver as recommended here.

[brainwane]

Sorry this hasn't gotten fixed yet; we have it on the roadmap to fix in the bugfix release 20.3.3.

Honestly, I don't think there was any way I could have caught this earlier. Our builds just run pip install --upgrade pip and I have no interest in installing a beta version of pip on my system so I don't think I would have caught this until the day 20.3 went live.

In pip 20.2, a beta of the new resolver was available, opt-in, using the flag --use-feature=2020-resolver; was this something that could have helped you @rcjsuen ? (Perhaps you did not hear about it in time.) I want to know because we will probably roll out new features in the future and I want to make those rollouts as smooth and testable as possible.

[rcjsuen]

In pip 20.2, a beta of the new resolver was available, opt-in, using the flag --use-feature=2020-resolver; was this something that could have helped you @rcjsuen ? (Perhaps you did not hear about it in time.)

@brainwane No, it would not have helped me because I have no interest in enabling a flag for a beta feature in our build pipeline.

I want to know because we will probably roll out new features in the future and I want to make those rollouts as smooth and testable as possible.

I think you certainly should offer such a flag so people can test new and upcoming features. You should be aware that it does not mean people will test said new features though. Everyone has their own priorities and I have to admit that testing beta features for pip is not high on my list.

[chriselion]

@brainwane

we have it on the roadmap to fix in the bugfix release 20.3.3

Did a fix for this make it into 20.3.3? I see that was released a few days ago.

[uranusjr]

No, there was a critical bug in 20.3.2, and 20.3.3 was assigned as an emergency release to fix that instead. This will likely be in 20.3.4.

[chriselion]

OK, thanks for the update.