polyglot.visit

Class DataFlow<FlowItem extends DataFlow.Item>

java.lang.Object

polyglot.visit.NodeVisitor

polyglot.visit.HaltingVisitor

polyglot.visit.ErrorHandlingVisitor

polyglot.visit.DataFlow<FlowItem>

All Implemented Interfaces:

java.lang.Cloneable, Copy<NodeVisitor>

Direct Known Subclasses:

CopyPropagator, DeadCodeEliminator, DefiniteAssignmentChecker, ExitChecker, InitChecker, ReachChecker

public abstract class DataFlow<FlowItem extends DataFlow.Item>
extends ErrorHandlingVisitor

Abstract dataflow Visitor, to allow simple dataflow equations to be easily implemented.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
protected static class	DataFlow.BoolItem<FlowItem extends DataFlow.Item> Deprecated. Use flowBooleanConditions
protected static class	DataFlow.ConditionNavigator<FlowItem extends DataFlow.Item> Deprecated.
protected static class	DataFlow.FlowGraphSource<FlowItem extends DataFlow.Item>
protected static class	DataFlow.Frame<FlowItem extends DataFlow.Item> A "stack frame" for recursive DFS
static class	DataFlow.Item An Item contains the data which flows during dataflow analysis.

Nested classes/interfaces inherited from interface polyglot.util.Copy

Copy.Util

Field Summary

Fields

Modifier and Type	Field and Description
protected boolean	dataflowOnEntry Indicates whether the dataflow should be performed on entering a CodeNode, or on leaving a CodeNode.
protected boolean	detectBackEdges Indicates whether the dataflow should detect back edges.
protected static int	flowCounter
protected java.util.LinkedList<DataFlow.FlowGraphSource<FlowItem>>	flowgraphStack A stack of FlowGraphSource.
protected boolean	forward Indicates whether this dataflow is a forward analysis.
protected java.util.Map<FlowGraph.Peer<FlowItem>,java.lang.Integer>	postordering Map from Peers to Integers that contains a post-ordering of Peers if this.detectBackEdges is true.

Fields inherited from class polyglot.visit.ErrorHandlingVisitor

error, job, nf, ts

Fields inherited from class polyglot.visit.HaltingVisitor

bypass, bypassParent

Constructor Summary

Constructors

