-- type normalisation wrt to toplevel equalities only
tcNormaliseFamInst,
- -- normalisation and solving of equalities
- EqConfig,
- normaliseEqs, propagateEqs, finaliseEqs, normaliseDicts,
+ -- instance normalisation wrt to equalities
+ tcReduceEqs,
-- errors
misMatchMsg, failWithMisMatch,
- -- DEPRECATED: interface for the ICFP'08 algorithm
- normaliseGivenEqs, normaliseGivenDicts,
- normaliseWantedEqs, normaliseWantedDicts,
-
- ) where
+) where
#include "HsVersions.h"
mkTyConApp coe_tc tys')
where
tys' = rep_tys ++ restTys
- coe_tc = expectJust "TcTyFun.tcUnfoldSynFamInst"
+ coe_tc = expectJust "TcTyFuns.tcUnfoldSynFamInst"
(tyConFamilyCoercion_maybe rep_tc)
}
where
--
tcNormaliseFamInst :: TcType -> TcM (CoercionI, TcType)
tcNormaliseFamInst = tcGenericNormaliseFamInst tcUnfoldSynFamInst
+\end{code}
+
+Generic normalisation of 'Type's and 'PredType's; ie, walk the type term and
+apply the normalisation function gives as the first argument to every TyConApp
+and every TyVarTy subterm.
+
+ tcGenericNormaliseFamInst fun ty = (co, ty')
+ then co : ty ~ ty'
+
+This function is (by way of using smart constructors) careful to ensure that
+the returned coercion is exactly IdCo (and not some semantically equivalent,
+but syntactically different coercion) whenever (ty' `tcEqType` ty). This
+makes it easy for the caller to determine whether the type changed. BUT
+even if we return IdCo, ty' may be *syntactically* different from ty due to
+unfolded closed type synonyms (by way of tcCoreView). In the interest of
+good error messages, callers should discard ty' in favour of ty in this case.
+
+\begin{code}
+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}
+
+
+%************************************************************************
+%* *
+ Normalisation of instances wrt to equalities
+%* *
+%************************************************************************
-tcNormaliseFamInstPred :: TcPredType -> TcM (CoercionI, TcPredType)
-tcNormaliseFamInstPred = tcGenericNormaliseFamInstPred tcUnfoldSynFamInst
+\begin{code}
+tcReduceEqs :: [Inst] -- locals
+ -> [Inst] -- wanteds
+ -> TcM ([Inst], -- normalised locals (w/o equalities)
+ [Inst], -- normalised wanteds (including equalities)
+ TcDictBinds, -- bindings for all simplified dictionaries
+ Bool) -- whether any flexibles where instantiated
+tcReduceEqs locals wanteds
+ = do { let (local_eqs , local_dicts) = partition isEqInst locals
+ (wanteds_eqs, wanteds_dicts) = partition isEqInst wanteds
+ ; eqCfg1 <- normaliseEqs (local_eqs ++ wanteds_eqs)
+ ; eqCfg2 <- normaliseDicts False local_dicts
+ ; eqCfg3 <- normaliseDicts True wanteds_dicts
+ ; eqCfg <- propagateEqs (eqCfg1 `unionEqConfig` eqCfg2
+ `unionEqConfig` eqCfg3)
+ ; finaliseEqsAndDicts eqCfg
+ }
\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.
+intermediates during flattening of equalities as well as
\begin{code}
-- |Configuration of normalised equalities used during solving.
--
-data EqConfig = EqConfig { eqs :: [RewriteInst]
- , skolems :: TyVarSet
+data EqConfig = EqConfig { eqs :: [RewriteInst] -- all equalities
+ , locals :: [Inst] -- given dicts
+ , wanteds :: [Inst] -- wanted dicts
+ , binds :: TcDictBinds -- bindings
+ , skolems :: TyVarSet -- flattening skolems
}
addSkolems :: EqConfig -> TyVarSet -> EqConfig
addEq :: EqConfig -> RewriteInst -> EqConfig
addEq eqCfg eq = eqCfg {eqs = eq : eqs eqCfg}
+
+unionEqConfig :: EqConfig -> EqConfig -> EqConfig
+unionEqConfig eqc1 eqc2 = EqConfig
+ { eqs = eqs eqc1 ++ eqs eqc2
+ , locals = locals eqc1 ++ locals eqc2
+ , wanteds = wanteds eqc1 ++ wanteds eqc2
+ , binds = binds eqc1 `unionBags` binds eqc2
+ , skolems = skolems eqc1 `unionVarSet` skolems eqc2
+ }
+
+emptyEqConfig :: EqConfig
+emptyEqConfig = EqConfig
+ { eqs = []
+ , locals = []
+ , wanteds = []
+ , binds = emptyBag
+ , skolems = emptyVarSet
+ }
+
+instance Outputable EqConfig where
+ ppr (EqConfig {eqs = eqs, locals = locals, wanteds = wanteds, binds = binds})
+ = vcat [ppr eqs, ppr locals, ppr wanteds, ppr binds]
\end{code}
The set of operations on an equality configuration. We obtain the initialise
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.
--
--
normaliseEqs :: [Inst] -> TcM EqConfig
normaliseEqs eqs
- = do { (eqss, skolemss) <- mapAndUnzipM normEqInst eqs
- ; return $ EqConfig { eqs = concat eqss
- , skolems = unionVarSets skolemss
- }
+ = do { ASSERTM2( allM wantedEqInstIsUnsolved eqs, ppr eqs )
+ ; traceTc $ ptext (sLit "Entering normaliseEqs")
+
+ ; (eqss, skolemss) <- mapAndUnzipM normEqInst eqs
+ ; return $ emptyEqConfig { eqs = concat eqss
+ , skolems = unionVarSets skolemss
+ }
+ }
+
+-- |Flatten the type arguments of all dictionaries, returning the result as a
+-- equality configuration. The dictionaries go into the 'wanted' component if
+-- the second argument is 'True'.
+--
+-- Precondition: The Insts are zonked.
+--
+normaliseDicts :: Bool -> [Inst] -> TcM EqConfig
+normaliseDicts isWanted insts
+ = do { traceTc $ hang (ptext (sLit "Entering normaliseDicts") <+>
+ ptext (if isWanted then sLit "[Wanted] for"
+ else sLit "[Local] for"))
+ 4 (ppr insts)
+ ; (insts', eqss, bindss, skolemss) <- mapAndUnzip4M (normDict isWanted)
+ insts
+
+ ; traceTc $ hang (ptext (sLit "normaliseDicts returns"))
+ 4 (ppr insts' $$ ppr eqss)
+ ; return $ emptyEqConfig { eqs = concat eqss
+ , locals = if isWanted then [] else insts'
+ , wanteds = if isWanted then insts' else []
+ , binds = unionManyBags bindss
+ , 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 = []})
+ = do { traceTc $ hang (ptext (sLit "Entering propagateEqs:"))
+ 4 (ppr eqCfg)
--- |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
+ ; propagate todoEqs (eqCfg {eqs = []})
}
--- |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.
+-- |Finalise a set of equalities and associated dictionaries after
+-- propagation. The returned 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 first returned
+-- set of instances are the locals (without equalities) and the second set are
+-- all residual wanteds, including equalities.
--
-normaliseDicts :: EqConfig -> [Inst] -> TcM (Maybe (EqConfig, [Inst]))
-normaliseDicts = error "TcTyFuns.normaliseDicts"
+finaliseEqsAndDicts :: EqConfig
+ -> TcM ([Inst], [Inst], TcDictBinds, Bool)
+finaliseEqsAndDicts (EqConfig { eqs = eqs
+ , locals = locals
+ , wanteds = wanteds
+ , binds = binds
+ , skolems = skolems
+ })
+ = do { traceTc $ ptext (sLit "finaliseEqsAndDicts")
+ ; (eqs', subst_binds, locals', wanteds') <- substitute eqs locals wanteds
+ ; (eqs'', improved) <- instantiateAndExtract eqs' (null locals) skolems
+ ; let final_binds = subst_binds `unionBags` binds
+
+ -- Assert that all cotvs of wanted equalities are still unfilled, and
+ -- zonk all final insts, to make any improvement visible
+ ; ASSERTM2( allM wantedEqInstIsUnsolved eqs'', ppr eqs'' )
+ ; zonked_locals <- zonkInsts locals'
+ ; zonked_wanteds <- zonkInsts (eqs'' ++ wanteds')
+ ; return (zonked_locals, zonked_wanteds, final_binds, improved)
+ }
\end{code}
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)
+ { 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)
+ , rwi_swapped :: Bool -- swapped orientation of original 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)
+ { 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)
+ , rwi_swapped :: Bool -- swapped orientation of original EqInst
}
isWantedRewriteInst :: RewriteInst -> Bool
isWantedRewriteInst = isWantedCo . rwi_co
-rewriteInstToInst :: RewriteInst -> Inst
+rewriteInstToInst :: RewriteInst -> TcM 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
- }
+ = deriveEqInst eq (mkTyVarTy tv) (rwi_right eq) (rwi_co 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
- }
+ = deriveEqInst eq (mkTyConApp fam args) (rwi_right eq) (rwi_co eq)
+
+-- Derive an EqInst based from a RewriteInst, possibly swapping the types
+-- around.
+--
+deriveEqInst :: RewriteInst -> TcType -> TcType -> EqInstCo -> TcM Inst
+deriveEqInst rewrite ty1 ty2 co
+ = do { co_adjusted <- if not swapped then return co
+ else mkSymEqInstCo co (ty2, ty1)
+ ; return $ EqInst
+ { tci_left = left
+ , tci_right = right
+ , tci_co = co_adjusted
+ , tci_loc = rwi_loc rewrite
+ , tci_name = rwi_name rewrite
+ }
+ }
+ where
+ swapped = rwi_swapped rewrite
+ (left, right) = if not swapped then (ty1, ty2) else (ty2, ty1)
+
+instance Outputable RewriteInst where
+ ppr (RewriteFam {rwi_fam = fam, rwi_args = args, rwi_right = rhs, rwi_co =co})
+ = hsep [ pprEqInstCo co <+> text "::"
+ , ppr (mkTyConApp fam args)
+ , text "~>"
+ , ppr rhs
+ ]
+ ppr (RewriteVar {rwi_var = tv, rwi_right = rhs, rwi_co =co})
+ = hsep [ pprEqInstCo co <+> text "::"
+ , ppr tv
+ , text "~>"
+ , ppr rhs
+ ]
+
+pprEqInstCo :: EqInstCo -> SDoc
+pprEqInstCo (Left cotv) = ptext (sLit "Wanted") <+> ppr cotv
+pprEqInstCo (Right co) = ptext (sLit "Local") <+> ppr co
\end{code}
The following functions turn an arbitrary equality into a set of normal
-equalities.
+equalities. This implements the WFlat and LFlat rules of the paper in one
+sweep. However, we use flexible variables for both locals and wanteds, and
+avoid to carry around the unflattening substitution \Sigma (for locals) by
+already updating the skolems for locals with the family application that they
+represent - i.e., they will turn into that family application on the next
+zonking (which only happens after finalisation).
+
+In a corresponding manner, normDict normalises class dictionaries by
+extracting any synonym family applications and generation appropriate normal
+equalities.
+
+Whenever we encounter a loopy equality (of the form a ~ T .. (F ...a...) ...),
+we drop that equality and raise an error if it is a wanted or a warning if it
+is a local.
\begin{code}
normEqInst :: Inst -> TcM ([RewriteInst], TyVarSet)
+-- Normalise one equality.
normEqInst inst
= ASSERT( isEqInst inst )
- go ty1 ty2 (eqInstCoercion inst)
+ do { traceTc $ ptext (sLit "normEqInst of ") <+>
+ pprEqInstCo co <+> text "::" <+>
+ ppr ty1 <+> text "~" <+> ppr ty2
+ ; res <- go ty1 ty2 co
+ ; traceTc $ ptext (sLit "normEqInst returns") <+> ppr res
+ ; return res
+ }
where
(ty1, ty2) = eqInstTys inst
+ co = eqInstCoercion 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
+ go ty1@(TyConApp con args) ty2 co
+ | isOpenSynTyConApp ty1 -- only if not oversaturated
+ = mkRewriteFam False con args ty2 co
-- right-to-left rule with type family head
go ty1 ty2@(TyConApp con args) co
- | isOpenSynTyCon con
+ | isOpenSynTyConApp ty2 -- only if not oversaturated
= do { co' <- mkSymEqInstCo co (ty2, ty1)
- ; mkRewriteFam con args ty1 co'
+ ; mkRewriteFam True con args ty1 co'
}
-- no outermost family
= 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
+ sym_co2 = mkSymCoercion co2
eqTys = (ty1', ty2')
- ; (co', ty12_eqs') <- adjustCoercions co rewriteCo eqTys ty12_eqs
+ ; (co', ty12_eqs') <- adjustCoercions co co1 sym_co2 eqTys ty12_eqs
; eqs <- checkOrientation ty1' ty2' co' inst
- ; return $ (eqs ++ ty12_eqs',
- ty1_skolems `unionVarSet` ty2_skolems)
+ ; if isLoopyEquality eqs ty12_eqs'
+ then do { if isWantedCo (tci_co inst)
+ then
+ addErrCtxt (ptext (sLit "Rejecting loopy equality")) $
+ eqInstMisMatch inst
+ else
+ warnDroppingLoopyEquality ty1 ty2
+ ; return ([], emptyVarSet) -- drop the equality
+ }
+ else
+ return (eqs ++ ty12_eqs',
+ ty1_skolems `unionVarSet` ty2_skolems)
}
- mkRewriteFam con args ty2 co
+ mkRewriteFam swapped 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
+ ; let co1 = mkTyConApp con cargs
+ sym_co2 = mkSymCoercion co2
all_eqs = concat args_eqss ++ ty2_eqs
eqTys = (mkTyConApp con args', ty2')
- ; (co', all_eqs') <- adjustCoercions co rewriteCo eqTys all_eqs
+ ; (co', all_eqs') <- adjustCoercions co co1 sym_co2 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
+ { rwi_fam = con
+ , rwi_args = args'
+ , rwi_right = ty2'
+ , rwi_co = co'
+ , rwi_loc = tci_loc inst
+ , rwi_name = tci_name inst
+ , rwi_swapped = swapped
}
; return $ (thisRewriteFam : all_eqs',
unionVarSets (ty2_skolems:args_skolemss))
}
+ -- If the original equality has the form a ~ T .. (F ...a...) ..., we will
+ -- have a variable equality with 'a' on the lhs as the first equality.
+ -- Then, check whether 'a' occurs in the lhs of any family equality
+ -- generated by flattening.
+ isLoopyEquality (RewriteVar {rwi_var = tv}:_) eqs
+ = any inRewriteFam eqs
+ where
+ inRewriteFam (RewriteFam {rwi_args = args})
+ = tv `elemVarSet` tyVarsOfTypes args
+ inRewriteFam _ = False
+ isLoopyEquality _ _ = False
+
+normDict :: Bool -> Inst -> TcM (Inst, [RewriteInst], TcDictBinds, TyVarSet)
+-- Normalise one dictionary or IP constraint.
+normDict isWanted inst@(Dict {tci_pred = ClassP clas args})
+ = do { (args', cargs, args_eqss, args_skolemss)
+ <- mapAndUnzip4M (flattenType inst) args
+ ; let rewriteCo = PredTy $ ClassP clas cargs
+ eqs = concat args_eqss
+ pred' = ClassP clas args'
+ ; if null eqs
+ then -- don't generate a binding if there is nothing to flatten
+ return (inst, [], emptyBag, emptyVarSet)
+ else do {
+ ; (inst', bind) <- mkDictBind inst isWanted rewriteCo pred'
+ ; eqs' <- if isWanted then return eqs else mapM wantedToLocal eqs
+ ; return (inst', eqs', bind, unionVarSets args_skolemss)
+ }}
+normDict _isWanted inst
+ = return (inst, [], emptyBag, emptyVarSet)
+-- !!!TODO: Still need to normalise IP constraints.
+
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)
-- two tvs, left greater => unchanged
go ty1@(TyVarTy tv1) ty2@(TyVarTy tv2)
| tv1 > tv2
- = mkRewriteVar tv1 ty2 co
+ = mkRewriteVar False tv1 ty2 co
-- two tvs, right greater => swap
| otherwise
= do { co' <- mkSymEqInstCo co (ty2, ty1)
- ; mkRewriteVar tv2 ty1 co'
+ ; mkRewriteVar True tv2 ty1 co'
}
-- only lhs is a tv => unchanged
| ty1 `tcPartOfType` ty2 -- occurs check!
= occurCheckErr ty1 ty2
| otherwise
- = mkRewriteVar tv1 ty2 co
+ = mkRewriteVar False tv1 ty2 co
-- only rhs is a tv => swap
go ty1 ty2@(TyVarTy tv2)
= occurCheckErr ty2 ty1
| otherwise
= do { co' <- mkSymEqInstCo co (ty2, ty1)
- ; mkRewriteVar tv2 ty1 co'
+ ; mkRewriteVar True tv2 ty1 co'
}
-- type applications => decompose
= 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
- }]
+ mkRewriteVar swapped tv ty co = return [RewriteVar
+ { rwi_var = tv
+ , rwi_right = ty
+ , rwi_co = co
+ , rwi_loc = tci_loc inst
+ , rwi_name = tci_name inst
+ , rwi_swapped = swapped
+ }]
flattenType :: Inst -- context to get location & name
-> Type -- the type to flatten
= go ty
where
-- look through synonyms
- go ty | Just ty' <- tcView ty = go ty'
+ go ty | Just ty' <- tcView ty
+ = do { (ty_flat, co, eqs, skolems) <- go ty'
+ ; if null eqs
+ then -- unchanged, keep the old type with folded synonyms
+ return (ty, ty, [], emptyVarSet)
+ else
+ return (ty_flat, co, eqs, skolems)
+ }
- -- type family application => flatten to "id :: F t1'..tn' ~ alpha"
+ -- type variable => nothing to do
+ go ty@(TyVarTy _)
+ = return (ty, ty, [] , emptyVarSet)
+
+ -- type family application & family arity matches number of args
+ -- => flatten to "gamma :: F t1'..tn' ~ alpha" (alpha & gamma fresh)
go ty@(TyConApp con args)
- | isOpenSynTyCon con
+ | isOpenSynTyConApp ty -- only if not oversaturated
= 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
+ { rwi_fam = con
+ , rwi_args = args'
+ , rwi_right = alphaTy
+ , rwi_co = mkWantedCo cotv
+ , rwi_loc = tci_loc inst
+ , rwi_name = tci_name inst
+ , rwi_swapped = True
}
; return (alphaTy,
mkTyConApp con cargs `mkTransCoercion` mkTyVarTy cotv,
-- data constructor application => flatten subtypes
-- NB: Special cased for efficiency - could be handled as type application
- go (TyConApp con args)
+ go ty@(TyConApp con args)
+ | not (isOpenSynTyCon con) -- don't match oversaturated family apps
= do { (args', cargs, args_eqss, args_skolemss) <- mapAndUnzip4M go args
- ; return (mkTyConApp con args',
- mkTyConApp con cargs,
- concat args_eqss,
- unionVarSets args_skolemss)
+ ; if null args_eqss
+ then -- unchanged, keep the old type with folded synonyms
+ return (ty, ty, [], emptyVarSet)
+ else
+ 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)
+ go ty@(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)
+ ; if null eqs_l && null eqs_r
+ then -- unchanged, keep the old type with folded synonyms
+ return (ty, ty, [], emptyVarSet)
+ else
+ 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
+ go ty
+ | Just (ty_l, ty_r) <- repSplitAppTy_maybe ty
+ -- need to use the smart split as ty may be an
+ -- oversaturated family application
= 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)
+ ; if null eqs_l && null eqs_r
+ then -- unchanged, keep the old type with folded synonyms
+ return (ty, ty, [], emptyVarSet)
+ else
+ 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)
+ -- forall type => panic if the body contains a type family
+ -- !!!TODO: As long as the family does not contain a quantified variable
+ -- we might pull it out, but what if it does contain a quantified
+ -- variable???
+ go ty@(ForAllTy _ body)
+ | null (tyFamInsts body)
+ = return (ty, ty, [] , emptyVarSet)
+ | otherwise
+ = panic "TcTyFuns.flattenType: synonym family in a rank-n type"
+
+ -- we should never see a predicate type
+ go (PredTy _)
+ = panic "TcTyFuns.flattenType: unexpected PredType"
+
+ go _ = panic "TcTyFuns: suppress bogus warning"
adjustCoercions :: EqInstCo -- coercion of original equality
- -> Coercion -- coercion witnessing the rewrite
- -> (Type, Type) -- type sof flattened equality
+ -> Coercion -- coercion witnessing the left rewrite
+ -> Coercion -- coercion witnessing the right rewrite
+ -> (Type, Type) -- types of 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)
+-- coercion and that of the new equalities produced during flattening are
+-- adjusted .
+adjustCoercions (Left cotv) co1 co2 (ty_l, ty_r) all_eqs
+ -- wanted => generate a fresh coercion variable for the flattened equality
+ = do { cotv' <- newMetaCoVar ty_l ty_r
+ ; writeMetaTyVar cotv $
+ (co1 `mkTransCoercion` TyVarTy cotv' `mkTransCoercion` co2)
+ ; return (Left cotv', all_eqs)
+ }
+
+adjustCoercions co@(Right _) _co1 _co2 _eqTys all_eqs
+ -- local => turn all new equalities into locals and update (but not zonk)
+ -- the skolem
+ = do { all_eqs' <- mapM wantedToLocal all_eqs
+ ; return (co, all_eqs')
+ }
+
+mkDictBind :: Inst -- original instance
+ -> Bool -- is this a wanted contraint?
+ -> Coercion -- coercion witnessing the rewrite
+ -> PredType -- coerced predicate
+ -> TcM (Inst, -- new inst
+ TcDictBinds) -- binding for coerced dictionary
+mkDictBind dict isWanted rewriteCo pred
+ = do { dict' <- newDictBndr loc pred
+ -- relate the old inst to the new one
+ -- target_dict = source_dict `cast` st_co
+ ; let (target_dict, source_dict, st_co)
+ | isWanted = (dict, dict', mkSymCoercion rewriteCo)
+ | otherwise = (dict', dict, rewriteCo)
+ -- we have
+ -- co :: dict ~ dict'
+ -- hence, if isWanted
+ -- dict = dict' `cast` sym co
+ -- else
+ -- dict' = dict `cast` co
+ expr = HsVar $ instToId source_dict
+ cast_expr = HsWrap (WpCast st_co) expr
+ rhs = L (instLocSpan loc) cast_expr
+ binds = instToDictBind target_dict rhs
+ ; return (dict', binds)
}
- | otherwise
- = return (co, map wantedToLocal all_eqs)
where
- wantedToLocal eq = eq {rwi_co = mkGivenCo (rwi_right eq)}
+ loc = tci_loc dict
+
+-- gamma ::^l Fam args ~ alpha
+-- => gamma ::^w Fam args ~ alpha, with alpha := Fam args & gamma := Fam args
+-- (the update of alpha will not be apparent during propagation, as we
+-- never follow the indirections of meta variables; it will be revealed
+-- when the equality is zonked)
+--
+-- NB: It's crucial to update *both* alpha and gamma, as gamma may already
+-- have escaped into some other coercions during normalisation.
+--
+wantedToLocal :: RewriteInst -> TcM RewriteInst
+wantedToLocal eq@(RewriteFam {rwi_fam = fam,
+ rwi_args = args,
+ rwi_right = TyVarTy alpha,
+ rwi_co = Left gamma})
+ = do { writeMetaTyVar alpha (mkTyConApp fam args)
+ ; writeMetaTyVar gamma (mkTyConApp fam args)
+ ; return $ eq {rwi_co = mkGivenCo $ mkTyVarTy gamma}
+ }
+wantedToLocal _ = panic "TcTyFuns.wantedToLocal"
\end{code}
}
where
substRules eq1 eq2
- = do { -- try the SubstFam rule
- optEqs <- applySubstFam eq1 eq2
+ = do {traceTc $ hang (ptext (sLit "Trying subst rules with"))
+ 4 (ppr eq1 $$ ppr eq2)
+
+ -- try the SubstFam rule
+ ; optEqs <- applySubstFam eq1 eq2
; case optEqs of
Just (eqs, skolems) -> return (eqs, [], skolems)
Nothing -> do
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
- }
+ ; eq' <- deriveEqInst eq lhs rhs co'
; liftM Just $ normEqInst eq'
}
}
-> TcM (Maybe ([RewriteInst], TyVarSet))
applySubstFam eq1@(RewriteFam {rwi_fam = fam1, rwi_args = args1})
eq2@(RewriteFam {rwi_fam = fam2, rwi_args = args2})
+
+ -- rule matches => rewrite
| 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
- }
+ ; eq2' <- deriveEqInst eq2 lhs rhs co2'
; liftM Just $ normEqInst eq2'
}
+
+ -- rule would match with eq1 and eq2 swapped => put eq2 into todo list
+ | fam1 == fam2 && tcEqTypes args1 args2 &&
+ (isWantedRewriteInst eq1 || not (isWantedRewriteInst eq2))
+ = return $ Just ([eq2], emptyVarSet)
+
where
lhs = rwi_right eq1
rhs = rwi_right eq2
co1 = eqInstCoType (rwi_co eq1)
co2 = rwi_co eq2
+
applySubstFam _ _ = return Nothing
\end{code}
-> TcM (Maybe ([RewriteInst], TyVarSet))
applySubstVarVar eq1@(RewriteVar {rwi_var = tv1})
eq2@(RewriteVar {rwi_var = tv2})
+
+ -- rule matches => rewrite
| 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
- }
+ ; eq2' <- deriveEqInst eq2 lhs rhs co2'
; liftM Just $ normEqInst eq2'
}
+
+ -- rule would match with eq1 and eq2 swapped => put eq2 into todo list
+ | tv1 == tv2 &&
+ (isWantedRewriteInst eq1 || not (isWantedRewriteInst eq2))
+ = return $ Just ([eq2], emptyVarSet)
+
where
lhs = rwi_right eq1
rhs = rwi_right eq2
co1 = eqInstCoType (rwi_co eq1)
co2 = rwi_co eq2
+
applySubstVarVar _ _ = return Nothing
\end{code}
\begin{code}
applySubstVarFam :: RewriteInst -> RewriteInst -> TcM (Maybe RewriteInst)
+
+ -- rule matches => rewrite
applySubstVarFam eq1@(RewriteVar {rwi_var = tv1})
eq2@(RewriteFam {rwi_fam = fam2, rwi_args = args2})
| tv1 `elemVarSet` tyVarsOfTypes args2
rhs2 = rwi_right eq2
co1 = eqInstCoType (rwi_co eq1)
co2 = rwi_co eq2
+
+ -- rule would match with eq1 and eq2 swapped => put eq2 into todo list
+applySubstVarFam (RewriteFam {rwi_args = args1})
+ eq2@(RewriteVar {rwi_var = tv2})
+ | tv2 `elemVarSet` tyVarsOfTypes args1
+ = return $ Just eq2
+
applySubstVarFam _ _ = return Nothing
\end{code}
%************************************************************************
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
+(both local and wanted) into the left-hand sides of 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.
+We also apply the same substitutions to the local and wanted class and IP
+dictionaries.
+
+The treatment of flexibles in wanteds is quite subtle. We absolutely want to
+substitute them into right-hand sides of equalities, to avoid getting two
+competing instantiations for a type variables; e.g., consider
+
+ F s ~ alpha, alpha ~ t
+
+If we don't substitute `alpha ~ t', we may instantiate t with `F s' instead.
+This would be bad as `F s' is less useful, eg, as an argument to a class
+constraint.
+
+However, there is no reason why we would want to *substitute* `alpha ~ t' into a
+class constraint. We rather wait until `alpha' is instantiated to `t` and
+save the extra dictionary binding that substitution would introduce.
+Moreover, we may substitute wanted equalities only into wanted dictionaries.
+
+NB:
+* Given that we apply the substitution corresponding to a single equality
+ exhaustively, before turning to the next, and because we eliminate recursive
+ equalities, 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 []
+substitute :: [RewriteInst] -- equalities
+ -> [Inst] -- local class dictionaries
+ -> [Inst] -- wanted class dictionaries
+ -> TcM ([RewriteInst], -- equalities after substitution
+ TcDictBinds, -- all newly generated dictionary bindings
+ [Inst], -- local dictionaries after substitution
+ [Inst]) -- wanted dictionaries after substitution
+substitute eqs locals wanteds = subst eqs [] emptyBag locals wanteds
where
- subst [] res = return res
- subst (eq:eqs) res
- = do { eqs' <- mapM (substOne eq) eqs
- ; res' <- mapM (substOne eq) res
- ; subst eqs' (eq:res')
+ subst [] res binds locals wanteds
+ = return (res, binds, locals, wanteds)
+
+ subst (eq@(RewriteVar {rwi_var = tv, rwi_right = ty, rwi_co = co}):eqs)
+ res binds locals wanteds
+ = do { traceTc $ ptext (sLit "TcTyFuns.substitute:") <+> ppr eq
+
+ ; let coSubst = zipOpenTvSubst [tv] [eqInstCoType co]
+ tySubst = zipOpenTvSubst [tv] [ty]
+ ; eqs' <- mapM (substEq eq coSubst tySubst) eqs
+ ; res' <- mapM (substEq eq coSubst tySubst) res
+
+ -- only susbtitute local equalities into local dictionaries
+ ; (lbinds, locals') <- if not (isWantedCo co)
+ then
+ mapAndUnzipM
+ (substDict eq coSubst tySubst False)
+ locals
+ else
+ return ([], locals)
+
+ -- flexible tvs in wanteds will be instantiated anyway, there is
+ -- no need to substitute them into dictionaries
+ ; (wbinds, wanteds') <- if not (isMetaTyVar tv && isWantedCo co)
+ then
+ mapAndUnzipM
+ (substDict eq coSubst tySubst True)
+ wanteds
+ else
+ return ([], wanteds)
+
+ ; let binds' = unionManyBags $ binds : lbinds ++ wbinds
+ ; subst eqs' (eq:res') binds' locals' wanteds'
}
-
- -- 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)
+ subst (eq:eqs) res binds locals wanteds
+ = subst eqs (eq:res) binds locals wanteds
+
+ -- We have, co :: tv ~ ty
+ -- => apply [ty/tv] to right-hand side of eq2
+ -- (but only if tv actually occurs in the right-hand side of eq2)
+ substEq (RewriteVar {rwi_var = tv, rwi_right = ty})
+ coSubst tySubst eq2
+ | tv `elemVarSet` tyVarsOfType (rwi_right eq2)
+ = do { let co1Subst = mkSymCoercion $ substTy coSubst (rwi_right eq2)
+ right2' = substTy tySubst (rwi_right eq2)
left2 = case eq2 of
RewriteVar {rwi_var = tv2} -> mkTyVarTy tv2
RewriteFam {rwi_fam = fam,
_ -> return $ eq2 {rwi_right = right2', rwi_co = co2'}
}
- -- changed
- substOne _ eq2
+ -- unchanged
+ substEq _ _ _ eq2
= return eq2
+
+ -- We have, co :: tv ~ ty
+ -- => apply [ty/tv] to dictionary predicate
+ -- (but only if tv actually occurs in the predicate)
+ substDict (RewriteVar {rwi_var = tv}) coSubst tySubst isWanted dict
+ | isClassDict dict
+ , tv `elemVarSet` tyVarsOfPred (tci_pred dict)
+ = do { let co1Subst = PredTy (substPred coSubst (tci_pred dict))
+ pred' = substPred tySubst (tci_pred dict)
+ ; (dict', binds) <- mkDictBind dict isWanted co1Subst pred'
+ ; return (binds, dict')
+ }
+
+ -- unchanged
+ substDict _ _ _ _ dict
+ = return (emptyBag, dict)
+-- !!!TODO: Still need to substitute into IP constraints.
\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.
+if at least one instantiation of a flexible that is *not* a skolem from
+flattening was performed.
+
+We need to instantiate all flexibles that arose as skolems during flattening
+of wanteds before we instantiate any other flexibles. Consider F delta ~
+alpha, F alpha ~ delta, where alpha is a skolem and delta a free flexible. We
+need to produce F (F delta) ~ delta (and not F (F alpha) ~ alpha). Otherwise,
+we may wrongly claim to having performed an improvement, which can lead to
+non-termination of the combined class-family solver.
\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)
+instantiateAndExtract :: [RewriteInst] -> Bool -> TyVarSet -> TcM ([Inst], Bool)
+instantiateAndExtract eqs localsEmpty skolems
+ = do { traceTc $ hang (ptext (sLit "instantiateAndExtract:"))
+ 4 (ppr eqs $$ ppr skolems)
+ -- start by *only* instantiating skolem flexibles from flattening
+ ; unflat_wanteds <- liftM catMaybes $
+ mapM (inst (`elemVarSet` skolems)) wanteds
+ -- only afterwards instantiate free flexibles
+ ; residuals <- liftM catMaybes $ mapM (inst (const True)) unflat_wanteds
+ ; let improvement = length residuals < length unflat_wanteds
+ ; residuals' <- mapM rewriteInstToInst residuals
+ ; return (residuals', improvement)
}
where
- inst eq@(RewriteVar {rwi_var = tv1, rwi_right = ty2, rwi_co = co})
-
- -- co :: alpha ~ t
- | isMetaTyVar tv1
- = doInst tv1 ty2 co eq
+ wanteds = filter (isWantedCo . rwi_co) eqs
+ checkingMode = length eqs > length wanteds || not localsEmpty
+ -- no local equalities or dicts => checking mode
+
+ -- co :: alpha ~ t or co :: a ~ alpha
+ inst mayInst eq@(RewriteVar {rwi_var = tv1, rwi_right = ty2, rwi_co = co})
+ = do { flexi_tv1 <- isFlexible mayInst tv1
+ ; maybe_flexi_tv2 <- isFlexibleTy mayInst ty2
+ ; case (flexi_tv1, maybe_flexi_tv2) of
+ (True, _)
+ -> -- co :: alpha ~ t
+ doInst (rwi_swapped eq) tv1 ty2 co eq
+ (False, Just tv2)
+ -> -- co :: a ~ alpha
+ doInst (not $ rwi_swapped eq) tv2 (mkTyVarTy tv1) co eq
+ _ -> return $ Just eq
+ }
- -- co :: a ~ alpha
+ -- co :: F args ~ alpha, and we are in checking mode (ie, no locals)
+ inst mayInst eq@(RewriteFam {rwi_fam = fam, rwi_args = args,
+ rwi_right = ty2, rwi_co = co})
| 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
- }
+ , mayInst tv2 && (checkingMode || tv2 `elemVarSet` skolems)
+ -- !!!FIXME: this is too liberal, even if tv2 is in
+ -- skolems we shouldn't instantiate if tvs occurs
+ -- in other equalities that may propagate it into the
+ -- environment
+ = doInst (not $ rwi_swapped eq) tv2 (mkTyConApp fam args) co eq
+
+ inst _mayInst eq = return $ Just eq
+
+ -- tv is a meta var and not filled
+ isFlexible mayInst tv
+ | isMetaTyVar tv && mayInst tv = liftM isFlexi $ readMetaTyVar tv
+ | otherwise = return False
+
+ -- type is a tv that is a meta var and not filled
+ isFlexibleTy mayInst ty
+ | Just tv <- tcGetTyVar_maybe ty = do {flexi <- isFlexible mayInst tv
+ ; if flexi then return $ Just tv
+ else return Nothing
+ }
+ | otherwise = return Nothing
+
+ doInst _swapped _tv _ty (Right ty) _eq
+ = pprPanic "TcTyFuns.doInst: local eq: " (ppr ty)
+ doInst swapped tv ty (Left cotv) eq
+ = do { lookupTV <- lookupTcTyVar tv
+ ; uMeta swapped 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"
+ -- => keep the equality
+ uMeta _swapped tv (IndirectTv fill_ty) ty _cotv
+ = do { traceTc $
+ ptext (sLit "flexible") <+> ppr tv <+>
+ ptext (sLit "already filled with") <+> ppr fill_ty <+>
+ ptext (sLit "meant to fill with") <+> ppr ty
+ ; return $ Just eq
+ }
-- type variable meets type variable
-- => check that tv2 hasn't been updated yet and choose which to update
; case mb_ty' of
Nothing ->
- -- normalisation shouldn't leave families in non_tv_ty
- panic "TcTyFuns.uMeta: unexpected synonym family"
+ -- there may be a family in non_tv_ty due to an unzonked,
+ -- but updated skolem for a local equality
+ return $ Just eq
Just ty' ->
do { checkUpdateMeta swapped tv ref ty' -- update meta var
; writeMetaTyVar cotv ty' -- update co var
(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
+ (_, _) | 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
\end{code}
+%************************************************************************
+%* *
+\section{Errors}
+%* *
+%************************************************************************
-==================== 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 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.
+The infamous couldn't match expected type soandso against inferred type
+somethingdifferent message.
\begin{code}
-data Rewrite = Rewrite TcType -- lhs of rewrite rule
- TcType -- rhs of rewrite rule
- TcType -- coercion witnessing the rewrite rule
-
-eqInstToRewrite :: Inst -> Maybe (Rewrite, Bool)
- -- True iff rewrite swapped equality
-eqInstToRewrite inst
+eqInstMisMatch :: Inst -> TcM a
+eqInstMisMatch inst
= ASSERT( isEqInst inst )
- go ty1 ty2 (eqInstType inst)
+ setErrCtxt ctxt $ failWithMisMatch ty_act ty_exp
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
+ (ty_act, ty_exp) = eqInstTys inst
+ InstLoc _ _ ctxt = instLoc inst
- -- left-to-right rule with type family head
- go ty1@(TyConApp con _) ty2 co
- | isOpenSynTyCon con
- = Just (Rewrite ty1 ty2 co, False) -- not swapped
-
- -- left-to-right rule with type variable head
- go ty1@(TyVarTy tv) ty2 co
- | isSkolemTyVar tv
- = Just (Rewrite ty1 ty2 co, False) -- not swapped
-
- -- 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), True) -- swapped
-
- -- 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), True) -- swapped
-
- -- this equality is not a rewrite rule => ignore
- go _ _ _ = Nothing
-\end{code}
+-----------------------
+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
+failWithMisMatch ty_act ty_exp
+ = do { env0 <- tcInitTidyEnv
+ ; ty_exp <- zonkTcType ty_exp
+ ; ty_act <- zonkTcType ty_act
+ ; failWithTcM (misMatchMsg env0 (ty_act, ty_exp))
+ }
-Normalise a type relative to an elementary rewrite implied by an EqInst or an
-explicitly given elementary rewrite.
+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)
-\begin{code}
--- Rewrite by EqInst
--- Precondition: the EqInst passes the occurs check
-tcEqInstNormaliseFamInst :: Inst -> TcType -> TcM (CoercionI, TcType)
-tcEqInstNormaliseFamInst inst ty
- = case eqInstToRewrite inst of
- Just (rewrite, _) -> tcEqRuleNormaliseFamInst rewrite ty
- Nothing -> return (IdCo, ty)
-
--- Rewrite by equality rewrite rule
-tcEqRuleNormaliseFamInst :: Rewrite -- elementary rewrite
- -> TcType -- type to rewrite
- -> TcM (CoercionI, -- witnessing coercion
- TcType) -- rewritten type
-tcEqRuleNormaliseFamInst (Rewrite pat rhs co) ty
- = tcGenericNormaliseFamInst matchEqRule ty
where
- matchEqRule sty | pat `tcEqType` sty = return $ Just (rhs, co)
- | otherwise = return $ Nothing
-\end{code}
+ 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)
-Generic normalisation of 'Type's and 'PredType's; ie, walk the type term and
-apply the normalisation function gives as the first argument to every TyConApp
-and every TyVarTy subterm.
+ -- (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
- tcGenericNormaliseFamInst fun ty = (co, ty')
- then co : ty ~ ty'
+ ppr_extra env _ty = (env, empty) -- Normal case
+\end{code}
-This function is (by way of using smart constructors) careful to ensure that
-the returned coercion is exactly IdCo (and not some semantically equivalent,
-but syntactically different coercion) whenever (ty' `tcEqType` ty). This
-makes it easy for the caller to determine whether the type changed. BUT
-even if we return IdCo, ty' may be *syntactically* different from ty due to
-unfolded closed type synonyms (by way of tcCoreView). In the interest of
-good error messages, callers should discard ty' in favour of ty in this case.
+Warn of loopy local equalities that were dropped.
\begin{code}
-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)
+warnDroppingLoopyEquality :: TcType -> TcType -> TcM ()
+warnDroppingLoopyEquality ty1 ty2
+ = do { env0 <- tcInitTidyEnv
+ ; ty1 <- zonkTcType ty1
+ ; ty2 <- zonkTcType ty2
+ ; let (env1 , tidy_ty1) = tidyOpenType env0 ty1
+ (_env2, tidy_ty2) = tidyOpenType env1 ty2
+ ; addWarnTc $ hang (ptext (sLit "Dropping loopy given equality"))
+ 2 (quotes (ppr tidy_ty1 <+> text "~" <+> ppr tidy_ty2))
}
- 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)
- }
- where
- unifyMeta inst
- = ASSERT( isEqInst 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
-
- | TyVarTy tv1 <- ty1
- , isMetaTyVar tv1 = do { lookupTV <- lookupTcTyVar tv1
- ; uMeta False tv1 lookupTV ty2 cotv
- }
- | TyVarTy tv2 <- ty2
- , isMetaTyVar tv2 = do { lookupTV <- lookupTcTyVar tv2
- ; uMeta True tv2 lookupTV ty1 cotv
- }
- | otherwise = return ([inst], False)
-
- -- meta variable has been filled already
- -- => ignore this inst (we'll come around again, after zonking)
- uMeta _swapped _tv (IndirectTv _) _ty _cotv
- = 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
- }
-
- ------ 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)) 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' ->
- do { checkUpdateMeta swapped tv ref ty' -- update meta var
- ; writeMetaTyVar cotv ty' -- update co var
- ; return ([], True)
- }
- }
-
- uMeta _ _ _ _ _ = panic "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 ([], True)
- }
-
- -- 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 ([], True)
- }
- 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}
-
-
-%************************************************************************
-%* *
-\section{Normalisation of Insts}
-%* *
-%************************************************************************
-
-Normalises a set of dictionaries relative to a set of given equalities (which
-are interpreted as rewrite rules). We only consider given equalities of the
-form
-
- F ts ~ t or a ~ t
-
-where F is a type family.
-
-\begin{code}
-substEqInDictInsts :: Bool -- whether the *dictionaries* are wanted/given
- -> [Inst] -- given equalities (used as rewrite rules)
- -> [Inst] -- dictinaries to be normalised
- -> TcM ([Inst], TcDictBinds)
-substEqInDictInsts isWanted eqInsts dictInsts
- = do { traceTc (text "substEqInDictInst <-" <+> ppr dictInsts)
- ; dictInsts' <-
- foldlM rewriteWithOneEquality (dictInsts, emptyBag) eqInsts
- ; traceTc (text "substEqInDictInst ->" <+> ppr dictInsts')
- ; return dictInsts'
- }
- where
- -- (1) Given equality of form 'F ts ~ t' or 'a ~ t': use for rewriting
- rewriteWithOneEquality (dictInsts, dictBinds)
- eqInst@(EqInst {tci_left = pattern,
- tci_right = target})
- | isOpenSynTyConApp pattern || isTyVarTy pattern
- = do { (dictInsts', moreDictBinds) <-
- genericNormaliseInsts isWanted applyThisEq dictInsts
- ; return (dictInsts', dictBinds `unionBags` moreDictBinds)
- }
- where
- applyThisEq = tcGenericNormaliseFamInstPred (return . matchResult)
-
- -- rewrite in case of an exact match
- matchResult ty | tcEqType pattern ty = Just (target, eqInstType eqInst)
- | otherwise = Nothing
-
- -- (2) Given equality has the wrong form: ignore
- rewriteWithOneEquality (dictInsts, dictBinds) _not_a_rewrite_rule
- = return (dictInsts, dictBinds)
-\end{code}
-
-
-Take a bunch of Insts (not EqInsts), and normalise them wrt the top-level
-type-function equations, where
-
- (norm_insts, binds) = normaliseInsts is_wanted insts
-
-If 'is_wanted'
- = True, (binds + norm_insts) defines insts (wanteds)
- = False, (binds + insts) defines norm_insts (givens)
-
-Ie, in the case of normalising wanted dictionaries, we use the normalised
-dictionaries to define the originally wanted ones. However, in the case of
-given dictionaries, we use the originally given ones to define the normalised
-ones.
-
-\begin{code}
-normaliseInsts :: Bool -- True <=> wanted insts
- -> [Inst] -- wanted or given insts
- -> TcM ([Inst], TcDictBinds) -- normalised insts and bindings
-normaliseInsts isWanted insts
- = genericNormaliseInsts isWanted tcNormaliseFamInstPred insts
-
-genericNormaliseInsts :: Bool -- True <=> wanted insts
- -> (TcPredType -> TcM (CoercionI, TcPredType))
- -- how to normalise
- -> [Inst] -- wanted or given insts
- -> TcM ([Inst], TcDictBinds) -- normalised insts & binds
-genericNormaliseInsts isWanted fun insts
- = do { (insts', binds) <- mapAndUnzipM (normaliseOneInst isWanted fun) insts
- ; return (insts', unionManyBags binds)
- }
- where
- normaliseOneInst isWanted fun
- dict@(Dict {tci_pred = pred,
- tci_loc = loc})
- = do { traceTc $ text "genericNormaliseInst <-" <+> ppr dict
- ; (coi, pred') <- fun pred
-
- ; case coi of
- IdCo ->
- do { traceTc $ text "genericNormaliseInst ->" <+> ppr dict
- ; return (dict, emptyBag)
- }
- -- don't use pred' in this case; otherwise, we get
- -- more unfolded closed type synonyms in error messages
- ACo co ->
- do { -- an inst for the new pred
- ; dict' <- newDictBndr loc pred'
- -- relate the old inst to the new one
- -- target_dict = source_dict `cast` st_co
- ; let (target_dict, source_dict, st_co)
- | isWanted = (dict, dict', mkSymCoercion co)
- | otherwise = (dict', dict, co)
- -- we have
- -- co :: dict ~ dict'
- -- hence, if isWanted
- -- dict = dict' `cast` sym co
- -- else
- -- dict' = dict `cast` co
- expr = HsVar $ instToId source_dict
- cast_expr = HsWrap (WpCast st_co) expr
- rhs = L (instLocSpan loc) cast_expr
- binds = instToDictBind target_dict rhs
- -- return the new inst
- ; 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}
-
-
-%************************************************************************
-%* *
-\section{Errors}
-%* *
-%************************************************************************
-
-The infamous couldn't match expected type soandso against inferred type
-somethingdifferent message.
-
-\begin{code}
-eqInstMisMatch :: Inst -> TcM a
-eqInstMisMatch inst
- = ASSERT( isEqInst inst )
- setErrCtxt ctxt $ failWithMisMatch ty_act ty_exp
- where
- (ty_act, ty_exp) = eqInstTys inst
- InstLoc _ _ ctxt = instLoc inst
-
------------------------
-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
-failWithMisMatch ty_act ty_exp
- = do { env0 <- tcInitTidyEnv
- ; ty_exp <- zonkTcType ty_exp
- ; ty_act <- zonkTcType ty_act
- ; 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
- 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 = (env, empty) -- Normal case
\end{code}