Dependency Resolution

When cabal tries to install a number of packages, including all their dependencies it has a non-trivial problem to solve. Here we try to describe the problem and some possible solutions.

The Problem

In general we start with a set of installed packages and a set of available packages.

Installed packages have fixed dependencies. They have already been built and we know exactly what packages they were built against, including their exact versions.

Available package have somewhat flexible dependencies. They are specified as version ranges, though really they're predicates. To make matters worse they have conditional flexible dependencies. Configuration flags can affect which packages are required and can place additional constraints on their versions.

These two sets of package can and usually do overlap. There can be installed packages that are also available which means they could be re-installed if required, though there will also be packages which are not available and cannot be re-installed. Very often there will be extra versions available than are installed. Sometimes we may like to prefer installed packages over available ones or perhaps always prefer the latest available version whether installed or not.

The goal is to calculate a consistent and complete installation plan.

An installation plan is a set of packages that are going to be used together. It will consist of a mixture of installed packages and available packages along with their exact version dependencies. An installation plan is complete if for every package in the set, all of its dependencies are also in the set. It is consistent if for every package in the set, all dependencies which target that package have the same version.