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