From the discussion on https://github.com/pypa/pip/issues/988#issuecomment-279033079:

- https://github.com/ContinuumIO/pycosat (picosat) - https://github.com/ContinuumIO/pycosat/blob/master/pycosat.c (C) - https://github.com/ContinuumIO/pycosat/blob/master/picosat.c - https://github.com/ContinuumIO/pycosat/tree/master/examples - https://github.com/enthought/sat-solver (MiniSat) - https://github.com/enthought/sat-solver/tree/master/simplesat/tests - https://github.com/enthought/sat-solver/blob/master/requirements.txt (PyYAML, enum34) Is there a better way than SAT? On Fri, Feb 10, 2017 at 12:20 PM, Pradyun Gedam <pradyunsg@gmail.com> wrote:

Yay! Thank you so much for a prompt and positive response! I'm pretty excited and looking forward to this.

On Thu, Feb 9, 2017, 20:23 Donald Stufft <donald@stufft.io> wrote:

I’ve never done it before, but I’m happy to provide mentoring on this.

On Feb 8, 2017, at 9:15 PM, Pradyun Gedam <pradyunsg@gmail.com> wrote:

Hello Everyone!

Ralf Gommers suggested that I put this proposal here on this list, for feedback and for seeing if anyone would be willing to mentor me. So, here it is.

-----

My name is Pradyun Gedam. I'm currently a first year student VIT University in India.

I would like to apply for GSoC 2017 under PSF.

I currently have a project in mind - the "pip needs a dependency resolver" issue [1]. I would like to take on this specific project but am willing to do some other project as well.

For some background, around mid 2016, I started contributing to pip. The first issue I tackled was #59 [2] - a request for upgrade command and an upgrade-all command that has been open for over 5.5 years. Over the months following that, I've have had the opportunity to work with and understand multiple parts of pip's codebase while working on this issue and a few others. This search on GitHub issues [3] also provides a good summary of what work I've done on pip.

[2]: https://github.com/pypa/pip/issues/988 [2]: https://github.com/pypa/pip/issues/59 [3]: https://github.com/pypa/pip/issues?q=author%3Apradyunsg

Eagerly-waiting-for-a-response-ly, Pradyun Gedam

_______________________________________________ Distutils-SIG maillist - Distutils-SIG@python.org https://mail.python.org/mailman/listinfo/distutils-sig

—

Donald Stufft

_______________________________________________ Distutils-SIG maillist - Distutils-SIG@python.org https://mail.python.org/mailman/listinfo/distutils-sig

While there may be some clever way of delivering changes to dependency metadata that consumes less bandwidth (The first delivery for a client will be somewhat large, but versioned metadata information plus compressed deltas could move clients from one version of the full metadata set to another, for example?), the larger problem, I think, is the lack of fixed dependencies. Even with a moderately small percentage of distributions having variable immediate dependencies, this expands out substantially when you consider all distributions that depend on those and so on, meaning that the full set of installed distributions when you run `pip install xyz==a.b.c` is surprisingly variable. In a series of install attempts run over about 400,000 of the package versions on PyPI last year, I found that simply changing the version of Python employed in an otherwise identical virtual environment results in pip installing different packages or package versions, for 16% of the distributions. If dependencies were knowable in static metadata, there would be a decent case for SAT solving. I'll try to get back to a write-up after the current rush on my main project subsides. On Fri, Feb 10, 2017 at 2:34 PM Justin Cappos <jcappos@nyu.edu> wrote:

Yes, don't use a SAT solver. It requires all metadata from all packages (~30MB uncompressed) and gives hard to predict results in some cases. Also the lack of fixed dependencies is a substantial problem for a SAT solver. Overall, we think it makes more sense to use a simple backtracking dependency resolution algorithm.

Sebastien Awwad (CCed) has been looking at a bunch of data around the speed and other tradeoffs of the different algos. Sebastien: Sometime next week, can you write it up in a way that is suitable for sharing?

