Package sootup.core.graph

Class MutableBlockControlFlowGraph

java.lang.Object

sootup.core.graph.ControlFlowGraph<MutableBasicBlock>

sootup.core.graph.MutableControlFlowGraph

sootup.core.graph.MutableBlockControlFlowGraph

All Implemented Interfaces:

Iterable<Stmt>

public class MutableBlockControlFlowGraph
extends MutableControlFlowGraph

Control flow graph that stores Stmts in maximal basic blocks.

Every mutation is built from three structural primitives on top of the edge primitives of MutableBasicBlockImpl:

• split(sootup.core.graph.MutableBasicBlockImpl, int): cut a block so that a given stmt becomes the head of a block,
• merge(sootup.core.graph.MutableBasicBlockImpl, sootup.core.graph.MutableBasicBlockImpl): join a block with its only, fall-through successor,
• normalize(sootup.core.graph.MutableBasicBlockImpl): merge a block with its neighbours where possible.

Operations validate their arguments first, split what they need, change edges, then normalize, so blocks stay maximal. Within beginBatch()/endBatch() merging is deferred.

Costs: a stmt index (IdentityHashMap) maps stmts to blocks; blocks store stmts in a deque with a position cache, so lookups and head/tail changes are O(1) and a split or merge moves the smaller part. The linearized block order is cached and survives changes inside a block.

Author:

Markus Schmidt

Constructor Summary

Constructors

Constructor	Description
MutableBlockControlFlowGraph()
MutableBlockControlFlowGraph(boolean isStatic, MethodSignature sig, LocalGenerator localgen)
MutableBlockControlFlowGraph(@NonNull ControlFlowGraph<? extends BasicBlock<?>> graph)	copies a ControlFlowGraph into this Mutable instance, block by block

Method Summary

