Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /* Soot - a J*va Optimization Framework
   * Copyright (C) 2002 Ondrej Lhotak
   *
   * This library is free software; you can redistribute it and/or
   * modify it under the terms of the GNU Lesser General Public
   * License as published by the Free Software Foundation; either
   * version 2.1 of the License, or (at your option) any later version.
   *
   * This library is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  * Lesser General Public License for more details.
  *
  * You should have received a copy of the GNU Lesser General Public
  * License along with this library; if not, write to the
  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  * Boston, MA 02111-1307, USA.
  */
 
 package soot;
 
 import soot.jimple.*;
 import soot.util.*;
 import java.util.*;

Represents the class hierarchy. It is closely linked to a Scene, and must be recreated if the Scene changes. This version supercedes the old soot.Hierarchy class.

Author(s):
Ondrej Lhotak
 
 public class FastHierarchy
 {
     private static void putMap<ObjectListmObject keyObject value ) {
         List<Objectl = m.getkey );
         ifl == null ) m.putkeyl = new ArrayList<Object>() );
         l.addvalue );
     }
    
    
This map holds all key,value pairs such that value.getSuperclass() == key. This is one of the three maps that hold the inverse of the relationships given by the getSuperclass and getInterfaces methods of SootClass.
 
     protected Map<ObjectListclassToSubclasses = new HashMap<ObjectList>();

    
This map holds all key,value pairs such that value is an interface and key is in value.getInterfaces(). This is one of the three maps that hold the inverse of the relationships given by the getSuperclass and getInterfaces methods of SootClass.
 
     protected MultiMap interfaceToSubinterfaces = new HashMultiMap();

    
This map holds all key,value pairs such that value is a class (NOT an interface) and key is in value.getInterfaces(). This is one of the three maps that hold the inverse of the relationships given by the getSuperclass and getInterfaces methods of SootClass.
 
     protected MultiMap interfaceToImplementers = new HashMultiMap();

    
This map is a transitive closure of interfaceToSubinterfaces, and each set contains its superinterface itself.
 
     protected MultiMap interfaceToAllSubinterfaces = new HashMultiMap();

    
This map gives, for an interface, all concrete classes that implement that interface and all its subinterfaces, but NOT their subclasses.
 
     protected MultiMap interfaceToAllImplementers = new HashMultiMap();

    
For each class (NOT interface), this map contains a Interval, which is a pair of numbers giving a preorder and postorder ordering of classes in the inheritance tree.
 
     protected Map<SootClassIntervalclassToInterval = new HashMap<SootClassInterval>();

    
These maps cache subtype queries, so they can be re-done quickly.
 
     //protected MultiMap cacheSubtypes = new HashMultiMap();
     //protected MultiMap cacheNonSubtypes = new HashMultiMap();
 
     protected Scene sc;
 
     protected class Interval {
         int lower;
         int upper;
         boolean isSubrangeInterval potentialSubrange ) {
             if > potentialSubrange.lower ) return false;
             if < potentialSubrange.upper ) return false;
             return true;
         }
     }
     protected int dfsVisitint startSootClass c ) {
         Interval r = new Interval();
         r.lower = start++;
         Collection col = .get(c);
         ifcol != null ) {
             Iterator it = col.iterator();
             whileit.hasNext() ) {
                 SootClass sc = (SootClassit.next();
                 // For some awful reason, Soot thinks interface are subclasses
                 // of java.lang.Object
                 ifsc.isInterface() ) continue;
                 start = dfsVisitstartsc );
            }
        }
        r.upper = start++;
        ifc.isInterface() ) {
            throw new RuntimeException"Attempt to dfs visit interface "+c );
        }
        if(!.containsKey(c))
        	.putcr );
        return start;
    }

    
