[Analyzer] Various fixes for the IteratorPastEnd checker

[baloghadamsoftware]

Summary

This patch fixes some issues for the IteratorPastEnd checkers. There are basically two main issues this patch targets: one is the handling of assignments between iterators, the other one is correct handling of the +, +=, - and -= operators of random-access iterators. The handling of these operators also checks the sign of the argument, e.g. a negative number for + or += is handled as decrementation.

[NoQ]

Thanks for the update, most welcome!

lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp

229

We usually write these as

const auto *InstCall = cast<CXXInstanceCall>(&Call);

Mostly because our custom cast<> has an assertion inside.

476

I'd suggest renaming the parameters to "LHS" and "RHS" or something like that, so that not to confuse those with "lvalue" and "rvalue".

492

Is there a test case for this hack?

I'd also consider inspecting the AST (probably before passing the values to handleRandomIncrOrDecr()) and making the decision based on that. Because even though this pattern ("if a value is a loc and we expect a nonloc, do an extra dereference") is present in many places in the analyzer, in most of these places it doesn't work correctly (what if we try to discriminate between int* and int*&?).

515

I think incrementing end() by 0 is not a bug (?)

[baloghadamsoftware]

Updates based on the comments.

[baloghadamsoftware]

lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp

492

I just want to get the sign of the integer value (if it is available). It turned out that I cannot do comparison between loc and nonloc. (Strange, because I can do anything else). After I created this hack, the Analyzer did not crash anymore on the llvm/clang code.

I do not fully understand what I should fix here and how? In this particular place we expect some integer, thus no int* or int*&.

515

I think it is not a bug, but how to solve it properly? If I chose just greaterThanZero, then we have the same problem for decrementing end() by 0. Is it worth to create three states here?

[NoQ]

lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp

492

Loc value, essentially, *is* a pointer or reference value. If you're getting a Loc, then your expectations of an integer are not met in the actual code. In this case you *want* to know why they are not met, otherwise you may avoid the crash, but do incorrect things and run into false positives. So i'd rather have this investigated carefully.

You say that you are crashing otherwise - and then it should be trivial for you to attach a debugger and dump() the expression for which you expect to take the integer value, and see why it suddenly has a pointer type in a particular case. From that you'd easily see what to do.

Also, crashes are often easy to auto-reduce using tools like creduce. Unlike false positives, which may turn into true positives during reduction.

If you still don't see the reason why your workaround is necessary and what exactly it does, could you attach a preprocessed file and an analyzer runline for the crash, so that we could have a look together?

515

Yep, i believe that indeed, we need three states here. There are three possible cases.

[baloghadamsoftware]

lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp

492

Just to be clear: I know why it crashes without the hack: I simply cannot compare loc and nonloc. Since concrete 0 is nonloc I need another nonloc. I suppose this happens if an integer reference is passed to the operator +, +=, - or -=. So I thought that dereferencing it by getting the raw SVal is the correct thing to do.

515

OK, I will do it.

[NoQ]

lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp

492

Yep, in this case the correct thing to do would be to check AST types rather than SVal types. Eg.,

if (Arg->getType()->isReferenceType())
 value = State->getRawSVal(*loc);

(you might need to do it in the caller function, which still has access to the expressions)

It is better this way because expectations are explicitly stated, and the assertion would still catch the situation when expectations are not met.

Also, please still add a test case to cover this branch :)

[baloghadamsoftware]

checkBind replaces checking of DeclStmt, CXXConstructExpr and assignment operators. Incremention by 0 is not a bug anymore regardless the position of the iterator.

[baloghadamsoftware]

lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp

492

I tried it and failed in std::vector::back(). It seems that the problem is not the reference, but loc::ConcreteInt. I added a test case, but in our mocked vector the integer 1 in *(end()-1) is nonloc::ConcreteInt, but in the real one it is loc::ConcreteInt. I do not see why is there a difference, neither do I know how could something be a location and a concrete integer at once. What is loc::ConcreteInt and what to do with it?

[NoQ]

lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp

492

What is loc::ConcreteInt and what to do with it?

It is a concrete memory address. The null pointer, for example, or maybe a fixed magic pointer in some embedded driver code.

Could you post an AST dump for the real (end()-1)on which you are failing? It might be that we end up looking at the other operator-() as in (end() - begin()), while iterators are implemented as pointers; no idea how that could be, but i'm suspecting something like that.

[NoQ]

lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp

492

Also, dereferencing a loc::ConcreteInt loc (through getSVal/getRawSVal) would always yield UndefinedVal value.

[NoQ]

Hello,

Because i couldn't reproduce the loc-nonloc problem on my standard library, could you share a preprocessed file with the issue? I'm really curious at what's going on here, and it's the only issue remaining, so maybe we could squash it together.

[baloghadamsoftware]

Whole checker superseeded by D31975.

lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp

