[ci skip]

The conflict set that represents the option to not choose a value for a goal,
'initial', has two purposes:

1. 'initial' contributes to a node's conflict set, because it is unioned with
   the other conflict sets under the same choice node, if the current variable
   is contained in all of them.
2. 'initial' contributes to the conflict count.  When it is unioned with the
   other conflict sets, it is also added to the ConflictMap.

Previously, 'initial' was treated as the first of a node's children for (1) and
the last of the children for (2).  This refactoring treats 'initial' as the last
child in both cases, to make the code clearer, and renames it to 'lastCS'.
There should be no change in behavior.

In Explore.hs, the solver calculates a conflict set corresponding to the option
to not choose a value for each goal, called 'initial'.  That conflict set should
be added to the ConflictMap when the current goal causes a conflict.  However,
there was a bug, and the solver added 'initial' to the ConflictMap at every
level.

The bug meant that the solver preferred all goals that it had already chosen.
If a new goal started to cause conflicts, it would take a while for the solver
to start preferring the new goal over the ones that it had previously seen.
See #4595 for an example where this problem caused longer backjumps and slowed
down the solver.

Testing

I ran "cabal install --dry-run" for all packages on Hackage with master and the branch with a 90 second timeout, GHC 8.0.1, and index state 2017-07-08T04:20:18Z. Then I filtered out all packages where both runs had the same result (success or failure) and the times were within 10%. I repeated that process three times to eliminate packages that had different run times due to noise. Then I ran "cabal install --dry-run --max-backjumps=-1" on the remaining packages and averaged three runs.

Since this branch changes a goal-ordering heuristic, I expected a lot of changes in run time in either direction. Out of 105 changes, 83 were faster, 20 were slower, and 2 involved a timeout on both branches. (The two that timed out had different run times before I removed the backjump limit.)

