jif.visit
Class IntegerBoundsChecker

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

All Implemented Interfaces:

java.lang.Cloneable, polyglot.util.Copy

public class IntegerBoundsChecker
extends polyglot.visit.DataFlow

This class finds integral bounds on expressions. It uses that information to determine whether it is impossible for certain exceptions to be thrown.

Nested Class Summary

protected static class	IntegerBoundsChecker.ArrayLengthBound
protected static class	IntegerBoundsChecker.Bound
protected static class	IntegerBoundsChecker.Bounds
protected static class	IntegerBoundsChecker.DataFlowItem The items that this dataflow analysis operates on is essetially a set of integer constraints.
static class	IntegerBoundsChecker.Interval A closed interval over the integers.
protected static class	IntegerBoundsChecker.LocalBound

Nested classes/interfaces inherited from class polyglot.visit.DataFlow

polyglot.visit.DataFlow.BoolItem, polyglot.visit.DataFlow.ConditionNavigator, polyglot.visit.DataFlow.FlowGraphSource, polyglot.visit.DataFlow.Item

Field Summary

protected static java.util.Set<polyglot.ast.Binary.Operator>

INTERESTING_BINARY_OPERATORS

Fields inherited from class polyglot.visit.DataFlow

dataflowOnEntry, flowCounter, flowgraphStack, forward

Fields inherited from class polyglot.visit.ErrorHandlingVisitor

error, job, nf, ts

Fields inherited from class polyglot.visit.HaltingVisitor

bypass, bypassParent

Constructor Summary

IntegerBoundsChecker(polyglot.frontend.Job job)

IntegerBoundsChecker(polyglot.frontend.Job job, polyglot.types.TypeSystem ts, polyglot.ast.NodeFactory nf)

Method Summary

protected void	addBounds(java.util.Map<polyglot.types.LocalInstance,IntegerBoundsChecker.Bounds> updates, polyglot.ast.Expr left, boolean strict, polyglot.ast.Expr right) Add bounds to updates given left < right or left <= right, depending on whether strict is set.
protected int	addBoundsAssign(java.util.Map<polyglot.types.LocalInstance,IntegerBoundsChecker.Bounds> updates, polyglot.types.LocalInstance li, polyglot.ast.Expr right, IntegerBoundsChecker.DataFlowItem df, IntegerBoundsChecker.Interval existingNumericBounds) Add the bounds for an assignment li = right.
void	check(polyglot.visit.FlowGraph graph, polyglot.ast.Term n, boolean entry, polyglot.visit.DataFlow.Item inItem, java.util.Map outItems) Record the bounds information.
protected polyglot.visit.DataFlow.Item	confluence(java.util.List items, polyglot.ast.Term node, boolean entry, polyglot.visit.FlowGraph graph) The confluence of a list of items.
protected polyglot.visit.DataFlow.Item	createInitialItem(polyglot.visit.FlowGraph graph, polyglot.ast.Term node, boolean entry) Create an initial Item for the dataflow analysis.
protected java.util.Set<polyglot.types.LocalInstance>	findArrayLengthBounds(polyglot.ast.Expr expr, boolean strict, IntegerBoundsChecker.DataFlowItem df) Finds the local instances that are arrays, and whose length is a (strict or non-strict) upper bound on the expression expr.
protected java.util.Set<polyglot.types.LocalInstance>	findArrayLengthBounds(polyglot.ast.Expr expr, IntegerBoundsChecker.Bound.Type type) Returns the set of LocalInstances of locals that are arrays, and whose lengths are (non-strict) lower or upper bounds on the expression
protected java.util.Set<polyglot.types.LocalInstance>	findArrayLengthBounds(polyglot.types.LocalInstance li, boolean strict, IntegerBoundsChecker.DataFlowItem df)
protected java.util.Set<polyglot.types.LocalInstance>	findArrayLengthBounds(polyglot.types.LocalInstance li, boolean strict, IntegerBoundsChecker.DataFlowItem df, java.util.Set<polyglot.types.LocalInstance> seen) Finds the local instances that are arrays, and whose length is a strict upper bound on the value of the local variable li.
protected java.util.Set<polyglot.types.LocalInstance>	findLocalInstanceBounds(polyglot.ast.Expr expr, IntegerBoundsChecker.Bound.Type type) Returns the set of LocalInstances that are (non-strict) lower or upper bounds on the expression
protected java.lang.Long	findNumericBound(polyglot.types.LocalInstance li, IntegerBoundsChecker.DataFlowItem df, IntegerBoundsChecker.Bound.Type type) Finds the tightest numeric bound possible for li.
protected java.lang.Long	findNumericBound(polyglot.types.LocalInstance li, IntegerBoundsChecker.DataFlowItem df, IntegerBoundsChecker.Bound.Type type, java.util.Set<polyglot.types.LocalInstance> seen) Finds the tightest numeric bound possible for li.
protected IntegerBoundsChecker.Interval	findNumericRange(polyglot.ast.Expr expr, IntegerBoundsChecker.DataFlowItem df) Finds the tightest numeric range for expr, given dataflow information available immediately before evaluation of this expression (but after any sub-expressions).
java.util.Map	flow(polyglot.visit.DataFlow.Item trueItem, polyglot.visit.DataFlow.Item falseItem, polyglot.visit.DataFlow.Item otherItem, polyglot.visit.FlowGraph graph, polyglot.ast.Term n, boolean entry, java.util.Set succEdgeKeys)
protected java.util.Map	flow(java.util.List inItems, java.util.List inItemKeys, polyglot.visit.FlowGraph graph, polyglot.ast.Term n, boolean entry, java.util.Set edgeKeys) We use boolean flows for this dataflow analysis, i.e., we want to track different information on the true and false branches.
protected IntegerBoundsChecker.Interval	getExprBounds(polyglot.ast.Expr e)
protected static java.lang.Long	max(java.lang.Long a, java.lang.Long b)
protected static java.lang.Long	min(java.lang.Long a, java.lang.Long b)
protected void	notifyAllNodes(polyglot.ast.Node n)
protected static boolean	nullableEquals(java.lang.Object o1, java.lang.Object o2) Checks two reference for object equality.
protected static int	nullableHashCode(java.lang.Object o) Gets the hash code for a given object, dealing with null pointers.
protected void	post(polyglot.visit.FlowGraph graph, polyglot.ast.Term root)
protected void	setExprBounds(polyglot.ast.Expr e, IntegerBoundsChecker.Interval bounds)

