|
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 |
[1] http://www.cjtucker.com/opium.pdf