Package sootup.core.graph

Class ImmutableBlockControlFlowGraph

java.lang.Object

sootup.core.graph.ControlFlowGraph<ImmutableBlockControlFlowGraph.ImmutableBasicBlock>

sootup.core.graph.ImmutableBlockControlFlowGraph

All Implemented Interfaces:

Iterable<Stmt>

public class ImmutableBlockControlFlowGraph
extends ControlFlowGraph<ImmutableBlockControlFlowGraph.ImmutableBasicBlock>

A truly immutable snapshot of a ControlFlowGraph. Constructed from any existing graph; subsequent mutations to the source do not affect this instance.

Provides O(1) bidirectional stmt-to-integer-index mapping via indexOf(Stmt) and getStmt(int), enabling bitset-based analysis passes (liveness, reaching definitions, etc.) without per-lookup HashMap overhead.

Construction uses a two-phase algorithm:

1. Linearise the source graph in RPO order into a flat Stmt[] array and create ImmutableBlockControlFlowGraph.ImmutableBasicBlock shells.
2. Wire predecessor/successor/exceptional-successor links between the shells.

Author:

Markus Schmidt

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
class	ImmutableBlockControlFlowGraph.ImmutableBasicBlock	An immutable basic block backed by a range [ImmutableBlockControlFlowGraph.ImmutableBasicBlock.startIdx, ImmutableBlockControlFlowGraph.ImmutableBasicBlock.endIdx] of the enclosing graph's flat statement array.

Constructor Summary

Constructors

Constructor	Description
ImmutableBlockControlFlowGraph(@NonNull ControlFlowGraph<? extends BasicBlock<?>> source)	Constructs an immutable snapshot of source.

Method Summary

Modifier and Type	Method	Description
boolean	containsNode(@NonNull Stmt node)
@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)
@NonNull ImmutableBlockControlFlowGraph.ImmutableBasicBlock	getBlockOf(@NonNull Stmt stmt)
@NonNull Collection<ImmutableBlockControlFlowGraph.ImmutableBasicBlock>	getBlocks()
@NonNull List<ImmutableBlockControlFlowGraph.ImmutableBasicBlock>	getBlocksSorted()
int	getNodeCount()	Total number of stmts in this graph — equals the length of the internal flat array.
@NonNull Collection<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 Stmt	getStmt(int index)	Returns the stmt at the given traversal-order index.
@NonNull List<Stmt>	getStmts()
@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
int	indexOf(@NonNull Stmt stmt)	Returns the traversal-order position of stmt in this graph's flat statement array.
@NonNull Iterator<Stmt>	iterator()
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	removeExceptionalFlowFromAllBlocks(ClassType exceptionType, Stmt exceptionHandlerStmt)	Removes the specified exceptional flow from all blocks.
@NonNull List<Stmt>	successors(@NonNull Stmt node)	returns the outgoing flows of node as ordered List.

Methods inherited from class sootup.core.graph.ControlFlowGraph

degree, equals, getAllSuccessors, getBlockIterator, getBranchTargetsOf, getEntrypoints, getExtendedBasicBlockPathBetween, getTails, isStmtBranchTarget, toString, validateStmtConnectionsInGraph

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Constructor Details

ImmutableBlockControlFlowGraph

public ImmutableBlockControlFlowGraph(@NonNull ControlFlowGraph<? extends BasicBlock<?>> source)

Constructs an immutable snapshot of source. The source graph is only read during construction; later changes to it do not affect this instance.

Method Details

indexOf

public int indexOf(@NonNull Stmt stmt)

Returns the traversal-order position of stmt in this graph's flat statement array. O(1) — identity-based IdentityHashMap lookup.

Throws:

NoSuchElementException - if stmt is not contained in this graph

getStmt

public @NonNull Stmt getStmt(int index)

Returns the stmt at the given traversal-order index. O(1) array access.

Throws:

ArrayIndexOutOfBoundsException - if index is out of range

getNodeCount

public int getNodeCount()

Total number of stmts in this graph — equals the length of the internal flat array.

getStartingStmt

public @Nullable Stmt getStartingStmt()

Specified by:

getStartingStmt in class ControlFlowGraph<ImmutableBlockControlFlowGraph.ImmutableBasicBlock>

getStartingStmtBlock

public @Nullable BasicBlock<?> getStartingStmtBlock()

Specified by:

getStartingStmtBlock in class ControlFlowGraph<ImmutableBlockControlFlowGraph.ImmutableBasicBlock>

getTailStmtBlocks

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

Specified by:

getTailStmtBlocks in class ControlFlowGraph<ImmutableBlockControlFlowGraph.ImmutableBasicBlock>

getNodes

public @NonNull Collection<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<ImmutableBlockControlFlowGraph.ImmutableBasicBlock>

getStmts

public @NonNull List<Stmt> getStmts()

Overrides:

getStmts in class ControlFlowGraph<ImmutableBlockControlFlowGraph.ImmutableBasicBlock>

iterator

public @NonNull Iterator<Stmt> iterator()

Specified by:

iterator in interface Iterable<Stmt>

Overrides:

iterator in class ControlFlowGraph<ImmutableBlockControlFlowGraph.ImmutableBasicBlock>

getBlocks

public @NonNull Collection<ImmutableBlockControlFlowGraph.ImmutableBasicBlock> getBlocks()

Specified by:

getBlocks in class ControlFlowGraph<ImmutableBlockControlFlowGraph.ImmutableBasicBlock>

getBlocksSorted

public @NonNull List<ImmutableBlockControlFlowGraph.ImmutableBasicBlock> getBlocksSorted()

Specified by:

getBlocksSorted in class ControlFlowGraph<ImmutableBlockControlFlowGraph.ImmutableBasicBlock>

getBlockOf

public @NonNull ImmutableBlockControlFlowGraph.ImmutableBasicBlock getBlockOf(@NonNull Stmt stmt)

Specified by:

getBlockOf in class ControlFlowGraph<ImmutableBlockControlFlowGraph.ImmutableBasicBlock>

containsNode

public boolean containsNode(@NonNull Stmt node)

Specified by:

containsNode in class ControlFlowGraph<ImmutableBlockControlFlowGraph.ImmutableBasicBlock>

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<ImmutableBlockControlFlowGraph.ImmutableBasicBlock>

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<ImmutableBlockControlFlowGraph.ImmutableBasicBlock>

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<ImmutableBlockControlFlowGraph.ImmutableBasicBlock>

exceptionalSuccessors

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

Specified by:

exceptionalSuccessors in class ControlFlowGraph<ImmutableBlockControlFlowGraph.ImmutableBasicBlock>

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<ImmutableBlockControlFlowGraph.ImmutableBasicBlock>

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<ImmutableBlockControlFlowGraph.ImmutableBasicBlock>

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<ImmutableBlockControlFlowGraph.ImmutableBasicBlock>

removeExceptionalFlowFromAllBlocks

public void removeExceptionalFlowFromAllBlocks(ClassType exceptionType,
 Stmt exceptionHandlerStmt)

Description copied from class: ControlFlowGraph

Removes the specified exceptional flow from all blocks.

Specified by:

removeExceptionalFlowFromAllBlocks in class ControlFlowGraph<ImmutableBlockControlFlowGraph.ImmutableBasicBlock>

Parameters:

exceptionType - The class type of the exceptional flow.

exceptionHandlerStmt - The handler statement of the exceptional flow.