Justin

On Fri, Feb 10, 2017 at 1:59 PM, Wes Turner <wes.turner@gmail.com> wrote:

From the discussion on https://github.com/pypa/pip/issues/988#issuecomment-279033079:

- https://github.com/ContinuumIO/pycosat (picosat) - https://github.com/ContinuumIO/pycosat/blob/master/pycosat.c (C) - https://github.com/ContinuumIO/pycosat/blob/master/picosat.c - https://github.com/ContinuumIO/pycosat/tree/master/examples - https://github.com/enthought/sat-solver (MiniSat) - https://github.com/enthought/sat-solver/tree/master/simplesat/tests - https://github.com/enthought/sat-solver/blob/master/requirements.txt (PyYAML, enum34)

Is there a better way than SAT?

On Fri, Feb 10, 2017 at 12:20 PM, Pradyun Gedam <pradyunsg@gmail.com> wrote:

Yay! Thank you so much for a prompt and positive response! I'm pretty excited and looking forward to this.

On Thu, Feb 9, 2017, 20:23 Donald Stufft <donald@stufft.io> wrote:

I’ve never done it before, but I’m happy to provide mentoring on this.

On Feb 8, 2017, at 9:15 PM, Pradyun Gedam <pradyunsg@gmail.com> wrote:

Hello Everyone!

Ralf Gommers suggested that I put this proposal here on this list, for feedback and for seeing if anyone would be willing to mentor me. So, here it is.

-----

My name is Pradyun Gedam. I'm currently a first year student VIT University in India.

I would like to apply for GSoC 2017 under PSF.

I currently have a project in mind - the "pip needs a dependency resolver" issue [1]. I would like to take on this specific project but am willing to do some other project as well.

For some background, around mid 2016, I started contributing to pip. The first issue I tackled was #59 [2] - a request for upgrade command and an upgrade-all command that has been open for over 5.5 years. Over the months following that, I've have had the opportunity to work with and understand multiple parts of pip's codebase while working on this issue and a few others. This search on GitHub issues [3] also provides a good summary of what work I've done on pip.

[2]: https://github.com/pypa/pip/issues/988 [2]: https://github.com/pypa/pip/issues/59 [3]: https://github.com/pypa/pip/issues?q=author%3Apradyunsg

Eagerly-waiting-for-a-response-ly, Pradyun Gedam

_______________________________________________ Distutils-SIG maillist - Distutils-SIG@python.org https://mail.python.org/mailman/listinfo/distutils-sig

—

Donald Stufft

_______________________________________________ Distutils-SIG maillist - Distutils-SIG@python.org https://mail.python.org/mailman/listinfo/distutils-sig

_______________________________________________ Distutils-SIG maillist - Distutils-SIG@python.org https://mail.python.org/mailman/listinfo/distutils-sig

I think the difference Sebastien is trying to say is that you need info from *all* pieces of static metadata. Not just that from the packages you will end up installing. Backtracking dependency resolution will be much more like the wheel model. If one does not backtrack (which is true most of the time), it only needs the metadata from the things you end up install. Justin On Fri, Feb 10, 2017 at 4:36 PM, Donald Stufft <donald@stufft.io> wrote:

On Feb 10, 2017, at 2:53 PM, Sebastien Awwad <sebastienawwad@gmail.com> wrote:

If dependencies were knowable in static metadata, there would be a decent case for SAT solving. I'll try to get back to a write-up after the current rush on my main project subsides.

The differences between backtracking and SAT solvers and such is perhaps a bit of of my depth, but just FWIW when installing from Wheel it’s basically just waiting on a new API to get this information in a static form. Installing from sdist still has the problem (and likely will forever) but I think it’s not *unreasonable* to say that using wheels is what you need to do to get fast dep solving and if people aren’t providing wheels it will be slow(er?).

— Donald Stufft

