pip: Improving failures at `ResolutionTooDeep` to include more context

Description

Example of pip backtracking failure

Repo for this example

… can be found there: https://github.com/vjmp/pipbacktracking and issues can be found there: https://github.com/pypa/pip/issues

Failing case description

Installing (internally conflicting) “requirements.txt” which has lots of transient dependencies, with simple command like pip install -r requirements.txt with “very simple” looking content of “requirements.txt” looking like:

pywebview[qt]==3.6.2
rpaframework==15.6.0

This will take long time to fail, like 4+ hours.

And note that this specific example applies only on Linux environments. But I think problem is general, and “old, previously working” requirement sets can get “rotten” over time, as dependency “future” takes “wrong” turn. This is because resolver works from latest to oldest, and even one few versions of some required dependencies can derail resolver into backtracking “mode”.

Context of our problem space.

Here are some things, that make this problem to Robocorp customers.

machines executing “pip install” can be fast or slow (or very slow)
pip version can be anything old or new (backward compatible generic usage)
pip environment setup time is “billable” time, so “fail fast” is cheaper in monetary terms than “fail 4+ hours later on total environment build failure”
automation is setting up environment, not humans
our tooling for automation in our rcc which is used here to also make this failure as repeatable process
and general context for automation is RPA (robotic process automation) so processes should be repeatable and reliable and not break, even if time passes

Problem with backtracking

It is very slow to fail.

Currently happy path works (fast enough), but if you derail resolver to unbeaten path, then resolution takes long time, because in pip source https://github.com/pypa/pip/blob/main/src/pip/_internal/resolution/resolvelib/resolver.py#L91 there is magical internal variable try_to_avoid_resolution_too_deep = 2000000 which causes very long search until it fails.

Brute force search for possibly huge search space.

When package, like rpaframework below, has something around 100 dependencies it its dependency tree, even happy path resolution takes 100+ rounds of pip dependency resolution to find it. When backtracking, (just one) processor becomes 100% busy for backtracking work.

In automation, there is no “human” to press “Control-C”.

INFO: pip is looking at multiple versions of selenium to determine which version is compatible with other requirements. This could take a while.

and …

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.

… are nice for pip to inform user that it is taking longer than usual, but in our customers automation cases, there is nobody who could see those, or to press that “Ctrl + C”.

This could be improved, if there would be environment variable like MAX_PIP_RESOLUTION_ROUNDS instead of having hard coded 2000000 internal limit. Also adding this as environment variable (instead of command line option is better backwards compatibility, since “extra” environment variable does not kill old pip version commands, but CLI option will).

Basic setup

What is needed:

a linux machine
content of repo containing this README.md file
rcc executable (optional, but useful, and if you have it, you don’t have to manually install following two things …)
python3, in our case we have tested 3.9.13
pip, in our case we have tested 22.1.2 (but mostly anything after 20.3 has this feature; this current example uses pip v22.2.2)

Example code

You need rcc to run these examples. Or do manual environment setup if you will.

You can download rcc binaries from https://downloads.robocorp.com/rcc/releases/index.html or if you want to more information, see https://github.com/robocorp/rcc

Success case (just for reference)

To run success case as what normal user sees, use this:

rcc run --task pass

And to see debugging output, use this:

rcc run --dev --task pass

Actual failure case (point of this demo)

To run failing case as what normal user sees, use this … and have patience to wait:

rcc run --task fail

And to see debugging output, use this … and have patience to wait:

rcc run --dev --task fail

Expected behavior

Faster (and configurable) failure on pip install on complex/big dependency tree.

pip version

22.2.2

Python version

3.9.13

OS

Linux

How to Reproduce

Clone repository from: https://github.com/vjmp/pipbacktracking
Download rcc from: https://downloads.robocorp.com/rcc/releases/index.html
Make it executable and note location
Change to “pipbacktracking” repo directory, and run command /path/to/rcc run --task fail

Note: no need to install specific python or pip versions, if you use these instructions.

Output

$ git clone https://github.com/vjmp/pipbacktracking
... your normal "git" output (not interesting)
$ cd pipbacktracking
$ curl -o bin/rcc https://downloads.robocorp.com/rcc/releases/v11.27.3/linux64/rcc
... your normal  curl output (not interesting)
$ chmod 755 bin/rcc
$ bin/rcc run --task fail
"/home/user/tmp/redo/pipbacktracking/robot.yaml" as robot.yaml is:
tasks:
  pass:
    shell: user_flow.sh pass
  fail:
    shell: user_flow.sh fail

devTasks:
  pass:
    shell: debug_flow.sh pass
  fail:
    shell: debug_flow.sh fail

condaConfigFile: conda.yaml
artifactsDir: temp
PATH:
  - bin
PYTHONPATH:
ignoreFiles:
  - .gitignore

