[Analyzer] Handle pointer implemented as iterators in iterator checkers

[baloghadamsoftware]

Summary

Iterators are an abstraction of pointers and in some data structures iterators may be implemented by pointers. This patch adds support for iterators implemented as pointers in all the iterator checkers (including iterator modeling).

[baloghadamsoftware]

clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp

256

This is the problematic point which is not working. I left the comments intentionally in the code.

The problem is that in postStmt we are after the operation. Thus the value of the operand (SubExpr) is not i anymore, but the former value of i (a pointer to a symbolic region initially). Instead, the result is i in case of prefix operators, but also the former value in case of postfix operators. This is correct, of course, because here, after the call the value of i was changed, thus it is not equal to the parameter. However, we need the region of i here and/or the new value bound to it (e.g. the pointer to an element region which is usually the result of a ++ or -- on a pointer to a symbolic region). How to reach that? Of course, in preStmt the operand is i as it should be. The same is true for binary operators += and -=.

[baloghadamsoftware]

clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp

256

Of course, I know it is all wrong to increment the former value. This is also not the goal, probably I cannot reuse handleIncrement() and the like here. The question is how to get the region of the variable or even better the new region (e.g. the pointer to element region) bound to it? In the prefix case I have the variable, but is there a generic way to get the region bound to it? By generic I mean that I hope that I do not have to branch on all possible lvalue expressions.

[baloghadamsoftware]

clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp

256

Wait! I know the solution! I will try it tomorrow.

[baloghadamsoftware]

Working.

[gamesh411]

clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp

625

Same as in the other patch. I think variable name TempState is too generic, should be AdvancedState or something more descriptive.

clang/test/Analysis/iterator-modeling.cpp

1880

Just being annoying here, but I saw you use // expected (with a space between the slash and expected) consistently elsewhere. Could you please also use that here in these tests as well? Being uniform with those helps spot other errors and typos IMHO.

[baloghadamsoftware]

Updated according to the comments.

[gamesh411]

Thanks, it LGTM now!

[thakis]

This (or a follow-up) broke tests on windows: http://45.33.8.238/win/18877/step_7.txt

Please take a look and revert for now if it takes a while to fix.

[baloghadamsoftware]

In D82185#2124948, @thakis wrote:

This (or a follow-up) broke tests on windows: http://45.33.8.238/win/18877/step_7.txt

Please take a look and revert for now if it takes a while to fix.

It was this one: D82385. I reverted that test function so one of the fixes now remains untested.

clang/lib/StaticAnalyzer/Checkers/InvalidatedIteratorChecker.cpp

 
 using namespace clang;
 using namespace ento;
 using namespace iterator;
 
 namespace {
 
 class InvalidatedIteratorChecker
-  : public Checker<check::PreCall> {
+  : public Checker<check::PreCall, check::PreStmt<UnaryOperator>,
+                   check::PreStmt<BinaryOperator>,
+                   check::PreStmt<ArraySubscriptExpr>,
+                   check::PreStmt<MemberExpr>> {
 
   std::unique_ptr<BugType> InvalidatedBugType;
 
   void verifyAccess(CheckerContext &C, const SVal &Val) const;
   void reportBug(const StringRef &Message, const SVal &Val,
                  CheckerContext &C, ExplodedNode *ErrNode) const;
 public:
   InvalidatedIteratorChecker();
 
   void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
+  void checkPreStmt(const UnaryOperator *UO, CheckerContext &C) const;
+  void checkPreStmt(const BinaryOperator *BO, CheckerContext &C) const;
+  void checkPreStmt(const ArraySubscriptExpr *ASE, CheckerContext &C) const;
+  void checkPreStmt(const MemberExpr *ME, CheckerContext &C) const;
 
 };
 
 } //namespace
 
 InvalidatedIteratorChecker::InvalidatedIteratorChecker() {
   InvalidatedBugType.reset(
       new BugType(this, "Iterator invalidated", "Misuse of STL APIs"));
if (Func->isOverloadedOperator() &&
     if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
       verifyAccess(C, InstCall->getCXXThisVal());
     } else {
       verifyAccess(C, Call.getArgSVal(0));
     }
   }
 }
 
