pip-compile fails to resolve dependency versions, even though solution exists

[tmarice]

For some reason pip-compile decides to pin a direct dependency's (google-api-python-client) dependency (google-auth-httplib2) to a higher-than-necessary version (0.1.0 instead of 0.0.4), which causes a clash between another direct dependency (httplib2==0.11.3 ) and the resolved version (google-auth-httplib2==0.1.0 requires httplib2>=0.15.0).

Directly running pip install google-api-python-client==1.7.8 httplib2==0.11.3 results in:

Successfully installed cachetools-4.2.1 google-api-python-client-1.7.8 google-auth-1.28.0 google-auth-httplib2-0.0.4 httplib2-0.11.3 pyasn1-0.4.8 pyasn1-modules-0.2.8 rsa-4.7.2 six-1.15.0 uritemplate-3.0.1

Environment Versions

1. Ubuntu 18.04.5 LTS (through Docker version 20.10.5, build 55c4c88 on Mac OS Catalina 10.15.7)
2. Python version: 3.6.9
3. pip version: 21.0.1
4. pip-tools version: 6.0.1

Steps to replicate

cat >> requirements.in <<EOF
httplib2==0.11.3
google-api-python-client==1.7.8
EOF

pip-compile requirements.in --output-file requirements.txt

Expected result

# requirements.txt
cachetools==4.2.1
google-api-python-client==1.7.8
google-auth==1.28.0
google-auth-httplib2==0.0.4
httplib2==0.11.3
pyasn1==0.4.8
pyasn1-modules==0.2.8
rsa==4.7.2
six==1.15.0
uritemplate==3.0.1

Actual result

Could not find a version that matches httplib2<1dev,==0.11.3,>=0.15.0,>=0.9.2 (from -r requirements/test.in (line 1))
Tried: 0.7.3, 0.7.3, 0.7.4, 0.7.4, 0.7.5, 0.7.5, 0.7.6, 0.7.6, 0.7.7, 0.7.7, 0.8, 0.8, 0.9, 0.9, 0.9.1, 0.9.1, 0.9.2, 0.9.2, 0.10.3, 0.11.0, 0.11.1, 0.11.3, 0.12.0, 0.12.1, 0.12.3, 0.12.3, 0.13.0, 0.13.0, 0.13.1, 0.13.1, 0.14.0, 0.14.0, 0.15.0, 0.15.0, 0.16.0, 0.16.0, 0.17.0, 0.17.0, 0.17.1, 0.17.1, 0.17.2, 0.17.2, 0.17.3, 0.17.3, 0.17.4, 0.17.4, 0.18.0, 0.18.0, 0.18.1, 0.18.1, 0.19.0, 0.19.0, 0.19.1, 0.19.1
There are incompatible versions in the resolved dependencies:
  httplib2==0.11.3 (from -r requirements/test.in (line 1))
  httplib2<1dev,>=0.9.2 (from google-api-python-client==1.7.8->-r requirements/test.in (line 2))
  httplib2>=0.15.0 (from google-auth-httplib2==0.1.0->google-api-python-client==1.7.8->-r requirements/test.in (line 2))

[atugushev]

Hello @tmarice,

Thanks for the report. That's because pip-tools doesn't yet have a proper dependency resolver. See #693 and the other related issues for details.

[dieggoluis]

@atugushev was it a design choice (not having a proper resolver) since it's faster and fails only in few cases, or you'd accept/consider a PR for example using resolvelib or another proper resolver?

[webknjaz]

@dieggoluis I think nobody here opposes having resolvelib integrated. I suggested it in some threads too. But it'd take some effort to get it done. I have experience integrating resolvelib but I've never gotten to explore what it'd take to get it pulled into pip-tools.

If you're willing to start working on a PR, I'll try to find some time to review it. Not sure if there's anybody else here who's actually worked with resolvelib directly in the past but if there is, it'd be useful to track them down and ask for reviews too.

[atugushev]

I have a prototype atugushev#10. Implemented the new resolver using pip itself (not resolvelib though). It almost works (98% tests passed) but it's pretty raw.

[webknjaz]

I'd still prefer resolvelib tho

