[Analyzer] Iterator Checker - Part 8: Support for assign, clear, insert, emplace and erase operations

[baloghadamsoftware]

Summary

This patch adds support for the following operations in the iterator checkers: assign, clear, insert, insert_after, emplace, emplace_after, erase and erase_after. This affects mismatched iterator checks ("this" and parameter must match) and invalidation checks (according to the standard).

[NoQ]

This looks clear to me.

[baloghadamsoftware]

Rebased.

[baloghadamsoftware]

Rebased.

cfe/trunk/lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

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::PostStmt<MaterializeTemporaryExpr>,
+                     check::PostStmt<MaterializeTemporaryExpr>, check::Bind,
                      check::LiveSymbols, check::DeadSymbols,
                      eval::Assume> {
 
   std::unique_ptr<BugType> OutOfRangeBugType;
   std::unique_ptr<BugType> MismatchedBugType;
   std::unique_ptr<BugType> InvalidatedBugType;
 
   void handleComparison(CheckerContext &C, const SVal &RetVal, const SVal &LVal,
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 Expr *CE = nullptr,
                     const SVal &OldCont = UndefinedVal()) const;
+  void handleClear(CheckerContext &C, const SVal &Cont) const;
   void handlePushBack(CheckerContext &C, const SVal &Cont) const;
   void handlePopBack(CheckerContext &C, const SVal &Cont) const;
   void handlePushFront(CheckerContext &C, const SVal &Cont) const;
   void handlePopFront(CheckerContext &C, const SVal &Cont) const;
+  void handleInsert(CheckerContext &C, const SVal &Iter) const;
+  void handleErase(CheckerContext &C, const SVal &Iter) const;
+  void handleErase(CheckerContext &C, const SVal &Iter1,
+                   const SVal &Iter2) const;
+  void handleEraseAfter(CheckerContext &C, const SVal &Iter) const;
+  void handleEraseAfter(CheckerContext &C, const SVal &Iter1,
+                        const SVal &Iter2) const;
   void verifyRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op,
                               const SVal &RetVal, const SVal &LHS,
                               const SVal &RHS) const;
+  void verifyMatch(CheckerContext &C, const SVal &Iter,
+                   const MemRegion *Cont) const;
   void verifyMatch(CheckerContext &C, const SVal &Iter1,
                    const SVal &Iter2) const;
 
   void reportOutOfRangeBug(const StringRef &Message, const SVal &Val,
                            CheckerContext &C, ExplodedNode *ErrNode) const;
   void reportMismatchedBug(const StringRef &Message, const SVal &Val1,
                            const SVal &Val2, CheckerContext &C,
                            ExplodedNode *ErrNode) const;
enum CheckKind {
     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 checkBind(SVal Loc, SVal Val, const Stmt *S, CheckerContext &C) const;
+  void checkPostStmt(const CXXConstructExpr *CCE, CheckerContext &C) const;
+  void checkPostStmt(const DeclStmt *DS, CheckerContext &C) const;
   void checkPostStmt(const MaterializeTemporaryExpr *MTE,
                      CheckerContext &C) const;
   void checkLiveSymbols(ProgramStateRef State, SymbolReaper &SR) const;
   void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
   ProgramStateRef evalAssume(ProgramStateRef State, SVal Cond,
                              bool Assumption) const;
 };
 } // namespace

 
 namespace {
 
 bool isIteratorType(const QualType &Type);
 bool isIterator(const CXXRecordDecl *CRD);
 bool isComparisonOperator(OverloadedOperatorKind OK);
 bool isBeginCall(const FunctionDecl *Func);
 bool isEndCall(const FunctionDecl *Func);
+bool isAssignCall(const FunctionDecl *Func);
+bool isClearCall(const FunctionDecl *Func);
 bool isPushBackCall(const FunctionDecl *Func);
 bool isEmplaceBackCall(const FunctionDecl *Func);
 bool isPopBackCall(const FunctionDecl *Func);
 bool isPushFrontCall(const FunctionDecl *Func);
 bool isEmplaceFrontCall(const FunctionDecl *Func);
 bool isPopFrontCall(const FunctionDecl *Func);
+bool isInsertCall(const FunctionDecl *Func);
+bool isEraseCall(const FunctionDecl *Func);
+bool isEraseAfterCall(const FunctionDecl *Func);
+bool isEmplaceCall(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);
 bool hasSubscriptOperator(ProgramStateRef State, const MemRegion *Reg);
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);
+ProgramStateRef
+invalidateAllIteratorPositionsExcept(ProgramStateRef State,
+                                     const MemRegion *Cont, SymbolRef Offset,
+                                     BinaryOperator::Opcode Opc);
 ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
                                             SymbolRef Offset,
                                             BinaryOperator::Opcode Opc);
+ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
+                                            SymbolRef Offset1,
+                                            BinaryOperator::Opcode Opc1,
+                                            SymbolRef Offset2,
+                                            BinaryOperator::Opcode Opc2);
 ProgramStateRef reassignAllIteratorPositions(ProgramStateRef State,
                                              const MemRegion *Cont,
                                              const MemRegion *NewCont);
 ProgramStateRef reassignAllIteratorPositionsUnless(ProgramStateRef State,
                                                    const MemRegion *Cont,
                                                    const MemRegion *NewCont,
                                                    SymbolRef Offset,
                                                    BinaryOperator::Opcode Opc);
if (ChecksEnabled[CK_IteratorRangeChecker] &&
 
         if (!isIteratorType(Call.getArgExpr(0)->getType()) ||
             !isIteratorType(Call.getArgExpr(1)->getType()))
           return;
 
         verifyMatch(C, Call.getArgSVal(0), Call.getArgSVal(1));
       }
     }
+  } else if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
+    if (!ChecksEnabled[CK_MismatchedIteratorChecker])
+      return;
+
+    const auto *ContReg = InstCall->getCXXThisVal().getAsRegion();
+    if (!ContReg)
+      return;
+    // Check for erase, insert and emplace using iterator of another container
+    if (isEraseCall(Func) || isEraseAfterCall(Func)) {
+      verifyMatch(C, Call.getArgSVal(0),
+                  InstCall->getCXXThisVal().getAsRegion());
+      if (Call.getNumArgs() == 2) {
+        verifyMatch(C, Call.getArgSVal(1),
+                    InstCall->getCXXThisVal().getAsRegion());
+      }
+    } else if (isInsertCall(Func)) {
+      verifyMatch(C, Call.getArgSVal(0),
+                  InstCall->getCXXThisVal().getAsRegion());
+      if (Call.getNumArgs() == 3 &&
+          isIteratorType(Call.getArgExpr(1)->getType()) &&
+          isIteratorType(Call.getArgExpr(2)->getType())) {
+        verifyMatch(C, Call.getArgSVal(1), Call.getArgSVal(2));
+      }
+    } else if (isEmplaceCall(Func)) {
+      verifyMatch(C, Call.getArgSVal(0),
+                  InstCall->getCXXThisVal().getAsRegion());
+    }
   } else if (isa<CXXConstructorCall>(&Call)) {
     // Check match of first-last iterator pair in a constructor of a container
     if (Call.getNumArgs() < 2)
       return;
 
     const auto *Ctr = cast<CXXConstructorDecl>(Call.getDecl());
     if (Ctr->getNumParams() < 2)
       return;
if (isAssignmentOperator(Op)) {
                         Call.getNumArgs());
       } else {
         handleDecrement(C, Call.getReturnValue(), Call.getArgSVal(0),
                         Call.getNumArgs());
       }
     }
   } else {
     if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
-      if (isPushBackCall(Func) || isEmplaceBackCall(Func)) {
+      if (isAssignCall(Func)) {
+        handleAssign(C, InstCall->getCXXThisVal());
+      } else if (isClearCall(Func)) {
+        handleClear(C, InstCall->getCXXThisVal());
+      } else if (isPushBackCall(Func) || isEmplaceBackCall(Func)) {
         handlePushBack(C, InstCall->getCXXThisVal());
       } else if (isPopBackCall(Func)) {
         handlePopBack(C, InstCall->getCXXThisVal());
       } else if (isPushFrontCall(Func) || isEmplaceFrontCall(Func)) {
         handlePushFront(C, InstCall->getCXXThisVal());
       } else if (isPopFrontCall(Func)) {
         handlePopFront(C, InstCall->getCXXThisVal());
+      } else if (isInsertCall(Func) || isEmplaceCall(Func)) {
+        handleInsert(C, Call.getArgSVal(0));
+      } else if (isEraseCall(Func)) {
+        if (Call.getNumArgs() == 1) {
+          handleErase(C, Call.getArgSVal(0));
+        } else if (Call.getNumArgs() == 2) {
+          handleErase(C, Call.getArgSVal(0), Call.getArgSVal(1));
+        }
+      } else if (isEraseAfterCall(Func)) {
+        if (Call.getNumArgs() == 1) {
+          handleEraseAfter(C, Call.getArgSVal(0));
+        } else if (Call.getNumArgs() == 2) {
+          handleEraseAfter(C, Call.getArgSVal(0), Call.getArgSVal(1));
+        }
       }
     }
 
     const auto *OrigExpr = Call.getOriginExpr();
     if (!OrigExpr)
       return;
 
     if (!isIteratorType(Call.getResultType()))
for (unsigned i = 0; i < Call.getNumArgs(); ++i) {
                             Pos->getContainer());
           return;
         }
       }
     }
   }
 }
 