Modifier and Type	Method	Description
void	addBlock(@NonNull List<Stmt> stmts, @NonNull Map<ClassType,Stmt> trapMap)	Adds a block.
void	addExceptionalEdge(@NonNull Stmt stmt, @NonNull ClassType exceptionType, @NonNull Stmt traphandlerStmt)	Adds an exceptional flow with the type "exception" to a "stmt" which will reach "traphandlerStmt"
void	addNode(@NonNull Stmt stmt, @NonNull Map<ClassType,Stmt> exceptions)	inserts a "stmt" with exceptional flows "traps" into the ControlFlowGraph
void	beginBatch()	Starts a batch of changes: blocks that become mergeable are not merged until the matching endBatch(), which saves repeated split/merge work in a sequence of edits.
void	clearExceptionalEdges(@NonNull Stmt node)	Modifications of exceptional flows removes all exceptional flows from "stmt"
boolean	containsNode(@NonNull Stmt node)
static ControlFlowGraph<?>	createUnmodifiableControlFlowGraph(ControlFlowGraph<?> controlFlowGraph)
void	endBatch()	ends a batch; the outermost one merges the blocks touched since its beginBatch()
List<? extends BasicBlock<?>>	exceptionalPredecessorBlocks(@NonNull BasicBlock<?> block)
List<Stmt>	exceptionalPredecessors(@NonNull MutableBasicBlock block)
@NonNull List<Stmt>	exceptionalPredecessors(@NonNull Stmt node)	it is possible to reach traphandlers through inline code i.e. without any exceptional flow
@NonNull Map<ClassType,Stmt>	exceptionalSuccessors(@NonNull Stmt node)
Iterator<BasicBlock<?>>	getBlockIterator()	blocks in linearized order; iterates a snapshot, the graph may change meanwhile
@NonNull BasicBlock<?>	getBlockOf(@NonNull Stmt stmt)
@NonNull Set<? extends BasicBlock<?>>	getBlocks()
@NonNull List<? extends BasicBlock<?>>	getBlocksSorted()
@NonNull Set<Stmt>	getNodes()	returns the nodes in this graph in a non-deterministic order (->Set) to get the nodes in linearized, ordered manner use iterator() or getStmts.
@Nullable Stmt	getStartingStmt()
@Nullable BasicBlock<?>	getStartingStmtBlock()
@NonNull List<Stmt>	getStmts()	The statements in ControlFlowGraph.iterator() order.
@NonNull List<BasicBlock<?>>	getTailStmtBlocks()
boolean	hasEdgeConnecting(@NonNull Stmt source, @NonNull Stmt target)	returns true if there is a flow between source and target throws an Exception if at least one of the parameters is not contained in the graph.
int	inDegree(@NonNull Stmt node)	returns the amount of ingoing flows into node
void	initializeWith(@NonNull List<List<Stmt>> blocks, @NonNull Map<BranchingStmt,List<Stmt>> successorMap, @NonNull List<Trap> traps)	Creates a Graph representation from the 'legacy' representation i.e. a List of Stmts and Traps.
@NonNull BasicBlock<?>	insertAfter(@NonNull Stmt existingStmt, @NonNull List<FallsThroughStmt> stmts, @NonNull Map<ClassType,Stmt> exceptionMap)
@NonNull BasicBlock<?>	insertBefore(@NonNull Stmt existingStmt, @NonNull List<FallsThroughStmt> stmts, @NonNull Map<ClassType,Stmt> exceptionMap)
int	outDegree(@NonNull Stmt node)	returns the amount of flows that start from node
@NonNull List<Stmt>	predecessors(@NonNull Stmt node)	returns the ingoing flows to node as an List with no reliable/specific order and possibly duplicate entries i.e. if a JSwitchStmt has multiple cases that brnach to `node`
void	putEdge(@NonNull BranchingStmt stmtA, int succesorIdx, @NonNull Stmt stmtB)
void	putEdge(@NonNull FallsThroughStmt stmtA, @NonNull Stmt stmtB)	Modifications of unexceptional flows
void	removeBlock(BasicBlock<?> block)
List<Integer>	removeEdge(@NonNull Stmt from, @NonNull Stmt to)	removes the current outgoing flows of "from" to "to"
void	removeExceptionalEdge(@NonNull Stmt node, @NonNull ClassType exceptionType)	removes an exceptional flow of the type "exception" flow from "stmt"
void	removeExceptionalFlowFromAllBlocks(@NonNull ClassType exceptionType, @NonNull Stmt exceptionHandlerStmt)	Removes the specified exceptional flow from all blocks.
void	removeNode(@NonNull Stmt stmt)	removes "stmt" from the ControlFlowGraph
void	removeNode(@NonNull Stmt stmt, boolean keepFlow)	Removes a Stmt from the ControlFlowGraph.
void	replaceNode(@NonNull Stmt oldStmt, @NonNull Stmt newStmt)	Modification of stmts (without manipulating any flows; possible assigned exceptional flows stay the same as well)
boolean	replaceSuccessorEdge(@NonNull Stmt from, @NonNull Stmt oldTo, @NonNull Stmt newTo)	Replaces all SuccessorEdge(s) of from to oldTo by newTo
void	setEdges(@NonNull BranchingStmt fromStmt, @NonNull List<Stmt> targets)	replaces the current outgoing flows of "from" to "targets"
void	setStartingStmt(@NonNull Stmt startingStmt)
@NonNull List<Stmt>	successors(@NonNull Stmt node)	returns the outgoing flows of node as ordered List.
@NonNull ControlFlowGraph<?>	unmodifiableControlFlowGraph()
void	validateBlocks()	checks the internal consistency; throws an IllegalStateException on a violation

Methods inherited from class sootup.core.graph.MutableControlFlowGraph

addBlock, addNode, insertAfter, insertBefore, replaceSucessorEdge, setEdges

Methods inherited from class sootup.core.graph.ControlFlowGraph

degree, equals, getAllSuccessors, getBranchTargetsOf, getEntrypoints, getExtendedBasicBlockPathBetween, getTails, hashCode, isStmtBranchTarget, iterator, toString, validateStmtConnectionsInGraph

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Constructor Details

MutableBlockControlFlowGraph

public MutableBlockControlFlowGraph()

