Pip fails to install some satisfiable requirements since extras optimization

[notatallshaw]

Description

In Pip 23.3, an extras optimization was introduced to improve the speed of backtracking when dealing with extras. However, under specific circumstances, this optimization can lead to Pip failing to install valid requirements.

In PR kedro-org/kedro#3182 it linked to a Pip issue #12317 as a cause of resolution failure, but investigating I found:

1. The issue started occurring in Pip 23.3, not Pip 23.1.
2. After examining the relevant code sarugaku/resolvelib#134, it seemed it was not responsible for triggering this error and therefore the error the PR is working around is not issue #12317

To further investigate I tested various Pip branches, and I believe the problem arises when the following warning is encountered:

WARNING: <package> <version> does not provide the extra '<extra>'

I hypothesize that the optimization is being applied when no extra actually exists. This occurs because extras are optional, and Pip will simply emit a warning when an extra is not present.

Expected behavior

Optimization should not cause failure

pip version

pip 23.3.1

Python version

3.11

OS

Linux

How to Reproduce

1. git clone https://github.com/kedro-org/kedro
2. cd kedro
3. python3.11 -m venv .venv
4. source .venv/bin/activate
5. python -m pip install pip --upgrade
6. pip install --dry-run .[test]

Output

...
WARNING: import-linter 1.8.0 does not provide the extra 'toml'
ERROR: Cannot install dask[complete]==2021.12.0 and kedro[test]==0.18.14 because these package versions have conflicting dependencies.

