Improve how dependency resolver order packages to resolve to avoid trying versions not related to an actual conflict

[tiangolo]

Edit from maintainer: this issue is also tracking the subthread started in #9187 (comment) that focuses on get_preference() improvements.

Description

I had conflicting dependencies between a private package package2 and its dependency package1.

When installing package2 with pip, it seems it detects the conflict between package2 and its dependency package1, because it starts the backtracking process.

But then it downloads several versions of other sub-dependencies, instead of erroring out right after noticing the actual unresolvable dependency conflict.

What I expected

I expected it to error out right away after finding the unresolvable conflict between the two fastapi versions. Instead of continuing and trying with many versions of sub-dependencies.

Example

Here's a minimal, self-contained, reproducible example:

Inside some project directory, create a venv, e.g.:

$ python3.7 -m venv .env3.7

Activate the venv:

$ source ./.env3.7/bin/activate

Upgrade pip:

$ python -m pip install --upgrade pip

--->100%
Successfully installed pip-20.3.3

Install wheel:

$ pip install --upgrade wheel

--->100%
Successfully installed wheel-0.36.2

Then, create a first package package1, by creating a file:

./package1/setup.py

with:

from setuptools import setup, find_packages

setup(
    name="package1",
    version="0.0.1",
    packages=find_packages(),
    install_requires=[
        "fastapi>=0.61.0,<0.62.0",
    ],
)

Then create another package package2, that depends on package1, creating a file:

./package2/setup.py

with:

from setuptools import setup, find_packages

setup(
    name="package2",
    version="0.0.2",
    packages=find_packages(),
    install_requires=[
        "fastapi>=0.60.0,<0.61.0",  # <-- Notice the unresolvable conflict with fastapi
        "package1",                 # <-- Notice it depends on package1
    ],
)

The current file tree looks like this:

.
├── package1
│   └── setup.py
└── package2
    └── setup.py

Now, go to ./package1/ and build the wheel for that package (so that it can be used while installing package2):

$ cd ./package1/

$ python setup.py sdist bdist_wheel

running sdist
...
...
removing build/bdist.linux-x86_64/wheel

Now go to ./package2/ and try to install it with pip, pointing to the dependency package1 wheel directory:

$ pip install -f ../package1/dist/ .

Looking in links: ../package1/dist/
Processing /home/user/code/debugdeps/package2
Collecting fastapi<0.61.0,>=0.60.0
  Using cached fastapi-0.60.2-py3-none-any.whl (50 kB)
Collecting starlette==0.13.6
  Using cached starlette-0.13.6-py3-none-any.whl (59 kB)
Collecting pydantic<2.0.0,>=0.32.2
  Using cached pydantic-1.7.3-cp37-cp37m-manylinux2014_x86_64.whl (9.1 MB)
Processing /home/user/code/debugdeps/package1/dist/package1-0.0.1-py3-none-any.whl
INFO: pip is looking at multiple versions of pydantic to determine which version is compatible with other requirements. This could take a while.
Collecting pydantic<2.0.0,>=0.32.2
  Using cached pydantic-1.7.2-cp37-cp37m-manylinux2014_x86_64.whl (9.1 MB)
  Using cached pydantic-1.7.1-cp37-cp37m-manylinux2014_x86_64.whl (9.1 MB)
  Using cached pydantic-1.7-cp37-cp37m-manylinux2014_x86_64.whl (9.1 MB)
  Using cached pydantic-1.6.1-cp37-cp37m-manylinux2014_x86_64.whl (8.6 MB)
  Using cached pydantic-1.6-cp37-cp37m-manylinux2014_x86_64.whl (8.6 MB)
  Using cached pydantic-1.5.1-cp37-cp37m-manylinux2014_x86_64.whl (7.3 MB)
  Using cached pydantic-1.5-cp37-cp37m-manylinux2014_x86_64.whl (7.3 MB)
INFO: pip is looking at multiple versions of pydantic to determine which version is compatible with other requirements. This could take a while.
  Using cached pydantic-1.4-cp37-cp37m-manylinux2010_x86_64.whl (7.5 MB)
  Using cached pydantic-1.3-cp37-cp37m-manylinux2010_x86_64.whl (7.3 MB)
  Using cached pydantic-1.2-cp37-cp37m-manylinux2010_x86_64.whl (7.1 MB)
  Using cached pydantic-1.1.1-cp37-cp37m-manylinux2010_x86_64.whl (6.9 MB)
  Using cached pydantic-1.1-cp37-cp37m-manylinux1_x86_64.whl (6.3 MB)
