GitLab

Ben Gamari authored Dec 06, 2016 and Mikhail Glushenkov committed Dec 07, 2016

(cherry picked from commit e0bf43c3)

Nix integration

Migrate ConflictSet qpn ↦ ConflictSet

Print final conflict set when search is exhaustive

Before this change, the behavior in the exhaustive case was to filter
the log up until the first error with the final conflict set, leading to
possibly inconsistently filtered error messages.

Now we always use the conflict set from the first error to filter the
the log, and then display the final conflict set as an additional hint.

[ci skip]

[ci skip]

Solver: Fix space leak in 'addlinking' (issue #2899).

Add some missing occurrences of flib in cabal-install.

Solver: Add missing call to 'simplifyVar'.

Solver: Avoid removing goal choices from the tree when applying heuristics.

'simplifyVar' removes flag names from the 'Var' type, so that all flags within a
package are treated as one during backjumping. A more complete fix would involve
creating a 'SimpleVar' type.

The bug caused the conflict counting heuristic to never prefer flag goals. Flag
variables in the tree's goals had the flags' original names, and the flag
variables in the conflict map did not have names, so they could never be equal.

Since this fix changes the goal order, I wanted to test for an unexpected large
negative impact on solver runtime. I ran the solver on all packages on Hackage
individually with GHC 8.0.1 and looked for differences of more than 10% between
master and the branch. There were twelve packages. I reran those packages three
times and found ten with a significant difference in runtime. Here are the
average runtimes. None of them hit the backjump limit.

package                         master (seconds)   branch (seconds)   ratio
clash-ghc                        2.60              3.99               1.54
hack-middleware-clientsession    8.22              2.54               0.31
hackage-server                   1.46              1.85               1.26
hamusic                          5.47              4.55               0.83
haskore-synthesizer             10.13              7.64               0.75
language-gcl                     2.54              2.03               0.80
ms                              36.98              8.02               0.22
pipes-cereal-plus                1.51              1.66               1.10
thorn                            8.28              3.08               0.37
wai-handler-devel                1.72              1.91               1.11

I looked at the diff in the -v3 log for several of them and saw that the solver
was making some flag choices earlier, as expected.

This isn't much of an improvement, but it at least looks like a safe change.

The error displayed is the first error, which matches the first
conflict set in the non-exhaustive case. In the exhaustive case,
however, we display the last conflict set alongside the first error.

The change in the error message, »the rest of the dependency tree«,
should make it clearer that the error may not come from the final
branches of the dependency tree, but that there may be a lot of branches
being traversed between the first error and the final conflict set, so
they may not be congruent.

(Reasoning for displaying the first rather than the last error in the
non-exhaustive case: Both the first and the last error may be occur near
the leaves, so the conflict set may be incomplete. At the first
backjump, however, the conflicts are more likely to be relevant as the
solver has made fewer compromises at that point.
In the exhaustive case, this is not relevant as the final conflict set
is located at the root, so the conflict set contains all the conflicts
of a certain path through the tree. This is much more useful than the
first conflict set.)

Example:

```
> ./.stack-work/install/x86_64-linux-nix/ghc-8.0.1/8.0.1/bin/cabal install --dry-run cabal-install-1.24.0.0 cabal-install-1.22.9.0
Warning: The package list for 'hackage.haskell.org' is 46 days old.
Run 'cabal update' to get the latest list of available packages.
Resolving dependencies...
cabal: Could not resolve dependencies:
next goal: cabal-install (user goal)
rejecting: cabal-install-1.24.0.0 (constraint from user target requires
==1.22.9.0)
rejecting: cabal-install-1.22.9.0 (constraint from user target requires
==1.24.0.0)
rejecting: cabal-install-1.22.8.0, cabal-install-1.22.7.0,
cabal-install-1.22.6.0, cabal-install-1.22.5.0, cabal-install-1.22.4.0,
cabal-install-1.22.3.0, cabal-install-1.22.2.0, cabal-install-1.22.0.1,
cabal-install-1.22.0.0, cabal-install-1.20.2.0, cabal-install-1.20.1.0,
cabal-install-1.20.0.6, cabal-install-1.20.0.5, cabal-install-1.20.0.4,
cabal-install-1.20.0.3, cabal-install-1.20.0.2, cabal-install-1.20.0.1,
cabal-install-1.20.0.0, cabal-install-1.18.2.0, cabal-install-1.18.1.0,
cabal-install-1.18.0.8, cabal-install-1.18.0.7, cabal-install-1.18.0.6,
cabal-install-1.18.0.5, cabal-install-1.18.0.4, cabal-install-1.18.0.3,
cabal-install-1.18.0.2, cabal-install-1.18.0.1, cabal-install-1.18.0,
cabal-install-1.16.1.0, cabal-install-1.16.0.2, cabal-install-1.16.0.1,
cabal-install-1.16.0, cabal-install-0.14.1, cabal-install-0.14.0,
cabal-install-0.10.2, cabal-install-0.10.0, cabal-install-0.8.2,
cabal-install-0.8.0, cabal-install-0.6.4, cabal-install-0.6.2,
cabal-install-0.6.0, cabal-install-0.5.2, cabal-install-0.5.1,
cabal-install-0.5.0, cabal-install-0.4.0 (constraint from user target requires
==1.22.9.0)
After searching the rest of the dependency tree exhaustively, these were the
goals I've had most trouble fulfilling: cabal-install (49)
```

Output the last error message in addition to the final conflict
set, and give a less technical description of the conflict set for the
user message.

An example for the expected output is:

> cabal install --dry-run DPM CurryDB DAV DSH Digit HList MagicHaskeller bamboo
cabal: Could not resolve dependencies:
trying: CurryDB-0.1.1.0 (user goal)
trying: base-4.8.0.0/installed-1b6... (dependency of CurryDB-0.1.1.0)
trying: unix-2.7.1.0/installed-e59... (dependency of process-1.2.3.0/installed-3b1...)
trying: directory-1.2.2.0/installed-b49... (dependency of process-1.2.3.0/installed-3b1...)
Dependency tree exhaustively searched.
I've had most trouble fulfilling the following goals: haskell98 (36850), base
(26359), directory (9599), HTF (5092), bamboo (3788), DPM (3452), unix (3208),
CurryDB (107)

Conflicts are sorted by conflict counts, so high-rated conflicts appear
early in the list. Currently the raw count is printed.

Keep information about the final conflict set and print it in case of
exhaustive search. The original error message is not printed any more.

Fixes #4141.
Signed-off-by: Edward Z. Yang <ezyang@cs.stanford.edu>

bootstrap.sh: do not use -j on ghc-7.8

--reorder-goals previously also preferred goals with two choices, but that had
the effect of preferring all flags, which can have at most two choices.

Previously, the solver applied goal-ordering heuristics by removing all
non-preferred goal choices when there was at least one preferred choice. This
left fewer goals for later steps, such as conflict counting, to work with.

This commit changes the heuristics so that they only sort the goals. I didn't
change the preferBaseGoalChoice heuristic, though, because it made the solver
slower in some cases. I also think that it is safe to always choose the version
of base first, because there is usually only one choice anyway.

I reversed the order of the heuristics, because sorting gives the most weight to
the last step, and pruning gives the most weight to the first step. The solver's
behavior should be unchanged with --no-count-conflicts.

Some notes on how I tested it:

I expected this change to improve performance in many cases by giving the
"conflict counting" heuristic more goals to choose from. However, I wasn't able
to find any cases where the solver made different choices compared with master,
except when I also used --reorder-goals. I spent a while looking, because it was
hard to believe.

I searched for examples first by comparing the verbose logs from this branch and
master for a few packages with many dependencies. Then I compared runtimes with
master when solving for each package on Hackage (with GHC 8.0.1), in order to
find packages with very large differences in runtime. Surprisingly, I didn't see
any where the change was over 50% in either direction. I reran ~10 with the
biggest difference and found two where the difference was more than noise. I
compared their logs, but they were also unchanged. Both were slower than master.
I profiled solving for grapefruit-ui-gtk, which was the slowest (18% slower than
master, with a runtime of ~20 seconds). I found that this branch spent about
twice as much time in Explore.getBestGoal. That makes sense, because getBestGoal
now has more goals to choose from. I didn't look into why the change had such a
big impact on that particular package.

I also tried running the solver on grapefruit-ui-gtk with --reorder-goals and no
backjump limit. This branch finished in about 67 seconds, and I stopped master
after ~8 minutes.

Then I compared runtime for another long-running combination of packages to test
the overhead of this change when the solver makes the same choices as master. I
ran 'cabal install --dry-run yesod phooey --max-backjumps -1' with GHC 8.0.1 and
took the average of 4 runs. master ran for 8.44 seconds, and this branch ran for
8.50 seconds, which is a difference of less than 1%.

Even though this change doesn't improve performance now, I think it's worthwhile
for simplifying the interactions between goal-ordering heuristics, and working
towards issue #3488 (Solver: Combine goal-ordering heuristics more effectively
by assigning scores to goal choices).

