TypeAna.hs revision 81d182b21020b815887e9057959228546cf61b6b
66267bcb678a9c341272c323b299337bcfdb7cc5Christian MaederModule : $Header$
66267bcb678a9c341272c323b299337bcfdb7cc5Christian MaederDescription : infer the kinds of types
66267bcb678a9c341272c323b299337bcfdb7cc5Christian MaederCopyright : (c) Christian Maeder and Uni Bremen 2003-2005
e7ce154edb906685b3fa7f6c0a764e18a4658068Christian MaederLicense : similar to LGPL, see HetCATS/LICENSE.txt or LIZENZ.txt
ffd01020a4f35f434b912844ad6e0d6918fadffdChristian MaederMaintainer : Christian.Maeder@dfki.de
66267bcb678a9c341272c323b299337bcfdb7cc5Christian MaederStability : experimental
66267bcb678a9c341272c323b299337bcfdb7cc5Christian MaederPortability : portable
08b724e8dcbba5820d80f0974b9a5385140815baChristian Maederimport qualified Data.Map as Map
e8ffec0fa3d3061061bdc16e44247b9cf96b050fChristian Maederimport qualified Data.Set as Set
e7ce154edb906685b3fa7f6c0a764e18a4658068Christian Maeder-- * infer kind
e7ce154edb906685b3fa7f6c0a764e18a4658068Christian Maeder-- | inspect types and classes only
e7ce154edb906685b3fa7f6c0a764e18a4658068Christian Maedertype TypeEnv = Env
e7ce154edb906685b3fa7f6c0a764e18a4658068Christian Maeder-- | extract kinds of type identifier
e7ce154edb906685b3fa7f6c0a764e18a4658068Christian MaedergetIdKind :: TypeEnv -> Id -> Result ((Variance, RawKind, [Kind]), Type)
024621f43239cfe9629e35d35a8669fad7acbba2Christian MaedergetIdKind te i =
cf3232cec840a6945667bdb06f5b47b22243bc8fChristian Maeder case Map.lookup i $ localTypeVars te of
cf3232cec840a6945667bdb06f5b47b22243bc8fChristian Maeder Nothing -> case Map.lookup i $ typeMap te of
e7ce154edb906685b3fa7f6c0a764e18a4658068Christian Maeder Nothing -> mkError "unknown type" i
e7ce154edb906685b3fa7f6c0a764e18a4658068Christian Maeder Just (TypeInfo rk l _ _) -> return ((InVar, rk, l), TypeName i rk 0)
e7ce154edb906685b3fa7f6c0a764e18a4658068Christian Maeder Just (TypeVarDefn v vk rk c) ->
51281dddda866c0cda9fca22bf6bc4eea7128112Christian Maeder return ((v, rk, [toKind vk]), TypeName i rk c)
ac07a6558423dae7adc488ed9092cd8e9450a29dChristian Maeder-- | extract kinds of co- or invariant type identifiers
cf3232cec840a6945667bdb06f5b47b22243bc8fChristian MaedergetCoVarKind :: Maybe Bool -> TypeEnv -> Id -> Result ((RawKind, [Kind]), Type)
cf3232cec840a6945667bdb06f5b47b22243bc8fChristian MaedergetCoVarKind b te i = do
cf3232cec840a6945667bdb06f5b47b22243bc8fChristian Maeder ((v, rk, l), ty) <- getIdKind te i
cf3232cec840a6945667bdb06f5b47b22243bc8fChristian Maeder case (v, b) of
e7ce154edb906685b3fa7f6c0a764e18a4658068Christian Maeder (ContraVar, Just True) -> Result
e7ce154edb906685b3fa7f6c0a764e18a4658068Christian Maeder [mkDiag Hint "wrong contravariance of" i] $ Just ((rk, []), ty)
e7ce154edb906685b3fa7f6c0a764e18a4658068Christian Maeder (CoVar, Just False) -> Result
e7ce154edb906685b3fa7f6c0a764e18a4658068Christian Maeder [mkDiag Hint "wrong covariance of" i] $ Just ((rk, []), ty)
e7ce154edb906685b3fa7f6c0a764e18a4658068Christian Maeder _ -> return ((rk, keepMinKinds (classMap te) l), ty)
fb50920e621bfc152c19147cb52077ff06b3526bChristian Maeder-- | check if there is at least one solution
df638d53c2d5fe5e80b943a58609c8936848ed82Christian MaedersubKinds :: DiagKind -> ClassMap -> Type -> Kind -> [Kind] -> [Kind]
df638d53c2d5fe5e80b943a58609c8936848ed82Christian Maeder -> Result [Kind]
e7ce154edb906685b3fa7f6c0a764e18a4658068Christian MaedersubKinds dk cm ty sk ks res =
e7ce154edb906685b3fa7f6c0a764e18a4658068Christian Maeder if any ( \ k -> lesserKind cm k sk) ks then return res
df638d53c2d5fe5e80b943a58609c8936848ed82Christian Maeder else Result [Diag dk
e7ce154edb906685b3fa7f6c0a764e18a4658068Christian Maeder ("no kind found for '" ++ showDoc ty "'" ++
fb50920e621bfc152c19147cb52077ff06b3526bChristian Maeder if null ks then "" else expected sk $ head ks)
fb50920e621bfc152c19147cb52077ff06b3526bChristian Maeder $ getRange ty] $ Just []
df638d53c2d5fe5e80b943a58609c8936848ed82Christian Maeder-- | add an analysed type argument (warn on redeclared types)
df638d53c2d5fe5e80b943a58609c8936848ed82Christian MaederaddTypeVarDecl :: Bool -> TypeArg -> State Env ()
e7ce154edb906685b3fa7f6c0a764e18a4658068Christian MaederaddTypeVarDecl warn (TypeArg i v vk rk c _ _) =
df638d53c2d5fe5e80b943a58609c8936848ed82Christian Maeder addLocalTypeVar warn (TypeVarDefn v vk rk c) i
cf3232cec840a6945667bdb06f5b47b22243bc8fChristian MaederaddLocalTypeVar :: Bool -> TypeVarDefn -> Id -> State Env ()
c18e9c3c6d5039618f1f2c05526ece84c7794ea3Christian MaederaddLocalTypeVar warn tvd i = do
c18e9c3c6d5039618f1f2c05526ece84c7794ea3Christian Maeder tvs <- gets localTypeVars
cf3232cec840a6945667bdb06f5b47b22243bc8fChristian Maeder if warn then do
e7ce154edb906685b3fa7f6c0a764e18a4658068Christian Maeder tm <- gets typeMap
fb69cd512eab767747f109e40322df7cae2f7bdfChristian Maeder Nothing -> case Map.lookup i tvs of
31242f7541fd6ef179e4eb5be7522ddf54ae397bChristian Maeder Nothing -> return ()
31242f7541fd6ef179e4eb5be7522ddf54ae397bChristian Maeder Just _ -> addDiags [mkDiag Hint "rebound type variable" i]
31242f7541fd6ef179e4eb5be7522ddf54ae397bChristian Maeder Just _ -> addDiags [mkDiag Hint
31242f7541fd6ef179e4eb5be7522ddf54ae397bChristian Maeder "type variable shadows type constructor" i]
628310b42327ad76ce471caf0dde6563d6fa6307Christian Maeder else return ()
e7ce154edb906685b3fa7f6c0a764e18a4658068Christian Maeder putLocalTypeVars $ Map.insert i tvd tvs
e7ce154edb906685b3fa7f6c0a764e18a4658068Christian Maeder-- | infer all minimal kinds
628310b42327ad76ce471caf0dde6563d6fa6307Christian MaederinferKinds :: Maybe Bool -> Type -> TypeEnv -> Result ((RawKind, [Kind]), Type)
e7ce154edb906685b3fa7f6c0a764e18a4658068Christian MaederinferKinds b ty te@Env{classMap = cm} = case ty of
04dada28736b4a237745e92063d8bdd49a362debChristian Maeder TypeName i _ _ -> getCoVarKind b te i
e7ce154edb906685b3fa7f6c0a764e18a4658068Christian Maeder TypeAppl t1 t2 -> do
76fa667489c5e0868ac68de9f0253ac10f73d0b5Christian Maeder ((rk, ks), t3) <- inferKinds b t1 te
628310b42327ad76ce471caf0dde6563d6fa6307Christian Maeder FunKind v _ rr _ -> do
628310b42327ad76ce471caf0dde6563d6fa6307Christian Maeder ((_, l), t4) <- inferKinds (case v of
628310b42327ad76ce471caf0dde6563d6fa6307Christian Maeder ContraVar -> Just $ maybe False not b
628310b42327ad76ce471caf0dde6563d6fa6307Christian Maeder CoVar -> Just $ maybe True id b
628310b42327ad76ce471caf0dde6563d6fa6307Christian Maeder InVar -> Nothing) t2 te
712f5e5ca1c3a5cfdd28518154ecf2dd0994cdb5Christian Maeder kks <- mapM (getFunKinds cm) ks
628310b42327ad76ce471caf0dde6563d6fa6307Christian Maeder rs <- mapM ( \ fk -> case fk of
ffd01020a4f35f434b912844ad6e0d6918fadffdChristian Maeder FunKind _ arg res _ -> do
ffd01020a4f35f434b912844ad6e0d6918fadffdChristian Maeder subKinds Hint cm t2 arg l [res]
ffd01020a4f35f434b912844ad6e0d6918fadffdChristian Maeder _ -> error "inferKinds: no function kind"
f0742398d4587242b1a115de113cd17f63dcb6d0Christian Maeder ) $ keepMinKinds cm $ concat kks
f0742398d4587242b1a115de113cd17f63dcb6d0Christian Maeder return ((rr, keepMinKinds cm $ concat rs), TypeAppl t3 t4)
f0742398d4587242b1a115de113cd17f63dcb6d0Christian Maeder _ -> mkError "unexpected type argument" t2
f0742398d4587242b1a115de113cd17f63dcb6d0Christian Maeder TypeAbs ta@(TypeArg _ v k r _ _ q) t ps -> do
f0742398d4587242b1a115de113cd17f63dcb6d0Christian Maeder let newEnv = execState (addTypeVarDecl False ta) te
e7ce154edb906685b3fa7f6c0a764e18a4658068Christian Maeder ((rk, ks), nt) <- inferKinds Nothing t newEnv
e7ce154edb906685b3fa7f6c0a764e18a4658068Christian Maeder return ((FunKind v r rk q, map (\ j -> FunKind v (toKind k) j q) ks)
e7ce154edb906685b3fa7f6c0a764e18a4658068Christian Maeder , TypeAbs ta nt ps)
e7ce154edb906685b3fa7f6c0a764e18a4658068Christian Maeder KindedType kt kind ps -> do
e7ce154edb906685b3fa7f6c0a764e18a4658068Christian Maeder let Result ds _ = anaKindM kind cm
e7ce154edb906685b3fa7f6c0a764e18a4658068Christian Maeder k <- if null ds then return kind else Result ds Nothing
e7ce154edb906685b3fa7f6c0a764e18a4658068Christian Maeder ((rk, ks), t) <- inferKinds b kt te
e7ce154edb906685b3fa7f6c0a764e18a4658068Christian Maeder l <- subKinds Hint cm kt k ks [k]
e7ce154edb906685b3fa7f6c0a764e18a4658068Christian Maeder return ((rk, l), KindedType t k ps)
e7ce154edb906685b3fa7f6c0a764e18a4658068Christian Maeder ExpandedType t1 t2 -> do
e7ce154edb906685b3fa7f6c0a764e18a4658068Christian Maeder ((rk, ks), t4) <- inferKinds b t2 te
fb69cd512eab767747f109e40322df7cae2f7bdfChristian Maeder ((_, aks), t3) <- inferKinds b t1 te
4954b30d3c209d7dee4e43016cee8189daf646e8Christian Maeder return ((rk, keepMinKinds cm $ aks ++ ks), ExpandedType t3 t4)
4954b30d3c209d7dee4e43016cee8189daf646e8Christian Maeder _ -> error "inferKinds"
08b724e8dcbba5820d80f0974b9a5385140815baChristian Maeder-- * converting type terms
08b724e8dcbba5820d80f0974b9a5385140815baChristian Maeder-- | throw away alias or kind information
4954b30d3c209d7dee4e43016cee8189daf646e8Christian MaederstripType :: String -> Type -> Type
08b724e8dcbba5820d80f0974b9a5385140815baChristian MaederstripType msg ty = case ty of
4954b30d3c209d7dee4e43016cee8189daf646e8Christian Maeder ExpandedType _ t -> t
5ea4161a514362065110614dd0d92adb13bf7cc3Christian Maeder KindedType t _ _ -> t
4954b30d3c209d7dee4e43016cee8189daf646e8Christian Maeder _ -> error $ "stripType " ++ msg
e7ce154edb906685b3fa7f6c0a764e18a4658068Christian Maeder-- * subtyping relation
08b724e8dcbba5820d80f0974b9a5385140815baChristian Maeder-- | extract the raw kind from a type term
08b724e8dcbba5820d80f0974b9a5385140815baChristian MaederrawKindOfType :: Type -> RawKind
08b724e8dcbba5820d80f0974b9a5385140815baChristian MaederrawKindOfType ty = case ty of
08b724e8dcbba5820d80f0974b9a5385140815baChristian Maeder TypeName _ k _ -> k
08b724e8dcbba5820d80f0974b9a5385140815baChristian Maeder TypeAppl t1 _ -> case rawKindOfType t1 of
08b724e8dcbba5820d80f0974b9a5385140815baChristian Maeder FunKind _ _ rk _ -> rk
08b724e8dcbba5820d80f0974b9a5385140815baChristian Maeder _ -> error "rawKindOfType"
ee9eddfa6953868fd6fbaff0d9ff68675a13675aChristian Maeder TypeAbs (TypeArg _ v _ r _ _ _) t ps ->
ee9eddfa6953868fd6fbaff0d9ff68675a13675aChristian Maeder FunKind v r (rawKindOfType t) ps
ee9eddfa6953868fd6fbaff0d9ff68675a13675aChristian Maeder _ -> rawKindOfType $ stripType "rawKindOfType" ty
ee9eddfa6953868fd6fbaff0d9ff68675a13675aChristian Maeder-- | subtyping relation
ee9eddfa6953868fd6fbaff0d9ff68675a13675aChristian MaederlesserType :: TypeEnv -> Type -> Type -> Bool
ee9eddfa6953868fd6fbaff0d9ff68675a13675aChristian MaederlesserType te t1 t2 = case (t1, t2) of
ee9eddfa6953868fd6fbaff0d9ff68675a13675aChristian Maeder (TypeAppl c1 a1, TypeAppl c2 a2) ->
ee9eddfa6953868fd6fbaff0d9ff68675a13675aChristian Maeder let b1 = lesserType te a1 a2
ee9eddfa6953868fd6fbaff0d9ff68675a13675aChristian Maeder b2 = lesserType te a2 a1
ee9eddfa6953868fd6fbaff0d9ff68675a13675aChristian Maeder in (case (rawKindOfType c1, rawKindOfType c2) of
ee9eddfa6953868fd6fbaff0d9ff68675a13675aChristian Maeder (FunKind v1 _ _ _, FunKind v2 _ _ _) ->
ee9eddfa6953868fd6fbaff0d9ff68675a13675aChristian Maeder if v1 == v2 then case v1 of
ee9eddfa6953868fd6fbaff0d9ff68675a13675aChristian Maeder ContraVar -> b2
ee9eddfa6953868fd6fbaff0d9ff68675a13675aChristian Maeder _ -> error "lesserType: no FunKind") && lesserType te c1 c2
ee9eddfa6953868fd6fbaff0d9ff68675a13675aChristian Maeder (TypeName i1 _ _, TypeName i2 _ _) | i1 == i2 -> True
(TypeName i k _, _) -> case Map.lookup i $ localTypeVars te of
Nothing -> case Map.lookup i $ typeMap te of
Set.toList $ superTypes ti
TypeAppl t1 t2 -> leaves b t1 `List.union` leaves b t2
List.delete (c, (i, r)) $ leaves b ty
idsOf :: (Int -> Bool) -> Type -> Set.Set TypeId
idsOf b = Set.fromList . map (fst . snd) . leaves b
repl :: Map.Map Id Type -> Type -> Type
case Map.lookup i m of
superIds :: TypeMap -> Id -> Set.Set Id
if Set.null new then known else
let more = Set.unions $ map ( \ i -> superTypes
$ Map.findWithDefault starTypeInfo i tm)
$ Set.toList new
newKnown = Set.union known new
filterAliases = Map.filter ( \ ti -> case typeDefn ti of
expandAliases tm = if Map.null tm then id else expandAux tm
case Map.lookup i tm of
Map.keysSet $ filterAliases tm
cyclicType i ty = Set.member i $ idsOf (==0) ty