cabal-install finds non-existent conflict due to picking base 3

[dreixel]

While creating a new package syb-0.2 (which supersedes syb-0.1), we have in the .cabal file:

build-depends:          base >= 4.0

'cabal configure -v' outputs:

(...)
Configuring syb-0.2...
Dependency base >=4.0: using base-4.0.0.0
Dependency mtl >=1.1.0.2: using mtl-1.1.0.2
Using Cabal-1.6.0.1 compiled by ghc-6.10
(...)

'cabal install -v' outputs:

(...)
Reading available packages...
Resolving dependencies...
selecting syb-0.2 (hackage) and discarding mtl-1.0, 1.1.0.0 and 1.1.0.1
selecting mtl-1.1.0.2 (installed or hackage)
selecting
cabal: dependencies conflict: base-3.0.3.0 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

However, 'runghc Setup.hs install' proceeds without problems.

[duncan]

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.

[kosmikus]

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.

[kosmikus]

I'll not fix this for 0.14 after all, but this situation should now be relatively rare.