Package com.ibm.wala.cfg
Class AbstractCFG<I,T extends IBasicBlock<I>>
- java.lang.Object
-
- com.ibm.wala.cfg.AbstractCFG<I,T>
-
- All Implemented Interfaces:
ControlFlowGraph<I,T>
,Constants
,EdgeManager<T>
,Graph<T>
,NodeManager<T>
,NumberedEdgeManager<T>
,NumberedGraph<T>
,NumberedNodeManager<T>
,Iterable<T>
- Direct Known Subclasses:
AstTranslator.AstCFG
,DexCFG
,InducedCFG
,ShrikeCFG
public abstract class AbstractCFG<I,T extends IBasicBlock<I>> extends Object implements ControlFlowGraph<I,T>, Constants
Common functionality forControlFlowGraph
implementations.
-
-
Field Summary
-
Fields inherited from interface com.ibm.wala.shrikeBT.Constants
ACC_ABSTRACT, ACC_FINAL, ACC_INTERFACE, ACC_NATIVE, ACC_PRIVATE, ACC_PROTECTED, ACC_PUBLIC, ACC_STATIC, ACC_STRICT, ACC_SUPER, ACC_SYNCHRONIZED, ACC_TRANSIENT, ACC_VOLATILE, CONSTANT_Class, CONSTANT_Double, CONSTANT_FieldRef, CONSTANT_Float, CONSTANT_Integer, CONSTANT_InterfaceMethodRef, CONSTANT_InvokeDynamic, CONSTANT_Long, CONSTANT_MethodHandle, CONSTANT_MethodRef, CONSTANT_MethodType, CONSTANT_NameAndType, CONSTANT_String, CONSTANT_Utf8, indexedTypes, indexedTypes_T, MAYBE, NO, OP_aaload, OP_aastore, OP_aconst_null, OP_aload, OP_aload_0, OP_aload_1, OP_aload_2, OP_aload_3, OP_anewarray, OP_areturn, OP_arraylength, OP_astore, OP_astore_0, OP_astore_1, OP_astore_2, OP_astore_3, OP_athrow, OP_baload, OP_bastore, OP_bipush, OP_caload, OP_castore, OP_checkcast, OP_d2f, OP_d2i, OP_d2l, OP_dadd, OP_daload, OP_dastore, OP_dcmpg, OP_dcmpl, OP_dconst_0, OP_dconst_1, OP_ddiv, OP_dload, OP_dload_0, OP_dload_1, OP_dload_2, OP_dload_3, OP_dmul, OP_dneg, OP_drem, OP_dreturn, OP_dstore, OP_dstore_0, OP_dstore_1, OP_dstore_2, OP_dstore_3, OP_dsub, OP_dup, OP_dup_x1, OP_dup_x2, OP_dup2, OP_dup2_x1, OP_dup2_x2, OP_f2d, OP_f2i, OP_f2l, OP_fadd, OP_faload, OP_fastore, OP_fcmpg, OP_fcmpl, OP_fconst_0, OP_fconst_1, OP_fconst_2, OP_fdiv, OP_fload, OP_fload_0, OP_fload_1, OP_fload_2, OP_fload_3, OP_fmul, OP_fneg, OP_frem, OP_freturn, OP_fstore, OP_fstore_0, OP_fstore_1, OP_fstore_2, OP_fstore_3, OP_fsub, OP_getfield, OP_getstatic, OP_goto, OP_goto_w, OP_i2b, OP_i2c, OP_i2d, OP_i2f, OP_i2l, OP_i2s, OP_iadd, OP_iaload, OP_iand, OP_iastore, OP_iconst_0, OP_iconst_1, OP_iconst_2, OP_iconst_3, OP_iconst_4, OP_iconst_5, OP_iconst_m1, OP_idiv, OP_if_acmpeq, OP_if_acmpne, OP_if_icmpeq, OP_if_icmpge, OP_if_icmpgt, OP_if_icmple, OP_if_icmplt, OP_if_icmpne, OP_ifeq, OP_ifge, OP_ifgt, OP_ifle, OP_iflt, OP_ifne, OP_ifnonnull, OP_ifnull, OP_iinc, OP_iload, OP_iload_0, OP_iload_1, OP_iload_2, OP_iload_3, OP_imul, OP_ineg, OP_instanceof, OP_invokedynamic, OP_invokeinterface, OP_invokespecial, OP_invokestatic, OP_invokevirtual, OP_ior, OP_irem, OP_ireturn, OP_ishl, OP_ishr, OP_istore, OP_istore_0, OP_istore_1, OP_istore_2, OP_istore_3, OP_isub, OP_iushr, OP_ixor, OP_jsr, OP_jsr_w, OP_l2d, OP_l2f, OP_l2i, OP_ladd, OP_laload, OP_land, OP_lastore, OP_lcmp, OP_lconst_0, OP_lconst_1, OP_ldc, OP_ldc_w, OP_ldc2_w, OP_ldiv, OP_lload, OP_lload_0, OP_lload_1, OP_lload_2, OP_lload_3, OP_lmul, OP_lneg, OP_lookupswitch, OP_lor, OP_lrem, OP_lreturn, OP_lshl, OP_lshr, OP_lstore, OP_lstore_0, OP_lstore_1, OP_lstore_2, OP_lstore_3, OP_lsub, OP_lushr, OP_lxor, OP_monitorenter, OP_monitorexit, OP_multianewarray, OP_new, OP_newarray, OP_nop, OP_pop, OP_pop2, OP_putfield, OP_putstatic, OP_ret, OP_return, OP_saload, OP_sastore, OP_sipush, OP_swap, OP_tableswitch, OP_wide, T_BOOLEAN, T_BYTE, T_CHAR, T_DOUBLE, T_FLOAT, T_INT, T_LONG, T_SHORT, TYPE_boolean, TYPE_boolean_index, TYPE_byte, TYPE_byte_index, TYPE_char, TYPE_char_index, TYPE_Class, TYPE_double, TYPE_double_index, TYPE_Error, TYPE_Exception, TYPE_float, TYPE_float_index, TYPE_int, TYPE_int_index, TYPE_long, TYPE_long_index, TYPE_MethodHandle, TYPE_MethodType, TYPE_null, TYPE_Object, TYPE_Object_index, TYPE_RuntimeException, TYPE_short, TYPE_short_index, TYPE_String, TYPE_Throwable, TYPE_unknown, TYPE_void, YES
-
-
Constructor Summary
Constructors Modifier Constructor Description protected
AbstractCFG(IMethod method)
-
Method Summary
All Methods Instance Methods Abstract Methods Concrete Methods Modifier and Type Method Description void
addEdge(T src, T dst)
void
addExceptionalEdge(T src, T dst)
void
addNode(T n)
add a node to this graphvoid
addNormalEdge(T src, T dst)
boolean
containsNode(T N)
T
entry()
Return the entry basic block for the CFG.abstract boolean
equals(Object o)
T
exit()
Return the exit basic block for the CFG.BitVector
getCatchBlocks()
Returns the catchBlocks.Collection<T>
getExceptionalPredecessors(T b)
The order of blocks returned should be arbitrary but deterministic.List<T>
getExceptionalSuccessors(T b)
The order of blocks returned must indicate the exception-handling scope.FixedSizeBitVector
getExceptionalToExit()
int
getMaxNumber()
IMethod
getMethod()
T
getNode(int number)
Collection<T>
getNormalPredecessors(T b)
The order of blocks returned should be arbitrary but deterministic.Collection<T>
getNormalSuccessors(T b)
The order of blocks returned should be arbitrary but deterministic.FixedSizeBitVector
getNormalToExit()
int
getNumber(T N)
int
getNumberOfExceptionalIn(T N)
int
getNumberOfExceptionalOut(int number)
int
getNumberOfExceptionalOut(T N)
int
getNumberOfNodes()
int
getNumberOfNormalIn(T N)
int
getNumberOfNormalOut(T N)
int
getPredNodeCount(T N)
Return the number ofimmediate predecessor
nodes of nIntSet
getPredNodeNumbers(T node)
Iterator<T>
getPredNodes(T N)
Return anIterator
over the immediate predecessor nodes of n This method never returnsnull
.int
getSuccNodeCount(T N)
Return the number ofimmediate successor
nodes of this Node in the GraphIntSet
getSuccNodeNumbers(T node)
Iterator<T>
getSuccNodes(T N)
Return an Iterator over the immediate successor nodes of nboolean
hasEdge(T src, T dst)
boolean
hasExceptionalEdge(T src, T dst)
abstract int
hashCode()
boolean
hasNormalEdge(T src, T dst)
protected void
init()
subclasses must call this before calling addEdge, but after creating the nodesboolean
isCatchBlock(int i)
Iterator<T>
iterateNodes(IntSet s)
Iterator<T>
iterator()
void
removeAllIncidentEdges(T node)
void
removeEdge(T src, T dst)
void
removeIncomingEdges(T node)
void
removeNode(T n)
remove a node from this graphvoid
removeNodeAndEdges(T N)
remove a node and all its incident edgesvoid
removeOutgoingEdges(T node)
protected void
setCatchBlock(int i)
record that basic block i is a catch blockString
toString()
-
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
-
Methods inherited from interface com.ibm.wala.cfg.ControlFlowGraph
getBlockForInstruction, getInstructions, getProgramCounter
-
Methods inherited from interface java.lang.Iterable
forEach, spliterator
-
-
-
-
Constructor Detail
-
AbstractCFG
protected AbstractCFG(IMethod method)
-
-
Method Detail
-
init
protected void init()
subclasses must call this before calling addEdge, but after creating the nodes
-
entry
public T entry()
Return the entry basic block for the CFG.- Specified by:
entry
in interfaceControlFlowGraph<I,T extends IBasicBlock<I>>
-
exit
public T exit()
Return the exit basic block for the CFG.- Specified by:
exit
in interfaceControlFlowGraph<I,T extends IBasicBlock<I>>
- Returns:
- the synthetic exit block for the cfg
-
getPredNodeCount
public int getPredNodeCount(T N)
Description copied from interface:EdgeManager
Return the number ofimmediate predecessor
nodes of n- Specified by:
getPredNodeCount
in interfaceEdgeManager<I>
- Returns:
- the number of immediate predecessors of n.
-
getNumberOfNormalIn
public int getNumberOfNormalIn(T N)
-
getNumberOfExceptionalIn
public int getNumberOfExceptionalIn(T N)
-
getNumberOfExceptionalOut
public int getNumberOfExceptionalOut(int number)
- Parameters:
number
- number of a basic block in this cfg
-
getNumberOfNormalOut
public int getNumberOfNormalOut(T N)
-
getNumberOfExceptionalOut
public int getNumberOfExceptionalOut(T N)
-
getPredNodes
public Iterator<T> getPredNodes(T N)
Description copied from interface:EdgeManager
Return anIterator
over the immediate predecessor nodes of n This method never returnsnull
.- Specified by:
getPredNodes
in interfaceEdgeManager<I>
- Returns:
- an
Iterator
over the immediate predecessor nodes of this Node.
-
getSuccNodeCount
public int getSuccNodeCount(T N)
Description copied from interface:EdgeManager
Return the number ofimmediate successor
nodes of this Node in the Graph- Specified by:
getSuccNodeCount
in interfaceEdgeManager<I>
- Returns:
- the number of immediate successor Nodes of this Node in the Graph.
-
getSuccNodes
public Iterator<T> getSuccNodes(T N)
Description copied from interface:EdgeManager
Return an Iterator over the immediate successor nodes of nThis method never returns
null
.- Specified by:
getSuccNodes
in interfaceEdgeManager<I>
- Returns:
- an Iterator over the immediate successor nodes of n
-
addNode
public void addNode(T n)
Description copied from interface:NodeManager
add a node to this graph- Specified by:
addNode
in interfaceNodeManager<I>
- Parameters:
n
-
-
getMaxNumber
public int getMaxNumber()
- Specified by:
getMaxNumber
in interfaceNumberedNodeManager<I>
-
getNode
public T getNode(int number)
- Specified by:
getNode
in interfaceNumberedNodeManager<I>
-
getNumber
public int getNumber(T N)
- Specified by:
getNumber
in interfaceNumberedNodeManager<I>
-
getNumberOfNodes
public int getNumberOfNodes()
- Specified by:
getNumberOfNodes
in interfaceNodeManager<I>
- Returns:
- the number of nodes in this graph
-
addEdge
public void addEdge(T src, T dst) throws UnimplementedError
- Specified by:
addEdge
in interfaceEdgeManager<I>
- Throws:
UnimplementedError
-
removeEdge
public void removeEdge(T src, T dst) throws UnsupportedOperationException
- Specified by:
removeEdge
in interfaceEdgeManager<I>
- Throws:
UnsupportedOperationException
-
hasEdge
public boolean hasEdge(T src, T dst)
- Specified by:
hasEdge
in interfaceEdgeManager<I>
-
addNormalEdge
public void addNormalEdge(T src, T dst)
- Throws:
IllegalArgumentException
- if src or dst is null
-
addExceptionalEdge
public void addExceptionalEdge(T src, T dst)
- Throws:
IllegalArgumentException
- if dst is null
-
removeNodeAndEdges
public void removeNodeAndEdges(T N) throws UnimplementedError
Description copied from interface:Graph
remove a node and all its incident edges- Specified by:
removeNodeAndEdges
in interfaceGraph<I>
- Throws:
UnimplementedError
-
removeNode
public void removeNode(T n) throws UnimplementedError
Description copied from interface:NodeManager
remove a node from this graph- Specified by:
removeNode
in interfaceNodeManager<I>
- Throws:
UnimplementedError
-
containsNode
public boolean containsNode(T N)
- Specified by:
containsNode
in interfaceNodeManager<I>
- Returns:
- true iff the graph contains the specified node
-
setCatchBlock
protected void setCatchBlock(int i)
record that basic block i is a catch block
-
isCatchBlock
public boolean isCatchBlock(int i)
- Returns:
- true iff block i is a catch block
-
getCatchBlocks
public BitVector getCatchBlocks()
Returns the catchBlocks.- Specified by:
getCatchBlocks
in interfaceControlFlowGraph<I,T extends IBasicBlock<I>>
- Returns:
- the indices of the catch blocks, as a bit vector
-
getMethod
public IMethod getMethod()
- Specified by:
getMethod
in interfaceControlFlowGraph<I,T extends IBasicBlock<I>>
- Returns:
- the Method this CFG represents
-
removeAllIncidentEdges
public void removeAllIncidentEdges(T node) throws UnimplementedError
- Specified by:
removeAllIncidentEdges
in interfaceEdgeManager<I>
- Throws:
UnimplementedError
-
getExceptionalSuccessors
public List<T> getExceptionalSuccessors(T b)
Description copied from interface:ControlFlowGraph
The order of blocks returned must indicate the exception-handling scope. So the first block is the first candidate catch block, and so on. With this invariant one can compute the exceptional control flow for a given exception type.- Specified by:
getExceptionalSuccessors
in interfaceControlFlowGraph<I,T extends IBasicBlock<I>>
- Returns:
- the basic blocks which may be reached from b via exceptional control flow
-
getNormalSuccessors
public Collection<T> getNormalSuccessors(T b)
Description copied from interface:ControlFlowGraph
The order of blocks returned should be arbitrary but deterministic.- Specified by:
getNormalSuccessors
in interfaceControlFlowGraph<I,T extends IBasicBlock<I>>
- Returns:
- the basic blocks which may be reached from b via normal control flow
-
iterateNodes
public Iterator<T> iterateNodes(IntSet s)
- Specified by:
iterateNodes
in interfaceNumberedNodeManager<I>
- Returns:
- iterator of nodes with the numbers in set s
-
removeIncomingEdges
public void removeIncomingEdges(T node) throws UnimplementedError
- Specified by:
removeIncomingEdges
in interfaceEdgeManager<I>
- Throws:
UnimplementedError
-
removeOutgoingEdges
public void removeOutgoingEdges(T node) throws UnimplementedError
- Specified by:
removeOutgoingEdges
in interfaceEdgeManager<I>
- Throws:
UnimplementedError
-
getExceptionalToExit
public FixedSizeBitVector getExceptionalToExit()
-
getNormalToExit
public FixedSizeBitVector getNormalToExit()
-
getExceptionalPredecessors
public Collection<T> getExceptionalPredecessors(T b)
Description copied from interface:ControlFlowGraph
The order of blocks returned should be arbitrary but deterministic.- Specified by:
getExceptionalPredecessors
in interfaceControlFlowGraph<I,T extends IBasicBlock<I>>
- Returns:
- the basic blocks from which b may be reached via exceptional control flow
-
getNormalPredecessors
public Collection<T> getNormalPredecessors(T b)
Description copied from interface:ControlFlowGraph
The order of blocks returned should be arbitrary but deterministic.- Specified by:
getNormalPredecessors
in interfaceControlFlowGraph<I,T extends IBasicBlock<I>>
- Returns:
- the basic blocks from which b may be reached via normal control flow
-
getPredNodeNumbers
public IntSet getPredNodeNumbers(T node) throws UnimplementedError
- Specified by:
getPredNodeNumbers
in interfaceNumberedEdgeManager<I>
- Returns:
- the numbers identifying the immediate predecessors of node
- Throws:
UnimplementedError
-
getSuccNodeNumbers
public IntSet getSuccNodeNumbers(T node)
- Specified by:
getSuccNodeNumbers
in interfaceNumberedEdgeManager<I>
- Returns:
- the numbers identifying the immediate successors of node
-
-