edu.umd.cs.findbugs.ba
Class SimplePathEnumerator

java.lang.Object
  extended by edu.umd.cs.findbugs.ba.SimplePathEnumerator
All Implemented Interfaces:
EdgeTypes, DFSEdgeTypes

public class SimplePathEnumerator
extends java.lang.Object
implements EdgeTypes, DFSEdgeTypes

Object to enumerate (some subset of) the simple paths in a CFG. A simple path is a path from entry to exit, ignoring backedges and unhandled exceptions.

FIXME: instead of storing the simple paths, should invoke a callback as each simple path is produced. That would save memory.

Author:
David Hovemeyer
See Also:
CFG

Field Summary
private  CFG cfg
           
private static boolean DEBUG
           
static int DEFAULT_MAX_WORK
          Default number of steps to be performed in path enumeration.
private  DepthFirstSearch dfs
           
private  int maxPaths
           
private  int maxWork
           
private  java.util.List<java.util.List<Edge>> pathList
           
private  int work
           
 
Fields inherited from interface edu.umd.cs.findbugs.ba.EdgeTypes
BACKEDGE_SOURCE_EDGE, BACKEDGE_TARGET_EDGE, CHECKED_EXCEPTIONS_FLAG, EXIT_EDGE, EXPLICIT_EXCEPTIONS_FLAG, FALL_THROUGH_EDGE, GOTO_EDGE, HANDLED_EXCEPTION_EDGE, IFCMP_EDGE, JSR_EDGE, RET_EDGE, RETURN_EDGE, START_EDGE, SWITCH_DEFAULT_EDGE, SWITCH_EDGE, UNHANDLED_EXCEPTION_EDGE, UNKNOWN_EDGE
 
Fields inherited from interface edu.umd.cs.findbugs.graph.DFSEdgeTypes
BACK_EDGE, CROSS_EDGE, FORWARD_EDGE, TREE_EDGE
 
Constructor Summary
SimplePathEnumerator(CFG cfg, int maxPaths)
          Constructor; max work is set to DEFAULT_MAX_WORK.
SimplePathEnumerator(CFG cfg, int maxPaths, int maxWork)
          Constructor.
 
Method Summary
 SimplePathEnumerator enumerate()
          Enumerate the simple paths.
 java.util.Iterator<java.util.List<Edge>> iterator()
          Iterate over simple paths.
private  void work(java.util.LinkedList<Edge> partialPath)
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

cfg

private CFG cfg

dfs

private DepthFirstSearch dfs

maxPaths

private int maxPaths

maxWork

private int maxWork

work

private int work

pathList

private java.util.List<java.util.List<Edge>> pathList

DEBUG

private static final boolean DEBUG

DEFAULT_MAX_WORK

public static final int DEFAULT_MAX_WORK
Default number of steps to be performed in path enumeration.

See Also:
Constant Field Values
Constructor Detail

SimplePathEnumerator

public SimplePathEnumerator(CFG cfg,
                            int maxPaths,
                            int maxWork)
Constructor.

Parameters:
cfg - the control flow graph to enumerate simple paths of
maxPaths - maximum number of simple paths to find
maxWork - maximum number of steps to be performed in the path enumeration (to handle exponential blowup of search space)

SimplePathEnumerator

public SimplePathEnumerator(CFG cfg,
                            int maxPaths)
Constructor; max work is set to DEFAULT_MAX_WORK.

Parameters:
cfg - the control flow graph to enumerate simple paths of
maxPaths - maximum number of simple paths to find
Method Detail

enumerate

public SimplePathEnumerator enumerate()
Enumerate the simple paths.

Returns:
this object

iterator

public java.util.Iterator<java.util.List<Edge>> iterator()
Iterate over simple paths.


work

private void work(java.util.LinkedList<Edge> partialPath)