[Distutils] name of the dependency problem

[Robert Collins]

On 16 April 2015 at 04:52, David Cournapeau <cournape at gmail.com> wrote:
>
>
> On Wed, Apr 15, 2015 at 11:32 AM, Trishank Karthik Kuppusamy
> <trishank at nyu.edu> wrote:
>>
>> On 15 April 2015 at 11:15, David Cournapeau <cournape at gmail.com> wrote:
>>>
>>>
>>> This is indeed the case. If you want to solve dependencies in a way that
>>> works well, you want an index that describes all your available package
>>> versions.
>>>
>>> While solving dependencies is indeed NP complete, they can be fairly fast
>>> in practice because of various specificities : each rule is generally only a
>>> few variables, and the rules have a specific form allowing for more
>>> efficient rule representation (e.g. "at most one of variable", etc...). In
>>> my experience, it is not more difficult than using graph-based algorithms,
>>> and
>>>
>>> FWIW, at Enthought, we are working on a pure python SAT solver for
>>> resolving dependencies, to solve some of those issues. I am actually hacking
>>> on it right at PyCon, we hope to have a first working version end of Q2, at
>>> which point it will be OSS, and reintegrated in my older project depsolver
>>> (https://github.com/enthought/depsolver).
>>>
>>
>> Awesome! Then pip could use that in the near future :)
>
>
> That's the goal. For various reasons, it ended up easier to develop the
> solver within our own package manager enstaller, but once done, extracting
> it as a separate library should not be too hard. It is for example designed
> to support various versioning schemes (for legacy reasons we can't use
> PEP440 just yet).
>
> Regarding speed, initial experiments showed that even for relatively deep
> graphs, the running time is taken outside the SAT solver (e.g. to generate
> the rules, you need to parse the version of every package you want to
> consider, and parsing 1000s of PEP440 versions is slow :) ).

My intent was to use a simple backtracking enhancement to the existing
pip code, because:
 - there is no index of dependencies today
 - many packages have no wheels, so we have to run arbitrary code in a
new process to produce dependency metadata
 - so only considering the versions we have to process seems preferrable.

Are you working on integrating your thing into PIP? My current work
queue is roughly:
- declarative setup_requires and install_requires/extra_requires
support in pip and setuptools
- handling conflicts with already installed packages
(https://github.com/pypa/pip/issues/2687)
- then teach pip how to backtrack

If you're actively working on integrating it into pip, cool.

-Rob

-- 
Robert Collins <rbtcollins at hp.com>
Distinguished Technologist
HP Converged Cloud