Molinillo: a dependency resolution algorithm | Hacker News Reader

Molinillo: a dependency resolution algorithm

github.com

38 pointspmoriarty9 comments

From what I recall, Molinillo is used by both Bundler and Cocoapods. It always struck me as a nice example of good collaboration between two major open-source projects.

What are the advantages/inconveniences compared to a standard topological sort algorithm ?

The problem of resolving a set of dependencies is actually NP complete. One can reduce the SATISFIABILITY problem to it. Russ Cox provides a good introduction to the problem [1,2]

What's challenging about dependency resolution is handling the versioning constraints. For example, you may state that your project is dependent on the following packages {"A:1.0", "B:[2.0,)", "C:3.2"}. Resolving a dependency is simply selecting one version of each package. At first glance this is easy. However, you need to consider the transitive dependencies of each package. Meaning, A:1.0 will have set of dependencies you need to resolve. Then B:2.0, B:2.1, etc will have their own set of dependencies. In some cases you may find that there is simply no means to resolve the dependencies.

For example, if A:1.0 depended on C:2.1, there would be no way to resolve your transitive dependency graph.

Currently, most package managers use a heuristic based backtracking approach. However, there has been a recent push to using SAT solvers. It's a fascinating and messy area.

[1] https://research.swtch.com/version-sat

[2] https://news.ycombinator.com/item?id=13167446

How are these recent approaches different from OPIUM[1] from 2007? 0install is based around this algorithm. Also as far as I know Debian and FreeBSD both offer options to resolve dependencies using SAT solvers.

[1] http://www.cjtucker.com/opium.pdf

Eclipse's P2 has also been using a SAT solver for quite some time [0].

[0] https://wiki.eclipse.org/Equinox_P2_Resolution

Also there is zypper, the package manager of OpenSUSE and SLES. That's where I first heard about this usage of SAT, around 10 years ago. https://en.wikipedia.org/wiki/ZYpp

It is NP complete, if conflicts are possible. Is that what Molinillo means by a 'locking' dependency graph?

If conflicts are not possible, then it is not NP complete, toposort is good enough, and backtracking is unnecessary.

That's fair. Whenever I think of dependencies, I imagine conflicts are fair game.

Why? In Debian conflicts are usually only used to remove obsolete software from old releases.

Conflicts between packages which are both maintained should not happen. If two packages want to provide the same file, Debian can install both and has tooling to switch between them.

Reply on news.ycombinator.com