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 |
|---|---|
AnnotationMirror |
GTEN1
The canonical
GTENegativeOne annotation. |
AnnotationMirror |
NN
The canonical
NonNegative annotation. |
AnnotationMirror |
POS
The canonical
Positive annotation. |
AnnotationMirror |
UNKNOWN
The canonical
LowerBoundUnknown annotation. |
analysis, sequentialSemantics| Constructor and Description |
|---|
LowerBoundTransfer(CFAnalysis analysis) |
visitGreaterThan, visitGreaterThanOrEqual, visitLessThan, visitLessThanOrEqualcreateTransferResult, finishValue, finishValue, getNarrowedValue, getValueFromFactory, getValueWithSameAnnotations, getWidenedValue, initialStore, isNotFullyInitializedReceiver, moreSpecificValue, processCommonAssignment, processConditionalPostconditions, processPostconditions, recreateTransferResult, setFixedInitialStore, splitAssignments, usesSequentialSemantics, visitArrayAccess, visitAssignment, visitCase, visitClassName, visitConditionalNot, visitEqualTo, visitFieldAccess, visitInstanceOf, visitLambdaResultExpression, visitLocalVariable, visitMethodInvocation, visitNarrowingConversion, visitNode, visitNotEqual, visitObjectCreation, visitReturn, visitStringConcatenateAssignment, visitStringConversion, visitTernaryExpression, visitThis, visitVariableDeclaration, visitWideningConversionvisitArrayCreation, visitArrayType, visitAssertionError, visitBitwiseComplement, visitBitwiseOr, visitBitwiseXor, visitBooleanLiteral, visitCharacterLiteral, visitClassDeclaration, visitConditionalAnd, visitConditionalOr, visitDoubleLiteral, visitExplicitThis, visitFloatingDivision, visitFloatingRemainder, visitFloatLiteral, visitImplicitThis, 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, visitClassDeclaration, visitConditionalAnd, visitConditionalOr, visitDoubleLiteral, visitExplicitThis, visitFloatingDivision, visitFloatingRemainder, visitFloatLiteral, visitImplicitThis, visitIntegerLiteral, visitLeftShift, visitLongLiteral, visitMarker, visitMemberReference, visitMethodAccess, visitNullChk, visitNullLiteral, visitNumericalMinus, visitNumericalPlus, visitPackageName, visitParameterizedType, visitPrimitiveType, visitShortLiteral, visitStringConcatenate, visitStringLiteral, visitSuper, visitSynchronized, visitThrow, visitTypeCastpublic final AnnotationMirror GTEN1
GTENegativeOne annotation.public final AnnotationMirror NN
NonNegative annotation.public final AnnotationMirror POS
Positive annotation.public final AnnotationMirror UNKNOWN
LowerBoundUnknown annotation.public LowerBoundTransfer(CFAnalysis analysis)
protected TransferResult<CFValue,CFStore> strengthenAnnotationOfEqualTo(TransferResult<CFValue,CFStore> result, Node firstNode, Node secondNode, CFValue firstValue, CFValue secondValue, boolean notEqualTo)
strengthenAnnotationOfEqualTo in class CFAbstractTransfer<CFValue,CFStore,CFTransfer>result - the previous resultnotEqualTo - if true, indicates that the logic is flipped (i.e., the information is
added to the elseStore instead of the thenStore) for a not-equal
comparison.null.protected void refineGT(Node left, AnnotationMirror leftAnno, Node right, AnnotationMirror rightAnno, CFStore store, TransferInput<CFValue,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(Node left, AnnotationMirror leftAnno, Node right, AnnotationMirror rightAnno, CFStore store, TransferInput<CFValue,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 IndexAbstractTransferprotected void addInformationFromPreconditions(CFStore info, AnnotatedTypeFactory factory, UnderlyingAST.CFGMethod method, MethodTree methodTree, ExecutableElement methodElement)
addInformationFromPreconditions in class CFAbstractTransfer<CFValue,CFStore,CFTransfer>info - the initial store for the method bodyfactory - the type factorymethod - the AST for a method declarationmethodTree - the declaration of the method; is a field of methodAstmethodElement - the element for the methodpublic AnnotationMirror getAnnotationForRemainder(IntegerRemainderNode node, TransferInput<CFValue,CFStore> p)
27. * % 1/-1 → nn
28. pos/nn % * → nn
29. gten1 % * → gten1
* % * → lbu
public TransferResult<CFValue,CFStore> visitNumericalAddition(NumericalAdditionNode n, TransferInput<CFValue,CFStore> p)
visitNumericalAddition in interface NodeVisitor<TransferResult<CFValue,CFStore>,TransferInput<CFValue,CFStore>>visitNumericalAddition in class AbstractNodeVisitor<TransferResult<CFValue,CFStore>,TransferInput<CFValue,CFStore>>public TransferResult<CFValue,CFStore> visitNumericalSubtraction(NumericalSubtractionNode n, TransferInput<CFValue,CFStore> p)
visitNumericalSubtraction in interface NodeVisitor<TransferResult<CFValue,CFStore>,TransferInput<CFValue,CFStore>>visitNumericalSubtraction in class AbstractNodeVisitor<TransferResult<CFValue,CFStore>,TransferInput<CFValue,CFStore>>public TransferResult<CFValue,CFStore> visitNumericalMultiplication(NumericalMultiplicationNode n, TransferInput<CFValue,CFStore> p)
visitNumericalMultiplication in interface NodeVisitor<TransferResult<CFValue,CFStore>,TransferInput<CFValue,CFStore>>visitNumericalMultiplication in class AbstractNodeVisitor<TransferResult<CFValue,CFStore>,TransferInput<CFValue,CFStore>>public TransferResult<CFValue,CFStore> visitIntegerDivision(IntegerDivisionNode n, TransferInput<CFValue,CFStore> p)
visitIntegerDivision in interface NodeVisitor<TransferResult<CFValue,CFStore>,TransferInput<CFValue,CFStore>>visitIntegerDivision in class AbstractNodeVisitor<TransferResult<CFValue,CFStore>,TransferInput<CFValue,CFStore>>public TransferResult<CFValue,CFStore> visitIntegerRemainder(IntegerRemainderNode n, TransferInput<CFValue,CFStore> p)
visitIntegerRemainder in interface NodeVisitor<TransferResult<CFValue,CFStore>,TransferInput<CFValue,CFStore>>visitIntegerRemainder in class AbstractNodeVisitor<TransferResult<CFValue,CFStore>,TransferInput<CFValue,CFStore>>public TransferResult<CFValue,CFStore> visitSignedRightShift(SignedRightShiftNode n, TransferInput<CFValue,CFStore> p)
visitSignedRightShift in interface NodeVisitor<TransferResult<CFValue,CFStore>,TransferInput<CFValue,CFStore>>visitSignedRightShift in class AbstractNodeVisitor<TransferResult<CFValue,CFStore>,TransferInput<CFValue,CFStore>>public TransferResult<CFValue,CFStore> visitUnsignedRightShift(UnsignedRightShiftNode n, TransferInput<CFValue,CFStore> p)
visitUnsignedRightShift in interface NodeVisitor<TransferResult<CFValue,CFStore>,TransferInput<CFValue,CFStore>>visitUnsignedRightShift in class AbstractNodeVisitor<TransferResult<CFValue,CFStore>,TransferInput<CFValue,CFStore>>public TransferResult<CFValue,CFStore> visitBitwiseAnd(BitwiseAndNode n, TransferInput<CFValue,CFStore> p)
visitBitwiseAnd in interface NodeVisitor<TransferResult<CFValue,CFStore>,TransferInput<CFValue,CFStore>>visitBitwiseAnd in class AbstractNodeVisitor<TransferResult<CFValue,CFStore>,TransferInput<CFValue,CFStore>>