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.