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