cabal-install needs a new package dependency resolution algorithm

[duncan]

The current package dependency algorithm is pretty simple. It's main failing is that it cannot backtrack if it finds the solution is impossible.

What we would like is a new dependency resolution algorithm that can backtrack. We would also like to be able to configure policy issues separately, perhaps as a parameter. It may also be handy to let users or the system add extra version constraints.

The input is the set of available packages and the output is a list of packages to install, and the assignment of configuration flags to use for each one. As for the policy input, this might take the form of a function that picks between possible dependencies in a slot, this could then allow us to make choices like preferring installed packages over the latest available package version, or vica versa.

See also symptoms of the existing system:

• bug #168 -- lack of configurable policy
• bug #174 -- lack of backtracking

[duncan]

Some exploration/prototype code Andres Löh came up with after talking about this problem a few weeks ago:  http://people.cs.uu.nl/andres/Deps.hs This is the kind of thing we should be thinking about.

[duncan]

We've got an improved dependency resolution algorithm now. It's not by any means perfect, there's still plenty of room for improvement and alternative approaches.

The new algorithm still does not backtrack so it is not guaranteed to find a solution. It does use constraints and smarter heuristics so it finds solutions more often than the previous one. Crucially, if it does find a solution then it's a valid one, which is a useful property the previous algorithm did not enjoy.

The new algorithm does have a simple policy control. It can prefer installed or the latest version on a per-package basis.

[duncan]

It seems to work well enough in practice. We can open new tickets for more specific problems and improvements.

[elga]

*  rio bouygues