Package soot

Class FastHierarchy

  • public class FastHierarchy
extends Object
    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:
    Ondrej Lhotak, Manuel Benz 22.10.19 - Fixed concrete/abstract dispatch methods to car for default interface methods and account for overwritten return types

    • Field Detail

      • USE_INTERVALS_BOUNDARY

        protected static final int USE_INTERVALS_BOUNDARY
        See Also:
        Constant Field Values

      • classToSubclasses

        protected MultiMap<SootClass,​SootClass> classToSubclasses
        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.

      • interfaceToSubinterfaces

        protected MultiMap<SootClass,​SootClass> interfaceToSubinterfaces
        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.

      • interfaceToImplementers

        protected MultiMap<SootClass,​SootClass> interfaceToImplementers
        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.

      • interfaceToAllSubinterfaces

        protected MultiMap<SootClass,​SootClass> interfaceToAllSubinterfaces
        This map is a transitive closure of interfaceToSubinterfaces, and each set contains its superinterface itself.

      • interfaceToAllImplementers

        protected MultiMap<SootClass,​SootClass> interfaceToAllImplementers
        This map gives, for an interface, all concrete classes that implement that interface and all its subinterfaces, but NOT their subclasses.

      • classToInterval

        protected Map<SootClass,​FastHierarchy.Interval> classToInterval
        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.

      • sc

        protected final Scene sc

      • rtObject

        protected final RefType rtObject

      • rtSerializable

        protected final RefType rtSerializable

      • rtCloneable

        protected final RefType rtCloneable

      • cilArray

        protected final RefType cilArray

      • cilIcomparable1

        protected final RefType cilIcomparable1

      • cilIcomparable

        protected final RefType cilIcomparable

      • cilIconvertible

        protected final RefType cilIconvertible

      • cilIequatable1

        protected final RefType cilIequatable1

      • cilIformattable

        protected final RefType cilIformattable

    • Constructor Detail

      • FastHierarchy

        public FastHierarchy()
        Constructs a hierarchy from the current scene.

    • Method Detail

      • dfsVisit

        protected int dfsVisit​(int start,
                       SootClass c)

      • buildInverseMaps

        protected void buildInverseMaps()

      • isSubclass

        public boolean isSubclass​(SootClass child,
                          SootClass parent)
        Return true if class child is a subclass of class parent, neither of them being allowed to be interfaces. If we don't know any of the classes, we always return false

      • getAllImplementersOfInterface

        public Set<SootClass> getAllImplementersOfInterface​(SootClass parent)
        For an interface parent (MUST be an interface), returns set of all implementers of it but NOT their subclasses.

        This method can be used concurrently (is thread safe).

        Parameters:
        parent - the parent interface.
        Returns:
        an set, possibly empty

      • getAllSubinterfaces

        public Set<SootClass> getAllSubinterfaces​(SootClass parent)
        For an interface parent (MUST be an interface), returns set of all subinterfaces including parent.

        This method can be used concurrently (is thread safe).

        Parameters:
        parent - the parent interface.
        Returns:
        an set, possibly empty

      • canStoreType

        public boolean canStoreType​(Type child,
                            Type parent)
        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.

      • canStoreClass

        public boolean canStoreClass​(SootClass child,
                             SootClass parent)
        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.

      • canStoreClassClassic

        protected boolean canStoreClassClassic​(SootClass child,
                                       SootClass parent)
        "Classic" implementation using the intuitive approach (without using FastHierarchy.Interval) to check whether child can be stored in a type of parent:

        If parent is not an interface we simply traverse and check the super-classes of child.

        If parent is an interface we traverse the super-classes of child and check each interface implemented by this class. Also each interface is checked recursively for super interfaces it implements.

        This implementation can be much faster (compared to the interval based implementation of canStoreClass(SootClass, SootClass) in cases where one interface is implemented in thousands of classes.

        Parameters:
        child -
        parent -
        Returns:

      • resolveAbstractDispatch

        public Set<SootMethod> resolveAbstractDispatch​(SootClass baseType,
                                               SootMethod m)
        Given an object of declared type C, returns the methods which could be called on an o.f() invocation.
        Parameters:
        baseType - The declared type C

      • resolveAbstractDispatch

        public Set<SootMethod> resolveAbstractDispatch​(SootClass baseType,
                                               SootMethodRef m)
        Given an object of declared type C, returns the methods which could be called on an o.f() invocation.
        Parameters:
        baseType - The declared type C

      • resolveConcreteDispatch

        public SootMethod resolveConcreteDispatch​(SootClass baseType,
                                          SootMethod m)
        Given an object of actual type C (o = new C()), returns the method which will be called on an o.f() invocation.
        Parameters:
        baseType - The actual type C

      • resolveConcreteDispatch

        public SootMethod resolveConcreteDispatch​(SootClass baseType,
                                          SootMethodRef m)
        Given an object of actual type C (o = new C()), returns the method which will be called on an o.f() invocation.
        Parameters:
        baseType - The actual type C

      • resolveMethod

        public SootMethod resolveMethod​(SootClass baseType,
                                SootMethod m,
                                boolean allowAbstract)
        Conducts the actual dispatch by searching up the baseType's superclass hierarchy and interface hierarchy if the sourcecode level is beyond Java 7 (due to default interface methods.) Given an object of actual type C (o = new C()), returns the method which will be called on an o.f() invocation.

        If abstract methods are allowed, it will just resolve to the first method found according to javas method resolution process: https://docs.oracle.com/javase/specs/jvms/se8/html/jvms-5.html#jvms-5.4.3.3

        Parameters:
        baseType - The type C
        m - The method f to resolve
        Returns:
        The concrete method o.f() to call

      • resolveMethod

        public SootMethod resolveMethod​(SootClass baseType,
                                SootMethodRef m,
                                boolean allowAbstract)
        Conducts the actual dispatch by searching up the baseType's superclass hierarchy and interface hierarchy if the sourcecode level is beyond Java 7 (due to default interface methods.) Given an object of actual type C (o = new C()), returns the method which will be called on an o.f() invocation.

        If abstract methods are allowed, it will just resolve to the first method found according to javas method resolution process: https://docs.oracle.com/javase/specs/jvms/se8/html/jvms-5.html#jvms-5.4.3.3

        Parameters:
        baseType - The type C
        m - The method f to resolve
        Returns:
        The concrete method o.f() to call

      • resolveMethod

        public SootMethod resolveMethod​(SootClass baseType,
                                SootClass declaringClass,
                                String name,
                                List<Type> parameterTypes,
                                Type returnType,
                                boolean allowAbstract)
        Conducts the actual dispatch by searching up the baseType's superclass hierarchy and interface hierarchy if the sourcecode level is beyond Java 7 (due to default interface methods.) Given an object of actual type C (o = new C()), returns the method which will be called on an o.f() invocation.

        If abstract methods are allowed, it will just resolve to the first method found according to javas method resolution process: https://docs.oracle.com/javase/specs/jvms/se8/html/jvms-5.html#jvms-5.4.3.3

        Parameters:
        baseType - The type C
        declaringClass - declaring class of the method to resolve
        name - Name of the method to resolve
        Returns:
        The concrete method o.f() to call

      • resolveMethod

        public SootMethod resolveMethod​(SootClass baseType,
                                SootClass declaringClass,
                                String name,
                                List<Type> parameterTypes,
                                Type returnType,
                                boolean allowAbstract,
                                NumberedString subsignature)
        Conducts the actual dispatch by searching up the baseType's superclass hierarchy and interface hierarchy if the sourcecode level is beyond Java 7 (due to default interface methods.) Given an object of actual type C (o = new C()), returns the method which will be called on an o.f() invocation.

        If abstract methods are allowed, it will just resolve to the first method found according to javas method resolution process: https://docs.oracle.com/javase/specs/jvms/se8/html/jvms-5.html#jvms-5.4.3.3

        Parameters:
        baseType - The type C
        declaringClass - declaring class of the method to resolve
        name - Name of the method to resolve
        subsignature - The subsignature (can be null) to speed up the resolving process.
        Returns:
        The concrete method o.f() to call

      • isHandleDefaultMethods

        protected boolean isHandleDefaultMethods()

      • resolveSpecialDispatch

        public SootMethod resolveSpecialDispatch​(SootMethod callee,
                                         SootMethod container)
        Returns the target for the given SpecialInvokeExpr.

      • getSubclassesOf

        public Collection<SootClass> getSubclassesOf​(SootClass c)
        Gets the direct subclasses of a given class. The class needs to be resolved at least at the HIERARCHY level.
        Parameters:
        c - the class
        Returns:
        a collection (possibly empty) of the direct subclasses

      • canStoreTypeList

        public Iterable<Type> canStoreTypeList​(Type nt)
        Returns a list of types which can be used to store the given type
        Parameters:
        nt - the given type
        Returns:
        the list of types which can be used to store the given type