|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectpolyglot.visit.NodeVisitor
polyglot.visit.HaltingVisitor
polyglot.visit.ErrorHandlingVisitor
polyglot.visit.DataFlow
public abstract class DataFlow
Abstract dataflow Visitor, to allow simple dataflow equations to be easily implemented.
Nested Class Summary | |
---|---|
protected static class |
DataFlow.BoolItem
This class contains two Item s, 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 Item s 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 Item s to contain only Item s
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 Item s to contain only Item s
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 Item s to contain only Item s
that are not associated with error flows, that is, only
Item s whose associated EdgeKey s are not
FlowGraph.ExceptionEdgeKey s 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 Item s to contain only Item s
that are not associated with exception flows, that is, only
Item s whose associated EdgeKey s are not
FlowGraph.ExceptionEdgeKey s. |
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 Item s 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 Item s as appropriate for the
Term n and the input Item s. |
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 IdentityKey s. |
protected Node |
leaveCall(Node n)
Overridden superclass method, to pop from the stack of FlowGraph s 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 |
---|
protected final boolean forward
protected final boolean dataflowOnEntry
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
CodeDecl
s will have already been processed.
protected java.util.LinkedList flowgraphStack
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.
protected static int flowCounter
Constructor Detail |
---|
public DataFlow(Job job, TypeSystem ts, NodeFactory nf, boolean forward)
public DataFlow(Job job, TypeSystem ts, NodeFactory nf, boolean forward, boolean dataflowOnEntry)
Method Detail |
---|
protected abstract DataFlow.Item createInitialItem(FlowGraph graph, Term node)
protected java.util.Map flow(DataFlow.Item in, FlowGraph graph, Term n, java.util.Set edgeKeys)
Item
s as appropriate for the
Term n
and the input Item in
.
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 onn
- 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.
protected java.util.Map flow(java.util.List inItems, java.util.List inItemKeys, FlowGraph graph, Term n, java.util.Set edgeKeys)
Item
s as appropriate for the
Term n
and the input Item
s. 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
.
inItems
- all the Items flowing into the node.inItemKeys
- the FlowGraph.EdgeKeys for the items in the list inItemsgraph
- the FlowGraph which the dataflow is operating onn
- 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.
protected final java.util.Map flowToBooleanFlow(java.util.List inItems, java.util.List inItemKeys, FlowGraph graph, Term n, java.util.Set edgeKeys)
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.
inItems
- all the Items flowing into the node.inItemKeys
- the FlowGraph.EdgeKeys for the items in the list inItemsgraph
- the FlowGraph which the dataflow is operating onn
- 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.
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 flowBooleanConditions(DataFlow.Item trueItem, DataFlow.Item falseItem, DataFlow.Item otherItem, FlowGraph graph, Expr n, java.util.Set edgeKeys)
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 nn
- The boolean expression.edgeKeys
- The outgoing edgesprotected abstract DataFlow.Item confluence(java.util.List items, Term node, FlowGraph graph)
items
- List of Item
s 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.
protected DataFlow.Item confluence(java.util.List items, java.util.List itemKeys, Term node, FlowGraph graph)
items
- List of Item
s that flow into node
.
This method will only be called if the list has at least 2
elements.itemKeys
- List of FlowGraph.ExceptionEdgeKey
s for
the edges that the corresponding Item
s in
items
flowed from.node
- Term
for which the items
are
flowing into.
protected DataFlow.Item safeConfluence(java.util.List items, java.util.List itemKeys, Term node, FlowGraph graph)
items
- List of Item
s that flow into node
.
This method will only be called if the list has at least 2
elements.itemKeys
- List of FlowGraph.ExceptionEdgeKey
s for
the edges that the corresponding Item
s in
items
flowed from.node
- Term
for which the items
are
flowing into.
protected DataFlow.Item safeConfluence(DataFlow.Item item1, FlowGraph.EdgeKey key1, DataFlow.Item item2, FlowGraph.EdgeKey key2, Term node, FlowGraph graph)
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 abstract void check(FlowGraph graph, Term n, DataFlow.Item inItem, java.util.Map outItems) throws SemanticException
SemanticException
- if the properties this dataflow
analysis is checking for is not satisfied.
SemanticException
protected void dataflow(CodeDecl cd) throws SemanticException
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 FlowGraph
s if
dataflow analysis is performed on entry to CodeDecl
nodes.
SemanticException
protected java.util.LinkedList findSCCs(FlowGraph graph)
protected void dataflow(FlowGraph graph)
protected FlowGraph initGraph(CodeDecl code, Term root)
FlowGraph
to be used in the dataflow
analysis.
FlowGraph.
protected CFGBuilder createCFGBuilder(TypeSystem ts, FlowGraph g)
ts
- The type systemg
- The flow graph to that the CFGBuilder will construct.
protected NodeVisitor enterCall(Node n) throws SemanticException
enterCall
in class ErrorHandlingVisitor
SemanticException
public Node leave(Node parent, Node old, Node n, NodeVisitor v)
IdentityKey
s.
leave
in class ErrorHandlingVisitor
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.
n
.protected Node leaveCall(Node n) throws SemanticException
FlowGraph
s if necessary.
leaveCall
in class ErrorHandlingVisitor
SemanticException
protected void post(FlowGraph graph, Term root) throws SemanticException
SemanticException
protected FlowGraph currentFlowGraph()
FlowGraph
at the top of the stack. This method
should not be called if dataflow is not being performed on entry to
the CodeDecl
s, 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
.
protected static final java.util.Map itemToMap(DataFlow.Item i, java.util.Set edgeKeys)
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.
i
- the Item
to be placed in the returned
Map
as the value for every EdgeKey
in
edgeKeys.
edgeKeys
- the Set
of EdgeKey
s to be used
as keys in the returned Map
.
Map
containing a mapping from every
EdgeKey
in edgeKeys
to the
Item i
.protected static final java.util.Map itemsToMap(DataFlow.Item trueItem, DataFlow.Item falseItem, DataFlow.Item remainingItem, java.util.Set edgeKeys)
Map
, to return from the
flow
methods.
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 EdgeKey
s to be used
as keys in the returned Map
.
Map
containing a mapping from every
EdgeKey
in edgeKeys
to the
Item i
.protected final java.util.List filterItemsNonError(java.util.List items, java.util.List itemKeys)
Item
s to contain only Item
s
that are not associated with error flows, that is, only
Item
s whose associated EdgeKey
s are not
FlowGraph.ExceptionEdgeKey
s with a type that is a subclass
of TypeSystem.Error()
.
items
- List of Items to filteritemKeys
- List of EdgeKey
s corresponding
to the edge keys for the Item
s in items
.
FlowGraph.ExceptionEdgeKey
s with
whose exception types are Error
s.protected final java.util.List filterItemsNonException(java.util.List items, java.util.List itemKeys)
Item
s to contain only Item
s
that are not associated with exception flows, that is, only
Item
s whose associated EdgeKey
s are not
FlowGraph.ExceptionEdgeKey
s.
items
- List of Items to filteritemKeys
- List of EdgeKey
s corresponding
to the edge keys for the Item
s in items
.
FlowGraph.ExceptionEdgeKey
s.protected final java.util.List filterItemsExceptionSubclass(java.util.List items, java.util.List itemKeys, Type excType)
Item
s to contain only Item
s
that are associated with exception flows, whose exception is a subclass
of excType
. That is, only
Item
s whose associated EdgeKey
s are
FlowGraph.ExceptionEdgeKey
s, with the type a subclass
of excType
.
items
- List of Items to filteritemKeys
- List of EdgeKey
s corresponding
to the edge keys for the Item
s in items
.excType
- an Exception Type
.
FlowGraph.ExceptionEdgeKey
s.protected final java.util.List filterItems(java.util.List items, java.util.List itemKeys, FlowGraph.EdgeKey filterEdgeKey)
Item
s to contain only Item
s
that are associated with the given EdgeKey
.
items
- List of Items to filteritemKeys
- List of EdgeKey
s corresponding
to the edge keys for the Item
s in items
.filterEdgeKey
- the EdgeKey
to use as a filter.
filterEdgeKey
s.protected static final boolean hasTrueFalseBranches(java.util.Set edgeKeys)
EdgeKey
s Edge_KEY_TRUE
and
Edge_KEY_FALSE
.
edgeKeys
- the Set
of EdgeKey
s of the
successor edges of a given node.
edgeKeys
contains both
Edge_KEY_TRUE
and
Edge_KEY_FALSE
protected static java.util.Map constructItemsFromCondition(Expr booleanCond, DataFlow.Item startingItem, java.util.Set succEdgeKeys, DataFlow.ConditionNavigator navigator)
Item
s for the
FlowGraph.EDGE_KEY_TRUE
and
FlowGraph.EDGE_KEY_FALSE
edges from a boolean condition.
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 Item
s from the
boolean condition.
Map
containing mappings for all entries in
succEdgeKeys
.
FlowGraph.EDGE_KEY_TRUE
and
FlowGraph.EDGE_KEY_FALSE
map to Item
s calculated for them using
navigator, and all other objects in
succEdgeKeys
are mapped to
startingItem
.protected void dumpFlowGraph(FlowGraph graph, Term root)
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |