public class LowerBoundTransfer extends IndexAbstractTransfer
Also implements the logic for binary operations: +, -, *, /, and %.
>, <, ≥, ≤, ==, and != nodes are represented as combinations of > and ≥ (e.g. == is ≥ in both directions in the then branch), and implement refinements based on these decompositions.
Refinement/transfer rules for conditionals:
There are two "primitives":
x > y, which implies things about x based on y's type:
y has type: implies x has type:
gte-1 nn
nn pos
pos pos
and x ≥ y:
y has type: implies x has type:
gte-1 gte-1
nn nn
pos pos
These two "building blocks" can be combined to make all
other conditional expressions:
EXPR THEN ELSE
x > y x > y y ≥ x
x ≥ y x ≥ y y > x
x < y y > x x ≥ y
x ≤ y y ≥ x x > y
Or, more formally:
EXPR THEN ELSE
x > y x_refined = GLB(x_orig, promote(y)) y_refined = GLB(y_orig, x)
x ≥ y x_refined = GLB(x_orig, y) y_refined = GLB(y_orig, promote(x))
x < y y_refined = GLB(y_orig, promote(x)) x_refined = GLB(x_orig, y)
x ≤ y y_refined = GLB(y_orig, x) x_refined = GLB(x_orig, promote(y))
where GLB is the greatest lower bound and promote is the increment
function on types (or, equivalently, the function specified by the "x
> y" information above).
There's also ==, which is a special case. Only the THEN
branch is refined:
EXPR THEN ELSE
x == y x ≥ y && y ≥ x nothing known
or, more formally:
EXPR THEN ELSE
x == y x_refined = GLB(x_orig, y_orig) nothing known
y_refined = GLB(x_orig, y_orig)
finally, not equal:
EXPR THEN ELSE
x != y nothing known x ≥ y && y ≥ x
more formally:
EXPR THEN ELSE
x != y nothing known x_refined = GLB(x_orig, y_orig)
y_refined = GLB(x_orig, y_orig)
Dividing these rules up by cases, this class implements:
x != -1 and x is GTEN1 implies x is
non-negative). Maybe two rules?
a <= b and a != b, then b is pos.
| Modifier and Type | Field and Description |
|---|---|
javax.lang.model.element.AnnotationMirror |
GTEN1
The canonical
GTENegativeOne annotation. |
javax.lang.model.element.AnnotationMirror |
NN
The canonical
NonNegative annotation. |
javax.lang.model.element.AnnotationMirror |
POS
The canonical
Positive annotation. |
javax.lang.model.element.AnnotationMirror |
UNKNOWN
The canonical
LowerBoundUnknown annotation. |
| Constructor and Description |
|---|
LowerBoundTransfer(org.checkerframework.framework.flow.CFAnalysis analysis) |
| Modifier and Type | Method and Description |
|---|---|
javax.lang.model.element.AnnotationMirror |
getAnnotationForRemainder(org.checkerframework.dataflow.cfg.node.IntegerRemainderNode node,
org.checkerframework.dataflow.analysis.TransferInput<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore> p)
getAnnotationForRemainder handles these cases:
|
protected void |
refineGT(org.checkerframework.dataflow.cfg.node.Node left,
javax.lang.model.element.AnnotationMirror leftAnno,
org.checkerframework.dataflow.cfg.node.Node right,
javax.lang.model.element.AnnotationMirror rightAnno,
org.checkerframework.framework.flow.CFStore store,
org.checkerframework.dataflow.analysis.TransferInput<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore> in)
The implementation of the algorithm for refining a > test.
|
protected void |
refineGTE(org.checkerframework.dataflow.cfg.node.Node left,
javax.lang.model.element.AnnotationMirror leftAnno,
org.checkerframework.dataflow.cfg.node.Node right,
javax.lang.model.element.AnnotationMirror rightAnno,
org.checkerframework.framework.flow.CFStore store,
org.checkerframework.dataflow.analysis.TransferInput<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore> in)
Refines left to exactly the level of right, since in the worst case they're equal.
|
protected org.checkerframework.dataflow.analysis.TransferResult<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore> |
strengthenAnnotationOfEqualTo(org.checkerframework.dataflow.analysis.TransferResult<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore> result,
org.checkerframework.dataflow.cfg.node.Node firstNode,
org.checkerframework.dataflow.cfg.node.Node secondNode,
org.checkerframework.framework.flow.CFValue firstValue,
org.checkerframework.framework.flow.CFValue secondValue,
boolean notEqualTo)
Implements the transfer rules for both equal nodes and not-equals nodes (i.e.
|
org.checkerframework.dataflow.analysis.TransferResult<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore> |
visitBitwiseAnd(org.checkerframework.dataflow.cfg.node.BitwiseAndNode n,
org.checkerframework.dataflow.analysis.TransferInput<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore> p) |
org.checkerframework.dataflow.analysis.TransferResult<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore> |
visitIntegerDivision(org.checkerframework.dataflow.cfg.node.IntegerDivisionNode n,
org.checkerframework.dataflow.analysis.TransferInput<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore> p) |
org.checkerframework.dataflow.analysis.TransferResult<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore> |
visitIntegerRemainder(org.checkerframework.dataflow.cfg.node.IntegerRemainderNode n,
org.checkerframework.dataflow.analysis.TransferInput<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore> p) |
org.checkerframework.dataflow.analysis.TransferResult<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore> |
visitNumericalAddition(org.checkerframework.dataflow.cfg.node.NumericalAdditionNode n,
org.checkerframework.dataflow.analysis.TransferInput<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore> p) |
org.checkerframework.dataflow.analysis.TransferResult<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore> |
visitNumericalMultiplication(org.checkerframework.dataflow.cfg.node.NumericalMultiplicationNode n,
org.checkerframework.dataflow.analysis.TransferInput<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore> p) |
org.checkerframework.dataflow.analysis.TransferResult<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore> |
visitNumericalSubtraction(org.checkerframework.dataflow.cfg.node.NumericalSubtractionNode n,
org.checkerframework.dataflow.analysis.TransferInput<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore> p) |
org.checkerframework.dataflow.analysis.TransferResult<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore> |
visitSignedRightShift(org.checkerframework.dataflow.cfg.node.SignedRightShiftNode n,
org.checkerframework.dataflow.analysis.TransferInput<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore> p) |
org.checkerframework.dataflow.analysis.TransferResult<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore> |
visitUnsignedRightShift(org.checkerframework.dataflow.cfg.node.UnsignedRightShiftNode n,
org.checkerframework.dataflow.analysis.TransferInput<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore> p) |
visitGreaterThan, visitGreaterThanOrEqual, visitLessThan, visitLessThanOrEqualaddInformationFromPreconditions, finishValue, finishValue, getValueFromFactory, getValueWithSameAnnotations, initialStore, isNotFullyInitializedReceiver, moreSpecificValue, processCommonAssignment, processConditionalPostconditions, processPostconditions, setFixedInitialStore, splitAssignments, usesSequentialSemantics, visitArrayAccess, visitAssignment, visitCase, visitClassName, visitConditionalNot, visitEqualTo, visitFieldAccess, visitLambdaResultExpression, visitLocalVariable, visitMethodInvocation, visitNarrowingConversion, visitNode, visitNotEqual, visitObjectCreation, visitReturn, visitStringConcatenateAssignment, visitStringConversion, visitTernaryExpression, visitThisLiteral, visitVariableDeclaration, visitWideningConversionvisitArrayCreation, visitArrayType, visitAssertionError, visitBitwiseComplement, visitBitwiseOr, visitBitwiseXor, visitBooleanLiteral, visitCharacterLiteral, visitConditionalAnd, visitConditionalOr, visitDoubleLiteral, visitExplicitThisLiteral, visitFloatingDivision, visitFloatingRemainder, visitFloatLiteral, visitImplicitThisLiteral, visitInstanceOf, visitIntegerLiteral, visitLeftShift, visitLongLiteral, visitMarker, visitMemberReference, visitMethodAccess, visitNullChk, visitNullLiteral, visitNumericalMinus, visitNumericalPlus, visitPackageName, visitParameterizedType, visitPrimitiveType, visitShortLiteral, visitStringConcatenate, visitStringLiteral, visitSuper, visitSynchronized, visitThrow, visitTypeCast, visitValueLiteralclone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, waitvisitArrayCreation, visitArrayType, visitAssertionError, visitBitwiseComplement, visitBitwiseOr, visitBitwiseXor, visitBooleanLiteral, visitCharacterLiteral, visitConditionalAnd, visitConditionalOr, visitDoubleLiteral, visitExplicitThisLiteral, visitFloatingDivision, visitFloatingRemainder, visitFloatLiteral, visitImplicitThisLiteral, visitInstanceOf, visitIntegerLiteral, visitLeftShift, visitLongLiteral, visitMarker, visitMemberReference, visitMethodAccess, visitNullChk, visitNullLiteral, visitNumericalMinus, visitNumericalPlus, visitPackageName, visitParameterizedType, visitPrimitiveType, visitShortLiteral, visitStringConcatenate, visitStringLiteral, visitSuper, visitSynchronized, visitThrow, visitTypeCastpublic final javax.lang.model.element.AnnotationMirror GTEN1
GTENegativeOne annotation.public final javax.lang.model.element.AnnotationMirror NN
NonNegative annotation.public final javax.lang.model.element.AnnotationMirror POS
Positive annotation.public final javax.lang.model.element.AnnotationMirror UNKNOWN
LowerBoundUnknown annotation.public LowerBoundTransfer(org.checkerframework.framework.flow.CFAnalysis analysis)
protected org.checkerframework.dataflow.analysis.TransferResult<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore> strengthenAnnotationOfEqualTo(org.checkerframework.dataflow.analysis.TransferResult<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore> result,
org.checkerframework.dataflow.cfg.node.Node firstNode,
org.checkerframework.dataflow.cfg.node.Node secondNode,
org.checkerframework.framework.flow.CFValue firstValue,
org.checkerframework.framework.flow.CFValue secondValue,
boolean notEqualTo)
strengthenAnnotationOfEqualTo in class org.checkerframework.framework.flow.CFAbstractTransfer<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore,org.checkerframework.framework.flow.CFTransfer>protected void refineGT(org.checkerframework.dataflow.cfg.node.Node left,
javax.lang.model.element.AnnotationMirror leftAnno,
org.checkerframework.dataflow.cfg.node.Node right,
javax.lang.model.element.AnnotationMirror rightAnno,
org.checkerframework.framework.flow.CFStore store,
org.checkerframework.dataflow.analysis.TransferInput<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore> in)
This implements parts of cases 1, 2, 3, and 4 using the decomposition strategy described in the Javadoc of this class.
refineGT in class IndexAbstractTransferprotected void refineGTE(org.checkerframework.dataflow.cfg.node.Node left,
javax.lang.model.element.AnnotationMirror leftAnno,
org.checkerframework.dataflow.cfg.node.Node right,
javax.lang.model.element.AnnotationMirror rightAnno,
org.checkerframework.framework.flow.CFStore store,
org.checkerframework.dataflow.analysis.TransferInput<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore> in)
This implements parts of cases 1, 2, 3, and 4 using the decomposition strategy described in this class's Javadoc.
refineGTE in class IndexAbstractTransferpublic javax.lang.model.element.AnnotationMirror getAnnotationForRemainder(org.checkerframework.dataflow.cfg.node.IntegerRemainderNode node,
org.checkerframework.dataflow.analysis.TransferInput<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore> p)
27. * % 1/-1 → nn
28. pos/nn % * → nn
29. gten1 % * → gten1
* % * → lbu
public org.checkerframework.dataflow.analysis.TransferResult<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore> visitNumericalAddition(org.checkerframework.dataflow.cfg.node.NumericalAdditionNode n,
org.checkerframework.dataflow.analysis.TransferInput<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore> p)
visitNumericalAddition in interface org.checkerframework.dataflow.cfg.node.NodeVisitor<org.checkerframework.dataflow.analysis.TransferResult<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore>,org.checkerframework.dataflow.analysis.TransferInput<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore>>visitNumericalAddition in class org.checkerframework.dataflow.cfg.node.AbstractNodeVisitor<org.checkerframework.dataflow.analysis.TransferResult<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore>,org.checkerframework.dataflow.analysis.TransferInput<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore>>public org.checkerframework.dataflow.analysis.TransferResult<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore> visitNumericalSubtraction(org.checkerframework.dataflow.cfg.node.NumericalSubtractionNode n,
org.checkerframework.dataflow.analysis.TransferInput<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore> p)
visitNumericalSubtraction in interface org.checkerframework.dataflow.cfg.node.NodeVisitor<org.checkerframework.dataflow.analysis.TransferResult<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore>,org.checkerframework.dataflow.analysis.TransferInput<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore>>visitNumericalSubtraction in class org.checkerframework.dataflow.cfg.node.AbstractNodeVisitor<org.checkerframework.dataflow.analysis.TransferResult<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore>,org.checkerframework.dataflow.analysis.TransferInput<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore>>public org.checkerframework.dataflow.analysis.TransferResult<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore> visitNumericalMultiplication(org.checkerframework.dataflow.cfg.node.NumericalMultiplicationNode n,
org.checkerframework.dataflow.analysis.TransferInput<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore> p)
visitNumericalMultiplication in interface org.checkerframework.dataflow.cfg.node.NodeVisitor<org.checkerframework.dataflow.analysis.TransferResult<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore>,org.checkerframework.dataflow.analysis.TransferInput<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore>>visitNumericalMultiplication in class org.checkerframework.dataflow.cfg.node.AbstractNodeVisitor<org.checkerframework.dataflow.analysis.TransferResult<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore>,org.checkerframework.dataflow.analysis.TransferInput<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore>>public org.checkerframework.dataflow.analysis.TransferResult<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore> visitIntegerDivision(org.checkerframework.dataflow.cfg.node.IntegerDivisionNode n,
org.checkerframework.dataflow.analysis.TransferInput<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore> p)
visitIntegerDivision in interface org.checkerframework.dataflow.cfg.node.NodeVisitor<org.checkerframework.dataflow.analysis.TransferResult<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore>,org.checkerframework.dataflow.analysis.TransferInput<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore>>visitIntegerDivision in class org.checkerframework.dataflow.cfg.node.AbstractNodeVisitor<org.checkerframework.dataflow.analysis.TransferResult<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore>,org.checkerframework.dataflow.analysis.TransferInput<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore>>public org.checkerframework.dataflow.analysis.TransferResult<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore> visitIntegerRemainder(org.checkerframework.dataflow.cfg.node.IntegerRemainderNode n,
org.checkerframework.dataflow.analysis.TransferInput<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore> p)
visitIntegerRemainder in interface org.checkerframework.dataflow.cfg.node.NodeVisitor<org.checkerframework.dataflow.analysis.TransferResult<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore>,org.checkerframework.dataflow.analysis.TransferInput<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore>>visitIntegerRemainder in class org.checkerframework.dataflow.cfg.node.AbstractNodeVisitor<org.checkerframework.dataflow.analysis.TransferResult<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore>,org.checkerframework.dataflow.analysis.TransferInput<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore>>public org.checkerframework.dataflow.analysis.TransferResult<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore> visitSignedRightShift(org.checkerframework.dataflow.cfg.node.SignedRightShiftNode n,
org.checkerframework.dataflow.analysis.TransferInput<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore> p)
visitSignedRightShift in interface org.checkerframework.dataflow.cfg.node.NodeVisitor<org.checkerframework.dataflow.analysis.TransferResult<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore>,org.checkerframework.dataflow.analysis.TransferInput<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore>>visitSignedRightShift in class org.checkerframework.dataflow.cfg.node.AbstractNodeVisitor<org.checkerframework.dataflow.analysis.TransferResult<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore>,org.checkerframework.dataflow.analysis.TransferInput<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore>>public org.checkerframework.dataflow.analysis.TransferResult<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore> visitUnsignedRightShift(org.checkerframework.dataflow.cfg.node.UnsignedRightShiftNode n,
org.checkerframework.dataflow.analysis.TransferInput<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore> p)
visitUnsignedRightShift in interface org.checkerframework.dataflow.cfg.node.NodeVisitor<org.checkerframework.dataflow.analysis.TransferResult<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore>,org.checkerframework.dataflow.analysis.TransferInput<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore>>visitUnsignedRightShift in class org.checkerframework.dataflow.cfg.node.AbstractNodeVisitor<org.checkerframework.dataflow.analysis.TransferResult<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore>,org.checkerframework.dataflow.analysis.TransferInput<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore>>public org.checkerframework.dataflow.analysis.TransferResult<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore> visitBitwiseAnd(org.checkerframework.dataflow.cfg.node.BitwiseAndNode n,
org.checkerframework.dataflow.analysis.TransferInput<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore> p)
visitBitwiseAnd in interface org.checkerframework.dataflow.cfg.node.NodeVisitor<org.checkerframework.dataflow.analysis.TransferResult<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore>,org.checkerframework.dataflow.analysis.TransferInput<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore>>visitBitwiseAnd in class org.checkerframework.dataflow.cfg.node.AbstractNodeVisitor<org.checkerframework.dataflow.analysis.TransferResult<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore>,org.checkerframework.dataflow.analysis.TransferInput<org.checkerframework.framework.flow.CFValue,org.checkerframework.framework.flow.CFStore>>