Package sootup.core.graph

Class StmtGraph<V extends BasicBlock<V>>

java.lang.Object
sootup.core.graph.StmtGraph<V>
All Implemented Interfaces:
Iterable<Stmt>
Direct Known Subclasses:
ForwardingStmtGraph, ImmutableBlockStmtGraph, MutableStmtGraph
public abstract class StmtGraph<V extends BasicBlock<V>> extends Object implements Iterable<Stmt>
Interface for control flow graphs on Jimple Stmts. A StmtGraph is directed and connected (except for traphandlers - those are not connected to the unexceptional flow via StmtGraph). 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 StmtGraph 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 StmtGraph it is not allowed to have unconnected Nodes. 

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

  • Constructor Details

    • StmtGraph

      public StmtGraph()

  • Method Details

    • getStartingStmt

      public abstract Stmt getStartingStmt()

    • getStartingStmtBlock

      public abstract BasicBlock<?> getStartingStmtBlock()

    • getNodes

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

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

    • getBlocksSorted

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

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

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

    • successors

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

    • exceptionalSuccessors

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

    • getAllSuccessors

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

    • buildTraps

      public abstract List<Trap> buildTraps()
      returns a (reconstructed) list of traps like the traptable in the bytecode

      Note: if you need exceptionional flow information in more augmented with the affected blocks/stmts and not just a (reconstructed, possibly more verbose) traptable - have a look at BasicBlock.getExceptionalSuccessor()

    • 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

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

    • getEntrypoints

      @Nonnull public 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

      @Nullable public 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

      @Nonnull public 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)

    • getLabeledStmts

      @Nonnull public Collection<Stmt> getLabeledStmts()
      Returns the result of iterating through all Stmts in this body. All Stmts thus found are returned. Branching Stmts and statements which use PhiExpr will have Stmts; a Stmt contains a Stmt that is either a target of a branch or is being used as a pointer to the end of a CFG block.

      This method was typically used for pointer patching, e.g. when the unit chain is cloned.

      Returns:
      A collection of all the Stmts that are targets of a BranchingStmt

    • toString

      public String toString()
      Overrides:
      toString in class Object