Package org.checkerframework.dataflow.analysis

Class AbstractAnalysis.Worklist

java.lang.Object

org.checkerframework.dataflow.analysis.AbstractAnalysis.Worklist

Enclosing class:

AbstractAnalysis<V extends AbstractValue<V>,S extends Store<S>,T extends TransferFunction<V,S>>

protected static class AbstractAnalysis.Worklist
extends Object

A worklist is a priority queue of blocks in which the order is given by depth-first ordering to place non-loop predecessors ahead of successors.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
class	AbstractAnalysis.Worklist.BackwardDfoComparator	Comparators to allow priority queue to order blocks by their depth-first order, using by backward analysis.
class	AbstractAnalysis.Worklist.ForwardDfoComparator	Comparators to allow priority queue to order blocks by their depth-first order, using by forward analysis.

Field Summary

Fields

Modifier and Type	Field	Description
protected final IdentityHashMap<Block,Integer>	depthFirstOrder	Map all blocks in the CFG to their depth-first order.
protected final PriorityQueue<Block>	queue	The backing priority queue.
protected final Set<Block>	queueSet	Contains the same elements as queue, for faster lookup.

Constructor Summary

Constructors

Constructor	Description
Worklist(Analysis.Direction direction)	Create a Worklist.

Method Summary

Modifier and Type	Method	Description
void	add(Block block)	Add the given block to this Worklist.
boolean	contains(Block block)	Returns true if this Worklist contains the given block.
boolean	isEmpty()	See AbstractCollection.isEmpty().
@Nullable Block	poll()	Returns the head of this Worklist.
void	process(ControlFlowGraph cfg)	Process the control flow graph.
Block	remove()	Returns the head of this Worklist.
String	toString()

Methods inherited from class java.lang.Object

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

Field Details

depthFirstOrder

protected final IdentityHashMap<Block,Integer> depthFirstOrder

Map all blocks in the CFG to their depth-first order.

queue

protected final PriorityQueue<Block> queue

The backing priority queue.

queueSet

protected final Set<Block> queueSet

Contains the same elements as queue, for faster lookup.

Constructor Details

Worklist

public Worklist(Analysis.Direction direction)

Create a Worklist.

Parameters:

direction - the direction (forward or backward)

Method Details

process

public void process(ControlFlowGraph cfg)

Process the control flow graph.

This implementation sets the depth-first order for each block, by adding the blocks to depthFirstOrder.

Parameters:

cfg - the control flow graph to process

isEmpty

@Pure
@EnsuresNonNullIf(result=false,
                  expression="poll()")
public boolean isEmpty()

See AbstractCollection.isEmpty().

Returns:

true if this Worklist is empty

See Also:

• AbstractCollection.isEmpty()

contains

public boolean contains(Block block)

Returns true if this Worklist contains the given block.

Parameters:

block - the given block to check

Returns:

true if this Worklist contains the given block

add

public void add(Block block)

Add the given block to this Worklist. Adds unconditionally: does not check containment first.

Parameters:

block - the block to add to this Worklist

poll

@Pure
public @Nullable Block poll()

Returns the head of this Worklist.

Returns:

the head of this Worklist

See Also:

• PriorityQueue.poll()

remove

@Pure
public Block remove()

Returns the head of this Worklist.

Returns:

the head of this Worklist

See Also:

• PriorityQueue.remove(java.lang.Object)

toString

public String toString()

Overrides:

toString in class Object