[Analyzer] Checker for mismatched iterators

[baloghadamsoftware]

Summary

A new checker to check whether multiple iterators which should refer to the same container refer to different ones. Here we include comparisons, constructors which take an iterator pair and any template function which takes iterator pair(s).

[baloghadamsoftware]

The checker itself disappeared mystically from the previous diff...

[NoQ]

Hello, thanks for another useful checker! I make quite a few of these mistakes regularly.

This one looks similar to the IteratorPastEnd checker, so much that i'd definitely advice re-using some code. At the very least, functions like isIterator() should definitely deserve a header somewhere in include/clang/StaticAnalyzer/Checkers.

Also, did you consider merging these checkers together into one file? Just because they have so much in common.

The usual stuff: do you already have any quality statistics, eg. how many warnings did you see emitted by this checker, how many of them are true/false positives. With that, better warning messages, and a bug reporter visitor to highlight the origin of the misplaced iterator, i think this checker should be enabled by default (go out of alpha).

lib/StaticAnalyzer/Checkers/MismatchedIteratorChecker.cpp

312

Hmm. Now i suspect that the checkBind() callback should have covered this, both here and in the previous checker. Did you try using that instead, and see if other callbacks are covered by checkBind() as well?

357

I'd consider !isLive() here due to, uhm, subtle differences we currently have between these two (there's a hard-to-fix bug that causes some symbols to never make it to the dead set, see D18860).

[baloghadamsoftware]

In D29419#671839, @NoQ wrote:

This one looks similar to the IteratorPastEnd checker, so much that i'd definitely advice re-using some code. At the very least, functions like isIterator() should definitely deserve a header somewhere in include/clang/StaticAnalyzer/Checkers.

Also, did you consider merging these checkers together into one file? Just because they have so much in common.

Yes. Actually these two checkers served for me as prototypes, but it turned out quite early that if I want to implement the most important iterator checker, thus the checker for invalidated iterators it requires a tracker structure that includes all the data we need for these two checkers. So it would be a wast of resources to duplicate these data. So now I am also working on the merged version.

[baloghadamsoftware]

Updated according to the comments.

[baloghadamsoftware]

lib/StaticAnalyzer/Checkers/MismatchedIteratorChecker.cpp

312

You are right. It seems to eliminate the need for checking C++ construct expressions, declarations with initial values and assignments.

[hiraditya]

lib/StaticAnalyzer/Checkers/MismatchedIteratorChecker.cpp

375

This can be rewritten as:

if (auto *N = C.generateNonFatalErrorNode(State, &Tag))
  reportMismatchedBug("Iterator access mismatched.", Iter1, C, N);

[zaks.anna]

So it would be a wast of resources to duplicate these data. So now I am also working on the merged version.

Would it make sense to just resume the review on the merged patch?

[baloghadamsoftware]

Superseeded by patch D31975.