+void InvalidatedIteratorChecker::checkPreStmt(const UnaryOperator *UO,
+                                              CheckerContext &C) const {
+  if (isa<CXXThisExpr>(UO->getSubExpr()))
+    return;
+
+  ProgramStateRef State = C.getState();
+  UnaryOperatorKind OK = UO->getOpcode();
+  SVal SubVal = State->getSVal(UO->getSubExpr(), C.getLocationContext());
+
+  if (isAccessOperator(OK)) {
+    verifyAccess(C, SubVal);
+  }
+}
+
+void InvalidatedIteratorChecker::checkPreStmt(const BinaryOperator *BO,
+                                              CheckerContext &C) const {
+  ProgramStateRef State = C.getState();
+  BinaryOperatorKind OK = BO->getOpcode();
+  SVal LVal = State->getSVal(BO->getLHS(), C.getLocationContext());
+
+  if (isAccessOperator(OK)) {
+    verifyAccess(C, LVal);
+  }
+}
+
+void InvalidatedIteratorChecker::checkPreStmt(const ArraySubscriptExpr *ASE,
+                                              CheckerContext &C) const {
+  ProgramStateRef State = C.getState();
+  SVal LVal = State->getSVal(ASE->getLHS(), C.getLocationContext());
+  verifyAccess(C, LVal);
+}
+
+void InvalidatedIteratorChecker::checkPreStmt(const MemberExpr *ME,
+                                              CheckerContext &C) const {
+  if (!ME->isArrow() || ME->isImplicitAccess())
+    return;
+
+  ProgramStateRef State = C.getState();
+  SVal BaseVal = State->getSVal(ME->getBase(), C.getLocationContext());
+  verifyAccess(C, BaseVal);
+}
+
 void InvalidatedIteratorChecker::verifyAccess(CheckerContext &C, const SVal &Val) const {
   auto State = C.getState();
   const auto *Pos = getIteratorPosition(State, Val);
   if (Pos && !Pos->isValid()) {
     auto *N = C.generateErrorNode(State);
     if (!N) {
       return;
     }

clang/lib/StaticAnalyzer/Checkers/Iterator.h

void Profile(llvm::FoldingSetNodeID &ID) const {
     ID.Add(End);
   }
 };
 
 class IteratorSymbolMap {};
 class IteratorRegionMap {};
 class ContainerMap {};
 
-using IteratorSymbolMapTy = CLANG_ENTO_PROGRAMSTATE_MAP(SymbolRef, IteratorPosition);
-using IteratorRegionMapTy = CLANG_ENTO_PROGRAMSTATE_MAP(const MemRegion *, IteratorPosition);
-using ContainerMapTy = CLANG_ENTO_PROGRAMSTATE_MAP(const MemRegion *, ContainerData);
+using IteratorSymbolMapTy =
+  CLANG_ENTO_PROGRAMSTATE_MAP(SymbolRef, IteratorPosition);
+using IteratorRegionMapTy =
+  CLANG_ENTO_PROGRAMSTATE_MAP(const MemRegion *, IteratorPosition);
+using ContainerMapTy =
+  CLANG_ENTO_PROGRAMSTATE_MAP(const MemRegion *, ContainerData);
 
 } // namespace iterator
 
 template<>
 struct ProgramStateTrait<iterator::IteratorSymbolMap>
   : public ProgramStatePartialTrait<iterator::IteratorSymbolMapTy> {
   static void *GDMIndex() { static int Index; return &Index; }
 };

 bool isIteratorType(const QualType &Type);
 bool isIterator(const CXXRecordDecl *CRD);
 bool isComparisonOperator(OverloadedOperatorKind OK);
 bool isInsertCall(const FunctionDecl *Func);
 bool isEraseCall(const FunctionDecl *Func);
 bool isEraseAfterCall(const FunctionDecl *Func);
 bool isEmplaceCall(const FunctionDecl *Func);
 bool isAccessOperator(OverloadedOperatorKind OK);
+bool isAccessOperator(UnaryOperatorKind OK);
+bool isAccessOperator(BinaryOperatorKind OK);
 bool isDereferenceOperator(OverloadedOperatorKind OK);
+bool isDereferenceOperator(UnaryOperatorKind OK);
+bool isDereferenceOperator(BinaryOperatorKind OK);
 bool isIncrementOperator(OverloadedOperatorKind OK);
+bool isIncrementOperator(UnaryOperatorKind OK);
 bool isDecrementOperator(OverloadedOperatorKind OK);
+bool isDecrementOperator(UnaryOperatorKind OK);
 bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK);