INFO: This is taking longer than usual. You might need to provide the dependency resolver with stricter constraints to reduce runtime. If you want to abort this run, you can press Ctrl + C to do so. To improve how pip performs, tell us what happened here: https://pip.pypa.io/surveys/backtracking
  Using cached pydantic-1.0-cp37-cp37m-manylinux1_x86_64.whl (5.7 MB)
  Using cached pydantic-0.32.2-cp37-cp37m-manylinux1_x86_64.whl (5.0 MB)
INFO: pip is looking at multiple versions of starlette to determine which version is compatible with other requirements. This could take a while.
INFO: pip is looking at multiple versions of <Python from Requires-Python> to determine which version is compatible with other requirements. This could take a while.
INFO: pip is looking at multiple versions of fastapi to determine which version is compatible with other requirements. This could take a while.
Collecting fastapi<0.61.0,>=0.60.0
  Using cached fastapi-0.60.1-py3-none-any.whl (49 kB)
  Using cached fastapi-0.60.0-py3-none-any.whl (49 kB)
Collecting starlette==0.13.4
  Using cached starlette-0.13.4-py3-none-any.whl (59 kB)
INFO: pip is looking at multiple versions of package2 to determine which version is compatible with other requirements. This could take a while.
ERROR: Cannot install package2 and package2==0.0.2 because these package versions have conflicting dependencies.

The conflict is caused by:
    package2 0.0.2 depends on fastapi<0.61.0 and >=0.60.0
    package1 0.0.1 depends on fastapi<0.62.0 and >=0.61.0

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

The final error output is perfect, it shows the conflict between fastapi versions.

🚨 What is not right, is that it first downloads several versions of pydantic, despite already having enough information to know it won't be able to solve the fastapi conflict.

After fixing the fastapi conflict, it no longer tries to download many versions of Pydantic. But I would think it wouldn't be necessary to download many versions of one dependency to realize a conflict in another one.

Making it worse

I would think the above are the minimum steps to reproduce the problem. Although in the case above it's not that terrible, as it will take some seconds/minutes to download all the Pydantic versions and then error out the conflict in fastapi.

But it gets worse when there are other dependencies. Even non-conflicting dependencies. Because the resolver will download many versions of those dependencies and their sub-dependencies before showing the conflict.

And by downloading many unnecessary versions of many dependencies, it can take a really long time.

And in some cases, even error out something else, completely unrelated to the actual conflict, after not being able to build a very old version of some sub-dependency (this specific point behaves differently in pip installed from master, more on that in the end).

To see it in the example above, modify the file:

./package2/setup.py

To include:

alembic>=1.4.3,<1.5.0

So it would now be:

from setuptools import setup, find_packages

setup(
    name="package2",
    version="0.0.2",
    packages=find_packages(),
    install_requires=[
        "fastapi>=0.60.0,<0.61.0",  # <-- Notice the unresolvable conflict with fastapi
        "package1",                 # <-- Notice it depends on package1
        "alembic>=1.4.3,<1.5.0",
    ],
)

And then try again to install it:

pip install -f ../package1/dist/ .

In this very simple example, in my computer that already has all those packages in cache (so not even counting download time), it takes 1m49s.

And the error is not related to the actual dependency conflict, but actually about not being able to build an old version of some dependency down the dependency tree:

Collecting Mako
  Using cached Mako-0.3.4.tar.gz (275 kB)
  Using cached Mako-0.3.3.tar.gz (272 kB)
  Using cached Mako-0.3.2.tar.gz (242 kB)
  Using cached Mako-0.3.1.tar.gz (242 kB)
  Using cached Mako-0.3.0.tar.gz (242 kB)
  Using cached Mako-0.2.5.tar.gz (228 kB)
    ERROR: Command errored out with exit status 1:
     command: /home/user/code/debugdeps/.env3.7/bin/python3.7 -c 'import sys, setuptools, tokenize; sys.argv[0] = '"'"'/tmp/pip-install-eu804_lk/mako_691c613f9a1c4dedb342df3544c2a03e/setup.py'"'"'; __file__='"'"'/tmp/pip-install-eu804_lk/mako_691c613f9a1c4dedb342df3544c2a03e/setup.py'"'"';f=getattr(tokenize, '"'"'open'"'"', open)(__file__);code=f.read().replace('"'"'\r\n'"'"', '"'"'\n'"'"');f.close();exec(compile(code, __file__, '"'"'exec'"'"'))' egg_info --egg-base /tmp/pip-pip-egg-info-wcc8z1p4
         cwd: /tmp/pip-install-eu804_lk/mako_691c613f9a1c4dedb342df3544c2a03e/
    Complete output (5 lines):
    Traceback (most recent call last):
      File "<string>", line 1, in <module>
      File "/tmp/pip-install-eu804_lk/mako_691c613f9a1c4dedb342df3544c2a03e/setup.py", line 5, in <module>
        v = file(os.path.join(os.path.dirname(__file__), 'lib', 'mako', '__init__.py'))
    NameError: name 'file' is not defined
    ----------------------------------------
