search

haskell / cabal

Official upstream development repository for Cabal and cabal-install
https://haskell.org/cabal
Other
1.59k stars 689 forks source link

Build plan only succeeds with --reorder-goals #1855

Closed snoyberg closed 9 years ago

snoyberg commented 10 years ago

In my Stackage builds, I use --max-backjumps=-1 --reorder-goals. Given the recent discussion about reorder-goals both being slow, and possibly causing non-termination in build plan construction, I decided to try out running the build without --reorder-goals. However, doing so caused the build plan to fail. Following is the command I ran, and the output from cabal.

Note that there are some local, patched versions of libraries I'm using here. These patches are all available in the Stackage repo, and I can additionally provide them directly if that would be useful.

cabal --package-db=clear --package-db=global install --dry-run --max-backjumps=-1 AC-Vector-2.3.2 BlastHTTP-1.0.1 BlogLiterately-0.7.1.6 BlogLiterately-diagrams-0.1.4.2 Boolean-0.2.1 ChasingBottoms-1.3.0.7 Diff-0.3.0 FenwickTree-0.1.1 Glob-0.7.5 HTF-0.11.3.4 HTTP-4000.2.15 HUnit-1.2.5.2 HaTeX-3.11.0.0 HaXml-1.24.1 HandsomeSoup-0.3.2 JuicyPixels-3.1.5.2 List-0.5.1 MaybeT-0.1.2 MemoTrie-0.6.2 MonadCatchIO-transformers-0.3.1.0 MonadRandom-0.1.13 NumInstances-1.3 /home/ubuntu/haskell/stackage/patching/tarballs/Octree-0.5.3.tar.gz QuickCheck-2.6 ReadArgs-1.2.1 SHA-1.6.4 abstract-deque-0.3 abstract-par-0.3.3 active-0.1.0.13 ad-4.2.0.1 adjunctions-4.0.3 aeson-0.7.0.3 aeson-pretty-0.7.1 ansi-terminal-0.6.1.1 ansi-wl-pprint-0.6.7.1 arithmoi-0.4.1.0 asn1-data-0.7.1 asn1-encoding-0.8.1.3 asn1-parse-0.8.1 asn1-types-0.2.3 async-2.0.1.5 attoparsec-0.11.3.0 attoparsec-conduit-1.1.0 attoparsec-enumerator-0.3.2 authenticate-1.3.2.8 aws-0.9 base-compat-0.5.0 base-unicode-symbols-0.2.2.4 base16-bytestring-0.1.1.6 base64-bytestring-1.0.0.1 basic-prelude-0.3.8 bifunctors-4.1.1.1 bindings-DSL-1.0.21 bioace-0.0.1 bioalign-0.0.5 biocore-0.3.1 biofasta-0.0.3 biofastq-0.1 biophd-0.0.5 biopsl-0.4 biosff-0.3.7.1 blastxml-0.3.1 blaze-builder-0.3.3.2 blaze-builder-conduit-1.1.0 blaze-builder-enumerator-0.2.0.5 blaze-html-0.7.0.2 blaze-markup-0.6.1.0 blaze-svg-0.3.3.1 blaze-textual-0.2.0.9 bool-extras-0.4.0 bound-1.0.2 /home/ubuntu/haskell/stackage/patching/tarballs/bson-0.2.4.tar.gz byteable-0.1.1 bytedump-1.0 byteorder-1.0.4 /home/ubuntu/haskell/stackage/patching/tarballs/bytes-0.14.tar.gz bytestring-mmap-0.2.2 /home/ubuntu/haskell/stackage/patching/tarballs/bzlib-conduit-0.2.1.1.tar.gz cabal-src-0.2.2.1 cairo-0.12.5.3 case-insensitive-1.2.0.0 cassava-0.4.0.0 cautious-file-1.0.2 cereal-0.4.0.1 cereal-conduit-0.7.2.2 certificate-1.3.9 charset-0.3.7 checkers-0.3.2 chunked-data-0.1.0.1 cipher-aes-0.2.7 cipher-blowfish-0.0.3 cipher-camellia-0.0.2 cipher-des-0.0.6 cipher-rc4-0.1.4 circle-packing-0.1.0.3 classy-prelude-0.9.1 classy-prelude-conduit-0.9.1 classy-prelude-yesod-0.9.1 clientsession-0.9.0.3 cmdargs-0.10.7 colour-2.3.3 comonad-4.0.1 comonad-transformers-4.0 comonads-fd-4.0 compdata-0.8.0.1 composition-1.0.1.0 compressed-3.10 concatenative-1.0.1 concurrent-extra-0.7.0.7 concurrent-supply-0.1.7 conduit-1.1.2.1 conduit-combinators-0.2.5.1 conduit-extra-1.1.0.3 configurator-0.2.0.2 connection-0.2.1 constraints-0.3.5 containers-unicode-symbols-0.3.1.1 contravariant-0.5.2 control-monad-loop-0.1 convertible-1.1.0.0 cookie-0.4.1.1 cpphs-1.18.4 cprng-aes-0.5.2 cpu-0.1.2 crypto-api-0.13 crypto-cipher-tests-0.0.11 crypto-cipher-types-0.0.9 crypto-numbers-0.2.3 crypto-pubkey-0.2.4 crypto-pubkey-types-0.4.2.2 crypto-random-0.0.7 crypto-random-api-0.2.0 cryptocipher-0.6.2 cryptohash-0.11.4 cryptohash-conduit-0.1.1 cryptohash-cryptoapi-0.1.3 css-text-0.1.2.1 csv-conduit-0.6.3 data-binary-ieee754-0.4.4 data-default-0.5.3 data-default-class-0.0.1 data-default-instances-base-0.0.1 data-default-instances-containers-0.0.1 data-default-instances-dlist-0.0.1 data-default-instances-old-locale-0.0.1 data-inttrie-0.1.0 data-lens-light-0.1.0.2 data-memocombinators-0.5.1 data-reify-0.6 derive-2.5.16 diagrams-1.1.0.1 /home/ubuntu/haskell/stackage/patching/tarballs/diagrams-builder-0.5.0.9.tar.gz diagrams-cairo-1.1.0.2 diagrams-contrib-1.1.1.4 diagrams-core-1.1.0.2 diagrams-haddock-0.2.2.7 diagrams-lib-1.1.0.6 diagrams-postscript-1.0.2.4 diagrams-svg-1.0.2.1 digest-0.0.1.2 dimensional-0.13 direct-sqlite-2.3.13 directory-tree-0.11.0 distributive-0.4.4 dlist-0.7.0.1 dlist-instances-0.1 doctest-0.9.11 double-conversion-0.2.0.6 dual-tree-0.2.0.2 either-4.1.1 email-validate-2.0.1 enclosed-exceptions-1.0.0.1 entropy-0.2.2.4 enumerator-0.4.20 eq-4.0.1 erf-2.0.0.0 errorcall-eq-instance-0.1.0 errors-1.4.6 esqueleto-1.4.1 exceptions-0.6.1 extensible-exceptions-0.1.1.4 failure-0.2.0.2 fast-logger-2.1.5 fay-0.20.0.3 fay-base-0.19.1.2 fay-dom-0.4 fay-jquery-0.6.0.2 fay-text-0.3.0.2 fay-uri-0.2.0.0 fb-1.0 fb-persistent-0.3.2 file-embed-0.0.6 filemanip-0.3.6.2 fingertree-0.1.0.0 fixed-list-0.1.5 foldl-1.0.3 force-layout-0.3.0.3 fpco-api-1.1.1.2 free-4.7.1 fsnotify-0.0.11 generic-deriving-1.6.3 ghc-mtl-1.2.1.0 ghc-paths-0.1.0.9 graphs-0.5.0.1 gravatar-0.5.4 groom-0.1.2 groundhog-0.5.0 groundhog-mysql-0.5.0 groundhog-postgresql-0.5.0 groundhog-sqlite-0.5.0 groundhog-th-0.5.0 groupoids-4.0 groups-0.4.0.0 hPDB-1.1.2 hamlet-1.2.0 happstack-server-7.3.5 hashable-1.2.1.0 hashable-extras-0.2 hashtables-1.1.2.1 haskell-lexer-1.0 haskell-names-0.4 haskell-packages-0.2.3.4 haskell-src-exts-1.15.0.1 haxr-3000.10.2 hdaemonize-0.4.5.0 heaps-0.3.1 hebrew-time-0.1.1 heist-0.13.1 hexpat-0.20.6 highlighting-kate-0.5.7.1 hinotify-0.3.7 hint-0.4.2.0 hit-0.6.0 hjsmin-0.1.4.6 hlint-1.8.61 hoogle-4.2.32 hostname-1.0 hourglass-0.1.2 hs-bibutils-5.0 hscolour-1.20.3 hse-cpp-0.1 hslogger-1.2.4 hslua-0.3.12 hspec-1.9.5 hspec-expectations-0.5.0.1 hspec-meta-1.8.3 hsyslog-1.6 html-1.0.1.2 html-conduit-1.1.0.5 http-client-0.3.2.2 http-client-conduit-0.3.0 http-client-tls-0.2.1.1 http-conduit-2.1.2 http-date-0.0.4 http-reverse-proxy-0.3.1.6 http-types-0.8.4 httpd-shed-0.4.0.1 hweblib-0.6.2 hxt-9.3.1.4 hxt-charproperties-9.1.1.1 hxt-http-9.1.4 hxt-regex-xmlschema-9.1.0 hxt-relaxng-9.1.4 hxt-unicode-9.0.2.2 hyphenation-0.4 idna-0.3.0 ieee754-0.7.3 incremental-parser-0.2.3.2 indents-0.3.3 ini-0.2.0 integration-0.2.0.1 intervals-0.7 io-memoize-1.0.0.0 io-streams-1.1.4.3 iterable-2.0 /home/ubuntu/haskell/stackage/patching/tarballs/judy-0.2.2.tar.gz kan-extensions-4.0.2 keter-1.3.0 keys-3.10 kure-2.4.10 language-c-0.4.5 language-ecmascript-0.16.2 language-haskell-extract-0.2.4 language-java-0.2.6 language-javascript-0.5.13 lca-0.2.4 lens-4.1.2 lens-family-th-0.3.0.0 libgit-0.3.0 lifted-async-0.2.0 lifted-base-0.2.2.1 linear-1.10.1.1 list-extras-0.4.1.3 lists-0.4.2 logict-0.6.0.2 machines-0.2.5 markdown-0.1.7.1 markdown-unlit-0.2.0.1 math-functions-0.1.5.2 matrix-0.3.0.0 mime-mail-0.4.5.2 mime-mail-ses-0.2.2.2 mime-types-0.1.0.4 mmap-0.5.9 mmorph-1.0.3 monad-control-0.3.3.0 monad-coroutine-0.8 monad-extras-0.5.8 monad-logger-0.3.6.1 monad-loops-0.4.2 monad-par-0.3.4.6 monad-par-extras-0.3.3 monad-parallel-0.7.1.2 monad-products-4.0.0.1 monad-st-0.2.3 monadic-arrays-0.2.1.3 monads-tf-0.1.0.2 mongoDB-1.4.4 mono-traversable-0.5.0 monoid-extras-0.3.3.2 monoid-subclasses-0.3.6 mtl-2.1.3.1 mwc-random-0.13.1.1 mysql-0.1.1.6 mysql-simple-0.2.2.4 nanospec-0.2.0 nats-0.1.3 network-2.4.2.3 network-conduit-1.1.0 network-conduit-tls-1.1.0 network-info-0.2.0.3 newtype-0.2 numbers-3000.2.0.1 numeric-extras-0.0.3 numtype-1.1 optparse-applicative-0.8.1 pandoc-1.12.4 pandoc-citeproc-0.3.1 pandoc-types-1.12.3.3 parallel-3.2.0.4 parseargs-0.1.5.2 parsec-3.1.5 parsers-0.11 path-pieces-0.1.3.1 patience-0.1.1 pcre-light-0.4.0.2 pem-0.2.2 persistent-1.3.0.6 persistent-mongoDB-1.3.0.4 persistent-sqlite-1.3.0.5 persistent-template-1.3.1.3 pipes-4.1.1 pipes-concurrency-2.0.2 pipes-parse-3.0.1 pointed-4.0 polyparse-1.9 pool-conduit-0.1.2.3 postgresql-libpq-0.9.0.0 postgresql-simple-0.4.2.1 prelude-extras-0.4 pretty-class-0.1 pretty-show-1.6.7 primes-0.2.1.0 primitive-0.5.2.1 /home/ubuntu/haskell/stackage/patching/tarballs/process-conduit-1.1.0.0.tar.gz profunctor-extras-4.0 profunctors-4.0.3 project-template-0.1.4.1 publicsuffixlist-0.1 punycode-2.0 pureMD5-2.1.2.1 pwstore-fast-2.4.1 quickcheck-instances-0.3.8 quickcheck-io-0.1.1 random-1.0.1.1 random-shuffle-0.0.4 reducers-3.10.2 reflection-1.4 regex-applicative-0.3.0.2 regex-base-0.93.2 regex-compat-0.95.1 regex-pcre-builtin-0.94.4.8.8.34 regex-posix-0.95.2 regex-tdfa-1.2.0 resource-pool-0.2.2.0 resourcet-1.1.2.2 rev-state-0.1 rfc5051-0.1.0.3 runmemo-1.0.0.1 safe-0.3.4 scientific-0.2.0.2 securemem-0.1.3 semigroupoid-extras-4.0 semigroupoids-4.0.2 semigroups-0.12.2 sendfile-0.7.9 seqloc-0.5.1.1 setenv-0.1.1.1 shake-0.12 shakespeare-2.0.0.3 shakespeare-css-1.1.0 shakespeare-i18n-1.1.0 shakespeare-js-1.3.0 shakespeare-text-1.1.0 shelly-1.5.3.1 silently-1.2.4.1 simple-reflect-0.3.2 simple-sendfile-0.2.14 siphash-1.0.3 skein-1.0.9 smallcheck-1.1.1 smtLib-1.0.7 snap-0.13.2.5 snap-core-0.9.6.2 snap-server-0.9.4.4 snaplet-fay-0.3.3.5 socks-0.5.4 sourcemap-0.1.3.0 spawn-0.3 speculation-1.5.0.1 split-0.2.2 spoon-0.3.1 sqlite-simple-0.4.7.0 statestack-0.2 /home/ubuntu/haskell/stackage/patching/tarballs/statistics-0.10.5.2.tar.gz stm-2.4.3 stm-chans-3.0.0.2 stm-conduit-2.4.0 stm-stats-0.2.0.0 storable-endian-0.2.5 streaming-commons-0.1.2.3 streams-3.2 strict-0.3.2 stringable-0.1.3 stringbuilder-0.4.0 stringprep-1.0.0 stringsearch-0.3.6.5 stylish-haskell-0.5.10.0 syb-0.4.1 system-fileio-0.3.13 system-filepath-0.4.10 system-posix-redirect-1.1.0.1 tagged-0.7.2 tagshare-0.0 tagsoup-0.13.1 tagstream-conduit-0.5.5.1 tar-0.4.0.1 tardis-0.3.0.0 tasty-0.8.0.4 tasty-golden-2.2.1.1 tasty-hunit-0.8.0.1 tasty-quickcheck-0.8 tasty-smallcheck-0.8 tasty-th-0.1.1 temporary-1.2.0.2 temporary-rc-1.2.0.3 terminfo-0.4.0.0 test-framework-0.8.0.3 test-framework-hunit-0.3.0.1 test-framework-quickcheck2-0.3.0.3 test-framework-th-0.2.4 test-framework-th-prime-0.0.6 testing-feat-0.4.0.2 texmath-0.6.6.1 text-1.1.1.2 text-format-0.3.1.1 text-icu-0.6.3.7 texts-0.3.1 tf-random-0.5 th-expand-syns-0.3.0.4 threads-0.5.1.1 thyme-0.3.3.0 time-compat-0.1.0.3 time-lens-0.4.0.1 tls-1.2.7 tls-debug-0.3.3 transformers-base-0.4.2 transformers-compat-0.3 traverse-with-class-0.1.1.1 tree-view-0.4 type-eq-0.4.2 udbus-0.2.0 unbounded-delays-0.1.0.7 uniplate-1.6.12 /home/ubuntu/haskell/stackage/patching/tarballs/uniqueid-0.1.1.tar.gz unix-compat-0.4.1.1 unix-time-0.2.2 unordered-containers-0.2.4.0 utf8-light-0.4.2 utf8-string-0.3.7 uuid-1.3.3 vault-0.3.0.3 vector-0.10.9.1 vector-algorithms-0.6.0.1 vector-binary-instances-0.2.1.0 vector-instances-3.3 vector-space-0.8.6 vector-space-points-0.2 vector-th-unbox-0.2.0.2 vhd-0.2.2 void-0.6.1 wai-2.1.0.2 wai-app-static-2.0.1 wai-eventsource-2.0.0.2 wai-extra-2.1.1.1 wai-logger-2.1.1 wai-test-2.0.1.2 wai-websockets-2.1.0.1 warp-2.1.5.1 warp-tls-2.0.5 web-fpco-0.1.1.0 websockets-0.8.2.2 wl-pprint-1.1 wl-pprint-extras-3.5 wl-pprint-terminfo-3.7.1 word8-0.0.4 x509-1.4.11 x509-store-1.4.4 x509-system-1.4.5 x509-validation-1.5.0 xenstore-0.1.1 xhtml-3000.2.1 xml-1.3.13 xml-conduit-1.2.0.1 xml-types-0.3.4 xmlgen-0.6.2.1 xmlhtml-0.2.3.2 xss-sanitize-0.3.5.2 yackage-0.7.0.3 yaml-0.8.8.2 yesod-1.2.5.2 yesod-auth-1.3.0.4 yesod-auth-fb-1.6.2.1 yesod-bin-1.2.9.1 yesod-core-1.2.15.1 yesod-eventsource-1.1.0.2 yesod-fay-0.5.2 yesod-fb-0.3.2 yesod-form-1.3.8.3 yesod-newsfeed-1.2.0.2 yesod-persistent-1.2.2.3 yesod-routes-1.2.0.6 yesod-sitemap-1.2.0 yesod-static-1.2.3 yesod-test-1.2.1.5 yesod-websockets-0.1.0.0 zip-archive-0.2.2.1 zlib-0.5.4.1 zlib-bindings-0.1.1.5 zlib-conduit-1.1.0 zlib-enum-0.2.3

