cabal doesn't find a non-destructive install plan

[UnkindPartition]

See UnkindPartition/tasty#80

The gist of it is that cabal unnecessarily suggests upgrading mtl from a globally installed version, then refuses to do it.

I thought the solver introduces constraints for the installed packages, but that didn't happen here, apparently.

[23Skidoo]

/cc @kosmikus

[kosmikus]

I may have a fix for this, but it requires more testing. It's all about tweaking heuristics, so it's potentially creating more problems than it solves.

In general, there's no guarantee that a non-destructive install plan is chosen if there is one. You only have such a guarantee if you say --avoid-reinstalls.

The solver locally prefers an already installed package over any other version. However, whether that preference is respected depends on what other choices the solver has made already at this point.

I'm going to explain the situation here, for future reference, also to myself. We're trying to install tasty with ghc-7.6.3 plus Haskell Platform as a basis.

Doing so gives us this:

$ cabal install --dry-run tasty -v3
[...]
Choosing modular solver.
Resolving dependencies...
[__0] trying: tasty-0.10.1 (user goal)
[__1] trying: base-4.6.0.1/installed-02a... (dependency of tasty-0.10.1)
[__2] trying: rts-1.0/installedbuil... (dependency of base-4.6.0.1/installed-02a...)
[__3] trying: integer-gmp-0.5.0.0/installed-2f1... (dependency of base-4.6.0.1/installed-02a...)
[__4] trying: ghc-prim-0.3.0.0/installed-d52... (dependency of base-4.6.0.1/installed-02a...)
[__5] trying: time-1.4.0.1/installed-0e9... (dependency of tasty-0.10.1)
[__6] trying: old-locale-1.0.0.5/installed-672... (dependency of time-1.4.0.1/installed-0e9...)
[__7] trying: ansi-terminal-0.6.2.1 (dependency of tasty-0.10.1)
[__8] trying: unix-2.6.0.1/installed-8e7... (dependency of ansi-terminal-0.6.2.1)
[__9] trying: bytestring-0.10.0.2/installed-af9... (dependency of unix-2.6.0.1/installed-8e7...)
[_10] trying: async-2.0.1.4/installed-d29... (dependency of tasty-0.10.1)
[_11] trying: unbounded-delays-0.1.0.8 (dependency of tasty-0.10.1)
[_12] trying: deepseq-1.3.0.1/installed-67a... (dependency of tasty-0.10.1)
[_13] trying: array-0.4.0.1/installed-6ee... (dependency of deepseq-1.3.0.1/installed-67a...)
[_14] trying: optparse-applicative-0.11.0.1 (dependency of tasty-0.10.1)
[_15] trying: ansi-wl-pprint-0.6.7.1 (dependency of optparse-applicative-0.11.0.1)
[_16] trying: process-1.1.0.2/installed-ab4... (dependency of optparse-applicative-0.11.0.1)
[_17] trying: filepath-1.3.0.1/installed-c5d... (dependency of process-1.1.0.2/installed-ab4...)
[_18] trying: directory-1.2.0.1/installed-e1c... (dependency of process-1.1.0.2/installed-ab4...)
[_19] trying: transformers-compat-0.3.3.4 (dependency of optparse-applicative-0.11.0.1)
[_20] trying: transformers-compat-0.3.3.4:-two
[_21] trying: transformers-compat-0.3.3.4:-three
[_22] next goal: transformers (dependency of optparse-applicative-0.11.0.1)
[_22] rejecting: transformers-0.3.0.0/installed-300... (conflict: transformers-compat-0.3.3.4:three => transformers>=0.4.1 && <0.5)
[_22] trying: transformers-0.4.2.0
[_23] trying: regex-tdfa-rc-1.1.8.3 (dependency of tasty-0.10.1)
[_24] trying: parsec-3.1.3/installed-846... (dependency of regex-tdfa-rc-1.1.8.3)
[_25] trying: text-0.11.3.1/installed-bb8... (dependency of parsec-3.1.3/installed-846...)
[_26] trying: regex-base-0.93.2/installed-0be... (dependency of regex-tdfa-rc-1.1.8.3)
[_27] trying: tagged-0.7.3 (dependency of tasty-0.10.1)
[_28] next goal: mtl (dependency of tasty-0.10.1)
[_28] rejecting: mtl-2.1.2/installed-c30... (conflict: transformers==0.4.2.0, mtl => transformers==0.3.0.0/installed-300...)
[_28] rejecting: mtl-2.2.1, 2.2.0.1, 2.2, 2.1.3.1, 2.1.2, 2.1.1, 2.1, 2.0.1.1, 2.0.1.0, 2.0.0.0, 1.1.1.1, 1.1.1.0, 1.1.0.2, 1.1.0.1, 1.1.0.0, 1.0 (conflict: parsec => mtl==2.1.2/installed-c30...)
[_25] fail (backjumping, conflict set: mtl, optparse-applicative, parsec, regex-tdfa-rc, tasty, transformers)
[_24] trying: parsec-3.1.7
[_25] trying: parsec-3.1.7:!test
[_26] trying: text-0.11.3.1/installed-bb8... (dependency of parsec-3.1.7)
[_27] trying: regex-base-0.93.2/installed-0be... (dependency of regex-tdfa-rc-1.1.8.3)
[_28] trying: tagged-0.7.3 (dependency of tasty-0.10.1)
[_29] next goal: mtl (dependency of tasty-0.10.1)
[_29] rejecting: mtl-2.1.2/installed-c30... (conflict: transformers==0.4.2.0, mtl => transformers==0.3.0.0/installed-300...)
[_29] rejecting: mtl-2.2.1, 2.2.0.1, 2.2, 2.1.3.1, 2.1.2, 2.1.1, 2.1, 2.0.1.1, 2.0.1.0, 2.0.0.0, 1.1.1.1, 1.1.1.0, 1.1.0.2, 1.1.0.1, 1.1.0.0, 1.0 (conflict: regex-base => mtl==2.1.2/installed-c30...)
[_28] fail (backjumping, conflict set: mtl, optparse-applicative, regex-base, regex-tdfa-rc, tasty, transformers)
[_27] trying: regex-base-0.93.2
[_28] trying: tagged-0.7.3 (dependency of tasty-0.10.1)
[_29] next goal: mtl (dependency of tasty-0.10.1)
[_29] rejecting: mtl-2.1.2/installed-c30... (conflict: transformers==0.4.2.0, mtl => transformers==0.3.0.0/installed-300...)
[_29] trying: mtl-2.2.1
[_30] trying: containers-0.5.0.0/installed-71f... (dependency of tasty-0.10.1)
[_31] trying: stm-2.4.2/installed-67e... (dependency of tasty-0.10.1)
[_32] trying: ansi-terminal-0.6.2.1:-example
[_33] trying: ansi-wl-pprint-0.6.7.1:-example
[_34] trying: ansi-wl-pprint-0.6.7.1:+newbase
[_35] trying: regex-tdfa-rc-1.1.8.3:+base4
[_36] trying: parsec-3.1.7:+base4
[_37] trying: regex-base-0.93.2:+newbase
[_38] trying: regex-base-0.93.2:+splitbase
[_39] done
In order, the following would be installed:
ansi-terminal-0.6.2.1 (new package)
ansi-wl-pprint-0.6.7.1 (new package)
tagged-0.7.3 (new package)
transformers-0.4.2.0 (new version)
mtl-2.2.1 (new version)
parsec-3.1.7 (new version)
regex-base-0.93.2 (reinstall) changes: mtl-2.1.2 -> 2.2.1
regex-tdfa-rc-1.1.8.3 (new package)
transformers-compat-0.3.3.4 (new package)
optparse-applicative-0.11.0.1 (new package)
unbounded-delays-0.1.0.8 (new package)
tasty-0.10.1 (new package)
Warning: The following packages are likely to be broken by the reinstalls:
regex-posix-0.95.2
regex-compat-0.95.1
haskell-platform-2013.2.0.0
Use --force-reinstalls if you want to install anyway.

