Why does this need a Cabal constraint?

[hamishmack]

This build failed with GHC 7.10 with:

+ cabal new-build jsaddle-warp:lib:jsaddle-warp jsaddle-warp:test:test-tool
Resolving dependencies...
cabal: Could not resolve dependencies:
trying: Cabal-1.22.5.0/installed-9ea... (dependency of haskell-gi-0.20)
trying: gi-glib-2.0.11 (dependency of jsaddle-webkit2gtk-0.8.2.0)
trying: ghc-paths-setup.Cabal~>Cabal-1.22.5.0/installed-9ea... (dependency of
ghc-paths-0.1.0.9)
trying: gi-glib-setup.haskell-gi~>haskell-gi-0.20 (dependency of
gi-glib-2.0.11)
next goal: gi-glib-setup.Cabal (dependency of gi-glib-2.0.11)
rejecting:
gi-glib-setup.Cabal~>ghc-paths-setup.Cabal-1.22.5.0/installed-9ea...,
gi-glib-setup.Cabal~>Cabal-1.22.5.0/installed-9ea... (conflict: gi-glib =>
gi-glib-setup.Cabal>=1.24)
rejecting: gi-glib-setup.Cabal-1.22.5.0/installed-9ea... (multiple instances)
rejecting: gi-glib-setup.Cabal-1.24.2.0, gi-glib-setup.Cabal-1.24.0.0,
gi-glib-setup.Cabal-1.22.8.0, gi-glib-setup.Cabal-1.22.7.0,
gi-glib-setup.Cabal-1.22.6.0, gi-glib-setup.Cabal-1.22.5.0,
gi-glib-setup.Cabal-1.22.4.0, gi-glib-setup.Cabal-1.22.3.0,
gi-glib-setup.Cabal-1.22.2.0, gi-glib-setup.Cabal-1.22.1.1,
gi-glib-setup.Cabal-1.22.1.0, gi-glib-setup.Cabal-1.22.0.0,
gi-glib-setup.Cabal-1.20.0.4, gi-glib-setup.Cabal-1.20.0.3,
gi-glib-setup.Cabal-1.20.0.2, gi-glib-setup.Cabal-1.20.0.1,
gi-glib-setup.Cabal-1.20.0.0, gi-glib-setup.Cabal-1.18.1.7,
gi-glib-setup.Cabal-1.18.1.6, gi-glib-setup.Cabal-1.18.1.5,
gi-glib-setup.Cabal-1.18.1.4, gi-glib-setup.Cabal-1.18.1.3,
gi-glib-setup.Cabal-1.18.1.2, gi-glib-setup.Cabal-1.18.1.1,
gi-glib-setup.Cabal-1.18.1, gi-glib-setup.Cabal-1.18.0,
gi-glib-setup.Cabal-1.16.0.3, gi-glib-setup.Cabal-1.16.0.2,
gi-glib-setup.Cabal-1.16.0.1, gi-glib-setup.Cabal-1.16.0,
gi-glib-setup.Cabal-1.14.0, gi-glib-setup.Cabal-1.12.0,
gi-glib-setup.Cabal-1.10.2.0, gi-glib-setup.Cabal-1.10.1.0,
gi-glib-setup.Cabal-1.10.0.0, gi-glib-setup.Cabal-1.8.0.6,
gi-glib-setup.Cabal-1.8.0.4, gi-glib-setup.Cabal-1.8.0.2,
gi-glib-setup.Cabal-1.6.0.3, gi-glib-setup.Cabal-1.6.0.2,
gi-glib-setup.Cabal-1.6.0.1, gi-glib-setup.Cabal-1.4.0.2,
gi-glib-setup.Cabal-1.4.0.1, gi-glib-setup.Cabal-1.4.0.0,
gi-glib-setup.Cabal-1.2.4.0, gi-glib-setup.Cabal-1.2.3.0,
gi-glib-setup.Cabal-1.2.2.0, gi-glib-setup.Cabal-1.2.1,
gi-glib-setup.Cabal-1.1.6, gi-glib-setup.Cabal-1.24.1.0 (dependencies not
linked: cannot make gi-glib-setup.Cabal canonical member of
{*Cabal-1.22.5.0/installed-9ea...,ghc-paths-setup.Cabal-1.22.5.0/installed-9ea...,gi-glib-setup.Cabal-1.22.5.0/installed-9ea...};
conflict set: Cabal, ghc-paths-setup.Cabal, gi-glib-setup.Cabal,
gi-glib-setup.haskell-gi)
Backjump limit reached (currently 2000, change with --max-backjumps or try to
run with --reorder-goals).

Adding --constraint='Cabal>=1.24.2.0' fixes it.

Adding --max-backjumps=20000 or --reorder-goals causes it to take more than the 10 minute travis timeout for no output.