####  Progress: 01/13  v11.27.3     0.009s  Fresh [private mode] holotree environment 66eec3ee-3650-220e-41fa-1b2f1f5e07c0.
####  Progress: 02/13  v11.27.3     0.001s  Holotree blueprint is "48b3e3ef4c244a3e" [linux_amd64].
####  Progress: 12/13  v11.27.3     0.294s  Restore space from library [with 7 workers].
Installation plan is: /home/user/.robocorp/holotree/59acff1_5a1fac3_9fcd2534/rcc_plan.log
Environment configuration descriptor is: /home/user/.robocorp/holotree/59acff1_5a1fac3_9fcd2534/identity.yaml
####  Progress: 13/13  v11.27.3     0.206s  Fresh holotree done [with 7 workers].
Wanted  Version  Origin  |  No.  |  Available         Version    Origin       |  Status
------  -------  ------  +  ---  +  ---------         -------    ------       +  ------
-       -        -       |    1  |  _libgcc_mutex     0.1        conda-forge  |  N/A
-       -        -       |    2  |  _openmp_mutex     4.5        conda-forge  |  N/A
-       -        -       |    3  |  bzip2             1.0.8      conda-forge  |  N/A
-       -        -       |    4  |  ca-certificates   2022.9.24  conda-forge  |  N/A
-       -        -       |    5  |  ld_impl_linux-64  2.36.1     conda-forge  |  N/A
-       -        -       |    6  |  libffi            3.4.2      conda-forge  |  N/A
-       -        -       |    7  |  libgcc-ng         12.1.0     conda-forge  |  N/A
-       -        -       |    8  |  libgomp           12.1.0     conda-forge  |  N/A
-       -        -       |    9  |  libnsl            2.0.0      conda-forge  |  N/A
-       -        -       |   10  |  libsqlite         3.39.3     conda-forge  |  N/A
-       -        -       |   11  |  libuuid           2.32.1     conda-forge  |  N/A
-       -        -       |   12  |  libzlib           1.2.12     conda-forge  |  N/A
-       -        -       |   13  |  ncurses           6.3        conda-forge  |  N/A
-       -        -       |   14  |  openssl           3.0.5      conda-forge  |  N/A
-       -        -       |   15  |  pip               22.2.2     conda-forge  |  N/A
-       -        -       |   16  |  python            3.9.13     conda-forge  |  N/A
-       -        -       |   17  |  readline          8.1.2      conda-forge  |  N/A
-       -        -       |   18  |  setuptools        65.4.0     conda-forge  |  N/A
-       -        -       |   19  |  sqlite            3.39.3     conda-forge  |  N/A
-       -        -       |   20  |  tk                8.6.12     conda-forge  |  N/A
-       -        -       |   21  |  tzdata            2022d      conda-forge  |  N/A
-       -        -       |   22  |  wheel             0.37.1     conda-forge  |  N/A
-       -        -       |   23  |  xz                5.2.6      conda-forge  |  N/A
------  -------  ------  +  ---  +  ---------         -------    ------       +  ------
Wanted  Version  Origin  |  No.  |  Available         Version    Origin       |  Status

--
+ pip install -r requirements_fail.txt
Collecting pywebview[qt]==3.6.2
  Using cached pywebview-3.6.2-py3-none-any.whl (351 kB)
Collecting rpaframework==15.6.0
  Using cached rpaframework-15.6.0-py3-none-any.whl (534 kB)
Collecting proxy-tools
  Using cached proxy_tools-0.1.0-py3-none-any.whl
Collecting PyQt5
  Using cached PyQt5-5.15.7-cp37-abi3-manylinux1_x86_64.whl (8.4 MB)
Collecting pyqtwebengine
  Using cached PyQtWebEngine-5.15.6-cp37-abi3-manylinux1_x86_64.whl (230 kB)
Collecting QtPy
  Using cached QtPy-2.2.0-py3-none-any.whl (82 kB)
Collecting PySocks!=1.5.7,<2.0.0,>=1.5.6
  Using cached PySocks-1.7.1-py3-none-any.whl (16 kB)
Collecting netsuitesdk<2.0.0,>=1.1.0
  Using cached netsuitesdk-1.24.0-py3-none-any.whl (31 kB)
Collecting python-xlib>=0.17
  Using cached python_xlib-0.31-py2.py3-none-any.whl (179 kB)
Collecting xlwt<2.0.0,>=1.3.0
  Using cached xlwt-1.3.0-py2.py3-none-any.whl (99 kB)
Collecting docutils
  Using cached docutils-0.19-py3-none-any.whl (570 kB)
Collecting pillow<10.0.0,>=9.1.1
  Using cached Pillow-9.2.0-cp39-cp39-manylinux_2_28_x86_64.whl (3.2 MB)
Collecting openpyxl<4.0.0,>=3.0.9
  Using cached openpyxl-3.0.10-py2.py3-none-any.whl (242 kB)
Collecting htmldocx<0.0.7,>=0.0.6
  Using cached htmldocx-0.0.6-py3-none-any.whl (9.5 kB)
Collecting graphviz<0.14.0,>=0.13.2
  Using cached graphviz-0.13.2-py2.py3-none-any.whl (17 kB)
Collecting exchangelib<5.0.0,>=4.5.1
  Using cached exchangelib-4.7.6-py2.py3-none-any.whl (236 kB)
Collecting xlutils<3.0.0,>=2.0.0
  Using cached xlutils-2.0.0-py2.py3-none-any.whl (55 kB)
Collecting click<9.0.0,>=8.1.2
  Using cached click-8.1.3-py3-none-any.whl (96 kB)
Collecting chardet<4.0.0,>=3.0.0
  Using cached chardet-3.0.4-py2.py3-none-any.whl (133 kB)
Collecting java-access-bridge-wrapper<0.10.0,>=0.9.4
  Using cached java_access_bridge_wrapper-0.9.5-py3-none-any.whl (28 kB)
Collecting pyperclip<2.0.0,>=1.8.0
  Using cached pyperclip-1.8.2-py3-none-any.whl
Collecting tzlocal<3.0,>=2.1
  Using cached tzlocal-2.1-py2.py3-none-any.whl (16 kB)
Collecting xlrd<3.0.0,>=2.0.1
  Using cached xlrd-2.0.1-py2.py3-none-any.whl (96 kB)
Collecting rpaframework-pdf<5.0.0,>=4.1.0
  Using cached rpaframework_pdf-4.1.0-py3-none-any.whl (609 kB)
Collecting PyYAML<6.0.0,>=5.4.1
  Using cached PyYAML-5.4.1-cp39-cp39-manylinux1_x86_64.whl (630 kB)
Collecting hubspot-api-client<5.0.0,>=4.0.6
  Using cached hubspot_api_client-4.0.6-py3-none-any.whl (1.9 MB)
Collecting robotframework-requests<0.10.0,>=0.9.1
  Using cached robotframework_requests-0.9.3-py3-none-any.whl (21 kB)
Collecting robotframework-seleniumtestability<2.0.0,>=1.1.0
  Using cached robotframework_seleniumtestability-1.1.0-py2.py3-none-any.whl
Collecting robotframework!=4.0.1,<6.0.0,>=4.0.0
  Using cached robotframework-5.0.1-py3-none-any.whl (639 kB)
Collecting notifiers<2.0.0,>=1.2.1
  Using cached notifiers-1.3.3-py3-none-any.whl (43 kB)
Collecting jsonpath-ng<2.0.0,>=1.5.2
  Using cached jsonpath_ng-1.5.3-py3-none-any.whl (29 kB)
Collecting rpaframework-core<10.0.0,>=9.1.0
  Using cached rpaframework_core-9.1.0-py3-none-any.whl (38 kB)
Collecting pynput-robocorp-fork<5.0.0,>=4.0.0
  Using cached pynput_robocorp_fork-4.0.0-py2.py3-none-any.whl (94 kB)
Collecting tweepy<4.0.0,>=3.8.0
  Using cached tweepy-3.10.0-py2.py3-none-any.whl (30 kB)
Collecting simple_salesforce<2.0.0,>=1.0.0
  Using cached simple_salesforce-1.12.2-py2.py3-none-any.whl (120 kB)
Collecting mss<7.0.0,>=6.0.0
  Using cached mss-6.1.0-py3-none-any.whl (76 kB)
Collecting robotframework-pythonlibcore<4.0.0,>=3.0.0
  Using cached robotframework_pythonlibcore-3.0.0-py2.py3-none-any.whl (9.9 kB)
Collecting rpaframework-dialogs<4.0.0,>=3.0.0
  Using cached rpaframework_dialogs-3.0.1-py3-none-any.whl (18 kB)
Collecting cryptography<4.0.0,>=3.3.1
  Using cached cryptography-3.4.8-cp36-abi3-manylinux_2_24_x86_64.whl (3.0 MB)
Collecting tenacity<9.0.0,>=8.0.1
  Using cached tenacity-8.1.0-py3-none-any.whl (23 kB)
Collecting robotframework-seleniumlibrary<6.0.0,>=5.1.0
  Using cached robotframework_seleniumlibrary-5.1.3-py2.py3-none-any.whl (94 kB)
Collecting selenium<4.0.0,>=3.141.0
  Using cached selenium-3.141.0-py2.py3-none-any.whl (904 kB)
Collecting cffi>=1.12
  Using cached cffi-1.15.1-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (441 kB)
Collecting requests-ntlm>=0.2.0
  Using cached requests_ntlm-1.1.0-py2.py3-none-any.whl (5.7 kB)
Collecting cached-property
  Using cached cached_property-1.5.2-py2.py3-none-any.whl (7.6 kB)
Collecting pygments
  Using cached Pygments-2.13.0-py3-none-any.whl (1.1 MB)
Collecting defusedxml>=0.6.0
  Using cached defusedxml-0.7.1-py2.py3-none-any.whl (25 kB)
Collecting requests>=2.7
  Using cached requests-2.28.1-py3-none-any.whl (62 kB)
Collecting oauthlib
  Using cached oauthlib-3.2.1-py3-none-any.whl (151 kB)