+void IteratorChecker::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 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::verifyRandomIncrOrDecr(CheckerContext &C,
   if (isOutOfRange(State, NewPos)) {
     auto *N = C.generateNonFatalErrorNode(State);
     if (!N)
       return;
     reportOutOfRangeBug("Iterator accessed past its end.", LHS, C, N);
   }
 }
 
+void IteratorChecker::verifyMatch(CheckerContext &C, const SVal &Iter,
+                                  const MemRegion *Cont) const {
+  // Verify match between a container and the container of an iterator
+  while (const auto *CBOR = Cont->getAs<CXXBaseObjectRegion>()) {
+    Cont = CBOR->getSuperRegion();
+  }
+
+  auto State = C.getState();
+  const auto *Pos = getIteratorPosition(State, Iter);
+  if (Pos && Pos->getContainer() != Cont) {
+    auto *N = C.generateNonFatalErrorNode(State);
+    if (!N) {
+      return;
+    }
+    reportMismatchedBug("Container accessed using foreign iterator argument.", Iter, Cont, C, N);
+  }
+}
+
 void IteratorChecker::verifyMatch(CheckerContext &C, const SVal &Iter1,
                                   const SVal &Iter2) const {
   // Verify match between the containers of two iterators
   auto State = C.getState();
   const auto *Pos1 = getIteratorPosition(State, Iter1);
   const auto *Pos2 = getIteratorPosition(State, Iter2);
   if (Pos1 && Pos2 && Pos1->getContainer() != Pos2->getContainer()) {
     auto *N = C.generateNonFatalErrorNode(State);
if (OldContReg) {
         // container, so reassign all iterator positions to the new container.
         State = reassignAllIteratorPositions(State, OldContReg, ContReg);
       }
     }
   }
   C.addTransition(State);
 }
 
+void IteratorChecker::handleClear(CheckerContext &C, const SVal &Cont) const {
+  const auto *ContReg = Cont.getAsRegion();
+  if (!ContReg)
+    return;
+
+  while (const auto *CBOR = ContReg->getAs<CXXBaseObjectRegion>()) {
+    ContReg = CBOR->getSuperRegion();
+  }
+
+  // The clear() operation invalidates all the iterators, except the past-end
+  // iterators of list-like containers
+  auto State = C.getState();
+  if (!hasSubscriptOperator(State, ContReg) ||
+      !backModifiable(State, ContReg)) {
+    const auto CData = getContainerData(State, ContReg);
+    if (CData) {
+      if (const auto EndSym = CData->getEnd()) {
+        State =
+            invalidateAllIteratorPositionsExcept(State, ContReg, EndSym, BO_GE);
+        C.addTransition(State);
+        return;
+      }
+    }
+  }
+  State = invalidateAllIteratorPositions(State, ContReg);
+  C.addTransition(State);
+}
+
 void IteratorChecker::handlePushBack(CheckerContext &C,
                                      const SVal &Cont) const {
   const auto *ContReg = Cont.getAsRegion();
   if (!ContReg)
     return;
 
   while (const auto *CBOR = ContReg->getAs<CXXBaseObjectRegion>()) {
     ContReg = CBOR->getSuperRegion();
const auto newBeginSym =
                     nonloc::SymbolVal(BeginSym),
                     nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
                     SymMgr.getType(BeginSym)).getAsSymbol();
     State = setContainerData(State, ContReg, CData->newBegin(newBeginSym));
     C.addTransition(State);
   }
 }
 