MutableBlockControlFlowGraph

public MutableBlockControlFlowGraph(boolean isStatic,
 MethodSignature sig,
 LocalGenerator localgen)

MutableBlockControlFlowGraph

public MutableBlockControlFlowGraph(@NonNull ControlFlowGraph<? extends BasicBlock<?>> graph)

copies a ControlFlowGraph into this Mutable instance, block by block

Method Details

createUnmodifiableControlFlowGraph

public static ControlFlowGraph<?> createUnmodifiableControlFlowGraph(ControlFlowGraph<?> controlFlowGraph)

initializeWith

public void initializeWith(@NonNull List<List<Stmt>> blocks,
 @NonNull Map<BranchingStmt,List<Stmt>> successorMap,
 @NonNull List<Trap> traps)

Creates a Graph representation from the 'legacy' representation i.e. a List of Stmts and Traps.

beginBatch

public void beginBatch()

Starts a batch of changes: blocks that become mergeable are not merged until the matching endBatch(), which saves repeated split/merge work in a sequence of edits. Within a batch the graph is consistent and its stmt-level flows are exact, only blocks may be smaller than necessary. Batches nest.

Overrides:

beginBatch in class MutableControlFlowGraph

endBatch

public void endBatch()

ends a batch; the outermost one merges the blocks touched since its beginBatch()

Overrides:

endBatch in class MutableControlFlowGraph

addExceptionalEdge

public void addExceptionalEdge(@NonNull Stmt stmt,
 @NonNull ClassType exceptionType,
 @NonNull Stmt traphandlerStmt)

Description copied from class: MutableControlFlowGraph

Adds an exceptional flow with the type "exception" to a "stmt" which will reach "traphandlerStmt"

Specified by:

addExceptionalEdge in class MutableControlFlowGraph

removeExceptionalEdge

public void removeExceptionalEdge(@NonNull Stmt node,
 @NonNull ClassType exceptionType)

Description copied from class: MutableControlFlowGraph

removes an exceptional flow of the type "exception" flow from "stmt"

Specified by:

removeExceptionalEdge in class MutableControlFlowGraph

clearExceptionalEdges

public void clearExceptionalEdges(@NonNull Stmt node)

Description copied from class: MutableControlFlowGraph

Modifications of exceptional flows removes all exceptional flows from "stmt"

Specified by:

clearExceptionalEdges in class MutableControlFlowGraph

removeExceptionalFlowFromAllBlocks

public void removeExceptionalFlowFromAllBlocks(@NonNull ClassType exceptionType,
 @NonNull Stmt exceptionHandlerStmt)

Description copied from class: ControlFlowGraph

Removes the specified exceptional flow from all blocks.

Specified by:

removeExceptionalFlowFromAllBlocks in class ControlFlowGraph<MutableBasicBlock>

Parameters:

exceptionType - The class type of the exceptional flow.

exceptionHandlerStmt - The handler statement of the exceptional flow.

getBlocks

public @NonNull Set<? extends BasicBlock<?>> getBlocks()

Specified by:

getBlocks in class ControlFlowGraph<MutableBasicBlock>

getBlocksSorted

public @NonNull List<? extends BasicBlock<?>> getBlocksSorted()

Specified by:

getBlocksSorted in class ControlFlowGraph<MutableBasicBlock>

getBlockIterator

public Iterator<BasicBlock<?>> getBlockIterator()

blocks in linearized order; iterates a snapshot, the graph may change meanwhile

Overrides:

getBlockIterator in class ControlFlowGraph<MutableBasicBlock>

addBlock

public void addBlock(@NonNull List<Stmt> stmts,
 @NonNull Map<ClassType,Stmt> trapMap)

Adds a block. Its Stmts must be new to the graph, except: the first one may be an existing single-Stmt block without successors, the last one may be the head of an existing block (it is then linked as successor). Only the last Stmt may branch or end the flow.

Specified by:

addBlock in class MutableControlFlowGraph

removeBlock

public void removeBlock(BasicBlock<?> block)

Specified by:

removeBlock in class MutableControlFlowGraph

addNode

public void addNode(@NonNull Stmt stmt,
 @NonNull Map<ClassType,Stmt> exceptions)

Description copied from class: MutableControlFlowGraph

inserts a "stmt" with exceptional flows "traps" into the ControlFlowGraph

Specified by:

addNode in class MutableControlFlowGraph

removeNode

public void removeNode(@NonNull Stmt stmt)

Description copied from class: MutableControlFlowGraph

removes "stmt" from the ControlFlowGraph

Specified by:

removeNode in class MutableControlFlowGraph

removeNode

public void removeNode(@NonNull Stmt stmt,
 boolean keepFlow)

Removes a Stmt from the ControlFlowGraph.

It can optionally keep the flow (edges) of the statement by connecting the predecessors of the statement with successors of the statement. Keeping the flow does not work when the statement has multiple successors.

Specified by:

removeNode in class MutableControlFlowGraph

Parameters:

stmt - the Stmt to be removed

keepFlow - flag indicating whether to keep the flow or not

Throws:

IllegalArgumentException - if keepFlow is true but the stmt has multiple successors

replaceNode

public void replaceNode(@NonNull Stmt oldStmt,
 @NonNull Stmt newStmt)

Description copied from class: MutableControlFlowGraph

Modification of stmts (without manipulating any flows; possible assigned exceptional flows stay the same as well)

Specified by:

replaceNode in class MutableControlFlowGraph

validateBlocks

public void validateBlocks()

checks the internal consistency; throws an IllegalStateException on a violation

insertBefore

public @NonNull BasicBlock<?> insertBefore(@NonNull Stmt existingStmt,
 @NonNull List<FallsThroughStmt> stmts,
 @NonNull Map<ClassType,Stmt> exceptionMap)

Specified by:

insertBefore in class MutableControlFlowGraph

insertAfter

public @NonNull BasicBlock<?> insertAfter(@NonNull Stmt existingStmt,
 @NonNull List<FallsThroughStmt> stmts,
 @NonNull Map<ClassType,Stmt> exceptionMap)

Specified by:

insertAfter in class MutableControlFlowGraph

replaceSuccessorEdge

public boolean replaceSuccessorEdge(@NonNull Stmt from,
 @NonNull Stmt oldTo,
 @NonNull Stmt newTo)

Replaces all SuccessorEdge(s) of from to oldTo by newTo

Specified by:

replaceSuccessorEdge in class MutableControlFlowGraph

Returns:

false if there is no such flow

putEdge

public void putEdge(@NonNull FallsThroughStmt stmtA,
 @NonNull Stmt stmtB)

Description copied from class: MutableControlFlowGraph

Modifications of unexceptional flows

Adds a flow "from" to "to". if at least one of the parameter Stmts is not already in the ControlFlowGraph it will be added. if "to" needs to be added to the ControlFlowGraph i.e. "to" is not already in the ControlFlowGraph the method assumes "to" has the same exceptional flows as "from".

Specified by:

putEdge in class MutableControlFlowGraph

putEdge

public void putEdge(@NonNull BranchingStmt stmtA,
 int succesorIdx,
 @NonNull Stmt stmtB)

Specified by:

putEdge in class MutableControlFlowGraph

removeEdge

public List<Integer> removeEdge(@NonNull Stmt from,
 @NonNull Stmt to)

Description copied from class: MutableControlFlowGraph

removes the current outgoing flows of "from" to "to"

Specified by:

removeEdge in class MutableControlFlowGraph

Returns:

returns List of the successor indices of "from" that were connected to "to" - items are 0 in case of FallsThroughStmts or idx > 0 in case of BranchingStmts with multiple successors

setEdges

public void setEdges(@NonNull BranchingStmt fromStmt,
 @NonNull List<Stmt> targets)

Description copied from class: MutableControlFlowGraph

replaces the current outgoing flows of "from" to "targets"

Specified by:

setEdges in class MutableControlFlowGraph

getStartingStmt

public @Nullable Stmt getStartingStmt()

Specified by:

