Index: lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp =================================================================== --- lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp +++ lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp @@ -72,19 +72,25 @@ check::PostStmt, check::PostStmt, check::PostStmt, 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 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(Call.getDecl()); if (!Func) return; if (Func->isOverloadedOperator()) { - if (isAccessOperator(Func->getOverloadedOperator())) { + if (isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) { + if (const auto *InstCall = dyn_cast(&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(&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(Call.getDecl()); if (!Func) return; if (Func->isOverloadedOperator()) { @@ -204,6 +228,23 @@ 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(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(Call); @@ -211,6 +252,12 @@ } else { handleDecrement(C, Call.getArgSVal(0)); } + } else if (const auto *Method = dyn_cast(Func)) { + if (!(Method->isCopyAssignmentOperator() || + Method->isMoveAssignmentOperator())) + return; + const auto &InstCall = static_cast(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()) { + value = State->getRawSVal(*loc); + } + // Hack - end + + auto greaterThanOrEqualToZero = + SVB.evalBinOp(State, BO_GE, value, zeroVal, SVB.getConditionType()) + .getAs(); + + 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(Reg); + } else if (const auto Sym = Val.getAsSymbol()) { + return State->remove(Sym); + } else if (const auto LCVal = Val.getAs()) { + return State->remove(LCVal->getRegion()); + } + return nullptr; +} + ProgramStateRef adjustIteratorPosition(ProgramStateRef State, RegionOrSymbol RegOrSym, IteratorPosition Pos, bool Equal) { 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 struct __iterator { - typedef __iterator iterator; - typedef __iterator 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 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 struct __vector_iterator { + typedef __vector_iterator iterator; + typedef __vector_iterator 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 operator++() { ++ ptr; return *this; } + __vector_iterator operator++(int) { + auto tmp = *this; + ++ ptr; + return tmp; + } + __vector_iterator operator--() { -- ptr; return *this; } + __vector_iterator operator--(int) { + auto tmp = *this; -- ptr; + return tmp; + } + __vector_iterator operator+(difference_type n) { + return ptr + n; + } + __vector_iterator operator-(difference_type n) { + return ptr - n; + } + __vector_iterator operator+=(difference_type n) { + return ptr += n; + } + __vector_iterator operator-=(difference_type n) { + return ptr -= n; + } - __iterator operator++() { return *this; } - __iterator operator++(int) { return *this; } - __iterator operator--() { return *this; } - __iterator operator--(int) { return *this; } Ref operator*() const { return *ptr; } Ptr operator->() const { return *ptr; } @@ -33,7 +75,45 @@ Ptr ptr; }; +template struct __list_iterator { + typedef __vector_iterator iterator; + typedef __vector_iterator 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 operator++() { item = item->next; return *this; } + __list_iterator operator++(int) { + auto tmp = *this; + item = item->next; + return tmp; + } + __list_iterator operator--() { item = item->prev; return *this; } + __list_iterator 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 struct pair { T1 first; @@ -50,13 +130,13 @@ template class vector { - typedef __iterator iterator; - typedef __iterator const_iterator; - T *_start; T *_finish; T *_end_of_storage; public: + typedef __vector_iterator iterator; + typedef __vector_iterator 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 + 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 +void __advance (BidirectionalIterator& it, Distance n, + std::bidirectional_iterator_tag) { + if (n >= 0) while(n-- > 0) ++it; else while (n++<0) --it; +} + +template +void __advance (RandomAccessIterator& it, Distance n, + std::random_access_iterator_tag) { + it += n; +} + +namespace std { + template + void advance (InputIterator& it, Distance n) { + __advance(it, n, typename InputIterator::iterator_category()); + } + + template + BidirectionalIterator + prev (BidirectionalIterator it, + typename iterator_traits::difference_type n = + 1) { + advance(it, -n); + return it; + } template 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: 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/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 &vec) { + auto i = vec.end(); + i = vec.begin(); + *i; // no-warning +} + +void good_overwrite_find(std::vector &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 &vec) { + auto i = vec.begin(); + i = vec.end(); + *i; // expected-warning{{Iterator accessed past its end}} +} + +void bad_overwrite_find(std::vector &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 &vec) { + auto i = vec.end(); + std::advance(i, -1); + *i; // no-warning +} + +void good_prev(std::vector &vec) { + auto i = std::prev(vec.end()); + *i; // no-warning +} + +struct init_value_prev { + init_value_prev(std::list l) : Back(std::prev(l.end())), Item(*Back) {} // no-warning +private: + std::list::iterator Back; + int Item; +};