Extremely slow dependency resolution with circular graph of dependencies

[multimeric]

Description

I have a scenario where I need to depend on 3 packages, one of which depends on the two others:

flowchart LR
    my_package --> aicsimageio
    my_package --> napari_aicsimageio
    my_package --> napari
    napari_aicsimageio --> napari
    napari_aicsimageio --> aicsimageio

Loading

When I try to install all these packages simultaneously, pip seems to struggle with the installation, but if I remove one of the nodes of the graph (thereby removing the cycle), it has no issue. Edit: actually I realise that this isn't a cycle, but I don't know how else to describe this graph pattern.

Expected behavior

In this case I expect to be able to solve the dependency tree. It may be the case that this tree of dependencies has no solution, but even if that is the case, I would hope that pip could realise it much faster than it does now.

pip version

23.2.1

Python version

3.9.12

OS

MacOS Monterey (12.6)

How to Reproduce

To obtain the infinite or very slow package solving, run this: pip install 'aicsimageio==4.9.1' 'napari-aicsimageio==0.7.2' 'napari==0.4.18'.

Note that, if you instead install two of the above three packages, pip has barely any trouble, and installs in a minute or so.

Output

The full log is extremely long, but I get lots of lines like the following:

INFO: This is taking longer than usual. You might need to provide the dependency resolver with stricter constraints to reduce runtime. See https://pip.pypa.io/warnings/backtracking for guidance. If you want to abort this run, press Ctrl + C.
INFO: pip is still looking at multiple versions of scikit-image[data] to determine which version is compatible with other requirements. This could take a while.
INFO: pip is looking at multiple versions of imageio[ffmpeg] to determine which version is compatible with other requirements. This could take a while.

Code of Conduct

• I agree to follow the PSF Code of Conduct.

[multimeric]

So indeed this does fail to solve (albeit very slowly, it takes > 30 mins on my machine). However the error message is also very confusing. I can't work out what the actual root problem is from this message:

ERROR: Cannot install aicsimageio==4.9.4, aicsimageio[all]==4.10.0, aicsimageio[all]==4.11.0, aicsimageio[all]==4.6.3, aicsimageio[all]==4.6.4, aicsimageio[all]==4.7.0, aicsimageio[all]==4.8.0, aicsimageio[all]==4.9.0, aicsimageio[all]==4.9.1, aicsimageio[all]==4.9.2 and aicsimageio[all]==4.9.3 because these package versions have conflicting dependencies.