ERROR: Command errored out with exit status 1: python setup.py egg_info Check the logs for full command output.

Output

Here's the very long output if you want to check it:

Looking in links: ../package1/dist/
Processing /home/user/code/debugdeps/package2
Collecting alembic<1.5.0,>=1.4.3
  Using cached alembic-1.4.3-py2.py3-none-any.whl (159 kB)
Collecting fastapi<0.61.0,>=0.60.0
  Using cached fastapi-0.60.2-py3-none-any.whl (50 kB)
Collecting starlette==0.13.6
  Using cached starlette-0.13.6-py3-none-any.whl (59 kB)
Collecting pydantic<2.0.0,>=0.32.2
  Using cached pydantic-1.7.3-cp37-cp37m-manylinux2014_x86_64.whl (9.1 MB)
Collecting python-editor>=0.3
  Using cached python_editor-1.0.4-py3-none-any.whl (4.9 kB)
Collecting SQLAlchemy>=1.1.0
  Using cached SQLAlchemy-1.3.22-cp37-cp37m-manylinux2010_x86_64.whl (1.3 MB)
Collecting Mako
  Using cached Mako-1.1.3-py2.py3-none-any.whl (75 kB)
Collecting MarkupSafe>=0.9.2
  Using cached MarkupSafe-1.1.1-cp37-cp37m-manylinux1_x86_64.whl (27 kB)
Processing /home/user/code/debugdeps/package1/dist/package1-0.0.1-py3-none-any.whl
INFO: pip is looking at multiple versions of markupsafe to determine which version is compatible with other requirements. This could take a while.
Collecting MarkupSafe>=0.9.2
  Using cached MarkupSafe-1.1.0-cp37-cp37m-manylinux1_x86_64.whl (27 kB)
  Using cached MarkupSafe-1.0.tar.gz (14 kB)
  Using cached MarkupSafe-0.23.tar.gz (13 kB)
  Using cached MarkupSafe-0.22.tar.gz (13 kB)
  Using cached MarkupSafe-0.21.tar.gz (13 kB)
  Using cached MarkupSafe-0.20.tar.gz (11 kB)
  Using cached MarkupSafe-0.19.tar.gz (11 kB)
INFO: pip is looking at multiple versions of markupsafe to determine which version is compatible with other requirements. This could take a while.
  Using cached MarkupSafe-0.18.tar.gz (11 kB)
  Using cached MarkupSafe-0.17.tar.gz (11 kB)
  Using cached MarkupSafe-0.16.tar.gz (11 kB)
  Using cached MarkupSafe-0.15.tar.gz (11 kB)
  Using cached MarkupSafe-0.14.tar.gz (11 kB)
INFO: This is taking longer than usual. You might need to provide the dependency resolver with stricter constraints to reduce runtime. If you want to abort this run, you can press Ctrl + C to do so. To improve how pip performs, tell us what happened here: https://pip.pypa.io/surveys/backtracking
  Using cached MarkupSafe-0.13.tar.gz (11 kB)
  Using cached MarkupSafe-0.12.tar.gz (10 kB)
  Using cached MarkupSafe-0.11.tar.gz (10 kB)
  Using cached MarkupSafe-0.9.3.tar.gz (10 kB)
  Using cached MarkupSafe-0.9.2.tar.gz (10 kB)
INFO: pip is looking at multiple versions of mako to determine which version is compatible with other requirements. This could take a while.
Collecting Mako
  Using cached Mako-1.1.2-py2.py3-none-any.whl (75 kB)
  Using cached Mako-1.1.1.tar.gz (468 kB)
  Using cached Mako-1.1.0.tar.gz (463 kB)
  Using cached Mako-1.0.14.tar.gz (462 kB)
  Using cached Mako-1.0.13.tar.gz (460 kB)
  Using cached Mako-1.0.12.tar.gz (460 kB)
  Using cached Mako-1.0.11.tar.gz (461 kB)