Collecting lxml>3.0
  Using cached lxml-4.9.1-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.manylinux_2_24_x86_64.whl (7.0 MB)
Collecting requests-oauthlib
  Using cached requests_oauthlib-1.3.1-py2.py3-none-any.whl (23 kB)
Collecting tzdata
  Using cached tzdata-2022.4-py2.py3-none-any.whl (336 kB)
Collecting dnspython>=2.0.0
  Using cached dnspython-2.2.1-py3-none-any.whl (269 kB)
Collecting isodate
  Using cached isodate-0.6.1-py2.py3-none-any.whl (41 kB)
Collecting python-docx>=0.8.10
  Using cached python_docx-0.8.11-py3-none-any.whl
Collecting beautifulsoup4>=4.7.0
  Using cached beautifulsoup4-4.11.1-py3-none-any.whl (128 kB)
Collecting certifi
  Using cached certifi-2022.9.24-py3-none-any.whl (161 kB)
Collecting python-dateutil
  Using cached python_dateutil-2.8.2-py2.py3-none-any.whl (247 kB)
Collecting urllib3>=1.15
  Using cached urllib3-1.26.12-py2.py3-none-any.whl (140 kB)
Collecting six>=1.10
  Using cached six-1.16.0-py2.py3-none-any.whl (11 kB)
Collecting decorator
  Using cached decorator-5.1.1-py3-none-any.whl (9.1 kB)
Collecting ply
  Using cached ply-3.11-py2.py3-none-any.whl (49 kB)
Collecting zeep
  Using cached zeep-4.1.0-py2.py3-none-any.whl (100 kB)
Collecting jsonschema<5.0.0,>=4.4.0
  Using cached jsonschema-4.16.0-py3-none-any.whl (83 kB)
Collecting et-xmlfile
  Using cached et_xmlfile-1.1.0-py3-none-any.whl (4.7 kB)
Collecting furl
  Using cached furl-2.1.3-py2.py3-none-any.whl (20 kB)
Collecting wrapt
  Using cached wrapt-1.14.1-cp39-cp39-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl (77 kB)
Collecting webdrivermanager<0.11.0,>=0.10.0
  Using cached webdrivermanager-0.10.0-py2.py3-none-any.whl
Collecting robocorp-dialog<0.6.0,>=0.5.3
  Using cached robocorp_dialog-0.5.3-py3-none-any.whl (22.2 MB)
Collecting fpdf2<3.0.0,>=2.5.2
  Using cached fpdf2-2.5.7-py2.py3-none-any.whl (237 kB)
Collecting pypdf2!=1.27.10,!=1.27.11,<2.0.0,>=1.27.4
  Using cached PyPDF2-1.28.6-py3-none-any.whl (87 kB)
Collecting pdfminer.six==20201018
  Using cached pdfminer.six-20201018-py3-none-any.whl (5.6 MB)
Collecting sortedcontainers
  Using cached sortedcontainers-2.4.0-py2.py3-none-any.whl (29 kB)
Collecting authlib
  Using cached Authlib-1.1.0-py2.py3-none-any.whl (214 kB)
Collecting pytz
  Using cached pytz-2022.4-py2.py3-none-any.whl (500 kB)
Collecting PyQt5-sip<13,>=12.11
  Using cached PyQt5_sip-12.11.0-cp39-cp39-manylinux1_x86_64.whl (357 kB)
Collecting PyQt5-Qt5>=5.15.0
  Using cached PyQt5_Qt5-5.15.2-py3-none-manylinux2014_x86_64.whl (59.9 MB)
Collecting PyQtWebEngine-Qt5>=5.15.0
  Using cached PyQtWebEngine_Qt5-5.15.2-py3-none-manylinux2014_x86_64.whl (67.5 MB)
Collecting packaging
  Using cached packaging-21.3-py3-none-any.whl (40 kB)
Collecting soupsieve>1.2
  Using cached soupsieve-2.3.2.post1-py3-none-any.whl (37 kB)
Collecting pycparser
  Using cached pycparser-2.21-py2.py3-none-any.whl (118 kB)
Collecting fonttools
  Downloading fonttools-4.37.4-py3-none-any.whl (960 kB)
     ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 960.8/960.8 kB 1.3 MB/s eta 0:00:00
Collecting svg.path
  Using cached svg.path-6.2-py2.py3-none-any.whl (40 kB)
Collecting attrs>=17.4.0
  Using cached attrs-22.1.0-py2.py3-none-any.whl (58 kB)
Collecting pyrsistent!=0.17.0,!=0.17.1,!=0.17.2,>=0.14.0
  Using cached pyrsistent-0.18.1-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (115 kB)
Collecting charset-normalizer<3,>=2
  Using cached charset_normalizer-2.1.1-py3-none-any.whl (39 kB)
Collecting idna<4,>=2.5
  Using cached idna-3.4-py3-none-any.whl (61 kB)
Collecting ntlm-auth>=1.0.2
  Using cached ntlm_auth-1.5.0-py2.py3-none-any.whl (29 kB)