The conflict is caused by:
    The user requested aicsimageio==4.9.4
    aicsimageio[all] 4.11.0 depends on aicsimageio 4.11.0 (from https://files.pythonhosted.org/packages/02/1c/82a8a99104d0dc5ad3e20e939099518ed872b5adb1958a68ee7d724ffa96/aicsimageio-4.11.0-py2.py3-none-any.whl#sha256=c0c3359e014689675663adfc4feef44e94ad7c536c88b8d5db3051da663addaf (from https://pypi.org/simple/aicsimageio/) (requires-python:>=3.8))
    The user requested aicsimageio==4.9.4
    aicsimageio[all] 4.10.0 depends on aicsimageio 4.10.0 (from https://files.pythonhosted.org/packages/5c/65/1a167acfdb889ba46128a1612cdab2ab37e16af704801e9660db8fd0a549/aicsimageio-4.10.0-py2.py3-none-any.whl#sha256=f9bbc453fe95f53489c9b2d0fee9aa8308f4fe2125fdd6ba66f1ff9c6172c23d (from https://pypi.org/simple/aicsimageio/) (requires-python:>=3.8))
    The user requested aicsimageio==4.9.4
    aicsimageio[all] 4.9.3 depends on aicsimageio 4.9.3 (from https://files.pythonhosted.org/packages/b0/23/74184c892518ec94c1777509eb442c9d2ac829a566f63668722c57b89749/aicsimageio-4.9.3-py2.py3-none-any.whl#sha256=ea39bc0529aa418b9bdcf0c26650e6cfd6d1e78a5d09c7cb6726203c001f7388 (from https://pypi.org/simple/aicsimageio/) (requires-python:>=3.8))
    The user requested aicsimageio==4.9.4
    aicsimageio[all] 4.9.2 depends on aicsimageio 4.9.2 (from https://files.pythonhosted.org/packages/b7/ca/eb2fab73a13cd7d826073085b87ee54106b9cc82810bdd12c3db18119286/aicsimageio-4.9.2-py2.py3-none-any.whl#sha256=073718f6072f0d6efde1af851cfc72d91d064099f3ec3babe90c5257cb065b87 (from https://pypi.org/simple/aicsimageio/) (requires-python:>=3.8))
    The user requested aicsimageio==4.9.4
    aicsimageio[all] 4.9.1 depends on aicsimageio 4.9.1 (from https://files.pythonhosted.org/packages/11/90/360999aef55b50a3b04bdf3b9f7a1145178ed1c54b25087642f60af59448/aicsimageio-4.9.1-py2.py3-none-any.whl#sha256=79964c1833632c1e84dab2ee75f06c8d22ecbcf7c26819b00a09e1c9a8ae0998 (from https://pypi.org/simple/aicsimageio/) (requires-python:>=3.8))
    The user requested aicsimageio==4.9.4
    aicsimageio[all] 4.9.0 depends on aicsimageio 4.9.0 (from https://files.pythonhosted.org/packages/e7/21/e5376c98efdced988ff81a26670423be0f8ca8d81b89f9db45819b69504b/aicsimageio-4.9.0-py2.py3-none-any.whl#sha256=dfb461af344b0ed399ce110dc436e0d0a50524f99549b3d694d8e0d2770fa4a7 (from https://pypi.org/simple/aicsimageio/) (requires-python:>=3.8))
    The user requested aicsimageio==4.9.4
    aicsimageio[all] 4.8.0 depends on aicsimageio 4.8.0 (from https://files.pythonhosted.org/packages/fc/8b/6d8ee9040c1ea53f21e928a4aa6cd3fce198ea8500b4817bc5638f2c5853/aicsimageio-4.8.0-py2.py3-none-any.whl#sha256=e654ef541786d04138c7298dadc46267c64eda87c818132c6a0724acbb8991c3 (from https://pypi.org/simple/aicsimageio/) (requires-python:>=3.8))
    The user requested aicsimageio==4.9.4
    aicsimageio[all] 4.7.0 depends on aicsimageio 4.7.0 (from https://files.pythonhosted.org/packages/e6/e7/0d767fce6fef803831aa5490cabfa6db847c7039bb899ad7ef7847ae60b1/aicsimageio-4.7.0-py2.py3-none-any.whl#sha256=3026b565388bbee07870f08a2e4ebe3c14689c98cd7095ef6e80dcdff0e697c0 (from https://pypi.org/simple/aicsimageio/) (requires-python:>=3.7))
    The user requested aicsimageio==4.9.4
    aicsimageio[all] 4.6.4 depends on aicsimageio 4.6.4 (from https://files.pythonhosted.org/packages/03/10/35ea59573c60bbf6c913c153ee851a02af7daab8909525d3e6a7cfbe7a9e/aicsimageio-4.6.4-py2.py3-none-any.whl#sha256=94270e72b0a178155493a3caf652c0f5f8a5dd70da9b029b47f28697479734e8 (from https://pypi.org/simple/aicsimageio/) (requires-python:>=3.7))
    The user requested aicsimageio==4.9.4
    aicsimageio[all] 4.6.3 depends on aicsimageio 4.6.3 (from https://files.pythonhosted.org/packages/8d/72/c2cfc15de3b6b30f13d3d9158768d496589ebf4dce4e6c6fab3598ae56f0/aicsimageio-4.6.3-py2.py3-none-any.whl#sha256=0e4f9243d6d87b34fa24e8bbbb6cb1010dcc219129bb7183a4b036d084520b23 (from https://pypi.org/simple/aicsimageio/) (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
WARNING: You are using pip version 22.0.4; however, version 23.2.1 is available.
You should consider upgrading via the '/private/var/folders/q5/fvpyppm924525yl9m3xpgjm400031g/T/tmp.Qmuk3mdL/venv/bin/python3 -m pip install --upgrade pip' command.

[multimeric]

Another piece of data: with the legacy resolver, it solves in < 1 minute, having selected aicsimageio==4.9.4 (which is obviously the only option): pip install 'aicsimageio==4.9.4' 'napari-aicsimageio==0.7.2' 'napari==0.4.18' --use-deprecated=legacy-resolver

[notatallshaw]

Does the legacy resolver install a valid environment? I.e. what is the output of pip check after you install?

When there are no valid solutions and a large dependency graph it can take the resolver a long time to prove this. There might be some optimization available, I'll take a look at this specific example, but it might just not be possible to prove there's no solution without checking 1000s of packages and billions of combinations.

The legacy resolver in this scenario installs a broken environment, and so does not need to check all possibilities.

[multimeric]

It doesn't seem to be broken? I get:

$ pip check                                                                                                     
No broken requirements found.

[multimeric]

Even if this environment can't be solved, I would love to help with making the error message more informative. It's been a pain point for me. If we could get it to print out the exact conflict in this case that would be wonderful.

[notatallshaw]

If we could get it to print out the exact conflict in this case that would be wonderful.

Error messages are difficult for dependencies but I'm sure the Pip maintainers would accept PRs for better error messages.

In this case I suspect the issues is to do with the extra (transitive) dependency, which are known to produce not great error messages.

It's also potentially the reason why pip check is passing, as if the pip legacy resolver breaks the extra requirement but not the underlying packages then pip check would pass even if the install was inconsistent with the requirements.

I'll try and reproduce this, and test a few things, after work today when I have some time.

[uranusjr]

pip check is less reliable when you have extras involved, since it does not take them into account. I think the fact the new resolver fails is an indication there is not a valid solution; I would venture to guess the actual relevant factor here is not even the circular dependency, but the complicated overlapping extras instead.

[notatallshaw]

Okay, so I am able to reproduce the ResolutionImpossible, and I am able to reproduce the legacy resolver installs the requirements. Lets looking at these one at a time:

1. There is a bug in the deprecated legacy resolver

One thing you will notice with the logs of the legacy resolver is it never includes aicsimageio[all], which is weird because that's all over your ResolutionImpossible message, it's further weird because it's literally the first dependency listed of napari-aicsimageio==0.7.2: https://github.com/AllenCellModeling/napari-aicsimageio/blob/v0.7.2/pyproject.toml#L48

It appears by aicsimageio==4.9.1 being a top level user requirement the legacy resolver is ignoring/overwriting the transitive dependency aicsimageio[all]. So if we drop aicsimageio from the top level requirements you will notice that more packages get downloaded and it does indeed create a broken environment:

$ pip install 'napari-aicsimageio==0.7.2' 'napari==0.4.18' --use-deprecated=legacy-resolver
Defaulting to user installation because normal site-packages is not writeable
Collecting napari-aicsimageio==0.7.2
  Using cached napari_aicsimageio-0.7.2-py3-none-any.whl (20.6 MB)
Collecting napari==0.4.18
  Using cached napari-0.4.18-py3-none-any.whl (2.6 MB)
Collecting aicsimageio[all]>=4.6.3 (from napari-aicsimageio==0.7.2)
  Using cached aicsimageio-4.11.0-py2.py3-none-any.whl (129 kB)
Collecting fsspec[http]>=2022.7.1 (from napari-aicsimageio==0.7.2)
  Using cached fsspec-2023.6.0-py3-none-any.whl (163 kB)

...

ERROR: pip's legacy dependency resolver does not consider dependency conflicts when selecting packages. This behaviour is the source of the following dependency conflicts.
scipy 1.11.1 requires numpy<1.28.0,>=1.21.6, but you'll have numpy 1.21.5 which is incompatible.
rich 13.5.2 requires pygments<3.0.0,>=2.13.0, but you'll have pygments 2.11.2 which is incompatible.
Successfully installed IPython-8.14.0 Pillow-10.0.0 PyOpenGL-3.1.7 PyWavelets-1.4.1 aicsimageio-4.11.0 aicspylibczi-3.1.2 aiohttp-3.8.5 aiosignal-1.3.1 alabaster-0.7.13 app-model-0.2.0 appdirs-1.4.4 asciitree-0.3.3 asttokens-2.2.1 async-timeout-4.0.2 backcall-0.2.0 bfio-2.3.0 bioformats-jar-2020.5.27 build-0.10.0 cachey-0.2.1 charset-normalizer-3.2.0 cloudpickle-2.2.1 comm-0.1.4 dask-2023.8.0 debugpy-1.6.7 decorator-5.1.1 distributed-2023.8.0 docstring-parser-0.15 docutils-0.17.1 elementpath-4.1.5 entrypoints-0.4 executing-1.2.0 fasteners-0.18 freetype-py-2.4.0 frozenlist-1.4.0 fsspec-2023.6.0 heapdict-1.0.1 hsluv-5.0.3 imagecodecs-2023.7.10 imageio-2.31.1 imagesize-1.4.1 importlib-metadata-6.8.0 in-n-out-0.1.8 ipykernel-6.25.1 ipython-genutils-0.2.0 jedi-0.19.0 jgo-1.0.5 jpype1-1.4.1 jupyter-client-8.3.0 jupyter-core-5.3.1 kiwisolver-1.4.4 lazy-loader-0.3 locket-1.0.0 lxml-4.9.3 magicgui-0.7.2 markdown-it-py-3.0.0 matplotlib-inline-0.1.6 mdurl-0.1.2 mrc-0.3.1 msgpack-1.0.5 multidict-6.0.4 mypy-extensions-1.0.0 napari-0.4.18 napari-aicsimageio-0.7.2 napari-console-0.0.8 napari-plugin-engine-0.2.0 napari-svg-0.1.10 nd2-0.7.1 nest-asyncio-1.5.7 networkx-3.1 npe2-0.7.2 numcodecs-0.11.0 numpydoc-1.5.0 ome-types-0.4.1 ome-zarr-0.8.0 packaging-23.1 pandas-2.0.3 parso-0.8.3 partd-1.4.0 pickleshare-0.7.5 pint-0.22 platformdirs-3.10.0 pooch-1.7.0 prompt-toolkit-3.0.39 psutil-5.9.5 psygnal-0.9.1 pure-eval-0.2.2 pydantic-1.10.12 pyproject_hooks-1.0.0 python-dateutil-2.8.2 pyzmq-25.1.0 qtconsole-5.4.3 qtpy-2.3.1 readlif-0.6.5 resource-backed-dask-array-0.1.0 rich-13.5.2 scikit-image-0.21.0 scipy-1.11.1 scyjava-1.9.1 snowballstemmer-2.2.0 sortedcontainers-2.4.0 sphinx-4.5.0 sphinxcontrib-applehelp-1.0.4 sphinxcontrib-devhelp-1.0.2 sphinxcontrib-htmlhelp-2.0.1 sphinxcontrib-jsmath-1.0.1 sphinxcontrib-qthelp-1.0.3 sphinxcontrib-serializinghtml-1.1.5 stack-data-0.6.2 superqt-0.5.0 tblib-2.0.0 tifffile-2023.7.18 tomli-2.0.1 tomli-w-1.0.0 toolz-0.12.0 tornado-6.3.2 tqdm-4.65.0 traitlets-5.9.0 typer-0.9.0 typing-extensions-4.7.1 tzdata-2023.3 vispy-0.12.2 wcwidth-0.2.6 xarray-2023.1.0 xmlschema-2.4.0 xsdata-23.7 yarl-1.9.2 zarr-2.16.0 zict-3.0.0

While this is a bug I don't imagine this will be fixed by the Pip maintainers

2. The resolver somewhat struggles with extras

The resolver does not understand that foo[extra]==1 implies foo==1, this means that the resolver can waste a lot of time walking dependency trees it shouldn't have to and it's error message can be very confusing.

Fortunately you are not the first person to experience this, this is previously discussed in #11924 and a PR exists to fix this in #12095

While on my computer running with default Pip I still get a ResolutionImpossible in ~1-2 mins, with the branch in #12095 it resolves to the following much cleaner error in seconds:

ERROR: Cannot install aicsimageio[all]==4.9.1 and napari==0.4.18 because these package versions have conflicting dependencies.

The conflict is caused by:
    napari 0.4.18 depends on imageio!=2.22.1 and >=2.20
    aicsimageio[all] 4.9.1 depends on imageio<2.11.0 and >=2.9.0; extra == "all"

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

This is therefore a duplicate of #11924.

[multimeric]

Wow, this is amazing info thank you. If the PR you mention improves the error message and the solving speed then I think it would resolve this issue. Happy to close as a duplicate if appropriate.

[notatallshaw]

Also FYI using the branch from #12095 I was able to quickly produce a working set of requirements (by removing the version constraint on napari and seeing what got installed):

aicsimageio==4.9.1
napari-aicsimageio==0.7.2
napari==0.4.17

[pradyunsg]

I'll consolidate this into #11924. Thanks for that investigation @notatallshaw! ^.^