1. 18 May, 2018 2 commits
    • Simon Peyton Jones's avatar
      Do not unify representational equalities · ae292c6d
      Simon Peyton Jones authored
      This patch is an easy fix to Trac #15144, which was caused
      by accidentally unifying a representational equality in the
      unflattener.  (The main code in TcInteract was always careful
      not to do so, but I'd missed the test in the unflattener.)
      
      See Note [Do not unify representational equalities]
      in TcInteract
      ae292c6d
    • Simon Peyton Jones's avatar
      Comments only · 797a4623
      Simon Peyton Jones authored
      797a4623
  2. 13 May, 2018 1 commit
  3. 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
      TcErrors.
      
      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
         -fprint-explicit-runtime-reps
      
      Fixes #14066 #14749
      
      Test cases: dependent/should_compile/{T14066a,T14749},
                  dependent/should_fail/T14066{,c,d,e,f,g,h}
      faec8d35
  4. 26 Mar, 2018 1 commit
    • Richard Eisenberg's avatar
      Fix #12919 by making the flattener homegeneous. · e3dbb44f
      Richard Eisenberg authored
      This changes a key invariant of the flattener. Previously,
      flattening a type meant flattening its kind as well. But now,
      flattening is always homogeneous -- that is, the kind of the
      flattened type is the same as the kind of the input type.
      This is achieved by various wizardry in the TcFlatten.flatten_many
      function, as described in Note [flatten_many].
      
      There are several knock-on effects, including some refactoring
      in the canonicalizer to take proper advantage of the flattener's
      changed behavior. In particular, the tyvar case of can_eq_nc' no
      longer needs to take casts into account.
      
      Another effect is that flattening a tyconapp might change it
      into a casted tyconapp. This might happen if the result kind
      of the tycon contains a variable, and that variable changes
      during flattening. Because the flattener is homogeneous, it tacks
      on a cast to keep the tyconapp kind the same. However, this
      is problematic when flattening CFunEqCans, which need to have
      an uncasted tyconapp on the LHS and must remain homogeneous.
      The solution is a more involved canCFunEqCan, described in
      Note [canCFunEqCan].
      
      This patch fixes #13643 (as tested in typecheck/should_compile/T13643)
      and the panic in typecheck/should_compile/T13822 (as reported in #14024).
      Actually, there were two bugs in T13822: the first was just some
      incorrect logic in tryFill (part of the unflattener) -- also fixed
      in this patch -- and the other was the main bug fixed in this ticket.
      
      The changes in this patch exposed a long-standing flaw in OptCoercion,
      in that breaking apart an AppCo sometimes has unexpected effects on
      kinds. See new Note [EtaAppCo] in OptCoercion, which explains the
      problem and fix.
      
      Also here is a reversion of the major change in
      09bf135a, affecting ctEvCoercion.
      It turns out that making the flattener homogeneous changes the
      invariants on the algorithm, making the change in that patch
      no longer necessary.
      
      This patch also fixes:
        #14038 (dependent/should_compile/T14038)
        #13910 (dependent/should_compile/T13910)
        #13938 (dependent/should_compile/T13938)
        #14441 (typecheck/should_compile/T14441)
        #14556 (dependent/should_compile/T14556)
        #14720 (dependent/should_compile/T14720)
        #14749 (typecheck/should_compile/T14749)
      
      Sadly, this patch negatively affects performance of type-family-
      heavy code. The following patch fixes these performance degradations.
      However, the performance fixes are somewhat invasive and so I've
      kept them as a separate patch, labeling this one as [skip ci] so
      that validation doesn't fail on the performance cases.
      e3dbb44f
  5. 08 Feb, 2018 1 commit
    • Simon Peyton Jones's avatar
      Fix isDroppableCt (Trac #14763) · 6edafe3b
      Simon Peyton Jones authored
      When finishing up an implication constraint, it's a bit tricky to
      decide which Derived constraints to retain (for error reporting) and
      which to discard.  I got this wrong in commit
         f20cf982
         (Remove wc_insol from WantedConstraints)
      
      The particular problem in Trac #14763 was that we were reporting as an
      error a fundep-generated constraint
        (ex ~ T)
      where 'ex' is an existentially-bound variable in a pattern match.
      But this isn't really an error at all.
      
      This patch fixes the problem. Indeed, since I had to understand
      this rather tricky code, I took the opportunity to clean it up
      and document better.  See
        isDroppableCt :: Ct -> Bool
      and Note [Dropping derived constraints]
      
      I also removed wl_deriv altogether from the WorkList data type.  It
      was there in the hope of gaining efficiency by not even processing
      lots of derived constraints, but it has turned out that most derived
      constraints (notably equalities) must be processed anyway; see
      Note [Prioritise equalities] in TcSMonad.
      
      The two are coupled because to decide which constraints to put in
      wl_deriv I was using another variant of isDroppableCt.  Now it's much
      simpler -- and perhaps even more efficient too.
      6edafe3b
  6. 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
      expansion.
      65069806
  7. 31 Jan, 2018 1 commit
  8. 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
      0e022e56
  9. 21 Dec, 2017 2 commits
    • Simon Peyton Jones's avatar
      Refactor coercion holes · a492af06
      Simon Peyton Jones authored
      In fixing Trac #14584 I found that it would be /much/ more
      convenient if a "hole" in a coercion (much like a unification
      variable in a type) acutally had a CoVar associated with it
      rather than just a Unique.  Then I can ask what the free variables
      of a coercion is, and get a set of CoVars including those
      as-yet-un-filled in holes.
      
      Once that is done, it makes no sense to stuff coercion holes
      inside UnivCo.  They were there before so we could know the
      kind and role of a "hole" coercion, but once there is a CoVar
      we can get that info from the CoVar.  So I removed HoleProv
      from UnivCoProvenance and added HoleCo to Coercion.
      
      In summary:
      
      * Add HoleCo to Coercion and remove HoleProv from UnivCoProvanance
      
      * Similarly in IfaceCoercion
      
      * Make CoercionHole have a CoVar in it, not a Unique
      
      * Make tyCoVarsOfCo return the free coercion-hole variables
        as well as the ordinary free CoVars.  Similarly, remember
        to zonk the CoVar in a CoercionHole
      
      We could go further, and remove CoercionHole as a distinct type
      altogther, just collapsing it into HoleCo.  But I have not done
      that yet.
      a492af06
    • Simon Peyton Jones's avatar
      Simplify HsPatSynDetails · 584cbd4a
      Simon Peyton Jones authored
      This is a pure refactoring.  Use HsConDetails to implement
      HsPatSynDetails, instead of defining a whole new data type.
      Less code, fewer types, all good.
      584cbd4a
  10. 19 Dec, 2017 1 commit
  11. 08 Nov, 2017 1 commit
    • Simon Peyton Jones's avatar
      Fix another dark corner in the shortcut solver · 30058b0e
      Simon Peyton Jones authored
      The shortcut solver for type classes (Trac #12791) was eagerly
      solving a constaint from an OVERLAPPABLE instance. It happened
      to be the only one in scope, so it was unique, but since it's
      specfically flagged as overlappable it's really a bad idea to
      solve using it, rather than using the Given dictionary.
      
      This led to Trac #14434, a nasty and hard to identify bug.
      30058b0e
  12. 30 Oct, 2017 1 commit
  13. 20 Oct, 2017 1 commit
    • Simon Peyton Jones's avatar
      Improve kick-out in the constraint solver · 3acd6164
      Simon Peyton Jones authored
      This patch was provoked by Trac #14363.  Turned out that we were
      kicking out too many constraints in TcSMonad.kickOutRewritable, and
      that mean that the work-list never became empty: infinite loop!
      
      That in turn made me look harder at the Main Theorem in
      Note [Extending the inert equalities].
      
      Main changes
      
      * Replace TcType.isTyVarExposed by TcType.isTyVarHead.  The
        over-agressive isTyVarExposed is what caused Trac #14363.
        See Note [K3: completeness of solving] in TcSMonad.
      
      * TcType.Make anyRewriteableTyVar role-aware.  In particular,
            a ~R ty
        cannot rewrite
            b ~R f a
        See Note [anyRewriteableTyVar must be role-aware].  That means
        it has to be given a role argument, which forces a little
        refactoring.
      
        I think this change is fixing a bug that hasn't yet been reported.
        The actual reported bug is handled by the previous bullet.  But
        this change is definitely the Right Thing
      
      The main changes are in TcSMonad.kick_out_rewritable, and in TcType
      (isTyVarExposed ---> isTyVarHead).
      
      I did a little unforced refactoring:
      
       * Use the cc_eq_rel field of a CTyEqCan when it is available, rather
         than recomputing it.
      
       * Define eqCanRewrite :: EqRel -> EqRel -> EqRel, and use it, instead
         of duplicating its logic
      3acd6164
  14. 18 Oct, 2017 1 commit
    • Simon Peyton Jones's avatar
      Better solving for representational equalities · 5a66d574
      Simon Peyton Jones authored
      This patch adds a bit of extra solving power for representational
      equality constraints to fix Trac #14333
      
      The main changes:
      
      * Fix a buglet in TcType.isInsolubleOccursCheck which wrongly
        reported a definite occurs-check error for (a ~R# b a)
      
      * Get rid of TcSMonad.emitInsolubles.  It had an ad-hoc duplicate-removal
        piece that is better handled in interactIrred, now that insolubles
        are Irreds.
      
        We need a little care to keep inert_count (which does not include
        insolubles) accurate.
      
      * Refactor TcInteract.solveOneFromTheOther, to return a much simpler
        type.  It was just over-complicated before.
      
      * Make TcInteract.interactIrred look for constraints that match
        either way around, in TcInteract.findMatchingIrreds
      
      This wasn't hard and it cleaned up quite a bit of code.
      5a66d574
  15. 11 Oct, 2017 1 commit
    • Simon Peyton Jones's avatar
      Remove wc_insol from WantedConstraints · f20cf982
      Simon Peyton Jones authored
      This patch is a pure refactoring, which I've wanted to do for
      some time.  The main payload is
      
      * Remove the wc_insol field from WantedConstraints;
        instead put all the insolubles in wc_simple
      
      * Remove inert_insols from InertCans
        Instead put all the insolubles in inert_irreds
      
      * Add a cc_insol flag to CIrredCan, to record that
        the constraint is definitely insoluble
      
      Reasons
      
      * Quite a bit of code gets slightly simpler
      * Fewer concepts to keep separate
      * Insolubles don't happen at all in production code that is
        just being recompiled, so previously there was a lot of
        moving-about of empty sets
      
      A couple of error messages acutally improved.
      f20cf982
  16. 03 Oct, 2017 1 commit
    • Simon Peyton Jones's avatar
      Fix bug in the short-cut solver · a8fde183
      Simon Peyton Jones authored
      Trac #13943 showed that the relatively-new short-cut solver
      for class constraints (aka -fsolve-constant-dicts) was wrong.
      In particular, see "Type families" under Note [Shortcut solving]
      in TcInteract.
      
      The short-cut solver recursively solves sub-goals, but it doesn't
      flatten type-family applications, and as a result it erroneously
      thought that C (F a) cannot possibly match (C 0), which is
      simply untrue.  That led to an inifinte loop in the short-cut
      solver.
      
      The significant change is the one line
      
      +                 , all isTyFamFree preds  -- See "Type families" in
      +                                          -- Note [Shortcut solving]
      
      but, as ever, I do some other refactoring.  (E.g. I changed the
      name of the function to shortCutSolver rather than the more
      generic trySolveFromInstance.)
      
      I also made the short-cut solver respect the solver-depth limit,
      so that if this happens again it won't just produce an infinite
      loop.
      
      A bit of other refactoring, notably moving isTyFamFree
      from TcValidity to TcType
      a8fde183
  17. 27 Sep, 2017 1 commit
  18. 26 Sep, 2017 2 commits
  19. 25 Sep, 2017 1 commit
    • Simon Peyton Jones's avatar
      Fix solving of implicit parameter constraints · abed9bf5
      Simon Peyton Jones authored
      Trac #14218 showed that we were not solving implicit-parameter
      constraints correctly.  In particular,
      
      - A tuple constraint could "hide" an implicit-parameter wanted
        constraint, and that in turn could that we solved it from the
        wrong implicit-parameter binding.
      
      - As a special case the HasCallStack constraint (which is just
        short for (IP "callStack" CallStack), was getting mis-solved.
      
      The big change is to arrange that, in TcSMonad.findDict when looking
      for a dictionary, either when looking for a matching inert or solved
      dictionary, we fail for
      
        - Tuples that are hiding implicit parameters
          See Note [Tuples hiding implicit parameters]
      
        - HasCallStack constraints where we have not yet pushed
          on the call-site info
          See Note [Solving CallStack constraints]
      
      I also did a little refactoring
      
      * Move naturallyCoherentClass from Class to TcInteract, its sole
        use site.  Class.hs seems like the wrong place.  (And I also
        do not understand the reason that we need the eq/Coercible/
        Typable stuff in this predicate, but I'll tackle that separately.)
      
      * Move the code that pushes call-site info onto a call stack
        from the "interact" part to the "canonicalise" part of the solver.
      abed9bf5
  20. 19 Sep, 2017 1 commit
    • 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
      modules.
      
      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
      f63bc730
  21. 15 Aug, 2017 1 commit
    • Ryan Scott's avatar
      Fix #14060 by more conservatively annotating TH-reified types · ad7b9452
      Ryan Scott authored
      Before, TH was quite generous in applying kind annotations to reified
      type constructors whose result kind happened to mention type variables.
      This could result in agonizingly large reified types, so this patch aims
      to quell this a bit by adopting a more nuanced algorithm for determining
      when a tycon application deserves a kind annotation.
      
      This implements the algorithm laid out in
      https://ghc.haskell.org/trac/ghc/ticket/14060#comment:1. I've updated
      `Note [Kind annotations on TyConApps]` to reflect the new wisdom.
      Essentially, instead of only checking if the result kind contains free
      variables, we also check if any of those variables do not appear free in
      injective positions in the argument kinds—only then do we put on a kind
      annotation.
      
      Bumps `haddock` submodule.
      
      Test Plan: make test TEST=T14060
      
      Reviewers: goldfire, austin, bgamari
      
      Reviewed By: goldfire
      
      Subscribers: rwbarton, thomie
      
      GHC Trac Issues: #14060
      
      Differential Revision: https://phabricator.haskell.org/D3807
      ad7b9452
  22. 26 Jul, 2017 1 commit
  23. 26 May, 2017 1 commit
    • Simon Peyton Jones's avatar
      Re-engineer Given flatten-skolems · 8dc6d645
      Simon Peyton Jones authored
      The big change here is to fix an outright bug in flattening of Givens,
      albeit one that is very hard to exhibit.  Suppose we have the constraint
          forall a. (a ~ F b) => ..., (forall c. ....(F b)...) ...
      
      Then
       - we'll flatten the (F) b to a fsk, say  (F b ~ fsk1)
       - we'll rewrite the (F b) inside the inner implication to 'fsk1'
       - when we leave the outer constraint we are suppose to unflatten;
         but that fsk1 will still be there
       - if we re-simplify the entire outer implication, we'll re-flatten
         the Given (F b) to, say, (F b ~ fsk2)
      Now we have two fsks standing for the same thing, and that is very
      wrong.
      
      Solution: make fsks behave more like fmvs:
       - A flatten-skolem is now a MetaTyVar, whose MetaInfo is FlatSkolTv
       - We "fill in" that meta-tyvar when leaving the implication
       - The old FlatSkol form of TcTyVarDetails is gone completely
       - We track the flatten-skolems for the current implication in
         a new field of InertSet, inert_fsks.
      
      See Note [The flattening story] in TcFlatten.
      
      In doing this I found various other things to fix:
      
      * I removed the zonkSimples from TcFlatten.unflattenWanteds; it wasn't
        needed.   But I added one in TcSimplify.floatEqualities, which does
        the zonk precisely when it is needed.
      
      * Trac #13674 showed up a case where we had
           - an insoluble Given,   e.g.  a ~ [a]
           - the same insoluble Wanted   a ~ [a]
        We don't use the Given to rewwrite the Wanted (obviously), but
        we therefore ended up reporting
            Can't deduce (a ~ [a]) from (a ~ [a])
        which is silly.
      
        Conclusion: when reporting errors, make the occurs check "win"
        See Note [Occurs check wins] in TcErrors
      8dc6d645
  24. 16 May, 2017 1 commit
  25. 11 Apr, 2017 1 commit
  26. 31 Mar, 2017 1 commit
    • Ben Gamari's avatar
      Clean up coreView/tcView. · 6575f4b6
      Ben Gamari authored
      In Core, Constraint should be considered fully equal to
      TYPE LiftedRep, in all ways. Accordingly, coreView should
      unwrap Constraint to become TYPE LiftedRep. Of course, this
      would be a disaster in the type checker.
      
      So, where previously we used coreView in both the type checker
      and in Core, we now have coreView and tcView, which differ only
      in their treatment of Constraint.
      
      Historical note: once upon a past, we had tcView distinct from
      coreView. Back then, it was because newtypes were unwrapped in
      Core but not in the type checker. The distinction is back, but
      for a different reason than before.
      
      This had a few knock-on effects:
      
       * The Typeable solver must explicitly handle Constraint to ensure
         that we produce the correct evidence.
      
       * TypeMap now respects the Constraint/Type distinction
      
      Finished by: bgamari
      
      Test Plan: ./validate
      
      Reviewers: simonpj, austin, bgamari
      
      Reviewed By: simonpj
      
      Subscribers: rwbarton, thomie
      
      Differential Revision: https://phabricator.haskell.org/D3316
      6575f4b6
  27. 07 Mar, 2017 1 commit
  28. 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,
      
      ```lang=haskell
      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
      now).
      
      We also add a kind heterogeneous type equality type, (:~~:), to
      Data.Type.Equality.
      
      Implementation
      --------------
      
      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.
      
      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
      being.
      
      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
      proposal.
      8fa4bf9a
  29. 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
      da493897
  30. 08 Feb, 2017 1 commit
  31. 02 Feb, 2017 1 commit
  32. 31 Jan, 2017 1 commit
    • Daniel Haraj's avatar
      Use top-level instances to solve superclasses where possible · 748b7974
      Daniel Haraj authored
      This patch introduces a new flag `-fsolve-constant-dicts` which makes the
      constraint solver solve super class constraints with available dictionaries if
      possible. The flag is enabled by `-O1`.
      
      The motivation of this patch is that the compiler can produce more efficient
      code if the constraint solver used top-level instance declarations to solve
      constraints that are currently solved givens and their superclasses. In
      particular, as it currently stands, the compiler imposes a performance penalty
      on the common use-case where superclasses are bundled together for user
      convenience. The performance penalty applies to constraint synonyms as
      well. This example illustrates the issue:
      
      ```
      {-# LANGUAGE ConstraintKinds, MultiParamTypeClasses, FlexibleContexts #-}
      module B where
      
      class M a b where m :: a -> b
      
      type C a b = (Num a, M a b)
      
      f :: C Int b => b -> Int -> Int
      f _ x = x + 1
      ```
      
      Output without the patch, notice that we get the instance for `Num Int` by
      using the class selector `p1`.
      
      ```
      f :: forall b_arz. C Int b_arz => b_arz -> Int -> Int
      f =
        \ (@ b_a1EB) ($d(%,%)_a1EC :: C Int b_a1EB) _ (eta1_B1 :: Int) ->
          + @ Int
            (GHC.Classes.$p1(%,%) @ (Num Int) @ (M Int b_a1EB) $d(%,%)_a1EC)
            eta1_B1
            B.f1
      ```
      
      Output with the patch, nicely optimised code!
      
      ```
      f :: forall b. C Int b => b -> Int -> Int
      f =
        \ (@ b) _ _ (x_azg :: Int) ->
          case x_azg of { GHC.Types.I# x1_a1DP ->
          GHC.Types.I# (GHC.Prim.+# x1_a1DP 1#)
          }
      ```
      
      Reviewers: simonpj, bgamari, austin
      
      Reviewed By: simonpj
      
      Subscribers: mpickering, rwbarton, thomie
      
      Differential Revision: https://phabricator.haskell.org/D2714
      
      GHC Trac Issues: #12791, #5835
      748b7974
  33. 23 Jan, 2017 1 commit
    • Simon Peyton Jones's avatar
      Apply the right substitution in ty-fam improvement · 2b64e926
      Simon Peyton Jones authored
      Trac #13135 showed that we were failing to apply the
      correct substitution to the un-substituted tyvars during
      type-family improvement using injectivity.  Specifically
      in TcInteractlinjImproveEqns we need to use instFlexiX.
      
      An outright bug, easy to fix.
      
      Slight refactoring along the way.  The quantified tyars of the axiom are
      readily to hand; we don't need to take the free tyvars of the LHS
      2b64e926
  34. 25 Nov, 2016 3 commits
    • Simon Peyton Jones's avatar
      Be a bit more selective about improvement · f8c966c7
      Simon Peyton Jones authored
      This patch makes [W] constraints not participate in
      improvement.   See Note [Do not do improvement for WOnly]
      in TcSMonad.
      
      Removes some senseless work duplication in some cases (notably
      Trac #12860); should not change behaviour.
      f8c966c7
    • Simon Peyton Jones's avatar
      Refactor functional dependencies a bit · eb55ec29
      Simon Peyton Jones authored
      * Rename CoAxiom.Eqn = Pair Type to TypeEqn,
        and use it for fundeps
      
      * Use the FunDepEqn for injectivity, which lets us share a bit
        more code, and (more important) brain cells
      
      * When generating fundeps, take the max depth of the two
        constraints.  This aimed at tackling the strange loop in
        Trac #12860, but there is more to come for that.
      
      * Improve pretty-printing with -ddump-tc-trace
      eb55ec29
    • Simon Peyton Jones's avatar
      Another major constraint-solver refactoring · 1eec1f21
      Simon Peyton Jones authored
      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.
      1eec1f21
  35. 21 Nov, 2016 1 commit