Repository: pypa/pip
Pull request: Upgrade vendored resolvelib to 0.5.4
Fix #9180.

Problem statement:
AttributeError: 'NoneType' object has no attribute 'excluded_of' on pip 20.3
**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
```

Hints from issue discussion:
@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`).
(For maintainers) So the issue is in the new backtracking code:

```python
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.
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?

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.
Maybe? I'm gonna step through a debugger for this.
@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](https://pip.pypa.io/en/latest/user_guide/#how-to-upgrade-and-migrate): 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](https://pip.pypa.io/en/latest/user_guide/#deprecation-timeline-for-2020-resolver-changes)).

(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 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](https://pip.pypa.io/en/latest/user_guide/#how-to-upgrade-and-migrate): 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](https://pip.pypa.io/en/latest/user_guide/#deprecation-timeline-for-2020-resolver-changes)).

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.
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.
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.

Commit message: Upgrade vendored resolvelib to 0.5.4

Patch to review:
diff --git a/news/9180.vendor.rst b/news/9180.vendor.rst
new file mode 100644
index 00000000000..61c433fe631
--- /dev/null
+++ b/news/9180.vendor.rst
@@ -0,0 +1,2 @@
+Upgrade resolvelib to 0.5.4 to fix error when an existing incompatibility is
+unable to be applied to a backtracked state.
diff --git a/src/pip/_vendor/resolvelib/__init__.py b/src/pip/_vendor/resolvelib/__init__.py
index 5a400f23ed1..f023ad63154 100644
--- a/src/pip/_vendor/resolvelib/__init__.py
+++ b/src/pip/_vendor/resolvelib/__init__.py
@@ -11,7 +11,7 @@
     "ResolutionTooDeep",
 ]
 
-__version__ = "0.5.3"
+__version__ = "0.5.4"
 
 
 from .providers import AbstractProvider, AbstractResolver
diff --git a/src/pip/_vendor/resolvelib/resolvers.py b/src/pip/_vendor/resolvelib/resolvers.py
index acf0f8a6b43..bb88d8c2c75 100644
--- a/src/pip/_vendor/resolvelib/resolvers.py
+++ b/src/pip/_vendor/resolvelib/resolvers.py
@@ -257,7 +257,7 @@ def _backtrack(self):
             information from Y to Y'.
         4a. If this causes Y' to conflict, we need to backtrack again. Make Y'
             the new Z and go back to step 2.
-        4b. If the incompatibilites apply cleanly, end backtracking.
+        4b. If the incompatibilities apply cleanly, end backtracking.
         """
         while len(self._states) >= 3:
             # Remove the state that triggered backtracking.
@@ -271,28 +271,36 @@ def _backtrack(self):
                 for k, v in broken_state.criteria.items()
             ]
 
+            # Also mark the newly known incompatibility.
+            incompatibilities_from_broken.append((name, [candidate]))
+
             self._r.backtracking(candidate)
 
             # Create a new state from the last known-to-work one, and apply
             # the previously gathered incompatibility information.
-            self._push_new_state()
-            for k, incompatibilities in incompatibilities_from_broken:
-                try:
-                    crit = self.state.criteria[k]
-                except KeyError:
-                    continue
-                self.state.criteria[k] = crit.excluded_of(incompatibilities)
+            def _patch_criteria():
+                for k, incompatibilities in incompatibilities_from_broken:
+                    if not incompatibilities:
+                        continue
+                    try:
+                        criterion = self.state.criteria[k]
+                    except KeyError:
+                        continue
+                    criterion = criterion.excluded_of(incompatibilities)
+                    if criterion is None:
+                        return False
+                    self.state.criteria[k] = criterion
+                return True
 
-            # Mark the newly known incompatibility.
-            criterion = self.state.criteria[name].excluded_of([candidate])
+            self._push_new_state()
+            success = _patch_criteria()
 
             # It works! Let's work on this new state.
-            if criterion:
-                self.state.criteria[name] = criterion
+            if success:
                 return True
 
-            # State does not work after adding the new incompatibility
-            # information. Try the still previous state.
+            # State does not work after applying known incompatibilities.
+            # Try the still previous state.
 
         # No way to backtrack anymore.
         return False
diff --git a/src/pip/_vendor/vendor.txt b/src/pip/_vendor/vendor.txt
index 4f7042cc127..1db32f396ae 100644
--- a/src/pip/_vendor/vendor.txt
+++ b/src/pip/_vendor/vendor.txt
@@ -15,7 +15,7 @@ requests==2.25.0
     chardet==3.0.4
     idna==2.10
     urllib3==1.26.2
-resolvelib==0.5.3
+resolvelib==0.5.4
 retrying==1.3.3
 setuptools==44.0.0
 six==1.15.0


Code review comments:
diff_hunk: @@ -0,0 +1,2 @@
+Upgrade resolvelib to 0.5.4 to fix error when an existing incompatibility is
path: news/9180.vendor.rst
text: @user1:
suggestion: break this into 2 fragments -- since the vendoring section is primarily for redistributors, and folks looking for whether a bug was fixed might be surprised to see this listed under vendoring?

A `resolvelib.vendor.rst` and a `9180.bugfix.rst` would be nice! :)