X-Git-Url: http://git.megacz.com/?p=ghc-hetmet.git;a=blobdiff_plain;f=compiler%2Ftypecheck%2FTcTyFuns.lhs;h=188a29e384883c2e8458de2f66d75e7988d54d21;hp=bfe5207f07154d50ffc065daf632c6009a8c916a;hb=c4ec8f2a77894af1c6160c4e8ad5625ab62f0bea;hpb=7b3a6b7645b86f55a8e7109c139b0a3a5a7f43d2 diff --git a/compiler/typecheck/TcTyFuns.lhs b/compiler/typecheck/TcTyFuns.lhs index bfe5207..188a29e 100644 --- a/compiler/typecheck/TcTyFuns.lhs +++ b/compiler/typecheck/TcTyFuns.lhs @@ -3,15 +3,20 @@ normalisation and entailment checking of equality constraints. \begin{code} module TcTyFuns ( - tcNormaliseFamInst, + -- type normalisation wrt to toplevel equalities only + tcNormaliseFamInst, - normaliseGivenEqs, normaliseGivenDicts, - normaliseWantedEqs, normaliseWantedDicts, - solveWantedEqs, - substEqInDictInsts, + -- normalisation and solving of equalities + EqConfig, + normaliseEqs, propagateEqs, finaliseEqs, normaliseDicts, + + -- errors + misMatchMsg, failWithMisMatch, + + -- DEPRECATED: interface for the ICFP'08 algorithm + normaliseGivenEqs, normaliseGivenDicts, + normaliseWantedEqs, normaliseWantedDicts, - -- errors - eqInstMisMatch, misMatchMsg, ) where @@ -31,22 +36,24 @@ import TypeRep ( Type(..) ) import TyCon import HsSyn import VarEnv +import VarSet import Var import Name import Bag import Outputable import SrcLoc ( Located(..) ) import Maybes +import FastString -- standard import Data.List -import Control.Monad (liftM) +import Control.Monad \end{code} %************************************************************************ %* * - Normalisation of types + Normalisation of types wrt toplevel equality schemata %* * %************************************************************************ @@ -92,6 +99,10 @@ possible (ie, we treat family instances as a TRS). Also zonk meta variables. then co : ty ~ ty' \begin{code} +-- |Normalise the given type as far as possible with toplevel equalities. +-- This results in a coercion witnessing the type equality, in addition to the +-- normalised type. +-- tcNormaliseFamInst :: TcType -> TcM (CoercionI, TcType) tcNormaliseFamInst = tcGenericNormaliseFamInst tcUnfoldSynFamInst @@ -99,11 +110,781 @@ tcNormaliseFamInstPred :: TcPredType -> TcM (CoercionI, TcPredType) tcNormaliseFamInstPred = tcGenericNormaliseFamInstPred tcUnfoldSynFamInst \end{code} +%************************************************************************ +%* * + Equality Configurations +%* * +%************************************************************************ + +We maintain normalised equalities together with the skolems introduced as +intermediates during flattening of equalities. + +!!!TODO: Do we really need to keep track of the skolem variables? They are at +the moment not used in instantiateAndExtract, but it is hard to say until we +know exactly how finalisation will fianlly look like. + +\begin{code} +-- |Configuration of normalised equalities used during solving. +-- +data EqConfig = EqConfig { eqs :: [RewriteInst] + , skolems :: TyVarSet + } + +addSkolems :: EqConfig -> TyVarSet -> EqConfig +addSkolems eqCfg newSkolems + = eqCfg {skolems = skolems eqCfg `unionVarSet` newSkolems} + +addEq :: EqConfig -> RewriteInst -> EqConfig +addEq eqCfg eq = eqCfg {eqs = eq : eqs eqCfg} +\end{code} + +The set of operations on an equality configuration. We obtain the initialise +configuration by normalisation ('normaliseEqs'), solve the equalities by +propagation ('propagateEqs'), and eventually finalise the configuration when +no further propoagation is possible. + +!!!TODO: Eventually, normalisation of dictionaries and dictionary +simplification should be included in propagation. + +\begin{code} +-- |Turn a set of equalities into an equality configuration for solving. +-- +-- Precondition: The Insts are zonked. +-- +normaliseEqs :: [Inst] -> TcM EqConfig +normaliseEqs eqs + = do { (eqss, skolemss) <- mapAndUnzipM normEqInst eqs + ; return $ EqConfig { eqs = concat eqss + , skolems = unionVarSets skolemss + } + } + +-- |Solves the equalities as far as possible by applying propagation rules. +-- +propagateEqs :: EqConfig -> TcM EqConfig +propagateEqs eqCfg@(EqConfig {eqs = todoEqs}) + = propagate todoEqs (eqCfg {eqs = []}) + +-- |Finalise a set of equalities after propagation. The Boolean value is +-- `True' iff any flexible variables, except those introduced by flattening +-- (i.e., those in the `skolems' component of the argument) where instantiated. +-- The returned set of instances are all residual wanteds. +-- +finaliseEqs :: EqConfig -> TcM ([Inst], Bool) +finaliseEqs (EqConfig {eqs = eqs, skolems = skolems}) + = do { eqs' <- substitute eqs + ; instantiateAndExtract eqs' skolems + } + +-- |Normalise a set of class instances under a given equality configuration. +-- Both the class instances and the equality configuration may change. The +-- function returns 'Nothing' if neither changes. +-- +normaliseDicts :: EqConfig -> [Inst] -> TcM (Maybe (EqConfig, [Inst])) +normaliseDicts = error "TcTyFuns.normaliseDicts" +\end{code} + + +%************************************************************************ +%* * + Normalisation of equalities +%* * +%************************************************************************ + +A normal equality is a properly oriented equality with associated coercion +that contains at most one family equality (in its left-hand side) is oriented +such that it may be used as a reqrite rule. It has one of the following two +forms: + +(1) co :: F t1..tn ~ t (family equalities) +(2) co :: x ~ t (variable equalities) + +Variable equalities fall again in two classes: + +(2a) co :: x ~ t, where t is *not* a variable, or +(2b) co :: x ~ y, where x > y. + +The types t, t1, ..., tn may not contain any occurrences of synonym +families. Moreover, in Forms (2) & (3), the left-hand side may not occur in +the right-hand side, and the relation x > y is an arbitrary, but total order +on type variables + +!!!TODO: We may need to keep track of swapping for error messages (and to +re-orient on finilisation). + +\begin{code} +data RewriteInst + = RewriteVar -- Form (2) above + { rwi_var :: TyVar -- may be rigid or flexible + , rwi_right :: TcType -- contains no synonym family applications + , rwi_co :: EqInstCo -- the wanted or given coercion + , rwi_loc :: InstLoc + , rwi_name :: Name -- no semantic significance (cf. TcRnTypes.EqInst) + } + | RewriteFam -- Forms (1) above + { rwi_fam :: TyCon -- synonym family tycon + , rwi_args :: [Type] -- contain no synonym family applications + , rwi_right :: TcType -- contains no synonym family applications + , rwi_co :: EqInstCo -- the wanted or given coercion + , rwi_loc :: InstLoc + , rwi_name :: Name -- no semantic significance (cf. TcRnTypes.EqInst) + } + +isWantedRewriteInst :: RewriteInst -> Bool +isWantedRewriteInst = isWantedCo . rwi_co + +rewriteInstToInst :: RewriteInst -> Inst +rewriteInstToInst eq@(RewriteVar {rwi_var = tv}) + = EqInst + { tci_left = mkTyVarTy tv + , tci_right = rwi_right eq + , tci_co = rwi_co eq + , tci_loc = rwi_loc eq + , tci_name = rwi_name eq + } +rewriteInstToInst eq@(RewriteFam {rwi_fam = fam, rwi_args = args}) + = EqInst + { tci_left = mkTyConApp fam args + , tci_right = rwi_right eq + , tci_co = rwi_co eq + , tci_loc = rwi_loc eq + , tci_name = rwi_name eq + } +\end{code} + +The following functions turn an arbitrary equality into a set of normal +equalities. + +\begin{code} +normEqInst :: Inst -> TcM ([RewriteInst], TyVarSet) +normEqInst inst + = ASSERT( isEqInst inst ) + go ty1 ty2 (eqInstCoercion inst) + where + (ty1, ty2) = eqInstTys inst + + -- look through synonyms + go ty1 ty2 co | Just ty1' <- tcView ty1 = go ty1' ty2 co + go ty1 ty2 co | Just ty2' <- tcView ty2 = go ty1 ty2' co + + -- left-to-right rule with type family head + go (TyConApp con args) ty2 co + | isOpenSynTyCon con + = mkRewriteFam con args ty2 co + + -- right-to-left rule with type family head + go ty1 ty2@(TyConApp con args) co + | isOpenSynTyCon con + = do { co' <- mkSymEqInstCo co (ty2, ty1) + ; mkRewriteFam con args ty1 co' + } + + -- no outermost family + go ty1 ty2 co + = do { (ty1', co1, ty1_eqs, ty1_skolems) <- flattenType inst ty1 + ; (ty2', co2, ty2_eqs, ty2_skolems) <- flattenType inst ty2 + ; let ty12_eqs = ty1_eqs ++ ty2_eqs + rewriteCo = co1 `mkTransCoercion` mkSymCoercion co2 + eqTys = (ty1', ty2') + ; (co', ty12_eqs') <- adjustCoercions co rewriteCo eqTys ty12_eqs + ; eqs <- checkOrientation ty1' ty2' co' inst + ; return $ (eqs ++ ty12_eqs', + ty1_skolems `unionVarSet` ty2_skolems) + } + + mkRewriteFam con args ty2 co + = do { (args', cargs, args_eqss, args_skolemss) + <- mapAndUnzip4M (flattenType inst) args + ; (ty2', co2, ty2_eqs, ty2_skolems) <- flattenType inst ty2 + ; let rewriteCo = mkTyConApp con cargs `mkTransCoercion` + mkSymCoercion co2 + all_eqs = concat args_eqss ++ ty2_eqs + eqTys = (mkTyConApp con args', ty2') + ; (co', all_eqs') <- adjustCoercions co rewriteCo eqTys all_eqs + ; let thisRewriteFam = RewriteFam + { rwi_fam = con + , rwi_args = args' + , rwi_right = ty2' + , rwi_co = co' + , rwi_loc = tci_loc inst + , rwi_name = tci_name inst + } + ; return $ (thisRewriteFam : all_eqs', + unionVarSets (ty2_skolems:args_skolemss)) + } + +checkOrientation :: Type -> Type -> EqInstCo -> Inst -> TcM [RewriteInst] +-- Performs the occurs check, decomposition, and proper orientation +-- (returns a singleton, or an empty list in case of a trivial equality) +-- NB: We cannot assume that the two types already have outermost type +-- synonyms expanded due to the recursion in the case of type applications. +checkOrientation ty1 ty2 co inst + = go ty1 ty2 + where + -- look through synonyms + go ty1 ty2 | Just ty1' <- tcView ty1 = go ty1' ty2 + go ty1 ty2 | Just ty2' <- tcView ty2 = go ty1 ty2' + + -- identical types => trivial + go ty1 ty2 + | ty1 `tcEqType` ty2 + = do { mkIdEqInstCo co ty1 + ; return [] + } + + -- two tvs, left greater => unchanged + go ty1@(TyVarTy tv1) ty2@(TyVarTy tv2) + | tv1 > tv2 + = mkRewriteVar tv1 ty2 co + + -- two tvs, right greater => swap + | otherwise + = do { co' <- mkSymEqInstCo co (ty2, ty1) + ; mkRewriteVar tv2 ty1 co' + } + + -- only lhs is a tv => unchanged + go ty1@(TyVarTy tv1) ty2 + | ty1 `tcPartOfType` ty2 -- occurs check! + = occurCheckErr ty1 ty2 + | otherwise + = mkRewriteVar tv1 ty2 co + + -- only rhs is a tv => swap + go ty1 ty2@(TyVarTy tv2) + | ty2 `tcPartOfType` ty1 -- occurs check! + = occurCheckErr ty2 ty1 + | otherwise + = do { co' <- mkSymEqInstCo co (ty2, ty1) + ; mkRewriteVar tv2 ty1 co' + } + + -- type applications => decompose + go ty1 ty2 + | Just (ty1_l, ty1_r) <- repSplitAppTy_maybe ty1 -- won't split fam apps + , Just (ty2_l, ty2_r) <- repSplitAppTy_maybe ty2 + = do { (co_l, co_r) <- mkAppEqInstCo co (ty1_l, ty2_l) (ty1_r, ty2_r) + ; eqs_l <- checkOrientation ty1_l ty2_l co_l inst + ; eqs_r <- checkOrientation ty1_r ty2_r co_r inst + ; return $ eqs_l ++ eqs_r + } +-- !!!TODO: would be more efficient to handle the FunApp and the data +-- constructor application explicitly. + + -- inconsistency => type error + go ty1 ty2 + = ASSERT( (not . isForAllTy $ ty1) && (not . isForAllTy $ ty2) ) + eqInstMisMatch inst + + mkRewriteVar tv ty co = return [RewriteVar + { rwi_var = tv + , rwi_right = ty + , rwi_co = co + , rwi_loc = tci_loc inst + , rwi_name = tci_name inst + }] + +flattenType :: Inst -- context to get location & name + -> Type -- the type to flatten + -> TcM (Type, -- the flattened type + Coercion, -- coercion witness of flattening wanteds + [RewriteInst], -- extra equalities + TyVarSet) -- new intermediate skolems +-- Removes all family synonyms from a type by moving them into extra equalities +flattenType inst ty + = go ty + where + -- look through synonyms + go ty | Just ty' <- tcView ty = go ty' + + -- type family application => flatten to "id :: F t1'..tn' ~ alpha" + go ty@(TyConApp con args) + | isOpenSynTyCon con + = do { (args', cargs, args_eqss, args_skolemss) <- mapAndUnzip4M go args + ; alpha <- newFlexiTyVar (typeKind ty) + ; let alphaTy = mkTyVarTy alpha + ; cotv <- newMetaCoVar (mkTyConApp con args') alphaTy + ; let thisRewriteFam = RewriteFam + { rwi_fam = con + , rwi_args = args' + , rwi_right = alphaTy + , rwi_co = mkWantedCo cotv + , rwi_loc = tci_loc inst + , rwi_name = tci_name inst + } + ; return (alphaTy, + mkTyConApp con cargs `mkTransCoercion` mkTyVarTy cotv, + thisRewriteFam : concat args_eqss, + unionVarSets args_skolemss `extendVarSet` alpha) + } -- adding new unflatten var inst + + -- data constructor application => flatten subtypes + -- NB: Special cased for efficiency - could be handled as type application + go (TyConApp con args) + = do { (args', cargs, args_eqss, args_skolemss) <- mapAndUnzip4M go args + ; return (mkTyConApp con args', + mkTyConApp con cargs, + concat args_eqss, + unionVarSets args_skolemss) + } + + -- function type => flatten subtypes + -- NB: Special cased for efficiency - could be handled as type application + go (FunTy ty_l ty_r) + = do { (ty_l', co_l, eqs_l, skolems_l) <- go ty_l + ; (ty_r', co_r, eqs_r, skolems_r) <- go ty_r + ; return (mkFunTy ty_l' ty_r', + mkFunTy co_l co_r, + eqs_l ++ eqs_r, + skolems_l `unionVarSet` skolems_r) + } + + -- type application => flatten subtypes + go (AppTy ty_l ty_r) +-- | Just (ty_l, ty_r) <- repSplitAppTy_maybe ty + = do { (ty_l', co_l, eqs_l, skolems_l) <- go ty_l + ; (ty_r', co_r, eqs_r, skolems_r) <- go ty_r + ; return (mkAppTy ty_l' ty_r', + mkAppTy co_l co_r, + eqs_l ++ eqs_r, + skolems_l `unionVarSet` skolems_r) + } + + -- free of type families => leave as is + go ty + = ASSERT( not . isForAllTy $ ty ) + return (ty, ty, [] , emptyVarSet) + +adjustCoercions :: EqInstCo -- coercion of original equality + -> Coercion -- coercion witnessing the rewrite + -> (Type, Type) -- type sof flattened equality + -> [RewriteInst] -- equalities from flattening + -> TcM (EqInstCo, -- coercion for flattened equality + [RewriteInst]) -- final equalities from flattening +-- Depending on whether we flattened a local or wanted equality, that equality's +-- coercion and that of the new ones are adjusted +adjustCoercions co rewriteCo eqTys all_eqs + | isWantedCo co + = do { co' <- mkRightTransEqInstCo co rewriteCo eqTys + ; return (co', all_eqs) + } + | otherwise + = return (co, map wantedToLocal all_eqs) + where + wantedToLocal eq = eq {rwi_co = mkGivenCo (rwi_right eq)} +\end{code} + + +%************************************************************************ +%* * + Propagation of equalities +%* * +%************************************************************************ + +Apply the propagation rules exhaustively. + +\begin{code} +propagate :: [RewriteInst] -> EqConfig -> TcM EqConfig +propagate [] eqCfg = return eqCfg +propagate (eq:eqs) eqCfg + = do { optEqs <- applyTop eq + ; case optEqs of + + -- Top applied to 'eq' => retry with new equalities + Just (eqs2, skolems2) + -> propagate (eqs2 ++ eqs) (eqCfg `addSkolems` skolems2) + + -- Top doesn't apply => try subst rules with all other + -- equalities, after that 'eq' can go into the residual list + Nothing + -> do { (eqs', eqCfg') <- applySubstRules eq eqs eqCfg + ; propagate eqs' (eqCfg' `addEq` eq) + } + } + +applySubstRules :: RewriteInst -- currently considered eq + -> [RewriteInst] -- todo eqs list + -> EqConfig -- residual + -> TcM ([RewriteInst], EqConfig) -- new todo & residual +applySubstRules eq todoEqs (eqConfig@EqConfig {eqs = resEqs}) + = do { (newEqs_t, unchangedEqs_t, skolems_t) <- mapSubstRules eq todoEqs + ; (newEqs_r, unchangedEqs_r, skolems_r) <- mapSubstRules eq resEqs + ; return (newEqs_t ++ newEqs_r ++ unchangedEqs_t, + eqConfig {eqs = unchangedEqs_r} + `addSkolems` (skolems_t `unionVarSet` skolems_r)) + } + +mapSubstRules :: RewriteInst -- try substituting this equality + -> [RewriteInst] -- into these equalities + -> TcM ([RewriteInst], [RewriteInst], TyVarSet) +mapSubstRules eq eqs + = do { (newEqss, unchangedEqss, skolemss) <- mapAndUnzip3M (substRules eq) eqs + ; return (concat newEqss, concat unchangedEqss, unionVarSets skolemss) + } + where + substRules eq1 eq2 + = do { -- try the SubstFam rule + optEqs <- applySubstFam eq1 eq2 + ; case optEqs of + Just (eqs, skolems) -> return (eqs, [], skolems) + Nothing -> do + { -- try the SubstVarVar rule + optEqs <- applySubstVarVar eq1 eq2 + ; case optEqs of + Just (eqs, skolems) -> return (eqs, [], skolems) + Nothing -> do + { -- try the SubstVarFam rule + optEqs <- applySubstVarFam eq1 eq2 + ; case optEqs of + Just eq -> return ([eq], [], emptyVarSet) + Nothing -> return ([], [eq2], emptyVarSet) + -- if no rule matches, we return the equlity we tried to + -- substitute into unchanged + }}} +\end{code} + +Attempt to apply the Top rule. The rule is + + co :: F t1..tn ~ t + =(Top)=> + co' :: [s1/x1, .., sm/xm]s ~ t with co = g s1..sm |> co' + +where g :: forall x1..xm. F u1..um ~ s and [s1/x1, .., sm/xm]u1 == t1. + +Returns Nothing if the rule could not be applied. Otherwise, the resulting +equality is normalised and a list of the normal equalities is returned. + +\begin{code} +applyTop :: RewriteInst -> TcM (Maybe ([RewriteInst], TyVarSet)) + +applyTop eq@(RewriteFam {rwi_fam = fam, rwi_args = args}) + = do { optTyCo <- tcUnfoldSynFamInst (TyConApp fam args) + ; case optTyCo of + Nothing -> return Nothing + Just (lhs, rewrite_co) + -> do { co' <- mkRightTransEqInstCo co rewrite_co (lhs, rhs) + ; let eq' = EqInst + { tci_left = lhs + , tci_right = rhs + , tci_co = co' + , tci_loc = rwi_loc eq + , tci_name = rwi_name eq + } + ; liftM Just $ normEqInst eq' + } + } + where + co = rwi_co eq + rhs = rwi_right eq + +applyTop _ = return Nothing +\end{code} + +Attempt to apply the SubstFam rule. The rule is + + co1 :: F t1..tn ~ t & co2 :: F t1..tn ~ s + =(SubstFam)=> + co1 :: F t1..tn ~ t & co2' :: t ~ s with co2 = co1 |> co2' + +where co1 may be a wanted only if co2 is a wanted, too. + +Returns Nothing if the rule could not be applied. Otherwise, the equality +co2' is normalised and a list of the normal equalities is returned. (The +equality co1 is not returned as it remain unaltered.) + +\begin{code} +applySubstFam :: RewriteInst + -> RewriteInst + -> TcM (Maybe ([RewriteInst], TyVarSet)) +applySubstFam eq1@(RewriteFam {rwi_fam = fam1, rwi_args = args1}) + eq2@(RewriteFam {rwi_fam = fam2, rwi_args = args2}) + | fam1 == fam2 && tcEqTypes args1 args2 && + (isWantedRewriteInst eq2 || not (isWantedRewriteInst eq1)) +-- !!!TODO: tcEqTypes is insufficient as it does not look through type synonyms +-- !!!Check whether anything breaks by making tcEqTypes look through synonyms. +-- !!!Should be ok and we don't want three type equalities. + = do { co2' <- mkRightTransEqInstCo co2 co1 (lhs, rhs) + ; let eq2' = EqInst + { tci_left = lhs + , tci_right = rhs + , tci_co = co2' + , tci_loc = rwi_loc eq2 + , tci_name = rwi_name eq2 + } + ; liftM Just $ normEqInst eq2' + } + where + lhs = rwi_right eq1 + rhs = rwi_right eq2 + co1 = eqInstCoType (rwi_co eq1) + co2 = rwi_co eq2 +applySubstFam _ _ = return Nothing +\end{code} + +Attempt to apply the SubstVarVar rule. The rule is + + co1 :: x ~ t & co2 :: x ~ s + =(SubstVarVar)=> + co1 :: x ~ t & co2' :: t ~ s with co2 = co1 |> co2' + +where co1 may be a wanted only if co2 is a wanted, too. + +Returns Nothing if the rule could not be applied. Otherwise, the equality +co2' is normalised and a list of the normal equalities is returned. (The +equality co1 is not returned as it remain unaltered.) + +\begin{code} +applySubstVarVar :: RewriteInst + -> RewriteInst + -> TcM (Maybe ([RewriteInst], TyVarSet)) +applySubstVarVar eq1@(RewriteVar {rwi_var = tv1}) + eq2@(RewriteVar {rwi_var = tv2}) + | tv1 == tv2 && + (isWantedRewriteInst eq2 || not (isWantedRewriteInst eq1)) + = do { co2' <- mkRightTransEqInstCo co2 co1 (lhs, rhs) + ; let eq2' = EqInst + { tci_left = lhs + , tci_right = rhs + , tci_co = co2' + , tci_loc = rwi_loc eq2 + , tci_name = rwi_name eq2 + } + ; liftM Just $ normEqInst eq2' + } + where + lhs = rwi_right eq1 + rhs = rwi_right eq2 + co1 = eqInstCoType (rwi_co eq1) + co2 = rwi_co eq2 +applySubstVarVar _ _ = return Nothing +\end{code} + +Attempt to apply the SubstVarFam rule. The rule is + + co1 :: x ~ t & co2 :: F s1..sn ~ s + =(SubstVarFam)=> + co1 :: x ~ t & co2' :: [t/x](F s1..sn) ~ s + with co2 = [co1/x](F s1..sn) |> co2' + +where x occurs in F s1..sn. (co1 may be local or wanted.) + +Returns Nothing if the rule could not be applied. Otherwise, the equality +co2' is returned. (The equality co1 is not returned as it remain unaltered.) + +\begin{code} +applySubstVarFam :: RewriteInst -> RewriteInst -> TcM (Maybe RewriteInst) +applySubstVarFam eq1@(RewriteVar {rwi_var = tv1}) + eq2@(RewriteFam {rwi_fam = fam2, rwi_args = args2}) + | tv1 `elemVarSet` tyVarsOfTypes args2 + = do { let co1Subst = substTyWith [tv1] [co1] (mkTyConApp fam2 args2) + args2' = substTysWith [tv1] [rhs1] args2 + lhs2 = mkTyConApp fam2 args2' + ; co2' <- mkRightTransEqInstCo co2 co1Subst (lhs2, rhs2) + ; return $ Just (eq2 {rwi_args = args2', rwi_co = co2'}) + } + where + rhs1 = rwi_right eq1 + rhs2 = rwi_right eq2 + co1 = eqInstCoType (rwi_co eq1) + co2 = rwi_co eq2 +applySubstVarFam _ _ = return Nothing +\end{code} + + +%************************************************************************ +%* * + Finalisation of equalities +%* * +%************************************************************************ + +Exhaustive substitution of all variable equalities of the form co :: x ~ t +(both local and wanted) into the left-hand sides all other equalities. This +may lead to recursive equalities; i.e., (1) we need to apply the substitution +implied by one variable equality exhaustively before turning to the next and +(2) we need an occurs check. + +NB: Gievn that we apply the substitution corresponding to a single equality +exhaustively, before turning to the next, and because we eliminate recursive +eqaulities, all opportunities for subtitution will have been exhausted after +we have considered each equality once. + +\begin{code} +substitute :: [RewriteInst] -> TcM [RewriteInst] +substitute eqs = subst eqs [] + where + subst [] res = return res + subst (eq:eqs) res + = do { eqs' <- mapM (substOne eq) eqs + ; res' <- mapM (substOne eq) res + ; subst eqs' (eq:res') + } + + -- apply [ty/tv] to left-hand side of eq2 + substOne (RewriteVar {rwi_var = tv, rwi_right = ty, rwi_co = co}) eq2 + = do { let co1Subst = mkSymCoercion $ + substTyWith [tv] [eqInstCoType co] (rwi_right eq2) + right2' = substTyWith [tv] [ty] (rwi_right eq2) + left2 = case eq2 of + RewriteVar {rwi_var = tv2} -> mkTyVarTy tv2 + RewriteFam {rwi_fam = fam, + rwi_args = args} ->mkTyConApp fam args + ; co2' <- mkLeftTransEqInstCo (rwi_co eq2) co1Subst (left2, right2') + ; case eq2 of + RewriteVar {rwi_var = tv2} | tv2 `elemVarSet` tyVarsOfType ty + -> occurCheckErr left2 right2' + _ -> return $ eq2 {rwi_right = right2', rwi_co = co2'} + } + + -- changed + substOne _ eq2 + = return eq2 +\end{code} + +For any *wanted* variable equality of the form co :: alpha ~ t or co :: a ~ +alpha, we instantiate alpha with t or a, respectively, and set co := id. +Return all remaining wanted equalities. The Boolean result component is True +if at least one instantiation of a flexible was performed. + +\begin{code} +instantiateAndExtract :: [RewriteInst] -> TyVarSet -> TcM ([Inst], Bool) +instantiateAndExtract eqs _skolems + = do { let wanteds = filter (isWantedCo . rwi_co) eqs + ; wanteds' <- mapM inst wanteds + ; let residuals = catMaybes wanteds' + improved = length wanteds /= length residuals + ; return (map rewriteInstToInst residuals, improved) + } + where + inst eq@(RewriteVar {rwi_var = tv1, rwi_right = ty2, rwi_co = co}) + + -- co :: alpha ~ t + | isMetaTyVar tv1 + = doInst tv1 ty2 co eq + + -- co :: a ~ alpha + | Just tv2 <- tcGetTyVar_maybe ty2 + , isMetaTyVar tv2 + = doInst tv2 (mkTyVarTy tv1) co eq + + inst eq = return $ Just eq + + doInst _ _ (Right ty) _eq = pprPanic "TcTyFuns.doInst: local eq: " + (ppr ty) + doInst tv ty (Left cotv) eq = do { lookupTV <- lookupTcTyVar tv + ; uMeta False tv lookupTV ty cotv + } + where + -- meta variable has been filled already + -- => panic (all equalities should have been zonked on normalisation) + uMeta _swapped _tv (IndirectTv _) _ty _cotv + = panic "TcTyFuns.uMeta: expected zonked equalities" + + -- type variable meets type variable + -- => check that tv2 hasn't been updated yet and choose which to update + uMeta swapped tv1 (DoneTv details1) (TyVarTy tv2) cotv + | tv1 == tv2 + = panic "TcTyFuns.uMeta: normalisation shouldn't allow x ~ x" + + | otherwise + = do { lookupTV2 <- lookupTcTyVar tv2 + ; case lookupTV2 of + IndirectTv ty -> + uMeta swapped tv1 (DoneTv details1) ty cotv + DoneTv details2 -> + uMetaVar swapped tv1 details1 tv2 details2 cotv + } + + ------ Beyond this point we know that ty2 is not a type variable + + -- signature skolem meets non-variable type + -- => cannot update (retain the equality)! + uMeta _swapped _tv (DoneTv (MetaTv (SigTv _) _)) _non_tv_ty _cotv + = return $ Just eq + + -- updatable meta variable meets non-variable type + -- => occurs check, monotype check, and kinds match check, then update + uMeta swapped tv (DoneTv (MetaTv _ ref)) non_tv_ty cotv + = do { -- occurs + monotype check + ; mb_ty' <- checkTauTvUpdate tv non_tv_ty + + ; case mb_ty' of + Nothing -> + -- normalisation shouldn't leave families in non_tv_ty + panic "TcTyFuns.uMeta: unexpected synonym family" + Just ty' -> + do { checkUpdateMeta swapped tv ref ty' -- update meta var + ; writeMetaTyVar cotv ty' -- update co var + ; return Nothing + } + } + + uMeta _ _ _ _ _ = panic "TcTyFuns.uMeta" + + -- uMetaVar: unify two type variables + -- meta variable meets skolem + -- => just update + uMetaVar swapped tv1 (MetaTv _ ref) tv2 (SkolemTv _) cotv + = do { checkUpdateMeta swapped tv1 ref (mkTyVarTy tv2) + ; writeMetaTyVar cotv (mkTyVarTy tv2) + ; return Nothing + } + + -- meta variable meets meta variable + -- => be clever about which of the two to update + -- (from TcUnify.uUnfilledVars minus boxy stuff) + uMetaVar swapped tv1 (MetaTv info1 ref1) tv2 (MetaTv info2 ref2) cotv + = do { case (info1, info2) of + -- Avoid SigTvs if poss + (SigTv _, _ ) | k1_sub_k2 -> update_tv2 + (_, SigTv _) | k2_sub_k1 -> update_tv1 + + (_, _) | k1_sub_k2 -> if k2_sub_k1 && nicer_to_update_tv1 + then update_tv1 -- Same kinds + else update_tv2 + | k2_sub_k1 -> update_tv1 + | otherwise -> kind_err + -- Update the variable with least kind info + -- See notes on type inference in Kind.lhs + -- The "nicer to" part only applies if the two kinds are the same, + -- so we can choose which to do. + + ; writeMetaTyVar cotv (mkTyVarTy tv2) + ; return Nothing + } + where + -- Kinds should be guaranteed ok at this point + update_tv1 = updateMeta tv1 ref1 (mkTyVarTy tv2) + update_tv2 = updateMeta tv2 ref2 (mkTyVarTy tv1) + + kind_err = addErrCtxtM (unifyKindCtxt swapped tv1 (mkTyVarTy tv2)) $ + unifyKindMisMatch k1 k2 + + k1 = tyVarKind tv1 + k2 = tyVarKind tv2 + k1_sub_k2 = k1 `isSubKind` k2 + k2_sub_k1 = k2 `isSubKind` k1 + + nicer_to_update_tv1 = isSystemName (Var.varName tv1) + -- Try to update sys-y type variables in preference to ones + -- gotten (say) by instantiating a polymorphic function with + -- a user-written type sig + + uMetaVar _ _ _ _ _ _ = panic "uMetaVar" +\end{code} + + + +==================== CODE FOR THE OLD ICFP'08 ALGORITHM ====================== + An elementary rewrite is a properly oriented equality with associated coercion that has one of the following two forms: (1) co :: F t1..tn ~ t -(2) co :: a ~ t , where t /= F t1..tn +(2) co :: a ~ t , where t /= F t1..tn and a is a skolem tyvar + +NB: We do *not* use equalities of the form a ~ t where a is a meta tyvar as a +reqrite rule. Instead, such equalities are solved by unification. This is +essential; cf Note [skolemOccurs loop]. The following functions takes an equality instance and turns it into an elementary rewrite if possible. @@ -113,37 +894,41 @@ data Rewrite = Rewrite TcType -- lhs of rewrite rule TcType -- rhs of rewrite rule TcType -- coercion witnessing the rewrite rule -eqInstToRewrite :: Inst -> Maybe Rewrite +eqInstToRewrite :: Inst -> Maybe (Rewrite, Bool) + -- True iff rewrite swapped equality eqInstToRewrite inst = ASSERT( isEqInst inst ) - go (eqInstLeftTy inst) (eqInstRightTy inst) (eqInstType inst) + go ty1 ty2 (eqInstType inst) where + (ty1,ty2) = eqInstTys inst + -- look through synonyms go ty1 ty2 co | Just ty1' <- tcView ty1 = go ty1' ty2 co go ty1 ty2 co | Just ty2' <- tcView ty2 = go ty1 ty2' co - -- rewrite type family applications + -- left-to-right rule with type family head go ty1@(TyConApp con _) ty2 co | isOpenSynTyCon con - = Just $ Rewrite ty1 ty2 co + = Just (Rewrite ty1 ty2 co, False) -- not swapped - -- rewrite skolems + -- left-to-right rule with type variable head go ty1@(TyVarTy tv) ty2 co | isSkolemTyVar tv - = Just $ Rewrite ty1 ty2 co + = Just (Rewrite ty1 ty2 co, False) -- not swapped - -- rewrite type family applications from right-to-left, only after + -- right-to-left rule with type family head, only after -- having checked whether we can work left-to-right go ty1 ty2@(TyConApp con _) co | isOpenSynTyCon con - = Just $ Rewrite ty2 ty1 (mkSymCoercion co) + = Just (Rewrite ty2 ty1 (mkSymCoercion co), True) -- swapped - -- rewrite skolems from right-to-left, only after having checked - -- whether we can work left-to-right + -- right-to-left rule with type variable head, only after + -- having checked whether we can work left-to-right go ty1 ty2@(TyVarTy tv) co | isSkolemTyVar tv - = Just $ Rewrite ty2 ty1 (mkSymCoercion co) + = Just (Rewrite ty2 ty1 (mkSymCoercion co), True) -- swapped + -- this equality is not a rewrite rule => ignore go _ _ _ = Nothing \end{code} @@ -156,8 +941,8 @@ explicitly given elementary rewrite. tcEqInstNormaliseFamInst :: Inst -> TcType -> TcM (CoercionI, TcType) tcEqInstNormaliseFamInst inst ty = case eqInstToRewrite inst of - Just rewrite -> tcEqRuleNormaliseFamInst rewrite ty - Nothing -> return (IdCo, ty) + Just (rewrite, _) -> tcEqRuleNormaliseFamInst rewrite ty + Nothing -> return (IdCo, ty) -- Rewrite by equality rewrite rule tcEqRuleNormaliseFamInst :: Rewrite -- elementary rewrite @@ -223,10 +1008,6 @@ tcGenericNormaliseFamInst fun (ForAllTy tyvar ty1) = do { (coi,nty1) <- tcGenericNormaliseFamInst fun ty1 ; return (mkForAllTyCoI tyvar coi, mkForAllTy tyvar nty1) } -tcGenericNormaliseFamInst fun (NoteTy note ty1) - = do { (coi,nty1) <- tcGenericNormaliseFamInst fun ty1 - ; return (mkNoteTyCoI note coi, NoteTy note nty1) - } tcGenericNormaliseFamInst fun ty@(TyVarTy tv) | isTcTyVar tv = do { traceTc (text "tcGenericNormaliseFamInst" <+> ppr ty) @@ -303,38 +1084,12 @@ normaliseGivenEqs givens \end{code} \begin{code} -normaliseWantedEqs :: [Inst] -> TcM [Inst] -normaliseWantedEqs insts - = do { traceTc (text "normaliseWantedEqs <-" <+> ppr insts) - ; result <- liftM fst $ rewriteToFixedPoint Nothing - [ ("(ZONK)", dontRerun $ zonkInsts) - , ("(TRIVIAL)", dontRerun $ trivialRule) - , ("(DECOMP)", decompRule) - , ("(TOP)", topRule) - , ("(UNIFY)", unifyMetaRule) -- incl. occurs check - , ("(SUBST)", substRule) -- incl. occurs check - ] insts - ; traceTc (text "normaliseWantedEqs ->" <+> ppr result) - ; return result - } -\end{code} - - -%************************************************************************ -%* * -\section{Solving of wanted constraints with respect to a given set} -%* * -%************************************************************************ - -The set of given equalities must have been normalised already. - -\begin{code} -solveWantedEqs :: [Inst] -- givens - -> [Inst] -- wanteds - -> TcM [Inst] -- irreducible wanteds -solveWantedEqs givens wanteds - = do { traceTc $ text "solveWantedEqs <-" <+> ppr wanteds <+> text "with" <+> - ppr givens +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) @@ -342,8 +1097,9 @@ solveWantedEqs givens wanteds , ("(TOP)", topRule) , ("(GIVEN)", substGivens givens) -- incl. occurs check , ("(UNIFY)", unifyMetaRule) -- incl. occurs check + , ("(SUBST)", substRule) -- incl. occurs check ] wanteds - ; traceTc (text "solveWantedEqs ->" <+> ppr result) + ; traceTc (text "normaliseWantedEqs ->" <+> ppr result) ; return result } where @@ -380,14 +1136,18 @@ normalise_dicts -- Fals <=> they are given -> TcM ([Inst],TcDictBinds) normalise_dicts given_eqs dicts is_wanted - = do { traceTc $ text "normalise???Dicts <-" <+> ppr dicts <+> + = 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 given_eqs dicts0 + ; (dicts1, binds1) <- substEqInDictInsts is_wanted given_eqs dicts0 ; let binds01 = binds0 `unionBags` binds1 ; if isEmptyBag binds1 then return (dicts1, binds01) - else do { (dicts2, binds2) <- normaliseGivenDicts given_eqs dicts1 + else do { (dicts2, binds2) <- + normalise_dicts given_eqs dicts1 is_wanted ; return (dicts2, binds01 `unionBags` binds2) } } \end{code} @@ -489,7 +1249,7 @@ oriented properly, like F a ~ [G (F a)] or even - a ~ [G a] + 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 @@ -534,6 +1294,45 @@ NB: We perform this transformation for multiple occurences of ty1 under one 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] ~ a + + -->(TOP) + + [F a] ~ a + + -->(SkolemOccurs) + + [b] ~ a + F [b] ~ b , with b := F a + + -->(TOP) + + [b] ~ a + [F b] ~ b , with b := F a + +At this point (SkolemOccurs) does *not* apply anymore, as + + [F b] ~ b + +is not used as a rewrite rule. The variable b 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 @@ -543,38 +1342,21 @@ skolemOccurs insts where oneSkolemOccurs inst = ASSERT( isEqInst inst ) - isRewriteRule (eqInstLeftTy inst) (eqInstRightTy 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 - -- look through synonyms - isRewriteRule ty1 ty2 | Just ty1' <- tcView ty1 = isRewriteRule ty1' ty2 - isRewriteRule ty1 ty2 | Just ty2' <- tcView ty2 = isRewriteRule ty1 ty2' - - -- left-to-right rule with type family head - isRewriteRule ty1@(TyConApp con _) ty2 - | isOpenSynTyCon con - = breakRecursion ty1 ty2 False -- not swapped - - -- left-to-right rule with type variable head - isRewriteRule ty1@(TyVarTy _) ty2 - = breakRecursion ty1 ty2 False -- not swapped - - -- right-to-left rule with type family head - isRewriteRule ty1 ty2@(TyConApp con _) - | isOpenSynTyCon con - = breakRecursion ty2 ty1 True -- swapped - - -- right-to-left rule with type variable head - isRewriteRule ty1 ty2@(TyVarTy _) - = breakRecursion ty2 ty1 True -- swapped - - -- this equality is not a rewrite rule => ignore - isRewriteRule _ _ = return ([inst], return ()) - - ------------------ - breakRecursion pat body swapped + -- skolemOccurs does not apply, leave as is | null tysToLiftOut - = return ([inst], return ()) + = 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 @@ -629,7 +1411,7 @@ The following rules exploits the reflexivity of equality: \begin{code} trivialRule :: IdemRewriteRule trivialRule insts - = liftM catMaybes $ mappM trivial insts + = liftM catMaybes $ mapM trivial insts where trivial inst | ASSERT( isEqInst inst ) @@ -642,8 +1424,7 @@ trivialRule insts | otherwise = return $ Just inst where - ty1 = eqInstLeftTy inst - ty2 = eqInstRightTy inst + (ty1,ty2) = eqInstTys inst \end{code} @@ -674,8 +1455,9 @@ decompRule insts where decomp inst = ASSERT( isEqInst inst ) - go (eqInstLeftTy inst) (eqInstRightTy 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' @@ -794,8 +1576,7 @@ topRule insts } } where - ty1 = eqInstLeftTy inst - ty2 = eqInstRightTy inst + (ty1,ty2) = eqInstTys inst \end{code} @@ -848,8 +1629,8 @@ substRule insts = tryAllInsts insts [] substInst :: Inst -> [Inst] -> TcM ([Inst], Bool) substInst inst insts = case eqInstToRewrite inst of - Just rewrite -> substEquality rewrite insts - Nothing -> return (insts, False) + Just (rewrite, _) -> substEquality rewrite insts + Nothing -> return (insts, False) where substEquality :: Rewrite -- elementary rewrite -> [Inst] -- insts to rewrite @@ -893,8 +1674,7 @@ substInst inst insts } } where - ty1 = eqInstLeftTy inst - ty2 = eqInstRightTy inst + (ty1,ty2) = eqInstTys inst \end{code} @@ -931,9 +1711,10 @@ unifyMetaRule insts where unifyMeta inst = ASSERT( isEqInst inst ) - go (eqInstLeftTy inst) (eqInstRightTy inst) + go ty1 ty2 (fromWantedCo "unifyMetaRule" $ eqInstCoercion inst) where + (ty1,ty2) = eqInstTys inst go ty1 ty2 cotv | Just ty1' <- tcView ty1 = go ty1' ty2 cotv | Just ty2' <- tcView ty2 = go ty1 ty2' cotv @@ -953,26 +1734,30 @@ unifyMetaRule insts uMeta _swapped _tv (IndirectTv _) _ty _cotv = return ([inst], False) - -- signature skolem meets non-variable type - -- => cannot update! - uMeta _swapped _tv (DoneTv (MetaTv (SigTv _) _)) ty _cotv - | not $ isTyVarTy ty - = return ([inst], False) - -- type variable meets type variable -- => check that tv2 hasn't been updated yet and choose which to update uMeta swapped tv1 (DoneTv details1) (TyVarTy tv2) cotv + | tv1 == tv2 + = return ([inst], False) -- The two types are already identical + + | otherwise = do { lookupTV2 <- lookupTcTyVar tv2 ; case lookupTV2 of - IndirectTv ty -> uMeta swapped tv1 (DoneTv details1) ty cotv - DoneTv details2 -> - uMetaVar swapped tv1 details1 tv2 details2 cotv + IndirectTv ty -> uMeta swapped tv1 (DoneTv details1) ty cotv + DoneTv details2 -> uMetaVar swapped tv1 details1 tv2 details2 cotv } + ------ Beyond this point we know that ty2 is not a type variable + + -- signature skolem meets non-variable type + -- => cannot update! + uMeta _swapped _tv (DoneTv (MetaTv (SigTv _) _)) _non_tv_ty _cotv + = return ([inst], False) + -- updatable meta variable meets non-variable type -- => occurs check, monotype check, and kinds match check, then update - uMeta swapped tv (DoneTv (MetaTv _ ref)) ty cotv - = do { mb_ty' <- checkTauTvUpdate tv ty -- occurs + monotype check + uMeta swapped tv (DoneTv (MetaTv _ ref)) non_tv_ty cotv + = do { mb_ty' <- checkTauTvUpdate tv non_tv_ty -- occurs + monotype check ; case mb_ty' of Nothing -> return ([inst], False) -- tv occurs in faminst Just ty' -> @@ -984,6 +1769,7 @@ unifyMetaRule insts uMeta _ _ _ _ _ = panic "uMeta" + -- uMetaVar: unify two type variables -- meta variable meets skolem -- => just update uMetaVar swapped tv1 (MetaTv _ ref) tv2 (SkolemTv _) cotv @@ -1051,10 +1837,11 @@ form where F is a type family. \begin{code} -substEqInDictInsts :: [Inst] -- given equalities (used as rewrite rules) +substEqInDictInsts :: Bool -- whether the *dictionaries* are wanted/given + -> [Inst] -- given equalities (used as rewrite rules) -> [Inst] -- dictinaries to be normalised -> TcM ([Inst], TcDictBinds) -substEqInDictInsts eqInsts dictInsts +substEqInDictInsts isWanted eqInsts dictInsts = do { traceTc (text "substEqInDictInst <-" <+> ppr dictInsts) ; dictInsts' <- foldlM rewriteWithOneEquality (dictInsts, emptyBag) eqInsts @@ -1068,7 +1855,7 @@ substEqInDictInsts eqInsts dictInsts tci_right = target}) | isOpenSynTyConApp pattern || isTyVarTy pattern = do { (dictInsts', moreDictBinds) <- - genericNormaliseInsts True {- wanted -} applyThisEq dictInsts + genericNormaliseInsts isWanted applyThisEq dictInsts ; return (dictInsts', dictBinds `unionBags` moreDictBinds) } where @@ -1143,11 +1930,17 @@ genericNormaliseInsts isWanted fun insts -- else -- dict' = dict `cast` co expr = HsVar $ instToId source_dict - cast_expr = HsWrap (WpCo st_co) expr + cast_expr = HsWrap (WpCast st_co) expr rhs = L (instLocSpan loc) cast_expr binds = instToDictBind target_dict rhs -- return the new inst - ; traceTc $ text "genericNormaliseInst ->" <+> ppr dict' + ; traceTc $ let name | isWanted + = "genericNormaliseInst (wanted) ->" + | otherwise + = "genericNormaliseInst (given) ->" + in + text name <+> ppr dict' <+> + text "with" <+> ppr binds ; return (dict', binds) } } @@ -1155,6 +1948,8 @@ genericNormaliseInsts isWanted fun insts -- TOMDO: What do we have to do about ImplicInst, Method, and LitInst?? normaliseOneInst _isWanted _fun inst = do { inst' <- zonkInst inst + ; traceTc $ text "*** TcTyFuns.normaliseOneInst: Skipping" <+> + ppr inst ; return (inst', emptyBag) } \end{code} @@ -1173,45 +1968,49 @@ somethingdifferent message. eqInstMisMatch :: Inst -> TcM a eqInstMisMatch inst = ASSERT( isEqInst inst ) - do { (env, msg) <- misMatchMsg ty_act ty_exp - ; setErrCtxt ctxt $ - failWithTcM (env, msg) - } + setErrCtxt ctxt $ failWithMisMatch ty_act ty_exp where - ty_act = eqInstLeftTy inst - ty_exp = eqInstRightTy inst - InstLoc _ _ ctxt = instLoc inst + (ty_act, ty_exp) = eqInstTys inst + InstLoc _ _ ctxt = instLoc inst ----------------------- -misMatchMsg :: TcType -> TcType -> TcM (TidyEnv, SDoc) +failWithMisMatch :: TcType -> TcType -> TcM a -- Generate the message when two types fail to match, -- going to some trouble to make it helpful. -- The argument order is: actual type, expected type -misMatchMsg ty_act ty_exp +failWithMisMatch ty_act ty_exp = do { env0 <- tcInitTidyEnv ; ty_exp <- zonkTcType ty_exp ; ty_act <- zonkTcType ty_act - ; (env1, pp_exp, extra_exp) <- ppr_ty env0 ty_exp - ; (env2, pp_act, extra_act) <- ppr_ty env1 ty_act - ; return (env2, - sep [sep [ptext SLIT("Couldn't match expected type") <+> pp_exp, - nest 7 $ - ptext SLIT("against inferred type") <+> pp_act], - nest 2 (extra_exp $$ extra_act)]) } - -ppr_ty :: TidyEnv -> TcType -> TcM (TidyEnv, SDoc, SDoc) -ppr_ty env ty - = do { let (env1, tidy_ty) = tidyOpenType env ty - ; (env2, extra) <- ppr_extra env1 tidy_ty - ; return (env2, quotes (ppr tidy_ty), extra) } - --- (ppr_extra env ty) shows extra info about 'ty' -ppr_extra :: TidyEnv -> Type -> TcM (TidyEnv, SDoc) -ppr_extra env (TyVarTy tv) - | isSkolemTyVar tv || isSigTyVar tv - = return (env1, pprSkolTvBinding tv1) + ; failWithTcM (misMatchMsg env0 (ty_act, ty_exp)) + } + +misMatchMsg :: TidyEnv -> (TcType, TcType) -> (TidyEnv, SDoc) +misMatchMsg env0 (ty_act, ty_exp) + = let (env1, pp_exp, extra_exp) = ppr_ty env0 ty_exp + (env2, pp_act, extra_act) = ppr_ty env1 ty_act + msg = sep [sep [ptext (sLit "Couldn't match expected type") <+> pp_exp, + nest 7 $ + ptext (sLit "against inferred type") <+> pp_act], + nest 2 (extra_exp $$ extra_act)] + in + (env2, msg) + where - (env1, tv1) = tidySkolemTyVar env tv + ppr_ty :: TidyEnv -> TcType -> (TidyEnv, SDoc, SDoc) + ppr_ty env ty + = let (env1, tidy_ty) = tidyOpenType env ty + (env2, extra) = ppr_extra env1 tidy_ty + in + (env2, quotes (ppr tidy_ty), extra) + + -- (ppr_extra env ty) shows extra info about 'ty' + ppr_extra :: TidyEnv -> Type -> (TidyEnv, SDoc) + ppr_extra env (TyVarTy tv) + | isTcTyVar tv && (isSkolemTyVar tv || isSigTyVar tv) && not (isUnk tv) + = (env1, pprSkolTvBinding tv1) + where + (env1, tv1) = tidySkolemTyVar env tv -ppr_extra env _ty = return (env, empty) -- Normal case + ppr_extra env _ty = (env, empty) -- Normal case \end{code}