One of the things that I've found to be important for (and generally under-documented by) package managers is resolution strategy.
pip, for instance, eagerly resolves the highest version of a dependency first found in the tree and doesn't backtrack AFAIK [1]. Cargo sounds as though it behaves similarly, but will actually backtrack [2]. I've also seen package managers like 0install that will use SAT solvers to solve dependency constraints [3].
I've found lack of backtracking on conflicts to be frustrating, but I'm curious how the other two (and other conflict resolving strategies) compare in practice.
pip's lack of backtracking is doubly irritating, because it installs packages as it goes. It would be great if it would fetch all of the required manifests and make sure that the install was going to succeed before it starts spewing stuff everywhere, but instead it will happily back itself into a corner where A->B->C(v1) and A->D->C(v2) conflict and so it leaves the system with A, B and C(v1) installed and prints a nice red stack trace.
Yep it's maddening. We use pip-compile [1] at work and check-in the then totally-resolved requirements.txt. That is working for us well. However I still head-desk every time I just want to install a local package (with pip install -e) to work on it and pip runs amok, naïvely downgrading/upgrading/doing-whatever-it-pleases :/
This, along with the inability to intelligently detect a lack of necessary system package dependencies (e.g. libcurses/libpq-dev) is the most irritating part of pip.
and graydon wrote a POC of using the Z3 solver to find a solution where semver constraints were satisfied, optimizing for the latest versions within those constraints:
Resolution strategies are really interesting in Nix; specifically, because it doesn't have any! All dependencies, etc. are passed in explicitly (either as function arguments, or by importing files).
You are absolutely right about solver strategies. Most of the existing package managers in Go have no solver. It's all manual and typically the tip of master or latest commit.
Glide has a dumb solver in that it goes with the first best version it finds. It will tell you if there is a later conflict that you can manually resolve.
There is a package, discussed here called gps, that is being prepped to merge into Glide. This solver has a back-off strategy. It's loosely based on the solver in dart. The idea is to find the latest newest version that works for the complete tree.
We've been incrementally working to get a good solver and are almost there.
pip, for instance, eagerly resolves the highest version of a dependency first found in the tree and doesn't backtrack AFAIK [1]. Cargo sounds as though it behaves similarly, but will actually backtrack [2]. I've also seen package managers like 0install that will use SAT solvers to solve dependency constraints [3].
I've found lack of backtracking on conflicts to be frustrating, but I'm curious how the other two (and other conflict resolving strategies) compare in practice.
[1]: https://github.com/pypa/pip/issues/988
[2]: http://doc.crates.io/cargo/core/resolver/index.html
[3]: http://0install.net/solver.html