Improve solver error message by finding a minimal conflict set

[grayjay]

Currently cabal generates the summarized solver log by rerunning the dependency solver and having it prefer goals from the first run's final conflict set. The final conflict set may not be a minimal conflict set, though, which means that some goals could be irrelevant to the main conflict. Those extra goals could add irrelevant conflicts to the summarized log. We could improve the log by first minimizing the conflict set.

We could minimize the conflict set by removing one goal at a time and checking whether the remaining goals form a conflict set, until no more goals can be removed. One way to check that a set of goals X forms a conflict set is to run the solver and have it prefer goals from X, and then check that the solver's final conflict set is equal to X or a subset of X.

The feature might increase run time significantly, but we could control it with a flag, for use in difficult cases where it is worth waiting for a better error message.

See https://old.reddit.com/r/haskell/comments/9rmh9s/how_to_read_cabal_solver_failure_output/ for an example where this feature could have helped. I reproduced the original error message with https://github.com/tomjaguarpaw/haskell-opaleye/commit/6eabe92d14c51efbc4e6d0256c344c1f4fb42b65, GHC 8.6.1, and cabal-install-2.0.0.1. I installed hashable-1.2.7.0 and then ran cabal install --only-dependencies --enable-tests --force-reinstalls --index-state=2018-10-26T20:30:16Z. cabal HEAD (738a51148217885f797ea56af773b945469286b9) gives a better error message, but it still contains irrelevant lines about opaleye tests and the dotenv package that could be removed by this feature:

Resolving dependencies...
cabal: Could not resolve dependencies:
[__0] trying: opaleye-0.6.7003.0 (user goal)
[__1] rejecting: opaleye:!test (constraint from config file, command line
flag, or user target requires opposite flag selection)
[__1] trying: opaleye:*test
[__2] trying: dotenv-0.6.0.3 (dependency of opaleye *test)
[__3] trying: transformers-0.5.5.0/installed-0.5... (dependency of opaleye)
[__4] next goal: contravariant (dependency of opaleye)
[__4] rejecting: contravariant-1.5 (conflict: opaleye => contravariant>=1.2 &&
<1.5)
[__4] rejecting: contravariant-1.4.1, contravariant-1.4 (conflict:
transformers => base==4.12.0.0/installed-4.1..., contravariant => base<4.12)
[__4] rejecting: contravariant-1.3.3, contravariant-1.3.2,
contravariant-1.3.1.1, contravariant-1.3.1, contravariant-1.3,
contravariant-1.2.2.1, contravariant-1.2.2, contravariant-1.2.1,
contravariant-1.2.0.1, contravariant-1.2 (conflict:
transformers==0.5.5.0/installed-0.5..., contravariant => transformers>=0.2 &&
<0.5)
[__4] rejecting: contravariant-1.1, contravariant-1.0, contravariant-0.6.1.1,
contravariant-0.6.1, contravariant-0.6, contravariant-0.5.2,
contravariant-0.5.1, contravariant-0.5, contravariant-0.4.4,
contravariant-0.4.3, contravariant-0.4.1, contravariant-0.4,
contravariant-0.3, contravariant-0.2.0.2, contravariant-0.2.0.1,
contravariant-0.2, contravariant-0.1.3, contravariant-0.1.2.1,
contravariant-0.1.2, contravariant-0.1.1, contravariant-0.1.0.1,
contravariant-0.1.0 (conflict: opaleye => contravariant>=1.2 && <1.5)
[__4] fail (backjumping, conflict set: contravariant, opaleye, transformers)
After searching the rest of the dependency tree exhaustively, these were the
goals I've had most trouble fulfilling: transformers, contravariant, opaleye,
base, dotenv, opaleye:test

[grayjay]

This feature was implemented in #5680, but it is off by default because it reruns the solver and increases run time significantly. I'll leave this issue open for finding a way to control the run time and changing the default to true.

One way to limit the run time is to apply the backjump limit to the combined solver runs, for example, count 5 runs with 100 backjumps each as 500 backjumps. That would require returning the backjump count from the solver, which is related to #4594.