trying: BlastHTTP-1.0.1 (user goal)
trying: transformers-0.3.0.0/installed-7df... (dependency of BlastHTTP-1.0.1)
trying: transformers-compat-0.3 (user goal)
rejecting: transformers-compat-0.3:-transformers2 (conflict:
transformers==0.3.0.0/installed-7df..., transformers-compat-0.3:transformers2
=> transformers>=0.4 && <0.5)
rejecting: transformers-compat-0.3:+transformers2 (conflict:
transformers==0.3.0.0/installed-7df..., transformers-compat-0.3:transformers2
=> transformers>=0.2 && <0.3)
Dependency tree exhaustively searched.
Resolving dependencies...
cabal returned a bad result, exiting
23Skidoo commented 10 years ago

/cc @kosmikus

bergey commented 10 years ago

I'm also having trouble with transformers-compat. See for instance https://travis-ci.org/diagrams/diagrams-cairo/jobs/25420386 starting around line 342. It looks as though Cabal never tries transformers-compat-0.3:+transformers3 (which is what I'd like to install), and instead falls back to transformers-compat-0.1.1, which had fewer flags.

kosmikus commented 10 years ago

This looks worrying. To summarize: it shouldn't happen that a solution is found with --reorder-goals, but no solution is found without, and the tree has been searched exhaustively.

