compiler: introduce custom "GhcPrelude" Prelude
[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 GhcPrelude
37
38 import Digraph
39 import Name
40 import UniqFM
41 import UniqDFM
42 import Maybes
43
44 {-
45 ************************************************************************
46 * *
47 \subsection{Name environment}
48 * *
49 ************************************************************************
50 -}
51
52 {-
53 Note [depAnal determinism]
54 ~~~~~~~~~~~~~~~~~~~~~~~~~~
55 depAnal is deterministic provided it gets the nodes in a deterministic order.
56 The order of lists that get_defs and get_uses return doesn't matter, as these
57 are only used to construct the edges, and stronglyConnCompFromEdgedVertices is
58 deterministic even when the edges are not in deterministic order as explained
59 in Note [Deterministic SCC] in Digraph.
60 -}
61
62 depAnal :: (node -> [Name]) -- Defs
63 -> (node -> [Name]) -- Uses
64 -> [node]
65 -> [SCC node]
66 -- Perform dependency analysis on a group of definitions,
67 -- where each definition may define more than one Name
68 --
69 -- The get_defs and get_uses functions are called only once per node
70 depAnal get_defs get_uses nodes
71 = stronglyConnCompFromEdgedVerticesUniq (map mk_node keyed_nodes)
72 where
73 keyed_nodes = nodes `zip` [(1::Int)..]
74 mk_node (node, key) =
75 DigraphNode node key (mapMaybe (lookupNameEnv key_map) (get_uses node))
76
77 key_map :: NameEnv Int -- Maps a Name to the key of the decl that defines it
78 key_map = mkNameEnv [(name,key) | (node, key) <- keyed_nodes, name <- get_defs node]
79
80 {-
81 ************************************************************************
82 * *
83 \subsection{Name environment}
84 * *
85 ************************************************************************
86 -}
87
88 -- | Name Environment
89 type NameEnv a = UniqFM a -- Domain is Name
90
91 emptyNameEnv :: NameEnv a
92 isEmptyNameEnv :: NameEnv a -> Bool
93 mkNameEnv :: [(Name,a)] -> NameEnv a
94 nameEnvElts :: NameEnv a -> [a]
95 alterNameEnv :: (Maybe a-> Maybe a) -> NameEnv a -> Name -> NameEnv a
96 extendNameEnv_C :: (a->a->a) -> NameEnv a -> Name -> a -> NameEnv a
97 extendNameEnv_Acc :: (a->b->b) -> (a->b) -> NameEnv b -> Name -> a -> NameEnv b
98 extendNameEnv :: NameEnv a -> Name -> a -> NameEnv a
99 plusNameEnv :: NameEnv a -> NameEnv a -> NameEnv a
100 plusNameEnv_C :: (a->a->a) -> NameEnv a -> NameEnv a -> NameEnv a
101 extendNameEnvList :: NameEnv a -> [(Name,a)] -> NameEnv a
102 extendNameEnvList_C :: (a->a->a) -> NameEnv a -> [(Name,a)] -> NameEnv a
103 delFromNameEnv :: NameEnv a -> Name -> NameEnv a
104 delListFromNameEnv :: NameEnv a -> [Name] -> NameEnv a
105 elemNameEnv :: Name -> NameEnv a -> Bool
106 unitNameEnv :: Name -> a -> NameEnv a
107 lookupNameEnv :: NameEnv a -> Name -> Maybe a
108 lookupNameEnv_NF :: NameEnv a -> Name -> a
109 filterNameEnv :: (elt -> Bool) -> NameEnv elt -> NameEnv elt
110 anyNameEnv :: (elt -> Bool) -> NameEnv elt -> Bool
111 mapNameEnv :: (elt1 -> elt2) -> NameEnv elt1 -> NameEnv elt2
112 disjointNameEnv :: NameEnv a -> NameEnv a -> Bool
113
114 nameEnvElts x = eltsUFM x
115 emptyNameEnv = emptyUFM
116 isEmptyNameEnv = isNullUFM
117 unitNameEnv x y = unitUFM x y
118 extendNameEnv x y z = addToUFM x y z
119 extendNameEnvList x l = addListToUFM x l
120 lookupNameEnv x y = lookupUFM x y
121 alterNameEnv = alterUFM
122 mkNameEnv l = listToUFM l
123 elemNameEnv x y = elemUFM x y
124 plusNameEnv x y = plusUFM x y
125 plusNameEnv_C f x y = plusUFM_C f x y
126 extendNameEnv_C f x y z = addToUFM_C f x y z
127 mapNameEnv f x = mapUFM f x
128 extendNameEnv_Acc x y z a b = addToUFM_Acc x y z a b
129 extendNameEnvList_C x y z = addListToUFM_C x y z
130 delFromNameEnv x y = delFromUFM x y
131 delListFromNameEnv x y = delListFromUFM x y
132 filterNameEnv x y = filterUFM x y
133 anyNameEnv f x = foldUFM ((||) . f) False x
134 disjointNameEnv x y = isNullUFM (intersectUFM x y)
135
136 lookupNameEnv_NF env n = expectJust "lookupNameEnv_NF" (lookupNameEnv env n)
137
138 -- | Deterministic Name Environment
139 --
140 -- See Note [Deterministic UniqFM] in UniqDFM for explanation why we need
141 -- DNameEnv.
142 type DNameEnv a = UniqDFM a
143
144 emptyDNameEnv :: DNameEnv a
145 emptyDNameEnv = emptyUDFM
146
147 lookupDNameEnv :: DNameEnv a -> Name -> Maybe a
148 lookupDNameEnv = lookupUDFM
149
150 mapDNameEnv :: (a -> b) -> DNameEnv a -> DNameEnv b
151 mapDNameEnv = mapUDFM
152
153 alterDNameEnv :: (Maybe a -> Maybe a) -> DNameEnv a -> Name -> DNameEnv a
154 alterDNameEnv = alterUDFM