Hacker News Reader

Comment by lmns | Hacker News Reader

What are "absurd" amounts of CPU and memory? Calculating and pinning dependencies is just a very difficult problem which happens to be reducible to SAT. If you think a SAT solver takes a lot of time and memory, then all alternatives would probably be even slower.

View on HN

Dependency solvers that obey semver are a really hard problem that have very unintuitive challenges. I think a very large number of people who use them will not have spent a lot of time to think about the issues in detail, just their experiences as a user of them. NPM has less complaints than composer for example, but node_modules has an interesting way out of the problem by making dependencies into a hierarchy but this brings a new bunch of challenges elsewhere (in the runtime, any object transiting between a mutual package which has two different package versions of the same package name in the lineage will be have "weird" behaviour).

  Your Project --depends-on-> Foo@1.2.3 --depends-on-> SomeLib@1.2.3
  Your Project --depends-on-> Bar@4.0.1 --depends-on-> SomeLib@4.5.6

If Your Project touches SomeLib from Bar and passes it into Foo things go sideways. It's easy to state that this violates best practices but it is a reality of how the runtime works. This category of issue is removed in PHP/Python by the package manager (not the language). The trade-off is the large computation that checks for conflicts in SomeLib.

> Dependency solvers that obey semver are a really hard problem that have very unintuitive challenges

throw in platform specific binary packages for which platform triplets can be wildcarded plus dependencies that may vary across these platforms plus specifying package sources for which dependencies may be on another source and you're in for a crazy world of hurt (well, at least I am, given I found some issues in bundler+rubygems and have been trying to solve them upstream for a couple of years)

Anything over "basically none" is absurd, but in this case the worst case really is very bad.

How would you solve it with very little computing resources? I've yet to see any reasonable solution.

There's a few novel techniques such as minimal version selection: https://research.swtch.com/vgo-mvs. I know I've seen a few others in the past years but I'm struggling to remember which ones are non-SAT solving approaches.

Reply on news.ycombinator.com