Constructor and Description
DataFlow(Job job, TypeSystem ts, NodeFactory nf, boolean forward) Constructor.
DataFlow(Job job, TypeSystem ts, NodeFactory nf, boolean forward, boolean dataflowOnEntry) Constructor.
DataFlow(Job job, TypeSystem ts, NodeFactory nf, boolean forward, boolean dataflowOnEntry, boolean detectBackEdges) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
protected void	check(FlowGraph<FlowItem> graph, FlowGraph.Peer<FlowItem> p) Check that the term n satisfies whatever properties this dataflow is checking for.
protected abstract void	check(FlowGraph<FlowItem> graph, Term n, boolean entry, FlowItem inItem, java.util.Map<FlowGraph.EdgeKey,FlowItem> outItems) Check that the term n satisfies whatever properties this dataflow is checking for.
protected abstract FlowItem	confluence(java.util.List<FlowItem> items, FlowGraph.Peer<FlowItem> peer, FlowGraph<FlowItem> graph) The confluence operator for many flows.
protected FlowItem	confluence(java.util.List<FlowItem> items, java.util.List<FlowGraph.EdgeKey> itemKeys, FlowGraph.Peer<FlowItem> peer, FlowGraph<FlowItem> graph) The confluence operator for many flows.
protected static <FlowItem extends DataFlow.Item> java.util.Map<FlowGraph.EdgeKey,FlowItem>	constructItemsFromCondition(Expr booleanCond, FlowItem startingItem, java.util.Set<FlowGraph.EdgeKey> succEdgeKeys, DataFlow.ConditionNavigator<FlowItem> navigator) Deprecated.
protected CFGBuilder<FlowItem>	createCFGBuilder(TypeSystem ts, FlowGraph<FlowItem> g) Construct a CFGBuilder.
protected DataFlow.Frame<FlowItem>	createFrame(FlowGraph.Peer<FlowItem> p, boolean forward, FlowGraph<FlowItem> grahp)
protected FlowItem	createInitialItem(FlowGraph<FlowItem> graph, FlowGraph.Peer<FlowItem> peer) Create an initial Item for the term node.
protected abstract FlowItem	createInitialItem(FlowGraph<FlowItem> graph, Term node, boolean entry) Create an initial Item for the term node.
protected FlowGraph<FlowItem>	currentFlowGraph() Return the FlowGraph at the top of the stack.
protected void	dataflow(CodeDecl cd) Construct a flow graph for the CodeNode provided, and call dataflow(FlowGraph).
protected void	dataflow(CodeNode cd)
protected void	dataflow(FlowGraph<FlowItem> graph) Perform the dataflow on flow graph graph.
protected void	dumpFlowGraph(FlowGraph<FlowItem> graph, Term root) Dump a flow graph, labeling edges with their flows, to aid in the debugging of data flow.
protected NodeVisitor	enterCall(Node n) Overridden superclass method, to build the flow graph, perform dataflow analysis, and check the analysis for CodeNode nodes.
protected java.util.List<FlowItem>	filterItems(java.util.List<FlowItem> items, java.util.List<FlowGraph.EdgeKey> itemKeys, FlowGraph.EdgeKey filterEdgeKey) Filter a list of Items to contain only Items that are associated with the given EdgeKey.
protected java.util.List<FlowItem>	filterItemsExceptionSubclass(java.util.List<FlowItem> items, java.util.List<FlowGraph.EdgeKey> itemKeys, Type excType) Filter a list of Items to contain only Items that are associated with exception flows, whose exception is a subclass of excType.
protected java.util.List<FlowItem>	filterItemsNonError(java.util.List<FlowItem> items, java.util.List<FlowGraph.EdgeKey> itemKeys) Filter a list of Items to contain only Items that are not associated with error flows, that is, only Items whose associated EdgeKeys are not FlowGraph.ExceptionEdgeKeys with a type that is a subclass of TypeSystem.Error().
protected java.util.List<FlowItem>	filterItemsNonException(java.util.List<FlowItem> items, java.util.List<FlowGraph.EdgeKey> itemKeys) Filter a list of Items to contain only Items that are not associated with exception flows, that is, only Items whose associated EdgeKeys are not FlowGraph.ExceptionEdgeKeys.
protected Pair<FlowGraph.Peer<FlowItem>[],int[]>	findSCCs(FlowGraph<FlowItem> graph) Returns the linked list [by_scc, scc_head] where by_scc is an array in which SCCs occur in topologically sorted order.
protected java.util.Map<FlowGraph.EdgeKey,FlowItem>	flow(FlowItem in, FlowGraph<FlowItem> graph, FlowGraph.Peer<FlowItem> peer) Produce new Items as appropriate for the Peer and the input Items.
protected java.util.Map<FlowGraph.EdgeKey,FlowItem>	flow(FlowItem trueItem, FlowItem falseItem, FlowItem otherItem, FlowGraph<FlowItem> graph, FlowGraph.Peer<FlowItem> peer)
protected java.util.Map<FlowGraph.EdgeKey,FlowItem>	flow(java.util.List<FlowItem> inItems, java.util.List<FlowGraph.EdgeKey> inItemKeys, FlowGraph<FlowItem> graph, FlowGraph.Peer<FlowItem> peer) Produce new Items as appropriate for the peer's node and the input Items.
protected java.util.Map<FlowGraph.EdgeKey,FlowItem>	flow(java.util.List<FlowItem> inItems, java.util.List<FlowGraph.EdgeKey> inItemKeys, java.util.List<FlowGraph.Peer<FlowItem>> inItemPeers, FlowGraph<FlowItem> graph, FlowGraph.Peer<FlowItem> p) Produce new Items as appropriate for the Peer and the input Items.
protected java.util.Map<FlowGraph.EdgeKey,FlowItem>	flow(java.util.List<FlowItem> inItems, java.util.List<FlowGraph.EdgeKey> inItemKeys, java.util.List<FlowGraph.Peer<FlowItem>> inItemPeers, java.util.List<java.lang.Boolean> isBackEdges, FlowGraph<FlowItem> graph, FlowGraph.Peer<FlowItem> p)
protected java.util.Map<FlowGraph.EdgeKey,FlowItem>	flowBooleanConditions(FlowItem trueItem, FlowItem falseItem, FlowItem otherItem, FlowGraph<FlowItem> graph, FlowGraph.Peer<FlowItem> peer)
protected java.util.Map<FlowGraph.EdgeKey,FlowItem>	flowToBooleanFlow(java.util.List<FlowItem> inItems, java.util.List<FlowGraph.EdgeKey> inItemKeys, FlowGraph<FlowItem> graph, FlowGraph.Peer<FlowItem> peer) A utility method that simply collects together all the TRUE items, FALSE items, and all other items (including ExceptionEdgeKey items), calls confluence on each of these three collections as necessary, and passes the results to flow(Item, Item, Item, FlowGraph, Term, Set).
protected static boolean	hasTrueFalseBranches(java.util.Set<FlowGraph.EdgeKey> edgeKeys) This utility method is for subclasses to determine if the node currently under consideration has both true and false edges leaving it.
protected FlowGraph<FlowItem>	initGraph(CodeDecl code, Term root) Initialize the FlowGraph to be used in the dataflow analysis.
protected FlowGraph<FlowItem>	initGraph(CodeNode code, Term root) Initialize the FlowGraph to be used in the dataflow analysis.
protected static <FlowItem> java.util.Map<FlowGraph.EdgeKey,FlowItem>	itemsToMap(FlowItem trueItem, FlowItem falseItem, FlowItem remainingItem, java.util.Set<FlowGraph.EdgeKey> edgeKeys) This utility method is for subclasses to convert Items into a Map, to return from the flow methods.
static <FlowItem> java.util.Map<FlowGraph.EdgeKey,FlowItem>	itemToMap(FlowItem i, java.util.Set<FlowGraph.EdgeKey> edgeKeys) This utility method is for subclasses to convert a single Item into a Map, to return from the flow methods.
JLang	lang()
Node	leave(Node parent, Node old, Node n, NodeVisitor v) Overridden superclass method, to make sure that if a subclass has changed a Term, that we update the peer maps appropriately, since they are based on IdentityKeys.
protected Node	leaveCall(Node old, Node n, NodeVisitor v) Overridden superclass method, to pop from the stack of FlowGraphs if necessary.
protected void	post(FlowGraph<FlowItem> graph, Term root) Check all of the Peers in the graph, after the dataflow analysis has been performed.
protected FlowItem	safeConfluence(FlowItem item1, FlowGraph.EdgeKey key1, FlowItem item2, FlowGraph.EdgeKey key2, FlowGraph.Peer<FlowItem> peer, FlowGraph<FlowItem> graph)
protected FlowItem	safeConfluence(FlowItem item1, FlowGraph.EdgeKey key1, FlowItem item2, FlowGraph.EdgeKey key2, FlowItem item3, FlowGraph.EdgeKey key3, FlowGraph.Peer<FlowItem> peer, FlowGraph<FlowItem> graph)
protected FlowItem	safeConfluence(java.util.List<FlowItem> items, java.util.List<FlowGraph.EdgeKey> itemKeys, FlowGraph.Peer<FlowItem> peer, FlowGraph<FlowItem> graph) The confluence operator for many flows.

