Overview | Package | Class | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## 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.

Overview | Package | Class | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD