GitLab

We now track target packages and only require constraints on those
targets to be satisfiable. This allows us to overconstrain packages
that we do not care about, which is useful for excluding broken
packages.
We also now have a more general way of specifying constraints.
Previously constraints were specified as the conjunction of a version
range predicate and an optional installed constraint. This form made
it impossible to express constraints such as "exclude this source
package". Constraints for a package name are now specified simply by
a function predicate on the package version and installed/source state.

Rather than 'available' packages, the source now refers consistently to
'source' packages. This is a bit clearer.

It works by ignoring the possibility that there could be multiple
installed packages sharing the same source package Id. We just pick
the "top most" one which is usually ok. We make no attempt to check
that we are using consistent installed packages.

It now carries around the original version of the database
purely so that it can do a much more extensive consistency
check. Packages are never gained or lost, just transfered
between pots in various slightly tricky ways.

A rather subtle bug. The code was actually correct but the transitionsTo
assertion was not accounting for a transition between the case where
a package's available version had been excluded and then the whole thing
got excluded by a version constraint. It counted one side as a loss
without a corresponding gain on the other side.

The trick is that when applying constraints to paired
packages, the constraint has to exclude both packages at
once. We exclude the pair together or not at all. If it
would only exclude one then we discard the constraint.

Packages like base-3 and base-4 are paired. This means they are
supposed to be treated equivalently in some contexts. Paired
packages are installed packages with the same name where one
version depends on the other.

Each time we apply a constraint we can end up excluding some
extra package. Report that list of packages because it is
quite interesting information to get insight into what the
resolver is actually doing.

Previously directly inserted packages into the excluded package
list. Now we generate a list of them and then add them. We want
the list of newly excluded packages separately because it is
interesting information to report to the user when -v is on.

The branch of cabal-install that tracks Cabal-1.4 now lives at
http://darcs.haskell.org/cabal-branches/cabal-install-0.5/

And tidy some imports slightly

rather than Either and structured error type [Dependency]. The reason
we cannot use that as a structured error type any more is because
missing dependencies is not the only failure reason. There are
several reasons, several of which are pretty complex. For now we'll
have to do with a human readable message. Perhaps we may be able to
find a common structured type that the different dep resolvers can
all agree on. I'm not hopeful however as error reporting seems to be
closely tied to the dep resolution approach.

This is a new dependency resolver that produces valid install plans.
It works in polynomial time however because the search space is 
exponential in size it is not guaranteed to find a solution even if
one exists. It works by generating and then exploring the search
space represented as a lazy tree. It uses constraints to prune
choices and heuristics when guesses are necessary. Currently it can
generate install plans for 99% of the packages on hackage. The
remaining 6 packages should be doable with two extra tricks.
It is not finished and is not yet usable in practice.