Class SimplePathEnumerator

java.lang.Object

edu.umd.cs.findbugs.ba.SimplePathEnumerator

All Implemented Interfaces:

DFSEdgeTypes, EdgeTypes, DFSEdgeTypes

public class SimplePathEnumerator
extends 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.

See Also:

• CFG

Field Summary

Fields

Modifier and Type	Field	Description
private final CFG	cfg
private static final boolean	DEBUG
static final int	DEFAULT_MAX_WORK	Default number of steps to be performed in path enumeration.
private final DepthFirstSearch	dfs
private final int	maxPaths
private final int	maxWork
private final List<List<Edge>>	pathList
private int	work

Fields inherited from interface DFSEdgeTypes

BACK_EDGE, CROSS_EDGE, FORWARD_EDGE, TREE_EDGE, UNKNOWN_EDGE

Fields inherited from interface 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

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method	Description
SimplePathEnumerator	enumerate()	Enumerate the simple paths.
Iterator<List<Edge>>	iterator()	Iterate over simple paths.
private void	work(LinkedList<Edge> partialPath)

Methods inherited from class Object

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

Field Details

cfg

private final CFG cfg

dfs

private final DepthFirstSearch dfs

maxPaths

private final int maxPaths

maxWork

private final int maxWork

work

private int work

pathList

private final List<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 Details

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 Details

enumerate

public SimplePathEnumerator enumerate()

Enumerate the simple paths.

Returns:

this object

iterator

public Iterator<List<Edge>> iterator()

Iterate over simple paths.

work

private void work(LinkedList<Edge> partialPath)