Package sootup.core.graph

Class ControlFlowGraph<V extends BasicBlock<V>>

java.lang.Object
sootup.core.graph.ControlFlowGraph<V>
All Implemented Interfaces:
Iterable<Stmt>
Direct Known Subclasses:
ForwardingControlFlowGraph, ImmutableBlockControlFlowGraph, MutableControlFlowGraph
public abstract class ControlFlowGraph<V extends BasicBlock<V>> extends Object implements Iterable<Stmt>
Interface for control flow graphs on Jimple Stmts. A ControlFlowGraph is directed and connected (except for traphandlers - those are not connected to the unexceptional flow via ControlFlowGraph). Its directed edges represent flows between Stmts. If the edge starts in a branching Stmt there is an edge for each flow to the target Stmt. This can include duplicate flows to the same target e.g. for JSwitchStmt, so that every label has its own flow to a target.

The ControlFlowGraph structure keeps the edge insertion order of each node to store information about successor stmts in its edges for Branching. Ordered edges are necessary because we want to associate the i-th item with the i-th branch case of a BranchingStmt. In a valid ControlFlowGraph it is not allowed to have unconnected Nodes. 

  Stmt stmt1, stmt2;
  ...
  MutableControlFlowGraph graph = new MutableBlockControlFlowGraph();
  graph.setEntryPoint(stmt1);
  graph.addNode(stmt1);
  graph.addNode(stmt2);
  graph.putEdge(stmt1, stmt2);
Author:
Markus Schmidt

  • Constructor Details

    • ControlFlowGraph

      public ControlFlowGraph()

  • Method Details

    • getStartingStmt

      public abstract Stmt getStartingStmt()

    • getStartingStmtBlock

      public abstract BasicBlock<?> getStartingStmtBlock()

    • getTailStmtBlocks

      public abstract List<BasicBlock<?>> getTailStmtBlocks()

    • getNodes

      public abstract @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.

    • getStmts

      public List<Stmt> getStmts()

    • getBlocks

      public abstract @NonNull Collection<? extends BasicBlock<?>> getBlocks()

    • getBlocksSorted

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

    • getBlockIterator

      public Iterator<BasicBlock<?>> getBlockIterator()

    • getBlockOf

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

    • containsNode

      public abstract boolean containsNode(@NonNull Stmt node)

    • predecessors

      public abstract @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`

    • exceptionalPredecessors

      public abstract @NonNull List<Stmt> exceptionalPredecessors(@NonNull Stmt node)
      it is possible to reach traphandlers through inline code i.e. without any exceptional flow

    • successors

      public abstract @NonNull List<Stmt> successors(@NonNull Stmt node)
      returns the outgoing flows of node as ordered List. The List can have duplicate entries!

    • exceptionalSuccessors

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

    • getAllSuccessors

      public @NonNull List<Stmt> getAllSuccessors(@NonNull Stmt stmt)
      Collects all successors i.e. unexceptional and exceptional successors of a given stmt into a list.
      Parameters:
      stmt - in the given graph
      Returns:
      a list containing the unexceptional+exceptional successors of the given stmt

    • inDegree

      public abstract int inDegree(@NonNull Stmt node)
      returns the amount of ingoing flows into node

    • outDegree

      public abstract int outDegree(@NonNull Stmt node)
      returns the amount of flows that start from node

    • degree

      public int degree(@NonNull Stmt node)
      returns the amount of flows with node as source or target.

    • hasEdgeConnecting

      public abstract 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.

    • removeExceptionalFlowFromAllBlocks

      public abstract void removeExceptionalFlowFromAllBlocks(ClassType exceptionType, Stmt exceptionHandlerStmt)
      Removes the specified exceptional flow from all blocks.
      Parameters:
      exceptionType - The class type of the exceptional flow.
      exceptionHandlerStmt - The handler statement of the exceptional flow.

    • getTails

      public @NonNull List<Stmt> getTails()
      returns a Collection of Stmts that leave the body (i.e. JReturnVoidStmt, JReturnStmt and JThrowStmt)

    • getEntrypoints

      public @NonNull Collection<Stmt> getEntrypoints()
      returns a Collection of all stmt in the graph that are either the starting stmt or only have an exceptional ingoing flow

    • validateStmtConnectionsInGraph

      public void validateStmtConnectionsInGraph()
      validates whether the each Stmt has the correct amount of outgoing flows.

    • getExtendedBasicBlockPathBetween

      public @Nullable List<Stmt> getExtendedBasicBlockPathBetween(@NonNull Stmt from, @NonNull Stmt to)
      Look for a path in graph, from def to use. This path has to lie inside an extended basic block (and this property implies uniqueness.). The path returned includes from and to. FIXME: ms: explain better
      Parameters:
      from - start point for the path.
      to - end point for the path.
      Returns:
      null if there is no such path.

    • equals

      public boolean equals(Object o)
      Overrides:
      equals in class Object

    • iterator

      public @NonNull Iterator<Stmt> iterator()
      Specified by:
      iterator in interface Iterable<V extends BasicBlock<V>>

    • getBranchTargetsOf

      public List<Stmt> getBranchTargetsOf(BranchingStmt fromStmt)

    • isStmtBranchTarget

      public boolean isStmtBranchTarget(@NonNull Stmt targetStmt)

    • toString

      public String toString()
      Overrides:
      toString in class Object