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.
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.
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
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.
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.
9 comments
[ 1.8 ms ] story [ 28.6 ms ] threadWhat'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
[1] http://www.cjtucker.com/opium.pdf
[0] https://wiki.eclipse.org/Equinox_P2_Resolution
If conflicts are not possible, then it is not NP complete, toposort is good enough, and backtracking is unnecessary.
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.