baloghadamsoftware updated this revision to Diff 153308.
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/D32747
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
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<int> &L1,
+ const std::list<int> &L2) {
+ auto i0 = L1.cbegin();
+ L1 = L2;
+ *i0; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_copy_assign_operator_vector1(std::vector<int> &V1,
+ const std::vector<int> &V2) {
+ auto i0 = V1.cbegin();
+ V1 = V2;
+ *i0; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_copy_assign_operator_deque1(std::deque<int> &D1,
+ const std::deque<int> &D2) {
+ auto i0 = D1.cbegin();
+ D1 = D2;
+ *i0; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_copy_assign_operator_forward_list1(std::forward_list<int> &FL1,
+ const std::forward_list<int> &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<T> ilist);
+
+ void assign(size_type count, const T &value);
+ template <typename InputIterator >
+ void assign(InputIterator first, InputIterator last);
+ void assign(std::initializer_list<T> ilist);
+
void clear();
void push_back(const T &value);
@@ -301,8 +310,21 @@
list& operator=(list &&other);
list& operator=(std::initializer_list<T> ilist);
+ void assign(size_type count, const T &value);
+ template <typename InputIterator >
+ void assign(InputIterator first, InputIterator last);
+ void assign(std::initializer_list<T> ilist);
+
void clear();
+ void push_back(const T &value);
+ void push_back(T &&value);
+ void pop_back();
+
+ void push_front(const T &value);
+ void push_front(T &&value);
+ void pop_front();
+
iterator begin() { return iterator(_start); }
const_iterator begin() const { return const_iterator(_start); }
const_iterator cbegin() const { return const_iterator(_start); }
@@ -338,6 +360,15 @@
return size_t(_finish - _start);
}
+ deque& operator=(const deque &other);
+ deque& operator=(deque &&other);
+ deque& operator=(std::initializer_list<T> ilist);
+
+ void assign(size_type count, const T &value);
+ template <typename InputIterator >
+ void assign(InputIterator first, InputIterator last);
+ void assign(std::initializer_list<T> ilist);
+
void clear();
void push_back(const T &value);
@@ -351,11 +382,11 @@
T &operator[](size_t n) {
return _start[n];
}
-
+
const T &operator[](size_t n) const {
return _start[n];
}
-
+
iterator begin() { return iterator(_start); }
const_iterator begin() const { return const_iterator(_start); }
const_iterator cbegin() const { return const_iterator(_start); }
@@ -367,7 +398,7 @@
T& back() { return *(end() - 1); }
const T& back() const { return *(end() - 1); }
};
-
+
template<typename T>
class forward_list {
struct __item {
@@ -387,6 +418,15 @@
forward_list(forward_list &&other);
~forward_list();
+ forward_list& operator=(const forward_list &other);
+ forward_list& operator=(forward_list &&other);
+ forward_list& operator=(std::initializer_list<T> ilist);
+
+ void assign(size_type count, const T &value);
+ template <typename InputIterator >
+ void assign(InputIterator first, InputIterator last);
+ void assign(std::initializer_list<T> ilist);
+
void clear();
void push_front(const T &value);
Index: lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
===================================================================
--- lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
+++ lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
@@ -67,11 +67,14 @@
// a constraint which we later retrieve when doing an actual comparison.
#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;
@@ -85,34 +88,43 @@
// Container the iterator belongs to
const MemRegion *Cont;
+ // Whether iterator is valid
+ bool Valid;
+
// Abstract offset
const SymbolRef Offset;
- IteratorPosition(const MemRegion *C, SymbolRef Of)
- : Cont(C), Offset(Of) {}
+ IteratorPosition(const MemRegion *C, bool V, SymbolRef Of)
+ : Cont(C), Valid(V), Offset(Of) {}
public:
const MemRegion *getContainer() const { return Cont; }
+ bool isValid() const { return Valid; }
SymbolRef getOffset() const { return Offset; }
+ IteratorPosition invalidate() const {
+ return IteratorPosition(Cont, false, Offset);
+ }
+
static IteratorPosition getPosition(const MemRegion *C, SymbolRef Of) {
- return IteratorPosition(C, Of);
+ return IteratorPosition(C, true, Of);
}
IteratorPosition setTo(SymbolRef NewOf) const {
- return IteratorPosition(Cont, NewOf);
+ return IteratorPosition(Cont, Valid, NewOf);
}
bool operator==(const IteratorPosition &X) const {
- return Cont == X.Cont && Offset == X.Offset;
+ return Cont == X.Cont && Valid == X.Valid && Offset == X.Offset;
}
bool operator!=(const IteratorPosition &X) const {
- return Cont != X.Cont || Offset != X.Offset;
+ return Cont != X.Cont || Valid != X.Valid || Offset != X.Offset;
}
void Profile(llvm::FoldingSetNodeID &ID) const {
ID.AddPointer(Cont);
+ ID.AddInteger(Valid);
ID.Add(Offset);
}
};
@@ -187,9 +199,11 @@
eval::Assume> {
std::unique_ptr<BugType> OutOfRangeBugType;
+ std::unique_ptr<BugType> InvalidatedBugType;
void handleComparison(CheckerContext &C, const SVal &RetVal, const SVal &LVal,
const SVal &RVal, OverloadedOperatorKind Op) const;
+ void verifyAccess(CheckerContext &C, const SVal &Val) const;
void verifyDereference(CheckerContext &C, const SVal &Val) const;
void handleIncrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter,
bool Postfix) const;
@@ -204,17 +218,21 @@
const SVal &Cont) const;
void assignToContainer(CheckerContext &C, const Expr *CE, const SVal &RetVal,
const MemRegion *Cont) const;
+ void handleAssign(CheckerContext &C, const SVal &Cont) const;
void verifyRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op,
const SVal &RetVal, const SVal &LHS,
const SVal &RHS) const;
void reportOutOfRangeBug(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_InvalidatedIteratorChecker,
CK_NumCheckKinds
};
@@ -248,7 +266,9 @@
bool isIterator(const CXXRecordDecl *CRD);
bool isBeginCall(const FunctionDecl *Func);
bool isEndCall(const FunctionDecl *Func);
+bool isAssignmentOperator(OverloadedOperatorKind OK);
bool isSimpleComparisonOperator(OverloadedOperatorKind OK);
+bool isAccessOperator(OverloadedOperatorKind OK);
bool isDereferenceOperator(OverloadedOperatorKind OK);
bool isIncrementOperator(OverloadedOperatorKind OK);
bool isDecrementOperator(OverloadedOperatorKind OK);
@@ -287,6 +307,8 @@
const IteratorPosition &Pos1,
const IteratorPosition &Pos2,
bool Equal);
+ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State,
+ const MemRegion *Cont);
const ContainerData *getContainerData(ProgramStateRef State,
const MemRegion *Cont);
ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont,
@@ -299,16 +321,29 @@
OutOfRangeBugType.reset(
new BugType(this, "Iterator out of range", "Misuse of STL APIs"));
OutOfRangeBugType->setSuppressOnSink(true);
+ InvalidatedBugType.reset(
+ new BugType(this, "Iterator invalidated", "Misuse of STL APIs"));
+ InvalidatedBugType->setSuppressOnSink(true);
}
void IteratorChecker::checkPreCall(const CallEvent &Call,
CheckerContext &C) const {
- // Check for out of range access
+ // Check for out of range access or access of invalidated position and
+ // iterator mismatches
const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
if (!Func)
return;
if (Func->isOverloadedOperator()) {
+ if (ChecksEnabled[CK_InvalidatedIteratorChecker] &&
+ isAccessOperator(Func->getOverloadedOperator())) {
+ // Check for any kind of access of invalidated iterator positions
+ if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
+ verifyAccess(C, InstCall->getCXXThisVal());
+ } else {
+ verifyAccess(C, Call.getArgSVal(0));
+ }
+ }
if (ChecksEnabled[CK_IteratorRangeChecker] &&
isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) {
if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
@@ -346,7 +381,10 @@
if (Func->isOverloadedOperator()) {
const auto Op = Func->getOverloadedOperator();
- if (isSimpleComparisonOperator(Op)) {
+ if (isAssignmentOperator(Op)) {
+ const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call);
+ handleAssign(C, InstCall->getCXXThisVal());
+ } else if (isSimpleComparisonOperator(Op)) {
if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
handleComparison(C, Call.getReturnValue(), InstCall->getCXXThisVal(),
Call.getArgSVal(0), Op);
@@ -456,7 +494,7 @@
// FIXME: This solution is unreliable. It may happen that another checker
// subscribes to the pre-statement check of `CXXOperatorCallExpr`
// and adds a transition before us. The proper fix is to make the
- // CFG provide a `ConstructionContext` for the `CXXOperatorCallExpr`,
+ // CFG provide a `ConstructionContext` for the `CXXOperatorCallExpr`
// which would turn the corresponding `CFGStmt` element into a
// `CFGCXXRecordTypedCall` element, which will allow `ExprEngine` to
// foresee that the `begin()`/`end()` call constructs the object
@@ -623,6 +661,21 @@
}
}
+void IteratorChecker::verifyAccess(CheckerContext &C, const SVal &Val) const {
+ auto State = C.getState();
+ const auto *Pos = getIteratorPosition(State, Val);
+ if (Pos && !Pos->isValid()) {
+ // If I do not put a tag here, some invalidation tests will fail
+ static CheckerProgramPointTag Tag("InvalidatedIteratorChecker",
+ "InvalidatedIterator");
+ auto *N = C.generateNonFatalErrorNode(State, &Tag);
+ if (!N) {
+ return;
+ }
+ reportInvalidatedBug("Invalidated iterator accessed.", Val, C, N);
+ }
+}
+
void IteratorChecker::handleIncrement(CheckerContext &C, const SVal &RetVal,
const SVal &Iter, bool Postfix) const {
// Increment the symbolic expressions which represents the position of the
@@ -863,14 +916,42 @@
C.addTransition(State);
}
+void IteratorChecker::handleAssign(CheckerContext &C, const SVal &Cont) const {
+ const auto *ContReg = Cont.getAsRegion();
+ if (!ContReg)
+ return;
+
+ while (const auto *CBOR = ContReg->getAs<CXXBaseObjectRegion>()) {
+ ContReg = CBOR->getSuperRegion();
+ }
+
+ // Assignment of a new value to a container always invalidates all its
+ // iterators
+ auto State = C.getState();
+ const auto CData = getContainerData(State, ContReg);
+ if (CData) {
+ State = invalidateAllIteratorPositions(State, ContReg);
+ }
+
+ C.addTransition(State);
+}
+
void IteratorChecker::reportOutOfRangeBug(const StringRef &Message,
const SVal &Val, CheckerContext &C,
ExplodedNode *ErrNode) const {
auto R = llvm::make_unique<BugReport>(*OutOfRangeBugType, Message, ErrNode);
R->markInteresting(Val);
C.emitReport(std::move(R));
}
+void IteratorChecker::reportInvalidatedBug(const StringRef &Message,
+ const SVal &Val, CheckerContext &C,
+ ExplodedNode *ErrNode) const {
+ auto R = llvm::make_unique<BugReport>(*InvalidatedBugType, Message, ErrNode);
+ R->markInteresting(Val);
+ C.emitReport(std::move(R));
+}
+
namespace {
bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
@@ -946,10 +1027,17 @@
return IdInfo->getName().endswith_lower("end");
}
+bool isAssignmentOperator(OverloadedOperatorKind OK) { return OK == OO_Equal; }
+
bool isSimpleComparisonOperator(OverloadedOperatorKind OK) {
return OK == OO_EqualEqual || OK == OO_ExclaimEqual;
}
+bool isAccessOperator(OverloadedOperatorKind OK) {
+ return isDereferenceOperator(OK) || isIncrementOperator(OK) ||
+ isDecrementOperator(OK) || isRandomIncrOrDecrOperator(OK);
+}
+
bool isDereferenceOperator(OverloadedOperatorKind OK) {
return OK == OO_Star || OK == OO_Arrow || OK == OO_ArrowStar ||
OK == OO_Subscript;
@@ -1174,6 +1262,49 @@
return State;
}
+template <typename Condition, typename Process>
+ProgramStateRef processIteratorPositions(ProgramStateRef State, Condition Cond,
+ Process Proc) {
+ auto &RegionMapFactory = State->get_context<IteratorRegionMap>();
+ auto RegionMap = State->get<IteratorRegionMap>();
+ bool Changed = false;
+ for (const auto Reg : RegionMap) {
+ if (Cond(Reg.second)) {
+ RegionMap = RegionMapFactory.add(RegionMap, Reg.first, Proc(Reg.second));
+ Changed = true;
+ }
+ }
+
+ if (Changed)
+ State = State->set<IteratorRegionMap>(RegionMap);
+
+ auto &SymbolMapFactory = State->get_context<IteratorSymbolMap>();
+ auto SymbolMap = State->get<IteratorSymbolMap>();
+ Changed = false;
+ for (const auto Sym : SymbolMap) {
+ if (Cond(Sym.second)) {
+ SymbolMap = SymbolMapFactory.add(SymbolMap, Sym.first, Proc(Sym.second));
+ Changed = true;
+ }
+ }
+
+ if (Changed)
+ State = State->set<IteratorSymbolMap>(SymbolMap);
+
+ return State;
+}
+
+ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State,
+ const MemRegion *Cont) {
+ auto MatchCont = [&](const IteratorPosition &Pos) {
+ return Pos.getContainer() == Cont;
+ };
+ auto Invalidate = [&](const IteratorPosition &Pos) {
+ return Pos.invalidate();
+ };
+ return processIteratorPositions(State, MatchCont, Invalidate);
+}
+
bool isZero(ProgramStateRef State, const NonLoc &Val) {
auto &BVF = State->getBasicVals();
return compare(State, Val,
@@ -1246,4 +1377,4 @@
}
REGISTER_CHECKER(IteratorRangeChecker)
-
+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 InvalidatedIteratorChecker : Checker<"InvalidatedIterator">,
+ HelpText<"Check for use of invalidated iterators">,
+ DescFile<"IteratorChecker.cpp">;
+
def MisusedMovedObjectChecker: Checker<"MisusedMovedObject">,
HelpText<"Method calls on a moved-from object and copying a moved-from "
"object will be reported">,
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