INFO: pip is looking at multiple versions of requests[socks] to determine which version is compatible with other requirements. This could take a while.
Collecting requests[socks]>=2.11.1
  Using cached requests-2.28.0-py3-none-any.whl (62 kB)
INFO: pip is looking at multiple versions of oauthlib to determine which version is compatible with other requirements. This could take a while.
Collecting oauthlib
  Using cached oauthlib-3.2.0-py3-none-any.whl (151 kB)
INFO: pip is looking at multiple versions of requests-oauthlib to determine which version is compatible with other requirements. This could take a while.
Collecting requests-oauthlib
  Using cached requests_oauthlib-1.3.0-py2.py3-none-any.whl (23 kB)
INFO: pip is looking at multiple versions of requests-ntlm to determine which version is compatible with other requirements. This could take a while.
Collecting requests-ntlm>=0.2.0
  Using cached requests_ntlm-1.0.0-py2.py3-none-any.whl (5.2 kB)
INFO: pip is looking at multiple versions of certifi to determine which version is compatible with other requirements. This could take a while.
Collecting certifi
  Using cached certifi-2022.9.14-py3-none-any.whl (162 kB)
INFO: pip is looking at multiple versions of requests to determine which version is compatible with other requirements. This could take a while.
INFO: pip is looking at multiple versions of python-docx to determine which version is compatible with other requirements. This could take a while.
Collecting python-docx>=0.8.10
  Using cached python-docx-0.8.10.tar.gz (5.5 MB)
  Preparing metadata (setup.py): started
  Preparing metadata (setup.py): finished with status 'done'
INFO: pip is looking at multiple versions of pyqtwebengine-qt5 to determine which version is compatible with other requirements. This could take a while.
INFO: pip is looking at multiple versions of pyqt5-sip to determine which version is compatible with other requirements. This could take a while.
INFO: pip is looking at multiple versions of pyqt5-qt5 to determine which version is compatible with other requirements. This could take a while.
INFO: pip is looking at multiple versions of pypdf2 to determine which version is compatible with other requirements. This could take a while.
Collecting pypdf2!=1.27.10,!=1.27.11,<2.0.0,>=1.27.4
  Using cached PyPDF2-1.28.5-py3-none-any.whl (87 kB)
INFO: pip is looking at multiple versions of lxml to determine which version is compatible with other requirements. This could take a while.
Collecting lxml>3.0
  Using cached lxml-4.9.0-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.manylinux_2_24_x86_64.whl (7.0 MB)
INFO: pip is looking at multiple versions of jsonschema to determine which version is compatible with other requirements. This could take a while.
Collecting jsonschema<5.0.0,>=4.4.0
  Using cached jsonschema-4.15.0-py3-none-any.whl (82 kB)
INFO: pip is looking at multiple versions of fpdf2 to determine which version is compatible with other requirements. This could take a while.
Collecting fpdf2<3.0.0,>=2.5.2
  Using cached fpdf2-2.5.6-py2.py3-none-any.whl (233 kB)
INFO: pip is looking at multiple versions of dnspython to determine which version is compatible with other requirements. This could take a while.
Collecting dnspython>=2.0.0
  Using cached dnspython-2.2.0-py3-none-any.whl (266 kB)
INFO: pip is looking at multiple versions of defusedxml to determine which version is compatible with other requirements. This could take a while.
Collecting defusedxml>=0.6.0
  Using cached defusedxml-0.7.0-py2.py3-none-any.whl (25 kB)
INFO: pip is looking at multiple versions of cffi to determine which version is compatible with other requirements. This could take a while.
Collecting cffi>=1.12
  Using cached cffi-1.15.0-cp39-cp39-manylinux_2_12_x86_64.manylinux2010_x86_64.whl (444 kB)
INFO: pip is looking at multiple versions of beautifulsoup4 to determine which version is compatible with other requirements. This could take a while.
Collecting beautifulsoup4>=4.7.0
  Using cached beautifulsoup4-4.11.0-py3-none-any.whl (71 kB)
INFO: pip is looking at multiple versions of qtpy to determine which version is compatible with other requirements. This could take a while.
Collecting QtPy
  Using cached QtPy-2.1.0-py3-none-any.whl (68 kB)
INFO: pip is looking at multiple versions of pywebview to determine which version is compatible with other requirements. This could take a while.
INFO: pip is looking at multiple versions of pyqtwebengine to determine which version is compatible with other requirements. This could take a while.
Collecting pyqtwebengine
  Using cached PyQtWebEngine-5.15.5-cp36-abi3-manylinux1_x86_64.whl (228 kB)
INFO: pip is looking at multiple versions of pyqt5 to determine which version is compatible with other requirements. This could take a while.
Collecting PyQt5
  Using cached PyQt5-5.15.6-cp36-abi3-manylinux1_x86_64.whl (8.3 MB)
