2 % (c) The GRASP/AQUA Project, Glasgow University, 1998
4 \section[NameSet]{@NameSets@}
10 emptyNameSet, unitNameSet, mkNameSet, unionNameSets, unionManyNameSets,
11 minusNameSet, elemNameSet, nameSetToList, addOneToNameSet, addListToNameSet,
12 delFromNameSet, delListFromNameSet, isEmptyNameSet, foldNameSet, filterNameSet,
13 intersectsNameSet, intersectNameSet,
16 FreeVars, isEmptyFVs, emptyFVs, plusFVs, plusFV,
17 mkFVs, addOneFV, unitFV, delFV, delFVs,
20 Defs, Uses, DefUse, DefUses,
21 emptyDUs, usesOnly, mkDUs, plusDU,
22 findUses, duDefs, duUses, allUses
25 #include "HsVersions.h"
32 %************************************************************************
34 \subsection[Sets of names}
36 %************************************************************************
39 type NameSet = UniqSet Name
40 emptyNameSet :: NameSet
41 unitNameSet :: Name -> NameSet
42 addListToNameSet :: NameSet -> [Name] -> NameSet
43 addOneToNameSet :: NameSet -> Name -> NameSet
44 mkNameSet :: [Name] -> NameSet
45 unionNameSets :: NameSet -> NameSet -> NameSet
46 unionManyNameSets :: [NameSet] -> NameSet
47 minusNameSet :: NameSet -> NameSet -> NameSet
48 elemNameSet :: Name -> NameSet -> Bool
49 nameSetToList :: NameSet -> [Name]
50 isEmptyNameSet :: NameSet -> Bool
51 delFromNameSet :: NameSet -> Name -> NameSet
52 delListFromNameSet :: NameSet -> [Name] -> NameSet
53 foldNameSet :: (Name -> b -> b) -> b -> NameSet -> b
54 filterNameSet :: (Name -> Bool) -> NameSet -> NameSet
55 intersectNameSet :: NameSet -> NameSet -> NameSet
56 intersectsNameSet :: NameSet -> NameSet -> Bool -- True if non-empty intersection
57 -- (s1 `intersectsVarSet` s2) doesn't compute s2 if s1 is empty
59 isEmptyNameSet = isEmptyUniqSet
60 emptyNameSet = emptyUniqSet
61 unitNameSet = unitUniqSet
63 addListToNameSet = addListToUniqSet
64 addOneToNameSet = addOneToUniqSet
65 unionNameSets = unionUniqSets
66 unionManyNameSets = unionManyUniqSets
67 minusNameSet = minusUniqSet
68 elemNameSet = elementOfUniqSet
69 nameSetToList = uniqSetToList
70 delFromNameSet = delOneFromUniqSet
71 foldNameSet = foldUniqSet
72 filterNameSet = filterUniqSet
73 intersectNameSet = intersectUniqSets
75 delListFromNameSet set ns = foldl delFromNameSet set ns
77 intersectsNameSet s1 s2 = not (isEmptyNameSet (s1 `intersectNameSet` s2))
81 %************************************************************************
83 \subsection{Free variables}
85 %************************************************************************
87 These synonyms are useful when we are thinking of free variables
90 type FreeVars = NameSet
92 plusFV :: FreeVars -> FreeVars -> FreeVars
93 addOneFV :: FreeVars -> Name -> FreeVars
94 unitFV :: Name -> FreeVars
96 plusFVs :: [FreeVars] -> FreeVars
97 mkFVs :: [Name] -> FreeVars
98 delFV :: Name -> FreeVars -> FreeVars
99 delFVs :: [Name] -> FreeVars -> FreeVars
101 isEmptyFVs = isEmptyNameSet
102 emptyFVs = emptyNameSet
103 plusFVs = unionManyNameSets
104 plusFV = unionNameSets
106 addOneFV = addOneToNameSet
108 delFV n s = delFromNameSet s n
109 delFVs ns s = delListFromNameSet s ns
113 %************************************************************************
117 %************************************************************************
123 type DefUses = [DefUse]
124 -- In dependency order: earlier Defs scope over later Uses
126 type DefUse = (Maybe Defs, Uses)
127 -- For items (Just ds, us), the use of any member
128 -- of the ds implies that all the us are used too
130 -- Also, us may mention ds
132 -- Nothing => Nothing defined in this group, but
133 -- nevertheless all the uses are essential.
134 -- Used for instance declarations, for example
139 usesOnly :: Uses -> DefUses
140 usesOnly uses = [(Nothing, uses)]
142 mkDUs :: [(Defs,Uses)] -> DefUses
143 mkDUs pairs = [(Just defs, uses) | (defs,uses) <- pairs]
145 plusDU :: DefUses -> DefUses -> DefUses
148 allUses :: DefUses -> Uses -> Uses
149 -- Collect all uses, removing defs
151 = foldr get emptyNameSet dus
153 get (Nothing, rhs_uses) uses = rhs_uses `unionNameSets` uses
154 get (Just defs, rhs_uses) uses = (rhs_uses `unionNameSets` uses)
157 findUses :: DefUses -> Uses -> Uses
158 -- Given some DefUses and some Uses,
159 -- find all the uses, transitively.
160 -- The result is a superset of the input uses;
161 -- and includes things defined in the input DefUses
162 -- (if they are used, of course)
166 get (Nothing, rhs_uses) uses
167 = rhs_uses `unionNameSets` uses
168 get (Just defs, rhs_uses) uses
169 | defs `intersectsNameSet` uses
170 = rhs_uses `unionNameSets` uses
171 | otherwise -- No def is used
174 duDefs :: DefUses -> Defs
175 duDefs dus = foldr get emptyNameSet dus
177 get (Nothing, u1) d2 = d2
178 get (Just d1, u1) d2 = d1 `unionNameSets` d2
180 duUses :: DefUses -> Uses
181 -- Defs are not eliminated
182 duUses dus = foldr get emptyNameSet dus
184 get (d1, u1) u2 = u1 `unionNameSets` u2