Hi all, Assuming that all the requirements are wheels and coming from PyPI. Installed using a recent pip. How often do you think the resolution will be the same for all clients, and mostly be "pull everything from latest" ? If so, would it make sense to pre-compute thing on PyPI/warehouse at package publication time, and provide a resolution "hint" as an API endpoint ? If this "hint" is correct, it should avoid clientside work most of time. And the resolution can probably be efficiently updated as you only have to re-solve by looking as the dependees of previous version. -- M On Fri, Feb 10, 2017 at 1:36 PM, Donald Stufft <donald@stufft.io> wrote:

On Feb 10, 2017, at 2:53 PM, Sebastien Awwad <sebastienawwad@gmail.com> wrote:

If dependencies were knowable in static metadata, there would be a decent case for SAT solving. I'll try to get back to a write-up after the current rush on my main project subsides.

The differences between backtracking and SAT solvers and such is perhaps a bit of of my depth, but just FWIW when installing from Wheel it’s basically just waiting on a new API to get this information in a static form. Installing from sdist still has the problem (and likely will forever) but I think it’s not *unreasonable* to say that using wheels is what you need to do to get fast dep solving and if people aren’t providing wheels it will be slow(er?).

— Donald Stufft

_______________________________________________ Distutils-SIG maillist - Distutils-SIG@python.org https://mail.python.org/mailman/listinfo/distutils-sig

On Fri, Feb 10, 2017 at 2:33 PM, Justin Cappos <jcappos@nyu.edu> wrote:

Yes, don't use a SAT solver. It requires all metadata from all packages (~30MB uncompressed) and gives hard to predict results in some cases.

I doubt there exists an algorithm where this is not the case. Also the lack of fixed dependencies is a substantial problem for a SAT

solver. Overall, we think it makes more sense to use a simple backtracking dependency resolution algorithm.

As soon as you want to deal with version ranges and ensure consistency of the installed packages, backtracking stops being simple rather quickly. I agree lack of fixed dependencies is an issue, but I doubt it is specific to a SAT solver. SAT solvers have been used successfully in many cases now: composer (php), dnf (Red Hat/Fedora), conda or our own packages manager at Enthought in python, 0install. I would certainly be interested in seeing a proper comparison with other algorithms. David

Sebastien Awwad (CCed) has been looking at a bunch of data around the speed and other tradeoffs of the different algos. Sebastien: Sometime next week, can you write it up in a way that is suitable for sharing?

Justin

On Fri, Feb 10, 2017 at 1:59 PM, Wes Turner <wes.turner@gmail.com> wrote:

...

From the discussion on https://github.com/pypa/pip/is sues/988#issuecomment-279033079:

- https://github.com/ContinuumIO/pycosat (picosat) - https://github.com/ContinuumIO/pycosat/blob/master/pycosat.c (C) - https://github.com/ContinuumIO/pycosat/blob/master/picosat.c - https://github.com/ContinuumIO/pycosat/tree/master/examples - https://github.com/enthought/sat-solver (MiniSat) - https://github.com/enthought/sat-solver/tree/master/simplesa t/tests - https://github.com/enthought/sat-solver/blob/master/requirem ents.txt (PyYAML, enum34)

Is there a better way than SAT?

On Fri, Feb 10, 2017 at 12:20 PM, Pradyun Gedam <pradyunsg@gmail.com> wrote:

...

Yay! Thank you so much for a prompt and positive response! I'm pretty excited and looking forward to this.

On Thu, Feb 9, 2017, 20:23 Donald Stufft <donald@stufft.io> wrote:

I’ve never done it before, but I’m happy to provide mentoring on this.

On Feb 8, 2017, at 9:15 PM, Pradyun Gedam <pradyunsg@gmail.com> wrote:

Hello Everyone!

Ralf Gommers suggested that I put this proposal here on this list, for feedback and for seeing if anyone would be willing to mentor me. So, here it is.

-----

My name is Pradyun Gedam. I'm currently a first year student VIT University in India.

I would like to apply for GSoC 2017 under PSF.

