    -----------------------------------------------------------------------------
    -- |
    -- 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)

    {-
    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 :: forall k v. Ord k => NameSpaceMap k v -> Map k v
    globalNames (NsMap Map k v
    g [[(k, v)]]
    _) = Map k v
    g
    hasLocalNames :: NameSpaceMap k v -> Bool
    hasLocalNames :: forall k v. NameSpaceMap k v -> Bool
    hasLocalNames (NsMap Map k v
    _ [[(k, v)]]
    l) = Bool -> Bool
    not ([[(k, v)]] -> Bool
    forall a. [a] -> Bool
    forall (t :: * -> *) a. Foldable t => t a -> Bool
    null [[(k, v)]]
    l)
    localNames :: (Ord k) => NameSpaceMap k v -> [[(k,v)]]
    localNames :: forall k v. Ord k => NameSpaceMap k v -> [[(k, v)]]
    localNames (NsMap Map k v
    _ [[(k, v)]]
    l) = [[(k, v)]]
    l

    -- | create a name space
    nameSpaceMap :: (Ord k) => NameSpaceMap k v
    nameSpaceMap :: forall k v. Ord k => NameSpaceMap k v
    nameSpaceMap  = Map k v -> [[(k, v)]] -> NameSpaceMap k v
    forall k v. Map k v -> [[(k, v)]] -> NameSpaceMap k v
    NsMap Map k v
    forall k a. Map k a
    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 :: forall k a.
    Ord k =>
    NameSpaceMap k a -> k -> a -> (NameSpaceMap k a, Maybe a)
    defGlobal (NsMap Map k a
    gs [[(k, a)]]
    lss) k
    ident a
    def
        = (Map k a -> [[(k, a)]] -> NameSpaceMap k a
    forall k v. Map k v -> [[(k, v)]] -> NameSpaceMap k v
    NsMap (k -> a -> Map k a -> Map k a
    forall k a. Ord k => k -> a -> Map k a -> Map k a
    Map.insert k
    ident a
    def Map k a
    gs) [[(k, a)]]
    lss, k -> Map k a -> Maybe a
    forall k a. Ord k => k -> Map k a -> Maybe a
    Map.lookup k
    ident Map k a
    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 :: forall k a. Ord k => NameSpaceMap k a -> NameSpaceMap k a
    enterNewScope (NsMap Map k a
    gs [[(k, a)]]
    lss)  = Map k a -> [[(k, a)]] -> NameSpaceMap k a
    forall k v. Map k v -> [[(k, v)]] -> NameSpaceMap k v
    NsMap Map k a
    gs ([][(k, a)] -> [[(k, a)]] -> [[(k, a)]]
    forall a. a -> [a] -> [a]
    :[[(k, a)]]
    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 :: forall k a.
    Ord k =>
    NameSpaceMap k a -> (NameSpaceMap k a, [(k, a)])
    leaveScope (NsMap Map k a
    _ [])         = [Char] -> (NameSpaceMap k a, [(k, a)])
    forall a. HasCallStack => [Char] -> a
    error [Char]
    "NsMaps.leaveScope: No local scope!"
    leaveScope (NsMap Map k a
    gs ([(k, a)]
    ls:[[(k, a)]]
    lss))  = (Map k a -> [[(k, a)]] -> NameSpaceMap k a
    forall k v. Map k v -> [[(k, v)]] -> NameSpaceMap k v
    NsMap Map k a
    gs [[(k, a)]]
    lss, [(k, a)]
    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 :: forall k a.
    Ord k =>
    NameSpaceMap k a -> k -> a -> (NameSpaceMap k a, Maybe a)
    defLocal ns :: NameSpaceMap k a
    ns@(NsMap Map k a
    _ []) k
    ident a
    def = NameSpaceMap k a -> k -> a -> (NameSpaceMap k a, Maybe a)
    forall k a.
    Ord k =>
    NameSpaceMap k a -> k -> a -> (NameSpaceMap k a, Maybe a)
    defGlobal NameSpaceMap k a
    ns k
    ident a
    def
    defLocal (NsMap    Map k a
    gs ([(k, a)]
    ls:[[(k, a)]]
    lss)) k
    ident a
    def =
      (Map k a -> [[(k, a)]] -> NameSpaceMap k a
    forall k v. Map k v -> [[(k, v)]] -> NameSpaceMap k v
    NsMap Map k a
    gs (((k
    ident, a
    def)(k, a) -> [(k, a)] -> [(k, a)]
    forall a. a -> [a] -> [a]
    :[(k, a)]
    ls)[(k, a)] -> [[(k, a)]] -> [[(k, a)]]
    forall a. a -> [a] -> [a]
    :[[(k, a)]]
    lss),
       k -> [(k, a)] -> Maybe a
    forall a b. Eq a => a -> [(a, b)] -> Maybe b
    Prelude.lookup k
    ident [(k, a)]
    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 :: forall k a. Ord k => NameSpaceMap k a -> k -> Maybe a
    lookupName ns :: NameSpaceMap k a
    ns@(NsMap Map k a
    _ [[(k, a)]]
    localDefs) k
    ident
        = case [[(k, a)]] -> Maybe a
    forall {a}. [[(k, a)]] -> Maybe a
    lookupLocal [[(k, a)]]
    localDefs of
            Maybe a
    Nothing  -> NameSpaceMap k a -> k -> Maybe a
    forall k a. Ord k => NameSpaceMap k a -> k -> Maybe a
    lookupGlobal NameSpaceMap k a
    ns k
    ident
            Just a
    def -> a -> Maybe a
    forall a. a -> Maybe a
    Just a
    def
      where
        lookupLocal :: [[(k, a)]] -> Maybe a
    lookupLocal []       = Maybe a
    forall a. Maybe a
    Nothing
        lookupLocal ([(k, a)]
    ls:[[(k, a)]]
    lss) =
          case k -> [(k, a)] -> Maybe a
    forall a b. Eq a => a -> [(a, b)] -> Maybe b
    Prelude.lookup k
    ident [(k, a)]
    ls of
            Maybe a
    Nothing  -> [[(k, a)]] -> Maybe a
    lookupLocal [[(k, a)]]
    lss
            Just a
    def -> a -> Maybe a
    forall a. a -> Maybe a
    Just a
    def

    lookupGlobal :: (Ord k) => NameSpaceMap k a -> k -> Maybe a
    lookupGlobal :: forall k a. Ord k => NameSpaceMap k a -> k -> Maybe a
    lookupGlobal (NsMap Map k a
    gs [[(k, a)]]
    _) k
    ident = k -> Map k a -> Maybe a
    forall k a. Ord k => k -> Map k a -> Maybe a
    Map.lookup k
    ident Map k a
    gs

    lookupInnermostScope :: (Ord k) => NameSpaceMap k a -> k -> Maybe a
    lookupInnermostScope :: forall k a. Ord k => NameSpaceMap k a -> k -> Maybe a
    lookupInnermostScope nsm :: NameSpaceMap k a
    nsm@(NsMap Map k a
    _gs [[(k, a)]]
    localDefs) k
    ident  =
        case [[(k, a)]]
    localDefs of
            ([(k, a)]
    ls : [[(k, a)]]
    _lss) -> k -> [(k, a)] -> Maybe a
    forall a b. Eq a => a -> [(a, b)] -> Maybe b
    Prelude.lookup k
    ident [(k, a)]
    ls
            [] -> NameSpaceMap k a -> k -> Maybe a
    forall k a. Ord k => NameSpaceMap k a -> k -> Maybe a
    lookupGlobal NameSpaceMap k a
    nsm k
    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 :: forall k a. Ord k => NameSpaceMap k a -> [(k, a)]
    nsMapToList (NsMap Map k a
    gs [[(k, a)]]
    lss)  = [[(k, a)]] -> [(k, a)]
    forall (t :: * -> *) a. Foldable t => t [a] -> [a]
    concat [[(k, a)]]
    lss [(k, a)] -> [(k, a)] -> [(k, a)]
    forall a. [a] -> [a] -> [a]
    ++ Map k a -> [(k, a)]
    forall k a. Map k a -> [(k, a)]
    Map.toList Map k a
    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 :: forall k a.
    Ord k =>
    NameSpaceMap k a -> NameSpaceMap k a -> NameSpaceMap k a
    mergeNameSpace (NsMap Map k a
    global1 [[(k, a)]]
    local1) (NsMap Map k a
    global2 [[(k, a)]]
    local2) =
      Map k a -> [[(k, a)]] -> NameSpaceMap k a
    forall k v. Map k v -> [[(k, v)]] -> NameSpaceMap k v
    NsMap (Map k a -> Map k a -> Map k a
    forall k a. Ord k => Map k a -> Map k a -> Map k a
    Map.union Map k a
    global1 Map k a
    global2) ([[(k, a)]] -> [[(k, a)]] -> [[(k, a)]]
    forall {a} {b}. Eq a => [[(a, b)]] -> [[(a, b)]] -> [[(a, b)]]
    localUnion [[(k, a)]]
    local1 [[(k, a)]]
    local2)
      where localUnion :: [[(a, b)]] -> [[(a, b)]] -> [[(a, b)]]
    localUnion ([(a, b)]
    l1:[[(a, b)]]
    ls1) ([(a, b)]
    l2:[[(a, b)]]
    ls2) =
              ((a, b) -> (a, b) -> Bool) -> [(a, b)] -> [(a, b)] -> [(a, b)]
    forall a. (a -> a -> Bool) -> [a] -> [a] -> [a]
    List.unionBy (\(a, b)
    p1 (a, b)
    p2 -> (a, b) -> a
    forall a b. (a, b) -> a
    fst (a, b)
    p1 a -> a -> Bool
    forall a. Eq a => a -> a -> Bool
    == (a, b) -> a
    forall a b. (a, b) -> a
    fst (a, b)
    p2) [(a, b)]
    l1 [(a, b)]
    l2 [(a, b)] -> [[(a, b)]] -> [[(a, b)]]
    forall a. a -> [a] -> [a]
    : [[(a, b)]] -> [[(a, b)]] -> [[(a, b)]]
    localUnion [[(a, b)]]
    ls1 [[(a, b)]]
    ls2
            localUnion [] [[(a, b)]]
    ls2 = [[(a, b)]]
    ls2
            localUnion [[(a, b)]]
    ls1 [] = [[(a, b)]]
    ls1