polyglot.visit
Class DataFlow

java.lang.Object
  polyglot.visit.NodeVisitor
      polyglot.visit.HaltingVisitor
          polyglot.visit.ErrorHandlingVisitor
              polyglot.visit.DataFlow

All Implemented Interfaces:

java.lang.Cloneable, Copy

Direct Known Subclasses:

CopyPropagator, DeadCodeEliminator, ExitChecker, InitChecker, KeyChecker, ReachChecker

public abstract class DataFlow
extends ErrorHandlingVisitor

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

Nested Class Summary

protected static class	DataFlow.BoolItem This class contains two Items, one being the Item that is used when an expression is true, the other being the one that is used when an expression is false.
protected static class	DataFlow.ConditionNavigator Deprecated.
protected static class	DataFlow.FlowGraphSource
static class	DataFlow.Item An Item contains the data which flows during the dataflow analysis.

Field Summary

protected boolean	dataflowOnEntry Indicates whether the dataflow should be performed on entering a CodeDecl, or on leaving a CodeDecl.
protected static int	flowCounter
protected java.util.LinkedList	flowgraphStack A stack of FlowGraphSource.
protected boolean	forward Indicates whether this dataflow is a forward analysis.

Fields inherited from class polyglot.visit.ErrorHandlingVisitor

error, job, nf, ts

Constructor Summary

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

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

Method Summary

