-tcGenericNormaliseFamInst :: (TcType -> TcM (Maybe (TcType, Coercion)))
- -- what to do with type functions and tyvars
- -> TcType -- old type
- -> TcM (CoercionI, TcType) -- (coercion, new type)
-tcGenericNormaliseFamInst fun ty
- | Just ty' <- tcView ty = tcGenericNormaliseFamInst fun ty'
-tcGenericNormaliseFamInst fun (TyConApp tyCon tys)
- = do { (cois, ntys) <- mapAndUnzipM (tcGenericNormaliseFamInst fun) tys
- ; let tycon_coi = mkTyConAppCoI tyCon ntys cois
- ; maybe_ty_co <- fun (mkTyConApp tyCon ntys) -- use normalised args!
- ; case maybe_ty_co of
- -- a matching family instance exists
- Just (ty', co) ->
- do { let first_coi = mkTransCoI tycon_coi (ACo co)
- ; (rest_coi, nty) <- tcGenericNormaliseFamInst fun ty'
- ; let fix_coi = mkTransCoI first_coi rest_coi
- ; return (fix_coi, nty)
- }
- -- no matching family instance exists
- -- we do not do anything
- Nothing -> return (tycon_coi, mkTyConApp tyCon ntys)
- }
-tcGenericNormaliseFamInst fun (AppTy ty1 ty2)
- = do { (coi1,nty1) <- tcGenericNormaliseFamInst fun ty1
- ; (coi2,nty2) <- tcGenericNormaliseFamInst fun ty2
- ; return (mkAppTyCoI nty1 coi1 nty2 coi2, mkAppTy nty1 nty2)
- }
-tcGenericNormaliseFamInst fun (FunTy ty1 ty2)
- = do { (coi1,nty1) <- tcGenericNormaliseFamInst fun ty1
- ; (coi2,nty2) <- tcGenericNormaliseFamInst fun ty2
- ; return (mkFunTyCoI nty1 coi1 nty2 coi2, mkFunTy nty1 nty2)
- }
-tcGenericNormaliseFamInst fun (ForAllTy tyvar ty1)
- = do { (coi,nty1) <- tcGenericNormaliseFamInst fun ty1
- ; return (mkForAllTyCoI tyvar coi, mkForAllTy tyvar nty1)
- }
-tcGenericNormaliseFamInst fun ty@(TyVarTy tv)
- | isTcTyVar tv
- = do { traceTc (text "tcGenericNormaliseFamInst" <+> ppr ty)
- ; res <- lookupTcTyVar tv
- ; case res of
- DoneTv _ ->
- do { maybe_ty' <- fun ty
- ; case maybe_ty' of
- Nothing -> return (IdCo, ty)
- Just (ty', co1) ->
- do { (coi2, ty'') <- tcGenericNormaliseFamInst fun ty'
- ; return (ACo co1 `mkTransCoI` coi2, ty'')
- }
- }
- IndirectTv ty' -> tcGenericNormaliseFamInst fun ty'
- }
- | otherwise
- = return (IdCo, ty)
-tcGenericNormaliseFamInst fun (PredTy predty)
- = do { (coi, pred') <- tcGenericNormaliseFamInstPred fun predty
- ; return (coi, PredTy pred') }
-
----------------------------------
-tcGenericNormaliseFamInstPred :: (TcType -> TcM (Maybe (TcType,Coercion)))
- -> TcPredType
- -> TcM (CoercionI, TcPredType)
-
-tcGenericNormaliseFamInstPred fun (ClassP cls tys)
- = do { (cois, tys')<- mapAndUnzipM (tcGenericNormaliseFamInst fun) tys
- ; return (mkClassPPredCoI cls tys' cois, ClassP cls tys')
- }
-tcGenericNormaliseFamInstPred fun (IParam ipn ty)
- = do { (coi, ty') <- tcGenericNormaliseFamInst fun ty
- ; return $ (mkIParamPredCoI ipn coi, IParam ipn ty')
- }
-tcGenericNormaliseFamInstPred fun (EqPred ty1 ty2)
- = do { (coi1, ty1') <- tcGenericNormaliseFamInst fun ty1
- ; (coi2, ty2') <- tcGenericNormaliseFamInst fun ty2
- ; return (mkEqPredCoI ty1' coi1 ty2' coi2, EqPred ty1' ty2') }
-\end{code}
-
-
-%************************************************************************
-%* *
-\section{Normalisation of equality constraints}
-%* *
-%************************************************************************
-
-Note [Inconsistencies in equality constraints]
-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-We guarantee that we raise an error if we discover any inconsistencies (i.e.,
-equalities that if presented to the unifer in TcUnify would result in an
-error) during normalisation of wanted constraints. This is especially so that
-we don't solve wanted constraints under an inconsistent given set. In
-particular, we don't want to permit signatures, such as
-
- bad :: (Int ~ Bool => Int) -> a -> a
-
-\begin{code}
-normaliseGivenEqs :: [Inst] -> TcM ([Inst], TcM ())
-normaliseGivenEqs givens
- = do { traceTc (text "normaliseGivenEqs <-" <+> ppr givens)
- ; (result, deSkolem) <-
- rewriteToFixedPoint (Just ("(SkolemOccurs)", skolemOccurs))
- [ ("(ZONK)", dontRerun $ zonkInsts)
- , ("(TRIVIAL)", dontRerun $ trivialRule)
- , ("(DECOMP)", decompRule)
- , ("(TOP)", topRule)
- , ("(SUBST)", substRule) -- incl. occurs check
- ] givens
- ; traceTc (text "normaliseGivenEqs ->" <+> ppr result)
- ; return (result, deSkolem)
- }
-\end{code}
-
-\begin{code}
-normaliseWantedEqs :: [Inst] -- givens
- -> [Inst] -- wanteds
- -> TcM [Inst] -- irreducible wanteds
-normaliseWantedEqs givens wanteds
- = do { traceTc $ text "normaliseWantedEqs <-" <+> ppr wanteds
- <+> text "with" <+> ppr givens
- ; result <- liftM fst $ rewriteToFixedPoint Nothing
- [ ("(ZONK)", dontRerun $ zonkInsts)
- , ("(TRIVIAL)", dontRerun $ trivialRule)
- , ("(DECOMP)", decompRule)
- , ("(TOP)", topRule)
- , ("(GIVEN)", substGivens givens) -- incl. occurs check
- , ("(UNIFY)", unifyMetaRule) -- incl. occurs check
- , ("(SUBST)", substRule) -- incl. occurs check
- ] wanteds
- ; traceTc (text "normaliseWantedEqs ->" <+> ppr result)
- ; return result
- }
- where
- -- Use `substInst' with every given on all the wanteds.
- substGivens :: [Inst] -> [Inst] -> TcM ([Inst], Bool)
- substGivens [] wanteds = return (wanteds, False)
- substGivens (g:gs) wanteds
- = do { (wanteds1, changed1) <- substGivens gs wanteds
- ; (wanteds2, changed2) <- substInst g wanteds1
- ; return (wanteds2, changed1 || changed2)
- }
-\end{code}
-
-
-%************************************************************************
-%* *
-\section{Normalisation of non-equality dictionaries}
-%* *
-%************************************************************************
-
-\begin{code}
-normaliseGivenDicts, normaliseWantedDicts
- :: [Inst] -- given equations
- -> [Inst] -- dictionaries
- -> TcM ([Inst],TcDictBinds)
-
-normaliseGivenDicts eqs dicts = normalise_dicts eqs dicts False
-normaliseWantedDicts eqs dicts = normalise_dicts eqs dicts True
-
-normalise_dicts
- :: [Inst] -- given equations
- -> [Inst] -- dictionaries
- -> Bool -- True <=> the dicts are wanted
- -- Fals <=> they are given
- -> TcM ([Inst],TcDictBinds)
-normalise_dicts given_eqs dicts is_wanted
- = do { traceTc $ let name | is_wanted = "normaliseWantedDicts <-"
- | otherwise = "normaliseGivenDicts <-"
- in
- text name <+> ppr dicts <+>
- text "with" <+> ppr given_eqs
- ; (dicts0, binds0) <- normaliseInsts is_wanted dicts
- ; (dicts1, binds1) <- substEqInDictInsts is_wanted given_eqs dicts0
- ; let binds01 = binds0 `unionBags` binds1
- ; if isEmptyBag binds1
- then return (dicts1, binds01)
- else do { (dicts2, binds2) <-
- normalise_dicts given_eqs dicts1 is_wanted
- ; return (dicts2, binds01 `unionBags` binds2) } }
-\end{code}
-
-
-%************************************************************************
-%* *
-\section{Normalisation rules and iterative rule application}
-%* *
-%************************************************************************
-
-We have three kinds of normalising rewrite rules:
-
-(1) Normalisation rules that rewrite a set of insts and return a flag indicating
- whether any changes occurred during rewriting that necessitate re-running
- the current rule set.
-
-(2) Precondition rules that rewrite a set of insts and return a monadic action
- that reverts the effect of preconditioning.
-
-(3) Idempotent normalisation rules that never require re-running the rule set.
-
-\begin{code}
-type RewriteRule = [Inst] -> TcM ([Inst], Bool) -- rewrite, maybe re-run
-type PrecondRule = [Inst] -> TcM ([Inst], TcM ()) -- rewrite, revertable
-type IdemRewriteRule = [Inst] -> TcM [Inst] -- rewrite, don't re-run
-
-type NamedRule = (String, RewriteRule) -- rule with description
-type NamedPreRule = (String, PrecondRule) -- precond with desc
-\end{code}
-
-Template lifting idempotent rules to full rules (which can be put into a rule
-set).
-
-\begin{code}
-dontRerun :: IdemRewriteRule -> RewriteRule
-dontRerun rule insts = liftM addFalse $ rule insts
- where
- addFalse x = (x, False)
-\end{code}
-
-The following function applies a set of rewrite rules until a fixed point is
-reached; i.e., none of the `RewriteRule's require re-running the rule set.
-Optionally, there may be a pre-conditing rule that is applied before any other
-rules are applied and before the rule set is re-run.
-
-The result is the set of rewritten (i.e., normalised) insts and, in case of a
-pre-conditing rule, a monadic action that reverts the effects of
-pre-conditioning - specifically, this is removing introduced skolems.
-
-\begin{code}
-rewriteToFixedPoint :: Maybe NamedPreRule -- optional preconditioning rule
- -> [NamedRule] -- rule set
- -> [Inst] -- insts to rewrite
- -> TcM ([Inst], TcM ())
-rewriteToFixedPoint precondRule rules insts
- = completeRewrite (return ()) precondRule insts
- where
- completeRewrite :: TcM () -> Maybe NamedPreRule -> [Inst]
- -> TcM ([Inst], TcM ())
- completeRewrite dePrecond (Just (precondName, precond)) insts
- = do { traceTc $ text precondName <+> text " <- " <+> ppr insts
- ; (insts', dePrecond') <- precond insts
- ; traceTc $ text precondName <+> text " -> " <+> ppr insts'
- ; tryRules (dePrecond >> dePrecond') rules insts'
- }
- completeRewrite dePrecond Nothing insts
- = tryRules dePrecond rules insts
-
- tryRules dePrecond _ [] = return ([] , dePrecond)
- tryRules dePrecond [] insts = return (insts, dePrecond)
- tryRules dePrecond ((name, rule):rules) insts
- = do { traceTc $ text name <+> text " <- " <+> ppr insts
- ; (insts', rerun) <- rule insts
- ; traceTc $ text name <+> text " -> " <+> ppr insts'
- ; if rerun then completeRewrite dePrecond precondRule insts'
- else tryRules dePrecond rules insts'
- }
-\end{code}
-
-
-%************************************************************************
-%* *
-\section{Different forms of Inst rewrite rules}
-%* *
-%************************************************************************
-
-Splitting of non-terminating given constraints: skolemOccurs
-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-This is a preconditioning rule exclusively applied to given constraints.
-Moreover, its rewriting is only temporary, as it is undone by way of
-side-effecting mutable type variables after simplification and constraint
-entailment has been completed.
-
-This version is an (attempt at, yet unproven, an) *unflattened* version of
-the SubstL-Ev completion rule.
-
-The above rule is essential to catch non-terminating rules that cannot be
-oriented properly, like
-
- F a ~ [G (F a)]
- or even
- a ~ [G a] , where a is a skolem tyvar
-
-The left-to-right orientiation is not suitable because it does not
-terminate. The right-to-left orientation is not suitable because it
-does not have a type-function on the left. This is undesirable because
-it would hide information. E.g. assume
-
- instance C [x]
-
-then rewriting C [G (F a)] to C (F a) is bad because we cannot now
-see that the C [x] instance applies.
-
-The rule also caters for badly-oriented rules of the form:
-
- F a ~ G (F a)
-
-for which other solutions are possible, but this one will do too.
-
-It's behavior is:
-
- co : ty1 ~ ty2{F ty1}
- >-->
- co : ty1 ~ ty2{b}
- sym (F co) : F ty2{b} ~ b
- where b is a fresh skolem variable
-
-We also cater for the symmetric situation *if* the rule cannot be used as a
-left-to-right rewrite rule.
-
-We also return an action (b := ty1) which is used to eliminate b
-after the dust of normalisation with the completed rewrite system
-has settled.
-
-A subtle point of this transformation is that both coercions in the results
-are strictly speaking incorrect. However, they are correct again after the
-action {B := ty1} has removed the skolem again. This happens immediately
-after constraint entailment has been checked; ie, code outside of the
-simplification and entailment checking framework will never see these
-temporarily incorrect coercions.
-
-NB: We perform this transformation for multiple occurences of ty1 under one
- or multiple family applications on the left-hand side at once (ie, the
- rule doesn't need to be applied multiple times at a single inst). As a
- result we can get two or more insts back.
-
-Note [skolemOccurs loop]
-~~~~~~~~~~~~~~~~~~~~~~~~
-You might think that under
-
- type family F a
- type instance F [a] = [F a]
-
-a signature such as
-
- foo :: (F [a] ~ a) => a
-
-will get us into a loop. However, this is *not* the case. Here is why:
-
- F [a<sk>] ~ a<sk>
-
- -->(TOP)
-
- [F a<sk>] ~ a<sk>
-
- -->(SkolemOccurs)
-
- [b<tau>] ~ a<sk>
- F [b<tau>] ~ b<tau> , with b := F a
-
- -->(TOP)
-
- [b<tau>] ~ a<sk>
- [F b<tau>] ~ b<tau> , with b := F a
-
-At this point (SkolemOccurs) does *not* apply anymore, as
-
- [F b<tau>] ~ b<tau>
-
-is not used as a rewrite rule. The variable b<tau> is not a skolem (cf
-eqInstToRewrite).
-
-(The regression test indexed-types/should_compile/Simple20 checks that the
-described property of the system does not change.)
-
-\begin{code}
-skolemOccurs :: PrecondRule
-skolemOccurs insts
- = do { (instss, undoSkolems) <- mapAndUnzipM oneSkolemOccurs insts
- ; return (concat instss, sequence_ undoSkolems)
- }
- where
- oneSkolemOccurs inst
- = ASSERT( isEqInst inst )
- case eqInstToRewrite inst of
- Just (rewrite, swapped) -> breakRecursion rewrite swapped
- Nothing -> return ([inst], return ())
- where
- -- inst is an elementary rewrite rule, check whether we need to break
- -- it up
- breakRecursion (Rewrite pat body _) swapped
-
- -- skolemOccurs does not apply, leave as is
- | null tysToLiftOut
- = do { traceTc $ text "oneSkolemOccurs: no tys to lift out"
- ; return ([inst], return ())
- }
-
- -- recursive occurence of pat in body under a type family application
- | otherwise
- = do { traceTc $ text "oneSkolemOccurs[TLO]:" <+> ppr tysToLiftOut
- ; skTvs <- mapM (newMetaTyVar TauTv . typeKind) tysToLiftOut
- ; let skTvs_tysTLO = zip skTvs tysToLiftOut
- insertSkolems = return . replace skTvs_tysTLO
- ; (_, body') <- tcGenericNormaliseFamInst insertSkolems body
- ; inst' <- if swapped then mkEqInst (EqPred body' pat) co
- else mkEqInst (EqPred pat body') co
- -- ensure to reconstruct the inst in the
- -- original orientation
- ; traceTc $ text "oneSkolemOccurs[inst']:" <+> ppr inst'
- ; (insts, undoSk) <- mapAndUnzipM (mkSkolemInst inst')
- skTvs_tysTLO
- ; return (inst':insts, sequence_ undoSk)
- }
- where
- co = eqInstCoercion inst
-
- -- all subtypes that are (1) type family instances and (2) contain
- -- the lhs type as part of the type arguments of the type family
- -- constructor
- tysToLiftOut = [mkTyConApp tc tys | (tc, tys) <- tyFamInsts body
- , any (pat `tcPartOfType`) tys]
-
- replace :: [(TcTyVar, Type)] -> Type -> Maybe (Type, Coercion)
- replace [] _ = Nothing
- replace ((skTv, tyTLO):rest) ty
- | tyTLO `tcEqType` ty = Just (mkTyVarTy skTv, undefined)
- | otherwise = replace rest ty
-
- -- create the EqInst for the equality determining the skolem and a
- -- TcM action undoing the skolem introduction
- mkSkolemInst inst' (skTv, tyTLO)
- = do { (co, tyLiftedOut) <- tcEqInstNormaliseFamInst inst' tyTLO
- ; inst <- mkEqInst (EqPred tyLiftedOut (mkTyVarTy skTv))
- (mkGivenCo $ mkSymCoercion (fromACo co))
- -- co /= IdCo due to construction of inst'
- ; return (inst, writeMetaTyVar skTv tyTLO)
- }
-\end{code}
-
-
-Removal of trivial equalities: trivialRule
-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-The following rules exploits the reflexivity of equality:
-
- (Trivial)
- g1 : t ~ t
- >-->
- g1 := t
-
-\begin{code}
-trivialRule :: IdemRewriteRule
-trivialRule insts
- = liftM catMaybes $ mapM trivial insts
- where
- trivial inst
- | ASSERT( isEqInst inst )
- ty1 `tcEqType` ty2
- = do { eitherEqInst inst
- (\cotv -> writeMetaTyVar cotv ty1)
- (\_ -> return ())
- ; return Nothing
- }
- | otherwise
- = return $ Just inst
- where
- (ty1,ty2) = eqInstTys inst
-\end{code}
-
-
-Decomposition of data type constructors: decompRule
-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-Whenever, the same *data* constructors occurs on both sides of an equality, we
-can decompose as in standard unification.
-
- (Decomp)
- g1 : T cs ~ T ds
- >-->
- g21 : c1 ~ d1, ..., g2n : cn ~ dn
- g1 := T g2s
-
-Works also for the case where T is actually an application of a type family
-constructor to a set of types, provided the applications on both sides of the
-~ are identical; see also Note [OpenSynTyCon app] in TcUnify.
-
-We guarantee to raise an error for any inconsistent equalities;
-cf Note [Inconsistencies in equality constraints].
-
-\begin{code}
-decompRule :: RewriteRule
-decompRule insts
- = do { (insts, changed) <- mapAndUnzipM decomp insts
- ; return (concat insts, or changed)
- }
- where
- decomp inst
- = ASSERT( isEqInst inst )
- go ty1 ty2
- where
- (ty1,ty2) = eqInstTys inst
- go ty1 ty2
- | Just ty1' <- tcView ty1 = go ty1' ty2
- | Just ty2' <- tcView ty2 = go ty1 ty2'
-
- go (TyConApp con1 tys1) (TyConApp con2 tys2)
- | con1 == con2 && identicalHead
- = mkArgInsts (mkTyConApp con1) tys1 tys2
-
- | con1 /= con2 && not (isOpenSynTyCon con1 || isOpenSynTyCon con2)
- -- not matching data constructors (of any flavour) are bad news
- = eqInstMisMatch inst
- where
- n = tyConArity con1
- (idxTys1, _) = splitAt n tys1
- (idxTys2, _) = splitAt n tys2
- identicalHead = not (isOpenSynTyCon con1) ||
- idxTys1 `tcEqTypes` idxTys2
-
- go (FunTy fun1 arg1) (FunTy fun2 arg2)
- = mkArgInsts (\[funCo, argCo] -> mkFunTy funCo argCo) [fun1, arg1]
- [fun2, arg2]
-
- -- Applications need a bit of care!
- -- They can match FunTy and TyConApp, so use splitAppTy_maybe
- go (AppTy s1 t1) ty2
- | Just (s2, t2) <- tcSplitAppTy_maybe ty2
- = mkArgInsts (\[s, t] -> mkAppTy s t) [s1, t1] [s2, t2]
-
- -- Symmetric case
- go ty1 (AppTy s2 t2)
- | Just (s1, t1) <- tcSplitAppTy_maybe ty1
- = mkArgInsts (\[s, t] -> mkAppTy s t) [s1, t1] [s2, t2]
-
- -- We already covered all the consistent cases of rigid types on both
- -- sides; so, if we see two rigid types here, we discovered an
- -- inconsistency.
- go ty1 ty2
- | isRigid ty1 && isRigid ty2
- = eqInstMisMatch inst
-
- -- We can neither assert consistency nor inconsistency => defer
- go _ _ = return ([inst], False)
-
- isRigid (TyConApp con _) = not (isOpenSynTyCon con)
- isRigid (FunTy _ _) = True
- isRigid (AppTy _ _) = True
- isRigid _ = False
-
- -- Create insts for matching argument positions (ie, the bit after
- -- '>-->' in the rule description above)
- mkArgInsts con tys1 tys2
- = do { cos <- eitherEqInst inst
- -- old_co := Con1 cos
- (\old_covar ->
- do { cotvs <- zipWithM newMetaCoVar tys1 tys2
- ; let cos = map mkTyVarTy cotvs
- ; writeMetaTyVar old_covar (con cos)
- ; return $ map mkWantedCo cotvs
- })
- -- co_i := Con_i old_co
- (\old_co ->
- return $ map mkGivenCo $
- mkRightCoercions (length tys1) old_co)
- ; insts <- zipWithM mkEqInst (zipWith EqPred tys1 tys2) cos
- ; traceTc (text "decomp identicalHead" <+> ppr insts)
- ; return (insts, not $ null insts)
- }
-\end{code}
-
-
-Rewriting with type instances: topRule
-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-We use (toplevel) type instances to normalise both sides of equalities.
-
- (Top)
- g1 : t ~ s
- >--> co1 :: t ~ t' / co2 :: s ~ s'
- g2 : t' ~ s'
- g1 := co1 * g2 * sym co2
-
-\begin{code}
-topRule :: RewriteRule
-topRule insts
- = do { (insts, changed) <- mapAndUnzipM top insts
- ; return (insts, or changed)
- }
- where
- top inst
- = ASSERT( isEqInst inst )
- do { (coi1, ty1') <- tcNormaliseFamInst ty1
- ; (coi2, ty2') <- tcNormaliseFamInst ty2
- ; case (coi1, coi2) of
- (IdCo, IdCo) -> return (inst, False)
- _ ->
- do { wg_co <-
- eitherEqInst inst
- -- old_co = co1 * new_co * sym co2
- (\old_covar ->
- do { new_cotv <- newMetaCoVar ty1' ty2'
- ; let new_co = mkTyVarTy new_cotv
- old_coi = coi1 `mkTransCoI`
- ACo new_co `mkTransCoI`
- (mkSymCoI coi2)
- ; writeMetaTyVar old_covar (fromACo old_coi)
- ; return $ mkWantedCo new_cotv
- })
- -- new_co = sym co1 * old_co * co2
- (\old_co ->
- return $
- mkGivenCo $
- fromACo $
- mkSymCoI coi1 `mkTransCoI`
- ACo old_co `mkTransCoI` coi2)
- ; new_inst <- mkEqInst (EqPred ty1' ty2') wg_co
- ; return (new_inst, True)
- }
- }
- where
- (ty1,ty2) = eqInstTys inst
-\end{code}
-
-
-Rewriting with equalities: substRule
-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-From a set of insts, use all insts that can be read as rewrite rules to
-rewrite the types in all other insts.
-
- (Subst)
- g : F c ~ t,
- forall g1 : s1{F c} ~ s2{F c}
- >-->
- g2 : s1{t} ~ s2{t}
- g1 := s1{g} * g2 * sym s2{g} <=> g2 := sym s1{g} * g1 * s2{g}
-
-Alternatively, the rewrite rule may have the form (g : a ~ t).
-
-To avoid having to swap rules of the form (g : t ~ F c) and (g : t ~ a),
-where t is neither a variable nor a type family application, we use them for
-rewriting from right-to-left. However, it is crucial to only apply rules
-from right-to-left if they cannot be used left-to-right.
-
-The workhorse is substInst, which performs an occurs check before actually
-using an equality for rewriting. If the type pattern occurs in the type we
-substitute for the pattern, normalisation would diverge.
-
-\begin{code}
-substRule :: RewriteRule
-substRule insts = tryAllInsts insts []
- where
- -- for every inst check whether it can be used to rewrite the others
- -- (we make an effort to keep the insts in order; it makes debugging
- -- easier)
- tryAllInsts [] triedInsts = return (reverse triedInsts, False)
- tryAllInsts (inst:insts) triedInsts
- = do { (insts', changed) <- substInst inst (reverse triedInsts ++ insts)
- ; if changed then return (insertAt (length triedInsts) inst insts',
- True)
- else tryAllInsts insts (inst:triedInsts)
- }
- where
- insertAt n x xs = let (xs1, xs2) = splitAt n xs
- in xs1 ++ [x] ++ xs2
-
--- Use the given inst as a rewrite rule to normalise the insts in the second
--- argument. Don't do anything if the inst cannot be used as a rewrite rule,
--- but do apply it right-to-left, if possible, and if it cannot be used
--- left-to-right.
---
-substInst :: Inst -> [Inst] -> TcM ([Inst], Bool)
-substInst inst insts
- = case eqInstToRewrite inst of
- Just (rewrite, _) -> substEquality rewrite insts
- Nothing -> return (insts, False)
- where
- substEquality :: Rewrite -- elementary rewrite
- -> [Inst] -- insts to rewrite
- -> TcM ([Inst], Bool)
- substEquality eqRule@(Rewrite pat rhs _) insts
- | pat `tcPartOfType` rhs -- occurs check!
- = occurCheckErr pat rhs
- | otherwise
- = do { (insts', changed) <- mapAndUnzipM substOne insts
- ; return (insts', or changed)
- }
- where
- substOne inst
- = ASSERT( isEqInst inst )
- do { (coi1, ty1') <- tcEqRuleNormaliseFamInst eqRule ty1
- ; (coi2, ty2') <- tcEqRuleNormaliseFamInst eqRule ty2
- ; case (coi1, coi2) of
- (IdCo, IdCo) -> return (inst, False)
- _ ->
- do { gw_co <-
- eitherEqInst inst
- -- old_co := co1 * new_co * sym co2
- (\old_covar ->
- do { new_cotv <- newMetaCoVar ty1' ty2'
- ; let new_co = mkTyVarTy new_cotv
- old_coi = coi1 `mkTransCoI`
- ACo new_co `mkTransCoI`
- (mkSymCoI coi2)
- ; writeMetaTyVar old_covar (fromACo old_coi)
- ; return $ mkWantedCo new_cotv
- })
- -- new_co := sym co1 * old_co * co2
- (\old_co ->
- return $
- mkGivenCo $
- fromACo $
- mkSymCoI coi1 `mkTransCoI`
- ACo old_co `mkTransCoI` coi2)
- ; new_inst <- mkEqInst (EqPred ty1' ty2') gw_co
- ; return (new_inst, True)
- }
- }
- where
- (ty1,ty2) = eqInstTys inst
-\end{code}
-
-
-Instantiate meta variables: unifyMetaRule
-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-If an equality equates a meta type variable with a type, we simply instantiate
-the meta variable.
-
- (UnifyMeta)
- g : alpha ~ t
- >-->
- alpha := t
- g := t
-
-Meta variables can only appear in wanted constraints, and this rule should
-only be applied to wanted constraints. We also know that t definitely is
-distinct from alpha (as the trivialRule) has been run on the insts beforehand.
-
-NB: We cannot assume that meta tyvars are empty. They may have been updated
-by another inst in the currently processed wanted list. We need to be very
-careful when updateing type variables (see TcUnify.uUnfilledVar), but at least
-we know that we have no boxes. It's unclear that it would be an advantage to
-common up the code in TcUnify and the code below. Firstly, we don't want
-calls to TcUnify.defer_unification here, and secondly, TcUnify import the
-current module, so we would have to move everything here (Yuk!) or to
-TcMType. Besides, the code here is much simpler due to the lack of boxes.
-
-\begin{code}
-unifyMetaRule :: RewriteRule
-unifyMetaRule insts
- = do { (insts', changed) <- mapAndUnzipM unifyMeta insts
- ; return (concat insts', or changed)