[This looks like a bug report against PIP because Tarek told me distutils2 would be responsible for this kind of thing and that there was an open ticket for it.  However, I can't find any such ticket so I'm posting it here]

Not only does pip not check for conflicts as noted in http://bitbucket.org/ianb/pip/src/tip/pip/req.py#cl-928, it doesn't consider any requirements on a package other than the first. So if I have

A requires B and C
B requires D<=1.1
C requires D<=0.9

installing A will give us D==1.1 rather than D==0.9

Once responsibility for this functionality is sorted out, we may be able to close this ticket or http://bitbucket.org/ianb/pip/issue/119

Josip has written a depgraph module at the beginning of this GSoC. It is now in the main distutils2 repository. The documentation Josip wrote can be seen at http://distutils2.notmyidea.org/depgraph.html

I haven’t had time to see how the module handles the problem you’re raising. Can you maybe test it? Josip, can you comment?

I'm not sure the change of title you made is appropriate.  The case I described isn't a conflict, in the sense that there is a version of D that satisfies everybody's requirements.

Maybe the real title should be something like "exhaustively or comprehensively test dependency resolution."

Oh, and http://distutils2.notmyidea.org/depgraph.html is a 404 for me.

Re: title, I don’t know how to phrase it best.  What exactly is the behavior you request?  I put “handle” as in “do the right thing”, that is, “don’t install the newest version but the one that satisfies all predicates”.  I softened “conflicts” to “incompatibilities”, does it work for you?  In any case, the important thing is that your report describes the problem well.

Re: 404, it has moved to http://distutils2.notmyidea.org/library/distutils2.depgraph.html

As discussed on the Fellowship ML, ActiveState has implemented an algo for a smart dependency graph: https://github.com/ActiveState/depgraph

On the one hand, I think it’s not outside the scope of packaging.depgraph to be a bit smarter about dependencies.  On the other hand, this is still a deep research subject that’s by no means solved, so maybe keeping depgraph simple and dumb is more maintainable.

The only way to fix this is to /not/ install *any* packages prior to resolving *all* dependencies ... which means that there needs to be a way to resolve the entire dependency graph for any given package in PyPI.

If PyPI provided a mechanism to fetch the entire dependency graph[1], then https://github.com/ActiveState/depgraph can be used to implement comprehensive dependency resolution. PyPM can do this because the PyPM repository provides a sqlite db containing dependency information for all packages and their versions.

Let me know if you need any assistance regarding ActiveState's depgraph implementation (I may have pending commits to be merged to the GitHub repo)

[1] I posted a few suggestions in regards to facilitating such exposure of static metadata in PyPI to distutils-sig@ - but until this day they remain as merely ideas.

> The only way to fix this is to /not/ install *any* packages prior to
> resolving *all* dependencies

packaging.install rolls back in case of error, so the system can’t be left in a half-installed state.  p7g.install is only as smart as p7g.depgraph, however.

> which means that there needs to be a way to resolve the entire
> dependency graph for any given package in PyPI.

PyPI exposes requires, obsoletes and provides for releases that upload PEP 345 metadata; client code using p7g.pypi and p7g.depgraph can then build a dependency graph.

> the PyPM repository provides a sqlite db containing dependency
> information for all packages and their versions.

This experiment with a local copy of the full repo graph is interesting.  Do you have blog posts or something talking about synchronization issues, dealing with multiple repositories, using SQL vs. something less ugly <wink>, etc.?

> Let me know if you need any assistance regarding ActiveState's
> depgraph implementation

First, what we need here is a pronouncement from Tarek about smarter depgraph vs. simple stupid depgraph.  If we decide to improve depgraph, ideas from your code will have to be extracted and ported.  This will probably require a contributor agreement.

On 2011-06-07, at 9:48 AM, Éric Araujo wrote:

> 
> Éric Araujo <merwok@netwok.org> added the comment:
> 
>> The only way to fix this is to /not/ install *any* packages prior to
>> resolving *all* dependencies
> 
> packaging.install rolls back in case of error, so the system can’t be left in a half-installed state.  p7g.install is only as smart as p7g.depgraph, however.

Well, if the same behavior is adopted for dependency conflicts (eg: see issue description) as well, it would necessitate rolling back by uninstalling the previous N packages, then installing these N packages (again) by traversing a different path (and repeat for other conflicts), would it not?

>> which means that there needs to be a way to resolve the entire
>> dependency graph for any given package in PyPI.
> 
> PyPI exposes requires, obsoletes and provides for releases that upload PEP 345 metadata; client code using p7g.pypi and p7g.depgraph can then build a dependency graph.