Methods inherited from class polyglot.visit.ErrorHandlingVisitor

begin, catchErrors, enter, enterCall, enterError, errorQueue, hasErrors, job, leaveCall, leaveCall, nodeFactory, typeSystem

Methods inherited from class polyglot.visit.HaltingVisitor

bypass, bypass, bypassChildren, override, visitChildren

Methods inherited from class polyglot.visit.NodeVisitor

copy, enter, finish, finish, leave, override, toString, visitEdge, visitEdgeNoOverride

Methods inherited from class java.lang.Object

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

Field Detail

forward

protected final boolean forward

Indicates whether this dataflow is a forward analysis.

detectBackEdges

protected final boolean detectBackEdges

Indicates whether the dataflow should detect back edges. Detecting back edges allows clients to use a widening operator just on confluences from back edges, permitting analyses to use data flow lattices of infinite height while guaranteeing termination.

dataflowOnEntry

protected final boolean dataflowOnEntry

Indicates whether the dataflow should be performed on entering a CodeNode, or on leaving a CodeNode. If dataflow is performed on entry, then the control flow graph will be available when visiting children of the CodeNode, via the currentFlowGraph method. If dataflow is performed on leaving, then the control flow graph will not be available, but nested CodeNodes will have already been processed.

flowgraphStack