[23Skidoo]

/cc @edsko

[edsko]

If this is with cabal HEAD, then this does seem to confirm #3932 is indeed not yet fixed.

[hamishmack]

I updated the travis build to use cabal-install-head travis output it is using 1.25+git20161109.0.d48c1eb-3~14.04.

[grayjay]

@hamishmack Do you know whether cabal was built with assertions enabled? I was able to reproduce the issue at first, but when I turned off assertions, cabal found a solution in less than two minutes (I ran cabal new-build jsaddle-warp:lib:jsaddle-warp jsaddle-warp:test:test-tool --dry-run --max-backjumps 20000).

The assertion at

cabal/cabal-install/Distribution/Solver/Modular/Linking.hs

Line 138 in 19d9738

assert (lgInvariant $ vsLinks st) $ return ()

seems to be very expensive.

[grayjay]

I looked into this further, and I think I found one pattern in the dependency graph that the solver isn't handling well. It is only a performance problem, AFAICT.

Relevant lines from the start of the -v3 log:

[185] trying: haskell-gi-0.20 (dependency of gi-javascriptcore-4.0.11)
[247] trying: Cabal-1.22.5.0/installed-9ea... (dependency of haskell-gi-0.20)
[268] trying: gi-glib-2.0.11 (dependency of jsaddle-webkit2gtk-0.8.2.0)
[444] trying: gi-glib-setup.haskell-gi~>haskell-gi-0.20 (dependency of gi-glib-2.0.11)
[568] next goal: gi-glib-setup.Cabal (dependency of gi-glib-2.0.11)
[568] rejecting: gi-glib-setup.Cabal~>Cabal-1.22.5.0/installed-9ea...
                 (conflict: gi-glib => gi-glib-setup.Cabal>=1.24)
[568] rejecting: gi-glib-setup.Cabal-1.22.5.0/installed-9ea... (multiple instances)
[568] rejecting: gi-glib-setup.Cabal-1.24.2.0, gi-glib-setup.Cabal-1.24.0.0,
                 gi-glib-setup.Cabal-1.22.8.0, gi-glib-setup.Cabal-1.22.7.0,
                 gi-glib-setup.Cabal-1.22.6.0, gi-glib-setup.Cabal-1.22.5.0,
                 gi-glib-setup.Cabal-1.22.4.0, gi-glib-setup.Cabal-1.22.3.0,
                 gi-glib-setup.Cabal-1.22.2.0, gi-glib-setup.Cabal-1.22.1.1,
                 gi-glib-setup.Cabal-1.22.1.0, gi-glib-setup.Cabal-1.22.0.0,
                 gi-glib-setup.Cabal-1.20.0.4, gi-glib-setup.Cabal-1.20.0.3,
                 gi-glib-setup.Cabal-1.20.0.2, gi-glib-setup.Cabal-1.20.0.1,
                 gi-glib-setup.Cabal-1.20.0.0
                 (dependencies not linked: cannot make gi-glib-setup.Cabal canonical member of
                  {*Cabal-1.22.5.0/installed-9ea...,ghc-paths-setup.Cabal-1.22.5.0/installed-9ea...,gi-glib-setup.Cabal-1.22.5.0/installed-9ea...};
                  conflict set: Cabal, ghc-paths-setup.Cabal, gi-glib-setup.Cabal, gi-glib-setup.haskell-gi)
[568] rejecting: gi-glib-setup.Cabal-1.18.1.7, gi-glib-setup.Cabal-1.18.1.6,
                 gi-glib-setup.Cabal-1.18.1.5, gi-glib-setup.Cabal-1.18.1.4,
                 gi-glib-setup.Cabal-1.18.1.3, gi-glib-setup.Cabal-1.18.1.2,
                 gi-glib-setup.Cabal-1.18.1.1, gi-glib-setup.Cabal-1.18.1,
                 gi-glib-setup.Cabal-1.18.0, gi-glib-setup.Cabal-1.16.0.3,
                 gi-glib-setup.Cabal-1.16.0.2, gi-glib-setup.Cabal-1.16.0.1,
                 gi-glib-setup.Cabal-1.16.0, gi-glib-setup.Cabal-1.14.0,
                 gi-glib-setup.Cabal-1.12.0, gi-glib-setup.Cabal-1.10.2.0,
                 gi-glib-setup.Cabal-1.10.1.0, gi-glib-setup.Cabal-1.10.0.0,
                 gi-glib-setup.Cabal-1.8.0.6, gi-glib-setup.Cabal-1.8.0.4,
                 gi-glib-setup.Cabal-1.8.0.2, gi-glib-setup.Cabal-1.6.0.3,
                 gi-glib-setup.Cabal-1.6.0.2, gi-glib-setup.Cabal-1.6.0.1,
                 gi-glib-setup.Cabal-1.4.0.2, gi-glib-setup.Cabal-1.4.0.1,
                 gi-glib-setup.Cabal-1.4.0.0, gi-glib-setup.Cabal-1.2.4.0,
                 gi-glib-setup.Cabal-1.2.3.0, gi-glib-setup.Cabal-1.2.2.0,
                 gi-glib-setup.Cabal-1.2.1, gi-glib-setup.Cabal-1.1.6
                 (constraint from minimum version of Cabal used by Setup.hs requires >=1.20)
