Package proguard.util

Class CallGraphWalker

  • public class CallGraphWalker
extends java.lang.Object
    Generic utilities to traverse the call graph.

    • Field Detail

      • MAX_DEPTH_DEFAULT

        public static final int MAX_DEPTH_DEFAULT
        Call graph strands are no longer explored after a maximum distance from the original root.
        See Also:
        Constant Field Values

      • MAX_WIDTH_DEFAULT

        public static final int MAX_WIDTH_DEFAULT
        Once the call graph reaches a maximum width, no more nodes are added to the worklist of the next level. E.g. suppose this limit is 5 and we have already discovered the following call graph: 
             
         level2_0 <-- level1_0 <-- root
         level2_1 <------|          |
         level2_2 <------|          |
                                    |
         level2_3 <-- level1_1 <----|
         level2_4 <------|
        If level1_1 has any more known predecessors, level 2 of the call graph would have width 6, which is more than the 5 allowed nodes. Thus, level1_1 is marked as truncated and its other predecessors are discarded.
        See Also:
        Constant Field Values

    • Constructor Detail

      • CallGraphWalker

        public CallGraphWalker()

    • Method Detail

      • getSuccessors

        public static java.util.Set<MethodSignature> getSuccessors​(CallGraph callGraph,
                                                           MethodSignature start,
                                                           int maxDepth,
                                                           int maxWidth)
        Analogous to Soot's getReachableMethods(): Starting from one particular method, all methods that are transitively reachable are collected in a single set. The exploration stops after no more reachable methods have been found, or the reachable call graph exceeds MAX_DEPTH_DEFAULT and MAX_WIDTH_DEFAULT.
        Parameters:
        callGraph - The CallGraph to use as the basis for this exploration
        start - The method that is to be used as the exploration root
        maxDepth - See MAX_DEPTH_DEFAULT
        maxWidth - See MAX_WIDTH_DEFAULT
        Returns:
        A set of all transitively reachable methods

      • successorPathsAccept

        public static Node successorPathsAccept​(CallGraph callGraph,
                                        MethodSignature start,
                                        java.util.function.Predicate<Node> handler,
                                        int maxDepth,
                                        int maxWidth)
        Interactively explore the outgoing call graph (breadth-first) of a specific method.

        Outgoing call graph edges are transitively visited, one level of the call graph at a time. E.g. if we have the following graph: 

             
         level2_0 <-- level1_0 <-- root
         level2_1 <------|          |
         level2_2 <------|          |
                                    |
         level2_3 <-- level1_1 <----|
         level2_4 <------|
        In this case, level1_0 and level1_1 are visited first, then level2_* and so on. The user of this method provides a callback that will be executed for every newly visited path. This handler receives a Node that represents e.g. level2_1 and contains references to all its predecessors that have been visited in this particular path. Like this, the user can evaluate the whole call chain that led to any specific method being reachable from the starting point. Graph limits MAX_DEPTH_DEFAULT and MAX_WIDTH_DEFAULT are applicable. Any paths that are truncated due to any limit being reached, are marked with Node.isTruncated

        If you are only interested in which methods are reachable from a start method, but do not care about the individual paths that make this possible, you should use getSuccessors(CallGraph, MethodSignature) instead.

        Parameters:
        callGraph - The CallGraph to use as the basis of this exploration
        start - The method that is to be used as the exploration root
        handler - The callback function that is invoked for newly visited paths. If this returns false, this specific path is not explored any further, without marking it as truncated.
        maxDepth - See MAX_DEPTH_DEFAULT
        maxWidth - See MAX_WIDTH_DEFAULT
        Returns:
        The Node representing the start method and all its successors

      • successorPathsAccept

        public static Node successorPathsAccept​(CallGraph callGraph,
                                        MethodSignature start,
                                        java.util.function.Predicate<Node> handler)
        Like successorPathsAccept(CallGraph, MethodSignature, Predicate, int, int) but using default values for max depth and max width.
        Parameters:
        callGraph - The CallGraph to use as the basis of this exploration
        start - The method that is to be used as the exploration root
        handler - The callback function that is invoked for newly visited paths. If this returns false, this specific path is not explored any further, without marking it as truncated.
        Returns:
        The Node representing the start method and all its successors

      • predecessorPathsAccept

        public static Node predecessorPathsAccept​(CallGraph callGraph,
                                          MethodSignature start,
                                          java.util.function.Predicate<Node> handler,
                                          int maxDepth,
                                          int maxWidth)
        Interactively explore the incoming call graph (breadth-first) of a specific method.

        Inverse of successorPathsAccept(CallGraph, MethodSignature, Predicate): Explores all methods that can reach the starting point and notifies the user's handler of newly found paths.

        Parameters:
        callGraph - The CallGraph to use as the basis of this exploration
        start - The method that is to be used as the exploration root
        handler - The callback function that is invoked for newly visited paths. If this returns false, this specific path is not explored any further, without marking it as truncated.
        maxDepth - See MAX_DEPTH_DEFAULT
        maxWidth - See MAX_WIDTH_DEFAULT
        Returns:
        The Node representing the start method and all its predecessors

      • predecessorPathsAccept

        public static Node predecessorPathsAccept​(CallGraph callGraph,
                                          MethodSignature start,
                                          java.util.function.Predicate<Node> handler)
        Like predecessorPathsAccept(CallGraph, MethodSignature, Predicate, int, int) but using default values for max depth and max width.
        Parameters:
        callGraph - The CallGraph to use as the basis of this exploration
        start - The method that is to be used as the exploration root
        handler - The callback function that is invoked for newly visited paths. If this returns false, this specific path is not explored any further, without marking it as truncated.
        Returns:
        The Node representing the start method and all its predecessors