bool operator!=(const IteratorComparison &X) const {
     return Left != X.Left || Right != X.Right || Equality != X.Equality;
   }
   void Profile(llvm::FoldingSetNodeID &ID) const { ID.AddInteger(Equality); }
 };
 
 class IteratorPastEndChecker
     : public Checker<
           check::PreCall, check::PostCall, check::PreStmt<CXXOperatorCallExpr>,
-          check::PostStmt<CXXConstructExpr>, check::PostStmt<DeclStmt>,
-          check::PostStmt<MaterializeTemporaryExpr>, check::BeginFunction,
-          check::DeadSymbols, eval::Assume, eval::Call> {
-  mutable IdentifierInfo *II_find = nullptr,
-                         *II_find_end = nullptr, *II_find_first_of = nullptr,
-                         *II_find_if = nullptr, *II_find_if_not = nullptr,
-                         *II_lower_bound = nullptr, *II_upper_bound = nullptr,
-                         *II_search = nullptr, *II_search_n = nullptr;
+          check::PostStmt<MaterializeTemporaryExpr>, check::Bind,
+          check::BeginFunction, check::DeadSymbols, eval::Assume, eval::Call> {
+  mutable IdentifierInfo *II_find = nullptr, *II_find_end = nullptr,
+                         *II_find_first_of = nullptr, *II_find_if = nullptr,
+                         *II_find_if_not = nullptr, *II_lower_bound = nullptr,
+                         *II_upper_bound = nullptr, *II_search = nullptr,
+                         *II_search_n = nullptr;
 
   std::unique_ptr<BugType> PastEndBugType;
 
-  void handleComparison(CheckerContext &C, const SVal &RetVal, const SVal &LVal,
-                        const SVal &RVal, OverloadedOperatorKind Op) const;
+  void handleComparison(CheckerContext &C, const SVal &RetVal, const SVal &LHS,
+                        const SVal &RHS, OverloadedOperatorKind Op) const;
+  void handleRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op,
+                              const SVal &RetVal, const SVal &LHS,
+                              const SVal &RHS, QualType RHSType,
+                              bool PreCheck) const;
   void handleAccess(CheckerContext &C, const SVal &Val) const;
   void handleDecrement(CheckerContext &C, const SVal &Val) const;
   void handleEnd(CheckerContext &C, const SVal &RetVal) const;
 
   bool evalFind(CheckerContext &C, const CallExpr *CE) const;
   bool evalFindEnd(CheckerContext &C, const CallExpr *CE) const;
   bool evalFindFirstOf(CheckerContext &C, const CallExpr *CE) const;
   bool evalFindIf(CheckerContext &C, const CallExpr *CE) const;

 
 public:
   IteratorPastEndChecker();
 
   void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
   void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
   void checkPreStmt(const CXXOperatorCallExpr *COCE, CheckerContext &C) const;
   void checkBeginFunction(CheckerContext &C) const;
-  void checkPostStmt(const CXXConstructExpr *CCE, CheckerContext &C) const;
-  void checkPostStmt(const DeclStmt *DS, CheckerContext &C) const;
+  void checkBind(SVal Loc, SVal Val, const Stmt *S, CheckerContext &C) const;
   void checkPostStmt(const MaterializeTemporaryExpr *MTE,
                      CheckerContext &C) const;
   void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
   ProgramStateRef evalAssume(ProgramStateRef State, SVal Cond,
                              bool Assumption) const;
   bool evalCall(const CallExpr *CE, CheckerContext &C) const;
 };
 }

 
 namespace {
 
 bool isIteratorType(const QualType &Type);
 bool isIterator(const CXXRecordDecl *CRD);
 bool isEndCall(const FunctionDecl *Func);
 bool isSimpleComparisonOperator(OverloadedOperatorKind OK);
 bool isAccessOperator(OverloadedOperatorKind OK);
+bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK);
 bool isDecrementOperator(OverloadedOperatorKind OK);
 BinaryOperator::Opcode getOpcode(const SymExpr *SE);
 const RegionOrSymbol getRegionOrSymbol(const SVal &Val);
 const ProgramStateRef processComparison(ProgramStateRef State,
-                                        RegionOrSymbol LVal,
-                                        RegionOrSymbol RVal, bool Equal);
+                                        RegionOrSymbol LHS, RegionOrSymbol RHS,
+                                        bool Equal);
 const ProgramStateRef saveComparison(ProgramStateRef State,
-                                     const SymExpr *Condition, const SVal &LVal,
-                                     const SVal &RVal, bool Eq);
+                                     const SymExpr *Condition, const SVal &LHS,
+                                     const SVal &RHS, bool Eq);
 const IteratorComparison *loadComparison(ProgramStateRef State,
                                          const SymExpr *Condition);
 const IteratorPosition *getIteratorPosition(ProgramStateRef State,
                                             const SVal &Val);
 const IteratorPosition *getIteratorPosition(ProgramStateRef State,
                                             RegionOrSymbol RegOrSym);
 ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val,
                                     IteratorPosition Pos);
 ProgramStateRef setIteratorPosition(ProgramStateRef State,
                                     RegionOrSymbol RegOrSym,
                                     IteratorPosition Pos);
+ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val);
 ProgramStateRef adjustIteratorPosition(ProgramStateRef State,
                                        RegionOrSymbol RegOrSym,
                                        IteratorPosition Pos, bool Equal);
 bool contradictingIteratorPositions(IteratorPosition Pos1,
                                     IteratorPosition Pos2, bool Equal);
 }
 
 IteratorPastEndChecker::IteratorPastEndChecker() {
   PastEndBugType.reset(
       new BugType(this, "Iterator Past End", "Misuse of STL APIs"));
   PastEndBugType->setSuppressOnSink(true);
 }
 
 void IteratorPastEndChecker::checkPreCall(const CallEvent &Call,
                                           CheckerContext &C) const {
   // Check for access past end
-  const auto *Func = Call.getDecl()->getAsFunction();
+  const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
   if (!Func)
     return;
   if (Func->isOverloadedOperator()) {
-    if (isAccessOperator(Func->getOverloadedOperator())) {
+    if (isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) {
+      if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
+        if (Call.getNumArgs() >= 1) {
+          handleRandomIncrOrDecr(C, Func->getOverloadedOperator(),
+                                 Call.getReturnValue(),
+                                 InstCall->getCXXThisVal(), Call.getArgSVal(0),
+                                 Call.getArgExpr(0)->getType(), true);
+        }
+      } else {
+        if (Call.getNumArgs() >= 2) {
+          handleRandomIncrOrDecr(C, Func->getOverloadedOperator(),
+                                 Call.getReturnValue(), Call.getArgSVal(0),
+                                 Call.getArgSVal(1),
+                                 Call.getArgExpr(1)->getType(), true);
+        }
+      }
+    } else if (isAccessOperator(Func->getOverloadedOperator())) {
       if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
         handleAccess(C, InstCall->getCXXThisVal());
       } else {
         handleAccess(C, Call.getArgSVal(0));
       }
     }
   }
 }
 
 void IteratorPastEndChecker::checkPostCall(const CallEvent &Call,
                                            CheckerContext &C) const {
   // Record end() iterators, iterator decrementation and comparison
-  const auto *Func = Call.getDecl()->getAsFunction();
+  const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
   if (!Func)
     return;
   if (Func->isOverloadedOperator()) {
     const auto Op = Func->getOverloadedOperator();
     if (isSimpleComparisonOperator(Op)) {
-      if (Func->isCXXInstanceMember()) {
-        const auto &InstCall = static_cast<const CXXInstanceCall &>(Call);
-        handleComparison(C, InstCall.getReturnValue(), InstCall.getCXXThisVal(),
-                         InstCall.getArgSVal(0), Op);
+      if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
+        handleComparison(C, Call.getReturnValue(), InstCall->getCXXThisVal(),
+                         Call.getArgSVal(0), Op);
       } else {
         handleComparison(C, Call.getReturnValue(), Call.getArgSVal(0),
                          Call.getArgSVal(1), Op);
       }
+    } else if (isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) {
+      if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
+        if (Call.getNumArgs() >= 1) {
+          handleRandomIncrOrDecr(C, Func->getOverloadedOperator(),
+                                 Call.getReturnValue(),
+                                 InstCall->getCXXThisVal(), Call.getArgSVal(0),
+                                 Call.getArgExpr(0)->getType(), false);
+        }
+      } else {
+        if (Call.getNumArgs() >= 2) {
+          handleRandomIncrOrDecr(C, Func->getOverloadedOperator(),
+                                 Call.getReturnValue(), Call.getArgSVal(0),
+                                 Call.getArgSVal(1),
+                                 Call.getArgExpr(1)->getType(), false);
+        }
+      }
     } else if (isDecrementOperator(Func->getOverloadedOperator())) {
-      if (Func->isCXXInstanceMember()) {
-        const auto &InstCall = static_cast<const CXXInstanceCall &>(Call);
-        handleDecrement(C, InstCall.getCXXThisVal());
+      if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
+        handleDecrement(C, InstCall->getCXXThisVal());
       } else {
         handleDecrement(C, Call.getArgSVal(0));
       }
     }
   } else if (Func->isCXXInstanceMember()) {
     if (!isEndCall(Func))
       return;
     if (!isIteratorType(Call.getResultType()))
if (const auto *Reg = CurrentThis.getAsRegion()) {
     const auto *Pos = getIteratorPosition(OldState, OldThis);
     if (!Pos)
       return;
     State = setIteratorPosition(State, CurrentThis, *Pos);
     C.addTransition(State);
   }
 }
 