Methods inherited from class polyglot.visit.DataFlow

confluence, constructItemsFromCondition, createCFGBuilder, currentFlowGraph, dataflow, dataflow, dataflow, dumpFlowGraph, enterCall, filterItems, filterItemsExceptionSubclass, filterItemsNonError, filterItemsNonException, findSCCs, flow, flowBooleanConditions, flowToBooleanFlow, hasTrueFalseBranches, initGraph, initGraph, itemsToMap, itemToMap, leave, leaveCall, safeConfluence, safeConfluence, safeConfluence

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

INTERESTING_BINARY_OPERATORS

protected static final java.util.Set<polyglot.ast.Binary.Operator> INTERESTING_BINARY_OPERATORS

Constructor Detail

IntegerBoundsChecker

public IntegerBoundsChecker(polyglot.frontend.Job job)

IntegerBoundsChecker

public IntegerBoundsChecker(polyglot.frontend.Job job,
                            polyglot.types.TypeSystem ts,
                            polyglot.ast.NodeFactory nf)

Method Detail

createInitialItem

protected polyglot.visit.DataFlow.Item createInitialItem(polyglot.visit.FlowGraph graph,
                                                         polyglot.ast.Term node,
                                                         boolean entry)

Create an initial Item for the dataflow analysis. By default, the map of integer bounds is empty.

Specified by:

createInitialItem in class polyglot.visit.DataFlow

flow

protected java.util.Map flow(java.util.List inItems,
                             java.util.List inItemKeys,
                             polyglot.visit.FlowGraph graph,
                             polyglot.ast.Term n,
                             boolean entry,
                             java.util.Set edgeKeys)

We use boolean flows for this dataflow analysis, i.e., we want to track different information on the true and false branches.

Overrides:

flow in class polyglot.visit.DataFlow

flow

public java.util.Map flow(polyglot.visit.DataFlow.Item trueItem,
                          polyglot.visit.DataFlow.Item falseItem,
                          polyglot.visit.DataFlow.Item otherItem,
                          polyglot.visit.FlowGraph graph,
                          polyglot.ast.Term n,
                          boolean entry,
                          java.util.Set succEdgeKeys)

Overrides:

flow in class polyglot.visit.DataFlow

post

protected void post(polyglot.visit.FlowGraph graph,
                    polyglot.ast.Term root)
             throws polyglot.types.SemanticException

Overrides:

post in class polyglot.visit.DataFlow

Throws:

polyglot.types.SemanticException

check

public void check(polyglot.visit.FlowGraph graph,
                  polyglot.ast.Term n,
                  boolean entry,
                  polyglot.visit.DataFlow.Item inItem,
                  java.util.Map outItems)
           throws polyglot.types.SemanticException

Record the bounds information. We could be extensible here, and allow other uses of the info.

Specified by:

check in class polyglot.visit.DataFlow

Throws:

polyglot.types.SemanticException

notifyAllNodes

protected void notifyAllNodes(polyglot.ast.Node n)

