1. 25 Jul, 2018 1 commit
    • Simon Peyton Jones's avatar
      Fix and document cloneWC · 857ef25e
      Simon Peyton Jones authored
      The cloneWC, cloneWanted, cloneImplication family are used by
        * TcHoleErrors
        * TcRule
      to clone the /bindings/ in a constraint, so that solving the
      constraint will not add bindings to the program. The idea is only
      to affect unifications.
      But I had it wrong -- I failed to clone the EvBindsVar of an
      implication.  That gave an assert failure, I think, as well as
      useless dead code.
      The fix is easy.  I'm not adding a test case.
      In the type 'TcEvidence.EvBindsVar', I also renamed the
      'NoEvBindsVar' constructor to 'CoEvBindsVar'.  It's not that we
      have /no/ evidence bindings, just that we can only have coercion
      bindings, done via HoleDest.
  2. 10 Jul, 2018 1 commit
    • Ningning Xie's avatar
      Refactor coercion rule · 55a3f855
      Ningning Xie authored
      The patch is an attempt on #15192.
      It defines a new coercion rule
       | GRefl Role Type MCoercion
      which correspondes to the typing rule
           t1 : k1
        GRefl r t1 MRefl: t1 ~r t1
           t1 : k1       co :: k1 ~ k2
        GRefl r t1 (MCo co) : t1 ~r t1 |> co
      MCoercion wraps a coercion, which might be reflexive (MRefl)
      or not (MCo co). To know more about MCoercion see #14975.
      We keep Refl ty as a special case for nominal reflexive coercions,
      naemly, Refl ty :: ty ~n ty.
      This commit is meant to be a general performance improvement,
      but there are a few regressions. See #15192, comment:13 for
      more information.
      Test Plan: ./validate
      Reviewers: bgamari, goldfire, simonpj
      Subscribers: rwbarton, thomie, carter
      GHC Trac Issues: #15192
      Differential Revision: https://phabricator.haskell.org/D4747
  3. 04 Jun, 2018 1 commit
    • Simon Peyton Jones's avatar
      Implement QuantifiedConstraints · 7df58960
      Simon Peyton Jones authored
      We have wanted quantified constraints for ages and, as I hoped,
      they proved remarkably simple to implement.   All the machinery was
      already in place.
      The main ticket is Trac #2893, but also relevant are
        #9123 (especially!  higher kinded roles)
      The wiki page is
      which in turn contains a link to the GHC Proposal where the change
      is specified.
      Here is the relevant Note:
      Note [Quantified constraints]
      The -XQuantifiedConstraints extension allows type-class contexts like
        data Rose f x = Rose x (f (Rose f x))
        instance (Eq a, forall b. Eq b => Eq (f b))
              => Eq (Rose f a)  where
          (Rose x1 rs1) == (Rose x2 rs2) = x1==x2 && rs1 >= rs2
      Note the (forall b. Eq b => Eq (f b)) in the instance contexts.
      This quantified constraint is needed to solve the
       [W] (Eq (f (Rose f x)))
      constraint which arises form the (==) definition.
      Here are the moving parts
        * Language extension {-# LANGUAGE QuantifiedConstraints #-}
          and add it to ghc-boot-th:GHC.LanguageExtensions.Type.Extension
        * A new form of evidence, EvDFun, that is used to discharge
          such wanted constraints
        * checkValidType gets some changes to accept forall-constraints
          only in the right places.
        * Type.PredTree gets a new constructor ForAllPred, and
          and classifyPredType analyses a PredType to decompose
          the new forall-constraints
        * Define a type TcRnTypes.QCInst, which holds a given
          quantified constraint in the inert set
        * TcSMonad.InertCans gets an extra field, inert_insts :: [QCInst],
          which holds all the Given forall-constraints.  In effect,
          such Given constraints are like local instance decls.
        * When trying to solve a class constraint, via
          TcInteract.matchInstEnv, use the InstEnv from inert_insts
          so that we include the local Given forall-constraints
          in the lookup.  (See TcSMonad.getInstEnvs.)
        * topReactionsStage calls doTopReactOther for CIrredCan and
          CTyEqCan, so they can try to react with any given
          quantified constraints (TcInteract.matchLocalInst)
        * TcCanonical.canForAll deals with solving a
          forall-constraint.  See
             Note [Solving a Wanted forall-constraint]
             Note [Solving a Wanted forall-constraint]
        * We augment the kick-out code to kick out an inert
          forall constraint if it can be rewritten by a new
          type equality; see TcSMonad.kick_out_rewritable
      Some other related refactoring
      * Move SCC on evidence bindings to post-desugaring, which fixed
        #14735, and is generally nicer anyway because we can use
        existing CoreSyn free-var functions.  (Quantified constraints
        made the free-vars of an ev-term a bit more complicated.)
      * In LookupInstResult, replace GenInst with OneInst and NotSure,
        using the latter for multiple matches and/or one or more
  4. 21 May, 2018 1 commit
    • Simon Peyton Jones's avatar
      Do better sharing in the short-cut solver · f2ce86c2
      Simon Peyton Jones authored
      Trac #15164 showed that it sometimes really matters to share
      sub-proofs when solving constraints.  Without it, we can get
      exponentialy bad behaviour.
      Fortunately, it's easily solved.
      Note [Shortcut try_solve_from_instance] explains.
      I did some minor assocaited refactoring.
  5. 18 May, 2018 1 commit
    • Simon Peyton Jones's avatar
      Orient TyVar/TyVar equalities with deepest on the left · 2bbdd00c
      Simon Peyton Jones authored
      Trac #15009 showed that, for Given TyVar/TyVar equalities, we really
      want to orient them with the deepest-bound skolem on the left. As it
      happens, we also want to do the same for Wanteds, but for a different
      reason (more likely to be touchable).  Either way, deepest wins:
      see TcUnify Note [Deeper level on the left].
      This observation led me to some significant changes:
      * A SkolemTv already had a TcLevel, but the level wasn't really being
        used.   Now it is!
      * I updated added invariant (SkolInf) to TcType
        Note [TcLevel and untouchable type variables], documenting that
        the level number of all the ic_skols should be the same as the
        ic_tclvl of the implication
      * FlatSkolTvs and FlatMetaTvs previously had a dummy level-number of
        zero, which messed the scheme up.   Now they get a level number the
        same way as all other TcTyVars, instead of being a special case.
      * To make sure that FlatSkolTvs and FlatMetaTvs are untouchable (which
        was previously done via their magic zero level) isTouchableMetaTyVar
        just tests for those two cases.
      * TcUnify.swapOverTyVars is the crucial orientation function; see the
        new Note [TyVar/TyVar orientation].  I completely rewrote this function,
        and it's now much much easier to understand.
      I ended up doing some related refactoring, of course
      * I noticed that tcImplicitTKBndrsX and tcExplicitTKBndrsX were doing
        a lot of useless work in the case where there are no skolems; I
        added a fast-patch
      * Elminate the un-used tcExplicitTKBndrsSig; and thereby get rid of
        the higher-order parameter to tcExpliciTKBndrsX.
      * Replace TcHsType.emitTvImplication with TcUnify.checkTvConstraints,
        by analogy with TcUnify.checkConstraints.
      * Inline TcUnify.buildImplication into its only call-site in
      * TcS.buildImplication becomes TcS.CheckConstraintsTcS, with a
        simpler API
      * Now that we have NoEvBindsVar we have no need of termEvidenceAllowed;
        nuke the latter, adding Note [No evidence bindings] to TcEvidence.
  6. 20 Apr, 2018 1 commit
    • Tobias Dammers's avatar
      Caching coercion roles in NthCo and coercionKindsRole refactoring · 2fbe0b51
      Tobias Dammers authored
      While addressing nonlinear behavior related to coercion roles,
      particularly `NthCo`, we noticed that coercion roles are recalculated
      often even though they should be readily at hand already in most cases.
      This patch adds a `Role` to the `NthCo` constructor so that we can cache
      them rather than having to recalculate them on the fly.
      https://ghc.haskell.org/trac/ghc/ticket/11735#comment:23 explains the
      Performance improvement over GHC HEAD, when compiling Grammar.hs (see below):
      GHC 8.2.1:
      ghc Grammar.hs  176.27s user 0.23s system 99% cpu 2:56.81 total
      before patch (but with other optimizations applied):
      ghc Grammar.hs -fforce-recomp  175.77s user 0.19s system 100% cpu 2:55.78 total
      ../../ghc/inplace/bin/ghc-stage2 Grammar.hs  10.32s user 0.17s system 98% cpu 10.678 total
      Introduces the following regressions:
      - perf/compiler/parsing001 (possibly false positive)
      - perf/compiler/T9872
      - perf/compiler/haddock.base
      Reviewers: goldfire, bgamari, simonpj
      Reviewed By: simonpj
      Subscribers: rwbarton, thomie, carter
      GHC Trac Issues: #11735
      Differential Revision: https://phabricator.haskell.org/D4394
  7. 01 Apr, 2018 1 commit
    • Richard Eisenberg's avatar
      Track type variable scope more carefully. · faec8d35
      Richard Eisenberg authored
      The main job of this commit is to track more accurately the scope
      of tyvars introduced by user-written foralls. For example, it would
      be to have something like this:
        forall a. Int -> (forall k (b :: k). Proxy '[a, b]) -> Bool
      In that type, a's kind must be k, but k isn't in scope. We had a
      terrible way of doing this before (not worth repeating or describing
      here, but see the old tcImplicitTKBndrs and friends), but now
      we have a principled approach: make an Implication when kind-checking
      a forall. Doing so then hooks into the existing machinery for
      preventing skolem-escape, performing floating, etc. This also means
      that we bump the TcLevel whenever going into a forall.
      The new behavior is done in TcHsType.scopeTyVars, but see also
      TcHsType.tc{Im,Ex}plicitTKBndrs, which have undergone significant
      rewriting. There are several Notes near there to guide you. Of
      particular interest there is that Implication constraints can now
      have skolems that are out of order; this situation is reported in
      A major consequence of this is a slightly tweaked process for type-
      checking type declarations. The new Note [Use SigTvs in kind-checking
      pass] in TcTyClsDecls lays it out.
      The error message for dependent/should_fail/TypeSkolEscape has become
      noticeably worse. However, this is because the code in TcErrors goes to
      some length to preserve pre-8.0 error messages for kind errors. It's time
      to rip off that plaster and get rid of much of the kind-error-specific
      error messages. I tried this, and doing so led to a lovely error message
      for TypeSkolEscape. So: I'm accepting the error message quality regression
      for now, but will open up a new ticket to fix it, along with a larger
      error-message improvement I've been pondering. This applies also to
      dependent/should_fail/{BadTelescope2,T14066,T14066e}, polykinds/T11142.
      Other minor changes:
       - isUnliftedTypeKind didn't look for tuples and sums. It does now.
       - check_type used check_arg_type on both sides of an AppTy. But the left
         side of an AppTy isn't an arg, and this was causing a bad error message.
         I've changed it to use check_type on the left-hand side.
       - Some refactoring around when we print (TYPE blah) in error messages.
         The changes decrease the times when we do so, to good effect.
         Of course, this is still all controlled by
      Fixes #14066 #14749
      Test cases: dependent/should_compile/{T14066a,T14749},
  8. 07 Feb, 2018 1 commit
    • Simon Peyton Jones's avatar
      Fix solveOneFromTheOther for RecursiveSuperclasses · 65069806
      Simon Peyton Jones authored
      This patch fixes the redundant superclass expansion
      in Trac #14774.
      The main change is to fix TcInterac.solveOneFromTheOther, so
      that it does not prefer a work-item with a binding if that binding
      transitively depends on the inert item we are comparing it with.
      Explained in Note [Replacement vs keeping] in TcInert, esp
      item (c) of the "Constraints coming from the same level" part.
      To make this work I refactored out a new function
      TcEvidence.findNeededEvVars, which was previously buried
      inside TcSimplify.neededEvVars.
      I added quite a few more comments and signposts about superclass
  9. 26 Jan, 2018 1 commit
    • Joachim Breitner's avatar
      Turn EvTerm (almost) into CoreExpr (#14691) · 0e022e56
      Joachim Breitner authored
      Ideally, I'd like to do
          type EvTerm = CoreExpr
      and the type checker builds the evidence terms as it goes. This failed,
      becuase the evidence for `Typeable` refers to local identifiers that are
      added *after* the typechecker solves constraints. Therefore, `EvTerm`
      stays a data type with two constructors: `EvExpr` for `CoreExpr`
      evidence, and `EvTypeable` for the others.
      Delted `Note [Memoising typeOf]`, its reference (and presumably
      relevance) was removed in 8fa4bf9a.
      Differential Revision: https://phabricator.haskell.org/D4341
  10. 04 Jan, 2018 1 commit
    • Simon Peyton Jones's avatar
      Drop dead Given bindings in setImplicationStatus · 954cbc7c
      Simon Peyton Jones authored
      Trac #13032 pointed out that we sometimes generate unused
      bindings for Givens, and (worse still) we can't always discard
      them later (we don't drop a case binding unless we can prove
      that the scrutinee is non-bottom.
      It looks as if this may be a major reason for the performace
      problems in #14338 (see comment:29).
      This patch fixes the problem at source, by pruning away all the
      dead Givens.  See Note [Delete dead Given evidence bindings]
      Remarkably, compiler allocation falls by 23% in
      I have not confirmed whether this change actualy helps with
  11. 19 Sep, 2017 2 commits
    • Herbert Valerio Riedel's avatar
      compiler: introduce custom "GhcPrelude" Prelude · f63bc730
      Herbert Valerio Riedel authored
      This switches the compiler/ component to get compiled with
      -XNoImplicitPrelude and a `import GhcPrelude` is inserted in all
      This is motivated by the upcoming "Prelude" re-export of
      `Semigroup((<>))` which would cause lots of name clashes in every
      modulewhich imports also `Outputable`
      Reviewers: austin, goldfire, bgamari, alanz, simonmar
      Reviewed By: bgamari
      Subscribers: goldfire, rwbarton, thomie, mpickering, bgamari
      Differential Revision: https://phabricator.haskell.org/D3989
    • Simon Peyton Jones's avatar
      Fix unused-given-constraint bug · 1db0f4a4
      Simon Peyton Jones authored
      This bug was shown up by Trac #14237.  It turned out
      to be an outright error in TcSimplify.neededEvVars,
      easily fixed.
      I improved the comments.
  12. 27 Jul, 2017 1 commit
    • Richard Eisenberg's avatar
      Improve error messages around kind mismatches. · 8e15e3d3
      Richard Eisenberg authored
      Previously, when canonicalizing (or unifying, in uType) a
      heterogeneous equality, we emitted a kind equality and used the
      resulting coercion to cast one side of the heterogeneous equality.
      While sound, this led to terrible error messages. (See the bugs
      listed below.) The problem is that using the coercion built from
      the emitted kind equality is a bit like a wanted rewriting a wanted.
      The solution is to keep heterogeneous equalities as irreducible.
      See Note [Equalities with incompatible kinds] in TcCanonical.
      This commit also removes a highly suspicious switch to FM_SubstOnly
      when flattening in the kinds of a type variable. I have no idea
      why this was there, other than as a holdover from pre-TypeInType.
      I've not left a Note because there is simply no reason I can conceive
      of that the FM_SubstOnly should be there.
      One challenge with this patch is that the emitted derived equalities
      might get emitted several times: when a heterogeneous equality is
      in an implication and then gets floated out from the implication,
      the Derived is present both in and out of the implication. This
      causes a duplicate error message. (Test case:
      typecheck/should_fail/T7368) Solution: track the provenance of
      Derived constraints and refuse to float out a constraint that has
      an insoluble Derived.
      Lastly, this labels one test (dependent/should_fail/RAE_T32a)
      as expect_broken, because the problem is really #12919. The
      different handling of constraints in this patch exposes the error.
      This fixes bugs #11198, #12373, #13530, and #13610.
      test cases:
  13. 05 Apr, 2017 1 commit
  14. 01 Mar, 2017 1 commit
    • David Feuer's avatar
      Upgrade UniqSet to a newtype · cbe569a5
      David Feuer authored
      The fundamental problem with `type UniqSet = UniqFM` is that `UniqSet`
      has a key invariant `UniqFM` does not. For example, `fmap` over
      `UniqSet` will generally produce nonsense.
      * Upgrade `UniqSet` from a type synonym to a newtype.
      * Remove unused and shady `extendVarSet_C` and `addOneToUniqSet_C`.
      * Use cached unique in `tyConsOfType` by replacing
        `unitNameEnv (tyConName tc) tc` with `unitUniqSet tc`.
      Reviewers: austin, hvr, goldfire, simonmar, niteria, bgamari
      Reviewed By: niteria
      Subscribers: thomie
      Differential Revision: https://phabricator.haskell.org/D3146
  15. 18 Feb, 2017 1 commit
    • Ben Gamari's avatar
      Type-indexed Typeable · 8fa4bf9a
      Ben Gamari authored
      This at long last realizes the ideas for type-indexed Typeable discussed in A
      Reflection on Types (#11011). The general sketch of the project is described on
      the Wiki (Typeable/BenGamari). The general idea is that we are adding a type
      index to `TypeRep`,
          data TypeRep (a :: k)
      This index allows the typechecker to reason about the type represented by the `TypeRep`.
      This index representation mechanism is exposed as `Type.Reflection`, which also provides
      a number of patterns for inspecting `TypeRep`s,
      pattern TRFun :: forall k (fun :: k). ()
                    => forall (r1 :: RuntimeRep) (r2 :: RuntimeRep)
                              (arg :: TYPE r1) (res :: TYPE r2).
                       (k ~ Type, fun ~~ (arg -> res))
                    => TypeRep arg
                    -> TypeRep res
                    -> TypeRep fun
      pattern TRApp :: forall k2 (t :: k2). ()
                    => forall k1 (a :: k1 -> k2) (b :: k1). (t ~ a b)
                    => TypeRep a -> TypeRep b -> TypeRep t
      -- | Pattern match on a type constructor.
      pattern TRCon :: forall k (a :: k). TyCon -> TypeRep a
      -- | Pattern match on a type constructor including its instantiated kind
      -- variables.
      pattern TRCon' :: forall k (a :: k). TyCon -> [SomeTypeRep] -> TypeRep a
      In addition, we give the user access to the kind of a `TypeRep` (#10343),
          typeRepKind :: TypeRep (a :: k) -> TypeRep k
      Moreover, all of this plays nicely with 8.2's levity polymorphism, including the
      newly levity polymorphic (->) type constructor.
      Library changes
      The primary change here is the introduction of a Type.Reflection module to base.
      This module provides access to the new type-indexed TypeRep introduced in this
      patch. We also continue to provide the unindexed Data.Typeable interface, which
      is simply a type synonym for the existentially quantified SomeTypeRep,
          data SomeTypeRep where SomeTypeRep :: TypeRep a -> SomeTypeRep
      Naturally, this change also touched Data.Dynamic, which can now export the
      Dynamic data constructor. Moreover, I removed a blanket reexport of
      Data.Typeable from Data.Dynamic (which itself doesn't even import Data.Typeable
      We also add a kind heterogeneous type equality type, (:~~:), to
      The implementation strategy is described in Note [Grand plan for Typeable] in
      TcTypeable. None of it was difficult, but it did exercise a number of parts of
      the new levity polymorphism story which had not yet been exercised, which took
      some sorting out.
      The rough idea is that we augment the TyCon produced for each type constructor
      with information about the constructor's kind (which we call a KindRep). This
      allows us to reconstruct the monomorphic result kind of an particular
      instantiation of a type constructor given its kind arguments.
      Unfortunately all of this takes a fair amount of work to generate and send
      through the compilation pipeline. In particular, the KindReps can unfortunately
      get quite large. Moreover, the simplifier will float out various pieces of them,
      resulting in numerous top-level bindings. Consequently we mark the KindRep
      bindings as noinline, ensuring that the float-outs don't make it into the
      interface file. This is important since there is generally little benefit to
      inlining KindReps and they would otherwise strongly affect compiler performance.
      Initially I was hoping to also clear up the remaining holes in Typeable's
      coverage by adding support for both unboxed tuples (#12409) and unboxed sums
      (#13276). While the former was fairly straightforward, the latter ended up being
      quite difficult: while the implementation can support them easily, enabling this
      support causes thousands of Typeable bindings to be emitted to the GHC.Types as
      each arity-N sum tycon brings with it N promoted datacons, each of which has a
      KindRep whose size which itself scales with N. Doing this was simply too
      expensive to be practical; consequently I've disabled support for the time
      Even after disabling sums this change regresses compiler performance far more
      than I would like. In particular there are several testcases in the testsuite
      which consist mostly of types which regress by over 30% in compiler allocations.
      These include (considering the "bytes allocated" metric),
       * T1969:  +10%
       * T10858: +23%
       * T3294:  +19%
       * T5631:  +41%
       * T6048:  +23%
       * T9675:  +20%
       * T9872a: +5.2%
       * T9872d: +12%
       * T9233:  +10%
       * T10370: +34%
       * T12425: +30%
       * T12234: +16%
       * 13035:  +17%
       * T4029:  +6.1%
      I've spent quite some time chasing down the source of this regression and while
      I was able to make som improvements, I think this approach of generating
      Typeable bindings at time of type definition is doomed to give us unnecessarily
      large compile-time overhead.
      In the future I think we should consider moving some of all of the Typeable
      binding generation logic back to the solver (where it was prior to
      91c6b1f5). I've opened #13261 documenting this
  16. 14 Feb, 2017 1 commit
    • Adam Gundry's avatar
      Implement HasField constraint solving and modify OverloadedLabels · da493897
      Adam Gundry authored
      This implements automatic constraint solving for the new HasField class
      and modifies the existing OverloadedLabels extension, as described in
      the GHC proposal
      (https://github.com/ghc-proposals/ghc-proposals/pull/6). Per the current
      form of the proposal, it does *not* currently introduce a separate
      `OverloadedRecordFields` extension.
      This replaces D1687.
      The users guide documentation still needs to be written, but I'll do
      that after the implementation is merged, in case there are further
      design changes.
      Test Plan: new and modified tests in overloadedrecflds
      Reviewers: simonpj, goldfire, dfeuer, bgamari, austin, hvr
      Reviewed By: bgamari
      Subscribers: maninalift, dfeuer, ysangkok, thomie, mpickering
      Differential Revision: https://phabricator.haskell.org/D2708
  17. 09 Feb, 2017 1 commit
  18. 19 Jan, 2017 1 commit
    • Richard Eisenberg's avatar
      Update levity polymorphism · e7985ed2
      Richard Eisenberg authored
      This commit implements the proposal in
      https://github.com/ghc-proposals/ghc-proposals/pull/29 and
      Here are some of the pieces of that proposal:
      * Some of RuntimeRep's constructors have been shortened.
      * TupleRep and SumRep are now parameterized over a list of RuntimeReps.
      * This
      means that two types with the same kind surely have the same
      Previously, all unboxed tuples had the same kind, and thus the fact
      above was
      * RepType.typePrimRep and friends now return a *list* of PrimReps. These
      functions can now work successfully on unboxed tuples. This change is
      necessary because we allow abstraction over unboxed tuple types and so
      always handle unboxed tuples specially as we did before.
      * We sometimes have to create an Id from a PrimRep. I thus split PtrRep
      * into
      LiftedRep and UnliftedRep, so that the created Ids have the right
      * The RepType.RepType type was removed, as it didn't seem to help with
      * much.
      * The RepType.repType function is also removed, in favor of typePrimRep.
      * I have waffled a good deal on whether or not to keep VoidRep in
      TyCon.PrimRep. In the end, I decided to keep it there. PrimRep is *not*
      represented in RuntimeRep, and typePrimRep will never return a list
      VoidRep. But it's handy to have in, e.g., ByteCodeGen and friends. I can
      imagine another design choice where we have a PrimRepV type that is
      with an extra constructor. That seemed to be a heavier design, though,
      and I'm
      not sure what the benefit would be.
      * The last, unused vestiges of # (unliftedTypeKind) have been removed.
      * There were several pretty-printing bugs that this change exposed;
      * these are fixed.
      * We previously checked for levity polymorphism in the types of binders.
      * But we
      also must exclude levity polymorphism in function arguments. This is
      hard to check
      for, requiring a good deal of care in the desugarer. See Note [Levity
      checking] in DsMonad.
      * In order to efficiently check for levity polymorphism in functions, it
      * was necessary
      to add a new bit of IdInfo. See Note [Levity info] in IdInfo.
      * It is now safe for unlifted types to be unsaturated in Core. Core Lint
      * is updated
      * We can only know strictness after zonking, so several checks around
      * strictness
      in the type-checker (checkStrictBinds, the check for unlifted variables
      under a ~
      pattern) have been moved to the desugarer.
      * Along the way, I improved the treatment of unlifted vs. banged
      * bindings. See
      Note [Strict binds checks] in DsBinds and #13075.
      * Now that we print type-checked source, we must be careful to print
      * ConLikes correctly.
      This is facilitated by a new HsConLikeOut constructor to HsExpr.
      Particularly troublesome
      are unlifted pattern synonyms that get an extra void# argument.
      * Includes a submodule update for haddock, getting rid of #.
      * New testcases:
      * Fixed tickets:
      * This also adds a test case for #13105. This test case is
      * "compile_fail" and
      succeeds, because I want the testsuite to monitor the error message.
      When #13105 is fixed, the test case will compile cleanly.
  19. 21 Dec, 2016 1 commit
    • Simon Peyton Jones's avatar
      Fix 'SPECIALISE instance' · 1a4c04b1
      Simon Peyton Jones authored
      Trac #12944 showed that the DsBinds code that implemented a
      SPECIALISE pragma was inadequate if the constraints solving
      added let-bindings for dictionaries.  The result was that
      we ended up with an unbound dictionary in a DFunUnfolding -- and
      Lint didn't even check for that!
      Fixing this was not entirely straightforward
      * In DsBinds.dsSpec we use a new function
        to pick off the lambda binders from the HsWapper
      * dsWrapper now returns a (CoreExpr -> CoreExpr) function
      * CoreUnfold.specUnfolding now takes a (CoreExpr -> CoreExpr)
        function it can use to specialise the unfolding.
      On the whole the code is simpler than before.
  20. 27 Oct, 2016 1 commit
    • Simon Peyton Jones's avatar
      Collect coercion variables, not type variables · f9308c2a
      Simon Peyton Jones authored
      ...when tracking which constraints are used.
      Previously we were gathering type variables too, which meant that the
      ics_need field was (stupidly) non-empty, which meant that we kept hold
      of solved implications for no purpose.  Better just to get rid of them,
      which setImplicationStatus is all ste up to to do.
      No change in behaviour; a bit more efficient.
  21. 21 Oct, 2016 1 commit
    • Simon Peyton Jones's avatar
      A collection of type-inference refactorings. · 3f5673f3
      Simon Peyton Jones authored
      This patch does a raft of useful tidy-ups in the type checker.
      I've been meaning to do this for some time, and finally made
      time to do it en route to ICFP.
      1. Modify TcType.ExpType to make a distinct data type,
         InferResult for the Infer case, and consequential
      2. Define a new function TcUnify.fillInferResult, to fill in
         an InferResult. It uses TcMType.promoteTcType to promote
         the type to the level of the InferResult.
         See TcMType Note [Promoting a type]
         This refactoring is in preparation for an improvement
         to typechecking pattern bindings, coming next.
         I flirted with an elaborate scheme to give better
         higher rank inference, but it was just too complicated.
         See TcMType Note [Promotion and higher rank types]
      3. Add to InferResult a new field ir_inst :: Bool to say
         whether or not the type used to fill in the
         InferResult should be deeply instantiated.  See
         TcUnify Note [Deep instantiation of InferResult].
      4. Add a TcLevel to SkolemTvs. This will be useful generally
          - it's a fast way to see if the type
            variable escapes when floating (not used yet)
          - it provides a good consistency check when updating a
            unification variable (TcMType.writeMetaTyVarRef, the
            level_check_ok check)
         I originally had another reason (related to the flirting
         in (2), but I left it in because it seems like a step in
         the right direction.
      5. Reduce and simplify the plethora of uExpType,
         tcSubType and related functions in TcUnify.  It was
         such an opaque mess and it's still not great, but it's
      6. Simplify the uo_expected field of TypeEqOrigin.  Richard
         had generatlised it to a ExpType, but it was almost always
         a Check type.  Now it's back to being a plain TcType which
         is much, much easier.
      7. Improve error messages by refraining from skolemisation when
         it's clear that there's an error: see
         TcUnify Note [Don't skolemise unnecessarily]
      8. Type.isPiTy and isForAllTy seem to be missing a coreView check,
         so I added it
      9. Kill off tcs_used_tcvs.  Its purpose is to track the
         givens used by wanted constraints.  For dictionaries etc
         we do that via the free vars of the /bindings/ in the
         implication constraint ic_binds.  But for coercions we
         just do update-in-place in the type, rather than
         generating a binding.  So we need something analogous to
         bindings, to track what coercions we have added.
         That was the purpose of tcs_used_tcvs.  But it only
         worked for a /single/ iteration, whereas we may have
         multiple iterations of solving an implication.  Look
         at (the old) 'setImplicationStatus'.  If the constraint
         is unsolved, it just drops the used_tvs on the floor.
         If it becomes solved next time round, we'll pick up
         coercions used in that round, but ignore ones used in
         the first round.
         There was an outright bug.  Result = (potentialy) bogus
         unused-constraint errors.  Constructing a case where this
         actually happens seems quite trick so I did not do so.
         Solution: expand EvBindsVar to include the (free vars of
         the) coercions, so that the coercions are tracked in
         essentially the same way as the bindings.
         This turned out to be much simpler.  Less code, more
      10. Make the ic_binds field in an implication have type
            ic_binds :: EvBindsVar
          instead of (as previously)
             ic_binds :: Maybe EvBindsVar
          This is notably simpler, and faster to use -- less
          testing of the Maybe.  But in the occaional situation
          where we don't have anywhere to put the bindings, the
          belt-and-braces error check is lost.  So I put it back
          as an ASSERT in 'setImplicationStatus' (see the use of
      All these changes led to quite bit of error message wibbling
  22. 14 Aug, 2016 1 commit
  23. 23 Jun, 2016 1 commit
    • niteria's avatar
      Provide Uniquable version of SCC · 35d1564c
      niteria authored
      We want to remove the `Ord Unique` instance because there's
      no way to implement it in deterministic way and it's too
      easy to use by accident.
      We sometimes compute SCC for datatypes whose Ord instance
      is implemented in terms of Unique. The Ord constraint on
      SCC is just an artifact of some internal data structures.
      We can have an alternative implementation with a data
      structure that uses Uniquable instead.
      This does exactly that and I'm pleased that I didn't have
      to introduce any duplication to do that.
      Test Plan:
      I looked at performance tests and it's a tiny bit better.
      Reviewers: bgamari, simonmar, ezyang, austin, goldfire
      Subscribers: thomie
      Differential Revision: https://phabricator.haskell.org/D2359
      GHC Trac Issues: #4012
  24. 24 May, 2016 1 commit
    • Ryan Scott's avatar
      Remove 'deriving Typeable' statements · 95dfdceb
      Ryan Scott authored
      Deriving `Typeable` has been a no-op since GHC 7.10, and now that we
      require 7.10+ to build GHC, we can remove all the redundant `deriving Typeable`
      statements in GHC.
      Test Plan: ./validate
      Reviewers: goldfire, austin, hvr, bgamari
      Reviewed By: austin, hvr, bgamari
      Subscribers: thomie
      Differential Revision: https://phabricator.haskell.org/D2260
  25. 11 May, 2016 1 commit
    • niteria's avatar
      Document SCC determinism · 3edbd091
      niteria authored
      I've documented the guarantees that stronglyConnCompFromEdgedVertices
      provides and commented on the call sites to explain why they are
      OK from determinism standpoint. I've changed the functions to
      nonDetUFM versions, so that it's explicit they could introduce
      nondeterminism.  I haven't defined container (VarSet, NameSet)
      specific versions, so that we have less functions to worry about.
      Test Plan: this is mostly just documentation,
      it should have no runtime effect
      Reviewers: bgamari, simonmar, austin, simonpj
      Reviewed By: simonpj
      Subscribers: thomie
      Differential Revision: https://phabricator.haskell.org/D2194
      GHC Trac Issues: #4012
  26. 04 Apr, 2016 1 commit
    • Eric Seidel's avatar
      Don't infer CallStacks · 7407a66d
      Eric Seidel authored
      We originally wanted CallStacks to be opt-in, but dealing with let
      binders complicated things, forcing us to infer CallStacks. It turns
      out that the inference is actually unnecessary though, we can let the
      wanted CallStacks bubble up to the outer context by refusing to
      quantify over them. Eventually they'll be solved from a given CallStack
      or defaulted to the empty CallStack if they reach the top.
      So this patch prevents GHC from quantifying over CallStacks, getting us
      back to the original plan. There's a small ugliness to do with
      PartialTypeSignatures, if the partial theta contains a CallStack
      constraint, we *do* want to quantify over the CallStack; the user asked
      us to!
      Note that this means that
        foo :: _ => CallStack
        foo = getCallStack callStack
      will be an *empty* CallStack, since we won't infer a CallStack for the
      hole in the theta. I think this is the right move though, since we want
      CallStacks to be opt-in. One can always write
        foo :: (HasCallStack, _) => CallStack
        foo = getCallStack callStack
      to get the CallStack and still have GHC infer the rest of the theta.
      Test Plan: ./validate
      Reviewers: goldfire, simonpj, austin, hvr, bgamari
      Reviewed By: simonpj, bgamari
      Subscribers: bitemyapp, thomie
      Projects: #ghc
      Differential Revision: https://phabricator.haskell.org/D1912
      GHC Trac Issues: #11573
  27. 26 Feb, 2016 1 commit
  28. 12 Feb, 2016 1 commit
    • Simon Peyton Jones's avatar
      Improve pretty-printing of HsWrappers · d0846243
      Simon Peyton Jones authored
      Reduces un-neede parens.
      Also -fprint-typechecker-elaboration now makes type applications
      and casts in expressions also appear.  (Previously those were
      confusingly controlled by -fprint-explicit-coercions.)
  29. 01 Feb, 2016 1 commit
    • Eric Seidel's avatar
      Hide the CallStack implicit parameter · 94048f9f
      Eric Seidel authored
      The implicit parameter isn't actually very relevant to the CallStack
      machinery, so we hide the implementation details behind a constraint
      type HasCallStack = (?callStack :: CallStack)
      This has a few benefits:
      1. No need to enable `ImplicitParams` in user code.
      2. No need to remember the `?callStack` naming convention.
      3. Gives us the option to change the implementation details in the
      future with less user-land breakage.
      The revised `CallStack` API is exported from `GHC.Stack` and makes no
      mention of the implicit parameter.
      Test Plan: ./validate
      Reviewers: simonpj, austin, hvr, bgamari
      Reviewed By: simonpj, bgamari
      Subscribers: thomie
      Projects: #ghc
      Differential Revision: https://phabricator.haskell.org/D1818
  30. 27 Jan, 2016 1 commit
    • eir@cis.upenn.edu's avatar
      Refactor the typechecker to use ExpTypes. · 00cbbab3
      eir@cis.upenn.edu authored
      The idea here is described in [wiki:Typechecker]. Briefly,
      this refactor keeps solid track of "synthesis" mode vs
      "checking" in GHC's bidirectional type-checking algorithm.
      When in synthesis mode, the expected type is just an IORef
      to write to.
      In addition, this patch does a significant reworking of
      RebindableSyntax, allowing much more freedom in the types
      of the rebindable operators. For example, we can now have
      `negate :: Int -> Bool` and
      `(>>=) :: m a -> (forall x. a x -> m b) -> m b`. The magic
      is in tcSyntaxOp.
      This addresses tickets #11397, #11452, and #11458.
  31. 18 Jan, 2016 1 commit
    • Jan Stolarek's avatar
      Replace calls to `ptext . sLit` with `text` · b8abd852
      Jan Stolarek authored
      In the past the canonical way for constructing an SDoc string literal was the
      composition `ptext . sLit`.  But for some time now we have function `text` that
      does the same.  Plus it has some rules that optimize its runtime behaviour.
      This patch takes all uses of `ptext . sLit` in the compiler and replaces them
      with calls to `text`.  The main benefits of this patch are clener (shorter) code
      and less dependencies between module, because many modules now do not need to
      import `FastString`.  I don't expect any performance benefits - we mostly use
      SDocs to report errors and it seems there is little to be gained here.
      Test Plan: ./validate
      Reviewers: bgamari, austin, goldfire, hvr, alanz
      Subscribers: goldfire, thomie, mpickering
      Differential Revision: https://phabricator.haskell.org/D1784
  32. 31 Dec, 2015 1 commit
  33. 24 Dec, 2015 1 commit
    • eir@cis.upenn.edu's avatar
      Visible type application · 2db18b81
      eir@cis.upenn.edu authored
      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
      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.
  34. 12 Dec, 2015 1 commit
    • Eric Seidel's avatar
      Rework the Implicit CallStack solver to handle local lets. · 3ec8288a
      Eric Seidel authored
      We can't just solve CallStack constraints indiscriminately when they
      occur in the RHS of a let-binder. The top-level given CallStack (if
      any) will not be in scope, so I've re-worked the CallStack solver as
      1. CallStacks are treated like regular IPs unless one of the following
         two rules apply.
      2. In a function call, we push the call-site onto a NEW wanted
         CallStack, which GHC will solve as a regular IP (either directly from a
         given, or by quantifying over it in a local let).
      3. If, after the constraint solver is done, any wanted CallStacks
         remain, we default them to the empty CallStack. This rule exists mainly
         to clean up after rule 2 in a top-level binder with no given CallStack.
      In rule (2) we have to be careful to emit the new wanted with an
      IPOccOrigin instead of an OccurrenceOf origin, so rule (2) doesn't fire
      again. This is a bit shady but I've updated the Note to explain the
      Test Plan: validate
      Reviewers: simonpj, austin, bgamari, hvr
      Reviewed By: simonpj, bgamari
      Subscribers: thomie
      Differential Revision: https://phabricator.haskell.org/D1422
      GHC Trac Issues: #10845
  35. 11 Dec, 2015 1 commit
    • eir@cis.upenn.edu's avatar
      Add kind equalities to GHC. · 67465497
      eir@cis.upenn.edu authored
      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
       * 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.
  36. 01 Dec, 2015 1 commit
    • Simon Peyton Jones's avatar
      Refactor treatment of wildcards · 1e041b73
      Simon Peyton Jones authored
      This patch began as a modest refactoring of HsType and friends, to
      clarify and tidy up exactly where quantification takes place in types.
      Although initially driven by making the implementation of wildcards more
      tidy (and fixing a number of bugs), I gradually got drawn into a pretty
      big process, which I've been doing on and off for quite a long time.
      There is one compiler performance regression as a result of all
      this, in perf/compiler/T3064.  I still need to look into that.
      * The principal driving change is described in Note [HsType binders]
        in HsType.  Well worth reading!
      * Those data type changes drive almost everything else.  In particular
        we now statically know where
             (a) implicit quantification only (LHsSigType),
                 e.g. in instance declaratios and SPECIALISE signatures
             (b) implicit quantification and wildcards (LHsSigWcType)
                 can appear, e.g. in function type signatures
      * As part of this change, HsForAllTy is (a) simplified (no wildcards)
        and (b) split into HsForAllTy and HsQualTy.  The two contructors
        appear when and only when the correponding user-level construct
        appears.  Again see Note [HsType binders].
        HsExplicitFlag disappears altogether.
      * Other simplifications
           - ExprWithTySig no longer needs an ExprWithTySigOut variant
           - TypeSig no longer needs a PostRn name [name] field
             for wildcards
           - PatSynSig records a LHsSigType rather than the decomposed
           - The mysterious 'GenericSig' is now 'ClassOpSig'
      * Renamed LHsTyVarBndrs to LHsQTyVars
      * There are some uninteresting knock-on changes in Haddock,
        because of the HsSyn changes
      I also did a bunch of loosely-related changes:
      * We already had type synonyms CoercionN/CoercionR for nominal and
        representational coercions.  I've added similar treatment for
        All just type synonyms but jolly useful.
      * I record-ised ForeignImport and ForeignExport
      * I improved the (poor) fix to Trac #10896, by making
        TcTyClsDecls.checkValidTyCl recover from errors, but adding a
        harmless, abstract TyCon to the envt if so.
      * I did some significant refactoring in RnEnv.lookupSubBndrOcc,
        for reasons that I have (embarrassingly) now totally forgotten.
        It had to do with something to do with import and export
      Updates haddock submodule.
  37. 17 Nov, 2015 1 commit
  38. 30 Oct, 2015 2 commits
    • niteria's avatar
      Make type-class dictionary let binds deterministic · a5cb27f3
      niteria authored
      When generating dictionary let binds in dsTcEvBinds we may
      end up generating them in arbitrary order according to Unique order.
      let $dEq = GHC.Classes.$fEqInt in
      let $$dNum = GHC.Num.$fNumInt in ...
      let $dNum = GHC.Num.$fNumInt in
      let $dEq = GHC.Classes.$fEqInt in ...
      The way this change fixes it is by using `UniqDFM` - a type of
      deterministic finite maps of things keyed on `Unique`s. This way when
      you pull out evidence variables corresponding to type-class dictionaries
      they are in deterministic order.
      Currently it's the order of insertion and the way it's implemented is by
      tagging the values with the time of insertion.
      Test Plan:
      I've added a new test case to reproduce the issue.
      Reviewers: ezyang, simonmar, austin, simonpj, bgamari
      Reviewed By: simonmar, simonpj, bgamari
      Subscribers: thomie
      Differential Revision: https://phabricator.haskell.org/D1396
      GHC Trac Issues: #4012
    • Ben Gamari's avatar
      Generate Typeable info at definition sites · 91c6b1f5
      Ben Gamari authored
      This is the second attempt at merging D757.
      This patch implements the idea floated in Trac #9858, namely that we
      should generate type-representation information at the data type
      declaration site, rather than when solving a Typeable constraint.
      However, this turned out quite a bit harder than I expected. I still
      think it's the right thing to do, and it's done now, but it was quite
      a struggle.
      See particularly
       * Note [Grand plan for Typeable] in TcTypeable (which is a new module)
       * Note [The overall promotion story] in DataCon (clarifies existing
      The most painful bit was that to generate Typeable instances (ie
      TyConRepName bindings) for every TyCon is tricky for types in ghc-prim
       * We need to have enough data types around to *define* a TyCon
       * Many of these types are wired-in
      Also, to minimise the code generated for each data type, I wanted to
      generate pure data, not CAFs with unpackCString# stuff floating about.
      Three perf/compiler tests start to allocate quite a bit more. This isn't
      surprising, because they all allocate zillions of data types, with
      practically no other code, esp. T1969
       * T1969:    GHC allocates 19% more
       * T4801:    GHC allocates 13% more
       * T5321FD:  GHC allocates 13% more
       * T9675:    GHC allocates 11% more
       * T783:     GHC allocates 11% more
       * T5642:    GHC allocates 10% more
      I'm treating this as acceptable. The payoff comes in Typeable-heavy
      Remaining to do
       * I think that "TyCon" and "Module" are over-generic names to use for
         the runtime type representations used in GHC.Typeable. Better might
         "TrTyCon" and "TrModule". But I have not yet done this
       * Add more info the the "TyCon" e.g. source location where it was
       * Use the new "Module" type to help with Trac Trac #10068
       * It would be possible to generate TyConRepName (ie Typeable
         instances) selectively rather than all the time. We'd need to persist
         the information in interface files. Lacking a motivating reason I
         not done this, but it would not be difficult.
      As is so often the case, I ended up refactoring more than I intended.
      In particular
       * In TyCon, a type *family* (whether type or data) is repesented by a
           * a algebraic data type (including data/newtype instances) is
             represented by AlgTyCon This wasn't true before; a data family
             was represented as an AlgTyCon. There are some corresponding
             changes in IfaceSyn.
           * Also get rid of the (unhelpfully named) tyConParent.
       * In TyCon define 'Promoted', isomorphic to Maybe, used when things are
         optionally promoted; and use it elsewhere in GHC.
       * Cleanup handling of knownKeyNames
       * Each TyCon, including promoted TyCons, contains its TyConRepName, if
         it has one. This is, in effect, the name of its Typeable instance.
      Updates haddock submodule
      Test Plan: Let Harbormaster validate
      Reviewers: austin, hvr, goldfire
      Subscribers: goldfire, thomie
      Differential Revision: https://phabricator.haskell.org/D1404
      GHC Trac Issues: #9858