1
-- Compiler Toolkit: name space management
3
-- Author : Manuel M. T. Chakravarty
4
-- Created: 12 November 95
6
-- Version $Revision: 1.2 $ from $Date: 2004/11/13 17:26:50 $
8
-- Copyright (c) [1995..1999] Manuel M. T. Chakravarty
10
-- This file is free software; you can redistribute it and/or modify
11
-- it under the terms of the GNU General Public License as published by
12
-- the Free Software Foundation; either version 2 of the License, or
13
-- (at your option) any later version.
15
-- This file is distributed in the hope that it will be useful,
16
-- but WITHOUT ANY WARRANTY; without even the implied warranty of
17
-- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18
-- GNU General Public License for more details.
20
--- DESCRIPTION ---------------------------------------------------------------
22
-- This module manages name spaces.
24
--- DOCU ----------------------------------------------------------------------
26
-- language: Haskell 98
28
-- * A name space associates identifiers with their definition.
30
-- * Each name space is organized in a hierarchical way using the notion of
31
-- ranges. A name space, at any moment, always has a global range and may
32
-- have several local ranges. Definitions in inner ranges hide definitions
33
-- of the same identifiert in outer ranges.
35
--- TODO ----------------------------------------------------------------------
37
-- * evaluate the performance gain that a hashtable would bring
40
module NameSpaces (NameSpace, nameSpace, defGlobal, enterNewRange, leaveRange,
41
defLocal, find, nameSpaceToList)
44
import Common (Position, Pos(posOf)) -- for importing `Idents'
45
import Data.FiniteMap (FiniteMap, emptyFM, addToFM, lookupFM, fmToList, listToFM)
47
import Errors (interr)
48
import Binary (Binary(..))
51
-- name space (EXPORTED ABSTRACT)
53
-- * the definitions in the global ranges are stored in a finite map, because
54
-- they tend to be a lot and are normally not updated after the global range
57
-- * the definitions of the local ranges are stored in a single list, usually
58
-- they are not very many and the definitions entered last are the most
59
-- frequently accessed ones; the list structure naturally hides older
60
-- definitions, i.e., definitions from outer ranges; adding new definitions
61
-- is done in time proportinal to the current size of the range; removing a
62
-- range is done in constant time (and the definitions of a range can be
63
-- returned as a result of leaving the range); lookup is proportional to the
64
-- number of definitions in the local ranges and the logarithm of the number
65
-- of definitions in the global range---i.e., efficiency relies on a
66
-- relatively low number of local definitions together with frequent lookup
67
-- of the most recently defined local identifiers
69
data NameSpace a = NameSpace (FiniteMap Ident a) -- defs in global range
70
[[(Ident, a)]] -- stack of local ranges
72
-- create a name space (EXPORTED)
74
nameSpace :: NameSpace a
75
nameSpace = NameSpace emptyFM []
77
-- add global definition (EXPORTED)
79
-- * returns the modfied name space
81
-- * if the identfier is already declared, the resulting name space contains
82
-- the new binding and the second component of the result contains the
83
-- definition declared previosuly (which is henceforth not contained in the
84
-- name space anymore)
86
defGlobal :: NameSpace a -> Ident -> a -> (NameSpace a, Maybe a)
87
defGlobal (NameSpace gs lss) id def = (NameSpace (addToFM gs id def) lss,
90
-- add new range (EXPORTED)
92
enterNewRange :: NameSpace a -> NameSpace a
93
enterNewRange (NameSpace gs lss) = NameSpace gs ([]:lss)
95
-- pop topmost range and return its definitions (EXPORTED)
97
leaveRange :: NameSpace a -> (NameSpace a, [(Ident, a)])
98
leaveRange (NameSpace gs []) = interr "NameSpaces.leaveRange: \
100
leaveRange (NameSpace gs (ls:lss)) = (NameSpace gs lss, ls)
102
-- add local definition (EXPORTED)
104
-- * returns the modfied name space
106
-- * if there is no local range, the definition is entered globally
108
-- * if the identfier is already declared, the resulting name space contains
109
-- the new binding and the second component of the result contains the
110
-- definition declared previosuly (which is henceforth not contained in the
111
-- name space anymore)
113
defLocal :: NameSpace a -> Ident -> a -> (NameSpace a, Maybe a)
114
defLocal ns@(NameSpace gs [] ) id def = defGlobal ns id def
115
defLocal (NameSpace gs (ls:lss)) id def =
116
(NameSpace gs (((id, def):ls):lss),
120
lookup ((id', def):ls) | id == id' = Just def
121
| otherwise = lookup ls
123
-- search for a definition (EXPORTED)
125
-- * the definition from the innermost range is returned, if any
127
find :: NameSpace a -> Ident -> Maybe a
128
find (NameSpace gs lss) id = case (lookup lss) of
129
Nothing -> lookupFM gs id
133
lookup (ls:lss) = case (lookup' ls) of
134
Nothing -> lookup lss
138
lookup' ((id', def):ls)
139
| id' == id = Just def
140
| otherwise = lookup' ls
142
-- dump a name space into a list (EXPORTED)
144
-- * local ranges are concatenated
146
nameSpaceToList :: NameSpace a -> [(Ident, a)]
147
nameSpaceToList (NameSpace gs lss) = fmToList gs ++ concat lss
150
{-! for NameSpace derive : GhcBinary !-}
151
{-* Generated by DrIFT : Look, but Don't Touch. *-}
152
instance (Binary a) => Binary (NameSpace a) where
153
put_ bh (NameSpace aa ab) = do
159
return (NameSpace aa ab)
added
removed
tools/c2hs/base/syms/NameSpaces.hs