Constructs a hierarchy from the current scene.
    public FastHierarchy()
    {
        this. = Scene.v();
        /* First build the inverse maps. */
        forIterator clIt = .getClasses().iterator(); clIt.hasNext(); ) {
            final SootClass cl = (SootClassclIt.next();
            ifcl.resolvingLevel() < . ) continue;
            if( !cl.isInterface() && cl.hasSuperclass() ) {
                putcl.getSuperclass(), cl );
            }
            forIterator superclIt = cl.getInterfaces().iterator(); superclIt.hasNext(); ) {
                final SootClass supercl = (SootClasssuperclIt.next();
                ifcl.isInterface() ) {
                    .putsuperclcl );
                } else {
                    .putsuperclcl );
                }
            }
        }
        /* Now do a dfs traversal to get the Interval numbers. */
        dfsVisit( 0, Scene.v().getSootClass"java.lang.Object" ) );
        /* also have to traverse for all phantom classes because they also
         * can be roots of the type hierarchy
         */
        for(SootClass phantomClass: Scene.v().getPhantomClasses()) {
        	if(!phantomClass.isInterface())
        		dfsVisit( 0, phantomClass );
        }
    }

    
Return true if class child is a subclass of class parent, neither of them being allowed to be interfaces.
    public boolean isSubclassSootClass childSootClass parent ) {
        child.checkLevel(.);
        parent.checkLevel(.);
        Interval parentInterval = .getparent );
        Interval childInterval = .getchild );
        return parentInterval.isSubrangechildInterval );
    }

    
For an interface parent (MUST be an interface), returns set of all implementers of it but NOT their subclasses.
    public Set getAllImplementersOfInterfaceSootClass parent ) {
        parent.checkLevel(.);
        if( !.containsKeyparent ) ) {
            forIterator subinterfaceIt = getAllSubinterfacesparent ).iterator(); subinterfaceIt.hasNext(); ) {
                final SootClass subinterface = (SootClasssubinterfaceIt.next();
                ifsubinterface == parent ) continue;
                .putAll(parent,
                    getAllImplementersOfInterfacesubinterface ) );
            }
            .putAll(parent
                    .getparent ) );
        }
        return .getparent );
    }

    
For an interface parent (MUST be an interface), returns set of all subinterfaces.
    protected Set getAllSubinterfacesSootClass parent ) {
        parent.checkLevel(.);
        if( !.containsKeyparent ) ) {
            .putparentparent );
            forIterator it = .getparent ).iterator(); it.hasNext(); ) {
                .putAll(parent
                    getAllSubinterfaces( (SootClassit.next() ) );
            }
        }
        return .getparent );
    }

    
Given an object of declared type child, returns true if the object can be stored in a variable of type parent. If child is an interface that is not a subinterface of parent, this method will return false even though some objects implementing the child interface may also implement the parent interface.
    /*
    public boolean canStoreType( Type child, Type parent ) {
        if( cacheSubtypes.get( parent ).contains( child ) ) return true;
        if( cacheNonSubtypes.get( parent ).contains( child ) ) return false;
        boolean ret = canStoreTypeInternal( child, parent );
        ( ret ? cacheSubtypes : cacheNonSubtypes ).put( parent, child );
        return ret;
    }
    */

    