+bool isRandomIncrOrDecrOperator(BinaryOperatorKind OK);
 const ContainerData *getContainerData(ProgramStateRef State,
                                       const MemRegion *Cont);
 const IteratorPosition *getIteratorPosition(ProgramStateRef State,
                                             const SVal &Val);
 ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val,
                                     const IteratorPosition &Pos);
 ProgramStateRef createIteratorPosition(ProgramStateRef State, const SVal &Val,
                                        const MemRegion *Cont, const Stmt* S,

clang/lib/StaticAnalyzer/Checkers/Iterator.cpp

bool isEraseAfterCall(const FunctionDecl *Func) {
   return IdInfo->getName() == "erase_after";
 }
 
 bool isAccessOperator(OverloadedOperatorKind OK) {
   return isDereferenceOperator(OK) || isIncrementOperator(OK) ||
          isDecrementOperator(OK) || isRandomIncrOrDecrOperator(OK);
 }
 
+bool isAccessOperator(UnaryOperatorKind OK) {
+  return isDereferenceOperator(OK) || isIncrementOperator(OK) ||
+         isDecrementOperator(OK);
+}
+
+bool isAccessOperator(BinaryOperatorKind OK) {
+  return isDereferenceOperator(OK) || isRandomIncrOrDecrOperator(OK);
+}
+
 bool isDereferenceOperator(OverloadedOperatorKind OK) {
   return OK == OO_Star || OK == OO_Arrow || OK == OO_ArrowStar ||
          OK == OO_Subscript;
 }
 
+bool isDereferenceOperator(UnaryOperatorKind OK) {
+  return OK == UO_Deref;
+}
+
+bool isDereferenceOperator(BinaryOperatorKind OK) {
+  return OK == BO_PtrMemI;
+}
+
 bool isIncrementOperator(OverloadedOperatorKind OK) {
   return OK == OO_PlusPlus;
 }
 
+bool isIncrementOperator(UnaryOperatorKind OK) {
+  return OK == UO_PreInc || OK == UO_PostInc;
+}
+
 bool isDecrementOperator(OverloadedOperatorKind OK) {
   return OK == OO_MinusMinus;
 }
 
+bool isDecrementOperator(UnaryOperatorKind OK) {
+  return OK == UO_PreDec || OK == UO_PostDec;
+}
+
 bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK) {
   return OK == OO_Plus || OK == OO_PlusEqual || OK == OO_Minus ||
          OK == OO_MinusEqual;
 }
 
+bool isRandomIncrOrDecrOperator(BinaryOperatorKind OK) {
+  return OK == BO_Add || OK == BO_AddAssign ||
+         OK == BO_Sub || OK == BO_SubAssign;
+}
+
 const ContainerData *getContainerData(ProgramStateRef State,
                                       const MemRegion *Cont) {
   return State->get<ContainerMap>(Cont);
 }
 
 const IteratorPosition *getIteratorPosition(ProgramStateRef State,
                                             const SVal &Val) {
   if (auto Reg = Val.getAsRegion()) {

clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp

 
 using namespace clang;
 using namespace ento;
 using namespace iterator;
 
 namespace {
 
 class IteratorModeling
-    : public Checker<check::PostCall, check::PostStmt<MaterializeTemporaryExpr>,
+    : public Checker<check::PostCall, check::PostStmt<UnaryOperator>,
+                     check::PostStmt<BinaryOperator>,
+                     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 handlePtrIncrOrDecr(CheckerContext &C, const Expr *Iterator,
+                           OverloadedOperatorKind OK, SVal Offset) 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;
CallDescriptionMap<AdvanceFn> AdvanceLikeFunctions = {
       {{{"std", "next"}, 2}, &IteratorModeling::handleNext},
   };
 
 public:
   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 UnaryOperator *UO, CheckerContext &C) const;
+  void checkPostStmt(const BinaryOperator *BO, 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);
+bool isSimpleComparisonOperator(BinaryOperatorKind 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
if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(0))) {
         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.
+  //             container, then look for the first iterator argument of the
+  //             same type as the return value 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 (isIteratorType(Call.getArgExpr(i)->getType()) &&
+        Call.getArgExpr(i)->getType().getNonReferenceType().getDesugaredType(
+            C.getASTContext()).getTypePtr() ==
+        Call.getResultType().getDesugaredType(C.getASTContext()).getTypePtr()) {
       if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(i))) {
         assignToContainer(C, OrigExpr, Call.getReturnValue(),
                           Pos->getContainer());
         return;
       }
     }
   }
 }
if (Pos) {
     const auto *OldPos = getIteratorPosition(State, Loc);
     if (OldPos) {
       State = removeIteratorPosition(State, Loc);
       C.addTransition(State);
     }
   }
 }
 
+void IteratorModeling::checkPostStmt(const UnaryOperator *UO,
+                                     CheckerContext &C) const {
+  UnaryOperatorKind OK = UO->getOpcode();
+  if (!isIncrementOperator(OK) && !isDecrementOperator(OK))
+    return;
+
+  auto &SVB = C.getSValBuilder();
+  handlePtrIncrOrDecr(C, UO->getSubExpr(),
+                      isIncrementOperator(OK) ? OO_Plus : OO_Minus,
+                      SVB.makeArrayIndex(1));
+}
+
+void IteratorModeling::checkPostStmt(const BinaryOperator *BO,
+                                     CheckerContext &C) const {
+  ProgramStateRef State = C.getState();
+  BinaryOperatorKind OK = BO->getOpcode();
+  SVal RVal = State->getSVal(BO->getRHS(), C.getLocationContext());
+
+  if (isSimpleComparisonOperator(BO->getOpcode())) {
+    SVal LVal = State->getSVal(BO->getLHS(), C.getLocationContext());
+    SVal Result = State->getSVal(BO, C.getLocationContext());
+    handleComparison(C, BO, Result, LVal, RVal,
+                     BinaryOperator::getOverloadedOperator(OK));
+  } else if (isRandomIncrOrDecrOperator(OK)) {
+    handlePtrIncrOrDecr(C, BO->getLHS(),
+                        BinaryOperator::getOverloadedOperator(OK), RVal);
+  }
+}
+
 void IteratorModeling::checkPostStmt(const MaterializeTemporaryExpr *MTE,
                                      CheckerContext &C) const {
   /* Transfer iterator state to temporary objects */
   auto State = C.getState();
   const auto *Pos = getIteratorPosition(State, C.getSVal(MTE->getSubExpr()));
   if (!Pos)
     return;
   State = setIteratorPosition(State, C.getSVal(MTE), *Pos);
if (AdvancedState) {
 
     State = setIteratorPosition(State, TgtVal, *NewPos);
     C.addTransition(State);
   } else {
     assignToContainer(C, CE, TgtVal, Pos->getContainer());
   }
 }
 
