-- (c) The University of Glasgow 2006 {-# LANGUAGE ScopedTypeVariables, PatternSynonyms, MultiWayIf #-} {-# LANGUAGE DeriveFunctor #-} module GHC.Core.Unify ( tcMatchTy, tcMatchTyKi, tcMatchTys, tcMatchTyKis, tcMatchTyX, tcMatchTysX, tcMatchTyKisX, tcMatchTyX_BM, ruleMatchTyKiX, -- Side-effect free unification tcUnifyTy, tcUnifyTys, tcUnifyFunDeps, tcUnifyDebugger, tcUnifyTysFG, tcUnifyTyForInjectivity, BindTvFun, BindFamFun, BindFlag(..), matchBindTv, alwaysBindTv, alwaysBindFam, dontCareBindFam, UnifyResult, UnifyResultM(..), MaybeApartReason(..), typesCantMatch, typesAreApart, -- Matching a type against a lifted type (coercion) liftCoMatch ) where import GHC.Prelude import GHC.Types.Var import GHC.Types.Var.Env import GHC.Types.Var.Set import GHC.Builtin.Names( tYPETyConKey, cONSTRAINTTyConKey ) import GHC.Core.Type hiding ( getTvSubstEnv ) import GHC.Core.Coercion hiding ( getCvSubstEnv ) import GHC.Core.Predicate( scopedSort ) import GHC.Core.TyCon import GHC.Core.Predicate( CanEqLHS(..), canEqLHS_maybe ) import GHC.Core.TyCon.Env import GHC.Core.TyCo.Rep import GHC.Core.TyCo.Compare ( eqType, tcEqType, tcEqTyConAppArgs ) import GHC.Core.TyCo.FVs ( tyCoVarsOfCoList, tyCoFVsOfTypes ) import GHC.Core.TyCo.Subst ( mkTvSubst ) import GHC.Core.Map.Type import GHC.Core.Multiplicity import GHC.Utils.FV( FV, fvVarList ) import GHC.Utils.Misc import GHC.Utils.Outputable import GHC.Types.Basic( SwapFlag(..) ) import GHC.Types.Unique.FM import GHC.Exts( oneShot ) import GHC.Utils.Panic import GHC.Data.Pair import GHC.Data.TrieMap import GHC.Data.Maybe( orElse ) import Control.Monad import qualified Data.Semigroup as S import GHC.Builtin.Types.Prim (fUNTyCon) {- Note [The Core unifier] ~~~~~~~~~~~~~~~~~~~~~~~~~~ This module contains the (pure) unifier two types. It is subtle in a number of ways. Here we summarise, but see Note [Specification of unification]. (CU1) It creates a substition only for "bindable" or "template" type variables. These are identified by a `um_bind_tv_fun` function passed down in the `UMEnv` environment. (CU2) We want to match in the presence of foralls; e.g (forall a. t1) ~ (forall b. t2) That is what the `um_rn_env :: RnEnv2` field of `UMEnv` is for; it does the alpha-renaming that makes it as if `a` and `b` were the same variable. Initialising the `RnEnv2`, so that it can generate a fresh binder when necessary, entails knowing the free variables of both types. Of course, we must be careful not to bind a template type variable to a locally bound variable. E.g. (forall a. x) ~ (forall b. b) where `x` is the template type variable. Then we do not want to bind `x` to a/b! See `mentionsForAllBoundTyVarsL/R`. (CU3) We want to take special care for type families. See the big Note [Apartness and type families] (CU4) Rather than returning just "unifiable" or "not-unifiable" we do "fine-grained" unification (hence "fg" or "FG" in this module) returning three possiblities, captured in `UnifyResult`: - Unifiable subst : certainly unifiable with this type substitution - SurelyApart : cannot be unifiable, regardless of how type familes reduce - MaybeApart : neither of the above See Note [Unification result]. Four reasons for MaybeApart (see `MaybeApartReason`). The first two are the big ones! * MARTypeFamily: Family reduction might make the two types equal Maybe (F Int) ~ Maybe Bool See Note [Apartness and type families] * MARInfinite (occurs check): See Note [Infinitary substitutions] * MARTypeVsConstraint: See Note [Type and Constraint are not apart] in GHC.Builtin.Types.Prim * MARCast (obscure): See (KCU2) in Note [Kind coercions in Unify] (CU5) We need to take care with kinds. See Note [tcMatchTy vs tcMatchTyKi] (CU6) The "unifier" can also do /matching/, governed by `um_unif :: AmIUnifying`. When matching, the LHS and RHS namespaces are unrelated. In particular, the bindable type variable can occur (unrelatedly) in the RHS. E.g. match (a,Maybe a) ~ ([a], Maybe [a]) We get the substitution [a :-> [a]], without confusing the LHS `a` with the RHS `a`. The substitition is "one-shot", and should not be iterated. Note [Infinitary substitutions] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Do the types (x, x) and ([y], y) unify? The answer is seemingly "no" -- no substitution to finite types makes these match. This is the famous "occurs check". But, a substitution to *infinite* types can unify these two types: [x |-> [[...]]], y |-> [[[...]]] ]. Why do we care? Consider these two type family instances: type instance F x x = Int type instance F [y] y = Bool If we also have type instance Looper = [Looper] then the instances potentially overlap -- they are not "apart". So we must distinguish failure-to-unify from definitely-apart. The solution is to use unification over infinite terms. This is possible (see [1] for lots of gory details), but a full algorithm is a little more powerful than we need. Instead, we make a conservative approximation and just omit the occurs check. [1]: http://research.microsoft.com/en-us/um/people/simonpj/papers/ext-f/axioms-extended.pdf tcUnifyTys considers an occurs-check problem as the same as general unification failure. See also #8162. It's worth noting that unification in the presence of infinite types is not complete. This means that, sometimes, a closed type family does not reduce when it should. See test case indexed-types/should_fail/Overlap15 for an example. Note [tcMatchTy vs tcMatchTyKi] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ This module offers two variants of matching: with kinds and without. The TyKi variant takes two types, of potentially different kinds, and matches them. Along the way, it necessarily also matches their kinds. The Ty variant instead assumes that the kinds are already eqType and so skips matching up the kinds. How do you choose between them? 1. If you know that the kinds of the two types are eqType, use the Ty variant. It is more efficient, as it does less work. 2. If the kinds of variables in the template type might mention type families, use the Ty variant (and do other work to make sure the kinds work out). These pure unification functions do a straightforward syntactic unification and do no complex reasoning about type families. Note that the types of the variables in instances can indeed mention type families, so instance lookup must use the Ty variant. (Nothing goes terribly wrong -- no panics -- if there might be type families in kinds in the TyKi variant. You just might get match failure even though a reducing a type family would lead to success.) 3. Otherwise, if you're sure that the variable kinds do not mention type families and you're not already sure that the kind of the template equals the kind of the target, then use the TyKi version. Note [Unification result] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ See `UnifyResult` and `UnifyResultM`. When unifying t1 ~ t2, we return * Unifiable s, if s is a substitution such that s(t1) is syntactically the same as s(t2), modulo type-synonym expansion. * SurelyApart, if there is no substitution s such that s(t1) = s(t2), where "=" includes type-family reductions. * MaybeApart mar s, when we aren't sure. `mar` is a MaybeApartReason. Examples * [a] ~ Maybe b: SurelyApart, because [] and Maybe can't unify * [(a,Int)] ~ [(Bool,b)]: Unifiable * [F Int] ~ [Bool]: MaybeApart MARTypeFamily, because F Int might reduce to Bool (the unifier does not try this) * a ~ Maybe a: MaybeApart MARInfinite. Not Unifiable clearly, but not SurelyApart either; consider a := Loop where type family Loop where Loop = Maybe Loop Wrinkle (UR1): see `combineMAR` There is the possibility that two types are MaybeApart for *both* reasons: * (a, F Int) ~ (Maybe a, Bool) What reason should we use? The *only* consumer of the reason is described in Note [Infinitary substitution in lookup] in GHC.Core.InstEnv. The goal there is identify which instances might match a target later (but don't match now) -- except that we want to ignore the possibility of infinitary substitutions. So let's examine a concrete scenario: class C a b c instance C a (Maybe a) Bool -- other instances, including one that will actually match [W] C b b (F Int) Do we want the instance as a future possibility? No. The only way that instance can match is in the presence of an infinite type (infinitely nested Maybes). We thus say that `MARInfinite` takes precedence, so that InstEnv treats this case as an infinitary substitution case; the fact that a type family is involved is only incidental. We thus define `combineMAR` to prefer `MARInfinite`. Note [Apartness and type families] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Consider this: type family F a b where F Int Bool = Char F a b = Double type family G a -- open, no instances How do we reduce (F (G Float) (G Float))? The first equation clearly doesn't match immediately while the second equation does. But, before reducing, we must make sure that the target can never become (F Int Bool). Well, no matter what G Float becomes, it certainly won't become *both* Int and Bool, so indeed we're safe reducing (F (G Float) (G Float)) to Double. So we must say that the argument list (G Float) (G Float) is SurelyApart from Int Bool This is necessary not only to get more reductions (which we might be willing to give up on), but for /substitutivity/. If we have (F x x), we can see that (F x x) can reduce to Double. So, it had better be the case that (F blah blah) can reduce to Double, no matter what (blah) is! To achieve this, `go` in `uVarOrFam` does this; * We maintain /two/ substitutions, not just one: * um_tv_env: the regular substitution, mapping TyVar :-> Type * um_fam_env: maps (TyCon,[Type]) :-> Type, where the LHS is a type-fam application In effect, these constitute one substitution mapping CanEqLHS :-> Types * When we attempt to unify (G Float) ~ Int, we return MaybeApart.. but we /also/ add a "family substitution" [G Float :-> Int], to `um_fam_env`. See the `BindMe` case of `go` in `uVarOrFam`. * When we later encounter (G Float) ~ Bool, we apply the family substitution, very much as we apply the conventional [tyvar :-> type] substitution when we encounter a type variable. See the `lookupFamEnv` in `go` in `uVarOrFam`. So (G Float ~ Bool) becomes (Int ~ Bool) which is SurelyApart. Bingo. Wrinkles (ATF0) Once we encounter a type-family application, we only ever return MaybeApart or SurelyApart but never `Unifiable`. Accordingly, we only return a TyCoVar substitution from `tcUnifyTys` and friends; we don't return a type-family substitution as well. (We could imagine doing so, though.) (ATF1) Exactly the same mechanism is used in class-instance checking. If we have instance C (Maybe b) instance {-# OVERLAPPING #-} C (Maybe Bool) [W] C (Maybe (F a)) we want to know that the second instance might match later, when we know more about `a`. The function `GHC.Core.InstEnv.instEnvMatchesAndUnifiers` uses `tcUnifyTysFG` to account for type families in the type being matched. (ATF2) A very similar check is made in `GHC.Tc.Utils.Unify.mightEqualLater`, which again uses `tcUnifyTysFG` to account for the possibility of type families. See Note [What might equal later?] in GHC.Tc.Utils.Unify, esp example (10). (ATF3) What about foralls? For example, supppose we are unifying (forall a. F a) -> (forall a. F a) against some other type. Those two (F a) types are unrelated, bound by different foralls; we cannot extend the um_fam_env with a binding [F a :-> blah] So to keep things simple, the entire family-substitution machinery is used only if there are no enclosing foralls (see the `under_forall` check in `uSatFamApp`). That's fine, because the apartness business is used only for reducing type-family applications, and class instances, and their arguments can't have foralls anyway. The bottom line is that we won't discover that (forall a. (a, F Int, F Int)) is surely apart from (forall a. (a, Int, Bool)) but that doesn't matter. Fixing this would be possible, but would require quite a bit of head-scratching. (ATF4) The family substitution only has /saturated/ family applications in its domain. Consider the following concrete example from #16995: type family Param :: Type -> Type -- arity 0 type family LookupParam (a :: Type) :: Type where LookupParam (f Char) = Bool LookupParam x = Int foo :: LookupParam (Param ()) foo = 42 In order for `foo` to typecheck, `LookupParam (Param ())` must reduce to `Int`. So (f Char) ~ (Param ()) must be SurelyApart. Remember, since `Param` is a nullary type family, it is over-saturated in (Param ()). This unification will only be SurelyApart if we decompose the outer AppTy separately, to then give (() ~ Char). Not only does this allow more programs to be accepted, it's also important for correctness. Not doing this was the root cause of the Core Lint error in #16995. (ATF5) Consider instance (Generic1 f, Ord (Rep1 f a)) => Ord (Generically1 f a) where ... -- The "..." gives rise to [W] Ord (Generically1 f a) where Rep1 is a type family. We must use the instance decl (recursively) to simplify the [W] constraint; we do /not/ want to worry that the `[G] Ord (Rep1 f a)` might be an alternative path. So `noMatchableGivenDicts` must return False; so `mightMatchLater` must return False; so when um_bind_fam_fun returns `DontBindMe`, the unifier must return `SurelyApart`, not `MaybeApart`. See `go` in `uVarOrFam` This looks a bit sketchy, because they aren't SurelyApart, but see Note [What might equal later?] in GHC.Tc.Utils.Unify, esp "Red Herring". If we are under a forall, we return `MaybeApart`; that seems more conservative, and class constraints are on tau-types so it doesn't matter. (ATF6) When /matching/ can we ever have a type-family application on the LHS, in the template? You might think not, because type-class-instance and type-family-instance heads can't include type families. E.g. instance C (F a) where ... -- Illegal But you'd be wrong: even when matching, we can see type families in the LHS template: * In `checkValidClass`, in `check_dm` we check that the default method has the right type, using matching, both ways. And that type may have type-family applications in it. Examples in test CoOpt_Singletons and T26457. * In the specialiser: see the call to `tcMatchTy` in `GHC.Core.Opt.Specialise.beats_or_same` * With -fpolymorphic-specialisation, we might get a specialiation rule like RULE forall a (d :: Eq (Maybe (F a))) . f @(Maybe (F a)) d = ... See #25965. * A user-written RULE could conceivably have a type-family application in the template. It might not be a good rule, but I don't think we currently check for this. In all these cases we are only interested in finding a substitution /for type variables/ that makes the match work. So we simply want to recurse into the arguments of the type family. E.g. Template: forall a. Maybe (F a) Target: Maybe (F Int) We want to succeed with substitution [a :-> Int]. See (ATF9). Conclusion: where we enter via `tcMatchTy`, `tcMatchTys`, `tc_match_tys`, etc, we always end up in `tc_match_tys_x`. There we invoke the unifier but we do not distinguish between `SurelyApart` and `MaybeApart`. So in these cases we can set `um_bind_fam_fun` to `neverBindFam`. (ATF7) There is one other, very special case of matching where we /do/ want to bind type families in `um_fam_env`, namely in GHC.Tc.Solver.Equality, the call to `tcUnifyTyForInjectivity False` in `improve_injective_wanted_top`. Consider of a match. Consider type family G6 a = r | r -> a type instance G6 [a] = [G a] type instance G6 Bool = Int and suppose we have a Wanted constraint [W] G6 alpha ~ [Int] According to Section 5.2 of "Injective type families for Haskell", we /match/ the RHS each of type instance with [Int]. So we try Template: [G a] Target: [Int] and we want to succeed with MaybeApart, so that we can generate the improvement constraint [W] alpha ~ [beta] where beta is fresh. We do this by binding [G a :-> Int] (ATF8) The treatment of type families is governed by um_bind_fam_fun :: BindFamFun in UMEnv, where type BindFamFun = TyCon -> [Type] -> Type -> BindFlag There are some simple BindFamFun functions provided: alwaysBindFam do the clever stuff above neverBindFam treat type families as SurelyApart dontCareBindFam type families shouldn't exist at all This function only affects the difference between the results MaybeApart and SurelyApart; it never does not affect whether or not we return Unifiable. (ATF9) Decomposition. Consider unifying F a ~ F Int when `um_bind_fam_fun` says DontBindMe. There is a unifying substitition [a :-> Int], and we want to find it, returning Unifiable. Why? - Remember, this is the Core unifier -- we are not doing type inference - When we have two equal types, like F a ~ F a, it is ridiculous to say that they are MaybeApart. Example: the two-way tcMatchTy in `checkValidClass` and #26457. (ATF9-1) But consider unifying F Int ~ F Bool Although Int and Bool are SurelyApart, we must return MaybeApart for the outer unification. Hence the use of `don'tBeSoSure` in `go_fam_fam`; it leaves Unifiable alone, but weakens `SurelyApart` to `MaybeApart`. (ATF9-2) We want this decomposition to occur even under a forall (this was #26457). E.g. (forall a. F Int) -> Int ~ (forall a. F Int) ~ Int (ATF10) Injectivity. Consider (AFT9) where F is known to be injective. Then if we are unifying F Int ~ F Bool we /can/ say SurelyApart. See the inj/noninj stuff in `go_fam_fam`. (ATF11) Consider unifying [F Int, F Int, F Bool] ~ [F Bool, Char, Double] We find (F Int ~ F Bool), so we can decompose. But we /also/ want to remember the substitution [F Int :-> F Bool]. Then from (F Int ~ Char) we get the substitution [F Bool :-> Char]. And that flat-out contradicts (F Bool ~ Double) so we should get SurelyApart. Key point: when decomposing (F tys1 ~ F tys2), we should /also/ extend the type-family substitution. (ATF11-1) All this cleverness only matters when unifying, not when matching (ATF12) There is a horrid exception for the injectivity check. See (UR1) in in Note [Specification of unification]. (ATF13) We have to be careful about the occurs check. See Note [The occurs check in the Core unifier] SIDE NOTE. The paper "Closed type families with overlapping equations" http://research.microsoft.com/en-us/um/people/simonpj/papers/ext-f/axioms-extended.pdf tries to achieve the same effect with a standard yes/no unifier, by "flattening" the types (replacing each type-family application with a fresh type variable) and then unifying. But that does not work well. Consider (#25657) type MyEq :: k -> k -> Bool type family MyEq a b where MyEq a a = 'True MyEq _ _ = 'False type Var :: forall {k}. Tag -> k type family Var tag = a | a -> tag Then, because Var is injective, we want MyEq (Var A) (Var B) --> False MyEq (Var A) (Var A) --> True But if we flattten the types (Var A) and (Var B) we'll just get fresh type variables, and all is lost. But with the current algorithm we have that a a ~ (Var A) (Var B) is SurelyApart, so the first equation definitely doesn't match and we can try the second, which does. END OF SIDE NOTE. Note [Shortcomings of the apartness test] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Note [Apartness and type families] is very clever. But it still has shortcomings (#26358). Consider unifying [F a, F Int, Int] ~ [Bool, Char, a] Working left to right you might think we would build the mapping F a :-> Bool F Int :-> Char Now we discover that `a` unifies with `Int`. So really these two lists are Apart because F Int can't be both Bool and Char. Just the same applies when adding a type-family binding to um_fam_env: [F (G Float), F Int, G Float] ~ [Bool, Char, Iont] Again these are Apart, because (G Float = Int), and (F Int) can't be both Bool and Char But achieving this is very tricky! Perhaps whenever we unify a type variable, or a type family, we should run it over the domain and (maybe range) of the type-family mapping too? Sigh. For now we make no such attempt. * The um_fam_env has only /un-substituted/ types. * We look up only /un-substituted/ types in um_fam_env This may make us say MaybeApart when we could say SurelyApart, but it has no effect on the correctness of unification: if we return Unifiable, it really is Unifiable. This is all quite subtle. suppose we have: um_tv_env: c :-> b um_fam_env F b :-> a and we are trying to add a :-> F c. We will call lookupFamEnv on (F, [c]), which will fail because b and c are not equal. So we go ahead and add a :-> F c as a new tyvar eq, getting: um_tv_env: a :-> F c, c :-> b um_fam_env F b :-> a Does that loop, like this: a --> F c --> F b --> a? No, because we do not substitute (F c) to (F b) and then look up in um_fam_env; we look up only un-substituted types. -} {- ********************************************************************* * * Binding decisions * * ********************************************************************* -} data BindFlag = BindMe -- ^ A bindable type variable | DontBindMe -- ^ Do not bind this type variable is /apart/ -- See also Note [Super skolems: binding when looking up instances] -- in GHC.Core.InstEnv. deriving Eq -- | Some unification functions are parameterised by a 'BindTvFun', which -- says whether or not to allow a certain unification to take place. -- A 'BindTvFun' takes the 'TyVar' involved along with the 'Type' it will -- potentially be bound to. -- -- It is possible for the variable to actually be a coercion variable -- (Note [Matching coercion variables]), but only when one-way matching. -- In this case, the 'Type' will be a 'CoercionTy'. type BindTvFun = TyCoVar -> Type -> BindFlag -- | BindFamFun is similiar to BindTvFun, but deals with a saturated -- type-family application. See Note [Apartness and type families]. type BindFamFun = TyCon -> [Type] -> Type -> BindFlag -- | Allow binding only for any variable in the set. Variables may -- be bound to any type. -- Used when doing simple matching; e.g. can we find a substitution -- -- @ -- S = [a :-> t1, b :-> t2] such that -- S( Maybe (a, b->Int ) = Maybe (Bool, Char -> Int) -- @ matchBindTv :: TyCoVarSet -> BindTvFun matchBindTv tvs tv _ty | tv `elemVarSet` tvs = BindMe | otherwise = DontBindMe -- | Allow the binding of any variable to any type alwaysBindTv :: BindTvFun alwaysBindTv _tv _ty = BindMe -- | Allow the binding of a type-family application to any type alwaysBindFam :: BindFamFun -- See (ATF8) in Note [Apartness and type families] alwaysBindFam _tc _args _rhs = BindMe dontCareBindFam :: HasCallStack => BindFamFun -- See (ATF8) in Note [Apartness and type families] dontCareBindFam tc args rhs = pprPanic "dontCareBindFam" $ vcat [ ppr tc <+> ppr args, text "rhs" <+> ppr rhs ] -- | Don't allow the binding of a type-family application at all neverBindFam :: BindFamFun -- See (ATF8) in Note [Apartness and type families] neverBindFam _tc _args _rhs = DontBindMe {- ********************************************************************* * * Various wrappers for matching * * ********************************************************************* -} -- | @tcMatchTy t1 t2@ produces a substitution (over fvs(t1)) -- @s@ such that @s(t1)@ equals @t2@. -- The returned substitution might bind coercion variables, -- if the variable is an argument to a GADT constructor. -- -- Precondition: typeKind ty1 `eqType` typeKind ty2 -- -- We don't pass in a set of "template variables" to be bound -- by the match, because tcMatchTy (and similar functions) are -- always used on top-level types, so we can bind any of the -- free variables of the LHS. -- See also Note [tcMatchTy vs tcMatchTyKi] tcMatchTy :: HasDebugCallStack => Type -> Type -> Maybe Subst tcMatchTy ty1 ty2 = tcMatchTys [ty1] [ty2] tcMatchTyX_BM :: HasDebugCallStack => BindTvFun -> Subst -> Type -> Type -> Maybe Subst tcMatchTyX_BM bind_tv subst ty1 ty2 = tc_match_tys_x bind_tv False subst [ty1] [ty2] -- | Like 'tcMatchTy', but allows the kinds of the types to differ, -- and thus matches them as well. -- See also Note [tcMatchTy vs tcMatchTyKi] tcMatchTyKi :: HasDebugCallStack => Type -> Type -> Maybe Subst tcMatchTyKi ty1 ty2 = tc_match_tys alwaysBindTv True [ty1] [ty2] -- | This is similar to 'tcMatchTy', but extends a substitution -- See also Note [tcMatchTy vs tcMatchTyKi] tcMatchTyX :: HasDebugCallStack => Subst -- ^ Substitution to extend -> Type -- ^ Template -> Type -- ^ Target -> Maybe Subst tcMatchTyX subst ty1 ty2 = tc_match_tys_x alwaysBindTv False subst [ty1] [ty2] -- | Like 'tcMatchTy' but over a list of types. -- See also Note [tcMatchTy vs tcMatchTyKi] tcMatchTys :: HasDebugCallStack => [Type] -- ^ Template -> [Type] -- ^ Target -> Maybe Subst -- ^ One-shot; in principle the template -- variables could be free in the target -- See (CU6) in Note [The Core unifier] tcMatchTys tys1 tys2 = tc_match_tys alwaysBindTv False tys1 tys2 -- | Like 'tcMatchTyKi' but over a list of types. -- See also Note [tcMatchTy vs tcMatchTyKi] tcMatchTyKis :: HasDebugCallStack => [Type] -- ^ Template -> [Type] -- ^ Target -> Maybe Subst -- ^ One-shot substitution -- See (CU6) in Note [The Core unifier] tcMatchTyKis tys1 tys2 = tc_match_tys alwaysBindTv True tys1 tys2 -- | Like 'tcMatchTys', but extending a substitution -- See also Note [tcMatchTy vs tcMatchTyKi] tcMatchTysX :: HasDebugCallStack => Subst -- ^ Substitution to extend -> [Type] -- ^ Template -> [Type] -- ^ Target -> Maybe Subst -- ^ One-shot substitution tcMatchTysX subst tys1 tys2 = tc_match_tys_x alwaysBindTv False subst tys1 tys2 -- | Like 'tcMatchTyKis', but extending a substitution -- See also Note [tcMatchTy vs tcMatchTyKi] tcMatchTyKisX :: HasDebugCallStack => Subst -- ^ Substitution to extend -> [Type] -- ^ Template -> [Type] -- ^ Target -> Maybe Subst -- ^ One-shot substitution tcMatchTyKisX subst tys1 tys2 = tc_match_tys_x alwaysBindTv True subst tys1 tys2 -- | Same as tc_match_tys_x, but starts with an empty substitution tc_match_tys :: HasDebugCallStack => BindTvFun -> Bool -- ^ match kinds? -> [Type] -> [Type] -> Maybe Subst tc_match_tys bind_me match_kis tys1 tys2 = tc_match_tys_x bind_me match_kis (mkEmptySubst in_scope) tys1 tys2 where in_scope = mkInScopeSet (tyCoVarsOfTypes tys1 `unionVarSet` tyCoVarsOfTypes tys2) -- | Worker for 'tcMatchTysX' and 'tcMatchTyKisX' tc_match_tys_x :: HasDebugCallStack => BindTvFun -> Bool -- ^ match kinds? -> Subst -> [Type] -> [Type] -> Maybe Subst tc_match_tys_x bind_tv match_kis (Subst in_scope id_env tv_env cv_env) tys1 tys2 = case tc_unify_tys neverBindFam -- (ATF7) in Note [Apartness and type families] bind_tv False -- Matching, not unifying False -- Not an injectivity check match_kis RespectMultiplicities (mkRnEnv2 in_scope) tv_env cv_env tys1 tys2 of Unifiable (tv_env', cv_env') -> Just $ Subst in_scope id_env tv_env' cv_env' _ -> Nothing -- | This one is called from the expression matcher, -- which already has a MatchEnv in hand ruleMatchTyKiX :: TyCoVarSet -- ^ template variables -> RnEnv2 -> TvSubstEnv -- ^ type substitution to extend -> Type -- ^ Template -> Type -- ^ Target -> Maybe TvSubstEnv ruleMatchTyKiX tmpl_tvs rn_env tenv tmpl target -- See Note [Kind coercions in Unify] = case tc_unify_tys neverBindFam (matchBindTv tmpl_tvs) -- neverBindFam: a type family probably shouldn't appear -- on the LHS of a RULE, although we don't currently prevent it. -- But even if it did, (ATF8) in Note [Apartness and type families] -- says it doesn't matter becuase here we only care about Unifiable. -- So neverBindFam is efficient, and sufficient. False -- Matching, not unifying False -- No doing an injectivity check True -- Match the kinds IgnoreMultiplicities -- See Note [Rewrite rules ignore multiplicities in FunTy] rn_env tenv emptyCvSubstEnv [tmpl] [target] of Unifiable (tenv', _) -> Just tenv' _ -> Nothing {- ************************************************************************ * * GADTs * * ************************************************************************ Note [Pruning dead case alternatives] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Consider data T a where T1 :: T Int T2 :: T a newtype X = MkX Int newtype Y = MkY Char type family F a type instance F Bool = Int Now consider case x of { T1 -> e1; T2 -> e2 } The question before the house is this: if I know something about the type of x, can I prune away the T1 alternative? Suppose x::T Char. It's impossible to construct a (T Char) using T1, Answer = YES we can prune the T1 branch (clearly) Suppose x::T (F a), where 'a' is in scope. Then 'a' might be instantiated to 'Bool', in which case x::T Int, so ANSWER = NO (clearly) We see here that we want precisely the apartness check implemented within tcUnifyTysFG. So that's what we do! Two types cannot match if they are surely apart. Note that since we are simply dropping dead code, a conservative test suffices. -} -- | Given a list of pairs of types, are any two members of a pair surely -- apart, even after arbitrary type function evaluation and substitution? typesCantMatch :: [(Type,Type)] -> Bool -- See Note [Pruning dead case alternatives] typesCantMatch prs = any (uncurry typesAreApart) prs typesAreApart :: Type -> Type -> Bool typesAreApart t1 t2 = case tcUnifyTysFG alwaysBindFam alwaysBindTv [t1] [t2] of SurelyApart -> True _ -> False {- ************************************************************************ * * Various wrappers for unification * * ********************************************************************* -} -- | Simple unification of two types; all type variables are bindable -- Precondition: the kinds are already equal tcUnifyTy :: Type -> Type -- All tyvars are bindable -> Maybe Subst -- A regular one-shot (idempotent) substitution tcUnifyTy t1 t2 = tcUnifyTys alwaysBindTv [t1] [t2] tcUnifyDebugger :: Type -> Type -> Maybe Subst tcUnifyDebugger t1 t2 = case tc_unify_tys_fg True -- Unify kinds neverBindFam -- Does not affect Unifiable, so pick max efficient -- See (ATF8) in Note [Apartness and type families] alwaysBindTv [t1] [t2] of Unifiable subst -> Just subst _ -> Nothing -- | Like 'tcUnifyTys' but also unifies the kinds tcUnifyFunDeps :: TyCoVarSet -> [Type] -> [Type] -> Maybe Subst tcUnifyFunDeps qtvs tys1 tys2 = case tc_unify_tys_fg True -- Unify kinds dontCareBindFam -- Class-instance heads never mention type families (matchBindTv qtvs) tys1 tys2 of Unifiable subst -> Just subst _ -> Nothing -- | Unify or match a type-family RHS with a type (possibly another type-family RHS) -- Precondition: kinds are the same tcUnifyTyForInjectivity :: AmIUnifying -- ^ True <=> do two-way unification; -- False <=> do one-way matching. -- See end of sec 5.2 from the paper -> InScopeSet -- Should include the free tyvars of both Type args -> Type -> Type -- Types to unify -> Maybe Subst -- This algorithm is an implementation of the "Algorithm U" presented in -- the paper "Injective type families for Haskell", Figures 2 and 3. -- The code is incorporated with the standard unifier for convenience, but -- its operation should match the specification in the paper. tcUnifyTyForInjectivity unif in_scope t1 t2 = case tc_unify_tys alwaysBindFam alwaysBindTv unif -- Am I unifying? True -- Do injectivity checks False -- Don't check outermost kinds RespectMultiplicities rn_env emptyTvSubstEnv emptyCvSubstEnv [t1] [t2] of Unifiable (tv_subst, _cv_subst) -> Just $ maybe_fix tv_subst MaybeApart _reason (tv_subst, _cv_subst) -> Just $ maybe_fix tv_subst -- We want to *succeed* in questionable cases. -- This is a pre-unification algorithm. SurelyApart -> Nothing where rn_env = mkRnEnv2 in_scope maybe_fix | unif = niFixSubst in_scope | otherwise = mkTvSubst in_scope -- when matching, don't confuse -- domain with range ----------------- tcUnifyTys :: BindTvFun -> [Type] -> [Type] -> Maybe Subst -- ^ A regular one-shot (idempotent) substitution -- that unifies the erased types. See comments -- for 'tcUnifyTysFG' -- The two types may have common type variables, and indeed do so in the -- second call to tcUnifyTys in GHC.Tc.Instance.FunDeps.checkClsFD tcUnifyTys bind_fn tys1 tys2 = case tcUnifyTysFG neverBindFam bind_fn tys1 tys2 of Unifiable result -> Just result _ -> Nothing -- | (tcUnifyTysFG bind_fam bind_tv tys1 tys2) does "fine-grain" unification -- of tys1 and tys2, under the control of `bind_fam` and `bind_tv`. -- This version requires that the kinds of the types are the same, -- if you unify left-to-right. -- See Note [The Core unifier] tcUnifyTysFG :: BindFamFun -> BindTvFun -> [Type] -> [Type] -> UnifyResult tcUnifyTysFG bind_fam bind_tv tys1 tys2 = tc_unify_tys_fg False bind_fam bind_tv tys1 tys2 tc_unify_tys_fg :: Bool -> BindFamFun -> BindTvFun -> [Type] -> [Type] -> UnifyResult tc_unify_tys_fg match_kis bind_fam bind_tv tys1 tys2 = do { (tv_env, _) <- tc_unify_tys bind_fam bind_tv True -- Unifying False -- Not doing an injectivity check match_kis -- Match outer kinds RespectMultiplicities rn_env emptyTvSubstEnv emptyCvSubstEnv tys1 tys2 ; return $ niFixSubst in_scope tv_env } where in_scope = mkInScopeSet $ tyCoVarsOfTypes tys1 `unionVarSet` tyCoVarsOfTypes tys2 rn_env = mkRnEnv2 in_scope -- | This function is actually the one to call the unifier -- a little -- too general for outside clients, though. tc_unify_tys :: BindFamFun -> BindTvFun -> AmIUnifying -- ^ True <=> unify; False <=> match -> Bool -- ^ True <=> doing an injectivity check -> Bool -- ^ True <=> treat the kinds as well -> MultiplicityFlag -- ^ see Note [Rewrite rules ignore multiplicities in FunTy] in GHC.Core.Unify -> RnEnv2 -> TvSubstEnv -- ^ substitution to extend -> CvSubstEnv -> [Type] -> [Type] -> UnifyResultM (TvSubstEnv, CvSubstEnv) -- NB: It's tempting to ASSERT here that, if we're not matching kinds, then -- the kinds of the types should be the same. However, this doesn't work, -- as the types may be a dependent telescope, where later types have kinds -- that mention variables occurring earlier in the list of types. Here's an -- example (from typecheck/should_fail/T12709): -- template: [rep :: RuntimeRep, a :: TYPE rep] -- target: [LiftedRep :: RuntimeRep, Int :: TYPE LiftedRep] -- We can see that matching the first pair will make the kinds of the second -- pair equal. Yet, we still don't need a separate pass to unify the kinds -- of these types, so it's appropriate to use the Ty variant of unification. -- See also Note [tcMatchTy vs tcMatchTyKi]. tc_unify_tys bind_fam bind_tv unif inj_check match_kis match_mults rn_env tv_env cv_env tys1 tys2 = initUM tv_env cv_env $ do { when match_kis $ unify_tys env kis1 kis2 ; unify_tys env tys1 tys2 } where env = UMEnv { um_bind_tv_fun = bind_tv , um_bind_fam_fun = bind_fam , um_foralls = emptyVarSet , um_unif = unif , um_inj_tf = inj_check , um_arr_mult = match_mults , um_rn_env = rn_env } kis1 = map typeKind tys1 kis2 = map typeKind tys2 {- ********************************************************************* * * UnifyResult, MaybeApart etc * * ********************************************************************* -} {- Note [Rewrite rules ignore multiplicities in FunTy] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Consider the following (higher-order) rule: m :: Bool -> Bool -> Bool {-# RULES "m" forall f. m (f True) = f #-} let x = m ((,) @Bool @Bool True True) The rewrite rule expects an `f :: Bool -> Bool`, but `(,) @Bool @Bool True :: Bool %1 -> Bool` is linear (see Note [Data constructors are linear by default] in GHC.Core.Multiplicity) Should the rule match? Yes! According to the principles laid out in Note [Linting linearity] in GHC.Core.Lint, optimisation shouldn't be constrained by linearity. However, when matching the template variable `f` to `(,) True`, we do check that their types unify (see Note [Matching variable types] in GHC.Core.Rules). So when unifying types for the sake of rule-matching, the unification algorithm must be able to ignore multiplicities altogether. How is this done? (1) The `um_arr_mult` field of `UMEnv` recordsw when we are doing rule-matching, and hence want to ignore multiplicities. (2) The field is set to True in by `ruleMatchTyKiX`. (3) It is consulted when matching `FunTy` in `unify_ty`. Wrinkle in (3). In `unify_tc_app`, in `unify_ty`, `FunTy` is handled as if it was a regular type constructor. In this case, and when the types being unified are *function* arrows, but not constraint arrows, then the first argument is a multiplicity. We select this situation by comparing the type constructor with fUNTyCon. In this case, and this case only, we can safely drop the first argument (using the tail function) and unify the rest. Note [The substitution in MaybeApart] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ The constructor MaybeApart carries data with it, typically a TvSubstEnv. Why? Because consider unifying these: (a, a, Int) ~ (b, [b], Bool) If we go left-to-right, we start with [a |-> b]. Then, on the middle terms, we apply the subst we have so far and discover that we need [b |-> [b]]. Because this fails the occurs check, we say that the types are MaybeApart (see above Note [Infinitary substitutions]). But, we can't stop there! Because if we continue, we discover that Int is SurelyApart from Bool, and therefore the types are apart. This has practical consequences for the ability for closed type family applications to reduce. See test case indexed-types/should_compile/Overlap14. -} -- This type does double-duty. It is used in the UM (unifier monad) and to -- return the final result. See Note [Unification result] type UnifyResult = UnifyResultM Subst -- | See Note [Unification result] data UnifyResultM a = Unifiable a -- the subst that unifies the types | MaybeApart MaybeApartReason a -- the subst has as much as we know -- it must be part of a most general unifier -- See Note [The substitution in MaybeApart] | SurelyApart deriving Functor -- | Why are two types 'MaybeApart'? 'MARInfinite' takes precedence: -- This is used (only) in Note [Infinitary substitution in lookup] in GHC.Core.InstEnv -- As of Feb 2022, we never differentiate between MARTypeFamily and MARTypeVsConstraint; -- it's really only MARInfinite that's interesting here. data MaybeApartReason = MARTypeFamily -- ^ matching e.g. F Int ~? Bool | MARInfinite -- ^ matching e.g. a ~? Maybe a | MARTypeVsConstraint -- ^ matching Type ~? Constraint or the arrow types -- See Note [Type and Constraint are not apart] in GHC.Builtin.Types.Prim | MARCast -- ^ Very obscure. -- See (KCU2) in Note [Kind coercions in Unify] combineMAR :: MaybeApartReason -> MaybeApartReason -> MaybeApartReason -- See (UR1) in Note [Unification result] for why MARInfinite wins combineMAR MARInfinite _ = MARInfinite -- MARInfinite wins combineMAR MARTypeFamily r = r -- Otherwise it doesn't really matter combineMAR MARTypeVsConstraint r = r combineMAR MARCast r = r instance Outputable MaybeApartReason where ppr MARTypeFamily = text "MARTypeFamily" ppr MARInfinite = text "MARInfinite" ppr MARTypeVsConstraint = text "MARTypeVsConstraint" ppr MARCast = text "MARCast" instance Semigroup MaybeApartReason where (<>) = combineMAR instance Applicative UnifyResultM where pure = Unifiable (<*>) = ap instance Monad UnifyResultM where SurelyApart >>= _ = SurelyApart MaybeApart r1 x >>= f = case f x of Unifiable y -> MaybeApart r1 y MaybeApart r2 y -> MaybeApart (r1 S.<> r2) y SurelyApart -> SurelyApart Unifiable x >>= f = f x instance Outputable a => Outputable (UnifyResultM a) where ppr SurelyApart = text "SurelyApart" ppr (Unifiable x) = text "Unifiable" <+> ppr x ppr (MaybeApart r x) = text "MaybeApart" <+> ppr r <+> ppr x {- ************************************************************************ * * Non-idempotent substitution * * ************************************************************************ Note [Non-idempotent substitution] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ During unification we use a TvSubstEnv/CvSubstEnv pair that is (a) non-idempotent (b) loop-free; ie repeatedly applying it yields a fixed point Note [Finding the substitution fixpoint] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Finding the fixpoint of a non-idempotent substitution arising from a unification is much trickier than it looks, because of kinds. Consider T k (H k (f:k)) ~ T * (g:*) If we unify, we get the substitution [ k -> * , g -> H k (f:k) ] To make it idempotent we don't want to get just [ k -> * , g -> H * (f:k) ] We also want to substitute inside f's kind, to get [ k -> * , g -> H k (f:*) ] If we don't do this, we may apply the substitution to something, and get an ill-formed type, i.e. one where typeKind will fail. This happened, for example, in #9106. It gets worse. In #14164 we wanted to take the fixpoint of this substitution [ xs_asV :-> F a_aY6 (z_aY7 :: a_aY6) (rest_aWF :: G a_aY6 (z_aY7 :: a_aY6)) , a_aY6 :-> a_aXQ ] We have to apply the substitution for a_aY6 two levels deep inside the invocation of F! We don't have a function that recursively applies substitutions inside the kinds of variable occurrences (and probably rightly so). So, we work as follows: 1. Start with the current substitution (which we are trying to fixpoint [ xs :-> F a (z :: a) (rest :: G a (z :: a)) , a :-> b ] 2. Take all the free vars of the range of the substitution: {a, z, rest, b} NB: the free variable finder closes over the kinds of variable occurrences 3. If none are in the domain of the substitution, stop. We have found a fixpoint. 4. Remove the variables that are bound by the substitution, leaving {z, rest, b} 5. Do a topo-sort to put them in dependency order: [ b :: *, z :: a, rest :: G a z ] 6. Apply the substitution left-to-right to the kinds of these tyvars, extending it each time with a new binding, so we finish up with [ xs :-> ..as before.. , a :-> b , b :-> b :: * , z :-> z :: b , rest :-> rest :: G b (z :: b) ] Note that rest now has the right kind 7. Apply this extended substitution (once) to the range of the /original/ substitution. (Note that we do the extended substitution would go on forever if you tried to find its fixpoint, because it maps z to z.) 8. And go back to step 1 In Step 6 we use the free vars from Step 2 as the initial in-scope set, because all of those variables appear in the range of the substitution, so they must all be in the in-scope set. But NB that the type substitution engine does not look up variables in the in-scope set; it is used only to ensure no shadowing. -} niFixSubst :: InScopeSet -> TvSubstEnv -> Subst -- Find the idempotent fixed point of the non-idempotent substitution -- This is surprisingly tricky: -- see Note [Finding the substitution fixpoint] -- ToDo: use laziness instead of iteration? niFixSubst in_scope tenv | not_fixpoint = niFixSubst in_scope (mapVarEnv (substTy subst) tenv) | otherwise = subst where range_fvs :: FV range_fvs = tyCoFVsOfTypes (nonDetEltsUFM tenv) -- It's OK to use nonDetEltsUFM here because the -- order of range_fvs, range_tvs is immaterial range_tvs :: [TyVar] range_tvs = fvVarList range_fvs not_fixpoint = any in_domain range_tvs in_domain tv = tv `elemVarEnv` tenv free_tvs = scopedSort (filterOut in_domain range_tvs) -- See Note [Finding the substitution fixpoint], Step 6 subst = foldl' add_free_tv (mkTvSubst in_scope tenv) free_tvs add_free_tv :: Subst -> TyVar -> Subst add_free_tv subst tv = extendTvSubst subst tv (mkTyVarTy tv') where tv' = updateTyVarKind (substTy subst) tv {- ************************************************************************ * * unify_ty: the main workhorse * * ************************************************************************ Note [Specification of unification] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ The pure unifier, unify_ty, defined in this module, tries to work out a substitution to make two types say True to eqType. NB: eqType is itself not purely syntactic; it accounts for CastTys; see Note [Non-trivial definitional equality] in GHC.Core.TyCo.Rep Unlike the "impure unifiers" in the typechecker (the eager unifier in GHC.Tc.Utils.Unify, and the constraint solver itself in GHC.Tc.Solver.Equality), the pure unifier does /not/ work up to ~. The algorithm implemented here is rather delicate, and we depend on it to uphold certain properties. This is a summary of these required properties. Notation: θ,φ substitutions ξ type-function-free types τ,σ other types τ♭ type τ, flattened ≡ eqType (U1) Soundness. If (unify τ₁ τ₂) = Unifiable θ, then θ(τ₁) ≡ θ(τ₂). θ is a most general unifier for τ₁ and τ₂. (U2) Completeness. If (unify ξ₁ ξ₂) = SurelyApart, then there exists no substitution θ such that θ(ξ₁) ≡ θ(ξ₂). These two properties are stated as Property 11 in the "Closed Type Families" paper (POPL'14). Below, this paper is called [CTF]. (U3) Apartness under substitution. If (unify ξ τ♭) = SurelyApart, then (unify ξ θ(τ)♭) = SurelyApart, for any θ. (Property 12 from [CTF]) (U4) Apart types do not unify. If (unify ξ τ♭) = SurelyApart, then there exists no θ such that θ(ξ) = θ(τ). (Property 13 from [CTF]) THEOREM. Completeness w.r.t ~ If (unify τ₁♭ τ₂♭) = SurelyApart, then there exists no proof that (τ₁ ~ τ₂). PROOF. See appendix of [CTF]. The unification algorithm is used for type family injectivity, as described in the "Injective Type Families" paper (Haskell'15), called [ITF]. When run in this mode, it has the following properties. (I1) If (unify σ τ) = SurelyApart, then σ and τ are not unifiable, even after arbitrary type family reductions. (I2) If (unify σ τ) = MaybeApart θ, and if some φ exists such that φ(σ) ~ φ(τ), then φ extends θ. Furthermore, the RULES matching algorithm requires this property, but only when using this algorithm for matching: (M1) If (match σ τ) succeeds with θ, then all matchable tyvars in σ are bound in θ. Property M1 means that we must extend the substitution with, say (a ↦ a) when appropriate during matching. See also Note [Self-substitution when unifying or matching]. (M2) Completeness of matching. If θ(σ) = τ, then (match σ τ) = Unifiable φ, where θ is an extension of φ. Wrinkle (SI1): um_inj_tf: Sadly, property M2 and I2 conflict. Consider type family F1 a b where F1 Int Bool = Char F1 Double String = Char Consider now two matching problems: P1. match (F1 a Bool) (F1 Int Bool) P2. match (F1 a Bool) (F1 Double String) In case P1, we must find (a ↦ Int) to satisfy M2. In case P2, we must /not/ find (a ↦ Double), in order to satisfy I2. (Note that the correct mapping for I2 is (a ↦ Int). There is no way to discover this, but we mustn't map a to anything else!) We thus must parameterize the algorithm over whether it's being used for an injectivity check (refrain from looking at non-injective arguments to type families) or not (do indeed look at those arguments). This is implemented by the um_inj_tf field of UMEnv. (It's all a question of whether or not to include equation (7) from Fig. 2 of [ITF].) This extra parameter is a bit fiddly, perhaps, but seemingly less so than having two separate, almost-identical algorithms. Note [Self-substitution when unifying or matching] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ What happens when we are unifying or matching two identical type variables? a ~ a * When /unifying/, just succeed, without binding [a :-> a] in the substitution, else we'd get an infinite substitution. We need to make this check before we do the occurs check, of course. * When /matching/, and `a` is a bindable variable from the template, we /do/ want to extend the substitution. Remember, a successful match should map all the template variables (except ones that disappear when expanding synonyms), But when `a` is /not/ a bindable variable (perhaps it is a globally-in-scope skolem) we want to treat it like a constant `Int ~ Int` and succeed. Notice: no occurs check! It's fine to match (a ~ Maybe a), because the template vars of the template come from a different name space to the free vars of the target. Note that this arrangement was provoked by a real failure, where the same unique ended up in the template as in the target. (It was a rule firing when compiling Data.List.NonEmpty.) * What about matching a /non-bindable/ variable? For example: template-vars : {a} matching problem: (forall b. b -> a) ~ (forall c. c -> Int) We want to emerge with the substitution [a :-> Int] But on the way we will encounter (b ~ b), when we match the bits before the arrow under the forall, having renamed `c` to `b`. This match should just succeed, just like (Int ~ Int), without extending the substitution. It's important to do this for /non-bindable/ variables, not just for forall-bound ones. In an associated type instance C (Maybe a) where { type F (Maybe a) = Int } `checkConsistentFamInst` matches (Maybe a) from the header against (Maybe a) from the type-family instance, with `a` marked as non-bindable. Note [Matching coercion variables] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Consider this: type family F a data G a where MkG :: F a ~ Bool => G a type family Foo (x :: G a) :: F a type instance Foo MkG = False We would like that to be accepted. For that to work, we need to introduce a coercion variable on the left and then use it on the right. Accordingly, at use sites of Foo, we need to be able to use matching to figure out the value for the coercion. (See the desugared version: axFoo :: [a :: *, c :: F a ~ Bool]. Foo (MkG c) = False |> (sym c) ) We never want this action to happen during *unification* though, when all bets are off. Note [Kind coercions in Unify] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ We wish to match/unify while ignoring casts. But, we can't just ignore them completely, or we'll end up with ill-kinded substitutions. For example, say we're matching `a` with `ty |> co`. If we just drop the cast, we'll return [a |-> ty], but `a` and `ty` might have different kinds. We can't just match/unify their kinds, either, because this might gratuitously fail. After all, `co` is the witness that the kinds are the same -- they may look nothing alike. So, we pass a kind coercion `kco` to the main `unify_ty`. This coercion witnesses the equality between the substed kind of the left-hand type and the substed kind of the right-hand type. Note that we do not unify kinds at the leaves (as we did previously). Hence: (UKINV) Unification Kind Invariant * In the call unify_ty ty1 ty2 kco it must be that subst(kco) :: subst(kind(ty1)) ~N subst(kind(ty2)) where `subst` is the ambient substitution in the UM monad * In the call unify_tys tys1 tys2 (which has no kco), after we unify any prefix of tys1,tys2, the kinds of the head of the remaining tys1,tys2 are identical after substitution. This implies, for example, that the kinds of the head of tys1,tys2 are identical after substitution. Preserving (UKINV) takes a bit of work, governed by the `match_kis` flag in `tc_unify_tys`: * When we're working with type applications (either TyConApp or AppTy) we need to worry about establishing (UKINV), as the kinds of the function & arguments aren't (necessarily) included in the kind of the result. When unifying two TyConApps, this is easy, because the two TyCons are the same. Their kinds are thus the same. As long as we unify left-to-right, we'll be sure to unify types' kinds before the types themselves. (For example, think about Proxy :: forall k. k -> *. Unifying the first args matches up the kinds of the second args.) * For AppTy, we must unify the kinds of the functions, but once these are unified, we can continue unifying arguments without worrying further about kinds. * The interface to this module includes both "...Ty" functions and "...TyKi" functions. The former assume that (UKINV) is already established, either because the kinds are the same or because the list of types being passed in are the well-typed arguments to some type constructor (see two paragraphs above). The latter take a separate pre-pass over the kinds to establish (UKINV). Sometimes, it's important not to take the second pass, as it caused #12442. Wrinkles (KCU1) We ensure that the `kco` argument never mentions variables in the domain of either RnEnvL or RnEnvR. Why? * `kco` is used only to build the final well-kinded substitution a :-> ty |> kco The range of the substitution never mentions forall-bound variables, so `kco` cannot either. * `kco` mixes up types from both left and right arguments of `unify_ty`, which have different renamings in the RnEnv2. The easiest thing is to insist that `kco` does not need renaming with the RnEnv2; it mentions no forall-bound variables. To achieve this we do a `mentionsForAllBoundTyVars` test in the `CastTy` cases of `unify_ty`. (KCU2) Suppose we are unifying (forall a. x |> (...F a b...) ~ (forall a. y) We can't bind y :-> x |> (...F a b...), becuase of that free `a`. But if we later learn that b=Int, and F a Int = Bool, that free `a` might disappear, so we could unify with y :-> x |> (...Bool...) Conclusion: if there is a free forall-bound variable in a cast, return MaybeApart, with a MaybeApartReason of MARCast. (KCU3) We thought, at one point, that this was all unnecessary: why should casts be in types in the first place? But they are sometimes. In dependent/should_compile/KindEqualities2, we see, for example the constraint Num (Int |> (blah ; sym blah)). We naturally want to find a dictionary for that constraint, which requires dealing with coercions in this manner. Note [Matching in the presence of casts (1)] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ When matching, it is crucial that no variables from the template end up in the range of the matching substitution (obviously!). When unifying, that's not a constraint; instead we take the fixpoint of the substitution at the end. So what should we do with this, when matching? unify_ty (tmpl |> co) tgt kco Previously, wrongly, we pushed 'co' in the (horrid) accumulating 'kco' argument like this: unify_ty (tmpl |> co) tgt kco = unify_ty tmpl tgt (kco ; co) But that is obviously wrong because 'co' (from the template) ends up in 'kco', which in turn ends up in the range of the substitution. This all came up in #13910. Because we match tycon arguments left-to-right, the ambient substitution will already have a matching substitution for any kinds; so there is an easy fix: just apply the substitution-so-far to the coercion from the LHS. Note that * When matching, the first arg of unify_ty is always the template; we never swap round. * The above argument is distressingly indirect. We seek a better way. * One better way is to ensure that type patterns (the template in the matching process) have no casts. See #14119. Note [Matching in the presence of casts (2)] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ There is another wrinkle (#17395). Suppose (T :: forall k. k -> Type) and we are matching tcMatchTy (T k (a::k)) (T j (b::j)) Then we'll match k :-> j, as expected. But then in unify_tys we invoke unify_tys env (a::k) (b::j) (Refl j) Although we have unified k and j, it's very important that we put (Refl j), /not/ (Refl k) as the fourth argument to unify_tys. If we put (Refl k) we'd end up with the substitution a :-> b |> Refl k which is bogus because one of the template variables, k, appears in the range of the substitution. Eek. Similar care is needed in unify_ty_app. Note [Polykinded tycon applications] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Suppose T :: forall k. Type -> K and we are unifying ty1: T @Type Int :: Type ty2: T @(Type->Type) Int Int :: Type These two TyConApps have the same TyCon at the front but they (legitimately) have different numbers of arguments. They are surelyApart, so we can report that without looking any further (see #15704). Note [Unifying type applications] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Unifying type applications is quite subtle, as we found in #23134 and #22647, when type families are involved. Suppose type family F a :: Type -> Type type family G k :: k = r | r -> k and consider these examples: * F Int ~ F Char, where F is injective Since F is injective, we can reduce this to Int ~ Char, therefore SurelyApart. * F Int ~ F Char, where F is not injective Without injectivity, return MaybeApart. * G Type ~ G (Type -> Type) Int Even though G is injective and the arguments to G are different, we cannot deduce apartness because the RHS is oversaturated. For example, G might be defined as G Type = Maybe Int G (Type -> Type) = Maybe So we return MaybeApart. * F Int Bool ~ F Int Char -- SurelyApart (since Bool is apart from Char) F Int Bool ~ Maybe a -- MaybeApart F Int Bool ~ a b -- MaybeApart F Int Bool ~ Char -> Bool -- MaybeApart An oversaturated type family can match an application, whether it's a TyConApp, AppTy or FunTy. Decompose. * F Int ~ a b We cannot decompose a saturated, or under-saturated type family application. We return MaybeApart. To handle all those conditions, unify_ty goes through the following checks in sequence, where Fn is a type family of arity n: * (C1) Fn x_1 ... x_n ~ Fn y_1 .. y_n A saturated application. Here we can unify arguments in which Fn is injective. * (C2) Fn x_1 ... x_n ~ anything, anything ~ Fn x_1 ... x_n A saturated type family can match anything - we return MaybeApart. * (C3) Fn x_1 ... x_m ~ a b, a b ~ Fn x_1 ... x_m where m > n An oversaturated type family can be decomposed. * (C4) Fn x_1 ... x_m ~ anything, anything ~ Fn x_1 ... x_m, where m > n If we couldn't decompose in the previous step, we return SurelyApart. Afterwards, the rest of the code doesn't have to worry about type families. Note [Unifying type synonyms] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Consider the task of unifying two 'Type's of the form TyConApp tc [] ~ TyConApp tc [] where `tc` is a type synonym. A naive way to perform this comparison these would first expand the synonym and then compare the resulting expansions. However, this is obviously wasteful and the RHS of `tc` may be large; it is much better to rather compare the TyCons directly. Consequently, before expanding type synonyms in type comparisons we first look for a nullary TyConApp and simply compare the TyCons if we find one. Of course, if we find that the TyCons are *not* equal then we still need to perform the expansion as their RHSs may still be unifiable. E.g type T = S (a->a) type S a = [a] and consider T Int ~ S (Int -> Int) We can't decompose non-nullary synonyms. E.g. type R a = F a -- Where F is a type family and consider R (a->a) ~ R Int We can't conclude that (a->) ~ Int. (There is a currently-missed opportunity here; if we knew that R was /injective/, perhaps we could decompose.) We perform the nullary-type-synonym optimisation in a number of places: * GHC.Core.Unify.unify_ty * GHC.Tc.Solver.Equality.can_eq_nc' * GHC.Tc.Utils.Unify.uType This optimisation is especially helpful for the ubiquitous GHC.Types.Type, since GHC prefers to use the type synonym over @TYPE 'LiftedRep@ applications whenever possible. See Note [Using synonyms to compress types] in GHC.Core.Type for details. c.f. Note [Comparing type synonyms] in GHC.Core.TyCo.Compare -} -------------- unify_ty: the main workhorse ----------- type AmIUnifying = Bool -- True <=> Unifying -- False <=> Matching type InType = Type -- Before applying the RnEnv2 type OutCoercion = Coercion -- After applying the RnEnv2 unify_ty :: UMEnv -> InType -> InType -- Types to be unified -> OutCoercion -- A nominal coercion between their kinds -- OutCoercion: the RnEnv has already been applied -- When matching, the coercion is in "target space", -- not "template space" -- See Note [Kind coercions in Unify] -> UM () -- Precondition: see (Unification Kind Invariant) -- -- See Note [Specification of unification] -- Respects newtypes, PredTypes -- See Note [Computing equality on types] in GHC.Core.Type unify_ty _env (TyConApp tc1 []) (TyConApp tc2 []) _kco -- See Note [Unifying type synonyms] | tc1 == tc2 = return () unify_ty env ty1 ty2 kco -- Now handle the cases we can "look through": synonyms and casts. | Just ty1' <- coreView ty1 = unify_ty env ty1' ty2 kco | Just ty2' <- coreView ty2 = unify_ty env ty1 ty2' kco unify_ty env (CastTy ty1 co1) ty2 kco | mentionsForAllBoundTyVarsL env (tyCoVarsOfCo co1) -- See (KCU1) in Note [Kind coercions in Unify] = maybeApart MARCast -- See (KCU2) | um_unif env = unify_ty env ty1 ty2 (co1 `mkTransCo` kco) | otherwise -- We are matching, not unifying = do { subst <- getSubst env ; let co' = substCo subst co1 -- We match left-to-right, so the free template vars of the -- coercion should already have been matched. -- See Note [Matching in the presence of casts (1)] -- NB: co1 does not mention forall-bound vars, so no need to rename ; unify_ty env ty1 ty2 (co' `mkTransCo` kco) } unify_ty env ty1 (CastTy ty2 co2) kco | mentionsForAllBoundTyVarsR env (tyCoVarsOfCo co2) -- See (KCU1) in Note [Kind coercions in Unify] = maybeApart MARCast -- See (KCU2) | otherwise = unify_ty env ty1 ty2 (kco `mkTransCo` mkSymCo co2) -- NB: co2 does not mention forall-bound variables -- Applications need a bit of care! -- They can match FunTy and TyConApp, so use splitAppTy_maybe unify_ty env (AppTy ty1a ty1b) ty2 _kco | Just (ty2a, ty2b) <- tcSplitAppTyNoView_maybe ty2 = unify_ty_app env ty1a [ty1b] ty2a [ty2b] unify_ty env ty1 (AppTy ty2a ty2b) _kco | Just (ty1a, ty1b) <- tcSplitAppTyNoView_maybe ty1 = unify_ty_app env ty1a [ty1b] ty2a [ty2b] unify_ty _ (LitTy x) (LitTy y) _kco | x == y = return () unify_ty env (ForAllTy (Bndr tv1 _) ty1) (ForAllTy (Bndr tv2 _) ty2) kco -- ToDo: See Note [Unifying coercion-foralls] = do { unify_ty env (varType tv1) (varType tv2) (mkNomReflCo liftedTypeKind) ; let env' = umRnBndr2 env tv1 tv2 ; unify_ty env' ty1 ty2 kco } -- See Note [Matching coercion variables] unify_ty env (CoercionTy co1) (CoercionTy co2) kco = do { c_subst <- getCvSubstEnv ; case co1 of CoVarCo cv | not (um_unif env) , not (cv `elemVarEnv` c_subst) -- Not forall-bound , let (_mult_co, co_l, co_r) = decomposeFunCo kco -- Because the coercion is used in a type, it should be safe to -- ignore the multiplicity coercion, _mult_co -- cv :: t1 ~ t2 -- co2 :: s1 ~ s2 -- co_l :: t1 ~ s1 -- co_r :: t2 ~ s2 rhs_co = co_l `mkTransCo` co2 `mkTransCo` mkSymCo co_r , BindMe <- um_bind_tv_fun env cv (CoercionTy rhs_co) -> if mentionsForAllBoundTyVarsR env (tyCoVarsOfCo co2) then surelyApart else extendCvEnv cv rhs_co _ -> return () } unify_ty env (TyVarTy tv1) ty2 kco = uVarOrFam env (TyVarLHS tv1) ty2 kco unify_ty env ty1 (TyVarTy tv2) kco | um_unif env -- If unifying, can swap args; but not when matching = uVarOrFam (umSwapRn env) (TyVarLHS tv2) ty1 (mkSymCo kco) -- Deal with TyConApps unify_ty env ty1 ty2 kco -- Handle non-oversaturated type families first -- See Note [Unifying type applications] | Just (tc,tys) <- mb_sat_fam_app1 = uVarOrFam env (TyFamLHS tc tys) ty2 kco | um_unif env , Just (tc,tys) <- mb_sat_fam_app2 = uVarOrFam (umSwapRn env) (TyFamLHS tc tys) ty1 (mkSymCo kco) -- Handle oversaturated type families. Suppose we have -- (F a b) ~ (c d) where F has arity 1 -- We definitely want to decompose that type application! (#22647) -- -- If there is no application, an oversaturated type family can only -- match a type variable or a saturated type family, -- both of which we handled earlier. So we can say surelyApart. | Just (tc1, _) <- mb_tc_app1 , isTypeFamilyTyCon tc1 = if | Just (ty1a, ty1b) <- tcSplitAppTyNoView_maybe ty1 , Just (ty2a, ty2b) <- tcSplitAppTyNoView_maybe ty2 -> unify_ty_app env ty1a [ty1b] ty2a [ty2b] -- (C3) | otherwise -> surelyApart -- (C4) | Just (tc2, _) <- mb_tc_app2 , isTypeFamilyTyCon tc2 = if | Just (ty1a, ty1b) <- tcSplitAppTyNoView_maybe ty1 , Just (ty2a, ty2b) <- tcSplitAppTyNoView_maybe ty2 -> unify_ty_app env ty1a [ty1b] ty2a [ty2b] -- (C3) | otherwise -> surelyApart -- (C4) -- At this point, neither tc1 nor tc2 can be a type family. | Just (tc1, tys1) <- mb_tc_app1 , Just (tc2, tys2) <- mb_tc_app2 , tc1 == tc2 = do { massertPpr (isInjectiveTyCon tc1 Nominal) (ppr tc1) ; unify_tc_app env tc1 tys1 tys2 } -- TYPE and CONSTRAINT are not Apart -- See Note [Type and Constraint are not apart] in GHC.Builtin.Types.Prim -- NB: at this point we know that the two TyCons do not match | Just (tc1,_) <- mb_tc_app1, let u1 = tyConUnique tc1 , Just (tc2,_) <- mb_tc_app2, let u2 = tyConUnique tc2 , (u1 == tYPETyConKey && u2 == cONSTRAINTTyConKey) || (u2 == tYPETyConKey && u1 == cONSTRAINTTyConKey) = maybeApart MARTypeVsConstraint -- We don't bother to look inside; wrinkle (W3) in GHC.Builtin.Types.Prim -- Note [Type and Constraint are not apart] -- The arrow types are not Apart -- See Note [Type and Constraint are not apart] in GHC.Builtin.Types.Prim -- wrinkle (W2) -- NB1: at this point we know that the two TyCons do not match -- NB2: In the common FunTy/FunTy case you might wonder if we want to go via -- splitTyConApp_maybe. But yes we do: we need to look at those implied -- kind argument in order to satisfy (Unification Kind Invariant) | FunTy {} <- ty1 , FunTy {} <- ty2 = maybeApart MARTypeVsConstraint -- We don't bother to look inside; wrinkle (W3) in GHC.Builtin.Types.Prim -- Note [Type and Constraint are not apart] where mb_tc_app1 = splitTyConApp_maybe ty1 mb_tc_app2 = splitTyConApp_maybe ty2 mb_sat_fam_app1 = isSatTyFamApp ty1 mb_sat_fam_app2 = isSatTyFamApp ty2 unify_ty _ _ _ _ = surelyApart ----------------------------- unify_tc_app :: UMEnv -> TyCon -> [Type] -> [Type] -> UM () -- Mainly just unifies the argument types; -- but with a special case for fUNTyCon unify_tc_app env tc tys1 tys2 | tc == fUNTyCon , IgnoreMultiplicities <- um_arr_mult env , (_mult1 : no_mult_tys1) <- tys1 , (_mult2 : no_mult_tys2) <- tys2 = -- We're comparing function arrow types here (not constraint arrow -- types!), and they have at least one argument, which is the arrow's -- multiplicity annotation. The flag `um_arr_mult` instructs us to -- ignore multiplicities in this very case. This is a little tricky: see -- point (3) in Note [Rewrite rules ignore multiplicities in FunTy]. unify_tys env no_mult_tys1 no_mult_tys2 | otherwise = unify_tys env tys1 tys2 ----------------------------- unify_ty_app :: UMEnv -> Type -> [Type] -> Type -> [Type] -> UM () -- Deal with (t1 t1args) ~ (t2 t2args) -- where length t1args = length t2args unify_ty_app env ty1 ty1args ty2 ty2args | Just (ty1', ty1a) <- splitAppTyNoView_maybe ty1 , Just (ty2', ty2a) <- splitAppTyNoView_maybe ty2 = unify_ty_app env ty1' (ty1a : ty1args) ty2' (ty2a : ty2args) | otherwise = do { let ki1 = typeKind ty1 ki2 = typeKind ty2 -- See Note [Kind coercions in Unify] ; unify_ty env ki1 ki2 (mkNomReflCo liftedTypeKind) ; unify_ty env ty1 ty2 (mkNomReflCo ki2) -- Very important: 'ki2' not 'ki1' -- See Note [Matching in the presence of casts (2)] ; unify_tys env ty1args ty2args } ----------------------------- unify_tys :: UMEnv -> [Type] -> [Type] -> UM () -- Precondition: see (Unification Kind Invariant) unify_tys env orig_xs orig_ys = go orig_xs orig_ys where go [] [] = return () go (x:xs) (y:ys) -- See Note [Kind coercions in Unify] = do { unify_ty env x y (mkNomReflCo $ typeKind y) -- Very important: 'y' not 'x' -- See Note [Matching in the presence of casts (2)] ; go xs ys } go _ _ = surelyApart -- Possibly different saturations of a polykinded tycon -- See Note [Polykinded tycon applications] --------------------------------- uVarOrFam :: UMEnv -> CanEqLHS -> InType -> OutCoercion -> UM () -- Invariants: (a) If ty1 is a TyFamLHS, then ty2 is NOT a TyVarTy -- (b) both args have had coreView already applied -- Why saturated? See (ATF4) in Note [Apartness and type families] uVarOrFam env ty1 ty2 kco = do { substs <- getSubstEnvs -- ; pprTrace "uVarOrFam" (vcat -- [ text "ty1" <+> ppr ty1 -- , text "ty2" <+> ppr ty2 -- , text "tv_env" <+> ppr (um_tv_env substs) -- , text "fam_env" <+> ppr (um_fam_env substs) ]) $ ; go NotSwapped substs ty1 ty2 kco } where foralld_tvs = um_foralls env under_forall = not (isEmptyVarSet foralld_tvs) -- `go` takes two bites at the cherry; if the first one fails -- it swaps the arguments and tries again; and then it fails. -- The SwapFlag argument tells `go` whether it is on the first -- bite (NotSwapped) or the second (IsSwapped). -- E.g. a ~ F p q -- Starts with: go a (F p q) -- if `a` not bindable, swap to: go (F p q) a ----------------------------- -- LHS is a type variable -- The sequence of tests is very similar to go_tv go :: SwapFlag -> UMState -> CanEqLHS -> InType -> OutCoercion -> UM () go swapped substs lhs@(TyVarLHS tv1) ty2 kco | Just ty1' <- lookupVarEnv (um_tv_env substs) tv1' = -- We already have a substitution for tv1 if | um_unif env -> unify_ty env ty1' ty2 kco | (ty1' `mkCastTy` kco) `tcEqType` ty2 -> return () | otherwise -> surelyApart -- Unifying: recurse into unify_ty -- Matching: we /don't/ want to just recurse here, because the range of -- the subst is the target type, not the template type. So, just check -- for normal type equality. -- NB: it's important to use `tcEqType` instead of `eqType` here, -- otherwise we might not reject a substitution -- which unifies `Type` with `Constraint`, e.g. -- a call to tc_unify_tys with arguments -- -- tys1 = [k,k] -- tys2 = [Type, Constraint] -- -- See test cases: T11715b, T20521. -- If we are matching or unifying a ~ a, take care -- See Note [Self-substitution when unifying or matching] | TyVarTy tv2 <- ty2 , let tv2' = umRnOccR env tv2 , tv1' == tv2' = if | um_unif env -> return () | tv1_is_bindable -> extendTvEnv tv1' ty2 | otherwise -> return () | tv1_is_bindable , not (mentionsForAllBoundTyVarsR env ty2_fvs) -- ty2_fvs: kco does not mention forall-bound vars , not occurs_check = -- No occurs check, nor skolem-escape; just bind the tv -- We don't need to rename `rhs` because it mentions no forall-bound vars extendTvEnv tv1' rhs -- Bind tv1:=rhs and continue -- When unifying, try swapping: -- e.g. a ~ F p q with `a` not bindable: we might succeed with go_fam -- e.g. a ~ beta with `a` not bindable: we might be able to bind `beta` -- e.g. beta ~ F beta Int occurs check; but MaybeApart after swapping | um_unif env , NotSwapped <- swapped -- If we have swapped already, don't do so again , Just lhs2 <- canEqLHS_maybe ty2 = go IsSwapped substs lhs2 (mkTyVarTy tv1) (mkSymCo kco) | occurs_check = maybeApart MARInfinite -- Occurs check | otherwise = surelyApart where tv1' = umRnOccL env tv1 ty2_fvs = tyCoVarsOfType ty2 rhs = ty2 `mkCastTy` mkSymCo kco tv1_is_bindable | not (tv1' `elemVarSet` foralld_tvs) -- tv1' is not forall-bound, but tv1 can still differ -- from tv1; see Note [Cloning the template binders] -- in GHC.Core.Rules. So give tv1' to um_bind_tv_fun. , BindMe <- um_bind_tv_fun env tv1' rhs = True | otherwise = False occurs_check = um_unif env && uOccursCheck substs foralld_tvs lhs rhs -- Occurs check, only when unifying -- see Note [Infinitary substitutions] -- Make sure you include `kco` in rhs #14846 ----------------------------- -- LHS is a saturated type-family application -- Invariant: ty2 is not a TyVarTy go swapped substs lhs@(TyFamLHS tc1 tys1) ty2 kco -- Check if we have an existing substitution for the LHS; if so, recurse -- But not under a forall; see (ATF3) in Note [Apartness and type families] -- Hence the RnEnv2 is empty | not under_forall , Just ty1' <- lookupFamEnv (um_fam_env substs) tc1 tys1 = if | um_unif env -> unify_ty env ty1' ty2 kco -- Below here we are matching -- The return () case deals with: -- Template: (F a)..(F a) -- Target: (F b)..(F b) -- This should match! With [a :-> b] | (ty1' `mkCastTy` kco) `tcEqType` ty2 -> return () | otherwise -> maybeApart MARTypeFamily -- Check for equality F tys1 ~ F tys2 -- Very important that this can happen under a forall, so that we -- successfully match (forall a. F a) ~ (forall b. F b) See (ATF9-2) | Just (tc2, tys2) <- isSatTyFamApp ty2 , tc1 == tc2 = go_fam_fam substs tc1 tys1 tys2 kco -- If we are under a forall, just give up -- see (ATF3) and (ATF5) in Note [Apartness and type families] | under_forall = maybeApart MARTypeFamily -- Now check if we can bind the (F tys) to the RHS -- Again, not under a forall; see (ATF3) -- This can happen even when matching: see (ATF7) | BindMe <- um_bind_fam_fun env tc1 tys1 rhs = if uOccursCheck substs emptyVarSet lhs rhs then maybeApart MARInfinite else do { extendFamEnv tc1 tys1 rhs -- We don't substitute tys1 before extending -- See Note [Shortcomings of the apartness test] ; maybeApart MARTypeFamily } -- Swap in case of (F a b) ~ (G c d e) -- Maybe um_bind_fam_fun is False of (F a b) but true of (G c d e) -- NB: a type family can appear on the template when matching -- see (ATF6) in Note [Apartness and type families] -- (Only worth doing this if we are not under a forall.) | um_unif env , NotSwapped <- swapped , Just lhs2 <- canEqLHS_maybe ty2 = go IsSwapped substs lhs2 (mkTyConApp tc1 tys1) (mkSymCo kco) | otherwise -- See (ATF5) in Note [Apartness and type families] = surelyApart where rhs = ty2 `mkCastTy` mkSymCo kco ----------------------------- -- go_fam_fam: LHS and RHS are both saturated type-family applications, -- for the same type-family F go_fam_fam substs tc tys1 tys2 kco -- Decompose (F tys1 ~ F tys2): (ATF9) -- Use injectivity information of F: (ATF10) -- But first bind the type-fam if poss: (ATF11) = do { bind_fam_if_poss -- (ATF11) ; unify_tys env inj_tys1 inj_tys2 -- (ATF10) ; unless (um_inj_tf env) $ -- (ATF12) don'tBeSoSure MARTypeFamily $ -- (ATF9-1) unify_tys env noninj_tys1 noninj_tys2 } where inj = case tyConInjectivityInfo tc of NotInjective -> repeat False Injective bs -> bs (inj_tys1, noninj_tys1) = partitionByList inj tys1 (inj_tys2, noninj_tys2) = partitionByList inj tys2 bind_fam_if_poss | not (um_unif env) -- Not when matching (ATF11-1) = return () | under_forall -- Not under a forall (ATF3) = return () | BindMe <- um_bind_fam_fun env tc tys1 rhs1 = unless (uOccursCheck substs emptyVarSet (TyFamLHS tc tys1) rhs1) $ extendFamEnv tc tys1 rhs1 -- At this point um_unif=True, so we can unify either way | BindMe <- um_bind_fam_fun env tc tys2 rhs2 = unless (uOccursCheck substs emptyVarSet (TyFamLHS tc tys2) rhs2) $ extendFamEnv tc tys2 rhs2 | otherwise = return () rhs1 = mkTyConApp tc tys2 `mkCastTy` mkSymCo kco rhs2 = mkTyConApp tc tys1 `mkCastTy` kco uOccursCheck :: UMState -> TyVarSet -- Bound by enclosing foralls; see (OCU1) -> CanEqLHS -> Type -- Can we unify (lhs := ty)? -> Bool -- See Note [The occurs check in the Core unifier] and (ATF13) uOccursCheck (UMState { um_tv_env = tv_env, um_fam_env = fam_env }) bvs lhs ty = go bvs ty where go :: TyCoVarSet -- Bound by enclosing foralls; see (OCU1) -> Type -> Bool go bvs ty | Just ty' <- coreView ty = go bvs ty' go bvs (TyVarTy tv) | Just ty' <- lookupVarEnv tv_env tv = go bvs ty' | TyVarLHS tv' <- lhs, tv==tv' = True | otherwise = go bvs (tyVarKind tv) go bvs (AppTy ty1 ty2) = go bvs ty1 || go bvs ty2 go _ (LitTy {}) = False go bvs (FunTy _ w arg res) = go bvs w || go bvs arg || go bvs res go bvs (TyConApp tc tys) = go_tc bvs tc tys go bvs (ForAllTy (Bndr tv _) ty) = go bvs (tyVarKind tv) || (case lhs of TyVarLHS tv' | tv==tv' -> False -- Shadowing | otherwise -> go (bvs `extendVarSet` tv) ty TyFamLHS {} -> False) -- Lookups don't happen under a forall go bvs (CastTy ty _co) = go bvs ty -- ToDo: should we worry about `co`? go _ (CoercionTy _co) = False -- ToDo: should we worry about `co`? go_tc bvs tc tys | isEmptyVarSet bvs -- Never look up in um_fam_env under a forall (ATF3) , isTypeFamilyTyCon tc , Just ty' <- lookupFamEnv fam_env tc (take arity tys) -- NB: we look up /un-substituted/ types; -- See Note [Shortcomings of the apartness test] = go bvs ty' || any (go bvs) (drop arity tys) | TyFamLHS tc' tys' <- lhs , tc == tc' , tys `lengthAtLeast` arity -- Saturated, or over-saturated , tcEqTyConAppArgs tys tys' = True | otherwise = any (go bvs) tys where arity = tyConArity tc {- Note [The occurs check in the Core unifier] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ The unifier applies both substitutions (um_tv_env and um_fam_env) as it goes, so we'll get an infinite loop if we have, for example um_tv_env: a :-> F b -- (1) um_fam_env F b :-> a -- (2) So (uOccursCheck substs lhs ty) returns True iff extending `substs` with `lhs :-> ty` could lead to a loop. That is, could there by a type `s` such that applySubsts( (substs + lhs:->ty), s ) is infinite It's vital that we do both at once: we might have (1) already and add (2); or we might have (2) already and add (1). A very similar task is done by GHC.Tc.Utils.Unify.checkTyEqRhs. (OCU1) We keep track of the forall-bound variables because the um_fam_env is inactive under a forall; indeed it is /unsound/ to consult it because we may have a binding (F a :-> Int), and then unify (forall a. ...(F a)...) with something. We don't want to map that (F a) to Int! (OCU2) Performance. Consider unifying [a, b] ~ [big-ty, (a,a,a)] We'll unify a:=big-ty. Then we'll attempt b:=(a,a,a), but must do an occurs check. So we'll walk over big-ty, looking for `b`. And then again, and again, once for each occurrence of `a`. A similar thing happens for [a, (b,b,b)] ~ [big-ty, (a,a,a)] albeit a bit less obviously. Potentially we could use a cache to record checks we have already done; but I have not attempted that yet. Precisely similar remarks would apply to GHC.Tc.Utils.Unify.checkTyEqRhs Note [Unifying coercion-foralls] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Suppose we try to unify (forall cv. t1) ~ (forall cv. t2). See Note [ForAllTy] in GHC.Core.TyCo.Rep. The problem with coercion variables is that coercion abstraction is not erased: the `kco` shouldn't propagate from outside the ForAllTy to inside. Instead, I think the correct new `kco` for the recursive call is `mkNomReflCo liftedTypeKind` (but I'm a little worried it might be Constraint sometimes). This potential problem has been there a long time, and I'm going to let sleeping dogs lie for now. -} {- ************************************************************************ * * Unification monad * * ************************************************************************ -} data UMEnv = UMEnv { um_unif :: AmIUnifying , um_inj_tf :: Bool -- Checking for injectivity? -- See (SI1) in Note [Specification of unification] , um_arr_mult :: MultiplicityFlag -- Whether to unify multiplicity arguments when unifying arrows. -- See Note [Rewrite rules ignore multiplicities in FunTy] , um_rn_env :: RnEnv2 -- Renaming InTyVars to OutTyVars; this eliminates shadowing, and -- lines up matching foralls on the left and right -- See (CU2) in Note [The Core unifier] , um_foralls :: TyVarSet -- OutTyVars bound by a forall in this unification; -- Do not bind these in the substitution! -- See the function tvBindFlag , um_bind_tv_fun :: BindTvFun -- User-supplied BindFlag function, for variables not in um_foralls -- See (CU1) in Note [The Core unifier] , um_bind_fam_fun :: BindFamFun -- Similar to um_bind_tv_fun, but for type-family applications -- See (ATF8) in Note [Apartness and type families] } type FamSubstEnv = TyConEnv (ListMap TypeMap Type) -- Map a TyCon and a list of types to a type -- Domain of FamSubstEnv is exactly-saturated type-family -- applications (F t1...tn) lookupFamEnv :: FamSubstEnv -> TyCon -> [Type] -> Maybe Type lookupFamEnv env tc tys = do { tys_map <- lookupTyConEnv env tc ; lookupTM tys tys_map } data UMState = UMState { um_tv_env :: TvSubstEnv , um_cv_env :: CvSubstEnv , um_fam_env :: FamSubstEnv } -- um_tv_env, um_cv_env, um_fam_env are all "global" substitutions; -- that is, neither their domains nor their ranges mention any variables -- in um_foralls; i.e. variables bound by foralls inside the types being unified -- When /matching/ um_fam_env is usually empty; but not quite always. -- See (ATF7) of Note [Apartness and type families] newtype UM a = UM' { unUM :: UMState -> UnifyResultM (UMState, a) } -- See Note [The one-shot state monad trick] in GHC.Utils.Monad pattern UM :: (UMState -> UnifyResultM (UMState, a)) -> UM a -- See Note [The one-shot state monad trick] in GHC.Utils.Monad pattern UM m <- UM' m where UM m = UM' (oneShot m) {-# COMPLETE UM #-} instance Functor UM where fmap f (UM m) = UM (\s -> fmap (\(s', v) -> (s', f v)) (m s)) instance Applicative UM where pure a = UM (\s -> pure (s, a)) (<*>) = ap instance Monad UM where {-# INLINE (>>=) #-} -- See Note [INLINE pragmas and (>>)] in GHC.Utils.Monad m >>= k = UM (\state -> do { (state', v) <- unUM m state ; unUM (k v) state' }) instance MonadFail UM where fail _ = UM (\_ -> SurelyApart) -- failed pattern match initUM :: TvSubstEnv -- subst to extend -> CvSubstEnv -> UM () -> UnifyResultM (TvSubstEnv, CvSubstEnv) initUM subst_env cv_subst_env um = case unUM um state of Unifiable (state, _) -> Unifiable (get state) MaybeApart r (state, _) -> MaybeApart r (get state) SurelyApart -> SurelyApart where state = UMState { um_tv_env = subst_env , um_cv_env = cv_subst_env , um_fam_env = emptyTyConEnv } get (UMState { um_tv_env = tv_env, um_cv_env = cv_env }) = (tv_env, cv_env) getTvSubstEnv :: UM TvSubstEnv getTvSubstEnv = UM $ \state -> Unifiable (state, um_tv_env state) getCvSubstEnv :: UM CvSubstEnv getCvSubstEnv = UM $ \state -> Unifiable (state, um_cv_env state) getSubstEnvs :: UM UMState getSubstEnvs = UM $ \state -> Unifiable (state, state) getSubst :: UMEnv -> UM Subst getSubst env = do { tv_env <- getTvSubstEnv ; cv_env <- getCvSubstEnv ; let in_scope = rnInScopeSet (um_rn_env env) ; return (mkTCvSubst in_scope tv_env cv_env) } extendTvEnv :: TyVar -> Type -> UM () extendTvEnv tv ty = UM $ \state -> Unifiable (state { um_tv_env = extendVarEnv (um_tv_env state) tv ty }, ()) extendCvEnv :: CoVar -> Coercion -> UM () extendCvEnv cv co = UM $ \state -> Unifiable (state { um_cv_env = extendVarEnv (um_cv_env state) cv co }, ()) extendFamEnv :: TyCon -> [Type] -> Type -> UM () extendFamEnv tc tys ty = UM $ \state -> Unifiable (state { um_fam_env = extend (um_fam_env state) tc }, ()) where extend :: FamSubstEnv -> TyCon -> FamSubstEnv extend = alterTyConEnv alter_tm alter_tm :: Maybe (ListMap TypeMap Type) -> Maybe (ListMap TypeMap Type) alter_tm m_elt = Just (alterTM tys (\_ -> Just ty) (m_elt `orElse` emptyTM)) umRnBndr2 :: UMEnv -> TyCoVar -> TyCoVar -> UMEnv umRnBndr2 env v1 v2 = env { um_rn_env = rn_env', um_foralls = um_foralls env `extendVarSet` v' } where (rn_env', v') = rnBndr2_var (um_rn_env env) v1 v2 mentionsForAllBoundTyVarsL, mentionsForAllBoundTyVarsR :: UMEnv -> VarSet -> Bool -- See (CU2) in Note [The Core unifier] mentionsForAllBoundTyVarsL = mentions_forall_bound_tvs inRnEnvL mentionsForAllBoundTyVarsR = mentions_forall_bound_tvs inRnEnvR mentions_forall_bound_tvs :: (RnEnv2 -> TyVar -> Bool) -> UMEnv -> VarSet -> Bool mentions_forall_bound_tvs in_rn_env env varset | isEmptyVarSet (um_foralls env) = False | anyVarSet (in_rn_env (um_rn_env env)) varset = True | otherwise = False -- NB: That isEmptyVarSet guard is a critical optimization; -- it means we don't have to calculate the free vars of -- the type, often saving quite a bit of allocation. -- | Converts any SurelyApart to a MaybeApart don'tBeSoSure :: MaybeApartReason -> UM () -> UM () don'tBeSoSure r um = UM $ \ state -> case unUM um state of SurelyApart -> MaybeApart r (state, ()) other -> other umRnOccL :: UMEnv -> TyVar -> TyVar umRnOccL env v = rnOccL (um_rn_env env) v umRnOccR :: UMEnv -> TyVar -> TyVar umRnOccR env v = rnOccR (um_rn_env env) v umSwapRn :: UMEnv -> UMEnv umSwapRn env = env { um_rn_env = rnSwap (um_rn_env env) } maybeApart :: MaybeApartReason -> UM () maybeApart r = UM (\state -> MaybeApart r (state, ())) surelyApart :: UM a surelyApart = UM (\_ -> SurelyApart) {- %************************************************************************ %* * Matching a (lifted) type against a coercion %* * %************************************************************************ This section defines essentially an inverse to liftCoSubst. It is defined here to avoid a dependency from Coercion on this module. -} data MatchEnv = ME { me_tmpls :: TyVarSet , me_env :: RnEnv2 } -- | 'liftCoMatch' is sort of inverse to 'liftCoSubst'. In particular, if -- @liftCoMatch vars ty co == Just s@, then @liftCoSubst s ty == co@, -- where @==@ there means that the result of 'liftCoSubst' has the same -- type as the original co; but may be different under the hood. -- That is, it matches a type against a coercion of the same -- "shape", and returns a lifting substitution which could have been -- used to produce the given coercion from the given type. -- Note that this function is incomplete -- it might return Nothing -- when there does indeed exist a possible lifting context. -- -- This function is incomplete in that it doesn't respect the equality -- in `eqType`. That is, it's possible that this will succeed for t1 and -- fail for t2, even when t1 `eqType` t2. That's because it depends on -- there being a very similar structure between the type and the coercion. -- This incompleteness shouldn't be all that surprising, especially because -- it depends on the structure of the coercion, which is a silly thing to do. -- -- The lifting context produced doesn't have to be exacting in the roles -- of the mappings. This is because any use of the lifting context will -- also require a desired role. Thus, this algorithm prefers mapping to -- nominal coercions where it can do so. liftCoMatch :: TyCoVarSet -> Type -> Coercion -> Maybe LiftingContext liftCoMatch tmpls ty co = do { cenv1 <- ty_co_match menv emptyVarEnv ki ki_co ki_ki_co ki_ki_co ; cenv2 <- ty_co_match menv cenv1 ty co (mkNomReflCo co_lkind) (mkNomReflCo co_rkind) ; return (LC (mkEmptySubst in_scope) cenv2) } where menv = ME { me_tmpls = tmpls, me_env = mkRnEnv2 in_scope } in_scope = mkInScopeSet (tmpls `unionVarSet` tyCoVarsOfCo co) -- Like tcMatchTy, assume all the interesting variables -- in ty are in tmpls ki = typeKind ty ki_co = promoteCoercion co ki_ki_co = mkNomReflCo liftedTypeKind Pair co_lkind co_rkind = coercionKind ki_co -- | 'ty_co_match' does all the actual work for 'liftCoMatch'. ty_co_match :: MatchEnv -- ^ ambient helpful info -> LiftCoEnv -- ^ incoming subst -> Type -- ^ ty, type to match -> Coercion -- ^ co :: lty ~r rty, coercion to match against -> Coercion -- ^ :: kind(lsubst(ty)) ~N kind(lty) -> Coercion -- ^ :: kind(rsubst(ty)) ~N kind(rty) -> Maybe LiftCoEnv -- ^ Just env ==> liftCoSubst Nominal env ty == co, modulo roles. -- Also: Just env ==> lsubst(ty) == lty and rsubst(ty) == rty, -- where lsubst = lcSubstLeft(env) and rsubst = lcSubstRight(env) ty_co_match menv subst ty co lkco rkco | Just ty' <- coreView ty = ty_co_match menv subst ty' co lkco rkco -- handle Refl case: | tyCoVarsOfType ty `isNotInDomainOf` subst , Just (ty', _) <- isReflCo_maybe co , ty `eqType` ty' -- Why `eqType` and not `tcEqType`? Because this function is only used -- during coercion optimisation, after type-checking has finished. = Just subst where isNotInDomainOf :: VarSet -> VarEnv a -> Bool isNotInDomainOf set env = noneSet (\v -> elemVarEnv v env) set noneSet :: (Var -> Bool) -> VarSet -> Bool noneSet f = allVarSet (not . f) ty_co_match menv subst ty co lkco rkco | CastTy ty' co' <- ty -- See Note [Matching in the presence of casts (1)] = let empty_subst = mkEmptySubst (rnInScopeSet (me_env menv)) substed_co_l = substCo (liftEnvSubstLeft empty_subst subst) co' substed_co_r = substCo (liftEnvSubstRight empty_subst subst) co' in ty_co_match menv subst ty' co (substed_co_l `mkTransCo` lkco) (substed_co_r `mkTransCo` rkco) | SymCo co' <- co = swapLiftCoEnv <$> ty_co_match menv (swapLiftCoEnv subst) ty co' rkco lkco -- Match a type variable against a non-refl coercion ty_co_match menv subst (TyVarTy tv1) co lkco rkco | Just co1' <- lookupVarEnv subst tv1' -- tv1' is already bound to co1 = if eqCoercionX (nukeRnEnvL rn_env) co1' co then Just subst else Nothing -- no match since tv1 matches two different coercions | tv1' `elemVarSet` me_tmpls menv -- tv1' is a template var = if any (inRnEnvR rn_env) (tyCoVarsOfCoList co) then Nothing -- occurs check failed else Just $ extendVarEnv subst tv1' $ castCoercionKind co (mkSymCo lkco) (mkSymCo rkco) | otherwise = Nothing where rn_env = me_env menv tv1' = rnOccL rn_env tv1 -- just look through SubCo's. We don't really care about roles here. ty_co_match menv subst ty (SubCo co) lkco rkco = ty_co_match menv subst ty co lkco rkco ty_co_match menv subst (AppTy ty1a ty1b) co _lkco _rkco | Just (co2, arg2) <- splitAppCo_maybe co -- c.f. Unify.match on AppTy = ty_co_match_app menv subst ty1a [ty1b] co2 [arg2] ty_co_match menv subst ty1 (AppCo co2 arg2) _lkco _rkco | Just (ty1a, ty1b) <- splitAppTyNoView_maybe ty1 -- yes, the one from Type, not TcType; this is for coercion optimization = ty_co_match_app menv subst ty1a [ty1b] co2 [arg2] ty_co_match menv subst (TyConApp tc1 tys) (TyConAppCo _ tc2 cos) _lkco _rkco = ty_co_match_tc menv subst tc1 tys tc2 cos ty_co_match menv subst (FunTy { ft_mult = w, ft_arg = ty1, ft_res = ty2 }) (FunCo { fco_mult = co_w, fco_arg = co1, fco_res = co2 }) _lkco _rkco = ty_co_match_args menv subst [w, rep1, rep2, ty1, ty2] [co_w, co1_rep, co2_rep, co1, co2] where rep1 = getRuntimeRep ty1 rep2 = getRuntimeRep ty2 co1_rep = mkRuntimeRepCo co1 co2_rep = mkRuntimeRepCo co2 -- NB: we include the RuntimeRep arguments in the matching; -- not doing so caused #21205. ty_co_match menv subst (ForAllTy (Bndr tv1 vis1t) ty1) (ForAllCo tv2 vis1c vis2c kind_co2 co2) lkco rkco | isTyVar tv1 && isTyVar tv2 , vis1t == vis1c && vis1c == vis2c -- Is this necessary? -- Is this visibility check necessary? @rae says: yes, I think the -- check is necessary, if we're caring about visibility (and we are). -- But ty_co_match is a dark and not important corner. = do { subst1 <- ty_co_match menv subst (tyVarKind tv1) kind_co2 ki_ki_co ki_ki_co ; let rn_env0 = me_env menv rn_env1 = rnBndr2 rn_env0 tv1 tv2 menv' = menv { me_env = rn_env1 } ; ty_co_match menv' subst1 ty1 co2 lkco rkco } where ki_ki_co = mkNomReflCo liftedTypeKind -- ty_co_match menv subst (ForAllTy (Bndr cv1 _) ty1) -- (ForAllCo cv2 kind_co2 co2) -- lkco rkco -- | isCoVar cv1 && isCoVar cv2 -- We seems not to have enough information for this case -- 1. Given: -- cv1 :: (s1 :: k1) ~r (s2 :: k2) -- kind_co2 :: (s1' ~ s2') ~N (t1 ~ t2) -- eta1 = mkSelCo (SelTyCon 2 role) (downgradeRole r Nominal kind_co2) -- :: s1' ~ t1 -- eta2 = mkSelCo (SelTyCon 3 role) (downgradeRole r Nominal kind_co2) -- :: s2' ~ t2 -- Wanted: -- subst1 <- ty_co_match menv subst s1 eta1 kco1 kco2 -- subst2 <- ty_co_match menv subst1 s2 eta2 kco3 kco4 -- Question: How do we get kcoi? -- 2. Given: -- lkco :: <*> -- See Note [Weird typing rule for ForAllTy] in GHC.Core.TyCo.Rep -- rkco :: <*> -- Wanted: -- ty_co_match menv' subst2 ty1 co2 lkco' rkco' -- Question: How do we get lkco' and rkco'? ty_co_match _ subst (CoercionTy {}) _ _ _ = Just subst -- don't inspect coercions ty_co_match menv subst ty (GRefl r t (MCo co)) lkco rkco = ty_co_match menv subst ty (GRefl r t MRefl) lkco (rkco `mkTransCo` mkSymCo co) ty_co_match menv subst ty co1 lkco rkco | Just (CastTy t co, r) <- isReflCo_maybe co1 -- In @pushRefl@, pushing reflexive coercion inside CastTy will give us -- t |> co ~ t ; ; t ~ t |> co -- But transitive coercions are not helpful. Therefore we deal -- with it here: we do recursion on the smaller reflexive coercion, -- while propagating the correct kind coercions. = let kco' = mkSymCo co in ty_co_match menv subst ty (mkReflCo r t) (lkco `mkTransCo` kco') (rkco `mkTransCo` kco') ty_co_match menv subst ty co lkco rkco | Just co' <- pushRefl co = ty_co_match menv subst ty co' lkco rkco | otherwise = Nothing ty_co_match_tc :: MatchEnv -> LiftCoEnv -> TyCon -> [Type] -> TyCon -> [Coercion] -> Maybe LiftCoEnv ty_co_match_tc menv subst tc1 tys1 tc2 cos2 = do { guard (tc1 == tc2) ; ty_co_match_args menv subst tys1 cos2 } ty_co_match_app :: MatchEnv -> LiftCoEnv -> Type -> [Type] -> Coercion -> [Coercion] -> Maybe LiftCoEnv ty_co_match_app menv subst ty1 ty1args co2 co2args | Just (ty1', ty1a) <- splitAppTyNoView_maybe ty1 , Just (co2', co2a) <- splitAppCo_maybe co2 = ty_co_match_app menv subst ty1' (ty1a : ty1args) co2' (co2a : co2args) | otherwise = do { subst1 <- ty_co_match menv subst ki1 ki2 ki_ki_co ki_ki_co ; let Pair lkco rkco = mkNomReflCo <$> coercionKind ki2 ; subst2 <- ty_co_match menv subst1 ty1 co2 lkco rkco ; ty_co_match_args menv subst2 ty1args co2args } where ki1 = typeKind ty1 ki2 = promoteCoercion co2 ki_ki_co = mkNomReflCo liftedTypeKind ty_co_match_args :: MatchEnv -> LiftCoEnv -> [Type] -> [Coercion] -> Maybe LiftCoEnv ty_co_match_args menv subst (ty:tys) (arg:args) = do { let Pair lty rty = coercionKind arg lkco = mkNomReflCo (typeKind lty) rkco = mkNomReflCo (typeKind rty) ; subst' <- ty_co_match menv subst ty arg lkco rkco ; ty_co_match_args menv subst' tys args } ty_co_match_args _ subst [] [] = Just subst ty_co_match_args _ _ _ _ = Nothing pushRefl :: Coercion -> Maybe Coercion pushRefl co = case (isReflCo_maybe co) of Just (AppTy ty1 ty2, Nominal) -> Just (AppCo (mkReflCo Nominal ty1) (mkNomReflCo ty2)) Just (FunTy af w ty1 ty2, r) -> Just (FunCo r af af (mkReflCo r w) (mkReflCo r ty1) (mkReflCo r ty2)) Just (TyConApp tc tys, r) -> Just (TyConAppCo r tc (zipWith mkReflCo (tyConRoleListX r tc) tys)) Just (ForAllTy (Bndr tv vis) ty, r) -> Just (ForAllCo { fco_tcv = tv, fco_visL = vis, fco_visR = vis , fco_kind = mkNomReflCo (varType tv) , fco_body = mkReflCo r ty }) _ -> Nothing