Not all packages upload their release sources (thus metadata) to PyPI, which is why - I believe - PIP is scraping the Simple Index and home_page urls to get the appropriate sdist for any package. I am not fully aware of what kind of packages p7g.install is supposed to support, though. I assume that setuptools-style projects (using install_requires) are not supported by p7g.install.

>> the PyPM repository provides a sqlite db containing dependency
>> information for all packages and their versions.
> 
> This experiment with a local copy of the full repo graph is interesting.  Do you have blog posts or something talking about synchronization issues, dealing with multiple repositories, using SQL vs. something less ugly <wink>, etc.?

The local index cache is automatically updated not more than once a day. Multiple repositories are searched in the configured order (linearly). SQL is just a data format, the remote index can be of any format (xml, json, pickle, ..) as long as the client can easily query the dependency chain.

But its probably much simpler to only expose per-package dependency (and other metadata) through REST urls (at the cost of network delays, however). No index is required. Eg:

    http://pypi.python.org/metadata/scipy/0.9.0/DIST-INFO -> requires, obsoletes, etc...

(of course, this assumes that even packages that do not upload their sdists have the metadata available in PyPI somehow; perhaps the server caches them. we have our own pypi-like mirror that does this)

Tarek’s reply on IRC:

> I think we should make it dumb: in case of a conflict, it's always
> better/simpler to let the user deal with it.  A simple "could not
> install because you have package X version Y installed'.  Trying to do
> something smarter is very very hard and will probably fail.

About adding smarts to deal with simple cases like the one you mentioned in your email:
> If we provide automation for simple cases, people will want more.

So I think we’re leaning towards rejecting this.  pysetup is a simple installer for simple installs; pip and other installers will use the information returned by packaging.depgraph/install to be smart about conflicts.

> Not all packages upload their release sources (thus metadata) to PyPI
No, it’s register that uploads metadata.

> which is why - I believe - PIP is scraping the Simple Index and
> home_page urls to get the appropriate sdist for any package.
Yes, the screen scraping in setuptools comes from the fact that not all projects upload distributions on PyPI.  (Actually, setuptools did the screen scraping before PyPI supported distributions upload.)

> I am not fully aware of what kind of packages p7g.install is supposed
> to support, though. I assume that setuptools-style projects (using
> install_requires) are not supported by p7g.install.
I think they are, or if not it’s a missing feature we want to support.  Kelsey and Alexis know more about that topic.  See recent threads on Fellowship.

> But its probably much simpler to only expose per-package dependency
> (and other metadata) through REST urls
RESTful PyPI is Alexis’ pony :)  Right know, the XML-RPC exposes the metadata, including PEP 345 Requires-Dist if the release provided it.

I'm sorry, but it is simply not true that this is not a solved problem.  This is a well-understood problem that's solved --- at least as well as anyone could want it to be --- by aptitude (not apt-get) and by http://en.opensuse.org/openSUSE:Libzypp_satsolver

On 2011-06-07, at 10:39 AM, Éric Araujo wrote:

> Éric Araujo <merwok@netwok.org> added the comment:
> 
>> Not all packages upload their release sources (thus metadata) to PyPI
> No, it’s register that uploads metadata.

(was not sent before?)

Ok, that's interesting. Does p7g.install support packages that do not register their new releases?

Setuptools/PIP does by scraping the project home pages.

Eg: http://pypi.python.org/pypi/PyChecker incorrectly (but expected) shows 0.8.12 as latest, but http://pychecker.sourceforge.net/ shows 0.8.19 as the latest. Will p7g.install install 0.8.19?

Dave, but aptitude contains a local index of all dependency information. Whereas, PyPI's infrastructure and pip/easy_install/p7g.install do not rely on one. Therefore, I think when Tarek said "Trying to do something smarter is very very hard and will probably fail." he is referring to doing such dependency resolution *with* the constraint of lack of such local metadata index.

That's quite true.  However, I don't think a local index is needed if there's a remote index; you're already looking in a remote index, albeit a less-completeone.  And it could be maintained automatically from individual package metadata.  Maybe that's out of scope for this project, though.

[Sridhar]
>> No, it’s register that uploads metadata.
>(was not sent before?)

To me, not to the tracker.

> Ok, that's interesting. Does p7g.install support packages that do not
> register their new releases?
> Setuptools/PIP does by scraping the project home pages.

p7g.pypi.simple uses the screen-scraping PyPI interface called “simple”, but I don’t know if it goes over to home pages to find links.

> Will p7g.install install 0.8.19?
Try it in a shell?

[Dave]
> I'm sorry, but it is simply not true that this is not a solved
> problem.  This is a well-understood problem that's solved

Well, I’m no researcher but I know that there’s still some research ongoing, in particular for upgrades: http://www.mancoosi.org/

Per Tarek’s pronouncement, closing.