package                          master result   master time (seconds)   branch result   branch time (seconds)   speedup
AesonBson                        solution         3.06                   solution         2.59                    1.18
DisTract                         no solution      1.48                   no solution      1.34                    1.1
GPipe-Examples                   timeout         90.01                   no solution      2.11                    -
GuiTV                            solution         2.54                   solution        16.05                    0.16
Phsu                             solution         3.49                   solution         1.83                    1.9
Ranka                            no solution      2.05                   no solution      1.65                    1.25
Rlang-QQ                         no solution      2.97                   no solution      1.89                    1.57
SourceGraph                      timeout         90.04                   no solution     11.53                    -
Validation                       no solution      2.1                    no solution      6.59                    0.32
WebCont                          no solution      2.04                   no solution      1.6                     1.28
acme-everything                  timeout         90.02                   timeout         90                       -
aeson-t                          solution         2.04                   solution         1.81                    1.13
alsa-gui                         no solution      1.62                   no solution      1.86                    0.87
aviation-cessna172-diagrams      no solution      2.56                   no solution      2.29                    1.12
aws-dynamodb-conduit             no solution      2.22                   no solution      1.83                    1.22
azure-servicebus                 no solution      5.18                   no solution      2.87                    1.8
bamboo-theme-mini-html5          no solution      2.51                   no solution      2                       1.26
bitcoin-payment-channel          solution         3.42                   solution         2.73                    1.25
bittorrent                       no solution      2.75                   no solution      2.4                     1.15
blaze-builder-enumerator         no solution      1.62                   no solution      1.88                    0.86
blunt                            solution         2.99                   solution         2.5                     1.19
cash                             no solution      1.33                   no solution      1.53                    0.87
cheapskate-terminal              no solution      2.04                   no solution      1.62                    1.26
clckwrks-plugin-bugs             no solution      3.85                   no solution      5.78                    0.67
cmdtheline                       no solution      1.96                   no solution      1.63                    1.2
colchis                          no solution      1.99                   no solution      2.23                    0.89
collada-types                    no solution      1.86                   no solution      1.66                    1.12
convertible-text                 solution         1.61                   solution         1.83                    0.88
cqrs-example                     no solution      2.64                   no solution      2.32                    1.14
dixi                             solution         4.44                   solution         4.03                    1.1
ethereum-client-haskell          no solution      1.84                   no solution      2.45                    0.75
flowdock                         no solution      2.46                   no solution      3.19                    0.77
geniserver                       no solution      5.34                   no solution      4.84                    1.1
ghc-imported-from                solution         4.59                   solution         2.9                     1.58
gps2htmlReport                   solution         3.08                   solution         5.58                    0.55
guarded-rewriting                solution         1.54                   solution         1.34                    1.14
hack2-handler-happstack-server   no solution      1.76                   no solution      2                       0.88
halma-telegram-bot               solution         4.27                   solution         3.37                    1.27
happs-tutorial                   no solution      2.08                   no solution      1.86                    1.12
happstack                        no solution      3.08                   no solution      5.86                    0.53
happstack-facebook               timeout         90.01                   timeout         90.03                    -
haskelldb-hsql-mysql             no solution      1.73                   no solution      1.5                     1.16
hdbi                             no solution      1.92                   no solution      1.66                    1.15
hdbi-postgresql                  no solution      3.05                   no solution      1.95                    1.56
hdbi-sqlite                      no solution      1.91                   no solution      1.69                    1.13
hexpat-iteratee                  no solution      2.61                   no solution      1.84                    1.42
hist-pl                          no solution      2.69                   no solution      2.36                    1.14
hscd                             no solution      2.53                   no solution      1.59                    1.59
http-client-lens                 no solution      3.63                   no solution      1.96                    1.85
hubris                           no solution      3.62                   no solution      1.63                    2.22
infinity                         no solution      1.34                   no solution      1.5                     0.89
iteratee-parsec                  no solution      2.01                   no solution      1.74                    1.16
json-togo                        no solution      1.86                   no solution      1.65                    1.13
lat                              no solution      2.87                   no solution      1.86                    1.55
liquidhaskell                    solution         3.34                   solution         2.25                    1.48
manatee-core                     no solution      1.79                   no solution      1.6                     1.12
manatee-curl                     no solution      8.44                   no solution      2.73                    3.09
manatee-editor                   no solution      5.05                   no solution      2.81                    1.8
manatee-filemanager              no solution     29.09                   no solution      2.96                    9.82
manatee-imageviewer              no solution      1.78                   no solution      1.57                    1.13
manatee-mplayer                  no solution      8.98                   no solution      4.05                    2.22
manatee-terminal                 no solution      3.19                   no solution      2.41                    1.32
minimung                         no solution      1.86                   no solution      1.57                    1.19
monoids                          no solution      3.02                   no solution      2.68                    1.13
mprover                          no solution      1.89                   no solution      1.54                    1.23
ms                               no solution      8.04                   no solution      4.35                    1.85
music-sibelius                   solution         3.1                    solution         2.5                     1.24
nerf                             solution        22.54                   solution         3.09                    7.29
nomyx-api                        solution         5.46                   solution         4.39                    1.24
nomyx-library                    solution         2.08                   solution         1.86                    1.11
nomyx-server                     no solution      4.83                   no solution      3.92                    1.23
opaleye-classy                   no solution      2.07                   no solution      3.58                    0.58
openflow                         no solution      1.95                   no solution      1.66                    1.18
ot                               no solution      3.37                   no solution      1.95                    1.73
paypal-api                       no solution      1.89                   no solution      1.64                    1.15
pdf-slave-server                 no solution      3.21                   no solution      2.15                    1.49
phooey                           solution         2.55                   solution        16.24                    0.16
pipes-cereal-plus                solution         1.85                   solution         1.65                    1.12
pocket-dns                       no solution      2.71                   no solution      2.08                    1.3
pontarius-mediaserver            no solution      2.29                   no solution      2.7                     0.85
precis                           no solution      2.53                   no solution      3.23                    0.78
prove-everywhere-server          no solution      2.19                   no solution      1.92                    1.14
quickbooks                       no solution      5.86                   no solution      5.17                    1.13
rbpcp-api                        solution         2.35                   solution         2.13                    1.11
react-haskell                    timeout         90.02                   no solution     71.21                    -
regex-xmlschema                  no solution      1.34                   no solution      1.51                    0.89
remote-json-server               solution         2.1                    solution         1.8                     1.16
scholdoc-citeproc                no solution      3                      no solution      1.92                    1.57
scion-browser                    no solution      5.21                   no solution      4.65                    1.12
semdoc                           no solution      4.21                   no solution      3.04                    1.39
servant-auth-token-rocksdb       no solution      4.68                   no solution      2.32                    2.02
snaplet-auth-acid                no solution      2.25                   no solution      1.99                    1.13
snaplet-stripe                   no solution      3.46                   no solution      2.97                    1.16
sssp                             no solution      3.3                    no solution      2.79                    1.18
target                           solution         2.8                    solution         2.11                    1.32
tls-extra                        no solution      2.74                   no solution      2.36                    1.16
twentefp-rosetree                no solution      1.69                   no solution      1.97                    0.86
twitter-enumerator               no solution     28.39                   no solution      2.16                   13.15
wai-middleware-cache             no solution      1.95                   no solution      1.56                    1.25
wai-middleware-catch             no solution      1.9                    no solution      1.54                    1.24
wai-middleware-route             solution        11.9                    solution         1.62                    7.34
xml2json                         no solution      2.27                   no solution      1.68                    1.35
yesod-auth-account-fork          solution         3.33                   solution         2.87                    1.16
yesod-comments                   no solution     25.6                    no solution     14.44                    1.77
yesod-pure                       solution         7.99                   solution         4.45                    1.79

