baloghadamsoftware updated this revision to Diff 251567.
baloghadamsoftware added a comment.
Updated according to the comments and automatic formatting suggestions.
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D76361/new/
https://reviews.llvm.org/D76361
Files:
clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp
clang/test/Analysis/Inputs/system-header-simulator-cxx.h
clang/test/Analysis/iterator-modelling.cpp
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<int> &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<int> &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<int> &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<int> &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<int> &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<int> &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
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 <class BidirectionalIterator, class Distance>
-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 <class RandomAccessIterator, class Distance>
-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 <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 Distance>
+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 <class BidirectionalIterator>
+BidirectionalIterator
+prev(BidirectionalIterator it,
+ typename iterator_traits<BidirectionalIterator>::difference_type n =
+ 1)
+#if !defined(STD_ADVANCE_INLINE_LEVEL) || STD_ADVANCE_INLINE_LEVEL > 0
+{
+ advance(it, -n);
+ return it;
+}
+#else
+ ;
+#endif
+
+template <class ForwardIterator>
+ForwardIterator
+next(ForwardIterator it,
+ typename iterator_traits<ForwardIterator>::difference_type n =
+ 1)
+#if !defined(STD_ADVANCE_INLINE_LEVEL) || STD_ADVANCE_INLINE_LEVEL > 0
+{
+ advance(it, n);
+ return it;
+}
+#else
+ ;
+#endif
template <class InputIt, class T>
InputIt find(InputIt first, InputIt last, const T& value);
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::PostCall, check::PostStmt<MaterializeTemporaryExpr>,
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<AdvanceFn> AdvanceLikeFunctions = {
+ // template<class InputIt, class Distance>
+ // void advance(InputIt& it, Distance n);
+ {{{"std", "advance"}, 2}, &IteratorModeling::handleAdvance},
+
+ // template<class BidirIt>
+ // BidirIt prev(
+ // BidirIt it,
+ // typename std::iterator_traits<BidirIt>::difference_type n = 1);
+ {{{"std", "prev"}, 2}, &IteratorModeling::handlePrev},
+
+ // template<class ForwardIt>
+ // ForwardIt next(
+ // ForwardIt it,
+ // typename std::iterator_traits<ForwardIt>::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<CXXInstanceCall>(&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<CXXInstanceCall>(&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<CXXInstanceCall>(&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<CXXInstanceCall>(&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<CXXConstructorCall>(&Call) && Call.getNumArgs() == 1) {
- if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(0))) {
- State = setIteratorPosition(State, Call.getReturnValue(), *Pos);
- if (cast<CXXConstructorDecl>(Func)->isMoveConstructor()) {
- State = removeIteratorPosition(State, Call.getArgSVal(0));
- }
- C.addTransition(State);
- return;
+ // Copy-like and move constructors
+ if (isa<CXXConstructorCall>(&Call) && Call.getNumArgs() == 1) {
+ if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(0))) {
+ State = setIteratorPosition(State, Call.getReturnValue(), *Pos);
+ if (cast<CXXConstructorDecl>(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<CXXInstanceCall>(&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<CXXInstanceCall>(&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<CXXInstanceCall>(&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<CXXInstanceCall>(&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<FunctionDecl>(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<IteratorSymbolMap>();
@@ -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<CallEnter>()) {
+ if (Enter->getCallExpr() == Call)
+ break;
+ }
+
+ Node = Node->getFirstPred();
+ }
+
+ return Node;
+}
+
} // namespace
void ento::registerIteratorModeling(CheckerManager &mgr) {
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
