f5ea6edf19fb4273ea2e8e132b28750185014c58
[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 ) where
24
25 #include "HsVersions.h"
26
27 import Var ( Var, TyVar, CoVar, Id )
28 import Unique
29 import UniqSet
30 import UniqFM( disjointUFM )
31
32 {-
33 ************************************************************************
34 * *
35 \subsection{@VarSet@s}
36 * *
37 ************************************************************************
38 -}
39
40 type VarSet = UniqSet Var
41 type IdSet = UniqSet Id
42 type TyVarSet = UniqSet TyVar
43 type CoVarSet = UniqSet CoVar
44
45 emptyVarSet :: VarSet
46 intersectVarSet :: VarSet -> VarSet -> VarSet
47 unionVarSet :: VarSet -> VarSet -> VarSet
48 unionVarSets :: [VarSet] -> VarSet
49
50 mapUnionVarSet :: (a -> VarSet) -> [a] -> VarSet
51 -- ^ map the function oer the list, and union the results
52
53 varSetElems :: VarSet -> [Var]
54 unitVarSet :: Var -> VarSet
55 extendVarSet :: VarSet -> Var -> VarSet
56 extendVarSetList:: VarSet -> [Var] -> VarSet
57 elemVarSet :: Var -> VarSet -> Bool
58 delVarSet :: VarSet -> Var -> VarSet
59 delVarSetList :: VarSet -> [Var] -> VarSet
60 minusVarSet :: VarSet -> VarSet -> VarSet
61 isEmptyVarSet :: VarSet -> Bool
62 mkVarSet :: [Var] -> VarSet
63 foldVarSet :: (Var -> a -> a) -> a -> VarSet -> a
64 lookupVarSet :: VarSet -> Var -> Maybe Var
65 -- Returns the set element, which may be
66 -- (==) to the argument, but not the same as
67 mapVarSet :: (Var -> Var) -> VarSet -> VarSet
68 sizeVarSet :: VarSet -> Int
69 filterVarSet :: (Var -> Bool) -> VarSet -> VarSet
70 extendVarSet_C :: (Var->Var->Var) -> VarSet -> Var -> VarSet
71
72 delVarSetByKey :: VarSet -> Unique -> VarSet
73 elemVarSetByKey :: Unique -> VarSet -> Bool
74 partitionVarSet :: (Var -> Bool) -> VarSet -> (VarSet, VarSet)
75
76 emptyVarSet = emptyUniqSet
77 unitVarSet = unitUniqSet
78 extendVarSet = addOneToUniqSet
79 extendVarSetList= addListToUniqSet
80 intersectVarSet = intersectUniqSets
81
82 intersectsVarSet:: VarSet -> VarSet -> Bool -- True if non-empty intersection
83 disjointVarSet :: VarSet -> VarSet -> Bool -- True if empty intersection
84 subVarSet :: VarSet -> VarSet -> Bool -- True if first arg is subset of second
85 -- (s1 `intersectsVarSet` s2) doesn't compute s2 if s1 is empty;
86 -- ditto disjointVarSet, subVarSet
87
88 unionVarSet = unionUniqSets
89 unionVarSets = unionManyUniqSets
90 varSetElems = uniqSetToList
91 elemVarSet = elementOfUniqSet
92 minusVarSet = minusUniqSet
93 delVarSet = delOneFromUniqSet
94 delVarSetList = delListFromUniqSet
95 isEmptyVarSet = isEmptyUniqSet
96 mkVarSet = mkUniqSet
97 foldVarSet = foldUniqSet
98 lookupVarSet = lookupUniqSet
99 mapVarSet = mapUniqSet
100 sizeVarSet = sizeUniqSet
101 filterVarSet = filterUniqSet
102 extendVarSet_C = addOneToUniqSet_C
103 delVarSetByKey = delOneFromUniqSet_Directly
104 elemVarSetByKey = elemUniqSet_Directly
105 partitionVarSet = partitionUniqSet
106
107 mapUnionVarSet get_set xs = foldr (unionVarSet . get_set) emptyVarSet xs
108
109 -- See comments with type signatures
110 intersectsVarSet s1 s2 = not (s1 `disjointVarSet` s2)
111 disjointVarSet s1 s2 = disjointUFM s1 s2
112 subVarSet s1 s2 = isEmptyVarSet (s1 `minusVarSet` s2)
113
114 fixVarSet :: (VarSet -> VarSet) -- Map the current set to a new set
115 -> VarSet -> VarSet
116 -- (fixVarSet f s) repeatedly applies f to the set s,
117 -- until it reaches a fixed point.
118 fixVarSet fn vars
119 | new_vars `subVarSet` vars = vars
120 | otherwise = fixVarSet fn new_vars
121 where
122 new_vars = fn vars
123
124 transCloVarSet :: (VarSet -> VarSet)
125 -- Map some variables in the set to
126 -- extra variables that should be in it
127 -> VarSet -> VarSet
128 -- (transCloVarSet f s) repeatedly applies f to new candidates, adding any
129 -- new variables to s that it finds thereby, until it reaches a fixed point.
130 --
131 -- The function fn could be (Var -> VarSet), but we use (VarSet -> VarSet)
132 -- for efficiency, so that the test can be batched up.
133 -- It's essential that fn will work fine if given new candidates
134 -- one at at time; ie fn {v1,v2} = fn v1 `union` fn v2
135 -- Use fixVarSet if the function needs to see the whole set all at once
136 transCloVarSet fn seeds
137 = go seeds seeds
138 where
139 go :: VarSet -- Accumulating result
140 -> VarSet -- Work-list; un-processed subset of accumulating result
141 -> VarSet
142 -- Specification: go acc vs = acc `union` transClo fn vs
143
144 go acc candidates
145 | isEmptyVarSet new_vs = acc
146 | otherwise = go (acc `unionVarSet` new_vs) new_vs
147 where
148 new_vs = fn candidates `minusVarSet` acc
149
150 seqVarSet :: VarSet -> ()
151 seqVarSet s = sizeVarSet s `seq` ()