[Analyzer] Iterator Checker - Part 3: Invalidation check, first for (copy) assignments

[baloghadamsoftware]

Summary

We add check for invalidation of iterators. The only operation we handle here is the (copy) assignment.

[takuto.ikuta]

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

324

OK to use make_unique here?

[NoQ]

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

644

This needs investigation, because it may be nasty.

generateNonFatalErrorNode() returns null when the exact same non-fatal error node, also produced by the iterator checker with the exact same program state and exact same program point and exact same tag on the program point already exists. As far as i understand, the only difference your tag makes is that the tag is now different, so it is not merged with the existing node. However, it is worth it to try to find out why the node gets merged at all.

This may be caused by an accidental state split. For example, if you are calling generateNonFatalErrorNode() twice in the same checker callback without chaining them together (passing node returned by one as an argument to another), this in fact splits states. I'm not immediately seeing such places in the code - you seem to be aware of this problem and avoiding it well. But still, looking at the topology of the exploded graph in the failing test should help finding out what is going on.

[baloghadamsoftware]

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

644

I made some more investigation this time. Unfortunately the case is not what you suggest. Only one non-fatal error node is produced. I tested it with a common tag (a global static so the tag is exactly the same at every generateNonFatalErrorNode(), but the tests still pass. I printed out the exploded graph and I found that there are indeed two nodes with the same state ID. The tag is the default tag automatically generated from the name of the checker. The first state is created in function checkPreStatement() for CXXOperatorCallExpr where I copy the state of the iterator from the formal to the actual this parameter. All the test fails happen at the dereference operator call (*) of another operator call (++ or --). After this copy, when I call generateNonFatalErrorNode() I get nullptr because at some point under the hood (I debugged it when I created it originally) the error node is considered as "not new". If I use a custom tag here, the state ID remains, not the node ID changes.

[baloghadamsoftware]

Rebased to current Part 2.

[a.sidorin]

Hello Adam. I have a nit inline.

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

1270

Updating ProgramState is usually considered as an expensive operation. Instead, we can update maps (RegionMap and SymbolMap) and then, if they have any updates, create a state containing these maps. What do you think?

[baloghadamsoftware]

Thanks you for your comments! I have one question:

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

1270

How to update ImmutableMap?

[a.sidorin]

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

1270

You can create a new Immutable map from existing with factory methods:

auto Factory = State->get_context<IteratorRegionMap>();
auto Map = State->get<RegionMap>();
Map = Factory.add(Map, Key, Value);
Map = Factory.add(Map, Key2, Value2);
State = State->set<IteratorRegionMap>(Map);

[baloghadamsoftware]

Updated according to the comments.

[baloghadamsoftware]

Rebased to rL335835.

[whisperity]

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

92

Seeing that in line 106 you consider this record immutable, you might want to add a const on this field too.

test/Analysis/invalidated-iterator.cpp

33

This might not be applicable here, but isn't there a test case for copy operations where the iterator isn't invalidated? Something of a positive test to be added here. My only idea is something with weird reference-to-pointer magic. Might not worth the hassle.

[baloghadamsoftware]

Updated according to the comments.

[baloghadamsoftware]

Re-upload because of a mistake.

[baloghadamsoftware]

test/Analysis/invalidated-iterator.cpp

33

Accoring to the rules (on STL containers) if a container is overwritten using a copy assignment, all its iterators become invalidated. So I cannot imagine a positive test case here.

[NoQ]

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

644

I think i see the problem. The checker subscribes to both PreCall and PreStmt<CallExpr> (to be exact, CXXOperatorCallExpr) and adds transitions in both cases. It results with a predecessor node in CheckerContext that's already tagged by the checker. Apparently this never worked, but nobody tried that.

Ideally, we should make sure those callbacks use different program points, eg. introduce PreCall/PostCall program point kinds and use them.

Also i wonder why are you using pre- rather than post-statement callback. You model all other operators in PostCall, why did those end up here? Maybe merge them? It is generally better to model pre-conditions and look for bugs in PreStmt/PreCall (before we don't care what happens within the call), and model effects in PostStmt/PostCall (because effects don't take effect until the call happens).

[baloghadamsoftware]

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

644

That is what I am trying to to: Post* for modelling and Pre* for checking. However, this PreStmt<CXXOperatorCallExpr>() is special since I have to move the arguments to the context of the called operator before the call.

[NoQ]

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

644

Ah, it's that thing, PreCall then?

[baloghadamsoftware]

Pre-statement check of CXXOperatorCallExpr merged into pre-call check.

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

644

Yes! It seems to be working. Thank you for your help!

[NoQ]

I suspect that with rC338135 your operator this-argument re-assignment mechanism is no longer necessary. Due to the combination of support for materializing temporaries that i added previously and the change in the AST that turns the operator this-argument into a simple temporary, i believe that the memory region should no longer change and you don't need to move your metadata. Could you check this?

[baloghadamsoftware]

Copying iterator position for the this pointer of C++ operators from the caller's context to the callee's context is no longer needed.

[baloghadamsoftware]

Yes, it is working now without the hack.

[baloghadamsoftware]

[NoQ]

Looks great, let's land this!

include/clang/StaticAnalyzer/Checkers/Checkers.td

def DeleteWithNonVirtualDtorChecker : Checker<"DeleteWithNonVirtualDtor">,
   HelpText<"Reports destructions of polymorphic objects with a non-virtual "
            "destructor in their base class">,
   DescFile<"DeleteWithNonVirtualDtorChecker.cpp">;
 
 def IteratorRangeChecker : Checker<"IteratorRange">,
   HelpText<"Check for iterators used outside their valid ranges">,
   DescFile<"IteratorChecker.cpp">;
 
+def InvalidatedIteratorChecker : Checker<"InvalidatedIterator">,
+  HelpText<"Check for use of invalidated iterators">,
+  DescFile<"IteratorChecker.cpp">;
+
 def MisusedMovedObjectChecker: Checker<"MisusedMovedObject">,
      HelpText<"Method calls on a moved-from object and copying a moved-from "
               "object will be reported">,
      DescFile<"MisusedMovedObjectChecker.cpp">;
 
 def UninitializedObjectChecker: Checker<"UninitializedObject">,
      HelpText<"Reports uninitialized fields after object construction">,
      DescFile<"UninitializedObjectChecker.cpp">;

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

 //
 // Since `SimpleConstraintManager` cannot handle complex symbolic expressions
 // we only use expressions of the format S, S+n or S-n for iterator positions
 // where S is a conjured symbol and n is an unsigned concrete integer. When
 // making an assumption e.g. `S1 + n == S2 + m` we store `S1 - S2 == m - n` as
 // a constraint which we later retrieve when doing an actual comparison.
 
 #include "ClangSACheckers.h"
+#include "clang/AST/DeclTemplate.h"
 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
 #include "clang/StaticAnalyzer/Core/Checker.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
 
+#include <utility>
+
 using namespace clang;
 using namespace ento;
 
 namespace {
 
 // Abstract position of an iterator. This helps to handle all three kinds
 // of operators in a common way by using a symbolic position.
 struct IteratorPosition {
 private:
 
   // Container the iterator belongs to
   const MemRegion *Cont;
 
+  // Whether iterator is valid
+  const bool Valid;
+
   // Abstract offset
   const SymbolRef Offset;
 
-  IteratorPosition(const MemRegion *C, SymbolRef Of)
-      : Cont(C), Offset(Of) {}
+  IteratorPosition(const MemRegion *C, bool V, SymbolRef Of)
+      : Cont(C), Valid(V), Offset(Of) {}
 
 public:
   const MemRegion *getContainer() const { return Cont; }
+  bool isValid() const { return Valid; }
   SymbolRef getOffset() const { return Offset; }
 
+  IteratorPosition invalidate() const {
+    return IteratorPosition(Cont, false, Offset);
+  }
+
   static IteratorPosition getPosition(const MemRegion *C, SymbolRef Of) {
-    return IteratorPosition(C, Of);
+    return IteratorPosition(C, true, Of);
   }
 
   IteratorPosition setTo(SymbolRef NewOf) const {
-    return IteratorPosition(Cont, NewOf);
+    return IteratorPosition(Cont, Valid, NewOf);
   }
 
   bool operator==(const IteratorPosition &X) const {
-    return Cont == X.Cont && Offset == X.Offset;
+    return Cont == X.Cont && Valid == X.Valid && Offset == X.Offset;
   }
 
   bool operator!=(const IteratorPosition &X) const {
-    return Cont != X.Cont || Offset != X.Offset;
+    return Cont != X.Cont || Valid != X.Valid || Offset != X.Offset;
   }
 
   void Profile(llvm::FoldingSetNodeID &ID) const {
     ID.AddPointer(Cont);
+    ID.AddInteger(Valid);
     ID.Add(Offset);
   }
 };
 
 typedef llvm::PointerUnion<const MemRegion *, SymbolRef> RegionOrSymbol;
 
 // Structure to record the symbolic begin and end position of a container
 struct ContainerData {
public:
   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 IteratorChecker
     : public Checker<check::PreCall, check::PostCall,
-                     check::PreStmt<CXXOperatorCallExpr>,
                      check::PostStmt<MaterializeTemporaryExpr>,
                      check::LiveSymbols, check::DeadSymbols,
                      eval::Assume> {
 
   std::unique_ptr<BugType> OutOfRangeBugType;
+  std::unique_ptr<BugType> InvalidatedBugType;
 
   void handleComparison(CheckerContext &C, const SVal &RetVal, const SVal &LVal,
                         const SVal &RVal, OverloadedOperatorKind Op) const;
+  void verifyAccess(CheckerContext &C, const SVal &Val) const;
   void verifyDereference(CheckerContext &C, const SVal &Val) 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, OverloadedOperatorKind Op,
                               const SVal &RetVal, const SVal &LHS,
                               const SVal &RHS) const;
   void handleBegin(CheckerContext &C, const Expr *CE, const SVal &RetVal,
                    const SVal &Cont) const;
   void handleEnd(CheckerContext &C, const Expr *CE, const SVal &RetVal,
                  const SVal &Cont) const;
   void assignToContainer(CheckerContext &C, const Expr *CE, const SVal &RetVal,
                          const MemRegion *Cont) const;
+  void handleAssign(CheckerContext &C, const SVal &Cont) const;
   void verifyRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op,
                               const SVal &RetVal, const SVal &LHS,
                               const SVal &RHS) const;
   void reportOutOfRangeBug(const StringRef &Message, const SVal &Val,
                            CheckerContext &C, ExplodedNode *ErrNode) const;
+  void reportInvalidatedBug(const StringRef &Message, const SVal &Val,
+                            CheckerContext &C, ExplodedNode *ErrNode) const;
 
 public:
   IteratorChecker();
 
   enum CheckKind {
     CK_IteratorRangeChecker,
+    CK_InvalidatedIteratorChecker,
     CK_NumCheckKinds
   };
 
   DefaultBool ChecksEnabled[CK_NumCheckKinds];
   CheckName CheckNames[CK_NumCheckKinds];
 
   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 checkPostStmt(const MaterializeTemporaryExpr *MTE,
                      CheckerContext &C) const;
   void checkLiveSymbols(ProgramStateRef State, SymbolReaper &SR) const;
   void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
   ProgramStateRef evalAssume(ProgramStateRef State, SVal Cond,
                              bool Assumption) const;
 };
 } // namespace
 
 REGISTER_MAP_WITH_PROGRAMSTATE(IteratorSymbolMap, SymbolRef, IteratorPosition)
 REGISTER_MAP_WITH_PROGRAMSTATE(IteratorRegionMap, const MemRegion *,
                                IteratorPosition)
 
 REGISTER_MAP_WITH_PROGRAMSTATE(ContainerMap, const MemRegion *, ContainerData)
 
 REGISTER_MAP_WITH_PROGRAMSTATE(IteratorComparisonMap, const SymExpr *,
                                IteratorComparison)
 
 namespace {
 
 bool isIteratorType(const QualType &Type);
 bool isIterator(const CXXRecordDecl *CRD);
 bool isBeginCall(const FunctionDecl *Func);
 bool isEndCall(const FunctionDecl *Func);
+bool isAssignmentOperator(OverloadedOperatorKind OK);
 bool isSimpleComparisonOperator(OverloadedOperatorKind OK);
+bool isAccessOperator(OverloadedOperatorKind OK);
 bool isDereferenceOperator(OverloadedOperatorKind OK);
 bool isIncrementOperator(OverloadedOperatorKind OK);
 bool isDecrementOperator(OverloadedOperatorKind OK);
 bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK);
 BinaryOperator::Opcode getOpcode(const SymExpr *SE);
 const RegionOrSymbol getRegionOrSymbol(const SVal &Val);
 const ProgramStateRef processComparison(ProgramStateRef State,
                                         RegionOrSymbol LVal,

 ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val);
 ProgramStateRef adjustIteratorPosition(ProgramStateRef State,
                                        RegionOrSymbol RegOrSym,
                                        const IteratorPosition &Pos, bool Equal);
 ProgramStateRef relateIteratorPositions(ProgramStateRef State,
                                         const IteratorPosition &Pos1,
                                         const IteratorPosition &Pos2,
                                         bool Equal);
+ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State,
+                                               const MemRegion *Cont);
 const ContainerData *getContainerData(ProgramStateRef State,
                                       const MemRegion *Cont);
 ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont,
                                  const ContainerData &CData);
 bool hasLiveIterators(ProgramStateRef State, const MemRegion *Cont);
 bool isOutOfRange(ProgramStateRef State, const IteratorPosition &Pos);
 bool isZero(ProgramStateRef State, const NonLoc &Val);
 } // namespace
 
 IteratorChecker::IteratorChecker() {
   OutOfRangeBugType.reset(
       new BugType(this, "Iterator out of range", "Misuse of STL APIs"));
   OutOfRangeBugType->setSuppressOnSink(true);
+  InvalidatedBugType.reset(
+      new BugType(this, "Iterator invalidated", "Misuse of STL APIs"));
+  InvalidatedBugType->setSuppressOnSink(true);
 }
 
 void IteratorChecker::checkPreCall(const CallEvent &Call,
                                    CheckerContext &C) const {
-  // Check for out of range access
+  // Check for out of range access or access of invalidated position and
+  // iterator mismatches
   const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
   if (!Func)
     return;
 
   if (Func->isOverloadedOperator()) {
+    if (ChecksEnabled[CK_InvalidatedIteratorChecker] &&
+        isAccessOperator(Func->getOverloadedOperator())) {
+      // Check for any kind of access of invalidated iterator positions
+      if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
+        verifyAccess(C, InstCall->getCXXThisVal());
+      } else {
+        verifyAccess(C, Call.getArgSVal(0));
+      }
+    }
     if (ChecksEnabled[CK_IteratorRangeChecker] &&
         isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) {
       if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
         // Check for out-of-range incrementions and decrementions
         if (Call.getNumArgs() >= 1) {
           verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(),
                                  Call.getReturnValue(),
                                  InstCall->getCXXThisVal(), Call.getArgSVal(0));
void IteratorChecker::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)) {
+    if (isAssignmentOperator(Op)) {
+      const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call);
+      handleAssign(C, InstCall->getCXXThisVal());
+    } else if (isSimpleComparisonOperator(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())) {
for (unsigned i = 0; i < Call.getNumArgs(); ++i) {
                             Pos->getContainer());
           return;
         }
       }
     }
   }
 }
 
-void IteratorChecker::checkPreStmt(const CXXOperatorCallExpr *COCE,
-                                   CheckerContext &C) const {
-  const auto *ThisExpr = COCE->getArg(0);
-
-  auto State = C.getState();
-  const auto *LCtx = C.getLocationContext();
-
-  const auto CurrentThis = State->getSVal(ThisExpr, LCtx);
-  if (const auto *Reg = CurrentThis.getAsRegion()) {
-    if (!Reg->getAs<CXXTempObjectRegion>())
-      return;
-    const auto OldState = C.getPredecessor()->getFirstPred()->getState();
-    const auto OldThis = OldState->getSVal(ThisExpr, LCtx);
-    // FIXME: This solution is unreliable. It may happen that another checker
-    //        subscribes to the pre-statement check of `CXXOperatorCallExpr`
-    //        and adds a transition before us. The proper fix is to make the
-    //        CFG provide a `ConstructionContext` for the `CXXOperatorCallExpr`,
-    //        which would turn the corresponding `CFGStmt` element into a
-    //        `CFGCXXRecordTypedCall` element, which will allow `ExprEngine` to
-    //        foresee that the `begin()`/`end()` call constructs the object
-    //        directly in the temporary region that `CXXOperatorCallExpr` takes
-    //        as its implicit object argument.
-    const auto *Pos = getIteratorPosition(OldState, OldThis);
-    if (!Pos)
-      return;
-    State = setIteratorPosition(State, CurrentThis, *Pos);
-    C.addTransition(State);
-  }
-}
-
 void IteratorChecker::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->GetTemporaryExpr()));
   if (!Pos)
     return;
