DUB - call to arms

[H. S. Teoh]

On Wed, Apr 17, 2019 at 07:29:39PM -0400, Paul Backus via Digitalmars-d wrote:
> On 4/17/19 12:18 PM, H. S. Teoh wrote:
> > On Wed, Apr 17, 2019 at 07:03:33PM +0300, drug via Digitalmars-d wrote:
> >> To be more correct I mean version constraints.
> > 
> > Ah, I see what you mean.  So package xyz may have, say, 10 different
> > versions, and each version could potentially have different
> > dependencies (since dependencies can change over time).  So after
> > narrowing down to the subset of xyz versions that satisfy the given
> > version criteria, you still have to decide which of the remaining
> > versions to use, since they may depend on other packages that are
> > subject to other version constraints.  So you'll need some graph
> > algorithms to resolve these constraints.
> > 
> > Interesting, I've never thought about this before.  I'll have to
> > think about this some more.  Thanks!
[...]
> Dependency resolution is actually NP-complete in the general case:
> 
> https://research.swtch.com/version-sat
> 
> Of course, in practice, there are solutions that work well enough to
> be usable; several are discussed in the linked article.

Ouch.  The term "dependency hell" never seemed more apt, after reading
the article. :-/

Interestingly, NP completeness can be avoided by only allowing packages
to specify minimum versions, rather than a specific version (or
arbitrarily complex version conditions).  Allowing installation of
multiple versions of the same package also gets away from NP
completeness, though in practice it's probably a lot harder to pull off.
An interesting hybrid approach is to combine both using semver, which
sorta makes sense in some way. Though it's unclear how well this works
in practice.

Time to bust out that SAT solver... :-/


T

-- 
Tell me and I forget. Teach me and I remember. Involve me and I understand. -- Benjamin Franklin