I currently have a project in mind - the "pip needs a dependency resolver" issue [1]. I would like to take on this specific project but am willing to do some other project as well.

For some background, around mid 2016, I started contributing to pip. The first issue I tackled was #59 [2] - a request for upgrade command and an upgrade-all command that has been open for over 5.5 years. Over the months following that, I've have had the opportunity to work with and understand multiple parts of pip's codebase while working on this issue and a few others. This search on GitHub issues [3] also provides a good summary of what work I've done on pip.

[2]: https://github.com/pypa/pip/issues/988 [2]: https://github.com/pypa/pip/issues/59 [3]: https://github.com/pypa/pip/issues?q=author%3Apradyunsg

Eagerly-waiting-for-a-response-ly, Pradyun Gedam

_______________________________________________ Distutils-SIG maillist - Distutils-SIG@python.org https://mail.python.org/mailman/listinfo/distutils-sig

—

Donald Stufft

_______________________________________________ Distutils-SIG maillist - Distutils-SIG@python.org https://mail.python.org/mailman/listinfo/distutils-sig

_______________________________________________ Distutils-SIG maillist - Distutils-SIG@python.org https://mail.python.org/mailman/listinfo/distutils-sig

_______________________________________________ Distutils-SIG maillist - Distutils-SIG@python.org https://mail.python.org/mailman/listinfo/distutils-sig

So, there aren't "heuristics" to tweak here. The algorithm just encodes the rules for trying package combinations (usually, latest version first) and then backtracks to a previous point when an unresolvable conflict is found. This is quite different from something like a SAT solver where it does use heuristics to come up with a matching scenario quickly. I don't think developers need to tweak heuristics in either case. You just pick your SAT solver and it has reasonable heuristics built in, right? Thanks, Justin On Fri, Feb 10, 2017 at 4:03 PM, David Cournapeau <cournape@gmail.com> wrote:

On Fri, Feb 10, 2017 at 3:52 PM, David Cournapeau <cournape@gmail.com> wrote:

...

On Fri, Feb 10, 2017 at 2:33 PM, Justin Cappos <jcappos@nyu.edu> wrote:

...

Yes, don't use a SAT solver. It requires all metadata from all packages (~30MB uncompressed) and gives hard to predict results in some cases.

I doubt there exists an algorithm where this is not the case.

Also the lack of fixed dependencies is a substantial problem for a SAT

...

solver. Overall, we think it makes more sense to use a simple backtracking dependency resolution algorithm.

As soon as you want to deal with version ranges and ensure consistency of the installed packages, backtracking stops being simple rather quickly.

I agree lack of fixed dependencies is an issue, but I doubt it is specific to a SAT solver. SAT solvers have been used successfully in many cases now: composer (php), dnf (Red Hat/Fedora), conda or our own packages manager at Enthought in python, 0install.

I would certainly be interested in seeing a proper comparison with other algorithms.

I don't have experience implementing non SAT dependency solvers, but I suspect that whatever algorithm you end up using, the "core" is the simple part, and tweaking heuristics will be the hard, developer-time consuming part.

David

...

David

...

Sebastien Awwad (CCed) has been looking at a bunch of data around the speed and other tradeoffs of the different algos. Sebastien: Sometime next week, can you write it up in a way that is suitable for sharing?

Justin

On Fri, Feb 10, 2017 at 1:59 PM, Wes Turner <wes.turner@gmail.com> wrote:

...

From the discussion on https://github.com/pypa/pip/is sues/988#issuecomment-279033079:

- https://github.com/ContinuumIO/pycosat (picosat) - https://github.com/ContinuumIO/pycosat/blob/master/pycosat.c (C) - https://github.com/ContinuumIO/pycosat/blob/master/picosat.c - https://github.com/ContinuumIO/pycosat/tree/master/examples - https://github.com/enthought/sat-solver (MiniSat) - https://github.com/enthought/sat-solver/tree/master/simplesa t/tests - https://github.com/enthought/sat-solver/blob/master/requirem ents.txt (PyYAML, enum34)

