Expanded abbreviations in Haddock documentation
[ghc.git] / compiler / basicTypes / NameEnv.hs
1 {-
2 (c) The University of Glasgow 2006
3 (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
4
5 \section[NameEnv]{@NameEnv@: name environments}
6 -}
7
8 {-# LANGUAGE CPP #-}
9 module NameEnv (
10 -- * Var, Id and TyVar environments (maps)
11 NameEnv,
12
13 -- ** Manipulating these environments
14 mkNameEnv,
15 emptyNameEnv, isEmptyNameEnv,
16 unitNameEnv, nameEnvElts,
17 extendNameEnv_C, extendNameEnv_Acc, extendNameEnv,
18 extendNameEnvList, extendNameEnvList_C,
19 filterNameEnv, anyNameEnv,
20 plusNameEnv, plusNameEnv_C, alterNameEnv,
21 lookupNameEnv, lookupNameEnv_NF, delFromNameEnv, delListFromNameEnv,
22 elemNameEnv, mapNameEnv, disjointNameEnv,
23
24 DNameEnv,
25
26 emptyDNameEnv,
27 lookupDNameEnv,
28 mapDNameEnv,
29 alterDNameEnv,
30 -- ** Dependency analysis
31 depAnal
32 ) where
33
34 #include "HsVersions.h"
35
36 import Digraph
37 import Name
38 import UniqFM
39 import UniqDFM
40 import Maybes
41
42 {-
43 ************************************************************************
44 * *
45 \subsection{Name environment}
46 * *
47 ************************************************************************
48 -}
49
50 {-
51 Note [depAnal determinism]
52 ~~~~~~~~~~~~~~~~~~~~~~~~~~
53 depAnal is deterministic provided it gets the nodes in a deterministic order.
54 The order of lists that get_defs and get_uses return doesn't matter, as these
55 are only used to construct the edges, and stronglyConnCompFromEdgedVertices is
56 deterministic even when the edges are not in deterministic order as explained
57 in Note [Deterministic SCC] in Digraph.
58 -}
59
60 depAnal :: (node -> [Name]) -- Defs
61 -> (node -> [Name]) -- Uses
62 -> [node]
63 -> [SCC node]
64 -- Peform dependency analysis on a group of definitions,
65 -- where each definition may define more than one Name
66 --
67 -- The get_defs and get_uses functions are called only once per node
68 depAnal get_defs get_uses nodes
69 = stronglyConnCompFromEdgedVerticesUniq (map mk_node keyed_nodes)
70 where
71 keyed_nodes = nodes `zip` [(1::Int)..]
72 mk_node (node, key) = (node, key, mapMaybe (lookupNameEnv key_map) (get_uses node))
73
74 key_map :: NameEnv Int -- Maps a Name to the key of the decl that defines it
75 key_map = mkNameEnv [(name,key) | (node, key) <- keyed_nodes, name <- get_defs node]
76
77 {-
78 ************************************************************************
79 * *
80 \subsection{Name environment}
81 * *
82 ************************************************************************
83 -}
84
85 -- | Name Environment
86 type NameEnv a = UniqFM a -- Domain is Name
87
88 emptyNameEnv :: NameEnv a
89 isEmptyNameEnv :: NameEnv a -> Bool
90 mkNameEnv :: [(Name,a)] -> NameEnv a
91 nameEnvElts :: NameEnv a -> [a]
92 alterNameEnv :: (Maybe a-> Maybe a) -> NameEnv a -> Name -> NameEnv a
93 extendNameEnv_C :: (a->a->a) -> NameEnv a -> Name -> a -> NameEnv a
94 extendNameEnv_Acc :: (a->b->b) -> (a->b) -> NameEnv b -> Name -> a -> NameEnv b
95 extendNameEnv :: NameEnv a -> Name -> a -> NameEnv a
96 plusNameEnv :: NameEnv a -> NameEnv a -> NameEnv a
97 plusNameEnv_C :: (a->a->a) -> NameEnv a -> NameEnv a -> NameEnv a
98 extendNameEnvList :: NameEnv a -> [(Name,a)] -> NameEnv a
99 extendNameEnvList_C :: (a->a->a) -> NameEnv a -> [(Name,a)] -> NameEnv a
100 delFromNameEnv :: NameEnv a -> Name -> NameEnv a
101 delListFromNameEnv :: NameEnv a -> [Name] -> NameEnv a
102 elemNameEnv :: Name -> NameEnv a -> Bool
103 unitNameEnv :: Name -> a -> NameEnv a
104 lookupNameEnv :: NameEnv a -> Name -> Maybe a
105 lookupNameEnv_NF :: NameEnv a -> Name -> a
106 filterNameEnv :: (elt -> Bool) -> NameEnv elt -> NameEnv elt
107 anyNameEnv :: (elt -> Bool) -> NameEnv elt -> Bool
108 mapNameEnv :: (elt1 -> elt2) -> NameEnv elt1 -> NameEnv elt2
109 disjointNameEnv :: NameEnv a -> NameEnv a -> Bool
110
111 nameEnvElts x = eltsUFM x
112 emptyNameEnv = emptyUFM
113 isEmptyNameEnv = isNullUFM
114 unitNameEnv x y = unitUFM x y
115 extendNameEnv x y z = addToUFM x y z
116 extendNameEnvList x l = addListToUFM x l
117 lookupNameEnv x y = lookupUFM x y
118 alterNameEnv = alterUFM
119 mkNameEnv l = listToUFM l
120 elemNameEnv x y = elemUFM x y
121 plusNameEnv x y = plusUFM x y
122 plusNameEnv_C f x y = plusUFM_C f x y
123 extendNameEnv_C f x y z = addToUFM_C f x y z
124 mapNameEnv f x = mapUFM f x
125 extendNameEnv_Acc x y z a b = addToUFM_Acc x y z a b
126 extendNameEnvList_C x y z = addListToUFM_C x y z
127 delFromNameEnv x y = delFromUFM x y
128 delListFromNameEnv x y = delListFromUFM x y
129 filterNameEnv x y = filterUFM x y
130 anyNameEnv f x = foldUFM ((||) . f) False x
131 disjointNameEnv x y = isNullUFM (intersectUFM x y)
132
133 lookupNameEnv_NF env n = expectJust "lookupNameEnv_NF" (lookupNameEnv env n)
134
135 -- | Deterministic Name Environment
136 --
137 -- See Note [Deterministic UniqFM] in UniqDFM for explanation why we need
138 -- DNameEnv.
139 type DNameEnv a = UniqDFM a
140
141 emptyDNameEnv :: DNameEnv a
142 emptyDNameEnv = emptyUDFM
143
144 lookupDNameEnv :: DNameEnv a -> Name -> Maybe a
145 lookupDNameEnv = lookupUDFM
146
147 mapDNameEnv :: (a -> b) -> DNameEnv a -> DNameEnv b
148 mapDNameEnv = mapUDFM
149
150 alterDNameEnv :: (Maybe a -> Maybe a) -> DNameEnv a -> Name -> DNameEnv a
151 alterDNameEnv = alterUDFM