On Wed, Apr 17, 2019 at 10:40:29AM +0300, drug via Digitalmars-d wrote:
> On 16.04.2019 20:39, H. S. Teoh wrote:
> > If done correctly, dependency resolution is just a topological walk on a DAG.  Get this right, and everything else falls into place.
> > 
> How do you resolve conflicts using DAG only?

What kind of conflicts?


T

-- 
Too many people have open minds but closed eyes.

On 17.04.2019 18:53, H. S. Teoh wrote:
> 
> What kind of conflicts?
> 
To be more correct I mean version constraints.

On Wed, Apr 17, 2019 at 07:03:33PM +0300, drug via Digitalmars-d wrote:
> On 17.04.2019 18:53, H. S. Teoh wrote:
> > 
> > What kind of conflicts?
> > 
> 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!


T

-- 
Not all rumours are as misleading as this one.

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!
> 
> 
> T

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.

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

On Wed, 2019-04-17 at 22:27 -0700, H. S. Teoh via Digitalmars-d wrote: […]
> 
> Ouch.  The term "dependency hell" never seemed more apt, after
> reading
> the article. :-/
[…]

The Gradle people have been through all this over the years, and now have an excellent dependency management system including allowing quite fine grain manual specifications.

Gradle now has a C++ build as well as the whol gamut of JVM-based languages. An alternative is to add D to this.

-- 
Russel.
===========================================
Dr Russel Winder      t: +44 20 7585 2200
41 Buckmaster Road    m: +44 7770 465 077
London SW11 1EN, UK   w: www.russel.org.uk

On 4/18/19 5:40 AM, Russel Winder wrote:
> 
> The Gradle people have been through all this over the years, and now
> have an excellent dependency management system including allowing quite
> fine grain manual specifications.
> 
> Gradle now has a C++ build as well as the whol gamut of JVM-based
> languages. An alternative is to add D to this.

My old JVM days predate Gradle, but at a glance it looks like Gradle is mainly a buildsystem. As the key problem we're facing is needing to separate package management from buildsystem, utilizing Gradle seems like a tough sell (tough to sell to me, included), even if only utilized for its package management.

Although I'm personally not entirely against the idea of utilizing an existing cross-platform language-agnostic package manager behind-the-scenes.

For example: What do you think of 0install? <https://github.com/Abscissa/DPak/issues/1>  I haven't personally used it, but I've had my eye on it for quite a number of years. Seems similar to Nix, but without the difficult Nix expression language, and without the difficulty of installing older package versions.

On Thu, 2019-04-18 at 12:01 -0400, Nick Sabalausky (Abscissa) via Digitalmars-
d wrote:
[…]
> 
> My old JVM days predate Gradle, but at a glance it looks like Gradle is mainly a buildsystem. As the key problem we're facing is needing to separate package management from buildsystem, utilizing Gradle seems like a tough sell (tough to sell to me, included), even if only utilized for its package management.
[…]

Gradle has always been an integrated dependency management and build system ever since its genesis in the Conservatory of Barbican Centre in 2007.

Looking at Gradle, Maven, Cargo, Go, Conan, the choice is for integrated dependency management and build. Dub it would seem has taken the right overall approach, just not gone an implementation route that serves D the way Cargo serves Rust.

-- 
Russel.
===========================================
Dr Russel Winder      t: +44 20 7585 2200
41 Buckmaster Road    m: +44 7770 465 077
London SW11 1EN, UK   w: www.russel.org.uk

On Friday, 19 April 2019 at 06:19:42 UTC, Russel Winder wrote:
>
> Gradle has always been an integrated dependency management and build system ever since its genesis in the Conservatory of Barbican Centre in 2007.
>
> Looking at Gradle, Maven, Cargo, Go, Conan, the choice is for integrated dependency management and build. Dub it would seem has taken the right overall approach, just not gone an implementation route that serves D the way Cargo serves Rust.

+1 (for everything that Russel said in this thread!)

On 4/19/19 2:19 AM, Russel Winder wrote:
> 
> Looking at Gradle, Maven, Cargo, Go, Conan, the choice is for integrated
> dependency management and build. Dub it would seem has taken the right overall
> approach,

Well, it certainly seems to have taken a *popular* approach. I wouldn't necessarily take that as implying the "right" approach (for us).

> just not gone an implementation route that serves D the way Cargo
> serves Rust.

Maybe. But there's two things I think you're overlooking:

1. Differences in manpower.
2. Differences in situation/requirements.

1: Getting something like that right, without being overly-limited, amounts to quite a significant project in terms of manpower and, though I could be wrong, my perspective is that those communities have had more manpower to put into such a project than we have. At the very least, I think DUB has proven it's a poor approach for our current level of manpower.

2: D currently has plenty of buildsystem options to choose from, there's likely to be something for everyone. BUT, what D completely lacks right now, and desperately needs IMO, is a good package manager that's non-restrictive enough to suit everyone's needs. Making the D community wait to get that until we *finally* manage to work out our own one-buildsystem-to-rule-them-all (which we're currently nowhere near) is a terrible strategic approach for our current position.

Later on, if a D buildsystem that works great for everyone's needs actually manages to emerge...THEN we can integrate our package manager with it.

Summary: There is FAR more to good design and management than playing follow-the-leader.