INFO: pip is looking at multiple versions of proxy-tools to determine which version is compatible with other requirements. This could take a while.
INFO: pip is looking at multiple versions of docutils to determine which version is compatible with other requirements. This could take a while.
Collecting docutils
  Using cached docutils-0.18.1-py2.py3-none-any.whl (570 kB)
INFO: pip is looking at multiple versions of xlwt to determine which version is compatible with other requirements. This could take a while.
INFO: pip is looking at multiple versions of xlutils to determine which version is compatible with other requirements. This could take a while.
INFO: pip is looking at multiple versions of xlrd to determine which version is compatible with other requirements. This could take a while.
INFO: pip is looking at multiple versions of tzlocal to determine which version is compatible with other requirements. This could take a while.
INFO: pip is looking at multiple versions of tweepy to determine which version is compatible with other requirements. This could take a while.
Collecting tweepy<4.0.0,>=3.8.0
  Using cached tweepy-3.9.0-py2.py3-none-any.whl (30 kB)
INFO: pip is looking at multiple versions of tenacity to determine which version is compatible with other requirements. This could take a while.
Collecting tenacity<9.0.0,>=8.0.1
  Using cached tenacity-8.0.1-py3-none-any.whl (24 kB)
INFO: pip is looking at multiple versions of simple-salesforce to determine which version is compatible with other requirements. This could take a while.
Collecting simple_salesforce<2.0.0,>=1.0.0
  Using cached simple_salesforce-1.12.1-py2.py3-none-any.whl (119 kB)
INFO: pip is looking at multiple versions of selenium to determine which version is compatible with other requirements. This could take a while.
INFO: pip is looking at multiple versions of pdfminer-six to determine which version is compatible with other requirements. This could take a while.
INFO: pip is looking at multiple versions of rpaframework-pdf to determine which version is compatible with other requirements. This could take a while.
INFO: pip is looking at multiple versions of rpaframework-dialogs to determine which version is compatible with other requirements. This could take a while.
Collecting rpaframework-dialogs<4.0.0,>=3.0.0
  Using cached rpaframework_dialogs-3.0.0-py3-none-any.whl (18 kB)
INFO: pip is looking at multiple versions of pywebview to determine which version is compatible with other requirements. This could take a while.
INFO: pip is looking at multiple versions of rpaframework-core to determine which version is compatible with other requirements. This could take a while.
INFO: pip is looking at multiple versions of robotframework-seleniumtestability to determine which version is compatible with other requirements. This could take a while.
INFO: pip is looking at multiple versions of robotframework-seleniumlibrary to determine which version is compatible with other requirements. This could take a while.
Collecting robotframework-seleniumlibrary<6.0.0,>=5.1.0
  Using cached robotframework_seleniumlibrary-5.1.2-py2.py3-none-any.whl (94 kB)
  Using cached robotframework_seleniumlibrary-5.1.1-py2.py3-none-any.whl (94 kB)
  Using cached robotframework_seleniumlibrary-5.1.0-py2.py3-none-any.whl (94 kB)
INFO: pip is looking at multiple versions of rpaframework-dialogs to determine which version is compatible with other requirements. This could take a while.
INFO: pip is looking at multiple versions of robotframework-requests to determine which version is compatible with other requirements. This could take a while.
Collecting robotframework-requests<0.10.0,>=0.9.1
  Using cached robotframework_requests-0.9.2-py3-none-any.whl (20 kB)
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 looking at multiple versions of rpaframework-core to determine which version is compatible with other requirements. This could take a while.
INFO: pip is looking at multiple versions of robotframework-seleniumtestability to determine which version is compatible with other requirements. This could take a while.
INFO: pip is looking at multiple versions of robotframework-seleniumlibrary to determine which version is compatible with other requirements. This could take a while.
  Using cached robotframework_requests-0.9.1-py3-none-any.whl (20 kB)
INFO: pip is looking at multiple versions of robotframework-pythonlibcore to determine which version is compatible with other requirements. This could take a while.
INFO: pip is looking at multiple versions of robotframework to determine which version is compatible with other requirements. This could take a while.
Collecting robotframework!=4.0.1,<6.0.0,>=4.0.0
  Using cached robotframework-5.0-py3-none-any.whl (638 kB)
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: 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: 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.
  Using cached robotframework-4.1.3-py2.py3-none-any.whl (659 kB)
INFO: pip is looking at multiple versions of robotframework-requests to determine which version is compatible with other requirements. This could take a while.
  Using cached robotframework-4.1.2-py2.py3-none-any.whl (659 kB)
  Using cached robotframework-4.1.1-py2.py3-none-any.whl (658 kB)
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.
  Using cached robotframework-4.1-py2.py3-none-any.whl (657 kB)
  Using cached robotframework-4.0.3-py2.py3-none-any.whl (655 kB)
  Using cached robotframework-4.0.2-py2.py3-none-any.whl (655 kB)
INFO: pip is looking at multiple versions of robotframework-pythonlibcore to determine which version is compatible with other requirements. This could take a while.
INFO: pip is looking at multiple versions of robotframework to determine which version is compatible with other requirements. This could take a while.
  Using cached robotframework-4.0-py2.py3-none-any.whl (653 kB)