protected abstract void	check(FlowGraph graph, Term n, DataFlow.Item inItem, java.util.Map outItems) Check that the term n satisfies whatever properties this dataflow is checking for.
protected DataFlow.Item	confluence(java.util.List items, java.util.List itemKeys, Term node, FlowGraph graph) The confluence operator for many flows.
protected abstract DataFlow.Item	confluence(java.util.List items, Term node, FlowGraph graph) The confluence operator for many flows.
protected static java.util.Map	constructItemsFromCondition(Expr booleanCond, DataFlow.Item startingItem, java.util.Set succEdgeKeys, DataFlow.ConditionNavigator navigator) 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.
protected CFGBuilder	createCFGBuilder(TypeSystem ts, FlowGraph g) Construct a CFGBuilder.
protected abstract DataFlow.Item	createInitialItem(FlowGraph graph, Term node) Create an initial Item for the term node.
protected FlowGraph	currentFlowGraph() Return the FlowGraph at the top of the stack.
protected void	dataflow(CodeDecl cd) Construct a flow graph for the CodeDecl provided, and call dataflow(FlowGraph).
protected void	dataflow(FlowGraph graph) Perform the dataflow on the flowgraph provided.
protected void	dumpFlowGraph(FlowGraph 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 CodeDecl nodes.
protected java.util.List	filterItems(java.util.List items, java.util.List itemKeys, FlowGraph.EdgeKey filterEdgeKey) Filter a list of Items to contain only Items that are associated with the given EdgeKey.
protected java.util.List	filterItemsExceptionSubclass(java.util.List items, java.util.List 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	filterItemsNonError(java.util.List items, java.util.List 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	filterItemsNonException(java.util.List items, java.util.List 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 java.util.LinkedList	findSCCs(FlowGraph graph) Returns the linked list [by_scc, scc_head] where by_scc is an array in which SCCs occur in topologically order.
protected java.util.Map	flow(DataFlow.Item trueItem, DataFlow.Item falseItem, DataFlow.Item otherItem, FlowGraph graph, Term n, java.util.Set edgeKeys)
protected java.util.Map	flow(DataFlow.Item in, FlowGraph graph, Term n, java.util.Set edgeKeys) Produce new Items as appropriate for the Term n and the input Item in.
protected java.util.Map	flow(java.util.List inItems, java.util.List inItemKeys, FlowGraph graph, Term n, java.util.Set edgeKeys) Produce new Items as appropriate for the Term n and the input Items.
protected java.util.Map	flowBooleanConditions(DataFlow.Item trueItem, DataFlow.Item falseItem, DataFlow.Item otherItem, FlowGraph graph, Expr n, java.util.Set edgeKeys)
protected java.util.Map	flowToBooleanFlow(java.util.List inItems, java.util.List inItemKeys, FlowGraph graph, Term n, java.util.Set edgeKeys) 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 neccessary, and passes the results to flow(Item, Item, Item, FlowGraph, Term, Set).
protected static boolean	hasTrueFalseBranches(java.util.Set 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	initGraph(CodeDecl code, Term root) Initialise the FlowGraph to be used in the dataflow analysis.
protected static java.util.Map	itemsToMap(DataFlow.Item trueItem, DataFlow.Item falseItem, DataFlow.Item remainingItem, java.util.Set edgeKeys) This utility methods is for subclasses to convert a Items into a Map, to return from the flow methods.
protected static java.util.Map	itemToMap(DataFlow.Item i, java.util.Set edgeKeys) This utility methods is for subclasses to convert a single Item into a Map, to return from the flow methods.
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 peermaps appropriately, since they are based on IdentityKeys.
protected Node	leaveCall(Node n) Overridden superclass method, to pop from the stack of FlowGraphs if necessary.
protected void	post(FlowGraph graph, Term root) Check all of the Peers in the graph, after the dataflow analysis has been performed.
protected DataFlow.Item	safeConfluence(DataFlow.Item item1, FlowGraph.EdgeKey key1, DataFlow.Item item2, FlowGraph.EdgeKey key2, DataFlow.Item item3, FlowGraph.EdgeKey key3, Term node, FlowGraph graph)
protected DataFlow.Item	safeConfluence(DataFlow.Item item1, FlowGraph.EdgeKey key1, DataFlow.Item item2, FlowGraph.EdgeKey key2, Term node, FlowGraph graph)
protected DataFlow.Item	safeConfluence(java.util.List items, java.util.List itemKeys, Term node, FlowGraph graph) The confluence operator for many flows.

Methods inherited from class polyglot.visit.ErrorHandlingVisitor

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

Methods inherited from class polyglot.visit.HaltingVisitor

bypass, bypass, bypassChildren, copy, override, visitChildren

Methods inherited from class polyglot.visit.NodeVisitor

enter, finish, finish, leave, override, toString, visitEdge

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.

dataflowOnEntry

protected final boolean dataflowOnEntry

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

flowgraphStack

protected java.util.LinkedList flowgraphStack

A stack of FlowGraphSource. The flow graph is constructed upon entering a CodeDecl AST node, and dataflow performed on that flow graph immediately. The flow graph is available during the visiting of children of the CodeDecl, if subclasses want to use this information to update AST nodes. The stack is only maintained if dataflowOnEntry 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.

Method Detail

createInitialItem

protected abstract DataFlow.Item createInitialItem(FlowGraph graph,
                                                   Term node)

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 flow(DataFlow.Item in,
                             FlowGraph graph,
                             Term n,
                             java.util.Set edgeKeys)

Produce new Items as appropriate for the Term n and the input Item in.

Parameters:

in - the Item flowing into the node. Note that if the Term n has many flows going into it, the Item in may be the result of a call to confluence(List, List, Term)

graph - the FlowGraph which the dataflow is operating on

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

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.

flow

protected java.util.Map flow(java.util.List inItems,
                             java.util.List inItemKeys,
                             FlowGraph graph,
                             Term n,
                             java.util.Set edgeKeys)

Produce new Items as appropriate for the Term n 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 grain 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.

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 flowToBooleanFlow(java.util.List inItems,
                                                java.util.List inItemKeys,
                                                FlowGraph graph,
                                                Term n,
                                                java.util.Set edgeKeys)

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 neccessary, 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 grain 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

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

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.

flow

protected java.util.Map flow(DataFlow.Item trueItem,
                             DataFlow.Item falseItem,
                             DataFlow.Item otherItem,
                             FlowGraph graph,
                             Term n,
                             java.util.Set edgeKeys)

flowBooleanConditions

protected java.util.Map flowBooleanConditions(DataFlow.Item trueItem,
                                              DataFlow.Item falseItem,
                                              DataFlow.Item otherItem,
                                              FlowGraph graph,
                                              Expr n,
                                              java.util.Set edgeKeys)

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

n - The boolean expression.

edgeKeys - The outgoing edges

confluence

protected abstract DataFlow.Item confluence(java.util.List items,
                                            Term node,
                                            FlowGraph 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.

node - Term for which the items are flowing into.

Returns:

a non-null Item.

confluence

protected DataFlow.Item confluence(java.util.List items,
                                   java.util.List itemKeys,
                                   Term node,
                                   FlowGraph 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.

node - Term for which the items are flowing into.

Returns:

a non-null Item.

safeConfluence

protected DataFlow.Item safeConfluence(java.util.List items,
                                       java.util.List itemKeys,
                                       Term node,
                                       FlowGraph 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.

node - Term for which the items are flowing into.

Returns:

a non-null Item.

safeConfluence

protected DataFlow.Item safeConfluence(DataFlow.Item item1,
                                       FlowGraph.EdgeKey key1,
                                       DataFlow.Item item2,
                                       FlowGraph.EdgeKey key2,
                                       Term node,
                                       FlowGraph graph)

safeConfluence

protected DataFlow.Item safeConfluence(DataFlow.Item item1,
                                       FlowGraph.EdgeKey key1,
                                       DataFlow.Item item2,
                                       FlowGraph.EdgeKey key2,
                                       DataFlow.Item item3,
                                       FlowGraph.EdgeKey key3,
                                       Term node,
                                       FlowGraph graph)

check

protected abstract void check(FlowGraph graph,
                              Term n,
                              DataFlow.Item inItem,
                              java.util.Map outItems)
                       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.

SemanticException

dataflow

protected void dataflow(CodeDecl cd)
                 throws SemanticException

Construct a flow graph for the CodeDecl 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 CodeDecl nodes.

Throws:

SemanticException

findSCCs

protected java.util.LinkedList findSCCs(FlowGraph graph)

Returns the linked list [by_scc, scc_head] where by_scc is an array in which SCCs occur in topologically 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 graph)

Perform the dataflow on the flowgraph provided.

initGraph

protected FlowGraph initGraph(CodeDecl code,
                              Term root)

Initialise the FlowGraph to be used in the dataflow analysis.

Returns:

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

createCFGBuilder

protected CFGBuilder createCFGBuilder(TypeSystem ts,
                                      FlowGraph 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 CodeDecl 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 peermaps 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 n)
                  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 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 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 CodeDecls, 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 CodeDecl, then the FlowGraph returned should be the FlowGraph for the dataflow for innermost CodeDecl.

itemToMap

protected static final java.util.Map itemToMap(DataFlow.Item i,
                                               java.util.Set edgeKeys)

This utility methods 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 java.util.Map itemsToMap(DataFlow.Item trueItem,
                                                DataFlow.Item falseItem,
                                                DataFlow.Item remainingItem,
                                                java.util.Set edgeKeys)

This utility methods is for subclasses to convert a 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 filterItemsNonError(java.util.List items,
                                                   java.util.List 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 filterItemsNonException(java.util.List items,
                                                       java.util.List 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 filterItemsExceptionSubclass(java.util.List items,
                                                            java.util.List 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 filterItems(java.util.List items,
                                           java.util.List 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 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

protected static java.util.Map constructItemsFromCondition(Expr booleanCond,
                                                           DataFlow.Item startingItem,
                                                           java.util.Set succEdgeKeys,
                                                           DataFlow.ConditionNavigator navigator)

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 graph,
                             Term root)

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