getStartingStmt in class ControlFlowGraph<MutableBasicBlock>

getStartingStmtBlock

public @Nullable BasicBlock<?> getStartingStmtBlock()

Specified by:

getStartingStmtBlock in class ControlFlowGraph<MutableBasicBlock>

getTailStmtBlocks

public @NonNull List<BasicBlock<?>> getTailStmtBlocks()

Specified by:

getTailStmtBlocks in class ControlFlowGraph<MutableBasicBlock>

getBlockOf

public @NonNull BasicBlock<?> getBlockOf(@NonNull Stmt stmt)

Specified by:

getBlockOf in class ControlFlowGraph<MutableBasicBlock>

unmodifiableControlFlowGraph

public @NonNull ControlFlowGraph<?> unmodifiableControlFlowGraph()

Specified by:

unmodifiableControlFlowGraph in class MutableControlFlowGraph

setStartingStmt

public void setStartingStmt(@NonNull Stmt startingStmt)

Specified by:

setStartingStmt in class MutableControlFlowGraph

getStmts

public @NonNull List<Stmt> getStmts()

The statements in ControlFlowGraph.iterator() order. The order is computed once until the graph changes; each call returns a new list, as before.

Overrides:

getStmts in class ControlFlowGraph<MutableBasicBlock>

getNodes

public @NonNull Set<Stmt> getNodes()

Description copied from class: ControlFlowGraph

returns the nodes in this graph in a non-deterministic order (->Set) to get the nodes in linearized, ordered manner use iterator() or getStmts.

Specified by:

getNodes in class ControlFlowGraph<MutableBasicBlock>

containsNode

public boolean containsNode(@NonNull Stmt node)

Specified by:

containsNode in class ControlFlowGraph<MutableBasicBlock>

predecessors

public @NonNull List<Stmt> predecessors(@NonNull Stmt node)

Description copied from class: ControlFlowGraph

returns the ingoing flows to node as an List with no reliable/specific order and possibly duplicate entries i.e. if a JSwitchStmt has multiple cases that brnach to `node`

Specified by:

predecessors in class ControlFlowGraph<MutableBasicBlock>

exceptionalPredecessors

public @NonNull List<Stmt> exceptionalPredecessors(@NonNull Stmt node)

Description copied from class: ControlFlowGraph

it is possible to reach traphandlers through inline code i.e. without any exceptional flow

Specified by:

exceptionalPredecessors in class ControlFlowGraph<MutableBasicBlock>

exceptionalPredecessors

public List<Stmt> exceptionalPredecessors(@NonNull MutableBasicBlock block)

exceptionalPredecessorBlocks

public List<? extends BasicBlock<?>> exceptionalPredecessorBlocks(@NonNull BasicBlock<?> block)

successors

public @NonNull List<Stmt> successors(@NonNull Stmt node)

Description copied from class: ControlFlowGraph

returns the outgoing flows of node as ordered List. The List can have duplicate entries!

Specified by:

successors in class ControlFlowGraph<MutableBasicBlock>

exceptionalSuccessors

public @NonNull Map<ClassType,Stmt> exceptionalSuccessors(@NonNull Stmt node)

Specified by:

exceptionalSuccessors in class ControlFlowGraph<MutableBasicBlock>

inDegree

public int inDegree(@NonNull Stmt node)

Description copied from class: ControlFlowGraph

returns the amount of ingoing flows into node

Specified by:

inDegree in class ControlFlowGraph<MutableBasicBlock>

outDegree

public int outDegree(@NonNull Stmt node)

Description copied from class: ControlFlowGraph

returns the amount of flows that start from node

Specified by:

outDegree in class ControlFlowGraph<MutableBasicBlock>

hasEdgeConnecting

public boolean hasEdgeConnecting(@NonNull Stmt source,
 @NonNull Stmt target)

Description copied from class: ControlFlowGraph

returns true if there is a flow between source and target throws an Exception if at least one of the parameters is not contained in the graph.

Specified by:

hasEdgeConnecting in class ControlFlowGraph<MutableBasicBlock>