Package proguard.util

Class CallGraphWalker

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

  • Field Details

    • 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:

    • 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:

  • Constructor Details

    • CallGraphWalker

      public CallGraphWalker()

  • Method Details

    • getSuccessors

      public static 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

    • getSuccessors

      public static Set<MethodSignature> getSuccessors(CallGraph callGraph, MethodSignature start)
      Like getSuccessors(CallGraph, MethodSignature, int, int) but using default values for max depth and max width.
      Parameters:
      callGraph - The CallGraph to use as the basis for this exploration
      start - The method that is to be used as the exploration root
      Returns:
      A set of all transitively reachable methods

    • getPredecessors

      public static Set<MethodSignature> getPredecessors(CallGraph callGraph, MethodSignature start, int maxDepth, int maxWidth)
      Inverse of getSuccessors(CallGraph, MethodSignature): Starting from one particular method, all methods that can transitively reach it are collected in a single set. The exploration stops after no more incoming methods have been found, or the inversely-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 methods that can transitively reach the root

    • getPredecessors

      public static Set<MethodSignature> getPredecessors(CallGraph callGraph, MethodSignature start)
      Like getPredecessors(CallGraph, MethodSignature, int, int) but using default values for max depth and max width.
      Parameters:
      callGraph - The CallGraph to use as the basis for this exploration
      start - The method that is to be used as the exploration root
      Returns:
      A set of all methods that can transitively reach the root

    • successorPathsAccept

      public static Node successorPathsAccept(CallGraph callGraph, MethodSignature start, 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, 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, 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, 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