Given an object of declared type child, returns true if the object can be stored in a variable of type parent. If child is an interface that is not a subinterface of parent, this method will return false even though some objects implementing the child interface may also implement the parent interface.
    public boolean canStoreTypeType childType parent ) {
        ifchild.equalsparent ) ) return true;
        ifparent instanceof NullType ) {
            return false;
        }
        ifchild instanceof NullType ) {
        	return parent instanceof RefLikeType;
        }
        ifchild instanceof RefType ) {
            ifparent instanceof RefType) {
                return canStoreClass( ((RefTypechild).getSootClass(),
                    ((RefTypeparent).getSootClass() );
            } else {
                return false;
            }
        } else ifchild instanceof AnySubType ) {
            if( !(parent instanceof RefLikeType ) ) {
                throw new RuntimeException"Unhandled type "+parent );
            } else if(parent instanceof ArrayType) {
                Type base = ((AnySubType)child).getBase();
                // From Java Language Spec 2nd ed., Chapter 10, Arrays
                return base.equals( RefType.v"java.lang.Object" ) )
                || base.equals( RefType.v"java.io.Serializable" ) )
                || base.equals( RefType.v"java.lang.Cloneable" ) );
            } else {
                SootClass base = ((AnySubType)child).getBase().getSootClass();
                SootClass parentClass = ((RefTypeparent).getSootClass();
                LinkedList worklist = new LinkedList();
                ifbase.isInterface() ) worklist.addAll(getAllImplementersOfInterface(base));
                else worklist.add(base);
                Set<SootClassworkset = new HashSet<SootClass>();
                while(!worklist.isEmpty()) {
                    SootClass cl = (SootClassworklist.removeFirst();
                    if( !workset.add(cl) ) continue;
                    ifcl.isConcrete() 
                    &&  canStoreClass(clparentClass) ) return true;
                    worklist.addAll(getSubclassesOf(cl));
                }
                return false;
            }
        } else {
            ArrayType achild = (ArrayTypechild;
            ifparent instanceof RefType ) {
                // From Java Language Spec 2nd ed., Chapter 10, Arrays
                return parent.equals( RefType.v"java.lang.Object" ) )
                || parent.equals( RefType.v"java.io.Serializable" ) )
                || parent.equals( RefType.v"java.lang.Cloneable" ) );
            }
            ArrayType aparent = (ArrayTypeparent;
                                                
            // You can store a int[][] in a Object[]. Yuck!
            // Also, you can store a Interface[] in a Object[]
            ifachild.numDimensions == aparent.numDimensions ) {
                ifachild.baseType.equalsaparent.baseType ) ) return true;
                if( !(achild.baseType instanceof RefType ) ) return false;
                if( !(aparent.baseType instanceof RefType ) ) return false;
                return canStoreTypeachild.baseTypeaparent.baseType );
            } else ifachild.numDimensions > aparent.numDimensions ) {
                ifaparent.baseType.equals( RefType.v"java.lang.Object" ) ) )
                    return true;
                ifaparent.baseType.equals( RefType.v"java.io.Serializable" ) ) )
                    return true;
                ifaparent.baseType.equals( RefType.v"java.lang.Cloneable" ) ) )
                    return true;
                return false;
            } else return false;
        }
    }

    
