Add DVarSet - a deterministic set of Vars
[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,
30 elemDVarSet, dVarSetElems, subDVarSet,
31 unionDVarSet, unionDVarSets, mapUnionDVarSet,
32 intersectDVarSet,
33 isEmptyDVarSet, delDVarSet,
34 minusDVarSet, foldDVarSet, filterDVarSet,
35 sizeDVarSet, seqDVarSet,
36 ) where
37
38 #include "HsVersions.h"
39
40 import Var ( Var, TyVar, CoVar, Id )
41 import Unique
42 import UniqSet
43 import UniqDSet
44 import UniqFM( disjointUFM )
45
46 {-
47 ************************************************************************
48 * *
49 \subsection{@VarSet@s}
50 * *
51 ************************************************************************
52 -}
53
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 isEmptyDVarSet :: DVarSet -> Bool
210 isEmptyDVarSet = isEmptyUniqDSet
211
212 delDVarSet :: DVarSet -> Var -> DVarSet
213 delDVarSet = delOneFromUniqDSet
214
215 minusDVarSet :: DVarSet -> DVarSet -> DVarSet
216 minusDVarSet = minusUniqDSet
217
218 foldDVarSet :: (Var -> a -> a) -> a -> DVarSet -> a
219 foldDVarSet = foldUniqDSet
220
221 filterDVarSet :: (Var -> Bool) -> DVarSet -> DVarSet
222 filterDVarSet = filterUniqDSet
223
224 sizeDVarSet :: DVarSet -> Int
225 sizeDVarSet = sizeUniqDSet
226
227 seqDVarSet :: DVarSet -> ()
228 seqDVarSet s = sizeDVarSet s `seq` ()