X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=compiler%2Ftypecheck%2FTcTyFuns.lhs;h=113ea43bd5e68c2a16e439814c9934718e9c4917;hb=5045af3106f3d1e3cb223c254af2de6a8a265797;hp=981845a4f05aa3272f8e9a10a73da632856e280c;hpb=e891720545a2f088cc48ad62bad7c5b2ad7d183f;p=ghc-hetmet.git diff --git a/compiler/typecheck/TcTyFuns.lhs b/compiler/typecheck/TcTyFuns.lhs index 981845a..113ea43 100644 --- a/compiler/typecheck/TcTyFuns.lhs +++ b/compiler/typecheck/TcTyFuns.lhs @@ -268,6 +268,10 @@ emptyEqConfig = EqConfig , 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 @@ -282,7 +286,10 @@ no further propoagation is possible. -- normaliseEqs :: [Inst] -> TcM EqConfig normaliseEqs eqs - = do { (eqss, skolemss) <- mapAndUnzipM normEqInst eqs + = do { ASSERTM2( allM isValidWantedEqInst eqs, ppr eqs ) + ; traceTc $ ptext (sLit "Entering normaliseEqs") + + ; (eqss, skolemss) <- mapAndUnzipM normEqInst eqs ; return $ emptyEqConfig { eqs = concat eqss , skolems = unionVarSets skolemss } @@ -296,7 +303,9 @@ normaliseEqs eqs -- normaliseDicts :: Bool -> [Inst] -> TcM EqConfig normaliseDicts isWanted insts - = do { (insts', eqss, bindss, skolemss) <- mapAndUnzip4M (normDict isWanted) + = do { traceTc $ ptext (sLit "Entering normaliseDicts") <+> + ptext (if isWanted then sLit "[Wanted]" else sLit "[Local]") + ; (insts', eqss, bindss, skolemss) <- mapAndUnzip4M (normDict isWanted) insts ; return $ emptyEqConfig { eqs = concat eqss , locals = if isWanted then [] else insts' @@ -310,7 +319,11 @@ normaliseDicts isWanted insts -- propagateEqs :: EqConfig -> TcM EqConfig propagateEqs eqCfg@(EqConfig {eqs = todoEqs}) - = propagate todoEqs (eqCfg {eqs = []}) + = do { traceTc $ hang (ptext (sLit "Entering propagateEqs:")) + 4 (ppr eqCfg) + + ; propagate todoEqs (eqCfg {eqs = []}) + } -- |Finalise a set of equalities and associated dictionaries after -- propagation. The returned Boolean value is `True' iff any flexible @@ -325,13 +338,19 @@ finaliseEqsAndDicts (EqConfig { eqs = eqs , locals = locals , wanteds = wanteds , binds = binds + , skolems = skolems }) - = do { (eqs', subst_binds, locals', wanteds') <- substitute eqs locals wanteds - ; (eqs'', improved) <- instantiateAndExtract eqs' - ; return (locals', - eqs'' ++ wanteds', - subst_binds `unionBags` binds, - improved) + = 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 isValidWantedEqInst eqs'', ppr eqs'' ) + ; zonked_locals <- zonkInsts locals' + ; zonked_wanteds <- zonkInsts (eqs'' ++ wanteds') + ; return (zonked_locals, zonked_wanteds, final_binds, improved) } \end{code} @@ -366,41 +385,68 @@ 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 @@ -415,6 +461,10 @@ 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. @@ -431,13 +481,13 @@ normEqInst inst -- left-to-right rule with type family head go (TyConApp con args) ty2 co | isOpenSynTyCon con - = mkRewriteFam con args ty2 co + = mkRewriteFam False 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' + ; mkRewriteFam True con args ty1 co' } -- no outermost family @@ -445,35 +495,58 @@ normEqInst inst = 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}) @@ -482,10 +555,15 @@ normDict isWanted inst@(Dict {tci_pred = ClassP clas args}) ; let rewriteCo = PredTy $ ClassP clas cargs eqs = concat args_eqss pred' = ClassP clas args' - ; (inst', bind, eqs') <- mkDictBind inst isWanted rewriteCo pred' eqs + ; 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 + }} +normDict _isWanted inst = return (inst, [], emptyBag, emptyVarSet) -- !!!TODO: Still need to normalise IP constraints. @@ -495,7 +573,13 @@ checkOrientation :: Type -> Type -> EqInstCo -> Inst -> TcM [RewriteInst] -- 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 + = do { traceTc $ ptext (sLit "checkOrientation of ") <+> + pprEqInstCo co <+> text "::" <+> + ppr ty1 <+> text "~" <+> ppr ty2 + ; eqs <- go ty1 ty2 + ; traceTc $ ptext (sLit "checkOrientation returns") <+> ppr eqs + ; return eqs + } where -- look through synonyms go ty1 ty2 | Just ty1' <- tcView ty1 = go ty1' ty2 @@ -511,12 +595,12 @@ checkOrientation ty1 ty2 co inst -- 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 @@ -524,7 +608,7 @@ checkOrientation ty1 ty2 co inst | 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) @@ -532,7 +616,7 @@ checkOrientation ty1 ty2 co inst = occurCheckErr ty2 ty1 | otherwise = do { co' <- mkSymEqInstCo co (ty2, ty1) - ; mkRewriteVar tv2 ty1 co' + ; mkRewriteVar True tv2 ty1 co' } -- type applications => decompose @@ -552,13 +636,14 @@ checkOrientation ty1 ty2 co inst = 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 @@ -571,7 +656,18 @@ flattenType inst ty = 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 variable => nothing to do + go ty@(TyVarTy _) + = return (ty, ty, [] , emptyVarSet) -- type family application -- => flatten to "gamma :: F t1'..tn' ~ alpha" (alpha & gamma fresh) @@ -582,12 +678,13 @@ flattenType inst 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, @@ -597,43 +694,64 @@ flattenType inst ty -- 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) = 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@(AppTy 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 (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" adjustCoercions :: EqInstCo -- coercion of original equality - -> Coercion -- coercion witnessing the rewrite + -> 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 @@ -641,17 +759,17 @@ adjustCoercions :: EqInstCo -- coercion of original equality -- Depending on whether we flattened a local or wanted equality, that equality's -- coercion and that of the new equalities produced during flattening are -- adjusted . -adjustCoercions co rewriteCo eqTys all_eqs - +adjustCoercions (Left cotv) co1 co2 (ty_l, ty_r) all_eqs -- wanted => generate a fresh coercion variable for the flattened equality - | isWantedCo co - = do { co' <- mkRightTransEqInstCo co rewriteCo eqTys - ; return (co', all_eqs) + = 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 - | otherwise = do { all_eqs' <- mapM wantedToLocal all_eqs ; return (co, all_eqs') } @@ -660,13 +778,9 @@ mkDictBind :: Inst -- original instance -> Bool -- is this a wanted contraint? -> Coercion -- coercion witnessing the rewrite -> PredType -- coerced predicate - -> [RewriteInst] -- equalities from flattening -> TcM (Inst, -- new inst - TcDictBinds, -- binding for coerced dictionary - [RewriteInst]) -- final equalities from flattening -mkDictBind dict _isWanted _rewriteCo _pred [] - = return (dict, emptyBag, []) -- don't generate binding for an id coercion -mkDictBind dict isWanted rewriteCo pred eqs + 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 @@ -683,8 +797,7 @@ mkDictBind dict isWanted rewriteCo pred eqs cast_expr = HsWrap (WpCast st_co) expr rhs = L (instLocSpan loc) cast_expr binds = instToDictBind target_dict rhs - ; eqs' <- if isWanted then return eqs else mapM wantedToLocal eqs - ; return (dict', binds, eqs') + ; return (dict', binds) } where loc = tci_loc dict @@ -793,13 +906,7 @@ applyTop eq@(RewriteFam {rwi_fam = fam, rwi_args = args}) 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' } } @@ -834,13 +941,7 @@ applySubstFam eq1@(RewriteFam {rwi_fam = fam1, rwi_args = args1}) -- !!!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' } where @@ -872,13 +973,7 @@ applySubstVarVar eq1@(RewriteVar {rwi_var = tv1}) | 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' } where @@ -936,10 +1031,26 @@ implied by one variable equality exhaustively before turning to the next and We also apply the same substitutions to the local and wanted class and IP 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. +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] -- equalities @@ -953,18 +1064,35 @@ substitute eqs locals wanteds = subst eqs [] emptyBag locals wanteds where 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 { let coSubst = zipOpenTvSubst [tv] [eqInstCoType co] + = 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 - ; (lbinds, locals') <- mapAndUnzipM - (substDict eq coSubst tySubst False) - locals - ; (wbinds, wanteds') <- mapAndUnzipM - (substDict eq coSubst tySubst True) - wanteds + ; 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' } @@ -974,7 +1102,7 @@ substitute eqs locals wanteds = subst eqs [] emptyBag 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, rwi_co = co}) + 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) @@ -997,14 +1125,12 @@ substitute eqs locals wanteds = subst eqs [] emptyBag locals wanteds -- 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, rwi_right = ty, rwi_co = co}) - coSubst tySubst isWanted dict + substDict (RewriteVar {rwi_var = tv}) coSubst tySubst isWanted dict | isClassDict dict , tv `elemVarSet` tyVarsOfPred (tci_pred dict) - = do { let co1Subst = mkSymCoercion $ - PredTy (substPred coSubst (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' [] + ; (dict', binds) <- mkDictBind dict isWanted co1Subst pred' ; return (binds, dict') } @@ -1017,41 +1143,64 @@ substitute eqs locals wanteds = subst eqs [] emptyBag locals wanteds 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. \begin{code} -instantiateAndExtract :: [RewriteInst] -> TcM ([Inst], Bool) -instantiateAndExtract eqs - = 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 { results <- mapM inst wanteds + ; let residuals = [eq | Left eq <- results] + only_skolems = and [tv `elemVarSet` skolems | Right tv <- results] + ; residuals' <- mapM rewriteInstToInst residuals + ; return (residuals', not only_skolems) } where + wanteds = filter (isWantedCo . rwi_co) eqs + checkingMode = length eqs > length wanteds || not localsEmpty + -- no local equalities or dicts => checking mode + inst eq@(RewriteVar {rwi_var = tv1, rwi_right = ty2, rwi_co = co}) -- co :: alpha ~ t | isMetaTyVar tv1 - = doInst tv1 ty2 co eq + = doInst (rwi_swapped eq) tv1 ty2 co eq -- co :: a ~ alpha | Just tv2 <- tcGetTyVar_maybe ty2 , isMetaTyVar tv2 - = doInst tv2 (mkTyVarTy tv1) co eq + = doInst (not $ rwi_swapped eq) 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 - } + -- co :: F args ~ alpha, and we are in checking mode (ie, no locals) + inst eq@(RewriteFam {rwi_fam = fam, rwi_args = args, rwi_right = ty2, + rwi_co = co}) + | Just tv2 <- tcGetTyVar_maybe ty2 + , isMetaTyVar tv2 + , checkingMode || tv2 `elemVarSet` skolems + -- !!!TODO: 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 eq = return $ Left eq + + 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 - -- => ignore (must be a skolem that was introduced by flattening locals) - uMeta _swapped _tv (IndirectTv _) _ty _cotv - = return Nothing + -- => 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 $ Left eq + } -- type variable meets type variable -- => check that tv2 hasn't been updated yet and choose which to update @@ -1073,7 +1222,7 @@ instantiateAndExtract eqs -- signature skolem meets non-variable type -- => cannot update (retain the equality)! uMeta _swapped _tv (DoneTv (MetaTv (SigTv _) _)) _non_tv_ty _cotv - = return $ Just eq + = return $ Left eq -- updatable meta variable meets non-variable type -- => occurs check, monotype check, and kinds match check, then update @@ -1088,7 +1237,7 @@ instantiateAndExtract eqs Just ty' -> do { checkUpdateMeta swapped tv ref ty' -- update meta var ; writeMetaTyVar cotv ty' -- update co var - ; return Nothing + ; return $ Right tv } } @@ -1100,35 +1249,38 @@ instantiateAndExtract eqs uMetaVar swapped tv1 (MetaTv _ ref) tv2 (SkolemTv _) cotv = do { checkUpdateMeta swapped tv1 ref (mkTyVarTy tv2) ; writeMetaTyVar cotv (mkTyVarTy tv2) - ; return Nothing + ; return $ Right tv1 } -- 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 + = do { tv <- 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 >> return tv1 -- 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 + ; return $ Right tv } where -- Kinds should be guaranteed ok at this point update_tv1 = updateMeta tv1 ref1 (mkTyVarTy tv2) + >> return tv1 update_tv2 = updateMeta tv2 ref2 (mkTyVarTy tv1) + >> return tv2 kind_err = addErrCtxtM (unifyKindCtxt swapped tv1 (mkTyVarTy tv2)) $ unifyKindMisMatch k1 k2 @@ -1206,3 +1358,18 @@ misMatchMsg env0 (ty_act, ty_exp) ppr_extra env _ty = (env, empty) -- Normal case \end{code} + +Warn of loopy local equalities that were dropped. + +\begin{code} +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)) + } +\end{code}