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

These tests are copied from cabal-testsuite/PackageTests/TemplateHaskell with
only minor changes.

Hackage requires the .cabal file to be named consistently with the package name,
but `cabal check` didn't detect this yet.

Example output:

    $ cabal check
    The following errors will cause portability problems on other environments:
    * The filename ./doo.cabal does not match package name (expected: foobar.cabal)

    Hackage would reject this package.

Note: this new check is implicitly/accidentally tested by an existing (unrelated)
test in `cabal-testsuite`.

Here were the root causes:

- Some tests involving Custom setpu showed MORE output
  (UseLocalPackageForSetup) when run on GHC 8.2.  This is because GHC
  8.2 ships a recent enough version of Cabal to know how to emit
  markers, which means we have started picking up the output.  I hacked
  up these tests to not accept this output, but a more correct thing to
  do is figure out how to NOT request marking of a Setup script which is
  not the inplace install.  This was a little tricky so I bailed.

- GHC 8.2 no longer emits "It is a member of the hidden package".
  This broke CustomWithoutCabalDefaultMain.  Not sure if this
  is a GHC regression but it's pretty harmless.

- While I was at it, I fixed an inexhaustive pattern match in
  cabal-testsuite (though perhaps poorly; I couldn't figure out
  what the new constructor does.)

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

This commit adds "cabal-version: >= 1.20" to enable per-component build and
work with all Cabal versions that support new-build.  It also adds the
"default-language" field, in order to avoid warnings.

Specifically test whether the old config file (cabal.project.old) is
displayed on stdout before it gets overwritten with `cabal new-configure`.

Signed-off-by: Pranit Bauva <pranit.bauva@gmail.com>

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

Previously, we stated that registration was needed if any build target
was a library.  Actually, this is not enough: if we have a build target
on an executable which in turn depends on the library, we must register
it.

To actually get this information, I had to refactor ComponentsGraph to
return the actual *graph*, so I could do a reverse closure on it, giving
me the set of components that actually depend on the library.  That info
then gets plumbed through ElaboratedPackage and then used to determine
if registration is necessary.

Fixes #4450, but it's possible there is another variant of the bug
that occurs if the executable to be built does NOT depend on the
library.

I also needed to add a new hasNewBuildCompatBootCabal helper to the
test suite to check if we can actually build the Custom setup
with the boot Cabal.

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

A few things:

- We now have a proper pre-mixin-linking pass which computes
  just the set of requirements we expect to see after mixin
  linking is done.  That lets us precompute the unit id
  for locally defined modules.

- Since we now know the correct module identities, we can
  make shapes for exposed-modules/other-modules and make
  them participate in mix-in linking.

- But we don't actually want to instantiate a requirement with
  a locally defined module, because GHC can't compile that!
  We want to error in this case.  Previously, we didn't notice
  that this had occurred at all; now it is caught, fixing #4447.

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

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

Suppose you have a Backpack package foo-indef, which has
some signatures; furthermore, elsewhere in your install plan
ths packages gets instantiated. When you type
'cabal new-build foo-indef', what should get built?

Previously: foo-indef, as well as all of its instantiations,
get built.

Now: only the indefinite foo-indef is typechecked.

This is what you want!

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

Previously, we used the solver dependencies to figure out
what to monitor, but this lead to a failure mode where we
would also monitor the monitor files associated with the
test suite, which we really shouldn't do.

This patch pushes the monitor file calculation later until
the build step, at which point we know exactly what our
dependencies are, and monitor those precisely.

Fixes #4405.

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

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

* Propagate ComponentName to ModuleSource, allowing
  us to accurately specify both package and library name
  of references.  (Arguably, should just stuff a ComponentInclude
  in there.)

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

* Add missing record selector.

* Correctly mkPackageIndex

* Skip T4375 on GHC 8.2, it doesn't have a Cabal to actually use!

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

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

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

Since VQuiet is set programmatically, it's inappropriate
for it to be propagated to the command line.  But unfortunately,
if it was set, we were accidentally using the fancy flag format.
This patch moves VQuiet to its own field in Verbosity so we
don't get confused.

Fixes #4393.

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

Prior to this patch, we were unconditionally sticking all dependencies
in a "whole package' ElaboratedConfiguredPackage, which resulted in
cycles when there were internal dependencies on the library in question,
and broken deps with convenience libraries.  Happily, the fix is simple,
although I did have to add ConfiguredId to the "extra" dependency fields
to make it easier to tell if a dependency was external or internal.

I added an extra test to make sure that we give a good error message
if a package requires per-component builds (apparently, internal
libraries require per-component builds!)

Fixes #4388.

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

* toConfiguredComponents and friends are now monadic.  This means
  we can report a user-friendly error when we fail to find a
  dependency in the dependency map.  I had to rejigger a bit
  of the logic in ProjectPlanning since we were knot-tying through
  this function, but it all worked out.  This means
  that unbuildable_external_lib_deps is no more.

* cc_internal_build_tools is no more; instead it's cc_exe_deps,
  which tracks ALL dependencies.  It also comes with a PackageId
  so we can build ConfiguredId cabal-install side.  This change
  propagates all the way to 'ReadyComponent'

* ProjectPlanning: Instead of recomputing dependencies from scratch,
  we instead use the ElaboratedConfiguredPackages we just finished
  making to build the ComponentDeps.

* ProjectPlanning now constructs a skeletal setupComponent.  This
  is used to setup the above with correct setup dependencies.
  In principle this component might also be used for building, but
  lots of functionality isn't written in yet.

* filterExeMapDep is no more; it's all handled by Cabal now.

* The ConfiguredComponentMap now handles both libraries and
  executables in one data structure.  This is nice.

* compSetupDependencies is no more, because elaborated components
  never have custom setup.

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

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

Fixes bug where cabal exec with foreign libraries didn't
actually work on Windows (because it was selecting
the wrong library directory).

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

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

Needed to stop logging dir change to stdout
to make test output deterministic.

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

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

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

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

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