+void IteratorModeling::handlePtrIncrOrDecr(CheckerContext &C,
+                                           const Expr *Iterator,
+                                           OverloadedOperatorKind OK,
+                                           SVal Offset) const {
+  QualType PtrType = Iterator->getType();
+  if (!PtrType->isPointerType())
+    return;
+  QualType ElementType = PtrType->getPointeeType();
+
+  ProgramStateRef State = C.getState();
+  SVal OldVal = State->getSVal(Iterator, C.getLocationContext());
+
+  const IteratorPosition *OldPos = getIteratorPosition(State, OldVal);
+  if (!OldPos)
+    return;
+
+  SVal NewVal;
+  if (OK == OO_Plus || OK == OO_PlusEqual)
+    NewVal = State->getLValue(ElementType, Offset, OldVal);
+  else {
+    const llvm::APSInt &OffsetInt =
+      Offset.castAs<nonloc::ConcreteInt>().getValue();
+    auto &BVF = C.getSymbolManager().getBasicVals();
+    SVal NegatedOffset = nonloc::ConcreteInt(BVF.getValue(-OffsetInt));
+    NewVal = State->getLValue(ElementType, NegatedOffset, OldVal);
+  }
+
+  // `AdvancedState` is a state where the position of `Old` is advanced. We
+  // only need this state to retrieve the new position, but we do not want
+  // ever to change the position of `OldVal`.
+  auto AdvancedState = advancePosition(State, OldVal, OK, Offset);
+  if (AdvancedState) {
+    const IteratorPosition *NewPos = getIteratorPosition(AdvancedState, OldVal);
+    assert(NewPos &&
+           "Iterator should have position after successful advancement");
+
+    ProgramStateRef NewState = setIteratorPosition(State, NewVal, *NewPos);
+    C.addTransition(NewState);
+  } else {
+    assignToContainer(C, Iterator, NewVal, OldPos->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 {

 }
 
 namespace {
 
 bool isSimpleComparisonOperator(OverloadedOperatorKind OK) {
   return OK == OO_EqualEqual || OK == OO_ExclaimEqual;
 }
 
+bool isSimpleComparisonOperator(BinaryOperatorKind OK) {
+  return OK == BO_EQ || OK == BO_NE;
+}
+
 ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val) {
   if (auto Reg = Val.getAsRegion()) {
     Reg = Reg->getMostDerivedObjectRegion();
     return State->remove<IteratorRegionMap>(Reg);
   } else if (const auto Sym = Val.getAsSymbol()) {
     return State->remove<IteratorSymbolMap>(Sym);
   } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
     return State->remove<IteratorRegionMap>(LCVal->getRegion());

clang/lib/StaticAnalyzer/Checkers/IteratorRangeChecker.cpp

 
 using namespace clang;
 using namespace ento;
 using namespace iterator;
 
 namespace {
 
 class IteratorRangeChecker
-  : public Checker<check::PreCall> {
+  : public Checker<check::PreCall, check::PreStmt<UnaryOperator>,
+                   check::PreStmt<BinaryOperator>,
+                   check::PreStmt<ArraySubscriptExpr>,
+                   check::PreStmt<MemberExpr>> {
 
   std::unique_ptr<BugType> OutOfRangeBugType;
 
   void verifyDereference(CheckerContext &C, SVal Val) const;
   void verifyIncrement(CheckerContext &C, SVal Iter) const;
   void verifyDecrement(CheckerContext &C, SVal Iter) const;
   void verifyRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op,
                               SVal LHS, SVal RHS) const;
   void verifyAdvance(CheckerContext &C, SVal LHS, SVal RHS) const;
   void verifyPrev(CheckerContext &C, SVal LHS, SVal RHS) const;
   void verifyNext(CheckerContext &C, SVal LHS, SVal RHS) const;
   void reportBug(const StringRef &Message, SVal Val, CheckerContext &C,
                  ExplodedNode *ErrNode) const;
 
 public:
   IteratorRangeChecker();
 
   void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
+  void checkPreStmt(const UnaryOperator *UO, CheckerContext &C) const;
+  void checkPreStmt(const BinaryOperator *BO, CheckerContext &C) const;
+  void checkPreStmt(const ArraySubscriptExpr *ASE, CheckerContext &C) const;
+  void checkPreStmt(const MemberExpr *ME, CheckerContext &C) const;
 
   using AdvanceFn = void (IteratorRangeChecker::*)(CheckerContext &, SVal,
                                                    SVal) const;
 
   CallDescriptionMap<AdvanceFn> AdvanceFunctions = {
       {{{"std", "advance"}, 2}, &IteratorRangeChecker::verifyAdvance},
       {{{"std", "prev"}, 2}, &IteratorRangeChecker::verifyPrev},
       {{{"std", "next"}, 2}, &IteratorRangeChecker::verifyNext},
if (Verifier) {
         (this->**Verifier)(
             C, Call.getArgSVal(0),
             nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
       }
     }
   }
 }
 
+void IteratorRangeChecker::checkPreStmt(const UnaryOperator *UO,
+                                        CheckerContext &C) const {
+  if (isa<CXXThisExpr>(UO->getSubExpr()))
+    return;
+
+  ProgramStateRef State = C.getState();
+  UnaryOperatorKind OK = UO->getOpcode();
+  SVal SubVal = State->getSVal(UO->getSubExpr(), C.getLocationContext());
+
+  if (isDereferenceOperator(OK)) {
+    verifyDereference(C, SubVal);
+  } else if (isIncrementOperator(OK)) {
+    verifyIncrement(C, SubVal);
+  } else if (isDecrementOperator(OK)) {
+    verifyDecrement(C, SubVal);
+  }
+}
+
+void IteratorRangeChecker::checkPreStmt(const BinaryOperator *BO,
+                                        CheckerContext &C) const {
+  ProgramStateRef State = C.getState();
+  BinaryOperatorKind OK = BO->getOpcode();
+  SVal LVal = State->getSVal(BO->getLHS(), C.getLocationContext());
+
+  if (isDereferenceOperator(OK)) {
+    verifyDereference(C, LVal);
+  } else if (isRandomIncrOrDecrOperator(OK)) {
+    SVal RVal = State->getSVal(BO->getRHS(), C.getLocationContext());
+    verifyRandomIncrOrDecr(C, BinaryOperator::getOverloadedOperator(OK), LVal,
+                           RVal);
+  }
+}
+
+void IteratorRangeChecker::checkPreStmt(const ArraySubscriptExpr *ASE,
+                                        CheckerContext &C) const {
+  ProgramStateRef State = C.getState();
+  SVal LVal = State->getSVal(ASE->getLHS(), C.getLocationContext());
+  verifyDereference(C, LVal);
+}
+
+void IteratorRangeChecker::checkPreStmt(const MemberExpr *ME,
+                                        CheckerContext &C) const {
+  if (!ME->isArrow() || ME->isImplicitAccess())
+    return;
+
+  ProgramStateRef State = C.getState();
+  SVal BaseVal = State->getSVal(ME->getBase(), C.getLocationContext());
+  verifyDereference(C, BaseVal);
+}
+
 void IteratorRangeChecker::verifyDereference(CheckerContext &C,
                                              SVal Val) const {
   auto State = C.getState();
   const auto *Pos = getIteratorPosition(State, Val);
   if (Pos && isPastTheEnd(State, *Pos)) {
     auto *N = C.generateErrorNode(State);
     if (!N)
       return;

clang/lib/StaticAnalyzer/Checkers/MismatchedIteratorChecker.cpp

 
 using namespace clang;
 using namespace ento;
 using namespace iterator;
 
 namespace {
 
 class MismatchedIteratorChecker
-  : public Checker<check::PreCall> {
+  : public Checker<check::PreCall, check::PreStmt<BinaryOperator>> {
 
   std::unique_ptr<BugType> MismatchedBugType;
 
   void verifyMatch(CheckerContext &C, const SVal &Iter,
                    const MemRegion *Cont) const;
   void verifyMatch(CheckerContext &C, const SVal &Iter1,
                    const SVal &Iter2) const;
   void reportBug(const StringRef &Message, const SVal &Val1,
                  const SVal &Val2, CheckerContext &C,
                  ExplodedNode *ErrNode) const;
   void reportBug(const StringRef &Message, const SVal &Val,
                  const MemRegion *Reg, CheckerContext &C,
                  ExplodedNode *ErrNode) const;
 
 public:
   MismatchedIteratorChecker();
 
   void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
+  void checkPreStmt(const BinaryOperator *BO, CheckerContext &C) const;
 
 };
 
 } // namespace
 
 MismatchedIteratorChecker::MismatchedIteratorChecker() {
   MismatchedBugType.reset(
       new BugType(this, "Iterator(s) mismatched", "Misuse of STL APIs",
if (Func->isOverloadedOperator() &&
     // works on multiple containers using iterators takes different
     // template parameters for different containers. So we can safely
     // assume that passing iterators of different containers as arguments
     // whose type replaces the same template parameter is a bug.
     //
     // Example:
     // template<typename I1, typename I2>
     // void f(I1 first1, I1 last1, I2 first2, I2 last2);
-    // 
+    //
     // In this case the first two arguments to f() must be iterators must belong
     // to the same container and the last to also to the same container but
     // not necessarily to the same as the first two.
 
     const auto *Templ = Func->getPrimaryTemplate();
     if (!Templ)
       return;
 
for (size_t I = 0; I < TParams->size(); ++I) {
         } else {
           verifyMatch(C, LHS, Call.getArgSVal(J));
         }
       }
     }
   }
 }
 
+void MismatchedIteratorChecker::checkPreStmt(const BinaryOperator *BO,
+                                             CheckerContext &C) const {
+  if (!BO->isComparisonOp())
+    return;
+
+  ProgramStateRef State = C.getState();
+  SVal LVal = State->getSVal(BO->getLHS(), C.getLocationContext());
+  SVal RVal = State->getSVal(BO->getRHS(), C.getLocationContext());
+  verifyMatch(C, LVal, RVal);
+}
+
 void MismatchedIteratorChecker::verifyMatch(CheckerContext &C, const SVal &Iter,
                                             const MemRegion *Cont) const {
   // Verify match between a container and the container of an iterator
   Cont = Cont->getMostDerivedObjectRegion();
 
   if (const auto *ContSym = Cont->getSymbolicBase()) {
     if (isa<SymbolConjured>(ContSym->getSymbol()))
       return;

clang/test/Analysis/invalidated-iterator.cpp

void invalidated_subscript(std::vector<int> &V) {
   i[1]; // expected-warning{{Invalidated iterator accessed}}
 }
 
 void assignment(std::vector<int> &V) {
   auto i = V.cbegin();
   V.erase(i);
   auto j = V.cbegin(); // no-warning
 }
+
+template<typename T>
+struct cont_with_ptr_iterator {
+  T *begin() const;
+  T *end() const;
+  T &operator[](size_t);
+  void push_back(const T&);
+  T* erase(T*);
+};
+
+void invalidated_dereference_end_ptr_iterator(cont_with_ptr_iterator<int> &C) {
+  auto i = C.begin();
+  C.erase(i);
+  (void) *i; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void invalidated_prefix_increment_end_ptr_iterator(
+    cont_with_ptr_iterator<int> &C) {
+  auto i = C.begin();
+  C.erase(i);
+  ++i; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void invalidated_prefix_decrement_end_ptr_iterator(
+    cont_with_ptr_iterator<int> &C) {
+  auto i = C.begin() + 1;
+  C.erase(i);
+  --i; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void invalidated_postfix_increment_end_ptr_iterator(
+    cont_with_ptr_iterator<int> &C) {
+  auto i = C.begin();
+  C.erase(i);
+  i++; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void invalidated_postfix_decrement_end_ptr_iterator(
+    cont_with_ptr_iterator<int> &C) {
+  auto i = C.begin() + 1;
+  C.erase(i);
+  i--; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void invalidated_increment_by_2_end_ptr_iterator(
+    cont_with_ptr_iterator<int> &C) {
+  auto i = C.begin();
+  C.erase(i);
+  i += 2; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void invalidated_increment_by_2_copy_end_ptr_iterator(
+    cont_with_ptr_iterator<int> &C) {
+  auto i = C.begin();
+  C.erase(i);
+  auto j = i + 2; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void invalidated_decrement_by_2_end_ptr_iterator(
+    cont_with_ptr_iterator<int> &C) {
+  auto i = C.begin();
+  C.erase(i);
+  i -= 2; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void invalidated_decrement_by_2_copy_end_ptr_iterator(
+    cont_with_ptr_iterator<int> &C) {
+  auto i = C.begin();
+  C.erase(i);
+  auto j = i - 2; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void invalidated_subscript_end_ptr_iterator(cont_with_ptr_iterator<int> &C) {
+  auto i = C.begin();
+  C.erase(i);
+  (void) i[1]; // expected-warning{{Invalidated iterator accessed}}
+}

clang/test/Analysis/iterator-modeling.cpp

 #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&);
 template <typename Iterator>
 long clang_analyzer_iterator_position(const Iterator&);
+long clang_analyzer_iterator_position(int*);
 template <typename Iterator>
 void* clang_analyzer_iterator_container(const Iterator&);
 template <typename Iterator>
 bool clang_analyzer_iterator_validity(const Iterator&);
 
 void clang_analyzer_denote(long, const char*);
 void clang_analyzer_express(long);
 void clang_analyzer_eval(bool);
void non_std_find(std::vector<int> &V, int e) {
   clang_analyzer_eval(clang_analyzer_container_end(V) ==
                       clang_analyzer_iterator_position(first)); // expected-warning@-1{{FALSE}} expected-warning@-1{{TRUE}}
   if (V.end() != first) {
     clang_analyzer_eval(clang_analyzer_container_end(V) ==
                         clang_analyzer_iterator_position(first)); // expected-warning@-1{{FALSE}}
   }
 }
 
+template<typename T>
+struct cont_with_ptr_iterator {
+  typedef T* iterator;
+  T* begin() const;
+  T* end() const;
+};
+
+void begin_ptr_iterator(const cont_with_ptr_iterator<int> &c) {
+  auto i = c.begin();
+
+  clang_analyzer_eval(clang_analyzer_iterator_container(i) == &c); // expected-warning{{TRUE}}
+  clang_analyzer_denote(clang_analyzer_container_begin(c), "$c.begin()");
+  clang_analyzer_express(clang_analyzer_iterator_position(i)); // expected-warning{{$c.begin()}}
+
+  if (i != c.begin()) {
+    clang_analyzer_warnIfReached();
+  }
+  }
+
+void prefix_increment_ptr_iterator(const cont_with_ptr_iterator<int> &c) {
+  auto i = c.begin();
+
+  clang_analyzer_denote(clang_analyzer_container_begin(c), "$c.begin()");
+
+  auto j = ++i;
+
+  clang_analyzer_express(clang_analyzer_iterator_position(i)); // expected-warning{{$c.begin() + 1}}
+  clang_analyzer_express(clang_analyzer_iterator_position(j)); // expected-warning{{$c.begin() + 1}}
+}
+
+void prefix_decrement_ptr_iterator(const cont_with_ptr_iterator<int> &c) {
+  auto i = c.end();
+
+  clang_analyzer_denote(clang_analyzer_container_end(c), "$c.end()");
+
+  auto j = --i;
+
+  clang_analyzer_express(clang_analyzer_iterator_position(i)); // expected-warning{{$c.end() - 1}}
+  clang_analyzer_express(clang_analyzer_iterator_position(j)); // expected-warning{{$c.end() - 1}}
+}
+
+void postfix_increment_ptr_iterator(const cont_with_ptr_iterator<int> &c) {
+  auto i = c.begin();
+
+  clang_analyzer_denote(clang_analyzer_container_begin(c), "$c.begin()");
+
+  auto j = i++;
+
+  clang_analyzer_express(clang_analyzer_iterator_position(i)); // expected-warning{{$c.begin() + 1}}
+  clang_analyzer_express(clang_analyzer_iterator_position(j)); // expected-warning{{$c.begin()}}
+}
+
+void postfix_decrement_ptr_iterator(const cont_with_ptr_iterator<int> &c) {
+  auto i = c.end();
+
+  clang_analyzer_denote(clang_analyzer_container_end(c), "$c.end()");
+
+  auto j = i--;
+
+  clang_analyzer_express(clang_analyzer_iterator_position(i)); // expected-warning{{$c.end() - 1}}
+  clang_analyzer_express(clang_analyzer_iterator_position(j)); // expected-warning{{$c.end()}}
+}
+
+void plus_equal_ptr_iterator(const cont_with_ptr_iterator<int> &c) {
+  auto i = c.begin();
+
+  clang_analyzer_denote(clang_analyzer_container_begin(c), "$c.begin()");
+
+  i += 2;
+
+  clang_analyzer_express(clang_analyzer_iterator_position(i)); // expected-warning{{$c.begin() + 2}}
+}
+
+void minus_equal_ptr_iterator(const cont_with_ptr_iterator<int> &c) {
+  auto i = c.end();
+
+  clang_analyzer_denote(clang_analyzer_container_end(c), "$c.end()");
+
+  i -= 2;
+
+  clang_analyzer_express(clang_analyzer_iterator_position(i)); // expected-warning{{$c.end() - 2}}
+}
+
+void plus_ptr_iterator(const cont_with_ptr_iterator<int> &c) {
+  auto i1 = c.begin();
+
+  clang_analyzer_denote(clang_analyzer_container_begin(c), "$c.begin()");
+
+  auto i2 = i1 + 2;
+
+  clang_analyzer_eval(clang_analyzer_iterator_container(i2) == &c); // expected-warning{{TRUE}}
+  clang_analyzer_express(clang_analyzer_iterator_position(i1)); // expected-warning{{$c.begin()}}
+  clang_analyzer_express(clang_analyzer_iterator_position(i2)); // expected-warning{{$c.begin() + 2}}
+}
+
+void minus_ptr_iterator(const cont_with_ptr_iterator<int> &c) {
+  auto i1 = c.end();
+
+  clang_analyzer_denote(clang_analyzer_container_end(c), "$c.end()");
+
+  auto i2 = i1 - 2;
+
+  clang_analyzer_eval(clang_analyzer_iterator_container(i2) == &c); // expected-warning{{TRUE}}
+  clang_analyzer_express(clang_analyzer_iterator_position(i1)); // expected-warning{{$c.end()}}
+  clang_analyzer_express(clang_analyzer_iterator_position(i2)); // expected-warning{{$c.end() - 2}}
+}
+
 void clang_analyzer_printState();
 
 void print_state(std::vector<int> &V) {
   const auto i0 = V.cbegin();
   const auto i1 = V.cbegin() + 1;
   clang_analyzer_printState();
 
   // CHECK:      "checker_messages": [

clang/test/Analysis/iterator-range.cpp

 void deref_end_after_pop_back(std::vector<int> &V) {
   const auto i = --V.end();
 
   V.pop_back(); // expected-note{{Container 'V' shrank from the back by 1 position}}
 
   *i; // expected-warning{{Past-the-end iterator dereferenced}}
       // expected-note@-1{{Past-the-end iterator dereferenced}}
 }
+
+template<typename T>
+struct cont_with_ptr_iterator {
+  T* begin() const;
+  T* end() const;
+};
+
+void deref_end_ptr_iterator(const cont_with_ptr_iterator<S> &c) {
+  auto i = c.end();
+  (void) *i; // expected-warning{{Past-the-end iterator dereferenced}}
+             // expected-note@-1{{Past-the-end iterator dereferenced}}
+}
+
+void array_deref_end_ptr_iterator(const cont_with_ptr_iterator<S> &c) {
+  auto i = c.end();
+  (void) i[0]; // expected-warning{{Past-the-end iterator dereferenced}}
+               // expected-note@-1{{Past-the-end iterator dereferenced}}
+}
+
+void arrow_deref_end_ptr_iterator(const cont_with_ptr_iterator<S> &c) {
+  auto i = c.end();
+  (void) i->n; // expected-warning{{Past-the-end iterator dereferenced}}
+               // expected-note@-1{{Past-the-end iterator dereferenced}}
+}
+
+void arrow_star_deref_end_ptr_iterator(const cont_with_ptr_iterator<S> &c,
+                                       int S::*p) {
+  auto i = c.end();
+  (void)(i->*p); // expected-warning{{Past-the-end iterator dereferenced}}
+                 // expected-note@-1{{Past-the-end iterator dereferenced}}
+}
+
+void prefix_incr_end_ptr_iterator(const cont_with_ptr_iterator<S> &c) {
+  auto i = c.end();
+  ++i; // expected-warning{{Iterator incremented behind the past-the-end iterator}}
+       // expected-note@-1{{Iterator incremented behind the past-the-end iterator}}
+}
+
+void postfix_incr_end_ptr_iterator(const cont_with_ptr_iterator<S> &c) {
+  auto i = c.end();
+  i++; // expected-warning{{Iterator incremented behind the past-the-end iterator}}
+       // expected-note@-1{{Iterator incremented behind the past-the-end iterator}}
+}
+
+void prefix_decr_begin_ptr_iterator(const cont_with_ptr_iterator<S> &c) {
+  auto i = c.begin();
+  --i; // expected-warning{{Iterator decremented ahead of its valid range}}
+       // expected-note@-1{{Iterator decremented ahead of its valid range}}
+}
+
+void postfix_decr_begin_ptr_iterator(const cont_with_ptr_iterator<S> &c) {
+  auto i = c.begin();
+  i--; // expected-warning{{Iterator decremented ahead of its valid range}}
+       // expected-note@-1{{Iterator decremented ahead of its valid range}}
+}
+
+void prefix_add_2_end_ptr_iterator(const cont_with_ptr_iterator<S> &c) {
+  auto i = c.end();
+  (void)(i + 2); // expected-warning{{Iterator incremented behind the past-the-end iterator}}
+                 // expected-note@-1{{Iterator incremented behind the past-the-end iterator}}
+}
+
+void postfix_add_assign_2_end_ptr_iterator(const cont_with_ptr_iterator<S> &c) {
+  auto i = c.end();
+  i += 2; // expected-warning{{Iterator incremented behind the past-the-end iterator}}
+          // expected-note@-1{{Iterator incremented behind the past-the-end iterator}}
+}
+
+void prefix_minus_2_begin_ptr_iterator(const cont_with_ptr_iterator<S> &c) {
+  auto i = c.begin();
+  (void)(i - 2); // expected-warning{{Iterator decremented ahead of its valid range}}
+                 // expected-note@-1{{Iterator decremented ahead of its valid range}}
+}
+
+void postfix_minus_assign_2_begin_ptr_iterator(
+    const cont_with_ptr_iterator<S> &c) {
+  auto i = c.begin();
+  i -= 2; // expected-warning{{Iterator decremented ahead of its valid range}}
+          // expected-note@-1{{Iterator decremented ahead of its valid range}}
+}
+

clang/test/Analysis/mismatched-iterator.cpp

void ignore_conjured1() {
   V2.erase(V1.cbegin()); // no-warning
 }
 
 void ignore_conjured2() {
   std::vector<int> &V1 = return_vector_ref(), &V2 = return_vector_ref();
 
   if (V1.cbegin() == V2.cbegin()) {} //no-warning
 }
+
+template<typename T>
+struct cont_with_ptr_iterator {
+  T *begin() const;
+  T *end() const;
+};
+
+void comparison_ptr_iterator(cont_with_ptr_iterator<int> &C1,
+                             cont_with_ptr_iterator<int> &C2) {
+  if (C1.begin() != C2.end()) {} // expected-warning{{Iterators of different containers used where the same container is expected}}
+}
+