[Distutils] name of the dependency problem

[Justin Cappos]

Yes, it's another way to solve the problem.  Both backtracking dependency
resolution and ZYpp will always find a solution.  The tradeoff is really in
how they function.  ZYpp is faster if there are a lot of dependencies that
conflict.  The backtracking dependency resolution used in Stork is much
easier for the user to understand why it chose what it did.

An aside: I'm not necessarily convinced that you need to solve this problem
automatically, instead of just raising an error when it occurs.  It should
be quite rare in practice and as such may not be worth the complexity to
have an automatic solution for the problem.

Thanks,
Justin

On Wed, Apr 15, 2015 at 8:55 AM, Daniel Holth <dholth at gmail.com> wrote:

> See also http://en.wikipedia.org/wiki/ZYpp
>
> On Wed, Apr 15, 2015 at 7:43 AM, Justin Cappos <jcappos at nyu.edu> wrote:
> > 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
> >
> >
> >
> > _______________________________________________
> > 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/560b9939/attachment-0001.html>