include/clang/StaticAnalyzer/Checkers/Checkers.td

 } // end: "optin.cplusplus"
 
 let ParentPackage = CplusplusAlpha in {
 
 def IteratorPastEndChecker : Checker<"IteratorPastEnd">,
   HelpText<"Check iterators used past end">,
   DescFile<"IteratorPastEndChecker.cpp">;
 
+def MismatchedIteratorChecker : Checker<"MismatchedIterator">,
+  HelpText<"Check iterators used for the wrong container">,
+  DescFile<"MismatchedIteratorChecker.cpp">;
+
 } // end: "alpha.cplusplus"
 
 
 //===----------------------------------------------------------------------===//
 // Valist checkers.
 //===----------------------------------------------------------------------===//
 
 let ParentPackage = ValistAlpha in {

lib/StaticAnalyzer/Checkers/CMakeLists.txt

add_clang_library(clangStaticAnalyzerCheckers
   IvarInvalidationChecker.cpp
   LLVMConventionsChecker.cpp
   LocalizationChecker.cpp
   MacOSKeychainAPIChecker.cpp
   MacOSXAPIChecker.cpp
   MallocChecker.cpp
   MallocOverflowSecurityChecker.cpp
   MallocSizeofChecker.cpp
+  MismatchedIteratorChecker.cpp
   MPI-Checker/MPIBugReporter.cpp
   MPI-Checker/MPIChecker.cpp
   MPI-Checker/MPIFunctionClassifier.cpp
   NSAutoreleasePoolChecker.cpp
   NSErrorChecker.cpp
   NoReturnFunctionChecker.cpp
   NonNullParamChecker.cpp
   NullabilityChecker.cpp

lib/StaticAnalyzer/Checkers/MismatchedIteratorChecker.cpp

+//===-- MismatchedIteratorChecker.cpp -----------------------------*- C++ -*--//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Defines a checker for using iterators outside their range (past end). Usage
+// means here dereferencing, incrementing, decrementing etc.
+//
+//===----------------------------------------------------------------------===//
+
+#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 {
+class MismatchedIteratorChecker
+    : public Checker<check::PreCall, check::PostCall,
+                     check::PreStmt<CXXConstructExpr>,
+                     check::PreStmt<CXXOperatorCallExpr>,
+                     check::PostStmt<MaterializeTemporaryExpr>, check::Bind,
+                     check::BeginFunction, check::DeadSymbols> {
+
+  std::unique_ptr<BugType> MismatchedBugType;
+
+  void verifyMatch(CheckerContext &C, const SVal &Iter,
+                   const MemRegion *Cont) const;
+  void verifyMatch(CheckerContext &C, const SVal &Iter1,
+                   const SVal &Iter2) const;
+  void handleBeginOrEnd(CheckerContext &C, const SVal &RetVal,
+                        const SVal &Cont) const;
+  void handleAssignment(CheckerContext &C, const SVal &LHS,
+                        const SVal &RHS) const;
+
+  void reportMismatchedBug(const StringRef &Message, const SVal &Val,
+                           CheckerContext &C, ExplodedNode *ErrNode) const;
+
+public:
+  MismatchedIteratorChecker();
+
+  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 checkPreStmt(const CXXConstructExpr *CCE, CheckerContext &C) const;
+  void checkBind(SVal Loc, SVal Val, const Stmt *S, CheckerContext &C) const;
+  void checkBeginFunction(CheckerContext &C) const;
+  void checkPostStmt(const MaterializeTemporaryExpr *MTE,
+                     CheckerContext &C) const;
+  void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
+};
+}
+
+REGISTER_MAP_WITH_PROGRAMSTATE(IteratorSymbolMap, SymbolRef, const MemRegion *)
+REGISTER_MAP_WITH_PROGRAMSTATE(IteratorRegionMap, const MemRegion *,
+                               const MemRegion *)
+
+namespace {
+
+static bool isIteratorType(const QualType &Type);
+static bool isIterator(const CXXRecordDecl *CRD);
+static bool isComparisonOperator(OverloadedOperatorKind OK);
+static bool isBeginOrEndCall(const FunctionDecl *Func);
+static bool isInsertCall(const FunctionDecl *Func);
+static bool isEraseCall(const FunctionDecl *Func);
+static bool isEmplaceCall(const FunctionDecl *Func);
+static const MemRegion *const *getIteratorContainer(ProgramStateRef State,
+                                                    const SVal &Val);
+static ProgramStateRef setIteratorContainer(ProgramStateRef State,
+                                            const SVal &Val,
+                                            const MemRegion *Cont);
+static ProgramStateRef removeIteratorContainer(ProgramStateRef State,
+                                               const SVal &Val);
+}
+
+MismatchedIteratorChecker::MismatchedIteratorChecker() {
+  MismatchedBugType.reset(
+      new BugType(this, "Mismatched Iterator", "C++ STL Error"));
+  MismatchedBugType->setSuppressOnSink(true);
+}
+
+void MismatchedIteratorChecker::checkPreCall(const CallEvent &Call,
+                                             CheckerContext &C) const {
+  const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
+  if (!Func)
+    return;
+
+  if (Func->isOverloadedOperator()) {
+    if (!isComparisonOperator(Func->getOverloadedOperator()))
+      return;
+
+    if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
+      if (Call.getNumArgs() < 1)
+        return;
+
+      if (!isIteratorType(InstCall->getCXXThisExpr()->getType()) ||
+          !isIteratorType(Call.getArgExpr(0)->getType()))
+        return;
+
+      verifyMatch(C, InstCall->getCXXThisVal(), Call.getArgSVal(0));
+    } else {
+      if (Call.getNumArgs() < 2)
+        return;
+
+      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)) {
+    const auto *ContReg = InstCall->getCXXThisVal().getAsRegion();
+    if (!ContReg)
+      return;
+    if (isEraseCall(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)) {
+    // The main purpose of iterators is to abstract away from different
+    // containers and provide a (maybe limited) uniform access to them.
+    // This implies that any correctly written template function that
+    // works on multiple containers using iterators takes different
+    // template parameters for different containers. So we can safely
+    // assume that passing iterators of different containers as arguments
+    // whose type replaces the same template parameter is a bug.
+    const auto *Templ = Func->getPrimaryTemplate();
+    if (!Templ)
+      return;
+
+    const auto *TParams = Templ->getTemplateParameters();
+    const auto *TArgs = Func->getTemplateSpecializationArgs();
+
+    for (auto i = 0U; i < TParams->size(); ++i) {
+      const auto *TPDecl = dyn_cast<TypeDecl>(TParams->getParam(i));
+      if (!TPDecl)
+        continue;
+
+      const auto TAType = TArgs->get(i).getAsType();
+      if (!isIteratorType(TAType))
+        continue;
+
+      SVal LHS = UndefinedVal();
+
+      for (auto j = 0U; j < Func->getNumParams(); ++j) {
+        const auto *Param = Func->getParamDecl(j);
+        const auto *ParamType =
+            Param->getType()->getAs<SubstTemplateTypeParmType>();
+        if (!ParamType ||
+            ParamType->getReplacedParameter()->getDecl() != TPDecl)
+          continue;
+        if (LHS.isUndef()) {
+          LHS = Call.getArgSVal(j);
+        } else {
+          verifyMatch(C, LHS, Call.getArgSVal(j));
+        }
+      }
+    }
+  }
+}
+
+void MismatchedIteratorChecker::checkPostCall(const CallEvent &Call,
+                                              CheckerContext &C) const {
+  const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
+  if (!Func)
+    return;
+
+  if (!Call.getOriginExpr())
+    return;
+
+  if (!isIteratorType(Call.getResultType()))
+    return;
+
+  auto State = C.getState();
+  // Already bound to container?
+  if (getIteratorContainer(State, Call.getReturnValue()))
+    return;
+
+  if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
+    if (isBeginOrEndCall(Func)) {
+      handleBeginOrEnd(C, Call.getReturnValue(), InstCall->getCXXThisVal());
+      return;
+    }
+  }
+
+  // Assumption: if return value is an iterator which is not yet bound to a
+  //             container, then look for the first iterator argument, and
+  //             bind the return value to the same container. This approach
+  //             works for STL algorithms.
+  for (unsigned i = 0; i < Call.getNumArgs(); ++i) {
+    if (isIteratorType(Call.getArgExpr(i)->getType())) {
+      if (const auto *Cont = getIteratorContainer(State, Call.getArgSVal(i))) {
+        State = setIteratorContainer(State, Call.getReturnValue(), *Cont);
+        C.addTransition(State);
+        return;
+      }
+    }
+  }
+}
+
+void MismatchedIteratorChecker::checkPreStmt(const CXXConstructExpr *CCE,
+                                             CheckerContext &C) const {
+  if (CCE->getNumArgs() < 2)
+    return;
+
+  const auto *Ctr = CCE->getConstructor();
+  if (Ctr->getNumParams() < 2)
+    return;
+
+  if (Ctr->getParamDecl(0)->getName() != "first" ||
+      Ctr->getParamDecl(1)->getName() != "last")
+    return;
+
+  if (!isIteratorType(CCE->getArg(0)->getType()) ||
+      !isIteratorType(CCE->getArg(1)->getType()))
+    return;
+
+  auto State = C.getState();
+  const auto *LCtx = C.getPredecessor()->getLocationContext();
+
+  verifyMatch(C, State->getSVal(CCE->getArg(0), LCtx),
+              State->getSVal(CCE->getArg(1), LCtx));
+}
+
+void MismatchedIteratorChecker::checkPreStmt(const CXXOperatorCallExpr *COCE,
+                                             CheckerContext &C) const {
+  const auto *ThisExpr = COCE->getArg(0);
+
+  auto State = C.getState();
+  const auto *LCtx = C.getPredecessor()->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);
+    const auto *Cont = getIteratorContainer(OldState, OldThis);
+    if (!Cont)
+      return;
+    State = setIteratorContainer(State, CurrentThis, *Cont);
+    C.addTransition(State);
+  }
+}
+
+void MismatchedIteratorChecker::checkBind(SVal Loc, SVal Val, const Stmt *S,
+                                          CheckerContext &C) const {
+  auto State = C.getState();
+  const auto *const *Cont = getIteratorContainer(State, Val);
+  if (Cont) {
+    State = setIteratorContainer(State, Loc, *Cont);
+    C.addTransition(State);
+  } else {
+    const auto *const *OldCont = getIteratorContainer(State, Loc);
+    if (OldCont) {
+      State = removeIteratorContainer(State, Loc);
+      C.addTransition(State);
+    }
+  }
+}
+
+void MismatchedIteratorChecker::checkBeginFunction(CheckerContext &C) const {
+  // Copy container 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;
+
+  const auto *FD = dyn_cast<FunctionDecl>(LCtx->getDecl());
+  if (!FD)
+    return;
+
+  const auto *CE = dyn_cast<CallExpr>(Site);
+  if (!CE)
+    return;
+
+  bool Change = false;
+  int idx = 0;
+  for (const auto P : FD->parameters()) {
+    auto Param = State->getLValue(P, LCtx);
+    auto Arg = State->getSVal(CE->getArg(idx++), LCtx->getParent());
+    const auto *const *Cont = getIteratorContainer(State, Arg);
+    if (!Cont)
+      continue;
+    State = setIteratorContainer(State, Param, *Cont);
+    Change = true;
+  }
+  if (Change) {
+    C.addTransition(State);
+  }
+}
+
+void MismatchedIteratorChecker::checkPostStmt(
+    const MaterializeTemporaryExpr *MTE, CheckerContext &C) const {
+  /* Transfer iterator container for to temporary objects */
+  auto State = C.getState();
+  const auto *LCtx = C.getLocationContext();
+  const auto *const *Cont = getIteratorContainer(
+      State, State->getSVal(MTE->GetTemporaryExpr(), LCtx));
+  if (!Cont)
+    return;
+  State = setIteratorContainer(State, State->getSVal(MTE, LCtx), *Cont);
+  C.addTransition(State);
+}
+
+void MismatchedIteratorChecker::checkDeadSymbols(SymbolReaper &SR,
+                                                 CheckerContext &C) const {
+  auto State = C.getState();
+
+  auto RegionMap = State->get<IteratorRegionMap>();
+  for (auto I = RegionMap.begin(), E = RegionMap.end(); I != E; ++I) {
+    if (!SR.isLiveRegion(I->first)) {
+      State = State->remove<IteratorRegionMap>(I->first);
+    }
+  }
+
+  auto SymbolMap = State->get<IteratorSymbolMap>();
+  for (auto I = SymbolMap.begin(), E = SymbolMap.end(); I != E; ++I) {
+    if (SR.isDead(I->first)) {
+      State = State->remove<IteratorSymbolMap>(I->first);
+    }
+  }
+}
+
+void MismatchedIteratorChecker::verifyMatch(CheckerContext &C, const SVal &Iter,
+                                            const MemRegion *Cont) const {
+  auto State = C.getState();
+  const auto *const *IterCont = getIteratorContainer(State, Iter);
+  if (IterCont && *IterCont != Cont) {
+    auto *N = C.generateNonFatalErrorNode(State);
+    if (!N) {
+      return;
+    }
+    reportMismatchedBug("Iterator access mismatched.", Iter, C, N);
+  }
+}
+
+void MismatchedIteratorChecker::verifyMatch(CheckerContext &C,
+                                            const SVal &Iter1,
+                                            const SVal &Iter2) const {
+  auto State = C.getState();
+  const auto *const *IterCont1 = getIteratorContainer(State, Iter1);
+  const auto *const *IterCont2 = getIteratorContainer(State, Iter2);
+  if (IterCont1 && IterCont2 && *IterCont1 != *IterCont2) {
+    // If I do not put a tag here, the comparison test will fail
+    static CheckerProgramPointTag Tag("MismatchedIteratorChecker",
+                                      "MismatchedIterator");
+    auto *N = C.generateNonFatalErrorNode(State, &Tag);
+    if (!N) {
+      return;
+    }
+    reportMismatchedBug("Iterator access mismatched.", Iter1, C, N);
+  }
+}
+
+void MismatchedIteratorChecker::handleBeginOrEnd(CheckerContext &C,
+                                                 const SVal &RetVal,
+                                                 const SVal &Cont) const {
+  const auto *ContReg = Cont.getAsRegion();
+  if (!ContReg)
+    return;
+
+  auto State = C.getState();
+  State = setIteratorContainer(State, RetVal, ContReg);
+  C.addTransition(State);
+}
+
+void MismatchedIteratorChecker::reportMismatchedBug(
+    const StringRef &Message, const SVal &Val, CheckerContext &C,
+    ExplodedNode *ErrNode) const {
+  auto R = llvm::make_unique<BugReport>(*MismatchedBugType, Message, ErrNode);
+  R->markInteresting(Val);
+  C.emitReport(std::move(R));
+}
+
+namespace {
+
+static bool isIteratorType(const QualType &Type) {
+  const auto *CRD = Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl();
+  return isIterator(CRD);
+}
+
+static bool isIterator(const CXXRecordDecl *CRD) {
+  if (!CRD)
+    return false;
+
+  const auto Name = CRD->getName();
+  if (!(Name.endswith_lower("iterator") || Name.endswith_lower("iter") ||
+        Name.endswith_lower("it")))
+    return false;
+
+  bool CopyC = false, CopyA = true, Dest = false, PreIncr = false,
+       PostIncr = false, Deref = false;
+  for (const auto *M : CRD->methods()) {
+    if (const auto *C = dyn_cast<CXXConstructorDecl>(M)) {
+      if (C->isCopyConstructor()) {
+        CopyC = !C->isDeleted() && C->getAccess() == AS_public;
+      }
+      continue;
+    }
+    if (const auto *D = dyn_cast<CXXDestructorDecl>(M)) {
+      Dest = !D->isDeleted();
+      continue;
+    }
+    if (M->isCopyAssignmentOperator()) {
+      CopyA = !M->isDeleted() && M->getAccess() == AS_public;
+      continue;
+    }
+    if (!M->isOverloadedOperator())
+      continue;
+    const auto OPK = M->getOverloadedOperator();
+    if (OPK == OO_PlusPlus) {
+      PreIncr = PreIncr || (M->getNumParams() == 0);
+      PostIncr = PostIncr || (M->getNumParams() == 1);
+      continue;
+    }
+    if (OPK == OO_Star) {
+      Deref = (M->getNumParams() == 0);
+      continue;
+    }
+  }
+
+  return CopyC && CopyA && Dest && PreIncr && PostIncr && Deref;
+}
+
+static bool isComparisonOperator(OverloadedOperatorKind OK) {
+  return OK == OO_EqualEqual || OK == OO_ExclaimEqual || OK == OO_Less ||
+         OK == OO_LessEqual || OK == OO_Greater || OK == OO_GreaterEqual;
+}
+
+static bool isBeginOrEndCall(const FunctionDecl *Func) {
+  const auto *IdInfo = Func->getIdentifier();
+  if (!IdInfo)
+    return false;
+  return IdInfo->getName().endswith_lower("begin") ||
+         IdInfo->getName().endswith_lower("end");
+}
+
+static 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";
+}
+
+static 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";
+}
+
+static 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";
+}
+
+static const MemRegion *const *getIteratorContainer(ProgramStateRef State,
+                                                    const SVal &Val) {
+  if (const auto Reg = Val.getAsRegion()) {
+    return State->get<IteratorRegionMap>(Reg);
+  } else if (const auto Sym = Val.getAsSymbol()) {
+    return State->get<IteratorSymbolMap>(Sym);
+  } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
+    return State->get<IteratorRegionMap>(LCVal->getRegion());
+  }
+  return nullptr;
+}
+
+static ProgramStateRef setIteratorContainer(ProgramStateRef State,
+                                            const SVal &Val,
+                                            const MemRegion *Cont) {
+  if (const auto Reg = Val.getAsRegion()) {
+    return State->set<IteratorRegionMap>(Reg, Cont);
+  } else if (const auto Sym = Val.getAsSymbol()) {
+    return State->set<IteratorSymbolMap>(Sym, Cont);
+  } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
+    return State->set<IteratorRegionMap>(LCVal->getRegion(), Cont);
+  }
+  return nullptr;
+}
+
+static ProgramStateRef removeIteratorContainer(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;
+}
+}
+
+void ento::registerMismatchedIteratorChecker(CheckerManager &Mgr) {
+  Mgr.registerChecker<MismatchedIteratorChecker>();
+}

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;
 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(const Ptr p): ptr(p) {}
