4663a41a5bd6eb4f461606bbcfb2ec39e72c2cad
[ghc.git] / compiler / basicTypes / VarSet.hs
1 {-
2 (c) The University of Glasgow 2006
3 (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
4 -}
5
6 {-# LANGUAGE CPP #-}
7
8 module VarSet (
9 -- * Var, Id and TyVar set types
10 VarSet, IdSet, TyVarSet, CoVarSet, TyCoVarSet,
11
12 -- ** Manipulating these sets
13 emptyVarSet, unitVarSet, mkVarSet,
14 extendVarSet, extendVarSetList, extendVarSet_C,
15 elemVarSet, varSetElems, subVarSet,
16 unionVarSet, unionVarSets, mapUnionVarSet,
17 intersectVarSet, intersectsVarSet, disjointVarSet,
18 isEmptyVarSet, delVarSet, delVarSetList, delVarSetByKey,
19 minusVarSet, filterVarSet,
20 varSetAny, varSetAll,
21 transCloVarSet, fixVarSet,
22 lookupVarSet, lookupVarSetByName,
23 sizeVarSet, seqVarSet,
24 elemVarSetByKey, partitionVarSet,
25 pluralVarSet, pprVarSet,
26
27 -- * Deterministic Var set types
28 DVarSet, DIdSet, DTyVarSet, DTyCoVarSet,
29
30 -- ** Manipulating these sets
31 emptyDVarSet, unitDVarSet, mkDVarSet,
32 extendDVarSet, extendDVarSetList,
33 elemDVarSet, dVarSetElems, subDVarSet,
34 unionDVarSet, unionDVarSets, mapUnionDVarSet,
35 intersectDVarSet, intersectsDVarSet, disjointDVarSet,
36 isEmptyDVarSet, delDVarSet, delDVarSetList,
37 minusDVarSet, foldDVarSet, filterDVarSet,
38 dVarSetMinusVarSet,
39 transCloDVarSet,
40 sizeDVarSet, seqDVarSet,
41 partitionDVarSet,
42 dVarSetToVarSet,
43 ) where
44
45 #include "HsVersions.h"
46
47 import Var ( Var, TyVar, CoVar, TyCoVar, Id )
48 import Unique
49 import Name ( Name )
50 import UniqSet
51 import UniqDSet
52 import UniqFM( disjointUFM, pluralUFM, pprUFM )
53 import UniqDFM( disjointUDFM, udfmToUfm )
54 import Outputable (SDoc)
55
56 -- | A non-deterministic set of variables.
57 -- See Note [Deterministic UniqFM] in UniqDFM for explanation why it's not
58 -- deterministic and why it matters. Use DVarSet if the set eventually
59 -- gets converted into a list or folded over in a way where the order
60 -- changes the generated code, for example when abstracting variables.
61 type VarSet = UniqSet Var
62 type IdSet = UniqSet Id
63 type TyVarSet = UniqSet TyVar
64 type CoVarSet = UniqSet CoVar
65 type TyCoVarSet = UniqSet TyCoVar
66
67 emptyVarSet :: VarSet
68 intersectVarSet :: VarSet -> VarSet -> VarSet
69 unionVarSet :: VarSet -> VarSet -> VarSet
70 unionVarSets :: [VarSet] -> VarSet
71
72 mapUnionVarSet :: (a -> VarSet) -> [a] -> VarSet
73 -- ^ map the function over the list, and union the results
74
75 varSetElems :: VarSet -> [Var]
76 unitVarSet :: Var -> VarSet
77 extendVarSet :: VarSet -> Var -> VarSet
78 extendVarSetList:: VarSet -> [Var] -> VarSet
79 elemVarSet :: Var -> VarSet -> Bool
80 delVarSet :: VarSet -> Var -> VarSet
81 delVarSetList :: VarSet -> [Var] -> VarSet
82 minusVarSet :: VarSet -> VarSet -> VarSet
83 isEmptyVarSet :: VarSet -> Bool
84 mkVarSet :: [Var] -> VarSet
85 lookupVarSet :: VarSet -> Var -> Maybe Var
86 -- Returns the set element, which may be
87 -- (==) to the argument, but not the same as
88 lookupVarSetByName :: VarSet -> Name -> Maybe Var
89 sizeVarSet :: VarSet -> Int
90 filterVarSet :: (Var -> Bool) -> VarSet -> VarSet
91 extendVarSet_C :: (Var->Var->Var) -> VarSet -> Var -> VarSet
92
93 delVarSetByKey :: VarSet -> Unique -> VarSet
94 elemVarSetByKey :: Unique -> VarSet -> Bool
95 partitionVarSet :: (Var -> Bool) -> VarSet -> (VarSet, VarSet)
96
97 emptyVarSet = emptyUniqSet
98 unitVarSet = unitUniqSet
99 extendVarSet = addOneToUniqSet
100 extendVarSetList= addListToUniqSet
101 intersectVarSet = intersectUniqSets
102
103 intersectsVarSet:: VarSet -> VarSet -> Bool -- True if non-empty intersection
104 disjointVarSet :: VarSet -> VarSet -> Bool -- True if empty intersection
105 subVarSet :: VarSet -> VarSet -> Bool -- True if first arg is subset of second
106 -- (s1 `intersectsVarSet` s2) doesn't compute s2 if s1 is empty;
107 -- ditto disjointVarSet, subVarSet
108
109 unionVarSet = unionUniqSets
110 unionVarSets = unionManyUniqSets
111 varSetElems = uniqSetToList
112 elemVarSet = elementOfUniqSet
113 minusVarSet = minusUniqSet
114 delVarSet = delOneFromUniqSet
115 delVarSetList = delListFromUniqSet
116 isEmptyVarSet = isEmptyUniqSet
117 mkVarSet = mkUniqSet
118 lookupVarSet = lookupUniqSet
119 lookupVarSetByName = lookupUniqSet
120 sizeVarSet = sizeUniqSet
121 filterVarSet = filterUniqSet
122 extendVarSet_C = addOneToUniqSet_C
123 delVarSetByKey = delOneFromUniqSet_Directly
124 elemVarSetByKey = elemUniqSet_Directly
125 partitionVarSet = partitionUniqSet
126
127 mapUnionVarSet get_set xs = foldr (unionVarSet . get_set) emptyVarSet xs
128
129 -- See comments with type signatures
130 intersectsVarSet s1 s2 = not (s1 `disjointVarSet` s2)
131 disjointVarSet s1 s2 = disjointUFM s1 s2
132 subVarSet s1 s2 = isEmptyVarSet (s1 `minusVarSet` s2)
133
134 varSetAny :: (Var -> Bool) -> VarSet -> Bool
135 varSetAny = uniqSetAny
136
137 varSetAll :: (Var -> Bool) -> VarSet -> Bool
138 varSetAll = uniqSetAll
139
140 -- There used to exist mapVarSet, see Note [Unsound mapUniqSet] in UniqSet for
141 -- why it got removed.
142
143 fixVarSet :: (VarSet -> VarSet) -- Map the current set to a new set
144 -> VarSet -> VarSet
145 -- (fixVarSet f s) repeatedly applies f to the set s,
146 -- until it reaches a fixed point.
147 fixVarSet fn vars
148 | new_vars `subVarSet` vars = vars
149 | otherwise = fixVarSet fn new_vars
150 where
151 new_vars = fn vars
152
153 transCloVarSet :: (VarSet -> VarSet)
154 -- Map some variables in the set to
155 -- extra variables that should be in it
156 -> VarSet -> VarSet
157 -- (transCloVarSet f s) repeatedly applies f to new candidates, adding any
158 -- new variables to s that it finds thereby, until it reaches a fixed point.
159 --
160 -- The function fn could be (Var -> VarSet), but we use (VarSet -> VarSet)
161 -- for efficiency, so that the test can be batched up.
162 -- It's essential that fn will work fine if given new candidates
163 -- one at at time; ie fn {v1,v2} = fn v1 `union` fn v2
164 -- Use fixVarSet if the function needs to see the whole set all at once
165 transCloVarSet fn seeds
166 = go seeds seeds
167 where
168 go :: VarSet -- Accumulating result
169 -> VarSet -- Work-list; un-processed subset of accumulating result
170 -> VarSet
171 -- Specification: go acc vs = acc `union` transClo fn vs
172
173 go acc candidates
174 | isEmptyVarSet new_vs = acc
175 | otherwise = go (acc `unionVarSet` new_vs) new_vs
176 where
177 new_vs = fn candidates `minusVarSet` acc
178
179 seqVarSet :: VarSet -> ()
180 seqVarSet s = sizeVarSet s `seq` ()
181
182 -- | Determines the pluralisation suffix appropriate for the length of a set
183 -- in the same way that plural from Outputable does for lists.
184 pluralVarSet :: VarSet -> SDoc
185 pluralVarSet = pluralUFM
186
187 -- | Pretty-print a non-deterministic set.
188 -- The order of variables is non-deterministic and for pretty-printing that
189 -- shouldn't be a problem.
190 -- Having this function helps contain the non-determinism created with
191 -- varSetElems.
192 -- Passing a list to the pretty-printing function allows the caller
193 -- to decide on the order of Vars (eg. toposort them) without them having
194 -- to use varSetElems at the call site. This prevents from let-binding
195 -- non-deterministically ordered lists and reusing them where determinism
196 -- matters.
197 pprVarSet :: VarSet -- ^ The things to be pretty printed
198 -> ([Var] -> SDoc) -- ^ The pretty printing function to use on the
199 -- elements
200 -> SDoc -- ^ 'SDoc' where the things have been pretty
201 -- printed
202 pprVarSet = pprUFM
203
204 -- Deterministic VarSet
205 -- See Note [Deterministic UniqFM] in UniqDFM for explanation why we need
206 -- DVarSet.
207
208 type DVarSet = UniqDSet Var
209 type DIdSet = UniqDSet Id
210 type DTyVarSet = UniqDSet TyVar
211 type DTyCoVarSet = UniqDSet TyCoVar
212
213 emptyDVarSet :: DVarSet
214 emptyDVarSet = emptyUniqDSet
215
216 unitDVarSet :: Var -> DVarSet
217 unitDVarSet = unitUniqDSet
218
219 mkDVarSet :: [Var] -> DVarSet
220 mkDVarSet = mkUniqDSet
221
222 extendDVarSet :: DVarSet -> Var -> DVarSet
223 extendDVarSet = addOneToUniqDSet
224
225 elemDVarSet :: Var -> DVarSet -> Bool
226 elemDVarSet = elementOfUniqDSet
227
228 dVarSetElems :: DVarSet -> [Var]
229 dVarSetElems = uniqDSetToList
230
231 subDVarSet :: DVarSet -> DVarSet -> Bool
232 subDVarSet s1 s2 = isEmptyDVarSet (s1 `minusDVarSet` s2)
233
234 unionDVarSet :: DVarSet -> DVarSet -> DVarSet
235 unionDVarSet = unionUniqDSets
236
237 unionDVarSets :: [DVarSet] -> DVarSet
238 unionDVarSets = unionManyUniqDSets
239
240 -- | Map the function over the list, and union the results
241 mapUnionDVarSet :: (a -> DVarSet) -> [a] -> DVarSet
242 mapUnionDVarSet get_set xs = foldr (unionDVarSet . get_set) emptyDVarSet xs
243
244 intersectDVarSet :: DVarSet -> DVarSet -> DVarSet
245 intersectDVarSet = intersectUniqDSets
246
247 -- | True if empty intersection
248 disjointDVarSet :: DVarSet -> DVarSet -> Bool
249 disjointDVarSet s1 s2 = disjointUDFM s1 s2
250
251 -- | True if non-empty intersection
252 intersectsDVarSet :: DVarSet -> DVarSet -> Bool
253 intersectsDVarSet s1 s2 = not (s1 `disjointDVarSet` s2)
254
255 isEmptyDVarSet :: DVarSet -> Bool
256 isEmptyDVarSet = isEmptyUniqDSet
257
258 delDVarSet :: DVarSet -> Var -> DVarSet
259 delDVarSet = delOneFromUniqDSet
260
261 minusDVarSet :: DVarSet -> DVarSet -> DVarSet
262 minusDVarSet = minusUniqDSet
263
264 dVarSetMinusVarSet :: DVarSet -> VarSet -> DVarSet
265 dVarSetMinusVarSet = uniqDSetMinusUniqSet
266
267 foldDVarSet :: (Var -> a -> a) -> a -> DVarSet -> a
268 foldDVarSet = foldUniqDSet
269
270 filterDVarSet :: (Var -> Bool) -> DVarSet -> DVarSet
271 filterDVarSet = filterUniqDSet
272
273 sizeDVarSet :: DVarSet -> Int
274 sizeDVarSet = sizeUniqDSet
275
276 -- | Partition DVarSet according to the predicate given
277 partitionDVarSet :: (Var -> Bool) -> DVarSet -> (DVarSet, DVarSet)
278 partitionDVarSet = partitionUniqDSet
279
280 -- | Delete a list of variables from DVarSet
281 delDVarSetList :: DVarSet -> [Var] -> DVarSet
282 delDVarSetList = delListFromUniqDSet
283
284 seqDVarSet :: DVarSet -> ()
285 seqDVarSet s = sizeDVarSet s `seq` ()
286
287 -- | Add a list of variables to DVarSet
288 extendDVarSetList :: DVarSet -> [Var] -> DVarSet
289 extendDVarSetList = addListToUniqDSet
290
291 -- | Convert a DVarSet to a VarSet by forgeting the order of insertion
292 dVarSetToVarSet :: DVarSet -> VarSet
293 dVarSetToVarSet = udfmToUfm
294
295 -- | transCloVarSet for DVarSet
296 transCloDVarSet :: (DVarSet -> DVarSet)
297 -- Map some variables in the set to
298 -- extra variables that should be in it
299 -> DVarSet -> DVarSet
300 -- (transCloDVarSet f s) repeatedly applies f to new candidates, adding any
301 -- new variables to s that it finds thereby, until it reaches a fixed point.
302 --
303 -- The function fn could be (Var -> DVarSet), but we use (DVarSet -> DVarSet)
304 -- for efficiency, so that the test can be batched up.
305 -- It's essential that fn will work fine if given new candidates
306 -- one at at time; ie fn {v1,v2} = fn v1 `union` fn v2
307 transCloDVarSet fn seeds
308 = go seeds seeds
309 where
310 go :: DVarSet -- Accumulating result
311 -> DVarSet -- Work-list; un-processed subset of accumulating result
312 -> DVarSet
313 -- Specification: go acc vs = acc `union` transClo fn vs
314
315 go acc candidates
316 | isEmptyDVarSet new_vs = acc
317 | otherwise = go (acc `unionDVarSet` new_vs) new_vs
318 where
319 new_vs = fn candidates `minusDVarSet` acc