Le.hs revision c58a94c44b76b072ace930f2126c889c0b64cb2a
e9458b1a7a19a63aa4c179f9ab20f4d50681c168Jens ElknerModule : $Header$
fd8af3ecf2dff782cb2496c1c9bf9d0a76faa98bLiam O'ReillyCopyright : (c) Christian Maeder and Uni Bremen 2003-2005
fd8af3ecf2dff782cb2496c1c9bf9d0a76faa98bLiam O'ReillyLicense : similar to LGPL, see HetCATS/LICENSE.txt or LIZENZ.txt
98890889ffb2e8f6f722b00e265a211f13b5a861Corneliu-Claudiu ProdescuMaintainer : maeder@tzi.de
fd8af3ecf2dff782cb2496c1c9bf9d0a76faa98bLiam O'ReillyStability : experimental
fd8af3ecf2dff782cb2496c1c9bf9d0a76faa98bLiam O'ReillyPortability : portable
fd8af3ecf2dff782cb2496c1c9bf9d0a76faa98bLiam O'Reillyabstract syntax during static analysis
fd8af3ecf2dff782cb2496c1c9bf9d0a76faa98bLiam O'Reillyimport qualified Common.Lib.Map as Map
c3efd4f435e954846981cf46bca64e0485266634Liam O'Reillyimport qualified Common.Lib.Set as Set
c3efd4f435e954846981cf46bca64e0485266634Liam O'Reillyimport Common.Result(Diagnosis)
d3b4ad111a281d125659e12d6641943f29d6b3dfLiam O'Reilly-- * class info
fd8af3ecf2dff782cb2496c1c9bf9d0a76faa98bLiam O'Reilly-- | store the raw kind and all superclasses of a class identifier
c3efd4f435e954846981cf46bca64e0485266634Liam O'Reillydata ClassInfo = ClassInfo { rawKind :: RawKind
c3efd4f435e954846981cf46bca64e0485266634Liam O'Reilly , classKinds :: [Kind]
c3efd4f435e954846981cf46bca64e0485266634Liam O'Reilly } deriving (Show, Eq)
33bdce26495121cdbce30331ef90a1969126a840Liam O'Reillytype ClassMap = Map.Map ClassId ClassInfo
33bdce26495121cdbce30331ef90a1969126a840Liam O'Reilly-- * type info
c3efd4f435e954846981cf46bca64e0485266634Liam O'Reilly-- | data type generatedness indicator
c3efd4f435e954846981cf46bca64e0485266634Liam O'Reillydata GenKind = Free | Generated | Loose deriving (Show, Eq, Ord)
c3efd4f435e954846981cf46bca64e0485266634Liam O'Reilly-- | an analysed alternative with a list of (product) types
33bdce26495121cdbce30331ef90a1969126a840Liam O'Reillydata AltDefn = Construct (Maybe UninstOpId) [Type] Partiality [[Selector]]
1b2195930f52ad43e6bb64b1df0cf6718bfd84c0Liam O'Reilly -- only argument types
1b2195930f52ad43e6bb64b1df0cf6718bfd84c0Liam O'Reilly deriving (Show, Eq, Ord)
1b2195930f52ad43e6bb64b1df0cf6718bfd84c0Liam O'Reilly-- | an analysed component
1b2195930f52ad43e6bb64b1df0cf6718bfd84c0Liam O'Reillydata Selector = Select (Maybe UninstOpId) Type Partiality -- only result type
1b2195930f52ad43e6bb64b1df0cf6718bfd84c0Liam O'Reilly deriving (Show, Eq, Ord)
1b2195930f52ad43e6bb64b1df0cf6718bfd84c0Liam O'Reilly-- | a mapping of type (and disjoint class) identifiers
c3efd4f435e954846981cf46bca64e0485266634Liam O'Reillytype IdMap = Map.Map TypeId TypeId
c3efd4f435e954846981cf46bca64e0485266634Liam O'Reilly-- | for data types the morphism needs to be kept as well
fd8af3ecf2dff782cb2496c1c9bf9d0a76faa98bLiam O'Reillydata DataEntry = DataEntry IdMap TypeId GenKind [TypeArg] [AltDefn]
9738b4e358f960105062839c835bb9eff3e44588Liam O'Reilly deriving (Show, Eq, Ord)
d3b4ad111a281d125659e12d6641943f29d6b3dfLiam O'Reilly-- | possible definitions for type identifiers
9738b4e358f960105062839c835bb9eff3e44588Liam O'Reillydata TypeDefn = NoTypeDefn
9738b4e358f960105062839c835bb9eff3e44588Liam O'Reilly | PreDatatype -- auxiliary entry for DatatypeDefn
c3efd4f435e954846981cf46bca64e0485266634Liam O'Reilly | Supertype Vars TypeScheme Term
33bdce26495121cdbce30331ef90a1969126a840Liam O'Reilly | DatatypeDefn DataEntry
33bdce26495121cdbce30331ef90a1969126a840Liam O'Reilly | AliasTypeDefn TypeScheme
c3efd4f435e954846981cf46bca64e0485266634Liam O'Reilly deriving (Show, Eq)
c3efd4f435e954846981cf46bca64e0485266634Liam O'Reilly-- | for type identifiers also store the raw kind, instances and supertypes
c3efd4f435e954846981cf46bca64e0485266634Liam O'Reillydata TypeInfo = TypeInfo { typeKind :: RawKind
c3efd4f435e954846981cf46bca64e0485266634Liam O'Reilly , otherTypeKinds :: [Kind]
c3efd4f435e954846981cf46bca64e0485266634Liam O'Reilly , superTypes :: [Type]
c3efd4f435e954846981cf46bca64e0485266634Liam O'Reilly , typeDefn :: TypeDefn
c3efd4f435e954846981cf46bca64e0485266634Liam O'Reilly } deriving (Show, Eq)
c3efd4f435e954846981cf46bca64e0485266634Liam O'Reillytype TypeMap = Map.Map TypeId TypeInfo
c3efd4f435e954846981cf46bca64e0485266634Liam O'Reilly-- | the minimal information for a sort
fd8af3ecf2dff782cb2496c1c9bf9d0a76faa98bLiam O'ReillystarTypeInfo :: TypeInfo
fd8af3ecf2dff782cb2496c1c9bf9d0a76faa98bLiam O'ReillystarTypeInfo = TypeInfo star [star] [] NoTypeDefn
3d3889e0cefcdce9b3f43c53aaa201943ac2e895Jonathan von Schroeder-- | recursively substitute type names within a type
c3efd4f435e954846981cf46bca64e0485266634Liam O'Reillyrename :: (TypeId -> Kind -> Int -> Type) -> Type -> Type
3d3889e0cefcdce9b3f43c53aaa201943ac2e895Jonathan von Schroederrename m t = case t of
3d3889e0cefcdce9b3f43c53aaa201943ac2e895Jonathan von Schroeder TypeName i k n -> m i k n
fd8af3ecf2dff782cb2496c1c9bf9d0a76faa98bLiam O'Reilly TypeAppl t1 t2 -> TypeAppl (rename m t1) (rename m t2)
fd8af3ecf2dff782cb2496c1c9bf9d0a76faa98bLiam O'Reilly ExpandedType t1 t2 -> ExpandedType (rename m t1) (rename m t2)
c3efd4f435e954846981cf46bca64e0485266634Liam O'Reilly TypeToken _ -> t
c3efd4f435e954846981cf46bca64e0485266634Liam O'Reilly BracketType b l ps ->
fd8af3ecf2dff782cb2496c1c9bf9d0a76faa98bLiam O'Reilly BracketType b (map (rename m) l) ps
fd8af3ecf2dff782cb2496c1c9bf9d0a76faa98bLiam O'Reilly KindedType tk k ps ->
c3efd4f435e954846981cf46bca64e0485266634Liam O'Reilly KindedType (rename m tk) k ps
c3efd4f435e954846981cf46bca64e0485266634Liam O'Reilly MixfixType l -> MixfixType $ map (rename m) l
c3efd4f435e954846981cf46bca64e0485266634Liam O'Reilly LazyType tl ps -> LazyType (rename m tl) ps
3d3889e0cefcdce9b3f43c53aaa201943ac2e895Jonathan von Schroeder ProductType l ps -> ProductType (map (rename m) l) ps
fd8af3ecf2dff782cb2496c1c9bf9d0a76faa98bLiam O'Reilly FunType t1 a t2 ps -> FunType (rename m t1) a (rename m t2) ps
c3efd4f435e954846981cf46bca64e0485266634Liam O'Reilly-- | rename the type according to identifier map (for comorphisms)
c3efd4f435e954846981cf46bca64e0485266634Liam O'ReillymapType :: IdMap -> Type -> Type
c3efd4f435e954846981cf46bca64e0485266634Liam O'ReillymapType m ty = if Map.null m then ty else
3d3889e0cefcdce9b3f43c53aaa201943ac2e895Jonathan von Schroeder rename ( \ i k n ->
3d3889e0cefcdce9b3f43c53aaa201943ac2e895Jonathan von Schroeder let t = TypeName i k n in
c3efd4f435e954846981cf46bca64e0485266634Liam O'Reilly if n == 0 then
fd8af3ecf2dff782cb2496c1c9bf9d0a76faa98bLiam O'Reilly Just j -> TypeName j k 0
c3efd4f435e954846981cf46bca64e0485266634Liam O'Reilly-- * sentences
fd8af3ecf2dff782cb2496c1c9bf9d0a76faa98bLiam O'Reilly-- | data types are also special sentences because of their properties
fd8af3ecf2dff782cb2496c1c9bf9d0a76faa98bLiam O'Reillydata Sentence = Formula Term
c3efd4f435e954846981cf46bca64e0485266634Liam O'Reilly | DatatypeSen [DataEntry]
c3efd4f435e954846981cf46bca64e0485266634Liam O'Reilly | ProgEqSen UninstOpId TypeScheme ProgEq
fd8af3ecf2dff782cb2496c1c9bf9d0a76faa98bLiam O'Reilly deriving (Show, Eq, Ord)
c3efd4f435e954846981cf46bca64e0485266634Liam O'Reilly-- * variables
fd8af3ecf2dff782cb2496c1c9bf9d0a76faa98bLiam O'Reilly-- | type variable are kept separately
3d3889e0cefcdce9b3f43c53aaa201943ac2e895Jonathan von Schroederdata TypeVarDefn = TypeVarDefn RawKind VarKind Int deriving Show
d3b4ad111a281d125659e12d6641943f29d6b3dfLiam O'Reillytype LocalTypeVars = Map.Map TypeId TypeVarDefn
d3b4ad111a281d125659e12d6641943f29d6b3dfLiam O'Reilly-- | the type of a local variable
fd8af3ecf2dff782cb2496c1c9bf9d0a76faa98bLiam O'Reillydata VarDefn = VarDefn Type deriving Show
3348c9a9d620bfab82296cc7f7a8f968f79916bcLiam O'Reilly-- * assumptions
fd8af3ecf2dff782cb2496c1c9bf9d0a76faa98bLiam O'Reilly-- | name and scheme of a constructor
05cc55892e6c93bdd7b9c3f100ab1bb65fe6a21eLiam O'Reillydata ConstrInfo = ConstrInfo { constrId :: UninstOpId
05cc55892e6c93bdd7b9c3f100ab1bb65fe6a21eLiam O'Reilly , constrType :: TypeScheme
05cc55892e6c93bdd7b9c3f100ab1bb65fe6a21eLiam O'Reilly } deriving (Show, Eq)
05cc55892e6c93bdd7b9c3f100ab1bb65fe6a21eLiam O'Reilly-- | possible definitions of functions
05cc55892e6c93bdd7b9c3f100ab1bb65fe6a21eLiam O'Reillydata OpDefn = NoOpDefn OpBrand
05cc55892e6c93bdd7b9c3f100ab1bb65fe6a21eLiam O'Reilly | ConstructData TypeId -- target type
c3efd4f435e954846981cf46bca64e0485266634Liam O'Reilly | SelectData [ConstrInfo] TypeId -- constructors of source type
c3efd4f435e954846981cf46bca64e0485266634Liam O'Reilly | Definition OpBrand Term
c3efd4f435e954846981cf46bca64e0485266634Liam O'Reilly deriving (Show, Eq)
c3efd4f435e954846981cf46bca64e0485266634Liam O'Reilly-- | scheme, attributes and definition for function identifiers
3d3889e0cefcdce9b3f43c53aaa201943ac2e895Jonathan von Schroederdata OpInfo = OpInfo { opType :: TypeScheme
3d3889e0cefcdce9b3f43c53aaa201943ac2e895Jonathan von Schroeder , opAttrs :: [OpAttr]
c3efd4f435e954846981cf46bca64e0485266634Liam O'Reilly , opDefn :: OpDefn
c3efd4f435e954846981cf46bca64e0485266634Liam O'Reilly } deriving (Show, Eq)
3d3889e0cefcdce9b3f43c53aaa201943ac2e895Jonathan von Schroeder-- | test for constructor
3d3889e0cefcdce9b3f43c53aaa201943ac2e895Jonathan von SchroederisConstructor :: OpInfo -> Bool
c3efd4f435e954846981cf46bca64e0485266634Liam O'ReillyisConstructor o = case opDefn o of
3d3889e0cefcdce9b3f43c53aaa201943ac2e895Jonathan von Schroeder ConstructData _ -> True
3d3889e0cefcdce9b3f43c53aaa201943ac2e895Jonathan von Schroeder-- | a list of infos for overloaded functions
c3efd4f435e954846981cf46bca64e0485266634Liam O'Reillydata OpInfos = OpInfos { opInfos :: [OpInfo] } deriving (Show, Eq)
c3efd4f435e954846981cf46bca64e0485266634Liam O'Reillytype Assumps = Map.Map UninstOpId OpInfos
33bdce26495121cdbce30331ef90a1969126a840Liam O'Reilly-- * the local environment and final signature
33bdce26495121cdbce30331ef90a1969126a840Liam O'Reilly-- | the precedence map
33bdce26495121cdbce30331ef90a1969126a840Liam O'Reillytype PrecMap = (Map.Map Id Int, Int, Int)
33bdce26495121cdbce30331ef90a1969126a840Liam O'Reilly-- | the signature is established by the classes, types and assumptions
33bdce26495121cdbce30331ef90a1969126a840Liam O'Reillydata Env = Env { classMap :: ClassMap
3d3889e0cefcdce9b3f43c53aaa201943ac2e895Jonathan von Schroeder , typeMap :: TypeMap
33bdce26495121cdbce30331ef90a1969126a840Liam O'Reilly , localTypeVars :: LocalTypeVars
3d3889e0cefcdce9b3f43c53aaa201943ac2e895Jonathan von Schroeder , assumps :: Assumps
3d3889e0cefcdce9b3f43c53aaa201943ac2e895Jonathan von Schroeder , localVars :: Map.Map Id VarDefn
3d3889e0cefcdce9b3f43c53aaa201943ac2e895Jonathan von Schroeder , sentences :: [Named Sentence]
33bdce26495121cdbce30331ef90a1969126a840Liam O'Reilly , envDiags :: [Diagnosis]
33bdce26495121cdbce30331ef90a1969126a840Liam O'Reilly , preIds :: (PrecMap, Set.Set Id)
33bdce26495121cdbce30331ef90a1969126a840Liam O'Reilly , counter :: Int
d3b4ad111a281d125659e12d6641943f29d6b3dfLiam O'Reilly } deriving Show
d3b4ad111a281d125659e12d6641943f29d6b3dfLiam O'Reilly-- | the empty environment (fresh variables start with 1)
d3b4ad111a281d125659e12d6641943f29d6b3dfLiam O'ReillyinitialEnv :: Env
3d3889e0cefcdce9b3f43c53aaa201943ac2e895Jonathan von SchroederinitialEnv = Env Map.empty Map.empty Map.empty Map.empty Map.empty [] []
1b2195930f52ad43e6bb64b1df0cf6718bfd84c0Liam O'Reilly-- * symbol stuff
3d3889e0cefcdce9b3f43c53aaa201943ac2e895Jonathan von Schroeder-- | the type or kind of an identifier
3d3889e0cefcdce9b3f43c53aaa201943ac2e895Jonathan von Schroederdata SymbolType = OpAsItemType TypeScheme
1b2195930f52ad43e6bb64b1df0cf6718bfd84c0Liam O'Reilly | TypeAsItemType Kind
1b2195930f52ad43e6bb64b1df0cf6718bfd84c0Liam O'Reilly | ClassAsItemType Kind
1b2195930f52ad43e6bb64b1df0cf6718bfd84c0Liam O'Reilly deriving (Show, Eq, Ord)
1b2195930f52ad43e6bb64b1df0cf6718bfd84c0Liam O'Reilly-- symbols (may) need the env to look up type aliases
1b2195930f52ad43e6bb64b1df0cf6718bfd84c0Liam O'Reillydata Symbol = Symbol {symName :: Id, symType :: SymbolType, symEnv :: Env}
1b2195930f52ad43e6bb64b1df0cf6718bfd84c0Liam O'Reilly deriving Show
1b2195930f52ad43e6bb64b1df0cf6718bfd84c0Liam O'Reillyinstance Eq Symbol where
1b2195930f52ad43e6bb64b1df0cf6718bfd84c0Liam O'Reilly s1 == s2 = (symName s1, symType s1) == (symName s2, symType s2)
1b2195930f52ad43e6bb64b1df0cf6718bfd84c0Liam O'Reillyinstance Ord Symbol where
1b2195930f52ad43e6bb64b1df0cf6718bfd84c0Liam O'Reilly s1 <= s2 = (symName s1, symType s1) <= (symName s2, symType s2)
1b2195930f52ad43e6bb64b1df0cf6718bfd84c0Liam O'Reillytype SymbolMap = Map.Map Symbol Symbol
1b2195930f52ad43e6bb64b1df0cf6718bfd84c0Liam O'Reillytype SymbolSet = Set.Set Symbol
1b2195930f52ad43e6bb64b1df0cf6718bfd84c0Liam O'ReillyidToTypeSymbol :: Env -> Id -> Kind -> Symbol
1b2195930f52ad43e6bb64b1df0cf6718bfd84c0Liam O'ReillyidToTypeSymbol e idt k = Symbol idt (TypeAsItemType k) e
1b2195930f52ad43e6bb64b1df0cf6718bfd84c0Liam O'ReillyidToClassSymbol :: Env -> Id -> Kind -> Symbol
1b2195930f52ad43e6bb64b1df0cf6718bfd84c0Liam O'ReillyidToClassSymbol e idt k = Symbol idt (ClassAsItemType k) e
3d3889e0cefcdce9b3f43c53aaa201943ac2e895Jonathan von SchroederidToOpSymbol :: Env -> Id -> TypeScheme -> Symbol
c3efd4f435e954846981cf46bca64e0485266634Liam O'ReillyidToOpSymbol e idt typ = Symbol idt (OpAsItemType typ) e
c3efd4f435e954846981cf46bca64e0485266634Liam O'Reilly-- note that the type of a qualified raw symbol is not analysed!
3d3889e0cefcdce9b3f43c53aaa201943ac2e895Jonathan von Schroederdata RawSymbol = AnID Id | AKindedId SymbKind Id
3d3889e0cefcdce9b3f43c53aaa201943ac2e895Jonathan von Schroeder | AQualId Id SymbolType
9738b4e358f960105062839c835bb9eff3e44588Liam O'Reilly | ASymbol Symbol
9738b4e358f960105062839c835bb9eff3e44588Liam O'Reilly deriving (Show, Eq, Ord)
3d3889e0cefcdce9b3f43c53aaa201943ac2e895Jonathan von Schroedertype RawSymbolMap = Map.Map RawSymbol RawSymbol
c3efd4f435e954846981cf46bca64e0485266634Liam O'ReillyidToRaw :: Id -> RawSymbol
3d3889e0cefcdce9b3f43c53aaa201943ac2e895Jonathan von SchroederidToRaw x = AnID x
3d3889e0cefcdce9b3f43c53aaa201943ac2e895Jonathan von SchroederrawSymName :: RawSymbol -> Id
3d3889e0cefcdce9b3f43c53aaa201943ac2e895Jonathan von SchroederrawSymName (AnID i) = i
fd8af3ecf2dff782cb2496c1c9bf9d0a76faa98bLiam O'ReillyrawSymName (AKindedId _ i) = i
3d3889e0cefcdce9b3f43c53aaa201943ac2e895Jonathan von SchroederrawSymName (AQualId i _) = i
fd8af3ecf2dff782cb2496c1c9bf9d0a76faa98bLiam O'ReillyrawSymName (ASymbol s) = symName s
3d3889e0cefcdce9b3f43c53aaa201943ac2e895Jonathan von SchroedersymbTypeToKind :: SymbolType -> SymbKind
9738b4e358f960105062839c835bb9eff3e44588Liam O'ReillysymbTypeToKind (OpAsItemType _) = SK_op
9738b4e358f960105062839c835bb9eff3e44588Liam O'ReillysymbTypeToKind (TypeAsItemType _) = SK_type
9738b4e358f960105062839c835bb9eff3e44588Liam O'ReillysymbTypeToKind (ClassAsItemType _) = SK_class
3d3889e0cefcdce9b3f43c53aaa201943ac2e895Jonathan von SchroedersymbolToRaw :: Symbol -> RawSymbol
3d3889e0cefcdce9b3f43c53aaa201943ac2e895Jonathan von SchroedersymbolToRaw sym = ASymbol sym
3d3889e0cefcdce9b3f43c53aaa201943ac2e895Jonathan von SchroedersymbKindToRaw :: SymbKind -> Id -> RawSymbol
05cc55892e6c93bdd7b9c3f100ab1bb65fe6a21eLiam O'ReillysymbKindToRaw Implicit = AnID
05cc55892e6c93bdd7b9c3f100ab1bb65fe6a21eLiam O'ReillysymbKindToRaw sk = AKindedId $ case sk of
05cc55892e6c93bdd7b9c3f100ab1bb65fe6a21eLiam O'Reilly SK_pred -> SK_op
05cc55892e6c93bdd7b9c3f100ab1bb65fe6a21eLiam O'Reilly SK_fun -> SK_op
05cc55892e6c93bdd7b9c3f100ab1bb65fe6a21eLiam O'Reilly SK_sort -> SK_type