INFO: pip is looking at multiple versions of pyyaml to determine which version is compatible with other requirements. This could take a while.
INFO: pip is looking at multiple versions of python-xlib to determine which version is compatible with other requirements. This could take a while.
Collecting python-xlib>=0.17
  Using cached python_xlib-0.30-py2.py3-none-any.whl (178 kB)
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: 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.
  Using cached python_xlib-0.29-py2.py3-none-any.whl (176 kB)
  Using cached python_xlib-0.28-py2.py3-none-any.whl (176 kB)

....

… and output will continue for next 4+ hours (of course depending on your network speed, machine performance, etc.)

Code of Conduct

I agree to follow the PSF Code of Conduct.

About this issue

Original URL
State: open
Created 2 years ago
Comments: 49 (35 by maintainers)

Most upvoted comments

BTW. @pfmoore @pradyunsg -> I thought about maybe a proposal to Pypa to host constraints in PyPI as optional metadata (linked to package but updateable unlike the package). That would be a way I could see this could become a “standard”. For example you could apply constraints automatically if they are present and you specify --with-default-constraints option of pip. That would make it super easy for people to build a solution based on constraints and it could be turned into a PEP /standard.

WDYT? Would tha fly (of course this is just very, very, very rough idea, it would require a LOT more discussion and consensus - just wanted to hear your comments, whether it’s one of: nonsense, maybe, plausible, great idea to explore … 😃

potiuk on Oct 27, 2022

Here’s some numbers for us to consider based on back-of-the-napkin math…

2_000_000 (current) -> ~4 hrs (250 mins)
200_000 -> ~30 minutes (25 minutes)
100_000 -> ~10 minutes (12 minutes)

I think there’s a significant experience difference in 100_000 vs 2_000_000. The former is clearly better but it will be won’t be able to handle really complex graphs. OTOH, we’re gonna have fewer rounds thanks to backjumping. I’m comfortable with the middle ground but I’m happy to be aggressive and go down to 100_000 here too.

FWIW, this issue is about improving the messaging so that it’s more actionable rather than a blunt “IDK what to do” message. That’s a change that’ll need to happen on both resolvelib’s end and our end IMO – and backjumping makes it harder to hit this case; doesn’t eliminate it.

pradyunsg on Mar 28, 2023

This issue is effectively resolved on Pip main (28239f9) likely thanks to https://github.com/sarugaku/resolvelib/pull/111 and https://github.com/sarugaku/resolvelib/pull/113.

The issue is still reproducible on Python 3.9 Pip 23.0.1 with the following command (takes a very long time with no apparent resolution):

pip download -d downloads -r https://raw.githubusercontent.com/vjmp/pipbacktracking/trunk/requirements_fail.txt

However on Pip main (28239f9) the following output is quickly given:

ERROR: Cannot install pywebview[qt]==3.6.2 and rpaframework-dialogs because these package versions have conflicting dependencies.

The conflict is caused by:
    pywebview[qt] 3.6.2 depends on pywebview 3.6.2 (from https://files.pythonhosted.org/packages/23/b6/e1da5ff929ea0eedae11b53f4273583dccb7a6de37b68388201db43eeafc/pywebview-3.6.2-py3-none-any.whl (from https://pypi.org/simple/pywebview/))
    robocorp-dialog 0.5.3 depends on pywebview==3.6.3; sys_platform == "linux"

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

I suggest this issue be closed and if there is some different set of requirements that causes long backtracking a new issue should be opened (I would actually be surprised given how powerful both these improvements are).

notatallshaw on Mar 28, 2023

Yeah apologies on my behalf as well, Friday evening is not the best time to comment on these kinds of things ✋ The last answers got me the answer I was looking so this is about support and maintenance where every extra thing is a big thing so I totally understand the point now.

In this backdrop @pradyunsg three option scoping make a lot more sense and I think the third option of getting predictable outputs that applications can parse from the pip output would probably solve the situation and enable us to determine when enough back-tracking has happened.

I’ll open our case a bit more to answer @notatallshaw’s question: In our case we are providing tools for users that are creating RPA robots (with python and RobotFramework) that are not just about python. We need more and we have already solved some big puzzles to enable getting other apps like browser, AWS tools, Terraform, … from conda-forge and also enabling pip loading into isolated environments that can also be moved from one machine to another. Here relying on things that are installed on the end-users machine is a big no-no as it just leads to huge IT costs. Our tooling can make a freeze file that goes over conda-forge, pip and some extra post install scripts to achieve a fully locked environment even for environments that things like nodejs.

The problem is that we need to be able to built that environment somewhere and also provide tooling for the devs / IT people how are managing the dependencies… There a CI could be burning a lot of time and energy running back-tracking without any human interaction. So predictable behavior of the base tools is everything to us.

I’ll check if we could pitch in and try to help out with the notifications. (…and again sorry for the flaming)

kariharju on Oct 24, 2022

@notatallshaw It is other way round, our customers write RPA robots

If I was in your situation I would still try providing a constraints file to your customers to say “this is what we tested our application against” and “when you are doing pip install please use these constraints”, much in the same way Apache Airflow recommends: https://airflow.apache.org/docs/apache-airflow/stable/installation/installing-from-pypi.html

From my point of view this provides a few benefits:

It means your customers are using the same transitive dependencies as you tested with
If customers add mutually incompatible requirements it is going to appear much quicker and they can bring it up with you much faster
When a customer requires a dependency that explicitly breaks your constraints they are going to understand much faster that they are walking in to problems of complex requirement dependencies because they will have to take an action, either manually editing the constraints file or not using it at all

I may be over simplifying your problem, but I’ve been very happy using well specified constraints files as a tool to make multiple environments with slightly different requirements work well with each other.

notatallshaw on Oct 24, 2022

What problems would come from reading the value for try_to_avoid_resolution_too_deep from an environment variable (if exists and use default if not)? What am I missing?

Feel free to experiment using the hack I provided above. Or simply patch your copy of pip.

I’d consider it a good idea to cap resolution times /depth by default so people can opt in when the edge cases hit

I believe this is reasonable. For now, the Unix timeout command will do this. PRs to add a timeout to pip, and give helpful output if the timeout is reached, would be welcomed. I’ll freely admit that I’ve no idea how I would go about providing useful guidance on hitting a timeout, so it’s unlikely I’ll be able to do anything about this myself.

pfmoore on Oct 21, 2022

And if we do reduce the number, I’d like to see some evidence that any proposed new value is (in some sense) better than the current value.

Dropping a zero brings us down from 4 hours to ~30 minutes of trying to resolve (assuming similar per-round average timing).

I can see the argument that it is a more reasonable amount of time for failure in automation. 😃

pradyunsg on Oct 18, 2022

@aigarius Can you confirm that you are using the latest version of pip?

Having said all of this, if you really want to try experimenting with try_to_avoid_resolution_too_deep=1

That would mean that you can’t even have dependencies – a round is the resolver evaluating a single candidate (or set of them). You won’t be able to install more packages than set in that variable.

I’m personally fine if we implemented a --no-backtracking-in-resolve flag or something.

pradyunsg on Oct 17, 2022

We are seeing a related issue - in some environments we do not want the backtracking behaviour at all and being able to set try_to_avoid_resolution_too_deep=1 for those test jobs with an explicit environment variable or pip runtime option would be essential to avoid pip (incorrectly) selecting an old and completely obsolete version of a dependency and running tests against that (which will be useless anyway) instead of failing with a clear and explicit error message like - “hey, your requirements can not be satisfied because that one thing you depend on needs a newer Python version”.

User-configurable setting is important because pip is being used in very different environments - in some the goal is to get a working environment at whatever cost, in others quickly failing to set up the environment (and producing an error message that explains why!) is actually more important. And only the user/admin/dev setting that environment up knows what they expect/want from pip.

aigarius on Oct 17, 2022

I’m not opposed to the idea that we should reduce that number. 😃

To be clear, nor am I. I am uncomfortable about making it user-settable, though, as we’ll just end up with people wanting advice on what to set it to. And if we do reduce the number, I’d like to see some evidence that any proposed new value is (in some sense) better than the current value.

pfmoore on Oct 11, 2022

Thanks for the detailed report. Unfortunately, some sets of requirements trigger exponential behaviour and while we might be able to alter the heuristics we use to “fix” those cases, we’ll inevitably break a different case in the process.

There has been a lot of work done by volunteers (either pip maintainers or pip users) to examine possible improvements - examples are #10884, https://github.com/sarugaku/resolvelib/issues/64, #10479, #10201. I suggest you read these for background. A search on the issue tracker for “is:issue resolver performance” should find plenty more.

In particular, https://github.com/pypa/pip/issues/10479#issuecomment-940129717 might be relevant here.

Basically, though, the answer is that it’s not even theoretically possible to avoid all pathological behaviour. We’ve done a lot of work algorithmically, and we have implemented heuristics to address the common cases of slowdown, but it’s entirely possible that there are still improvements to be made, but we have to be extremely careful that we don’t simply adjust the trade-offs in a way that hurts other users when we change things.

If you’re interested, we’d welcome suggestions on changes that you think might help. Or if you find a specific feature of your example that might generalise, that would also be useful (as would suggesting approaches to address that feature).

In the meantime, however, the following approaches have been useful for others trying to work around long resolve times:

Don’t let this happen in CI, if you can avoid it. Test the install process locally, where you can Ctrl-C a long-running resolve, and identify the problem and any workaround before deploying it to CI.
If you’re building an application, pin your dependencies to exact versions, then the resolve doesn’t have to do anything complicated anyway.
If you have to depend on version ranges, use constraints files to eliminate parts of the solution space that you know won’t lead to valid solves (for example, add constraints to stop pip considering very old versions of your dependencies).

pfmoore on Oct 3, 2022