Given an object of declared type child, returns true if the object can be stored in a variable of type parent. If child is an interface that is not a subinterface of parent, this method will return false even though some objects implementing the child interface may also implement the parent interface.
    protected boolean canStoreClassSootClass childSootClass parent ) {
        parent.checkLevel(.);
        child.checkLevel(.);
        Interval parentInterval = .getparent );
        Interval childInterval = .getchild );
        ifparentInterval != null && childInterval != null ) {
            return parentInterval.isSubrangechildInterval );
        }
        ifchildInterval == null ) { // child is interface
            ifparentInterval != null ) { // parent is not interface
                return parent.equals( RefType.v("java.lang.Object").getSootClass() );
            } else {
                return getAllSubinterfacesparent ).containschild );
            }
        } else {
            Set impl = getAllImplementersOfInterfaceparent );
            forIterator it = impl.iterator(); it.hasNext(); ) {
                parentInterval = .getit.next() );
                ifparentInterval != null && parentInterval.isSubrangechildInterval ) ) {
                    return true;
                }
            }
            return false;
        }
    }
    public Collection<SootMethodresolveConcreteDispatchWithoutFailing(Collection concreteTypesSootMethod mRefType declaredTypeOfBase ) {
        Set<SootMethodret = new HashSet<SootMethod>();
        SootClass declaringClass = declaredTypeOfBase.getSootClass();
        declaringClass.checkLevel(.);
        forIterator tIt = concreteTypes.iterator(); tIt.hasNext(); ) {
            final Type t = (TypetIt.next();
            ift instanceof AnySubType ) {
                String methodSig = m.getSubSignature();
                HashSet s = new HashSet();
                s.adddeclaringClass );
                while( !s.isEmpty() ) {
                    SootClass c = (SootClasss.iterator().next();
                    s.removec );
                    if( !c.isInterface() && !c.isAbstract()
                            && canStoreClasscdeclaringClass ) ) {
                        SootMethod concreteM = resolveConcreteDispatchcm );
                        ifconcreteM != null )
                            ret.addconcreteM );
                    }
                    if.containsKeyc ) ) {
                        s.addAll.getc ) );
                    }
                    if.containsKeyc ) ) {
                        s.addAll.getc ) );
                    }
                    if.containsKeyc ) ) {
                        s.addAll.getc ) );
                    }
                }
                return ret;
            } else ift instanceof RefType ) {
                RefType concreteType = (RefTypet;
                SootClass concreteClass = concreteType.getSootClass();
                if( !canStoreClassconcreteClassdeclaringClass ) ) {
                    continue;
                }
                SootMethod concreteM = null;
                try {
                    concreteM = resolveConcreteDispatchconcreteClassm );
                } catchException e ) {
                    concreteM = null;
                }
                ifconcreteM != null ) ret.addconcreteM );
            } else ift instanceof ArrayType ) {
                SootMethod concreteM = null;
                try {
                    concreteM = resolveConcreteDispatch
                        RefType.v"java.lang.Object" ).getSootClass(), m );
                } catchException e ) {
                    concreteM = null;
                }
                ifconcreteM != null ) ret.addconcreteM );
            } else throw new RuntimeException"Unrecognized reaching type "+t );
        }
        return ret;
    }
    public Collection<SootMethodresolveConcreteDispatch(Collection concreteTypesSootMethod mRefType declaredTypeOfBase ) {
        Set<SootMethodret = new HashSet<SootMethod>();
        SootClass declaringClass = declaredTypeOfBase.getSootClass();
        declaringClass.checkLevel(.);
        forIterator tIt = concreteTypes.iterator(); tIt.hasNext(); ) {
            final Type t = (TypetIt.next();
            ift instanceof AnySubType ) {
                String methodSig = m.getSubSignature();
                HashSet s = new HashSet();
                s.adddeclaringClass );
                while( !s.isEmpty() ) {
                    SootClass c = (SootClasss.iterator().next();
                    s.removec );
                    if( !c.isInterface() && !c.isAbstract()
                            && canStoreClasscdeclaringClass ) ) {
                        SootMethod concreteM = resolveConcreteDispatchcm );
                        ifconcreteM != null )
                            ret.addconcreteM );
                    }
                    if.containsKeyc ) ) {
                        s.addAll.getc ) );
                    }
                    if.containsKeyc ) ) {
                        s.addAll.getc ) );
                    }
                    if.containsKeyc ) ) {
                        s.addAll.getc ) );
                    }
                }
                return ret;
            } else ift instanceof RefType ) {
                RefType concreteType = (RefTypet;
                SootClass concreteClass = concreteType.getSootClass();
                if( !canStoreClassconcreteClassdeclaringClass ) ) {
                    continue;
                }
                SootMethod concreteM = resolveConcreteDispatchconcreteClassm );
                ifconcreteM != null ) ret.addconcreteM );
            } else ift instanceof ArrayType ) {
                SootMethod concreteM = resolveConcreteDispatch
                        RefType.v"java.lang.Object" ).getSootClass(), m );
                ifconcreteM != null ) ret.addconcreteM );
            } else throw new RuntimeException"Unrecognized reaching type "+t );
        }
        return ret;
    }
    // Questions about method invocation.

    
Returns true if the method m is visible from code in the class from.
    private boolean isVisibleSootClass fromSootMethod m ) {
        from.checkLevel(.);
        ifm.isPublic() ) return true;
        ifm.isPrivate() ) {
            return from.equalsm.getDeclaringClass() );
        }
        ifm.isProtected() ) {
            return canStoreClassfromm.getDeclaringClass() );
        }
        // m is package
        return from.getJavaPackageName().equals(
                m.getDeclaringClass().getJavaPackageName() );
            //|| canStoreClass( from, m.getDeclaringClass() );
    }

    
