(Imported from Trac #405, reported by @dreixel on 2008-11-13)
While creating a new package syb-0.2 (which supersedes syb-0.1), we have in the .cabal file:
build-depends: base >= 4.0
Dependency base >=4.0: using base-126.96.36.199
Dependency mtl >=188.8.131.52: using mtl-184.108.40.206
Using Cabal-220.127.116.11 compiled by ghc-6.10
Reading available packages...
selecting syb-0.2 (hackage) and discarding mtl-1.0, 18.104.22.168 and 22.214.171.124
selecting mtl-126.96.36.199 (installed or hackage)
cabal: dependencies conflict: base-188.8.131.52 requires syb ==0.1.0.0 however
syb-0.1.0.0 was excluded because syb-0.2 was selected instead
syb-0.1.0.0 was excluded because of the top level dependency syb ==0.2
(Imported comment by @dcoutts on 2008-11-13)
The problem here is the subtleties of the constraint solver and the modifications we made to enable it to work in the presence of base 3 and 4.
The solver is specifically designed to avoid picking two versions of any package. However the presence of base 3 and 4 messes all that up. The hack was to pretend to some degree that base 3 and 4 are really the same thing. So whenever we select one, we select the other. They get included or excluded from a solution as a pair. Then in a pass at the end we work out for each individual package if its dependency on base should be on base 3 or on 4. At that stage we obviously use any constraints that package specifies like base >= 4.
Normally this works, but in this case adding base 3 into the solution causes a conflict that would not be there if we avoided adding base 3. In particular base 3 pulls in the older version of syb.
It's not clear to me if it's possible to salvage the constraint solver in its current form. We may need to move directly to a proper solver based on SAT or more general constraint programming.
Note: for people who wonder if this problem is really that hard; yes it is, it's NP-complete. Fortunately most instances of the problem are 'easy' though some instances (like installing all of hackage) are rather large.
(Imported comment by @kosmikus on 2008-11-13)
I think I can fix this problem in the new solver (but haven't done so yet). It's one of the things I'd like to do prior to releasing cabal-install-0.14.
(Imported comment by @kosmikus on 2012-03-08)
I'll not fix this for 0.14 after all, but this situation should now be relatively rare.
Rare enough that nobody is going to get around to fixing it :-(