----------------------------------------------------------------------------- -- | -- Module : Language.C.Analysis.NameSpaceMap -- Copyright : (c) [1995..1999] Manuel M. T. Chakravarty -- (c) 2008 Benedikt Huber -- License : BSD-style -- Maintainer : benedikt.huber@gmail.com -- Stability : alpha -- Portability : portable -- -- This module manages name spaces. -- -- * A name space map associates identifiers with their definition. -- -- * Each name space map is organized in a hierarchical way using the notion of -- scopes. A name space map, at any moment, always has a global scope and may -- have several local scopes. Definitions in inner scopes hide definitions -- of the same identifier in outer scopes. -- module Language.C.Analysis.NameSpaceMap ( -- * name space maps NameSpaceMap, nameSpaceMap, nsMapToList, globalNames,localNames,hasLocalNames, -- * scope modification defGlobal, enterNewScope, leaveScope, defLocal, lookupName,lookupGlobal,lookupInnermostScope, mergeNameSpace ) where import Prelude hiding (lookup) import qualified Prelude import qualified Data.Map as Map (empty, insert, lookup, toList, union) import qualified Data.List as List (unionBy) import Data.Map (Map) import Language.C.Data.Ident (Ident) {- C Namespaces and scopes: -} -- DevDocs: -- -- * the definitions in the global scope are stored in a finite map, because -- they tend to be a lot. -- -- * the definitions of the local scopes are stored in a single list, usually -- they are not very many and the definitions entered last are the most -- frequently accessed ones; the list structure naturally hides older -- definitions, i.e., definitions from outer scopes; adding new definitions -- is done in time proportinal to the current size of the scope; removing a -- scope is done in constant time (and the definitions of a scope can be -- returned as a result of leaving the scope); lookup is proportional to the -- number of definitions in the local scopes and the logarithm of the number -- of definitions in the global scope -- i.e., efficiency relies on a -- relatively low number of local definitions together with frequent lookup -- of the most recently defined local identifiers -- -- | @NameSpaceMap a@ is a Map from identifiers to @a@, which manages -- global and local name spaces. data NameSpaceMap k v = NsMap (Map k v) -- defs in global scope [[(k, v)]] -- stack of local scopes globalNames :: (Ord k) => NameSpaceMap k v -> Map k v globalNames (NsMap g _) = g hasLocalNames :: NameSpaceMap k v -> Bool hasLocalNames (NsMap _ l) = not (null l) localNames :: (Ord k) => NameSpaceMap k v -> [[(k,v)]] localNames (NsMap _ l) = l -- | create a name space nameSpaceMap :: (Ord k) => NameSpaceMap k v nameSpaceMap = NsMap Map.empty [] -- | Add global definition -- -- @(ns',oldDef) = defGlobal ns ident def@ -- adds a global definition @ident := def@ to the namespace. -- It returns the modified namespace @ns'@. If the identifier is -- already declared in the global namespace, the definition is overwritten -- and the old definition @oldDef@ is returned. defGlobal :: (Ord k) => NameSpaceMap k a -> k -> a -> (NameSpaceMap k a, Maybe a) defGlobal (NsMap gs lss) ident def = (NsMap (Map.insert ident def gs) lss, Map.lookup ident gs) -- | Enter new local scope -- -- @ns' = enterNewScope ns@ creates and enters a new local scope. enterNewScope :: (Ord k) => NameSpaceMap k a -> NameSpaceMap k a enterNewScope (NsMap gs lss) = NsMap gs ([]:lss) -- | Leave innermost local scope -- -- @(ns',defs) = leaveScope ns@ pops leaves the innermost local scope. -- and returns its definitions leaveScope :: (Ord k) => NameSpaceMap k a -> (NameSpaceMap k a, [(k, a)]) leaveScope (NsMap _ []) = error "NsMaps.leaveScope: No local scope!" leaveScope (NsMap gs (ls:lss)) = (NsMap gs lss, ls) -- | Add local definition -- -- @(ns',oldDef) = defLocal ns ident def@ adds the local definition -- @ident := def@ to the innermost local scope, if there is a local scope, -- and to the global scope otherwise. -- It returns the modified name space @ns'@ and the old binding of -- the identifier @oldDef@, which is overwritten. defLocal :: (Ord k) => NameSpaceMap k a -> k -> a -> (NameSpaceMap k a, Maybe a) defLocal ns@(NsMap _ []) ident def = defGlobal ns ident def defLocal (NsMap gs (ls:lss)) ident def = (NsMap gs (((ident, def):ls):lss), Prelude.lookup ident ls) -- | Search for a definition -- -- @def = find ns ident@ returns the definition in some scope (inner to outer), -- if there is one. lookupName :: (Ord k) => NameSpaceMap k a -> k -> Maybe a lookupName ns@(NsMap _ localDefs) ident = case (lookupLocal localDefs) of Nothing -> lookupGlobal ns ident Just def -> Just def where lookupLocal [] = Nothing lookupLocal (ls:lss) = case (Prelude.lookup ident ls) of Nothing -> lookupLocal lss Just def -> Just def lookupGlobal :: (Ord k) => NameSpaceMap k a -> k -> Maybe a lookupGlobal (NsMap gs _) ident = Map.lookup ident gs lookupInnermostScope :: (Ord k) => NameSpaceMap k a -> k -> Maybe a lookupInnermostScope nsm@(NsMap _gs localDefs) ident = case localDefs of (ls : _lss) -> Prelude.lookup ident ls [] -> lookupGlobal nsm ident -- | flatten a namespace into a assoc list -- -- @nameSpaceToList ns = (localDefInnermost ns ++ .. ++ localDefsOutermost ns) ++ globalDefs ns@ nsMapToList :: (Ord k) => NameSpaceMap k a -> [(k, a)] nsMapToList (NsMap gs lss) = concat lss ++ Map.toList gs -- | Merge two namespaces. If they disagree on the types of any -- variables, all bets are off. mergeNameSpace :: (Ord k) => NameSpaceMap k a -> NameSpaceMap k a -> NameSpaceMap k a mergeNameSpace (NsMap global1 local1) (NsMap global2 local2) = NsMap (Map.union global1 global2) (localUnion local1 local2) where localUnion (l1:ls1) (l2:ls2) = List.unionBy (\p1 p2 -> fst p1 == fst p2) l1 l2 : localUnion ls1 ls2 localUnion [] ls2 = ls2 localUnion ls1 [] = ls1