new-build dependency solver failure with GHC 7.0 #4154
Comments
|
One thing that pops out to me: GHC 7.0.4 is really old. When I run your repro steps with cabal-install HEAD, I get this: |
|
I think the problem is that your |
|
I don't understand the error you get from cabal-install HEAD: can't it just install a new FWIW I'm using an old GHC and time to test that HTTP continues to work with its lower bounds. If I can't make this work I'll just bump them, but I thought it was worth investigating/understanding because the error didn't seem specific to using very old software. Thanks for looking at this, in any case. |
|
I think there are two more bugs here. new-build adds default setup dependencies to packages that have cabal/cabal-install/Distribution/Client/ProjectPlanning.hs Lines 2503 to 2505 in 32cae60 time-1.1.2.3 also has build-type Custom. This creates a cycle. Then the solver filters the full log incorrectly and doesn't show the most important line. Here is the end of the -v3 log, with the message about cyclic dependencies on the last line:
Even the full log is a little misleading, because the solver doesn't complain about the cycle until after it has chosen all of the dependencies. One solution would be to check for cycles at every step. I'm not sure what we should do about the default setup dependencies. /cc @dcoutts EDIT: I ran cabal with --max-backjumps=0, which is why the log stopped after the first error. |
|
@grayjay thanks for the explanation - which also points to a simpler repro. I see the same problem either building time-1.1.2.3 itself, or a fresh cabal project that depends on time, both with the |
|
Yes, when I just realized that the log actually refers to a cycle between |
|
Isn't this a general bootstrapping problem? For example if I unpack I think as @ezyang says we need a way to specify the constraint without constraining setup deps. In fact I'd say that should be the default, and we'd need something explicit to constrain setup deps. Otherwise you're always risking confusion if you try to constrain something that happens to be a dep of |
grayjay
added a commit
to grayjay/cabal
that referenced
this issue
Dec 19, 2016
Previously, the solver only checked for cycles after it had already found a solution. That reduced the number of times that it performed the check in the common case when there were no cycles. However, when there was a cycle, the solver could spend a lot of time searching subtrees that already had a cyclic dependency and therefore could not lead to a solution. This is part of haskell#3824. Changes in this commit: - Store the reverse dependency map on all choice nodes in the search tree, so that 'detectCyclesPhase' can access it at every step. - Check for cycles incrementally at every step. Any new cycle must contain the current package, so we just check whether the current package is reachable from its neighbors. - If there is a cycle, we convert the map to a graph and find a strongly connected component, as before. - Instead of using the whole strongly connected component as the conflict set, we select one cycle. Smaller conflict sets are better for backjumping. - The incremental cycle detection automatically fixes a bug where the solver filtered out the message about cyclic dependencies when it summarized the full log. The bug occurred when the failure message was not immediately after the line where the solver chose one of the packages involved in the conflict. See haskell#4154. I tried several approaches before I found something with reasonable performance. Here is a comparison of runtime and memory usage. I turned off assertions when building cabal. Index state: index-state(hackage.haskell.org) = 2016-12-03T17:22:05Z GHC 8.0.1 Runtime in seconds: Packages Search tree depth Trials master This PR haskell#1 haskell#2 yesod 343 3 2.00 2.00 2.13 2.02 yesod gi-glib leksah 744 3 3.21 3.31 4.10 3.48 phooey 66 3 3.48 3.54 3.56 3.57 stackage nightly snapshot 6791 1 186 193 357 191 Total memory usage in MB, with '+RTS -s': Packages Trials master This PR haskell#1 haskell#2 yesod 1 189 188 188 198 yesod gi-glib leksah 1 257 257 263 306 stackage nightly snapshot 1 1288 1338 1432 12699 haskell#1 - Same as master, but with cycle checking (Data.Graph.stronglyConnComp) after every step. haskell#2 - Store dependencies in Distribution.Compat.Graph in the search tree, and check for cycles containing the current package at every step.
grayjay
added a commit
to grayjay/cabal
that referenced
this issue
Dec 19, 2016
Previously, the solver only checked for cycles after it had already found a solution. That reduced the number of times that it performed the check in the common case where there were no cycles. However, when there was a cycle, the solver could spend a lot of time searching subtrees that already had a cyclic dependency and therefore could not lead to a solution. This is part of haskell#3824. Changes in this commit: - Store the reverse dependency map on all choice nodes in the search tree, so that 'detectCyclesPhase' can access it at every step. - Check for cycles incrementally at every step. Any new cycle must contain the current package, so we just check whether the current package is reachable from its neighbors. - If there is a cycle, we convert the map to a graph and find a strongly connected component, as before. - Instead of using the whole strongly connected component as the conflict set, we select one cycle. Smaller conflict sets are better for backjumping. - The incremental cycle detection automatically fixes a bug where the solver filtered out the message about cyclic dependencies when it summarized the full log. The bug occurred when the failure message was not immediately after the line where the solver chose one of the packages involved in the conflict. See haskell#4154. I tried several approaches and compared performance when solving for packages with different numbers of dependencies. Here are the results. None of these runs involved any cycles, so they should have only tested the overhead of cycle checking. I turned off assertions when building cabal. Index state: index-state(hackage.haskell.org) = 2016-12-03T17:22:05Z GHC 8.0.1 Runtime in seconds: Packages Search tree depth Trials master This PR haskell#1 haskell#2 yesod 343 3 2.00 2.00 2.13 2.02 yesod gi-glib leksah 744 3 3.21 3.31 4.10 3.48 phooey 66 3 3.48 3.54 3.56 3.57 Stackage nightly snapshot 6791 1 186 193 357 191 Total memory usage in MB, with '+RTS -s': Packages Trials master This PR haskell#1 haskell#2 yesod 1 189 188 188 198 yesod gi-glib leksah 1 257 257 263 306 Stackage nightly snapshot 1 1288 1338 1432 12699 haskell#1 - Same as master, but with cycle checking (Data.Graph.stronglyConnComp) after every step. haskell#2 - Store dependencies in Distribution.Compat.Graph in the search tree, and check for cycles containing the current package at every step.
I think it makes sense to only constrain the main dependencies by default, to avoid interfering with bootstrapping. |
ezyang
pushed a commit
that referenced
this issue
Dec 27, 2016
Previously, the solver only checked for cycles after it had already found a solution. That reduced the number of times that it performed the check in the common case where there were no cycles. However, when there was a cycle, the solver could spend a lot of time searching subtrees that already had a cyclic dependency and therefore could not lead to a solution. This is part of #3824. Changes in this commit: - Store the reverse dependency map on all choice nodes in the search tree, so that 'detectCyclesPhase' can access it at every step. - Check for cycles incrementally at every step. Any new cycle must contain the current package, so we just check whether the current package is reachable from its neighbors. - If there is a cycle, we convert the map to a graph and find a strongly connected component, as before. - Instead of using the whole strongly connected component as the conflict set, we select one cycle. Smaller conflict sets are better for backjumping. - The incremental cycle detection automatically fixes a bug where the solver filtered out the message about cyclic dependencies when it summarized the full log. The bug occurred when the failure message was not immediately after the line where the solver chose one of the packages involved in the conflict. See #4154. I tried several approaches and compared performance when solving for packages with different numbers of dependencies. Here are the results. None of these runs involved any cycles, so they should have only tested the overhead of cycle checking. I turned off assertions when building cabal. Index state: index-state(hackage.haskell.org) = 2016-12-03T17:22:05Z GHC 8.0.1 Runtime in seconds: Packages Search tree depth Trials master This PR #1 #2 yesod 343 3 2.00 2.00 2.13 2.02 yesod gi-glib leksah 744 3 3.21 3.31 4.10 3.48 phooey 66 3 3.48 3.54 3.56 3.57 Stackage nightly snapshot 6791 1 186 193 357 191 Total memory usage in MB, with '+RTS -s': Packages Trials master This PR #1 #2 yesod 1 189 188 188 198 yesod gi-glib leksah 1 257 257 263 306 Stackage nightly snapshot 1 1288 1338 1432 12699 #1 - Same as master, but with cycle checking (Data.Graph.stronglyConnComp) after every step. #2 - Store dependencies in Distribution.Compat.Graph in the search tree, and check for cycles containing the current package at every step.
grayjay
added a commit
to grayjay/cabal
that referenced
this issue
Jan 22, 2017
grayjay
added a commit
to grayjay/cabal
that referenced
this issue
Jan 22, 2017
grayjay
added a commit
to grayjay/cabal
that referenced
this issue
Jan 22, 2017
grayjay
added a commit
to grayjay/cabal
that referenced
this issue
Jan 22, 2017
grayjay
added a commit
to grayjay/cabal
that referenced
this issue
Jan 30, 2017
ezyang
pushed a commit
that referenced
this issue
Feb 3, 2017
grayjay
added a commit
to grayjay/cabal
that referenced
this issue
Jan 8, 2018
…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
…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
…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
…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
…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.
4 tasks
grayjay
added a commit
to grayjay/cabal
that referenced
this issue
Mar 5, 2018
…askell#415. This commit addresses the comments in PR haskell#5183.
grayjay
added a commit
to grayjay/cabal
that referenced
this issue
Mar 5, 2018
…askell#415. This commit addresses the comments in PR haskell#5183.
grayjay
added a commit
to grayjay/cabal
that referenced
this issue
Mar 8, 2018
…askell#415. This commit addresses the comments in PR haskell#5183. (cherry picked from commit 2b197f8)
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
I'm running
This command-line works fine with a clean sandbox:
If I unpack HTTP-4000.3.3 and run this command-line in the unpacked folder, it fails in the dependency solver after several minutes:
with
I'm not sure how to interpret the error message - the first line suggests it's trying to link the
Cabalversions used fortimeandentropy's setup programs, but I'm not sure what the second line is about at all.The text was updated successfully, but these errors were encountered: