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