Index: clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp =================================================================== --- clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp +++ clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp @@ -86,6 +86,15 @@ : public Checker, check::Bind, check::LiveSymbols, check::DeadSymbols> { + using AdvanceFn = void (IteratorModeling::*)(CheckerContext &, const Expr *, + SVal, SVal, SVal) const; + + void handleOverloadedOperator(CheckerContext &C, const CallEvent &Call, + OverloadedOperatorKind Op) const; + void handleAdvanceLikeFunction(CheckerContext &C, const CallEvent &Call, + const Expr *OrigExpr, + const AdvanceFn *Handler) const; + void handleComparison(CheckerContext &C, const Expr *CE, SVal RetVal, const SVal &LVal, const SVal &RVal, OverloadedOperatorKind Op) const; @@ -99,13 +108,39 @@ 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 noChangeInAdvance(CheckerContext &C, SVal Iter, const Expr *CE) const; void printState(raw_ostream &Out, ProgramStateRef State, const char *NL, const char *Sep) const override; + // std::advance, std::prev & std::next + CallDescriptionMap AdvanceLikeFunctions = { + // template + // void advance(InputIt& it, Distance n); + {{{"std", "advance"}, 2}, &IteratorModeling::handleAdvance}, + + // template + // BidirIt prev( + // BidirIt it, + // typename std::iterator_traits::difference_type n = 1); + {{{"std", "prev"}, 2}, &IteratorModeling::handlePrev}, + + // template + // ForwardIt next( + // ForwardIt it, + // typename std::iterator_traits::difference_type n = 1); + {{{"std", "next"}, 2}, &IteratorModeling::handleNext}, + }; + public: - IteratorModeling() {} + IteratorModeling() = default; void checkPostCall(const CallEvent &Call, CheckerContext &C) const; void checkBind(SVal Loc, SVal Val, const Stmt *S, CheckerContext &C) const; @@ -123,6 +158,7 @@ SymbolRef Sym2, bool Equal); bool isBoundThroughLazyCompoundVal(const Environment &Env, const MemRegion *Reg); +const ExplodedNode *findCallEnter(const ExplodedNode *Node, const Expr *Call); } // namespace @@ -135,101 +171,52 @@ if (Func->isOverloadedOperator()) { const auto Op = Func->getOverloadedOperator(); - if (isSimpleComparisonOperator(Op)) { - const auto *OrigExpr = Call.getOriginExpr(); - if (!OrigExpr) - return; - - if (const auto *InstCall = dyn_cast(&Call)) { - handleComparison(C, OrigExpr, Call.getReturnValue(), - InstCall->getCXXThisVal(), Call.getArgSVal(0), Op); - return; - } - - handleComparison(C, OrigExpr, Call.getReturnValue(), Call.getArgSVal(0), - Call.getArgSVal(1), Op); - return; - } else if (isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) { - const auto *OrigExpr = Call.getOriginExpr(); - if (!OrigExpr) - return; - - if (const auto *InstCall = dyn_cast(&Call)) { - if (Call.getNumArgs() >= 1 && - Call.getArgExpr(0)->getType()->isIntegralOrEnumerationType()) { - handleRandomIncrOrDecr(C, OrigExpr, Func->getOverloadedOperator(), - Call.getReturnValue(), - InstCall->getCXXThisVal(), Call.getArgSVal(0)); - return; - } - } else { - if (Call.getNumArgs() >= 2 && - Call.getArgExpr(1)->getType()->isIntegralOrEnumerationType()) { - handleRandomIncrOrDecr(C, OrigExpr, Func->getOverloadedOperator(), - Call.getReturnValue(), Call.getArgSVal(0), - Call.getArgSVal(1)); - return; - } - } - } else if (isIncrementOperator(Func->getOverloadedOperator())) { - if (const auto *InstCall = dyn_cast(&Call)) { - handleIncrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(), - Call.getNumArgs()); - return; - } + handleOverloadedOperator(C, Call, Op); + return; + } - handleIncrement(C, Call.getReturnValue(), Call.getArgSVal(0), - Call.getNumArgs()); - return; - } else if (isDecrementOperator(Func->getOverloadedOperator())) { - if (const auto *InstCall = dyn_cast(&Call)) { - handleDecrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(), - Call.getNumArgs()); - return; - } + const auto *OrigExpr = Call.getOriginExpr(); + if (!OrigExpr) + return; - handleDecrement(C, Call.getReturnValue(), Call.getArgSVal(0), - Call.getNumArgs()); - return; - } - } else { - if (!isIteratorType(Call.getResultType())) - return; + const AdvanceFn *Handler = AdvanceLikeFunctions.lookup(Call); + if (Handler) { + handleAdvanceLikeFunction(C, Call, OrigExpr, Handler); + return; + } - const auto *OrigExpr = Call.getOriginExpr(); - if (!OrigExpr) - return; + if (!isIteratorType(Call.getResultType())) + return; - auto State = C.getState(); + auto State = C.getState(); - // Already bound to container? - if (getIteratorPosition(State, Call.getReturnValue())) - return; + // Already bound to container? + if (getIteratorPosition(State, Call.getReturnValue())) + return; - // Copy-like and move constructors - if (isa(&Call) && Call.getNumArgs() == 1) { - if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(0))) { - State = setIteratorPosition(State, Call.getReturnValue(), *Pos); - if (cast(Func)->isMoveConstructor()) { - State = removeIteratorPosition(State, Call.getArgSVal(0)); - } - C.addTransition(State); - return; + // Copy-like and move constructors + if (isa(&Call) && Call.getNumArgs() == 1) { + if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(0))) { + State = setIteratorPosition(State, Call.getReturnValue(), *Pos); + if (cast(Func)->isMoveConstructor()) { + State = removeIteratorPosition(State, Call.getArgSVal(0)); } + C.addTransition(State); + return; } + } - // Assumption: if return value is an iterator which is not yet bound to a - // container, then look for the first iterator argument, and - // bind the return value to the same container. This approach - // works for STL algorithms. - // FIXME: Add a more conservative mode - for (unsigned i = 0; i < Call.getNumArgs(); ++i) { - if (isIteratorType(Call.getArgExpr(i)->getType())) { - if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(i))) { - assignToContainer(C, OrigExpr, Call.getReturnValue(), - Pos->getContainer()); - return; - } + // Assumption: if return value is an iterator which is not yet bound to a + // container, then look for the first iterator argument, and + // bind the return value to the same container. This approach + // works for STL algorithms. + // FIXME: Add a more conservative mode + for (unsigned i = 0; i < Call.getNumArgs(); ++i) { + if (isIteratorType(Call.getArgExpr(i)->getType())) { + if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(i))) { + assignToContainer(C, OrigExpr, Call.getReturnValue(), + Pos->getContainer()); + return; } } } @@ -310,6 +297,91 @@ C.addTransition(State); } +void +IteratorModeling::handleOverloadedOperator(CheckerContext &C, + const CallEvent &Call, + OverloadedOperatorKind Op) const { + if (isSimpleComparisonOperator(Op)) { + const auto *OrigExpr = Call.getOriginExpr(); + if (!OrigExpr) + return; + + if (const auto *InstCall = dyn_cast(&Call)) { + handleComparison(C, OrigExpr, Call.getReturnValue(), + InstCall->getCXXThisVal(), Call.getArgSVal(0), Op); + return; + } + + handleComparison(C, OrigExpr, Call.getReturnValue(), Call.getArgSVal(0), + Call.getArgSVal(1), Op); + return; + } else if (isRandomIncrOrDecrOperator(Op)) { + const auto *OrigExpr = Call.getOriginExpr(); + if (!OrigExpr) + return; + + if (const auto *InstCall = dyn_cast(&Call)) { + if (Call.getNumArgs() >= 1 && + Call.getArgExpr(0)->getType()->isIntegralOrEnumerationType()) { + handleRandomIncrOrDecr(C, OrigExpr, Op, Call.getReturnValue(), + InstCall->getCXXThisVal(), Call.getArgSVal(0)); + return; + } + } else { + if (Call.getNumArgs() >= 2 && + Call.getArgExpr(1)->getType()->isIntegralOrEnumerationType()) { + handleRandomIncrOrDecr(C, OrigExpr, Op, Call.getReturnValue(), + Call.getArgSVal(0), Call.getArgSVal(1)); + return; + } + } + } else if (isIncrementOperator(Op)) { + if (const auto *InstCall = dyn_cast(&Call)) { + handleIncrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(), + Call.getNumArgs()); + return; + } + + handleIncrement(C, Call.getReturnValue(), Call.getArgSVal(0), + Call.getNumArgs()); + return; + } else if (isDecrementOperator(Op)) { + if (const auto *InstCall = dyn_cast(&Call)) { + handleDecrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(), + Call.getNumArgs()); + return; + } + + handleDecrement(C, Call.getReturnValue(), Call.getArgSVal(0), + Call.getNumArgs()); + return; + } +} + +void +IteratorModeling::handleAdvanceLikeFunction(CheckerContext &C, + const CallEvent &Call, + const Expr *OrigExpr, + const AdvanceFn *Handler) const { + if (!C.wasInlined) { + (this->**Handler)(C, OrigExpr, Call.getReturnValue(), + Call.getArgSVal(0), Call.getArgSVal(1)); + return; + } + + // If std::advance() was inlined, but a non-standard function it calls inside + // was not, then we have to model it explicitly + const auto *IdInfo = cast(Call.getDecl())->getIdentifier(); + if (IdInfo) { + if (IdInfo->getName() == "advance") { + if (noChangeInAdvance(C, Call.getArgSVal(0), OrigExpr)) { + (this->**Handler)(C, OrigExpr, Call.getReturnValue(), + Call.getArgSVal(0), Call.getArgSVal(1)); + } + } + } +} + void IteratorModeling::handleComparison(CheckerContext &C, const Expr *CE, SVal RetVal, const SVal &LVal, const SVal &RVal, @@ -481,6 +553,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 +581,31 @@ C.addTransition(State); } +bool IteratorModeling::noChangeInAdvance(CheckerContext &C, SVal Iter, + const Expr *CE) const { + // Compare the iterator position before and after the call. (To be called + // from `checkPostCall()`.) + 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 = findCallEnter(C.getPredecessor(), CE); + 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(); @@ -584,6 +697,20 @@ return false; } +const ExplodedNode *findCallEnter(const ExplodedNode *Node, const Expr *Call) { + while (Node) { + ProgramPoint PP = Node->getLocation(); + if (auto Enter = PP.getAs()) { + if (Enter->getCallExpr() == Call) + break; + } + + Node = Node->getFirstPred(); + } + + return Node; +} + } // namespace void ento::registerIteratorModeling(CheckerManager &mgr) { 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 @@ -757,31 +757,66 @@ } template -void __advance (BidirectionalIterator& it, Distance n, - std::bidirectional_iterator_tag) { +void __advance(BidirectionalIterator& it, Distance n, + 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) { +void __advance(RandomAccessIterator& it, Distance n, + 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) { - __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 +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) +#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