We end up with the undesired upgrade of mtl. Why? Well, tasty depends on (uninstalled) optparse-applicative, which defaults to the latest version, and optparse-applicative depends on (uninstalled) transformers-compat, which defaults to the latest version, and that in turn pulls in the latest version of transformers, and that then causes the installed version of mtl to be incompatible.

Note that rejecting a different version of mtl at this point is dangerous. It's not clear that there are any valid solutions without upgrading mtl at this point. Similarly, rejecting a reinstlal of regex-base at this point is dangerous, because it's not clear that will lead to valid solutions.

We can do the same with --avoid-reinstalls:

$ ~/.cabal/bin/cabal install --dry-run tasty -v3 --avoid-reinstalls
[...]
Choosing modular solver.
Resolving dependencies...
[__0] trying: tasty-0.10.1 (user goal)
[__1] trying: base-4.6.0.1/installed-02a... (dependency of tasty-0.10.1)
[__2] trying: rts-1.0/installedbuil... (dependency of base-4.6.0.1/installed-02a...)
[__3] trying: integer-gmp-0.5.0.0/installed-2f1... (dependency of base-4.6.0.1/installed-02a...)
[__4] trying: ghc-prim-0.3.0.0/installed-d52... (dependency of base-4.6.0.1/installed-02a...)
[__5] trying: time-1.4.0.1/installed-0e9... (dependency of tasty-0.10.1)
[__6] trying: old-locale-1.0.0.5/installed-672... (dependency of time-1.4.0.1/installed-0e9...)
[__7] trying: ansi-terminal-0.6.2.1 (dependency of tasty-0.10.1)
[__8] trying: unix-2.6.0.1/installed-8e7... (dependency of ansi-terminal-0.6.2.1)
[__9] trying: bytestring-0.10.0.2/installed-af9... (dependency of unix-2.6.0.1/installed-8e7...)
[_10] trying: async-2.0.1.4/installed-d29... (dependency of tasty-0.10.1)
[_11] trying: unbounded-delays-0.1.0.8 (dependency of tasty-0.10.1)
[_12] trying: deepseq-1.3.0.1/installed-67a... (dependency of tasty-0.10.1)
[_13] trying: array-0.4.0.1/installed-6ee... (dependency of deepseq-1.3.0.1/installed-67a...)
[_14] trying: optparse-applicative-0.11.0.1 (dependency of tasty-0.10.1)
[_15] trying: ansi-wl-pprint-0.6.7.1 (dependency of optparse-applicative-0.11.0.1)
[_16] trying: process-1.1.0.2/installed-ab4... (dependency of optparse-applicative-0.11.0.1)
[_17] trying: filepath-1.3.0.1/installed-c5d... (dependency of process-1.1.0.2/installed-ab4...)
[_18] trying: directory-1.2.0.1/installed-e1c... (dependency of process-1.1.0.2/installed-ab4...)
[_19] trying: transformers-compat-0.3.3.4 (dependency of optparse-applicative-0.11.0.1)
[_20] trying: transformers-compat-0.3.3.4:-two
[_21] trying: transformers-compat-0.3.3.4:-three
[_22] next goal: transformers (dependency of optparse-applicative-0.11.0.1)
[_22] rejecting: transformers-0.3.0.0/installed-300... (conflict: transformers-compat-0.3.3.4:three => transformers>=0.4.1 && <0.5)
[_22] trying: transformers-0.4.2.0
[_23] trying: regex-tdfa-rc-1.1.8.3 (dependency of tasty-0.10.1)
[_24] trying: parsec-3.1.3/installed-846... (dependency of regex-tdfa-rc-1.1.8.3)
[_25] trying: text-0.11.3.1/installed-bb8... (dependency of parsec-3.1.3/installed-846...)
[_26] trying: regex-base-0.93.2/installed-0be... (dependency of regex-tdfa-rc-1.1.8.3)
[_27] trying: tagged-0.7.3 (dependency of tasty-0.10.1)
[_28] next goal: mtl (dependency of tasty-0.10.1)
[_28] rejecting: mtl-2.1.2/installed-c30... (conflict: transformers==0.4.2.0, mtl => transformers==0.3.0.0/installed-300...)
[_28] rejecting: mtl-2.2.1, 2.2.0.1, 2.2, 2.1.3.1, 2.1.2, 2.1.1, 2.1, 2.0.1.1, 2.0.1.0, 2.0.0.0, 1.1.1.1, 1.1.1.0, 1.1.0.2, 1.1.0.1, 1.1.0.0, 1.0 (conflict: parsec => mtl==2.1.2/installed-c30...)
[_25] fail (backjumping, conflict set: mtl, optparse-applicative, parsec, regex-tdfa-rc, tasty, transformers)
[_24] trying: parsec-3.1.7
[_25] trying: parsec-3.1.7:!test
[_26] trying: text-0.11.3.1/installed-bb8... (dependency of parsec-3.1.7)
[_27] trying: regex-base-0.93.2/installed-0be... (dependency of regex-tdfa-rc-1.1.8.3)
[_28] trying: tagged-0.7.3 (dependency of tasty-0.10.1)
[_29] next goal: mtl (dependency of tasty-0.10.1)
[_29] rejecting: mtl-2.1.2/installed-c30... (conflict: transformers==0.4.2.0, mtl => transformers==0.3.0.0/installed-300...)
[_29] rejecting: mtl-2.2.1, 2.2.0.1, 2.2, 2.1.3.1, 2.1.2, 2.1.1, 2.1, 2.0.1.1, 2.0.1.0, 2.0.0.0, 1.1.1.1, 1.1.1.0, 1.1.0.2, 1.1.0.1, 1.1.0.0, 1.0 (conflict: regex-base => mtl==2.1.2/installed-c30...)
[_28] fail (backjumping, conflict set: mtl, optparse-applicative, regex-base, regex-tdfa-rc, tasty, transformers)
[_27] rejecting: regex-base-0.93.2 (avoiding to reinstall a package with same version but new dependencies)
[_27] trying: regex-base-0.93.1
[_28] trying: tagged-0.7.3 (dependency of tasty-0.10.1)
[_29] next goal: mtl (dependency of tasty-0.10.1)
[_29] rejecting: mtl-2.1.2/installed-c30... (conflict: transformers==0.4.2.0, mtl => transformers==0.3.0.0/installed-300...)
[_29] trying: mtl-2.2.1
[_30] trying: containers-0.5.0.0/installed-71f... (dependency of tasty-0.10.1)
[_31] trying: stm-2.4.2/installed-67e... (dependency of tasty-0.10.1)
[_32] trying: ansi-terminal-0.6.2.1:-example
[_33] trying: ansi-wl-pprint-0.6.7.1:-example
[_34] trying: ansi-wl-pprint-0.6.7.1:+newbase
[_35] trying: regex-tdfa-rc-1.1.8.3:+base4
[_36] trying: parsec-3.1.7:+base4
[_37] trying: regex-base-0.93.1:+splitbase
[_38] done
In order, the following would be installed:
ansi-terminal-0.6.2.1 (new package)
ansi-wl-pprint-0.6.7.1 (new package)
tagged-0.7.3 (new package)
transformers-0.4.2.0 (new version)
mtl-2.2.1 (new version)
parsec-3.1.7 (new version)
regex-base-0.93.1 (latest: 0.93.2) (new version)
regex-tdfa-rc-1.1.8.3 (new package)
transformers-compat-0.3.3.4 (new package)
optparse-applicative-0.11.0.1 (new package)
unbounded-delays-0.1.0.8 (new package)
tasty-0.10.1 (new package)

