baloghadamsoftware updated this revision to Diff 144999.
baloghadamsoftware added a comment.
Rebased.
https://reviews.llvm.org/D32905
Files:
lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
test/Analysis/Inputs/system-header-simulator-cxx.h
test/Analysis/iterator-range.cpp
Index: test/Analysis/iterator-range.cpp
===================================================================
--- test/Analysis/iterator-range.cpp
+++ test/Analysis/iterator-range.cpp
@@ -97,6 +97,125 @@
*i2; // expected-warning{{Iterator accessed outside of its range}}
}
+void good_find(std::vector<int> &V, int e) {
+ auto first = std::find(V.begin(), V.end(), e);
+ if (V.end() != first)
+ *first; // no-warning
+}
+
+void bad_find(std::vector<int> &V, int e) {
+ auto first = std::find(V.begin(), V.end(), e);
+ *first; // expected-warning{{Iterator accessed outside of its range}}
+}
+
+void good_find_end(std::vector<int> &V, std::vector<int> &seq) {
+ auto last = std::find_end(V.begin(), V.end(), seq.begin(), seq.end());
+ if (V.end() != last)
+ *last; // no-warning
+}
+
+void bad_find_end(std::vector<int> &V, std::vector<int> &seq) {
+ auto last = std::find_end(V.begin(), V.end(), seq.begin(), seq.end());
+ *last; // expected-warning{{Iterator accessed outside of its range}}
+}
+
+void good_find_first_of(std::vector<int> &V, std::vector<int> &seq) {
+ auto first =
+ std::find_first_of(V.begin(), V.end(), seq.begin(), seq.end());
+ if (V.end() != first)
+ *first; // no-warning
+}
+
+void bad_find_first_of(std::vector<int> &V, std::vector<int> &seq) {
+ auto first = std::find_end(V.begin(), V.end(), seq.begin(), seq.end());
+ *first; // expected-warning{{Iterator accessed outside of its range}}
+}
+
+bool odd(int i) { return i % 2; }
+
+void good_find_if(std::vector<int> &V) {
+ auto first = std::find_if(V.begin(), V.end(), odd);
+ if (V.end() != first)
+ *first; // no-warning
+}
+
+void bad_find_if(std::vector<int> &V, int e) {
+ auto first = std::find_if(V.begin(), V.end(), odd);
+ *first; // expected-warning{{Iterator accessed outside of its range}}
+}
+
+void good_find_if_not(std::vector<int> &V) {
+ auto first = std::find_if_not(V.begin(), V.end(), odd);
+ if (V.end() != first)
+ *first; // no-warning
+}
+
+void bad_find_if_not(std::vector<int> &V, int e) {
+ auto first = std::find_if_not(V.begin(), V.end(), odd);
+ *first; // expected-warning{{Iterator accessed outside of its range}}
+}
+
+void good_lower_bound(std::vector<int> &V, int e) {
+ auto first = std::lower_bound(V.begin(), V.end(), e);
+ if (V.end() != first)
+ *first; // no-warning
+}
+
+void bad_lower_bound(std::vector<int> &V, int e) {
+ auto first = std::lower_bound(V.begin(), V.end(), e);
+ *first; // expected-warning{{Iterator accessed outside of its range}}
+}
+
+void good_upper_bound(std::vector<int> &V, int e) {
+ auto last = std::lower_bound(V.begin(), V.end(), e);
+ if (V.end() != last)
+ *last; // no-warning
+}
+
+void bad_upper_bound(std::vector<int> &V, int e) {
+ auto last = std::lower_bound(V.begin(), V.end(), e);
+ *last; // expected-warning{{Iterator accessed outside of its range}}
+}
+
+void good_search(std::vector<int> &V, std::vector<int> &seq) {
+ auto first = std::search(V.begin(), V.end(), seq.begin(), seq.end());
+ if (V.end() != first)
+ *first; // no-warning
+}
+
+void bad_search(std::vector<int> &V, std::vector<int> &seq) {
+ auto first = std::search(V.begin(), V.end(), seq.begin(), seq.end());
+ *first; // expected-warning{{Iterator accessed outside of its range}}
+}
+
+void good_search_n(std::vector<int> &V, std::vector<int> &seq) {
+ auto nth = std::search_n(V.begin(), V.end(), seq.begin(), seq.end());
+ if (V.end() != nth)
+ *nth; // no-warning
+}
+
+void bad_search_n(std::vector<int> &V, std::vector<int> &seq) {
+ auto nth = std::search_n(V.begin(), V.end(), seq.begin(), seq.end());
+ *nth; // expected-warning{{Iterator accessed outside of its range}}
+}
+
+template <class InputIterator, class T>
+InputIterator nonStdFind(InputIterator first, InputIterator last,
+ const T &val) {
+ for (auto i = first; i != last; ++i) {
+ if (*i == val) {
+ return i;
+ }
+ }
+ return last;
+}
+
+void good_non_std_find(std::vector<int> &V, int e) {
+ auto first = nonStdFind(V.begin(), V.end(), e);
+ if (V.end() != first)
+ *first; // no-warning
+}
+
void tricky(std::vector<int> &V, int e) {
const auto first = V.begin();
const auto comp1 = (first != V.end()), comp2 = (first == V.end());
Index: test/Analysis/Inputs/system-header-simulator-cxx.h
===================================================================
--- test/Analysis/Inputs/system-header-simulator-cxx.h
+++ test/Analysis/Inputs/system-header-simulator-cxx.h
@@ -714,12 +714,32 @@
template <class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T &val);
-
+ template <class ForwardIterator1, class ForwardIterator2>
+ ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1,
+ ForwardIterator2 first2, ForwardIterator2 last2);
template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 find_first_of(ForwardIterator1 first1,
ForwardIterator1 last1,
ForwardIterator2 first2,
ForwardIterator2 last2);
+ template <class InputIterator, class UnaryPredicate>
+ InputIterator find_if(InputIterator first, InputIterator last,
+ UnaryPredicate pred);
+ template <class InputIterator, class UnaryPredicate>
+ InputIterator find_if_not(InputIterator first, InputIterator last,
+ UnaryPredicate pred);
+ template <class InputIterator, class T>
+ InputIterator lower_bound(InputIterator first, InputIterator last,
+ const T &val);
+ template <class InputIterator, class T>
+ InputIterator upper_bound(InputIterator first, InputIterator last,
+ const T &val);
+ template <class ForwardIterator1, class ForwardIterator2>
+ ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1,
+ ForwardIterator2 first2, ForwardIterator2 last2);
+ template <class ForwardIterator1, class ForwardIterator2>
+ ForwardIterator1 search_n(ForwardIterator1 first1, ForwardIterator1 last1,
+ ForwardIterator2 first2, ForwardIterator2 last2);
template <class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator first, InputIterator last,
Index: lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
===================================================================
--- lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
+++ lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
@@ -201,7 +201,12 @@
check::PreStmt<CXXOperatorCallExpr>,
check::PostStmt<MaterializeTemporaryExpr>, check::Bind,
check::LiveSymbols, check::DeadSymbols,
- eval::Assume> {
+ eval::Assume, eval::Call> {
+ mutable IdentifierInfo *II_find = nullptr, *II_find_end = nullptr,
+ *II_find_first_of = nullptr, *II_find_if = nullptr,
+ *II_find_if_not = nullptr, *II_lower_bound = nullptr,
+ *II_upper_bound = nullptr, *II_search = nullptr,
+ *II_search_n = nullptr;
std::unique_ptr<BugType> OutOfRangeBugType;
std::unique_ptr<BugType> MismatchedBugType;
@@ -246,6 +251,17 @@
const MemRegion *Cont) const;
void verifyMatch(CheckerContext &C, const SVal &Iter1,
const SVal &Iter2) const;
+ bool evalFind(CheckerContext &C, const CallExpr *CE) const;
+ bool evalFindEnd(CheckerContext &C, const CallExpr *CE) const;
+ bool evalFindFirstOf(CheckerContext &C, const CallExpr *CE) const;
+ bool evalFindIf(CheckerContext &C, const CallExpr *CE) const;
+ bool evalFindIfNot(CheckerContext &C, const CallExpr *CE) const;
+ bool evalLowerBound(CheckerContext &C, const CallExpr *CE) const;
+ bool evalUpperBound(CheckerContext &C, const CallExpr *CE) const;
+ bool evalSearch(CheckerContext &C, const CallExpr *CE) const;
+ bool evalSearchN(CheckerContext &C, const CallExpr *CE) const;
+ void Find(CheckerContext &C, const CallExpr *CE) const;
+ void initIdentifiers(ASTContext &Ctx) const;
void reportOutOfRangeBug(const StringRef &Message, const SVal &Val,
CheckerContext &C, ExplodedNode *ErrNode) const;
@@ -284,6 +300,7 @@
void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
ProgramStateRef evalAssume(ProgramStateRef State, SVal Cond,
bool Assumption) const;
+ bool evalCall(const CallExpr *CE, CheckerContext &C) const;
};
} // namespace
@@ -296,6 +313,10 @@
REGISTER_MAP_WITH_PROGRAMSTATE(IteratorComparisonMap, const SymExpr *,
IteratorComparison)
+#define INIT_ID(Id) \
+ if (!II_##Id) \
+ II_##Id = &Ctx.Idents.get(#Id)
+
namespace {
bool isIteratorType(const QualType &Type);
@@ -882,6 +903,44 @@
(Comp->isEquality() == Assumption) != Negated);
}
+// FIXME: Evaluation of these STL calls should be moved to StdCLibraryFunctions
+// checker (see patch r284960) or another similar checker for C++ STL
+// functions (e.g. StdCXXLibraryFunctions or StdCppLibraryFunctions).
+bool IteratorChecker::evalCall(const CallExpr *CE, CheckerContext &C) const {
+ const FunctionDecl *FD = C.getCalleeDecl(CE);
+ if (!FD)
+ return false;
+
+ ASTContext &Ctx = C.getASTContext();
+ initIdentifiers(Ctx);
+
+ if (FD->getKind() == Decl::Function) {
+ if (FD->isInStdNamespace()) {
+ if (FD->getIdentifier() == II_find) {
+ return evalFind(C, CE);
+ } else if (FD->getIdentifier() == II_find_end) {
+ return evalFindEnd(C, CE);
+ } else if (FD->getIdentifier() == II_find_first_of) {
+ return evalFindFirstOf(C, CE);
+ } else if (FD->getIdentifier() == II_find_if) {
+ return evalFindIf(C, CE);
+ } else if (FD->getIdentifier() == II_find_if_not) {
+ return evalFindIfNot(C, CE);
+ } else if (FD->getIdentifier() == II_upper_bound) {
+ return evalUpperBound(C, CE);
+ } else if (FD->getIdentifier() == II_lower_bound) {
+ return evalLowerBound(C, CE);
+ } else if (FD->getIdentifier() == II_search) {
+ return evalSearch(C, CE);
+ } else if (FD->getIdentifier() == II_search_n) {
+ return evalSearchN(C, CE);
+ }
+ }
+ }
+
+ return false;
+}
+
void IteratorChecker::handleComparison(CheckerContext &C, const SVal &RetVal,
const SVal &LVal, const SVal &RVal,
OverloadedOperatorKind Op) const {
@@ -1589,6 +1648,118 @@
C.addTransition(State);
}
+bool IteratorChecker::evalFind(CheckerContext &C, const CallExpr *CE) const {
+ if (CE->getNumArgs() == 3 && isIteratorType(CE->getArg(0)->getType()) &&
+ isIteratorType(CE->getArg(1)->getType())) {
+ Find(C, CE);
+ return true;
+ }
+ return false;
+}
+
+bool IteratorChecker::evalFindEnd(CheckerContext &C, const CallExpr *CE) const {
+ if ((CE->getNumArgs() == 4 || CE->getNumArgs() == 5) &&
+ isIteratorType(CE->getArg(0)->getType()) &&
+ isIteratorType(CE->getArg(1)->getType()) &&
+ isIteratorType(CE->getArg(2)->getType()) &&
+ isIteratorType(CE->getArg(3)->getType())) {
+ Find(C, CE);
+ return true;
+ }
+ return false;
+}
+
+bool IteratorChecker::evalFindFirstOf(CheckerContext &C,
+ const CallExpr *CE) const {
+ if ((CE->getNumArgs() == 4 || CE->getNumArgs() == 5) &&
+ isIteratorType(CE->getArg(0)->getType()) &&
+ isIteratorType(CE->getArg(1)->getType()) &&
+ isIteratorType(CE->getArg(2)->getType()) &&
+ isIteratorType(CE->getArg(3)->getType())) {
+ Find(C, CE);
+ return true;
+ }
+ return false;
+}
+
+bool IteratorChecker::evalFindIf(CheckerContext &C, const CallExpr *CE) const {
+ if (CE->getNumArgs() == 3 && isIteratorType(CE->getArg(0)->getType()) &&
+ isIteratorType(CE->getArg(1)->getType())) {
+ Find(C, CE);
+ return true;
+ }
+ return false;
+}
+
+bool IteratorChecker::evalFindIfNot(CheckerContext &C,
+ const CallExpr *CE) const {
+ if (CE->getNumArgs() == 3 && isIteratorType(CE->getArg(0)->getType()) &&
+ isIteratorType(CE->getArg(1)->getType())) {
+ Find(C, CE);
+ return true;
+ }
+ return false;
+}
+
+bool IteratorChecker::evalLowerBound(CheckerContext &C,
+ const CallExpr *CE) const {
+ if ((CE->getNumArgs() == 3 || CE->getNumArgs() == 4) &&
+ isIteratorType(CE->getArg(0)->getType()) &&
+ isIteratorType(CE->getArg(1)->getType())) {
+ Find(C, CE);
+ return true;
+ }
+ return false;
+}
+
+bool IteratorChecker::evalUpperBound(CheckerContext &C,
+ const CallExpr *CE) const {
+ if ((CE->getNumArgs() == 3 || CE->getNumArgs() == 4) &&
+ isIteratorType(CE->getArg(0)->getType()) &&
+ isIteratorType(CE->getArg(1)->getType())) {
+ Find(C, CE);
+ return true;
+ }
+ return false;
+}
+
+bool IteratorChecker::evalSearch(CheckerContext &C, const CallExpr *CE) const {
+ if ((CE->getNumArgs() == 4 || CE->getNumArgs() == 5) &&
+ isIteratorType(CE->getArg(0)->getType()) &&
+ isIteratorType(CE->getArg(1)->getType()) &&
+ isIteratorType(CE->getArg(2)->getType()) &&
+ isIteratorType(CE->getArg(3)->getType())) {
+ Find(C, CE);
+ return true;
+ }
+ return false;
+}
+
+bool IteratorChecker::evalSearchN(CheckerContext &C, const CallExpr *CE) const {
+ if ((CE->getNumArgs() == 4 || CE->getNumArgs() == 5) &&
+ isIteratorType(CE->getArg(0)->getType()) &&
+ isIteratorType(CE->getArg(1)->getType())) {
+ Find(C, CE);
+ return true;
+ }
+ return false;
+}
+
+void IteratorChecker::Find(CheckerContext &C, const CallExpr *CE) const {
+ auto state = C.getState();
+ auto &svalBuilder = C.getSValBuilder();
+ const auto *LCtx = C.getLocationContext();
+
+ auto RetVal = svalBuilder.conjureSymbolVal(nullptr, CE, LCtx, C.blockCount());
+ auto SecondParam = state->getSVal(CE->getArg(1), LCtx);
+
+ auto stateFound = state->BindExpr(CE, LCtx, RetVal);
+ auto stateNotFound = state->BindExpr(CE, LCtx, SecondParam);
+
+ C.addTransition(stateFound);
+ C.addTransition(stateNotFound);
+}
+
void IteratorChecker::reportOutOfRangeBug(const StringRef &Message,
const SVal &Val, CheckerContext &C,
ExplodedNode *ErrNode) const {
@@ -1625,6 +1796,18 @@
C.emitReport(std::move(R));
}
+void IteratorChecker::initIdentifiers(ASTContext &Ctx) const {
+ INIT_ID(find);
+ INIT_ID(find_end);
+ INIT_ID(find_first_of);
+ INIT_ID(find_if);
+ INIT_ID(find_if_not);
+ INIT_ID(lower_bound);
+ INIT_ID(upper_bound);
+ INIT_ID(search);
+ INIT_ID(search_n);
+}
+
namespace {
bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
