GitLab

Summary:
When GHC reports that it cannot solve a constraint in error
messages, it often reports what given constraints it has in scope.
Unfortunately, sometimes redundant constraints (like `* ~ *`, from
#15361) can sneak in. The fix is simple: blast away these redundant
constraints using `mkMinimalBySCs`.

Test Plan: make test TEST=T15361

Reviewers: simonpj, bgamari

Subscribers: rwbarton, thomie, carter

GHC Trac Issues: #15361

Differential Revision: https://phabricator.haskell.org/D5002

Summary:
Previously, GHC would always raise the possibility that a
type family might not be injective in certain error messages, even if
that type family actually //was// injective. Fix this by actually
checking for a type family's lack of injectivity before emitting
such an error message.

Test Plan: ./validate

Reviewers: goldfire, austin, bgamari, simonpj

Reviewed By: simonpj

Subscribers: simonpj, rwbarton, thomie

GHC Trac Issues: #14369

Differential Revision: https://phabricator.haskell.org/D4106

This patch takes further my refactoring of the constraint
solver, which I've been doing over the last couple of months
in consultation with Richard.

It fixes a number of tricky bugs that made the constraint
solver actually go into a loop, including

  Trac #12526
  Trac #12444
  Trac #12538

The main changes are these

* Flatten unification variables (fmvs/fuvs) appear on the LHS
  of a tvar/tyvar equality; thus
           fmv ~ alpha
  and not
           alpha ~ fmv

  See Note [Put flatten unification variables on the left]
  in TcUnify.  This is implemented by TcUnify.swapOverTyVars.

* Don't reduce a "loopy" CFunEqCan where the fsk appears on
  the LHS:
      F t1 .. tn ~ fsk
  where 'fsk' is free in t1..tn.
  See Note [FunEq occurs-check principle] in TcInteract

  This neatly stops some infinite loops that people reported;
  and it allows us to delete some crufty code in reduce_top_fun_eq.
  And it appears to be no loss whatsoever.

  As well as fixing loops, ContextStack2 and T5837 both terminate
  when they didn't before.

* Previously we generated "derived shadow" constraints from
  Wanteds, but we could (and sometimes did; Trac #xxxx) repeatedly
  generate a derived shadow from the same Wanted.

  A big change in this patch is to have two kinds of Wanteds:
     [WD] behaves like a pair of a Wanted and a Derived
     [W]  behaves like a Wanted only
  See CtFlavour and ShadowInfo in TcRnTypes, and the ctev_nosh
  field of a Wanted.

  This turned out to be a lot simpler.  A [WD] gets split into a
  [W] and a [D] in TcSMonad.maybeEmitShaodow.

  See TcSMonad Note [The improvement story and derived shadows]

* Rather than have a separate inert_model in the InertCans, I've
  put the derived equalities back into inert_eqs.  We weren't
  gaining anything from a separate field.

* Previously we had a mode for the constraint solver in which it
  would more aggressively solve Derived constraints; it was used
  for simplifying the context of a 'deriving' clause, or a 'default'
  delcaration, for example.

  But the complexity wasn't worth it; now I just make proper Wanted
  constraints.  See TcMType.cloneWC

* Don't generate injectivity improvement for Givens; see
  Note [No FunEq improvement for Givens] in TcInteract

* solveSimpleWanteds leaves the insolubles in-place rather than
  returning them.  Simpler.

I also did lots of work on comments, including fixing Trac #12821.

Summary:
foldUFM introduces unnecessary non-determinism that actually
leads to different generated code as explained in
Note [TrieMap determinism].

As we're switching from UniqFM to UniqDFM here you might be
concerned about performance. There's nothing that ./validate
detects. nofib reports no change in Compile Allocations, but
Compile Time got better on some tests and worse on some,
yielding this summary:

        -1 s.d.                -----            -3.8%
        +1 s.d.                -----            +5.4%
        Average                -----            +0.7%

This is not a fair comparison as the order of Uniques
changes what GHC is actually doing. One benefit from making
this deterministic is also that it will make the
performance results more stable.

Full nofib results: P108

Test Plan: ./validate, nofib

Reviewers: goldfire, simonpj, simonmar, austin, bgamari

Reviewed By: simonpj

Subscribers: thomie

Differential Revision: https://phabricator.haskell.org/D2169

GHC Trac Issues: #4012

varSetElemsWellScoped introduces unnecessary non-determinism in
inferred type signatures.
Removing this instance required changing the representation of
TcDepVars to use deterministic sets.
This is the last occurence of varSetElemsWellScoped, allowing me to
finally remove it.

Test Plan:
./validate
I will update the expected outputs when commiting, some reordering
of type variables in types is expected.

Reviewers: goldfire, simonpj, austin, bgamari

Reviewed By: simonpj

Subscribers: thomie, simonmar

Differential Revision: https://phabricator.haskell.org/D2135

GHC Trac Issues: #4012

This patch fixes Trac #11523.

* The basic problem was that TcRnTypes.superClassesMightHelp was
  returning True of a Derived constraint, and that led to us
  expanding Given superclasses, which produced the same Derived
  constraint again, and so on infinitely.  We really want to do
  this only if there are unsolve /Wanted/ contraints!

* On the way I made TcSMonad.getUnsolvedInerts a bit more
  discriminating about which Derived equalities it returns;
  see Note [Unsolved Derived equalities] in TcSMonad

* Lots of new comments in TcSMonad.

This re-working of the typechecker algorithm is based on
the paper "Visible type application", by Richard Eisenberg,
Stephanie Weirich, and Hamidhasan Ahmed, to be published at
ESOP'16.

This patch introduces -XTypeApplications, which allows users
to say, for example `id @Int`, which has type `Int -> Int`. See
the changes to the user manual for details.

This patch addresses tickets #10619, #5296, #10589.

This patch fulfils the request in Trac #11067, #10318, and #10592,
by lifting the conservative restrictions on superclass constraints.

These restrictions are there (and have been since Haskell was born) to
ensure that the transitive superclasses of a class constraint is a finite
set.  However (a) this restriction is conservative, and can be annoying
when there really is no recursion, and (b) sometimes genuinely recursive
superclasses are useful (see the tickets).

Dimitrios and I worked out that there is actually a relatively simple way
to do the job. It’s described in some detail in

   Note [The superclass story] in TcCanonical
   Note [Expanding superclasses] in TcType

In brief, the idea is to expand superclasses only finitely, but to
iterate (using a loop that already existed) if there are more
superclasses to explore.

Other small things

- I improved grouping of error messages a bit in TcErrors

- I re-centred the haddock.compiler test, which was at 9.8%
  above the norm, and which this patch pushed slightly over

This implements the ideas originally put forward in
"System FC with Explicit Kind Equality" (ICFP'13).

There are several noteworthy changes with this patch:
 * We now have casts in types. These change the kind
   of a type. See new constructor `CastTy`.

 * All types and all constructors can be promoted.
   This includes GADT constructors. GADT pattern matches
   take place in type family equations. In Core,
   types can now be applied to coercions via the
   `CoercionTy` constructor.

 * Coercions can now be heterogeneous, relating types
   of different kinds. A coercion proving `t1 :: k1 ~ t2 :: k2`
   proves both that `t1` and `t2` are the same and also that
   `k1` and `k2` are the same.

 * The `Coercion` type has been significantly enhanced.
   The documentation in `docs/core-spec/core-spec.pdf` reflects
   the new reality.

 * The type of `*` is now `*`. No more `BOX`.

 * Users can write explicit kind variables in their code,
   anywhere they can write type variables. For backward compatibility,
   automatic inference of kind-variable binding is still permitted.

 * The new extension `TypeInType` turns on the new user-facing
   features.

 * Type families and synonyms are now promoted to kinds. This causes
   trouble with parsing `*`, leading to the somewhat awkward new
   `HsAppsTy` constructor for `HsType`. This is dispatched with in
   the renamer, where the kind `*` can be told apart from a
   type-level multiplication operator. Without `-XTypeInType` the
   old behavior persists. With `-XTypeInType`, you need to import
   `Data.Kind` to get `*`, also known as `Type`.

 * The kind-checking algorithms in TcHsType have been significantly
   rewritten to allow for enhanced kinds.

 * The new features are still quite experimental and may be in flux.

 * TODO: Several open tickets: #11195, #11196, #11197, #11198, #11203.

 * TODO: Update user manual.

Tickets addressed: #9017, #9173, #7961, #10524, #8566, #11142.
Updates Haddock submodule.

This puts the "Relevant bindings" section at the end.

It uses a TcErrors.Report Monoid to divide messages by importance and
then mappends them together.  This is not the most efficient way since
there are various intermediate Reports and list appends, but it probably
doesn't matter since error messages shouldn't get that large, and are
usually prepended.  In practice, everything is `important` except
`relevantBindings`, which is `supplementary`.

ErrMsg's errMsgShortDoc and errMsgExtraInfo were extracted into ErrDoc,
which has important, context, and suppelementary fields.  Each of those
three sections is marked with a bullet character, '•' on unicode
terminals and '*' on ascii terminals.  Since this breaks tons of tests,
I also modified testlib.normalise_errmsg to strip out '•'s.

--- Additional notes:

To avoid prepending * to an empty doc, I needed to filter empty docs.
This seemed less error-prone than trying to modify everyone who produces
SDoc to instead produce Maybe SDoc.  So I added `Outputable.isEmpty`.
Unfortunately it needs a DynFlags, which is kind of bogus, but otherwise
I think I'd need another Empty case for SDoc, and then it couldn't be a
newtype any more.

ErrMsg's errMsgShortString is only used by the Show instance, which is
in turn only used by Show HscTypes.SourceError, which is in turn only
needed for the Exception instance.  So it's probably possible to get rid
of errMsgShortString, but that would a be an unrelated cleanup.

Fixes #11014.

Test Plan: see above

Reviewers: austin, simonpj, thomie, bgamari

Reviewed By: thomie, bgamari

Subscribers: simonpj, nomeata, thomie

Differential Revision: https://phabricator.haskell.org/D1427

GHC Trac Issues: #11014

I just didn't think it was buying enough for all the cruft it caused.
We can put some back if people start complaining about poor error
messages. I forget quite how I tripped over this but I got sucked in.

* Lots of tidying up in TcErrors

* Rename pprArisingAt to pprCtLoc, by analogy with pprCtOrigin

* Remove CoercibleOrigin data constructor from CtOrigin

* Make relevantBindings return a Ct with a zonked
  and tidied CtOrigin

* Add to TcRnTypes
      ctOrigin   :: Ct -> CtOrigin
      ctEvOrigin :: CtEvidence -> CtOrigin
      setCtLoc   :: Ct -> CtLoc -> Ct

I wasn't very happy with my fix to Trac #10009. This is much better.

The main idea is that the inert set now contains a "model", which
embodies *all* the (nominal) equalities that we know about, with
a view to exposing unifications.  This requires a lot fewer iterations
of the solver than before.

There are extensive comments in
 TcSMonad:  Note [inert_model: the inert model]
            Note [Adding an inert canonical constraint the InertCans]

The big changes are

  * New inert_model field in InertCans

  * Functions addInertEq, addInertCan deal with adding a
    constraint, maintaining the model

  * A nice improvement is that unification variables can
    unify with fmvs, so that from, say   alpha ~ fmv
    we get              alpha := fmv
    See Note [Orientation of equalities with fmvs] in TcFlatten
    It's still not perfect, as the Note explains

New flag -fconstraint-solver-iterations=n, allows us to control
the number of constraint solver iterations, and in particular
will flag up when it's more than a small number.

Performance is generally slightly better:
T5837 is a lot better for some reason.

The main point is described in Note [Solve order for RULES].
I'm not sure if the potential bug described there could actually
happen, but I bet it could.  Anyway, this patch explicitly solves
LHS constraints and *then* RHS constraints (see the Note).

I also moved simplifyRule from TcSimplify (a large module) to
TcRules (a small one), which brings related code together.
It did mean I had to export runTcS from TcSimplify, but I think
that's a price worth paying.

The main change is in TypeRep.pprTheta, so we print
       Eq a
for a singleton, but
      (Eq a, Show a)
for multiple constraints.

There are lots of trivial knock-on changes to error messages

Trac #9872 showed the importance of processing goals in depth-first, so that
we do not build up a huge pool of suspended function calls, waiting for their
children to fire.  There is a detailed explanation in
     Note [The flattening work list]
in TcFlatten

The effect for Trac #9872 (slow1.hs) is dramatic.  We go from too long
to wait down to 28Gbyte allocation.  GHC 7.8.3 did 116Gbyte allocation!

This matches GCC's choice of Unicode quotation marks (i.e. U+2018 and U+2019)
and therefore looks more familiar on the console. This addresses #2507.
Signed-off-by: Herbert Valerio Riedel <hvr@gnu.org>

Almost all are re-orderings of relevant-binding output

       Relevant bindings include
  +      m :: Map (a, b) elt (bound at T3169.hs:12:17)
  +      b :: b (bound at T3169.hs:12:13)
         lookup :: (a, b) -> Map (a, b) elt -> Maybe elt
           (bound at T3169.hs:12:3)
  -      b :: b (bound at T3169.hs:12:13)
  -      m :: Map (a, b) elt (bound at T3169.hs:12:17)

Notably
 * Showing relevant bindings
 * Not suggesting add instance (Num T); see Trac #7222