fosskers/aura — pull request #129 by knrafto (2013-07-29 06:10:20+00:00)
Title: Rewrite dependency algorithm

Fixes #104. This turned out to be a pretty large project, so I've split it up into logical chunks and written detailed commit messages. I've copied the first here, but please read all of them.

Basically, dependency solving is faster, limits costly package lookups
(fetching information from the AUR can take a long time), and should
solve the "Prelude.head: empty list" problem.

The new dependency algorithm uses as concrete `Package` type for
simplicity. Packages can be installed in two ways: pacman, or
building (represented by the `Buildabe` type, formerly a typeclass).

To flexibly resolve dependencies, it uses a `Repository`
type, which provides packages (e.g. from the AUR, ABS tree, or pacman
repositories). Multiple repositories can be combined to search one
before the other.

The algorithm starts by compiling a map of package names. For each
dependency, it searches the map and then the outside repository for
a package. Once a package is found, it checks the version to make sure
it satisfies the dependency. If the package needs to be added to the
map, its dependencies are recursively added. After all the needed
packages are added to the map, they are put into a graph and topsorted
into the required install order.

Package groups and packages provided by another one (virtual
packages) are not handled. If they are in the pacman repos,
pacman will handle them. If they are in the AUR, this method does not
handle them (but neither could the previous method). Hopefully this
will be fixed soon.

Error messages are a little tricky because I don't speak 11 languages.
`getRealPkgConflicts_1` and `getRealPkgConflicts_2` are both used as
they were originally. `getVirtualConflicts_1` (which has a terrible
English message, in my opinion) is hijacked to indicate a dependency
could not be found. `getVirtualConflicts_2` and `getVirtualConflicts_3`
are not used.

If there's something I've left out or something you want me to change, please ask and I'll try to address it.