Is there a better way than SAT?

On Fri, Feb 10, 2017 at 12:20 PM, Pradyun Gedam <pradyunsg@gmail.com> wrote:

...

Yay! Thank you so much for a prompt and positive response! I'm pretty excited and looking forward to this.

On Thu, Feb 9, 2017, 20:23 Donald Stufft <donald@stufft.io> wrote:

I’ve never done it before, but I’m happy to provide mentoring on this.

On Feb 8, 2017, at 9:15 PM, Pradyun Gedam <pradyunsg@gmail.com> wrote:

Hello Everyone!

Ralf Gommers suggested that I put this proposal here on this list, for feedback and for seeing if anyone would be willing to mentor me. So, here it is.

-----

My name is Pradyun Gedam. I'm currently a first year student VIT University in India.

I would like to apply for GSoC 2017 under PSF.

I currently have a project in mind - the "pip needs a dependency resolver" issue [1]. I would like to take on this specific project but am willing to do some other project as well.

For some background, around mid 2016, I started contributing to pip. The first issue I tackled was #59 [2] - a request for upgrade command and an upgrade-all command that has been open for over 5.5 years. Over the months following that, I've have had the opportunity to work with and understand multiple parts of pip's codebase while working on this issue and a few others. This search on GitHub issues [3] also provides a good summary of what work I've done on pip.

[2]: https://github.com/pypa/pip/issues/988 [2]: https://github.com/pypa/pip/issues/59 [3]: https://github.com/pypa/pip/issues?q=author%3Apradyunsg

Eagerly-waiting-for-a-response-ly, Pradyun Gedam

_______________________________________________ Distutils-SIG maillist - Distutils-SIG@python.org https://mail.python.org/mailman/listinfo/distutils-sig

—

Donald Stufft

_______________________________________________ Distutils-SIG maillist - Distutils-SIG@python.org https://mail.python.org/mailman/listinfo/distutils-sig

_______________________________________________ Distutils-SIG maillist - Distutils-SIG@python.org https://mail.python.org/mailman/listinfo/distutils-sig

_______________________________________________ Distutils-SIG maillist - Distutils-SIG@python.org https://mail.python.org/mailman/listinfo/distutils-sig

On Fri, Feb 10, 2017 at 3:52 PM, David Cournapeau <cournape@gmail.com> wrote:

On Fri, Feb 10, 2017 at 2:33 PM, Justin Cappos <jcappos@nyu.edu> wrote:

...

Yes, don't use a SAT solver. It requires all metadata from all packages (~30MB uncompressed) and gives hard to predict results in some cases.

I doubt there exists an algorithm where this is not the case.

Okay, so there was a discussion about the pros and cons (including algorithms like backtracking dependency resolution which do not require all metadata) a while back on the mailing list: https://mail.python.org/pipermail/distutils-sig/2015-April/026157.html (I believe you may have seen this before because you replied to a message further down in the thread.)

Also the lack of fixed dependencies is a substantial problem for a SAT

...

solver. Overall, we think it makes more sense to use a simple backtracking dependency resolution algorithm.

As soon as you want to deal with version ranges and ensure consistency of the installed packages, backtracking stops being simple rather quickly.

Can you explain why you think this is true? I agree lack of fixed dependencies is an issue, but I doubt it is specific

to a SAT solver. SAT solvers have been used successfully in many cases now: composer (php), dnf (Red Hat/Fedora), conda or our own packages manager at Enthought in python, 0install.

I would certainly be interested in seeing a proper comparison with other algorithms.

Sure, there are different tradeoffs which make sense in different domains. Certainly, if you have a relatively small set of packages with statically defined dependencies and already are distributing all package metadata to clients, a SAT solver will be faster at resolving complex dependency issues. We can provide the data we gathered (maybe others provide get some data too?) and then the discussion will be more grounded with numbers. Thanks, Justin