+void IteratorChecker::handleInsert(CheckerContext &C, const SVal &Iter) const {
+  auto State = C.getState();
+  const auto *Pos = getIteratorPosition(State, Iter);
+  if (!Pos)
+    return;
+
+  // For deque-like containers invalidate all iterator positions. For
+  // vector-like containers invalidate iterator positions after the insertion.
+  const auto *Cont = Pos->getContainer();
+  if (hasSubscriptOperator(State, Cont) && backModifiable(State, Cont)) {
+    if (frontModifiable(State, Cont)) {
+      State = invalidateAllIteratorPositions(State, Cont);
+    } else {
+      State = invalidateIteratorPositions(State, Pos->getOffset(), BO_GE);
+    }
+    if (const auto *CData = getContainerData(State, Cont)) {
+      if (const auto EndSym = CData->getEnd()) {
+        State = invalidateIteratorPositions(State, EndSym, BO_GE);
+        State = setContainerData(State, Cont, CData->newEnd(nullptr));
+      }
+    }
+    C.addTransition(State);
+  }
+}
+
+void IteratorChecker::handleErase(CheckerContext &C, const SVal &Iter) const {
+  auto State = C.getState();
+  const auto *Pos = getIteratorPosition(State, Iter);
+  if (!Pos)
+    return;
+
+  // For deque-like containers invalidate all iterator positions. For
+  // vector-like containers invalidate iterator positions at and after the
+  // deletion. For list-like containers only invalidate the deleted position.
+  const auto *Cont = Pos->getContainer();
+  if (hasSubscriptOperator(State, Cont) && backModifiable(State, Cont)) {
+    if (frontModifiable(State, Cont)) {
+      State = invalidateAllIteratorPositions(State, Cont);
+    } else {
+      State = invalidateIteratorPositions(State, Pos->getOffset(), BO_GE);
+    }
+    if (const auto *CData = getContainerData(State, Cont)) {
+      if (const auto EndSym = CData->getEnd()) {
+        State = invalidateIteratorPositions(State, EndSym, BO_GE);
+        State = setContainerData(State, Cont, CData->newEnd(nullptr));
+      }
+    }
+  } else {
+    State = invalidateIteratorPositions(State, Pos->getOffset(), BO_EQ);
+  }
+  C.addTransition(State);
+}
+
+void IteratorChecker::handleErase(CheckerContext &C, const SVal &Iter1,
+                                  const SVal &Iter2) const {
+  auto State = C.getState();
+  const auto *Pos1 = getIteratorPosition(State, Iter1);
+  const auto *Pos2 = getIteratorPosition(State, Iter2);
+  if (!Pos1 || !Pos2)
+    return;
+
+  // For deque-like containers invalidate all iterator positions. For
+  // vector-like containers invalidate iterator positions at and after the
+  // deletion range. For list-like containers only invalidate the deleted
+  // position range [first..last].
+  const auto *Cont = Pos1->getContainer();
+  if (hasSubscriptOperator(State, Cont) && backModifiable(State, Cont)) {
+    if (frontModifiable(State, Cont)) {
+      State = invalidateAllIteratorPositions(State, Cont);
+    } else {
+      State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GE);
+    }
+    if (const auto *CData = getContainerData(State, Cont)) {
+      if (const auto EndSym = CData->getEnd()) {
+        State = invalidateIteratorPositions(State, EndSym, BO_GE);
+        State = setContainerData(State, Cont, CData->newEnd(nullptr));
+      }
+    }
+  } else {
+    State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GE,
+                                        Pos2->getOffset(), BO_LT);
+  }
+  C.addTransition(State);
+}
+
+void IteratorChecker::handleEraseAfter(CheckerContext &C,
+                                       const SVal &Iter) const {
+  auto State = C.getState();
+  const auto *Pos = getIteratorPosition(State, Iter);
+  if (!Pos)
+    return;
+
+  // Invalidate the deleted iterator position, which is the position of the
+  // parameter plus one.
+  auto &SymMgr = C.getSymbolManager();
+  auto &BVF = SymMgr.getBasicVals();
+  auto &SVB = C.getSValBuilder();
+  const auto NextSym =
+    SVB.evalBinOp(State, BO_Add,
+                  nonloc::SymbolVal(Pos->getOffset()),
+                  nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
+                  SymMgr.getType(Pos->getOffset())).getAsSymbol();
+  State = invalidateIteratorPositions(State, NextSym, BO_EQ);
+  C.addTransition(State);
+}
+
+void IteratorChecker::handleEraseAfter(CheckerContext &C, const SVal &Iter1,
+                                       const SVal &Iter2) const {
+  auto State = C.getState();
+  const auto *Pos1 = getIteratorPosition(State, Iter1);
+  const auto *Pos2 = getIteratorPosition(State, Iter2);
+  if (!Pos1 || !Pos2)
+    return;
+
+  // Invalidate the deleted iterator position range (first..last)
+  State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GT,
+                                      Pos2->getOffset(), BO_LT);
+  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));
 }
 

 
 bool isEndCall(const FunctionDecl *Func) {
   const auto *IdInfo = Func->getIdentifier();
   if (!IdInfo)
     return false;
   return IdInfo->getName().endswith_lower("end");
 }
 
