KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > soot > Hierarchy


1 /* Soot - a J*va Optimization Framework
2  * Copyright (C) 1997-1999 Raja Vallee-Rai
3  *
4  * This library is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU Lesser General Public
6  * License as published by the Free Software Foundation; either
7  * version 2.1 of the License, or (at your option) any later version.
8  *
9  * This library is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12  * Lesser General Public License for more details.
13  *
14  * You should have received a copy of the GNU Lesser General Public
15  * License along with this library; if not, write to the
16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17  * Boston, MA 02111-1307, USA.
18  */

19
20 /*
21  * Modified by the Sable Research Group and others 1997-1999.
22  * See the 'credits' file distributed with Soot for the complete list of
23  * contributors. (Soot is distributed at http://www.sable.mcgill.ca/soot)
24  */

25
26 package soot;
27
28 import soot.jimple.*;
29 import soot.util.*;
30 import java.util.*;
31
32 /** Represents the class hierarchy. It is closely linked to a Scene,
33  * and must be recreated if the Scene changes.
34  *
35  * The general convention is that if a method name contains
36  * "Including", then it returns the non-strict result; otherwise,
37  * it does a strict query (e.g. strict superclass). */

38 public class Hierarchy
39 {
40     // These two maps are not filled in the constructor.
41
HashMap classToSubclasses;
42     HashMap interfaceToSubinterfaces;
43
44     HashMap classToDirSubclasses;
45     HashMap interfaceToDirSubinterfaces;
46
47     // This holds the direct implementers.
48
HashMap interfaceToDirImplementers;
49
50     int state;
51     Scene sc;
52
53     /** Constructs a hierarchy from the current scene. */
54     public Hierarchy()
55     {
56         this.sc = Scene.v();
57         state = sc.getState();
58
59         // Well, this used to be describable by 'Duh'.
60
// Construct the subclasses hierarchy and the subinterfaces hierarchy.
61
{
62             Chain allClasses = sc.getClasses();
63
64             classToSubclasses = new HashMap(allClasses.size() * 2 + 1, 0.7f);
65             interfaceToSubinterfaces = new HashMap(allClasses.size() * 2 + 1, 0.7f);
66
67             classToDirSubclasses = new HashMap
68                 (allClasses.size() * 2 + 1, 0.7f);
69             interfaceToDirSubinterfaces = new HashMap
70                 (allClasses.size() * 2 + 1, 0.7f);
71             interfaceToDirImplementers = new HashMap
72                 (allClasses.size() * 2 + 1, 0.7f);
73
74             Iterator classesIt = allClasses.iterator();
75             while (classesIt.hasNext())
76             {
77                 SootClass c = (SootClass)classesIt.next();
78                 if( c.resolvingLevel() < SootClass.HIERARCHY ) continue;
79
80                 if (c.isInterface())
81                 {
82                     interfaceToDirSubinterfaces.put(c, new ArrayList());
83                     interfaceToDirImplementers.put(c, new ArrayList());
84                 }
85                 else
86                     classToDirSubclasses.put(c, new ArrayList());
87             }
88
89             classesIt = allClasses.iterator();
90             while (classesIt.hasNext())
91             {
92                 SootClass c = (SootClass)classesIt.next();
93                 if( c.resolvingLevel() < SootClass.HIERARCHY ) continue;
94
95                 if (c.hasSuperclass())
96                 {
97                     if (c.isInterface())
98                     {
99                         Iterator subIt = c.getInterfaces().iterator();
100
101                         while (subIt.hasNext())
102                         {
103                             SootClass i = (SootClass)subIt.next();
104                             if( c.resolvingLevel() < SootClass.HIERARCHY ) continue;
105                             List l = (List)interfaceToDirSubinterfaces.get(i);
106                             l.add(c);
107                         }
108                     }
109                     else
110                     {
111                         List l = (List)classToDirSubclasses.get(c.getSuperclass());
112                         l.add(c);
113
114                     
115                         Iterator subIt = c.getInterfaces().iterator();
116
117                         while (subIt.hasNext())
118                         {
119                             SootClass i = (SootClass)subIt.next();
120                             if( c.resolvingLevel() < SootClass.HIERARCHY ) continue;
121                             l = (List)interfaceToDirImplementers.get(i);
122                             l.add(c);
123                         }
124                     }
125                 }
126             }
127
128             // Fill the directImplementers lists with subclasses.
129
{
130                 classesIt = allClasses.iterator();
131                 while (classesIt.hasNext())
132                 {
133                     SootClass c = (SootClass)classesIt.next();
134                     if( c.resolvingLevel() < SootClass.HIERARCHY ) continue;
135                     if (c.isInterface())
136                     {
137                         List imp = (List)interfaceToDirImplementers.get(c);
138                         Set s = new ArraySet();
139                         
140                         Iterator impIt = imp.iterator();
141                         while (impIt.hasNext())
142                         {
143                             SootClass c0 = (SootClass)impIt.next();
144                             if( c.resolvingLevel() < SootClass.HIERARCHY ) continue;
145                             s.addAll(getSubclassesOfIncluding(c0));
146                         }
147
148                         imp.clear(); imp.addAll(s);
149                     }
150                 }
151             }
152
153             classesIt = allClasses.iterator();
154             while (classesIt.hasNext())
155             {
156                 SootClass c = (SootClass)classesIt.next();
157                 if( c.resolvingLevel() < SootClass.HIERARCHY ) continue;
158
159                 if (c.isInterface())
160                 {
161                     interfaceToDirSubinterfaces.put(c, Collections.unmodifiableList
162                                           ((List)interfaceToDirSubinterfaces.get(c)));
163                     interfaceToDirImplementers.put(c, Collections.unmodifiableList
164                                                 ((List)interfaceToDirImplementers.get(c)));
165                 }
166                 else
167                     classToDirSubclasses.put(c, Collections.unmodifiableList
168                                           ((List)classToDirSubclasses.get(c)));
169             }
170         }
171     }
172
173     private void checkState()
174     {
175         if (state != sc.getState())
176             throw new ConcurrentModificationException("Scene changed for Hierarchy!");
177     }
178
179     // This includes c in the list of subclasses.
180
/** Returns a list of subclasses of c, including itself. */
181     public List getSubclassesOfIncluding(SootClass c)
182     {
183         c.checkLevel(SootClass.HIERARCHY);
184         if (c.isInterface())
185             throw new RuntimeException JavaDoc("class needed!");
186
187         List l = new ArrayList();
188         l.addAll(getSubclassesOf(c));
189         l.add(c);
190
191         return Collections.unmodifiableList(l);
192     }
193
194     /** Returns a list of subclasses of c, excluding itself. */
195     public List getSubclassesOf(SootClass c)
196     {
197         c.checkLevel(SootClass.HIERARCHY);
198         if (c.isInterface())
199             throw new RuntimeException JavaDoc("class needed!");
200
201         checkState();
202
203         // If already cached, return the value.
204
if (classToSubclasses.get(c) != null)
205             return (List)classToSubclasses.get(c);
206
207         // Otherwise, build up the hashmap.
208
List l = new ArrayList();
209
210         ListIterator it = ((List)classToDirSubclasses.get(c)).listIterator();
211         while (it.hasNext())
212         {
213             SootClass cls = (SootClass) it.next();
214             if( cls.resolvingLevel() < cls.HIERARCHY ) continue;
215             l.addAll(getSubclassesOfIncluding(cls));
216         }
217         
218         l = Collections.unmodifiableList(l);
219         classToSubclasses.put(c, l);
220
221         return l;
222     }
223
224     /** Returns a list of superclasses of c, including itself. */
225     public List getSuperclassesOfIncluding(SootClass c)
226     {
227         c.checkLevel(SootClass.HIERARCHY);
228         List l = getSuperclassesOf(c);
229         ArrayList al = new ArrayList(); al.add(c); al.addAll(l);
230         return Collections.unmodifiableList(al);
231     }
232
233     /** Returns a list of strict superclasses of c, starting with c's parent. */
234     public List getSuperclassesOf(SootClass c)
235     {
236         c.checkLevel(SootClass.HIERARCHY);
237         if (c.isInterface())
238             throw new RuntimeException JavaDoc("class needed!");
239
240         checkState();
241
242         ArrayList l = new ArrayList();
243         SootClass cl = c;
244
245         while (cl.hasSuperclass())
246         {
247             l.add(cl.getSuperclass());
248             cl = cl.getSuperclass();
249         }
250
251         return Collections.unmodifiableList(l);
252     }
253
254     /** Returns a list of subinterfaces of c, including itself. */
255     public List getSubinterfacesOfIncluding(SootClass c)
256     {
257         c.checkLevel(SootClass.HIERARCHY);
258         if (!c.isInterface())
259             throw new RuntimeException JavaDoc("interface needed!");
260
261         List l = new ArrayList();
262         l.addAll(getSubinterfacesOf(c));
263         l.add(c);
264
265         return Collections.unmodifiableList(l);
266     }
267
268     /** Returns a list of subinterfaces of c, excluding itself. */
269     public List getSubinterfacesOf(SootClass c)
270     {
271         c.checkLevel(SootClass.HIERARCHY);
272         if (!c.isInterface())
273             throw new RuntimeException JavaDoc("interface needed!");
274
275         checkState();
276
277         // If already cached, return the value.
278
if (interfaceToSubinterfaces.get(c) != null)
279             return (List)interfaceToSubinterfaces.get(c);
280
281         // Otherwise, build up the hashmap.
282
List l = new ArrayList();
283
284         ListIterator it = ((List)interfaceToDirSubinterfaces.get(c)).listIterator();
285         while (it.hasNext())
286         {
287             l.addAll(getSubinterfacesOfIncluding((SootClass)it.next()));
288         }
289         
290         interfaceToSubinterfaces.put(c, Collections.unmodifiableList(l));
291
292         return Collections.unmodifiableList(l);
293     }
294
295     /** Returns a list of superinterfaces of c, excluding itself. */
296     public List getSuperinterfacesOf(SootClass c)
297     {
298         throw new RuntimeException JavaDoc("Not implemented yet!");
299     }
300
301     /** Returns a list of direct superclasses of c, excluding c. */
302     public List getDirectSuperclassesOf(SootClass c)
303     {
304         throw new RuntimeException JavaDoc("Not implemented yet!");
305     }
306
307     /** Returns a list of direct subclasses of c, excluding c. */
308     public List getDirectSubclassesOf(SootClass c)
309     {
310         c.checkLevel(SootClass.HIERARCHY);
311         if (c.isInterface())
312             throw new RuntimeException JavaDoc("class needed!");
313
314         checkState();
315
316         return Collections.unmodifiableList((List)classToDirSubclasses.get(c));
317     }
318
319     // This includes c in the list of subclasses.
320
/** Returns a list of direct subclasses of c, including c. */
321     public List getDirectSubclassesOfIncluding(SootClass c)
322     {
323         c.checkLevel(SootClass.HIERARCHY);
324         if (c.isInterface())
325             throw new RuntimeException JavaDoc("class needed!");
326
327         checkState();
328
329         List l = new ArrayList();
330         l.addAll((List)classToDirSubclasses.get(c));
331         l.add(c);
332
333         return Collections.unmodifiableList(l);
334     }
335
336     /** Returns a list of direct superinterfaces of c. */
337     public List getDirectSuperinterfacesOf(SootClass c)
338     {
339         throw new RuntimeException JavaDoc("Not implemented yet!");
340     }
341
342     /** Returns a list of direct subinterfaces of c. */
343     public List getDirectSubinterfacesOf(SootClass c)
344     {
345         c.checkLevel(SootClass.HIERARCHY);
346         if (!c.isInterface())
347             throw new RuntimeException JavaDoc("interface needed!");
348
349         checkState();
350
351         return (List)interfaceToDirSubinterfaces.get(c);
352     }
353
354     /** Returns a list of direct subinterfaces of c, including itself. */
355     public List getDirectSubinterfacesOfIncluding(SootClass c)
356     {
357         c.checkLevel(SootClass.HIERARCHY);
358         if (!c.isInterface())
359             throw new RuntimeException JavaDoc("interface needed!");
360
361         checkState();
362
363         List l = new ArrayList();
364         l.addAll((List)interfaceToDirSubinterfaces.get(c));
365         l.add(c);
366
367         return Collections.unmodifiableList(l);
368     }
369
370     /** Returns a list of direct implementers of c, excluding itself. */
371     public List getDirectImplementersOf(SootClass i)
372     {
373         i.checkLevel(SootClass.HIERARCHY);
374         if (!i.isInterface())
375             throw new RuntimeException JavaDoc("interface needed; got "+i);
376
377         checkState();
378
379         return Collections.unmodifiableList((List)interfaceToDirImplementers.get(i));
380     }
381
382     /** Returns a list of implementers of c, excluding itself. */
383     public List getImplementersOf(SootClass i)
384     {
385         i.checkLevel(SootClass.HIERARCHY);
386         if (!i.isInterface())
387             throw new RuntimeException JavaDoc("interface needed; got "+i);
388
389         checkState();
390
391         Iterator it = getSubinterfacesOfIncluding(i).iterator();
392         ArraySet set = new ArraySet();
393
394         while (it.hasNext())
395         {
396             SootClass c = (SootClass)it.next();
397
398             set.addAll(getDirectImplementersOf(c));
399         }
400
401         ArrayList l = new ArrayList();
402         l.addAll(set);
403
404         return Collections.unmodifiableList(l);
405     }
406
407     /** Returns true if child is a subclass of possibleParent. */
408     public boolean isClassSubclassOf(SootClass child, SootClass possibleParent)
409     {
410         child.checkLevel(SootClass.HIERARCHY);
411         possibleParent.checkLevel(SootClass.HIERARCHY);
412         return getSuperclassesOf(child).contains(possibleParent);
413     }
414
415     /** Returns true if child is, or is a subclass of, possibleParent. */
416     public boolean isClassSubclassOfIncluding(SootClass child, SootClass possibleParent)
417     {
418         child.checkLevel(SootClass.HIERARCHY);
419         possibleParent.checkLevel(SootClass.HIERARCHY);
420         return getSuperclassesOfIncluding(child).contains(possibleParent);
421     }
422
423     /** Returns true if child is a direct subclass of possibleParent. */
424     public boolean isClassDirectSubclassOf(SootClass c, SootClass c2)
425     {
426         throw new RuntimeException JavaDoc("Not implemented yet!");
427     }
428
429     /** Returns true if child is a superclass of possibleParent. */
430     public boolean isClassSuperclassOf(SootClass parent, SootClass possibleChild)
431     {
432         parent.checkLevel(SootClass.HIERARCHY);
433         possibleChild.checkLevel(SootClass.HIERARCHY);
434         return getSubclassesOf(parent).contains(possibleChild);
435     }
436
437     /** Returns true if parent is, or is a superclass of, possibleChild. */
438     public boolean isClassSuperclassOfIncluding(SootClass parent, SootClass possibleChild)
439     {
440         parent.checkLevel(SootClass.HIERARCHY);
441         possibleChild.checkLevel(SootClass.HIERARCHY);
442         return getSubclassesOfIncluding(parent).contains(possibleChild);
443     }
444
445     /** Returns true if child is a subinterface of possibleParent. */
446     public boolean isInterfaceSubinterfaceOf(SootClass child, SootClass possibleParent)
447     {
448         child.checkLevel(SootClass.HIERARCHY);
449         possibleParent.checkLevel(SootClass.HIERARCHY);
450         return getSubinterfacesOf(possibleParent).contains(child);
451     }
452
453     /** Returns true if child is a direct subinterface of possibleParent. */
454     public boolean isInterfaceDirectSubinterfaceOf(SootClass child,
455                                                    SootClass possibleParent)
456     {
457         child.checkLevel(SootClass.HIERARCHY);
458         possibleParent.checkLevel(SootClass.HIERARCHY);
459         return getDirectSubinterfacesOf(possibleParent).contains(child);
460     }
461
462     /** Returns the most specific type which is an ancestor of both c1 and c2. */
463     public SootClass getLeastCommonSuperclassOf(SootClass c1,
464                                                 SootClass c2)
465     {
466         c1.checkLevel(SootClass.HIERARCHY);
467         c2.checkLevel(SootClass.HIERARCHY);
468         throw new RuntimeException JavaDoc("Not implemented yet!");
469     }
470
471     // Questions about method invocation.
472

473     /** Returns true if the method m is visible from code in the class from. */
474     private boolean isVisible( SootClass from, SootMethod m ) {
475         from.checkLevel(SootClass.HIERARCHY);
476         m.getDeclaringClass().checkLevel(SootClass.HIERARCHY);
477         if( m.isPublic() ) return true;
478         if( m.isPrivate() ) {
479             return from.equals( m.getDeclaringClass() );
480         }
481         if( m.isProtected() ) {
482             return isClassSubclassOfIncluding( from, m.getDeclaringClass() );
483         }
484         // m is package
485
return from.getJavaPackageName().equals(
486                 m.getDeclaringClass().getJavaPackageName() );
487             //|| isClassSubclassOfIncluding( from, m.getDeclaringClass() );
488
}
489
490     /** Given an object of actual type C (o = new C()), returns the method which will be called
491         on an o.f() invocation. */

492     public SootMethod resolveConcreteDispatch(SootClass concreteType, SootMethod m)
493     {
494         concreteType.checkLevel(SootClass.HIERARCHY);
495         m.getDeclaringClass().checkLevel(SootClass.HIERARCHY);
496         checkState();
497
498         if (concreteType.isInterface())
499             throw new RuntimeException JavaDoc("class needed!");
500
501         Iterator it = getSuperclassesOfIncluding(concreteType).iterator();
502         String JavaDoc methodSig = m.getSubSignature();
503
504         while (it.hasNext())
505         {
506             SootClass c = (SootClass)it.next();
507             if (c.declaresMethod(methodSig)
508             && isVisible( c, m )
509             ) {
510                 return c.getMethod(methodSig);
511             }
512         }
513         throw new RuntimeException JavaDoc("could not resolve concrete dispatch!\nType: "+concreteType+"\nMethod: "+m);
514     }
515
516     /** Given a set of definite receiver types, returns a list of possible targets. */
517     public List resolveConcreteDispatch(List classes, SootMethod m)
518     {
519         m.getDeclaringClass().checkLevel(SootClass.HIERARCHY);
520         checkState();
521
522         ArraySet s = new ArraySet();
523         Iterator classesIt = classes.iterator();
524
525         while (classesIt.hasNext()) {
526             Object JavaDoc cls = classesIt.next();
527             if (cls instanceof RefType)
528                 s.add(resolveConcreteDispatch(((RefType)cls).getSootClass(), m));
529             else if (cls instanceof ArrayType) {
530                 s.add(resolveConcreteDispatch((RefType.v("java.lang.Object")).getSootClass(), m));
531             }
532             else throw new RuntimeException JavaDoc("Unable to resolve concrete dispatch of type "+ cls);
533         }
534
535         List l = new ArrayList(); l.addAll(s);
536         return Collections.unmodifiableList(l);
537     }
538
539     // what can get called for c & all its subclasses
540
/** Given an abstract dispatch to an object of type c and a method m, gives
541      * a list of possible receiver methods. */

542     public List resolveAbstractDispatch(SootClass c, SootMethod m)
543     {
544         c.checkLevel(SootClass.HIERARCHY);
545         m.getDeclaringClass().checkLevel(SootClass.HIERARCHY);
546         checkState();
547
548         Iterator classesIt = null;
549
550         if (c.isInterface()) {
551             classesIt = getImplementersOf(c).iterator();
552             HashSet classes = new HashSet();
553             while (classesIt.hasNext())
554                 classes.addAll(getSubclassesOfIncluding((SootClass)classesIt.next()));
555             classesIt = classes.iterator();
556         }
557             
558         else
559             classesIt = getSubclassesOfIncluding(c).iterator();
560
561         ArraySet s = new ArraySet();
562         
563         while (classesIt.hasNext()) {
564             SootClass cl = (SootClass) classesIt.next();
565             if( Modifier.isAbstract( cl.getModifiers() ) ) continue;
566             s.add(resolveConcreteDispatch(cl, m));
567         }
568
569         List l = new ArrayList(); l.addAll(s);
570         return Collections.unmodifiableList(l);
571     }
572
573     // what can get called if you have a set of possible receiver types
574
/** Returns a list of possible targets for the given method and set of receiver types. */
575     public List resolveAbstractDispatch(List classes, SootMethod m)
576     {
577         m.getDeclaringClass().checkLevel(SootClass.HIERARCHY);
578         ArraySet s = new ArraySet();
579         Iterator classesIt = classes.iterator();
580
581         while (classesIt.hasNext())
582             s.addAll(resolveAbstractDispatch((SootClass)classesIt.next(), m));
583
584         List l = new ArrayList(); l.addAll(s);
585         return Collections.unmodifiableList(l);
586     }
587
588     /** Returns the target for the given SpecialInvokeExpr. */
589     public SootMethod resolveSpecialDispatch(SpecialInvokeExpr ie, SootMethod container)
590     {
591         container.getDeclaringClass().checkLevel(SootClass.HIERARCHY);
592         SootMethod target = ie.getMethod();
593         target.getDeclaringClass().checkLevel(SootClass.HIERARCHY);
594
595         /* This is a bizarre condition! Hopefully the implementation is correct.
596            See VM Spec, 2nd Edition, Chapter 6, in the definition of invokespecial. */

597         if (target.getName().equals("<init>") || target.isPrivate())
598             return target;
599         else if (isClassSubclassOf(target.getDeclaringClass(), container.getDeclaringClass()))
600             return resolveConcreteDispatch(container.getDeclaringClass(), target);
601         else
602             return target;
603     }
604 }
605
Popular Tags