baloghadamsoftware created this revision.
baloghadamsoftware added reviewers: zaks.anna, NoQ.
baloghadamsoftware added subscribers: xazax.hun, o.gyorgy, cfe-commits.
This patch fixes some issues for the IteratorPastEnd checkers. There are
basically two main issues this patch targets: one is the handling of
assignments between iterators, the other one is correct handling of the +, +=,
- and -= operators of random-access iterators. The handling of these operators
also checks the sign of the argument, e.g. a negative number for + or += is
handled as decrementation.
https://reviews.llvm.org/D28771
Files:
lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp
test/Analysis/Inputs/system-header-simulator-cxx.h
test/Analysis/diagnostics/explicit-suppression.cpp
test/Analysis/iterator-past-end.cpp
Index: test/Analysis/iterator-past-end.cpp
===================================================================
--- test/Analysis/iterator-past-end.cpp
+++ test/Analysis/iterator-past-end.cpp
@@ -203,3 +203,49 @@
start = ++item; // no-warning
}
}
+
+void good_overwrite(std::vector<int> &vec) {
+ auto i = vec.end();
+ i = vec.begin();
+ *i; // no-warning
+}
+
+void good_overwrite_find(std::vector<int> &vec, int e) {
+ auto i = std::find(vec.begin(), vec.end(), e);
+ if(i == vec.end()) {
+ i = vec.begin();
+ }
+ *i; // no-warning
+}
+
+void bad_overwrite(std::vector<int> &vec) {
+ auto i = vec.begin();
+ i = vec.end();
+ *i; // expected-warning{{Iterator accessed past its end}}
+}
+
+void bad_overwrite_find(std::vector<int> &vec, int e) {
+ auto i = std::find(vec.begin(), vec.end(), e);
+ if(i != vec.end()) {
+ i = vec.begin();
+ }
+ *i; // expected-warning{{Iterator accessed past its end}}
+}
+
+void good_advance(std::vector<int> &vec) {
+ auto i = vec.end();
+ std::advance(i, -1);
+ *i; // no-warning
+}
+
+void good_prev(std::vector<int> &vec) {
+ auto i = std::prev(vec.end());
+ *i; // no-warning
+}
+
+struct init_value_prev {
+ init_value_prev(std::list<int> l) : Back(std::prev(l.end())), Item(*Back) {} // no-warning
+private:
+ std::list<int>::iterator Back;
+ int Item;
+};
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:293 {{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
@@ -8,18 +8,60 @@
typedef unsigned char uint8_t;
typedef __typeof__(sizeof(int)) size_t;
+typedef __typeof__((char*)0-(char*)0) ptrdiff_t;
void *memmove(void *s1, const void *s2, size_t n);
-template <typename T, typename Ptr, typename Ref> struct __iterator {
- typedef __iterator<T, T *, T &> iterator;
- typedef __iterator<T, const T *, const T &> const_iterator;
+namespace std {
+ struct input_iterator_tag { };
+ struct output_iterator_tag { };
+ struct forward_iterator_tag : public input_iterator_tag { };
+ struct bidirectional_iterator_tag : public forward_iterator_tag { };
+ struct random_access_iterator_tag : public bidirectional_iterator_tag { };
+
+ template <typename Iterator> struct iterator_traits {
+ typedef typename Iterator::difference_type difference_type;
+ typedef typename Iterator::value_type value_type;
+ typedef typename Iterator::pointer pointer;
+ typedef typename Iterator::reference reference;
+ typedef typename Iterator::iterator_category iterator_category;
+ };
+}
- __iterator(const Ptr p) : ptr(p) {}
+template <typename T, typename Ptr, typename Ref> struct __vector_iterator {
+ typedef __vector_iterator<T, T *, T &> iterator;
+ typedef __vector_iterator<T, const T *, const T &> const_iterator;
+
+ typedef ptrdiff_t difference_type;
+ typedef T value_type;
+ typedef Ptr pointer;
+ typedef Ref reference;
+ typedef std::random_access_iterator_tag iterator_category;
+
+ __vector_iterator(const Ptr p) : ptr(p) {}
+ __vector_iterator<T, Ptr, Ref> operator++() { ++ ptr; return *this; }
+ __vector_iterator<T, Ptr, Ref> operator++(int) {
+ auto tmp = *this;
+ ++ ptr;
+ return tmp;
+ }
+ __vector_iterator<T, Ptr, Ref> operator--() { -- ptr; return *this; }
+ __vector_iterator<T, Ptr, Ref> operator--(int) {
+ auto tmp = *this; -- ptr;
+ return tmp;
+ }
+ __vector_iterator<T, Ptr, Ref> operator+(difference_type n) {
+ return ptr + n;
+ }
+ __vector_iterator<T, Ptr, Ref> operator-(difference_type n) {
+ return ptr - n;
+ }
+ __vector_iterator<T, Ptr, Ref> operator+=(difference_type n) {
+ return ptr += n;
+ }
+ __vector_iterator<T, Ptr, Ref> operator-=(difference_type n) {
+ return ptr -= n;
+ }
- __iterator<T, Ptr, Ref> operator++() { return *this; }
- __iterator<T, Ptr, Ref> operator++(int) { return *this; }
- __iterator<T, Ptr, Ref> operator--() { return *this; }
- __iterator<T, Ptr, Ref> operator--(int) { return *this; }
Ref operator*() const { return *ptr; }
Ptr operator->() const { return *ptr; }
@@ -33,7 +75,45 @@
Ptr ptr;
};
+template <typename T, typename Ptr, typename Ref> struct __list_iterator {
+ typedef __vector_iterator<T, __typeof__(T::data) *, __typeof__(T::data) &> iterator;
+ typedef __vector_iterator<T, const __typeof__(T::data) *, const __typeof__(T::data) &> const_iterator;
+
+ typedef ptrdiff_t difference_type;
+ typedef T value_type;
+ typedef Ptr pointer;
+ typedef Ref reference;
+ typedef std::bidirectional_iterator_tag iterator_category;
+
+ __list_iterator(T* it) : item(it) {}
+ __list_iterator<T, Ptr, Ref> operator++() { item = item->next; return *this; }
+ __list_iterator<T, Ptr, Ref> operator++(int) {
+ auto tmp = *this;
+ item = item->next;
+ return tmp;
+ }
+ __list_iterator<T, Ptr, Ref> operator--() { item = item->prev; return *this; }
+ __list_iterator<T, Ptr, Ref> operator--(int) {
+ auto tmp = *this;
+ item = item->prev;
+ return tmp;
+ }
+
+ Ref operator*() const { return item->data; }
+ Ptr operator->() const { return item->data; }
+
+ bool operator==(const iterator &rhs) const { return item == rhs->item; }
+ bool operator==(const const_iterator &rhs) const { return item == rhs->item; }
+
+ bool operator!=(const iterator &rhs) const { return item != rhs->item; }
+ bool operator!=(const const_iterator &rhs) const { return item != rhs->item; }
+
+private:
+ T* item;
+};
+
namespace std {
+
template <class T1, class T2>
struct pair {
T1 first;
@@ -50,13 +130,13 @@
template<typename T>
class vector {
- typedef __iterator<T, T *, T &> iterator;
- typedef __iterator<T, const T *, const T &> const_iterator;
-
T *_start;
T *_finish;
T *_end_of_storage;
public:
+ typedef __vector_iterator<T, T *, T &> iterator;
+ typedef __vector_iterator<T, const T *, const T &> const_iterator;
+
vector() : _start(0), _finish(0), _end_of_storage(0) {}
~vector();
@@ -81,6 +161,28 @@
const_iterator end() const { return const_iterator(_finish); }
};
+ template<typename T>
+ class list {
+ struct __item {
+ T data;
+ __item *prev, *next;
+ } *_start, *_finish;
+ public:
+ typedef __list_iterator<__item, T *, T &> iterator;
+ typedef __list_iterator<__item, const T *, const T &> const_iterator;
+
+ list() : _start(0), _finish(0) {}
+ ~list();
+
+ void push_back();
+ T pop_back();
+
+ iterator begin() { return iterator(_start); }
+ const_iterator begin() const { return const_iterator(_start); }
+ iterator end() { return iterator(_finish); }
+ const_iterator end() const { return const_iterator(_finish); }
+ };
+
class exception {
public:
exception() throw();
@@ -247,6 +349,34 @@
OutputIter copy_backward(InputIter II, InputIter IE, OutputIter OI) {
return __copy_backward(II, IE, OI);
}
+}
+
+template <class BidirectionalIterator, class Distance>
+void __advance (BidirectionalIterator& it, Distance n,
+ std::bidirectional_iterator_tag) {
+ if (n >= 0) while(n-- > 0) ++it; else while (n++<0) --it;
+}
+
+template <class RandomAccessIterator, class Distance>
+void __advance (RandomAccessIterator& it, Distance n,
+ std::random_access_iterator_tag) {
+ it += n;
+}
+
+namespace std {
+ template <class InputIterator, class Distance>
+ void advance (InputIterator& it, Distance n) {
+ __advance(it, n, typename InputIterator::iterator_category());
+ }
+
+ template <class BidirectionalIterator>
+ BidirectionalIterator
+ prev (BidirectionalIterator it,
+ typename iterator_traits<BidirectionalIterator>::difference_type n =
+ 1) {
+ advance(it, -n);
+ return it;
+ }
template <class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T &val);
@@ -277,12 +407,6 @@
ForwardIterator1 search_n(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);
- struct input_iterator_tag { };
- struct output_iterator_tag { };
- struct forward_iterator_tag : public input_iterator_tag { };
- struct bidirectional_iterator_tag : public forward_iterator_tag { };
- struct random_access_iterator_tag : public bidirectional_iterator_tag { };
-
}
void* operator new(std::size_t, const std::nothrow_t&) throw();
Index: lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp
===================================================================
--- lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp
+++ lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp
@@ -72,19 +72,25 @@
check::PostStmt<CXXConstructExpr>, check::PostStmt<DeclStmt>,
check::PostStmt<MaterializeTemporaryExpr>, check::BeginFunction,
check::DeadSymbols, eval::Assume, eval::Call> {
- mutable IdentifierInfo *II_find = nullptr,
- *II_find_end = nullptr, *II_find_first_of = nullptr,
- *II_find_if = nullptr, *II_find_if_not = nullptr,
- *II_lower_bound = nullptr, *II_upper_bound = nullptr,
- *II_search = nullptr, *II_search_n = nullptr;
+ mutable IdentifierInfo *II_find = nullptr, *II_find_end = nullptr,
+ *II_find_first_of = nullptr, *II_find_if = nullptr,
+ *II_find_if_not = nullptr, *II_lower_bound = nullptr,
+ *II_upper_bound = nullptr, *II_search = nullptr,
+ *II_search_n = nullptr;
std::unique_ptr<BugType> PastEndBugType;
void handleComparison(CheckerContext &C, const SVal &RetVal, const SVal &LVal,
const SVal &RVal, OverloadedOperatorKind Op) const;
+ void handleRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op,
+ const SVal &RetVal, const SVal &LVal,
+ const SVal &RVal, QualType RValType,
+ bool PreCheck) const;
void handleAccess(CheckerContext &C, const SVal &Val) const;
void handleDecrement(CheckerContext &C, const SVal &Val) const;
void handleEnd(CheckerContext &C, const SVal &RetVal) const;
+ void handleAssignment(CheckerContext &C, const SVal &LVal,
+ const SVal &RVal) const;
bool evalFind(CheckerContext &C, const CallExpr *CE) const;
bool evalFindEnd(CheckerContext &C, const CallExpr *CE) const;
@@ -137,6 +143,7 @@
bool isEndCall(const FunctionDecl *Func);
bool isSimpleComparisonOperator(OverloadedOperatorKind OK);
bool isAccessOperator(OverloadedOperatorKind OK);
+bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK);
bool isDecrementOperator(OverloadedOperatorKind OK);
BinaryOperator::Opcode getOpcode(const SymExpr *SE);
const RegionOrSymbol getRegionOrSymbol(const SVal &Val);
@@ -157,6 +164,7 @@
ProgramStateRef setIteratorPosition(ProgramStateRef State,
RegionOrSymbol RegOrSym,
IteratorPosition Pos);
+ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val);
ProgramStateRef adjustIteratorPosition(ProgramStateRef State,
RegionOrSymbol RegOrSym,
IteratorPosition Pos, bool Equal);
@@ -173,11 +181,27 @@
void IteratorPastEndChecker::checkPreCall(const CallEvent &Call,
CheckerContext &C) const {
// Check for access past end
- const auto *Func = Call.getDecl()->getAsFunction();
+ const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
if (!Func)
return;
if (Func->isOverloadedOperator()) {
- if (isAccessOperator(Func->getOverloadedOperator())) {
+ if (isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) {
+ if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
+ if (Call.getNumArgs() >= 1) {
+ handleRandomIncrOrDecr(C, Func->getOverloadedOperator(),
+ Call.getReturnValue(),
+ InstCall->getCXXThisVal(), Call.getArgSVal(0),
+ Call.getArgExpr(0)->getType(), true);
+ }
+ } else {
+ if (Call.getNumArgs() >= 2) {
+ handleRandomIncrOrDecr(C, Func->getOverloadedOperator(),
+ Call.getReturnValue(), Call.getArgSVal(0),
+ Call.getArgSVal(1),
+ Call.getArgExpr(1)->getType(), true);
+ }
+ }
+ } else if (isAccessOperator(Func->getOverloadedOperator())) {
if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
handleAccess(C, InstCall->getCXXThisVal());
} else {
@@ -190,7 +214,7 @@
void IteratorPastEndChecker::checkPostCall(const CallEvent &Call,
CheckerContext &C) const {
// Record end() iterators, iterator decrementation and comparison
- const auto *Func = Call.getDecl()->getAsFunction();
+ const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
if (!Func)
return;
if (Func->isOverloadedOperator()) {
@@ -204,13 +228,36 @@
handleComparison(C, Call.getReturnValue(), Call.getArgSVal(0),
Call.getArgSVal(1), Op);
}
+ } else if (isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) {
+ if (Func->isCXXInstanceMember()) {
+ if (Call.getNumArgs() >= 1) {
+ const auto &InstCall = static_cast<const CXXInstanceCall &>(Call);
+ handleRandomIncrOrDecr(C, Func->getOverloadedOperator(),
+ Call.getReturnValue(),
+ InstCall.getCXXThisVal(), Call.getArgSVal(0),
+ Call.getArgExpr(0)->getType(), false);
+ }
+ } else {
+ if (Call.getNumArgs() >= 2) {
+ handleRandomIncrOrDecr(C, Func->getOverloadedOperator(),
+ Call.getReturnValue(), Call.getArgSVal(0),
+ Call.getArgSVal(1),
+ Call.getArgExpr(1)->getType(), false);
+ }
+ }
} else if (isDecrementOperator(Func->getOverloadedOperator())) {
if (Func->isCXXInstanceMember()) {
const auto &InstCall = static_cast<const CXXInstanceCall &>(Call);
handleDecrement(C, InstCall.getCXXThisVal());
} else {
handleDecrement(C, Call.getArgSVal(0));
}
+ } else if (const auto *Method = dyn_cast<CXXMethodDecl>(Func)) {
+ if (!(Method->isCopyAssignmentOperator() ||
+ Method->isMoveAssignmentOperator()))
+ return;
+ const auto &InstCall = static_cast<const CXXInstanceCall &>(Call);
+ handleAssignment(C, InstCall.getCXXThisVal(), InstCall.getArgSVal(0));
}
} else if (Func->isCXXInstanceMember()) {
if (!isEndCall(Func))
@@ -462,15 +509,76 @@
}
}
+void IteratorPastEndChecker::handleRandomIncrOrDecr(
+ CheckerContext &C, OverloadedOperatorKind Op, const SVal &RetVal,
+ const SVal &LVal, const SVal &RVal, QualType RValType,
+ bool PreCheck) const {
+ if (!RValType->isIntegerType())
+ return;
+
+ auto State = C.getState();
+ const auto *Pos = getIteratorPosition(State, LVal);
+ if (!Pos || Pos->isInRange())
+ return;
+
+ auto &SVB = C.getSValBuilder();
+ auto &CM = C.getConstraintManager();
+ auto zeroVal = SVB.makeIntVal(0, RValType);
+
+ // Hack - begin
+ auto value = RVal;
+ if (auto loc = value.getAs<Loc>()) {
+ value = State->getRawSVal(*loc);
+ }
+ // Hack - end
+
+ auto greaterThanOrEqualToZero =
+ SVB.evalBinOp(State, BO_GE, value, zeroVal, SVB.getConditionType())
+ .getAs<DefinedSVal>();
+
+ if (!greaterThanOrEqualToZero) {
+ // Cannot properly reason so assume the best to prevent false positives
+ if (!PreCheck) {
+ auto &TgtVal =
+ (Op == OO_PlusEqual || Op == OO_MinusEqual) ? LVal : RetVal;
+ State = removeIteratorPosition(State, TgtVal);
+ C.addTransition(State);
+ }
+ return;
+ }
+
+ ProgramStateRef StateLT, StateGE;
+ std::tie(StateGE, StateLT) = CM.assumeDual(State, *greaterThanOrEqualToZero);
+
+ // When increasing by positive or decreasing by negative an iterator past its
+ // end, then it is a bug. We check for bugs before the operator call.
+ if (PreCheck && ((StateGE && (Op == OO_Plus || Op == OO_PlusEqual)) ||
+ (StateLT && (Op == OO_Minus || Op == OO_MinusEqual)))) {
+ auto *N = C.generateNonFatalErrorNode(State);
+ if (!N)
+ return;
+ reportPastEndBug("Iterator accessed past its end.", LVal, C, N);
+ }
+
+ // When increasing by negative or decreasing by positive an iterator past its
+ // end, then we assume that the iterator is back to its range.
+ if (!PreCheck && ((StateGE && (Op == OO_Minus || Op == OO_MinusEqual)) ||
+ (StateLT && (Op == OO_Plus || Op == OO_PlusEqual)))) {
+ State = (Op == OO_Minus || Op == OO_MinusEqual) ? StateGE : StateLT;
+ auto &TgtVal = (Op == OO_PlusEqual || Op == OO_MinusEqual) ? LVal : RetVal;
+ State = setIteratorPosition(State, TgtVal, IteratorPosition::getInRange());
+ C.addTransition(State);
+ }
+}
+
void IteratorPastEndChecker::handleAccess(CheckerContext &C,
const SVal &Val) const {
auto State = C.getState();
const auto *Pos = getIteratorPosition(State, Val);
if (Pos && Pos->isOutofRange()) {
auto *N = C.generateNonFatalErrorNode(State);
- if (!N) {
+ if (!N)
return;
- }
reportPastEndBug("Iterator accessed past its end.", Val, C, N);
}
}
@@ -496,6 +604,19 @@
C.addTransition(State);
}
+void IteratorPastEndChecker::handleAssignment(CheckerContext &C,
+ const SVal &LVal,
+ const SVal &RVal) const {
+ auto State = C.getState();
+ const auto *Pos = getIteratorPosition(State, RVal);
+ if (Pos) {
+ State = setIteratorPosition(State, LVal, *Pos);
+ } else {
+ State = removeIteratorPosition(State, LVal);
+ }
+ C.addTransition(State);
+}
+
bool IteratorPastEndChecker::evalFind(CheckerContext &C,
const CallExpr *CE) const {
if (CE->getNumArgs() == 3 && isIteratorType(CE->getArg(0)->getType()) &&
@@ -701,12 +822,16 @@
bool isAccessOperator(OverloadedOperatorKind OK) {
return OK == OO_Star || OK == OO_Arrow || OK == OO_ArrowStar ||
- OK == OO_Plus || OK == OO_PlusEqual || OK == OO_PlusPlus ||
- OK == OO_Subscript;
+ OK == OO_PlusPlus || OK == OO_Subscript;
+}
+
+bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK) {
+ return OK == OO_Plus || OK == OO_PlusEqual || OK == OO_Minus ||
+ OK == OO_MinusEqual;
}
bool isDecrementOperator(OverloadedOperatorKind OK) {
- return OK == OO_MinusEqual || OK == OO_MinusMinus;
+ return OK == OO_MinusMinus;
}
BinaryOperator::Opcode getOpcode(const SymExpr *SE) {
@@ -816,6 +941,17 @@
return nullptr;
}
+ProgramStateRef removeIteratorPosition(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;
+}
+
ProgramStateRef adjustIteratorPosition(ProgramStateRef State,
RegionOrSymbol RegOrSym,
IteratorPosition Pos, bool Equal) {
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