+void IteratorPastEndChecker::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);
+  } else {
+    const auto *OldPos = getIteratorPosition(State, Loc);
+    if (OldPos) {
+      State = removeIteratorPosition(State, Loc);
+      C.addTransition(State);
+    }
+  }
+}
+
 void IteratorPastEndChecker::checkBeginFunction(CheckerContext &C) const {
   // Copy state of iterator arguments to iterator parameters
   auto State = C.getState();
   const auto *LCtx = C.getLocationContext();
 
   const auto *Site = cast<StackFrameContext>(LCtx)->getCallSite();
   if (!Site)
     return;
for (const auto P : FD->parameters()) {
     State = setIteratorPosition(State, Param, *Pos);
     Change = true;
   }
   if (Change) {
     C.addTransition(State);
   }
 }
 
-void IteratorPastEndChecker::checkPostStmt(const CXXConstructExpr *CCE,
-                                           CheckerContext &C) const {
-  // Transfer iterator state in case of copy or move by constructor
-  const auto *ctr = CCE->getConstructor();
-  if (!ctr->isCopyOrMoveConstructor())
-    return;
-  const auto *RHSExpr = CCE->getArg(0);
-
-  auto State = C.getState();
-  const auto *LCtx = C.getLocationContext();
-
-  const auto RetVal = State->getSVal(CCE, LCtx);
-
-  const auto RHSVal = State->getSVal(RHSExpr, LCtx);
-  const auto *RHSPos = getIteratorPosition(State, RHSVal);
-  if (!RHSPos)
-    return;
-  State = setIteratorPosition(State, RetVal, *RHSPos);
-  C.addTransition(State);
-}
-
-void IteratorPastEndChecker::checkPostStmt(const DeclStmt *DS,
-                                           CheckerContext &C) const {
-  // Transfer iterator state to new variable declaration
-  for (const auto *D : DS->decls()) {
-    const auto *VD = dyn_cast<VarDecl>(D);
-    if (!VD || !VD->hasInit())
-      continue;
-
-    auto State = C.getState();
-    const auto *LCtx = C.getPredecessor()->getLocationContext();
-    const auto *Pos =
-        getIteratorPosition(State, State->getSVal(VD->getInit(), LCtx));
-    if (!Pos)
-      continue;
-    State = setIteratorPosition(State, State->getLValue(VD, LCtx), *Pos);
-    C.addTransition(State);
-  }
-}
-
 void IteratorPastEndChecker::checkPostStmt(const MaterializeTemporaryExpr *MTE,
                                            CheckerContext &C) const {
   /* Transfer iterator state for to temporary objects */
   auto State = C.getState();
   const auto *LCtx = C.getPredecessor()->getLocationContext();
   const auto *Pos =
       getIteratorPosition(State, State->getSVal(MTE->GetTemporaryExpr(), LCtx));
   if (!Pos)
if (FD->getKind() == Decl::Function) {
     }
   }
 
   return false;
 }
 
 void IteratorPastEndChecker::handleComparison(CheckerContext &C,
                                               const SVal &RetVal,
-                                              const SVal &LVal,
-                                              const SVal &RVal,
+                                              const SVal &LHS, const SVal &RHS,
                                               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
   auto State = C.getState();
   if (const auto *Condition = RetVal.getAsSymbolicExpression()) {
-    const auto *LPos = getIteratorPosition(State, LVal);
-    const auto *RPos = getIteratorPosition(State, RVal);
+    const auto *LPos = getIteratorPosition(State, LHS);
+    const auto *RPos = getIteratorPosition(State, RHS);
     if (!LPos && !RPos)
       return;
-    State = saveComparison(State, Condition, LVal, RVal, Op == OO_EqualEqual);
+    State = saveComparison(State, Condition, LHS, RHS, Op == OO_EqualEqual);
     C.addTransition(State);
   } else if (const auto TruthVal = RetVal.getAs<nonloc::ConcreteInt>()) {
     if ((State = processComparison(
-             State, getRegionOrSymbol(LVal), getRegionOrSymbol(RVal),
+             State, getRegionOrSymbol(LHS), getRegionOrSymbol(RHS),
              (Op == OO_EqualEqual) == (TruthVal->getValue() != 0)))) {
       C.addTransition(State);
     } else {
       C.generateSink(State, C.getPredecessor());
     }
   }
 }
 
