1 cananian 1.1.2.3 // EdgesNCallees.java, created Mon Dec 11 17:58:49 2000 by vivien
2 vivien 1.1.2.1 // Copyright (C)
3 vivien 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 vivien 1.1.2.1 package harpoon.Analysis.PointerAnalysis;
5 vivien 1.1.2.1
6 vivien 1.1.2.1 import java.util.HashSet;
7 vivien 1.1.2.1 import java.util.Set;
8 vivien 1.1.2.1 import java.util.Iterator;
9 vivien 1.1.2.1 import java.util.Map;
10 vivien 1.1.2.1
11 vivien 1.1.2.1 import harpoon.Util.Util;
12 vivien 1.1.2.1
13 vivien 1.1.2.1 import harpoon.Util.DataStructs.Relation;
14 vivien 1.1.2.1 import harpoon.Util.DataStructs.LightRelation;
15 vivien 1.1.2.1 import harpoon.Util.DataStructs.LightMap;
16 vivien 1.1.2.1
17 vivien 1.1.2.1
18 vivien 1.1.2.1 /**
19 vivien 1.1.2.1 * <code>EdgesNCallees</code> models a precedence relation between
20 vivien 1.1.2.1 * (inside or outside) edges and call sites skipped by an on demand
21 vivien 1.1.2.1 * analysis. This precedence relation may be strict or not.
22 vivien 1.1.2.1 */
23 salcianu 1.1.2.2 public class EdgesNCallees implements java.io.Serializable {
24 vivien 1.1.2.1 public static final boolean DEBUG = false;
25 vivien 1.1.2.1
26 vivien 1.1.2.1 // Decide whether we do precise or conservative joins...
27 vivien 1.1.2.1 private static final boolean VERY_PRECISE = false;
28 vivien 1.1.2.1
29 vivien 1.1.2.1 // The data structure itself.
30 vivien 1.1.2.1 public Map edges;
31 vivien 1.1.2.1
32 vivien 1.1.2.1 // Flag which specifies if the precedence relation is an ``always
33 vivien 1.1.2.1 // precedes'' relation (strict = true), or a ``may be precedes''
34 vivien 1.1.2.1 // relation.
35 vivien 1.1.2.1 private boolean strict = true;
36 vivien 1.1.2.1
37 vivien 1.1.2.1
38 vivien 1.1.2.1 /** Return the type of the precedence relation. true means "always
39 vivien 1.1.2.1 * precedes".
40 vivien 1.1.2.1 */
41 vivien 1.1.2.1 public boolean strict()
42 vivien 1.1.2.1 {
43 vivien 1.1.2.1 return strict;
44 vivien 1.1.2.1 }
45 vivien 1.1.2.1
46 vivien 1.1.2.1
47 cananian 1.4 /** Creates a <code>EdgesNCallees</code> coding a strict precedence
48 vivien 1.1.2.1 * relation.*/
49 vivien 1.1.2.1 public EdgesNCallees(){
50 vivien 1.1.2.1 edges = new LightMap();
51 vivien 1.1.2.1 strict = true;
52 vivien 1.1.2.1 }
53 vivien 1.1.2.1
54 vivien 1.1.2.1
55 cananian 1.4 /** Creates a <code>EdgesNCallees</code> coding a strict precedence
56 vivien 1.1.2.1 * relation iff the argument is true.*/
57 vivien 1.1.2.1 public EdgesNCallees(boolean strictness){
58 vivien 1.1.2.1 edges = new LightMap();
59 vivien 1.1.2.1 strict = strictness;
60 vivien 1.1.2.1 }
61 vivien 1.1.2.1
62 vivien 1.1.2.1
63 cananian 1.4 /** Add the <code>callees</code> to the precedence relation of the
64 cananian 1.4 * edge from a node in <code>heads</code> to a node in
65 cananian 1.4 * <code>tails</code> via the field <code>f</code>, according to
66 vivien 1.1.2.1 * the precedence policy (strict or not). */
67 vivien 1.1.2.1 public void add(Set heads, String f, Set tails, Set callees)
68 vivien 1.1.2.1 {
69 vivien 1.1.2.1 if (callees==null) return;
70 vivien 1.1.2.1
71 vivien 1.1.2.1 for(Iterator h_it=heads.iterator(); h_it.hasNext(); )
72 vivien 1.1.2.1 add((PANode)h_it.next(), f, tails, callees);
73 vivien 1.1.2.1 }
74 vivien 1.1.2.1
75 vivien 1.1.2.1
76 cananian 1.4 /** Add the <code>callees</code> to the precedence relation of the
77 cananian 1.4 * edge from a node in <code>heads</code> to <code>tail</code> via
78 cananian 1.4 * the field <code>f</code>, according to the precedence policy
79 vivien 1.1.2.1 * (strict or not). */
80 vivien 1.1.2.1 public void add(Set heads, String f, PANode tail, Set callees)
81 vivien 1.1.2.1 {
82 vivien 1.1.2.1 if (callees==null) return;
83 vivien 1.1.2.1
84 vivien 1.1.2.1 for(Iterator h_it=heads.iterator(); h_it.hasNext(); )
85 vivien 1.1.2.1 add((PANode)h_it.next(), f, tail, callees);
86 vivien 1.1.2.1 }
87 vivien 1.1.2.1
88 vivien 1.1.2.1
89 cananian 1.4 /** Add the <code>callees</code> to the precedence relation of the
90 cananian 1.4 * edge from <code>head</code> to <code>tail</code> via the field
91 cananian 1.4 * <code>f</code>, according to the precedence policy (strict or
92 vivien 1.1.2.1 * not). */
93 vivien 1.1.2.1 public void add(PANode head, String f, PANode tail, Set callees)
94 vivien 1.1.2.1 {
95 vivien 1.1.2.1 if (callees==null) return;
96 vivien 1.1.2.1
97 vivien 1.1.2.1 Map from_head = (Map) edges.get(head);
98 vivien 1.1.2.1
99 vivien 1.1.2.1 // To avoid the empty set problem
100 vivien 1.1.2.1 HashSet holes = new HashSet(callees);
101 vivien 1.1.2.1 holes.add(ODPointerAnalysis.BottomHole);
102 vivien 1.1.2.1 //tbu the bottomhole should be an element of MethodHole class
103 vivien 1.1.2.1
104 vivien 1.1.2.1 if (from_head==null){
105 vivien 1.1.2.1 Relation tails = (Relation) new LightRelation();
106 vivien 1.1.2.1 tails.addAll(tail,holes);
107 vivien 1.1.2.1 from_head = new LightMap();
108 vivien 1.1.2.1 from_head.put(f,tails);
109 vivien 1.1.2.1 edges.put(head,from_head);
110 vivien 1.1.2.1 }
111 vivien 1.1.2.1 else{
112 vivien 1.1.2.1 Relation tails = (Relation) from_head.get(f);
113 vivien 1.1.2.1 if (tails==null){
114 vivien 1.1.2.1 tails = new LightRelation();
115 vivien 1.1.2.1 tails.addAll(tail,holes);
116 vivien 1.1.2.1 from_head.put(f,tails);
117 vivien 1.1.2.1 }
118 vivien 1.1.2.1 else{
119 vivien 1.1.2.1 if (strict){
120 vivien 1.1.2.1 Set sites = tails.getValues(tail);
121 vivien 1.1.2.1 if (sites==null){
122 vivien 1.1.2.1 tails.addAll(tail,holes);
123 vivien 1.1.2.1 }
124 vivien 1.1.2.1 else{
125 vivien 1.1.2.1 HashSet for_trash = new HashSet();
126 vivien 1.1.2.1 for(Iterator it=sites.iterator();it.hasNext();){
127 vivien 1.1.2.1 Object hole = it.next();
128 vivien 1.1.2.1 if (!holes.contains(hole)) for_trash.add(hole);
129 vivien 1.1.2.1 }
130 vivien 1.1.2.1 tails.removeAll(tail,for_trash);
131 vivien 1.1.2.1 }
132 vivien 1.1.2.1 }
133 vivien 1.1.2.1 else{
134 vivien 1.1.2.1 tails.addAll(tail,holes);
135 vivien 1.1.2.1 }
136 vivien 1.1.2.1 }
137 vivien 1.1.2.1 }
138 vivien 1.1.2.1 if (DEBUG){
139 vivien 1.1.2.1 System.out.println("New relation " + toString());
140 vivien 1.1.2.1 }
141 vivien 1.1.2.1 }
142 vivien 1.1.2.1
143 vivien 1.1.2.1
144 cananian 1.4 /** Add the <code>callees</code> to the precedence relation of all
145 cananian 1.4 * the edges from <code>head</code> to a node in
146 cananian 1.4 * <code>tails</code> via the field <code>f</code>, according to
147 vivien 1.1.2.1 * the precedence policy (strict or not). */
148 vivien 1.1.2.1 public void add(PANode head, String f, Set tails, Set callees)
149 vivien 1.1.2.1 {
150 vivien 1.1.2.1 if (callees==null) return;
151 vivien 1.1.2.1
152 vivien 1.1.2.1 if (DEBUG)
153 vivien 1.1.2.1 {
154 vivien 1.1.2.1 System.out.println("EdgesNCallees.add: " +
155 vivien 1.1.2.1 head +" "+ f +" "+ tails
156 vivien 1.1.2.1 + " (" + callees + " ) to \n"
157 vivien 1.1.2.1 + toString());
158 vivien 1.1.2.1 }
159 vivien 1.1.2.1
160 vivien 1.1.2.1 Map from_head = (Map) edges.get(head);
161 vivien 1.1.2.1
162 vivien 1.1.2.1 // To avoid the empty set problem
163 vivien 1.1.2.1 HashSet holes = new HashSet(callees);
164 vivien 1.1.2.1 holes.add(ODPointerAnalysis.BottomHole);
165 vivien 1.1.2.1 //tbu the bottomhole should be an element of MethodHole class
166 vivien 1.1.2.1
167 vivien 1.1.2.1 if (from_head==null){
168 vivien 1.1.2.1 from_head = new LightMap();
169 vivien 1.1.2.1 Relation tail_rel = (Relation) new LightRelation();
170 cananian 1.6 for(Object tailO : tails){
171 cananian 1.6 PANode tail = (PANode) tailO;
172 vivien 1.1.2.1 tail_rel.addAll(tail,holes);
173 vivien 1.1.2.1 }
174 vivien 1.1.2.1 from_head.put(f,tail_rel);
175 vivien 1.1.2.1 edges.put(head,from_head);
176 vivien 1.1.2.1 }
177 vivien 1.1.2.1 else{
178 vivien 1.1.2.1 Relation tail_rel = (Relation) from_head.get(f);
179 vivien 1.1.2.1 if (tail_rel==null){
180 vivien 1.1.2.1 tail_rel = new LightRelation();
181 cananian 1.6 for(Object tailO : tails){
182 cananian 1.6 PANode tail = (PANode) tailO;
183 vivien 1.1.2.1 tail_rel.addAll(tail,holes);
184 vivien 1.1.2.1 }
185 vivien 1.1.2.1 from_head.put(f,tail_rel);
186 vivien 1.1.2.1 }
187 vivien 1.1.2.1 else{
188 vivien 1.1.2.1 if (strict){
189 cananian 1.6 for(Object tailO : tails){
190 cananian 1.6 PANode tail = (PANode) tailO;
191 vivien 1.1.2.1 Set sites = tail_rel.getValues(tail);
192 vivien 1.1.2.1 if (sites==null){
193 vivien 1.1.2.1 tail_rel.addAll(tail,holes);
194 vivien 1.1.2.1 }
195 vivien 1.1.2.1 else{
196 vivien 1.1.2.1 HashSet for_trash = new HashSet();
197 vivien 1.1.2.1 for(Iterator it=sites.iterator();it.hasNext();){
198 vivien 1.1.2.1 Object hole = it.next();
199 vivien 1.1.2.1 if (!holes.contains(hole)) for_trash.add(hole);
200 vivien 1.1.2.1 }
201 vivien 1.1.2.1 tail_rel.removeAll(tail,for_trash);
202 vivien 1.1.2.1 }
203 vivien 1.1.2.1 }
204 vivien 1.1.2.1 }
205 vivien 1.1.2.1 else{
206 vivien 1.1.2.1 for(Iterator t_it=tails.iterator(); t_it.hasNext(); )
207 vivien 1.1.2.1 tail_rel.addAll(t_it.next(),holes);
208 vivien 1.1.2.1 }
209 vivien 1.1.2.1 }
210 vivien 1.1.2.1 }
211 vivien 1.1.2.1 if (DEBUG){
212 vivien 1.1.2.1 System.out.println("New relation " + toString());
213 vivien 1.1.2.1 }
214 vivien 1.1.2.1 }
215 vivien 1.1.2.1
216 vivien 1.1.2.1
217 cananian 1.4 /** Set the <code>callees</code> to the precedence relation of the
218 cananian 1.4 * edge from <code>head</code> to <code>tail</code> via the field
219 cananian 1.4 * <code>f</code>.
220 vivien 1.1.2.1 */
221 vivien 1.1.2.1 public void set(PANode head, String f, PANode tail, Set callees)
222 vivien 1.1.2.1 {
223 vivien 1.1.2.1 if (callees==null) return;
224 vivien 1.1.2.1
225 vivien 1.1.2.1 Map from_head = (Map) edges.get(head);
226 vivien 1.1.2.1
227 vivien 1.1.2.1 // To avoid the empty set problem
228 vivien 1.1.2.1 HashSet holes = new HashSet(callees);
229 vivien 1.1.2.1 holes.add(ODPointerAnalysis.BottomHole);
230 vivien 1.1.2.1 //tbu the bottomhole should be an element of MethodHole class
231 vivien 1.1.2.1
232 vivien 1.1.2.1 if (from_head==null){
233 vivien 1.1.2.1 Relation tails = (Relation) new LightRelation();
234 vivien 1.1.2.1 tails.addAll(tail,holes);
235 vivien 1.1.2.1 from_head = new LightMap();
236 vivien 1.1.2.1 from_head.put(f,tails);
237 vivien 1.1.2.1 edges.put(head,from_head);
238 vivien 1.1.2.1 }
239 vivien 1.1.2.1 else{
240 vivien 1.1.2.1 Relation tails = (Relation) from_head.get(f);
241 vivien 1.1.2.1 if (tails==null){
242 vivien 1.1.2.1 tails = new LightRelation();
243 vivien 1.1.2.1 tails.addAll(tail,holes);
244 vivien 1.1.2.1 from_head.put(f,tails);
245 vivien 1.1.2.1 }
246 vivien 1.1.2.1 else{
247 vivien 1.1.2.1 tails.removeKey(tail);
248 vivien 1.1.2.1 tails.addAll(tail, holes);
249 vivien 1.1.2.1 }
250 vivien 1.1.2.1 }
251 vivien 1.1.2.1 }
252 vivien 1.1.2.1
253 vivien 1.1.2.1
254 vivien 1.1.2.1 /** Return the set of callees in relation with the edges from
255 cananian 1.4 * <code>head</code> to <code>tail</code> via the field
256 cananian 1.4 * <code>f</code>.*/
257 vivien 1.1.2.1 public Set callees(PANode head, String f, PANode tail)
258 vivien 1.1.2.1 {
259 vivien 1.1.2.1 Map from_head = (Map) edges.get(head);
260 vivien 1.1.2.1
261 vivien 1.1.2.1 if (from_head==null){
262 vivien 1.1.2.1 System.err.println("Error in EdgesNCallees.callees (1): "
263 vivien 1.1.2.1 + "Map should not be null");
264 vivien 1.1.2.1 System.out.println("Error in EdgesNCallees.callees (1): "
265 vivien 1.1.2.1 + "Map should not be null");
266 vivien 1.1.2.1 System.out.println("Problem for: " + head + " --" + f + "-> " + tail);
267 vivien 1.1.2.1 System.out.println("in " + this);
268 vivien 1.1.2.1
269 vivien 1.1.2.1 if(DEBUG){
270 vivien 1.1.2.1 System.out.println(head + " - " + f + " -> " + tail);
271 vivien 1.1.2.1 System.out.println(" " + head + "(" + head.details() + ")");
272 vivien 1.1.2.1 if (head.isCSSpec()){
273 vivien 1.1.2.1 System.out.println("This is a CS specialization");
274 vivien 1.1.2.1 }
275 vivien 1.1.2.1 else{
276 vivien 1.1.2.1 System.out.println("This is **NOT** a CS specialization");
277 vivien 1.1.2.1 }
278 vivien 1.1.2.1 System.out.println(" " + head.getCSParent());
279 vivien 1.1.2.1 System.out.println(" " + head.getTSParent());
280 vivien 1.1.2.1 System.out.println(toString());
281 vivien 1.1.2.1 }
282 vivien 1.1.2.1 return null;
283 vivien 1.1.2.1 }
284 vivien 1.1.2.1 else{
285 vivien 1.1.2.1 Relation tails = (Relation) from_head.get(f);
286 vivien 1.1.2.1 if (tails==null){
287 vivien 1.1.2.1 System.err.println("Error in EdgesNCallees.callees (2): "
288 vivien 1.1.2.1 + "Relation should not be null");
289 vivien 1.1.2.1 System.out.println("Error in EdgesNCallees.callees (2): "
290 vivien 1.1.2.1 + "Relation should not be null");
291 vivien 1.1.2.1 if(DEBUG){
292 vivien 1.1.2.1 System.out.println(head + " - " + f + " -> " + tail);
293 vivien 1.1.2.1 System.out.println(" " + head + "(" + head.details()
294 vivien 1.1.2.1 + ")\n " + toString());
295 vivien 1.1.2.1 }
296 vivien 1.1.2.1 return new HashSet();
297 vivien 1.1.2.1 }
298 vivien 1.1.2.1 else
299 vivien 1.1.2.1 return new HashSet(tails.getValues(tail));
300 vivien 1.1.2.1 }
301 vivien 1.1.2.1 }
302 vivien 1.1.2.1
303 vivien 1.1.2.1 /** Same as callees but whithout the error messages (this method
304 vivien 1.1.2.1 * is not used in the same context).
305 vivien 1.1.2.1 */
306 vivien 1.1.2.1 private Set calleessilent(PANode head, String f, PANode tail)
307 vivien 1.1.2.1 {
308 vivien 1.1.2.1 Map from_head = (Map) edges.get(head);
309 vivien 1.1.2.1
310 vivien 1.1.2.1 if (from_head==null){
311 vivien 1.1.2.1 return null;
312 vivien 1.1.2.1 }
313 vivien 1.1.2.1 else{
314 vivien 1.1.2.1 Relation tails = (Relation) from_head.get(f);
315 vivien 1.1.2.1 if (tails==null)
316 vivien 1.1.2.1 return null;
317 vivien 1.1.2.1 else
318 vivien 1.1.2.1 return new HashSet(tails.getValues(tail));
319 vivien 1.1.2.1 }
320 vivien 1.1.2.1 }
321 vivien 1.1.2.1
322 vivien 1.1.2.1
323 vivien 1.1.2.1 /** Removes the MethodHole <code>hole</code> from all the sets of
324 vivien 1.1.2.1 * callees that may contain it.
325 vivien 1.1.2.1 */
326 vivien 1.1.2.1 public void remove(MethodHole hole)
327 vivien 1.1.2.1 {
328 vivien 1.1.2.1 if (edges==null) return;
329 vivien 1.1.2.1
330 cananian 1.6 for(Object n1O : edges.keySet()){
331 cananian 1.6 PANode n1 = (PANode) n1O;
332 vivien 1.1.2.1 Map n1_map = (Map) edges.get(n1);
333 cananian 1.6 for(Object fO : n1_map.keySet()){
334 cananian 1.6 String f = (String) fO;
335 vivien 1.1.2.1 Relation n1_f = (Relation) n1_map.get(f);
336 cananian 1.6 for(Object n2O : n1_f.keys()){
337 cananian 1.6 PANode n2 = (PANode) n2O;
338 vivien 1.1.2.1 n1_f.remove(n2,hole);
339 vivien 1.1.2.1 }
340 vivien 1.1.2.1 }
341 vivien 1.1.2.1 }
342 vivien 1.1.2.1 }
343 vivien 1.1.2.1
344 vivien 1.1.2.1
345 vivien 1.1.2.1 /** Conservative implementation */
346 vivien 1.1.2.1 public void join(Set firstHoles, EdgesNCallees second, Set secondHoles)
347 vivien 1.1.2.1 {
348 vivien 1.1.2.1 if (second==null) return;
349 vivien 1.1.2.1
350 cananian 1.3.2.1 assert strict==second.strict() : "Attempt to join to EdgesNCallees "
351 cananian 1.3.2.1 + "of different types";
352 vivien 1.1.2.1
353 cananian 1.6 for(Object n1O : second.edges.keySet()){
354 cananian 1.6 PANode n1 = (PANode) n1O;
355 vivien 1.1.2.1 Map n1_map = (Map) second.edges.get(n1);
356 vivien 1.1.2.1
357 cananian 1.6 for(Object fO : n1_map.keySet()){
358 cananian 1.6 String f = (String) fO;
359 vivien 1.1.2.1 Relation n1_f = (Relation) n1_map.get(f);
360 vivien 1.1.2.1
361 cananian 1.6 for(Object n2O : n1_f.keys()){
362 cananian 1.6 PANode n2 = (PANode) n2O;
363 vivien 1.1.2.1 if (strict){
364 vivien 1.1.2.1 HashSet callees_1 = (HashSet) callees(n1, f, n2);
365 vivien 1.1.2.1 if((callees_1==null)||(callees_1.isEmpty())){
366 vivien 1.1.2.1 // simple addition as the edge does not
367 vivien 1.1.2.1 // exist in the current object.
368 vivien 1.1.2.1 add(n1, f, n2, n1_f.getValues(n2));
369 vivien 1.1.2.1 }
370 vivien 1.1.2.1 else{
371 vivien 1.1.2.1 HashSet callees_2 = (HashSet) n1_f.getValues(n2);
372 vivien 1.1.2.1
373 vivien 1.1.2.1 // Intersection
374 vivien 1.1.2.1 HashSet intersect = (HashSet) callees_1.clone();
375 vivien 1.1.2.1 intersect.retainAll(callees_2);
376 vivien 1.1.2.1
377 vivien 1.1.2.1 // The holes in the current object but
378 vivien 1.1.2.1 // unknown in "second" should be kept.
379 vivien 1.1.2.1 HashSet firstMinusSecond = (HashSet) callees_1.clone();
380 vivien 1.1.2.1 firstMinusSecond.removeAll(callees_2);
381 vivien 1.1.2.1
382 vivien 1.1.2.1 // Conversely
383 vivien 1.1.2.1 callees_2.removeAll(callees_1);
384 vivien 1.1.2.1
385 vivien 1.1.2.1 // What should be kept, other than the
386 vivien 1.1.2.1 // intersection
387 vivien 1.1.2.1 firstMinusSecond.addAll(callees_2);
388 vivien 1.1.2.1
389 vivien 1.1.2.1 // The final set
390 vivien 1.1.2.1 firstMinusSecond.addAll(intersect);
391 vivien 1.1.2.1
392 vivien 1.1.2.1 set(n1, f, n2, firstMinusSecond);
393 vivien 1.1.2.1 }
394 vivien 1.1.2.1 }
395 vivien 1.1.2.1 else
396 vivien 1.1.2.1 add(n1, f, n2, n1_f.getValues(n2));
397 vivien 1.1.2.1 }
398 vivien 1.1.2.1 }
399 vivien 1.1.2.1 }
400 vivien 1.1.2.1 }
401 vivien 1.1.2.1
402 vivien 1.1.2.1 /** Conservative implementation */
403 vivien 1.1.2.1 public void joinbis(EdgesNCallees second)
404 vivien 1.1.2.1 {
405 vivien 1.1.2.1 if (second==null) return;
406 vivien 1.1.2.1
407 cananian 1.3.2.1 assert strict==second.strict() : "Attempt to join to EdgesNCallees "
408 cananian 1.3.2.1 + "of different types";
409 vivien 1.1.2.1
410 cananian 1.6 for(Object n1O : second.edges.keySet()){
411 cananian 1.6 PANode n1 = (PANode) n1O;
412 vivien 1.1.2.1 Map n1_map = (Map) second.edges.get(n1);
413 vivien 1.1.2.1
414 cananian 1.6 for(Object fO : n1_map.keySet()){
415 cananian 1.6 String f = (String) fO;
416 vivien 1.1.2.1 Relation n1_f = (Relation) n1_map.get(f);
417 vivien 1.1.2.1
418 cananian 1.6 for(Object n2O : n1_f.keys()){
419 cananian 1.6 PANode n2 = (PANode) n2O;
420 vivien 1.1.2.1 if (strict){
421 vivien 1.1.2.1 // A real implementation should be more precise than that !
422 vivien 1.1.2.1 add(n1, f, n2, n1_f.getValues(n2));
423 vivien 1.1.2.1 }
424 vivien 1.1.2.1 else
425 vivien 1.1.2.1 add(n1, f, n2, n1_f.getValues(n2));
426 vivien 1.1.2.1 }
427 vivien 1.1.2.1 }
428 vivien 1.1.2.1 }
429 vivien 1.1.2.1 }
430 vivien 1.1.2.1
431 vivien 1.1.2.1
432 vivien 1.1.2.1 /** Conservative implementation */
433 vivien 1.1.2.1 public void join(EdgesNCallees second, Map holeConversion,
434 vivien 1.1.2.1 Set firstholes, Set secondholes,
435 vivien 1.1.2.1 Set control)
436 vivien 1.1.2.1 {
437 vivien 1.1.2.1 if (second==null) return;
438 vivien 1.1.2.1
439 cananian 1.3.2.1 assert strict==second.strict() : "Attempt to join to EdgesNCallees "
440 cananian 1.3.2.1 + "of different types";
441 vivien 1.1.2.1
442 cananian 1.6 for(Object n1O : second.edges.keySet()){
443 cananian 1.6 PANode n1 = (PANode) n1O;
444 vivien 1.1.2.1 Map n1_map = (Map) second.edges.get(n1);
445 vivien 1.1.2.1
446 cananian 1.6 for(Object fO : n1_map.keySet()){
447 cananian 1.6 String f = (String) fO;
448 vivien 1.1.2.1 Relation n1_f = (Relation) n1_map.get(f);
449 vivien 1.1.2.1
450 cananian 1.6 for(Object n2O : n1_f.keys()){
451 cananian 1.6 PANode n2 = (PANode) n2O;
452 vivien 1.1.2.1 if (strict){
453 vivien 1.1.2.1 if (VERY_PRECISE){
454 vivien 1.1.2.1 HashSet callees_1 = (HashSet) calleessilent(n1, f, n2);
455 vivien 1.1.2.1 if((callees_1==null)||(callees_1.isEmpty())){
456 vivien 1.1.2.1 // simple addition as the edge does not
457 vivien 1.1.2.1 // exist in the current object.
458 vivien 1.1.2.1 set(n1, f, n2, project(n1_f.getValues(n2), holeConversion));
459 vivien 1.1.2.1 }
460 vivien 1.1.2.1 else{
461 vivien 1.1.2.1 HashSet callees_2 =
462 vivien 1.1.2.1 (HashSet) project(n1_f.getValues(n2), holeConversion);
463 vivien 1.1.2.1
464 vivien 1.1.2.1 // Intersection
465 vivien 1.1.2.1 HashSet intersect = (HashSet) callees_1.clone();
466 vivien 1.1.2.1 intersect.retainAll(callees_2);
467 vivien 1.1.2.1
468 vivien 1.1.2.1 if ((intersect.size()!=callees_1.size())||
469 vivien 1.1.2.1 (intersect.size()!=callees_2.size())){
470 vivien 1.1.2.1 // The holes in the current object but
471 vivien 1.1.2.1 // unknown in "second" should be kept.
472 vivien 1.1.2.1 callees_1.removeAll(secondholes);
473 vivien 1.1.2.1
474 vivien 1.1.2.1 // Conversely
475 vivien 1.1.2.1 callees_2.removeAll(firstholes);
476 vivien 1.1.2.1
477 vivien 1.1.2.1 // What should be kept, other than the
478 vivien 1.1.2.1 // intersection
479 vivien 1.1.2.1 intersect.addAll(callees_2);
480 vivien 1.1.2.1
481 vivien 1.1.2.1 // The final set
482 vivien 1.1.2.1 intersect.addAll(callees_1);
483 vivien 1.1.2.1 }
484 vivien 1.1.2.1
485 vivien 1.1.2.1 set(n1, f, n2, intersect);
486 vivien 1.1.2.1 }
487 vivien 1.1.2.1 }
488 vivien 1.1.2.1 else{
489 vivien 1.1.2.1 add(n1, f, n2,
490 vivien 1.1.2.1 project(n1_f.getValues(n2), holeConversion));
491 vivien 1.1.2.1 }
492 vivien 1.1.2.1 }
493 vivien 1.1.2.1 else
494 vivien 1.1.2.1 add(n1, f, n2, project(n1_f.getValues(n2), holeConversion));
495 vivien 1.1.2.1 }
496 vivien 1.1.2.1 }
497 vivien 1.1.2.1 }
498 vivien 1.1.2.1 }
499 vivien 1.1.2.1
500 vivien 1.1.2.1 /** Simply clone an <code>EdgesNCallees</code> object.
501 vivien 1.1.2.1 */
502 vivien 1.1.2.1 public Object clone()
503 vivien 1.1.2.1 {
504 cananian 1.3.2.1 assert edges!=null : ("Problem in EdgesNCallees.clone: null map");
505 vivien 1.1.2.1
506 vivien 1.1.2.1 EdgesNCallees new_enc = new EdgesNCallees(strict);
507 vivien 1.1.2.1
508 cananian 1.6 for(Object n1O : edges.keySet()){
509 cananian 1.6 PANode n1 = (PANode) n1O;
510 vivien 1.1.2.1 Map n1_map = (Map) edges.get(n1);
511 vivien 1.1.2.1 Map new_n1_map = new LightMap();
512 vivien 1.1.2.1
513 cananian 1.6 for(Object fO : n1_map.keySet()){
514 cananian 1.6 String f = (String) fO;
515 vivien 1.1.2.1 Relation n1_f = (Relation) n1_map.get(f);
516 vivien 1.1.2.1 Relation new_n1_f = new LightRelation();
517 vivien 1.1.2.1
518 vivien 1.1.2.1 for(Iterator it_n2=n1_f.keys().iterator(); it_n2.hasNext(); ){
519 vivien 1.1.2.1 Object obj = it_n2.next();
520 vivien 1.1.2.1 PANode n2 = (PANode) obj;
521 vivien 1.1.2.1 new_n1_f.addAll(n2, n1_f.getValues(n2));
522 vivien 1.1.2.1 }
523 vivien 1.1.2.1 new_n1_map.put(f,new_n1_f);
524 vivien 1.1.2.1 }
525 vivien 1.1.2.1 new_enc.edges.put(n1,new_n1_map);
526 vivien 1.1.2.1 }
527 vivien 1.1.2.1 return new_enc;
528 vivien 1.1.2.1 }
529 vivien 1.1.2.1
530 vivien 1.1.2.1
531 vivien 1.1.2.1 /** clone the <code>EdgesNCallees</code> while transposing the
532 vivien 1.1.2.1 * callees using the <code>map</code>.
533 vivien 1.1.2.1 */
534 vivien 1.1.2.1 public EdgesNCallees clone(Map hole_conversion)
535 vivien 1.1.2.1 {
536 cananian 1.3.2.1 assert edges!=null : ("Problem in EdgesNCallees.clone: null map");
537 vivien 1.1.2.1
538 vivien 1.1.2.1 EdgesNCallees new_enc = new EdgesNCallees(strict);
539 vivien 1.1.2.1
540 cananian 1.6 for(Object n1O : edges.keySet()){
541 cananian 1.6 PANode n1 = (PANode) n1O;
542 vivien 1.1.2.1 Map n1_map = (Map) edges.get(n1);
543 vivien 1.1.2.1 Map new_n1_map = new LightMap();
544 vivien 1.1.2.1
545 cananian 1.6 for(Object fO : n1_map.keySet()){
546 cananian 1.6 String f = (String) fO;
547 vivien 1.1.2.1 Relation n1_f = (Relation) n1_map.get(f);
548 vivien 1.1.2.1 Relation new_n1_f = new LightRelation();
549 vivien 1.1.2.1
550 vivien 1.1.2.1 for(Iterator it_n2=n1_f.keys().iterator(); it_n2.hasNext(); ){
551 vivien 1.1.2.1 Object obj = it_n2.next();
552 vivien 1.1.2.1 PANode n2 = (PANode) obj;
553 cananian 1.6 for(Object mhO : n1_f.getValues(n2)){
554 cananian 1.6 MethodHole mh = (MethodHole) mhO;
555 vivien 1.1.2.1 if (mh==ODPointerAnalysis.BottomHole)
556 vivien 1.1.2.1 new_n1_f.add(n2,ODPointerAnalysis.BottomHole);
557 vivien 1.1.2.1 else {
558 vivien 1.1.2.1 if (hole_conversion.get(mh)==null){
559 vivien 1.1.2.1 System.err.println("EdgesNCallees.clone: " +
560 vivien 1.1.2.1 "no conversion for " + mh);
561 vivien 1.1.2.1 System.out.println("EdgesNCallees.clone: " +
562 vivien 1.1.2.1 "no conversion for " + mh
563 vivien 1.1.2.1 + " in " + hole_conversion);
564 vivien 1.1.2.1 }
565 vivien 1.1.2.1 else
566 vivien 1.1.2.1 new_n1_f.add(n2,hole_conversion.get(mh));
567 vivien 1.1.2.1 }
568 vivien 1.1.2.1 }
569 vivien 1.1.2.1 }
570 vivien 1.1.2.1 new_n1_map.put(f,new_n1_f);
571 vivien 1.1.2.1 }
572 vivien 1.1.2.1 new_enc.edges.put(n1,new_n1_map);
573 vivien 1.1.2.1 }
574 vivien 1.1.2.1 return new_enc;
575 vivien 1.1.2.1 }
576 vivien 1.1.2.1
577 vivien 1.1.2.1
578 vivien 1.1.2.1
579 vivien 1.1.2.1 /** clone the <code>EdgesNCallees</code> while transposing the
580 vivien 1.1.2.1 * callees using the first <code>map</code>, and the nodes using
581 vivien 1.1.2.1 * the second one.
582 vivien 1.1.2.1 */
583 vivien 1.1.2.1
584 vivien 1.1.2.1 public EdgesNCallees clone(Map hole_conversion, Map node_conversion)
585 vivien 1.1.2.1 {
586 cananian 1.3.2.1 assert edges!=null : ("Problem in EdgesNCallees.clone: null map");
587 vivien 1.1.2.1
588 vivien 1.1.2.1 EdgesNCallees new_enc = new EdgesNCallees(strict);
589 vivien 1.1.2.1
590 cananian 1.6 for(Object n1O : edges.keySet()){
591 cananian 1.6 PANode n1 = (PANode) n1O;
592 vivien 1.1.2.1 PANode new_n1 = (PANode) node_conversion.get(n1);
593 vivien 1.1.2.1 if (new_n1==null){
594 vivien 1.1.2.1 System.err.println("Error in EdgesNCallees.clone with node_conversion");
595 vivien 1.1.2.1 System.out.println("Error in EdgesNCallees.clone with node_conversion");
596 vivien 1.1.2.1 System.out.println("Node with no translation: " + n1);
597 vivien 1.1.2.1 System.out.println("Map: " + node_conversion);
598 vivien 1.1.2.1 }
599 vivien 1.1.2.1 Map n1_map = (Map) edges.get(n1);
600 vivien 1.1.2.1 Map new_n1_map = new LightMap();
601 vivien 1.1.2.1
602 cananian 1.6 for(Object fO : n1_map.keySet()){
603 cananian 1.6 String f = (String) fO;
604 vivien 1.1.2.1 Relation n1_f = (Relation) n1_map.get(f);
605 vivien 1.1.2.1 Relation new_n1_f = new LightRelation();
606 vivien 1.1.2.1
607 cananian 1.6 for(Object n2O : n1_f.keys()){
608 cananian 1.6 PANode n2 = (PANode) n2O;
609 vivien 1.1.2.1 PANode new_n2 = (PANode) node_conversion.get(n2);
610 vivien 1.1.2.1 if (new_n2==null){
611 vivien 1.1.2.1 System.err.println("Error in EdgesNCallees.clone " +
612 vivien 1.1.2.1 "with node_conversion");
613 vivien 1.1.2.1 System.out.println("Error in EdgesNCallees.clone " +
614 vivien 1.1.2.1 "with node_conversion");
615 vivien 1.1.2.1 System.out.println("Null node " + n2);
616 vivien 1.1.2.1 System.out.println("Map: " + node_conversion);
617 vivien 1.1.2.1 }
618 vivien 1.1.2.1
619 cananian 1.6 for(Object mhO : n1_f.getValues(n2)){
620 cananian 1.6 MethodHole mh = (MethodHole) mhO;
621 vivien 1.1.2.1 if (mh==ODPointerAnalysis.BottomHole)
622 vivien 1.1.2.1 new_n1_f.add(new_n2,ODPointerAnalysis.BottomHole);
623 vivien 1.1.2.1 else {
624 vivien 1.1.2.1 if (hole_conversion.get(mh)==null){
625 vivien 1.1.2.1 System.err.println("EdgesNCallees.clone: " +
626 vivien 1.1.2.1 "no conversion for " + mh
627 vivien 1.1.2.1 + " in " + hole_conversion);
628 vivien 1.1.2.1 System.out.println("EdgesNCallees.clone: " +
629 vivien 1.1.2.1 "no conversion for " + mh
630 vivien 1.1.2.1 + " in " + hole_conversion);
631 vivien 1.1.2.1 }
632 vivien 1.1.2.1 else
633 vivien 1.1.2.1 new_n1_f.add(new_n2,hole_conversion.get(mh));
634 vivien 1.1.2.1 }
635 vivien 1.1.2.1 }
636 vivien 1.1.2.1 }
637 vivien 1.1.2.1 new_n1_map.put(f,new_n1_f);
638 vivien 1.1.2.1 }
639 vivien 1.1.2.1 new_enc.edges.put(new_n1,new_n1_map);
640 vivien 1.1.2.1 }
641 vivien 1.1.2.1 return new_enc;
642 vivien 1.1.2.1 }
643 vivien 1.1.2.1
644 vivien 1.1.2.1
645 vivien 1.1.2.1
646 vivien 1.1.2.1 /** Pretty-print debug function.
647 vivien 1.1.2.1 */
648 vivien 1.1.2.1 public String toString()
649 vivien 1.1.2.1 {
650 vivien 1.1.2.1 return toString("");
651 vivien 1.1.2.1
652 vivien 1.1.2.1 }
653 vivien 1.1.2.1
654 vivien 1.1.2.1 /** Pretty-print debug function.
655 vivien 1.1.2.1 */
656 vivien 1.1.2.1 public String toString(String s)
657 vivien 1.1.2.1 {
658 vivien 1.1.2.1 StringBuffer buffer = new StringBuffer(" EdgesNCallees: " + s);
659 vivien 1.1.2.1
660 vivien 1.1.2.1 if (edges==null) {
661 vivien 1.1.2.1 buffer.append("\n -- empty --\n");
662 vivien 1.1.2.1 return buffer.toString();
663 vivien 1.1.2.1 }
664 vivien 1.1.2.1
665 cananian 1.6 for(Object n1O : edges.keySet()){
666 cananian 1.6 PANode n1 = (PANode) n1O;
667 vivien 1.1.2.1 buffer.append("\n" + n1 + "\t-> ");
668 vivien 1.1.2.1 Map n1_map = (Map) edges.get(n1);
669 vivien 1.1.2.1 boolean firstfield = true;
670 cananian 1.6 for(Object fO : n1_map.keySet()){
671 cananian 1.6 String f = (String) fO;
672 vivien 1.1.2.1 Relation n1_f = (Relation) n1_map.get(f);
673 vivien 1.1.2.1 if (firstfield){
674 vivien 1.1.2.1 buffer.append(f + "\t-> ");
675 vivien 1.1.2.1 firstfield=false;
676 vivien 1.1.2.1 }
677 vivien 1.1.2.1 else
678 vivien 1.1.2.1 buffer.append("\n\t " + f + "\t -> ");
679 vivien 1.1.2.1 boolean firstnode = true;
680 vivien 1.1.2.1 for(Iterator it_n2=n1_f.keys().iterator(); it_n2.hasNext(); ){
681 vivien 1.1.2.1 Object obj = it_n2.next();
682 vivien 1.1.2.1 PANode n2 = (PANode) obj;
683 vivien 1.1.2.1 if(firstnode){
684 vivien 1.1.2.1 buffer.append(n2 + "\t-> " +
685 vivien 1.1.2.1 n1_f.getValues(n2));
686 vivien 1.1.2.1 firstnode = false;
687 vivien 1.1.2.1 }
688 vivien 1.1.2.1 else
689 vivien 1.1.2.1 buffer.append("\n\t \t " + n2 + "\t-> " +
690 vivien 1.1.2.1 n1_f.getValues(n2));
691 vivien 1.1.2.1 }
692 vivien 1.1.2.1 }
693 vivien 1.1.2.1 }
694 vivien 1.1.2.1 return buffer.toString();
695 vivien 1.1.2.1 }
696 vivien 1.1.2.1
697 vivien 1.1.2.1 public Set project(Set holes, Map projection)
698 vivien 1.1.2.1 {
699 vivien 1.1.2.1 HashSet newHoles = new HashSet();
700 vivien 1.1.2.1
701 vivien 1.1.2.1 for(Iterator it=holes.iterator(); it.hasNext(); )
702 vivien 1.1.2.1 newHoles.add(projection.get(it.next()));
703 vivien 1.1.2.1
704 vivien 1.1.2.1 return newHoles;
705 vivien 1.1.2.1 }
706 vivien 1.1.2.1
707 vivien 1.1.2.1
708 cananian 1.2 }