pip-compile may not be able to resolve dependencies

[davidovich]

pip-compile can be left with wrong candidates when toplevel requirements happen to be also pinned in subdependencies. This is a regression caused by #378 which indirectly (and subtly) modifies the self.our_constraints set.

Note that in the actual result (pasted below) we see that the resolver is attempting to remove an offending billard, but because we are using groupby() in _group_constraints() which uses a shared iterator, the self.our_constraints gets rewritten with the wrong constraints candidate. In other words the iterator is a kind of view on the elements of self.our_constraints.

Here is a relevant excerpt of a failing compile:

Removed dependencies in this round:
  removing ['billiard', '<3.6.0,>=3.5.0.2', '[]']
  removing ['kombu', '<5.0,>=4.0.2', '[]']
------------------------------------------------------------
Result of round 2: not stable

                          ROUND 3
Current constraints:
  amqp<3.0,>=2.1.4
  billiard<3.4,<3.6.0,>=3.3.0.20,>=3.5.0.2  # this should not have been there.

I have an MCVE, and a PR is coming to fix this.

Steps to replicate

1. make a fake project with a single pinned subdependency (install_requires) (say celery==3.1.18)
2. generate a wheel locally for this fake-project
3. add celery, billiard and fake-project in the requirements.in
4. run pip compile

Expected result

A correctly resolved requirements.txt file.

$ rm -f requirements.txt && pip-compile -vv --rebuild --find-links fake_package/

Configuration:
  -f fake_package/

                          ROUND 1
Current constraints:
  billiard
  celery
  fake-with-deps

Finding the best candidates:
  found candidate billiard==3.5.0.2 (constraint was <any>)
  found candidate celery==4.0.2 (constraint was <any>)
  found candidate fake-with-deps==0.1 (constraint was <any>)

Finding secondary dependencies:
  fake-with-deps==0.1 not in cache, need to check index
  fake-with-deps==0.1       requires celery==3.1.18
  celery==4.0.2 not in cache, need to check index
  celery==4.0.2             requires billiard<3.6.0,>=3.5.0.2, kombu<5.0,>=4.0.2, pytz>dev
  billiard==3.5.0.2 not in cache, need to check index
  billiard==3.5.0.2         requires -

New dependencies found in this round:
  adding ['billiard', '<3.6.0,>=3.5.0.2', '[]']
  adding ['celery', '==3.1.18', '[]']
  adding ['kombu', '<5.0,>=4.0.2', '[]']
  adding ['pytz', '>dev', '[]']
Removed dependencies in this round:
------------------------------------------------------------
Result of round 1: not stable

                          ROUND 2
Current constraints:
  billiard<3.6.0,>=3.5.0.2
  celery==3.1.18
  fake-with-deps
  kombu<5.0,>=4.0.2
  pytz>dev

Finding the best candidates:
  found candidate billiard==3.5.0.2 (constraint was >=3.5.0.2,<3.6.0)
  found candidate celery==3.1.18 (constraint was ==3.1.18)
  found candidate fake-with-deps==0.1 (constraint was <any>)
  found candidate kombu==4.0.2 (constraint was >=4.0.2,<5.0)
  found candidate pytz==2016.10 (constraint was >dev)

Finding secondary dependencies:
  pytz==2016.10 not in cache, need to check index
  pytz==2016.10             requires -
  kombu==4.0.2 not in cache, need to check index
  kombu==4.0.2              requires amqp<3.0,>=2.1.4
  billiard==3.5.0.2         requires -
  fake-with-deps==0.1       requires celery==3.1.18
  celery==3.1.18 not in cache, need to check index
  celery==3.1.18            requires billiard<3.4,>=3.3.0.20, kombu<3.1,>=3.0.25, pytz>dev

New dependencies found in this round:
  adding ['amqp', '<3.0,>=2.1.4', '[]']
  adding ['billiard', '<3.4,>=3.3.0.20', '[]']
  adding ['kombu', '<3.1,>=3.0.25', '[]']
Removed dependencies in this round:
  removing ['billiard', '<3.6.0,>=3.5.0.2', '[]']
  removing ['kombu', '<5.0,>=4.0.2', '[]']
------------------------------------------------------------
Result of round 2: not stable

                          ROUND 3
Current constraints:
  amqp<3.0,>=2.1.4
  billiard<3.4,>=3.3.0.20
  celery==3.1.18
  fake-with-deps
  kombu<3.1,>=3.0.25
  pytz>dev

Finding the best candidates:
  found candidate amqp==2.1.4 (constraint was >=2.1.4,<3.0)
  found candidate billiard==3.3.0.23 (constraint was >=3.3.0.20,<3.4)
  found candidate celery==3.1.18 (constraint was ==3.1.18)
  found candidate fake-with-deps==0.1 (constraint was <any>)
  found candidate kombu==3.0.37 (constraint was >=3.0.25,<3.1)
  found candidate pytz==2016.10 (constraint was >dev)

