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