Class PropagationCallGraphBuilder

  • All Implemented Interfaces:
    CallGraphBuilder
    Direct Known Subclasses:
    AbstractRTABuilder, SSAPropagationCallGraphBuilder

    public abstract class PropagationCallGraphBuilder
    extends Object
    implements CallGraphBuilder
    This abstract base class provides the general algorithm for a call graph builder that relies on propagation through an iterative dataflow solver TODO: This implementation currently keeps all points to sets live ... even those for local variables that do not span interprocedural boundaries. This may be too space-inefficient .. we can consider recomputing local sets on demand.
    • Field Detail

      • pointerKeyFactory

        protected PointerKeyFactory pointerKeyFactory
        Meta-data regarding how pointers are modeled
      • options

        protected final AnalysisOptions options
        Special rules for bypassing Java calls
      • entrypointCallSites

        protected final Set<CallSiteReference> entrypointCallSites
        Set of calls (CallSiteReferences) that are created by entrypoints
      • system

        protected PropagationSystem system
        The system of constraints used to build this graph
      • callGraph

        protected final ExplicitCallGraph callGraph
        The call graph under construction
      • assignOperator

        protected static final com.ibm.wala.ipa.callgraph.propagation.AssignOperator assignOperator
        Singleton operator for assignments
      • contextSelector

        protected ContextSelector contextSelector
        A context selector which may use information derived from the propagation-based dataflow.
      • instanceKeyFactory

        protected InstanceKeyFactory instanceKeyFactory
        An object that abstracts how to model instances in the heap.
    • Constructor Detail

      • PropagationCallGraphBuilder

        protected PropagationCallGraphBuilder​(IClassHierarchy cha,
                                              AnalysisOptions options,
                                              AnalysisCache cache,
                                              PointerKeyFactory pointerKeyFactory)
        Parameters:
        cha - governing class hierarchy
        options - governing call graph construction options
        pointerKeyFactory - factory which embodies pointer abstraction policy
    • Method Detail

      • isJavaLangObject

        protected boolean isJavaLangObject​(IClass klass)
        Returns:
        true iff the klass represents java.lang.Object
      • customInit

        protected void customInit()
      • addConstraintsFromNewNodes

        protected boolean addConstraintsFromNewNodes​(MonitorUtil.IProgressMonitor monitor)
                                              throws CancelException
        Add constraints from newly discovered nodes. Note: the act of adding constraints may discover new nodes, so this routine is iterative.
        Returns:
        true iff any new constraints are added.
        Throws:
        CancelException
      • getPointerKeyForLocal

        public PointerKey getPointerKeyForLocal​(CGNode node,
                                                int valueNumber)
        Returns:
        the PointerKey that acts as a representative for the class of pointers that includes the local variable identified by the value number parameter.
      • getFilteredPointerKeyForLocal

        public FilteredPointerKey getFilteredPointerKeyForLocal​(CGNode node,
                                                                int valueNumber,
                                                                FilteredPointerKey.TypeFilter filter)
        Returns:
        the PointerKey that acts as a representative for the class of pointers that includes the local variable identified by the value number parameter.
      • getPointerKeyForReturnValue

        public PointerKey getPointerKeyForReturnValue​(CGNode node)
        Returns:
        the PointerKey that acts as a representative for the class of pointers that includes the return value for a node
      • getPointerKeyForExceptionalReturnValue

        public PointerKey getPointerKeyForExceptionalReturnValue​(CGNode node)
        Returns:
        the PointerKey that acts as a representative for the class of pointers that includes the exceptional return value
      • getPointerKeyForStaticField

        public PointerKey getPointerKeyForStaticField​(IField f)
        Returns:
        the PointerKey that acts as a representative for the class of pointers that includes the contents of the static field
      • getPointerKeyForArrayContents

        public PointerKey getPointerKeyForArrayContents​(InstanceKey I)
        TODO: expand this API to differentiate between different array indices
        Parameters:
        I - an InstanceKey representing an abstract array
        Returns:
        the PointerKey that acts as a representation for the class of pointers that includes the given array contents, or null if none found.
        Throws:
        IllegalArgumentException - if I is null
      • assignInstanceToCatch

        protected void assignInstanceToCatch​(PointerKey exceptionVar,
                                             Set<IClass> catchClasses,
                                             InstanceKey e)
        Handle assign of a particular exception instance into an exception variable
        Parameters:
        exceptionVar - points-to set for a variable representing a caught exception
        catchClasses - set of TypeReferences that the exceptionVar may catch
        e - a particular exception instance
      • addAssignmentsForCatchPointerKey

        protected void addAssignmentsForCatchPointerKey​(PointerKey exceptionVar,
                                                        Set<IClass> catchClasses,
                                                        PointerKey e)
        Generate a set of constraints to represent assignment to an exception variable in a catch clause. Note that we use FilterOperator to filter out types that the exception handler doesn't catch.
        Parameters:
        exceptionVar - points-to set for a variable representing a caught exception
        catchClasses - set of TypeReferences that the exceptionVar may catch
        e - points-to-set representing a thrown exception that might be caught.
      • catches

        public static boolean catches​(Set<IClass> catchClasses,
                                      IClass klass,
                                      IClassHierarchy cha)
        Parameters:
        catchClasses - Set of TypeReference
        klass - an Exception Class
        Returns:
        true iff klass is a subclass of some element of the Set
        Throws:
        IllegalArgumentException - if catchClasses is null
      • getJavaLangObject

        public IClass getJavaLangObject()
      • setContextInterpreter

        public void setContextInterpreter​(SSAContextInterpreter interpreter)
        Subclasses must register the context interpreter before building a call graph.
      • setPointerKeyFactory

        public void setPointerKeyFactory​(PointerKeyFactory pkFact)
        BEGIN Custom change: setter for pointerkey factory
      • getContextInterpreter

        public RTAContextInterpreter getContextInterpreter()
        END Custom change: setter for pointerkey factory
      • getTargetForCall

        protected CGNode getTargetForCall​(CGNode caller,
                                          CallSiteReference site,
                                          IClass recv,
                                          InstanceKey[] iKey)
        Parameters:
        caller - the caller node
        iKey - an abstraction of the receiver of the call (or null if not applicable)
        Returns:
        the CGNode to which this particular call should dispatch.
      • getContextSelector

        public ContextSelector getContextSelector()
        Returns:
        the context selector for this call graph builder
      • setContextSelector

        public void setContextSelector​(ContextSelector selector)
      • getInstanceKeyForAllocation

        public InstanceKey getInstanceKeyForAllocation​(CGNode node,
                                                       NewSiteReference allocation)
        Returns:
        the InstanceKey that acts as a representative for the class of objects that includes objects allocated at the given new instruction in the given node
      • getInstanceKeyForMultiNewArray

        public InstanceKey getInstanceKeyForMultiNewArray​(CGNode node,
                                                          NewSiteReference allocation,
                                                          int dim)
        Parameters:
        dim - the dimension of the array whose instance we would like to model. dim == 0 represents the first dimension, e.g., the [Object; instances in [[Object; e.g., the [[Object; instances in [[[Object; dim == 1 represents the second dimension, e.g., the [Object instances in [[[Object;
        Returns:
        the InstanceKey that acts as a representative for the class of array contents objects that includes objects allocated at the given new instruction in the given node
      • haveAlreadyVisited

        public boolean haveAlreadyVisited​(CGNode node)
      • markAlreadyVisited

        protected void markAlreadyVisited​(CGNode node)
      • markDiscovered

        public void markDiscovered​(CGNode node)
        record that we've discovered a node
      • markChanged

        protected void markChanged​(CGNode node)
      • wasChanged

        protected boolean wasChanged​(CGNode node)
      • getMutableInstanceKeysForClass

        protected MutableIntSet getMutableInstanceKeysForClass​(IClass klass)
      • getInstanceKeysForClass

        protected IntSet getInstanceKeysForClass​(IClass klass)
      • filterForClass

        protected IntSet filterForClass​(IntSet S,
                                        IClass klass)
        Parameters:
        klass - a class
        Returns:
        an int set which represents the subset of S that correspond to subtypes of klass