[Distutils] name of the dependency problem

[Justin Cappos]

First of all, I'm surprised that pip doesn't warn or error in this case.  I
think this is certainly a bug that should be fixed.  The problem can come
up in much more subtle cases too that are very hard for the user to
understand.

The good news is that this is a known problem that happens when doing
dependency resolution and has a solution.  The solution, which is referred
to as backtracking dependency resolution, basically boils down to saving
the state of the dependency resolver whenever you have multiple choices to
resolve a dependency.  Then if you reach a later point where there is a
conflict, you can backtrack to the point where you made a choice and see if
another option would resolve the conflict.

I have some of the gory details, in Chapter 3.8.5 of my dissertation (
http://isis.poly.edu/~jcappos/papers/cappos_stork_dissertation_08.pdf ).
There is also working Python code out there that shows how this should
behave.  (I implemented this as part of Stork, a package manager that was
used for years in a large academic testbed. )

Thanks,
Justin





On Wed, Apr 15, 2015 at 7:09 AM, Robin Becker <robin at reportlab.com> wrote:

> After again finding that pip doesn't have a correct dependency resolution
> solution a colleage and I discussed the nature of the problem. We examined
> the script capture of our install and it seems as though when presented with
>
>
> level 0 A
>   A level 1  1.4<= C
>
>
> level 0 B
>   B level 1  1.6<= C <1.7
>
> pip manages to download version 1.8 of C(Django) using A's requirement,
> but never even warns us that the B requirement of C was violated. Surely
> even in the absence of a resolution pip could raise a warning at the end.
>
> Anyhow after some discussion I realize I don't even know the name of the
> problem that pip should try to solve, is there some tree / graph problem
> that corresponds? Searching on dependency seems to lead to topological
> sorts of one kind or another, but here we seem to have nodes with discrete
> values attached so in the above example we might have (assuming only
> singleton A & B)
>
> R --> A
> R --> B
>
> A --> C-1.4
> A --> C-1.6
> A --> C-1.6.11
> A --> C-1.7
> A --> C-1.8
>
> B --> C-1.6
> B --> C-1.6.11
>
> so looking at C equivalent nodes seems to allow a solution set. Are there
> any real problem descriptions / solutions to this kind of problem?
> --
> Robin Becker
> _______________________________________________
> Distutils-SIG maillist  -  Distutils-SIG at python.org
> https://mail.python.org/mailman/listinfo/distutils-sig
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/distutils-sig/attachments/20150415/91fcadff/attachment.html>