I don't know if it was there for a reason, but it looks like it wasn't.

[ci skip]

This reverts commit aa682f9e.

This extends the capabilities of `--allow-{newer,older}` to allow for more
fine-grained scoping to control more precisely which packages and constraints
a relaxation is applied to. See updated documentation for more details.

The idea here is to break the dependency that has crept in from the
"Solver" into the "Client". (If there's ever going to be a separate
solver then the dependency would become a big problem.)

Completely randomizing the goal order exposes more bugs in backjumping than
using --reorder-goals.  I only applied the change to one test in this commit,
because the randomization function slowed down some of the other tests
significantly.

A DependencyReason contains flags paired with values FlagTrue, FlagFalse, or
FlagBoth, where FlagBoth means that the dependency was introduced by either
value of the flag and was lifted out of a conditional.  In the previous commit,
when a dependency led to a conflict, all flags in the DependencyReason were
added to the error message and conflict set.  This commit avoids adding flags
with value FlagBoth to the conflict set, because they can have a negative effect
on goal order: After the solver encounters a conflict involving such a flag, it
starts to prefer the flag when choosing goals, due to the solver's conflict
counting feature.  The solver shouldn't prefer the flag goal because it didn't
actually need to choose the flag to see the dependency.  Flags with value
FlagBoth are still useful for error messages, though.

I measured the performance of the last two commits by comparing commit
fc3ef2a7 (master) with this commit.  I did all
testing with GHC 8.0.1 and
'index-state(hackage.haskell.org) = 2017-06-11T02:16:39Z'.  I ran each version
of cabal (cabal install --dry-run) on each package on Hackage and looked for
packages with a difference in run time of at least 10%.  Then I reran cabal on
those packages to narrow down the list further (The results were noisy).  Here
are the average run times from five runs with the remaining packages:

package                        master result   master time (seconds)   branch result   branch time (seconds)   speedup
concraft                       backjump limit   5.67                   backjump limit   4.89                    1.16
forml                          backjump limit  10.26                   backjump limit   8.85                    1.16
hack-handler-simpleserver      backjump limit   6.28                   no solution      1.96                    3.21
hack-middleware-clientsession  backjump limit  17.86                   no solution      1.95                    9.14
haskore                        backjump limit   5.21                   no solution      1.67                    3.12
haskore-synthesizer            no solution     23.14                   no solution      2.21                   10.49
language-gcl                   no solution      3.06                   no solution      2.31                    1.33
ms                             backjump limit  61.68                   no solution      7.95                    7.76
nerf                           solution         4.1                    backjump limit   5.87                    0.7
puzzle-draw                    solution        56.28                   solution         5.31                   10.6
react-haskell                  backjump limit  44.23                   backjump limit  14.46                    3.06
reflex-transformers            no solution      2.18                   no solution      1.9                     1.15
shpider                        backjump limit   7.44                   solution         1.88                    3.95
thorn                          backjump limit  11.11                   backjump limit   4.44                    2.5

Both versions of cabal hit the backjump limit in four of the cases, so they
don't really tell us which version performed better.  All but one of the others
are improvements.  I looked at a few of the logs, and, as far as I can tell,
most of the improvements are due to flags being used in conflict counting.  This
behavior is similar to #4147, which was reverted.  The log for 'nerf', the one
package that had worse performance, showed that the solver chose some flags
earlier, but I didn't see any other reason for the slowdown.  The solver found a
solution when I used '--max-backjumps -1'.

These differences in run time are caused by differences in goal order and/or
backjumping, but I also wanted to compare performance when the solver went
through similar steps on master and the branch.  I found two commands that led
to very similar -v3 output between the cabal versions.  Presumably, package
flags didn't cause many conflicts in these runs.

cabal install --dry-run --max-backjumps -1 gi-glib happstack
cabal install --dry-run yesod

I took the average of three runs.  There wasn't a big difference between master
and the branch.

packages             result        master time (seconds)   branch time (seconds)   master memory (MB)   branch memory (MB)
gi-glib, happstack   no solution   30.02                   30.70                   245                  245
yesod                solution       3.53                    3.55                   239                  239.3

This commit changes the way that the solver tracks the variables that introduce
dependencies, in order to fix some bugs that prevented the solver from tracking
individual flags.  I refactored Dep, the type that represents a build-depends or
build-tool-depends dependency, so that it stores the package, flag, and stanza
choices that introduced the dependency.  That information is stored in a field
of type DependencyReason.  The DependencyReason is available to any solver phase
that needs to create conflict sets, such as "build" or "validation".  Whenever
there is a conflict involving a dependency, the solver creates a conflict set
and a log message using the dependency's DependencyReason.  This means that the
solver only needs to calculate the dependency reasons once, in
IndexConversion.hs, rather than every time they are used, i.e., in Builder.hs
(for goal reasons), Validate.hs, and Linking.hs.

Another difference between this commit and master is the dependencies between
solver variables.  On master, each dependency or variable is introduced by
exactly one other variable.  For example, if package x has a flag y, which
controls a dependency on package z, then the three variables depend on each
other in a chain, x -> y -> z.  If z can't be satisfied, the solver backjumps
to its cause, y, and if flipping y doesn't help, it continues backjumping to y's
cause, which is x.  In contrast, this commit allows each dependency to be
introduced by a package and any number of flags and stanzas.  So z's
DependencyReason would contain both x and y.

Storing all flags that introduced a dependency allows the solver to correctly
calculate conflict sets when there are nested conditionals.  We no longer need
to combine each package's flags into a single conflict set variable.  This
commit removes the 'simplifyVar' function and adds flag variables directly to
conflict sets.  See issue #4391.

This commit makes another minor change.  In this commit and master, if a
dependency appears in the if and else blocks of a conditional, the solver lifts
it out of the conditional.  Previously, the solver behaved as if the flag did
not introduce the dependency.  This commit adds the flag variable to the
conflict set or error message if the dependency is involved in a conflict.  This
change doesn't affect correctness, but I think it improves the error messages,
since it gives the whole reason that each dependency was introduced.

This just moves some functions and types into Validate.hs in preparation for
#4391.

Now DSL.exResolve takes a goal-ordering function, which is more flexible
than a list of sorted goals.