2 % (c) The University of Glasgow 2006
3 % (c) The GRASP/AQUA Project, Glasgow University, 1998
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 -- XXX This define is a bit of a hack, and should be done more nicely
26 #define FAST_STRING_NOT_NEEDED 1
27 #include "HsVersions.h"
33 %************************************************************************
35 \subsection[Sets of names}
37 %************************************************************************
40 type NameSet = UniqSet Name
41 emptyNameSet :: NameSet
42 unitNameSet :: Name -> NameSet
43 addListToNameSet :: NameSet -> [Name] -> NameSet
44 addOneToNameSet :: NameSet -> Name -> NameSet
45 mkNameSet :: [Name] -> NameSet
46 unionNameSets :: NameSet -> NameSet -> NameSet
47 unionManyNameSets :: [NameSet] -> NameSet
48 minusNameSet :: NameSet -> NameSet -> NameSet
49 elemNameSet :: Name -> NameSet -> Bool
50 nameSetToList :: NameSet -> [Name]
51 isEmptyNameSet :: NameSet -> Bool
52 delFromNameSet :: NameSet -> Name -> NameSet
53 delListFromNameSet :: NameSet -> [Name] -> NameSet
54 foldNameSet :: (Name -> b -> b) -> b -> NameSet -> b
55 filterNameSet :: (Name -> Bool) -> NameSet -> NameSet
56 intersectNameSet :: NameSet -> NameSet -> NameSet
57 intersectsNameSet :: NameSet -> NameSet -> Bool -- True if non-empty intersection
58 -- (s1 `intersectsNameSet` s2) doesn't compute s2 if s1 is empty
60 isEmptyNameSet = isEmptyUniqSet
61 emptyNameSet = emptyUniqSet
62 unitNameSet = unitUniqSet
64 addListToNameSet = addListToUniqSet
65 addOneToNameSet = addOneToUniqSet
66 unionNameSets = unionUniqSets
67 unionManyNameSets = unionManyUniqSets
68 minusNameSet = minusUniqSet
69 elemNameSet = elementOfUniqSet
70 nameSetToList = uniqSetToList
71 delFromNameSet = delOneFromUniqSet
72 foldNameSet = foldUniqSet
73 filterNameSet = filterUniqSet
74 intersectNameSet = intersectUniqSets
76 delListFromNameSet set ns = foldl delFromNameSet set ns
78 intersectsNameSet s1 s2 = not (isEmptyNameSet (s1 `intersectNameSet` s2))
82 %************************************************************************
84 \subsection{Free variables}
86 %************************************************************************
88 These synonyms are useful when we are thinking of free variables
91 type FreeVars = NameSet
93 plusFV :: FreeVars -> FreeVars -> FreeVars
94 addOneFV :: FreeVars -> Name -> FreeVars
95 unitFV :: Name -> FreeVars
97 plusFVs :: [FreeVars] -> FreeVars
98 mkFVs :: [Name] -> FreeVars
99 delFV :: Name -> FreeVars -> FreeVars
100 delFVs :: [Name] -> FreeVars -> FreeVars
102 isEmptyFVs :: NameSet -> Bool
103 isEmptyFVs = isEmptyNameSet
104 emptyFVs = emptyNameSet
105 plusFVs = unionManyNameSets
106 plusFV = unionNameSets
108 addOneFV = addOneToNameSet
110 delFV n s = delFromNameSet s n
111 delFVs ns s = delListFromNameSet s ns
115 %************************************************************************
119 %************************************************************************
125 type DefUses = [DefUse]
126 -- In dependency order: earlier Defs scope over later Uses
128 type DefUse = (Maybe Defs, Uses)
129 -- For items (Just ds, us), the use of any member
130 -- of the ds implies that all the us are used too
132 -- Also, us may mention ds
134 -- Nothing => Nothing defined in this group, but
135 -- nevertheless all the uses are essential.
136 -- Used for instance declarations, for example
141 usesOnly :: Uses -> DefUses
142 usesOnly uses = [(Nothing, uses)]
144 mkDUs :: [(Defs,Uses)] -> DefUses
145 mkDUs pairs = [(Just defs, uses) | (defs,uses) <- pairs]
147 plusDU :: DefUses -> DefUses -> DefUses
150 duDefs :: DefUses -> Defs
151 duDefs dus = foldr get emptyNameSet dus
153 get (Nothing, _u1) d2 = d2
154 get (Just d1, _u1) d2 = d1 `unionNameSets` d2
156 duUses :: DefUses -> Uses
157 -- Just like allUses, but defs are not eliminated
158 duUses dus = foldr get emptyNameSet dus
160 get (_d1, u1) u2 = u1 `unionNameSets` u2
162 allUses :: DefUses -> Uses
163 -- Collect all uses, regardless of
164 -- whether the group is itself used,
165 -- but remove defs on the way
167 = foldr get emptyNameSet dus
169 get (Nothing, rhs_uses) uses = rhs_uses `unionNameSets` uses
170 get (Just defs, rhs_uses) uses = (rhs_uses `unionNameSets` uses)
173 findUses :: DefUses -> Uses -> Uses
174 -- Given some DefUses and some Uses,
175 -- find all the uses, transitively.
176 -- The result is a superset of the input uses;
177 -- and includes things defined in the input DefUses
178 -- (but only if they are used)
182 get (Nothing, rhs_uses) uses
183 = rhs_uses `unionNameSets` uses
184 get (Just defs, rhs_uses) uses
185 | defs `intersectsNameSet` uses -- Used
186 || not (all (reportIfUnused . nameOccName) (nameSetToList defs))
187 -- At least one starts with an "_",
188 -- so treat the group as used
189 = rhs_uses `unionNameSets` uses
190 | otherwise -- No def is used