1. 16 Jan, 2016 1 commit
    • Simon Peyton Jones's avatar
      Fix a number of subtle solver bugs · 9308c736
      Simon Peyton Jones authored
      As a result of some other unrelated changes I found that
      IndTypesPerf was failing, and opened Trac #11408.  There's
      a test in indexed-types/should-compile/T11408.
      
      The bug was that a type like
       forall t. (MT (UL t) (UR t) ~ t) => UL t -> UR t -> Int
      is in fact unambiguous, but it's a bit subtle to prove
      that it is unambiguous.
      
      In investigating, Dimitrios and I found several subtle
      bugs in the constraint solver, fixed by this patch
      
      * canRewrite was missing a Derived/Derived case.  This was
        lost by accident in Richard's big kind-equality patch.
      
      * Interact.interactTyVarEq would discard [D] a ~ ty if there
        was a [W] a ~ ty in the inert set.  But that is wrong because
        the former can rewrite things that the latter cannot.
        Fix: a new function eqCanDischarge
      
      * In TcSMonad.addInertEq, the process was outright wrong for
        a Given/Wanted in the (GWModel) case.  We were adding a new
        Derived without kicking out things that it could rewrite.
        Now the code is simpler (no special GWModel case), and works
        correctly.
      
      * The special case in kickOutRewritable for [W] fsk ~ ty,
        turns out not to be needed.  (We emit a [D] fsk ~ ty which
        will do the job.
      
      I improved comments and documentation, esp in TcSMonad.
      9308c736
  2. 31 Dec, 2015 2 commits
  3. 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
         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.
      67465497
  4. 17 Oct, 2015 1 commit
    • Herbert Valerio Riedel's avatar
      Make Monad/Applicative instances MRP-friendly · e8ed2136
      Herbert Valerio Riedel authored
      This patch refactors pure/(*>) and return/(>>) in MRP-friendly way, i.e.
      such that the explicit definitions for `return` and `(>>)` match the
      MRP-style default-implementation, i.e.
      
        return = pure
      
      and
      
        (>>) = (*>)
      
      This way, e.g. all `return = pure` definitions can easily be grepped and
      removed in GHC 8.1;
      
      Test Plan: Harbormaster
      
      Reviewers: goldfire, alanz, bgamari, quchen, austin
      
      Reviewed By: quchen, austin
      
      Subscribers: thomie
      
      Differential Revision: https://phabricator.haskell.org/D1312
      e8ed2136
  5. 21 Sep, 2015 1 commit
    • eir@cis.upenn.edu's avatar
      Run simplifier only when the env is clean. · 8e8b9ed9
      eir@cis.upenn.edu authored
      This fixes #10896. In the indexed-types/should_fail/BadSock test,
      there is a bad type definition. This gets type-checked, an error
      gets reported, but then **GHC keeps going**. Later, when
      running the simplifier to do an ambiguity check, the bad type
      environment causes GHC to fall over. My solution: only run the
      simplifier in a clean, error-free type environment.
      
      A downside of this is that fewer error messages are reported.
      This makes me a bit sad, but I'm not sure how to avoid the problem.
      Suggestions welcome.
      8e8b9ed9
  6. 07 Aug, 2015 1 commit
  7. 15 Jul, 2015 1 commit
    • eir@cis.upenn.edu's avatar
      Fix #10642. · 9f978b67
      eir@cis.upenn.edu authored
      Representational equalities cannot discharge nominal ones.
      Even if, somehow, this didn't cause a type error (as reported
      in the ticket), it would surely cause a core lint error.
      9f978b67
  8. 11 Jun, 2015 1 commit
    • Simon Peyton Jones's avatar
      Another major improvement of "improvement" · ddbb97d0
      Simon Peyton Jones authored
      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.
      ddbb97d0
  9. 07 May, 2015 1 commit
  10. 01 May, 2015 1 commit
  11. 29 Apr, 2015 2 commits
    • Simon Peyton Jones's avatar
      Improve improvement in the constraint solver · a1275a76
      Simon Peyton Jones authored
      This regrettably-big patch substantially improves the way in which
      "improvement" happens in the constraint solver.  It was triggered by
      trying to crack Trac #10009, but it turned out to solve #10340 as
      well.
      
      The big picture, with several of the trickiest examples, is described
      in Note [The improvement story] in TcInteract.
      
      The major change is this:
      
      * After solving we explicitly try "improvement", by
           - making the unsolved Wanteds into Deriveds
           - allowing Deriveds to rewrite Deriveds
        This more aggressive rewriting "unlocks" some extra
        guess-free unifications.
      
      * The main loop is in TcInteract.solveSimpleWanteds, but I also ended
        up refactoring TcSimplify.simpl_loop, and its surrounding code.
      
        Notably, any insolubles from the Givens are pulled out
        and treated separately, rather than staying in the inert set
        during the solveSimpleWanteds loop.
      
      There are a lot of follow-on changes
      
      * Do not emit generate Derived improvements from Wanteds.
        This saves work in the common case where they aren't needed.
      
      * For improvement we should really do type-class reduction on Derived
        constraints in doTopReactDict.  That entailed changing the GenInst
        constructor a bit; a local and minor change
      
      * Some annoying faffing about with dropping derived constraints;
        see dropDerivedWC, dropDerivedSimples, dropDerivedInsols,
        and their Notes.
      
      * Some substantial refactoring in TcErrors.reportWanteds.
        This work wasn't strictly forced, but I got sucked into it.
        All the changes are in TcErrors.
      
      * Use TcS.unifyTyVar consistently, rather than setWantedTyBind,
        so that unifications are properly tracked.
      
      * Refactoring around solveWantedsTcM, solveWantedsAndDrop.
        They previously guaranteed a zonked result, but it's more
        straightforward for clients to zonk.
      a1275a76
    • Simon Peyton Jones's avatar
      Don't print evidence in TcFlatten · d9bb0ee7
      Simon Peyton Jones authored
      Because when flattening a Derived constraint, the evidence doesn't exist
      (it's an error thunk)
      d9bb0ee7
  12. 22 Apr, 2015 1 commit
  13. 14 Apr, 2015 1 commit
  14. 23 Mar, 2015 1 commit
    • eir@cis.upenn.edu's avatar
      Do proper depth checking in the flattener to avoid looping. · c1edbdfd
      eir@cis.upenn.edu authored
      This implements (roughly) the plan put forward in comment:14:ticket:7788,
      fixing #7788, #8550, #9554, #10139, and addressing concerns raised in #10079.
      There are some regressions w.r.t. GHC 7.8, but only with pathological type
      families (like F a = F a). This also (hopefully -- don't have a test case)
      fixes #10158. Unsolved problems include #10184 and #10185, which are both
      known deficiencies of the approach used here.
      
      As part of this change, the plumbing around detecting infinite loops has
      changed. Instead of -fcontext-stack and -ftype-function-depth, we now have
      one combined -freduction-depth parameter. Setting it to 0 disbales the
      check, which is now the recommended way to get (terminating) code to
      typecheck in releases. (The number of reduction steps may well change between
      minor GHC releases!)
      
      This commit also introduces a new IntWithInf type in BasicTypes
      that represents an integer+infinity. This type is used in a few
      places throughout the code.
      
      Tests in
        indexed-types/should_fail/T7788
        indexed-types/should_fail/T8550
        indexed-types/should_fail/T9554
        indexed-types/should_compile/T10079
        indexed-types/should_compile/T10139
        typecheck/should_compile/T10184  (expected broken)
        typecheck/should_compile/T10185  (expected broken)
      
      This commit also changes performance testsuite numbers, for the better.
      c1edbdfd
  15. 02 Mar, 2015 1 commit
  16. 20 Feb, 2015 1 commit
  17. 09 Jan, 2015 1 commit
    • Simon Peyton Jones's avatar
      A little tidying up in the flattener · 3d449110
      Simon Peyton Jones authored
      Particularly, flatten_many was exported, but the caller was not doing
      runFlatten.  Moreover it was always used at nominal role.
      
      This patch makes the API clearer, and more robust
      3d449110
  18. 06 Jan, 2015 1 commit
    • Simon Peyton Jones's avatar
      Major patch to add -fwarn-redundant-constraints · 32973bf3
      Simon Peyton Jones authored
      The idea was promted by Trac #9939, but it was Christmas, so I did
      some recreational programming that went much further.
      
      The idea is to warn when a constraint in a user-supplied context is
      redundant.  Everything is described in detail in
        Note [Tracking redundant constraints]
      in TcSimplify.
      
      Main changes:
      
       * The new ic_status field in an implication, of type ImplicStatus.
         It replaces ic_insol, and includes information about redundant
         constraints.
      
       * New function TcSimplify.setImplicationStatus sets the ic_status.
      
       * TcSigInfo has sig_report_redundant field to say whenther a
         redundant constraint should be reported; and similarly
         the FunSigCtxt constructor of UserTypeCtxt
      
       * EvBinds has a field eb_is_given, to record whether it is a given
         or wanted binding. Some consequential chagnes to creating an evidence
         binding (so that we record whether it is given or wanted).
      
       * AbsBinds field abs_ev_binds is now a *list* of TcEvBiinds;
         see Note [Typechecking plan for instance declarations] in
         TcInstDcls
      
       * Some significant changes to the type checking of instance
         declarations; Note [Typechecking plan for instance declarations]
         in TcInstDcls.
      
       * I found that TcErrors.relevantBindings was failing to zonk the
         origin of the constraint it was looking at, and hence failing to
         find some relevant bindings.  Easy to fix, and orthogonal to
         everything else, but hard to disentangle.
      
      Some minor refactorig:
      
       * TcMType.newSimpleWanteds moves to Inst, renamed as newWanteds
      
       * TcClassDcl and TcInstDcls now have their own code for typechecking
         a method body, rather than sharing a single function. The shared
         function (ws TcClassDcl.tcInstanceMethodBody) didn't have much code
         and the differences were growing confusing.
      
       * Add new function TcRnMonad.pushLevelAndCaptureConstraints, and
         use it
      
       * Add new function Bag.catBagMaybes, and use it in TcSimplify
      32973bf3
  19. 23 Dec, 2014 1 commit
  20. 22 Dec, 2014 1 commit
  21. 20 Dec, 2014 1 commit
  22. 17 Dec, 2014 1 commit
    • eir@cis.upenn.edu's avatar
      Performance enhancements in TcFlatten. · 922168fd
      eir@cis.upenn.edu authored
      This commit fixes some performance regressions introduced by 0cc47eb9,
      adding more `Coercible` magic to the solver. See Note
      [flatten_many performance] in TcFlatten for more info.
      
      The improvements do not quite restore the old numbers. Given that
      the solver is really more involved now, I am accepting this regression.
      
      The way forward (I believe) would be to have *two* flatteners: one
      that deals only with nominal equalities and thus never checks roles,
      and the more general one. A nice design of keeping this performant
      without duplicating code eludes me, but someone else is welcome
      to take a stab.
      922168fd
  23. 12 Dec, 2014 1 commit
    • eir@cis.upenn.edu's avatar
      Rewrite `Coercible` solver · 0cc47eb9
      eir@cis.upenn.edu authored
      Summary:
      This is a rewrite of the algorithm to solve for Coercible "instances".
      
      A preliminary form of these ideas is at
      https://ghc.haskell.org/trac/ghc/wiki/Design/NewCoercibleSolver
      
      The basic idea here is that the `EqPred` constructor of `PredTree`
      now is parameterised by a new type `EqRel` (where
      `data EqRel = NomEq | ReprEq`). Thus, every equality constraint can
      now talk about nominal equality (the usual case) or representational
      equality (the `Coercible` case).
      
      This is a change from the previous
      behavior where `Coercible` was just considered a regular class with
      a special case in `matchClassInst`.
      
      Because of this change, representational equalities are now
      canonicalized just like nominal ones, allowing more equalities
      to be solved -- in particular, the case at the top of #9117.
      
      A knock-on effect is that the flattener must be aware of the
      choice of equality relation, because the inert set now stores
      both representational inert equalities alongside the nominal
      inert equalities. Of course, we can use representational equalities
      to rewrite only within another representational equality --
      thus the parameterization of the flattener.
      
      A nice side effect of this change is that I've introduced a new
      type `CtFlavour`, which tracks G vs. W vs. D, removing some ugliness
      in the flattener.
      
      This commit includes some refactoring as discussed on D546.
      It also removes the ability of Deriveds to rewrite Deriveds.
      
      This fixes bugs #9117 and #8984.
      
      Reviewers: simonpj, austin, nomeata
      
      Subscribers: carter, thomie
      
      Differential Revision: https://phabricator.haskell.org/D546
      
      GHC Trac Issues: #9117, #8984
      0cc47eb9
  24. 11 Dec, 2014 1 commit
  25. 10 Dec, 2014 3 commits
  26. 08 Dec, 2014 1 commit
    • Simon Peyton Jones's avatar
      Revise the inert-set invariants again · 1d44261c
      Simon Peyton Jones authored
      In particular this patch
      
      - Accepts that rewriting with the inert CTyEqCans should be done recursively
        (hence removing the Bool result from flattenTyVarOuter)
      
      - Refines the kick-out criterion, in paticular to avoid kick-out of (a -f-> ty)
        when f cannot rewrite f.  This is true of Wanteds and hence reduces kick-outs
        of Wanteds, perhaps by a lot
      
      This stuff is not fully documented because the details are still settling, but
      it's looking good.
      
      (And it validates.)
      
      This patch includes the testsuite wibbles.  perf/compiler/T5030 and
      T5837 both improve in bytes-allocated (by 11% and 13% resp), which is
      good.  I'm not sure which of today's short series of patches is
      responsible, nor do I mind much.  (One could find out if necessary.)
      1d44261c
  27. 03 Dec, 2014 1 commit
  28. 02 Dec, 2014 1 commit
    • Simon Peyton Jones's avatar
      Rename Untouchables to TcLevel · 26a3d0fe
      Simon Peyton Jones authored
      This is a long-overdue renaming
         Untouchables  -->   TcLevel
      It is renaming only; no change in functionality.
      
      We really wanted to get this done before the 7.10 fork.
      26a3d0fe
  29. 21 Nov, 2014 1 commit
  30. 20 Nov, 2014 1 commit
    • Jan Stolarek's avatar
      Split SynTyCon to SynonymTyCon and FamilyTyCon · 696fc4ba
      Jan Stolarek authored
      This patch refactors internal representation of type synonyms and type families by splitting them into two separate data constructors of TyCon data type. The main motivation is is that some fields make sense only for type synonyms and some make sense only for type families. This will be even more true with the upcoming injective type families.
      
      There is also some refactoring of names to keep the naming constistent. And thus tc_kind field has become tyConKind and tc_roles has become tcRoles. Both changes are not visible from the outside of TyCon module.
      
      Updates haddock submodule
      
      Reviewers: simonpj
      
      Differential Revision: https://phabricator.haskell.org/D508
      
      GHC Trac Issues: #9812
      696fc4ba
  31. 18 Nov, 2014 1 commit
  32. 11 Nov, 2014 1 commit
  33. 06 Nov, 2014 2 commits
  34. 04 Nov, 2014 1 commit
    • Simon Peyton Jones's avatar
      Simon's major commit to re-engineer the constraint solver · 5770029a
      Simon Peyton Jones authored
      The driving change is this:
      
      * The canonical CFunEqCan constraints now have the form
             [G] F xis ~ fsk
             [W] F xis ~ fmv
        where fsk is a flatten-skolem, and fmv is a flatten-meta-variable
        Think of them as the name of the type-function application
      
      See Note [The flattening story] in TcFlatten.  A flatten-meta-variable
      is distinguishable by its MetaInfo of FlatMetaTv
      
      This in turn led to an enormous cascade of other changes, which simplify
      and modularise the constraint solver.  In particular:
      
      * Basic data types
          * I got rid of inert_solved_funeqs altogether. It serves no useful
            role that inert_flat_cache does not solve.
      
          * I added wl_implics to the WorkList, as a convenient place to
            accumulate newly-emitted implications; see Note [Residual
            implications] in TcSMonad.
      
          * I eliminated tcs_ty_binds altogether. These were the bindings
            for unification variables that we have now solved by
            unification.  We kept them in a finite map and did the
            side-effecting unification later.  But in cannonicalisation we
            had to look up in the side-effected mutable tyvars anyway, so
            nothing was being gained.
      
            Our original idea was that the solver would be pure, and would
            be a no-op if you discarded its results, but this was already
            not-true for implications since we update their evidence
            bindings in an imperative way.  So rather than the uneasy
            compromise, it's now clearly imperative!
      
      * I split out the flatten/unflatten code into a new module, TcFlatten
      
      * I simplified and articulated explicitly the (rather hazy) invariants
        for the inert substitution inert_eqs.  See Note [eqCanRewrite] and
        See Note [Applying the inert substitution] in TcFlatten
      
      * Unflattening is now done (by TcFlatten.unflatten) after solveFlats,
        before solving nested implications.  This turned out to simplify a
        lot of code. Previously, unflattening was done as part of zonking, at
        the very very end.
      
          * Eager unflattening allowed me to remove the unpleasant ic_fsks
            field of an Implication (hurrah)
      
          * Eager unflattening made the TcSimplify.floatEqualities function
            much simpler (just float equalities looking like a ~ ty, where a
            is an untouchable meta-tyvar).
      
          * Likewise the idea of "pushing wanteds in as givens" could be
            completely eliminated.
      
      * I radically simplified the code that determines when there are
        'given' equalities, and hence whether we can float 'wanted' equalies
        out.  See TcSMonad.getNoGivenEqs, and Note [When does an implication
        have given equalities?].
      
        This allowed me to get rid of the unpleasant inert_no_eqs flag in InertCans.
      
      * As part of this given-equality stuff, I fixed Trac #9211. See Note
        [Let-bound skolems] in TcSMonad
      
      * Orientation of tyvar/tyvar equalities (a ~ b) was partly done during
        canonicalisation, but then repeated in the spontaneous-solve stage
        (trySpontaneousSolveTwoWay). Now it is done exclusively during
        canonicalisation, which keeps all the code in one place.  See
        Note [Canonical orientation for tyvar/tyvar equality constraints]
        in TcCanonical
      5770029a