baloghadamsoftware updated this revision to Diff 153481.
baloghadamsoftware added a comment.
Previous rebase was wrong, this is the correct one.
https://reviews.llvm.org/D32845
Files:
include/clang/StaticAnalyzer/Checkers/Checkers.td
lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
test/Analysis/Inputs/system-header-simulator-cxx.h
test/Analysis/mismatched-iterator.cpp
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<int> &v, int n) {
+ std::find(v.cbegin(), v.cend(), n); // no-warning
+}
+
+void good_find_first_of(std::vector<int> &v1, std::vector<int> &v2) {
+ std::find_first_of(v1.cbegin(), v1.cend(), v2.cbegin(), v2.cend()); // no-warning
+}
+
+void good_copy(std::vector<int> &v1, std::vector<int> &v2, int n) {
+ std::copy(v1.cbegin(), v1.cend(), v2.begin()); // no-warning
+}
+
+void bad_find(std::vector<int> &v1, std::vector<int> &v2, int n) {
+ std::find(v1.cbegin(), v2.cend(), n); // expected-warning{{Iterator access mismatched}}
+}
+
+void bad_find_first_of(std::vector<int> &v1, std::vector<int> &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}}
+}
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 <class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T &val);
+ template <class ForwardIterator1, class ForwardIterator2>
+ ForwardIterator1 find_first_of(ForwardIterator1 first1,
+ ForwardIterator1 last1,
+ ForwardIterator2 first2,
+ ForwardIterator2 last2);
+
template <class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator first, InputIterator last,
OutputIterator result);
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<BugType> OutOfRangeBugType;
+ std::unique_ptr<BugType> MismatchedBugType;
std::unique_ptr<BugType> InvalidatedBugType;
void handleComparison(CheckerContext &C, const SVal &RetVal, const SVal &LVal,
@@ -222,16 +223,23 @@
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 &Val1,
+ const SVal &Val2, CheckerContext &C,
+ ExplodedNode *ErrNode) const;
void reportInvalidatedBug(const StringRef &Message, const SVal &Val,
CheckerContext &C, ExplodedNode *ErrNode) const;
public:
IteratorChecker();
enum CheckKind {
CK_IteratorRangeChecker,
+ CK_MismatchedIteratorChecker,
CK_InvalidatedIteratorChecker,
CK_NumCheckKinds
};
@@ -321,6 +329,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 +380,65 @@
verifyDereference(C, Call.getArgSVal(0));
}
}
+ } 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.
+ //
+ // Example:
+ // template<typename I1, typename I2>
+ // 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 (size_t i = 0; i < TParams->size(); ++i) {
+ const auto *TPDecl = dyn_cast<TemplateTypeParmDecl>(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<SubstTemplateTypeParmType>();
+ if (!ParamType ||
+ ParamType->getReplacedParameter()->getDecl() != TPDecl)
+ continue;
+ if (LHS.isUndef()) {
+ LHS = Call.getArgSVal(j);
+ } else {
+ verifyMatch(C, LHS, Call.getArgSVal(j));
+ }
+ }
+ }
}
}
@@ -847,6 +917,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, Iter2, C, N);
+ }
+}
+
void IteratorChecker::handleBegin(CheckerContext &C, const Expr *CE,
const SVal &RetVal, const SVal &Cont) const {
const auto *ContReg = Cont.getAsRegion();
@@ -944,6 +1032,16 @@
C.emitReport(std::move(R));
}
+void IteratorChecker::reportMismatchedBug(const StringRef &Message,
+ const SVal &Val1, const SVal &Val2,
+ CheckerContext &C,
+ ExplodedNode *ErrNode) const {
+ auto R = llvm::make_unique<BugReport>(*MismatchedBugType, Message, ErrNode);
+ R->markInteresting(Val1);
+ R->markInteresting(Val2);
+ C.emitReport(std::move(R));
+}
+
void IteratorChecker::reportInvalidatedBug(const StringRef &Message,
const SVal &Val, CheckerContext &C,
ExplodedNode *ErrNode) const {
@@ -1377,4 +1475,5 @@
}
REGISTER_CHECKER(IteratorRangeChecker)
+REGISTER_CHECKER(MismatchedIteratorChecker)
REGISTER_CHECKER(InvalidatedIteratorChecker)
Index: include/clang/StaticAnalyzer/Checkers/Checkers.td
===================================================================
--- include/clang/StaticAnalyzer/Checkers/Checkers.td
+++ include/clang/StaticAnalyzer/Checkers/Checkers.td
@@ -314,6 +314,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">;
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
