Is this a bug in dependency resolver?

[osa1]

I'm trying to install pretty library(from HEAD) with tests. Cabal is failing with this error message:

➜  pretty git:(master) ✗ cabal install --enable-tests
Resolving dependencies...
cabal: internal error: could not construct a valid install plan.
The proposed (invalid) plan contained the following problems:
The following packages are involved in a dependency cycle QuickCheck-2.7.6, template-haskell-2.9.0.0, pretty-1.1.3.1
Proposed plan:
Configured QuickCheck-2.7.6 (.fake.QuickCheck-2.7.6)
Configured pretty-1.1.3.1 (.fake.pretty-1.1.3.1)
Configured primitive-0.5.4.0 (.fake.primitive-0.5.4.0)
Configured random-1.1 (.fake.random-1.1)
Configured template-haskell-2.9.0.0 (.fake.template-haskell-2.9.0.0)
Configured tf-random-0.5 (.fake.tf-random-0.5)
PreExisting array-0.5.0.0 (array-0.5.0.0-470385a50d2b78598af85cfe9d988e1b)
PreExisting base-4.7.0.2 (base-4.7.0.2-bfd89587617e381ae01b8dd7b6c7f1c1)
PreExisting rts-1.0 (builtin_rts)
PreExisting containers-0.5.5.1 (containers-0.5.5.1-d4bd887fb97aa3a46cbadc13709b7653)
PreExisting deepseq-1.3.0.2 (deepseq-1.3.0.2-63a1ab91b7017a28bb5d04cb1b5d2d02)
PreExisting ghc-prim-0.3.1.0 (ghc-prim-0.3.1.0-a24f9c14c632d75b683d0f93283aea37)
PreExisting integer-gmp-0.5.1.0 (integer-gmp-0.5.1.0-26579559b3647acf4f01d5edd9491a46)
PreExisting old-locale-1.0.0.6 (old-locale-1.0.0.6-50b0125c49f76af85dc7aa22975cdc34)
PreExisting time-1.4.2 (time-1.4.2-9b3076800c33f8382c38628f35717951)
PreExisting transformers-0.3.0.0 (transformers-0.3.0.0-6458c21515cab7c1cf21e53141557a1c)

I can't see how there is a dependency cycle, this doesn't form a cycle: QuickCheck-2.7.6, template-haskell-2.9.0.0, pretty-1.1.3.1 because we're not building the library, we're building the test suite.

prettys cabal file is a bit weird, test suite doesn't depend on the library itself, instead it compiles the library again. As an experiment, I made this change:

diff --git a/pretty.cabal b/pretty.cabal
index c4ac991..6c260db 100644
--- a/pretty.cabal
+++ b/pretty.cabal
@@ -43,10 +43,10 @@ Library
 Test-Suite test-pretty
     type: exitcode-stdio-1.0
     hs-source-dirs: tests
-                    src
     build-depends: base >= 4.5 && < 5,
                    deepseq >= 1.1,
                    ghc-prim,
+                   pretty,
                    QuickCheck >= 2.5 && <3
     main-is: Test.hs
     other-modules:

But it failed with same error message.

Any ideas?

[23Skidoo]

/cc @kosmikus

I believe that this is a duplicate of #1575.

[kosmikus]

Something is definitely strange. I can reproduce this with cabal-install HEAD, but I don't get an error with e.g. cabal-install-1.20.0.2. I'll need to investigate this in more detail, but independently of the fact that cabal should most certainly not report an "internal error" on this, I agree with @23Skidoo that most likely, the issue is related to #1575.

[kosmikus]

Oh, I see, the difference between the cabal-install versions is that there used to be a built in template-haskell installed constraint, which has been removed. With the constraint added --constraint="template-haskell installed", there's at least no invalid install plan being generated.

Without it, the solver selects QuickCheck with the +template-haskell flag, and to reinstall template-haskell, and there is a true dependency cycle as follows:

template-haskell-2.9.0.0 (which depends on pretty-1.1.*)
QuickCheck-2.7.6 (which depends on template-haskell >= 2.4)
pretty-1.1.3.1 (test-suite depends on QuickCheck >= 2.5 && < 3)

The solver doesn't currently check for cycles properly. (My original reasoning was that cycles are "wrong" and shouldn't occur in practice. But this is clearly no longer true.) The sanity check for the install plan catches it, but then it's too late to look for different solutions.

So yes, this is related to #1575, but nevertheless one can argue that it's a bug in the solver, and it should probably be fixed in some way.

[osa1]

I'm actually willing to work on this during the next week. @kosmikus is this too hard to fix? As far as I can see, we should be treating each component(library, executables, tests, benchmarks) as separate things but currently they're considered as one installation unit, did I get it right?

[kosmikus]

Well, this bug is, as I said above, actually a solver bug. It shouldn't be too hard to fix (but isn't trivial either). The #1575 bug is about resolving cycles such as this one by allowing the pretty library to be built first, then template-haskell and QuickCheck, and only then the test suite for pretty, thereby avoiding the cycle. Discussion about details on this should probably be on #1575, but the bottom line is that I don't think the solver side is extremely hard, but the interaction with the rest of Cabal is quite tricky. For example, the whole notion of install plan has to be refined, because it's now not just containing packages, but components of packages. As a consequence, the sanity check has to be adapted significantly. And finally, we have to properly turn the install plan into build instructions that actually build the individual components separately and correctly.

At the same time, there are some changes for the solver and rest of Cabal in the pipeline that are related to this as well, and that probably should be merged first. @edsko has been working on implementing independent goals in the solver (roughly speaking, this allows you to have two goals on a single package to be resolved to different instances under certain circumstances). The primary goal of that work is to allow Setup files to have dependencies that do not interfere with the dependencies of the package itself, but the same mechanism can in principle also be used for (some) test suites and executables, and it's an extension we've discussed. This stuff is currently here: https://github.com/edsko/cabal/tree/orthogonal-linking

/cc @dcoutts (who's also been involved in the design of the independent goals changes)

[kosmikus]

I think this is actually fixed by #3170. At least the original example now produces:

QuickCheck-2.8.2 -templatehaskell (via: pretty-1.1.3.3) (new version)
pretty-1.1.3.3 *test (new version)

and

$ cabal install --enable-tests --dry-run -v3 | grep cyclic
[_20] rejecting: QuickCheck-2.8.2:+base3 (cyclic dependencies; conflict set: QuickCheck, pretty, template-haskell, QuickCheck-2.8.2:flag, QuickCheck-2.8.2:test, pretty-1.1.3.3:test)
[_20] rejecting: QuickCheck-2.8.2:-base3 (cyclic dependencies; conflict set: QuickCheck, pretty, template-haskell, QuickCheck-2.8.2:flag, QuickCheck-2.8.2:test, pretty-1.1.3.3:test)
[_20] rejecting: QuickCheck-2.8.2:+base3 (cyclic dependencies; conflict set: QuickCheck, pretty, template-haskell, QuickCheck-2.8.2:flag, QuickCheck-2.8.2:test, pretty-1.1.3.3:test)
[_20] rejecting: QuickCheck-2.8.2:-base3 (cyclic dependencies; conflict set: QuickCheck, pretty, template-haskell, QuickCheck-2.8.2:flag, QuickCheck-2.8.2:test, pretty-1.1.3.3:test)

shows that cyclic solutions are being rejected.