The Backpack patch.
[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, 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 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 :: VarSet -> Var -> Maybe Var
95 -- Returns the set element, which may be
96 -- (==) to the argument, but not the same as
97 lookupVarSetByName :: VarSet -> Name -> Maybe Var
98 sizeVarSet :: VarSet -> Int
99 filterVarSet :: (Var -> Bool) -> VarSet -> VarSet
100 extendVarSet_C :: (Var->Var->Var) -> VarSet -> Var -> 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 = lookupUniqSet
127 lookupVarSetByName = lookupUniqSet
128 sizeVarSet = sizeUniqSet
129 filterVarSet = filterUniqSet
130 extendVarSet_C = addOneToUniqSet_C
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 s1 s2
140 subVarSet s1 s2 = isEmptyVarSet (s1 `minusVarSet` s2)
141
142 varSetAny :: (Var -> Bool) -> VarSet -> Bool
143 varSetAny = uniqSetAny
144
145 varSetAll :: (Var -> Bool) -> VarSet -> Bool
146 varSetAll = 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
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
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 filterDVarSet :: (Var -> Bool) -> DVarSet -> DVarSet
286 filterDVarSet = filterUniqDSet
287
288 sizeDVarSet :: DVarSet -> Int
289 sizeDVarSet = sizeUniqDSet
290
291 -- | Partition DVarSet according to the predicate given
292 partitionDVarSet :: (Var -> Bool) -> DVarSet -> (DVarSet, DVarSet)
293 partitionDVarSet = partitionUniqDSet
294
295 -- | Delete a list of variables from DVarSet
296 delDVarSetList :: DVarSet -> [Var] -> DVarSet
297 delDVarSetList = delListFromUniqDSet
298
299 seqDVarSet :: DVarSet -> ()
300 seqDVarSet s = sizeDVarSet s `seq` ()
301
302 -- | Add a list of variables to DVarSet
303 extendDVarSetList :: DVarSet -> [Var] -> DVarSet
304 extendDVarSetList = addListToUniqDSet
305
306 -- | Convert a DVarSet to a VarSet by forgeting the order of insertion
307 dVarSetToVarSet :: DVarSet -> VarSet
308 dVarSetToVarSet = udfmToUfm
309
310 -- | transCloVarSet for DVarSet
311 transCloDVarSet :: (DVarSet -> DVarSet)
312 -- Map some variables in the set to
313 -- extra variables that should be in it
314 -> DVarSet -> DVarSet
315 -- (transCloDVarSet f s) repeatedly applies f to new candidates, adding any
316 -- new variables to s that it finds thereby, until it reaches a fixed point.
317 --
318 -- The function fn could be (Var -> DVarSet), but we use (DVarSet -> DVarSet)
319 -- for efficiency, so that the test can be batched up.
320 -- It's essential that fn will work fine if given new candidates
321 -- one at at time; ie fn {v1,v2} = fn v1 `union` fn v2
322 transCloDVarSet fn seeds
323 = go seeds seeds
324 where
325 go :: DVarSet -- Accumulating result
326 -> DVarSet -- Work-list; un-processed subset of accumulating result
327 -> DVarSet
328 -- Specification: go acc vs = acc `union` transClo fn vs
329
330 go acc candidates
331 | isEmptyDVarSet new_vs = acc
332 | otherwise = go (acc `unionDVarSet` new_vs) new_vs
333 where
334 new_vs = fn candidates `minusDVarSet` acc