Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Add the ability to rerun the dependency solver based on the result of the first run #4823

Closed
grayjay opened this issue Oct 14, 2017 · 1 comment
Closed

Add the ability to rerun the dependency solver based on the result of the first run #4823

grayjay opened this issue Oct 14, 2017 · 1 comment
Labels
cabal-install: solver type: enhancement

Comments

@grayjay
Copy link
Collaborator

grayjay commented Oct 14, 2017 •
edited
Loading

This change would involve modifying the modularResolver function in D.Solver.Modular.hs to return the type of failure, i.e., backjump limit reached or no solution. When the result is "no solution", it could return the final conflict set. Then we could rerun the dependency solver for two reasons:

  1. When the result is "no solution", we could rerun the solver with a goalOrder parameter that prefers all packages in the final conflict set. Then we wouldn't need to filter the log with the p argument in D.Solver.Modular.Message.showMessages, because all goals would be relevant to the conflict. That would handle issues Incorrect error messages for non-existing dependencies #941 and Solver sometimes filters out relevant lines in the summarized log. #4792.
  2. When the result is "backjump limit reached", we could rerun the solver with --reorder-goals (issue Try rerunning the solver with --reorder-goals when it reaches the backjump limit. #4776).

EDIT: I fixed the link to the function that runs the solver.
grayjay added a commit to grayjay/cabal that referenced this issue Jan 8, 2018
@grayjay
Rerun dependency solver to generate a better error message (issue has…
6a1fe23 
…kell#4823).

This commit changes the way that the solver generates the summarized log that it
displays at normal verbosity.

Previously, the solver saved the full log from
the start to the first backjump.  Then it filtered the log using the conflict
set from the node where the first backjump occurred, i.e., it removed all lines
from the log that did not relate to variables in the conflict set.  The solver
also printed the final conflict set at the end of the log.

This approach had several problems:

1. It was possible for the conflicts at the first backjump to be completely
   unrelated to the final conflict set (issue haskell#941).  The conflicts in the
   summarized log could be irrelevant to the failure, for example, if they were
   introduced by only a single version of a dependency, which the solver could
   easily skip, and the real problem was a different dependency that was missing
   from the index.  Even if the summarized log was relevant, but different from
   the final conflict set, it was confusing to show two different explanations
   for the same failure.

2. Filtering the full log was error prone and could easily remove lines relevant
   to the conflict set.  It caused bugs mentioned in haskell#2853 and haskell#4154.

3. The conflict set at the first backjump contains the variables directly
   involved in the conflicts at that level and the variables that introduced
   them, but it doesn't contain the whole chain of variables starting with the
   user targets.  When the log is filtered with that conflict set, it can be
   unclear why the solver needed to choose those packages in the first place.

This commit creates the summarized log by rerunning the solver with a backjump
limit of zero and using the full log.  Using the full log avoids (2) and (3).
However, it is also important to shorten the log by only showing choices that
are relevant to conflicts. This commit uses different approaches for the two
types of failure.

No solution:

This commit makes the solver prefer variables from the final conflict set from
the first run when choosing goals in the second run.  This means that the log to
the first backjump should only mention packages, flags, and stanzas from the
final conflict set.  (The solver shouldn't need to choose any other packages,
because, for every variable in the final conflict set, the final conflict set
should also contain the variable that introduced that variable.  The solver can
follow that chain of variables in reverse order from the user target to the
conflict.)

Backjump limit reached:

There is no final conflict set in this case, since the solver didn't search the
whole tree.  This commit tries to create a final conflict set by rerunning the
solver with a subtree of the original search tree that contains the path to the
first backjump.  Then it uses the final conflict set as above.

Here is an example of the differences between the new and old logs, from haskell#4792,
using GHC 8.2.1:

Before:

$ cabal install --dry-run --index-state=2018-01-04T21:05:55Z thorn
Resolving dependencies...
cabal: Could not resolve dependencies:
trying: base-4.10.0.0/installed-4.1... (dependency of thorn)
next goal: profunctors (dependency of thorn)
rejecting: profunctors-5.2.1, profunctors-5.2, profunctors-5.1.2,
profunctors-5.1.1, profunctors-5.1, profunctors-5.0.1, profunctors-5.0.0.1,
profunctors-5 (conflict: thorn => profunctors<5)
trying: profunctors-4.4.1
next goal: transformers (dependency of profunctors)
rejecting: transformers-0.5.2.0/installed-0.5..., transformers-0.5.5.0,
transformers-0.5.4.0, transformers-0.5.2.0, transformers-0.5.1.0,
transformers-0.5.0.1, transformers-0.5.0.0 (conflict: profunctors =>
transformers>=0.2 && <0.5)
rejecting: transformers-0.4.3.0, transformers-0.4.2.0 (conflict:
base==4.10.0.0/installed-4.1..., transformers => base>=2 && <4.9)
rejecting: transformers-0.4.1.0, transformers-0.3.0.0, transformers-0.2.2.1
(conflict: base==4.10.0.0/installed-4.1..., transformers +/-applicativeinbase
=> base>=1.0 && <4.8)
rejecting: transformers-0.2.1.0, transformers-0.2.0.0 (conflict:
base==4.10.0.0/installed-4.1..., transformers +/-applicativeinbase =>
base>=1.0 && <4.3)
rejecting: transformers-0.1.4.0, transformers-0.1.3.0, transformers-0.1.1.0,
transformers-0.1.0.1, transformers-0.0.1.0, transformers-0.0.0.0,
transformers-0.5.3.1, transformers-0.5.3.0, transformers-0.5.0.2 (conflict:
profunctors => transformers>=0.2 && <0.5)
rejecting: transformers-0.4.0.0 (conflict: base==4.10.0.0/installed-4.1...,
transformers +/-applicativeinbase => base>=1.0 && <4.8)
rejecting: transformers-0.2.2.0 (conflict: base==4.10.0.0/installed-4.1...,
transformers +/-applicativeinbase => base>=1.0 && <4.6)
rejecting: transformers-0.1.0.0 (conflict: profunctors => transformers>=0.2 &&
<0.5)
After searching the rest of the dependency tree exhaustively, these were the
goals I've had most trouble fulfilling: transformers, contravariant, base,
thorn

After:

$ cabal install --dry-run --index-state=2018-01-04T21:05:55Z thorn
Resolving dependencies...
cabal: Could not resolve dependencies:
[__0] trying: thorn-0.2 (user goal)
[__1] next goal: contravariant (dependency of thorn)
[__1] rejecting: contravariant-1.4, 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, contravariant-1.1, contravariant-1.0
(conflict: thorn => contravariant<1)
[__1] trying: contravariant-0.6.1.1
[__2] next goal: transformers (dependency of contravariant)
[__2] rejecting: transformers-0.5.2.0/installed-0.5..., transformers-0.5.5.0,
transformers-0.5.4.0, transformers-0.5.2.0, transformers-0.5.1.0,
transformers-0.5.0.1, transformers-0.5.0.0 (conflict: contravariant =>
transformers>=0.2 && <0.5)
[__2] trying: transformers-0.4.3.0
[__3] next goal: base (dependency of thorn)
[__3] rejecting: base-4.10.0.0/installed-4.1... (conflict: transformers =>
base>=2 && <4.9)
[__3] rejecting: base-4.10.1.0, base-4.10.0.0, base-4.9.1.0, base-4.9.0.0,
base-4.8.2.0, base-4.8.1.0, base-4.8.0.0, base-4.7.0.2, base-4.7.0.1,
base-4.7.0.0, base-4.6.0.1, base-4.6.0.0, base-4.5.1.0, base-4.5.0.0,
base-4.4.1.0, base-4.4.0.0, base-4.3.1.0, base-4.3.0.0, base-4.2.0.2,
base-4.2.0.1, base-4.2.0.0, base-4.1.0.0, base-4.0.0.0, base-3.0.3.2,
base-3.0.3.1 (constraint from non-upgradeable package requires installed
instance)
After searching the rest of the dependency tree exhaustively, these were the
goals I've had most trouble fulfilling: transformers, contravariant, base,
thorn

Differences:

- The new summary has level numbers, like the full log.
- The conflicts are different.  The old log mentions thorn, base, profunctors,
  and transformers, and the new log mentions the four packages from the conflict
  set: thorn, contravariant, transformers, and base.
- The new log starts with the solver choosing a user goal, thorn.

The solver continues to display the conflicts at the first backjump when it
reaches the backjump limit, i.e, it shows profunctors instead of contravariant.
The goal order differs, though:

Before:

$ cabal install --dry-run --index-state=2018-01-04T21:05:55Z thorn --max-backjumps=10
Resolving dependencies...
cabal: Could not resolve dependencies:
trying: base-4.10.0.0/installed-4.1... (dependency of thorn)
next goal: profunctors (dependency of thorn)
rejecting: profunctors-5.2.1, profunctors-5.2, profunctors-5.1.2,
profunctors-5.1.1, profunctors-5.1, profunctors-5.0.1, profunctors-5.0.0.1,
profunctors-5 (conflict: thorn => profunctors<5)
trying: profunctors-4.4.1
next goal: transformers (dependency of profunctors)
rejecting: transformers-0.5.2.0/installed-0.5..., transformers-0.5.5.0,
transformers-0.5.4.0, transformers-0.5.2.0, transformers-0.5.1.0,
transformers-0.5.0.1, transformers-0.5.0.0 (conflict: profunctors =>
transformers>=0.2 && <0.5)
rejecting: transformers-0.4.3.0, transformers-0.4.2.0 (conflict:
base==4.10.0.0/installed-4.1..., transformers => base>=2 && <4.9)
rejecting: transformers-0.4.1.0, transformers-0.3.0.0, transformers-0.2.2.1
(conflict: base==4.10.0.0/installed-4.1..., transformers +/-applicativeinbase
=> base>=1.0 && <4.8)
rejecting: transformers-0.2.1.0, transformers-0.2.0.0 (conflict:
base==4.10.0.0/installed-4.1..., transformers +/-applicativeinbase =>
base>=1.0 && <4.3)
rejecting: transformers-0.1.4.0, transformers-0.1.3.0, transformers-0.1.1.0,
transformers-0.1.0.1, transformers-0.0.1.0, transformers-0.0.0.0,
transformers-0.5.3.1, transformers-0.5.3.0, transformers-0.5.0.2 (conflict:
profunctors => transformers>=0.2 && <0.5)
rejecting: transformers-0.4.0.0 (conflict: base==4.10.0.0/installed-4.1...,
transformers +/-applicativeinbase => base>=1.0 && <4.8)
rejecting: transformers-0.2.2.0 (conflict: base==4.10.0.0/installed-4.1...,
transformers +/-applicativeinbase => base>=1.0 && <4.6)
rejecting: transformers-0.1.0.0 (conflict: profunctors => transformers>=0.2 &&
<0.5)
Backjump limit reached (currently 10, change with --max-backjumps or try to
run with --reorder-goals).

After:

$ cabal install --dry-run --index-state=2018-01-04T21:05:55Z thorn --max-backjumps=10
Resolving dependencies...
cabal: Could not resolve dependencies:
[__0] trying: thorn-0.2 (user goal)
[__1] next goal: profunctors (dependency of thorn)
[__1] rejecting: profunctors-5.2.1, profunctors-5.2, profunctors-5.1.2,
profunctors-5.1.1, profunctors-5.1, profunctors-5.0.1, profunctors-5.0.0.1,
profunctors-5 (conflict: thorn => profunctors<5)
[__1] trying: profunctors-4.4.1
[__2] next goal: transformers (dependency of profunctors)
[__2] rejecting: transformers-0.5.2.0/installed-0.5..., transformers-0.5.5.0,
transformers-0.5.4.0, transformers-0.5.2.0, transformers-0.5.1.0,
transformers-0.5.0.1, transformers-0.5.0.0 (conflict: profunctors =>
transformers>=0.2 && <0.5)
[__2] trying: transformers-0.4.3.0
[__3] next goal: base (dependency of thorn)
[__3] rejecting: base-4.10.0.0/installed-4.1... (conflict: transformers =>
base>=2 && <4.9)
[__3] rejecting: base-4.10.1.0, base-4.10.0.0, base-4.9.1.0, base-4.9.0.0,
base-4.8.2.0, base-4.8.1.0, base-4.8.0.0, base-4.7.0.2, base-4.7.0.1,
base-4.7.0.0, base-4.6.0.1, base-4.6.0.0, base-4.5.1.0, base-4.5.0.0,
base-4.4.1.0, base-4.4.0.0, base-4.3.1.0, base-4.3.0.0, base-4.2.0.2,
base-4.2.0.1, base-4.2.0.0, base-4.1.0.0, base-4.0.0.0, base-3.0.3.2,
base-3.0.3.1 (constraint from non-upgradeable package requires installed
instance)
Backjump limit reached (currently 10, change with --max-backjumps or try to
run with --reorder-goals).

One downside of this change is that the solver may reach the backjump limit when
generating the summarized log, if the backjump limit is small:

$ cabal install --dry-run --index-state=2018-01-04T21:05:55Z thorn --max-backjumps=1
Resolving dependencies...
cabal: Backjump limit reached (currently 1, change with --max-backjumps or try
to run with --reorder-goals).
Failed to generate a summarized dependency solver log due to low backjump
limit.

Another downside is the performance impact of rerunning the solver.
grayjay added a commit to grayjay/cabal that referenced this issue Jan 8, 2018
@grayjay
Rerun dependency solver to generate a better error message (issue has…
f96b127 
…kell#4823).

This commit changes the way that the solver generates the summarized log that it
displays at normal verbosity.

Previously, the solver saved the full log from the start to the first backjump.
Then it filtered the log using the conflict set from the node where the first
backjump occurred, i.e., it removed all lines from the log that did not relate
to variables in the conflict set.  The solver also printed the final conflict
set at the end of the log.

This approach had several problems:

1. It was possible for the conflicts at the first backjump to be completely
   unrelated to the final conflict set (issue haskell#941).  The conflicts in the
   summarized log could be irrelevant to the failure, for example, if they were
   introduced by only a single version of a dependency, which the solver could
   easily skip, and the real problem was a different dependency that was missing
   from the index.  Even if the summarized log was relevant, it could differ
   from the final conflict set and be misleading.

2. Filtering the full log was error prone and could easily remove the wrong
   lines.  It caused bugs mentioned in haskell#2853 and haskell#4154.

3. The conflict set at the first backjump contains the variables directly
   involved in the conflicts at that level and the variables that introduced
   them, but it doesn't contain the whole chain of variables starting with the
   user targets.  When the log is filtered with that conflict set, it can be
   unclear why the solver needed to choose the conflicting packages in the first
   place.

This commit creates the summarized log by rerunning the solver with a backjump
limit of zero and using the full log.  Using the full log avoids (2) and (3).
However, it is also important to shorten the log by only showing choices that
are relevant to conflicts.  This commit uses different approaches for the two
types of solver failure.

No solution:

This commit makes the solver prefer variables from the first run's final
conflict set when choosing goals in the second run.  This means that the log to
the first backjump should be more relevant to the final failure, because it only
mentions packages, flags, and stanzas from the final conflict set.  (The solver
shouldn't need to choose any packages that aren't in the conflict set, because,
for every variable in the final conflict set, the final conflict set should also
contain the variable that introduced that variable.  The solver can follow that
chain of variables in reverse order from the user target to the conflict.)

Backjump limit reached:

There is no final conflict set in this case, since the solver did not traverse
the whole tree.  This commit tries to create a final conflict set by rerunning
the solver with a subtree of the original search tree that contains the path to
the first backjump.  Then it uses the final conflict set to generate a log
message as above.

Here is an example of the differences between the new and old logs, from haskell#4792,
using GHC 8.2.1:

Before:

$ cabal install --dry-run --index-state=2018-01-04T21:05:55Z thorn
Resolving dependencies...
cabal: Could not resolve dependencies:
trying: base-4.10.0.0/installed-4.1... (dependency of thorn)
next goal: profunctors (dependency of thorn)
rejecting: profunctors-5.2.1, profunctors-5.2, profunctors-5.1.2,
profunctors-5.1.1, profunctors-5.1, profunctors-5.0.1, profunctors-5.0.0.1,
profunctors-5 (conflict: thorn => profunctors<5)
trying: profunctors-4.4.1
next goal: transformers (dependency of profunctors)
rejecting: transformers-0.5.2.0/installed-0.5..., transformers-0.5.5.0,
transformers-0.5.4.0, transformers-0.5.2.0, transformers-0.5.1.0,
transformers-0.5.0.1, transformers-0.5.0.0 (conflict: profunctors =>
transformers>=0.2 && <0.5)
rejecting: transformers-0.4.3.0, transformers-0.4.2.0 (conflict:
base==4.10.0.0/installed-4.1..., transformers => base>=2 && <4.9)
rejecting: transformers-0.4.1.0, transformers-0.3.0.0, transformers-0.2.2.1
(conflict: base==4.10.0.0/installed-4.1..., transformers +/-applicativeinbase
=> base>=1.0 && <4.8)
rejecting: transformers-0.2.1.0, transformers-0.2.0.0 (conflict:
base==4.10.0.0/installed-4.1..., transformers +/-applicativeinbase =>
base>=1.0 && <4.3)
rejecting: transformers-0.1.4.0, transformers-0.1.3.0, transformers-0.1.1.0,
transformers-0.1.0.1, transformers-0.0.1.0, transformers-0.0.0.0,
transformers-0.5.3.1, transformers-0.5.3.0, transformers-0.5.0.2 (conflict:
profunctors => transformers>=0.2 && <0.5)
rejecting: transformers-0.4.0.0 (conflict: base==4.10.0.0/installed-4.1...,
transformers +/-applicativeinbase => base>=1.0 && <4.8)
rejecting: transformers-0.2.2.0 (conflict: base==4.10.0.0/installed-4.1...,
transformers +/-applicativeinbase => base>=1.0 && <4.6)
rejecting: transformers-0.1.0.0 (conflict: profunctors => transformers>=0.2 &&
<0.5)
After searching the rest of the dependency tree exhaustively, these were the
goals I've had most trouble fulfilling: transformers, contravariant, base,
thorn

After:

$ cabal install --dry-run --index-state=2018-01-04T21:05:55Z thorn
Resolving dependencies...
cabal: Could not resolve dependencies:
[__0] trying: thorn-0.2 (user goal)
[__1] next goal: contravariant (dependency of thorn)
[__1] rejecting: contravariant-1.4, 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, contravariant-1.1, contravariant-1.0
(conflict: thorn => contravariant<1)
[__1] trying: contravariant-0.6.1.1
[__2] next goal: transformers (dependency of contravariant)
[__2] rejecting: transformers-0.5.2.0/installed-0.5..., transformers-0.5.5.0,
transformers-0.5.4.0, transformers-0.5.2.0, transformers-0.5.1.0,
transformers-0.5.0.1, transformers-0.5.0.0 (conflict: contravariant =>
transformers>=0.2 && <0.5)
[__2] trying: transformers-0.4.3.0
[__3] next goal: base (dependency of thorn)
[__3] rejecting: base-4.10.0.0/installed-4.1... (conflict: transformers =>
base>=2 && <4.9)
[__3] rejecting: base-4.10.1.0, base-4.10.0.0, base-4.9.1.0, base-4.9.0.0,
base-4.8.2.0, base-4.8.1.0, base-4.8.0.0, base-4.7.0.2, base-4.7.0.1,
base-4.7.0.0, base-4.6.0.1, base-4.6.0.0, base-4.5.1.0, base-4.5.0.0,
base-4.4.1.0, base-4.4.0.0, base-4.3.1.0, base-4.3.0.0, base-4.2.0.2,
base-4.2.0.1, base-4.2.0.0, base-4.1.0.0, base-4.0.0.0, base-3.0.3.2,
base-3.0.3.1 (constraint from non-upgradeable package requires installed
instance)
After searching the rest of the dependency tree exhaustively, these were the
goals I've had most trouble fulfilling: transformers, contravariant, base,
thorn

Differences:

- The new summary has level numbers, like the full log.
- The conflicts are different.  The old log mentions thorn, base, profunctors,
  and transformers, and the new log mentions the four packages from the conflict
  set: thorn, contravariant, transformers, and base.
- The new log starts with the solver choosing a user goal, thorn.

The solver continues to display the conflicts at the first backjump when it
reaches the backjump limit, i.e, it shows profunctors instead of contravariant.
The goal order differs, though:

Before:

$ cabal install --dry-run --index-state=2018-01-04T21:05:55Z thorn --max-backjumps=10
Resolving dependencies...
cabal: Could not resolve dependencies:
trying: base-4.10.0.0/installed-4.1... (dependency of thorn)
next goal: profunctors (dependency of thorn)
rejecting: profunctors-5.2.1, profunctors-5.2, profunctors-5.1.2,
profunctors-5.1.1, profunctors-5.1, profunctors-5.0.1, profunctors-5.0.0.1,
profunctors-5 (conflict: thorn => profunctors<5)
trying: profunctors-4.4.1
next goal: transformers (dependency of profunctors)
rejecting: transformers-0.5.2.0/installed-0.5..., transformers-0.5.5.0,
transformers-0.5.4.0, transformers-0.5.2.0, transformers-0.5.1.0,
transformers-0.5.0.1, transformers-0.5.0.0 (conflict: profunctors =>
transformers>=0.2 && <0.5)
rejecting: transformers-0.4.3.0, transformers-0.4.2.0 (conflict:
base==4.10.0.0/installed-4.1..., transformers => base>=2 && <4.9)
rejecting: transformers-0.4.1.0, transformers-0.3.0.0, transformers-0.2.2.1
(conflict: base==4.10.0.0/installed-4.1..., transformers +/-applicativeinbase
=> base>=1.0 && <4.8)
rejecting: transformers-0.2.1.0, transformers-0.2.0.0 (conflict:
base==4.10.0.0/installed-4.1..., transformers +/-applicativeinbase =>
base>=1.0 && <4.3)
rejecting: transformers-0.1.4.0, transformers-0.1.3.0, transformers-0.1.1.0,
transformers-0.1.0.1, transformers-0.0.1.0, transformers-0.0.0.0,
transformers-0.5.3.1, transformers-0.5.3.0, transformers-0.5.0.2 (conflict:
profunctors => transformers>=0.2 && <0.5)
rejecting: transformers-0.4.0.0 (conflict: base==4.10.0.0/installed-4.1...,
transformers +/-applicativeinbase => base>=1.0 && <4.8)
rejecting: transformers-0.2.2.0 (conflict: base==4.10.0.0/installed-4.1...,
transformers +/-applicativeinbase => base>=1.0 && <4.6)
rejecting: transformers-0.1.0.0 (conflict: profunctors => transformers>=0.2 &&
<0.5)
Backjump limit reached (currently 10, change with --max-backjumps or try to
run with --reorder-goals).

After:

$ cabal install --dry-run --index-state=2018-01-04T21:05:55Z thorn --max-backjumps=10
Resolving dependencies...
cabal: Could not resolve dependencies:
[__0] trying: thorn-0.2 (user goal)
[__1] next goal: profunctors (dependency of thorn)
[__1] rejecting: profunctors-5.2.1, profunctors-5.2, profunctors-5.1.2,
profunctors-5.1.1, profunctors-5.1, profunctors-5.0.1, profunctors-5.0.0.1,
profunctors-5 (conflict: thorn => profunctors<5)
[__1] trying: profunctors-4.4.1
[__2] next goal: transformers (dependency of profunctors)
[__2] rejecting: transformers-0.5.2.0/installed-0.5..., transformers-0.5.5.0,
transformers-0.5.4.0, transformers-0.5.2.0, transformers-0.5.1.0,
transformers-0.5.0.1, transformers-0.5.0.0 (conflict: profunctors =>
transformers>=0.2 && <0.5)
[__2] trying: transformers-0.4.3.0
[__3] next goal: base (dependency of thorn)
[__3] rejecting: base-4.10.0.0/installed-4.1... (conflict: transformers =>
base>=2 && <4.9)
[__3] rejecting: base-4.10.1.0, base-4.10.0.0, base-4.9.1.0, base-4.9.0.0,
base-4.8.2.0, base-4.8.1.0, base-4.8.0.0, base-4.7.0.2, base-4.7.0.1,
base-4.7.0.0, base-4.6.0.1, base-4.6.0.0, base-4.5.1.0, base-4.5.0.0,
base-4.4.1.0, base-4.4.0.0, base-4.3.1.0, base-4.3.0.0, base-4.2.0.2,
base-4.2.0.1, base-4.2.0.0, base-4.1.0.0, base-4.0.0.0, base-3.0.3.2,
base-3.0.3.1 (constraint from non-upgradeable package requires installed
instance)
Backjump limit reached (currently 10, change with --max-backjumps or try to
run with --reorder-goals).

One downside of this change is that the solver may reach the backjump limit when
generating the summarized log, if the backjump limit is small:

$ cabal install --dry-run --index-state=2018-01-04T21:05:55Z thorn --max-backjumps=1
Resolving dependencies...
cabal: Backjump limit reached (currently 1, change with --max-backjumps or try
to run with --reorder-goals).
Failed to generate a summarized dependency solver log due to low backjump
limit.

Another downside is the performance impact of rerunning the solver.  I timed
solving for several packages, and there wasn't a significant difference in run
time when the solver found a solution or failed after an exhaustive search.
However, this branch was often significantly slower when the solver reached the
backjump limit.  The extra time was probably spent in the second run of the
solver, where it had to traverse the tree to the first backjump.  The worst case
was acme-everything with GHC 7.10.3, where that step took 13 seconds.  In other
cases, it was less than a second.  For example,
'cabal install --dry-run push-notify' took 5.62 seconds on master and 5.71
seconds on this branch, and 'cabal install --dry-run reactive-glut' took 3.77
seconds on master and 3.825 seconds on this branch (average of three trials).
grayjay added a commit to grayjay/cabal that referenced this issue Jan 9, 2018
@grayjay
Rerun dependency solver to generate a better error message (issue has…
395538d 
…kell#4823).

This commit changes the way that the solver generates the summarized log that it
displays at normal verbosity.

Previously, the solver saved the full log from the start to the first backjump.
Then it filtered the log using the conflict set from the node where the first
backjump occurred, i.e., it removed all lines from the log that did not relate
to variables in the conflict set.  The solver also printed the final conflict
set at the end of the log.

This approach had several problems:

1. It was possible for the conflicts at the first backjump to be unrelated to
   the final conflict set (issue haskell#941).  The conflicts in the summarized log
   could be irrelevant to the failure, for example, if they were caused by only
   a single version of a dependency, which the solver could skip, and the real
   problem was that a different dependency was missing from the index.  Even if
   the summarized log was relevant, showing two different explanations for the
   same failure could be confusing.

2. Filtering the full log was error prone and could remove the wrong lines.  It
   caused bugs mentioned in haskell#2853 and haskell#4154.

3. The conflict set at the first backjump contains the variables directly
   involved in the conflicts at that level and the variables that introduced
   them, but it doesn't contain the whole chain of variables starting with the
   user targets.  When the log is filtered with that conflict set, it can be
   unclear why the solver needed to choose the conflicting packages in the first
   place.

This commit creates the summarized log by rerunning the solver with a backjump
limit of zero and using the full log.  Using the full log avoids (2) and (3).
However, it is also important to shorten the log by only showing choices that
are relevant to conflicts.  This commit uses different approaches for the two
types of solver failure.

No solution:

This commit makes the solver prefer variables from the first run's final
conflict set when choosing goals in the second run.  This means that the log to
the first backjump is more likely to be relevant to the final failure, because
it only mentions packages, flags, and stanzas from the final conflict set.

Backjump limit reached:

There is no final conflict set in this case, since the solver did not traverse
the whole tree.  This commit tries to create a final conflict set by rerunning
the solver with a subtree of the original search tree that contains the path to
the first backjump.  Then it uses the final conflict set to generate a log
message, as in the case where the solver found that there was no solution.

Here is an example of the differences between the new and old logs, using the
command from issue haskell#4792 and GHC 8.2.1:

Before:

$ cabal install --dry-run --index-state=2018-01-04T21:05:55Z thorn
Resolving dependencies...
cabal: Could not resolve dependencies:
trying: base-4.10.0.0/installed-4.1... (dependency of thorn)
next goal: profunctors (dependency of thorn)
rejecting: profunctors-5.2.1, profunctors-5.2, profunctors-5.1.2,
profunctors-5.1.1, profunctors-5.1, profunctors-5.0.1, profunctors-5.0.0.1,
profunctors-5 (conflict: thorn => profunctors<5)
trying: profunctors-4.4.1
next goal: transformers (dependency of profunctors)
rejecting: transformers-0.5.2.0/installed-0.5..., transformers-0.5.5.0,
transformers-0.5.4.0, transformers-0.5.2.0, transformers-0.5.1.0,
transformers-0.5.0.1, transformers-0.5.0.0 (conflict: profunctors =>
transformers>=0.2 && <0.5)
rejecting: transformers-0.4.3.0, transformers-0.4.2.0 (conflict:
base==4.10.0.0/installed-4.1..., transformers => base>=2 && <4.9)
rejecting: transformers-0.4.1.0, transformers-0.3.0.0, transformers-0.2.2.1
(conflict: base==4.10.0.0/installed-4.1..., transformers +/-applicativeinbase
=> base>=1.0 && <4.8)
rejecting: transformers-0.2.1.0, transformers-0.2.0.0 (conflict:
base==4.10.0.0/installed-4.1..., transformers +/-applicativeinbase =>
base>=1.0 && <4.3)
rejecting: transformers-0.1.4.0, transformers-0.1.3.0, transformers-0.1.1.0,
transformers-0.1.0.1, transformers-0.0.1.0, transformers-0.0.0.0,
transformers-0.5.3.1, transformers-0.5.3.0, transformers-0.5.0.2 (conflict:
profunctors => transformers>=0.2 && <0.5)
rejecting: transformers-0.4.0.0 (conflict: base==4.10.0.0/installed-4.1...,
transformers +/-applicativeinbase => base>=1.0 && <4.8)
rejecting: transformers-0.2.2.0 (conflict: base==4.10.0.0/installed-4.1...,
transformers +/-applicativeinbase => base>=1.0 && <4.6)
rejecting: transformers-0.1.0.0 (conflict: profunctors => transformers>=0.2 &&
<0.5)
After searching the rest of the dependency tree exhaustively, these were the
goals I've had most trouble fulfilling: transformers, contravariant, base,
thorn

After:

$ cabal install --dry-run --index-state=2018-01-04T21:05:55Z thorn
Resolving dependencies...
cabal: Could not resolve dependencies:
[__0] trying: thorn-0.2 (user goal)
[__1] next goal: contravariant (dependency of thorn)
[__1] rejecting: contravariant-1.4, 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, contravariant-1.1, contravariant-1.0
(conflict: thorn => contravariant<1)
[__1] trying: contravariant-0.6.1.1
[__2] next goal: transformers (dependency of contravariant)
[__2] rejecting: transformers-0.5.2.0/installed-0.5..., transformers-0.5.5.0,
transformers-0.5.4.0, transformers-0.5.2.0, transformers-0.5.1.0,
transformers-0.5.0.1, transformers-0.5.0.0 (conflict: contravariant =>
transformers>=0.2 && <0.5)
[__2] trying: transformers-0.4.3.0
[__3] next goal: base (dependency of thorn)
[__3] rejecting: base-4.10.0.0/installed-4.1... (conflict: transformers =>
base>=2 && <4.9)
[__3] rejecting: base-4.10.1.0, base-4.10.0.0, base-4.9.1.0, base-4.9.0.0,
base-4.8.2.0, base-4.8.1.0, base-4.8.0.0, base-4.7.0.2, base-4.7.0.1,
base-4.7.0.0, base-4.6.0.1, base-4.6.0.0, base-4.5.1.0, base-4.5.0.0,
base-4.4.1.0, base-4.4.0.0, base-4.3.1.0, base-4.3.0.0, base-4.2.0.2,
base-4.2.0.1, base-4.2.0.0, base-4.1.0.0, base-4.0.0.0, base-3.0.3.2,
base-3.0.3.1 (constraint from non-upgradeable package requires installed
instance)
After searching the rest of the dependency tree exhaustively, these were the
goals I've had most trouble fulfilling: transformers, contravariant, base,
thorn

Differences:

- The new summary has level numbers, like the full log.
- The conflicts are different.  The old log mentions thorn, base, profunctors,
  and transformers, and the new log mentions the four packages from the conflict
  set: thorn, contravariant, transformers, and base.
- The new log starts with the solver choosing a user goal, thorn.

The solver continues to display the conflicts at the first backjump when it
reaches the backjump limit, i.e, it shows profunctors instead of contravariant:

Before:

$ cabal install --dry-run --index-state=2018-01-04T21:05:55Z thorn --max-backjumps=10
Resolving dependencies...
cabal: Could not resolve dependencies:
trying: base-4.10.0.0/installed-4.1... (dependency of thorn)
next goal: profunctors (dependency of thorn)
rejecting: profunctors-5.2.1, profunctors-5.2, profunctors-5.1.2,
profunctors-5.1.1, profunctors-5.1, profunctors-5.0.1, profunctors-5.0.0.1,
profunctors-5 (conflict: thorn => profunctors<5)
trying: profunctors-4.4.1
next goal: transformers (dependency of profunctors)
rejecting: transformers-0.5.2.0/installed-0.5..., transformers-0.5.5.0,
transformers-0.5.4.0, transformers-0.5.2.0, transformers-0.5.1.0,
transformers-0.5.0.1, transformers-0.5.0.0 (conflict: profunctors =>
transformers>=0.2 && <0.5)
rejecting: transformers-0.4.3.0, transformers-0.4.2.0 (conflict:
base==4.10.0.0/installed-4.1..., transformers => base>=2 && <4.9)
rejecting: transformers-0.4.1.0, transformers-0.3.0.0, transformers-0.2.2.1
(conflict: base==4.10.0.0/installed-4.1..., transformers +/-applicativeinbase
=> base>=1.0 && <4.8)
rejecting: transformers-0.2.1.0, transformers-0.2.0.0 (conflict:
base==4.10.0.0/installed-4.1..., transformers +/-applicativeinbase =>
base>=1.0 && <4.3)
rejecting: transformers-0.1.4.0, transformers-0.1.3.0, transformers-0.1.1.0,
transformers-0.1.0.1, transformers-0.0.1.0, transformers-0.0.0.0,
transformers-0.5.3.1, transformers-0.5.3.0, transformers-0.5.0.2 (conflict:
profunctors => transformers>=0.2 && <0.5)
rejecting: transformers-0.4.0.0 (conflict: base==4.10.0.0/installed-4.1...,
transformers +/-applicativeinbase => base>=1.0 && <4.8)
rejecting: transformers-0.2.2.0 (conflict: base==4.10.0.0/installed-4.1...,
transformers +/-applicativeinbase => base>=1.0 && <4.6)
rejecting: transformers-0.1.0.0 (conflict: profunctors => transformers>=0.2 &&
<0.5)
Backjump limit reached (currently 10, change with --max-backjumps or try to
run with --reorder-goals).

After:

$ cabal install --dry-run --index-state=2018-01-04T21:05:55Z thorn --max-backjumps=10
Resolving dependencies...
cabal: Could not resolve dependencies:
[__0] trying: thorn-0.2 (user goal)
[__1] next goal: profunctors (dependency of thorn)
[__1] rejecting: profunctors-5.2.1, profunctors-5.2, profunctors-5.1.2,
profunctors-5.1.1, profunctors-5.1, profunctors-5.0.1, profunctors-5.0.0.1,
profunctors-5 (conflict: thorn => profunctors<5)
[__1] trying: profunctors-4.4.1
[__2] next goal: transformers (dependency of profunctors)
[__2] rejecting: transformers-0.5.2.0/installed-0.5..., transformers-0.5.5.0,
transformers-0.5.4.0, transformers-0.5.2.0, transformers-0.5.1.0,
transformers-0.5.0.1, transformers-0.5.0.0 (conflict: profunctors =>
transformers>=0.2 && <0.5)
[__2] trying: transformers-0.4.3.0
[__3] next goal: base (dependency of thorn)
[__3] rejecting: base-4.10.0.0/installed-4.1... (conflict: transformers =>
base>=2 && <4.9)
[__3] rejecting: base-4.10.1.0, base-4.10.0.0, base-4.9.1.0, base-4.9.0.0,
base-4.8.2.0, base-4.8.1.0, base-4.8.0.0, base-4.7.0.2, base-4.7.0.1,
base-4.7.0.0, base-4.6.0.1, base-4.6.0.0, base-4.5.1.0, base-4.5.0.0,
base-4.4.1.0, base-4.4.0.0, base-4.3.1.0, base-4.3.0.0, base-4.2.0.2,
base-4.2.0.1, base-4.2.0.0, base-4.1.0.0, base-4.0.0.0, base-3.0.3.2,
base-3.0.3.1 (constraint from non-upgradeable package requires installed
instance)
Backjump limit reached (currently 10, change with --max-backjumps or try to
run with --reorder-goals).

One downside of this change is that the solver may reach the backjump limit when
generating the summarized log, if the backjump limit is very low:

$ cabal install --dry-run --index-state=2018-01-04T21:05:55Z thorn --max-backjumps=1
Resolving dependencies...
cabal: Backjump limit reached (currently 1, change with --max-backjumps or try
to run with --reorder-goals).
Failed to generate a summarized dependency solver log due to low backjump
limit.

Another downside is the performance impact of rerunning the solver.  It looks
like there isn't a big change in run time when the solver finds a solution or
fails after an exhaustive search.  However, rerunning the solver to the first
backjump after it reaches the backjump limit can take a significant amount of
time.  The worst case I could find was acme-everything with GHC 7.10.3, where
that step took 13 seconds.

I also ran hackage-benchmark on packages from Hackage to try to find packages
where the run time changed by more than a few percent.  I stopped it after all
packages starting with "b" (That includes all uppercase packages).

compiler: GHC 8.2.1
index state: 2018-01-04T21:05:55Z
parameters: --min-run-time-percentage-difference-to-rerun=1 --pvalue=0.01 --trials=20 --print-skipped-packages

Out of 2219 packages, 1064 were skipped because the run times in the first trial
were within 1%, 1065 differed by more than 1% in the first trial but did not
show a significant difference in run time in 20 trials, and 90 did show a
significant difference in run time.  Here are the package counts for different
ranges of speedup, for those 90 packages:

speedup (master avg. run time / branch avg. run time)     package count
[0.93, 0.94)                                              1
[0.94, 0.95)                                              0
[0.95, 0.96)                                              0
[0.96, 0.97)                                              1
[0.97, 0.98)                                              7
[0.98, 0.99)                                              29
[0.99, 1.00)                                              47
[1.00, 1.01)                                              3
[1.01, 1.02)                                              2

The package with the biggest change was bittorrent, which had a speedup of
0.936.  It reached the backjump limit.
grayjay added a commit to grayjay/cabal that referenced this issue Jan 10, 2018
@grayjay
Rerun dependency solver to generate a better error message (issue has…
84ebedc 
…kell#4823).

This commit changes the way that the solver generates the summarized log that it
displays at normal verbosity.

Previously, the solver saved the full log from the start to the first backjump.
Then it filtered the log using the conflict set from the node where the first
backjump occurred, i.e., it removed all lines from the log that did not relate
to variables in the conflict set.  The solver also printed the final conflict
set at the end of the log.

This approach had several problems:

1. It was possible for the conflicts at the first backjump to be unrelated to
   the final conflict set (issue haskell#941).  The conflicts in the summarized log
   could be irrelevant to the failure, for example, if they were caused by only
   a single version of a dependency, which the solver could skip, and the real
   problem was a different dependency that was missing from the index.  Even if
   the summarized log was relevant, showing two different explanations for the
   same failure could be confusing.

2. Filtering the full log was error prone and could remove the wrong lines.  It
   caused bugs mentioned in haskell#2853 and haskell#4154.

3. The conflict set at the first backjump contains the variables directly
   involved in the conflicts at that level and the variables that introduced
   them, but it doesn't contain the whole chain of variables starting with the
   user targets.  When the log is filtered with that conflict set, it can be
   unclear why the solver needed to choose the conflicting packages in the first
   place.

This commit creates the summarized log by rerunning the solver with a backjump
limit of zero and using the full log.  Using an unfiltered log avoids (2) and
(3).  However, it is also important to shorten the log by only showing choices
that are relevant to conflicts.  This commit uses different approaches for the
two types of solver failures.

No solution:

This commit makes the solver prefer variables from the first run's final
conflict set when choosing goals in the second run.  This means that the log to
the first backjump is more likely to be relevant to the final failure, because
it only mentions packages, flags, and stanzas from the final conflict set.

Backjump limit reached:

There is no final conflict set in this case, since the solver did not traverse
the whole tree.  This commit tries to create a final conflict set by rerunning
the solver with a subtree of the original search tree that contains the path to
the first backjump.  Then it uses the final conflict set from that run to
generate a log message, as in the case where the solver found that there was no
solution.

Here is an example of the differences between the new and old logs, using the
command from issue haskell#4792 and GHC 8.2.1:

Before:

$ cabal install --dry-run --index-state=2018-01-04T21:05:55Z thorn
Resolving dependencies...
cabal: Could not resolve dependencies:
trying: base-4.10.0.0/installed-4.1... (dependency of thorn)
next goal: profunctors (dependency of thorn)
rejecting: profunctors-5.2.1, profunctors-5.2, profunctors-5.1.2,
profunctors-5.1.1, profunctors-5.1, profunctors-5.0.1, profunctors-5.0.0.1,
profunctors-5 (conflict: thorn => profunctors<5)
trying: profunctors-4.4.1
next goal: transformers (dependency of profunctors)
rejecting: transformers-0.5.2.0/installed-0.5..., transformers-0.5.5.0,
transformers-0.5.4.0, transformers-0.5.2.0, transformers-0.5.1.0,
transformers-0.5.0.1, transformers-0.5.0.0 (conflict: profunctors =>
transformers>=0.2 && <0.5)
rejecting: transformers-0.4.3.0, transformers-0.4.2.0 (conflict:
base==4.10.0.0/installed-4.1..., transformers => base>=2 && <4.9)
rejecting: transformers-0.4.1.0, transformers-0.3.0.0, transformers-0.2.2.1
(conflict: base==4.10.0.0/installed-4.1..., transformers +/-applicativeinbase
=> base>=1.0 && <4.8)
rejecting: transformers-0.2.1.0, transformers-0.2.0.0 (conflict:
base==4.10.0.0/installed-4.1..., transformers +/-applicativeinbase =>
base>=1.0 && <4.3)
rejecting: transformers-0.1.4.0, transformers-0.1.3.0, transformers-0.1.1.0,
transformers-0.1.0.1, transformers-0.0.1.0, transformers-0.0.0.0,
transformers-0.5.3.1, transformers-0.5.3.0, transformers-0.5.0.2 (conflict:
profunctors => transformers>=0.2 && <0.5)
rejecting: transformers-0.4.0.0 (conflict: base==4.10.0.0/installed-4.1...,
transformers +/-applicativeinbase => base>=1.0 && <4.8)
rejecting: transformers-0.2.2.0 (conflict: base==4.10.0.0/installed-4.1...,
transformers +/-applicativeinbase => base>=1.0 && <4.6)
rejecting: transformers-0.1.0.0 (conflict: profunctors => transformers>=0.2 &&
<0.5)
After searching the rest of the dependency tree exhaustively, these were the
goals I've had most trouble fulfilling: transformers, contravariant, base,
thorn

After:

$ cabal install --dry-run --index-state=2018-01-04T21:05:55Z thorn
Resolving dependencies...
cabal: Could not resolve dependencies:
[__0] trying: thorn-0.2 (user goal)
[__1] next goal: contravariant (dependency of thorn)
[__1] rejecting: contravariant-1.4, 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, contravariant-1.1, contravariant-1.0
(conflict: thorn => contravariant<1)
[__1] trying: contravariant-0.6.1.1
[__2] next goal: transformers (dependency of contravariant)
[__2] rejecting: transformers-0.5.2.0/installed-0.5..., transformers-0.5.5.0,
transformers-0.5.4.0, transformers-0.5.2.0, transformers-0.5.1.0,
transformers-0.5.0.1, transformers-0.5.0.0 (conflict: contravariant =>
transformers>=0.2 && <0.5)
[__2] trying: transformers-0.4.3.0
[__3] next goal: base (dependency of thorn)
[__3] rejecting: base-4.10.0.0/installed-4.1... (conflict: transformers =>
base>=2 && <4.9)
[__3] rejecting: base-4.10.1.0, base-4.10.0.0, base-4.9.1.0, base-4.9.0.0,
base-4.8.2.0, base-4.8.1.0, base-4.8.0.0, base-4.7.0.2, base-4.7.0.1,
base-4.7.0.0, base-4.6.0.1, base-4.6.0.0, base-4.5.1.0, base-4.5.0.0,
base-4.4.1.0, base-4.4.0.0, base-4.3.1.0, base-4.3.0.0, base-4.2.0.2,
base-4.2.0.1, base-4.2.0.0, base-4.1.0.0, base-4.0.0.0, base-3.0.3.2,
base-3.0.3.1 (constraint from non-upgradeable package requires installed
instance)
After searching the rest of the dependency tree exhaustively, these were the
goals I've had most trouble fulfilling: transformers, contravariant, base,
thorn

Differences:

- The new summary has level numbers, like the full log.
- The conflicts are different.  The old log mentions thorn, base, profunctors,
  and transformers, and the new log mentions the four packages from the conflict
  set: thorn, contravariant, transformers, and base.
- The new log starts with the solver choosing a user goal, thorn.

The solver continues to display the conflicts at the first backjump when it
reaches the backjump limit, i.e, it shows profunctors instead of contravariant:

Before:

$ cabal install --dry-run --index-state=2018-01-04T21:05:55Z thorn --max-backjumps=10
Resolving dependencies...
cabal: Could not resolve dependencies:
trying: base-4.10.0.0/installed-4.1... (dependency of thorn)
next goal: profunctors (dependency of thorn)
rejecting: profunctors-5.2.1, profunctors-5.2, profunctors-5.1.2,
profunctors-5.1.1, profunctors-5.1, profunctors-5.0.1, profunctors-5.0.0.1,
profunctors-5 (conflict: thorn => profunctors<5)
trying: profunctors-4.4.1
next goal: transformers (dependency of profunctors)
rejecting: transformers-0.5.2.0/installed-0.5..., transformers-0.5.5.0,
transformers-0.5.4.0, transformers-0.5.2.0, transformers-0.5.1.0,
transformers-0.5.0.1, transformers-0.5.0.0 (conflict: profunctors =>
transformers>=0.2 && <0.5)
rejecting: transformers-0.4.3.0, transformers-0.4.2.0 (conflict:
base==4.10.0.0/installed-4.1..., transformers => base>=2 && <4.9)
rejecting: transformers-0.4.1.0, transformers-0.3.0.0, transformers-0.2.2.1
(conflict: base==4.10.0.0/installed-4.1..., transformers +/-applicativeinbase
=> base>=1.0 && <4.8)
rejecting: transformers-0.2.1.0, transformers-0.2.0.0 (conflict:
base==4.10.0.0/installed-4.1..., transformers +/-applicativeinbase =>
base>=1.0 && <4.3)
rejecting: transformers-0.1.4.0, transformers-0.1.3.0, transformers-0.1.1.0,
transformers-0.1.0.1, transformers-0.0.1.0, transformers-0.0.0.0,
transformers-0.5.3.1, transformers-0.5.3.0, transformers-0.5.0.2 (conflict:
profunctors => transformers>=0.2 && <0.5)
rejecting: transformers-0.4.0.0 (conflict: base==4.10.0.0/installed-4.1...,
transformers +/-applicativeinbase => base>=1.0 && <4.8)
rejecting: transformers-0.2.2.0 (conflict: base==4.10.0.0/installed-4.1...,
transformers +/-applicativeinbase => base>=1.0 && <4.6)
rejecting: transformers-0.1.0.0 (conflict: profunctors => transformers>=0.2 &&
<0.5)
Backjump limit reached (currently 10, change with --max-backjumps or try to
run with --reorder-goals).

After:

$ cabal install --dry-run --index-state=2018-01-04T21:05:55Z thorn --max-backjumps=10
Resolving dependencies...
cabal: Could not resolve dependencies:
[__0] trying: thorn-0.2 (user goal)
[__1] next goal: profunctors (dependency of thorn)
[__1] rejecting: profunctors-5.2.1, profunctors-5.2, profunctors-5.1.2,
profunctors-5.1.1, profunctors-5.1, profunctors-5.0.1, profunctors-5.0.0.1,
profunctors-5 (conflict: thorn => profunctors<5)
[__1] trying: profunctors-4.4.1
[__2] next goal: transformers (dependency of profunctors)
[__2] rejecting: transformers-0.5.2.0/installed-0.5..., transformers-0.5.5.0,
transformers-0.5.4.0, transformers-0.5.2.0, transformers-0.5.1.0,
transformers-0.5.0.1, transformers-0.5.0.0 (conflict: profunctors =>
transformers>=0.2 && <0.5)
[__2] trying: transformers-0.4.3.0
[__3] next goal: base (dependency of thorn)
[__3] rejecting: base-4.10.0.0/installed-4.1... (conflict: transformers =>
base>=2 && <4.9)
[__3] rejecting: base-4.10.1.0, base-4.10.0.0, base-4.9.1.0, base-4.9.0.0,
base-4.8.2.0, base-4.8.1.0, base-4.8.0.0, base-4.7.0.2, base-4.7.0.1,
base-4.7.0.0, base-4.6.0.1, base-4.6.0.0, base-4.5.1.0, base-4.5.0.0,
base-4.4.1.0, base-4.4.0.0, base-4.3.1.0, base-4.3.0.0, base-4.2.0.2,
base-4.2.0.1, base-4.2.0.0, base-4.1.0.0, base-4.0.0.0, base-3.0.3.2,
base-3.0.3.1 (constraint from non-upgradeable package requires installed
instance)
Backjump limit reached (currently 10, change with --max-backjumps or try to
run with --reorder-goals).

One downside of this change is that the solver may reach the backjump limit when
generating the summarized log, if the backjump limit is very low:

$ cabal install --dry-run --index-state=2018-01-04T21:05:55Z thorn --max-backjumps=1
Resolving dependencies...
cabal: Backjump limit reached (currently 1, change with --max-backjumps or try
to run with --reorder-goals).
Failed to generate a summarized dependency solver log due to low backjump
limit.

Another downside is the performance impact of rerunning the solver.  It looks
like there isn't a big change in run time when the solver finds a solution or
fails after an exhaustive search.  However, rerunning the solver to the first
backjump after it reaches the backjump limit can take a significant amount of
time.  The worst case I could find was acme-everything with GHC 7.10.3, where
that step took 13 seconds.  The difference was normally small, though.

I ran hackage-benchmark on packages from Hackage to try to find packages where
the run time changed by more than a few percent.  I stopped it after all
packages starting with "b" (That includes all uppercase packages).

compiler: GHC 8.2.1
index state: 2018-01-04T21:05:55Z
parameters: --min-run-time-percentage-difference-to-rerun=1 --pvalue=0.01 --trials=20 --print-skipped-packages

Out of 2219 packages, 1064 were skipped because the run times in the first trial
were within 1%, 1065 differed by more than 1% in the first trial but did not
show a significant difference in run time in 20 trials, and 90 did show a
significant difference in run time.  Here are the counts of packages for
different ranges of speedup, for those 90 packages:

speedup (master avg. run time / branch avg. run time)     package count
[0.93, 0.94)                                              1
[0.94, 0.95)                                              0
[0.95, 0.96)                                              0
[0.96, 0.97)                                              1
[0.97, 0.98)                                              7
[0.98, 0.99)                                              29
[0.99, 1.00)                                              47
[1.00, 1.01)                                              3
[1.01, 1.02)                                              2

The package with the biggest percentage change was bittorrent, which ran for
3.85 seconds on master and 4.12 seconds on this branch.  It reached the backjump
limit.
grayjay added a commit to grayjay/cabal that referenced this issue Jan 10, 2018
@grayjay
Rerun dependency solver to generate a better error message (issue has…
5d3618a 
…kell#4823).

This commit changes the way that the solver generates the summarized log that it
displays at normal verbosity.

Previously, the solver saved the full log from the start to the first backjump.
Then it filtered the log using the conflict set from the node where the first
backjump occurred, i.e., it removed all lines from the log that did not relate
to variables in the conflict set.  The solver also printed the final conflict
set at the end of the log.

This approach had several problems:

1. It was possible for the conflicts at the first backjump to be unrelated to
   the final conflict set (issue haskell#941).  The conflicts in the summarized log
   could be irrelevant to the failure, for example, if they were caused by only
   a single version of a dependency, which the solver could skip, and the real
   problem was a different dependency that was missing from the index.  Even if
   the summarized log was relevant, showing two different explanations for the
   same failure could be confusing.

2. Filtering the full log was error prone and could remove the wrong lines.  It
   caused bugs mentioned in haskell#2853 and haskell#4154.

3. The conflict set at the first backjump contains the variables directly
   involved in the conflicts at that level and the variables that introduced
   them, but it doesn't contain the whole chain of variables starting with the
   user targets (issue haskell#4792).  When the log is filtered with that conflict set,
   it can be unclear why the solver needed to choose the conflicting packages in
   the first place.

This commit creates the summarized log by rerunning the solver with a backjump
limit of zero and using the full log.  Using an unfiltered log avoids (2) and
(3).  However, it is also important to shorten the log by only showing choices
that are relevant to conflicts.  This commit uses different approaches for the
two types of solver failures.

No solution:

This commit makes the solver prefer variables from the first run's final
conflict set when choosing goals in the second run.  This means that the log to
the first backjump is more likely to be relevant to the final failure, because
it only mentions packages, flags, and stanzas from the final conflict set.

Backjump limit reached:

There is no final conflict set in this case, since the solver did not traverse
the whole tree.  This commit tries to create a final conflict set by rerunning
the solver with a subtree of the original search tree that contains the path to
the first backjump.  Then it uses the final conflict set from that run to
generate a log message, as in the case where the solver found that there was no
solution.

Here is an example of the differences between the new and old logs, using the
command from issue haskell#4792 and GHC 8.2.1:

Before:

$ cabal install --dry-run --index-state=2018-01-04T21:05:55Z thorn
Resolving dependencies...
cabal: Could not resolve dependencies:
trying: base-4.10.0.0/installed-4.1... (dependency of thorn)
next goal: profunctors (dependency of thorn)
rejecting: profunctors-5.2.1, profunctors-5.2, profunctors-5.1.2,
profunctors-5.1.1, profunctors-5.1, profunctors-5.0.1, profunctors-5.0.0.1,
profunctors-5 (conflict: thorn => profunctors<5)
trying: profunctors-4.4.1
next goal: transformers (dependency of profunctors)
rejecting: transformers-0.5.2.0/installed-0.5..., transformers-0.5.5.0,
transformers-0.5.4.0, transformers-0.5.2.0, transformers-0.5.1.0,
transformers-0.5.0.1, transformers-0.5.0.0 (conflict: profunctors =>
transformers>=0.2 && <0.5)
rejecting: transformers-0.4.3.0, transformers-0.4.2.0 (conflict:
base==4.10.0.0/installed-4.1..., transformers => base>=2 && <4.9)
rejecting: transformers-0.4.1.0, transformers-0.3.0.0, transformers-0.2.2.1
(conflict: base==4.10.0.0/installed-4.1..., transformers +/-applicativeinbase
=> base>=1.0 && <4.8)
rejecting: transformers-0.2.1.0, transformers-0.2.0.0 (conflict:
base==4.10.0.0/installed-4.1..., transformers +/-applicativeinbase =>
base>=1.0 && <4.3)
rejecting: transformers-0.1.4.0, transformers-0.1.3.0, transformers-0.1.1.0,
transformers-0.1.0.1, transformers-0.0.1.0, transformers-0.0.0.0,
transformers-0.5.3.1, transformers-0.5.3.0, transformers-0.5.0.2 (conflict:
profunctors => transformers>=0.2 && <0.5)
rejecting: transformers-0.4.0.0 (conflict: base==4.10.0.0/installed-4.1...,
transformers +/-applicativeinbase => base>=1.0 && <4.8)
rejecting: transformers-0.2.2.0 (conflict: base==4.10.0.0/installed-4.1...,
transformers +/-applicativeinbase => base>=1.0 && <4.6)
rejecting: transformers-0.1.0.0 (conflict: profunctors => transformers>=0.2 &&
<0.5)
After searching the rest of the dependency tree exhaustively, these were the
goals I've had most trouble fulfilling: transformers, contravariant, base,
thorn

After:

$ cabal install --dry-run --index-state=2018-01-04T21:05:55Z thorn
Resolving dependencies...
cabal: Could not resolve dependencies:
[__0] trying: thorn-0.2 (user goal)
[__1] next goal: contravariant (dependency of thorn)
[__1] rejecting: contravariant-1.4, 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, contravariant-1.1, contravariant-1.0
(conflict: thorn => contravariant<1)
[__1] trying: contravariant-0.6.1.1
[__2] next goal: transformers (dependency of contravariant)
[__2] rejecting: transformers-0.5.2.0/installed-0.5..., transformers-0.5.5.0,
transformers-0.5.4.0, transformers-0.5.2.0, transformers-0.5.1.0,
transformers-0.5.0.1, transformers-0.5.0.0 (conflict: contravariant =>
transformers>=0.2 && <0.5)
[__2] trying: transformers-0.4.3.0
[__3] next goal: base (dependency of thorn)
[__3] rejecting: base-4.10.0.0/installed-4.1... (conflict: transformers =>
base>=2 && <4.9)
[__3] rejecting: base-4.10.1.0, base-4.10.0.0, base-4.9.1.0, base-4.9.0.0,
base-4.8.2.0, base-4.8.1.0, base-4.8.0.0, base-4.7.0.2, base-4.7.0.1,
base-4.7.0.0, base-4.6.0.1, base-4.6.0.0, base-4.5.1.0, base-4.5.0.0,
base-4.4.1.0, base-4.4.0.0, base-4.3.1.0, base-4.3.0.0, base-4.2.0.2,
base-4.2.0.1, base-4.2.0.0, base-4.1.0.0, base-4.0.0.0, base-3.0.3.2,
base-3.0.3.1 (constraint from non-upgradeable package requires installed
instance)
After searching the rest of the dependency tree exhaustively, these were the
goals I've had most trouble fulfilling: transformers, contravariant, base,
thorn

Differences:

- The new summary has level numbers, like the full log.
- The conflicts are different.  The old log mentions thorn, base, profunctors,
  and transformers, and the new log mentions the four packages from the conflict
  set: thorn, contravariant, transformers, and base.
- The new log starts with the solver choosing a user goal, thorn.

The solver continues to display the conflicts at the first backjump when it
reaches the backjump limit, i.e, it shows profunctors instead of contravariant:

Before:

$ cabal install --dry-run --index-state=2018-01-04T21:05:55Z thorn --max-backjumps=10
Resolving dependencies...
cabal: Could not resolve dependencies:
trying: base-4.10.0.0/installed-4.1... (dependency of thorn)
next goal: profunctors (dependency of thorn)
rejecting: profunctors-5.2.1, profunctors-5.2, profunctors-5.1.2,
profunctors-5.1.1, profunctors-5.1, profunctors-5.0.1, profunctors-5.0.0.1,
profunctors-5 (conflict: thorn => profunctors<5)
trying: profunctors-4.4.1
next goal: transformers (dependency of profunctors)
rejecting: transformers-0.5.2.0/installed-0.5..., transformers-0.5.5.0,
transformers-0.5.4.0, transformers-0.5.2.0, transformers-0.5.1.0,
transformers-0.5.0.1, transformers-0.5.0.0 (conflict: profunctors =>
transformers>=0.2 && <0.5)
rejecting: transformers-0.4.3.0, transformers-0.4.2.0 (conflict:
base==4.10.0.0/installed-4.1..., transformers => base>=2 && <4.9)
rejecting: transformers-0.4.1.0, transformers-0.3.0.0, transformers-0.2.2.1
(conflict: base==4.10.0.0/installed-4.1..., transformers +/-applicativeinbase
=> base>=1.0 && <4.8)
rejecting: transformers-0.2.1.0, transformers-0.2.0.0 (conflict:
base==4.10.0.0/installed-4.1..., transformers +/-applicativeinbase =>
base>=1.0 && <4.3)
rejecting: transformers-0.1.4.0, transformers-0.1.3.0, transformers-0.1.1.0,
transformers-0.1.0.1, transformers-0.0.1.0, transformers-0.0.0.0,
transformers-0.5.3.1, transformers-0.5.3.0, transformers-0.5.0.2 (conflict:
profunctors => transformers>=0.2 && <0.5)
rejecting: transformers-0.4.0.0 (conflict: base==4.10.0.0/installed-4.1...,
transformers +/-applicativeinbase => base>=1.0 && <4.8)
rejecting: transformers-0.2.2.0 (conflict: base==4.10.0.0/installed-4.1...,
transformers +/-applicativeinbase => base>=1.0 && <4.6)
rejecting: transformers-0.1.0.0 (conflict: profunctors => transformers>=0.2 &&
<0.5)
Backjump limit reached (currently 10, change with --max-backjumps or try to
run with --reorder-goals).

After:

$ cabal install --dry-run --index-state=2018-01-04T21:05:55Z thorn --max-backjumps=10
Resolving dependencies...
cabal: Could not resolve dependencies:
[__0] trying: thorn-0.2 (user goal)
[__1] next goal: profunctors (dependency of thorn)
[__1] rejecting: profunctors-5.2.1, profunctors-5.2, profunctors-5.1.2,
profunctors-5.1.1, profunctors-5.1, profunctors-5.0.1, profunctors-5.0.0.1,
profunctors-5 (conflict: thorn => profunctors<5)
[__1] trying: profunctors-4.4.1
[__2] next goal: transformers (dependency of profunctors)
[__2] rejecting: transformers-0.5.2.0/installed-0.5..., transformers-0.5.5.0,
transformers-0.5.4.0, transformers-0.5.2.0, transformers-0.5.1.0,
transformers-0.5.0.1, transformers-0.5.0.0 (conflict: profunctors =>
transformers>=0.2 && <0.5)
[__2] trying: transformers-0.4.3.0
[__3] next goal: base (dependency of thorn)
[__3] rejecting: base-4.10.0.0/installed-4.1... (conflict: transformers =>
base>=2 && <4.9)
[__3] rejecting: base-4.10.1.0, base-4.10.0.0, base-4.9.1.0, base-4.9.0.0,
base-4.8.2.0, base-4.8.1.0, base-4.8.0.0, base-4.7.0.2, base-4.7.0.1,
base-4.7.0.0, base-4.6.0.1, base-4.6.0.0, base-4.5.1.0, base-4.5.0.0,
base-4.4.1.0, base-4.4.0.0, base-4.3.1.0, base-4.3.0.0, base-4.2.0.2,
base-4.2.0.1, base-4.2.0.0, base-4.1.0.0, base-4.0.0.0, base-3.0.3.2,
base-3.0.3.1 (constraint from non-upgradeable package requires installed
instance)
Backjump limit reached (currently 10, change with --max-backjumps or try to
run with --reorder-goals).

One downside of this change is that the solver may reach the backjump limit when
generating the summarized log, if the backjump limit is very low:

$ cabal install --dry-run --index-state=2018-01-04T21:05:55Z thorn --max-backjumps=1
Resolving dependencies...
cabal: Backjump limit reached (currently 1, change with --max-backjumps or try
to run with --reorder-goals).
Failed to generate a summarized dependency solver log due to low backjump
limit.

Another downside is the performance impact of rerunning the solver.  It looks
like there isn't a big change in run time when the solver finds a solution or
fails after an exhaustive search.  However, rerunning the solver to the first
backjump after it reaches the backjump limit can take a significant amount of
time.  The worst case I could find was acme-everything with GHC 7.10.3, where
that step took 13 seconds.  The difference was normally small, though.

I ran hackage-benchmark on packages from Hackage to try to find packages where
the run time changed by more than a few percent.  I stopped it after all
packages starting with "b" (That includes all uppercase packages).

compiler: GHC 8.2.1
index state: 2018-01-04T21:05:55Z
parameters: --min-run-time-percentage-difference-to-rerun=1 --pvalue=0.01 --trials=20 --print-skipped-packages

Out of 2219 packages, 1064 were skipped because the run times in the first trial
were within 1%, 1065 differed by more than 1% in the first trial but did not
show a significant difference in run time in 20 trials, and 90 did show a
significant difference in run time.  Here are the counts of packages for
different ranges of speedup, for those 90 packages:

speedup (master avg. run time / branch avg. run time)     package count
[0.93, 0.94)                                              1
[0.94, 0.95)                                              0
[0.95, 0.96)                                              0
[0.96, 0.97)                                              1
[0.97, 0.98)                                              7
[0.98, 0.99)                                              29
[0.99, 1.00)                                              47
[1.00, 1.01)                                              3
[1.01, 1.02)                                              2

The package with the biggest percentage change was bittorrent, which ran for
3.85 seconds on master and 4.12 seconds on this branch.  It reached the backjump
limit.
23Skidoo added a commit that referenced this issue Feb 8, 2018
@23Skidoo
Merge pull request #5012 from grayjay/issue-4823
11d8a77 
 Rerun dependency solver to generate a better error message (issue #4823).
23Skidoo added a commit that referenced this issue Feb 8, 2018
@23Skidoo
Revert " Rerun dependency solver to generate a better error message (…
a50c004 
…issue #4823)."
@grayjay
Copy link
Collaborator Author

grayjay commented Feb 11, 2018

Implemented in #5012.

@grayjay grayjay closed this as completed Feb 11, 2018
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
cabal-install: solver type: enhancement
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@grayjay