2 % (c) The University of Glasgow 2006
3 % (c) The GRASP/AQUA Project, Glasgow University, 1998
11 -- ** Manipulating these sets
12 emptyNameSet, unitNameSet, mkNameSet, unionNameSets, unionManyNameSets,
13 minusNameSet, elemNameSet, nameSetToList, addOneToNameSet, addListToNameSet,
14 delFromNameSet, delListFromNameSet, isEmptyNameSet, foldNameSet, filterNameSet,
15 intersectsNameSet, intersectNameSet,
20 -- ** Manipulating sets of free variables
21 isEmptyFVs, emptyFVs, plusFVs, plusFV,
22 mkFVs, addOneFV, unitFV, delFV, delFVs,
25 Defs, Uses, DefUse, DefUses,
27 -- ** Manipulating defs and uses
28 emptyDUs, usesOnly, mkDUs, plusDU,
29 findUses, duDefs, duUses, allUses
32 #include "HsVersions.h"
38 %************************************************************************
40 \subsection[Sets of names}
42 %************************************************************************
45 type NameSet = UniqSet Name
47 emptyNameSet :: NameSet
48 unitNameSet :: Name -> NameSet
49 addListToNameSet :: NameSet -> [Name] -> NameSet
50 addOneToNameSet :: NameSet -> Name -> NameSet
51 mkNameSet :: [Name] -> NameSet
52 unionNameSets :: NameSet -> NameSet -> NameSet
53 unionManyNameSets :: [NameSet] -> NameSet
54 minusNameSet :: NameSet -> NameSet -> NameSet
55 elemNameSet :: Name -> NameSet -> Bool
56 nameSetToList :: NameSet -> [Name]
57 isEmptyNameSet :: NameSet -> Bool
58 delFromNameSet :: NameSet -> Name -> NameSet
59 delListFromNameSet :: NameSet -> [Name] -> NameSet
60 foldNameSet :: (Name -> b -> b) -> b -> NameSet -> b
61 filterNameSet :: (Name -> Bool) -> NameSet -> NameSet
62 intersectNameSet :: NameSet -> NameSet -> NameSet
63 intersectsNameSet :: NameSet -> NameSet -> Bool
64 -- ^ True if there is a non-empty intersection.
65 -- @s1 `intersectsNameSet` s2@ doesn't compute @s2@ if @s1@ is empty
67 isEmptyNameSet = isEmptyUniqSet
68 emptyNameSet = emptyUniqSet
69 unitNameSet = unitUniqSet
71 addListToNameSet = addListToUniqSet
72 addOneToNameSet = addOneToUniqSet
73 unionNameSets = unionUniqSets
74 unionManyNameSets = unionManyUniqSets
75 minusNameSet = minusUniqSet
76 elemNameSet = elementOfUniqSet
77 nameSetToList = uniqSetToList
78 delFromNameSet = delOneFromUniqSet
79 foldNameSet = foldUniqSet
80 filterNameSet = filterUniqSet
81 intersectNameSet = intersectUniqSets
83 delListFromNameSet set ns = foldl delFromNameSet set ns
85 intersectsNameSet s1 s2 = not (isEmptyNameSet (s1 `intersectNameSet` s2))
89 %************************************************************************
91 \subsection{Free variables}
93 %************************************************************************
95 These synonyms are useful when we are thinking of free variables
98 type FreeVars = NameSet
100 plusFV :: FreeVars -> FreeVars -> FreeVars
101 addOneFV :: FreeVars -> Name -> FreeVars
102 unitFV :: Name -> FreeVars
104 plusFVs :: [FreeVars] -> FreeVars
105 mkFVs :: [Name] -> FreeVars
106 delFV :: Name -> FreeVars -> FreeVars
107 delFVs :: [Name] -> FreeVars -> FreeVars
109 isEmptyFVs :: NameSet -> Bool
110 isEmptyFVs = isEmptyNameSet
111 emptyFVs = emptyNameSet
112 plusFVs = unionManyNameSets
113 plusFV = unionNameSets
115 addOneFV = addOneToNameSet
117 delFV n s = delFromNameSet s n
118 delFVs ns s = delListFromNameSet s ns
122 %************************************************************************
126 %************************************************************************
129 -- | A set of names that are defined somewhere
132 -- | A set of names that are used somewhere
135 -- | @(Just ds, us) =>@ The use of any member of the @ds@
136 -- implies that all the @us@ are used too.
137 -- Also, @us@ may mention @ds@.
139 -- @Nothing =>@ Nothing is defined in this group, but
140 -- nevertheless all the uses are essential.
141 -- Used for instance declarations, for example
142 type DefUse = (Maybe Defs, Uses)
144 -- | A number of 'DefUse's in dependency order: earlier 'Defs' scope over later 'Uses'
145 type DefUses = [DefUse]
150 usesOnly :: Uses -> DefUses
151 usesOnly uses = [(Nothing, uses)]
153 mkDUs :: [(Defs,Uses)] -> DefUses
154 mkDUs pairs = [(Just defs, uses) | (defs,uses) <- pairs]
156 plusDU :: DefUses -> DefUses -> DefUses
159 duDefs :: DefUses -> Defs
160 duDefs dus = foldr get emptyNameSet dus
162 get (Nothing, _u1) d2 = d2
163 get (Just d1, _u1) d2 = d1 `unionNameSets` d2
165 duUses :: DefUses -> Uses
166 -- ^ Just like 'allUses', but 'Defs' are not eliminated from the 'Uses' returned
167 duUses dus = foldr get emptyNameSet dus
169 get (_d1, u1) u2 = u1 `unionNameSets` u2
171 allUses :: DefUses -> Uses
172 -- ^ Collect all 'Uses', regardless of whether the group is itself used,
173 -- but remove 'Defs' on the way
175 = foldr get emptyNameSet dus
177 get (Nothing, rhs_uses) uses = rhs_uses `unionNameSets` uses
178 get (Just defs, rhs_uses) uses = (rhs_uses `unionNameSets` uses)
181 findUses :: DefUses -> Uses -> Uses
182 -- ^ Given some 'DefUses' and some 'Uses', find all the uses, transitively.
183 -- The result is a superset of the input 'Uses'; and includes things defined
184 -- in the input 'DefUses' (but only if they are used)
188 get (Nothing, rhs_uses) uses
189 = rhs_uses `unionNameSets` uses
190 get (Just defs, rhs_uses) uses
191 | defs `intersectsNameSet` uses -- Used
192 || not (all (reportIfUnused . nameOccName) (nameSetToList defs))
193 -- At least one starts with an "_",
194 -- so treat the group as used
195 = rhs_uses `unionNameSets` uses
196 | otherwise -- No def is used