confluence

protected polyglot.visit.DataFlow.Item confluence(java.util.List items,
                                                  polyglot.ast.Term node,
                                                  boolean entry,
                                                  polyglot.visit.FlowGraph graph)

The confluence of a list of items. Only facts that are true of all items should be retained.

Specified by:

confluence in class polyglot.visit.DataFlow

setExprBounds

protected void setExprBounds(polyglot.ast.Expr e,
                             IntegerBoundsChecker.Interval bounds)

getExprBounds

protected IntegerBoundsChecker.Interval getExprBounds(polyglot.ast.Expr e)

addBounds

protected void addBounds(java.util.Map<polyglot.types.LocalInstance,IntegerBoundsChecker.Bounds> updates,
                         polyglot.ast.Expr left,
                         boolean strict,
                         polyglot.ast.Expr right)

Add bounds to updates given left < right or left <= right, depending on whether strict is set.

addBoundsAssign

protected int addBoundsAssign(java.util.Map<polyglot.types.LocalInstance,IntegerBoundsChecker.Bounds> updates,
                              polyglot.types.LocalInstance li,
                              polyglot.ast.Expr right,
                              IntegerBoundsChecker.DataFlowItem df,
                              IntegerBoundsChecker.Interval existingNumericBounds)

Add the bounds for an assignment li = right. Returns an int indicating if the value of li may have increased or decreased as a result of the assignment. existingNumericBounds is the existing numeric bounds recorded for the assignment, and is used to detect if we may be increasing upper bound without end, or decreasing the lower bound without end.

findLocalInstanceBounds

protected java.util.Set<polyglot.types.LocalInstance> findLocalInstanceBounds(polyglot.ast.Expr expr,
                                                                              IntegerBoundsChecker.Bound.Type type)

Returns the set of LocalInstances that are (non-strict) lower or upper bounds on the expression

findArrayLengthBounds

protected java.util.Set<polyglot.types.LocalInstance> findArrayLengthBounds(polyglot.ast.Expr expr,
                                                                            IntegerBoundsChecker.Bound.Type type)

Returns the set of LocalInstances of locals that are arrays, and whose lengths are (non-strict) lower or upper bounds on the expression

findArrayLengthBounds

protected java.util.Set<polyglot.types.LocalInstance> findArrayLengthBounds(polyglot.ast.Expr expr,
                                                                            boolean strict,
                                                                            IntegerBoundsChecker.DataFlowItem df)

Finds the local instances that are arrays, and whose length is a (strict or non-strict) upper bound on the expression expr.

findArrayLengthBounds

protected java.util.Set<polyglot.types.LocalInstance> findArrayLengthBounds(polyglot.types.LocalInstance li,
                                                                            boolean strict,
                                                                            IntegerBoundsChecker.DataFlowItem df)

findArrayLengthBounds

protected java.util.Set<polyglot.types.LocalInstance> findArrayLengthBounds(polyglot.types.LocalInstance li,
                                                                            boolean strict,
                                                                            IntegerBoundsChecker.DataFlowItem df,
                                                                            java.util.Set<polyglot.types.LocalInstance> seen)

Finds the local instances that are arrays, and whose length is a strict upper bound on the value of the local variable li.

findNumericBound

protected java.lang.Long findNumericBound(polyglot.types.LocalInstance li,
                                          IntegerBoundsChecker.DataFlowItem df,
                                          IntegerBoundsChecker.Bound.Type type)

Finds the tightest numeric bound possible for li. Type can be lower/upper, strict/non-strict.

findNumericBound

protected java.lang.Long findNumericBound(polyglot.types.LocalInstance li,
                                          IntegerBoundsChecker.DataFlowItem df,
                                          IntegerBoundsChecker.Bound.Type type,
                                          java.util.Set<polyglot.types.LocalInstance> seen)

Finds the tightest numeric bound possible for li. Type can be lower/upper, strict/non-strict.

findNumericRange

protected IntegerBoundsChecker.Interval findNumericRange(polyglot.ast.Expr expr,
                                                         IntegerBoundsChecker.DataFlowItem df)

Finds the tightest numeric range for expr, given dataflow information available immediately before evaluation of this expression (but after any sub-expressions).

max

protected static java.lang.Long max(java.lang.Long a,
                                    java.lang.Long b)

min

protected static java.lang.Long min(java.lang.Long a,
                                    java.lang.Long b)

nullableEquals

protected static boolean nullableEquals(java.lang.Object o1,
                                        java.lang.Object o2)

Checks two reference for object equality. Deals with null pointers. Should really be a utility method somewhere...

nullableHashCode

protected static int nullableHashCode(java.lang.Object o)

Gets the hash code for a given object, dealing with null pointers.