baloghadamsoftware created this revision.
This patch adds explicit evaluation of the following functions: std::find,
std::find_end, std::find_first_of, std::find_if, std::find_if_not,
std::lower_bound, std::upper_bound, std::search and std::search_n. On the one
hand this is an optimization since the result of each of these functions is an
iterators either inside the range or the iterator past the end of the range.
This evaluation does exactly this. (We cannot simulate "inside the range" just
an iterator bound to the same container with a new offset). On the other hand
this evaluation is needed for random access operators since some STL
implementations do some optimization where the length of the range is used
instead of iterating until the end. This is hard to track in a checker so we
must do this evaluation to prevent false positives and catch more real bugs.
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
@@ -79,6 +79,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
@@ -715,10 +715,31 @@
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
@@ -135,7 +135,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;
@@ -180,14 +185,26 @@
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 reportOutOfRangeBug(const StringRef &Message, const SVal &Val,
CheckerContext &C, ExplodedNode *ErrNode) const;
void reportMismatchedBug(const StringRef &Message, const SVal &Val,
CheckerContext &C, ExplodedNode *ErrNode) const;
void reportInvalidatedBug(const StringRef &Message, const SVal &Val,
CheckerContext &C, ExplodedNode *ErrNode) const;
+ void initIdentifiers(ASTContext &Ctx) const;
+
public:
IteratorChecker();
@@ -214,6 +231,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
@@ -802,6 +820,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 {
@@ -1420,6 +1476,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 {
@@ -1444,6 +1612,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
