baloghadamsoftware created this revision.
baloghadamsoftware added a reviewer: dcoughlin.
baloghadamsoftware added subscribers: cfe-commits, xazax.hun, o.gyorgy.
Herald added subscribers: modocache, mgorny, beanz.
This checker checks for iterators dereferenced when they are equal to the end()
of their container. Return value of any end() method is tracked if its type has
the same properties as a typical iterator (can be incremented, dereferenced,
and its name ends with "iterator", "iter" or "it"). STL functions that search a
value or range are evaluated by the checker as an optimization.
https://reviews.llvm.org/D25660
Files:
include/clang/StaticAnalyzer/Checkers/Checkers.td
lib/StaticAnalyzer/Checkers/CMakeLists.txt
lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp
lib/StaticAnalyzer/Core/ExprEngine.cpp
test/Analysis/iterator-past-end.cpp
Index: test/Analysis/iterator-past-end.cpp
===================================================================
--- /dev/null
+++ test/Analysis/iterator-past-end.cpp
@@ -0,0 +1,240 @@
+// RUN: %clang_cc1 -std=c++11 -analyze -analyzer-checker=core,cplusplus,alpha.cplusplus.IteratorPastEnd %s -verify
+
+template <typename T, typename Ptr, typename Ref> struct __iterator {
+ typedef __iterator<T, T *, T &> iterator;
+ typedef __iterator<T, const T *, const T &> const_iterator;
+
+ __iterator(Ptr p) : ptr(p) {}
+ __iterator<T, Ptr, Ref> operator++() { return *this; }
+ __iterator<T, Ptr, Ref> operator++(int) { return *this; }
+ __iterator<T, Ptr, Ref> operator--() { return *this; }
+ __iterator<T, Ptr, Ref> operator--(int) { return *this; }
+ Ref operator*() const { return *ptr; }
+ Ptr operator->() const { return *ptr; }
+
+ bool operator==(const iterator &rhs) const { return ptr == rhs.ptr; }
+ bool operator==(const const_iterator &rhs) const { return ptr == rhs.ptr; }
+
+ bool operator!=(const iterator &rhs) const { return ptr != rhs.ptr; }
+ bool operator!=(const const_iterator &rhs) const { return ptr != rhs.ptr; }
+
+private:
+ Ptr ptr;
+};
+
+namespace std {
+
+template <typename T> struct vector {
+ typedef __iterator<T, T *, T &> iterator;
+ typedef __iterator<T, const T *, const T &> const_iterator;
+
+ iterator begin();
+ const_iterator begin() const;
+ iterator end();
+ const_iterator end() const;
+};
+
+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);
+}
+
+void simple_good(const std::vector<int> &v) {
+ auto i = v.end();
+ if (i != v.end())
+ *i; // no-warning
+}
+
+void simple_bad(const std::vector<int> &v) {
+ auto i = v.end();
+ *i; // expected-warning{{Iterator possibly accessed past its end}}
+}
+
+void copy(const std::vector<int> &v) {
+ auto i1 = v.end();
+ auto i2 = i1;
+ *i2; // expected-warning{{Iterator possibly accessed past its end}}
+}
+
+void decrease(const std::vector<int> &v) {
+ auto i = v.end();
+ --i;
+ *i; // no-warning
+}
+
+void copy_and_decrease1(const std::vector<int> &v) {
+ auto i1 = v.end();
+ auto i2 = i1;
+ --i1;
+ *i1; // no-warning
+}
+
+void copy_and_decrease2(const std::vector<int> &v) {
+ auto i1 = v.end();
+ auto i2 = i1;
+ --i1;
+ *i2; // expected-warning{{Iterator possibly accessed past its end}}
+}
+
+void copy_and_increase1(const std::vector<int> &v) {
+ auto i1 = v.begin();
+ auto i2 = i1;
+ ++i1;
+ if (i1 == v.end())
+ *i2; // no-warning
+}
+
+void copy_and_increase2(const std::vector<int> &v) {
+ auto i1 = v.begin();
+ auto i2 = i1;
+ ++i1;
+ if (i2 == v.end())
+ *i2; // expected-warning{{Iterator possibly accessed past its end}}
+}
+
+void good_find(std::vector<int> &vec, int e) {
+ auto first = std::find(vec.begin(), vec.end(), e);
+ if (vec.end() != first)
+ *first; // no-warning
+}
+
+void bad_find(std::vector<int> &vec, int e) {
+ auto first = std::find(vec.begin(), vec.end(), e);
+ *first; // expected-warning{{Iterator possibly accessed past its end}}
+}
+
+void good_find_end(std::vector<int> &vec, std::vector<int> &seq) {
+ auto last = std::find_end(vec.begin(), vec.end(), seq.begin(), seq.end());
+ if (vec.end() != last)
+ *last; // no-warning
+}
+
+void bad_find_end(std::vector<int> &vec, std::vector<int> &seq) {
+ auto last = std::find_end(vec.begin(), vec.end(), seq.begin(), seq.end());
+ *last; // expected-warning{{Iterator possibly accessed past its end}}
+}
+
+void good_find_first_of(std::vector<int> &vec, std::vector<int> &seq) {
+ auto first =
+ std::find_first_of(vec.begin(), vec.end(), seq.begin(), seq.end());
+ if (vec.end() != first)
+ *first; // no-warning
+}
+
+void bad_find_first_of(std::vector<int> &vec, std::vector<int> &seq) {
+ auto first = std::find_end(vec.begin(), vec.end(), seq.begin(), seq.end());
+ *first; // expected-warning{{Iterator possibly accessed past its end}}
+}
+
+bool odd(int i) { return i % 2; }
+
+void good_find_if(std::vector<int> &vec) {
+ auto first = std::find_if(vec.begin(), vec.end(), odd);
+ if (vec.end() != first)
+ *first; // no-warning
+}
+
+void bad_find_if(std::vector<int> &vec, int e) {
+ auto first = std::find_if(vec.begin(), vec.end(), odd);
+ *first; // expected-warning{{Iterator possibly accessed past its end}}
+}
+
+void good_find_if_not(std::vector<int> &vec) {
+ auto first = std::find_if_not(vec.begin(), vec.end(), odd);
+ if (vec.end() != first)
+ *first; // no-warning
+}
+
+void bad_find_if_not(std::vector<int> &vec, int e) {
+ auto first = std::find_if_not(vec.begin(), vec.end(), odd);
+ *first; // expected-warning{{Iterator possibly accessed past its end}}
+}
+
+void good_lower_bound(std::vector<int> &vec, int e) {
+ auto first = std::lower_bound(vec.begin(), vec.end(), e);
+ if (vec.end() != first)
+ *first; // no-warning
+}
+
+void bad_lower_bound(std::vector<int> &vec, int e) {
+ auto first = std::lower_bound(vec.begin(), vec.end(), e);
+ *first; // expected-warning{{Iterator possibly accessed past its end}}
+}
+
+void good_upper_bound(std::vector<int> &vec, int e) {
+ auto last = std::lower_bound(vec.begin(), vec.end(), e);
+ if (vec.end() != last)
+ *last; // no-warning
+}
+
+void bad_upper_bound(std::vector<int> &vec, int e) {
+ auto last = std::lower_bound(vec.begin(), vec.end(), e);
+ *last; // expected-warning{{Iterator possibly accessed past its end}}
+}
+
+void good_search(std::vector<int> &vec, std::vector<int> &seq) {
+ auto first = std::search(vec.begin(), vec.end(), seq.begin(), seq.end());
+ if (vec.end() != first)
+ *first; // no-warning
+}
+
+void bad_search(std::vector<int> &vec, std::vector<int> &seq) {
+ auto first = std::search(vec.begin(), vec.end(), seq.begin(), seq.end());
+ *first; // expected-warning{{Iterator possibly accessed past its end}}
+}
+
+void good_search_n(std::vector<int> &vec, std::vector<int> &seq) {
+ auto nth = std::search_n(vec.begin(), vec.end(), seq.begin(), seq.end());
+ if (vec.end() != nth)
+ *nth; // no-warning
+}
+
+void bad_search_n(std::vector<int> &vec, std::vector<int> &seq) {
+ auto nth = std::search_n(vec.begin(), vec.end(), seq.begin(), seq.end());
+ *nth; // expected-warning{{Iterator possibly accessed past its end}}
+}
+
+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> &vec, int e) {
+ auto first = nonStdFind(vec.begin(), vec.end(), e);
+ if (vec.end() != first)
+ *first; // no-warning
+}
+
+void bad_non_std_find(std::vector<int> &vec, int e) {
+ auto first = nonStdFind(vec.begin(), vec.end(), e);
+ *first; // expected-warning{{Iterator possibly accessed past its end}}
+}
Index: lib/StaticAnalyzer/Core/ExprEngine.cpp
===================================================================
--- lib/StaticAnalyzer/Core/ExprEngine.cpp
+++ lib/StaticAnalyzer/Core/ExprEngine.cpp
@@ -1224,7 +1224,14 @@
case Expr::MaterializeTemporaryExprClass: {
Bldr.takeNodes(Pred);
const MaterializeTemporaryExpr *MTE = cast<MaterializeTemporaryExpr>(S);
- CreateCXXTemporaryObject(MTE, Pred, Dst);
+ ExplodedNodeSet dstPrevisit;
+ getCheckerManager().runCheckersForPreStmt(dstPrevisit, Pred, MTE, *this);
+ ExplodedNodeSet dstExpr;
+ for (ExplodedNodeSet::iterator i = dstPrevisit.begin(),
+ e = dstPrevisit.end(); i != e ; ++i) {
+ CreateCXXTemporaryObject(MTE, *i, dstExpr);
+ }
+ getCheckerManager().runCheckersForPostStmt(Dst, dstExpr, MTE, *this);
Bldr.addNodes(Dst);
break;
}
Index: lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp
===================================================================
--- /dev/null
+++ lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp
@@ -0,0 +1,729 @@
+//===-- IteratorPastEndChecker.cpp --------------------------------*- C++ -*--//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Defines a checker for using iterators outside their range (past end). Usage
+// means here dereferencing, incrementing, decrementing etc.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ClangSACheckers.h"
+#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
+#include "clang/StaticAnalyzer/Core/Checker.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+
+#include <utility>
+
+using namespace clang;
+using namespace ento;
+
+namespace {
+struct IteratorPosition {
+private:
+ enum Kind { InRange, OutofRange } K;
+ IteratorPosition(Kind InK) : K(InK) {}
+
+public:
+ bool isInRange() const { return K == InRange; }
+ bool isOutofRange() const { return K == OutofRange; }
+
+ static IteratorPosition getInRange() { return IteratorPosition(InRange); }
+ static IteratorPosition getOutofRange() {
+ return IteratorPosition(OutofRange);
+ }
+
+ bool operator==(const IteratorPosition &X) const { return K == X.K; }
+ bool operator!=(const IteratorPosition &X) const { return K != X.K; }
+ void Profile(llvm::FoldingSetNodeID &ID) const { ID.AddInteger(K); }
+
+ friend llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
+ const IteratorPosition &Pos) {
+ OS << ((Pos.K == InRange) ? "In Range" : "Out of Range");
+ return OS;
+ }
+};
+
+class IteratorPastEndChecker
+ : public Checker<
+ check::PreStmt<CXXOperatorCallExpr>, check::PostCall,
+ check::PostStmt<CXXConstructExpr>, check::PostStmt<DeclStmt>,
+ check::PostStmt<MaterializeTemporaryExpr>, check::BeginFunction,
+ check::DeadSymbols, eval::Assume, eval::Call> {
+ mutable IdentifierInfo *II_std = nullptr, *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> PastEndBugType;
+
+ void handleComparison(CheckerContext &C, const SVal &LVal,
+ const SVal &RVal) const;
+ void handleAccess(CheckerContext &C, const SVal &Val) const;
+ void handleDecrement(CheckerContext &C, const SVal &Val) const;
+ void handleEnd(CheckerContext &C, const SVal &RetVal) const;
+
+ void evalFind(CheckerContext &C, const CallExpr *CE) const;
+ void evalFindEnd(CheckerContext &C, const CallExpr *CE) const;
+ void evalFindFirstOf(CheckerContext &C, const CallExpr *CE) const;
+ void evalFindIf(CheckerContext &C, const CallExpr *CE) const;
+ void evalFindIfNot(CheckerContext &C, const CallExpr *CE) const;
+ void evalLowerBound(CheckerContext &C, const CallExpr *CE) const;
+ void evalUpperBound(CheckerContext &C, const CallExpr *CE) const;
+ void evalSearch(CheckerContext &C, const CallExpr *CE) const;
+ void evalSearchN(CheckerContext &C, const CallExpr *CE) const;
+ void Find(CheckerContext &C, const CallExpr *CE) const;
+
+ void reportPastEndBug(const StringRef &Message, const SVal &Val,
+ CheckerContext &C, ExplodedNode *ErrNode) const;
+
+public:
+ IteratorPastEndChecker();
+
+ void checkPreStmt(const CXXOperatorCallExpr *COCE, CheckerContext &C) const;
+ void checkBeginFunction(CheckerContext &C) const;
+ void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
+ void checkPostStmt(const CXXConstructExpr *CCE, CheckerContext &C) const;
+ void checkPostStmt(const DeclStmt *DS, CheckerContext &C) const;
+ void checkPostStmt(const MaterializeTemporaryExpr *MTE,
+ CheckerContext &C) const;
+ void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
+ ProgramStateRef evalAssume(ProgramStateRef State, SVal Cond,
+ bool Assumption) const;
+ bool evalCall(const CallExpr *CE, CheckerContext &C) const;
+};
+}
+
+REGISTER_MAP_WITH_PROGRAMSTATE(IteratorSymbolMap, SymbolRef, IteratorPosition)
+REGISTER_MAP_WITH_PROGRAMSTATE(IteratorRegionMap, const MemRegion *,
+ IteratorPosition)
+
+REGISTER_TRAIT_WITH_PROGRAMSTATE(LeftRegion, const void *)
+REGISTER_TRAIT_WITH_PROGRAMSTATE(LeftSymbol, const void *)
+
+REGISTER_TRAIT_WITH_PROGRAMSTATE(RightRegion, const void *)
+REGISTER_TRAIT_WITH_PROGRAMSTATE(RightSymbol, const void *)
+
+namespace {
+
+typedef std::pair<const MemRegion *, SymbolRef> RegionOrSymbol;
+
+static bool isIteratorType(const QualType &Type);
+static bool isIterator(const CXXRecordDecl *CRD);
+static bool isEndCall(const FunctionDecl *Func);
+static bool isSimpleComparisonOperator(OverloadedOperatorKind OK);
+static bool isAccessOperator(OverloadedOperatorKind OK);
+static bool isDecrementOperator(OverloadedOperatorKind OK);
+static bool inTopLevelNamespace(const Decl *D, IdentifierInfo *II);
+static const RegionOrSymbol loadLeftOperand(ProgramStateRef State);
+static const RegionOrSymbol loadRightOperand(ProgramStateRef State);
+static const ProgramStateRef clearLeftOperand(ProgramStateRef State);
+static const ProgramStateRef clearRightOperand(ProgramStateRef State);
+static const ProgramStateRef saveLeftOperand(ProgramStateRef State,
+ const SVal &Val);
+static const ProgramStateRef saveRightOperand(ProgramStateRef State,
+ const SVal &Val);
+static const RegionOrSymbol loadLeftOperand(ProgramStateRef State);
+static const RegionOrSymbol loadRightOperand(ProgramStateRef State);
+static const IteratorPosition *getIteratorPosition(ProgramStateRef State,
+ const SVal &Val);
+static const IteratorPosition *getIteratorPosition(ProgramStateRef State,
+ RegionOrSymbol RegOrSym);
+static ProgramStateRef setIteratorPosition(ProgramStateRef State,
+ const SVal &Val,
+ IteratorPosition Pos);
+static ProgramStateRef setIteratorPosition(ProgramStateRef State,
+ RegionOrSymbol RegOrSym,
+ IteratorPosition Pos);
+}
+
+IteratorPastEndChecker::IteratorPastEndChecker() {
+ PastEndBugType.reset(new BugType(this, "Iterator Past End", "C++ STL Error"));
+ PastEndBugType->setSuppressOnSink(true);
+}
+
+void IteratorPastEndChecker::checkPreStmt(const CXXOperatorCallExpr *COCE,
+ CheckerContext &C) const {
+ const auto *ThisExpr = COCE->getArg(0);
+
+ auto State = C.getState();
+ const auto *LCtx = C.getPredecessor()->getLocationContext();
+
+ const auto CurrentThis = State->getSVal(ThisExpr, LCtx);
+ if (const auto *Reg = CurrentThis.getAsRegion()) {
+ if (!Reg->getAs<CXXTempObjectRegion>())
+ return;
+ const auto OldState = C.getPredecessor()->getFirstPred()->getState();
+ const auto OldThis = OldState->getSVal(ThisExpr, LCtx);
+ const auto *Pos = getIteratorPosition(OldState, OldThis);
+ if (!Pos)
+ return;
+ State = setIteratorPosition(State, CurrentThis, *Pos);
+ C.addTransition(State);
+ }
+}
+
+void IteratorPastEndChecker::checkBeginFunction(CheckerContext &C) const {
+ auto State = C.getState();
+ const auto *LCtx = C.getLocationContext();
+ if (LCtx->getKind() != LocationContext::StackFrame)
+ return;
+
+ const auto *FD = dyn_cast<FunctionDecl>(LCtx->getDecl());
+ if (!FD)
+ return;
+
+ const auto *Site =
+ static_cast<const StackFrameContext *>(LCtx)->getCallSite();
+ if (!Site)
+ return;
+
+ const auto *CE = dyn_cast<CallExpr>(Site);
+ if (!CE)
+ return;
+
+ bool Change = false;
+ int idx = 0;
+ for (const auto P : FD->parameters()) {
+ auto Param = State->getLValue(P, LCtx);
+ auto Arg = State->getSVal(CE->getArg(idx++), LCtx->getParent());
+ const auto *Pos = getIteratorPosition(State, Arg);
+ if (!Pos)
+ continue;
+ State = setIteratorPosition(State, Param, *Pos);
+ Change = true;
+ }
+ if (Change) {
+ C.addTransition(State);
+ }
+}
+
+void IteratorPastEndChecker::checkPostCall(const CallEvent &Call,
+ CheckerContext &C) const {
+ const auto *Func = Call.getDecl()->getAsFunction();
+ if (Func->isOverloadedOperator()) {
+ if (isSimpleComparisonOperator(Func->getOverloadedOperator())) {
+ if (Func->isCXXInstanceMember()) {
+ const auto &InstCall = static_cast<const CXXInstanceCall &>(Call);
+ handleComparison(C, InstCall.getCXXThisVal(), InstCall.getArgSVal(0));
+ } else {
+ handleComparison(C, Call.getArgSVal(0), Call.getArgSVal(1));
+ }
+ } else if (isAccessOperator(Func->getOverloadedOperator())) {
+ if (Func->isCXXInstanceMember()) {
+ const auto &InstCall = static_cast<const CXXInstanceCall &>(Call);
+ handleAccess(C, InstCall.getCXXThisVal());
+ } else {
+ handleAccess(C, Call.getArgSVal(0));
+ }
+ } else if (isDecrementOperator(Func->getOverloadedOperator())) {
+ if (Func->isCXXInstanceMember()) {
+ const auto &InstCall = static_cast<const CXXInstanceCall &>(Call);
+ handleDecrement(C, InstCall.getCXXThisVal());
+ } else {
+ handleDecrement(C, Call.getArgSVal(0));
+ }
+ }
+ } else if (Func->isCXXInstanceMember()) {
+ if (!isEndCall(Func))
+ return;
+ if (!isIteratorType(Call.getResultType()))
+ return;
+ handleEnd(C, Call.getReturnValue());
+ }
+}
+
+void IteratorPastEndChecker::checkPostStmt(const CXXConstructExpr *CCE,
+ CheckerContext &C) const {
+ const auto *ctr = CCE->getConstructor();
+ if (!ctr->isCopyOrMoveConstructor())
+ return;
+ const auto *RHSExpr = CCE->getArg(0);
+
+ auto State = C.getState();
+ const auto *LCtx = C.getPredecessor()->getLocationContext();
+
+ const auto RetVal = State->getSVal(CCE, LCtx);
+
+ const auto RHSVal = State->getSVal(RHSExpr, LCtx);
+ const auto *RHSPos = getIteratorPosition(State, RHSVal);
+ if (RHSPos) {
+ State = setIteratorPosition(State, RetVal, *RHSPos);
+ }
+ C.addTransition(State);
+}
+
+void IteratorPastEndChecker::checkPostStmt(const DeclStmt *DS,
+ CheckerContext &C) const {
+ for (const auto *D : DS->decls()) {
+ const auto *VD = dyn_cast<VarDecl>(D);
+ if (!VD || !VD->hasInit())
+ continue;
+
+ auto State = C.getState();
+ const auto *LCtx = C.getPredecessor()->getLocationContext();
+ const auto *Pos =
+ getIteratorPosition(State, State->getSVal(VD->getInit(), LCtx));
+ if (!Pos)
+ continue;
+ State = setIteratorPosition(State, State->getLValue(VD, LCtx), *Pos);
+ C.addTransition(State);
+ }
+}
+
+void IteratorPastEndChecker::checkPostStmt(const MaterializeTemporaryExpr *MTE,
+ CheckerContext &C) const {
+ auto State = C.getState();
+ const auto *LCtx = C.getPredecessor()->getLocationContext();
+ const auto *Pos =
+ getIteratorPosition(State, State->getSVal(MTE->GetTemporaryExpr(), LCtx));
+ if (!Pos)
+ return;
+ State = setIteratorPosition(State, State->getSVal(MTE, LCtx), *Pos);
+ C.addTransition(State);
+}
+
+void IteratorPastEndChecker::checkDeadSymbols(SymbolReaper &SR,
+ CheckerContext &C) const {
+ auto State = C.getState();
+
+ auto RegionMap = State->get<IteratorRegionMap>();
+ for (auto I = RegionMap.begin(), E = RegionMap.end(); I != E; ++I) {
+ if (!SR.isLiveRegion(I->first)) {
+ State = State->remove<IteratorRegionMap>(I->first);
+ }
+ }
+
+ auto SymbolMap = State->get<IteratorSymbolMap>();
+ for (auto I = SymbolMap.begin(), E = SymbolMap.end(); I != E; ++I) {
+ if (SR.isDead(I->first)) {
+ State = State->remove<IteratorSymbolMap>(I->first);
+ }
+ }
+}
+
+ProgramStateRef IteratorPastEndChecker::evalAssume(ProgramStateRef State,
+ SVal Cond,
+ bool Assumption) const {
+ const auto *SE = Cond.getAsSymExpr();
+ if (!SE)
+ return State;
+ BinaryOperator::Opcode Opc;
+ if (const auto *BSE = dyn_cast<BinarySymExpr>(SE)) {
+ Opc = BSE->getOpcode();
+ if (Opc != BO_EQ && Opc != BO_NE)
+ return State;
+ }
+
+ const auto Left = loadLeftOperand(State);
+ const auto Right = loadRightOperand(State);
+ State = clearLeftOperand(State);
+ State = clearRightOperand(State);
+ if ((!Left.first && !Left.second) || (!Right.first && !Right.second))
+ return State;
+ const auto *LPos = getIteratorPosition(State, Left);
+ const auto *RPos = getIteratorPosition(State, Right);
+ if (LPos && !RPos) {
+ if ((LPos->isInRange() && ((Opc == BO_EQ) == Assumption)) ||
+ (LPos->isOutofRange() && ((Opc == BO_EQ) != Assumption))) {
+ State = setIteratorPosition(State, Right, IteratorPosition::getInRange());
+ } else if (LPos->isOutofRange() && ((Opc == BO_EQ) == Assumption)) {
+ State =
+ setIteratorPosition(State, Right, IteratorPosition::getOutofRange());
+ }
+ } else if (!LPos && RPos) {
+ if ((RPos->isInRange() && ((Opc == BO_EQ) == Assumption)) ||
+ (RPos->isOutofRange() && ((Opc == BO_EQ) != Assumption))) {
+ State = setIteratorPosition(State, Left, IteratorPosition::getInRange());
+ } else if (RPos->isOutofRange() && ((Opc == BO_EQ) == Assumption)) {
+ State =
+ setIteratorPosition(State, Left, IteratorPosition::getOutofRange());
+ }
+ } else if (LPos && RPos) {
+ if (((*LPos != *RPos) && ((Opc == BO_EQ) == Assumption)) ||
+ ((LPos->isOutofRange() && RPos->isOutofRange()) &&
+ ((Opc == BO_EQ) != Assumption))) {
+ return nullptr;
+ }
+ }
+ return State;
+}
+
+bool IteratorPastEndChecker::evalCall(const CallExpr *CE,
+ CheckerContext &C) const {
+ const FunctionDecl *FD = C.getCalleeDecl(CE);
+ if (!FD)
+ return false;
+
+ ASTContext &Ctx = C.getASTContext();
+ if (!II_std)
+ II_std = &Ctx.Idents.get("std");
+ if (!II_find)
+ II_find = &Ctx.Idents.get("find");
+ if (!II_find_end)
+ II_find_end = &Ctx.Idents.get("find_end");
+ if (!II_find_first_of)
+ II_find_first_of = &Ctx.Idents.get("find_first_of");
+ if (!II_find_if)
+ II_find_if = &Ctx.Idents.get("find_if");
+ if (!II_find_if_not)
+ II_find_if_not = &Ctx.Idents.get("find_if_not");
+ if (!II_lower_bound)
+ II_lower_bound = &Ctx.Idents.get("lower_bound");
+ if (!II_upper_bound)
+ II_upper_bound = &Ctx.Idents.get("upper_bound");
+ if (!II_search)
+ II_search = &Ctx.Idents.get("search");
+ if (!II_search_n)
+ II_search_n = &Ctx.Idents.get("search_n");
+
+ if (FD->getKind() == Decl::Function) {
+ if (inTopLevelNamespace(FD, II_std)) {
+ if (FD->getIdentifier() == II_find) {
+ evalFind(C, CE);
+ return true;
+ } else if (FD->getIdentifier() == II_find_end) {
+ evalFindEnd(C, CE);
+ return true;
+ } else if (FD->getIdentifier() == II_find_first_of) {
+ evalFindFirstOf(C, CE);
+ return true;
+ } else if (FD->getIdentifier() == II_find_if) {
+ evalFindIf(C, CE);
+ return true;
+ } else if (FD->getIdentifier() == II_find_if) {
+ evalFindIf(C, CE);
+ return true;
+ } else if (FD->getIdentifier() == II_find_if_not) {
+ evalFindIfNot(C, CE);
+ return true;
+ } else if (FD->getIdentifier() == II_upper_bound) {
+ evalUpperBound(C, CE);
+ return true;
+ } else if (FD->getIdentifier() == II_lower_bound) {
+ evalLowerBound(C, CE);
+ return true;
+ } else if (FD->getIdentifier() == II_search) {
+ evalSearch(C, CE);
+ return true;
+ } else if (FD->getIdentifier() == II_search_n) {
+ evalSearchN(C, CE);
+ return true;
+ }
+ }
+ }
+
+ return false;
+}
+
+void IteratorPastEndChecker::handleComparison(CheckerContext &C,
+ const SVal &LVal,
+ const SVal &RVal) const {
+ auto State = C.getState();
+ const auto *LPos = getIteratorPosition(State, LVal);
+ const auto *RPos = getIteratorPosition(State, RVal);
+ if (!LPos && !RPos)
+ return;
+ State = saveLeftOperand(State, LVal);
+ State = saveRightOperand(State, RVal);
+ C.addTransition(State);
+}
+
+void IteratorPastEndChecker::handleAccess(CheckerContext &C,
+ const SVal &Val) const {
+ auto State = C.getState();
+ const auto *Pos = getIteratorPosition(State, Val);
+ if (Pos && Pos->isOutofRange()) {
+ auto *N = C.generateNonFatalErrorNode(State);
+ if (!N)
+ return;
+ reportPastEndBug("Iterator possibly accessed past its end.", Val, C, N);
+ }
+}
+
+void IteratorPastEndChecker::handleDecrement(CheckerContext &C,
+ const SVal &Val) const {
+ auto State = C.getState();
+ const auto *Pos = getIteratorPosition(State, Val);
+ if (Pos && Pos->isOutofRange()) {
+ State = setIteratorPosition(State, Val, IteratorPosition::getInRange());
+ C.addTransition(State);
+ }
+}
+
+void IteratorPastEndChecker::handleEnd(CheckerContext &C,
+ const SVal &RetVal) const {
+ auto State = C.getState();
+ const auto Sym = RetVal.getAsSymbol();
+ if (!Sym)
+ return;
+ State = State->set<IteratorSymbolMap>(Sym, IteratorPosition::getOutofRange());
+ C.addTransition(State);
+}
+
+void IteratorPastEndChecker::evalFind(CheckerContext &C,
+ const CallExpr *CE) const {
+ Find(C, CE);
+}
+
+void IteratorPastEndChecker::evalFindEnd(CheckerContext &C,
+ const CallExpr *CE) const {
+ Find(C, CE);
+}
+
+void IteratorPastEndChecker::evalFindFirstOf(CheckerContext &C,
+ const CallExpr *CE) const {
+ Find(C, CE);
+}
+
+void IteratorPastEndChecker::evalFindIf(CheckerContext &C,
+ const CallExpr *CE) const {
+ Find(C, CE);
+}
+
+void IteratorPastEndChecker::evalFindIfNot(CheckerContext &C,
+ const CallExpr *CE) const {
+ Find(C, CE);
+}
+
+void IteratorPastEndChecker::evalLowerBound(CheckerContext &C,
+ const CallExpr *CE) const {
+ Find(C, CE);
+}
+
+void IteratorPastEndChecker::evalUpperBound(CheckerContext &C,
+ const CallExpr *CE) const {
+ Find(C, CE);
+}
+
+void IteratorPastEndChecker::evalSearch(CheckerContext &C,
+ const CallExpr *CE) const {
+ Find(C, CE);
+}
+
+void IteratorPastEndChecker::evalSearchN(CheckerContext &C,
+ const CallExpr *CE) const {
+ Find(C, CE);
+}
+
+void IteratorPastEndChecker::Find(CheckerContext &C, const CallExpr *CE) const {
+ auto state = C.getState();
+ auto &svalBuilder = C.getSValBuilder();
+ const auto *LCtx = C.getPredecessor()->getLocationContext();
+
+ auto RetVal = svalBuilder.conjureSymbolVal(nullptr, CE, LCtx, C.blockCount());
+ auto SecondParam = state->getSVal(CE->getArg(1), C.getLocationContext());
+
+ auto stateFound = state->BindExpr(CE, C.getLocationContext(), RetVal);
+ auto stateNotFound = state->BindExpr(CE, C.getLocationContext(), SecondParam);
+
+ C.addTransition(stateFound);
+ C.addTransition(stateNotFound);
+}
+
+void IteratorPastEndChecker::reportPastEndBug(const StringRef &Message,
+ const SVal &Val,
+ CheckerContext &C,
+ ExplodedNode *ErrNode) const {
+ auto R = llvm::make_unique<BugReport>(*PastEndBugType, Message, ErrNode);
+ R->markInteresting(Val);
+ C.emitReport(std::move(R));
+}
+
+namespace {
+
+template <typename RegionOperand, typename SymbolOperand>
+static const RegionOrSymbol loadOperand(ProgramStateRef State);
+
+template <typename RegionOperand, typename SymbolOperand>
+static const ProgramStateRef clearOperand(ProgramStateRef State);
+
+template <typename RegionOperand, typename SymbolOperand>
+static const ProgramStateRef saveOperand(ProgramStateRef State,
+ const SVal &Val);
+
+static bool isIteratorType(const QualType &Type) {
+ const auto *CRD = Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl();
+ return isIterator(CRD);
+}
+
+static bool isIterator(const CXXRecordDecl *CRD) {
+ if (!CRD)
+ return false;
+
+ const auto Name = CRD->getName();
+ if (!(Name.endswith_lower("iterator") || Name.endswith_lower("iter") ||
+ Name.endswith_lower("it")))
+ return false;
+
+ bool CopyC = false, Dest = false, PreIncr = false, PostIncr = false,
+ Deref = false;
+ // We also should check for copy assignment operator, but for some reason
+ // it is not provided implicitly in Clang Static Analyzer
+ for (const auto *M : CRD->methods()) {
+ if (const auto *C = dyn_cast<CXXConstructorDecl>(M)) {
+ if (C->isCopyConstructor()) {
+ CopyC = !C->isDeleted();
+ }
+ continue;
+ }
+ if (const auto *D = dyn_cast<CXXDestructorDecl>(M)) {
+ Dest = !D->isDeleted();
+ continue;
+ }
+ if (!M->isOverloadedOperator())
+ continue;
+ const auto OPK = M->getOverloadedOperator();
+ if (OPK == OO_PlusPlus) {
+ PreIncr = PreIncr || (M->getNumParams() == 0);
+ PostIncr = PostIncr || (M->getNumParams() == 1);
+ continue;
+ }
+ if (OPK == OO_Star) {
+ Deref = (M->getNumParams() == 0);
+ continue;
+ }
+ }
+
+ return CopyC && Dest && PreIncr && PostIncr && Deref;
+}
+
+static bool isEndCall(const FunctionDecl *Func) {
+ const auto *IdInfo = Func->getIdentifier();
+ if (!IdInfo)
+ return false;
+ return IdInfo->getName().endswith_lower("end");
+}
+
+static bool isSimpleComparisonOperator(OverloadedOperatorKind OK) {
+ return OK == OO_EqualEqual || OK == OO_ExclaimEqual;
+}
+
+static bool isAccessOperator(OverloadedOperatorKind OK) {
+ return OK == OO_Star || OK == OO_Arrow || OK == OO_ArrowStar ||
+ OK == OO_Plus || OK == OO_PlusEqual || OK == OO_PlusPlus ||
+ OK == OO_Subscript;
+}
+
+static bool isDecrementOperator(OverloadedOperatorKind OK) {
+ return OK == OO_MinusEqual || OK == OO_MinusMinus;
+}
+
+static bool inTopLevelNamespace(const Decl *D, IdentifierInfo *II) {
+ const auto *ND = dyn_cast<NamespaceDecl>(D->getDeclContext());
+ if (!ND)
+ return false;
+
+ if (ND->getIdentifier() != II)
+ return false;
+
+ return isa<TranslationUnitDecl>(ND->getDeclContext());
+}
+
+static const RegionOrSymbol loadLeftOperand(ProgramStateRef State) {
+ return loadOperand<LeftRegion, LeftSymbol>(State);
+}
+
+static const RegionOrSymbol loadRightOperand(ProgramStateRef State) {
+ return loadOperand<RightRegion, RightSymbol>(State);
+}
+
+template <typename RegionOperand, typename SymbolOperand>
+static const RegionOrSymbol loadOperand(ProgramStateRef State) {
+ const auto *Reg = static_cast<const MemRegion *>(State->get<RegionOperand>());
+ const auto Sym = static_cast<SymbolRef>(State->get<SymbolOperand>());
+ return std::make_pair(Reg, Sym);
+}
+
+static const ProgramStateRef clearLeftOperand(ProgramStateRef State) {
+ return clearOperand<LeftRegion, LeftSymbol>(State);
+}
+
+static const ProgramStateRef clearRightOperand(ProgramStateRef State) {
+ return clearOperand<RightRegion, RightSymbol>(State);
+}
+
+template <typename RegionOperand, typename SymbolOperand>
+static const ProgramStateRef clearOperand(ProgramStateRef State) {
+ State = State->set<RegionOperand>(nullptr);
+ State = State->set<SymbolOperand>(nullptr);
+ return State;
+}
+
+static const ProgramStateRef saveLeftOperand(ProgramStateRef State,
+ const SVal &Val) {
+ return saveOperand<LeftRegion, LeftSymbol>(State, Val);
+}
+
+static const ProgramStateRef saveRightOperand(ProgramStateRef State,
+ const SVal &Val) {
+ return saveOperand<RightRegion, RightSymbol>(State, Val);
+}
+
+template <typename RegionOperand, typename SymbolOperand>
+static const ProgramStateRef saveOperand(ProgramStateRef State,
+ const SVal &Val) {
+ State = State->set<RegionOperand>(Val.getAsRegion());
+ State = State->set<SymbolOperand>(Val.getAsSymbol());
+ if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
+ State = State->set<RegionOperand>(LCVal->getRegion());
+ }
+ return State;
+}
+
+static const IteratorPosition *getIteratorPosition(ProgramStateRef State,
+ const SVal &Val) {
+ if (const auto Reg = Val.getAsRegion()) {
+ return State->get<IteratorRegionMap>(Reg);
+ } else if (const auto Sym = Val.getAsSymbol()) {
+ return State->get<IteratorSymbolMap>(Sym);
+ } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
+ return State->get<IteratorRegionMap>(LCVal->getRegion());
+ }
+ return nullptr;
+}
+
+static const IteratorPosition *getIteratorPosition(ProgramStateRef State,
+ RegionOrSymbol RegOrSym) {
+ if (const auto Reg = RegOrSym.first) {
+ return State->get<IteratorRegionMap>(Reg);
+ } else if (const auto Sym = RegOrSym.second) {
+ return State->get<IteratorSymbolMap>(Sym);
+ }
+ return nullptr;
+}
+
+static ProgramStateRef setIteratorPosition(ProgramStateRef State,
+ const SVal &Val,
+ IteratorPosition Pos) {
+ if (const auto Reg = Val.getAsRegion()) {
+ return State->set<IteratorRegionMap>(Reg, Pos);
+ } else if (const auto Sym = Val.getAsSymbol()) {
+ return State->set<IteratorSymbolMap>(Sym, Pos);
+ } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
+ return State->set<IteratorRegionMap>(LCVal->getRegion(), Pos);
+ }
+ return nullptr;
+}
+
+static ProgramStateRef setIteratorPosition(ProgramStateRef State,
+ RegionOrSymbol RegOrSym,
+ IteratorPosition Pos) {
+ if (const auto Reg = RegOrSym.first) {
+ return State->set<IteratorRegionMap>(Reg, Pos);
+ } else if (const auto Sym = RegOrSym.second) {
+ return State->set<IteratorSymbolMap>(Sym, Pos);
+ }
+ return nullptr;
+}
+}
+
+void ento::registerIteratorPastEndChecker(CheckerManager &Mgr) {
+ Mgr.registerChecker<IteratorPastEndChecker>();
+}
Index: lib/StaticAnalyzer/Checkers/CMakeLists.txt
===================================================================
--- lib/StaticAnalyzer/Checkers/CMakeLists.txt
+++ lib/StaticAnalyzer/Checkers/CMakeLists.txt
@@ -38,6 +38,7 @@
FixedAddressChecker.cpp
GenericTaintChecker.cpp
IdenticalExprChecker.cpp
+ IteratorPastEndChecker.cpp
IvarInvalidationChecker.cpp
LLVMConventionsChecker.cpp
LocalizationChecker.cpp
Index: include/clang/StaticAnalyzer/Checkers/Checkers.td
===================================================================
--- include/clang/StaticAnalyzer/Checkers/Checkers.td
+++ include/clang/StaticAnalyzer/Checkers/Checkers.td
@@ -268,6 +268,10 @@
HelpText<"Check virtual function calls during construction or destruction">,
DescFile<"VirtualCallChecker.cpp">;
+def IteratorPastEndChecker : Checker<"IteratorPastEnd">,
+ HelpText<"Check iterators used past end">,
+ DescFile<"IteratorPastEndChecker.cpp">;
+
} // end: "alpha.cplusplus"
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