protected java.util.LinkedList<DataFlow.FlowGraphSource<FlowItem extends DataFlow.Item>> flowgraphStack

A stack of FlowGraphSource. The flow graph is constructed upon entering a CodeNode AST node, and dataflow performed on that flow graph immediately. The flow graph is available during the visiting of children of the CodeNode, if subclasses want to use this information to update AST nodes. The stack is maintained only if dataflowOnEntry is true.

postordering

protected java.util.Map<FlowGraph.Peer<FlowItem extends DataFlow.Item>,java.lang.Integer> postordering

Map from Peers to Integers that contains a post-ordering of Peers if this.detectBackEdges is true.

flowCounter

protected static int flowCounter

Constructor Detail

DataFlow

public DataFlow(Job job,
        TypeSystem ts,
        NodeFactory nf,
        boolean forward)

Constructor.

DataFlow

public DataFlow(Job job,
        TypeSystem ts,
        NodeFactory nf,
        boolean forward,
        boolean dataflowOnEntry)

Constructor.

DataFlow

public DataFlow(Job job,
        TypeSystem ts,
        NodeFactory nf,
        boolean forward,
        boolean dataflowOnEntry,
        boolean detectBackEdges)

Constructor.

Method Detail

lang

public JLang lang()

Overrides:

lang in class NodeVisitor

createInitialItem

protected FlowItem createInitialItem(FlowGraph<FlowItem> graph,
                         FlowGraph.Peer<FlowItem> peer)

Create an initial Item for the term node. This is generally how the Item that will be given to the entry peer of a graph is created, although this method may also be called for other (non-start) nodes.

Returns:

a (possibly null) Item.

createInitialItem

protected abstract FlowItem createInitialItem(FlowGraph<FlowItem> graph,
                         Term node,
                         boolean entry)

Create an initial Item for the term node. This is generally how the Item that will be given to the start node of a graph is created, although this method may also be called for other (non-start) nodes.

Returns:

a (possibly null) Item.

flow

protected java.util.Map<FlowGraph.EdgeKey,FlowItem> flow(FlowItem in,
                                             FlowGraph<FlowItem> graph,
                                             FlowGraph.Peer<FlowItem> peer)

Produce new Items as appropriate for the Peer and the input Items.

Parameters:

inItems - all the Items flowing into the node.

inItemKeys - the FlowGraph.EdgeKeys for the items in the list inItems

graph - the FlowGraph which the dataflow is operating on

peer - the Peer which this method must calculate the flow for.

Returns:

a Map from FlowGraph.EdgeKeys to Items. The map must have entries for all EdgeKeys in edgeKeys.

flow

protected java.util.Map<FlowGraph.EdgeKey,FlowItem> flow(java.util.List<FlowItem> inItems,
                                             java.util.List<FlowGraph.EdgeKey> inItemKeys,
                                             java.util.List<FlowGraph.Peer<FlowItem>> inItemPeers,
                                             FlowGraph<FlowItem> graph,
                                             FlowGraph.Peer<FlowItem> p)

Produce new Items as appropriate for the Peer and the input Items. Subclasses should override if flow behavior needs to distinguish between source peers.

Parameters:

inItems - all the Items flowing into the node.

inItemKeys - the FlowGraph.EdgeKeys for the items in the list inItems

inItemPeers - the Peers from which the Items flowed into the node

graph - the FlowGraph which the dataflow is operating on

peer - the Peer which this method must calculate the flow for.

Returns:

a Map from FlowGraph.EdgeKeys to Items. The map must have entries for all EdgeKeys in edgeKeys.

flow

protected java.util.Map<FlowGraph.EdgeKey,FlowItem> flow(java.util.List<FlowItem> inItems,
                                             java.util.List<FlowGraph.EdgeKey> inItemKeys,
                                             java.util.List<FlowGraph.Peer<FlowItem>> inItemPeers,
                                             java.util.List<java.lang.Boolean> isBackEdges,
                                             FlowGraph<FlowItem> graph,
                                             FlowGraph.Peer<FlowItem> p)

Parameters:

inItems - all the Items flowing into the node.

inItemKeys - the FlowGraph.EdgeKeys for the items in the list inItems

inItemPeers - the Peers from which the Items flowed into the node

isBackEdge - list of Booleans indicating whether the edge represented by the corresponding element in inItems is a back edge or not.

