[PATCH] D32845: [Analyzer] Iterator Checker - Part 4: Mismatched iterator checker for function parameters
This revision was automatically updated to reflect the committed changes.
baloghadamsoftware marked an inline comment as done.
Closed by commit rC341790: [Analyzer] Iterator Checker - Part 4: Mismatched
iterator checker for function… (authored by baloghadamsoftware, committed by ).
Changed prior to commit:
https://reviews.llvm.org/D32845?vs=163671&id=164631#toc
Repository:
rC Clang
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/invalidated-iterator.cpp
Index: lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
===
--- lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
+++ lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
@@ -198,6 +198,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,
@@ -221,16 +222,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
};
@@ -312,14 +320,19 @@
ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont,
const ContainerData &CData);
bool hasLiveIterators(ProgramStateRef State, const MemRegion *Cont);
+bool isBoundThroughLazyCompoundVal(const Environment &Env,
+ const MemRegion *Reg);
bool isOutOfRange(ProgramStateRef State, const IteratorPosition &Pos);
bool isZero(ProgramStateRef State, const NonLoc &Val);
} // namespace
IteratorChecker::IteratorChecker() {
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);
@@ -368,6 +381,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 (size_t I = 0; 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
[PATCH] D32845: [Analyzer] Iterator Checker - Part 4: Mismatched iterator checker for function parameters
baloghadamsoftware marked 3 inline comments as done.
baloghadamsoftware added inline comments.
Comment at: include/clang/StaticAnalyzer/Checkers/Checkers.td:317
+def MismatchedIteratorChecker : Checker<"MismatchedIterator">,
+ HelpText<"Check for use of iterators of different containers where iterators
of the same container are expected">,
whisperity wrote:
> Is there any particular order entries of this file should be in? Seems to be
> broken now, but I guess when this patch comes up to the top of the stack it
> shall be fixed at a rebase.
Alphabetical order. Now it seems to be OK.
Comment at: lib/StaticAnalyzer/Checkers/IteratorChecker.cpp:382
}
+ } else if (!isa(&Call)) {
+// The main purpose of iterators is to abstract away from different
baloghadamsoftware wrote:
> a.sidorin wrote:
> > The function becomes > 100 lines long. Should we refactor this check into a
> > separate function to improve readability?
> Yes, I think so this would be a good idea. Should I do it now?
I propose to refactor it later in a separate patch.
https://reviews.llvm.org/D32845
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D32845: [Analyzer] Iterator Checker - Part 4: Mismatched iterator checker for function parameters
baloghadamsoftware updated this revision to Diff 163671.
baloghadamsoftware added a comment.
Minor changes.
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/invalidated-iterator.cpp
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-config aggressive-binary-operation-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-config aggressive-binary-operation-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{{Iterators of different containers used where the same container is expected}}
+}
+
+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{{Iterators of different containers used where the same container is expected}}
+ std::find_first_of(v1.cbegin(), v1.cend(), v2.cbegin(), v1.cend()); // expected-warning{{Iterators of different containers used where the same container is expected}}
+}
Index: test/Analysis/invalidated-iterator.cpp
===
--- test/Analysis/invalidated-iterator.cpp
+++ test/Analysis/invalidated-iterator.cpp
@@ -1,5 +1,5 @@
-// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.InvalidatedIterator -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.InvalidatedIterator -analyzer-config aggressive-relational-comparison-simplification=true -analyzer-config c++-container-inlining=true -DINLINE=1 %s -verify
+// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.InvalidatedIterator -analyzer-config aggressive-binary-operation-simplification=true -analyzer-config c++-container-inlining=false %s -verify
+// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.InvalidatedIterator -analyzer-config aggressive-binary-operation-simplification=true -analyzer-config c++-container-inlining=true -DINLINE=1 %s -verify
#include "Inputs/system-header-simulator-cxx.h"
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: lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
===
--- lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
+++ lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
@@ -198,6 +198,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,
@@ -221,16 +222,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 reportM
[PATCH] D32845: [Analyzer] Iterator Checker - Part 4: Mismatched iterator checker for function parameters
baloghadamsoftware updated this revision to Diff 163517.
baloghadamsoftware removed a reviewer: george.karpenkov.
baloghadamsoftware added a comment.
Herald added a reviewer: george.karpenkov.
Since https://reviews.llvm.org/rL338263 fixed a bug in the cleanup phase the
tests for mismatched iterator checker did not pass. The reason for this is that
the region of some `LazyCompoundVal`s are cleaned up while there are still
iterator positions connected to the `LazyCompoundVal` itself. This happens
typically for arguments which are constructed in-place (e.g. `begin()` or
`end()` of a container is invoked in the argument itself).
We applied a fix here that defers cleanup of such iterator positions. No other
solution comes to my mind at the moment.
I wanted to upload this fix in a separate patch but I could not create tests
for it.
@NoQ please review this fix before I commit the patch.
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/invalidated-iterator.cpp
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-config aggressive-binary-operation-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-config aggressive-binary-operation-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{{Iterators of different containers used where the same container is expected}}
+}
+
+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{{Iterators of different containers used where the same container is expected}}
+ std::find_first_of(v1.cbegin(), v1.cend(), v2.cbegin(), v1.cend()); // expected-warning{{Iterators of different containers used where the same container is expected}}
+}
Index: test/Analysis/invalidated-iterator.cpp
===
--- test/Analysis/invalidated-iterator.cpp
+++ test/Analysis/invalidated-iterator.cpp
@@ -1,5 +1,5 @@
-// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.InvalidatedIterator -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.InvalidatedIterator -analyzer-config aggressive-relational-comparison-simplification=true -analyzer-config c++-container-inlining=true -DINLINE=1 %s -verify
+// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.InvalidatedIterator -analyzer-config aggressive-binary-operation-simplification=true -analyzer-config c++-container-inlining=false %s -verify
+// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.InvalidatedIterator -analyzer-config aggressive-binary-operation-simplification=true -analyzer-config c++-container-inlining=true -DINLINE=1 %s -verify
#include "Inputs/system-header-simulator-cxx.h"
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: lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
===
--- lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
+++ lib
[PATCH] D32845: [Analyzer] Iterator Checker - Part 4: Mismatched iterator checker for function parameters
NoQ accepted this revision. NoQ added a comment. This revision is now accepted and ready to land. Herald added a subscriber: Szelethus. Looks good. I guess we may have to tone down the heuristic about "all template functions" if we see it fail. @a.sidorin and @whisperity have some valid minor comments. https://reviews.llvm.org/D32845 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D32845: [Analyzer] Iterator Checker - Part 4: Mismatched iterator checker for function parameters
baloghadamsoftware added inline comments. Comment at: lib/StaticAnalyzer/Checkers/IteratorChecker.cpp:388 +// 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. baloghadamsoftware wrote: > a.sidorin wrote: > > While this assumption is sane and is true for functions, user > > code can have other design solutions. There is nothing that prevents users > > from writing a function looking like: > > ``` > > template > > void f(IterTy FromBegin, IterTy FromEnd, IterTy ToBegin, IterTy ToEnd); > > ``` > > and there is nothing wrong with it. > > One of possible solutions is to restrict checker to check only functions > > from std namespace. What do you think? > We can restrict, of course, but first we should measure how it performs on > real code. With the restriction, we can get rid of some false positives but > we may also loose some true positives. One more thing: The main purpose of iterators is to make algorithms independent of the data representation. So you can decide whether your algorithm works on a specific representation and create non-template function that takes reference for the specific container itself or you make it generic so you use template function which takes iterators. If you chose this latter one for an algorithm that works on two different container then there is no point to restrict the function to only work on two containers with exactly the same representation. Either specific or generic, but there is no point for something in between. https://reviews.llvm.org/D32845 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D32845: [Analyzer] Iterator Checker - Part 4: Mismatched iterator checker for function parameters
whisperity added inline comments.
Comment at: include/clang/StaticAnalyzer/Checkers/Checkers.td:317
+def MismatchedIteratorChecker : Checker<"MismatchedIterator">,
+ HelpText<"Check for use of iterators of different containers where iterators
of the same container are expected">,
Is there any particular order entries of this file should be in? Seems to be
broken now, but I guess when this patch comes up to the top of the stack it
shall be fixed at a rebase.
Comment at: lib/StaticAnalyzer/Checkers/IteratorChecker.cpp:426
+ // 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
functions' parameters' ?
Comment at: lib/StaticAnalyzer/Checkers/IteratorChecker.cpp:934
+}
+reportMismatchedBug("Iterator access mismatched.", Iter1, Iter2, C, N);
+ }
If this string is the message that gets printed to the user, I think it must be
rephrased a bit. If this message came across me, I'd be puzzled at first to
understand what it is trying to mean.
https://reviews.llvm.org/D32845
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D32845: [Analyzer] Iterator Checker - Part 4: Mismatched iterator checker for function parameters
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 &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}}
+}
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: 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,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(&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 functio
[PATCH] D32845: [Analyzer] Iterator Checker - Part 4: Mismatched iterator checker for function parameters
baloghadamsoftware updated this revision to Diff 153314.
baloghadamsoftware added a comment.
Herald added a reviewer: george.karpenkov.
Herald added a subscriber: mikhail.ramalho.
Rebased to https://reviews.llvm.org/rL335835.
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/diagnostics/explicit-suppression.cpp
test/Analysis/invalidated-iterator.cpp
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 &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}}
+}
Index: test/Analysis/invalidated-iterator.cpp
===
--- /dev/null
+++ test/Analysis/invalidated-iterator.cpp
@@ -0,0 +1,32 @@
+// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.InvalidatedIterator -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.InvalidatedIterator -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 bad_copy_assign_operator_list1(std::list &L1,
+const std::list &L2) {
+ auto i0 = L1.cbegin();
+ L1 = L2;
+ *i0; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_copy_assign_operator_vector1(std::vector &V1,
+ const std::vector &V2) {
+ auto i0 = V1.cbegin();
+ V1 = V2;
+ *i0; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_copy_assign_operator_deque1(std::deque &D1,
+ const std::deque &D2) {
+ auto i0 = D1.cbegin();
+ D1 = D2;
+ *i0; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_copy_assign_operator_forward_list1(std::forward_list &FL1,
+const std::forward_list &FL2) {
+ auto i0 = FL1.cbegin();
+ FL1 = FL2;
+ *i0; // expected-warning{{Invalidated iterator accessed}}
+}
Index: test/Analysis/diagnostics/explicit-suppression.cpp
===
--- test/Analysis/diagnostics/explicit-suppression.cpp
+++ test/Analysis/diagnostics/explicit-suppression.cpp
@@ -19,6 +19,6 @@
void testCopyNull(C *I, C *E) {
std::copy(I, E, (C *)0);
#ifndef SUPPRESSED
- // expected-warning@../Inputs/system-header-simulator-cxx.h:514 {{Called C++ object pointer is null}}
+ // expected-warning@../Inputs/system-header-simulator-cxx.h:554 {{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
@@ -252,6 +252,15 @@
return size_t(_finish - _start);
}
+vector& operator=(const vector &other);
+vector& operator=(vector &&other);
+vector& operator=(std::initializer_list ilist);
+
+void assign(size_type count, const T &value);
+template
+void assign(InputIterator first, InputIterator last);
+void assign(std::initi
[PATCH] D32845: [Analyzer] Iterator Checker - Part 4: Mismatched iterator checker for function parameters
baloghadamsoftware updated this revision to Diff 130174.
baloghadamsoftware marked an inline comment as done.
baloghadamsoftware added a comment.
Updated according to some comments.
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 &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}}
+}
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: 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,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(&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 a
[PATCH] D32845: [Analyzer] Iterator Checker - Part 4: Mismatched iterator checker for function parameters
baloghadamsoftware marked an inline comment as done.
baloghadamsoftware added inline comments.
Comment at: lib/StaticAnalyzer/Checkers/IteratorChecker.cpp:382
}
+ } else if (!isa(&Call)) {
+// The main purpose of iterators is to abstract away from different
a.sidorin wrote:
> The function becomes > 100 lines long. Should we refactor this check into a
> separate function to improve readability?
Yes, I think so this would be a good idea. Should I do it now?
Comment at: lib/StaticAnalyzer/Checkers/IteratorChecker.cpp:388
+// 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.
a.sidorin wrote:
> While this assumption is sane and is true for functions, user
> code can have other design solutions. There is nothing that prevents users
> from writing a function looking like:
> ```
> template
> void f(IterTy FromBegin, IterTy FromEnd, IterTy ToBegin, IterTy ToEnd);
> ```
> and there is nothing wrong with it.
> One of possible solutions is to restrict checker to check only functions
> from std namespace. What do you think?
We can restrict, of course, but first we should measure how it performs on real
code. With the restriction, we can get rid of some false positives but we may
also loose some true positives.
https://reviews.llvm.org/D32845
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D32845: [Analyzer] Iterator Checker - Part 4: Mismatched iterator checker for function parameters
a.sidorin added a comment.
Hello Adam,
This looks like a nice improvement. I have some remarks inline.
Comment at: lib/StaticAnalyzer/Checkers/IteratorChecker.cpp:382
}
+ } else if (!isa(&Call)) {
+// The main purpose of iterators is to abstract away from different
The function becomes > 100 lines long. Should we refactor this check into a
separate function to improve readability?
Comment at: lib/StaticAnalyzer/Checkers/IteratorChecker.cpp:388
+// 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.
While this assumption is sane and is true for functions, user code
can have other design solutions. There is nothing that prevents users from
writing a function looking like:
```
template
void f(IterTy FromBegin, IterTy FromEnd, IterTy ToBegin, IterTy ToEnd);
```
and there is nothing wrong with it.
One of possible solutions is to restrict checker to check only functions from
std namespace. What do you think?
Comment at: lib/StaticAnalyzer/Checkers/IteratorChecker.cpp:410
+// Iterate over all the template parameters
+for (auto i = 0U; i < TParams->size(); ++i) {
+ const auto *TPDecl =
dyn_cast(TParams->getParam(i));
size_t I = 0?
Comment at: lib/StaticAnalyzer/Checkers/IteratorChecker.cpp:924
+}
+reportMismatchedBug("Iterator access mismatched.", Iter1, C, N);
+ }
We always report about first iterator, but the mismatched one can be second. I
think this deserves a FIXME, at least.
Comment at: lib/StaticAnalyzer/Checkers/IteratorChecker.cpp:1025
+void IteratorChecker::reportMismatchedBug(const StringRef &Message,
+ const SVal &Val, CheckerContext &C,
We usually pass StringRefs and SVals by value because they're very cheap for
copying. However, the surrounding code follows the same conventions so it's not
strongly required to change.
https://reviews.llvm.org/D32845
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D32845: [Analyzer] Iterator Checker - Part 4: Mismatched iterator checker for function parameters
baloghadamsoftware updated this revision to Diff 129871.
baloghadamsoftware added a comment.
Rebased to current Part 3. Comment added.
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 &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}}
+}
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: 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,16 +223,22 @@
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;
public:
IteratorChecker();
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 iterato
[PATCH] D32845: [Analyzer] Iterator Checker - Part 4: Mismatched iterator checker for function parameters
NoQ added inline comments. Herald added subscribers: a.sidorin, rnkovacs, szepet. Comment at: lib/StaticAnalyzer/Checkers/IteratorChecker.cpp:340-358 +const auto *Templ = Func->getPrimaryTemplate(); +if (!Templ) + return; + +const auto *TParams = Templ->getTemplateParameters(); +const auto *TArgs = Func->getTemplateSpecializationArgs(); + Could you add more comments on how this machinery works, probably with examples? https://reviews.llvm.org/D32845 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