+bool isAssignCall(const FunctionDecl *Func) {
+  const auto *IdInfo = Func->getIdentifier();
+  if (!IdInfo)
+    return false;
+  if (Func->getNumParams() > 2)
+    return false;
+  return IdInfo->getName() == "assign";
+}
+
+bool isClearCall(const FunctionDecl *Func) {
+  const auto *IdInfo = Func->getIdentifier();
+  if (!IdInfo)
+    return false;
+  if (Func->getNumParams() > 0)
+    return false;
+  return IdInfo->getName() == "clear";
+}
+
 bool isPushBackCall(const FunctionDecl *Func) {
   const auto *IdInfo = Func->getIdentifier();
   if (!IdInfo)
     return false;
   if (Func->getNumParams() != 1)
     return false;
   return IdInfo->getName() == "push_back";
 }
bool isPopFrontCall(const FunctionDecl *Func) {
   const auto *IdInfo = Func->getIdentifier();
   if (!IdInfo)
     return false;
   if (Func->getNumParams() > 0)
     return false;
   return IdInfo->getName() == "pop_front";
 }
 
+bool isInsertCall(const FunctionDecl *Func) {
+  const auto *IdInfo = Func->getIdentifier();
+  if (!IdInfo)
+    return false;
+  if (Func->getNumParams() < 2 || Func->getNumParams() > 3)
+    return false;
+  if (!isIteratorType(Func->getParamDecl(0)->getType()))
+    return false;
+  return IdInfo->getName() == "insert";
+}
+
+bool isEmplaceCall(const FunctionDecl *Func) {
+  const auto *IdInfo = Func->getIdentifier();
+  if (!IdInfo)
+    return false;
+  if (Func->getNumParams() < 2)
+    return false;
+  if (!isIteratorType(Func->getParamDecl(0)->getType()))
+    return false;
+  return IdInfo->getName() == "emplace";
+}
+
+bool isEraseCall(const FunctionDecl *Func) {
+  const auto *IdInfo = Func->getIdentifier();
+  if (!IdInfo)
+    return false;
+  if (Func->getNumParams() < 1 || Func->getNumParams() > 2)
+    return false;
+  if (!isIteratorType(Func->getParamDecl(0)->getType()))
+    return false;
+  if (Func->getNumParams() == 2 &&
+      !isIteratorType(Func->getParamDecl(1)->getType()))
+    return false;
+  return IdInfo->getName() == "erase";
+}
+
+bool isEraseAfterCall(const FunctionDecl *Func) {
+  const auto *IdInfo = Func->getIdentifier();
+  if (!IdInfo)
+    return false;
+  if (Func->getNumParams() < 1 || Func->getNumParams() > 2)
+    return false;
+  if (!isIteratorType(Func->getParamDecl(0)->getType()))
+    return false;
+  if (Func->getNumParams() == 2 &&
+      !isIteratorType(Func->getParamDecl(1)->getType()))
+    return false;
+  return IdInfo->getName() == "erase_after";
+}
+
 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) ||
