[Analyzer] Iterator Modeling - Model `std::advance()`, `std::prev()` and `std::next()`

[baloghadamsoftware]

Summary

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.

[baloghadamsoftware]

Partially replacing D62895.

[martong]

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.

I suppose we could get this strange behavior with std::distance too? Would it be worth to handle that as well here?

[martong]

clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp

193

Perhaps putting this hunk into a separate function or lambda could decrease the nesting level, b/c you could have an early return if there is no Handler.

194

Maybe a comment could be helpful here about the common signature of the prev/next functions. Like:

advanceFun ( It it, Distance n = 1 )

By the way, can we call std::advance with one argument?

210

Should this be __advance?

584

Some comments would be helpful here. Also, should we use this function only with advance() or it could be useful perhaps in other context?

596

I have a rough presumption that this hunk is a general pattern to get the previous node for the previous iterator position. So perhaps it would be useful as a standalone free/static member function too?

[baloghadamsoftware]

Updated according to the comments and automatic formatting suggestions.

[baloghadamsoftware]

In D76361#1929483, @martong wrote:

I suppose we could get this strange behavior with std::distance too? Would it be worth to handle that as well here?

Modeling of std::distance() is planned after we model the size of the container properly.

clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp

193

Early return is not possible because the execution must continue if the is no handler. However, I refactored checkPostCall now, the handling of both overloaded operators and advance-like functions are moved to separate functions.

194

I added them to the map.

210

No. __advance() is non-standard, I cannot rely on it. If the function was std::advance(), it was inlined, but still did not change the iterator's position means that it did not do its job. Probably the function it calls inside (which could be __advance() in most implementations) was not inlined. In this case we model the behavior of std::advance() explicitely.

584

I renamed the function and added a short comment. Is it OK?

596

I moved this to a standalone function and named it accordingly.

[martong]

LGTM!

clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp

193

Thanks, that's much better structured this way.

584

Yeah, looks ok.

596

Thanks, it's easier to read the code this way.

clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp

 using namespace iterator;
 
 namespace {
 
 class IteratorModeling
     : 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;
   void processComparison(CheckerContext &C, ProgramStateRef State,
                          SymbolRef Sym1, SymbolRef Sym2, const SVal &RetVal,
                          OverloadedOperatorKind Op) const;
   void handleIncrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter,
                        bool Postfix) const;
   void handleDecrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter,
                        bool Postfix) const;
   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;
   void checkPostStmt(const CXXConstructExpr *CCE, CheckerContext &C) const;
   void checkPostStmt(const DeclStmt *DS, CheckerContext &C) const;
   void checkPostStmt(const MaterializeTemporaryExpr *MTE,
                      CheckerContext &C) const;
   void checkLiveSymbols(ProgramStateRef State, SymbolReaper &SR) const;
   void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
 };
 
 bool isSimpleComparisonOperator(OverloadedOperatorKind OK);
 ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val);
 ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1,
                               SymbolRef Sym2, bool Equal);
 bool isBoundThroughLazyCompoundVal(const Environment &Env,
                                    const MemRegion *Reg);
+const ExplodedNode *findCallEnter(const ExplodedNode *Node, const Expr *Call);
 
 } // namespace
 
 void IteratorModeling::checkPostCall(const CallEvent &Call,
                                      CheckerContext &C) const {
   // Record new iterator positions and iterator position changes
   const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
   if (!Func)
     return;
 
   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;
-      }
+    handleOverloadedOperator(C, Call, Op);
 
-      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;
-      }
+  const AdvanceFn *Handler = AdvanceLikeFunctions.lookup(Call);
+  if (Handler) {
+    handleAdvanceLikeFunction(C, Call, OrigExpr, Handler);
 
-      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;
-      }
-
-      handleDecrement(C, Call.getReturnValue(), Call.getArgSVal(0),
-                        Call.getNumArgs());
-      return;
-    }
-  } else {
-    if (!isIteratorType(Call.getResultType()))
-      return;
 
-    const auto *OrigExpr = Call.getOriginExpr();
-    if (!OrigExpr)
-      return;
-
-    auto State = C.getState();
 
-    // 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;
-      }
-    }
 
