Haskell Cabal: “package indirectly depends on mult

After clearing out all of my cabal installed packages, I ran this following session:

$ cabal update
Downloading the latest package list from hackage.haskell.org
james@bast:~/.cabal/packages$ cabal install cabal-dev
Resolving dependencies...
Downloading cabal-dev-0.9.1...
[1 of 1] Compiling Main             ( /tmp/cabal-dev-0.9.124882/cabal-dev-0.9.1/Setup.hs, /tmp/cabal-dev-0.9.124882/cabal-dev-0.9.1/dist/setup/Main.o )
Linking /tmp/cabal-dev-0.9.124882/cabal-dev-0.9.1/dist/setup/setup ...
Configuring cabal-dev-0.9.1...
Warning: This package indirectly depends on multiple versions of the same
package. This is highly likely to cause a compile failure.
package containers-0.4.2.1 requires array-0.4.0.0
package Cabal-1.14.0 requires array-0.4.0.0
package text-0.11.1.13 requires array-0.4.0.0
package deepseq-1.3.0.0 requires array-0.4.0.0
package containers-0.4.2.1 requires array-0.4.0.0
package HTTP-4000.2.2 requires array-0.4.0.0
package cabal-dev-0.9.1 requires containers-0.4.2.1
package Cabal-1.14.0 requires containers-0.4.2.1
package template-haskell-2.7.0.0 requires containers-0.4.2.1
Building cabal-dev-0.9.1...
Preprocessing executable 'ghc-pkg-6_8-compat' for cabal-dev-0.9.1...
<command line>: cannot satisfy -package-id Cabal-1.14.0-4af45d3c8d10dc27db38ae0e7e5a952b: 
    Cabal-1.14.0-4af45d3c8d10dc27db38ae0e7e5a952b is unusable due to missing or recursive dependencies:
      array-0.4.0.0-46f61f5fd9543ebf309552ef84dccc86 containers-0.4.2.1-98f9aa15f9c08b13673dc9d89385f449
    (use -v for more information)
cabal: Error: some packages failed to install:
cabal-dev-0.9.1 failed during the building phase. The exception was:
ExitFailure 1
$

So the reason I can't install cabal-dev is apparently either that

it "indirectly depends on multiple versions of the same package." However, cabal does not name the package that it claims cabal-dev requires multiple versions of.
Cabal-1.14.0 has "missing or recursive dependencies", specifically somehow involving array-0.4.0.0 and containers-0.4.2.1.

A graph of the dependencies it lists confirms that neither of these claims are true (or the dependencies it lists are false or incomplete):

So: what am I missing? Who or what is incorrect: me, cabal, or one or more packages?

I am running:

$ cabal --version
cabal-install version 0.10.2
using version 1.10.1.0 of the Cabal library 
$ ghc --version
The Glorious Glasgow Haskell Compilation System, version 7.4.1
$

The problem arises when we have package B and C already installed but built against different versions of D and then we try to use both packages B and C together in package A: Diamond dependency problem This can work ok but only if packages B and C do not expose types defined in D in their interfaces. If they do then package A will not be able to use functions from B and C together because they will not be working with the same type. That is you'll get a type error.

To pick a concrete example, suppose package D is bytestring and we have both bytestring-0.9.0.1 and 0.9.0.4 installed. Lets say B is utf8-string and C is regex-base. Lets say that package A is the Yi editor program. So the point is, at some place in the code in Yi we want to pass a bytestring produced as the result of UTF-8 decoding as input to one of the regex functions. But this does not work because the functions in the utf8-string package are using the ByteString type from bytestring-0.9.0.1 while the regex functions in the regex package are using the ByteString type from bytestring-0.9.0.4. So we get a type error when we try to compile Yi:

Couldn't match expected type bytestring-0.9.0.4:Data.ByteString.ByteString' against inferred typebytestring-0.9.0.1:Data.ByteString.ByteString'

As far as GHC knows, these two types are totally unrelated!

This is obviously extremely annoying. There is also no easy solution. In this example we're assuming that packages B and C have already been built, so there is actually no way to sensibly use the two packages together without rebuilding on of them against a different version of package D. In this case the obvious solution is to rebuild B to use the D-1.1 rather than D-1.0. The problem with rebuilding a package of course is it breaks all other packages that have already been built against it. It isn't clear that you want a package manager to go automatically rebuilding lots of apparently unrelated packages.

In the longer term the best solution would seem to be to do what Nix does. In the above example, instead of replacing package B built against D-1.0 with B built against D-1.1, Nix would add another instance of B built against D-1.1. So the original instance of B would remain unchanged and nothing would break. It's the functional approach: we never mutate values (installed packages) we just create new ones and garbage collect old one when they are no longer needed.

In practice it means we have to identify installed packages using some hash of the package and the hashes of all dependent packages. jhc already does this and there are moves afoot to do something similar for GHC, though aimed more at tracking API/ABI changes. For sane source based package management, I think it's the right direction to take.

I should note that this is not a new problem. You've been able to construct this problem ever since ghc started to allow multiple versions of the same package to be installed at once. We are just noticing it a lot more frequently now because we split up the base package and allow those split-out packages to be upgraded.

The current state of play is that Cabal warns of this problem but doesn't really help you solve it. For the above example we'd get:

$ cabal configure
Configuring A-1.0...
Warning: This package indirectly depends on multiple versions of
the same package. This is highly likely to cause a compile failure.
package B-1.0 requires D-1.0
package C-1.0 requires D-1.1