proguard.util

Class CallGraphWalker

java.lang.Object

proguard.util.CallGraphWalker

public class CallGraphWalker
extends java.lang.Object

Generic utilities to traverse the call graph.

Field Summary

Fields

Modifier and Type	Field and Description
static int	MAX_DEPTH_DEFAULT Call graph strands are no longer explored after a maximum distance from the original root.
static int	MAX_WIDTH_DEFAULT Once the call graph reaches a maximum width, no more nodes are added to the worklist of the next level.

Constructor Summary

Constructors

Constructor and Description
CallGraphWalker()

Method Summary

Modifier and Type	Method and Description
static java.util.Set<MethodSignature>	getPredecessors(CallGraph callGraph, MethodSignature start) Like getPredecessors(CallGraph, MethodSignature, int, int) but using default values for max depth and max width.
static java.util.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.
static java.util.Set<MethodSignature>	getSuccessors(CallGraph callGraph, MethodSignature start) Like getSuccessors(CallGraph, MethodSignature, int, int) but using default values for max depth and max width.
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.
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.
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.
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.
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.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

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

getSuccessors

public static java.util.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 java.util.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 java.util.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,
                                        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