FastHierarchy


1   /* Soot - a J*va Optimization Framework
2    * Copyright (C) 2002 Ondrej Lhotak
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  package soot;
21  
22  import soot.jimple.*;
23  import soot.util.*;
24  import java.util.*;
25  
26  /** Represents the class hierarchy.  It is closely linked to a Scene,
27   * and must be recreated if the Scene changes. 
28   *
29   * This version supercedes the old soot.Hierarchy class.
30   *
31   * @author Ondrej Lhotak
32   */
33  public class FastHierarchy
34  {
35      private static void put( Map m, Object   key, Object   value ) {
36          List l = (List) m.get( key );
37          if( l == null ) m.put( key, l = new ArrayList() );
38          l.add( value );
39      }
40      
41      /** This map holds all key,value pairs such that 
42       * value.getSuperclass() == key. This is one of the three maps that hold
43       * the inverse of the relationships given by the getSuperclass and
44       * getInterfaces methods of SootClass. */
45      protected Map classToSubclasses = new HashMap();
46  
47      /** This map holds all key,value pairs such that value is an interface 
48       * and key is in value.getInterfaces(). This is one of the three maps 
49       * that hold the inverse of the relationships given by the getSuperclass 
50       * and getInterfaces methods of SootClass. */
51      protected MultiMap interfaceToSubinterfaces = new HashMultiMap();
52  
53      /** This map holds all key,value pairs such that value is a class 
54       * (NOT an interface) and key is in value.getInterfaces(). This is one of 
55       * the three maps that hold the inverse of the relationships given by the 
56       * getSuperclass and getInterfaces methods of SootClass. */
57      protected MultiMap interfaceToImplementers = new HashMultiMap();
58  
59      /** This map is a transitive closure of interfaceToSubinterfaces,
60       * and each set contains its superinterface itself. */
61      protected MultiMap interfaceToAllSubinterfaces = new HashMultiMap();
62  
63      /** This map gives, for an interface, all concrete classes that
64       * implement that interface and all its subinterfaces, but
65       * NOT their subclasses. */
66      protected MultiMap interfaceToAllImplementers = new HashMultiMap();
67  
68      /** For each class (NOT interface), this map contains a Interval, which is
69       * a pair of numbers giving a preorder and postorder ordering of classes
70       * in the inheritance tree. */
71      protected Map classToInterval = new HashMap();
72  
73      /** These maps cache subtype queries, so they can be re-done quickly. */
74      //protected MultiMap cacheSubtypes = new HashMultiMap();
75      //protected MultiMap cacheNonSubtypes = new HashMultiMap();
76  
77      protected Scene sc;
78  
79      protected class Interval {
80          int lower;
81          int upper;
82          boolean isSubrange( Interval potentialSubrange ) {
83              if( lower > potentialSubrange.lower ) return false;
84              if( upper < potentialSubrange.upper ) return false;
85              return true;
86          }
87      }
88      protected int dfsVisit( int start, SootClass c ) {
89          Interval r = new Interval();
90          r.lower = start++;
91          Collection col = (Collection) classToSubclasses.get(c);
92          if( col != null ) {
93              Iterator it = col.iterator();
94              while( it.hasNext() ) {
95                  SootClass sc = (SootClass) it.next();
96                  // For some awful reason, Soot thinks interface are subclasses
97                  // of java.lang.Object
98                  if( sc.isInterface() ) continue;
99                  start = dfsVisit( start, sc );
100             }
101         }
102         r.upper = start++;
103         if( c.isInterface() ) {
104             throw new RuntimeException  ( "Attempt to dfs visit interface "+c );
105         }
106         classToInterval.put( c, r );
107         return start;
108     }
109 
110     /** Constructs a hierarchy from the current scene. */
111     public FastHierarchy()
112     {
113         this.sc = Scene.v();
114 
115         /* First build the inverse maps. */
116         for( Iterator clIt = sc.getClasses().iterator(); clIt.hasNext(); ) {
117             final SootClass cl = (SootClass) clIt.next();
118             if( cl.resolvingLevel() < SootClass.HIERARCHY ) continue;
119             if( !cl.isInterface() && cl.hasSuperclass() ) {
120                 put( classToSubclasses, cl.getSuperclass(), cl );
121             }
122             for( Iterator superclIt = cl.getInterfaces().iterator(); superclIt.hasNext(); ) {
123                 final SootClass supercl = (SootClass) superclIt.next();
124                 if( cl.isInterface() ) {
125                     interfaceToSubinterfaces.put( supercl, cl );
126                 } else {
127                     interfaceToImplementers.put( supercl, cl );
128                 }
129             }
130         }
131 
132         /* Now do a dfs traversal to get the Interval numbers. */
133         dfsVisit( 0, Scene.v().getSootClass( "java.lang.Object" ) );
134     }
135 
136     /** Return true if class child is a subclass of class parent, neither of
137      * them being allowed to be interfaces. */
138     public boolean isSubclass( SootClass child, SootClass parent ) {
139         child.checkLevel(SootClass.HIERARCHY);
140         parent.checkLevel(SootClass.HIERARCHY);
141         Interval parentInterval = (Interval) classToInterval.get( parent );
142         Interval childInterval = (Interval) classToInterval.get( child );
143         return parentInterval.isSubrange( childInterval );
144     }
145 
146     /** For an interface parent (MUST be an interface), returns set of all
147      * implementers of it but NOT their subclasses. */
148     public Set getAllImplementersOfInterface( SootClass parent ) {
149         parent.checkLevel(SootClass.HIERARCHY);
150         if( !interfaceToAllImplementers.containsKey( parent ) ) {
151             for( Iterator subinterfaceIt = getAllSubinterfaces( parent ).iterator(); subinterfaceIt.hasNext(); ) {
152                 final SootClass subinterface = (SootClass) subinterfaceIt.next();
153                 if( subinterface == parent ) continue;
154                 interfaceToAllImplementers.putAll(parent,
155                     getAllImplementersOfInterface( subinterface ) );
156             }
157             interfaceToAllImplementers.putAll(parent, 
158                     interfaceToImplementers.get( parent ) );
159         }
160         return interfaceToAllImplementers.get( parent );
161     }
162 
163     /** For an interface parent (MUST be an interface), returns set of all
164      * subinterfaces. */
165     protected Set getAllSubinterfaces( SootClass parent ) {
166         parent.checkLevel(SootClass.HIERARCHY);
167         if( !interfaceToAllSubinterfaces.containsKey( parent ) ) {
168             interfaceToAllSubinterfaces.put( parent, parent );
169             for( Iterator it = interfaceToSubinterfaces.get( parent ).iterator(); it.hasNext(); ) {
170                 interfaceToAllSubinterfaces.putAll(parent, 
171                     getAllSubinterfaces( (SootClass) it.next() ) );
172             }
173         }
174         return interfaceToAllSubinterfaces.get( parent );
175     }
176 
177     /** Given an object of declared type child, returns true if the object
178      * can be stored in a variable of type parent. If child is an interface
179      * that is not a subinterface of parent, this method will return false
180      * even though some objects implementing the child interface may also
181      * implement the parent interface. */
182     /*
183     public boolean canStoreType( Type child, Type parent ) {
184         if( cacheSubtypes.get( parent ).contains( child ) ) return true;
185         if( cacheNonSubtypes.get( parent ).contains( child ) ) return false;
186         boolean ret = canStoreTypeInternal( child, parent );
187         ( ret ? cacheSubtypes : cacheNonSubtypes ).put( parent, child );
188         return ret;
189     }
190     */
191 
192     /** Given an object of declared type child, returns true if the object
193      * can be stored in a variable of type parent. If child is an interface
194      * that is not a subinterface of parent, this method will return false
195      * even though some objects implementing the child interface may also
196      * implement the parent interface. */
197     public boolean canStoreType( Type child, Type parent ) {
198         if( child.equals( parent ) ) return true;
199         if( parent instanceof NullType ) {
200             return false;
201         }
202         if( child instanceof RefType ) {
203             if( parent instanceof RefType) {
204                 return canStoreClass( ((RefType) child).getSootClass(),
205                     ((RefType) parent).getSootClass() );
206             } else {
207                 return false;
208             }
209         } else if( child instanceof AnySubType ) {
210             if( !(parent instanceof RefLikeType ) ) {
211                 throw new RuntimeException  ( "Unhandled type "+parent );
212             } else if(parent instanceof ArrayType) {
213                 Type base = ((AnySubType)child).getBase();
214                 // From Java Language Spec 2nd ed., Chapter 10, Arrays
215                 return base.equals( RefType.v( "java.lang.Object" ) )
216                 || base.equals( RefType.v( "java.io.Serializable" ) )
217                 || base.equals( RefType.v( "java.lang.Cloneable" ) );
218             } else {
219                 SootClass base = ((AnySubType)child).getBase().getSootClass();
220                 SootClass parentClass = ((RefType) parent).getSootClass();
221                 LinkedList worklist = new LinkedList();
222                 if( base.isInterface() ) worklist.addAll(getAllImplementersOfInterface(base));
223                 else worklist.add(base);
224                 Set workset = new HashSet();
225                 while(!worklist.isEmpty()) {
226                     SootClass cl = (SootClass) worklist.removeFirst();
227                     if( !workset.add(cl) ) continue;
228                     if( cl.isConcrete() 
229                     &&  canStoreClass(cl, parentClass) ) return true;
230                     worklist.addAll(getSubclassesOf(cl));
231                 }
232                 return false;
233             }
234         } else {
235             ArrayType achild = (ArrayType) child;
236             if( parent instanceof RefType ) {
237                 // From Java Language Spec 2nd ed., Chapter 10, Arrays
238                 return parent.equals( RefType.v( "java.lang.Object" ) )
239                 || parent.equals( RefType.v( "java.io.Serializable" ) )
240                 || parent.equals( RefType.v( "java.lang.Cloneable" ) );
241             }
242             ArrayType aparent = (ArrayType) parent;
243                                                 
244             // You can store a int[][] in a Object[]. Yuck!
245             // Also, you can store a Interface[] in a Object[]
246             if( achild.numDimensions == aparent.numDimensions ) {
247                 if( achild.baseType.equals( aparent.baseType ) ) return true;
248                 if( !(achild.baseType instanceof RefType ) ) return false;
249                 if( !(aparent.baseType instanceof RefType ) ) return false;
250                 return canStoreType( achild.baseType, aparent.baseType );
251             } else if( achild.numDimensions > aparent.numDimensions ) {
252                 if( aparent.baseType.equals( RefType.v( "java.lang.Object" ) ) )
253                     return true;
254                 if( aparent.baseType.equals( RefType.v( "java.io.Serializable" ) ) )
255                     return true;
256                 if( aparent.baseType.equals( RefType.v( "java.lang.Cloneable" ) ) )
257                     return true;
258                 return false;
259             } else return false;
260         }
261     }
262 
263     /** Given an object of declared type child, returns true if the object
264      * can be stored in a variable of type parent. If child is an interface
265      * that is not a subinterface of parent, this method will return false
266      * even though some objects implementing the child interface may also
267      * implement the parent interface. */
268     protected boolean canStoreClass( SootClass child, SootClass parent ) {
269         parent.checkLevel(SootClass.HIERARCHY);
270         child.checkLevel(SootClass.HIERARCHY);
271         Interval parentInterval = (Interval) classToInterval.get( parent );
272         Interval childInterval = (Interval) classToInterval.get( child );
273         if( parentInterval != null && childInterval != null ) {
274             return parentInterval.isSubrange( childInterval );
275         }
276         if( childInterval == null ) { // child is interface
277             if( parentInterval != null ) { // parent is not interface
278                 return parent.equals( RefType.v("java.lang.Object").getSootClass() );
279             } else {
280                 return getAllSubinterfaces( parent ).contains( child );
281             }
282         } else {
283             Set impl = getAllImplementersOfInterface( parent );
284             for( Iterator it = impl.iterator(); it.hasNext(); ) {
285                 parentInterval = (Interval) classToInterval.get( it.next() );
286                 if( parentInterval.isSubrange( childInterval ) ) {
287                     return true;
288                 }
289             }
290             return false;
291         }
292     }
293 
294     public Collection resolveConcreteDispatchWithoutFailing(Collection concreteTypes, SootMethod m, RefType declaredTypeOfBase ) {
295 
296         Set ret = new HashSet();
297         SootClass declaringClass = declaredTypeOfBase.getSootClass();
298         declaringClass.checkLevel(SootClass.HIERARCHY);
299         for( Iterator tIt = concreteTypes.iterator(); tIt.hasNext(); ) {
300             final Type t = (Type) tIt.next();
301             if( t instanceof AnySubType ) {
302                 String   methodSig = m.getSubSignature();
303                 HashSet s = new HashSet();
304                 s.add( declaringClass );
305                 while( !s.isEmpty() ) {
306                     SootClass c = (SootClass) s.iterator().next();
307                     s.remove( c );
308                     if( !c.isInterface() && !c.isAbstract()
309                             && canStoreClass( c, declaringClass ) ) {
310                         SootMethod concreteM = resolveConcreteDispatch( c, m );
311                         if( concreteM != null )
312                             ret.add( concreteM );
313                     }
314                     if( classToSubclasses.containsKey( c ) ) {
315                         s.addAll( (Collection) classToSubclasses.get( c ) );
316                     }
317                     if( interfaceToSubinterfaces.containsKey( c ) ) {
318                         s.addAll( interfaceToSubinterfaces.get( c ) );
319                     }
320                     if( interfaceToImplementers.containsKey( c ) ) {
321                         s.addAll( interfaceToImplementers.get( c ) );
322                     }
323                 }
324                 return ret;
325             } else if( t instanceof RefType ) {
326                 RefType concreteType = (RefType) t;
327                 SootClass concreteClass = concreteType.getSootClass();
328                 if( !canStoreClass( concreteClass, declaringClass ) ) {
329                     continue;
330                 }
331                 SootMethod concreteM = null;
332                 try {
333                     concreteM = resolveConcreteDispatch( concreteClass, m );
334                 } catch( Exception   e ) {
335                     concreteM = null;
336                 }
337                 if( concreteM != null ) ret.add( concreteM );
338             } else if( t instanceof ArrayType ) {
339                 SootMethod concreteM = null;
340                 try {
341                     concreteM = resolveConcreteDispatch( 
342                         RefType.v( "java.lang.Object" ).getSootClass(), m );
343                 } catch( Exception   e ) {
344                     concreteM = null;
345                 }
346                 if( concreteM != null ) ret.add( concreteM );
347             } else throw new RuntimeException  ( "Unrecognized reaching type "+t );
348         }
349         return ret;
350     }
351 
352     public Collection resolveConcreteDispatch(Collection concreteTypes, SootMethod m, RefType declaredTypeOfBase ) {
353 
354         Set ret = new HashSet();
355         SootClass declaringClass = declaredTypeOfBase.getSootClass();
356         declaringClass.checkLevel(SootClass.HIERARCHY);
357         for( Iterator tIt = concreteTypes.iterator(); tIt.hasNext(); ) {
358             final Type t = (Type) tIt.next();
359             if( t instanceof AnySubType ) {
360                 String   methodSig = m.getSubSignature();
361                 HashSet s = new HashSet();
362                 s.add( declaringClass );
363                 while( !s.isEmpty() ) {
364                     SootClass c = (SootClass) s.iterator().next();
365                     s.remove( c );
366                     if( !c.isInterface() && !c.isAbstract()
367                             && canStoreClass( c, declaringClass ) ) {
368                         SootMethod concreteM = resolveConcreteDispatch( c, m );
369                         if( concreteM != null )
370                             ret.add( concreteM );
371                     }
372                     if( classToSubclasses.containsKey( c ) ) {
373                         s.addAll( (Collection) classToSubclasses.get( c ) );
374                     }
375                     if( interfaceToSubinterfaces.containsKey( c ) ) {
376                         s.addAll( interfaceToSubinterfaces.get( c ) );
377                     }
378                     if( interfaceToImplementers.containsKey( c ) ) {
379                         s.addAll( interfaceToImplementers.get( c ) );
380                     }
381                 }
382                 return ret;
383             } else if( t instanceof RefType ) {
384                 RefType concreteType = (RefType) t;
385                 SootClass concreteClass = concreteType.getSootClass();
386                 if( !canStoreClass( concreteClass, declaringClass ) ) {
387                     continue;
388                 }
389                 SootMethod concreteM = resolveConcreteDispatch( concreteClass, m );
390                 if( concreteM != null ) ret.add( concreteM );
391             } else if( t instanceof ArrayType ) {
392                 SootMethod concreteM = resolveConcreteDispatch( 
393                         RefType.v( "java.lang.Object" ).getSootClass(), m );
394                 if( concreteM != null ) ret.add( concreteM );
395             } else throw new RuntimeException  ( "Unrecognized reaching type "+t );
396         }
397         return ret;
398     }
399 
400     // Questions about method invocation.
401 
402     /** Returns true if the method m is visible from code in the class from. */
403     private boolean isVisible( SootClass from, SootMethod m ) {
404         from.checkLevel(SootClass.HIERARCHY);
405         if( m.isPublic() ) return true;
406         if( m.isPrivate() ) {
407             return from.equals( m.getDeclaringClass() );
408         }
409         if( m.isProtected() ) {
410             return canStoreClass( from, m.getDeclaringClass() );
411         }
412         // m is package
413         return from.getJavaPackageName().equals(
414                 m.getDeclaringClass().getJavaPackageName() );
415             //|| canStoreClass( from, m.getDeclaringClass() );
416     }
417 
418     /** Given an object of declared type C, returns the methods which could
419      * be called on an o.f() invocation. */
420     public Set resolveAbstractDispatch(SootClass abstractType, SootMethod m )
421     {
422         String   methodSig = m.getSubSignature();
423         HashSet resolved = new HashSet();
424         HashSet ret = new HashSet();
425         LinkedList worklist = new LinkedList();
426         worklist.add( abstractType );
427         while( !worklist.isEmpty() ) {
428             SootClass concreteType = (SootClass) worklist.removeFirst();
429             SootClass savedConcreteType = concreteType;
430             if( concreteType.isInterface() ) {
431                 worklist.addAll( getAllImplementersOfInterface( concreteType ) );
432                 continue;
433             }
434             Collection c = (Collection) classToSubclasses.get( concreteType );
435             if( c != null ) worklist.addAll( c );
436             if( !concreteType.isAbstract() ) {
437                 while( true ) {
438                     if( resolved.contains( concreteType ) ) break;
439                     resolved.add( concreteType );
440                     if( concreteType.declaresMethod( methodSig ) ) {
441                         SootMethod method = concreteType.getMethod( methodSig );
442                         if( method.isAbstract() )
443                             throw new RuntimeException  ("abstract dispatch resolved to abstract method!\nAbstract Type: "+abstractType+"\nConcrete Type: "+savedConcreteType+"\nMethod: "+m);
444 
445                         if( isVisible( concreteType, m ) ) {
446                             ret.add( concreteType.getMethod( methodSig ) );
447                             break;
448                         }
449                     }
450                     if( !concreteType.hasSuperclass() ) 
451                         throw new RuntimeException  ("could not resolve abstract dispatch!\nAbstract Type: "+abstractType+"\nConcrete Type: "+savedConcreteType+"\nMethod: "+m);
452                     concreteType = concreteType.getSuperclass();
453                 }
454             }
455         }
456         return ret;
457     }
458 
459     /** Given an object of actual type C (o = new C()), returns the method which will be called
460         on an o.f() invocation. */
461     public SootMethod resolveConcreteDispatch(SootClass concreteType, SootMethod m)
462     {
463         concreteType.checkLevel(SootClass.HIERARCHY);
464         if( concreteType.isInterface() ) {
465             throw new RuntimeException  (
466                 "A concrete type cannot be an interface: "+concreteType );
467         }
468         if( concreteType.isAbstract() ) {
469             throw new RuntimeException  (
470                 "A concrete type cannot be abstract: "+concreteType );
471         }
472 
473         String   methodSig = m.getSubSignature();
474         while( true ) {
475             if( concreteType.declaresMethod( methodSig ) ) {
476                 if( isVisible( concreteType, m ) ) {
477                     return concreteType.getMethod( methodSig );
478                 }
479             }
480             if( !concreteType.hasSuperclass() ) break;
481             concreteType = concreteType.getSuperclass();
482         }
483         throw new RuntimeException  ("could not resolve concrete dispatch!\nType: "+concreteType+"\nMethod: "+m);
484     }
485 
486     /** Returns the target for the given SpecialInvokeExpr. */
487     public SootMethod resolveSpecialDispatch(SpecialInvokeExpr ie, SootMethod container)
488     {
489         SootMethod target = ie.getMethod();
490 
491         /* This is a bizarre condition!  Hopefully the implementation is correct.
492            See VM Spec, 2nd Edition, Chapter 6, in the definition of invokespecial. */
493         if (target.getName().equals("<init>") || target.isPrivate())
494             return target;
495         else if (isSubclass(target.getDeclaringClass(), container.getDeclaringClass()))
496             return resolveConcreteDispatch(container.getDeclaringClass(), target );
497         else
498             return target;
499     }
500 
501     public Collection getSubclassesOf( SootClass c ) {
502         c.checkLevel(SootClass.HIERARCHY);
503         Collection ret = (Collection) classToSubclasses.get(c);
504         if( ret == null ) return Collections.EMPTY_LIST;
505         return ret;
506     }
507 }
508
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags