summaryrefslogtreecommitdiff
path: root/compiler/GHC/Tc/Solver/Canonical.hs
Commit message (Collapse)AuthorAgeFilesLines
* Fix decomposition of TyConAppswip/T22331Simon Peyton Jones2022-11-251-197/+303
| | | | | | | | | | | | | | | | Ticket #22331 showed that we were being too eager to decompose a Wanted TyConApp, leading to incompleteness in the solver. To understand all this I ended up doing a substantial rewrite of the old Note [Decomposing equalities], now reborn as Note [Decomposing TyConApp equalities]. Plus rewrites of other related Notes. The actual fix is very minor and actually simplifies the code: in `can_decompose` in `GHC.Tc.Solver.Canonical.canTyConApp`, we now call `noMatchableIrreds`. A closely related refactor: we stop trying to use the same "no matchable givens" function here as in `matchClassInst`. Instead split into two much simpler functions.
* Type vs Constraint: finally nailedSimon Peyton Jones2022-11-111-131/+112
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This big patch addresses the rats-nest of issues that have plagued us for years, about the relationship between Type and Constraint. See #11715/#21623. The main payload of the patch is: * To introduce CONSTRAINT :: RuntimeRep -> Type * To make TYPE and CONSTRAINT distinct throughout the compiler Two overview Notes in GHC.Builtin.Types.Prim * Note [TYPE and CONSTRAINT] * Note [Type and Constraint are not apart] This is the main complication. The specifics * New primitive types (GHC.Builtin.Types.Prim) - CONSTRAINT - ctArrowTyCon (=>) - tcArrowTyCon (-=>) - ccArrowTyCon (==>) - funTyCon FUN -- Not new See Note [Function type constructors and FunTy] and Note [TYPE and CONSTRAINT] * GHC.Builtin.Types: - New type Constraint = CONSTRAINT LiftedRep - I also stopped nonEmptyTyCon being built-in; it only needs to be wired-in * Exploit the fact that Type and Constraint are distinct throughout GHC - Get rid of tcView in favour of coreView. - Many tcXX functions become XX functions. e.g. tcGetCastedTyVar --> getCastedTyVar * Kill off Note [ForAllTy and typechecker equality], in (old) GHC.Tc.Solver.Canonical. It said that typechecker-equality should ignore the specified/inferred distinction when comparein two ForAllTys. But that wsa only weakly supported and (worse) implies that we need a separate typechecker equality, different from core equality. No no no. * GHC.Core.TyCon: kill off FunTyCon in data TyCon. There was no need for it, and anyway now we have four of them! * GHC.Core.TyCo.Rep: add two FunTyFlags to FunCo See Note [FunCo] in that module. * GHC.Core.Type. Lots and lots of changes driven by adding CONSTRAINT. The key new function is sORTKind_maybe; most other changes are built on top of that. See also `funTyConAppTy_maybe` and `tyConAppFun_maybe`. * Fix a longstanding bug in GHC.Core.Type.typeKind, and Core Lint, in kinding ForAllTys. See new tules (FORALL1) and (FORALL2) in GHC.Core.Type. (The bug was that before (forall (cv::t1 ~# t2). blah), where blah::TYPE IntRep, would get kind (TYPE IntRep), but it should be (TYPE LiftedRep). See Note [Kinding rules for types] in GHC.Core.Type. * GHC.Core.TyCo.Compare is a new module in which we do eqType and cmpType. Of course, no tcEqType any more. * GHC.Core.TyCo.FVs. I moved some free-var-like function into this module: tyConsOfType, visVarsOfType, and occCheckExpand. Refactoring only. * GHC.Builtin.Types. Compiletely re-engineer boxingDataCon_maybe to have one for each /RuntimeRep/, rather than one for each /Type/. This dramatically widens the range of types we can auto-box. See Note [Boxing constructors] in GHC.Builtin.Types The boxing types themselves are declared in library ghc-prim:GHC.Types. GHC.Core.Make. Re-engineer the treatment of "big" tuples (mkBigCoreVarTup etc) GHC.Core.Make, so that it auto-boxes unboxed values and (crucially) types of kind Constraint. That allows the desugaring for arrows to work; it gathers up free variables (including dictionaries) into tuples. See Note [Big tuples] in GHC.Core.Make. There is still work to do here: #22336. But things are better than before. * GHC.Core.Make. We need two absent-error Ids, aBSENT_ERROR_ID for types of kind Type, and aBSENT_CONSTRAINT_ERROR_ID for vaues of kind Constraint. Ditto noInlineId vs noInlieConstraintId in GHC.Types.Id.Make; see Note [inlineId magic]. * GHC.Core.TyCo.Rep. Completely refactor the NthCo coercion. It is now called SelCo, and its fields are much more descriptive than the single Int we used to have. A great improvement. See Note [SelCo] in GHC.Core.TyCo.Rep. * GHC.Core.RoughMap.roughMatchTyConName. Collapse TYPE and CONSTRAINT to a single TyCon, so that the rough-map does not distinguish them. * GHC.Core.DataCon - Mainly just improve documentation * Some significant renamings: GHC.Core.Multiplicity: Many --> ManyTy (easier to grep for) One --> OneTy GHC.Core.TyCo.Rep TyCoBinder --> GHC.Core.Var.PiTyBinder GHC.Core.Var TyCoVarBinder --> ForAllTyBinder AnonArgFlag --> FunTyFlag ArgFlag --> ForAllTyFlag GHC.Core.TyCon TyConTyCoBinder --> TyConPiTyBinder Many functions are renamed in consequence e.g. isinvisibleArgFlag becomes isInvisibleForAllTyFlag, etc * I refactored FunTyFlag (was AnonArgFlag) into a simple, flat data type data FunTyFlag = FTF_T_T -- (->) Type -> Type | FTF_T_C -- (-=>) Type -> Constraint | FTF_C_T -- (=>) Constraint -> Type | FTF_C_C -- (==>) Constraint -> Constraint * GHC.Tc.Errors.Ppr. Some significant refactoring in the TypeEqMisMatch case of pprMismatchMsg. * I made the tyConUnique field of TyCon strict, because I saw code with lots of silly eval's. That revealed that GHC.Settings.Constants.mAX_SUM_SIZE can only be 63, because we pack the sum tag into a 6-bit field. (Lurking bug squashed.) Fixes * #21530 Updates haddock submodule slightly. Performance changes ~~~~~~~~~~~~~~~~~~~ I was worried that compile times would get worse, but after some careful profiling we are down to a geometric mean 0.1% increase in allocation (in perf/compiler). That seems fine. There is a big runtime improvement in T10359 Metric Decrease: LargeRecord MultiLayerModulesTH_OneShot T13386 T13719 Metric Increase: T8095
* Define `Infinite` list and use where appropriate.M Farkas-Dyck2022-11-081-2/+2
| | | | | | | | Also add perf test for infinite list fusion. In particular, in `GHC.Core`, often we deal with infinite lists of roles. Also in a few locations we deal with infinite lists of names. Thanks to simonpj for helping to write the Note [Fusion for `Infinite` lists].
* TyEq:N assertion: only for saturated applicationssheaf2022-10-191-5/+15
| | | | | | | | | | The assertion that checked TyEq:N in canEqCanLHSFinish incorrectly triggered in the case of an unsaturated newtype TyCon heading the RHS, even though we can't unwrap such an application. Now, we only trigger an assertion failure in case of a saturated application of a newtype TyCon. Fixes #22310
* Fix typosKrzysztof Gogolewski2022-09-141-1/+1
|
* Fix typosEric Lindblad2022-09-141-5/+5
| | | | | | | This fixes various typos and spelling mistakes in the compiler. Fixes #21891
* Remove TCvSubst and use Subst for both term and type-level substYiyun Liu2022-08-041-4/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This patch removes the TCvSubst data type and instead uses Subst as the environment for both term and type level substitution. This change is partially motivated by the existential type proposal, which will introduce types that contain expressions and therefore forces us to carry around an "IdSubstEnv" even when substituting for types. It also reduces the amount of code because "Subst" and "TCvSubst" share a lot of common operations. There isn't any noticeable impact on performance (geo. mean for ghc/alloc is around 0.0% but we have -94 loc and one less data type to worry abount). Currently, the "TCvSubst" data type for substitution on types is identical to the "Subst" data type except the former doesn't store "IdSubstEnv". Using "Subst" for type-level substitution means there will be a redundant field stored in the data type. However, in cases where the substitution starts from the expression, using "Subst" for type-level substitution saves us from having to project "Subst" into a "TCvSubst". This probably explains why the allocation is mostly even despite the redundant field. The patch deletes "TCvSubst" and moves "Subst" and its relevant functions from "GHC.Core.Subst" into "GHC.Core.TyCo.Subst". Substitution on expressions is still defined in "GHC.Core.Subst" so we don't have to expose the definition of "Expr" in the hs-boot file that "GHC.Core.TyCo.Subst" must import to refer to "IdSubstEnv" (whose codomain is "CoreExpr"). Most functions named fooTCvSubst are renamed into fooSubst with a few exceptions (e.g. "isEmptyTCvSubst" is a distinct function from "isEmptySubst"; the former ignores the emptiness of "IdSubstEnv"). These exceptions mainly exist for performance reasons and will go away when "Expr" and "Type" are mutually recursively defined (we won't be able to take those shortcuts if we can't make the assumption that expressions don't appear in types).
* Generalize breakTyVarCycle to work with TyFamLHSRichard Eisenberg2022-05-261-47/+75
| | | | | | | | | | | | | | | | | The function breakTyVarCycle_maybe has been installed in a dark corner of GHC to catch some gremlins (a.k.a. occurs-check failures) who lurk there. But it previously only caught gremlins of the form (a ~ ... F a ...), where some of our intrepid users have spawned gremlins of the form (G a ~ ... F (G a) ...). This commit improves breakTyVarCycle_maybe (and renames it to breakTyEqCycle_maybe) to catch the new gremlins. Happily, the change is remarkably small. The gory details are in Note [Type equality cycles]. Test cases: typecheck/should_compile/{T21515,T21473}.
* Fix unification of ConcreteTvs, removing IsRefl#sheaf2022-04-281-48/+0
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This patch fixes the unification of concrete type variables. The subtlety was that unifying concrete metavariables is more subtle than other metavariables, as decomposition is possible. See the Note [Unifying concrete metavariables], which explains how we unify a concrete type variable with a type 'ty' by concretising 'ty', using the function 'GHC.Tc.Utils.Concrete.concretise'. This can be used to perform an eager syntactic check for concreteness, allowing us to remove the IsRefl# special predicate. Instead of emitting two constraints `rr ~# concrete_tv` and `IsRefl# rr concrete_tv`, we instead concretise 'rr'. If this succeeds we can fill 'concrete_tv', and otherwise we directly emit an error message to the typechecker environment instead of deferring. We still need the error message to be passed on (instead of directly thrown), as we might benefit from further unification in which case we will need to zonk the stored types. To achieve this, we change the 'wc_holes' field of 'WantedConstraints' to 'wc_errors', which stores general delayed errors. For the moement, a delayed error is either a hole, or a syntactic equality error. hasFixedRuntimeRep_MustBeRefl is now hasFixedRuntimeRep_syntactic, and hasFixedRuntimeRep has been refactored to directly return the most useful coercion for PHASE 2 of FixedRuntimeRep. This patch also adds a field ir_frr to the InferResult datatype, holding a value of type Maybe FRROrigin. When this value is not Nothing, this means that we must fill the ir_ref field with a type which has a fixed RuntimeRep. When it comes time to fill such an ExpType, we ensure that the type has a fixed RuntimeRep by performing a representation-polymorphism check with the given FRROrigin This is similar to what we already do to ensure we fill an Infer ExpType with a type of the correct TcLevel. This allows us to properly perform representation-polymorphism checks on 'Infer' 'ExpTypes'. The fillInferResult function had to be moved to GHC.Tc.Utils.Unify to avoid a cyclic import now that it calls hasFixedRuntimeRep. This patch also changes the code in matchExpectedFunTys to make use of the coercions, which is now possible thanks to the previous change. This implements PHASE 2 of FixedRuntimeRep in some situations. For example, the test cases T13105 and T17536b are now both accepted. Fixes #21239 and #21325 ------------------------- Metric Decrease: T18223 T5631 -------------------------
* Fix isLiftedType_maybe and handle falloutsheaf2022-03-141-0/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | As #20837 pointed out, `isLiftedType_maybe` returned `Just False` in many situations where it should return `Nothing`, because it didn't take into account type families or type variables. In this patch, we fix this issue. We rename `isLiftedType_maybe` to `typeLevity_maybe`, which now returns a `Levity` instead of a boolean. We now return `Nothing` for types with kinds of the form `TYPE (F a1 ... an)` for a type family `F`, as well as `TYPE (BoxedRep l)` where `l` is a type variable. This fix caused several other problems, as other parts of the compiler were relying on `isLiftedType_maybe` returning a `Just` value, and were now panicking after the above fix. There were two main situations in which panics occurred: 1. Issues involving the let/app invariant. To uphold that invariant, we need to know whether something is lifted or not. If we get an answer of `Nothing` from `isLiftedType_maybe`, then we don't know what to do. As this invariant isn't particularly invariant, we can change the affected functions to not panic, e.g. by behaving the same in the `Just False` case and in the `Nothing` case (meaning: no observable change in behaviour compared to before). 2. Typechecking of data (/newtype) constructor patterns. Some programs involving patterns with unknown representations were accepted, such as T20363. Now that we are stricter, this caused further issues, culminating in Core Lint errors. However, the behaviour was incorrect the whole time; the incorrectness only being revealed by this change, not triggered by it. This patch fixes this by overhauling where the representation polymorphism involving pattern matching are done. Instead of doing it in `tcMatches`, we instead ensure that the `matchExpected` functions such as `matchExpectedFunTys`, `matchActualFunTySigma`, `matchActualFunTysRho` allow return argument pattern types which have a fixed RuntimeRep (as defined in Note [Fixed RuntimeRep]). This ensures that the pattern matching code only ever handles types with a known runtime representation. One exception was that patterns with an unknown representation type could sneak in via `tcConPat`, which points to a missing representation-polymorphism check, which this patch now adds. This means that we now reject the program in #20363, at least until we implement PHASE 2 of FixedRuntimeRep (allowing type families in RuntimeRep positions). The aforementioned refactoring, in which checks have been moved to `matchExpected` functions, is a first step in implementing PHASE 2 for patterns. Fixes #20837
* Introduce ConcreteTv metavariablessheaf2022-03-021-216/+39
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This patch introduces a new kind of metavariable, by adding the constructor `ConcreteTv` to `MetaInfo`. A metavariable with `ConcreteTv` `MetaInfo`, henceforth a concrete metavariable, can only be unified with a type that is concrete (that is, a type that answers `True` to `GHC.Core.Type.isConcrete`). This solves the problem of dangling metavariables in `Concrete#` constraints: instead of emitting `Concrete# ty`, which contains a secret existential metavariable, we simply emit a primitive equality constraint `ty ~# concrete_tv` where `concrete_tv` is a fresh concrete metavariable. This means we can avoid all the complexity of canonicalising `Concrete#` constraints, as we can just re-use the existing machinery for `~#`. To finish things up, this patch then removes the `Concrete#` special predicate, and instead introduces the special predicate `IsRefl#` which enforces that a coercion is reflexive. Such a constraint is needed because the canonicaliser is quite happy to rewrite an equality constraint such as `ty ~# concrete_tv`, but such a rewriting is not handled by the rest of the compiler currently, as we need to make use of the resulting coercion, as outlined in the FixedRuntimeRep plan. The big upside of this approach (on top of simplifying the code) is that we can now selectively implement PHASE 2 of FixedRuntimeRep, by changing individual calls of `hasFixedRuntimeRep_MustBeRefl` to `hasFixedRuntimeRep` and making use of the obtained coercion.
* Kill derived constraintsRichard Eisenberg2022-02-231-369/+340
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Co-authored by: Sam Derbyshire Previously, GHC had three flavours of constraint: Wanted, Given, and Derived. This removes Derived constraints. Though serving a number of purposes, the most important role of Derived constraints was to enable better error messages. This job has been taken over by the new RewriterSets, as explained in Note [Wanteds rewrite wanteds] in GHC.Tc.Types.Constraint. Other knock-on effects: - Various new Notes as I learned about under-described bits of GHC - A reshuffling around the AST for implicit-parameter bindings, with better integration with TTG. - Various improvements around fundeps. These were caused by the fact that, previously, fundep constraints were all Derived, and Derived constraints would get dropped. Thus, an unsolved Derived didn't stop compilation. Without Derived, this is no longer possible, and so we have to be considerably more careful around fundeps. - A nice little refactoring in GHC.Tc.Errors to center the work on a new datatype called ErrorItem. Constraints are converted into ErrorItems at the start of processing, and this allows for a little preprocessing before the main classification. - This commit also cleans up the behavior in generalisation around functional dependencies. Now, if a variable is determined by functional dependencies, it will not be quantified. This change is user facing, but it should trim down GHC's strange behavior around fundeps. - Previously, reportWanteds did quite a bit of work, even on an empty WantedConstraints. This commit adds a fast path. - Now, GHC will unconditionally re-simplify constraints during quantification. See Note [Unconditionally resimplify constraints when quantifying], in GHC.Tc.Solver. Close #18398. Close #18406. Solve the fundep-related non-confluence in #18851. Close #19131. Close #19137. Close #20922. Close #20668. Close #19665. ------------------------- Metric Decrease: LargeRecord T9872b T9872b_defer T9872d TcPlugin_RewritePerf -------------------------
* Fix some notesMatthew Pickering2022-02-081-2/+2
|
* Relax TyEq:N: allow out-of-scope newtype DataConsheaf2022-02-081-8/+20
| | | | | | | | | | The 'bad_newtype' assertion in GHC.Tc.Solver.Canonical.canEqCanLHSFinish failed to account for the possibility that the newtype constructor might not be in scope, in which case we don't provide any guarantees about canonicalising away a newtype on the RHS of a representational equality. Fixes #21010
* Rework the handling of SkolemInfoMatthew Pickering2022-01-291-11/+11
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The main purpose of this patch is to attach a SkolemInfo directly to each SkolemTv. This fixes the large number of bugs which have accumulated over the years where we failed to report errors due to having "no skolem info" for particular type variables. Now the origin of each type varible is stored on the type variable we can always report accurately where it cames from. Fixes #20969 #20732 #20680 #19482 #20232 #19752 #10946 #19760 #20063 #13499 #14040 The main changes of this patch are: * SkolemTv now contains a SkolemInfo field which tells us how the SkolemTv was created. Used when reporting errors. * Enforce invariants relating the SkolemInfoAnon and level of an implication (ic_info, ic_tclvl) to the SkolemInfo and level of the type variables in ic_skols. * All ic_skols are TcTyVars -- Check is currently disabled * All ic_skols are SkolemTv * The tv_lvl of the ic_skols agrees with the ic_tclvl * The ic_info agrees with the SkolInfo of the implication. These invariants are checked by a debug compiler by checkImplicationInvariants. * Completely refactor kcCheckDeclHeader_sig which kept doing my head in. Plus, it wasn't right because it wasn't skolemising the binders as it decomposed the kind signature. The new story is described in Note [kcCheckDeclHeader_sig]. The code is considerably shorter than before (roughly 240 lines turns into 150 lines). It still has the same awkward complexity around computing arity as before, but that is a language design issue. See Note [Arity inference in kcCheckDeclHeader_sig] * I added new type synonyms MonoTcTyCon and PolyTcTyCon, and used them to be clear which TcTyCons have "finished" kinds etc, and which are monomorphic. See Note [TcTyCon, MonoTcTyCon, and PolyTcTyCon] * I renamed etaExpandAlgTyCon to splitTyConKind, becuase that's a better name, and it is very useful in kcCheckDeclHeader_sig, where eta-expansion isn't an issue. * Kill off the nasty `ClassScopedTvEnv` entirely. Co-authored-by: Simon Peyton Jones <simon.peytonjones@gmail.com>
* Set the TcLclEnv when solving a ForAll constraintSimon Peyton Jones2022-01-271-0/+4
| | | | | | | Fix a simple omission in GHC.Tc.Solver.Canonical.solveForAll, where we ended up with the wrong TcLclEnv captured in an implication. Result: unhelpful error message (#21006)
* Skip computing superclass origins for equalitiesRichard Eisenberg2021-12-281-4/+13
| | | | This yields a small, but measurable, performance improvement.
* Ensure new Ct/evidence invariantChristiaan Baaij2021-11-251-5/+5
| | | | | | | | | | The `ctev_pred` field of a `CtEvidence` is a just a cache for the type of the evidence. More precisely: * For Givens, `ctev_pred` = `varType ctev_evar` * For Wanteds, `ctev_pred` = `evDestType ctev_dest` This new invariant is needed because evidence can become part of a type, via `Castty ty kco`.
* Use local instances with least superclass depthRichard Eisenberg2021-11-121-12/+12
| | | | | | | | | | See new Note [Use only the best local instance] in GHC.Tc.Solver.Interact. This commit also refactors the InstSC/OtherSC mechanism slightly. Close #20582.
* Improve redundant-constraints warningRichard Eisenberg2021-11-121-5/+12
| | | | | | | | | | | | | | Previously, we reported things wrong with f :: (Eq a, Ord a) => a -> Bool f x = x == x saying that Eq a was redundant. This is fixed now, along with some simplification in Note [Replacement vs keeping]. There's a tiny bit of extra complexity in setImplicationStatus, but it's explained in Note [Tracking redundant constraints]. Close #20602
* Introduce Concrete# for representation polymorphism checkssheaf2021-10-171-2/+143
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | PHASE 1: we never rewrite Concrete# evidence. This patch migrates all the representation polymorphism checks to the typechecker, using a new constraint form Concrete# :: forall k. k -> TupleRep '[] Whenever a type `ty` must be representation-polymorphic (e.g. it is the type of an argument to a function), we emit a new `Concrete# ty` Wanted constraint. If this constraint goes unsolved, we report a representation-polymorphism error to the user. The 'FRROrigin' datatype keeps track of the context of the representation-polymorphism check, for more informative error messages. This paves the way for further improvements, such as allowing type families in RuntimeReps and improving the soundness of typed Template Haskell. This is left as future work (PHASE 2). fixes #17907 #20277 #20330 #20423 #20426 updates haddock submodule ------------------------- Metric Decrease: T5642 -------------------------
* Compare FunTys as if they were TyConApps.Richard Eisenberg2021-09-291-3/+2
| | | | | | | | | | | See Note [Equality on FunTys] in TyCoRep. Close #17675. Close #17655, about documentation improvements included in this patch. Close #19677, about a further mistake around FunTy. test cases: typecheck/should_compile/T19677
* Use Reductions to keep track of rewritingssheaf2021-08-041-75/+70
| | | | | | | | | | | | | | | | | | | | | | | | | | | | We define Reduction = Reduction Coercion !Type. A reduction of the form 'Reduction co new_ty' witnesses an equality ty ~co~> new_ty. That is, the rewriting happens left-to-right: the right-hand-side type of the coercion is the rewritten type, and the left-hand-side type the original type. Sticking to this convention makes the codebase more consistent, helping to avoid certain applications of SymCo. This replaces the parts of the codebase which represented reductions as pairs, (Coercion,Type) or (Type,Coercion). Reduction being strict in the Type argument improves performance in some programs that rewrite many type families (such as T9872). Fixes #20161 ------------------------- Metric Decrease: T5321Fun T9872a T9872b T9872c T9872d -------------------------
* Make CallStacks work better with RebindableSyntaxSimon Peyton Jones2021-07-271-2/+4
| | | | | | | | | | | | | | | | | | | | As #19918 pointed out, the CallStack mechanism didn't work well with RebindableSyntax. This patch improves matters. See GHC.Tc.Types.Evidence Note [Overview of implicit CallStacks] * New predicate isPushCallStackOrigin distinguishes when a CallStack constraint should be solved "directly" or by pushing an item on the stack. * The constructor EvCsPushCall now has a FastString, which can describe not only a function call site, but also things like "the literal 42" or "an if-then-else expression". * I also fixed #20126 thus: exprCtOrigin (HsIf {}) = IfThenElseOrigin (Previously it was "can't happen".)
* Fix #19682 by breaking cycles in DerivedsRichard Eisenberg2021-06-051-304/+278
| | | | | | | | | | | | | | | | | | | | | | | | | | | | This commit expands the old Note [Type variable cycles in Givens] to apply as well to Deriveds. See the Note for details and examples. This fixes a regression introduced by my earlier commit that killed off the flattener in favor of the rewriter. A few other things happened along the way: * unifyTest was renamed to touchabilityTest, because that's what it does. * isInsolubleOccursCheck was folded into checkTypeEq, which does much of the same work. To get this to work out, though, we need to keep more careful track of what errors we spot in checkTypeEq, and so CheckTyEqResult has become rather more glorious. * A redundant Note or two was eliminated. * Kill off occCheckForErrors; due to Note [Rewriting synonyms], the extra occCheckExpand here is always redundant. * Store blocked equalities separately from other inerts; less stuff to look through when kicking out. Close #19682. test case: typecheck/should_compile/T19682{,b}
* Rip GHC.Tc.Solver.Monad asunder (only)Richard Eisenberg2021-05-291-2/+3
| | | | | | | | | | | This creates new modules GHC.Tc.Solver.InertSet and GHC.Tc.Solver.Types. The Monad module is still pretty big, but this is an improvement. Moreover, it means that GHC.HsToCore.Pmc.Solver.Types no longer depends on the constraint solver (it now depends on GHC.Tc.Solver.InertSet), making the error-messages work easier. This patch thus contributes to #18516.
* Fully remove HsVersions.hSylvain Henry2021-05-121-2/+0
| | | | | | | | | | Replace uses of WARN macro with calls to: warnPprTrace :: Bool -> SDoc -> a -> a Remove the now unused HsVersions.h Bump haddock submodule
* Replace CPP assertions with Haskell functionsSylvain Henry2021-05-121-8/+9
| | | | | | | | | | | | | | | There is no reason to use CPP. __LINE__ and __FILE__ macros are now better replaced with GHC's CallStack. As a bonus, assert error messages now contain more information (function name, column). Here is the mapping table (HasCallStack omitted): * ASSERT: assert :: Bool -> a -> a * MASSERT: massert :: Bool -> m () * ASSERTM: assertM :: m Bool -> m () * ASSERT2: assertPpr :: Bool -> SDoc -> a -> a * MASSERT2: massertPpr :: Bool -> SDoc -> m () * ASSERTM2: assertPprM :: m Bool -> SDoc -> m ()
* Avoid fundep-caused loop in the typecheckerSimon Peyton Jones2021-03-311-8/+15
| | | | | | | | | | | Ticket #19415 showed a nasty typechecker loop, which can happen with fundeps that do not satisfy the coverage condition. This patch fixes the problem. It's described in GHC.Tc.Solver.Interact Note [Fundeps with instances] It's not a perfect solution, as the Note explains, but it's better than the status quo.
* Establish invariant (GivenInv)Simon Peyton Jones2021-01-021-2/+3
| | | | | | | | | | | | | | | | | | This patch establishes invariant (GivenInv) from GHC.Tc.Utils.TcType Note [TcLevel invariants]. (GivenInv) says that unification variables from level 'n' should not appear in the Givens for level 'n'. See Note [GivenInv] in teh same module. This invariant was already very nearly true, but a dark corner of partial type signatures made it false. The patch re-jigs partial type signatures a bit to avoid the problem, and documents the invariant much more thorughly Fixes #18646 along the way: see Note [Extra-constraints wildcards] in GHC.Tc.Gen.Bind I also simplified the interface to tcSimplifyInfer slightly, so that it /emits/ the residual constraint, rather than /returning/ it.
* Refactor renamer datastructuresAdam Gundry2020-12-241-1/+1
| | | | | | | | | | | | | | | This patch significantly refactors key renamer datastructures (primarily Avail and GlobalRdrElt) in order to treat DuplicateRecordFields in a more robust way. In particular it allows the extension to be used with pattern synonyms (fixes where mangled record selector names could be printed instead of field labels (e.g. with -Wpartial-fields or hole fits, see new tests). The key idea is the introduction of a new type GreName for names that may represent either normal entities or field labels. This is then used in GlobalRdrElt and AvailInfo, in place of the old way of representing fields using FldParent (yuck) and an extra list in AvailTC. Updates the haddock submodule.
* Fix another haddock parse errorMatthew Pickering2020-12-221-1/+1
|
* Kill floatEqualities completelySimon Peyton Jones2020-12-201-23/+98
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This patch delivers on #17656, by entirel killing off the complex floatEqualities mechanism. Previously, floatEqualities would float an equality out of an implication, so that it could be solved at an outer level. But now we simply do unification in-place, without floating the constraint, relying on level numbers to determine untouchability. There are a number of important new Notes: * GHC.Tc.Utils.Unify Note [Unification preconditions] describes the preconditions for unification, including both skolem-escape and touchability. * GHC.Tc.Solver.Interact Note [Solve by unification] describes what we do when we do unify * GHC.Tc.Solver.Monad Note [The Unification Level Flag] describes how we control solver iteration under this new scheme * GHC.Tc.Solver.Monad Note [Tracking Given equalities] describes how we track when we have Given equalities * GHC.Tc.Types.Constraint Note [HasGivenEqs] is a new explanation of the ic_given_eqs field of an implication A big raft of subtle Notes in Solver, concerning floatEqualities, disappears. Main code changes: * GHC.Tc.Solver.floatEqualities disappears entirely * GHC.Tc.Solver.Monad: new fields in InertCans, inert_given_eq_lvl and inert_given_eq, updated by updateGivenEqs See Note [Tracking Given equalities]. * In exchange for updateGivenEqa, GHC.Tc.Solver.Monad.getHasGivenEqs is much simpler and more efficient * I found I could kill of metaTyVarUpdateOK entirely One test case T14683 showed a 5.1% decrease in compile-time allocation; and T5631 was down 2.2%. Other changes were small. Metric Decrease: T14683 T5631
* Optimise nullary type constructor usagewip/tyconapp-optsBen Gamari2020-12-141-0/+5
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | During the compilation of programs GHC very frequently deals with the `Type` type, which is a synonym of `TYPE 'LiftedRep`. This patch teaches GHC to avoid expanding the `Type` synonym (and other nullary type synonyms) during type comparisons, saving a good amount of work. This optimisation is described in `Note [Comparing nullary type synonyms]`. To maximize the impact of this optimisation, we introduce a few special-cases to reduce `TYPE 'LiftedRep` to `Type`. See `Note [Prefer Type over TYPE 'LiftedPtrRep]`. Closes #17958. Metric Decrease: T18698b T1969 T12227 T12545 T12707 T14683 T3064 T5631 T5642 T9020 T9630 T9872a T13035 haddock.Cabal haddock.base
* Revert "Optimise nullary type constructor usage"Ben Gamari2020-12-141-5/+0
| | | | | | This was inadvertently merged. This reverts commit 7e9debd4ceb068effe8ac81892d2cabcb8f55850.
* Optimise nullary type constructor usageBen Gamari2020-12-141-0/+5
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | During the compilation of programs GHC very frequently deals with the `Type` type, which is a synonym of `TYPE 'LiftedRep`. This patch teaches GHC to avoid expanding the `Type` synonym (and other nullary type synonyms) during type comparisons, saving a good amount of work. This optimisation is described in `Note [Comparing nullary type synonyms]`. To maximize the impact of this optimisation, we introduce a few special-cases to reduce `TYPE 'LiftedRep` to `Type`. See `Note [Prefer Type over TYPE 'LiftedPtrRep]`. Closes #17958. Metric Decrease: T18698b T1969 T12227 T12545 T12707 T14683 T3064 T5631 T5642 T9020 T9630 T9872a T13035 haddock.Cabal haddock.base
* Fix kind inference for data types. Again.Simon Peyton Jones2020-12-081-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This patch fixes several aspects of kind inference for data type declarations, especially data /instance/ declarations Specifically 1. In kcConDecls/kcConDecl make it clear that the tc_res_kind argument is only used in the H98 case; and in that case there is no result kind signature; and hence no need for the disgusting splitPiTys in kcConDecls (now thankfully gone). The GADT case is a bit different to before, and much nicer. This is what fixes #18891. See Note [kcConDecls: kind-checking data type decls] 2. Do not look at the constructor decls of a data/newtype instance in tcDataFamInstanceHeader. See GHC.Tc.TyCl.Instance Note [Kind inference for data family instances]. This was a new realisation that arose when doing (1) This causes a few knock-on effects in the tests suite, because we require more information than before in the instance /header/. New user-manual material about this in "Kind inference in data type declarations" and "Kind inference for data/newtype instance declarations". 3. Minor improvement in kcTyClDecl, combining GADT and H98 cases 4. Fix #14111 and #8707 by allowing the header of a data instance to affect kind inferece for the the data constructor signatures; as described at length in Note [GADT return types] in GHC.Tc.TyCl This led to a modest refactoring of the arguments (and argument order) of tcConDecl/tcConDecls. 5. Fix #19000 by inverting the sense of the test in new_locs in GHC.Tc.Solver.Canonical.canDecomposableTyConAppOK.
* Rename the flattener to become the rewriter.Richard Eisenberg2020-12-011-95/+97
| | | | | | | | Now that flattening doesn't produce flattening variables, it's not really flattening anything: it's rewriting. This change also means that the rewriter can no longer be confused the core flattener (in GHC.Core.Unify), which is sometimes used during type-checking.
* Remove flattening variablesRichard Eisenberg2020-12-011-327/+836
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This patch redesigns the flattener to simplify type family applications directly instead of using flattening meta-variables and skolems. The key new innovation is the CanEqLHS type and the new CEqCan constraint (Ct). A CanEqLHS is either a type variable or exactly-saturated type family application; either can now be rewritten using a CEqCan constraint in the inert set. Because the flattener no longer reduces all type family applications to variables, there was some performance degradation if a lengthy type family application is now flattened over and over (not making progress). To compensate, this patch contains some extra optimizations in the flattener, leading to a number of performance improvements. Close #18875. Close #18910. There are many extra parts of the compiler that had to be affected in writing this patch: * The family-application cache (formerly the flat-cache) sometimes stores coercions built from Given inerts. When these inerts get kicked out, we must kick out from the cache as well. (This was, I believe, true previously, but somehow never caused trouble.) Kicking out from the cache requires adding a filterTM function to TrieMap. * This patch obviates the need to distinguish "blocking" coercion holes from non-blocking ones (which, previously, arose from CFunEqCans). There is thus some simplification around coercion holes. * Extra commentary throughout parts of the code I read through, to preserve the knowledge I gained while working. * A change in the pure unifier around unifying skolems with other types. Unifying a skolem now leads to SurelyApart, not MaybeApart, as documented in Note [Binding when looking up instances] in GHC.Core.InstEnv. * Some more use of MCoercion where appropriate. * Previously, class-instance lookup automatically noticed that e.g. C Int was a "unifier" to a target [W] C (F Bool), because the F Bool was flattened to a variable. Now, a little more care must be taken around checking for unifying instances. * Previously, tcSplitTyConApp_maybe would split (Eq a => a). This is silly, because (=>) is not a tycon in Haskell. Fixed now, but there are some knock-on changes in e.g. TrieMap code and in the canonicaliser. * New function anyFreeVarsOf{Type,Co} to check whether a free variable satisfies a certain predicate. * Type synonyms now remember whether or not they are "forgetful"; a forgetful synonym drops at least one argument. This is useful when flattening; see flattenView. * The pattern-match completeness checker invokes the solver. This invocation might need to look through newtypes when checking representational equality. Thus, the desugarer needs to keep track of the in-scope variables to know what newtype constructors are in scope. I bet this bug was around before but never noticed. * Extra-constraints wildcards are no longer simplified before printing. See Note [Do not simplify ConstraintHoles] in GHC.Tc.Solver. * Whether or not there are Given equalities has become slightly subtler. See the new HasGivenEqs datatype. * Note [Type variable cycles in Givens] in GHC.Tc.Solver.Canonical explains a significant new wrinkle in the new approach. * See Note [What might match later?] in GHC.Tc.Solver.Interact, which explains the fix to #18910. * The inert_count field of InertCans wasn't actually used, so I removed it. Though I (Richard) did the implementation, Simon PJ was very involved in design and review. This updates the Haddock submodule to avoid #18932 by adding a type signature. ------------------------- Metric Decrease: T12227 T5030 T9872a T9872b T9872c Metric Increase: T9872d -------------------------
* Name (tc)SplitForAll- functions more consistentlyRyan Scott2020-11-151-3/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | There is a zoo of `splitForAll-` functions in `GHC.Core.Type` (as well as `tcSplitForAll-` functions in `GHC.Tc.Utils.TcType`) that all do very similar things, but vary in the particular form of type variable that they return. To make things worse, the names of these functions are often quite misleading. Some particularly egregious examples: * `splitForAllTys` returns `TyCoVar`s, but `splitSomeForAllTys` returns `VarBndr`s. * `splitSomeForAllTys` returns `VarBndr`s, but `tcSplitSomeForAllTys` returns `TyVar`s. * `splitForAllTys` returns `TyCoVar`s, but `splitForAllTysInvis` returns `InvisTVBinder`s. (This in particular arose in the context of #18939, and this finally motivated me to bite the bullet and improve the status quo vis-à-vis how we name these functions.) In an attempt to bring some sanity to how these functions are named, I have opted to rename most of these functions en masse to use consistent suffixes that describe the particular form of type variable that each function returns. In concrete terms, this amounts to: * Functions that return a `TyVar` now use the suffix `-TyVar`. This caused the following functions to be renamed: * `splitTyVarForAllTys` -> `splitForAllTyVars` * `splitForAllTy_ty_maybe` -> `splitForAllTyVar_maybe` * `tcSplitForAllTys` -> `tcSplitForAllTyVars` * `tcSplitSomeForAllTys` -> `tcSplitSomeForAllTyVars` * Functions that return a `CoVar` now use the suffix `-CoVar`. This caused the following functions to be renamed: * `splitForAllTy_co_maybe` -> `splitForAllCoVar_maybe` * Functions that return a `TyCoVar` now use the suffix `-TyCoVar`. This caused the following functions to be renamed: * `splitForAllTy` -> `splitForAllTyCoVar` * `splitForAllTys` -> `splitForAllTyCoVars` * `splitForAllTys'` -> `splitForAllTyCoVars'` * `splitForAllTy_maybe` -> `splitForAllTyCoVar_maybe` * Functions that return a `VarBndr` now use the suffix corresponding to the most relevant type synonym. This caused the following functions to be renamed: * `splitForAllVarBndrs` -> `splitForAllTyCoVarBinders` * `splitForAllTysInvis` -> `splitForAllInvisTVBinders` * `splitForAllTysReq` -> `splitForAllReqTVBinders` * `splitSomeForAllTys` -> `splitSomeForAllTyCoVarBndrs` * `tcSplitForAllVarBndrs` -> `tcSplitForAllTyVarBinders` * `tcSplitForAllTysInvis` -> `tcSplitForAllInvisTVBinders` * `tcSplitForAllTysReq` -> `tcSplitForAllReqTVBinders` * `tcSplitForAllTy_maybe` -> `tcSplitForAllTyVarBinder_maybe` Note that I left the following functions alone: * Functions that split apart things besides `ForAllTy`s, such as `splitFunTys` or `splitPiTys`. Thankfully, there are far fewer of these functions than there are functions that split apart `ForAllTy`s, so there isn't much of a pressing need to apply the new naming convention elsewhere. * Functions that split apart `ForAllCo`s in `Coercion`s, such as `GHC.Core.Coercion.splitForAllCo_maybe`. We could theoretically apply the new naming convention here, but then we'd have to figure out how to disambiguate `Type`-splitting functions from `Coercion`-splitting functions. Ultimately, the `Coercion`-splitting functions aren't used nearly as much as the `Type`-splitting functions, so I decided to leave the former alone. This is purely refactoring and should cause no change in behavior.
* Replace HsImplicitBndrs with HsOuterTyVarBndrsRyan Scott2020-11-061-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This refactors the GHC AST to remove `HsImplicitBndrs` and replace it with `HsOuterTyVarBndrs`, a type which records whether the outermost quantification in a type is explicit (i.e., with an outermost, invisible `forall`) or implicit. As a result of this refactoring, it is now evident in the AST where the `forall`-or-nothing rule applies: it's all the places that use `HsOuterTyVarBndrs`. See the revamped `Note [forall-or-nothing rule]` in `GHC.Hs.Type` (previously in `GHC.Rename.HsType`). Moreover, the places where `ScopedTypeVariables` brings lexically scoped type variables into scope are a subset of the places that adhere to the `forall`-or-nothing rule, so this also makes places that interact with `ScopedTypeVariables` easier to find. See the revamped `Note [Lexically scoped type variables]` in `GHC.Hs.Type` (previously in `GHC.Tc.Gen.Sig`). `HsOuterTyVarBndrs` are used in type signatures (see `HsOuterSigTyVarBndrs`) and type family equations (see `HsOuterFamEqnTyVarBndrs`). The main difference between the former and the latter is that the former cares about specificity but the latter does not. There are a number of knock-on consequences: * There is now a dedicated `HsSigType` type, which is the combination of `HsOuterSigTyVarBndrs` and `HsType`. `LHsSigType` is now an alias for an `XRec` of `HsSigType`. * Working out the details led us to a substantial refactoring of the handling of explicit (user-written) and implicit type-variable bindings in `GHC.Tc.Gen.HsType`. Instead of a confusing family of higher order functions, we now have a local data type, `SkolemInfo`, that controls how these binders are kind-checked. It remains very fiddly, not fully satisfying. But it's better than it was. Fixes #16762. Bumps the Haddock submodule. Co-authored-by: Simon Peyton Jones <simonpj@microsoft.com> Co-authored-by: Richard Eisenberg <rae@richarde.dev> Co-authored-by: Zubin Duggal <zubin@cmi.ac.in>
* Make typechecker equality consider visibility in ForAllTysRyan Scott2020-10-311-1/+60
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Previously, `can_eq_nc'` would equate `ForAllTy`s regardless of their `ArgFlag`, including `forall i -> i -> Type` and `forall i. i -> Type`! To fix this, `can_eq_nc'` now uses the `sameVis` function to first check if the `ArgFlag`s are equal modulo specificity. I have also updated `tcEqType`'s implementation to match this behavior. For more explanation on the "modulo specificity" part, see the new `Note [ForAllTy and typechecker equality]` in `GHC.Tc.Solver.Canonical`. While I was in town, I fixed some related documentation issues: * I added `Note [Typechecker equality]` to `GHC.Tc.Utils.TcType` to describe what exactly distinguishes `can_eq_nc'` and `tcEqType` (which implement typechecker equality) from `eqType` (which implements definitional equality, which does not care about the `ArgFlags` of `ForAllTy`s at all). * The User's Guide had some outdated prose on the specified/inferred distinction being different for types and kinds, a holdover from #15079. This is no longer the case on today's GHC, so I removed this prose, added some new prose to take its place, and added a regression test for the programs in #15079. * The User's Guide had some _more_ outdated prose on inferred type variables not being allowed in `default` type signatures for class methods, which is no longer true as of the resolution of #18432. * The related `Note [Deferred Unification]` was being referenced as `Note [Deferred unification]` elsewhere, which made it harder to `grep` for. I decided to change the name of the Note to `Deferred unification` for consistency with the capitalization style used for most other Notes. Fixes #18863.
* Implement Quick Look impredicativitySimon Peyton Jones2020-09-241-5/+17
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This patch implements Quick Look impredicativity (#18126), sticking very closely to the design in A quick look at impredicativity, Serrano et al, ICFP 2020 The main change is that a big chunk of GHC.Tc.Gen.Expr has been extracted to two new modules GHC.Tc.Gen.App GHC.Tc.Gen.Head which deal with typechecking n-ary applications, and the head of such applications, respectively. Both contain a good deal of documentation. Three other loosely-related changes are in this patch: * I implemented (partly by accident) points (2,3)) of the accepted GHC proposal "Clean up printing of foralls", namely https://github.com/ghc-proposals/ghc-proposals/blob/ master/proposals/0179-printing-foralls.rst (see #16320). In particular, see Note [TcRnExprMode] in GHC.Tc.Module - :type instantiates /inferred/, but not /specified/, quantifiers - :type +d instantiates /all/ quantifiers - :type +v is killed off That completes the implementation of the proposal, since point (1) was done in commit df08468113ab46832b7ac0a7311b608d1b418c4d Author: Krzysztof Gogolewski <krzysztof.gogolewski@tweag.io> Date: Mon Feb 3 21:17:11 2020 +0100 Always display inferred variables using braces * HsRecFld (which the renamer introduces for record field selectors), is now preserved by the typechecker, rather than being rewritten back to HsVar. This is more uniform, and turned out to be more convenient in the new scheme of things. * The GHCi debugger uses a non-standard unification that allows the unification variables to unify with polytypes. We used to hack this by using ImpredicativeTypes, but that doesn't work anymore so I introduces RuntimeUnkTv. See Note [RuntimeUnkTv] in GHC.Runtime.Heap.Inspect Updates haddock submodule. WARNING: this patch won't validate on its own. It was too hard to fully disentangle it from the following patch, on type errors and kind generalisation. Changes to tests * Fixes #9730 (test added) * Fixes #7026 (test added) * Fixes most of #8808, except function `g2'` which uses a section (which doesn't play with QL yet -- see #18126) Test added * Fixes #1330. NB Church1.hs subsumes Church2.hs, which is now deleted * Fixes #17332 (test added) * Fixes #4295 * This patch makes typecheck/should_run/T7861 fail. But that turns out to be a pre-existing bug: #18467. So I have just made T7861 into expect_broken(18467)
* Care with implicit-parameter superclassesSimon Peyton Jones2020-09-151-2/+2
| | | | | | | | | | | | | | | | | | | | | | Two bugs, #18627 and #18649, had the same cause: we were not account for the fact that a constaint tuple might hide an implicit parameter. The solution is not hard: look for implicit parameters in superclasses. See Note [Local implicit parameters] in GHC.Core.Predicate. Then we use this new function in two places * The "short-cut solver" in GHC.Tc.Solver.Interact.shortCutSolver which simply didn't handle implicit parameters properly at all. This fixes #18627 * The specialiser, which should not specialise on implicit parameters This fixes #18649 There are some lingering worries (see Note [Local implicit parameters]) but things are much better.
* DynFlags: disentangle OutputableSylvain Henry2020-08-121-0/+1
| | | | | | | | | - put panic related functions into GHC.Utils.Panic - put trace related functions using DynFlags in GHC.Driver.Ppr One step closer making Outputable fully independent of DynFlags. Bump haddock submodule
* Various performance improvementsKrzysztof Gogolewski2020-06-171-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This implements several general performance improvements to GHC, to offset the effect of the linear types change. General optimisations: - Add a `coreFullView` function which iterates `coreView` on the head. This avoids making function recursive solely because the iterate `coreView` themselves. As a consequence, this functions can be inlined, and trigger case-of-known constructor (_e.g._ `kindRep_maybe`, `isLiftedRuntimeRep`, `isMultiplicityTy`, `getTyVar_maybe`, `splitAppTy_maybe`, `splitFunType_maybe`, `tyConAppTyCon_maybe`). The common pattern about all these functions is that they are almost always used as views, and immediately consumed by a case expression. This commit also mark them asx `INLINE`. - In `subst_ty` add a special case for nullary `TyConApp`, which avoid allocations altogether. - Use `mkTyConApp` in `subst_ty` for the general `TyConApp`. This required quite a bit of module shuffling. case. `myTyConApp` enforces crucial sharing, which was lost during substitution. See also !2952 . - Make `subst_ty` stricter. - In `eqType` (specifically, in `nonDetCmpType`), add a special case, tested first, for the very common case of nullary `TyConApp`. `nonDetCmpType` has been made `INLINE` otherwise it is actually a regression. This is similar to the optimisations in !2952. Linear-type specific optimisations: - Use `tyConAppTyCon_maybe` instead of the more complex `eqType` in the definition of the pattern synonyms `One` and `Many`. - Break the `hs-boot` cycles between `Multiplicity.hs` and `Type.hs`: `Multiplicity` now import `Type` normally, rather than from the `hs-boot`. This way `tyConAppTyCon_maybe` can inline properly in the `One` and `Many` pattern synonyms. - Make `updateIdTypeAndMult` strict in its type and multiplicity - The `scaleIdBy` gets a specialised definition rather than being an alias to `scaleVarBy` - `splitFunTy_maybe` is given the type `Type -> Maybe (Mult, Type, Type)` instead of `Type -> Maybe (Scaled Type, Type)` - Remove the `MultMul` pattern synonym in favour of a view `isMultMul` because pattern synonyms appear not to inline well. - in `eqType`, in a `FunTy`, compare multiplicities last: they are almost always both `Many`, so it helps failing faster. - Cache `manyDataConTy` in `mkTyConApp`, to make sure that all the instances of `TyConApp ManyDataConTy []` are physically the same. This commit has been authored by * Richard Eisenberg * Krzysztof Gogolewski * Arnaud Spiwack Metric Decrease: haddock.base T12227 T12545 T12990 T1969 T3064 T5030 T9872b Metric Increase: haddock.base haddock.Cabal haddock.compiler T12150 T12234 T12425 T12707 T13035 T13056 T15164 T16190 T18304 T1969 T3064 T3294 T5631 T5642 T5837 T6048 T9020 T9233 T9675 T9872a T9961 WWRec
* Linear types (#15981)Krzysztof Gogolewski2020-06-171-12/+16
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This is the first step towards implementation of the linear types proposal (https://github.com/ghc-proposals/ghc-proposals/pull/111). It features * A language extension -XLinearTypes * Syntax for linear functions in the surface language * Linearity checking in Core Lint, enabled with -dlinear-core-lint * Core-to-core passes are mostly compatible with linearity * Fields in a data type can be linear or unrestricted; linear fields have multiplicity-polymorphic constructors. If -XLinearTypes is disabled, the GADT syntax defaults to linear fields The following items are not yet supported: * a # m -> b syntax (only prefix FUN is supported for now) * Full multiplicity inference (multiplicities are really only checked) * Decent linearity error messages * Linear let, where, and case expressions in the surface language (each of these currently introduce the unrestricted variant) * Multiplicity-parametric fields * Syntax for annotating lambda-bound or let-bound with a multiplicity * Syntax for non-linear/multiple-field-multiplicity records * Linear projections for records with a single linear field * Linear pattern synonyms * Multiplicity coercions (test LinearPolyType) A high-level description can be found at https://ghc.haskell.org/trac/ghc/wiki/LinearTypes/Implementation Following the link above you will find a description of the changes made to Core. This commit has been authored by * Richard Eisenberg * Krzysztof Gogolewski * Matthew Pickering * Arnaud Spiwack With contributions from: * Mark Barbone * Alexander Vershilov Updates haddock submodule.
* Simple subsumptionwip/T17775Simon Peyton Jones2020-06-051-45/+67
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This patch simplifies GHC to use simple subsumption. Ticket #17775 Implements GHC proposal #287 https://github.com/ghc-proposals/ghc-proposals/blob/master/ proposals/0287-simplify-subsumption.rst All the motivation is described there; I will not repeat it here. The implementation payload: * tcSubType and friends become noticably simpler, because it no longer uses eta-expansion when checking subsumption. * No deeplyInstantiate or deeplySkolemise That in turn means that some tests fail, by design; they can all be fixed by eta expansion. There is a list of such changes below. Implementing the patch led me into a variety of sticky corners, so the patch includes several othe changes, some quite significant: * I made String wired-in, so that "foo" :: String rather than "foo" :: [Char] This improves error messages, and fixes #15679 * The pattern match checker relies on knowing about in-scope equality constraints, andd adds them to the desugarer's environment using addTyCsDs. But the co_fn in a FunBind was missed, and for some reason simple-subsumption ends up with dictionaries there. So I added a call to addTyCsDs. This is really part of #18049. * I moved the ic_telescope field out of Implication and into ForAllSkol instead. This is a nice win; just expresses the code much better. * There was a bug in GHC.Tc.TyCl.Instance.tcDataFamInstHeader. We called checkDataKindSig inside tc_kind_sig, /before/ solveEqualities and zonking. Obviously wrong, easily fixed. * solveLocalEqualitiesX: there was a whole mess in here, around failing fast enough. I discovered a bad latent bug where we could successfully kind-check a type signature, and use it, but have unsolved constraints that could fill in coercion holes in that signature -- aargh. It's all explained in Note [Failure in local type signatures] in GHC.Tc.Solver. Much better now. * I fixed a serious bug in anonymous type holes. IN f :: Int -> (forall a. a -> _) -> Int that "_" should be a unification variable at the /outer/ level; it cannot be instantiated to 'a'. This was plain wrong. New fields mode_lvl and mode_holes in TcTyMode, and auxiliary data type GHC.Tc.Gen.HsType.HoleMode. This fixes #16292, but makes no progress towards the more ambitious #16082 * I got sucked into an enormous refactoring of the reporting of equality errors in GHC.Tc.Errors, especially in mkEqErr1 mkTyVarEqErr misMatchMsg misMatchMsgOrCND In particular, the very tricky mkExpectedActualMsg function is gone. It took me a full day. But the result is far easier to understand. (Still not easy!) This led to various minor improvements in error output, and an enormous number of test-case error wibbles. One particular point: for occurs-check errors I now just say Can't match 'a' against '[a]' rather than using the intimidating language of "occurs check". * Pretty-printing AbsBinds Tests review * Eta expansions T11305: one eta expansion T12082: one eta expansion (undefined) T13585a: one eta expansion T3102: one eta expansion T3692: two eta expansions (tricky) T2239: two eta expansions T16473: one eta determ004: two eta expansions (undefined) annfail06: two eta (undefined) T17923: four eta expansions (a strange program indeed!) tcrun035: one eta expansion * Ambiguity check at higher rank. Now that we have simple subsumption, a type like f :: (forall a. Eq a => Int) -> Int is no longer ambiguous, because we could write g :: (forall a. Eq a => Int) -> Int g = f and it'd typecheck just fine. But f's type is a bit suspicious, and we might want to consider making the ambiguity check do a check on each sub-term. Meanwhile, these tests are accepted, whereas they were previously rejected as ambiguous: T7220a T15438 T10503 T9222 * Some more interesting error message wibbles T13381: Fine: one error (Int ~ Exp Int) rather than two (Int ~ Exp Int, Exp Int ~ Int) T9834: Small change in error (improvement) T10619: Improved T2414: Small change, due to order of unification, fine T2534: A very simple case in which a change of unification order means we get tow unsolved constraints instead of one tc211: bizarre impredicative tests; just accept this for now Updates Cabal and haddock submodules. Metric Increase: T12150 T12234 T5837 haddock.base Metric Decrease: haddock.compiler haddock.Cabal haddock.base Merge note: This appears to break the `UnliftedNewtypesDifficultUnification` test. It has been marked as broken in the interest of merging. (cherry picked from commit 66b7b195cb3dce93ed5078b80bf568efae904cc5)
* Rename GHC.Hs.Types into GHC.Hs.TypeSylvain Henry2020-05-241-1/+1
| | | | See discussion in https://gitlab.haskell.org/ghc/ghc/issues/13009#note_268610
* Refactor hole constraints.Richard Eisenberg2020-05-061-17/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Previously, holes (both expression holes / out of scope variables and partial-type-signature wildcards) were emitted as *constraints* via the CHoleCan constructor. While this worked fine for error reporting, there was a fair amount of faff in keeping these constraints in line. In particular, and unlike other constraints, we could never change a CHoleCan to become CNonCanonical. In addition: * the "predicate" of a CHoleCan constraint was really the type of the hole, which is not a predicate at all * type-level holes (partial type signature wildcards) carried evidence, which was never used * tcNormalise (used in the pattern-match checker) had to create a hole constraint just to extract it again; it was quite messy The new approach is to record holes directly in WantedConstraints. It flows much more nicely now. Along the way, I did some cleaning up of commentary in GHC.Tc.Errors.Hole, which I had a hard time understanding. This was instigated by a future patch that will refactor the way predicates are handled. The fact that CHoleCan's "predicate" wasn't really a predicate is incompatible with that future patch. No test case, because this is meant to be purely internal. It turns out that this change improves the performance of the pattern-match checker, likely because fewer constraints are sloshing about in tcNormalise. I have not investigated deeply, but an improvement is not a surprise here: ------------------------- Metric Decrease: PmSeriesG -------------------------
View Lorry Controller Status