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>, MinimalCFG<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>, MinimalCFG<T>, Constants

Common functionality for ControlFlowGraph implementations.

Field Summary

Fields inherited from interface com.ibm.wala.shrike.shrikeBT.Constants

ACC_ABSTRACT, ACC_ANNOTATION, ACC_ENUM, ACC_FINAL, ACC_INTERFACE, ACC_MODULE, ACC_NATIVE, ACC_PRIVATE, ACC_PROTECTED, ACC_PUBLIC, ACC_STATIC, ACC_STRICT, ACC_SUPER, ACC_SYNCHRONIZED, ACC_SYNTHETIC, 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

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 graph
void	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 of immediate predecessor nodes of n
IntSet	getPredNodeNumbers(T node)
Iterator<T>	getPredNodes(T N)	Return an Iterator over the immediate predecessor nodes of n
int	getSuccNodeCount(T N)	Return the number of immediate successor nodes of this Node in the Graph
IntSet	getSuccNodeNumbers(T node)
Iterator<T>	getSuccNodes(T N)	Return an Iterator over the immediate successor nodes of n
boolean	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 nodes
boolean	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 graph
void	removeNodeAndEdges(T N)	remove a node and all its incident edges
void	removeOutgoingEdges(T node)
protected void	setCatchBlock(int i)	record that basic block i is a catch block
Stream<T>	stream()
String	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 Details

AbstractCFG

protected AbstractCFG(IMethod method)

Method Details

init

protected void init()

subclasses must call this before calling addEdge, but after creating the nodes

equals

public abstract boolean equals(Object o)

Overrides:

equals in class Object

hashCode

public abstract int hashCode()

Overrides:

hashCode in class Object

entry

public T entry()

Return the entry basic block for the CFG.

Specified by:

entry in interface MinimalCFG<I>

exit

public T exit()

Return the exit basic block for the CFG.

Specified by:

exit in interface MinimalCFG<I>

Returns:

the synthetic exit block for the cfg

getPredNodeCount

public int getPredNodeCount(T N)

Description copied from interface: EdgeManager

Return the number of immediate predecessor nodes of n

Specified by:

getPredNodeCount in interface EdgeManager<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 an Iterator over the immediate predecessor nodes of n

This method never returns null.

Specified by:

getPredNodes in interface EdgeManager<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 of immediate successor nodes of this Node in the Graph

Specified by:

getSuccNodeCount in interface EdgeManager<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 n

This method never returns null.

Specified by:

getSuccNodes in interface EdgeManager<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 interface NodeManager<I>

getMaxNumber

public int getMaxNumber()

Specified by:

getMaxNumber in interface NumberedNodeManager<I>

getNode

public T getNode(int number)

Specified by:

getNode in interface NumberedNodeManager<I>

getNumber

public int getNumber(T N)

Specified by:

getNumber in interface NumberedNodeManager<I>

getNumberOfNodes

public int getNumberOfNodes()

Specified by:

getNumberOfNodes in interface NodeManager<I>

Returns:

the number of nodes in this graph

iterator

public Iterator<T> iterator()

Specified by:

iterator in interface Iterable<I>

Specified by:

iterator in interface NodeManager<I>

Returns:

an Iterator of the nodes in this graph

stream

public Stream<T> stream()

Specified by:

stream in interface NodeManager<I>

Returns:

a Stream of the nodes in this graph

addEdge

public void addEdge(T src,
 T dst)
             throws UnimplementedError

Specified by:

addEdge in interface EdgeManager<I>

Throws:

UnimplementedError

removeEdge

public void removeEdge(T src,
 T dst)
                throws UnsupportedOperationException

Specified by:

removeEdge in interface EdgeManager<I>

Throws:

UnsupportedOperationException

hasEdge

public boolean hasEdge(T src,
 T dst)

Specified by:

hasEdge in interface EdgeManager<I>

hasExceptionalEdge

public boolean hasExceptionalEdge(T src,
 T dst)

hasNormalEdge

public boolean hasNormalEdge(T src,
 T dst)

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 interface Graph<I>

Throws:

UnimplementedError

See Also:

• NodeManager.removeNode(Object)

removeNode

public void removeNode(T n)
                throws UnimplementedError

Description copied from interface: NodeManager

remove a node from this graph

Specified by:

removeNode in interface NodeManager<I>

Throws:

UnimplementedError

See Also:

• NodeManager.removeNode(Object)

containsNode

public boolean containsNode(T N)

Specified by:

containsNode in interface NodeManager<I>

Returns:

true iff the graph contains the specified node

See Also:

• NodeManager.containsNode(Object)

toString

public String toString()

Overrides:

toString in class Object

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 interface ControlFlowGraph<I,T extends IBasicBlock<I>>

Returns:

the indices of the catch blocks, as a bit vector

getMethod

public IMethod getMethod()

Specified by:

getMethod in interface ControlFlowGraph<I,T extends IBasicBlock<I>>

Returns:

the Method this CFG represents

removeAllIncidentEdges

public void removeAllIncidentEdges(T node)
                            throws UnimplementedError

Specified by:

removeAllIncidentEdges in interface EdgeManager<I>

Throws:

UnimplementedError

See Also:

• EdgeManager.removeAllIncidentEdges(Object)

getExceptionalSuccessors

public List<T> getExceptionalSuccessors(T b)

Description copied from interface: MinimalCFG

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 interface MinimalCFG<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: MinimalCFG

The order of blocks returned should be arbitrary but deterministic.

Specified by:

getNormalSuccessors in interface MinimalCFG<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 interface NumberedNodeManager<I>

Returns:

iterator of nodes with the numbers in set s

See Also:

• NumberedNodeManager.iterateNodes(com.ibm.wala.util.intset.IntSet)

removeIncomingEdges

public void removeIncomingEdges(T node)
                         throws UnimplementedError

Specified by:

removeIncomingEdges in interface EdgeManager<I>

Throws:

UnimplementedError

removeOutgoingEdges

public void removeOutgoingEdges(T node)
                         throws UnimplementedError

Specified by:

removeOutgoingEdges in interface EdgeManager<I>

Throws:

UnimplementedError

getExceptionalToExit

public FixedSizeBitVector getExceptionalToExit()

getNormalToExit

public FixedSizeBitVector getNormalToExit()

getExceptionalPredecessors

public Collection<T> getExceptionalPredecessors(T b)

Description copied from interface: MinimalCFG

The order of blocks returned should be arbitrary but deterministic.

Specified by:

getExceptionalPredecessors in interface MinimalCFG<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: MinimalCFG

The order of blocks returned should be arbitrary but deterministic.

Specified by:

getNormalPredecessors in interface MinimalCFG<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 interface NumberedEdgeManager<I>

Returns:

the numbers identifying the immediate predecessors of node

Throws:

UnimplementedError

getSuccNodeNumbers

public IntSet getSuccNodeNumbers(T node)

Specified by:

getSuccNodeNumbers in interface NumberedEdgeManager<I>

Returns:

the numbers identifying the immediate successors of node