The conflict is caused by:
    kedro[test] 0.18.14 depends on dask~=2021.10; extra == "test"
    dask[complete] 2021.12.0 depends on dask 2021.12.0 (from https://files.pythonhosted.org/packages/15/6d/99c63be3ea8a4a651d845addeea1f1b3bb8e5c6730bc26cfb6176631adf7/dask-2021.12.0-py3-none-any.whl (from https://pypi.org/simple/dask/) (requires-python:>=3.7))

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/topics/dependency-resolution/#dealing-with-dependency-conflicts

Code of Conduct

• I agree to follow the PSF Code of Conduct.

[notatallshaw]

CC: @uranusjr @sanderr @sbidoul

FYI to be clear this is a regression since Pip 23.3, not sure how critical you consider it.

[sanderr]

I can not try for myself right now but this looks to me like the same root cause as #12372 (comment). I already have a potential fix to it (linked in that discussion).

[notatallshaw]

I can not try for myself right now but this looks to me like the same root cause as #12372 (comment). I already have a potential fix to it (linked in that discussion).

I don't think so, which is why I didn't add this example to that issue. And testing your branch I get the same error:

$ pip install https://github.com/sanderr/pip/archive/refs/heads/issue/12373-bugfix-install-local-extra.zip
...
$ pip install --dry-run .[test]
...
WARNING: import-linter 1.8.0 does not provide the extra 'toml'
ERROR: Cannot install dask[complete]==2021.12.0 and kedro[test]==0.18.14 because these package versions have conflicting dependencies.

The conflict is caused by:
    kedro[test] 0.18.14 depends on dask~=2021.10; extra == "test"
    dask[complete] 2021.12.0 depends on dask 2021.12.0 (from https://files.pythonhosted.org/packages/15/6d/99c63be3ea8a4a651d845addeea1f1b3bb8e5c6730bc26cfb6176631adf7/dask-2021.12.0-py3-none-any.whl (from https://pypi.org/simple/dask/) (requires-python:>=3.7))

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/topics/dependency-resolution/#dealing-with-dependency-conflicts

[notatallshaw]

I also tried the approach of pip install --dry-run kedro/[test] kedro/. and I got the same error.

That said I haven't been able to reproduce the error without using a local extra, so it could be the same root cause, but my beleif is just this is because I'm unable to successfully extract the same top level requirements Pip has collected in the order Pip has collected them (it would be great it Pip had a command for that #12185 !)

[notatallshaw]

Confirmed, it's not related to local extras install, can reproduce it by attempting to install from PyPI like so (no need to clone repo):

python -m pip install --dry-run kedro[test]==0.18.13

Which works on Pip 23.2.1 but fails on Pip 23.3.x with:

Collecting kedro==0.18.13 (from kedro[test]==0.18.13)
  Using cached kedro-0.18.13-py3-none-any.whl.metadata (25 kB)
Collecting anyconfig<0.14,>=0.10 (from kedro==0.18.13->kedro[test]==0.18.13)
  Using cached anyconfig-0.13.0-py2.py3-none-any.whl (87 kB)
Collecting attrs>=21.3 (from kedro==0.18.13->kedro[test]==0.18.13)

...

WARNING: import-linter 1.8.0 does not provide the extra 'toml'
ERROR: Cannot install dask[complete]==2021.12.0 and kedro[test]==0.18.13 because these package versions have conflicting dependencies.

The conflict is caused by:
    kedro[test] 0.18.13 depends on dask~=2021.10; extra == "test"
    dask[complete] 2021.12.0 depends on dask 2021.12.0 (from https://files.pythonhosted.org/packages/15/6d/99c63be3ea8a4a651d845addeea1f1b3bb8e5c6730bc26cfb6176631adf7/dask-2021.12.0-py3-none-any.whl (from https://pypi.org/simple/dask/) (requires-python:>=3.7))

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/topics/dependency-resolution/#dealing-with-dependency-conflicts

Also fails installing pip from https://github.com/sanderr/pip/archive/refs/heads/issue/12373-bugfix-install-local-extra.zip

[notatallshaw]

I tried debugging this a bit today, I think my hypothesis about the optimization being applied when the extra is invalid is not correct, adding some debug statements the optimization did only appear to being applied for valid extras.

Sorry I couldn't be of further help, if I think of something else I will investigate.

[sanderr]

I looked into this for some time and I think I understand more or less what's going on. First, this package has a huge and complicated dependency tree with many upper bounds, resulting in complicated resolution process. The dependency conflict seems to be an interplay between constraints on adlfs, dask and gcsfs, each of which have their own constraints on fsspec.

I am relatively confident that the root cause is that resolvelib can not reliably do the proper backtracking required to come to a satisfactory solution. That said, the specific case that resolvelib has trouble with used to be one that would only arise when dependencies with and without extra are present for the same package. Pip now inserts those itself, meaning that this behavior is triggered more easily. So it should probably be addressed.

Some more details, and a smaller reproduction follow below.

If you strip everything but the dependencies on adlfs, dask and gcsfs from the kedro setup.py and pyproject.toml, you can still reproduce the issue with pip install --dry-run .[test]. If you then add fsspec>=2021.3, <=2023.1 to the dependencies, the issue disappears. This additional constraint makes resolvelib backtrack on other packages, leading to a successful resolution (I only half understand the exact logic behind this so I can't really go into more details about that).

On pip 23.2.1, if you add dask~=2021.10 (without extra) to the dependencies, you get the same issue. This highlights that the issue is only triggered by the presence of both the extra and extra-less package. Other than that, the root cause has always been there.

#12095 made an attempt to couple extra and extra-less dependencies more tightly. However, it still has some limitations. One of them is that resolvelib still considers each a "name" to be resolved in its own right, even though both have to be the exact same version. Therefore, when a version is picked for both, resolvelib can no longer backtrack on just one of them, it would have to backtrack on both. I believe (not entirely certain) it now tries to backtrack on the one with the extra, but none of the other candidates for it are valid because the extra-less package is still pinned.

To be clear: I believe the only part of #12095 that really affects this regression is the injection of the implicit extra-less dependency. The rest of the pull request (tighter coupling of extra and extra-less dependencies) is unrelated as far as I can see.

I do not have a solution in mind yet. There are still some details that are not entirely clear to me. Perhaps some changes to the get_preferences implementation might do the trick.

[notatallshaw]

Interesting, I do wonder then if this is still an issue with backjumping but doesn't cause the specific exception that happens in the other issue.

I am interested if reverting the backjumping optimization the issue will still happen, when I get some free time I will try implementing that and see if it successfully resolved or still produces an error.

[pfmoore]

Interesting analysis. It's unfortunate that resolvelib needs these contortions to support extras - the problem is it's necessary because, while we can handle dependencies being costly to compute (and so, we calculate them on demand) we do still rely on them being constant once computed - and extras break that assumption if we take the project name/version alone as defining the candidate.

I'm not sure my observation here is particularly helpful, as I doubt we can modify something as fundamental as this, but maybe it'll suggest something 🤷

[notatallshaw]

I created a branch which reverted out the backjump optimization and for me this now resolves: notatallshaw/pip@main...remove-backjump

@sanderr when you get a chance would you mind testing this branch with your examples you give in your comment: https://github.com/notatallshaw/pip/tree/remove-backjump

I'm now of the opinion this is a correctness issue with the backjump optimization added to resolvelib, and not with the extras optimization added to Pip. And unless anyone objects we can mark this a duplicate of #12317.

I'm going to add a comment to sarugaku/resolvelib#134 and spend a little time seeing if I can spot where the backjump is incorrectly skipping over a correct state.

I do not have a solution in mind yet. There are still some details that are not entirely clear to me. Perhaps some changes to the get_preferences implementation might do the trick.

A note on this, my understanding is get_preferences should be able to produce any preference and the backtrack should eventually complete.