The dependency resolver fails with `ResolutionTooDeep` error for big project

Having seen @nlhkabu and @ei8fdb message I had a go with it using a huge project.

pip 20.1.1 and python 3.6.9

Command that was run:

pip install --unstable-feature=resolver -r requirements.txt --log pip.log

Traceback:

Collecting html5lib==1.0.1
  Using cached html5lib-1.0.1-py2.py3-none-any.whl (117 kB)
Collecting private2==0.4.0
  Downloading privaterepo/private2-0.4.0-py3-none-any.whl (14 kB)
Collecting PyHamcrest==1.9.0
  Using cached PyHamcrest-1.9.0-py2.py3-none-any.whl (52 kB)
Requirement already satisfied: setuptools==46.4.0 in ./.venv/lib/python3.6/site-packages (from PyHamcrest==1.9.0->private2==0.4.0->private1==1.2.6->-r requirements.txt (line 6)) (46.4.0)
ERROR: Exception:
Traceback (most recent call last):
  File "/test-project/.venv/lib/python3.6/site-packages/pip/_internal/cli/base_command.py", line 188, in _main
    status = self.run(options, args)
  File "/test-project/.venv/lib/python3.6/site-packages/pip/_internal/cli/req_command.py", line 185, in wrapper
    return func(self, options, args)
  File "/test-project/.venv/lib/python3.6/site-packages/pip/_internal/commands/install.py", line 333, in run
    reqs, check_supported_wheels=not options.target_dir
  File "/test-project/.venv/lib/python3.6/site-packages/pip/_internal/resolution/resolvelib/resolver.py", line 80, in resolve
    self._result = resolver.resolve(requirements)
  File "/test-project/.venv/lib/python3.6/site-packages/pip/_vendor/resolvelib/resolvers.py", line 413, in resolve
    state = resolution.resolve(requirements, max_rounds=max_rounds)
  File "/test-project/.venv/lib/python3.6/site-packages/pip/_vendor/resolvelib/resolvers.py", line 323, in resolve
    raise ResolutionTooDeep(max_rounds)
pip._vendor.resolvelib.resolvers.ResolutionTooDeep: 100

Context

Unfortunately, I cannot provide concrete details since I’m working with private packages. What I can tell is that the project I was trying to install is rather heavy:

• requirements.txt specifies around 70 only concrete (==<version>) package requirements
• majority are found in a private package repo
• majority are dependent on other packages that are also specified there, I’d say up to 6-7 levels deep (excluding 3rd party dependencies), so package1 -> package2 -> package3 -> package4 -> package5 -> package6 is possible, therefore circular dependencies have to be handled well by the resolver.
• in total, there are around 150 packages installed if successful - this includes 3rd party dependencies
• pipdeptree | wc -l says 7341 for the entire thing

Environment It was done in a clean environment, created with virtualenv

(test-project) ➜ pip list                                                                                                                                                                                       
Package    Version
---------- -------
pip        20.1.1
setuptools 46.4.0
wheel      0.34.2

Error

Requirement already satisfied: setuptools==46.4.0 in ./.venv/lib/python3.6/site-packages (from PyHamcrest==1.9.0->private2==0.4.0->private1==1.2.6->-r requirements.txt (line 6)) (46.4.0)

and then immediately after this

pip._vendor.resolvelib.resolvers.ResolutionTooDeep: 100

Seems like it’s related to the private1 package dependency depth, so I’ll include some more details
about it:

$ cat package1_pipdeptree_op.txt | ag "^  - " | wc -l # 1st level count                                                                                                                                                                   
15
$ cat package1_pipdeptree_op.txt | ag "^    - " | wc -l # 2nd level count                                                                                                                                                                 
77
$ cat package1_pipdeptree_op.txt | ag "^      - " | wc -l # 3rd level count                                                                                                                                                               
246
$ cat package1_pipdeptree_op.txt | ag "^        - " | wc -l # 4th level count                                                                                                                                                             
408
$ cat package1_pipdeptree_op.txt | ag "^          - " | wc -l # 5th level count                                                                                                                                                           
352
$ cat package1_pipdeptree_op.txt | ag "^            - " | wc -l # 6th level count                                                                                                                                                         
195
$ cat package1_pipdeptree_op.txt | ag "^              - " | wc -l # 7th level count                                                                                                                                                       
64
$ cat package1_pipdeptree_op.txt | ag "^                - " | wc -l # 8th level count                                                                                                                                                     
13
$ cat package1_pipdeptree_op.txt | ag "^                  - " | wc -l # 9th level count                                                                                                                                                   
1
$ cat package1_pipdeptree_op.txt | ag "^                    - " | wc -l # 10th level count                                                                                                                                                
0

Additionally, checked the entire project and it looks like 9 levels is as deep as it gets.

I had a look at the pip.log output and grepped the packages resolver has looked at before producing the error - the deepest it got was 4 levels.

Hope this helps - let me know if you need any more details