jif.visit

## Class IntegerBoundsChecker

- java.lang.Object
- - polyglot.visit.NodeVisitor
  - - polyglot.visit.HaltingVisitor
    - - polyglot.visit.ErrorHandlingVisitor
      - - polyglot.visit.DataFlow<IntegerBoundsChecker.DataFlowItem>
        - - jif.visit.IntegerBoundsChecker

- All Implemented Interfaces:
    java.lang.Cloneable, polyglot.util.Copy<polyglot.visit.NodeVisitor>

      public class IntegerBoundsChecker
      extends polyglot.visit.DataFlow<IntegerBoundsChecker.DataFlowItem>

  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

    Nested Classes
    Modifier and Type | Class and Description
    --- | ---
    `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<FlowItem extends polyglot.visit.DataFlow.Item>, polyglot.visit.DataFlow.ConditionNavigator<FlowItem extends polyglot.visit.DataFlow.Item>, polyglot.visit.DataFlow.FlowGraphSource<FlowItem extends polyglot.visit.DataFlow.Item>, polyglot.visit.DataFlow.Frame<FlowItem extends polyglot.visit.DataFlow.Item>, polyglot.visit.DataFlow.Item`

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

      `polyglot.util.Copy.Util`

  - ### Field Summary

    Fields
    Modifier and Type | Field and Description
    --- | ---
    `protected static java.util.Set<polyglot.ast.Binary.Operator>` | `INTERESTING_BINARY_OPERATORS`

    - ### Fields inherited from class polyglot.visit.DataFlow

      `dataflowOnEntry, detectBackEdges, flowCounter, flowgraphStack, forward, postordering`

    - ### 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
    `IntegerBoundsChecker(polyglot.frontend.Job job)`
    `IntegerBoundsChecker(polyglot.frontend.Job job, polyglot.types.TypeSystem ts, polyglot.ast.NodeFactory nf)`

  - ### Method Summary

    All Methods Static Methods Instance Methods Concrete Methods
    Modifier and Type | Method and Description
    --- | ---
    `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<IntegerBoundsChecker.DataFlowItem> graph, polyglot.ast.Term n, boolean entry, IntegerBoundsChecker.DataFlowItem inItem, java.util.Map<polyglot.visit.FlowGraph.EdgeKey,IntegerBoundsChecker.DataFlowItem> outItems)` Record the bounds information.
    `protected IntegerBoundsChecker.DataFlowItem` | `confluence(java.util.List<IntegerBoundsChecker.DataFlowItem> items, polyglot.visit.FlowGraph.Peer<IntegerBoundsChecker.DataFlowItem> peer, polyglot.visit.FlowGraph<IntegerBoundsChecker.DataFlowItem> graph)` The confluence of a list of items.
    `protected IntegerBoundsChecker.DataFlowItem` | `createInitialItem(polyglot.visit.FlowGraph<IntegerBoundsChecker.DataFlowItem> 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<polyglot.visit.FlowGraph.EdgeKey,IntegerBoundsChecker.DataFlowItem>` | `flow(IntegerBoundsChecker.DataFlowItem trueItem, IntegerBoundsChecker.DataFlowItem falseItem, IntegerBoundsChecker.DataFlowItem otherItem, polyglot.visit.FlowGraph<IntegerBoundsChecker.DataFlowItem> graph, polyglot.visit.FlowGraph.Peer<IntegerBoundsChecker.DataFlowItem> peer)`
    `protected java.util.Map<polyglot.visit.FlowGraph.EdgeKey,IntegerBoundsChecker.DataFlowItem>` | `flow(java.util.List<IntegerBoundsChecker.DataFlowItem> inItems, java.util.List<polyglot.visit.FlowGraph.EdgeKey> inItemKeys, polyglot.visit.FlowGraph<IntegerBoundsChecker.DataFlowItem> graph, polyglot.visit.FlowGraph.Peer<IntegerBoundsChecker.DataFlowItem> peer)` 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<IntegerBoundsChecker.DataFlowItem> graph, polyglot.ast.Term root)`
    `protected void` | `setExprBounds(polyglot.ast.Expr e, IntegerBoundsChecker.Interval bounds)`

    - ### Methods inherited from class polyglot.visit.DataFlow

      `check, confluence, constructItemsFromCondition, createCFGBuilder, createFrame, createInitialItem, currentFlowGraph, dataflow, dataflow, dataflow, dumpFlowGraph, enterCall, filterItems, filterItemsExceptionSubclass, filterItemsNonError, filterItemsNonException, findSCCs, flow, flow, flow, flowBooleanConditions, flowToBooleanFlow, hasTrueFalseBranches, initGraph, initGraph, itemsToMap, itemToMap, lang, 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 IntegerBoundsChecker.DataFlowItem createInitialItem(polyglot.visit.FlowGraph<IntegerBoundsChecker.DataFlowItem> 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<IntegerBoundsChecker.DataFlowItem>`

    - #### flow

          protected java.util.Map<polyglot.visit.FlowGraph.EdgeKey,IntegerBoundsChecker.DataFlowItem> flow(java.util.List<IntegerBoundsChecker.DataFlowItem> inItems,
                                                                                                           java.util.List<polyglot.visit.FlowGraph.EdgeKey> inItemKeys,
                                                                                                           polyglot.visit.FlowGraph<IntegerBoundsChecker.DataFlowItem> graph,
                                                                                                           polyglot.visit.FlowGraph.Peer<IntegerBoundsChecker.DataFlowItem> peer)

      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<IntegerBoundsChecker.DataFlowItem>`

    - #### flow

          public java.util.Map<polyglot.visit.FlowGraph.EdgeKey,IntegerBoundsChecker.DataFlowItem> flow(IntegerBoundsChecker.DataFlowItem trueItem,
                                                                                                        IntegerBoundsChecker.DataFlowItem falseItem,
                                                                                                        IntegerBoundsChecker.DataFlowItem otherItem,
                                                                                                        polyglot.visit.FlowGraph<IntegerBoundsChecker.DataFlowItem> graph,
                                                                                                        polyglot.visit.FlowGraph.Peer<IntegerBoundsChecker.DataFlowItem> peer)

      Overrides:
        `flow` in class `polyglot.visit.DataFlow<IntegerBoundsChecker.DataFlowItem>`

    - #### post

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

      Overrides:
        `post` in class `polyglot.visit.DataFlow<IntegerBoundsChecker.DataFlowItem>`
      Throws:
        `polyglot.types.SemanticException`

    - #### check

          public void check(polyglot.visit.FlowGraph<IntegerBoundsChecker.DataFlowItem> graph,
                            polyglot.ast.Term n,
                            boolean entry,
                            IntegerBoundsChecker.DataFlowItem inItem,
                            java.util.Map<polyglot.visit.FlowGraph.EdgeKey,IntegerBoundsChecker.DataFlowItem> outItems)

      Record the bounds information. We could be extensible here, and allow other uses of the info.
      Specified by:
        `check` in class `polyglot.visit.DataFlow<IntegerBoundsChecker.DataFlowItem>`

    - #### notifyAllNodes

          protected void notifyAllNodes(polyglot.ast.Node n)

    - #### confluence

          protected IntegerBoundsChecker.DataFlowItem confluence(java.util.List<IntegerBoundsChecker.DataFlowItem> items,
                                                                 polyglot.visit.FlowGraph.Peer<IntegerBoundsChecker.DataFlowItem> peer,
                                                                 polyglot.visit.FlowGraph<IntegerBoundsChecker.DataFlowItem> 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<IntegerBoundsChecker.DataFlowItem>`

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