As we see, not great either. Yay, no reinstall, but still an upgrade of mtl, and then it picks an older version of regex-base that it can build against mtl-2.2.1 without requiring a destructive reinstall.

There are two options to make progress:

1. Find several install plans (ideally, we'd find all) and compare them. Once we know all install plans that are possible, it's relatively easy (even automatically) to see which one we really want. So we could extend cabal to look for multiple plans, score them, and pick the best choice. I've been thinking about that for a while, but the problem is that in general, it might take too long.
2. Tweak the order in which goals are chosen. The problem above is that optparse-applicative and then transformers-compat and then transformers are all chosen before mtl, even though mtl is also a direct dependency of tasty. So we can try to pick goals that have installed options available early during solving, which means we'll really first look for any solutions that actually use the installed option.

I've implemented a change to cabal-install that follows option 2, and with it, we're getting this install plan:

$ cabal-patched install --dry-run tasty -v3
[...]
Choosing modular solver.
Resolving dependencies...
[...]
[__0] trying: tasty-0.10.1 (user goal)
[__1] trying: base-4.6.0.1/installed-02a... (dependency of tasty-0.10.1)
[__2] trying: rts-1.0/installedbuil... (dependency of base-4.6.0.1/installed-02a...)
[__3] trying: integer-gmp-0.5.0.0/installed-2f1... (dependency of base-4.6.0.1/installed-02a...)
[__4] trying: ghc-prim-0.3.0.0/installed-d52... (dependency of base-4.6.0.1/installed-02a...)
[__5] trying: time-1.4.0.1/installed-0e9... (dependency of tasty-0.10.1)
[__6] trying: old-locale-1.0.0.5/installed-672... (dependency of time-1.4.0.1/installed-0e9...)
[__7] trying: async-2.0.1.4/installed-d29... (dependency of tasty-0.10.1)
[__8] trying: deepseq-1.3.0.1/installed-67a... (dependency of tasty-0.10.1)
[__9] trying: array-0.4.0.1/installed-6ee... (dependency of deepseq-1.3.0.1/installed-67a...)
[_10] trying: mtl-2.1.2/installed-c30... (dependency of tasty-0.10.1)
[_11] trying: transformers-0.3.0.0/installed-300... (dependency of mtl-2.1.2/installed-c30...)
[_12] trying: containers-0.5.0.0/installed-71f... (dependency of tasty-0.10.1)
[_13] trying: stm-2.4.2/installed-67e... (dependency of tasty-0.10.1)
[_14] trying: ansi-terminal-0.6.2.1 (dependency of tasty-0.10.1)
[_15] trying: unix-2.6.0.1/installed-8e7... (dependency of ansi-terminal-0.6.2.1)
[_16] trying: bytestring-0.10.0.2/installed-af9... (dependency of unix-2.6.0.1/installed-8e7...)
[_17] trying: unbounded-delays-0.1.0.8 (dependency of tasty-0.10.1)
[_18] trying: optparse-applicative-0.11.0.1 (dependency of tasty-0.10.1)
[_19] trying: process-1.1.0.2/installed-ab4... (dependency of optparse-applicative-0.11.0.1)
[_20] trying: filepath-1.3.0.1/installed-c5d... (dependency of process-1.1.0.2/installed-ab4...)
[_21] trying: directory-1.2.0.1/installed-e1c... (dependency of process-1.1.0.2/installed-ab4...)
[_22] trying: ansi-wl-pprint-0.6.7.1 (dependency of optparse-applicative-0.11.0.1)
[_23] trying: transformers-compat-0.3.3.4 (dependency of optparse-applicative-0.11.0.1)
[_24] trying: transformers-compat-0.3.3.4:-two
[_25] rejecting: transformers-compat-0.3.3.4:-three (conflict: mtl => transformers==0.3.0.0/installed-300..., transformers-compat-0.3.3.4:three => transformers>=0.4.1 && <0.5)
[_25] rejecting: transformers-compat-0.3.3.4:+three (manual flag can only be changed explicitly)
[_25] fail (backjumping, conflict set: mtl, optparse-applicative, tasty, transformers-compat, transformers-compat-0.3.3.4:flag)
[_24] rejecting: transformers-compat-0.3.3.4:+two (manual flag can only be changed explicitly)
[_24] fail (backjumping, conflict set: mtl, optparse-applicative, tasty, transformers-compat, transformers-compat-0.3.3.4:flag)
[_23] trying: transformers-compat-0.3.3.3
[_24] trying: transformers-compat-0.3.3.3:-two
[_25] trying: transformers-compat-0.3.3.3:+three
[_26] trying: regex-tdfa-rc-1.1.8.3 (dependency of tasty-0.10.1)
[_27] trying: parsec-3.1.3/installed-846... (dependency of regex-tdfa-rc-1.1.8.3)
[_28] trying: text-0.11.3.1/installed-bb8... (dependency of parsec-3.1.3/installed-846...)
[_29] trying: regex-base-0.93.2/installed-0be... (dependency of regex-tdfa-rc-1.1.8.3)
[_30] trying: tagged-0.7.3 (dependency of tasty-0.10.1)
[_31] trying: ansi-terminal-0.6.2.1:-example
[_32] trying: ansi-wl-pprint-0.6.7.1:-example
[_33] trying: ansi-wl-pprint-0.6.7.1:+newbase
[_34] trying: regex-tdfa-rc-1.1.8.3:+base4
[_35] done
In order, the following would be installed:
ansi-terminal-0.6.2.1 (new package)
ansi-wl-pprint-0.6.7.1 (new package)
regex-tdfa-rc-1.1.8.3 (new package)
tagged-0.7.3 (new package)
transformers-compat-0.3.3.3 (latest: 0.3.3.4) (new package)
optparse-applicative-0.11.0.1 (new package)
unbounded-delays-0.1.0.8 (new package)
tasty-0.10.1 (new package)

This looks much better. It chooses mtl much earlier, defaulting to the installed version. Once we reach optparse-applicative, we can still pick the latest version, but now with transformers-compat, the choice of the latest version fails (which is good in this case). Choosing 0.3.3.3 here allows us to work with the installed version of transformers and mtl.

But this is a single example, and it's a significant change in heuristics. I'll run some more examples and tests to see how it seems to behave in general. I'm hopeful that this will turn out to be a general improvement, but I cannot yet say for certain.

[kosmikus]

If anyone wants to play with the change, it's at https://github.com/kosmikus/cabal/tree/prefer-goals-installed ...

[BardurArantsson]

QQ: Isn't this mostly made redundant irrelevant by @ezyang's Nix-style packages work that's already in master? If so, please close.