X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=compiler%2Ftypes%2FType.lhs;h=de0215e835a15238bd4d8dec191d0be2d8dc5742;hb=eab8711f0b0723c61ec4fece2b70983c90d92d19;hp=c3013ab5b3a12e7403912adc44c710d1d221a3de;hpb=a4c34367ce3e836f52f0ffb1e379ce81b8d65316;p=ghc-hetmet.git diff --git a/compiler/types/Type.lhs b/compiler/types/Type.lhs index c3013ab..de0215e 100644 --- a/compiler/types/Type.lhs +++ b/compiler/types/Type.lhs @@ -1,8 +1,9 @@ % +% (c) The University of Glasgow 2006 % (c) The GRASP/AQUA Project, Glasgow University, 1998 % -\section[Type]{Type - public interface} +Type - public interface \begin{code} module Type ( @@ -12,7 +13,7 @@ module Type ( -- Kinds Kind, SimpleKind, KindVar, - kindFunResult, splitKindFunTys, + kindFunResult, splitKindFunTys, splitKindFunTysN, liftedTypeKindTyCon, openTypeKindTyCon, unliftedTypeKindTyCon, argTypeKindTyCon, ubxTupleKindTyCon, @@ -24,7 +25,7 @@ module Type ( isLiftedTypeKind, isUnliftedTypeKind, isOpenTypeKind, isUbxTupleKind, isArgTypeKind, isKind, isTySuperKind, - isCoSuperKind, isSuperKind, isCoercionKind, + isCoSuperKind, isSuperKind, isCoercionKind, isEqPred, mkArrowKind, mkArrowKinds, isSubArgTypeKind, isSubOpenTypeKind, isSubKind, defaultKind, eqKind, @@ -93,7 +94,7 @@ module Type ( substPred, substTyVar, substTyVarBndr, deShadowTy, lookupTyVar, -- Pretty-printing - pprType, pprParendType, pprTyThingCategory, + pprType, pprParendType, pprTyThingCategory, pprForAll, pprPred, pprTheta, pprThetaArrow, pprClassPred, pprKind, pprParendKind ) where @@ -105,31 +106,22 @@ module Type ( import TypeRep -- friends: -import Var ( Var, TyVar, tyVarKind, tyVarName, - setTyVarName, setTyVarKind ) +import Var import VarEnv import VarSet -import OccName ( tidyOccName ) -import Name ( NamedThing(..), tidyNameOcc ) -import Class ( Class, classTyCon ) -import PrelNames( openTypeKindTyConKey, unliftedTypeKindTyConKey, - ubxTupleKindTyConKey, argTypeKindTyConKey ) -import TyCon ( TyCon, isRecursiveTyCon, isPrimTyCon, - isUnboxedTupleTyCon, isUnLiftedTyCon, - isFunTyCon, isNewTyCon, newTyConRep, newTyConRhs, - isAlgTyCon, tyConArity, isSuperKindTyCon, - tcExpandTyCon_maybe, coreExpandTyCon_maybe, - tyConKind, PrimRep(..), tyConPrimRep, tyConUnique, - isCoercionTyCon_maybe, isCoercionTyCon - ) +import Name +import Class +import PrelNames +import TyCon -- others -import StaticFlags ( opt_DictsStrict ) -import Util ( mapAccumL, seqList, lengthIs, snocView, thenCmp, isEqual, all2 ) +import StaticFlags +import Util import Outputable -import UniqSet ( sizeUniqSet ) -- Should come via VarSet -import Maybe ( isJust ) +import UniqSet + +import Data.Maybe ( isJust ) \end{code} @@ -164,7 +156,9 @@ coreView :: Type -> Maybe Type -- By being non-recursive and inlined, this case analysis gets efficiently -- joined onto the case analysis that the caller is already doing coreView (NoteTy _ ty) = Just ty -coreView (PredTy p) = Just (predTypeRep p) +coreView (PredTy p) + | isEqPred p = Nothing + | otherwise = Just (predTypeRep p) coreView (TyConApp tc tys) | Just (tenv, rhs, tys') <- coreExpandTyCon_maybe tc tys = Just (mkAppTys (substTy (mkTopTvSubst tenv) rhs) tys') -- Its important to use mkAppTys, rather than (foldl AppTy), @@ -305,10 +299,11 @@ splitAppTys ty = split ty ty [] \begin{code} mkFunTy :: Type -> Type -> Type +mkFunTy (PredTy (EqPred ty1 ty2)) res = mkForAllTy (mkWildCoVar (PredTy (EqPred ty1 ty2))) res mkFunTy arg res = FunTy arg res mkFunTys :: [Type] -> Type -> Type -mkFunTys tys ty = foldr FunTy ty tys +mkFunTys tys ty = foldr mkFunTy ty tys isFunTy :: Type -> Bool isFunTy ty = isJust (splitFunTy_maybe ty) @@ -445,7 +440,7 @@ repType looks through (b) synonyms (c) predicates (d) usage annotations - (e) all newtypes, including recursive ones + (e) all newtypes, including recursive ones, but not newtype families It's useful in the back end. \begin{code} @@ -454,7 +449,7 @@ repType :: Type -> Type repType ty | Just ty' <- coreView ty = repType ty' repType (ForAllTy _ ty) = repType ty repType (TyConApp tc tys) - | isNewTyCon tc = -- Recursive newtypes are opaque to coreView + | isClosedNewTyCon tc = -- Recursive newtypes are opaque to coreView -- but we must expand them here. Sure to -- be saturated because repType is only applied -- to types of kind * @@ -596,6 +591,7 @@ predTypeRep (IParam _ ty) = ty predTypeRep (ClassP clas tys) = mkTyConApp (classTyCon clas) tys -- Result might be a newtype application, but the consumer will -- look through that too if necessary +predTypeRep (EqPred ty1 ty2) = pprPanic "predTypeRep" (ppr (EqPred ty1 ty2)) \end{code} @@ -612,7 +608,7 @@ splitRecNewType_maybe :: Type -> Maybe Type -- Only applied to types of kind *, hence the newtype is always saturated splitRecNewType_maybe ty | Just ty' <- coreView ty = splitRecNewType_maybe ty' splitRecNewType_maybe (TyConApp tc tys) - | isNewTyCon tc + | isClosedNewTyCon tc = ASSERT( tys `lengthIs` tyConArity tc ) -- splitRecNewType_maybe only be applied -- to *types* (of kind *) ASSERT( isRecursiveTyCon tc ) -- Guaranteed by coreView @@ -1019,12 +1015,19 @@ cmpTypesX env ty [] = GT ------------- cmpPredX :: RnEnv2 -> PredType -> PredType -> Ordering cmpPredX env (IParam n1 ty1) (IParam n2 ty2) = (n1 `compare` n2) `thenCmp` cmpTypeX env ty1 ty2 - -- Compare types as well as names for implicit parameters - -- This comparison is used exclusively (I think) for the - -- finite map built in TcSimplify -cmpPredX env (ClassP c1 tys1) (ClassP c2 tys2) = (c1 `compare` c2) `thenCmp` cmpTypesX env tys1 tys2 -cmpPredX env (IParam _ _) (ClassP _ _) = LT -cmpPredX env (ClassP _ _) (IParam _ _) = GT + -- Compare names only for implicit parameters + -- This comparison is used exclusively (I believe) + -- for the Avails finite map built in TcSimplify + -- If the types differ we keep them distinct so that we see + -- a distinct pair to run improvement on +cmpPredX env (ClassP c1 tys1) (ClassP c2 tys2) = (c1 `compare` c2) `thenCmp` (cmpTypesX env tys1 tys2) +cmpPredX env (EqPred ty1 ty2) (EqPred ty1' ty2') = (cmpTypeX env ty1 ty1') `thenCmp` (cmpTypeX env ty2 ty2') + +-- Constructor order: IParam < ClassP < EqPred +cmpPredX env (IParam {}) _ = LT +cmpPredX env (ClassP {}) (IParam {}) = GT +cmpPredX env (ClassP {}) (EqPred {}) = LT +cmpPredX env (EqPred {}) _ = GT \end{code} PredTypes are used as a FM key in TcSimplify, @@ -1046,11 +1049,13 @@ instance Ord PredType where { compare = tcCmpPred } data TvSubst = TvSubst InScopeSet -- The in-scope type variables TvSubstEnv -- The substitution itself - -- See Note [Apply Once] + -- See Note [Apply Once] + -- and Note [Extending the TvSubstEnv] {- ---------------------------------------------------------- - Note [Apply Once] +Note [Apply Once] +~~~~~~~~~~~~~~~~~ We use TvSubsts to instantiate things, and we might instantiate forall a b. ty \with the types @@ -1067,6 +1072,38 @@ variations happen to; for example [a -> (a, b)]. A TvSubst is not idempotent, but, unlike the non-idempotent substitution we use during unifications, it must not be repeatedly applied. + +Note [Extending the TvSubst] +~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +The following invariant should hold of a TvSubst + + The in-scope set is needed *only* to + guide the generation of fresh uniques + + In particular, the *kind* of the type variables in + the in-scope set is not relevant + +This invariant allows a short-cut when the TvSubstEnv is empty: +if the TvSubstEnv is empty --- i.e. (isEmptyTvSubt subst) holds --- +then (substTy subst ty) does nothing. + +For example, consider: + (/\a. /\b:(a~Int). ...b..) Int +We substitute Int for 'a'. The Unique of 'b' does not change, but +nevertheless we add 'b' to the TvSubstEnv, because b's type does change + +This invariant has several crucial consequences: + +* In substTyVarBndr, we need extend the TvSubstEnv + - if the unique has changed + - or if the kind has changed + +* In substTyVar, we do not need to consult the in-scope set; + the TvSubstEnv is enough + +* In substTy, substTheta, we can short-circuit when the TvSubstEnv is empty + + -------------------------------------------------------------- -} @@ -1095,6 +1132,7 @@ composeTvSubst in_scope env1 env2 emptyTvSubst = TvSubst emptyInScopeSet emptyVarEnv isEmptyTvSubst :: TvSubst -> Bool + -- See Note [Extending the TvSubstEnv] isEmptyTvSubst (TvSubst _ env) = isEmptyVarEnv env mkTvSubst :: InScopeSet -> TvSubstEnv -> TvSubst @@ -1253,17 +1291,19 @@ subst_ty subst ty substTyVar :: TvSubst -> TyVar -> Type substTyVar subst@(TvSubst in_scope env) tv = case lookupTyVar subst tv of { - Nothing -> TyVarTy tv; + Nothing -> TyVarTy tv; Just ty -> ty -- See Note [Apply Once] } lookupTyVar :: TvSubst -> TyVar -> Maybe Type + -- See Note [Extending the TvSubst] lookupTyVar (TvSubst in_scope env) tv = lookupVarEnv env tv substTyVarBndr :: TvSubst -> TyVar -> (TvSubst, TyVar) substTyVarBndr subst@(TvSubst in_scope env) old_var = (TvSubst (in_scope `extendInScopeSet` new_var) new_env, new_var) where + is_co_var = isCoVar old_var new_env | no_change = delVarEnv env old_var | otherwise = extendVarEnv env old_var (TyVarTy new_var) @@ -1271,6 +1311,7 @@ substTyVarBndr subst@(TvSubst in_scope env) old_var no_change = new_var == old_var && not is_co_var -- no_change means that the new_var is identical in -- all respects to the old_var (same unique, same kind) + -- See Note [Extending the TvSubst] -- -- In that case we don't need to extend the substitution -- to map old to new. But instead we must zap any @@ -1282,12 +1323,10 @@ substTyVarBndr subst@(TvSubst in_scope env) old_var -- The uniqAway part makes sure the new variable is not already in scope subst_old_var -- subst_old_var is old_var with the substitution applied to its kind - -- It's only worth doing the substitution for coercions, - -- becuase only they can have free type variables - | is_co_var = setTyVarKind old_var (substTy subst kind) + -- It's only worth doing the substitution for coercions, + -- becuase only they can have free type variables + | is_co_var = setTyVarKind old_var (substTy subst (tyVarKind old_var)) | otherwise = old_var - kind = tyVarKind old_var - is_co_var = isCoercionKind kind \end{code} ---------------------------------------------------- @@ -1366,6 +1405,9 @@ kindFunResult k = funResultTy k splitKindFunTys :: Kind -> ([Kind],Kind) splitKindFunTys k = splitFunTys k +splitKindFunTysN :: Int -> Kind -> ([Kind],Kind) +splitKindFunTysN k = splitFunTysN k + isUbxTupleKind, isOpenTypeKind, isArgTypeKind, isUnliftedTypeKind :: Kind -> Bool isOpenTypeKindCon tc = tyConUnique tc == openTypeKindTyConKey @@ -1421,8 +1463,10 @@ isKind k = isSuperKind (typeKind k) isSubKind :: Kind -> Kind -> Bool -- (k1 `isSubKind` k2) checks that k1 <: k2 -isSubKind (TyConApp kc1 []) (TyConApp kc2 []) = kc1 `isSubKindCon` kc1 +isSubKind (TyConApp kc1 []) (TyConApp kc2 []) = kc1 `isSubKindCon` kc2 isSubKind (FunTy a1 r1) (FunTy a2 r2) = (a2 `isSubKind` a1) && (r1 `isSubKind` r2) +isSubKind (PredTy (EqPred ty1 ty2)) (PredTy (EqPred ty1' ty2')) + = ty1 `tcEqType` ty1' && ty2 `tcEqType` ty2' isSubKind k1 k2 = False eqKind :: Kind -> Kind -> Bool @@ -1458,11 +1502,7 @@ defaultKind k | isSubArgTypeKind k = liftedTypeKind | otherwise = k -isCoercionKind :: Kind -> Bool --- All coercions are of form (ty1 :=: ty2) --- This function is here rather than in Coercion, --- because it's used by substTy -isCoercionKind k | Just k' <- kindView k = isCoercionKind k' -isCoercionKind (PredTy (EqPred {})) = True -isCoercionKind other = False +isEqPred :: PredType -> Bool +isEqPred (EqPred _ _) = True +isEqPred other = False \end{code}