\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
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
%* *
%************************************************************************
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
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.
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}
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
= 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)
\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)
, ("(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
-- 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}
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
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
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
\begin{code}
trivialRule :: IdemRewriteRule
trivialRule insts
- = liftM catMaybes $ mappM trivial insts
+ = liftM catMaybes $ mapM trivial insts
where
trivial inst
| ASSERT( isEqInst inst )
| otherwise
= return $ Just inst
where
- ty1 = eqInstLeftTy inst
- ty2 = eqInstRightTy inst
+ (ty1,ty2) = eqInstTys inst
\end{code}
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'
}
}
where
- ty1 = eqInstLeftTy inst
- ty2 = eqInstRightTy inst
+ (ty1,ty2) = eqInstTys inst
\end{code}
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
}
}
where
- ty1 = eqInstLeftTy inst
- ty2 = eqInstRightTy inst
+ (ty1,ty2) = eqInstTys inst
\end{code}
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
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' ->
uMeta _ _ _ _ _ = panic "uMeta"
+ -- uMetaVar: unify two type variables
-- meta variable meets skolem
-- => just update
uMetaVar swapped tv1 (MetaTv _ ref) tv2 (SkolemTv _) cotv
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
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
-- 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)
}
}
-- 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}
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}
projects / ghc-hetmet.git / blobdiff