auto MatchCont = [&](const IteratorPosition &Pos) {
     return Pos.getContainer() == Cont;
   };
   auto Invalidate = [&](const IteratorPosition &Pos) {
     return Pos.invalidate();
   };
   return processIteratorPositions(State, MatchCont, Invalidate);
 }
 
+ProgramStateRef
+invalidateAllIteratorPositionsExcept(ProgramStateRef State,
+                                     const MemRegion *Cont, SymbolRef Offset,
+                                     BinaryOperator::Opcode Opc) {
+  auto MatchContAndCompare = [&](const IteratorPosition &Pos) {
+    return Pos.getContainer() == Cont &&
+           !compare(State, Pos.getOffset(), Offset, Opc);
+  };
+  auto Invalidate = [&](const IteratorPosition &Pos) {
+    return Pos.invalidate();
+  };
+  return processIteratorPositions(State, MatchContAndCompare, Invalidate);
+}
+
 ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
                                             SymbolRef Offset,
                                             BinaryOperator::Opcode Opc) {
   auto Compare = [&](const IteratorPosition &Pos) {
     return compare(State, Pos.getOffset(), Offset, Opc);
   };
   auto Invalidate = [&](const IteratorPosition &Pos) {
     return Pos.invalidate();
   };
   return processIteratorPositions(State, Compare, Invalidate);
 }
 
+ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
+                                            SymbolRef Offset1,
+                                            BinaryOperator::Opcode Opc1,
+                                            SymbolRef Offset2,
+                                            BinaryOperator::Opcode Opc2) {
+  auto Compare = [&](const IteratorPosition &Pos) {
+    return compare(State, Pos.getOffset(), Offset1, Opc1) &&
+           compare(State, Pos.getOffset(), Offset2, Opc2);
+  };
+  auto Invalidate = [&](const IteratorPosition &Pos) {
+    return Pos.invalidate();
+  };
+  return processIteratorPositions(State, Compare, Invalidate);
+}
+
 ProgramStateRef reassignAllIteratorPositions(ProgramStateRef State,
                                              const MemRegion *Cont,
                                              const MemRegion *NewCont) {
   auto MatchCont = [&](const IteratorPosition &Pos) {
     return Pos.getContainer() == Cont;
   };
   auto ReAssign = [&](const IteratorPosition &Pos) {
     return Pos.reAssign(NewCont);

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

public:
     void clear();
 
     void push_back(const T &value);
     void push_back(T &&value);
     template<class... Args>
     void emplace_back(Args&&... args);
     void pop_back();
 
+    iterator insert(const_iterator position, const value_type &val);
+    iterator insert(const_iterator position, size_type n,
+                    const value_type &val);
+    template <typename InputIterator>
+    iterator insert(const_iterator position, InputIterator first,
+                    InputIterator last);
+    iterator insert(const_iterator position, value_type &&val);
+    iterator insert(const_iterator position, initializer_list<value_type> il);
+
+    template <class... Args>
+    iterator emplace(const_iterator position, Args&&... args);
+
+    iterator erase(const_iterator position);
+    iterator erase(const_iterator first, const_iterator last);
+
     T &operator[](size_t n) {
       return _start[n];
     }
     
     const T &operator[](size_t n) const {
       return _start[n];
     }
     
public:
     void pop_back();
 
     void push_front(const T &value);
     void push_front(T &&value);
     template<class... Args>
     void emplace_front(Args&&... args);
     void pop_front();
 
+    iterator insert(const_iterator position, const value_type &val);
+    iterator insert(const_iterator position, size_type n,
+                    const value_type &val);
+    template <typename InputIterator>
+    iterator insert(const_iterator position, InputIterator first,
+                    InputIterator last);
+    iterator insert(const_iterator position, value_type &&val);
+    iterator insert(const_iterator position, initializer_list<value_type> il);
+
+    template <class... Args>
+    iterator emplace(const_iterator position, Args&&... args);
+
+    iterator erase(const_iterator position);
+    iterator erase(const_iterator first, const_iterator last);
+
     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:
     void pop_back();
 
     void push_front(const T &value);
     void push_front(T &&value);
     template<class... Args>
     void emplace_front(Args&&... args);
     void pop_front();
 
+    iterator insert(const_iterator position, const value_type &val);
+    iterator insert(const_iterator position, size_type n,
+                    const value_type &val);
+    template <typename InputIterator>
+    iterator insert(const_iterator position, InputIterator first,
+                    InputIterator last);
+    iterator insert(const_iterator position, value_type &&val);
+    iterator insert(const_iterator position, initializer_list<value_type> il);
+
+    template <class... Args>
+    iterator emplace(const_iterator position, Args&&... args);
+
+    iterator erase(const_iterator position);
+    iterator erase(const_iterator first, const_iterator last);
+
     T &operator[](size_t n) {
       return _start[n];
     }
 
     const T &operator[](size_t n) const {
       return _start[n];
     }
 
public:
     void clear();
 
     void push_front(const T &value);
     void push_front(T &&value);
     template<class... Args>
     void emplace_front(Args&&... args);
     void pop_front();
 
+    iterator insert_after(const_iterator position, const value_type &val);
+    iterator insert_after(const_iterator position, value_type &&val);
+    iterator insert_after(const_iterator position, size_type n,
+                          const value_type &val);
+    template <typename InputIterator>
+    iterator insert_after(const_iterator position, InputIterator first,
+                          InputIterator last);
+    iterator insert_after(const_iterator position,
+                          initializer_list<value_type> il);
+
+    template <class... Args>
+    iterator emplace_after(const_iterator position, Args&&... args);
+
+    iterator erase_after(const_iterator position);
+    iterator erase_after(const_iterator first, const_iterator last);
+
     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(); }
     const_iterator end() const { return const_iterator(); }
     const_iterator cend() const { return const_iterator(); }
 
     T& front() { return *begin(); }

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

cfe/trunk/test/Analysis/invalidated-iterator.cpp

 
 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}}
 }
 
