git.iko.soy/rowtype-yoga/purescript-native
on fff79d5 help sign in
rowtype-yoga/purescript-native/src/Language/PureScript/TypeChecker.hs
347 lines 16 kB history raw
1-----------------------------------------------------------------------------
2--
3-- Module : Language.PureScript.TypeChecker
4-- Copyright : (c) Phil Freeman 2013
5-- License : MIT
6--
7-- Maintainer : Phil Freeman <paf31@cantab.net>
8-- Stability : experimental
9-- Portability :
10--
11-- |
12-- The top-level type checker, which checks all declarations in a module.
13--
14-----------------------------------------------------------------------------
16{-# LANGUAGE FlexibleInstances #-}
18module Language.PureScript.TypeChecker (
19 module T,
20 typeCheckModule
21) where
23import Language.PureScript.TypeChecker.Monad as T
24import Language.PureScript.TypeChecker.Kinds as T
25import Language.PureScript.TypeChecker.Types as T
26import Language.PureScript.TypeChecker.Synonyms as T
28import Data.Maybe
29import Data.List (nub, (\\))
30import Data.Foldable (for_)
32import qualified Data.Map as M
34import Control.Monad.State
35import Control.Monad.Error.Class (MonadError(..))
37import Language.PureScript.Types
38import Language.PureScript.Names
39import Language.PureScript.Kinds
40import Language.PureScript.AST
41import Language.PureScript.TypeClassDictionaries
42import Language.PureScript.Environment
43import Language.PureScript.Errors
45addDataType :: ModuleName -> DataDeclType -> ProperName -> [(String, Maybe Kind)] -> [(ProperName, [Type])] -> Kind -> Check ()
46addDataType moduleName dtype name args dctors ctorKind = do
47 env <- getEnv
48 putEnv $ env { types = M.insert (Qualified (Just moduleName) name) (ctorKind, DataType args dctors) (types env) }
49 forM_ dctors $ \(dctor, tys) ->
50 rethrow (onErrorMessages (ErrorInDataConstructor dctor)) $
51 addDataConstructor moduleName dtype name (map fst args) dctor tys
53addDataConstructor :: ModuleName -> DataDeclType -> ProperName -> [String] -> ProperName -> [Type] -> Check ()
54addDataConstructor moduleName dtype name args dctor tys = do
55 env <- getEnv
56 mapM_ checkTypeSynonyms tys
57 let retTy = foldl TypeApp (TypeConstructor (Qualified (Just moduleName) name)) (map TypeVar args)
58 let dctorTy = foldr function retTy tys
59 let polyType = mkForAll args dctorTy
60 let fields = [Ident ("value" ++ show n) | n <- [0..(length tys - 1)]]
61 putEnv $ env { dataConstructors = M.insert (Qualified (Just moduleName) dctor) (dtype, name, polyType, fields) (dataConstructors env) }
63addTypeSynonym :: ModuleName -> ProperName -> [(String, Maybe Kind)] -> Type -> Kind -> Check ()
64addTypeSynonym moduleName name args ty kind = do
65 env <- getEnv
66 checkTypeSynonyms ty
67 putEnv $ env { types = M.insert (Qualified (Just moduleName) name) (kind, TypeSynonym) (types env)
68 , typeSynonyms = M.insert (Qualified (Just moduleName) name) (args, ty) (typeSynonyms env) }
70valueIsNotDefined :: ModuleName -> Ident -> Check ()
71valueIsNotDefined moduleName name = do
72 env <- getEnv
73 case M.lookup (moduleName, name) (names env) of
74 Just _ -> throwError . errorMessage $ RedefinedIdent name
75 Nothing -> return ()
77addValue :: ModuleName -> Ident -> Type -> NameKind -> Check ()
78addValue moduleName name ty nameKind = do
79 env <- getEnv
80 putEnv (env { names = M.insert (moduleName, name) (ty, nameKind, Defined) (names env) })
82addTypeClass :: ModuleName -> ProperName -> [(String, Maybe Kind)] -> [Constraint] -> [Declaration] -> Check ()
83addTypeClass moduleName pn args implies ds =
84 let members = map toPair ds in
85 modify $ \st -> st { checkEnv = (checkEnv st) { typeClasses = M.insert (Qualified (Just moduleName) pn) (args, members, implies) (typeClasses . checkEnv $ st) } }
86 where
87 toPair (TypeDeclaration ident ty) = (ident, ty)
88 toPair (PositionedDeclaration _ _ d) = toPair d
89 toPair _ = error "Invalid declaration in TypeClassDeclaration"
91addTypeClassDictionaries :: [TypeClassDictionaryInScope] -> Check ()
92addTypeClassDictionaries entries =
93 let mentries = M.fromList [ ((canonicalizeDictionary entry, mn), entry) | entry@TypeClassDictionaryInScope{ tcdName = Qualified mn _ } <- entries ]
94 in modify $ \st -> st { checkEnv = (checkEnv st) { typeClassDictionaries = (typeClassDictionaries . checkEnv $ st) `M.union` mentries } }
96checkDuplicateTypeArguments :: [String] -> Check ()
97checkDuplicateTypeArguments args = for_ firstDup $ \dup ->
98 throwError . errorMessage $ DuplicateTypeArgument dup
99 where
100 firstDup :: Maybe String
101 firstDup = listToMaybe $ args \\ nub args
103checkTypeClassInstance :: ModuleName -> Type -> Check ()
104checkTypeClassInstance _ (TypeVar _) = return ()
105checkTypeClassInstance _ (TypeConstructor ctor) = do
106 env <- getEnv
107 when (ctor `M.member` typeSynonyms env) . throwError . errorMessage $ TypeSynonymInstance
108 return ()
109checkTypeClassInstance m (TypeApp t1 t2) = checkTypeClassInstance m t1 >> checkTypeClassInstance m t2
110checkTypeClassInstance _ ty = throwError . errorMessage $ InvalidInstanceHead ty
112-- |
113-- Check that type synonyms are fully-applied in a type
114--
115checkTypeSynonyms :: Type -> Check ()
116checkTypeSynonyms = void . replaceAllTypeSynonyms
118-- |
119-- Type check all declarations in a module
120--
121-- At this point, many declarations will have been desugared, but it is still necessary to
122--
123-- * Kind-check all types and add them to the @Environment@
124--
125-- * Type-check all values and add them to the @Environment@
126--
127-- * Bring type class instances into scope
128--
129-- * Process module imports
130--
131typeCheckAll :: Maybe ModuleName -> ModuleName -> [DeclarationRef] -> [Declaration] -> Check [Declaration]
132typeCheckAll mainModuleName moduleName exps = go
133 where
134 go :: [Declaration] -> Check [Declaration]
135 go [] = return []
136 go (DataDeclaration dtype name args dctors : rest) = do
137 rethrow (onErrorMessages (ErrorInTypeConstructor name)) $ do
138 when (dtype == Newtype) $ checkNewtype dctors
139 checkDuplicateTypeArguments $ map fst args
140 ctorKind <- kindsOf True moduleName name args (concatMap snd dctors)
141 let args' = args `withKinds` ctorKind
142 addDataType moduleName dtype name args' dctors ctorKind
143 ds <- go rest
144 return $ DataDeclaration dtype name args dctors : ds
145 where
146 checkNewtype :: [(ProperName, [Type])] -> Check ()
147 checkNewtype [(_, [_])] = return ()
148 checkNewtype [(_, _)] = throwError . errorMessage $ InvalidNewtype
149 checkNewtype _ = throwError . errorMessage $ InvalidNewtype
150 go (d@(DataBindingGroupDeclaration tys) : rest) = do
151 rethrow (onErrorMessages ErrorInDataBindingGroup) $ do
152 let syns = mapMaybe toTypeSynonym tys
153 let dataDecls = mapMaybe toDataDecl tys
154 (syn_ks, data_ks) <- kindsOfAll moduleName syns (map (\(_, name, args, dctors) -> (name, args, concatMap snd dctors)) dataDecls)
155 forM_ (zip dataDecls data_ks) $ \((dtype, name, args, dctors), ctorKind) -> do
156 checkDuplicateTypeArguments $ map fst args
157 let args' = args `withKinds` ctorKind
158 addDataType moduleName dtype name args' dctors ctorKind
159 forM_ (zip syns syn_ks) $ \((name, args, ty), kind) -> do
160 checkDuplicateTypeArguments $ map fst args
161 let args' = args `withKinds` kind
162 addTypeSynonym moduleName name args' ty kind
163 ds <- go rest
164 return $ d : ds
165 where
166 toTypeSynonym (TypeSynonymDeclaration nm args ty) = Just (nm, args, ty)
167 toTypeSynonym (PositionedDeclaration _ _ d') = toTypeSynonym d'
168 toTypeSynonym _ = Nothing
169 toDataDecl (DataDeclaration dtype nm args dctors) = Just (dtype, nm, args, dctors)
170 toDataDecl (PositionedDeclaration _ _ d') = toDataDecl d'
171 toDataDecl _ = Nothing
172 go (TypeSynonymDeclaration name args ty : rest) = do
173 rethrow (onErrorMessages (ErrorInTypeSynonym name)) $ do
174 checkDuplicateTypeArguments $ map fst args
175 kind <- kindsOf False moduleName name args [ty]
176 let args' = args `withKinds` kind
177 addTypeSynonym moduleName name args' ty kind
178 ds <- go rest
179 return $ TypeSynonymDeclaration name args ty : ds
180 go (TypeDeclaration _ _ : _) = error "Type declarations should have been removed"
181 go (ValueDeclaration name nameKind [] (Right val) : rest) = do
182 d <- rethrow (onErrorMessages (ErrorInValueDeclaration name)) $ do
183 valueIsNotDefined moduleName name
184 [(_, (val', ty))] <- typesOf mainModuleName moduleName [(name, val)]
185 addValue moduleName name ty nameKind
186 return $ ValueDeclaration name nameKind [] $ Right val'
187 ds <- go rest
188 return $ d : ds
189 go (ValueDeclaration{} : _) = error "Binders were not desugared"
190 go (BindingGroupDeclaration vals : rest) = do
191 d <- rethrow (onErrorMessages (ErrorInBindingGroup (map (\(ident, _, _) -> ident) vals))) $ do
192 forM_ (map (\(ident, _, _) -> ident) vals) $ \name ->
193 valueIsNotDefined moduleName name
194 tys <- typesOf mainModuleName moduleName $ map (\(ident, _, ty) -> (ident, ty)) vals
195 vals' <- forM [ (name, val, nameKind, ty)
196 | (name, nameKind, _) <- vals
197 , (name', (val, ty)) <- tys
198 , name == name'
199 ] $ \(name, val, nameKind, ty) -> do
200 addValue moduleName name ty nameKind
201 return (name, nameKind, val)
202 return $ BindingGroupDeclaration vals'
203 ds <- go rest
204 return $ d : ds
205 go (d@(ExternDataDeclaration name kind) : rest) = do
206 env <- getEnv
207 putEnv $ env { types = M.insert (Qualified (Just moduleName) name) (kind, ExternData) (types env) }
208 ds <- go rest
209 return $ d : ds
210 go (d@(ExternDeclaration importTy name _ ty) : rest) = do
211 rethrow (onErrorMessages (ErrorInForeignImport name)) $ do
212 env <- getEnv
213 kind <- kindOf moduleName ty
214 guardWith (errorMessage (ExpectedType kind)) $ kind == Star
215 case M.lookup (moduleName, name) (names env) of
216 Just _ -> throwError . errorMessage $ RedefinedIdent name
217 Nothing -> putEnv (env { names = M.insert (moduleName, name) (ty, Extern importTy, Defined) (names env) })
218 ds <- go rest
219 return $ d : ds
220 go (d@(FixityDeclaration _ name) : rest) = do
221 ds <- go rest
222 env <- getEnv
223 guardWith (errorMessage (OrphanFixityDeclaration name)) $ M.member (moduleName, Op name) $ names env
224 return $ d : ds
225 go (d@(ImportDeclaration importedModule _ _) : rest) = do
226 tcds <- getTypeClassDictionaries
227 let instances = filter (\tcd -> let Qualified (Just mn) _ = tcdName tcd in importedModule == mn) tcds
228 addTypeClassDictionaries [ tcd { tcdName = Qualified (Just moduleName) ident, tcdType = TCDAlias (canonicalizeDictionary tcd) }
229 | tcd <- instances
230 , tcdExported tcd
231 , let (Qualified _ ident) = tcdName tcd
232 ]
233 ds <- go rest
234 return $ d : ds
235 go (d@(TypeClassDeclaration pn args implies tys) : rest) = do
236 addTypeClass moduleName pn args implies tys
237 ds <- go rest
238 return $ d : ds
239 go (d@(TypeInstanceDeclaration dictName deps className tys _) : rest) = do
240 goInstance d dictName deps className tys rest
241 go (d@(ExternInstanceDeclaration dictName deps className tys) : rest) = do
242 goInstance d dictName deps className tys rest
243 go (PositionedDeclaration pos com d : rest) =
244 rethrowWithPosition pos $ do
245 (d' : rest') <- go (d : rest)
246 return (PositionedDeclaration pos com d' : rest')
247 goInstance :: Declaration -> Ident -> [Constraint] -> Qualified ProperName -> [Type] -> [Declaration] -> Check [Declaration]
248 goInstance d dictName deps className tys rest = do
249 mapM_ (checkTypeClassInstance moduleName) tys
250 forM_ deps $ mapM_ (checkTypeClassInstance moduleName) . snd
251 addTypeClassDictionaries [TypeClassDictionaryInScope (Qualified (Just moduleName) dictName) className tys (Just deps) TCDRegular isInstanceExported]
252 ds <- go rest
253 return $ d : ds
255 where
257 isInstanceExported :: Bool
258 isInstanceExported = any exportsInstance exps
260 exportsInstance :: DeclarationRef -> Bool
261 exportsInstance (TypeInstanceRef name) | name == dictName = True
262 exportsInstance (PositionedDeclarationRef _ _ r) = exportsInstance r
263 exportsInstance _ = False
265 -- |
266 -- This function adds the argument kinds for a type constructor so that they may appear in the externs file,
267 -- extracted from the kind of the type constructor itself.
268 --
269 withKinds :: [(String, Maybe Kind)] -> Kind -> [(String, Maybe Kind)]
270 withKinds [] _ = []
271 withKinds (s@(_, Just _ ):ss) (FunKind _ k) = s : withKinds ss k
272 withKinds ( (s, Nothing):ss) (FunKind k1 k2) = (s, Just k1) : withKinds ss k2
273 withKinds _ _ = error "Invalid arguments to peelKinds"
275-- |
276-- Type check an entire module and ensure all types and classes defined within the module that are
277-- required by exported members are also exported.
278--
279typeCheckModule :: Maybe ModuleName -> Module -> Check Module
280typeCheckModule _ (Module _ _ _ Nothing) = error "exports should have been elaborated"
281typeCheckModule mainModuleName (Module coms mn decls (Just exps)) = rethrow (onErrorMessages (ErrorInModule mn)) $ do
282 modify (\s -> s { checkCurrentModule = Just mn })
283 decls' <- typeCheckAll mainModuleName mn exps decls
284 forM_ exps $ \e -> do
285 checkTypesAreExported e
286 checkClassMembersAreExported e
287 checkClassesAreExported e
288 return $ Module coms mn decls' (Just exps)
289 where
291 checkMemberExport :: (Type -> [DeclarationRef]) -> DeclarationRef -> Check ()
292 checkMemberExport extract dr@(ValueRef name) = do
293 ty <- lookupVariable mn (Qualified (Just mn) name)
294 case filter (not . exported) (extract ty) of
295 [] -> return ()
296 hidden -> throwError . errorMessage $ TransitiveExportError dr hidden
297 where
298 exported e = any (exports e) exps
299 exports (TypeRef pn1 _) (TypeRef pn2 _) = pn1 == pn2
300 exports (ValueRef id1) (ValueRef id2) = id1 == id2
301 exports (TypeClassRef pn1) (TypeClassRef pn2) = pn1 == pn2
302 exports (TypeInstanceRef id1) (TypeInstanceRef id2) = id1 == id2
303 exports (PositionedDeclarationRef _ _ r1) r2 = exports r1 r2
304 exports r1 (PositionedDeclarationRef _ _ r2) = exports r1 r2
305 exports _ _ = False
306 checkMemberExport _ _ = return ()
308 -- Check that all the type constructors defined in the current module that appear in member types
309 -- have also been exported from the module
310 checkTypesAreExported :: DeclarationRef -> Check ()
311 checkTypesAreExported = checkMemberExport findTcons
312 where
313 findTcons :: Type -> [DeclarationRef]
314 findTcons = everythingOnTypes (++) go
315 where
316 go (TypeConstructor (Qualified (Just mn') name)) | mn' == mn = [TypeRef name (error "Data constructors unused in checkTypesAreExported")]
317 go _ = []
319 -- Check that all the classes defined in the current module that appear in member types have also
320 -- been exported from the module
321 checkClassesAreExported :: DeclarationRef -> Check ()
322 checkClassesAreExported = checkMemberExport findClasses
323 where
324 findClasses :: Type -> [DeclarationRef]
325 findClasses = everythingOnTypes (++) go
326 where
327 go (ConstrainedType cs _) = mapMaybe (fmap TypeClassRef . extractCurrentModuleClass . fst) cs
328 go _ = []
329 extractCurrentModuleClass :: Qualified ProperName -> Maybe ProperName
330 extractCurrentModuleClass (Qualified (Just mn') name) | mn == mn' = Just name
331 extractCurrentModuleClass _ = Nothing
333 checkClassMembersAreExported :: DeclarationRef -> Check ()
334 checkClassMembersAreExported dr@(TypeClassRef name) = do
335 let members = ValueRef `map` head (mapMaybe findClassMembers decls)
336 let missingMembers = members \\ exps
337 unless (null missingMembers) $ throwError . errorMessage $ TransitiveExportError dr members
338 where
339 findClassMembers :: Declaration -> Maybe [Ident]
340 findClassMembers (TypeClassDeclaration name' _ _ ds) | name == name' = Just $ map extractMemberName ds
341 findClassMembers (PositionedDeclaration _ _ d) = findClassMembers d
342 findClassMembers _ = Nothing
343 extractMemberName :: Declaration -> Ident
344 extractMemberName (PositionedDeclaration _ _ d) = extractMemberName d
345 extractMemberName (TypeDeclaration memberName _) = memberName
346 extractMemberName _ = error "Unexpected declaration in typeclass member list"
347 checkClassMembersAreExported _ = return ()