graph - the FlowGraph which the dataflow is operating on

peer - the Peer which this method must calculate the flow for.

Returns:

a Map from FlowGraph.EdgeKeys to Items. The map must have entries for all EdgeKeys in edgeKeys.

flow

protected java.util.Map<FlowGraph.EdgeKey,FlowItem> flow(java.util.List<FlowItem> inItems,
                                             java.util.List<FlowGraph.EdgeKey> inItemKeys,
                                             FlowGraph<FlowItem> graph,
                                             FlowGraph.Peer<FlowItem> peer)

Produce new Items as appropriate for the peer's node and the input Items. The default implementation of this method is simply to call confluence for the list of inItems, and pass the result to flow(Item, FlowGraph, Term, Set). Subclasses may want to override this method if a finer-grained dataflow is required. Some subclasses may wish to override this method to call flowToBooleanFlow.

Parameters:

inItems - all the Items flowing into the node.

inItemKeys - the FlowGraph.EdgeKeys for the items in the list inItems

graph - the FlowGraph which the dataflow is operating on

n - the Term which this method must calculate the flow for.

entry - indicates whether we are looking at the entry or exit of n.

edgeKeys - a set of FlowGraph.EdgeKeys, being all the EdgeKeys of the edges leaving this node. The returned Map must have mappings for all objects in this set.

Returns:

a Map from FlowGraph.EdgeKeys to Items. The map must have entries for all EdgeKeys in edgeKeys.

flowToBooleanFlow

protected final java.util.Map<FlowGraph.EdgeKey,FlowItem> flowToBooleanFlow(java.util.List<FlowItem> inItems,
                                                          java.util.List<FlowGraph.EdgeKey> inItemKeys,
                                                          FlowGraph<FlowItem> graph,
                                                          FlowGraph.Peer<FlowItem> peer)

A utility method that simply collects together all the TRUE items, FALSE items, and all other items (including ExceptionEdgeKey items), calls confluence on each of these three collections as necessary, and passes the results to flow(Item, Item, Item, FlowGraph, Term, Set). It is expected that this method will typically be called by subclasses overriding the flow(List, List, FlowGraph, Term, Set) method, due to the need for a finer-grained dataflow analysis.

Parameters:

inItems - all the Items flowing into the node.

inItemKeys - the FlowGraph.EdgeKeys for the items in the list inItems

graph - the FlowGraph which the dataflow is operating on

peer - the Peer which this method must calculate the flow for.

Returns:

a Map from FlowGraph.EdgeKeys to Items. The map must have entries for all EdgeKeys in edgeKeys.

flow

protected java.util.Map<FlowGraph.EdgeKey,FlowItem> flow(FlowItem trueItem,
                                             FlowItem falseItem,
                                             FlowItem otherItem,
                                             FlowGraph<FlowItem> graph,
                                             FlowGraph.Peer<FlowItem> peer)

flowBooleanConditions

protected java.util.Map<FlowGraph.EdgeKey,FlowItem> flowBooleanConditions(FlowItem trueItem,
                                                              FlowItem falseItem,
                                                              FlowItem otherItem,
                                                              FlowGraph<FlowItem> graph,
                                                              FlowGraph.Peer<FlowItem> peer)

Parameters:

trueItem - The item for flows coming into n for true conditions. Cannot be null.

falseItem - The item for flows coming into n for false conditions. Cannot be null.

otherItem - The item for all other flows coming into n

peer - The Peer for the boolean expression.

Returns:

Map from edge keys to Items. Will return null if the binary operator was not one of !, &&, ||, & or |, to allow the calling method to determine which map to use.

confluence

protected abstract FlowItem confluence(java.util.List<FlowItem> items,
                  FlowGraph.Peer<FlowItem> peer,
                  FlowGraph<FlowItem> graph)

The confluence operator for many flows. This method produces a single Item from a List of Items, for the confluence just before flow enters node.

Parameters:

items - List of Items that flow into node. this method will only be called if the list has at least 2 elements.

peer - Peer for which the items are flowing into.

Returns:

a non-null Item.

confluence

protected FlowItem confluence(java.util.List<FlowItem> items,
                  java.util.List<FlowGraph.EdgeKey> itemKeys,
                  FlowGraph.Peer<FlowItem> peer,
                  FlowGraph<FlowItem> graph)