[FlorentJeannot]

@webknjaz May I ask you why you'd prefer resolvelib instead of using pip's resolver?

At Data Theorem, we are experimenting pip-tools in one of our projects in replacement of pipenv and we like it so far.

We think that it would make more sense that pip-tools uses pip's resolver. It would make it a thin wrapper around pip and we think that's what pip-tools should become (a set of tools based on pip which adds features that pip is currently missing).
It would also make sense to us to have pip-compile and pip-sync use the same resolver to ensure their behavior is more consistent.

If we can provide any help for the implementation or the review, we would be happy to contribute.

Thanks!

[dieggoluis]

@FlorentJeannot pip actually uses resolvelib as a vendored library. The advantage of using resolvelib might be that it is easier to get the most updated version. The drawback is adding a new dependency.

@atugushev I'd start working on it this weekend in my spare time, but if you are almost done with it I'll let you finish the job :) I'd be happy to help reviewing it

[webknjaz]

@FlorentJeannot As Diego mentioned, resolvelib is pip's resolver (it used to have a worse one which is probably still togglable tho). Also, pip-tools currently uses that legacy pip's resolver IIRC (which is what causes the resolution issues like this).

I think that it's easier to use resolvelib directly w/o pip's wrappers around it because pip-tools doesn't need all of those features baked in pip IMHO. Also, resolvelib has a public API and pip does not + relying on pip is a lock-in for the version of resolvelib that changes over time.
Besides, using pip's abstractions will probably get in the way of trying to implement custom resolution strategies.

By the way, you mentioned pipenv — AFAIK it also uses resolvelib. The only thing that I know of that doesn't is poetry, it has its own resolver called mixology which is pretty opinionated and implements a different resolution algorithm (PubGrub) that is coming from the Dart lang ecosystem.

[webknjaz]

It almost works (98% tests passed)

When I was integrating it into ansible-galaxy, I was at this point of 90% works in an hour after the start, and then the next 90% (polishing/testing/etc) lasted several months 😃

[FlorentJeannot]

I have a prototype atugushev#10. Implemented the new resolver using pip itself (not resolvelib though). It almost works (98% tests passed) but it's pretty raw.

@atugushev Sorry to bother, I'd like to know if there's any news about this PR and if we could expect an improved resolver for this year?

Thanks!

[atugushev]

I'd like to know if there's any news about this PR and if we could expect an improved resolver for this year?

@FlorentJeannot thanks for pinging 🙏🏻 It's at the top of my TODO list.

[atugushev]

@FlorentJeannot try #1539 which adds support for pip's 2020 dependency resolver

[atugushev]

Works with new resolver #1539:

Details

❯ pip-compile --resolver backtracking
#
# This file is autogenerated by pip-compile with python 3.8
# To update, run:
#
#    pip-compile --resolver=backtracking
#
aiobotocore[boto3]==1.3.0
    # via
    #   dvc
    #   s3fs
aiohttp==3.8.1
    # via aiobotocore
aioitertools==0.9.0
    # via aiobotocore
aiosignal==1.2.0
    # via aiohttp
appdirs==1.4.4
    # via dvc
async-timeout==4.0.2
    # via aiohttp
atpublic==3.0.1
    # via flufl-lock
attrs==21.4.0
    # via aiohttp
boto3==1.17.49
    # via
    #   -r requirements.in
    #   aiobotocore
botocore==1.20.49
    # via
    #   aiobotocore
    #   boto3
    #   s3transfer
cachetools==5.0.0
    # via google-auth
certifi==2021.10.8
    # via
    #   dulwich
    #   requests
cffi==1.15.0
    # via pygit2
charset-normalizer==2.0.12
    # via
    #   aiohttp
    #   requests
colorama==0.4.4
    # via
    #   dvc
    #   rich
commonmark==0.9.1
    # via rich
configobj==5.0.6
    # via dvc
decorator==5.1.1
    # via jsonpath-ng
dictdiffer==0.9.0
    # via dvc
diskcache==5.4.0
    # via dvc
distro==1.7.0
    # via dvc
dpath==2.0.6
    # via dvc
dulwich==0.20.32
    # via dvc
