[DannyBee]

I'll present a counterpoint of a different kind, since everyone is arguing about what current package managers do and don't do.

Satisfiability problems of this kind appear in a ridiculous number of fields and applications (and not just by reduction).

The vast majority of them, in practice, are approximated rather than exactly solved.

Most of the ones that are exactly solved are in software verification, model checking, etc. Areas where having an exact answer is very critical.

Outside of that, much like you see in MVS, they approximate or use heuristics. And it's fine. You don't notice or care.

The idea that "package management" is one of those areas that absolutely must be exactly solved to generate acceptable results seems to me to be ... probably wrong.

There are much more critical and harder things we've been approximating for years and everyone is just fine with it.

(IE not clamoring for faster exact solvers).

Thus i have trouble saying a sat solver is a better solution. It certainly would be a more "standard" one in this particular instance, but that's mostly irrelevant. It's also a very complex one that often fails in interesting ways in both this, and other, domains.

[pcwalton]

> The idea that "package management" is one of those areas that absolutely must be exactly solved to generate acceptable results seems to me to be ... probably wrong.

The logical conclusion of your statement is that minimal version selection is the wrong approach! Minimal version selection is an "exact" solution, in contrast to the traditional one. You would only arrive at MVS if you considered the problem of selecting precise dependencies to be so important that it's worth making it the user's problem instead of having the tool solve it. The philosophy of the traditional package management solution is that it's best to have the tool do the right thing--select most recent versions that satisfy constraints--so that the user is free to worry about more important things.

> There are much more critical and harder things we've been approximating for years and everyone is just fine with it.

Yes! That's why MVS, and by extension vgo, is oriented around solving a non-problem!

> It's also a very complex one that often fails in interesting ways in both this, and other, domains.

I cannot name one example of a single time SAT solving has failed in Cargo.

[DannyBee]

I feel like you are really stretching here. You took a bunch of words out of context so you could parse them.

"Minimal version selection is an "exact" solution, in contrast to the traditional one. "

It's not an exact solution to SAT, it's an exact solution to a simpler problem than SAT (2-SAT). A problem that admits linear time solutions, even.

That is in fact, what a lot of approximations actually are - reduction of the problem to a simpler problem + exact solving of the simpler problem.

Some are heuristic non-optimal solvers of course, but some are not.

Certainly you realize the complexity and other differences between "an exact solver for SAT" and "an approximation of a SAT problem as a 2-SAT problem + an exact solver for 2-SAT"

I can write a linear time 2-SAT solver in about 100 lines of code and prove it's correctness. It's even a nice, standard, strongly connected component based solver.

Here's a random one: https://github.com/kartikkukreja/blog-codes/blob/master/src/...

So if i have an SCC finder implemented somewhere, it's like 20 lines of code.

Past this, your argument about "taking the user's time" is so general you could apply it to literally any problem in any domain. You can just plug in whatever domain you like and whatever solution you happen to like into this argument.

Here it's backed by no data - you have surfaced zero evidence of your premise - "that it is taking user time". This entire thread in fact has exactly no evidence that it's taking any appreciable amount of user time, so it definitely fails as an argument.

(in fact, the only evidence presented in this thread is that the algorithm simply works on existing packages)

If you actually have such evidence, great, i'm 100% sure that go folks would love to see it!

Because right now the main time spend, in fact, seems to be people arguing in threads like these.

[pcwalton]

> Certainly you realize the complexity and other differences between "an exact solver for SAT" and "an approximation of a SAT problem as a 2-SAT problem + an exact solver for 2-SAT"

I'm saying that the theoretical complexity of the core dependency resolution algorithm is irrelevant in practice. Therefore, removing useful features to reduce SAT to 2-SAT is not a good trade. I, and everyone else who has worked with Cargo, keep saying this, but nobody listens. :(

> Here it's backed by no data - you have surfaced zero evidence of your premise - "that it is taking user time". This entire thread in fact has exactly no evidence that it's taking any appreciable amount of user time, so it definitely fails as an argument.

Minimum version selection makes it the user's problem to fetch the newest version of dependencies. That is the entire premise of minimum version selection. If you want to upgrade your versions, you have to use "go get -u". That command blindly updates all minor versions of packages. The problem arises when you have some packages that did not follow the semver rules (or are on 0.x) and you need to hold them back to avoid breaking your build. That is when the more fine-grained version control that systems like Cargo support becomes essential. Vgo has unfortunately decided to omit that support in favor of some theoretical benefits that make no difference in practice.

> If you actually have such evidence, great, i'm 100% sure that go folks would love to see it!

The Go team has the evidence in that every other package manager uses maximal version selection instead of minimal version selection, because of the problems with minimal version selection.

I strongly suspect that the problems in minimal version selection will become apparent over the years as people hit the limitations, at which point it will become apparent that Go made a mistake, but it will be difficult to fix. In particular, I think that, several years down the line, there's a good chance that running "go get -u" in large software projects is going to result in a broken build, because people are imperfect and don't perfectly follow semver. So people just won't upgrade their packages very often.

[kaeshiwaza]

In large software you'll not do go get -u for all packages, you'll upgrade each package separately, at the maximum version or at a specified one. It's just that it's you the user of the modules will choose what and when you upgrade, not the(this) tools automagicaly.

[pcwalton]

> It's just that it's you the user of the modules will choose what and when you upgrade, not the(this) tools automagicaly.

You've correctly identified the problem with vgo.

[kaeshiwaza]

You didn't find example of failed Cargo because most of the time it just do like go get -u, and solve a non-problem !