X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=ghc%2Fcompiler%2Ftypecheck%2FTcTyClsDecls.lhs;h=bdf1488e57c197310d6d54cacf0342c7129646ac;hb=495ef8bd9ef30bffe50ea399b91e3ba09646b59a;hp=7de928a77b6b8722a142d346122604950540f02b;hpb=c4f3290f3d4c2a5c2e81a97717f7fd06ee180f6d;p=ghc-hetmet.git diff --git a/ghc/compiler/typecheck/TcTyClsDecls.lhs b/ghc/compiler/typecheck/TcTyClsDecls.lhs index 7de928a..bdf1488 100644 --- a/ghc/compiler/typecheck/TcTyClsDecls.lhs +++ b/ghc/compiler/typecheck/TcTyClsDecls.lhs @@ -1,59 +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} module TcTyClsDecls ( - tcTyAndClassDecls1 + tcTyAndClassDecls ) where #include "HsVersions.h" -import HsSyn ( HsDecl(..), TyDecl(..), ClassDecl(..), - HsType(..), HsTyVar, +import HsSyn ( HsDecl(..), TyClDecl(..), + HsType(..), HsTyVarBndr, ConDecl(..), ConDetails(..), BangType(..), - Sig(..), - hsDeclName + Sig(..), HsPred(..), HsTupCon(..), + tyClDeclName, isClassDecl, isSynDecl ) -import RnHsSyn ( RenamedTyDecl(..), RenamedClassDecl(..), RenamedHsDecl ) -import TcHsSyn ( TcHsBinds ) -import BasicTypes ( RecFlag(..) ) +import RnHsSyn ( RenamedHsDecl, RenamedTyClDecl, listTyCon_name ) +import BasicTypes ( RecFlag(..), NewOrData(..), Arity ) import TcMonad import Inst ( InstanceMapper ) -import TcClassDcl ( tcClassDecl1 ) -import TcEnv ( TcIdOcc(..), GlobalValueEnv, tcExtendTyConEnv, tcExtendClassEnv ) -import TcKind ( TcKind, newKindVar, newKindVars, tcDefaultKind, kindToTcKind ) -import TcTyDecls ( tcTyDecl, mkDataBinds ) -import TcMonoType ( tcTyVarScope ) - -import TyCon ( tyConKind, tyConArity, isSynTyCon ) -import Class ( Class, classBigSig ) -import TyVar ( tyVarKind ) +import TcClassDcl ( kcClassDecl, tcClassDecl1 ) +import TcEnv ( ValueEnv, TcTyThing(..), + tcExtendTypeEnv, getEnvAllTyCons + ) +import TcTyDecls ( tcTyDecl, kcTyDecl ) +import TcMonoType ( kcHsTyVar ) +import TcType ( TcKind, newKindVar, newKindVars, kindToTcKind, zonkTcKindToKind ) + +import Type ( mkArrowKind, boxedTypeKind ) + +import Class ( Class ) +import Var ( TyVar, tyVarKind ) +import FiniteMap import Bag +import VarSet import Digraph ( stronglyConnComp, SCC(..) ) import Name ( Name, NamedThing(..), getSrcLoc, isTvOcc, nameOccName ) import Outputable -import Maybes ( mapMaybe ) +import Maybes ( mapMaybe, catMaybes, expectJust ) import UniqSet ( UniqSet, emptyUniqSet, unitUniqSet, unionUniqSets, unionManyUniqSets, uniqSetToList ) +import ErrUtils ( Message ) import SrcLoc ( SrcLoc ) -import TyCon ( TyCon, 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 :: GlobalValueEnv -> 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 @@ -62,66 +67,44 @@ tcGroups unf_env inst_mapper [] returnTc env tcGroups unf_env inst_mapper (group:groups) - = tcGroup unf_env inst_mapper group `thenTc` \ (group_tycons, group_classes) -> - - -- Extend the environment using the new tycons and classes - tcExtendTyConEnv [(getName tycon, (kindToTcKind (tyConKind tycon), - if isSynTyCon tycon then Just (tyConArity tycon) else Nothing, - tycon)) - | tycon <- group_tycons] $ - - tcExtendClassEnv [(getName clas, (classKind clas, clas)) - | clas <- group_classes] $ - - - -- Do the remaining groups + = tcGroup unf_env inst_mapper group `thenTc` \ env -> + tcSetEnv env $ tcGroups unf_env inst_mapper groups - where - classKind clas = map (kindToTcKind . tyVarKind) tyvars - where - (tyvars, _, _, _, _) = classBigSig clas \end{code} Dealing with a group ~~~~~~~~~~~~~~~~~~~~ -Notice the uses of @zipLazy@, which makes sure -that the knot-tied TyVars, TyCons and Classes aren't looked at too early. +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 :: GlobalValueEnv -> InstanceMapper -> SCC RenamedHsDecl -> TcM s ([TyCon], [Class]) +tcGroup :: ValueEnv -> InstanceMapper -> SCC RenamedTyClDecl -> TcM s TcEnv tcGroup unf_env inst_mapper scc - = -- TIE THE KNOT - fixTc ( \ ~(rec_tycons, rec_classes) -> - - -- EXTEND TYPE AND CLASS ENVIRONMENTS - let - mk_tycon_bind (name, arity) = newKindVar `thenNF_Tc` \ kind -> - returnNF_Tc (name, (kind, arity, find name rec_tycons)) - - mk_class_bind (name, arity) = newKindVars arity `thenNF_Tc` \ kinds -> - returnNF_Tc (name, (kinds, find name rec_classes)) - - find name [] = pprPanic "tcGroup" (ppr name) - find name (thing:things) | name == getName thing = thing - | otherwise = find name things - - in - mapNF_Tc mk_tycon_bind tycon_names_w_arities `thenNF_Tc` \ tycon_binds -> - mapNF_Tc mk_class_bind class_names_w_arities `thenNF_Tc` \ class_binds -> - tcExtendTyConEnv tycon_binds $ - tcExtendClassEnv class_binds $ - - -- DEAL WITH TYPE VARIABLES - tcTyVarScope tyvar_names ( \ tyvars -> - - -- DEAL WITH THE DEFINITIONS THEMSELVES - foldlTc (tcDecl is_rec_group unf_env inst_mapper) ([], []) decls - ) `thenTc` \ (tycons, classes) -> - - returnTc (tycons, classes) - ) + = -- 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, _) -> + let + rec_env = listToUFM rec_tyclss + rec_tycons = getEnvAllTyCons rec_tyclss + rec_vrcs = calcTyConArgVrcs rec_tycons + 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 -> + returnTc (tyclss, env) + ) `thenTc` \ (_, env) -> +-- traceTc (text "done" <+> ppr (map fst ty_env_stuff1)) `thenTc_` + returnTc env where is_rec_group = case scc of AcyclicSCC _ -> NonRecursive @@ -130,188 +113,232 @@ tcGroup unf_env inst_mapper scc decls = case scc of AcyclicSCC decl -> [decl] CyclicSCC decls -> decls - - (tyvar_names, tycon_names_w_arities, class_names_w_arities) = get_binders decls \end{code} Dealing with one decl ~~~~~~~~~~~~~~~~~~~~~ \begin{code} +kcDecl decl + = tcAddDeclCtxt decl $ + if isClassDecl decl then + kcClassDecl decl + else + kcTyDecl decl + tcDecl :: RecFlag -- True => recursive group - -> GlobalValueEnv -> InstanceMapper - -> ([TyCon], [Class]) -- Accumulating parameter - -> RenamedHsDecl - -> TcM s ([TyCon], [Class]) - -tcDecl is_rec_group unf_env inst_mapper (tycons, classes) (TyD decl) - = tcTyDecl is_rec_group decl `thenTc` \ tycon -> - returnTc (tycon:tycons, classes) - -tcDecl is_rec_group unf_env inst_mapper (tycons, classes) (ClD decl) - = tcClassDecl1 unf_env inst_mapper decl `thenTc` \ clas -> - returnTc (tycons, clas:classes) + -> ValueEnv -> InstanceMapper -> FiniteMap Name ArgVrcs + -> RenamedTyClDecl -> TcM s (Name, TcTyThing) + +tcDecl is_rec_group unf_env inst_mapper vrcs_env decl + = tcAddDeclCtxt decl $ + if isClassDecl decl then + tcClassDecl1 unf_env inst_mapper vrcs_env decl + else + tcTyDecl is_rec_group vrcs_env 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: + +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. + + [April 00: looks as if we've dropped this subtlety; I'm not sure when] + +\begin{code} +getTyBinding1 :: RenamedTyClDecl -> NF_TcM s (Name, (TcKind, 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, + ASynTyCon (pprPanic "ATyCon: syn" (ppr name)) (length tyvars))) + +getTyBinding1 (TyData _ _ name tyvars _ _ _ _ _) + = mapNF_Tc kcHsTyVar tyvars `thenNF_Tc` \ arg_kinds -> + returnNF_Tc (name, (foldr mkArrowKind boxedTypeKind arg_kinds, + ADataTyCon (error "ATyCon: data"))) + +getTyBinding1 (ClassDecl _ name tyvars _ _ _ _ _ _ _ _ _) + = mapNF_Tc kcHsTyVar tyvars `thenNF_Tc` \ arg_kinds -> + returnNF_Tc (name, (foldr mkArrowKind boxedTypeKind arg_kinds, + AClass (pprPanic "AClass" (ppr name)) (length tyvars))) + +-- Zonk the kind to its final form, and lookup the +-- recursive tycon/class +getTyBinding2 rec_env (name, (tc_kind, thing)) + = zonkTcKindToKind tc_kind `thenNF_Tc` \ kind -> + returnNF_Tc (name, (kind, mk_thing thing (lookupUFM rec_env name))) + where + mk_thing (ADataTyCon _) ~(Just (ADataTyCon tc)) = ADataTyCon tc + mk_thing (ASynTyCon _ arity) ~(Just (ASynTyCon tc _)) = ASynTyCon tc arity + mk_thing (AClass _ arity) ~(Just (AClass cls _)) = AClass cls arity \end{code} + +%************************************************************************ +%* * +\subsection{Dependency analysis} +%* * +%************************************************************************ + Dependency analysis ~~~~~~~~~~~~~~~~~~~ \begin{code} -sortByDependency :: [RenamedHsDecl] -> TcM s [SCC 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) + decl_sccs = stronglyConnComp edges in 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 \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` - get_cons condecls `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 (catMaybes (map get_clas 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_ctxt ctxt = unionManyUniqSets (map set_name (catMaybes (map get_clas ctxt))) +get_clas (HsPClass clas _) = Just clas +get_clas _ = Nothing +---------------------------------------------------- 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_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 (HsForAllTy _ ctxt mty) - = get_ctxt ctxt `unionUniqSets` get_ty mty -get_ty other = panic "TcTyClsDecls:get_ty" - -get_tys tys - = unionManyUniqSets (map get_ty tys) - +get_bty (Unpacked ty) = get_ty ty + +---------------------------------------------------- +get_ty (HsTyVar name) | isTvOcc (nameOccName name) = emptyUniqSet + | otherwise = set_name name +get_ty (HsAppTy ty1 ty2) = unionUniqSets (get_ty ty1) (get_ty ty2) +get_ty (HsFunTy ty1 ty2) = unionUniqSets (get_ty ty1) (get_ty ty2) +get_ty (HsListTy ty) = set_name listTyCon_name `unionUniqSets` get_ty ty +get_ty (HsTupleTy (HsTupCon n _) tys) = set_name n `unionUniqSets` get_tys tys +get_ty (HsUsgTy _ ty) = get_ty ty +get_ty (HsUsgForAllTy _ ty) = get_ty ty +get_ty (HsForAllTy _ ctxt mty) = get_ctxt ctxt `unionUniqSets` get_ty mty +get_ty (HsPredTy (HsPClass name _)) = set_name name +get_ty (HsPredTy (HsPIParam _ _)) = emptyUniqSet -- I think + +---------------------------------------------------- +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 :: [RenamedHsDecl] - -> ([HsTyVar Name], -- TyVars; no dups - [(Name, Maybe Arity)], -- Tycons; no dups; arities for synonyms - [(Name, Arity)]) -- Classes; no dups; with their arities +typeCycleErr, classCycleErr :: [[RenamedTyClDecl]] -> Message -get_binders decls = (bagToList tyvars, bagToList tycons, bagToList classes) - where - (tyvars, tycons, classes) = foldr (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 tyvars sigs _ _ _ _ _)) - = (listToBag tyvars `unionBags` sigs_tvs sigs, - emptyBag, unitBag (name, length tyvars)) - -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} - - -\begin{code} typeCycleErr syn_cycles = vcat (map (pp_cycle "Cycle in type declarations:") syn_cycles) @@ -325,5 +352,5 @@ pp_cycle str decls pp_decl decl = hsep [quotes (ppr name), ptext SLIT("at"), ppr (getSrcLoc name)] where - name = hsDeclName decl + name = tyClDeclName decl \end{code}