Finding secondary dependencies:
  pytz==2016.10             requires -
  kombu==3.0.37 not in cache, need to check index
  kombu==3.0.37             requires amqp<2.0,>=1.4.9, anyjson>=0.3.3
  billiard==3.3.0.23 not in cache, need to check index
  billiard==3.3.0.23        requires -
  fake-with-deps==0.1       requires celery==3.1.18
  amqp==2.1.4 not in cache, need to check index
  amqp==2.1.4               requires vine>=1.1.3
  celery==3.1.18            requires billiard<3.4,>=3.3.0.20, kombu<3.1,>=3.0.25, pytz>dev

New dependencies found in this round:
  adding ['amqp', '<2.0,>=1.4.9', '[]']
  adding ['anyjson', '>=0.3.3', '[]']
  adding ['vine', '>=1.1.3', '[]']
Removed dependencies in this round:
  removing ['amqp', '<3.0,>=2.1.4', '[]']
------------------------------------------------------------
Result of round 3: not stable

                          ROUND 4
Current constraints:
  amqp<2.0,>=1.4.9
  anyjson>=0.3.3
  billiard<3.4,>=3.3.0.20
  celery==3.1.18
  fake-with-deps
  kombu<3.1,>=3.0.25
  pytz>dev
  vine>=1.1.3

Finding the best candidates:
  found candidate amqp==1.4.9 (constraint was >=1.4.9,<2.0)
  found candidate anyjson==0.3.3 (constraint was >=0.3.3)
  found candidate billiard==3.3.0.23 (constraint was >=3.3.0.20,<3.4)
  found candidate celery==3.1.18 (constraint was ==3.1.18)
  found candidate fake-with-deps==0.1 (constraint was <any>)
  found candidate kombu==3.0.37 (constraint was >=3.0.25,<3.1)
  found candidate pytz==2016.10 (constraint was >dev)
  found candidate vine==1.1.3 (constraint was >=1.1.3)

Finding secondary dependencies:
  pytz==2016.10             requires -
  celery==3.1.18            requires billiard<3.4,>=3.3.0.20, kombu<3.1,>=3.0.25, pytz>dev
  amqp==1.4.9 not in cache, need to check index
  amqp==1.4.9               requires -
  fake-with-deps==0.1       requires celery==3.1.18
  kombu==3.0.37             requires amqp<2.0,>=1.4.9, anyjson>=0.3.3
  vine==1.1.3 not in cache, need to check index
  vine==1.1.3               requires -
  billiard==3.3.0.23        requires -
  anyjson==0.3.3 not in cache, need to check index
  anyjson==0.3.3            requires -

New dependencies found in this round:
Removed dependencies in this round:
  removing ['vine', '>=1.1.3', '[]']
------------------------------------------------------------
Result of round 4: not stable

                          ROUND 5
Current constraints:
  amqp<2.0,>=1.4.9
  anyjson>=0.3.3
  billiard<3.4,>=3.3.0.20
  celery==3.1.18
  fake-with-deps
  kombu<3.1,>=3.0.25
  pytz>dev

Finding the best candidates:
  found candidate amqp==1.4.9 (constraint was >=1.4.9,<2.0)
  found candidate anyjson==0.3.3 (constraint was >=0.3.3)
  found candidate billiard==3.3.0.23 (constraint was >=3.3.0.20,<3.4)
  found candidate celery==3.1.18 (constraint was ==3.1.18)
  found candidate fake-with-deps==0.1 (constraint was <any>)
  found candidate kombu==3.0.37 (constraint was >=3.0.25,<3.1)
  found candidate pytz==2016.10 (constraint was >dev)

Finding secondary dependencies:
  billiard==3.3.0.23        requires -
  celery==3.1.18            requires billiard<3.4,>=3.3.0.20, kombu<3.1,>=3.0.25, pytz>dev
  anyjson==0.3.3            requires -
  kombu==3.0.37             requires amqp<2.0,>=1.4.9, anyjson>=0.3.3
  fake-with-deps==0.1       requires celery==3.1.18
  pytz==2016.10             requires -
  amqp==1.4.9               requires -
------------------------------------------------------------
Result of round 5: stable, done

#
# This file is autogenerated by pip-compile
# To update, run:
#
#    pip-compile --output-file requirements.txt requirements.in
#

amqp==1.4.9               # via kombu
anyjson==0.3.3            # via kombu
billiard==3.3.0.23
celery==3.1.18
fake-with-deps==0.1
kombu==3.0.37             # via celery
pytz==2016.10             # via celery

Actual result

pip-compile fails to return a stable solution:

$ rm -f requirements.txt && pip-compile -vv --rebuild --find-links fake_package/

Configuration:
  -f fake_package/

                          ROUND 1
Current constraints:
  billiard
  celery
  fake-with-deps

Finding the best candidates:
  found candidate billiard==3.5.0.2 (constraint was <any>)
  found candidate celery==4.0.2 (constraint was <any>)
  found candidate fake-with-deps==0.1 (constraint was <any>)