The confluence operator for many flows. This method produces a single Item from a List of Items, for the confluence just before flow enters node.

Parameters:

items - List of Items that flow into node. This method will only be called if the list has at least 2 elements.

itemKeys - List of FlowGraph.ExceptionEdgeKeys for the edges that the corresponding Items in items flowed from.

peer - Peer for which the items are flowing into.

Returns:

a non-null Item.

safeConfluence

protected FlowItem safeConfluence(java.util.List<FlowItem> items,
                      java.util.List<FlowGraph.EdgeKey> itemKeys,
                      FlowGraph.Peer<FlowItem> peer,
                      FlowGraph<FlowItem> graph)

The confluence operator for many flows. This method produces a single Item from a List of Items, for the confluence just before flow enters node.

Parameters:

items - List of Items that flow into node. This method will only be called if the list has at least 2 elements.

itemKeys - List of FlowGraph.ExceptionEdgeKeys for the edges that the corresponding Items in items flowed from.

peer - Peer for which the items are flowing into.

safeConfluence

protected FlowItem safeConfluence(FlowItem item1,
                      FlowGraph.EdgeKey key1,
                      FlowItem item2,
                      FlowGraph.EdgeKey key2,
                      FlowGraph.Peer<FlowItem> peer,
                      FlowGraph<FlowItem> graph)

safeConfluence

protected FlowItem safeConfluence(FlowItem item1,
                      FlowGraph.EdgeKey key1,
                      FlowItem item2,
                      FlowGraph.EdgeKey key2,
                      FlowItem item3,
                      FlowGraph.EdgeKey key3,
                      FlowGraph.Peer<FlowItem> peer,
                      FlowGraph<FlowItem> graph)

check

protected abstract void check(FlowGraph<FlowItem> graph,
         Term n,
         boolean entry,
         FlowItem inItem,
         java.util.Map<FlowGraph.EdgeKey,FlowItem> outItems)
                       throws SemanticException

Check that the term n satisfies whatever properties this dataflow is checking for. Provided the method check(FlowGraph, Peer) is not overridden, this method is called for each term in a code declaration block after the dataflow for that block of code has been performed.

Throws:

SemanticException - if the properties this dataflow analysis is checking for is not satisfied.

check

protected void check(FlowGraph<FlowItem> graph,
         FlowGraph.Peer<FlowItem> p)
              throws SemanticException

Check that the term n satisfies whatever properties this dataflow is checking for. This method is called for each term in a code declaration block after the dataflow for that block of code has been performed.

Throws:

SemanticException - if the properties this dataflow analysis is checking for is not satisfied.

dataflow

protected void dataflow(CodeDecl cd)
                 throws SemanticException

Construct a flow graph for the CodeNode provided, and call dataflow(FlowGraph). Is also responsible for calling post(FlowGraph, Block) after dataflow(FlowGraph) has been called, and for pushing the FlowGraph onto the stack of FlowGraphs if dataflow analysis is performed on entry to CodeNode nodes.

Throws:

SemanticException

dataflow

protected void dataflow(CodeNode cd)
                 throws SemanticException

Throws:

SemanticException

createFrame

protected DataFlow.Frame<FlowItem> createFrame(FlowGraph.Peer<FlowItem> p,
                                   boolean forward,
                                   FlowGraph<FlowItem> grahp)

findSCCs

protected Pair<FlowGraph.Peer<FlowItem>[],int[]> findSCCs(FlowGraph<FlowItem> graph)

Returns the linked list [by_scc, scc_head] where by_scc is an array in which SCCs occur in topologically sorted order. scc_head[n] where n is the first peer in an SCC is set to -1. scc_head[n] where n is the last peer in a (non-singleton) SCC is set to the index of the first peer. Otherwise it is -2.

dataflow

protected void dataflow(FlowGraph<FlowItem> graph)

Perform the dataflow on flow graph graph.

initGraph

protected FlowGraph<FlowItem> initGraph(CodeNode code,
                            Term root)

Initialize the FlowGraph to be used in the dataflow analysis.

Returns:

null if no dataflow analysis should be performed for this code declaration; otherwise, an appropriately initialized FlowGraph.

initGraph

protected FlowGraph<FlowItem> initGraph(CodeDecl code,
                            Term root)

Initialize the FlowGraph to be used in the dataflow analysis.

Returns:

