> I've never heard of a package manager in which core dependency solving was a speed problem
Natalie Weizenbaum and I wrote the package manager for Dart. My naïve backtracking version solver was fine ~98% of the time. 2% of the time it was catastrophically, exponentially slow. Natalie wrote a much better one to solve exactly that:
If I correctly understood the post you linked, it looks like there is a big difference between Rust and Dart when it comes to dependency management: Rust allows for different major version of a crate to appear in the dependency tree, while it seems (from the first example given by the post) that Dart doesn't. That difference would dramatically change the difficulty of dependency resolution between the two languages, because there will be many more unsatisfiable cases in Dart than in Rust, leading to much more work to find a working set. (In the given example, cargo would just pick icon:1.0.0 and menu:1.5.0-> dropdown:2.3.0->icon:2.0.0, and call it a day).
The exponential search issue could arise if people used explicit upper bound on crate minor of patch versions, but since the number of crate doing that is few far between, there's little change to encounter such a degenerated exponential case in practice.
Natalie Weizenbaum and I wrote the package manager for Dart. My naïve backtracking version solver was fine ~98% of the time. 2% of the time it was catastrophically, exponentially slow. Natalie wrote a much better one to solve exactly that:
https://medium.com/@nex3/pubgrub-2fb6470504f