dvc[s3]==2.3.0
    # via -r requirements.in
flatten-dict==0.4.2
    # via dvc
flufl-lock==3.2
    # via dvc
frozenlist==1.3.0
    # via
    #   aiohttp
    #   aiosignal
fsspec==2021.5.0
    # via
    #   dvc
    #   s3fs
ftfy==6.1.1
    # via python-benedict
funcy==1.17
    # via dvc
future==0.18.2
    # via grandalf
gitdb==4.0.9
    # via gitpython
gitpython==3.1.27
    # via dvc
google-api-python-client==1.7.8
    # via -r requirements.in
google-auth==2.6.0
    # via
    #   google-api-python-client
    #   google-auth-httplib2
google-auth-httplib2==0.0.4
    # via google-api-python-client
grandalf==0.6
    # via dvc
httplib2==0.11.3
    # via
    #   -r requirements.in
    #   google-api-python-client
    #   google-auth-httplib2
idna==3.3
    # via
    #   requests
    #   yarl
jmespath==0.10.0
    # via
    #   boto3
    #   botocore
jsonpath-ng==1.5.3
    # via dvc
mailchecker==4.1.12
    # via python-benedict
multidict==6.0.2
    # via
    #   aiohttp
    #   yarl
nanotime==0.5.2
    # via dvc
networkx==2.6.3
    # via dvc
packaging==21.3
    # via dvc
pathspec==0.9.0
    # via dvc
phonenumbers==8.12.43
    # via python-benedict
ply==3.11
    # via
    #   dvc
    #   jsonpath-ng
psutil==5.9.0
    # via dvc
pyasn1==0.4.8
    # via
    #   dvc
    #   pyasn1-modules
    #   rsa
pyasn1-modules==0.2.8
    # via google-auth
pycparser==2.21
    # via cffi
pydot==1.4.2
    # via dvc
pygit2==1.9.0
    # via dvc
pygments==2.11.2
    # via rich
pygtrie==2.3.2
    # via dvc
pyparsing==2.4.7
    # via
    #   dvc
    #   grandalf
    #   packaging
    #   pydot
python-benedict==0.25.0
    # via dvc
python-dateutil==2.8.2
    # via
    #   botocore
    #   python-benedict
python-fsutil==0.6.0
    # via python-benedict
python-slugify==6.1.0
    # via python-benedict
pyyaml==6.0
    # via python-benedict
requests==2.27.1
    # via
    #   dvc
    #   python-benedict
rich==11.2.0
    # via dvc
rsa==4.8
    # via google-auth
ruamel-yaml==0.17.21
    # via dvc
ruamel-yaml-clib==0.2.6
    # via ruamel-yaml
s3fs==2021.5.0
    # via dvc
s3transfer==0.3.7
    # via boto3
shortuuid==1.0.8
    # via dvc
shtab==1.5.3
    # via dvc
six==1.16.0
    # via
    #   configobj
    #   flatten-dict
    #   google-api-python-client
    #   google-auth
    #   google-auth-httplib2
    #   jsonpath-ng
    #   python-dateutil
smmap==5.0.0
    # via gitdb
tabulate==0.8.9
    # via dvc
text-unidecode==1.3
    # via python-slugify
toml==0.10.2
    # via
    #   dvc
    #   python-benedict
tqdm==4.62.3
    # via dvc
typing-extensions==4.1.1
    # via
    #   aioitertools
    #   dvc
uritemplate==3.0.1
    # via google-api-python-client
urllib3==1.26.8
    # via
    #   botocore
    #   dulwich
    #   requests
voluptuous==0.12.2
    # via dvc
wcwidth==0.2.5
    # via ftfy
wrapt==1.13.3
    # via aiobotocore
xmltodict==0.12.0
    # via python-benedict
yarl==1.7.2
    # via aiohttp
zc-lockfile==2.0
    # via dvc

# The following packages are considered to be unsafe in a requirements file:
# setuptools

[atugushev]

This has been fixed in #1539 with the backtracking resolver, try pip-compile --resolver backtracking. The resolver is released as part of pip-tools v6.8.0. Please let us know if it doesn't resolve your issue. Thanks!