--  Compiler Toolkit: name space management
--
--  Author : Manuel M. T. Chakravarty
--  Created: 12 November 95
--
--  Adapted by Stefan Wehr, May 2005
--
--  Version $Revision: 1.8 $ from $Date: 1999/10/24 14:36:52 $
--
--  Copyright (c) [1995..1999] Manuel M. T. Chakravarty
--
--  This file is free software; you can redistribute it and/or modify
--  it under the terms of the GNU General Public License as published by
--  the Free Software Foundation; either version 2 of the License, or
--  (at your option) any later version.
--
--  This file is distributed in the hope that it will be useful,
--  but WITHOUT ANY WARRANTY; without even the implied warranty of
--  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
--  GNU General Public License for more details.
--
--- DESCRIPTION ---------------------------------------------------------------
--
--  This module manages name spaces.
--
--- DOCU ----------------------------------------------------------------------
--
--  language: Haskell 98
--
--  * A name space associates identifiers with their definition.
--
--  * Each name space is organized in a hierarchical way using the notion of
--    ranges. A name space, at any moment, always has a global range and may
--    have several local ranges. Definitions in inner ranges hide definitions
--    of the same identifiert in outer ranges.
--
--- TODO ----------------------------------------------------------------------
--
--  * evaluate the performance gain that a hashtable would bring
--

module Phrac.NameSpaces (NameSpace, nameSpace, defGlobal, enterNewRange, leaveRange,
		         defLocal, find, findGlobal, nameSpaceToList)
where

import qualified Phrac.Map as Map
import Phrac.Error
import Phrac.Pretty


-- name space (EXPORTED ABSTRACT)
--
-- * the definitions in the global ranges are stored in a finite map, because
--   they tend to be a lot and are normally not updated after the global range
--   is constructed
--
-- * the definitions of the local ranges 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 ranges; adding new definitions
--   is done in time proportinal to the current size of the range; removing a
--   range is done in constant time (and the definitions of a range can be
--   returned as a result of leaving the range); lookup is proportional to the
--   number of definitions in the local ranges and the logarithm of the number
--   of definitions in the global range---i.e., efficiency relies on a
--   relatively low number of local definitions together with frequent lookup
--   of the most recently defined local identifiers
--
data NameSpace k v = NameSpace (Map.Map k v)    -- defs in global range
			        [[(k, v)]]      -- stack of local ranges

-- create a name space (EXPORTED)
--
nameSpace :: NameSpace k v
nameSpace  = NameSpace Map.empty []

-- add global definition (EXPORTED)
--
-- * returns the modfied name space 
--
-- * if the identfier is already declared, the resulting name space contains
--   the new binding and the second component of the result contains the
--   definition declared previosuly (which is henceforth not contained in the
--   name space anymore)
--
defGlobal :: Ord k => k -> v -> NameSpace k v -> (Maybe v, NameSpace k v)
defGlobal id def (NameSpace gs lss)  = (Map.lookup id gs,
                                        NameSpace (Map.insert id def gs) lss)

-- add new range (EXPORTED)
--
enterNewRange			 :: NameSpace k v -> NameSpace k v
enterNewRange (NameSpace gs lss)  = NameSpace gs ([]:lss)

-- pop topmost range and return its definitions (EXPORTED)
--
leaveRange :: NameSpace k v -> (NameSpace k v, [(k, v)])
leaveRange (NameSpace gs [])        = 
    panic "leaveRange called, but no local range exists"
leaveRange (NameSpace gs (ls:lss))  = (NameSpace gs lss, ls)

-- add local definition (EXPORTED)
--
-- * returns the modfied name space 
--
-- * if there is no local range, the definition is entered globally
--
-- * if the identfier is already declared, the resulting name space contains
--   the new binding and the second component of the result contains the
--   definition declared previosuly (which is henceforth not contained in the
--   name space anymore)
--
defLocal :: Ord k => k -> v -> NameSpace k v -> (Maybe v, NameSpace k v)
defLocal id def ns@(NameSpace gs []) = defGlobal id def ns
defLocal id def (NameSpace gs (ls:lss)) = 
  (lookup ls,
   NameSpace gs (((id, def):ls):lss))
  where
    lookup []                          = Nothing
    lookup ((id', def):ls) | id == id' = Just def
                           | otherwise = lookup ls


-- search for a definition (EXPORTED)
--
-- * the definition from the innermost range is returned, if any
--
find :: (Ord k) => k -> NameSpace k v -> Maybe v
find id (NameSpace gs lss) = case (lookup lss) of
			        Nothing  -> Map.lookup id gs
			        Just def -> Just def
			      where
			        lookup []       = Nothing
			        lookup (ls:lss) = case (lookup' ls) of
						    Nothing  -> lookup lss
						    Just def -> Just def

				lookup' []              = Nothing
				lookup' ((id', def):ls)
				        | id' == id     = Just def
				        | otherwise     = lookup' ls

findGlobal :: (Ord k) => k -> NameSpace k v -> Maybe v
findGlobal id (NameSpace gs lss) = Map.lookup id gs

-- dump a name space into a list (EXPORTED)
--
-- * local ranges are concatenated
--
nameSpaceToList                    :: NameSpace k v -> [(k, v)]
nameSpaceToList (NameSpace gs lss)  = Map.toList gs ++ concat lss