Index: clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp =================================================================== --- clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp +++ clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp @@ -99,13 +99,20 @@ void handleRandomIncrOrDecr(CheckerContext &C, const Expr *CE, OverloadedOperatorKind Op, const SVal &RetVal, const SVal &LHS, const SVal &RHS) const; + void handleAdvance(CheckerContext &C, const Expr *CE, SVal RetVal, SVal Iter, + SVal Amount) const; + void handlePrev(CheckerContext &C, const Expr *CE, SVal RetVal, SVal Iter, + SVal Amount) const; + void handleNext(CheckerContext &C, const Expr *CE, SVal RetVal, SVal Iter, + SVal Amount) const; void assignToContainer(CheckerContext &C, const Expr *CE, const SVal &RetVal, const MemRegion *Cont) const; + bool noChangeInPosition(CheckerContext &C, SVal Iter, const Expr *CE) const; void printState(raw_ostream &Out, ProgramStateRef State, const char *NL, const char *Sep) const override; public: - IteratorModeling() {} + IteratorModeling() = default; void checkPostCall(const CallEvent &Call, CheckerContext &C) const; void checkBind(SVal Loc, SVal Val, const Stmt *S, CheckerContext &C) const; @@ -115,6 +122,18 @@ CheckerContext &C) const; void checkLiveSymbols(ProgramStateRef State, SymbolReaper &SR) const; void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const; + + typedef void (IteratorModeling::*AdvanceFn)(CheckerContext &, const Expr*, + SVal, SVal, SVal) const; + + CallDescriptionMap AdvanceFunctions = { + {{{"std", "advance"}, 2}, + &IteratorModeling::handleAdvance}, + {{{"std", "prev"}, 2}, + &IteratorModeling::handlePrev}, + {{{"std", "next"}, 2}, + &IteratorModeling::handleNext}, + }; }; bool isSimpleComparisonOperator(OverloadedOperatorKind OK); @@ -193,13 +212,41 @@ return; } } else { - if (!isIteratorType(Call.getResultType())) - return; - const auto *OrigExpr = Call.getOriginExpr(); if (!OrigExpr) return; + const AdvanceFn *Handler = AdvanceFunctions.lookup(Call); + if (Handler) { + if (!C.wasInlined) { + if (Call.getNumArgs() > 1) { + (this->**Handler)(C, OrigExpr, Call.getReturnValue(), + Call.getArgSVal(0), Call.getArgSVal(1)); + } else { + auto &BVF = C.getSValBuilder().getBasicValueFactory(); + (this->**Handler)(C, OrigExpr, Call.getReturnValue(), + Call.getArgSVal(0), + nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1)))); + } + return; + } + + // If std::advance() was inlined, but the non-standard function it calls + // was not, then we have to model it explicitly + const auto *IdInfo = Func->getIdentifier(); + if (IdInfo) { + if (IdInfo->getName() == "advance") { + if (noChangeInPosition(C, Call.getArgSVal(0), OrigExpr)) { + (this->**Handler)(C, OrigExpr, Call.getReturnValue(), + Call.getArgSVal(0), Call.getArgSVal(1)); + } + } + } + } + + if (!isIteratorType(Call.getResultType())) + return; + auto State = C.getState(); // Already bound to container? @@ -481,6 +528,22 @@ } } +void IteratorModeling::handleAdvance(CheckerContext &C, const Expr *CE, + SVal RetVal, SVal Iter, + SVal Amount) const { + handleRandomIncrOrDecr(C, CE, OO_PlusEqual, RetVal, Iter, Amount); +} + +void IteratorModeling::handlePrev(CheckerContext &C, const Expr *CE, + SVal RetVal, SVal Iter, SVal Amount) const { + handleRandomIncrOrDecr(C, CE, OO_Minus, RetVal, Iter, Amount); +} + +void IteratorModeling::handleNext(CheckerContext &C, const Expr *CE, + SVal RetVal, SVal Iter, SVal Amount) const { + handleRandomIncrOrDecr(C, CE, OO_Plus, RetVal, Iter, Amount); +} + void IteratorModeling::assignToContainer(CheckerContext &C, const Expr *CE, const SVal &RetVal, const MemRegion *Cont) const { @@ -493,6 +556,39 @@ C.addTransition(State); } +bool IteratorModeling::noChangeInPosition(CheckerContext &C, SVal Iter, + const Expr *CE) const { + const auto StateAfter = C.getState(); + + const auto *PosAfter = getIteratorPosition(StateAfter, Iter); + // If we have no position after the call of `std::advance`, then we are not + // interested. (Modeling of an inlined `std::advance()` should not remove the + // position in any case.) + if (!PosAfter) + return false; + + const ExplodedNode *N = C.getPredecessor(); + while (N) { + ProgramPoint PP = N->getLocation(); + if (auto Enter = PP.getAs()) { + if (Enter->getCallExpr() == CE) + break; + } + + N = N->getFirstPred(); + } + + assert (N && "Any call should have a `CallEnter` node."); + + const auto StateBefore = N->getState(); + const auto *PosBefore = getIteratorPosition(StateBefore, Iter); + + assert (PosBefore && "`std::advance() should not create new iterator " + "position but change existing ones"); + + return PosBefore->getOffset() == PosAfter->getOffset(); +} + void IteratorModeling::printState(raw_ostream &Out, ProgramStateRef State, const char *NL, const char *Sep) const { auto SymbolMap = State->get(); Index: clang/test/Analysis/Inputs/system-header-simulator-cxx.h =================================================================== --- clang/test/Analysis/Inputs/system-header-simulator-cxx.h +++ clang/test/Analysis/Inputs/system-header-simulator-cxx.h @@ -758,30 +758,64 @@ template void __advance (BidirectionalIterator& it, Distance n, - std::bidirectional_iterator_tag) { + std::bidirectional_iterator_tag) +#if !defined(STD_ADVANCE_INLINE_LEVEL) || STD_ADVANCE_INLINE_LEVEL > 2 +{ if (n >= 0) while(n-- > 0) ++it; else while (n++<0) --it; } +#else +; +#endif template void __advance (RandomAccessIterator& it, Distance n, - std::random_access_iterator_tag) { + std::random_access_iterator_tag) +#if !defined(STD_ADVANCE_INLINE_LEVEL) || STD_ADVANCE_INLINE_LEVEL > 2 +{ it += n; } +#else +; +#endif namespace std { template - void advance (InputIterator& it, Distance n) { + void advance (InputIterator& it, Distance n) +#if !defined(STD_ADVANCE_INLINE_LEVEL) || STD_ADVANCE_INLINE_LEVEL > 1 + { __advance(it, n, typename InputIterator::iterator_category()); } +#else + ; +#endif template BidirectionalIterator prev (BidirectionalIterator it, typename iterator_traits::difference_type n = - 1) { + 1) +#if !defined(STD_ADVANCE_INLINE_LEVEL) || STD_ADVANCE_INLINE_LEVEL > 0 + { advance(it, -n); return it; } +#else + ; +#endif + + template + ForwardIterator + next (ForwardIterator it, + typename iterator_traits::difference_type n = + 1) +#if !defined(STD_ADVANCE_INLINE_LEVEL) || STD_ADVANCE_INLINE_LEVEL > 0 + { + advance(it, n); + return it; + } +#else + ; +#endif template InputIt find(InputIt first, InputIt last, const T& value); Index: clang/test/Analysis/iterator-modelling.cpp =================================================================== --- clang/test/Analysis/iterator-modelling.cpp +++ clang/test/Analysis/iterator-modelling.cpp @@ -2,6 +2,12 @@ // RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,debug.DebugIteratorModeling,debug.ExprInspection -analyzer-config aggressive-binary-operation-simplification=true -analyzer-config c++-container-inlining=true -DINLINE=1 %s -verify +// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,debug.DebugIteratorModeling,debug.ExprInspection -analyzer-config aggressive-binary-operation-simplification=true -analyzer-config c++-container-inlining=true -DINLINE=1 -DSTD_ADVANCE_INLINE_LEVEL=0 %s -verify + +// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,debug.DebugIteratorModeling,debug.ExprInspection -analyzer-config aggressive-binary-operation-simplification=true -analyzer-config c++-container-inlining=true -DINLINE=1 -DSTD_ADVANCE_INLINE_LEVEL=1 %s -verify + +// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,debug.DebugIteratorModeling,debug.ExprInspection -analyzer-config aggressive-binary-operation-simplification=true -analyzer-config c++-container-inlining=true -DINLINE=1 -DSTD_ADVANCE_INLINE_LEVEL=2 %s -verify + // RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.IteratorModeling,debug.ExprInspection -analyzer-config aggressive-binary-operation-simplification=true %s 2>&1 | FileCheck %s #include "Inputs/system-header-simulator-cxx.h" @@ -233,6 +239,68 @@ clang_analyzer_express(clang_analyzer_iterator_position(i2)); //expected-warning{{$v.end() - 1}} } +/// std::advance(), std::prev(), std::next() + +void std_advance_minus(const std::vector &v) { + auto i = v.end(); + + clang_analyzer_denote(clang_analyzer_container_end(v), "$v.end()"); + + std::advance(i, -1); + + clang_analyzer_express(clang_analyzer_iterator_position(i)); //expected-warning{{$v.end() - 1}} +} + +void std_advance_plus(const std::vector &v) { + auto i = v.begin(); + + clang_analyzer_denote(clang_analyzer_container_begin(v), "$v.begin()"); + + std::advance(i, 1); + + clang_analyzer_express(clang_analyzer_iterator_position(i)); //expected-warning{{$v.begin() + 1}} +} + +void std_prev(const std::vector &v) { + auto i = v.end(); + + clang_analyzer_denote(clang_analyzer_container_end(v), "$v.end()"); + + auto j = std::prev(i); + + clang_analyzer_express(clang_analyzer_iterator_position(j)); //expected-warning{{$v.end() - 1}} +} + +void std_prev2(const std::vector &v) { + auto i = v.end(); + + clang_analyzer_denote(clang_analyzer_container_end(v), "$v.end()"); + + auto j = std::prev(i, 2); + + clang_analyzer_express(clang_analyzer_iterator_position(j)); //expected-warning{{$v.end() - 2}} +} + +void std_next(const std::vector &v) { + auto i = v.begin(); + + clang_analyzer_denote(clang_analyzer_container_begin(v), "$v.begin()"); + + auto j = std::next(i); + + clang_analyzer_express(clang_analyzer_iterator_position(j)); //expected-warning{{$v.begin() + 1}} +} + +void std_next2(const std::vector &v) { + auto i = v.begin(); + + clang_analyzer_denote(clang_analyzer_container_begin(v), "$v.begin()"); + + auto j = std::next(i, 2); + + clang_analyzer_express(clang_analyzer_iterator_position(j)); //expected-warning{{$v.begin() + 2}} +} + //////////////////////////////////////////////////////////////////////////////// /// /// C O N T A I N E R A S S I G N M E N T S