baloghadamsoftware created this revision.
baloghadamsoftware added reviewers: NoQ, Szelethus.
baloghadamsoftware added a project: clang.
Herald added subscribers: Charusso, gamesh411, donat.nagy, mikhail.ramalho,
a.sidorin, rnkovacs, szepet, xazax.hun, whisperity.
Modeling of the `size()` method is essential for more accurate reporting
past-the-end iterator access.
Repository:
rC Clang
https://reviews.llvm.org/D62724
Files:
lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
test/Analysis/iterator-range.cpp
Index: test/Analysis/iterator-range.cpp
===================================================================
--- test/Analysis/iterator-range.cpp
+++ test/Analysis/iterator-range.cpp
@@ -236,3 +236,19 @@
*i0; // no-warning
}
}
+
+void size0(const std::vector<int>& V) {
+ if (V.size() != 0)
+ return;
+
+ *V.begin(); // expected-warning{{Past-the-end iterator dereferenced}}
+}
+
+void size1(const std::vector<int>& V) {
+ if(V.size() != 1)
+ return;
+ *V.begin(); // no-warning
+ auto i = V.cbegin();
+ ++i;
+ *i; // expected-warning{{Past-the-end iterator dereferenced}}
+}
Index: lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
===================================================================
--- lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
+++ lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
@@ -182,6 +182,8 @@
void handleComparison(CheckerContext &C, const Expr *CE, const SVal &RetVal,
const SVal &LVal, const SVal &RVal,
OverloadedOperatorKind Op) const;
+ void handleSize(CheckerContext &C, const Expr *CE, const SVal &Cont,
+ const SVal &RetVal) const;
void processComparison(CheckerContext &C, ProgramStateRef State,
SymbolRef Sym1, SymbolRef Sym2, const SVal &RetVal,
OverloadedOperatorKind Op) const;
@@ -272,6 +274,7 @@
bool isIteratorType(const QualType &Type);
bool isIterator(const CXXRecordDecl *CRD);
+bool isContainerType(const QualType &Type);
bool isComparisonOperator(OverloadedOperatorKind OK);
bool isBeginCall(const FunctionDecl *Func);
bool isEndCall(const FunctionDecl *Func);
@@ -287,6 +290,7 @@
bool isEraseCall(const FunctionDecl *Func);
bool isEraseAfterCall(const FunctionDecl *Func);
bool isEmplaceCall(const FunctionDecl *Func);
+bool isSizeCall(const FunctionDecl *Func);
bool isAssignmentOperator(OverloadedOperatorKind OK);
bool isSimpleComparisonOperator(OverloadedOperatorKind OK);
bool isAccessOperator(OverloadedOperatorKind OK);
@@ -314,6 +318,8 @@
ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val);
ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym,
long Scale);
+const llvm::APSInt* calculateSize(ProgramStateRef State, SymbolRef Begin,
+ SymbolRef End);
ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State,
const MemRegion *Cont);
ProgramStateRef
@@ -691,6 +697,16 @@
if (!OrigExpr)
return;
+ if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
+ if (isContainerType(InstCall->getCXXThisExpr()->getType())) {
+ if (isSizeCall(Func)) {
+ handleSize(C, OrigExpr, InstCall->getCXXThisVal(),
+ Call.getReturnValue());
+ return;
+ }
+ }
+ }
+
if (!isIteratorType(Call.getResultType()))
return;
@@ -918,6 +934,68 @@
}
}
+void IteratorChecker::handleSize(CheckerContext &C, const Expr *CE,
+ const SVal &Cont, const SVal &RetVal) const {
+ const auto *ContReg = Cont.getAsRegion();
+ if (!ContReg)
+ return;
+
+ ContReg = ContReg->getMostDerivedObjectRegion();
+
+ auto State = C.getState();
+
+ State = createContainerBegin(State, ContReg, CE, C.getASTContext().LongTy,
+ C.getLocationContext(), C.blockCount());
+ auto BeginSym = getContainerBegin(State, ContReg);
+ State = createContainerEnd(State, ContReg, CE, C.getASTContext().LongTy,
+ C.getLocationContext(), C.blockCount());
+ auto EndSym = getContainerEnd(State, ContReg);
+ const llvm::APSInt *CalcSize = calculateSize(State, BeginSym, EndSym);
+
+ auto &SVB = C.getSValBuilder();
+ auto &BVF = State->getBasicVals();
+ const llvm::APSInt *RetSize = nullptr;
+ if (const auto *KnownSize = SVB.getKnownValue(State, RetVal)) {
+ RetSize = &BVF.Convert(C.getASTContext().LongTy, *KnownSize);
+ }
+
+ if (RetSize) {
+ // If the return value is a concrete integer, then try to adjust the size
+ // of the container (the difference between its `begin()` and `end()` to
+ // this size. Function `relateSymbols()` returns null if it contradits
+ // the current size.
+ const auto CalcEnd =
+ SVB.evalBinOp(State, BO_Add, nonloc::SymbolVal(EndSym),
+ nonloc::ConcreteInt(*RetSize), C.getASTContext().LongTy)
+ .getAsSymbol();
+ if (CalcEnd) {
+ State = relateSymbols(State, BeginSym, EndSym, true);
+ }
+ } else {
+ if (CalcSize) {
+ // If the current size is a concrete integer, bind this to the return
+ // value of the function instead of the current one.
+ auto CSize = nonloc::ConcreteInt(BVF.Convert(CE->getType(), *CalcSize));
+ State = State->BindExpr(CE, C.getLocationContext(), CSize);
+ } else {
+ // If neither the returned nor the current size is a concrete integer,
+ // replace the return value with the symbolic difference of the
+ // container's `begin()` and `end()` symbols.
+ auto Size = SVB.evalBinOp(State, BO_Sub, nonloc::SymbolVal(EndSym),
+ nonloc::SymbolVal(BeginSym),
+ C.getASTContext().LongTy);
+ if (Size.isUnknown())
+ return;
+
+ auto CastedSize = SVB.evalCast(Size, CE->getType(),
+ C.getASTContext().LongTy);
+ State = State->BindExpr(CE, C.getLocationContext(), CastedSize);
+ }
+ }
+
+ C.addTransition(State);
+}
+
void IteratorChecker::verifyDereference(CheckerContext &C,
const SVal &Val) const {
auto State = C.getState();
@@ -1622,6 +1700,7 @@
namespace {
+bool isContainer(const CXXRecordDecl *CRD);
bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
bool isGreater(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
bool isEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
@@ -1686,6 +1765,39 @@
HasPostIncrOp && HasDerefOp;
}
+bool isContainerType(const QualType &Type) {
+ if (isIteratorType(Type))
+ return false;
+
+ const auto *CRD = Type.getNonReferenceType()
+ ->getUnqualifiedDesugaredType()->getAsCXXRecordDecl();
+ return isContainer(CRD);
+}
+
+bool isContainer(const CXXRecordDecl *CRD) {
+ if (!CRD)
+ return false;
+
+ for (const auto *Decl : CRD->decls()) {
+ const auto *TD = dyn_cast<TypeDecl>(Decl);
+ if (!TD)
+ continue;
+
+ const auto *Type = TD->getTypeForDecl();
+ if (!Type)
+ continue;
+
+ const auto *CRD = Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl();
+ if(!CRD)
+ continue;
+
+ if (isIterator(CRD))
+ return true;
+ }
+
+ return false;
+}
+
bool isComparisonOperator(OverloadedOperatorKind OK) {
return OK == OO_EqualEqual || OK == OO_ExclaimEqual || OK == OO_Less ||
OK == OO_LessEqual || OK == OO_Greater || OK == OO_GreaterEqual;
@@ -1827,6 +1939,17 @@
return IdInfo->getName() == "erase_after";
}
+bool isSizeCall(const FunctionDecl *Func) {
+ const auto *IdInfo = Func->getIdentifier();
+ if (!IdInfo)
+ return false;
+ if (Func->getNumParams() > 0)
+ return false;
+ if (!Func->getReturnType()->isUnsignedIntegerType())
+ return false;
+ return IdInfo->getName() == "size";
+}
+
bool isAssignmentOperator(OverloadedOperatorKind OK) { return OK == OO_Equal; }
bool isSimpleComparisonOperator(OverloadedOperatorKind OK) {
@@ -2127,6 +2250,40 @@
return NewState;
}
+const llvm::APSInt* calculateSize(ProgramStateRef State, SymbolRef Begin,
+ SymbolRef End) {
+ if (!Begin || !End)
+ return nullptr;
+
+ auto &SVB = State->getStateManager().getSValBuilder();
+ auto &SymMgr = State->getSymbolManager();
+ auto Size = SVB.evalBinOp(State, BO_Sub, nonloc::SymbolVal(End),
+ nonloc::SymbolVal(Begin),
+ SymMgr.getType(End)).getAsSymbol();
+ if (!Size)
+ return nullptr;
+
+ llvm::APSInt Diff = llvm::APSInt::get(0);
+ if (const auto *SizeExpr = dyn_cast<SymIntExpr>(Size)) {
+ assert(BinaryOperator::isAdditiveOp(SizeExpr->getOpcode()) &&
+ "Symbolic positions must be additive expressions");
+ if (SizeExpr->getOpcode() == BO_Add) {
+ Diff = SizeExpr->getRHS();
+ } else {
+ Diff = -SizeExpr->getRHS();
+ }
+ Size = SizeExpr->getLHS();
+ }
+
+ auto &CM = State->getConstraintManager();
+ if (const auto *SizeInt = CM.getSymVal(State, Size)) {
+ auto &BVF = SymMgr.getBasicVals();
+ return &BVF.getValue(Diff + *SizeInt);
+ }
+
+ return nullptr;
+}
+
template <typename Condition, typename Process>
ProgramStateRef processIteratorPositions(ProgramStateRef State, Condition Cond,
Process Proc) {
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
