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 #include "HsVersions.h"
31 %************************************************************************
33 \subsection[Sets of names}
35 %************************************************************************
38 type NameSet = UniqSet Name
39 emptyNameSet :: NameSet
40 unitNameSet :: Name -> NameSet
41 addListToNameSet :: NameSet -> [Name] -> NameSet
42 addOneToNameSet :: NameSet -> Name -> NameSet
43 mkNameSet :: [Name] -> NameSet
44 unionNameSets :: NameSet -> NameSet -> NameSet
45 unionManyNameSets :: [NameSet] -> NameSet
46 minusNameSet :: NameSet -> NameSet -> NameSet
47 elemNameSet :: Name -> NameSet -> Bool
48 nameSetToList :: NameSet -> [Name]
49 isEmptyNameSet :: NameSet -> Bool
50 delFromNameSet :: NameSet -> Name -> NameSet
51 delListFromNameSet :: NameSet -> [Name] -> NameSet
52 foldNameSet :: (Name -> b -> b) -> b -> NameSet -> b
53 filterNameSet :: (Name -> Bool) -> NameSet -> NameSet
54 intersectNameSet :: NameSet -> NameSet -> NameSet
55 intersectsNameSet :: NameSet -> NameSet -> Bool -- True if non-empty intersection
56 -- (s1 `intersectsNameSet` s2) doesn't compute s2 if s1 is empty
58 isEmptyNameSet = isEmptyUniqSet
59 emptyNameSet = emptyUniqSet
60 unitNameSet = unitUniqSet
62 addListToNameSet = addListToUniqSet
63 addOneToNameSet = addOneToUniqSet
64 unionNameSets = unionUniqSets
65 unionManyNameSets = unionManyUniqSets
66 minusNameSet = minusUniqSet
67 elemNameSet = elementOfUniqSet
68 nameSetToList = uniqSetToList
69 delFromNameSet = delOneFromUniqSet
70 foldNameSet = foldUniqSet
71 filterNameSet = filterUniqSet
72 intersectNameSet = intersectUniqSets
74 delListFromNameSet set ns = foldl delFromNameSet set ns
76 intersectsNameSet s1 s2 = not (isEmptyNameSet (s1 `intersectNameSet` s2))
80 %************************************************************************
82 \subsection{Free variables}
84 %************************************************************************
86 These synonyms are useful when we are thinking of free variables
89 type FreeVars = NameSet
91 plusFV :: FreeVars -> FreeVars -> FreeVars
92 addOneFV :: FreeVars -> Name -> FreeVars
93 unitFV :: Name -> FreeVars
95 plusFVs :: [FreeVars] -> FreeVars
96 mkFVs :: [Name] -> FreeVars
97 delFV :: Name -> FreeVars -> FreeVars
98 delFVs :: [Name] -> FreeVars -> FreeVars
100 isEmptyFVs :: NameSet -> Bool
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 duDefs :: DefUses -> Defs
149 duDefs dus = foldr get emptyNameSet dus
151 get (Nothing, _u1) d2 = d2
152 get (Just d1, _u1) d2 = d1 `unionNameSets` d2
154 duUses :: DefUses -> Uses
155 -- Just like allUses, but defs are not eliminated
156 duUses dus = foldr get emptyNameSet dus
158 get (_d1, u1) u2 = u1 `unionNameSets` u2
160 allUses :: DefUses -> Uses
161 -- Collect all uses, regardless of
162 -- whether the group is itself used,
163 -- but remove defs on the way
165 = foldr get emptyNameSet dus
167 get (Nothing, rhs_uses) uses = rhs_uses `unionNameSets` uses
168 get (Just defs, rhs_uses) uses = (rhs_uses `unionNameSets` uses)
171 findUses :: DefUses -> Uses -> Uses
172 -- Given some DefUses and some Uses,
173 -- find all the uses, transitively.
174 -- The result is a superset of the input uses;
175 -- and includes things defined in the input DefUses
176 -- (but only if they are used)
180 get (Nothing, rhs_uses) uses
181 = rhs_uses `unionNameSets` uses
182 get (Just defs, rhs_uses) uses
183 | defs `intersectsNameSet` uses -- Used
184 || not (all (reportIfUnused . nameOccName) (nameSetToList defs))
185 -- At least one starts with an "_",
186 -- so treat the group as used
187 = rhs_uses `unionNameSets` uses
188 | otherwise -- No def is used