1 salcianu 1.1.2.1 // LightPAEdgeSet.java, created Fri Jun 30 19:32:01 2000 by salcianu
2 cananian 1.1.2.4 // Copyright (C) 2000 Alexandru SALCIANU <salcianu@retezat.lcs.mit.edu>
3 salcianu 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 salcianu 1.1.2.1 package harpoon.Analysis.PointerAnalysis;
5 salcianu 1.1.2.1
6 salcianu 1.1.2.1 import java.util.Map;
7 salcianu 1.1.2.1 import java.util.Collection;
8 salcianu 1.1.2.1 import java.util.Collections;
9 salcianu 1.1.2.1 import java.util.Iterator;
10 salcianu 1.1.2.1 import java.util.Set;
11 salcianu 1.1.2.1
12 salcianu 1.1.2.1 import harpoon.Util.DataStructs.Relation;
13 salcianu 1.1.2.1 import harpoon.Util.DataStructs.LightRelation;
14 salcianu 1.1.2.1 import harpoon.Util.DataStructs.LightMap;
15 salcianu 1.1.2.1 import harpoon.Util.PredicateWrapper;
16 salcianu 1.1.2.1
17 salcianu 1.1.2.1 import harpoon.Util.Util;
18 salcianu 1.1.2.1
19 salcianu 1.1.2.1 import harpoon.Temp.Temp;
20 salcianu 1.1.2.1
21 salcianu 1.1.2.1
22 salcianu 1.1.2.1 /**
23 salcianu 1.1.2.1 * <code>LightPAEdgeSet</code>
24 salcianu 1.1.2.1 *
25 cananian 1.1.2.4 * @author Alexandru SALCIANU <salcianu@retezat.lcs.mit.edu>
26 cananian 1.8 * @version $Id: LightPAEdgeSet.java,v 1.8 2004/02/08 03:20:02 cananian Exp $
27 salcianu 1.1.2.1 */
28 salcianu 1.1.2.3 public class LightPAEdgeSet extends AbstrPAEdgeSet
29 salcianu 1.1.2.3 implements java.io.Serializable {
30 salcianu 1.1.2.1
31 salcianu 1.1.2.1 private Relation var_edges;
32 salcianu 1.1.2.1 private Map node_edges;
33 salcianu 1.1.2.1
34 salcianu 1.1.2.1
35 salcianu 1.1.2.1 /** Creates a <code>LightPAEdgeSet</code>. */
36 salcianu 1.1.2.1 public LightPAEdgeSet() {
37 salcianu 1.1.2.1 var_edges = new LightRelation();
38 salcianu 1.1.2.1 node_edges = new LightMap();
39 salcianu 1.1.2.1 }
40 salcianu 1.1.2.1
41 salcianu 1.1.2.1
42 salcianu 1.1.2.1 public void addEdge(Temp v, PANode node) {
43 salcianu 1.1.2.1 var_edges.add(v, node);
44 salcianu 1.1.2.1 }
45 salcianu 1.1.2.1
46 salcianu 1.1.2.1
47 salcianu 1.1.2.1 public void addEdges(Temp v, Collection nodes) {
48 salcianu 1.1.2.1 var_edges.addAll(v, nodes);
49 salcianu 1.1.2.1 }
50 salcianu 1.1.2.1
51 salcianu 1.1.2.1
52 salcianu 1.1.2.1 public void removeEdge(Temp v, PANode node) {
53 salcianu 1.1.2.1 var_edges.remove(v, node);
54 salcianu 1.1.2.1 }
55 salcianu 1.1.2.1
56 salcianu 1.1.2.1
57 salcianu 1.1.2.1 public void removeEdges(Temp v) {
58 salcianu 1.1.2.1 var_edges.removeKey(v);
59 salcianu 1.1.2.1 }
60 salcianu 1.1.2.1
61 salcianu 1.1.2.1
62 salcianu 1.1.2.1 public Set pointedNodes(Temp v) {
63 salcianu 1.1.2.1 Set retval = var_edges.getValues(v);
64 salcianu 1.1.2.1 if(retval == null)
65 salcianu 1.1.2.1 retval = Collections.EMPTY_SET;
66 salcianu 1.1.2.1 return retval;
67 salcianu 1.1.2.1 }
68 salcianu 1.1.2.1
69 salcianu 1.1.2.1
70 salcianu 1.1.2.1 public Set allVariables() {
71 salcianu 1.1.2.1 return var_edges.keys();
72 salcianu 1.1.2.1 }
73 salcianu 1.1.2.1
74 salcianu 1.1.2.1
75 salcianu 1.7 public boolean addEdge(PANode node1, String f, PANode node2) {
76 salcianu 1.7 // no edges out of NULL or CONST (const. strings are immutable)
77 salcianu 1.7 if((node1.type == PANode.NULL) ||
78 salcianu 1.7 (node1.type == PANode.CONST)) return false;
79 salcianu 1.7 // edges from LOST to LOST are informationless
80 salcianu 1.7 if(PointerAnalysis.COMPRESS_LOST_NODES &&
81 salcianu 1.7 (node1 == NodeRepository.LOST_SUMMARY) &&
82 salcianu 1.7 (node2 == NodeRepository.LOST_SUMMARY)) return false;
83 salcianu 1.1.2.1 Relation rel = (Relation) node_edges.get(node1);
84 salcianu 1.1.2.1 if(rel == null)
85 salcianu 1.1.2.1 node_edges.put(node1, rel = new LightRelation());
86 salcianu 1.7 return rel.add(f, node2);
87 salcianu 1.1.2.1 }
88 salcianu 1.1.2.1
89 salcianu 1.1.2.1
90 salcianu 1.7 public boolean addEdges(PANode node1, String f, Collection node2s) {
91 salcianu 1.7 // no edges out of NULL or CONST (const. strings are immutable)
92 salcianu 1.7 if((node1.type == PANode.NULL) ||
93 salcianu 1.7 (node1.type == PANode.CONST)) return false;
94 salcianu 1.7 if(node2s.isEmpty()) return false;
95 salcianu 1.7
96 salcianu 1.1.2.1 Relation rel = (Relation) node_edges.get(node1);
97 salcianu 1.1.2.1 if(rel == null)
98 salcianu 1.1.2.1 node_edges.put(node1, rel = new LightRelation());
99 salcianu 1.7
100 salcianu 1.7 boolean result = rel.addAll(f, node2s);
101 salcianu 1.7
102 salcianu 1.7 // edges from LOST to LOST are informationless
103 salcianu 1.7 if((node1 == NodeRepository.LOST_SUMMARY) &&
104 salcianu 1.7 node2s.contains(NodeRepository.LOST_SUMMARY)) {
105 salcianu 1.7 rel.remove(f, NodeRepository.LOST_SUMMARY);
106 salcianu 1.7 if(rel.isEmpty())
107 salcianu 1.7 node_edges.remove(node1);
108 salcianu 1.7 if(node2s.size() == 1) result=false;
109 salcianu 1.7 }
110 salcianu 1.7
111 salcianu 1.7 return result;
112 salcianu 1.1.2.1 }
113 salcianu 1.1.2.1
114 salcianu 1.1.2.1
115 salcianu 1.1.2.1 public void removeEdge(PANode node1, String f, PANode node2) {
116 salcianu 1.1.2.1 Relation rel = (Relation) node_edges.get(node1);
117 salcianu 1.1.2.1 if(rel != null)
118 salcianu 1.1.2.1 rel.remove(f, node2);
119 salcianu 1.1.2.1 }
120 salcianu 1.1.2.1
121 salcianu 1.1.2.1
122 salcianu 1.1.2.1 public void removeEdges(PANode node, String f) {
123 salcianu 1.1.2.1 Relation rel = (Relation) node_edges.get(node);
124 salcianu 1.1.2.1 if(rel != null)
125 salcianu 1.1.2.1 rel.removeKey(f);
126 salcianu 1.1.2.1 }
127 salcianu 1.1.2.1
128 salcianu 1.1.2.1
129 salcianu 1.1.2.1 public void removeEdges(PANode node1) {
130 salcianu 1.1.2.1 node_edges.remove(node1);
131 salcianu 1.1.2.1 }
132 salcianu 1.1.2.1
133 salcianu 1.1.2.1
134 salcianu 1.1.2.1 public Set pointedNodes(PANode node, String f) {
135 salcianu 1.1.2.1 Relation rel = (Relation) node_edges.get(node);
136 salcianu 1.1.2.1 if(rel == null)
137 salcianu 1.1.2.1 return Collections.EMPTY_SET;
138 salcianu 1.1.2.1 Set retval = rel.getValues(f);
139 salcianu 1.1.2.1 if(retval == null)
140 salcianu 1.1.2.1 return Collections.EMPTY_SET;
141 salcianu 1.1.2.1 return retval;
142 salcianu 1.1.2.1 }
143 salcianu 1.1.2.1
144 salcianu 1.1.2.1
145 salcianu 1.1.2.1 public Set pointedNodes(PANode node) {
146 salcianu 1.1.2.1 Relation rel = (Relation) node_edges.get(node);
147 salcianu 1.1.2.1 if(rel == null)
148 salcianu 1.1.2.1 return Collections.EMPTY_SET;
149 salcianu 1.1.2.1 return rel.values();
150 salcianu 1.1.2.1 }
151 salcianu 1.1.2.1
152 salcianu 1.1.2.1
153 salcianu 1.1.2.1 public Set allFlagsForNode(PANode node) {
154 salcianu 1.1.2.1 Relation rel = (Relation) node_edges.get(node);
155 salcianu 1.1.2.1 if(rel == null)
156 salcianu 1.1.2.1 return Collections.EMPTY_SET;
157 salcianu 1.1.2.1 return rel.keys();
158 salcianu 1.1.2.1 }
159 salcianu 1.1.2.1
160 salcianu 1.1.2.1
161 salcianu 1.1.2.1 public Set allSourceNodes() {
162 salcianu 1.1.2.1 return node_edges.keySet();
163 salcianu 1.1.2.1 }
164 salcianu 1.1.2.1
165 salcianu 1.1.2.1
166 salcianu 1.1.2.1 public void forAllPointedNodes(PANode node, PANodeVisitor visitor) {
167 salcianu 1.1.2.1 Relation rel = (Relation) node_edges.get(node);
168 salcianu 1.1.2.1 if(rel == null) return;
169 salcianu 1.1.2.1
170 salcianu 1.1.2.1 for(Iterator itf = rel.keys().iterator(); itf.hasNext(); ) {
171 salcianu 1.1.2.1 Set nodes = rel.getValues((String) itf.next());
172 salcianu 1.1.2.1 for(Iterator itn = nodes.iterator(); itn.hasNext(); )
173 salcianu 1.1.2.1 visitor.visit((PANode) itn.next());
174 salcianu 1.1.2.1 }
175 salcianu 1.1.2.1 }
176 salcianu 1.1.2.1
177 salcianu 1.1.2.1
178 salcianu 1.1.2.1 public void forAllEdges(PANode node, PAEdgeVisitor visitor) {
179 salcianu 1.1.2.1 Relation rel = (Relation) node_edges.get(node);
180 salcianu 1.1.2.1 if(rel == null) return;
181 salcianu 1.1.2.1
182 cananian 1.8 for(Object fO : rel.keys()) {
183 cananian 1.8 String f = (String) fO;
184 salcianu 1.1.2.1 Set nodes = rel.getValues(f);
185 salcianu 1.1.2.1 for(Iterator itn = nodes.iterator(); itn.hasNext(); )
186 salcianu 1.1.2.1 visitor.visit(node, f, (PANode) itn.next());
187 salcianu 1.1.2.1 }
188 salcianu 1.1.2.1 }
189 salcianu 1.1.2.1
190 salcianu 1.1.2.1
191 salcianu 1.1.2.1 protected PAEdgeSet getEmptyPAEdgeSet() {
192 salcianu 1.1.2.1 return new LightPAEdgeSet();
193 salcianu 1.1.2.1 }
194 salcianu 1.1.2.1
195 salcianu 1.1.2.1
196 salcianu 1.1.2.1 public void copyEdges(PANode node, PAEdgeSet dest_es) {
197 salcianu 1.6 // for efficiency reasons, treat only the homogenous case
198 cananian 1.3.2.1 assert dest_es instanceof LightPAEdgeSet;
199 salcianu 1.1.2.1 LightPAEdgeSet es2 = (LightPAEdgeSet) dest_es;
200 salcianu 1.6 if(node_edges.containsKey(node)) {
201 salcianu 1.6 es2.node_edges.put(node,
202 salcianu 1.6 ((LightRelation) node_edges.get(node)).clone());
203 salcianu 1.1.2.1 }
204 salcianu 1.1.2.1 }
205 salcianu 1.1.2.1
206 salcianu 1.1.2.1
207 salcianu 1.1.2.1 public void remove(final Set set) {
208 salcianu 1.1.2.1 // 1. remove the var edges terminated into a node from set
209 salcianu 1.1.2.1 PredicateWrapper predicate = new PredicateWrapper() {
210 salcianu 1.1.2.1 public boolean check(Object o) {
211 salcianu 1.1.2.1 return set.contains(o);
212 salcianu 1.1.2.1 }
213 salcianu 1.1.2.1 };
214 salcianu 1.1.2.1 var_edges.removeValues(predicate);
215 salcianu 1.1.2.1
216 salcianu 1.1.2.1 // 2. remove the node edges involving at least one node from set
217 salcianu 1.1.2.1 // 2.1 remove the edges starting from a node from set
218 salcianu 1.1.2.1 for(Iterator it = set.iterator(); it.hasNext(); )
219 salcianu 1.1.2.1 removeEdges((PANode) it.next());
220 salcianu 1.1.2.1 // 2.2 remove the edges ending in a node from set
221 cananian 1.8 for(Object nodeO : node_edges.keySet()) {
222 cananian 1.8 PANode node = (PANode) nodeO;
223 salcianu 1.1.2.1 Relation rel = (Relation) node_edges.get(node);
224 salcianu 1.1.2.1 rel.removeValues(predicate);
225 salcianu 1.1.2.1 if(rel.isEmpty())
226 salcianu 1.1.2.1 node_edges.remove(node);
227 salcianu 1.1.2.1 }
228 salcianu 1.1.2.1 }
229 salcianu 1.1.2.1
230 salcianu 1.1.2.1
231 salcianu 1.7 public void union(PAEdgeSet edges2, Set ppgRoots) {
232 salcianu 1.1.2.1 // for efficiency reasons, treat only the homogeneous case
233 salcianu 1.1.2.1 if(!(edges2 instanceof LightPAEdgeSet))
234 salcianu 1.1.2.1 throw new UnsupportedOperationException();
235 salcianu 1.1.2.1
236 salcianu 1.1.2.1 LightPAEdgeSet les2 = (LightPAEdgeSet) edges2;
237 salcianu 1.1.2.1
238 salcianu 1.1.2.1 // union of the var edges
239 salcianu 1.1.2.1 var_edges.union(les2.var_edges);
240 salcianu 1.1.2.1
241 salcianu 1.1.2.1 // union of the node edges
242 cananian 1.8 for(Object nodeO : les2.node_edges.keySet()) {
243 cananian 1.8 PANode node = (PANode) nodeO;
244 salcianu 1.1.2.1 LightRelation rel2 = (LightRelation) les2.node_edges.get(node);
245 salcianu 1.1.2.1 LightRelation rel1 = (LightRelation) node_edges.get(node);
246 salcianu 1.7 if(rel1 == null) {
247 salcianu 1.1.2.1 node_edges.put(node, (LightRelation) rel2.clone());
248 salcianu 1.7 if(ppgRoots != null)
249 salcianu 1.7 ppgRoots.add(node);
250 salcianu 1.7 }
251 salcianu 1.7 else {
252 salcianu 1.7 if(rel1.union(rel2))
253 salcianu 1.7 if(ppgRoots != null)
254 salcianu 1.7 ppgRoots.add(node);
255 salcianu 1.7 }
256 salcianu 1.1.2.1 }
257 salcianu 1.1.2.1 }
258 salcianu 1.1.2.1
259 salcianu 1.1.2.1
260 salcianu 1.1.2.1 public boolean equals(Object o) {
261 salcianu 1.1.2.2 if((o == null) || !(o instanceof PAEdgeSet))
262 salcianu 1.1.2.1 return false;
263 salcianu 1.1.2.1
264 salcianu 1.1.2.1 // for efficiency reasons, treat only the homogeneous case
265 salcianu 1.1.2.1 if(!(o instanceof LightPAEdgeSet))
266 salcianu 1.1.2.1 throw new UnsupportedOperationException();
267 salcianu 1.1.2.1
268 salcianu 1.1.2.1 LightPAEdgeSet les2 = (LightPAEdgeSet) o;
269 salcianu 1.1.2.2
270 salcianu 1.1.2.1 return
271 salcianu 1.1.2.2 var_edges.equals(les2.var_edges) &&
272 salcianu 1.1.2.1 node_edges.equals(les2.node_edges);
273 salcianu 1.1.2.1 }
274 salcianu 1.1.2.1
275 salcianu 1.1.2.1
276 salcianu 1.1.2.1 public int hashCode() {
277 salcianu 1.1.2.1 return var_edges.hashCode() + node_edges.hashCode();
278 salcianu 1.1.2.1 }
279 salcianu 1.1.2.1
280 salcianu 1.1.2.1
281 salcianu 1.1.2.1 public Object clone() {
282 salcianu 1.1.2.1 LightPAEdgeSet newes = (LightPAEdgeSet) super.clone();
283 salcianu 1.1.2.1
284 salcianu 1.1.2.1 newes.var_edges =
285 salcianu 1.1.2.1 (LightRelation) var_edges.clone();
286 salcianu 1.1.2.1
287 salcianu 1.1.2.1 LightMap new_nes = (LightMap) ((LightMap) node_edges).clone();
288 cananian 1.8 for(Object entryO : new_nes.entrySet()) {
289 cananian 1.8 Map.Entry entry = (Map.Entry) entryO;
290 salcianu 1.1.2.1 LightRelation rel =
291 salcianu 1.1.2.1 (LightRelation) ((Relation) entry.getValue()).clone();
292 salcianu 1.1.2.1 entry.setValue(rel);
293 salcianu 1.1.2.1 }
294 salcianu 1.1.2.1 newes.node_edges = new_nes;
295 salcianu 1.1.2.1
296 salcianu 1.1.2.1 return newes;
297 salcianu 1.1.2.1 }
298 salcianu 1.1.2.1
299 cananian 1.2 }