[568] rejecting: gi-glib-setup.Cabal-1.24.1.0
                 (dependencies not linked: cannot make gi-glib-setup.Cabal canonical member of
                  {*Cabal-1.22.5.0/installed-9ea...,ghc-paths-setup.Cabal-1.22.5.0/installed-9ea...,gi-glib-setup.Cabal-1.22.5.0/installed-9ea...};
                  conflict set: Cabal, ghc-paths-setup.Cabal, gi-glib-setup.Cabal, gi-glib-setup.haskell-gi)
[445] fail (backjumping, conflict set: Cabal, gi-glib, ghc-paths-setup.Cabal, gi-glib-setup.Cabal, gi-glib-setup.haskell-gi)

haskell-gi has a regular dependency on Cabal, which can be satisfied by the installed Cabal-1.22.5.0. gi-glib has setup dependencies on Cabal >= 1.24 and haskell-gi >= 0.20 && < 1. Note that there is only one version of haskell-gi that satisfies this constraint. cabal first chooses to link both uses of haskell-gi. Linking two packages forces their dependencies to be linked, so the two uses of Cabal must also be linked. However, Cabal-1.22.5.0 doesn't satisfy the setup dependency constraint. cabal needs to backtrack and try different versions for all of the packages in the conflict set. While trying those alternate versions, it also encounters other packages with the same setup dependencies as gi-glib, such as gi-gio, gi-gtk, and gi-cairo. Trying one set of dependencies and then backtracking for each of the gi-* packages takes a lot of time. Finally, cabal backtracks all the way to the non-setup Cabal at level 247. Once it tries the next best version, Cabal-1.24.2.0, solving for the other packages is straightforward. All uses of Cabal can be linked. Constraining Cabal saves the solver from first trying to find a solution with the installed Cabal.

If I understand the problem correctly, I think there are a few ways to improve the perforance.

1. In the log above, the choice to link haskell-gi at level 444 cannot lead to a solution, but the solver only discovers the conflict at level 568. It would be better if, every time the solver chose to link a package, it immediately looked for conflicts caused by linking the package's dependencies. I'm not sure how to implement that without duplicating work done in the validation phase, though.

   --reorder-goals has a similar effect: it looks for goals that cannot be satisfied after every choice, so it finds conflicts faster. Each step is much slower, though. I ran cabal new-build jsaddle-warp:lib:jsaddle-warp jsaddle-warp:test:test-tool --dry-run --reorder-goals without assertions enabled. As expected, the solver backtracked fewer times (only once), but it ran very slowly (~5 minutes).

2. It seems like cabal should be able to use Cabal-1.22.5.0 for the non-setup dependency and use one instance of Cabal-1.24.2.0 for all of the setup dependencies. That is what qualified goals are for, after all. The problem is that haskell-gi depends on Cabal in both situations, and only one version of haskell-gi fits the constraints. The solution would involve two instances of haskell-gi-0.20. Since the solver still enforces the Single Instance Restriction (SIR), it skips that install plan.

   I commented out the line that enforces the SIR (

   cabal/cabal-install/Distribution/Solver/Modular/Solver.hs

   Line 113 in 19d9738

   P.enforceSingleInstanceRestriction .

   ) to see what would happen. The solver found a solution in only 8 seconds. It backtracked once at level 568, as before, but then chose not to link haskell-gi. The second instance of haskell-gi-0.20 was free to depend on Cabal-1.24.2.0. Then all other setup scripts reused those instances of haskell-gi and Cabal.

   Does anyone know if there is any reason to continue enforcing the SIR with newer versions of GHC?

3. I think that we could also reduce the size of the first conflict set if we removed the SIR. We could remove ghc-paths-setup.Cabal, because it is only necessary to try different versions of ghc-paths-setup.Cabal if gi-glib-setup.Cabal must be linked to ghc-paths-setup.Cabal. Without the SIR, the solver can always choose to not link any particular package, simply by making a second instance with the same version.

   EDIT: I don't think this is a good idea. We shouldn't skip solutions just because we know there are other solutions farther along, especially if the later solutions are worse (less linking). This would become more important if we added install plan scoring and tried to find the best solution.

EDIT: I tested with ghcjs/jsaddle@f446802, 19d9738, and index-state(hackage.haskell.org) = 2017-01-01T23:45:10Z