Cabal-1.18 in ghc-7.8 does not support -j

cabal-install integration-tests replacement omnibus patch

Signed-off-by: Edward Z. Yang <ezyang@cs.stanford.edu>

Signed-off-by: Edward Z. Yang <ezyang@cs.stanford.edu>

This fixes some "permission denied" failures on Windows,
but it would be a lot better to fix properly.  See the comment
in Test.Cabal.Monad for more details.
Signed-off-by: Edward Z. Yang <ezyang@cs.stanford.edu>

Otherwise, ghc-pkg will complain that it's reinitializing the
package database.

Possibly there is some refactor to make withPackageDb more robust
if it is called multiple times.
Signed-off-by: Edward Z. Yang <ezyang@cs.stanford.edu>

TODO: This seems to cause Windows failure
Signed-off-by: Edward Z. Yang <ezyang@cs.stanford.edu>

Previously, clients of runM had to explicitly record and check
the exit code of a run subcommand.  This has now been folded into
runM, so this is done always (which is what you wanted anyway.)
Signed-off-by: Edward Z. Yang <ezyang@cs.stanford.edu>

Previously, in some cases we would carry around an explicit
FilePath for an executable that we wanted to invoke subsequently.

In this new scheme, any executable we want to execute gets registered
to the ProgramDb we are carrying around.  Now we can uniformly
use runProgramM in all cases.  Great!
Signed-off-by: Edward Z. Yang <ezyang@cs.stanford.edu>

Signed-off-by: Edward Z. Yang <ezyang@cs.stanford.edu>