I suspect a subtle bug in the computation or interpretation of conflict sets during backjumping.

I will look into this.

twittner commented 10 years ago

I encountered the same issue. The following cabal file seems to reproduce the problem:

name:          test
version:       0.1
build-type:    Simple
cabal-version: >= 1.10

library
    default-language: Haskell2010
    build-depends:
        base   >= 4.6   && < 4.8
      , errors == 1.4.7
kosmikus commented 10 years ago

Ok, I cannot tell yet whether all of this is the same issue. But I can say that I've tracked down the cause of what @bergey describes to a combination of two issues that, once solved, may or may not fix the others, too.

One issue is that manual flags may under certain circumstances cause parts of the search tree to be discarded. The flag transformers2 in transformers-compat is such a flag. This one is trivial to fix.

The other issue is that flag dependencies are not properly taken into account when computing conflict sets. Here, transformers2 depends on transformers3, because it appears in a nested if-statement in the Cabal file. This bug is easy to work around in a conservative way that makes it clear to me that this is indeed the culprit. However, the fix is a hack and may cause performance problems in unrelated areas. I'm working on fixing it properly now. Once I've done that, I'll try to figure out whether that fixes the other problems described here.

snoyberg commented 10 years ago

@kosmikus This sounds like an issue @cartazio opened against text-stream-decode (https://github.com/fpco/text-stream-decode/issues/1). I'm not sure if he ever turned it into a cabal-install issue, so linking to it here in case it helps.

kosmikus commented 10 years ago

@snoyberg @cartazio From a quick look, it seems as if fpco/text-stream-decode#1 is more related to https://github.com/bos/aeson/issues/177 and #1831 than this one.

kosmikus commented 10 years ago

Some more comments: The problem by @bergey should be fixed by the pull request I just sent. The test case provided by @twittner, too (thanks!). It should also fix the related problem reported on the cabal-devel mailing list today by Björn Peemöller (http://www.haskell.org/pipermail/cabal-devel/2014-May/009795.html). I cannot check the original test case provided by @snoyberg easily, but at least it should no longer report "Dependency tree exhaustively searched." It could still be that --max-backjumps=-1 takes significantly longer than --reorder-goals, though, or leads to a different (yet technically also valid) install plan.

The keter problem reported by @snoyberg in #1877 is not fixed by this. This looks like it's caused by "strong flag handling" instead, which is related to bos/aeson#177 and #1831 (and, as @snoyberg pointed out earlier, probably to fpco/text-stream-decode#1, too). I'll say more about this soon.

gibiansky commented 10 years ago

I am also seeing something like this with ihaskell and cabal-install version 1.20. If you create an empty sandbox and do cabal install ihaskell --reorder-goals it works, but if you don't have the flag you get a dependency tree exhaustively searched message and it dies.

See outputs for these two cases here: https://gist.github.com/gibiansky/a865467338945ece890c

kosmikus commented 10 years ago

@gibiansky This is just exactly the same issue, even triggered by the same package again (transformers-compat), so pull request #1878 should fix it.

gibiansky commented 10 years ago

@kosmikus Alright, cool, glad there's a fix on the way.

ekmett commented 10 years ago

Practically, if I were to remove the transformers2 flag from the package giving up on GHC 7.0.x would that resolve this issue?

kosmikus commented 10 years ago

@ekmett It would probably fix the issue without people having to upgrade cabal-install, yes. But I haven't really looked at the problem from this perspective yet. I can try to think about whether there's a "better" change for transformers-compat that would still work around this problem.

ekmett commented 10 years ago

Thanks. I need to get this to work for users with older cabals as well, because of the very purpose of the package, so if I'm forced into releasing a suboptimal version of the package simply to fix the issue, then I guess that is just the price I have to pay.

snoyberg commented 10 years ago

@ekmett It's a maintenance nightmare, but...

What about releasing three versions of transformers-compat:

And then cabal will simply select which of those three versions it uses based on the version of transformers. I think that will address the current problem.

kosmikus commented 10 years ago

@ekmett What @snoyberg suggests should work. Another option I could think of is to go to two separate transformers-compat packages, each with just one flag. One (let's call it t4 makes the decision between version 4 or else (and either depends on transformers == 0.4.* or on t3). The other (t3) makes the decision between version 3 or lower (and either depends on transformers == 0.3.* or on `transformers == 0.2.*. This way, you also avoid the nested flags.

ekmett commented 10 years ago

I could go for that solution if it is the only thing that works.

That said, it'd be a deliberately breaking @mightybyte's "implicit blacklisting" notion.

http://softwaresimply.blogspot.com/2014/05/implicit-blacklisting-for-cabal.html

If we did that on the minor version instead then his notion would still remain intact.

-Edward

On Tue, May 20, 2014 at 10:47 AM, Michael Snoyman notifications@github.comwrote:

@ekmett https://github.com/ekmett It's a maintenance nightmare, but...

What about releasing three versions of transformers-compat:

  • Version 0.3.3.1 will have a dependency transformers == 0.2.*
  • Version 0.3.3.2 will have a dependency transformers == 0.3.*
  • Version 0.3.3.3 will have a dependency transformers == 0.4.*

And then cabal will simply select which of those three versions it uses based on the version of transformers. I think that will address the current problem.

— Reply to this email directly or view it on GitHubhttps://github.com/haskell/cabal/issues/1855#issuecomment-43635727 .

snoyberg commented 10 years ago

Minor version instead of patch seems fine to me. I didn't have any strong reason for one vs the other.

mietek commented 10 years ago

I also encountered the flag issue, with ghc-7.8.2, cabal-install-1.20.0.2, and the following package description, generated by the snap scaffolding tool. Removing all mentions of the old-base flag from the package description helped me, however, specifying --reorder-goals did not.

Name:                snap-test
Version:             0.1
Synopsis:            Project Synopsis Here
Description:         Project Description Here
License:             AllRightsReserved
Author:              Author
Maintainer:          maintainer@example.com
Stability:           Experimental
Category:            Web
Build-type:          Simple
Cabal-version:       >=1.2

Flag development
  Description: Whether to build the server in development (interpreted) mode
  Default: False

Flag old-base
  default: False
  manual: False

Executable snap-test
  hs-source-dirs: src
  main-is: Main.hs

  Build-depends:
    bytestring                >= 0.9.1   && < 0.11,
    heist                     >= 0.13    && < 0.14,
    MonadCatchIO-transformers >= 0.2.1   && < 0.4,
    mtl                       >= 2       && < 3,
    snap                      >= 0.13    && < 0.14,
    snap-core                 >= 0.9     && < 0.11,
    snap-server               >= 0.9     && < 0.11,
    snap-loader-static        >= 0.9     && < 0.10,
    snaplet-postgresql-simple >= 0.5     && < 0.6,
    text                      >= 0.11    && < 1.2,
    time                      >= 1.1     && < 1.5,
    xmlhtml                   >= 0.1

  if flag(old-base)
    build-depends:
      base                      >= 4        && < 4.4,
      lens                      >= 3.7.6    && < 3.8
  else
    build-depends:
      base                      >= 4.4      && < 5,
      lens                      >= 3.7.6    && < 4.2

  if flag(development)
    build-depends:
      snap-loader-dynamic == 0.10.*
    cpp-options: -DDEVELOPMENT
    -- In development mode, speed is already going to suffer, so skip
    -- the fancy optimization flags.  Additionally, disable all
    -- warnings.  The hint library doesn't give an option to execute
    -- compiled code when there were also warnings, so disabling
    -- warnings allows quicker workflow.
    ghc-options: -threaded -w
  else
    if impl(ghc >= 6.12.0)
      ghc-options: -threaded -Wall -fwarn-tabs -funbox-strict-fields -O2
                   -fno-warn-orphans -fno-warn-unused-do-bind
    else
      ghc-options: -threaded -Wall -fwarn-tabs -funbox-strict-fields -O2
                   -fno-warn-orphans

Symptoms:

cabal: Could not resolve dependencies:
trying: snap-test-0.1 (user goal)
trying: lens-4.1.2.1 (dependency of snap-test-0.1)
trying: transformers-compat-0.3.3 (dependency of lens-4.1.2.1)
trying: transformers-0.3.0.0/installed-7df... (dependency of lens-4.1.2.1)
rejecting: transformers-compat-0.3.3:-two (conflict:
transformers==0.3.0.0/installed-7df..., transformers-compat-0.3.3:two =>
transformers>=0.4.1 && <0.5)
rejecting: transformers-compat-0.3.3:+two (conflict:
transformers==0.3.0.0/installed-7df..., transformers-compat-0.3.3:two =>
transformers>=0.2 && <0.3)
Backjump limit reached (change with --max-backjumps).
kosmikus commented 10 years ago

@mietek Thanks for the report, but this is not the same issue. The original problem was that a build plan was not found in a situation where one existed. Your example is just one that takes longer (and more backjumps) than the pre-set backjump limit. It's indeed curious that computing a build plan for this package takes so long without --reorder-goals, but I've just verified that it does indeed compute ultimately, so it's a performance bug, not a completeness bug. See #1780 about more discussion on --reorder-goals. I'm inclined to close this bug, because it's already confusing enough with all the discussion, and the original issue is now fixed. We could open a new bug reminding us that we should try to enhance the default heuristics to improve overall performance and avoid cases such as this one.

kosmikus commented 10 years ago

@mietek Hmm. While it's qualitatively not the same, there's still something strange going on which may potentially be related to the original bug not being properly fixed. Leaving this open for now, will investigate further asap.

kosmikus commented 10 years ago

@mietek Ok, unfortunately I'm now certain that there's still a bug related to the original issue, and that the fix in cabal-install-1.20.0.2 is, as sad as it is, incomplete. Apologies for doubting you :) I'll need to think about this carefully. I don't want to fix this improperly again, and the fact that the first fix wasn't complete shows that I've clearly underestimated the complexity of the underlying problem. In the short term, if you run into any issues, a workaround is still to set the flags of the transformers-compat package explicitly, via --constraint.

snoyberg commented 10 years ago

@kosmikus @ekmett I had to add a patch to Stackage about this recently as well. Edward: is there any chance of getting some patched versions of transformers-compat onto Hackage as we discussed earlier in this issue?

ekmett commented 10 years ago

Now that it is clear that the elegant version, which was going to be a third of the maintenance effort will not work; yes. ;)

kosmikus commented 10 years ago

I am not fully convinced that a further patch to transformers-compat is necessary. For all I can see, the latest version Edward uploaded fixes the issue for all older cabal-install versions, but ironically breaks once again for 1.20.0.2 (Edward's and my hack and my apparently improper fix cancel each other out). So everyone who is reluctant to upgrade cabal-install is probably fine right now (if not, please let me know more details). Those who are not reluctant to upgrade will probably also upgrade again once I fix this (and this time, hopefully, properly).

ekmett commented 10 years ago

Fair enough. I'll hold back and let you come up with a fix.

On Thu, May 29, 2014 at 5:51 PM, kosmikus notifications@github.com wrote:

I am not fully convinced that a further patch to transformers-compat is necessary. For all I can see, the latest version Edward uploaded fixes the issue for all older cabal-install versions, but ironically breaks once again for 1.20.0.2 (Edward's and my hack and my apparently improper fix cancel each other out). So everyone who is reluctant to upgrade cabal-install is probably fine right now (if not, please let me know more details). Those who are not reluctant to upgrade will probably also upgrade again once I fix this (and this time, hopefully, properly).

— Reply to this email directly or view it on GitHub https://github.com/haskell/cabal/issues/1855#issuecomment-44590216.

snoyberg commented 10 years ago

Just to throw in some more data:

$ cabal --version
cabal-install version 1.18.0.4
using version 1.18.1.3 of the Cabal library 
$ ghc --version
The Glorious Glasgow Haskell Compilation System, version 7.8.2
$ cabal install transformers-compat-0.3.3.4 --constraint 'transformers < 0.4'
Resolving dependencies...
cabal: Could not resolve dependencies:
trying: transformers-compat-0.3.3.4 (user goal)
trying: transformers-compat-0.3.3.4:-three
next goal: transformers (dependency of transformers-compat-0.3.3.4)
rejecting: transformers-0.3.0.0/installed-7df... (conflict:
transformers-compat-0.3.3.4:three => transformers>=0.4.1 && <0.5)
rejecting: transformers-0.4.1.0, 0.4.0.0 (global constraint requires <0.4)
rejecting: transformers-0.3.0.0, 0.2.2.1, 0.2.2.0, 0.2.1.0, 0.2.0.0, 0.1.4.0,
0.1.3.0, 0.1.1.0, 0.1.0.1, 0.1.0.0, 0.0.1.0, 0.0.0.0 (conflict:
transformers-compat-0.3.3.4:three => transformers>=0.4.1 && <0.5)
Dependency tree exhaustively searched.
ubuntu@picard-precise:~$ cabal version
cabal: unrecognised command: version (try --help)

And:

~$ cabal --version
cabal-install version 1.20.0.2
using version 1.20.0.0 of the Cabal library 
$ ghc --version
The Glorious Glasgow Haskell Compilation System, version 7.8.2
$ cabal install transformers-compat-0.3.3.4 --constraint 'transformers < 0.4'
Resolving dependencies...
cabal: Could not resolve dependencies:
trying: transformers-compat-0.3.3.4 (user goal)
trying: transformers-compat-0.3.3.4:-three
next goal: transformers (dependency of transformers-compat-0.3.3.4)
rejecting: transformers-0.3.0.0/installed-7df... (conflict:
transformers-compat-0.3.3.4:three => transformers>=0.4.1 && <0.5)
rejecting: transformers-0.4.1.0, 0.4.0.0 (global constraint requires <0.4)
rejecting: transformers-0.3.0.0, 0.2.2.1, 0.2.2.0, 0.2.1.0, 0.2.0.0, 0.1.4.0,
0.1.3.0, 0.1.1.0, 0.1.0.1, 0.1.0.0, 0.0.1.0, 0.0.0.0 (conflict:
transformers-compat-0.3.3.4:three => transformers>=0.4.1 && <0.5)
Dependency tree exhaustively searched.

I just ran into this when trying to update a customer's codebase to newer package versions. My current workaround is patching transformers-compat in Stackage to avoid any conditionals (since in Stackage, we're pegged at transformers-0.3.0.0).

kosmikus commented 10 years ago

@snoyberg This latest behaviour you're reporting is correct. In transformers-compat-0.3.3.4, the flags two and three are both set to manual, and they're both False by default, which means a dependency on transformers >= 0.4.1 which in combination with your explicit constraint simply cannot be resolved.

ekmett commented 10 years ago

Something like 

cabal install transformers-compat
  --constraint 'transformers < 0.4' 
  --constraint 'transformers-compat >= 0.3.3'

should work

snoyberg commented 10 years ago

Yes, my mistake with the overly restrictive bounds. The transformers-compat issue does seem to be resolved now.

idontgetoutmuch commented 10 years ago

How is this resolved? I try installing ad in a fresh sandbox and it fails with

$ cabal install ad
Resolving dependencies...
cabal: Could not resolve dependencies:
trying: ad-4.2.0.1 (user goal)
trying: transformers-0.3.0.0/installed-da9... (dependency of ad-4.2.0.1)
trying: free-4.7.1 (dependency of ad-4.2.0.1)
trying: semigroupoids-4.0.2 (dependency of free-4.7.1)
trying: contravariant-0.5.2 (dependency of semigroupoids-4.0.2)
trying: transformers-compat-0.3 (dependency of contravariant-0.5.2)
rejecting: transformers-compat-0.3:-transformers2 (conflict:
transformers==0.3.0.0/installed-da9..., transformers-compat-0.3:transformers2
=> transformers>=0.4 && <0.5)
rejecting: transformers-compat-0.3:+transformers2 (conflict:
transformers==0.3.0.0/installed-da9..., transformers-compat-0.3:transformers2
=> transformers>=0.2 && <0.3)
Dependency tree exhaustively searched.

Note: when using a sandbox, all packages are required to have consistent
dependencies. Try reinstalling/unregistering the offending packages or
recreating the sandbox.

But all is well if I do

$ cabal install ad --reorder-goals
Resolving dependencies...
Notice: installing into a sandbox located at
.cabal-sandbox
Downloading data-reify-0.6...
Configuring erf-2.0.0.0...
Downloading prelude-extras-0.4...
Configuring nats-0.1.3...
Building nats-0.1.3...
Building erf-2.0.0.0...
Configuring data-reify-0.6...
Downloading tagged-0.7.2...
Downloading transformers-compat-0.3...
Configuring prelude-extras-0.4...
Building data-reify-0.6...
Building prelude-extras-0.4...
Installed erf-2.0.0.0
Configuring tagged-0.7.2...
Configuring transformers-compat-0.3...
Installed nats-0.1.3
Building tagged-0.7.2...
Building transformers-compat-0.3...
Configuring semigroups-0.12.2...
Installed data-reify-0.6
Building semigroups-0.12.2...
Installed prelude-extras-0.4
Installed tagged-0.7.2
Downloading reflection-1.4...
Configuring reflection-1.4...
Building reflection-1.4...
Installed reflection-1.4
Installed transformers-compat-0.3
Downloading contravariant-0.5.2...
Downloading distributive-0.4.4...
Configuring distributive-0.4.4...
Configuring contravariant-0.5.2...
Building contravariant-0.5.2...
Building distributive-0.4.4...
Installed contravariant-0.5.2
Installed distributive-0.4.4
Installed semigroups-0.12.2
Downloading comonad-4.0.1...
Configuring comonad-4.0.1...
Building comonad-4.0.1...
Installed comonad-4.0.1
Downloading semigroupoids-4.0.2...
Configuring semigroupoids-4.0.2...
Building semigroupoids-4.0.2...
Installed semigroupoids-4.0.2
Downloading bifunctors-4.1.1.1...
Downloading profunctors-4.0.4...
Configuring bifunctors-4.1.1.1...
Configuring profunctors-4.0.4...
Building bifunctors-4.1.1.1...
Building profunctors-4.0.4...
Installed profunctors-4.0.4
Installed bifunctors-4.1.1.1
Downloading free-4.7.1...
Configuring free-4.7.1...
Building free-4.7.1...
Installed free-4.7.1
Downloading ad-4.2.0.1...
Configuring ad-4.2.0.1...
Building ad-4.2.0.1...
Installed ad-4.2.0.1
kosmikus commented 10 years ago

What version of cabal-install is this? Also, do you have the latest Hackage data? It's strange that free-4.7.1 is selected despite free-4.9 being available, and it's also strange that transformers-compat-0.3 is selected despite later versions being available.

idontgetoutmuch commented 10 years ago 
cabal-install version 1.18.0.3
using version 1.18.1.3 of the Cabal library

I am using stackage not hackage

remote-repo: ghc78alpha:http://www.stackage.org/alias/fpcomplete/ghc78-alpha
snoyberg commented 10 years ago

There are two things which, together, are causing this problem:

  1. cabal-install-1.18.0.3 is still buggy (1.18.0.4 seems to have this issue resolved).
  2. I added a patch to Stackage to completely bypass this bug by removing all of the conditionals from the transformers-compat cabal file. However, the snapshot you're using still has the conditionals, thus triggering the bug.

Why don't we follow up privately about the best way to address this issue (either moving to a new snapshot, or upgrading cabal-install). Can you email me?

idontgetoutmuch commented 10 years ago

Ok following up privately.

kosmikus commented 10 years ago

I think only 1.20.0.3 and 1.18.0.5 are truly ok as far as cabal-install is concerned.

snoyberg commented 10 years ago

@kosmikus I think you're right, but for this specific bug, I think 1.18.0.4 does not reproduce the issue.

kosmikus commented 10 years ago

@snoyberg Quite possible. I'm just saying that if anyone is taking the effort to upgrade cabal-install, they should rather go to 1.18.0.5, because 1.18.0.4 is known to still be buggy.

letmaik commented 9 years ago

More data:

$ cabal --version
cabal-install version 1.22.0.0
using version 1.22.0.0 of the Cabal library
$ cabal install buildwrapper scion-browser hoogle stylish-haskell hlint
Resolving dependencies...
cabal: Could not resolve dependencies:
trying: buildwrapper-0.9.1 (user goal)
trying: conduit-extra-1.1.6.2 (dependency of buildwrapper-0.9.1)
trying: streaming-commons-0.1.9.1 (dependency of conduit-extra-1.1.6.2)
trying: random-1.1 (dependency of streaming-commons-0.1.9.1)
trying: aeson-0.8.0.2 (dependency of buildwrapper-0.9.1)
trying: template-haskell-2.9.0.0/installed-6d2... (dependency of
aeson-0.8.0.2)
trying: scion-browser-0.5.0 (user goal)
next goal: parallel-io (dependency of scion-browser-0.5.0)
rejecting: parallel-io-0.3.3, 0.3.2.2, 0.3.2.1 (conflict: random==1.1,
parallel-io => random>=1.0 && <1.1)
rejecting: parallel-io-0.3.2, 0.3.1, 0.3.0.2, 0.3.0.1 (conflict:
template-haskell => containers==0.5.5.1/installed-d4b..., parallel-io =>
containers>=0.2 && <0.5)
rejecting: parallel-io-0.3.0 (conflict: template-haskell =>
containers==0.5.5.1/installed-d4b..., parallel-io => containers>=0.3 && <0.4)
rejecting: parallel-io-0.2.2, 0.2.1.1, 0.2.1, 0.2 (conflict: scion-browser =>
parallel-io>=0.3)
Backjump limit reached (change with --max-backjumps).

While with --reorder-goals it works.

bergmark commented 9 years ago

@neothemachine you should test that with --max-backjumps=-1, it stopped before the search space was exhausted.

letmaik commented 9 years ago

Well, after 15min of 100% CPU usage and 3.5GiB memory usage I killed cabal-install.

On 02/09/2015 06:35 PM, Adam Bergmark wrote:

@neothemachine https://github.com/neothemachine you should test that with --max-backjumps=-1, it stopped before the search space was exhausted.

— Reply to this email directly or view it on GitHub https://github.com/haskell/cabal/issues/1855#issuecomment-73552269.

kosmikus commented 9 years ago

Sorry for not following up properly on this. I actually believe this is fixed since 5b63fce601997009376522c5de9b11275c3681ee. I'm closing this bug. If after that there are still problems, please reopen or better, open a new issue.

(And because several things are mixed up in this thread, let me just reiterate: Adding or removing --reorder-goals may affect the time needed to find a solution dramatically. While this is unfortunate, it's not, strictly speaking, a bug. It's the reason this flag exists in the first place. It is a bug if without --reorder-goals, no solution is found with Dependency tree exhaustively searched., and with the flag, there suddenly is a solution; or the other way round.)

altaic commented 8 years ago

I apologize if this is somewhat off-topic. Why not have cabal automatically fall back to reordering goals in the event of the dependency tree being exhaustively searched? If one is supposed to try adding the --reorder-goals flag after getting that error, it seems like it'd be good if cabal just did it without intervention.

hvr commented 8 years ago

@altaic because it is a bug (that needs to be fixed rather than workarounded). The set of solutions is supposed to be equal whether you give --reorder-goals or not. It's just a different traversal of the same space.