Add uniqSetAny and uniqSetAll and use them
[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, foldVarSet, filterVarSet,
20 varSetAny, varSetAll,
21 transCloVarSet, fixVarSet,
22 lookupVarSet, lookupVarSetByName,
23 mapVarSet, 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 foldVarSet :: (Var -> a -> a) -> a -> VarSet -> a
86 lookupVarSet :: VarSet -> Var -> Maybe Var
87 -- Returns the set element, which may be
88 -- (==) to the argument, but not the same as
89 lookupVarSetByName :: VarSet -> Name -> Maybe Var
90 mapVarSet :: (Var -> Var) -> VarSet -> VarSet
91 sizeVarSet :: VarSet -> Int
92 filterVarSet :: (Var -> Bool) -> VarSet -> VarSet
93 extendVarSet_C :: (Var->Var->Var) -> VarSet -> Var -> VarSet
94
95 delVarSetByKey :: VarSet -> Unique -> VarSet
96 elemVarSetByKey :: Unique -> VarSet -> Bool
97 partitionVarSet :: (Var -> Bool) -> VarSet -> (VarSet, VarSet)
98
99 emptyVarSet = emptyUniqSet
100 unitVarSet = unitUniqSet
101 extendVarSet = addOneToUniqSet
102 extendVarSetList= addListToUniqSet
103 intersectVarSet = intersectUniqSets
104
105 intersectsVarSet:: VarSet -> VarSet -> Bool -- True if non-empty intersection
106 disjointVarSet :: VarSet -> VarSet -> Bool -- True if empty intersection
107 subVarSet :: VarSet -> VarSet -> Bool -- True if first arg is subset of second
108 -- (s1 `intersectsVarSet` s2) doesn't compute s2 if s1 is empty;
109 -- ditto disjointVarSet, subVarSet
110
111 unionVarSet = unionUniqSets
112 unionVarSets = unionManyUniqSets
113 varSetElems = uniqSetToList
114 elemVarSet = elementOfUniqSet
115 minusVarSet = minusUniqSet
116 delVarSet = delOneFromUniqSet
117 delVarSetList = delListFromUniqSet
118 isEmptyVarSet = isEmptyUniqSet
119 mkVarSet = mkUniqSet
120 foldVarSet = foldUniqSet
121 lookupVarSet = lookupUniqSet
122 lookupVarSetByName = lookupUniqSet
123 mapVarSet = mapUniqSet
124 sizeVarSet = sizeUniqSet
125 filterVarSet = filterUniqSet
126 extendVarSet_C = addOneToUniqSet_C
127 delVarSetByKey = delOneFromUniqSet_Directly
128 elemVarSetByKey = elemUniqSet_Directly
129 partitionVarSet = partitionUniqSet
130
131 mapUnionVarSet get_set xs = foldr (unionVarSet . get_set) emptyVarSet xs
132
133 -- See comments with type signatures
134 intersectsVarSet s1 s2 = not (s1 `disjointVarSet` s2)
135 disjointVarSet s1 s2 = disjointUFM s1 s2
136 subVarSet s1 s2 = isEmptyVarSet (s1 `minusVarSet` s2)
137
138 varSetAny :: (Var -> Bool) -> VarSet -> Bool
139 varSetAny = uniqSetAny
140
141 varSetAll :: (Var -> Bool) -> VarSet -> Bool
142 varSetAll = uniqSetAll
143
144 fixVarSet :: (VarSet -> VarSet) -- Map the current set to a new set
145 -> VarSet -> VarSet
146 -- (fixVarSet f s) repeatedly applies f to the set s,
147 -- until it reaches a fixed point.
148 fixVarSet fn vars
149 | new_vars `subVarSet` vars = vars
150 | otherwise = fixVarSet fn new_vars
151 where
152 new_vars = fn vars
153
154 transCloVarSet :: (VarSet -> VarSet)
155 -- Map some variables in the set to
156 -- extra variables that should be in it
157 -> VarSet -> VarSet
158 -- (transCloVarSet f s) repeatedly applies f to new candidates, adding any
159 -- new variables to s that it finds thereby, until it reaches a fixed point.
160 --
161 -- The function fn could be (Var -> VarSet), but we use (VarSet -> VarSet)
162 -- for efficiency, so that the test can be batched up.
163 -- It's essential that fn will work fine if given new candidates
164 -- one at at time; ie fn {v1,v2} = fn v1 `union` fn v2
165 -- Use fixVarSet if the function needs to see the whole set all at once
166 transCloVarSet fn seeds
167 = go seeds seeds
168 where
169 go :: VarSet -- Accumulating result
170 -> VarSet -- Work-list; un-processed subset of accumulating result
171 -> VarSet
172 -- Specification: go acc vs = acc `union` transClo fn vs
173
174 go acc candidates
175 | isEmptyVarSet new_vs = acc
176 | otherwise = go (acc `unionVarSet` new_vs) new_vs
177 where
178 new_vs = fn candidates `minusVarSet` acc
179
180 seqVarSet :: VarSet -> ()
181 seqVarSet s = sizeVarSet s `seq` ()
182
183 -- | Determines the pluralisation suffix appropriate for the length of a set
184 -- in the same way that plural from Outputable does for lists.
185 pluralVarSet :: VarSet -> SDoc
186 pluralVarSet = pluralUFM
187
188 -- | Pretty-print a non-deterministic set.
189 -- The order of variables is non-deterministic and for pretty-printing that
190 -- shouldn't be a problem.
191 -- Having this function helps contain the non-determinism created with
192 -- varSetElems.
193 -- Passing a list to the pretty-printing function allows the caller
194 -- to decide on the order of Vars (eg. toposort them) without them having
195 -- to use varSetElems at the call site. This prevents from let-binding
196 -- non-deterministically ordered lists and reusing them where determinism
197 -- matters.
198 pprVarSet :: ([Var] -> SDoc) -- ^ The pretty printing function to use on the
199 -- elements
200 -> VarSet -- ^ The things to be pretty printed
201 -> SDoc -- ^ 'SDoc' where the things have been pretty
202 -- printed
203 pprVarSet = pprUFM
204
205 -- Deterministic VarSet
206 -- See Note [Deterministic UniqFM] in UniqDFM for explanation why we need
207 -- DVarSet.
208
209 type DVarSet = UniqDSet Var
210 type DIdSet = UniqDSet Id
211 type DTyVarSet = UniqDSet TyVar
212 type DTyCoVarSet = UniqDSet TyCoVar
213
214 emptyDVarSet :: DVarSet
215 emptyDVarSet = emptyUniqDSet
216
217 unitDVarSet :: Var -> DVarSet
218 unitDVarSet = unitUniqDSet
219
220 mkDVarSet :: [Var] -> DVarSet
221 mkDVarSet = mkUniqDSet
222
223 extendDVarSet :: DVarSet -> Var -> DVarSet
224 extendDVarSet = addOneToUniqDSet
225
226 elemDVarSet :: Var -> DVarSet -> Bool
227 elemDVarSet = elementOfUniqDSet
228
229 dVarSetElems :: DVarSet -> [Var]
230 dVarSetElems = uniqDSetToList
231
232 subDVarSet :: DVarSet -> DVarSet -> Bool
233 subDVarSet s1 s2 = isEmptyDVarSet (s1 `minusDVarSet` s2)
234
235 unionDVarSet :: DVarSet -> DVarSet -> DVarSet
236 unionDVarSet = unionUniqDSets
237
238 unionDVarSets :: [DVarSet] -> DVarSet
239 unionDVarSets = unionManyUniqDSets
240
241 -- | Map the function over the list, and union the results
242 mapUnionDVarSet :: (a -> DVarSet) -> [a] -> DVarSet
243 mapUnionDVarSet get_set xs = foldr (unionDVarSet . get_set) emptyDVarSet xs
244
245 intersectDVarSet :: DVarSet -> DVarSet -> DVarSet
246 intersectDVarSet = intersectUniqDSets
247
248 -- | True if empty intersection
249 disjointDVarSet :: DVarSet -> DVarSet -> Bool
250 disjointDVarSet s1 s2 = disjointUDFM s1 s2
251
252 -- | True if non-empty intersection
253 intersectsDVarSet :: DVarSet -> DVarSet -> Bool
254 intersectsDVarSet s1 s2 = not (s1 `disjointDVarSet` s2)
255
256 isEmptyDVarSet :: DVarSet -> Bool
257 isEmptyDVarSet = isEmptyUniqDSet
258
259 delDVarSet :: DVarSet -> Var -> DVarSet
260 delDVarSet = delOneFromUniqDSet
261
262 minusDVarSet :: DVarSet -> DVarSet -> DVarSet
263 minusDVarSet = minusUniqDSet
264
265 dVarSetMinusVarSet :: DVarSet -> VarSet -> DVarSet
266 dVarSetMinusVarSet = uniqDSetMinusUniqSet
267
268 foldDVarSet :: (Var -> a -> a) -> a -> DVarSet -> a
269 foldDVarSet = foldUniqDSet
270
271 filterDVarSet :: (Var -> Bool) -> DVarSet -> DVarSet
272 filterDVarSet = filterUniqDSet
273
274 sizeDVarSet :: DVarSet -> Int
275 sizeDVarSet = sizeUniqDSet
276
277 -- | Partition DVarSet according to the predicate given
278 partitionDVarSet :: (Var -> Bool) -> DVarSet -> (DVarSet, DVarSet)
279 partitionDVarSet = partitionUniqDSet
280
281 -- | Delete a list of variables from DVarSet
282 delDVarSetList :: DVarSet -> [Var] -> DVarSet
283 delDVarSetList = delListFromUniqDSet
284
285 seqDVarSet :: DVarSet -> ()
286 seqDVarSet s = sizeDVarSet s `seq` ()
287
288 -- | Add a list of variables to DVarSet
289 extendDVarSetList :: DVarSet -> [Var] -> DVarSet
290 extendDVarSetList = addListToUniqDSet
291
292 -- | Convert a DVarSet to a VarSet by forgeting the order of insertion
293 dVarSetToVarSet :: DVarSet -> VarSet
294 dVarSetToVarSet = udfmToUfm
295
296 -- | transCloVarSet for DVarSet
297 transCloDVarSet :: (DVarSet -> DVarSet)
298 -- Map some variables in the set to
299 -- extra variables that should be in it
300 -> DVarSet -> DVarSet
301 -- (transCloDVarSet f s) repeatedly applies f to new candidates, adding any
302 -- new variables to s that it finds thereby, until it reaches a fixed point.
303 --
304 -- The function fn could be (Var -> DVarSet), but we use (DVarSet -> DVarSet)
305 -- for efficiency, so that the test can be batched up.
306 -- It's essential that fn will work fine if given new candidates
307 -- one at at time; ie fn {v1,v2} = fn v1 `union` fn v2
308 transCloDVarSet fn seeds
309 = go seeds seeds
310 where
311 go :: DVarSet -- Accumulating result
312 -> DVarSet -- Work-list; un-processed subset of accumulating result
313 -> DVarSet
314 -- Specification: go acc vs = acc `union` transClo fn vs
315
316 go acc candidates
317 | isEmptyDVarSet new_vs = acc
318 | otherwise = go (acc `unionDVarSet` new_vs) new_vs
319 where
320 new_vs = fn candidates `minusDVarSet` acc