> cabal-install: it does not work well with packages that have flags
> because it does not know what flags to use when building dependencies.
>  Really, packages with conditionals are different packages in one
> cabal file.

Packages are not supposed to expose different APIs with different flags
so I don't think that's right. Under that assumption cabal-install can
in principle resolve everything fine. I'm not claiming the current
resolution algorithm is very clever when it comes to picking flags
(though it should always pick ones that give an overall valid solution)
but there is certainly scope for a cleverer one. Also, the user can
always specify what features they want, which is what systems like
Gentoo do.

Do you have any specific test cases where the current algorithm is less
than ideal? It'd be useful to report those for the next time someone
hacks on the resolver.