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