+void IteratorPastEndChecker::handleRandomIncrOrDecr(
+    CheckerContext &C, OverloadedOperatorKind Op, const SVal &RetVal,
+    const SVal &LHS, const SVal &RHS, QualType RHSType, bool PreCheck) const {
+  if (!RHSType->isIntegerType())
+    return;
+
+  auto State = C.getState();
+  const auto *Pos = getIteratorPosition(State, LHS);
+  if (!Pos || Pos->isInRange())
+    return;
+
+  auto &SVB = C.getSValBuilder();
+  auto &CM = C.getConstraintManager();
+  auto zeroVal = SVB.makeIntVal(0, RHSType);
+
+  // Hack - begin
+  auto value = RHS;
+  if (auto loc = value.getAs<Loc>()) {
+    value = State->getRawSVal(*loc);
+  }
+  // Hack - end
+
+  auto greaterThanZero =
+      SVB.evalBinOp(State, BO_GT, value, zeroVal, SVB.getConditionType())
+          .getAs<DefinedSVal>();
+
+  auto lessThanZero =
+      SVB.evalBinOp(State, BO_LT, value, zeroVal, SVB.getConditionType())
+          .getAs<DefinedSVal>();
+
+  if (!greaterThanZero || !lessThanZero) {
+    // Cannot properly reason so assume the best to prevent false positives
+    if (!PreCheck) {
+      auto &TgtVal = (Op == OO_PlusEqual || Op == OO_MinusEqual) ? LHS : RetVal;
+      State = removeIteratorPosition(State, TgtVal);
+      C.addTransition(State);
+    }
+    return;
+  }
+
+  ProgramStateRef StatePositive, StateNonPositive;
+  std::tie(StatePositive, StateNonPositive) =
+      CM.assumeDual(State, *greaterThanZero);
+
+  ProgramStateRef StateNegative, StateZero;
+  std::tie(StateNegative, StateZero) =
+      CM.assumeDual(StateNonPositive, *lessThanZero);
+
+  // When increasing by positive or decreasing by negative an iterator past its
+  // end, then it is a bug. We check for bugs before the operator call.
+  if (PreCheck &&
+      ((StatePositive && (Op == OO_Plus || Op == OO_PlusEqual)) ||
+       (StateNegative && (Op == OO_Minus || Op == OO_MinusEqual)))) {
+    auto *N = C.generateNonFatalErrorNode(State);
+    if (!N)
+      return;
+    reportPastEndBug("Iterator accessed past its end.", LHS, C, N);
+  }
+
+  // When increasing by negative or decreasing by positive an iterator past its
+  // end, then we assume that the iterator is back to its range.
+  if (!PreCheck &&
+      ((StatePositive && (Op == OO_Minus || Op == OO_MinusEqual)) ||
+       (StateNegative && (Op == OO_Plus || Op == OO_PlusEqual)))) {
+    State =
+        (Op == OO_Minus || Op == OO_MinusEqual) ? StatePositive : StateNegative;
+    auto &TgtVal = (Op == OO_PlusEqual || Op == OO_MinusEqual) ? LHS : RetVal;
+    State = setIteratorPosition(State, TgtVal, IteratorPosition::getInRange());
+    C.addTransition(State);
+  }
+}
+
 void IteratorPastEndChecker::handleAccess(CheckerContext &C,
                                           const SVal &Val) const {
   auto State = C.getState();
   const auto *Pos = getIteratorPosition(State, Val);
   if (Pos && Pos->isOutofRange()) {
     auto *N = C.generateNonFatalErrorNode(State);
-    if (!N) {
+    if (!N)
       return;
-    }
     reportPastEndBug("Iterator accessed past its end.", Val, C, N);
   }
 }
 
 void IteratorPastEndChecker::handleDecrement(CheckerContext &C,
                                              const SVal &Val) const {
   auto State = C.getState();
   const auto *Pos = getIteratorPosition(State, Val);

 }
 
 bool isSimpleComparisonOperator(OverloadedOperatorKind OK) {
   return OK == OO_EqualEqual || OK == OO_ExclaimEqual;
 }
 
 bool isAccessOperator(OverloadedOperatorKind OK) {
   return OK == OO_Star || OK == OO_Arrow || OK == OO_ArrowStar ||
-         OK == OO_Plus || OK == OO_PlusEqual || OK == OO_PlusPlus ||
-         OK == OO_Subscript;
+         OK == OO_PlusPlus || OK == OO_Subscript;
+}
+
+bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK) {
+  return OK == OO_Plus || OK == OO_PlusEqual || OK == OO_Minus ||
+         OK == OO_MinusEqual;
 }
 
 bool isDecrementOperator(OverloadedOperatorKind OK) {
-  return OK == OO_MinusEqual || OK == OO_MinusMinus;
+  return OK == OO_MinusMinus;
 }
 
 BinaryOperator::Opcode getOpcode(const SymExpr *SE) {
   if (const auto *BSE = dyn_cast<BinarySymExpr>(SE)) {
     return BSE->getOpcode();
   } else if (const auto *SC = dyn_cast<SymbolConjured>(SE)) {
     const auto *COE = dyn_cast<CXXOperatorCallExpr>(SC->getStmt());
     if (!COE)
if (const auto Reg = Val.getAsRegion()) {
     return Sym;
   } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
     return LCVal->getRegion();
   }
   return RegionOrSymbol();
 }
 
 const ProgramStateRef processComparison(ProgramStateRef State,
-                                        RegionOrSymbol LVal,
-                                        RegionOrSymbol RVal, bool Equal) {
-  const auto *LPos = getIteratorPosition(State, LVal);
-  const auto *RPos = getIteratorPosition(State, RVal);
+                                        RegionOrSymbol LHS, RegionOrSymbol RHS,
+                                        bool Equal) {
+  const auto *LPos = getIteratorPosition(State, LHS);
+  const auto *RPos = getIteratorPosition(State, RHS);
   if (LPos && !RPos) {
-    State = adjustIteratorPosition(State, RVal, *LPos, Equal);
+    State = adjustIteratorPosition(State, RHS, *LPos, Equal);
   } else if (!LPos && RPos) {
-    State = adjustIteratorPosition(State, LVal, *RPos, Equal);
+    State = adjustIteratorPosition(State, LHS, *RPos, Equal);
   } else if (LPos && RPos) {
     if (contradictingIteratorPositions(*LPos, *RPos, Equal)) {
       return nullptr;
     }
   }
   return State;
 }
 
 const ProgramStateRef saveComparison(ProgramStateRef State,
-                                     const SymExpr *Condition, const SVal &LVal,
-                                     const SVal &RVal, bool Eq) {
-  const auto Left = getRegionOrSymbol(LVal);
-  const auto Right = getRegionOrSymbol(RVal);
+                                     const SymExpr *Condition, const SVal &LHS,
+                                     const SVal &RHS, bool Eq) {
+  const auto Left = getRegionOrSymbol(LHS);
+  const auto Right = getRegionOrSymbol(RHS);
   if (!Left || !Right)
     return State;
   return State->set<IteratorComparisonMap>(Condition,
                                            IteratorComparison(Left, Right, Eq));
 }
 
 const IteratorComparison *loadComparison(ProgramStateRef State,
                                          const SymExpr *Condition) {
if (RegOrSym.is<const MemRegion *>()) {
     return State->set<IteratorRegionMap>(RegOrSym.get<const MemRegion *>(),
                                          Pos);
   } else if (RegOrSym.is<SymbolRef>()) {
     return State->set<IteratorSymbolMap>(RegOrSym.get<SymbolRef>(), Pos);
   }
   return nullptr;
 }
 
+ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val) {
+  if (const auto Reg = Val.getAsRegion()) {
+    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());
+  }
+  return nullptr;
+}
+
 ProgramStateRef adjustIteratorPosition(ProgramStateRef State,
                                        RegionOrSymbol RegOrSym,
                                        IteratorPosition Pos, bool Equal) {
 
   if ((Pos.isInRange() && Equal) || (Pos.isOutofRange() && !Equal)) {
     return setIteratorPosition(State, RegOrSym, IteratorPosition::getInRange());
   } else if (Pos.isOutofRange() && Equal) {
     return setIteratorPosition(State, RegOrSym,

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

 // Like the compiler, the static analyzer treats some functions differently if
 // they come from a system header -- for example, it is assumed that system
 // functions do not arbitrarily free() their parameters, and that some bugs
 // found in system headers cannot be fixed by the user and should be
 // suppressed.
 #pragma clang system_header
 
 typedef unsigned char uint8_t;
 
 typedef __typeof__(sizeof(int)) size_t;
+typedef __typeof__((char*)0-(char*)0) ptrdiff_t;
 void *memmove(void *s1, const void *s2, size_t n);
 
-template <typename T, typename Ptr, typename Ref> struct __iterator {
-  typedef __iterator<T, T *, T &> iterator;
-  typedef __iterator<T, const T *, const T &> const_iterator;
-
-  __iterator(const Ptr p) : ptr(p) {}
-
-  __iterator<T, Ptr, Ref> operator++() { return *this; }
-  __iterator<T, Ptr, Ref> operator++(int) { return *this; }
-  __iterator<T, Ptr, Ref> operator--() { return *this; }
-  __iterator<T, Ptr, Ref> operator--(int) { return *this; }
+namespace std {
+  struct input_iterator_tag { };
+  struct output_iterator_tag { };
+  struct forward_iterator_tag : public input_iterator_tag { };
+  struct bidirectional_iterator_tag : public forward_iterator_tag { };
+  struct random_access_iterator_tag : public bidirectional_iterator_tag { };
+
+  template <typename Iterator> struct iterator_traits {
+    typedef typename Iterator::difference_type difference_type;
+    typedef typename Iterator::value_type value_type;
+    typedef typename Iterator::pointer pointer;
+    typedef typename Iterator::reference reference;
+    typedef typename Iterator::iterator_category iterator_category;
+  };
+}
+
+template <typename T, typename Ptr, typename Ref> struct __vector_iterator {
+  typedef __vector_iterator<T, T *, T &> iterator;
+  typedef __vector_iterator<T, const T *, const T &> const_iterator;
+
+  typedef ptrdiff_t difference_type;
+  typedef T value_type;
+  typedef Ptr pointer;
+  typedef Ref reference;
+  typedef std::random_access_iterator_tag iterator_category;
+
+  __vector_iterator(const Ptr p) : ptr(p) {}
+  __vector_iterator<T, Ptr, Ref> operator++() { ++ ptr; return *this; }
+  __vector_iterator<T, Ptr, Ref> operator++(int) {
+    auto tmp = *this;
+    ++ ptr;
+    return tmp;
+  }
+  __vector_iterator<T, Ptr, Ref> operator--() { -- ptr; return *this; }
+  __vector_iterator<T, Ptr, Ref> operator--(int) {
+    auto tmp = *this; -- ptr;
+    return tmp;
+  }
+  __vector_iterator<T, Ptr, Ref> operator+(difference_type n) {
+    return ptr + n;
+  }
+  __vector_iterator<T, Ptr, Ref> operator-(difference_type n) {
+    return ptr - n;
+  }
+  __vector_iterator<T, Ptr, Ref> operator+=(difference_type n) {
+    return ptr += n;
+  }
+  __vector_iterator<T, Ptr, Ref> operator-=(difference_type n) {
+    return ptr -= n;
+  }
+
   Ref operator*() const { return *ptr; }
   Ptr operator->() const { return *ptr; }
 
   bool operator==(const iterator &rhs) const { return ptr == rhs.ptr; }
   bool operator==(const const_iterator &rhs) const { return ptr == rhs.ptr; }
 
   bool operator!=(const iterator &rhs) const { return ptr != rhs.ptr; }
   bool operator!=(const const_iterator &rhs) const { return ptr != rhs.ptr; }
 
 private:
   Ptr ptr;
 };
 
+template <typename T, typename Ptr, typename Ref> struct __list_iterator {
+  typedef __vector_iterator<T, __typeof__(T::data) *, __typeof__(T::data) &> iterator;
+  typedef __vector_iterator<T, const __typeof__(T::data) *, const __typeof__(T::data) &> const_iterator;
+
+  typedef ptrdiff_t difference_type;
+  typedef T value_type;
+  typedef Ptr pointer;
+  typedef Ref reference;
+  typedef std::bidirectional_iterator_tag iterator_category;
+
+  __list_iterator(T* it) : item(it) {}
+  __list_iterator<T, Ptr, Ref> operator++() { item = item->next; return *this; }
+  __list_iterator<T, Ptr, Ref> operator++(int) {
+    auto tmp = *this;
+    item = item->next;
+    return tmp;
+  }
+  __list_iterator<T, Ptr, Ref> operator--() { item = item->prev; return *this; }
+  __list_iterator<T, Ptr, Ref> operator--(int) {
+    auto tmp = *this;
+    item = item->prev;
+    return tmp;
+  }
+
+  Ref operator*() const { return item->data; }
+  Ptr operator->() const { return item->data; }
+
+  bool operator==(const iterator &rhs) const { return item == rhs->item; }
+  bool operator==(const const_iterator &rhs) const { return item == rhs->item; }
+
+  bool operator!=(const iterator &rhs) const { return item != rhs->item; }
+  bool operator!=(const const_iterator &rhs) const { return item != rhs->item; }
+
+private:
+  T* item;
+};
+
 namespace std {
+
   template <class T1, class T2>
   struct pair {
     T1 first;
     T2 second;
     
     pair() : first(), second() {}
     pair(const T1 &a, const T2 &b) : first(a), second(b) {}
     
     template<class U1, class U2>
     pair(const pair<U1, U2> &other) : first(other.first), second(other.second) {}
   };
   
   typedef __typeof__(sizeof(int)) size_t;
   
   template<typename T>
   class vector {
-    typedef __iterator<T, T *, T &> iterator;
-    typedef __iterator<T, const T *, const T &> const_iterator;
-
     T *_start;
     T *_finish;
     T *_end_of_storage;
   public:
+    typedef __vector_iterator<T, T *, T &> iterator;
+    typedef __vector_iterator<T, const T *, const T &> const_iterator;
+
     vector() : _start(0), _finish(0), _end_of_storage(0) {}
     ~vector();
     
     size_t size() const {
       return size_t(_finish - _start);
     }
     
     void push_back();
     T pop_back();
 
     T &operator[](size_t n) {
       return _start[n];
     }
     
     const T &operator[](size_t n) const {
       return _start[n];
     }
     
     iterator begin() { return iterator(_start); }
     const_iterator begin() const { return const_iterator(_start); }
     iterator end() { return iterator(_finish); }
     const_iterator end() const { return const_iterator(_finish); }
+
+    T& front() { return *begin(); }
+    const T& front() const { return *begin(); }
+    T& back() { return *(end() - 1); }
+    const T& back() const { return *(end() - 1); }
+  };
+  
+  template<typename T>
+  class list {
+    struct __item {
+      T data;
+      __item *prev, *next;
+    } *_start, *_finish;
+  public:
+    typedef __list_iterator<__item, T *, T &> iterator;
+    typedef __list_iterator<__item, const T *, const T &> const_iterator;
+
+    list() : _start(0), _finish(0) {}
+    ~list();
+    
+    void push_back();
+    T pop_back();
+
+    iterator begin() { return iterator(_start); }
+    const_iterator begin() const { return const_iterator(_start); }
+    iterator end() { return iterator(_finish); }
+    const_iterator end() const { return const_iterator(_finish); }
+
+    T& front() { return *begin(); }
+    const T& front() const { return *begin(); }
+    T& back() { return *--end(); }
+    const T& back() const { return *--end(); }
   };
   
   class exception {
   public:
     exception() throw();
     virtual ~exception() throw();
     virtual const char *what() const throw() {
       return 0;
>::type __copy_backward(_Tp* __first, _Tp* __last, _Up* __result) {
     }
     return __result;
   }
 
   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) {
+  if (n >= 0) while(n-- > 0) ++it; else while (n++<0) --it;
+}
+
+template <class RandomAccessIterator, class Distance>
+void __advance (RandomAccessIterator& it, Distance n,
+                std::random_access_iterator_tag) {
+  it += n;
+}
+
+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 T>
   InputIterator find(InputIterator first, InputIterator last, const T &val);
   template <class ForwardIterator1, class ForwardIterator2>
   ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1,
                             ForwardIterator2 first2, ForwardIterator2 last2);
   template <class ForwardIterator1, class ForwardIterator2>
   ForwardIterator1 find_first_of(ForwardIterator1 first1,
InputIterator upper_bound(InputIterator first, InputIterator last,
                             const T &val);
   template <class ForwardIterator1, class ForwardIterator2>
   ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1,
                           ForwardIterator2 first2, ForwardIterator2 last2);
   template <class ForwardIterator1, class ForwardIterator2>
   ForwardIterator1 search_n(ForwardIterator1 first1, ForwardIterator1 last1,
                             ForwardIterator2 first2, ForwardIterator2 last2);
 
-  struct input_iterator_tag { };
-  struct output_iterator_tag { };
-  struct forward_iterator_tag : public input_iterator_tag { };
-  struct bidirectional_iterator_tag : public forward_iterator_tag { };
-  struct random_access_iterator_tag : public bidirectional_iterator_tag { };
-
 }
 
 void* operator new(std::size_t, const std::nothrow_t&) throw();
 void* operator new[](std::size_t, const std::nothrow_t&) throw();
 void operator delete(void*, const std::nothrow_t&) throw();
 void operator delete[](void*, const std::nothrow_t&) throw();
 
 void* operator new (std::size_t size, void* ptr) throw() { return ptr; };

test/Analysis/diagnostics/explicit-suppression.cpp

class C {
   // The virtual function is to make C not trivially copy assignable so that we call the
   // variant of std::copy() that does not defer to memmove().
   virtual int f();
 };
 
 void testCopyNull(C *I, C *E) {
   std::copy(I, E, (C *)0);
 #ifndef SUPPRESSED
-  // expected-warning@../Inputs/system-header-simulator-cxx.h:191 {{Called C++ object pointer is null}}
+  // expected-warning@../Inputs/system-header-simulator-cxx.h:303 {{Called C++ object pointer is null}}
 #endif
 }

test/Analysis/iterator-past-end.cpp

void loop(std::vector<int> &vec, int e) {
   while (true) {
     auto item = std::find(start, vec.end(), e);
     if (item == vec.end())
       break;
     *item;          // no-warning
     start = ++item; // no-warning
   }
 }
+
+void good_overwrite(std::vector<int> &vec) {
+  auto i = vec.end();
+  i = vec.begin();
+  *i; // no-warning
+}
+
+void good_overwrite_find(std::vector<int> &vec, int e) {
+  auto i = std::find(vec.begin(), vec.end(), e);
+  if(i == vec.end()) {
+    i = vec.begin();
+  }
+  *i; // no-warning
+}
+
+void bad_overwrite(std::vector<int> &vec) {
+  auto i = vec.begin();
+  i = vec.end();
+  *i; // expected-warning{{Iterator accessed past its end}}
+}
+
+void bad_overwrite_find(std::vector<int> &vec, int e) {
+  auto i = std::find(vec.begin(), vec.end(), e);
+  if(i != vec.end()) {
+    i = vec.begin();
+  }
+  *i; // expected-warning{{Iterator accessed past its end}}
+}
+
+void good_advance(std::vector<int> &vec) {
+  auto i = vec.end();
+  std::advance(i, -1);
+  *i; // no-warning
+}
+
+void good_prev(std::vector<int> &vec) {
+  auto i = std::prev(vec.end());
+  *i; // no-warning
+}
+
+void front(const std::vector<int> &vec) {
+  vec.front();
+}
+
+void back(const std::vector<int> &vec) {
+  vec.back();
+}