Finding secondary dependencies:
  celery==4.0.2 not in cache, need to check index
  celery==4.0.2             requires billiard<3.6.0,>=3.5.0.2, kombu<5.0,>=4.0.2, pytz>dev
  fake-with-deps==0.1 not in cache, need to check index
  fake-with-deps==0.1       requires celery==3.1.18
  billiard==3.5.0.2 not in cache, need to check index
  billiard==3.5.0.2         requires -

New dependencies found in this round:
  adding ['billiard', '<3.6.0,>=3.5.0.2', '[]']
  adding ['celery', '==3.1.18', '[]']
  adding ['kombu', '<5.0,>=4.0.2', '[]']
  adding ['pytz', '>dev', '[]']
Removed dependencies in this round:
------------------------------------------------------------
Result of round 1: not stable

                          ROUND 2
Current constraints:
  billiard<3.6.0,>=3.5.0.2
  celery==3.1.18
  fake-with-deps
  kombu<5.0,>=4.0.2
  pytz>dev

Finding the best candidates:
  found candidate billiard==3.5.0.2 (constraint was >=3.5.0.2,<3.6.0)
  found candidate celery==3.1.18 (constraint was ==3.1.18)
  found candidate fake-with-deps==0.1 (constraint was <any>)
  found candidate kombu==4.0.2 (constraint was >=4.0.2,<5.0)
  found candidate pytz==2016.10 (constraint was >dev)

Finding secondary dependencies:
  pytz==2016.10 not in cache, need to check index
  pytz==2016.10             requires -
  celery==3.1.18 not in cache, need to check index
  celery==3.1.18            requires billiard<3.4,>=3.3.0.20, kombu<3.1,>=3.0.25, pytz>dev
  kombu==4.0.2 not in cache, need to check index
  kombu==4.0.2              requires amqp<3.0,>=2.1.4
  billiard==3.5.0.2         requires -
  fake-with-deps==0.1       requires celery==3.1.18

New dependencies found in this round:
  adding ['amqp', '<3.0,>=2.1.4', '[]']
  adding ['billiard', '<3.4,>=3.3.0.20', '[]']
  adding ['kombu', '<3.1,>=3.0.25', '[]']
Removed dependencies in this round:
  removing ['billiard', '<3.6.0,>=3.5.0.2', '[]']
  removing ['kombu', '<5.0,>=4.0.2', '[]']
------------------------------------------------------------
Result of round 2: not stable

                          ROUND 3
Current constraints:
  amqp<3.0,>=2.1.4
  billiard<3.4,<3.6.0,>=3.3.0.20,>=3.5.0.2
  celery==3.1.18 from https://our_in_house_pypi.org/root/pypi/+f/692/453eb7257cc7b/celery-3.1.18-py2.py3-none-any.whl#md5=692453eb7257cc7b70b538fb3fc2f395
  fake-with-deps
  kombu<3.1,>=3.0.25
  pytz>dev

Finding the best candidates:
  found candidate amqp==2.1.4 (constraint was >=2.1.4,<3.0)
Could not find a version that matches billiard<3.4,<3.6.0,>=3.3.0.20,>=3.5.0.2
Tried: 0.1.0, 0.2.0, 0.2.1, 0.2.2, 0.2.3, 0.3.0, 0.3.1, 2.7.3.0, 2.7.3.1, 2.7.3.2, 2.7.3.3, 2.7.3.4, 2.7.3.5, 2.7.3.6, 2.7.3.7, 2.7.3.8, 2.7.3.9, 2.7.3.10, 2.7.3.11, 2.7.3.12, 2.7.3.13, 2.7.3.14, 2.7.3.15, 2.7.3.16, 2.7.3.17, 2.7.3.18, 2.7.3.19, 2.7.3.20, 2.7.3.21, 2.7.3.22, 2.7.3.23, 2.7.3.24, 2.7.3.25, 2.7.3.26, 2.7.3.27, 2.7.3.28, 2.7.3.30, 2.7.3.31, 2.7.3.32, 2.7.3.33, 2.7.3.34, 3.3.0.0, 3.3.0.1, 3.3.0.2, 3.3.0.3, 3.3.0.4, 3.3.0.5, 3.3.0.6, 3.3.0.7, 3.3.0.8, 3.3.0.9, 3.3.0.10, 3.3.0.11, 3.3.0.12, 3.3.0.13, 3.3.0.14, 3.3.0.15, 3.3.0.16, 3.3.0.17, 3.3.0.17, 3.3.0.18, 3.3.0.19, 3.3.0.20, 3.3.0.20, 3.3.0.21, 3.3.0.21, 3.3.0.22, 3.3.0.22, 3.3.0.23, 3.3.0.23, 3.5.0.0rc2, 3.5.0.0, 3.5.0.1, 3.5.0.2, 3.5.0.2

[davidovich]

Please note that #378 was NOT the feature that added the regression. I believe this bug was present since the introduction of groupby().

Sorry for the wrong deduction.