Index: include/clang/StaticAnalyzer/Checkers/Checkers.td =================================================================== --- include/clang/StaticAnalyzer/Checkers/Checkers.td +++ include/clang/StaticAnalyzer/Checkers/Checkers.td @@ -301,6 +301,10 @@ HelpText<"Check for iterators used outside their valid ranges">, DescFile<"IteratorChecker.cpp">; +def MismatchedIteratorChecker : Checker<"MismatchedIterator">, + HelpText<"Check for use of iterators of different containers where iterators of the same container are expected">, + DescFile<"IteratorChecker.cpp">; + def InvalidatedIteratorChecker : Checker<"InvalidatedIterator">, HelpText<"Check for use of invalidated iterators">, DescFile<"IteratorChecker.cpp">; Index: lib/StaticAnalyzer/Checkers/IteratorChecker.cpp =================================================================== --- lib/StaticAnalyzer/Checkers/IteratorChecker.cpp +++ lib/StaticAnalyzer/Checkers/IteratorChecker.cpp @@ -199,6 +199,7 @@ eval::Assume> { std::unique_ptr OutOfRangeBugType; + std::unique_ptr MismatchedBugType; std::unique_ptr InvalidatedBugType; void handleComparison(CheckerContext &C, const SVal &RetVal, const SVal &LVal, @@ -222,8 +223,13 @@ void verifyRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op, const SVal &RetVal, const SVal &LHS, const SVal &RHS) const; + void verifyMatch(CheckerContext &C, const SVal &Iter1, + const SVal &Iter2) 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; @@ -232,6 +238,7 @@ enum CheckKind { CK_IteratorRangeChecker, + CK_MismatchedIteratorChecker, CK_InvalidatedIteratorChecker, CK_NumCheckKinds }; @@ -321,6 +328,9 @@ OutOfRangeBugType.reset( new BugType(this, "Iterator out of range", "Misuse of STL APIs")); OutOfRangeBugType->setSuppressOnSink(true); + MismatchedBugType.reset( + new BugType(this, "Iterator(s) mismatched", "Misuse of STL APIs")); + MismatchedBugType->setSuppressOnSink(true); InvalidatedBugType.reset( new BugType(this, "Iterator invalidated", "Misuse of STL APIs")); InvalidatedBugType->setSuppressOnSink(true); @@ -369,6 +379,65 @@ verifyDereference(C, Call.getArgSVal(0)); } } + } else if (!isa(&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. + // + // Example: + // template + // void f(I1 first1, I1 last1, I2 first2, I2 last2); + // + // In this case the first two arguments to f() must be iterators must belong + // to the same container and the last to also to the same container but + // not neccessarily to the same as the first two. + + if (!ChecksEnabled[CK_MismatchedIteratorChecker]) + return; + + const auto *Templ = Func->getPrimaryTemplate(); + if (!Templ) + return; + + const auto *TParams = Templ->getTemplateParameters(); + const auto *TArgs = Func->getTemplateSpecializationArgs(); + + // Iterate over all the template parameters + for (auto i = 0U; i < TParams->size(); ++i) { + const auto *TPDecl = dyn_cast(TParams->getParam(i)); + if (!TPDecl) + continue; + + if (TPDecl->isParameterPack()) + continue; + + const auto TAType = TArgs->get(i).getAsType(); + if (!isIteratorType(TAType)) + continue; + + SVal LHS = UndefinedVal(); + + // For every template parameter which is an iterator type in the + // instantiation look for all functions parameters type by it and + // check whether they belong to the same container + for (auto j = 0U; j < Func->getNumParams(); ++j) { + const auto *Param = Func->getParamDecl(j); + const auto *ParamType = + Param->getType()->getAs(); + if (!ParamType || + ParamType->getReplacedParameter()->getDecl() != TPDecl) + continue; + if (LHS.isUndef()) { + LHS = Call.getArgSVal(j); + } else { + verifyMatch(C, LHS, Call.getArgSVal(j)); + } + } + } } } @@ -838,6 +907,24 @@ } } +void IteratorChecker::verifyMatch(CheckerContext &C, const SVal &Iter1, + const SVal &Iter2) const { + // Verify match between the containers of two iterators + auto State = C.getState(); + const auto *Pos1 = getIteratorPosition(State, Iter1); + const auto *Pos2 = getIteratorPosition(State, Iter2); + if (Pos1 && Pos2 && Pos1->getContainer() != Pos2->getContainer()) { + // 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 IteratorChecker::handleBegin(CheckerContext &C, const Expr *CE, const SVal &RetVal, const SVal &Cont) const { const auto *ContReg = Cont.getAsRegion(); @@ -935,6 +1022,14 @@ C.emitReport(std::move(R)); } +void IteratorChecker::reportMismatchedBug(const StringRef &Message, + const SVal &Val, CheckerContext &C, + ExplodedNode *ErrNode) const { + auto R = llvm::make_unique(*MismatchedBugType, Message, ErrNode); + R->markInteresting(Val); + C.emitReport(std::move(R)); +} + void IteratorChecker::reportInvalidatedBug(const StringRef &Message, const SVal &Val, CheckerContext &C, ExplodedNode *ErrNode) const { @@ -1350,4 +1445,5 @@ } REGISTER_CHECKER(IteratorRangeChecker) +REGISTER_CHECKER(MismatchedIteratorChecker) REGISTER_CHECKER(InvalidatedIteratorChecker) 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 @@ -642,6 +642,12 @@ template InputIterator find(InputIterator first, InputIterator last, const T &val); + template + ForwardIterator1 find_first_of(ForwardIterator1 first1, + ForwardIterator1 last1, + ForwardIterator2 first2, + ForwardIterator2 last2); + template OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result); Index: test/Analysis/mismatched-iterator.cpp =================================================================== --- /dev/null +++ test/Analysis/mismatched-iterator.cpp @@ -0,0 +1,25 @@ +// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.MismatchedIterator -analyzer-eagerly-assume -analyzer-config aggressive-relational-comparison-simplification=true -analyzer-config c++-container-inlining=false %s -verify +// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.MismatchedIterator -analyzer-eagerly-assume -analyzer-config aggressive-relational-comparison-simplification=true -analyzer-config c++-container-inlining=true -DINLINE=1 %s -verify + +#include "Inputs/system-header-simulator-cxx.h" + +void good_find(std::vector &v, int n) { + std::find(v.cbegin(), v.cend(), n); // no-warning +} + +void good_find_first_of(std::vector &v1, std::vector &v2) { + std::find_first_of(v1.cbegin(), v1.cend(), v2.cbegin(), v2.cend()); // no-warning +} + +void good_copy(std::vector &v1, std::vector &v2, int n) { + std::copy(v1.cbegin(), v1.cend(), v2.begin()); // no-warning +} + +void bad_find(std::vector &v1, std::vector &v2, int n) { + std::find(v1.cbegin(), v2.cend(), n); // expected-warning{{Iterator access mismatched}} +} + +void bad_find_first_of(std::vector &v1, std::vector &v2) { + std::find_first_of(v1.cbegin(), v2.cend(), v2.cbegin(), v2.cend()); // expected-warning{{Iterator access mismatched}} + std::find_first_of(v1.cbegin(), v1.cend(), v2.cbegin(), v1.cend()); // expected-warning{{Iterator access mismatched}} +}