-    // 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;
-        }
-      }
-    }
-  }
-}
 
 void IteratorModeling::checkBind(SVal Loc, SVal Val, const Stmt *S,
                                  CheckerContext &C) const {
   auto State = C.getState();
   const auto *Pos = getIteratorPosition(State, Val);
   if (Pos) {
     State = setIteratorPosition(State, Loc, *Pos);
     C.addTransition(State);
for (const auto &Sym : SymbolMap) {
     if (!SR.isLive(Sym.first)) {
       State = State->remove<IteratorSymbolMap>(Sym.first);
     }
   }
 
   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,
                                        OverloadedOperatorKind Op) const {
   // Record the operands and the operator of the comparison for the next
   // evalAssume, if the result is a symbolic expression. If it is a concrete
   // value (only one branch is possible), then transfer the state between
   // the operands according to the operator and the result
if (NewState) {
 
     State = setIteratorPosition(NewState, TgtVal, *NewPos);
     C.addTransition(State);
   } else {
     assignToContainer(C, CE, TgtVal, Pos->getContainer());
   }
 }
 
+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 {
   Cont = Cont->getMostDerivedObjectRegion();
 
   auto State = C.getState();
   const auto *LCtx = C.getLocationContext();
   State = createIteratorPosition(State, RetVal, Cont, CE, LCtx, C.blockCount());
 
   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>();
   auto RegionMap = State->get<IteratorRegionMap>();
 
   if (!SymbolMap.isEmpty() || !RegionMap.isEmpty()) {
     Out << Sep << "Iterator Positions :" << NL;
     for (const auto &Sym : SymbolMap) {
if (const auto LCVal = Binding.second.getAs<nonloc::LazyCompoundVal>()) {
       if (LCVal->getRegion() == Reg)
         return true;
     }
   }
 
   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) {
   mgr.registerChecker<IteratorModeling>();
 }
 
 bool ento::shouldRegisterIteratorModeling(const LangOptions &LO) {
   return true;
 }

clang/test/Analysis/Inputs/system-header-simulator-cxx.h

#endif
 
   template<class InputIter, class OutputIter>
   OutputIter copy_backward(InputIter II, InputIter IE, OutputIter OI) {
     return __copy_backward(II, IE, OI);
   }
 }
 
 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());
-  }
+
+void advance(InputIterator& it, Distance n)
+#if !defined(STD_ADVANCE_INLINE_LEVEL) || STD_ADVANCE_INLINE_LEVEL > 1
+{
+#else
+    ;
+#endif
 
-  template <class BidirectionalIterator>
-  BidirectionalIterator
-  prev (BidirectionalIterator it,
-        typename iterator_traits<BidirectionalIterator>::difference_type n =
-        1) {
-    advance(it, -n);
-    return it;
-  }
+prev(BidirectionalIterator it,
+         1)
+#if !defined(STD_ADVANCE_INLINE_LEVEL) || STD_ADVANCE_INLINE_LEVEL > 0
+{
+#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);
 
   template <class ExecutionPolicy, class ForwardIt, class T>
   ForwardIt find(ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
                  const T& value);
 

clang/test/Analysis/iterator-modelling.cpp

 // 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=false %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 %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"
 
 template <typename Container>
 long clang_analyzer_container_begin(const Container&);
 template <typename Container>
 long clang_analyzer_container_end(const Container&);
void copy_and_decrement2(const std::vector<int> &v) {
 
   auto i2 = i1;
   --i2;
 
   clang_analyzer_express(clang_analyzer_iterator_position(i1)); //expected-warning{{$v.end()}}
   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
 ///
 ////////////////////////////////////////////////////////////////////////////////
 
 // Copy