Improving failures at `ResolutionTooDeep` to include more context

[vjmp]

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

1. Clone repository from: https://github.com/vjmp/pipbacktracking
2. Download rcc from: https://downloads.robocorp.com/rcc/releases/index.html
3. Make it executable and note location
4. 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.

[pfmoore]

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, sarugaku/resolvelib#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, #10479 (comment) 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:

1. 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.
2. If you're building an application, pin your dependencies to exact versions, then the resolve doesn't have to do anything complicated anyway.
3. 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]

@pypa/pip-committers I'm surprised we don't have a "type: performance" label. Also, there's nothing for "known limitation" - I was tempted to mark this as "not a bug" but that seems a bit strong.

I've added those two labels for this issue (and other resolver performance issues) - if anyone would prefer to handle this another way, please say so.

[vjmp]

Bug part is that it takes too long, without control. So bug is that missing control on user side.

If we could just export MAX_PIP_RESOLUTION_ROUNDS=50000 for example (and that would override now hard coded try_to_avoid_resolution_too_deep = 2000000 definition) that would give us control over it.

We could then use this on our automation, and limit impact of time taken, and fail faster.

And yes, I understand problem space, that this is "feature" to do backtracking. It is fine when you have small dependency tree. We have that big tree, and just want to make it fail faster.

[pfmoore]

If we could just export MAX_PIP_RESOLUTION_ROUNDS=50000 for example (and that would override now hard coded try_to_avoid_resolution_too_deep = 2000000 definition) that would give us control over it.

Please read some of the other issues that I referenced. This was discussed extensively some time ago.

Or if you want to run pip with a maximum duration, there's the Unix timeout command (which I know next to nothing about, I found it via a Google search for "unix command to run subprocess with timeout"). The Python subprocess module lets you do the same thing, if you prefer to use Python for portability.

[kariharju]

Hi,

I think the only thing needed would be the ability to control that try_to_avoid_resolution_too_deep = 2000000 externally.

If that value could be controlled we could handle different cases we are seeing. In some cases, we do not want any backtracking; in others, 200 steps would make sense, and only in the most complex case would we even try with the full 2000000, just because that can mean 4+ hours of resolution time.
So instead of the hard-coded value, opening that up to a environment variable or a run flag would solve this.

The backtracking problem is really hard, and there are problems that I don't think it can (or even should) solve.
For example: "The resolution completed, but did I get what I asked for?".
So as an example, if the backtracking changes the major version of some dependency that can break the actual code, we would want to run. So in some cases, the resolution can succeed and fail at the same time 😉. Also, a resolution that takes over 30mins in most customer cases is a failure no matter what. The "correct" fix for that in every case should be to guide the developer to fix the dependencies, lock-down version, etc. In short not everything should be left to pip to solve.

So just having the ability to control how much backtracking is done would solve this issue.

[pfmoore]

I think the only thing needed would be the ability to control that try_to_avoid_resolution_too_deep = 2000000 externally.

Please read the other issues. This has been extensively discussed, and the issue is that there's no way to meaningfully know what a "reasonable" value is, without trying it. By the time you know you need to set the value smaller, it's too late - you've already taken 4 hours. And setting the value lower will never get a better result, it'll simply fail sooner (which is of no help if you've already determined that it's going to fail). In particular, the value has no useful link to how long pip is going to take to fail.

If you're convinced that setting this value is useful, I suggest you write a wrapper script that monkeypatches pip to let you do so, and try that out. If you find good evidence that setting the value is of benefit, feel free to present an argument based on actual real-world use cases.

Also note that if you want to set a time limit on how long pip will run when trying to resolve an install, you're better using something like the Unix timeout command, which will let you do exactly that: timeout 10m python -m pip install .... (I'm not aware of a similar Windows command, but it should be possible to write something in Python that works the same way).

[pradyunsg]

The "correct" fix for that in every case should be to guide the developer to fix the dependencies, lock-down version, etc. In short not everything should be left to pip to solve.

That's literally the documentation that https://pip.pypa.io/warnings/backtracking points to -- the link printed in the error messages.

This value is set so high, to ensure that people don't hit it in anything other than the most pathological cases.

[pradyunsg]

If you'd like for this value to be set to something lower, that's... a tractable request -- I'm not opposed to the idea that we should reduce that number. :)