null if no dataflow analysis should be performed for this code declaration; otherwise, an appropriately initialized FlowGraph.

createCFGBuilder

protected CFGBuilder<FlowItem> createCFGBuilder(TypeSystem ts,
                                    FlowGraph<FlowItem> g)

Construct a CFGBuilder.

Parameters:

ts - The type system

g - The flow graph to that the CFGBuilder will construct.

Returns:

a new CFGBuilder

enterCall

protected NodeVisitor enterCall(Node n)
                         throws SemanticException

Overridden superclass method, to build the flow graph, perform dataflow analysis, and check the analysis for CodeNode nodes.

Overrides:

enterCall in class ErrorHandlingVisitor

Throws:

SemanticException

leave

public Node leave(Node parent,
         Node old,
         Node n,
         NodeVisitor v)

Overridden superclass method, to make sure that if a subclass has changed a Term, that we update the peer maps appropriately, since they are based on IdentityKeys.

Overrides:

leave in class ErrorHandlingVisitor

Parameters:

parent - The parent of old, null if old has no parent.

old - The original state of root of the current subtree.

n - The current state of the root of the current subtree.

v - The NodeVisitor object used to visit the children.

Returns:

The final result of the traversal of the tree rooted at n.

leaveCall

protected Node leaveCall(Node old,
             Node n,
             NodeVisitor v)
                  throws SemanticException

Overridden superclass method, to pop from the stack of FlowGraphs if necessary.

Overrides:

leaveCall in class ErrorHandlingVisitor

Throws:

SemanticException

post

protected void post(FlowGraph<FlowItem> graph,
        Term root)
             throws SemanticException

Check all of the Peers in the graph, after the dataflow analysis has been performed.

Throws:

SemanticException

currentFlowGraph

protected FlowGraph<FlowItem> currentFlowGraph()

Return the FlowGraph at the top of the stack. This method should not be called if dataflow is not being performed on entry to the CodeNodes, as the stack is not maintained in that case. If this method is called by a subclass from the enterCall or leaveCall methods, for an AST node that is a child of a CodeNode, then the FlowGraph returned should be the FlowGraph for the dataflow for innermost CodeNode.

itemToMap

public static final <FlowItem> java.util.Map<FlowGraph.EdgeKey,FlowItem> itemToMap(FlowItem i,
                                                             java.util.Set<FlowGraph.EdgeKey> edgeKeys)

This utility method is for subclasses to convert a single Item into a Map, to return from the flow methods. This method should be used when the same output Item from the flow is to be used for all edges leaving the node.

Parameters:

i - the Item to be placed in the returned Map as the value for every EdgeKey in edgeKeys.

edgeKeys - the Set of EdgeKeys to be used as keys in the returned Map.

Returns:

a Map containing a mapping from every EdgeKey in edgeKeys to the Item i.

itemsToMap

protected static final <FlowItem> java.util.Map<FlowGraph.EdgeKey,FlowItem> itemsToMap(FlowItem trueItem,
                                                              FlowItem falseItem,
                                                              FlowItem remainingItem,
                                                              java.util.Set<FlowGraph.EdgeKey> edgeKeys)

This utility method is for subclasses to convert Items into a Map, to return from the flow methods.

Parameters:

trueItem - the Item to be placed in the returned Map as the value for the FlowGraph.EDGE_KEY_TRUE, if that key is present in edgeKeys.

falseItem - the Item to be placed in the returned Map as the value for the FlowGraph.EDGE_KEY_FALSE, if that key is present in edgeKeys.

remainingItem - the Item to be placed in the returned Map as the value for any edge key other than FlowGraph.EDGE_KEY_TRUE or FlowGraph.EDGE_KEY_FALSE, if any happen to be present in edgeKeys.

edgeKeys - the Set of EdgeKeys to be used as keys in the returned Map.

Returns:

a Map containing a mapping from every EdgeKey in edgeKeys to the Item i.

filterItemsNonError

protected final java.util.List<FlowItem> filterItemsNonError(java.util.List<FlowItem> items,
                                           java.util.List<FlowGraph.EdgeKey> itemKeys)

Filter a list of Items to contain only Items that are not associated with error flows, that is, only Items whose associated EdgeKeys are not FlowGraph.ExceptionEdgeKeys with a type that is a subclass of TypeSystem.Error().

Parameters:

items - List of Items to filter

itemKeys - List of EdgeKeys corresponding to the edge keys for the Items in items.

Returns:

a filtered list of items, containing only those whose edge keys are not FlowGraph.ExceptionEdgeKeys with whose exception types are Errors.

filterItemsNonException

protected final java.util.List<FlowItem> filterItemsNonException(java.util.List<FlowItem> items,
                                               java.util.List<FlowGraph.EdgeKey> itemKeys)

Filter a list of Items to contain only Items that are not associated with exception flows, that is, only Items whose associated EdgeKeys are not FlowGraph.ExceptionEdgeKeys.

Parameters:

items - List of Items to filter

itemKeys - List of EdgeKeys corresponding to the edge keys for the Items in items.

Returns:

a filtered list of items, containing only those whose edge keys are not FlowGraph.ExceptionEdgeKeys.

filterItemsExceptionSubclass

protected final java.util.List<FlowItem> filterItemsExceptionSubclass(java.util.List<FlowItem> items,
                                                    java.util.List<FlowGraph.EdgeKey> itemKeys,
                                                    Type excType)

Filter a list of Items to contain only Items that are associated with exception flows, whose exception is a subclass of excType. That is, only Items whose associated EdgeKeys are FlowGraph.ExceptionEdgeKeys, with the type a subclass of excType.

Parameters:

items - List of Items to filter

itemKeys - List of EdgeKeys corresponding to the edge keys for the Items in items.

excType - an Exception Type.

Returns:

a filtered list of items, containing only those whose edge keys are not FlowGraph.ExceptionEdgeKeys.

filterItems

protected final java.util.List<FlowItem> filterItems(java.util.List<FlowItem> items,
                                   java.util.List<FlowGraph.EdgeKey> itemKeys,
                                   FlowGraph.EdgeKey filterEdgeKey)

Filter a list of Items to contain only Items that are associated with the given EdgeKey.

Parameters:

items - List of Items to filter

itemKeys - List of EdgeKeys corresponding to the edge keys for the Items in items.

filterEdgeKey - the EdgeKey to use as a filter.

Returns:

a filtered list of items, containing only those whose edge keys are the same as filterEdgeKeys.

hasTrueFalseBranches

protected static final boolean hasTrueFalseBranches(java.util.Set<FlowGraph.EdgeKey> edgeKeys)

This utility method is for subclasses to determine if the node currently under consideration has both true and false edges leaving it. That is, the flow graph at this node has successor edges with the EdgeKeys Edge_KEY_TRUE and Edge_KEY_FALSE.

Parameters:

edgeKeys - the Set of EdgeKeys of the successor edges of a given node.

Returns:

true if the edgeKeys contains both Edge_KEY_TRUE and Edge_KEY_FALSE

constructItemsFromCondition

@Deprecated
protected static <FlowItem extends DataFlow.Item> java.util.Map<FlowGraph.EdgeKey,FlowItem> constructItemsFromCondition(Expr booleanCond,
                                                                                                                FlowItem startingItem,
                                                                                                                java.util.Set<FlowGraph.EdgeKey> succEdgeKeys,
                                                                                                                DataFlow.ConditionNavigator<FlowItem> navigator)

Deprecated.

This utility method is meant to be used by subclasses to help them produce appropriate Items for the FlowGraph.EDGE_KEY_TRUE and FlowGraph.EDGE_KEY_FALSE edges from a boolean condition.

Parameters:

booleanCond - the boolean condition that is used to branch on. The type of the expression must be boolean.

startingItem - the Item at the start of the flow for the expression booleanCond.

succEdgeKeys - the set of EdgeKeys of the successor nodes of the current node. Must contain both FlowGraph.EDGE_KEY_TRUE and FlowGraph.EDGE_KEY_FALSE.

navigator - an instance of ConditionNavigator to be used to generate appropriate Items from the boolean condition.

Returns:

a Map containing mappings for all entries in succEdgeKeys. FlowGraph.EDGE_KEY_TRUE and FlowGraph.EDGE_KEY_FALSE map to Items calculated for them using navigator, and all other objects in succEdgeKeys are mapped to startingItem.

dumpFlowGraph

protected void dumpFlowGraph(FlowGraph<FlowItem> graph,
                 Term root)

Dump a flow graph, labeling edges with their flows, to aid in the debugging of data flow.