INFO: pip is looking at multiple versions of mako to determine which version is compatible with other requirements. This could take a while.
  Using cached Mako-1.0.10.tar.gz (460 kB)
  Using cached Mako-1.0.9.tar.gz (459 kB)
  Using cached Mako-1.0.8.tar.gz (468 kB)
  Using cached Mako-1.0.7.tar.gz (564 kB)
  Using cached Mako-1.0.6.tar.gz (575 kB)
INFO: This is taking longer than usual. You might need to provide the dependency resolver with stricter constraints to reduce runtime. If you want to abort this run, you can press Ctrl + C to do so. To improve how pip performs, tell us what happened here: https://pip.pypa.io/surveys/backtracking
  Using cached Mako-1.0.5.tar.gz (574 kB)
  Using cached Mako-1.0.4.tar.gz (574 kB)
  Using cached Mako-1.0.3.tar.gz (565 kB)
  Using cached Mako-1.0.2.tar.gz (564 kB)
  Using cached Mako-1.0.1.tar.gz (473 kB)
  Using cached Mako-1.0.0.tar.gz (470 kB)
  Using cached Mako-0.9.1.tar.gz (421 kB)
  Using cached Mako-0.9.0.tar.gz (420 kB)
  Using cached Mako-0.8.1.tar.gz (407 kB)
  Using cached Mako-0.8.0.tar.gz (407 kB)
  Using cached Mako-0.7.3.tar.gz (401 kB)
  Using cached Mako-0.7.2.tar.gz (401 kB)
  Using cached Mako-0.7.1.tar.gz (400 kB)
  Using cached Mako-0.7.0.tar.gz (398 kB)
  Using cached Mako-0.6.2.tar.gz (384 kB)
  Using cached Mako-0.6.1.tar.gz (384 kB)
  Using cached Mako-0.6.0.tar.gz (384 kB)
  Using cached Mako-0.5.0.tar.gz (318 kB)
  Using cached Mako-0.4.2.tar.gz (317 kB)
  Using cached Mako-0.4.1.tar.gz (317 kB)
  Using cached Mako-0.4.0.tar.gz (300 kB)
  Using cached Mako-0.3.6.tar.gz (297 kB)
  Using cached Mako-0.3.5.tar.gz (276 kB)
Collecting Beaker>=1.1
  Using cached Beaker-1.11.0.tar.gz (40 kB)
INFO: pip is looking at multiple versions of beaker to determine which version is compatible with other requirements. This could take a while.
  Using cached Beaker-1.10.1.tar.gz (40 kB)
  Using cached Beaker-1.10.0.tar.gz (41 kB)
  Using cached Beaker-1.9.1.tar.gz (40 kB)
  Using cached Beaker-1.9.0.tar.gz (39 kB)
  Using cached Beaker-1.8.1.tar.gz (37 kB)
  Using cached Beaker-1.8.0.tar.gz (36 kB)
  Using cached Beaker-1.7.0.tar.gz (34 kB)
INFO: pip is looking at multiple versions of beaker to determine which version is compatible with other requirements. This could take a while.
  Using cached Beaker-1.6.5.post1.tar.gz (36 kB)
  Using cached Beaker-1.6.4.tar.gz (54 kB)
  Using cached Beaker-1.6.3.tar.gz (52 kB)
  Using cached Beaker-1.6.2.tar.gz (52 kB)
  Using cached Beaker-1.6.1.tar.gz (51 kB)
INFO: This is taking longer than usual. You might need to provide the dependency resolver with stricter constraints to reduce runtime. If you want to abort this run, you can press Ctrl + C to do so. To improve how pip performs, tell us what happened here: https://pip.pypa.io/surveys/backtracking
  Using cached Beaker-1.6.tar.gz (51 kB)
  Using cached Beaker-1.5.4.tar.gz (46 kB)
  Using cached Beaker-1.5.3.tar.gz (46 kB)
  Using cached Beaker-1.5.2.tar.gz (45 kB)
  Using cached Beaker-1.5.1.tar.gz (45 kB)
  Using cached Beaker-1.5.tar.gz (45 kB)
  Using cached Beaker-1.4.2.tar.gz (45 kB)
  Using cached Beaker-1.4.1.tar.gz (44 kB)
  Using cached Beaker-1.4.tar.gz (43 kB)
  Using cached Beaker-1.3.1.tar.gz (41 kB)
  Using cached Beaker-1.3.tar.gz (41 kB)
  Using cached Beaker-1.2.3.tar.gz (38 kB)
  Using cached Beaker-1.2.2.tar.gz (38 kB)
  Using cached Beaker-1.2.1.tar.gz (38 kB)
  Using cached Beaker-1.2.tar.gz (38 kB)
  Using cached Beaker-1.1.3.tar.gz (37 kB)
  Using cached Beaker-1.1.2.tar.gz (36 kB)
  Using cached Beaker-1.1.1.tar.gz (35 kB)
  Using cached Beaker-1.1.tar.gz (35 kB)