+  __iterator(const iterator &rhs): ptr(rhs.base()) {}
 
   __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; }
   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; }
 
+  const Ptr& base() const { return ptr; }
 private:
   Ptr ptr;
 };
 
 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 <class T> class initializer_list;
+  
   template<typename T>
   class vector {
+    typedef T value_type;
+    typedef size_t size_type;
     typedef __iterator<T, T *, T &> iterator;
     typedef __iterator<T, const T *, const T &> const_iterator;
 
     T *_start;
     T *_finish;
     T *_end_of_storage;
   public:
     vector() : _start(0), _finish(0), _end_of_storage(0) {}
+    template <typename InputIterator>
+      vector(InputIterator first, InputIterator last);
     ~vector();
     
     size_t size() const {
       return size_t(_finish - _start);
     }
     
     void push_back();
     T 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);
+    
+    iterator erase(const_iterator position);
+    iterator erase(const_iterator first, const_iterator last);
+    
+    template <class... Args>
+      iterator emplace(const_iterator position, Args&&... args);
+    
+
     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); }
   };
   
   class exception {
   public:
     exception() throw();
     virtual ~exception() throw();
     virtual const char *what() const throw() {
       return 0;

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:217 {{Called C++ object pointer is null}}
 #endif
 }

test/Analysis/mismatched-iterator.cpp

+// RUN: %clang_cc1 -std=c++11 -analyze -analyzer-checker=core,cplusplus,alpha.cplusplus.MismatchedIterator -analyzer-eagerly-assume %s -verify
+
+#include "Inputs/system-header-simulator-cxx.h"
+
+void good_insert1(std::vector<int> &v, int n) {
+  v.insert(v.cbegin(), n); // no-warning
+}
+
+
+void good_insert2(std::vector<int> &v, int len, int n) {
+  v.insert(v.cbegin(), len, n); // no-warning
+}
+
+void good_insert3(std::vector<int> &v1, std::vector<int> &v2) {
+  v1.insert(v1.cbegin(), v2.cbegin(), v2.cend()); // no-warning
+}
+
+void good_insert4(std::vector<int> &v, int len, int n) {
+  v.insert(v.cbegin(), {n-1, n, n+1}); // no-warning
+}
+
+void good_insert_find(std::vector<int> &v, int n, int m) {
+  auto i = std::find(v.begin(), v.end(), n);
+  v.insert(i, m); // no-warning
+}
+
+void good_erase1(std::vector<int> &v) {
+  v.erase(v.cbegin()); // no-warning
+}
+
+void good_erase2(std::vector<int> &v) {
+  v.erase(v.cbegin(), v.cend()); // no-warning
+}
+
+void good_emplace(std::vector<int> &v, int n) {
+  v.emplace(v.cbegin(), n); // no-warning
+}
+
+void good_ctor(std::vector<int> &v) {
+  std::vector<int> new_v(v.begin(), v.end()); // no-warning
+}
+
+void good_find(std::vector<int> &v, int n) {
+  std::find(v.begin(), v.end(), n); // no-warning
+}
+
+void good_find_first_of(std::vector<int> &v1, std::vector<int> &v2) {
+  std::find_first_of(v1.begin(), v1.end(), v2.begin(), v2.end()); // no-warning
+}
+
+void good_comparison(std::vector<int> &v) {
+  if (v.begin() == v.end()) {} // no-warning
+}
+
+void bad_insert1(std::vector<int> &v1, std::vector<int> &v2, int n) {
+  v2.insert(v1.cbegin(), n); // expected-warning{{Iterator access mismatched}}
+}
+
+void bad_insert2(std::vector<int> &v1, std::vector<int> &v2, int len, int n) {
+  v2.insert(v1.cbegin(), len, n); // expected-warning{{Iterator access mismatched}}
+}
+
+void bad_insert3(std::vector<int> &v1, std::vector<int> &v2) {
+  v2.insert(v1.cbegin(), v2.cbegin(), v2.cend()); // expected-warning{{Iterator access mismatched}}
+  v1.insert(v1.cbegin(), v1.cbegin(), v2.cend()); // expected-warning{{Iterator access mismatched}}
+  v1.insert(v1.cbegin(), v2.cbegin(), v1.cend()); // expected-warning{{Iterator access mismatched}}
+}
+
+void bad_insert4(std::vector<int> &v1, std::vector<int> &v2, int len, int n) {
+  v2.insert(v1.cbegin(), {n-1, n, n+1}); // expected-warning{{Iterator access mismatched}}
+}
+
+void bad_erase1(std::vector<int> &v1, std::vector<int> &v2) {
+  v2.erase(v1.cbegin()); // expected-warning{{Iterator access mismatched}}
+}
+
+void bad_erase2(std::vector<int> &v1, std::vector<int> &v2) {
+  v2.erase(v2.cbegin(), v1.cend()); // expected-warning{{Iterator access mismatched}}
+  v2.erase(v1.cbegin(), v2.cend()); // expected-warning{{Iterator access mismatched}}
+  v2.erase(v1.cbegin(), v1.cend()); // expected-warning{{Iterator access mismatched}}
+}
+
+void bad_emplace(std::vector<int> &v1, std::vector<int> &v2, int n) {
+  v2.emplace(v1.cbegin(), n); // expected-warning{{Iterator access mismatched}}
+}
+
+void bad_ctor(std::vector<int> &v1, std::vector<int> &v2) {
+  std::vector<int> new_v(v1.begin(), v2.end()); // expected-warning{{Iterator access mismatched}}
+}
+
+void bad_find(std::vector<int> &v1, std::vector<int> &v2, int n) {
+  std::find(v1.begin(), v2.end(), n); // expected-warning{{Iterator access mismatched}}
+}
+
+void bad_find_first_of(std::vector<int> &v1, std::vector<int> &v2) {
+  std::find_first_of(v1.begin(), v2.end(), v2.begin(), v2.end()); // expected-warning{{Iterator access mismatched}}
+  std::find_first_of(v1.begin(), v1.end(), v2.begin(), v1.end()); // expected-warning{{Iterator access mismatched}}
+}
+
+void bad_comparison(std::vector<int> &v1, std::vector<int> &v2) {
+  if (v1.begin() != v2.end()) { // expected-warning{{Iterator access mismatched}}
+    *v1.begin();
+  }
+}
+
+void bad_insert_find(std::vector<int> &v1, std::vector<int> &v2, int n, int m) {
+  auto i = std::find(v1.begin(), v1.end(), n);
+  v2.insert(i, m); // expected-warning{{Iterator access mismatched}}
+}
+
+void good_overwrite(std::vector<int> &v1, std::vector<int> &v2, int n) {
+  auto i = v1.cbegin();
+  i = v2.cbegin();
+  v2.insert(i, n); // no-warning
+}
+
+void bad_overwrite(std::vector<int> &v1, std::vector<int> &v2, int n) {
+  auto i = v1.cbegin();
+  i = v2.cbegin();
+  v1.insert(i, n); // expected-warning{{Iterator access mismatched}}
+}
+
+template<typename Container, typename Iterator>
+bool is_end(Container cont, Iterator it) {
+  return it == cont.end();
+}
+
+void good_empty(std::vector<int> &v) {
+  is_end(v, v.begin()); // no-warning
+}
+
+void bad_empty(std::vector<int> &v1, std::vector<int> &v2) {
+  is_end(v1, v2.begin()); // expected-warning@125{{Iterator access mismatched}}
+}