X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=ghc%2Fcompiler%2Ftypecheck%2FTcTyClsDecls.lhs;h=3535313054744bef84b3c2031502b66a46e38ac0;hb=e1e1d0204ff754def1b3675f539372fd4691d78d;hp=225b4de4226f696063aa90ca541a2a5fb713a421;hpb=5bb39849e8e9041a28cec2e83a2dc4779b9d8d2d;p=ghc-hetmet.git diff --git a/ghc/compiler/typecheck/TcTyClsDecls.lhs b/ghc/compiler/typecheck/TcTyClsDecls.lhs index 225b4de..3535313 100644 --- a/ghc/compiler/typecheck/TcTyClsDecls.lhs +++ b/ghc/compiler/typecheck/TcTyClsDecls.lhs @@ -1,60 +1,64 @@ % -% (c) The AQUA Project, Glasgow University, 1996 +% (c) The AQUA Project, Glasgow University, 1996-1998 % \section[TcTyClsDecls]{Typecheck type and class declarations} \begin{code} -#include "HsVersions.h" - module TcTyClsDecls ( - tcTyAndClassDecls1 + tcTyAndClassDecls ) where -IMP_Ubiq(){-uitous-} +#include "HsVersions.h" -import HsSyn ( HsDecl(..), TyDecl(..), ConDecl(..), ConDetails(..), BangType(..), - ClassDecl(..), HsType(..), HsTyVar, DefaultDecl, InstDecl, - IfaceSig, Sig(..), MonoBinds, Fake, InPat, HsBinds(..), HsExpr, NewOrData, - hsDeclName +import HsSyn ( HsDecl(..), TyClDecl(..), + HsType(..), HsTyVar, + ConDecl(..), ConDetails(..), BangType(..), + Sig(..), + tyClDeclName, isClassDecl, isSynDecl ) -import RnHsSyn ( RenamedTyDecl(..), RenamedClassDecl(..), SYN_IE(RenamedHsDecl) - ) -import TcHsSyn ( SYN_IE(TcHsBinds), TcIdOcc(..) ) +import RnHsSyn ( RenamedHsDecl, RenamedTyClDecl, listTyCon_name, tupleTyCon_name ) +import BasicTypes ( RecFlag(..), NewOrData(..), Arity ) import TcMonad -import Inst ( SYN_IE(InstanceMapper) ) -import TcClassDcl ( tcClassDecl1 ) -import TcEnv ( tcExtendTyConEnv, tcExtendClassEnv ) -import SpecEnv ( SpecEnv ) -import TcKind ( TcKind, newKindVars ) -import TcTyDecls ( tcTyDecl, mkDataBinds ) -import TcMonoType ( tcTyVarScope ) +import Inst ( InstanceMapper ) +import TcClassDcl ( kcClassDecl, tcClassDecl1 ) +import TcEnv ( ValueEnv, TcTyThing(..), + tcExtendTypeEnv, getAllEnvTyCons + ) +import TcTyDecls ( tcTyDecl, kcTyDecl ) +import TcMonoType ( kcHsTyVar ) +import TcType ( TcKind, newKindVar, newKindVars, kindToTcKind, zonkTcKindToKind ) + +import Type ( mkArrowKind, boxedTypeKind, mkDictTy ) +import Class ( Class ) +import Var ( TyVar, tyVarKind ) +import FiniteMap import Bag -import Class ( SYN_IE(Class) ) +import VarSet import Digraph ( stronglyConnComp, SCC(..) ) -import Name ( Name, getSrcLoc, isTvOcc, nameOccName ) +import Name ( Name, NamedThing(..), getSrcLoc, isTvOcc, nameOccName ) import Outputable -import Pretty -import Maybes ( mapMaybe ) -import UniqSet ( SYN_IE(UniqSet), emptyUniqSet, +import Maybes ( mapMaybe, expectJust ) +import UniqSet ( UniqSet, emptyUniqSet, unitUniqSet, unionUniqSets, unionManyUniqSets, uniqSetToList ) +import ErrUtils ( Message ) import SrcLoc ( SrcLoc ) -import TyCon ( TyCon, SYN_IE(Arity) ) +import TyCon ( TyCon, ArgVrcs ) +import Variance ( calcTyConArgVrcs ) import Unique ( Unique, Uniquable(..) ) -import Util ( panic{-, pprTrace-} ) - +import UniqFM ( listToUFM, lookupUFM ) \end{code} The main function ~~~~~~~~~~~~~~~~~ \begin{code} -tcTyAndClassDecls1 :: TcEnv s -> InstanceMapper -- Knot tying stuff - -> [RenamedHsDecl] - -> TcM s (TcEnv s) +tcTyAndClassDecls :: ValueEnv -> InstanceMapper -- Knot tying stuff + -> [RenamedHsDecl] + -> TcM s TcEnv -tcTyAndClassDecls1 unf_env inst_mapper decls +tcTyAndClassDecls unf_env inst_mapper decls = sortByDependency decls `thenTc` \ groups -> tcGroups unf_env inst_mapper groups @@ -63,249 +67,313 @@ tcGroups unf_env inst_mapper [] returnTc env tcGroups unf_env inst_mapper (group:groups) - = tcGroup unf_env inst_mapper group `thenTc` \ new_env -> - - -- Extend the environment using the new tycons and classes - tcSetEnv new_env $ - - -- Do the remaining groups + = tcGroup unf_env inst_mapper group `thenTc` \ env -> + tcSetEnv env $ tcGroups unf_env inst_mapper groups \end{code} Dealing with a group ~~~~~~~~~~~~~~~~~~~~ -\begin{code} -tcGroup :: TcEnv s -> InstanceMapper -> Bag RenamedHsDecl -> TcM s (TcEnv s) -tcGroup unf_env inst_mapper decls - = -- TIE THE KNOT - fixTc ( \ ~(tycons,classes,_) -> - - -- EXTEND TYPE AND CLASS ENVIRONMENTS - -- NB: it's important that the tycons and classes come back in just - -- the same order from this fix as from get_binders, so that these - -- extend-env things work properly. A bit UGH-ish. - tcExtendTyConEnv tycon_names_w_arities tycons $ - tcExtendClassEnv class_names classes $ - - -- DEAL WITH TYPE VARIABLES - tcTyVarScope tyvar_names ( \ tyvars -> - - -- DEAL WITH THE DEFINITIONS THEMSELVES - foldBag combine (tcDecl unf_env inst_mapper) - (returnTc (emptyBag, emptyBag)) - decls - ) `thenTc` \ (tycon_bag,class_bag) -> - let - tycons = bagToList tycon_bag - classes = bagToList class_bag - in - - -- SNAFFLE ENV TO RETURN - tcGetEnv `thenNF_Tc` \ final_env -> - - returnTc (tycons, classes, final_env) - ) `thenTc` \ (_, _, final_env) -> - - returnTc final_env +The knot-tying parameters: @rec_tyclss@ is an alist mapping @Name@s to +@TcTyThing@s. @rec_vrcs@ is a finite map from @Name@s to @ArgVrcs@s. + +\begin{code} +tcGroup :: ValueEnv -> InstanceMapper -> SCC RenamedTyClDecl -> TcM s TcEnv +tcGroup unf_env inst_mapper scc + = -- Do kind checking + mapNF_Tc getTyBinding1 decls `thenNF_Tc` \ ty_env_stuff1 -> + tcExtendTypeEnv ty_env_stuff1 (mapTc kcDecl decls) `thenTc_` + + -- Tie the knot +-- traceTc (ppr (map fst ty_env_stuff1)) `thenTc_` + fixTc ( \ ~(rec_tyclss, rec_vrcs, _) -> + let + rec_env = listToUFM rec_tyclss + in + + -- Do type checking + mapNF_Tc (getTyBinding2 rec_env) ty_env_stuff1 `thenNF_Tc` \ ty_env_stuff2 -> + tcExtendTypeEnv ty_env_stuff2 $ + mapTc (tcDecl is_rec_group unf_env inst_mapper rec_vrcs) decls + `thenTc` \ tyclss -> + + tcGetEnv `thenTc` \ env -> + let + tycons = getAllEnvTyCons env + vrcs = calcTyConArgVrcs tycons + in + + returnTc (tyclss, vrcs, env) + ) `thenTc` \ (_, _, env) -> +-- traceTc (text "done" <+> ppr (map fst ty_env_stuff1)) `thenTc_` + returnTc env where - (tyvar_names, tycon_names_w_arities, class_names) = get_binders decls + is_rec_group = case scc of + AcyclicSCC _ -> NonRecursive + CyclicSCC _ -> Recursive - combine do_a do_b - = do_a `thenTc` \ (a1,a2) -> - do_b `thenTc` \ (b1,b2) -> - returnTc (a1 `unionBags` b1, a2 `unionBags` b2) + decls = case scc of + AcyclicSCC decl -> [decl] + CyclicSCC decls -> decls \end{code} Dealing with one decl ~~~~~~~~~~~~~~~~~~~~~ \begin{code} -tcDecl :: TcEnv s -> InstanceMapper - -> RenamedHsDecl - -> TcM s (Bag TyCon, Bag Class) +kcDecl decl + = tcAddDeclCtxt decl $ + if isClassDecl decl then + kcClassDecl decl + else + kcTyDecl decl + +tcDecl :: RecFlag -- True => recursive group + -> ValueEnv -> InstanceMapper -> FiniteMap Name ArgVrcs + -> RenamedTyClDecl -> TcM s (Name, TcTyThing) + +tcDecl is_rec_group unf_env inst_mapper vrcs_env decl + = tcAddDeclCtxt decl $ +-- traceTc (text "Starting" <+> ppr name) `thenTc_` + if isClassDecl decl then + tcClassDecl1 unf_env inst_mapper vrcs_env decl `thenTc` \ clas -> +-- traceTc (text "Finished" <+> ppr name) `thenTc_` + returnTc (getName clas, AClass clas) + else + tcTyDecl is_rec_group vrcs_env decl `thenTc` \ tycon -> +-- traceTc (text "Finished" <+> ppr name) `thenTc_` + returnTc (getName tycon, ATyCon tycon) + + where + name = tyClDeclName decl + + +tcAddDeclCtxt decl thing_inside + = tcAddSrcLoc loc $ + tcAddErrCtxt ctxt $ + thing_inside + where + (name, loc, thing) + = case decl of + (ClassDecl _ name _ _ _ _ _ _ _ _ loc) -> (name, loc, "class") + (TySynonym name _ _ loc) -> (name, loc, "type synonym") + (TyData NewType _ name _ _ _ _ loc) -> (name, loc, "data type") + (TyData DataType _ name _ _ _ _ loc) -> (name, loc, "newtype") + + ctxt = hsep [ptext SLIT("In the"), text thing, + ptext SLIT("declaration for"), quotes (ppr name)] +\end{code} + + +getTyBinders +~~~~~~~~~~~ +Extract *binding* names from type and class decls. Type variables are +bound in type, data, newtype and class declarations, + *and* the polytypes in the class op sigs. + *and* the existentially quantified contexts in datacon decls + +Why do we need to grab all these type variables at once, including +those locally-quantified type variables in class op signatures? + + [Incidentally, this only works because the names are all unique by now.] + +Because we can only commit to the final kind of a type variable when +we've completed the mutually recursive group. For example: -tcDecl unf_env inst_mapper (TyD decl) - = tcTyDecl decl `thenTc` \ tycon -> - returnTc (unitBag tycon, emptyBag) +class C a where + op :: D b => a -> b -> b + +class D c where + bop :: (Monad c) => ... -tcDecl unf_env inst_mapper (ClD decl) - = tcClassDecl1 unf_env inst_mapper decl `thenTc` \ clas -> - returnTc (emptyBag, unitBag clas) +Here, the kind of the locally-polymorphic type variable "b" +depends on *all the uses of class D*. For example, the use of +Monad c in bop's type signature means that D must have kind Type->Type. + + +\begin{code} +getTyBinding1 :: RenamedTyClDecl -> NF_TcM s (Name, (TcKind, Maybe Arity, TcTyThing)) +getTyBinding1 (TySynonym name tyvars _ _) + = mapNF_Tc kcHsTyVar tyvars `thenNF_Tc` \ arg_kinds -> + newKindVar `thenNF_Tc` \ result_kind -> + returnNF_Tc (name, (foldr mkArrowKind result_kind arg_kinds, + Just (length tyvars), + ATyCon (pprPanic "ATyCon: syn" (ppr name)))) + +getTyBinding1 (TyData _ _ name tyvars _ _ _ _) + = mapNF_Tc kcHsTyVar tyvars `thenNF_Tc` \ arg_kinds -> + returnNF_Tc (name, (foldr mkArrowKind boxedTypeKind arg_kinds, + Nothing, + ATyCon (error "ATyCon: data"))) + +getTyBinding1 (ClassDecl _ name tyvars _ _ _ _ _ _ _ _) + = mapNF_Tc kcHsTyVar tyvars `thenNF_Tc` \ arg_kinds -> + returnNF_Tc (name, (foldr mkArrowKind boxedTypeKind arg_kinds, + Just (length tyvars), + AClass (error "AClass"))) + +-- Zonk the kind to its final form, and lookup the +-- recursive tycon/class +getTyBinding2 rec_env (name, (tc_kind, maybe_arity, thing)) + = zonkTcKindToKind tc_kind `thenNF_Tc` \ kind -> + returnNF_Tc (name, (kind, maybe_arity, mk_thing thing (lookupUFM rec_env name))) + where + mk_thing (ATyCon _) ~(Just (ATyCon tc)) = ATyCon tc + mk_thing (AClass _) ~(Just (AClass cls)) = AClass cls \end{code} + +%************************************************************************ +%* * +\subsection{Dependency analysis} +%* * +%************************************************************************ + Dependency analysis ~~~~~~~~~~~~~~~~~~~ \begin{code} -sortByDependency :: [RenamedHsDecl] -> TcM s [Bag RenamedHsDecl] +sortByDependency :: [RenamedHsDecl] -> TcM s [SCC RenamedTyClDecl] sortByDependency decls - = let -- CHECK FOR SYNONYM CYCLES + = let -- CHECK FOR CLASS CYCLES + cls_sccs = stronglyConnComp (mapMaybe mk_cls_edges tycl_decls) + cls_cycles = [ decls | CyclicSCC decls <- cls_sccs] + in + checkTc (null cls_cycles) (classCycleErr cls_cycles) `thenTc_` + + let -- CHECK FOR SYNONYM CYCLES syn_sccs = stronglyConnComp (filter is_syn_decl edges) syn_cycles = [ decls | CyclicSCC decls <- syn_sccs] in checkTc (null syn_cycles) (typeCycleErr syn_cycles) `thenTc_` - let -- CHECK FOR CLASS CYCLES - cls_sccs = stronglyConnComp (filter is_cls_decl edges) - cls_cycles = [ decls | CyclicSCC decls <- cls_sccs] - - in - checkTc (null cls_cycles) (classCycleErr cls_cycles) `thenTc_` - - -- DO THE MAIN DEPENDENCY ANALYSIS + -- DO THE MAIN DEPENDENCY ANALYSIS let - decl_sccs = stronglyConnComp (filter is_ty_cls_decl edges) - scc_bags = map bag_acyclic decl_sccs + decl_sccs = stronglyConnComp edges in - returnTc (scc_bags) - + returnTc decl_sccs where - edges = mapMaybe mk_edges decls + tycl_decls = [d | TyClD d <- decls] + edges = map mk_edges tycl_decls -bag_acyclic (AcyclicSCC scc) = unitBag scc -bag_acyclic (CyclicSCC sccs) = listToBag sccs - -is_syn_decl (TyD (TySynonym _ _ _ _), _, _) = True -is_syn_decl _ = False - -is_ty_cls_decl (TyD _, _, _) = True -is_ty_cls_decl (ClD _, _, _) = True -is_ty_cls_decl other = False - -is_cls_decl (ClD _, _, _) = True -is_cls_decl other = False + is_syn_decl (d, _, _) = isSynDecl d + is_cls_decl (d, _, _) = isClassDecl d \end{code} Edges in Type/Class decls ~~~~~~~~~~~~~~~~~~~~~~~~~ + \begin{code} -mk_edges decl@(TyD (TyData _ ctxt name _ condecls derivs _ _)) - = Just (decl, uniqueOf name, uniqSetToList (get_ctxt ctxt `unionUniqSets` +---------------------------------------------------- +-- mk_cls_edges looks only at the context of class decls +-- Its used when we are figuring out if there's a cycle in the +-- superclass hierarchy + +mk_cls_edges :: RenamedTyClDecl -> Maybe (RenamedTyClDecl, Unique, [Unique]) + +mk_cls_edges decl@(ClassDecl ctxt name _ _ _ _ _ _ _ _ _) + = Just (decl, getUnique name, map (getUnique . fst) ctxt) +mk_cls_edges other_decl + = Nothing + +---------------------------------------------------- +mk_edges :: RenamedTyClDecl -> (RenamedTyClDecl, Unique, [Unique]) + +mk_edges decl@(TyData _ ctxt name _ condecls derivs _ _) + = (decl, getUnique name, uniqSetToList (get_ctxt ctxt `unionUniqSets` get_cons condecls `unionUniqSets` get_deriv derivs)) -mk_edges decl@(TyD (TySynonym name _ rhs _)) - = Just (decl, uniqueOf name, uniqSetToList (get_ty rhs)) +mk_edges decl@(TySynonym name _ rhs _) + = (decl, getUnique name, uniqSetToList (get_ty rhs)) -mk_edges decl@(ClD (ClassDecl ctxt name _ sigs _ _ _)) - = Just (decl, uniqueOf name, uniqSetToList (get_ctxt ctxt `unionUniqSets` +mk_edges decl@(ClassDecl ctxt name _ _ sigs _ _ _ _ _ _) + = (decl, getUnique name, uniqSetToList (get_ctxt ctxt `unionUniqSets` get_sigs sigs)) -mk_edges other_decl = Nothing +---------------------------------------------------- get_ctxt ctxt = unionManyUniqSets (map (set_name.fst) ctxt) +---------------------------------------------------- get_deriv Nothing = emptyUniqSet get_deriv (Just clss) = unionManyUniqSets (map set_name clss) +---------------------------------------------------- get_cons cons = unionManyUniqSets (map get_con cons) -get_con (ConDecl _ ctxt details _) +---------------------------------------------------- +get_con (ConDecl _ _ ctxt details _) = get_ctxt ctxt `unionUniqSets` get_con_details details +---------------------------------------------------- get_con_details (VanillaCon btys) = unionManyUniqSets (map get_bty btys) get_con_details (InfixCon bty1 bty2) = unionUniqSets (get_bty bty1) (get_bty bty2) -get_con_details (NewCon ty) = get_ty ty +get_con_details (NewCon ty _) = get_ty ty get_con_details (RecCon nbtys) = unionManyUniqSets (map (get_bty.snd) nbtys) +---------------------------------------------------- get_bty (Banged ty) = get_ty ty get_bty (Unbanged ty) = get_ty ty +get_bty (Unpacked ty) = get_ty ty +---------------------------------------------------- get_ty (MonoTyVar name) = if isTvOcc (nameOccName name) then emptyUniqSet else set_name name get_ty (MonoTyApp ty1 ty2) = unionUniqSets (get_ty ty1) (get_ty ty2) get_ty (MonoFunTy ty1 ty2) = unionUniqSets (get_ty ty1) (get_ty ty2) -get_ty (MonoListTy tc ty) - = set_name tc `unionUniqSets` get_ty ty -get_ty (MonoTupleTy tc tys) - = set_name tc `unionUniqSets` get_tys tys +get_ty (MonoListTy ty) + = set_name listTyCon_name `unionUniqSets` get_ty ty +get_ty (MonoTupleTy tys boxed) + = set_name (tupleTyCon_name boxed (length tys)) `unionUniqSets` get_tys tys +get_ty (MonoUsgTy _ ty) + = get_ty ty +get_ty (MonoUsgForAllTy _ ty) + = get_ty ty get_ty (HsForAllTy _ ctxt mty) = get_ctxt ctxt `unionUniqSets` get_ty mty -get_ty other = panic "TcTyClsDecls:get_ty" +get_ty (MonoDictTy name _) + = set_name name +---------------------------------------------------- get_tys tys = unionManyUniqSets (map get_ty tys) +---------------------------------------------------- get_sigs sigs = unionManyUniqSets (map get_sig sigs) where - get_sig (ClassOpSig _ _ ty _) = get_ty ty + get_sig (ClassOpSig _ _ _ ty _) = get_ty ty + get_sig (FixSig _) = emptyUniqSet get_sig other = panic "TcTyClsDecls:get_sig" -set_name name = unitUniqSet (uniqueOf name) - +---------------------------------------------------- +set_name name = unitUniqSet (getUnique name) set_to_bag set = listToBag (uniqSetToList set) \end{code} -get_binders -~~~~~~~~~~~ -Extract *binding* names from type and class decls. Type variables are -bound in type, data, newtype and class declarations and the polytypes -in the class op sigs. - -Why do we need to grab all these type variables at once, including -those locally-quantified type variables in class op signatures? -Because we can only commit to the final kind of a type variable when -we've completed the mutually recursive group. For example: - -class C a where - op :: D b => a -> b -> b - -class D c where - bop :: (Monad c) => ... - -Here, the kind of the locally-polymorphic type variable "b" -depends on *all the uses of class D*. For example, the use of -Monad c in bop's type signature means that D must have kind Type->Type. - - \begin{code} -get_binders :: Bag RenamedHsDecl - -> ([HsTyVar Name], -- TyVars; no dups - [(Name, Maybe Arity)], -- Tycons; no dups; arities for synonyms - [Name]) -- Classes; no dups - -get_binders decls = (bagToList tyvars, bagToList tycons, bagToList classes) - where - (tyvars, tycons, classes) = foldBag union3 get_binders1 - (emptyBag,emptyBag,emptyBag) - decls - - union3 (a1,a2,a3) (b1,b2,b3) - = (a1 `unionBags` b1, a2 `unionBags` b2, a3 `unionBags` b3) - -get_binders1 (TyD (TyData _ _ name tyvars _ _ _ _)) - = (listToBag tyvars, unitBag (name,Nothing), emptyBag) -get_binders1 (TyD (TySynonym name tyvars _ _)) - = (listToBag tyvars, unitBag (name, Just (length tyvars)), emptyBag) -get_binders1 (ClD (ClassDecl _ name tyvar sigs _ _ _)) - = (unitBag tyvar `unionBags` sigs_tvs sigs, - emptyBag, unitBag name) - -sigs_tvs sigs = unionManyBags (map sig_tvs sigs) - where - sig_tvs (ClassOpSig _ _ ty _) = pty_tvs ty - pty_tvs (HsForAllTy tvs _ _) = listToBag tvs -- tvs doesn't include the class tyvar - pty_tvs other = emptyBag -\end{code} +typeCycleErr, classCycleErr :: [[RenamedTyClDecl]] -> Message +typeCycleErr syn_cycles + = vcat (map (pp_cycle "Cycle in type declarations:") syn_cycles) -\begin{code} -typeCycleErr syn_cycles sty - = vcat (map (pp_cycle sty "Cycle in type declarations ...") syn_cycles) +classCycleErr cls_cycles + = vcat (map (pp_cycle "Cycle in class declarations:") cls_cycles) -classCycleErr cls_cycles sty - = vcat (map (pp_cycle sty "Cycle in class declarations ...") cls_cycles) - -pp_cycle sty str decls +pp_cycle str decls = hang (text str) 4 (vcat (map pp_decl decls)) where pp_decl decl - = hsep [ppr sty name, ppr sty (getSrcLoc name)] + = hsep [quotes (ppr name), ptext SLIT("at"), ppr (getSrcLoc name)] where - name = hsDeclName decl + name = tyClDeclName decl \end{code} + + + +