[Distutils] name of the dependency problem

[Daniel Holth]

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
>