baloghadamsoftware created this revision.
baloghadamsoftware added reviewers: NoQ, Szelethus.
baloghadamsoftware added a project: clang.
Herald added subscribers: ASDenysPetrov, martong, steakhal, Charusso,
gamesh411, dkrupp, donat.nagy, mikhail.ramalho, a.sidorin, rnkovacs, szepet,
xazax.hun, whisperity.
baloghadamsoftware added a comment.
Partially replacing D62895 <https://reviews.llvm.org/D62895>.
Whenever the analyzer budget runs out just at the point where `std::advance()`,
`std::prev()` or `std::next()` is invoked the function are not inlined. This
results in strange behavior such as `std::prev(v.end())` equals `v.end()`. To
prevent this model these functions if they were not inlined. It may also
happend that although `std::advance()` is inlined but a function it calls
inside (e.g. `__advance()` in some implementations) is not. This case is also
handled in this patch.
Repository:
rG LLVM Github Monorepo
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
@@ -758,30 +758,64 @@
template <class BidirectionalIterator, class Distance>
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 <class RandomAccessIterator, class Distance>
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 <class InputIterator, class Distance>
- 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 <class BidirectionalIterator>
BidirectionalIterator
prev (BidirectionalIterator it,
typename iterator_traits<BidirectionalIterator>::difference_type n =
- 1) {
+ 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
@@ -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<AdvanceFn> 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<CallEnter>()) {
+ 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<IteratorSymbolMap>();
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