Collecting Mako
  Using cached Mako-0.3.4.tar.gz (275 kB)
  Using cached Mako-0.3.3.tar.gz (272 kB)
  Using cached Mako-0.3.2.tar.gz (242 kB)
  Using cached Mako-0.3.1.tar.gz (242 kB)
  Using cached Mako-0.3.0.tar.gz (242 kB)
  Using cached Mako-0.2.5.tar.gz (228 kB)
    ERROR: Command errored out with exit status 1:
     command: /home/user/code/debugdeps/.env3.7/bin/python3.7 -c 'import sys, setuptools, tokenize; sys.argv[0] = '"'"'/tmp/pip-install-unckp7wk/mako_826db1a2e8764498a609cab88518ebd5/setup.py'"'"'; __file__='"'"'/tmp/pip-install-unckp7wk/mako_826db1a2e8764498a609cab88518ebd5/setup.py'"'"';f=getattr(tokenize, '"'"'open'"'"', open)(__file__);code=f.read().replace('"'"'\r\n'"'"', '"'"'\n'"'"');f.close();exec(compile(code, __file__, '"'"'exec'"'"'))' egg_info --egg-base /tmp/pip-pip-egg-info-ne79o3_k
         cwd: /tmp/pip-install-unckp7wk/mako_826db1a2e8764498a609cab88518ebd5/
    Complete output (5 lines):
    Traceback (most recent call last):
      File "<string>", line 1, in <module>
      File "/tmp/pip-install-unckp7wk/mako_826db1a2e8764498a609cab88518ebd5/setup.py", line 5, in <module>
        v = file(os.path.join(os.path.dirname(__file__), 'lib', 'mako', '__init__.py'))
    NameError: name 'file' is not defined
    ----------------------------------------
ERROR: Command errored out with exit status 1: python setup.py egg_info Check the logs for full command output.

Additional information

I also tried upgrading setuptools, but then I got another unrelated error from one of the sub-dependencies that was trying to import a deprecated module/object from it. So I removed that part to avoid more confusion.

These are the packages I have in my environment:

$ pip list

Package    Version
---------- -------
pip        20.3.3
setuptools 41.2.0
wheel      0.36.2

---

I also tried installing pip from master with:

$ python -m pip install -U "pip @ https://github.com/pypa/pip/archive/master.zip"

And then after that, it still downloads all those versions, shows the same error as above, and continues downloading. So, the final error is not as strange, but it takes even longer (it's still running after more than 10m).

[uranusjr]

Thanks for the detailed report! The issue here is logically similar to what is described here (read the discussion started from the linked comment; messages prior are about the “resolver is slow” issue in a broader sense). Quoting myself from the discussion:

The resolver currently has a special treatment of “top-level” requirements (i.e. what you specify from the command line, including -r) and resolve those first. But when you put those into a setup.py, the requirements become transitive and only one top-level requirement is registered.

I’ve been trying to avoid the discussion since it’s difficult to do, but maybe we really should order transitive dependencies by their “depth” as well. This makes sense intuitively since the deeper a dependency is at, the looser it should generally be less likely to require excessive backtracking.

As I mentioned in the same issue, there are various strategies being experiemented on to improve the logic, and this is definitely a valuable example to observe. If only I can find more energy to actually come up with an implementatio…

[tiangolo]

Thanks for the speedy response @uranusjr ! 🙇

I'm sorry I ended up creating a duplicate, I swear I searched all the resolver issues before posting this, but I didn't notice it was related to that one. 😅 🤦

Feel free to close this one if it doesn't add anything useful and/or you prefer to track it on the other one.

[uranusjr]

It’s perfectly fine! That thread grew way too long for anyone not following the issue tracker intimately to reasonably read. It’s also unfortunate the discussion is buried so low in the thread. I’ll use this one to track the resolution priority logic improvement specifically.