void IteratorChecker::handleComparison(CheckerContext &C, const SVal &RetVal,
   }
 }
 
 void IteratorChecker::verifyDereference(CheckerContext &C,
                                         const SVal &Val) const {
   auto State = C.getState();
   const auto *Pos = getIteratorPosition(State, Val);
   if (Pos && isOutOfRange(State, *Pos)) {
-    // If I do not put a tag here, some range tests will fail
-    static CheckerProgramPointTag Tag("IteratorRangeChecker",
-                                      "IteratorOutOfRange");
-    auto *N = C.generateNonFatalErrorNode(State, &Tag);
+    auto *N = C.generateNonFatalErrorNode(State);
     if (!N)
       return;
     reportOutOfRangeBug("Iterator accessed outside of its range.", Val, C, N);
   }
 }
 
+void IteratorChecker::verifyAccess(CheckerContext &C, const SVal &Val) const {
+  auto State = C.getState();
+  const auto *Pos = getIteratorPosition(State, Val);
+  if (Pos && !Pos->isValid()) {
+    auto *N = C.generateNonFatalErrorNode(State);
+    if (!N) {
+      return;
+    }
+    reportInvalidatedBug("Invalidated iterator accessed.", Val, C, N);
+  }
+}
+
 void IteratorChecker::handleIncrement(CheckerContext &C, const SVal &RetVal,
                                       const SVal &Iter, bool Postfix) const {
   // Increment the symbolic expressions which represents the position of the
   // iterator
   auto State = C.getState();
   const auto *Pos = getIteratorPosition(State, Iter);
   if (Pos) {
     auto &SymMgr = C.getSymbolManager();
void IteratorChecker::assignToContainer(CheckerContext &C, const Expr *CE,
   auto Sym = SymMgr.conjureSymbol(CE, C.getLocationContext(),
                                   C.getASTContext().LongTy, C.blockCount());
   State = assumeNoOverflow(State, Sym, 4);
   State = setIteratorPosition(State, RetVal,
                               IteratorPosition::getPosition(Cont, Sym));
   C.addTransition(State);
 }
 
+void IteratorChecker::handleAssign(CheckerContext &C, const SVal &Cont) const {
+  const auto *ContReg = Cont.getAsRegion();
+  if (!ContReg)
+    return;
+
+  while (const auto *CBOR = ContReg->getAs<CXXBaseObjectRegion>()) {
+    ContReg = CBOR->getSuperRegion();
+  }
+
+  // Assignment of a new value to a container always invalidates all its
+  // iterators
+  auto State = C.getState();
+  const auto CData = getContainerData(State, ContReg);
+  if (CData) {
+    State = invalidateAllIteratorPositions(State, ContReg);
+  }
+
+  C.addTransition(State);
+}
+
 void IteratorChecker::reportOutOfRangeBug(const StringRef &Message,
                                           const SVal &Val, CheckerContext &C,
                                           ExplodedNode *ErrNode) const {
   auto R = llvm::make_unique<BugReport>(*OutOfRangeBugType, Message, ErrNode);
   R->markInteresting(Val);
   C.emitReport(std::move(R));
 }
 
+void IteratorChecker::reportInvalidatedBug(const StringRef &Message,
+                                           const SVal &Val, CheckerContext &C,
+                                           ExplodedNode *ErrNode) const {
+  auto R = llvm::make_unique<BugReport>(*InvalidatedBugType, Message, ErrNode);
+  R->markInteresting(Val);
+  C.emitReport(std::move(R));
+}
+
 namespace {
 
 bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
 bool isGreaterOrEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
 bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
              BinaryOperator::Opcode Opc);
 bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2,
              BinaryOperator::Opcode Opc);

 
 bool isEndCall(const FunctionDecl *Func) {
   const auto *IdInfo = Func->getIdentifier();
   if (!IdInfo)
     return false;
   return IdInfo->getName().endswith_lower("end");
 }
 
+bool isAssignmentOperator(OverloadedOperatorKind OK) { return OK == OO_Equal; }
+
 bool isSimpleComparisonOperator(OverloadedOperatorKind OK) {
   return OK == OO_EqualEqual || OK == OO_ExclaimEqual;
 }
 
+bool isAccessOperator(OverloadedOperatorKind OK) {
+  return isDereferenceOperator(OK) || isIncrementOperator(OK) ||
+         isDecrementOperator(OK) || isRandomIncrOrDecrOperator(OK);
+}
+
 bool isDereferenceOperator(OverloadedOperatorKind OK) {
   return OK == OO_Star || OK == OO_Arrow || OK == OO_ArrowStar ||
          OK == OO_Subscript;
 }
 
 bool isIncrementOperator(OverloadedOperatorKind OK) {
   return OK == OO_PlusPlus;
 }
bool hasLiveIterators(ProgramStateRef State, const MemRegion *Cont) {
   for (const auto Sym : SymbolMap) {
     if (Sym.second.getContainer() == Cont)
       return true;
   }
 
   return false;
 }
 
+template <typename Condition, typename Process>
+ProgramStateRef processIteratorPositions(ProgramStateRef State, Condition Cond,
+                                         Process Proc) {
+  auto &RegionMapFactory = State->get_context<IteratorRegionMap>();
+  auto RegionMap = State->get<IteratorRegionMap>();
+  bool Changed = false;
+  for (const auto Reg : RegionMap) {
+    if (Cond(Reg.second)) {
+      RegionMap = RegionMapFactory.add(RegionMap, Reg.first, Proc(Reg.second));
+      Changed = true;
+    }
+  }
+
+  if (Changed)
+    State = State->set<IteratorRegionMap>(RegionMap);
+
+  auto &SymbolMapFactory = State->get_context<IteratorSymbolMap>();
+  auto SymbolMap = State->get<IteratorSymbolMap>();
+  Changed = false;
+  for (const auto Sym : SymbolMap) {
+    if (Cond(Sym.second)) {
+      SymbolMap = SymbolMapFactory.add(SymbolMap, Sym.first, Proc(Sym.second));
+      Changed = true;
+    }
+  }
+
+  if (Changed)
+    State = State->set<IteratorSymbolMap>(SymbolMap);
+
+  return State;
+}
+
+ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State,
+                                               const MemRegion *Cont) {
+  auto MatchCont = [&](const IteratorPosition &Pos) {
+    return Pos.getContainer() == Cont;
+  };
+  auto Invalidate = [&](const IteratorPosition &Pos) {
+    return Pos.invalidate();
+  };
+  return processIteratorPositions(State, MatchCont, Invalidate);
+}
+
 bool isZero(ProgramStateRef State, const NonLoc &Val) {
   auto &BVF = State->getBasicVals();
   return compare(State, Val,
                  nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(0))),
                  BO_EQ);
 }
 
 bool isOutOfRange(ProgramStateRef State, const IteratorPosition &Pos) {
#define REGISTER_CHECKER(name)                                                 \
   void ento::register##name(CheckerManager &Mgr) {                             \
     auto *checker = Mgr.registerChecker<IteratorChecker>();                    \
     checker->ChecksEnabled[IteratorChecker::CK_##name] = true;                 \
     checker->CheckNames[IteratorChecker::CK_##name] =                          \
         Mgr.getCurrentCheckName();                                             \
   }
 
 REGISTER_CHECKER(IteratorRangeChecker)
-
+REGISTER_CHECKER(InvalidatedIteratorChecker)

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

public:
     vector(const vector &other);
     vector(vector &&other);
     ~vector();
     
     size_t size() const {
       return size_t(_finish - _start);
     }
 
+    vector& operator=(const vector &other);
+    vector& operator=(vector &&other);
+    vector& operator=(std::initializer_list<T> ilist);
+
+    void assign(size_type count, const T &value);
+    template <typename InputIterator >
+    void assign(InputIterator first, InputIterator last);
+    void assign(std::initializer_list<T> ilist);
+
     void clear();
 
     void push_back(const T &value);
     void push_back(T &&value);
     void pop_back();
 
     T &operator[](size_t n) {
       return _start[n];
public:
     list(const list &other);
     list(list &&other);
     ~list();
     
     list& operator=(const list &other);
     list& operator=(list &&other);
     list& operator=(std::initializer_list<T> ilist);
 
+    void assign(size_type count, const T &value);
+    template <typename InputIterator >
+    void assign(InputIterator first, InputIterator last);
+    void assign(std::initializer_list<T> ilist);
+
     void clear();
 
+    void push_back(const T &value);
+    void push_back(T &&value);
+    void pop_back();
+
+    void push_front(const T &value);
+    void push_front(T &&value);
+    void pop_front();
+
     iterator begin() { return iterator(_start); }
     const_iterator begin() const { return const_iterator(_start); }
     const_iterator cbegin() const { return const_iterator(_start); }
     iterator end() { return iterator(_finish); }
     const_iterator end() const { return const_iterator(_finish); }
     const_iterator cend() const { return const_iterator(_finish); }
 
     T& front() { return *begin(); }
public:
     deque(const deque &other);
     deque(deque &&other);
     ~deque();
     
     size_t size() const {
       return size_t(_finish - _start);
     }
     
+    deque& operator=(const deque &other);
+    deque& operator=(deque &&other);
+    deque& operator=(std::initializer_list<T> ilist);
+
+    void assign(size_type count, const T &value);
+    template <typename InputIterator >
+    void assign(InputIterator first, InputIterator last);
+    void assign(std::initializer_list<T> ilist);
+
     void clear();
 
     void push_back(const T &value);
     void push_back(T &&value);
     void pop_back();
 
     void push_front(const T &value);
     void push_front(T &&value);
     void pop_front();
 
     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); }
     const_iterator cbegin() const { return const_iterator(_start); }
     iterator end() { return iterator(_finish); }
     const_iterator end() const { return const_iterator(_finish); }
     const_iterator cend() 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 forward_list {
     struct __item {
       T data;
       __item *next;
     } *_start;
   public:
     typedef T value_type;
     typedef size_t size_type;
     typedef __fwdl_iterator<__item, T *, T &> iterator;
     typedef __fwdl_iterator<__item, const T *, const T &> const_iterator;
 
     forward_list() : _start(0) {}
     template <typename InputIterator>
     forward_list(InputIterator first, InputIterator last);
     forward_list(const forward_list &other);
     forward_list(forward_list &&other);
     ~forward_list();
     
+    forward_list& operator=(const forward_list &other);
+    forward_list& operator=(forward_list &&other);
+    forward_list& operator=(std::initializer_list<T> ilist);
+
+    void assign(size_type count, const T &value);
+    template <typename InputIterator >
+    void assign(InputIterator first, InputIterator last);
+    void assign(std::initializer_list<T> ilist);
+
     void clear();
 
     void push_front(const T &value);
     void push_front(T &&value);
     void pop_front();
 
     iterator begin() { return iterator(_start); }
     const_iterator begin() const { return const_iterator(_start); }

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:514 {{Called C++ object pointer is null}}
+  // expected-warning@../Inputs/system-header-simulator-cxx.h:554 {{Called C++ object pointer is null}}
 #endif
 }

test/Analysis/invalidated-iterator.cpp

+// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.InvalidatedIterator -analyzer-eagerly-assume -analyzer-config aggressive-relational-comparison-simplification=true -analyzer-config c++-container-inlining=false %s -verify
+// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.InvalidatedIterator -analyzer-eagerly-assume -analyzer-config aggressive-relational-comparison-simplification=true -analyzer-config c++-container-inlining=true -DINLINE=1 %s -verify
+
+#include "Inputs/system-header-simulator-cxx.h"
+
+void bad_copy_assign_operator_list1(std::list<int> &L1,
+                                    const std::list<int> &L2) {
+  auto i0 = L1.cbegin();
+  L1 = L2;
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_copy_assign_operator_vector1(std::vector<int> &V1,
+                                      const std::vector<int> &V2) {
+  auto i0 = V1.cbegin();
+  V1 = V2;
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_copy_assign_operator_deque1(std::deque<int> &D1,
+                                     const std::deque<int> &D2) {
+  auto i0 = D1.cbegin();
+  D1 = D2;
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_copy_assign_operator_forward_list1(std::forward_list<int> &FL1,
+                                            const std::forward_list<int> &FL2) {
+  auto i0 = FL1.cbegin();
+  FL1 = FL2;
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+}