baloghadamsoftware updated this revision to Diff 89123.
baloghadamsoftware added a comment.
Updated according to the comments.
https://reviews.llvm.org/D29419
Files:
include/clang/StaticAnalyzer/Checkers/Checkers.td
lib/StaticAnalyzer/Checkers/CMakeLists.txt
lib/StaticAnalyzer/Checkers/MismatchedIteratorChecker.cpp
test/Analysis/Inputs/system-header-simulator-cxx.h
test/Analysis/diagnostics/explicit-suppression.cpp
test/Analysis/mismatched-iterator.cpp
Index: test/Analysis/mismatched-iterator.cpp
===================================================================
--- /dev/null
+++ test/Analysis/mismatched-iterator.cpp
@@ -0,0 +1,134 @@
+// RUN: %clang_cc1 -std=c++11 -analyze -analyzer-checker=core,cplusplus,alpha.cplusplus.MismatchedIterator -analyzer-eagerly-assume %s -verify
+
+#include "Inputs/system-header-simulator-cxx.h"
+
+void good_insert1(std::vector<int> &v, int n) {
+ v.insert(v.cbegin(), n); // no-warning
+}
+
+
+void good_insert2(std::vector<int> &v, int len, int n) {
+ v.insert(v.cbegin(), len, n); // no-warning
+}
+
+void good_insert3(std::vector<int> &v1, std::vector<int> &v2) {
+ v1.insert(v1.cbegin(), v2.cbegin(), v2.cend()); // no-warning
+}
+
+void good_insert4(std::vector<int> &v, int len, int n) {
+ v.insert(v.cbegin(), {n-1, n, n+1}); // no-warning
+}
+
+void good_insert_find(std::vector<int> &v, int n, int m) {
+ auto i = std::find(v.begin(), v.end(), n);
+ v.insert(i, m); // no-warning
+}
+
+void good_erase1(std::vector<int> &v) {
+ v.erase(v.cbegin()); // no-warning
+}
+
+void good_erase2(std::vector<int> &v) {
+ v.erase(v.cbegin(), v.cend()); // no-warning
+}
+
+void good_emplace(std::vector<int> &v, int n) {
+ v.emplace(v.cbegin(), n); // no-warning
+}
+
+void good_ctor(std::vector<int> &v) {
+ std::vector<int> new_v(v.begin(), v.end()); // no-warning
+}
+
+void good_find(std::vector<int> &v, int n) {
+ std::find(v.begin(), v.end(), n); // no-warning
+}
+
+void good_find_first_of(std::vector<int> &v1, std::vector<int> &v2) {
+ std::find_first_of(v1.begin(), v1.end(), v2.begin(), v2.end()); // no-warning
+}
+
+void good_comparison(std::vector<int> &v) {
+ if (v.begin() == v.end()) {} // no-warning
+}
+
+void bad_insert1(std::vector<int> &v1, std::vector<int> &v2, int n) {
+ v2.insert(v1.cbegin(), n); // expected-warning{{Iterator access mismatched}}
+}
+
+void bad_insert2(std::vector<int> &v1, std::vector<int> &v2, int len, int n) {
+ v2.insert(v1.cbegin(), len, n); // expected-warning{{Iterator access mismatched}}
+}
+
+void bad_insert3(std::vector<int> &v1, std::vector<int> &v2) {
+ v2.insert(v1.cbegin(), v2.cbegin(), v2.cend()); // expected-warning{{Iterator access mismatched}}
+ v1.insert(v1.cbegin(), v1.cbegin(), v2.cend()); // expected-warning{{Iterator access mismatched}}
+ v1.insert(v1.cbegin(), v2.cbegin(), v1.cend()); // expected-warning{{Iterator access mismatched}}
+}
+
+void bad_insert4(std::vector<int> &v1, std::vector<int> &v2, int len, int n) {
+ v2.insert(v1.cbegin(), {n-1, n, n+1}); // expected-warning{{Iterator access mismatched}}
+}
+
+void bad_erase1(std::vector<int> &v1, std::vector<int> &v2) {
+ v2.erase(v1.cbegin()); // expected-warning{{Iterator access mismatched}}
+}
+
+void bad_erase2(std::vector<int> &v1, std::vector<int> &v2) {
+ v2.erase(v2.cbegin(), v1.cend()); // expected-warning{{Iterator access mismatched}}
+ v2.erase(v1.cbegin(), v2.cend()); // expected-warning{{Iterator access mismatched}}
+ v2.erase(v1.cbegin(), v1.cend()); // expected-warning{{Iterator access mismatched}}
+}
+
+void bad_emplace(std::vector<int> &v1, std::vector<int> &v2, int n) {
+ v2.emplace(v1.cbegin(), n); // expected-warning{{Iterator access mismatched}}
+}
+
+void bad_ctor(std::vector<int> &v1, std::vector<int> &v2) {
+ std::vector<int> new_v(v1.begin(), v2.end()); // expected-warning{{Iterator access mismatched}}
+}
+
+void bad_find(std::vector<int> &v1, std::vector<int> &v2, int n) {
+ std::find(v1.begin(), v2.end(), n); // expected-warning{{Iterator access mismatched}}
+}
+
+void bad_find_first_of(std::vector<int> &v1, std::vector<int> &v2) {
+ std::find_first_of(v1.begin(), v2.end(), v2.begin(), v2.end()); // expected-warning{{Iterator access mismatched}}
+ std::find_first_of(v1.begin(), v1.end(), v2.begin(), v1.end()); // expected-warning{{Iterator access mismatched}}
+}
+
+void bad_comparison(std::vector<int> &v1, std::vector<int> &v2) {
+ if (v1.begin() != v2.end()) { // expected-warning{{Iterator access mismatched}}
+ *v1.begin();
+ }
+}
+
+void bad_insert_find(std::vector<int> &v1, std::vector<int> &v2, int n, int m) {
+ auto i = std::find(v1.begin(), v1.end(), n);
+ v2.insert(i, m); // expected-warning{{Iterator access mismatched}}
+}
+
+void good_overwrite(std::vector<int> &v1, std::vector<int> &v2, int n) {
+ auto i = v1.cbegin();
+ i = v2.cbegin();
+ v2.insert(i, n); // no-warning
+}
+
+void bad_overwrite(std::vector<int> &v1, std::vector<int> &v2, int n) {
+ auto i = v1.cbegin();
+ i = v2.cbegin();
+ v1.insert(i, n); // expected-warning{{Iterator access mismatched}}
+}
+
+template<typename Container, typename Iterator>
+bool is_end(Container cont, Iterator it) {
+ return it == cont.end();
+}
+
+void good_empty(std::vector<int> &v) {
+ is_end(v, v.begin()); // no-warning
+}
+
+void bad_empty(std::vector<int> &v1, std::vector<int> &v2) {
+ is_end(v1, v2.begin()); // expected-warning@125{{Iterator access mismatched}}
+}
Index: test/Analysis/diagnostics/explicit-suppression.cpp
===================================================================
--- test/Analysis/diagnostics/explicit-suppression.cpp
+++ test/Analysis/diagnostics/explicit-suppression.cpp
@@ -18,6 +18,6 @@
void testCopyNull(C *I, C *E) {
std::copy(I, E, (C *)0);
#ifndef SUPPRESSED
- // expected-warning@../Inputs/system-header-simulator-cxx.h:191 {{Called C++ object pointer is null}}
+ // expected-warning@../Inputs/system-header-simulator-cxx.h:217 {{Called C++ object pointer is null}}
#endif
}
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
@@ -14,7 +14,8 @@
typedef __iterator<T, T *, T &> iterator;
typedef __iterator<T, const T *, const T &> const_iterator;
- __iterator(const Ptr p) : ptr(p) {}
+ __iterator(const Ptr p): ptr(p) {}
+ __iterator(const iterator &rhs): ptr(rhs.base()) {}
__iterator<T, Ptr, Ref> operator++() { return *this; }
__iterator<T, Ptr, Ref> operator++(int) { return *this; }
@@ -29,6 +30,7 @@
bool operator!=(const iterator &rhs) const { return ptr != rhs.ptr; }
bool operator!=(const const_iterator &rhs) const { return ptr != rhs.ptr; }
+ const Ptr& base() const { return ptr; }
private:
Ptr ptr;
};
@@ -47,17 +49,23 @@
};
typedef __typeof__(sizeof(int)) size_t;
+
+ template <class T> class initializer_list;
template<typename T>
class vector {
+ typedef T value_type;
+ typedef size_t size_type;
typedef __iterator<T, T *, T &> iterator;
typedef __iterator<T, const T *, const T &> const_iterator;
T *_start;
T *_finish;
T *_end_of_storage;
public:
vector() : _start(0), _finish(0), _end_of_storage(0) {}
+ template <typename InputIterator>
+ vector(InputIterator first, InputIterator last);
~vector();
size_t size() const {
@@ -67,6 +75,22 @@
void push_back();
T pop_back();
+ iterator insert(const_iterator position, const value_type& val);
+ iterator insert(const_iterator position, size_type n,
+ const value_type& val);
+ template <typename InputIterator>
+ iterator insert(const_iterator position, InputIterator first,
+ InputIterator last);
+ iterator insert(const_iterator position, value_type&& val);
+ iterator insert(const_iterator position, initializer_list<value_type> il);
+
+ iterator erase(const_iterator position);
+ iterator erase(const_iterator first, const_iterator last);
+
+ template <class... Args>
+ iterator emplace(const_iterator position, Args&&... args);
+
+
T &operator[](size_t n) {
return _start[n];
}
@@ -77,8 +101,10 @@
iterator begin() { return iterator(_start); }
const_iterator begin() const { return const_iterator(_start); }
+ const_iterator cbegin() const { return const_iterator(_start); }
iterator end() { return iterator(_finish); }
const_iterator end() const { return const_iterator(_finish); }
+ const_iterator cend() const { return const_iterator(_finish); }
};
class exception {
Index: lib/StaticAnalyzer/Checkers/MismatchedIteratorChecker.cpp
===================================================================
--- /dev/null
+++ lib/StaticAnalyzer/Checkers/MismatchedIteratorChecker.cpp
@@ -0,0 +1,542 @@
+//===-- MismatchedIteratorChecker.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/AST/DeclTemplate.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 {
+class MismatchedIteratorChecker
+ : public Checker<check::PreCall, check::PostCall,
+ check::PreStmt<CXXConstructExpr>,
+ check::PreStmt<CXXOperatorCallExpr>,
+ check::PostStmt<MaterializeTemporaryExpr>, check::Bind,
+ check::BeginFunction, check::DeadSymbols> {
+
+ std::unique_ptr<BugType> MismatchedBugType;
+
+ void verifyMatch(CheckerContext &C, const SVal &Iter,
+ const MemRegion *Cont) const;
+ void verifyMatch(CheckerContext &C, const SVal &Iter1,
+ const SVal &Iter2) const;
+ void handleBeginOrEnd(CheckerContext &C, const SVal &RetVal,
+ const SVal &Cont) const;
+ void handleAssignment(CheckerContext &C, const SVal &LHS,
+ const SVal &RHS) const;
+
+ void reportMismatchedBug(const StringRef &Message, const SVal &Val,
+ CheckerContext &C, ExplodedNode *ErrNode) const;
+
+public:
+ MismatchedIteratorChecker();
+
+ void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
+ void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
+ void checkPreStmt(const CXXOperatorCallExpr *COCE, CheckerContext &C) const;
+ void checkPreStmt(const CXXConstructExpr *CCE, CheckerContext &C) const;
+ void checkBind(SVal Loc, SVal Val, const Stmt *S, CheckerContext &C) const;
+ void checkBeginFunction(CheckerContext &C) const;
+ void checkPostStmt(const MaterializeTemporaryExpr *MTE,
+ CheckerContext &C) const;
+ void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
+};
+}
+
+REGISTER_MAP_WITH_PROGRAMSTATE(IteratorSymbolMap, SymbolRef, const MemRegion *)
+REGISTER_MAP_WITH_PROGRAMSTATE(IteratorRegionMap, const MemRegion *,
+ const MemRegion *)
+
+namespace {
+
+static bool isIteratorType(const QualType &Type);
+static bool isIterator(const CXXRecordDecl *CRD);
+static bool isComparisonOperator(OverloadedOperatorKind OK);
+static bool isBeginOrEndCall(const FunctionDecl *Func);
+static bool isInsertCall(const FunctionDecl *Func);
+static bool isEraseCall(const FunctionDecl *Func);
+static bool isEmplaceCall(const FunctionDecl *Func);
+static const MemRegion *const *getIteratorContainer(ProgramStateRef State,
+ const SVal &Val);
+static ProgramStateRef setIteratorContainer(ProgramStateRef State,
+ const SVal &Val,
+ const MemRegion *Cont);
+static ProgramStateRef removeIteratorContainer(ProgramStateRef State,
+ const SVal &Val);
+}
+
+MismatchedIteratorChecker::MismatchedIteratorChecker() {
+ MismatchedBugType.reset(
+ new BugType(this, "Mismatched Iterator", "C++ STL Error"));
+ MismatchedBugType->setSuppressOnSink(true);
+}
+
+void MismatchedIteratorChecker::checkPreCall(const CallEvent &Call,
+ CheckerContext &C) const {
+ const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
+ if (!Func)
+ return;
+
+ if (Func->isOverloadedOperator()) {
+ if (!isComparisonOperator(Func->getOverloadedOperator()))
+ return;
+
+ if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
+ if (Call.getNumArgs() < 1)
+ return;
+
+ if (!isIteratorType(InstCall->getCXXThisExpr()->getType()) ||
+ !isIteratorType(Call.getArgExpr(0)->getType()))
+ return;
+
+ verifyMatch(C, InstCall->getCXXThisVal(), Call.getArgSVal(0));
+ } else {
+ if (Call.getNumArgs() < 2)
+ return;
+
+ if (!isIteratorType(Call.getArgExpr(0)->getType()) ||
+ !isIteratorType(Call.getArgExpr(1)->getType()))
+ return;
+
+ verifyMatch(C, Call.getArgSVal(0), Call.getArgSVal(1));
+ }
+ } else if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
+ const auto *ContReg = InstCall->getCXXThisVal().getAsRegion();
+ if (!ContReg)
+ return;
+ if (isEraseCall(Func)) {
+ verifyMatch(C, Call.getArgSVal(0),
+ InstCall->getCXXThisVal().getAsRegion());
+ if (Call.getNumArgs() == 2) {
+ verifyMatch(C, Call.getArgSVal(1),
+ InstCall->getCXXThisVal().getAsRegion());
+ }
+ } else if (isInsertCall(Func)) {
+ verifyMatch(C, Call.getArgSVal(0),
+ InstCall->getCXXThisVal().getAsRegion());
+ if (Call.getNumArgs() == 3 &&
+ isIteratorType(Call.getArgExpr(1)->getType()) &&
+ isIteratorType(Call.getArgExpr(2)->getType())) {
+ verifyMatch(C, Call.getArgSVal(1), Call.getArgSVal(2));
+ }
+ } else if (isEmplaceCall(Func)) {
+ verifyMatch(C, Call.getArgSVal(0),
+ InstCall->getCXXThisVal().getAsRegion());
+ }
+ } else if (!isa<CXXConstructorCall>(&Call)) {
+ // The main purpose of iterators is to abstract away from different
+ // containers and provide a (maybe limited) uniform access to them.
+ // This implies that any correctly written template function that
+ // works on multiple containers using iterators takes different
+ // template parameters for different containers. So we can safely
+ // assume that passing iterators of different containers as arguments
+ // whose type replaces the same template parameter is a bug.
+ const auto *Templ = Func->getPrimaryTemplate();
+ if (!Templ)
+ return;
+
+ const auto *TParams = Templ->getTemplateParameters();
+ const auto *TArgs = Func->getTemplateSpecializationArgs();
+
+ for (auto i = 0U; i < TParams->size(); ++i) {
+ const auto *TPDecl = dyn_cast<TypeDecl>(TParams->getParam(i));
+ if (!TPDecl)
+ continue;
+
+ const auto TAType = TArgs->get(i).getAsType();
+ if (!isIteratorType(TAType))
+ continue;
+
+ SVal LHS = UndefinedVal();
+
+ for (auto j = 0U; j < Func->getNumParams(); ++j) {
+ const auto *Param = Func->getParamDecl(j);
+ const auto *ParamType =
+ Param->getType()->getAs<SubstTemplateTypeParmType>();
+ if (!ParamType ||
+ ParamType->getReplacedParameter()->getDecl() != TPDecl)
+ continue;
+ if (LHS.isUndef()) {
+ LHS = Call.getArgSVal(j);
+ } else {
+ verifyMatch(C, LHS, Call.getArgSVal(j));
+ }
+ }
+ }
+ }
+}
+
+void MismatchedIteratorChecker::checkPostCall(const CallEvent &Call,
+ CheckerContext &C) const {
+ const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
+ if (!Func)
+ return;
+
+ if (!Call.getOriginExpr())
+ return;
+
+ if (!isIteratorType(Call.getResultType()))
+ return;
+
+ auto State = C.getState();
+ // Already bound to container?
+ if (getIteratorContainer(State, Call.getReturnValue()))
+ return;
+
+ if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
+ if (isBeginOrEndCall(Func)) {
+ handleBeginOrEnd(C, Call.getReturnValue(), InstCall->getCXXThisVal());
+ return;
+ }
+ }
+
+ // Assumption: if return value is an iterator which is not yet bound to a
+ // container, then look for the first iterator argument, and
+ // bind the return value to the same container. This approach
+ // works for STL algorithms.
+ for (unsigned i = 0; i < Call.getNumArgs(); ++i) {
+ if (isIteratorType(Call.getArgExpr(i)->getType())) {
+ if (const auto *Cont = getIteratorContainer(State, Call.getArgSVal(i))) {
+ State = setIteratorContainer(State, Call.getReturnValue(), *Cont);
+ C.addTransition(State);
+ return;
+ }
+ }
+ }
+}
+
+void MismatchedIteratorChecker::checkPreStmt(const CXXConstructExpr *CCE,
+ CheckerContext &C) const {
+ if (CCE->getNumArgs() < 2)
+ return;
+
+ const auto *Ctr = CCE->getConstructor();
+ if (Ctr->getNumParams() < 2)
+ return;
+
+ if (Ctr->getParamDecl(0)->getName() != "first" ||
+ Ctr->getParamDecl(1)->getName() != "last")
+ return;
+
+ if (!isIteratorType(CCE->getArg(0)->getType()) ||
+ !isIteratorType(CCE->getArg(1)->getType()))
+ return;
+
+ auto State = C.getState();
+ const auto *LCtx = C.getPredecessor()->getLocationContext();
+
+ verifyMatch(C, State->getSVal(CCE->getArg(0), LCtx),
+ State->getSVal(CCE->getArg(1), LCtx));
+}
+
+void MismatchedIteratorChecker::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 *Cont = getIteratorContainer(OldState, OldThis);
+ if (!Cont)
+ return;
+ State = setIteratorContainer(State, CurrentThis, *Cont);
+ C.addTransition(State);
+ }
+}
+
+void MismatchedIteratorChecker::checkBind(SVal Loc, SVal Val, const Stmt *S,
+ CheckerContext &C) const {
+ auto State = C.getState();
+ const auto *const *Cont = getIteratorContainer(State, Val);
+ if (Cont) {
+ State = setIteratorContainer(State, Loc, *Cont);
+ C.addTransition(State);
+ } else {
+ const auto *const *OldCont = getIteratorContainer(State, Loc);
+ if (OldCont) {
+ State = removeIteratorContainer(State, Loc);
+ C.addTransition(State);
+ }
+ }
+}
+
+void MismatchedIteratorChecker::checkBeginFunction(CheckerContext &C) const {
+ // Copy container of iterator arguments to iterator parameters
+ auto State = C.getState();
+ const auto *LCtx = C.getLocationContext();
+
+ const auto *Site = cast<StackFrameContext>(LCtx)->getCallSite();
+ if (!Site)
+ return;
+
+ const auto *FD = dyn_cast<FunctionDecl>(LCtx->getDecl());
+ if (!FD)
+ 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 *const *Cont = getIteratorContainer(State, Arg);
+ if (!Cont)
+ continue;
+ State = setIteratorContainer(State, Param, *Cont);
+ Change = true;
+ }
+ if (Change) {
+ C.addTransition(State);
+ }
+}
+
+void MismatchedIteratorChecker::checkPostStmt(
+ const MaterializeTemporaryExpr *MTE, CheckerContext &C) const {
+ /* Transfer iterator container for to temporary objects */
+ auto State = C.getState();
+ const auto *LCtx = C.getLocationContext();
+ const auto *const *Cont = getIteratorContainer(
+ State, State->getSVal(MTE->GetTemporaryExpr(), LCtx));
+ if (!Cont)
+ return;
+ State = setIteratorContainer(State, State->getSVal(MTE, LCtx), *Cont);
+ C.addTransition(State);
+}
+
+void MismatchedIteratorChecker::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);
+ }
+ }
+}
+
+void MismatchedIteratorChecker::verifyMatch(CheckerContext &C, const SVal &Iter,
+ const MemRegion *Cont) const {
+ auto State = C.getState();
+ const auto *const *IterCont = getIteratorContainer(State, Iter);
+ if (IterCont && *IterCont != Cont) {
+ auto *N = C.generateNonFatalErrorNode(State);
+ if (!N) {
+ return;
+ }
+ reportMismatchedBug("Iterator access mismatched.", Iter, C, N);
+ }
+}
+
+void MismatchedIteratorChecker::verifyMatch(CheckerContext &C,
+ const SVal &Iter1,
+ const SVal &Iter2) const {
+ auto State = C.getState();
+ const auto *const *IterCont1 = getIteratorContainer(State, Iter1);
+ const auto *const *IterCont2 = getIteratorContainer(State, Iter2);
+ if (IterCont1 && IterCont2 && *IterCont1 != *IterCont2) {
+ // If I do not put a tag here, the comparison test will fail
+ static CheckerProgramPointTag Tag("MismatchedIteratorChecker",
+ "MismatchedIterator");
+ auto *N = C.generateNonFatalErrorNode(State, &Tag);
+ if (!N) {
+ return;
+ }
+ reportMismatchedBug("Iterator access mismatched.", Iter1, C, N);
+ }
+}
+
+void MismatchedIteratorChecker::handleBeginOrEnd(CheckerContext &C,
+ const SVal &RetVal,
+ const SVal &Cont) const {
+ const auto *ContReg = Cont.getAsRegion();
+ if (!ContReg)
+ return;
+
+ auto State = C.getState();
+ State = setIteratorContainer(State, RetVal, ContReg);
+ C.addTransition(State);
+}
+
+void MismatchedIteratorChecker::reportMismatchedBug(
+ const StringRef &Message, const SVal &Val, CheckerContext &C,
+ ExplodedNode *ErrNode) const {
+ auto R = llvm::make_unique<BugReport>(*MismatchedBugType, Message, ErrNode);
+ R->markInteresting(Val);
+ C.emitReport(std::move(R));
+}
+
+namespace {
+
+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, CopyA = true, Dest = false, PreIncr = false,
+ PostIncr = false, Deref = false;
+ for (const auto *M : CRD->methods()) {
+ if (const auto *C = dyn_cast<CXXConstructorDecl>(M)) {
+ if (C->isCopyConstructor()) {
+ CopyC = !C->isDeleted() && C->getAccess() == AS_public;
+ }
+ continue;
+ }
+ if (const auto *D = dyn_cast<CXXDestructorDecl>(M)) {
+ Dest = !D->isDeleted();
+ continue;
+ }
+ if (M->isCopyAssignmentOperator()) {
+ CopyA = !M->isDeleted() && M->getAccess() == AS_public;
+ 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 && CopyA && Dest && PreIncr && PostIncr && Deref;
+}
+
+static bool isComparisonOperator(OverloadedOperatorKind OK) {
+ return OK == OO_EqualEqual || OK == OO_ExclaimEqual || OK == OO_Less ||
+ OK == OO_LessEqual || OK == OO_Greater || OK == OO_GreaterEqual;
+}
+
+static bool isBeginOrEndCall(const FunctionDecl *Func) {
+ const auto *IdInfo = Func->getIdentifier();
+ if (!IdInfo)
+ return false;
+ return IdInfo->getName().endswith_lower("begin") ||
+ IdInfo->getName().endswith_lower("end");
+}
+
+static bool isInsertCall(const FunctionDecl *Func) {
+ const auto *IdInfo = Func->getIdentifier();
+ if (!IdInfo)
+ return false;
+ if (Func->getNumParams() < 2 || Func->getNumParams() > 3)
+ return false;
+ if (!isIteratorType(Func->getParamDecl(0)->getType()))
+ return false;
+ return IdInfo->getName() == "insert";
+}
+
+static bool isEraseCall(const FunctionDecl *Func) {
+ const auto *IdInfo = Func->getIdentifier();
+ if (!IdInfo)
+ return false;
+ if (Func->getNumParams() < 1 || Func->getNumParams() > 2)
+ return false;
+ if (!isIteratorType(Func->getParamDecl(0)->getType()))
+ return false;
+ if (Func->getNumParams() == 2 &&
+ !isIteratorType(Func->getParamDecl(1)->getType()))
+ return false;
+ return IdInfo->getName() == "erase";
+}
+
+static bool isEmplaceCall(const FunctionDecl *Func) {
+ const auto *IdInfo = Func->getIdentifier();
+ if (!IdInfo)
+ return false;
+ if (Func->getNumParams() < 2)
+ return false;
+ if (!isIteratorType(Func->getParamDecl(0)->getType()))
+ return false;
+ return IdInfo->getName() == "emplace";
+}
+
+static const MemRegion *const *getIteratorContainer(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 ProgramStateRef setIteratorContainer(ProgramStateRef State,
+ const SVal &Val,
+ const MemRegion *Cont) {
+ if (const auto Reg = Val.getAsRegion()) {
+ return State->set<IteratorRegionMap>(Reg, Cont);
+ } else if (const auto Sym = Val.getAsSymbol()) {
+ return State->set<IteratorSymbolMap>(Sym, Cont);
+ } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
+ return State->set<IteratorRegionMap>(LCVal->getRegion(), Cont);
+ }
+ return nullptr;
+}
+
+static ProgramStateRef removeIteratorContainer(ProgramStateRef State,
+ const SVal &Val) {
+ if (const auto Reg = Val.getAsRegion()) {
+ return State->remove<IteratorRegionMap>(Reg);
+ } else if (const auto Sym = Val.getAsSymbol()) {
+ return State->remove<IteratorSymbolMap>(Sym);
+ } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
+ return State->remove<IteratorRegionMap>(LCVal->getRegion());
+ }
+ return nullptr;
+}
+}
+
+void ento::registerMismatchedIteratorChecker(CheckerManager &Mgr) {
+ Mgr.registerChecker<MismatchedIteratorChecker>();
+}
Index: lib/StaticAnalyzer/Checkers/CMakeLists.txt
===================================================================
--- lib/StaticAnalyzer/Checkers/CMakeLists.txt
+++ lib/StaticAnalyzer/Checkers/CMakeLists.txt
@@ -48,6 +48,7 @@
MallocChecker.cpp
MallocOverflowSecurityChecker.cpp
MallocSizeofChecker.cpp
+ MismatchedIteratorChecker.cpp
MPI-Checker/MPIBugReporter.cpp
MPI-Checker/MPIChecker.cpp
MPI-Checker/MPIFunctionClassifier.cpp
Index: include/clang/StaticAnalyzer/Checkers/Checkers.td
===================================================================
--- include/clang/StaticAnalyzer/Checkers/Checkers.td
+++ include/clang/StaticAnalyzer/Checkers/Checkers.td
@@ -284,6 +284,10 @@
HelpText<"Check iterators used past end">,
DescFile<"IteratorPastEndChecker.cpp">;
+def MismatchedIteratorChecker : Checker<"MismatchedIterator">,
+ HelpText<"Check iterators used for the wrong container">,
+ DescFile<"MismatchedIteratorChecker.cpp">;
+
} // end: "alpha.cplusplus"
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
