Backtracking Resolver misses a category of conflict resolutions.

[awwad]

There's a bug relating to the innate order of the recursion in the backtracking resolver. While it resolves most conflicts, it misses a sizeable portion. gerritbot(0.2.0) exemplifies the error.

A dependency of gerritbot adds pbr 0.9.0 to be installed before gerritbot asserts its own dependency on pbr >=0.5 <0.6.
resolver.ConflictingVersionError is raised.

A simplified case:
X(1) depends on B and C, any version
B(1) has no dependencies
B(2) has no dependencies
C(1) depends on B==1

Once possible versions of B and all its dependencies are handled, the selected version of B (B(2) in this case) is set in stone and cannot be backtracked, so no version of C can be installed in this case.

While the algo does manage to resolve a surprising number of conflicts (58% of the 2,862 conflicts that pip fails to correctly resolve from a >200k package scrape of PyPI), this is obviously a substantial bug. Until it's fixed, I won't know how many more of the conflicts are resolvable (17% turn out to be malformed, but the other 35%, which show up as unresolvable, may or may not be.).

The algorithm has to be changed:

Rewrite the core of the backtracker (the high level part - not so long) either using Justin's algorithm (which may have the same bug) or, more likely, this one from semver-resolver.

This will allow it to catch all resolvable conflicts, and therefore categorize resolvable/unresolvable conflicts with certainty.

[awwad]

I have a new algorithm (adapted from this one), but this will have to wait until after I've worked on testing rbtcollins' pip backtracker patch.

[awwad]

There's a workaround that mitigates this problem in some cases (but does not eliminate it).

Here's a particular experiment:

Conclusion: Bigjob(0.64.5) has resolvable dependencies, and Issue 12 caused the resolution to fail, but sorting dependencies both ways allows the resolver to succeed in this case.

Backtracker couldn't find solution to bigjob(0.64.5)

>>> ry.backtracking_satisfy('bigjob(0.64.5)', data.elaborated_dependencies, data.versions_by_package)
Traceback (most recent call last):
  File "/Users/s/w/depresolve/depresolve/resolver/resolvability.py", line 506, in backtracking_satisfy
    _backtracking_satisfy(distkey_to_satisfy, edeps, versions_by_package)
  File "/Users/s/w/depresolve/depresolve/resolver/resolvability.py", line 639, in _backtracking_satisfy
    preexisting_dist_of_this_package)
depresolve.ConflictingVersionError: Dependency of bigjob(0.64.5) on simplejson with specstring <2.1 conflicts with a pre-existing distkey in the list of candidates to install: simplejson(3.8.1)

During handling of the above exception, another exception occurred:

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/Users/s/w/depresolve/depresolve/_external/timeout.py", line 35, in new_f
    result = f(*args, **kwargs)
  File "/Users/s/w/depresolve/depresolve/resolver/resolvability.py", line 513, in backtracking_satisfy
    'dependencies.'), sys.exc_info()[2])
  File "/Users/s/w/depresolve/v3p/lib/python3.5/site-packages/six.py", line 685, in reraise
    raise value.with_traceback(tb)
  File "/Users/s/w/depresolve/depresolve/resolver/resolvability.py", line 506, in backtracking_satisfy
    _backtracking_satisfy(distkey_to_satisfy, edeps, versions_by_package)
  File "/Users/s/w/depresolve/depresolve/resolver/resolvability.py", line 639, in _backtracking_satisfy
    preexisting_dist_of_this_package)
depresolve.UnresolvableConflictError: Unable to find solution to a conflict with one of bigjob(0.64.5)'s immediate dependencies.

Sorted bigjob's immediate dependencies alphabetically:

>>> data.elaborated_dependencies['bigjob(0.64.5)'] = sorted(data.elaborated_dependencies['bigjob(0.64.5)'])

Repeated, to the same result.

Sorted bigjob's immediate dependencies reverse-alphabetically:

>>> data.elaborated_dependencies['bigjob(0.64.5)'] = sorted(data.elaborated_dependencies['bigjob(0.64.5)'], reverse=True)

Repeated backtracking resolution, with success:

>>> ry.backtracking_satisfy('jmbo-neo(0.1)', data.elaborated_dependencies, data.versions_by_package)
['rjsmin(1.0.12)', 'billiard(3.3.0.22)', 'jmbo-analytics(0.2)', 'django-model-utils(2.4)', 'python-mimeparse(0.1.4)', 'django-googlesearch(0.2)', 'django-generate(0.0.6)', 'django-compressor(2.0)', 'django-social-auth(0.7.18)', 'httplib2(0.9.2)', 'jmbo(2.0.12)', 'python-dateutil(2.4.2)', 'pyyaml(3.11)', 'jmbo-neo(0.1)', 'django-sites-groups(0.1.2)', 'django-recaptcha(1.0.5)', 'celery(3.1.20)', 'jmbo-post(2.0.0)', 'south(1.0.2)', 'beautifulsoup(3.2.1)', 'django-category(0.1.3)', 'setuptools(19.6.1)', 'django-tastypie(0.11.1)', 'django-sortedm2m(1.1.1)', 'django-preferences(0.1)', 'lxml(3.5.0)', 'django-publisher(0.0.3)', 'python-openid(2.2.5)', 'django-layers-hr(0.5.1)', 'django-ultracache(0.2)', 'django-photologue(3.1.1)', 'kombu(3.0.33)', 'django-secretballot(0.5.0)', 'django-dfp(0.4.1)', 'django-likes(0.2)', 'six(1.10.0)', 'pillow(3.1.0)', 'django-pagination(1.0.7)', 'django-export(1.0.4)', 'amqp(1.4.9)', 'django-simple-autocomplete(0.5.1)', 'beautifulsoup4(4.4.1)', 'django(1.6.11)', 'rcssmin(1.0.6)', 'jmbo-contact(2.0.0)', 'jellyfish(0.5.1)', 'zope.interface(4.1.3)', 'pyjwt(1.4.0)', 'requests(2.9.1)', 'jmbo-foundry(2.1)', 'django-appconf(1.0.1)', 'django-object-tools(1.1.0)', 'django-celery(3.1.17)', 'django-ckeditor(5.0.3)', 'pytz(2015.7)', 'python-memcached(1.57)', 'anyjson(0.3.3)', 'oauth2(1.9.0.post1)', 'django-snippetscream(0.0.7)']

[awwad]

There are two ways this can fail (aside from the dependencies simply being unresolvable):

1. On the same tier: dependencies on leaf dependency (conflict target) from both alphabetical directions: A has dependencies on B, C, and D. B and D both have dependencies on C. It is not possible to freely choose C before B or D set C in stone.
2. Multiple, complex dependency conflicts.

If I have two dependency libraries, one alpha and one reverse-alpha, and use alpha for one solution run and reverse-alpha for another, that will handle a lot of the missed resolutions (though not those which require alpha order and reverse in the same run - I could do that, too, but this is already complicated enough as a workaround for something that I should just fix by rewriting the code with the new algorithm). Anyway, I think this has a better time complexity than the rewrite will.

[awwad]

Updated stats:
68% resolved
27% supposedly unresolvable
4.3% error during resolve attempt

(Most of the 17% errors had been previously resolved by small bugfixes.)