Given an object of declared type C, returns the methods which could be called on an o.f() invocation.
    public Set<SootMethodresolveAbstractDispatch(SootClass abstractTypeSootMethod m )
    {
        String methodSig = m.getSubSignature();
        HashSet<SootClassresolved = new HashSet<SootClass>();
        HashSet<SootMethodret = new HashSet<SootMethod>();
        LinkedList worklist = new LinkedList();
        worklist.addabstractType );
        while( !worklist.isEmpty() ) {
            SootClass concreteType = (SootClassworklist.removeFirst();
            SootClass savedConcreteType = concreteType;
            ifconcreteType.isInterface() ) {
                worklist.addAllgetAllImplementersOfInterfaceconcreteType ) );
                continue;
            }
            Collection c = .getconcreteType );
            ifc != null ) worklist.addAllc );
            if( !concreteType.isAbstract() ) {
                whiletrue ) {
                    ifresolved.containsconcreteType ) ) break;
                    resolved.addconcreteType );
                    ifconcreteType.declaresMethodmethodSig ) ) {
                        SootMethod method = concreteType.getMethodmethodSig );
                        ifmethod.isAbstract() )
                            throw new RuntimeException("abstract dispatch resolved to abstract method!\nAbstract Type: "+abstractType+"\nConcrete Type: "+savedConcreteType+"\nMethod: "+m);
                        ifisVisibleconcreteTypem ) ) {
                            ret.addconcreteType.getMethodmethodSig ) );
                            break;
                        }
                    }
                    if( !concreteType.hasSuperclass() ) 
                        throw new RuntimeException("could not resolve abstract dispatch!\nAbstract Type: "+abstractType+"\nConcrete Type: "+savedConcreteType+"\nMethod: "+m);
                    concreteType = concreteType.getSuperclass();
                }
            }
        }
        return ret;
    }

    
Given an object of actual type C (o = new C()), returns the method which will be called on an o.f() invocation.
    public SootMethod resolveConcreteDispatch(SootClass concreteTypeSootMethod m)
    {
        concreteType.checkLevel(.);
        ifconcreteType.isInterface() ) {
            throw new RuntimeException(
                "A concrete type cannot be an interface: "+concreteType );
        }
        String methodSig = m.getSubSignature();
        whiletrue ) {
            ifconcreteType.declaresMethodmethodSig ) ) {
                ifisVisibleconcreteTypem ) ) {
                    SootMethod method = concreteType.getMethodmethodSig );
                    if(method.isAbstract()) {
                    	throw new RuntimeException("Error: Method call resolves to abstract method!");
                    }
					return method;
                }
            }
            if( !concreteType.hasSuperclass() ) break;
            concreteType = concreteType.getSuperclass();
        }
     // When there is no proper dispatch found, we simply return null to let the caller decide what to do 
        return null;
//        throw new RuntimeException("could not resolve concrete dispatch!\nType: "+concreteType+"\nMethod: "+m);
    }

    
Returns the target for the given SpecialInvokeExpr.
    {
        SootMethod target = ie.getMethod();
        /* This is a bizarre condition!  Hopefully the implementation is correct.
           See VM Spec, 2nd Edition, Chapter 6, in the definition of invokespecial. */
        if (target.getName().equals("<init>") || target.isPrivate())
            return target;
        else if (isSubclass(target.getDeclaringClass(), container.getDeclaringClass()))
            return resolveConcreteDispatch(container.getDeclaringClass(), target );
        else
            return target;
    }
    public Collection getSubclassesOfSootClass c ) {
        c.checkLevel(.);
        Collection ret = .get(c);
        ifret == null ) return .;
        return ret;
    }
New to GrepCode? Check out our FAQ X