+void bad_assign_list1(std::list<int> &L, int n) {
+  auto i0 = L.cbegin();
+  L.assign(10, n);
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_assign_vector1(std::vector<int> &V, int n) {
+  auto i0 = V.cbegin();
+  V.assign(10, n);
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_assign_deque1(std::deque<int> &D, int n) {
+  auto i0 = D.cbegin();
+  D.assign(10, n);
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_assign_forward_list1(std::forward_list<int> &FL, int n) {
+  auto i0 = FL.cbegin();
+  FL.assign(10, n);
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void good_clear_list1(std::list<int> &L) {
+  auto i0 = L.cend();
+  L.clear();
+  --i0; // no-warning
+}
+
+void bad_clear_list1(std::list<int> &L) {
+  auto i0 = L.cbegin(), i1 = L.cend();
+  L.clear();
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_clear_vector1(std::vector<int> &V) {
+  auto i0 = V.cbegin(), i1 = V.cend();
+  V.clear();
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+  --i1; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_clear_deque1(std::deque<int> &D) {
+  auto i0 = D.cbegin(), i1 = D.cend();
+  D.clear();
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+  --i1; // expected-warning{{Invalidated iterator accessed}}
+}
+
 void good_push_back_list1(std::list<int> &L, int n) {
   auto i0 = L.cbegin(), i1 = L.cend();
   L.push_back(n);
   *i0; // no-warning
   --i1; // no-warning
 }
 
 void good_push_back_vector1(std::vector<int> &V, int n) {
void good_pop_front_forward_list1(std::forward_list<int> &FL, int n) {
   *i1; // no-warning
 }
 
 void bad_pop_front_forward_list1(std::forward_list<int> &FL, int n) {
   auto i1 = FL.cbegin(), i0 = i1++;
   FL.pop_front();
   *i0; // expected-warning{{Invalidated iterator accessed}}
 }
+
+void good_insert_list1(std::list<int> &L, int n) {
+  auto i1 = L.cbegin(), i0 = i1++;
+  L.insert(i1, n);
+  *i0; // no-warning
+  *i1; // no-warning
+}
+
+void good_insert_vector1(std::vector<int> &V, int n) {
+  auto i1 = V.cbegin(), i0 = i1++;
+  V.insert(i1, n);
+  *i0; // no-warning
+}
+
+void bad_insert_vector1(std::vector<int> &V, int n) {
+  auto i1 = V.cbegin(), i0 = i1++;
+  V.insert(i1, n);
+  *i1; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_insert_deque1(std::deque<int> &D, int n) {
+  auto i1 = D.cbegin(), i0 = i1++;
+  D.insert(i1, n);
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+  *i1; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void good_emplace_list1(std::list<int> &L, int n) {
+  auto i1 = L.cbegin(), i0 = i1++;
+  L.emplace(i1, n);
+  *i0; // no-warning
+  *i1; // no-warning
+}
+
+void good_emplace_vector1(std::vector<int> &V, int n) {
+  auto i1 = V.cbegin(), i0 = i1++;
+  V.emplace(i1, n);
+  *i0; // no-warning
+}
+
+void bad_emplace_vector1(std::vector<int> &V, int n) {
+  auto i1 = V.cbegin(), i0 = i1++;
+  V.emplace(i1, n);
+  *i1; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_emplace_deque1(std::deque<int> &D, int n) {
+  auto i1 = D.cbegin(), i0 = i1++;
+  D.emplace(i1, n);
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+  *i1; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void good_erase_list1(std::list<int> &L) {
+  auto i2 = L.cbegin(), i0 = i2++, i1 = i2++;
+  L.erase(i1);
+  *i0; // no-warning
+  *i2; // no-warning
+}
+
+void bad_erase_list1(std::list<int> &L) {
+  auto i0 = L.cbegin();
+  L.erase(i0);
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void good_erase_vector1(std::vector<int> &V) {
+  auto i2 = V.cbegin(), i0 = i2++, i1 = i2++;
+  V.erase(i1);
+  *i0; // no-warning
+}
+
+void bad_erase_vector1(std::vector<int> &V) {
+  auto i1 = V.cbegin(), i0 = i1++;
+  V.erase(i0);
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+  *i1; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_erase_deque1(std::deque<int> &D) {
+  auto i2 = D.cbegin(), i0 = i2++, i1 = i2++;
+  D.erase(i1);
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+  *i1; // expected-warning{{Invalidated iterator accessed}}
+  *i2; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void good_erase_list2(std::list<int> &L) {
+  auto i3 = L.cbegin(), i0 = i3++, i1 = i3++, i2 = i3++;
+  L.erase(i1, i3);
+  *i0; // no-warning
+  *i3; // no-warning
+}
+
+void bad_erase_list2(std::list<int> &L) {
+  auto i2 = L.cbegin(), i0 = i2++, i1 = i2++;
+  L.erase(i0, i2);
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+  *i1; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void good_erase_vector2(std::vector<int> &V) {
+  auto i3 = V.cbegin(), i0 = i3++, i1 = i3++, i2 = i3++;;
+  V.erase(i1, i3);
+  *i0; // no-warning
+}
+
+void bad_erase_vector2(std::vector<int> &V) {
+  auto i2 = V.cbegin(), i0 = i2++, i1 = i2++;
+  V.erase(i0, i2);
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+  *i1; // expected-warning{{Invalidated iterator accessed}}
+  *i2; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_erase_deque2(std::deque<int> &D) {
+  auto i3 = D.cbegin(), i0 = i3++, i1 = i3++, i2 = i3++;
+  D.erase(i1, i3);
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+  *i1; // expected-warning{{Invalidated iterator accessed}}
+  *i2; // expected-warning{{Invalidated iterator accessed}}
+  *i3; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void good_erase_after_forward_list1(std::forward_list<int> &FL) {
+  auto i2 = FL.cbegin(), i0 = i2++, i1 = i2++;
+  FL.erase_after(i0);
+  *i0; // no-warning
+  *i2; // no-warning
+}
+
+void bad_erase_after_forward_list1(std::forward_list<int> &FL) {
+  auto i1 = FL.cbegin(), i0 = i1++;
+  FL.erase_after(i0);
+  *i1; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void good_erase_after_forward_list2(std::forward_list<int> &FL) {
+  auto i3 = FL.cbegin(), i0 = i3++, i1 = i3++, i2 = i3++;
+  FL.erase_after(i0, i3);
+  *i0; // no-warning
+  *i3; // no-warning
+}
+
+void bad_erase_after_forward_list2(std::forward_list<int> &FL) {
+  auto i3 = FL.cbegin(), i0 = i3++, i1 = i3++, i2 = i3++;
+  FL.erase_after(i0, i3);
+  *i1; // expected-warning{{Invalidated iterator accessed}}
+  *i2; // expected-warning{{Invalidated iterator accessed}}
+}