[Analyzer] [NFC] Iterator Checkers - Separate iterator modeling and the actual checkers

[baloghadamsoftware]

Summary

A monolithic checker class is hard to maintain. This patch splits it up into a modelling part, the three checkers and a debug checker. The common functions are moved into a library.

[NoQ]

I love how this checker is pioneering in so many ways.

clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp

1307–1317

Maybe move this function to Iterator.cpp as well, and then move the definitions for iterator maps from Iterator.h to Iterator.cpp, which will allow you to use the usual REGISTER_MAP_WITH_PROGRAMSTATE macros, and additionally guarantee that all access to the maps goes through the accessor methods that you provide?

[baloghadamsoftware]

clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp

1307–1317

Hmm, I was trying hard to use these macros but failed so I reverted to the manual solution. I will retry now.

[Charusso]

clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp

1307–1317

Here is a how-to: https://reviews.llvm.org/D69726

You need to add the fully qualified names to the register macro because of the global scope. I hope it helps.

[baloghadamsoftware]

clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp

1307–1317

OK, I checked it now. If we want to put the maps into Iterator.cpp then we also have to move a couple of functions there which are only used by the modeling part: the internals of checkDeadSymbols() and checkLiveSymbols() must go there, although no other checker should use them. Also processIteratorPositions() iterates over these maps, thus it must also go there. Should I do it? Generally I like the current solution better, only functions used by multiple checker classes are in the library.

On the other hand I do not see why I should move assumeNoOverflow() to Iterator.cpp? This function is only used by the modeling part, and does not refer to the maps. You mean that we should ensure this constraint whenever setting the position for any iterator? This would mean that we should decompose every symblic expression and (re)assume this range on the symbolic part. Or we should replace setPosition() by at least two different functions (e.g. setAdvancedPosition() and setConjuredPosition()) but this means a total reqriting of the modeling.

I plan some refactoring but this first patch is meant to be a single separation of code.

[baloghadamsoftware]

clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp

1307–1317

@Charusso It does not help because the macros put the maps into a local namespace. If it is in a header, it means separate maps for every checker and the modeling which of course does not work.

1307–1317

@NoQ What is the decision? Should I move everything to the lib such as the body of checkDeadSymbols() and checkLiveSymbols() which I am reluctant because they belong only to the modeling, or leave it as it is now?

[NoQ]

I plan some refactoring but this first patch is meant to be a single separation of code.

Sounds great!

clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp

1307–1317

I think all the functions for manipulating the state trait (including dead symbol cleanup and escapes) should live in the modeling file. Like, it doesn't mean that checkDeadSymbols itself should necessarily live there, but in any case the file should provide a nice cleanup method that can be invoked from the real checkDeadSymbols.

This way you can encapsulate all the implementation details in the cpp file and only interact with it with fancy accessors.

I'm perfectly ok with delaying this work ^.^

clang/lib/StaticAnalyzer/Checkers/CMakeLists.txt

add_clang_library(clangStaticAnalyzerCheckers
   CheckSizeofPointer.cpp
   CheckerDocumentation.cpp
   ChrootChecker.cpp
   CloneChecker.cpp
   ConversionChecker.cpp
   CXXSelfAssignmentChecker.cpp
   DeadStoresChecker.cpp
   DebugCheckers.cpp
+  DebugIteratorModeling.cpp
   DeleteWithNonVirtualDtorChecker.cpp
   DereferenceChecker.cpp
   DirectIvarAssignment.cpp
   DivZeroChecker.cpp
   DynamicTypePropagation.cpp
   DynamicTypeChecker.cpp
   EnumCastOutOfRangeChecker.cpp
   ExprInspectionChecker.cpp
   FixedAddressChecker.cpp
   GCDAntipatternChecker.cpp
   GenericTaintChecker.cpp
   GTestChecker.cpp
   IdenticalExprChecker.cpp
   InnerPointerChecker.cpp
-  IteratorChecker.cpp
+  InvalidatedIteratorChecker.cpp
+  Iterator.cpp
+  IteratorModeling.cpp
+  IteratorRangeChecker.cpp
   IvarInvalidationChecker.cpp
   LLVMConventionsChecker.cpp
   LocalizationChecker.cpp
   MacOSKeychainAPIChecker.cpp
   MacOSXAPIChecker.cpp
   MallocChecker.cpp
   MallocOverflowSecurityChecker.cpp
   MallocSizeofChecker.cpp
+  MismatchedIteratorChecker.cpp
   MmapWriteExecChecker.cpp
   MIGChecker.cpp
   MoveChecker.cpp
   MPI-Checker/MPIBugReporter.cpp
   MPI-Checker/MPIChecker.cpp
   MPI-Checker/MPIFunctionClassifier.cpp
   NSAutoreleasePoolChecker.cpp
   NSErrorChecker.cpp

clang/lib/StaticAnalyzer/Checkers/DebugIteratorModeling.cpp

+//===-- DebugIteratorModeling.cpp ---------------------------------*- C++ -*--//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Defines a checker for debugging iterator modeling.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.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 "Iterator.h"
+
+using namespace clang;
+using namespace ento;
+using namespace iterator;
+
+namespace {
+
+class DebugIteratorModeling
+  : public Checker<eval::Call> {
+
+  std::unique_ptr<BugType> DebugMsgBugType;
+
+  template <typename Getter>
+  void analyzerContainerDataField(const CallExpr *CE, CheckerContext &C,
+                                  Getter get) const;
+  void analyzerContainerBegin(const CallExpr *CE, CheckerContext &C) const;
+  void analyzerContainerEnd(const CallExpr *CE, CheckerContext &C) const;
+  template <typename Getter>
+  void analyzerIteratorDataField(const CallExpr *CE, CheckerContext &C,
+                                 Getter get, SVal Default) const;
+  void analyzerIteratorPosition(const CallExpr *CE, CheckerContext &C) const;
+  void analyzerIteratorContainer(const CallExpr *CE, CheckerContext &C) const;
+  void analyzerIteratorValidity(const CallExpr *CE, CheckerContext &C) const;
+  ExplodedNode *reportDebugMsg(llvm::StringRef Msg, CheckerContext &C) const;
+
+  typedef void (DebugIteratorModeling::*FnCheck)(const CallExpr *,
+                                                 CheckerContext &) const;
+
+  CallDescriptionMap<FnCheck> Callbacks = {
+    {{0, "clang_analyzer_container_begin", 1},
+     &DebugIteratorModeling::analyzerContainerBegin},
+    {{0, "clang_analyzer_container_end", 1},
+     &DebugIteratorModeling::analyzerContainerEnd},
+    {{0, "clang_analyzer_iterator_position", 1},
+     &DebugIteratorModeling::analyzerIteratorPosition},
+    {{0, "clang_analyzer_iterator_container", 1},
+     &DebugIteratorModeling::analyzerIteratorContainer},
+    {{0, "clang_analyzer_iterator_validity", 1},
+     &DebugIteratorModeling::analyzerIteratorValidity},
+  };
+
+public:
+  DebugIteratorModeling();
+
+  bool evalCall(const CallEvent &Call, CheckerContext &C) const;
+};
+
+} //namespace
+
+DebugIteratorModeling::DebugIteratorModeling() {
+  DebugMsgBugType.reset(
+      new BugType(this, "Checking analyzer assumptions", "debug",
+                  /*SuppressOnSink=*/true));
+}
+
+bool DebugIteratorModeling::evalCall(const CallEvent &Call,
+                                     CheckerContext &C) const {
+  const auto *CE = dyn_cast_or_null<CallExpr>(Call.getOriginExpr());
+  if (!CE)
+    return false;
+
+  const FnCheck *Handler = Callbacks.lookup(Call);
+  if (!Handler)
+    return false;
+
+  (this->**Handler)(CE, C);
+  return true;
+}
+
+template <typename Getter>
+void DebugIteratorModeling::analyzerContainerDataField(const CallExpr *CE,
+                                                       CheckerContext &C,
+                                                       Getter get) const {
+  if (CE->getNumArgs() == 0) {
+    reportDebugMsg("Missing container argument", C);
+    return;
+  }
+
+  auto State = C.getState();
+  const MemRegion *Cont = C.getSVal(CE->getArg(0)).getAsRegion();
+  if (Cont) {
+    const auto *Data = getContainerData(State, Cont);
+    if (Data) {
+      SymbolRef Field = get(Data);
+      if (Field) {
+        State = State->BindExpr(CE, C.getLocationContext(),
+                                nonloc::SymbolVal(Field));
+        C.addTransition(State);
+        return;
+      }
+    }
+  }
+
+  auto &BVF = C.getSValBuilder().getBasicValueFactory();
+  State = State->BindExpr(CE, C.getLocationContext(),
+                   nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(0))));
+}
+
+void DebugIteratorModeling::analyzerContainerBegin(const CallExpr *CE,
+                                                   CheckerContext &C) const {
+  analyzerContainerDataField(CE, C, [](const ContainerData *D) {
+      return D->getBegin();
+    });
+}
+
+void DebugIteratorModeling::analyzerContainerEnd(const CallExpr *CE,
+                                                 CheckerContext &C) const {
+  analyzerContainerDataField(CE, C, [](const ContainerData *D) {
+      return D->getEnd();
+    });
+}
+
+template <typename Getter>
+void DebugIteratorModeling::analyzerIteratorDataField(const CallExpr *CE,
+                                                      CheckerContext &C,
+                                                      Getter get,
+                                                      SVal Default) const {
+  if (CE->getNumArgs() == 0) {
+    reportDebugMsg("Missing iterator argument", C);
+    return;
+  }
+
+  auto State = C.getState();
+  SVal V = C.getSVal(CE->getArg(0));
+  const auto *Pos = getIteratorPosition(State, V);
+  if (Pos) {
+    State = State->BindExpr(CE, C.getLocationContext(), get(Pos));
+  } else {
+    State = State->BindExpr(CE, C.getLocationContext(), Default);
+  }
+  C.addTransition(State);
+}
+
+void DebugIteratorModeling::analyzerIteratorPosition(const CallExpr *CE,
+                                                     CheckerContext &C) const {
+  auto &BVF = C.getSValBuilder().getBasicValueFactory();
+  analyzerIteratorDataField(CE, C, [](const IteratorPosition *P) {
+      return nonloc::SymbolVal(P->getOffset());
+    }, nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(0))));
+}
+
+void DebugIteratorModeling::analyzerIteratorContainer(const CallExpr *CE,
+                                                      CheckerContext &C) const {
+  auto &BVF = C.getSValBuilder().getBasicValueFactory();
+  analyzerIteratorDataField(CE, C, [](const IteratorPosition *P) {
+      return loc::MemRegionVal(P->getContainer());
+    }, loc::ConcreteInt(BVF.getValue(llvm::APSInt::get(0))));
+}
+
+void DebugIteratorModeling::analyzerIteratorValidity(const CallExpr *CE,
+                                                     CheckerContext &C) const {
+  auto &BVF = C.getSValBuilder().getBasicValueFactory();
+  analyzerIteratorDataField(CE, C, [&BVF](const IteratorPosition *P) {
+      return
+        nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get((P->isValid()))));
+    }, nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(0))));
+}
+
+ExplodedNode *DebugIteratorModeling::reportDebugMsg(llvm::StringRef Msg,
+                                                    CheckerContext &C) const {
+  ExplodedNode *N = C.generateNonFatalErrorNode();
+  if (!N)
+    return nullptr;
+
+  auto &BR = C.getBugReporter();
+  BR.emitReport(std::make_unique<PathSensitiveBugReport>(*DebugMsgBugType,
+                                                         Msg, N));
+  return N;
+}
+
+void ento::registerDebugIteratorModeling(CheckerManager &mgr) {
+  mgr.registerChecker<DebugIteratorModeling>();
+}
+
+bool ento::shouldRegisterDebugIteratorModeling(const LangOptions &LO) {
+  return true;
+}

clang/lib/StaticAnalyzer/Checkers/InvalidatedIteratorChecker.cpp

+//===-- InvalidatedIteratorChecker.cpp ----------------------------*- C++ -*--//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Defines a checker for access of invalidated iterators.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.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 "Iterator.h"
+
+using namespace clang;
+using namespace ento;
+using namespace iterator;
+
+namespace {
+
+class InvalidatedIteratorChecker
+  : public Checker<check::PreCall> {
+
+  std::unique_ptr<BugType> InvalidatedBugType;
+
+  void verifyAccess(CheckerContext &C, const SVal &Val) const;
+  void reportBug(const StringRef &Message, const SVal &Val,
+                 CheckerContext &C, ExplodedNode *ErrNode) const;
+public:
+  InvalidatedIteratorChecker();
+
+  void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
+
+};
+
+} //namespace
+
+InvalidatedIteratorChecker::InvalidatedIteratorChecker() {
+  InvalidatedBugType.reset(
+      new BugType(this, "Iterator invalidated", "Misuse of STL APIs"));
+}
+
+void InvalidatedIteratorChecker::checkPreCall(const CallEvent &Call,
+                                              CheckerContext &C) const {
+  // Check for access of invalidated position
+  const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
+  if (!Func)
+    return;
+
+  if (Func->isOverloadedOperator() &&
+      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));
+    }
+  }
+}
+
+void InvalidatedIteratorChecker::verifyAccess(CheckerContext &C, const SVal &Val) const {
+  auto State = C.getState();
+  const auto *Pos = getIteratorPosition(State, Val);
+  if (Pos && !Pos->isValid()) {
+    auto *N = C.generateErrorNode(State);
+    if (!N) {
+      return;
+    }
+    reportBug("Invalidated iterator accessed.", Val, C, N);
+  }
+}
+
+void InvalidatedIteratorChecker::reportBug(const StringRef &Message,
+                                           const SVal &Val, CheckerContext &C,
+                                           ExplodedNode *ErrNode) const {
+  auto R = std::make_unique<PathSensitiveBugReport>(*InvalidatedBugType,
+                                                    Message, ErrNode);
+  R->markInteresting(Val);
+  C.emitReport(std::move(R));
+}
+
+void ento::registerInvalidatedIteratorChecker(CheckerManager &mgr) {
+  mgr.registerChecker<InvalidatedIteratorChecker>();
+}
+
+bool ento::shouldRegisterInvalidatedIteratorChecker(const LangOptions &LO) {
+  return true;
+}

clang/lib/StaticAnalyzer/Checkers/Iterator.h

+//=== Iterator.h - Common functions for iterator checkers. ---------*- C++ -*-//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Defines common functions to be used by the itertor checkers .
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_LIB_STATICANALYZER_CHECKERS_ITERATOR_H
+#define LLVM_CLANG_LIB_STATICANALYZER_CHECKERS_ITERATOR_H
+
+#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h"
+
+namespace clang {
+namespace ento {
+namespace iterator {
+
+// 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, 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, true, Of);
+  }
+
+  IteratorPosition setTo(SymbolRef NewOf) const {
+    return IteratorPosition(Cont, Valid, NewOf);
+  }
+
+  IteratorPosition reAssign(const MemRegion *NewCont) const {
+    return IteratorPosition(NewCont, Valid, Offset);
+  }
+
+  bool operator==(const IteratorPosition &X) const {
+    return Cont == X.Cont && Valid == X.Valid && Offset == X.Offset;
+  }
+
+  bool operator!=(const IteratorPosition &X) const {
+    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);
+  }
+};
+
+// Structure to record the symbolic begin and end position of a container
+struct ContainerData {
+private:
+  const SymbolRef Begin, End;
+
+  ContainerData(SymbolRef B, SymbolRef E) : Begin(B), End(E) {}
+
+public:
+  static ContainerData fromBegin(SymbolRef B) {
+    return ContainerData(B, nullptr);
+  }
+
+  static ContainerData fromEnd(SymbolRef E) {
+    return ContainerData(nullptr, E);
+  }
+
+  SymbolRef getBegin() const { return Begin; }
+  SymbolRef getEnd() const { return End; }
+
+  ContainerData newBegin(SymbolRef B) const { return ContainerData(B, End); }
+
+  ContainerData newEnd(SymbolRef E) const { return ContainerData(Begin, E); }
+
+  bool operator==(const ContainerData &X) const {
+    return Begin == X.Begin && End == X.End;
+  }
+
+  bool operator!=(const ContainerData &X) const {
+    return Begin != X.Begin || End != X.End;
+  }
+
+  void Profile(llvm::FoldingSetNodeID &ID) const {
+    ID.Add(Begin);
+    ID.Add(End);
+  }
+};
+
+class IteratorSymbolMap {};
+class IteratorRegionMap {};
+class ContainerMap {};
+
+using IteratorSymbolMapTy = CLANG_ENTO_PROGRAMSTATE_MAP(SymbolRef, IteratorPosition);
+using IteratorRegionMapTy = CLANG_ENTO_PROGRAMSTATE_MAP(const MemRegion *, IteratorPosition);
+using ContainerMapTy = CLANG_ENTO_PROGRAMSTATE_MAP(const MemRegion *, ContainerData);
+
+} // namespace iterator
+
+template<>
+struct ProgramStateTrait<iterator::IteratorSymbolMap>
+  : public ProgramStatePartialTrait<iterator::IteratorSymbolMapTy> {
+  static void *GDMIndex() { static int Index; return &Index; }
+};
+
+template<>
+struct ProgramStateTrait<iterator::IteratorRegionMap>
+  : public ProgramStatePartialTrait<iterator::IteratorRegionMapTy> {
+  static void *GDMIndex() { static int Index; return &Index; }
+};
+
+template<>
+struct ProgramStateTrait<iterator::ContainerMap>
+  : public ProgramStatePartialTrait<iterator::ContainerMapTy> {
+  static void *GDMIndex() { static int Index; return &Index; }
+};
+
+namespace iterator {
+
+bool isIteratorType(const QualType &Type);
+bool isIterator(const CXXRecordDecl *CRD);
+bool isComparisonOperator(OverloadedOperatorKind OK);
+bool isInsertCall(const FunctionDecl *Func);
+bool isEraseCall(const FunctionDecl *Func);
+bool isEraseAfterCall(const FunctionDecl *Func);
+bool isEmplaceCall(const FunctionDecl *Func);
+bool isAccessOperator(OverloadedOperatorKind OK);
+bool isDereferenceOperator(OverloadedOperatorKind OK);
+bool isIncrementOperator(OverloadedOperatorKind OK);
+bool isDecrementOperator(OverloadedOperatorKind OK);
+bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK);
+const ContainerData *getContainerData(ProgramStateRef State,
+                                      const MemRegion *Cont);
+const IteratorPosition *getIteratorPosition(ProgramStateRef State,
+                                            const SVal &Val);
+ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val,
+                                    const IteratorPosition &Pos);
+ProgramStateRef advancePosition(ProgramStateRef State,
+                                const SVal &Iter,
+                                OverloadedOperatorKind Op,
+                                const SVal &Distance);
+bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
+             BinaryOperator::Opcode Opc);
+bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2,
+             BinaryOperator::Opcode Opc);
+
+} // namespace iterator
+} // namespace ento
+} // namespace clang
+
+#endif

clang/lib/StaticAnalyzer/Checkers/Iterator.cpp

+//=== Iterator.cpp - Common functions for iterator checkers. -------*- C++ -*-//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Defines common functions to be used by the itertor checkers .
+//
+//===----------------------------------------------------------------------===//
+
+#include "Iterator.h"
+
+namespace clang {
+namespace ento {
+namespace iterator {
+
+bool isIteratorType(const QualType &Type) {
+  if (Type->isPointerType())
+    return true;
+
+  const auto *CRD = Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl();
+  return isIterator(CRD);
+}
+
+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 HasCopyCtor = false, HasCopyAssign = true, HasDtor = false,
+       HasPreIncrOp = false, HasPostIncrOp = false, HasDerefOp = false;
+  for (const auto *Method : CRD->methods()) {
+    if (const auto *Ctor = dyn_cast<CXXConstructorDecl>(Method)) {
+      if (Ctor->isCopyConstructor()) {
+        HasCopyCtor = !Ctor->isDeleted() && Ctor->getAccess() == AS_public;
+      }
+      continue;
+    }
+    if (const auto *Dtor = dyn_cast<CXXDestructorDecl>(Method)) {
+      HasDtor = !Dtor->isDeleted() && Dtor->getAccess() == AS_public;
+      continue;
+    }
+    if (Method->isCopyAssignmentOperator()) {
+      HasCopyAssign = !Method->isDeleted() && Method->getAccess() == AS_public;
+      continue;
+    }
+    if (!Method->isOverloadedOperator())
+      continue;
+    const auto OPK = Method->getOverloadedOperator();
+    if (OPK == OO_PlusPlus) {
+      HasPreIncrOp = HasPreIncrOp || (Method->getNumParams() == 0);
+      HasPostIncrOp = HasPostIncrOp || (Method->getNumParams() == 1);
+      continue;
+    }
+    if (OPK == OO_Star) {
+      HasDerefOp = (Method->getNumParams() == 0);
+      continue;
+    }
+  }
+
+  return HasCopyCtor && HasCopyAssign && HasDtor && HasPreIncrOp &&
+         HasPostIncrOp && HasDerefOp;
+}
+
+bool isComparisonOperator(OverloadedOperatorKind OK) {
+  return OK == OO_EqualEqual || OK == OO_ExclaimEqual || OK == OO_Less ||
+         OK == OO_LessEqual || OK == OO_Greater || OK == OO_GreaterEqual;
+}
+
+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 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 isDecrementOperator(OverloadedOperatorKind OK) {
+  return OK == OO_MinusMinus;
+}
+
+bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK) {
+  return OK == OO_Plus || OK == OO_PlusEqual || OK == OO_Minus ||
+         OK == OO_MinusEqual;
+}
+
+const ContainerData *getContainerData(ProgramStateRef State,
+                                      const MemRegion *Cont) {
+  return State->get<ContainerMap>(Cont);
+}
+
+const IteratorPosition *getIteratorPosition(ProgramStateRef State,
+                                            const SVal &Val) {
+  if (auto Reg = Val.getAsRegion()) {
+    Reg = Reg->getMostDerivedObjectRegion();
+    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;
+}
+
+ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val,
+                                    const IteratorPosition &Pos) {
+  if (auto Reg = Val.getAsRegion()) {
+    Reg = Reg->getMostDerivedObjectRegion();
+    return State->set<IteratorRegionMap>(Reg, Pos);
+  } else if (const auto Sym = Val.getAsSymbol()) {
+    return State->set<IteratorSymbolMap>(Sym, Pos);
+  } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
+    return State->set<IteratorRegionMap>(LCVal->getRegion(), Pos);
+  }
+  return nullptr;
+}
+
+ProgramStateRef advancePosition(ProgramStateRef State, const SVal &Iter,
+                                OverloadedOperatorKind Op,
+                                const SVal &Distance) {
+  const auto *Pos = getIteratorPosition(State, Iter);
+  if (!Pos)
+    return nullptr;
+
+  auto &SymMgr = State->getStateManager().getSymbolManager();
+  auto &SVB = State->getStateManager().getSValBuilder();
+
+  assert ((Op == OO_Plus || Op == OO_PlusEqual ||
+           Op == OO_Minus || Op == OO_MinusEqual) &&
+          "Advance operator must be one of +, -, += and -=.");
+  auto BinOp = (Op == OO_Plus || Op == OO_PlusEqual) ? BO_Add : BO_Sub;
+  if (const auto IntDist = Distance.getAs<nonloc::ConcreteInt>()) {
+    // For concrete integers we can calculate the new position
+    const auto NewPos =
+      Pos->setTo(SVB.evalBinOp(State, BinOp,
+                               nonloc::SymbolVal(Pos->getOffset()),
+                               *IntDist, SymMgr.getType(Pos->getOffset()))
+                 .getAsSymbol());
+    return setIteratorPosition(State, Iter, NewPos);
+  }
+
+  return nullptr;
+}
+
+bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
+             BinaryOperator::Opcode Opc) {
+  return compare(State, nonloc::SymbolVal(Sym1), nonloc::SymbolVal(Sym2), Opc);
+}
+
+bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2,
+             BinaryOperator::Opcode Opc) {
+  auto &SVB = State->getStateManager().getSValBuilder();
+
+  const auto comparison =
+    SVB.evalBinOp(State, Opc, NL1, NL2, SVB.getConditionType());
+
+  assert(comparison.getAs<DefinedSVal>() &&
+    "Symbol comparison must be a `DefinedSVal`");
+
+  return !State->assume(comparison.castAs<DefinedSVal>(), false);
+}
+
+} // namespace iterator
+} // namespace ento
+} // namespace clang

clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp

-//===-- IteratorChecker.cpp ---------------------------------------*- C++ -*--//
+//===-- IteratorModeling.cpp --------------------------------------*- C++ -*--//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // Defines a checker for using iterators outside their range (past end). Usage

 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.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 "clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h"
 
+#include "Iterator.h"
+
 #include <utility>
 
 using namespace clang;
 using namespace ento;
+using namespace iterator;
 
 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, 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, true, Of);
-  }
-
-  IteratorPosition setTo(SymbolRef NewOf) const {
-    return IteratorPosition(Cont, Valid, NewOf);
-  }
-
-  IteratorPosition reAssign(const MemRegion *NewCont) const {
-    return IteratorPosition(NewCont, Valid, Offset);
-  }
-
-  bool operator==(const IteratorPosition &X) const {
-    return Cont == X.Cont && Valid == X.Valid && Offset == X.Offset;
-  }
-
-  bool operator!=(const IteratorPosition &X) const {
-    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);
-  }
-};
-
-// Structure to record the symbolic begin and end position of a container
-struct ContainerData {
-private:
-  const SymbolRef Begin, End;
-
-  ContainerData(SymbolRef B, SymbolRef E) : Begin(B), End(E) {}
-
-public:
-  static ContainerData fromBegin(SymbolRef B) {
-    return ContainerData(B, nullptr);
-  }
-
-  static ContainerData fromEnd(SymbolRef E) {
-    return ContainerData(nullptr, E);
-  }
-
-  SymbolRef getBegin() const { return Begin; }
-  SymbolRef getEnd() const { return End; }
-
-  ContainerData newBegin(SymbolRef B) const { return ContainerData(B, End); }
-
-  ContainerData newEnd(SymbolRef E) const { return ContainerData(Begin, E); }
-
-  bool operator==(const ContainerData &X) const {
-    return Begin == X.Begin && End == X.End;
-  }
-
-  bool operator!=(const ContainerData &X) const {
-    return Begin != X.Begin || End != X.End;
-  }
-
-  void Profile(llvm::FoldingSetNodeID &ID) const {
-    ID.Add(Begin);
-    ID.Add(End);
-  }
-};
-
-class IteratorChecker
-    : public Checker<check::PreCall, check::PostCall,
-                     check::PostStmt<MaterializeTemporaryExpr>, check::Bind,
-                     check::LiveSymbols, check::DeadSymbols, eval::Call> {
-
-  std::unique_ptr<BugType> OutOfRangeBugType;
-  std::unique_ptr<BugType> MismatchedBugType;
-  std::unique_ptr<BugType> InvalidatedBugType;
-  std::unique_ptr<BugType> DebugMsgBugType;
+class IteratorModeling
+    : public Checker<check::PostCall, check::PostStmt<MaterializeTemporaryExpr>,
+                     check::Bind, check::LiveSymbols, check::DeadSymbols> {
 
   void handleComparison(CheckerContext &C, const Expr *CE, const SVal &RetVal,
                         const SVal &LVal, const SVal &RVal,
                         OverloadedOperatorKind Op) const;
   void processComparison(CheckerContext &C, ProgramStateRef State,
                          SymbolRef Sym1, SymbolRef Sym2, const SVal &RetVal,
                          OverloadedOperatorKind Op) const;
-  void 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 handleRandomIncrOrDecr(CheckerContext &C, const Expr *CE,
+                              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 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 verifyIncrement(CheckerContext &C, const SVal &Iter) const;
-  void verifyDecrement(CheckerContext &C, const SVal &Iter) const;
-  void verifyRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op,
-                              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;
-  IteratorPosition advancePosition(CheckerContext &C, OverloadedOperatorKind Op,
-                                   const IteratorPosition &Pos,
-                                   const SVal &Distance) 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;
-  void reportMismatchedBug(const StringRef &Message, const SVal &Val,
-                           const MemRegion *Reg, CheckerContext &C,
-                           ExplodedNode *ErrNode) const;
-  void reportInvalidatedBug(const StringRef &Message, const SVal &Val,
-                            CheckerContext &C, ExplodedNode *ErrNode) const;
-  template <typename Getter>
-  void analyzerContainerDataField(const CallExpr *CE, CheckerContext &C,
-                                  Getter get) const;
-  void analyzerContainerBegin(const CallExpr *CE, CheckerContext &C) const;
-  void analyzerContainerEnd(const CallExpr *CE, CheckerContext &C) const;
-  template <typename Getter>
-  void analyzerIteratorDataField(const CallExpr *CE, CheckerContext &C,
-                                 Getter get, SVal Default) const;
-  void analyzerIteratorPosition(const CallExpr *CE, CheckerContext &C) const;
-  void analyzerIteratorContainer(const CallExpr *CE, CheckerContext &C) const;
-  void analyzerIteratorValidity(const CallExpr *CE, CheckerContext &C) const;
-  ExplodedNode *reportDebugMsg(llvm::StringRef Msg, CheckerContext &C) const;
-
-  typedef void (IteratorChecker::*FnCheck)(const CallExpr *,
-                                           CheckerContext &) const;
-
-  CallDescriptionMap<FnCheck> Callbacks = {
-    {{0, "clang_analyzer_container_begin", 1},
-     &IteratorChecker::analyzerContainerBegin},
-    {{0, "clang_analyzer_container_end", 1},
-     &IteratorChecker::analyzerContainerEnd},
-    {{0, "clang_analyzer_iterator_position", 1},
-     &IteratorChecker::analyzerIteratorPosition},
-    {{0, "clang_analyzer_iterator_container", 1},
-     &IteratorChecker::analyzerIteratorContainer},
-    {{0, "clang_analyzer_iterator_validity", 1},
-     &IteratorChecker::analyzerIteratorValidity},
-  };
-  
 public:
-  IteratorChecker();
-
-  enum CheckKind {
-    CK_IteratorRangeChecker,
-    CK_MismatchedIteratorChecker,
-    CK_InvalidatedIteratorChecker,
-    CK_DebugIteratorModeling,
-    CK_NumCheckKinds
-  };
-
-  DefaultBool ChecksEnabled[CK_NumCheckKinds];
-  CheckerNameRef CheckNames[CK_NumCheckKinds];
+  IteratorModeling() {}
 
-  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;
-  bool evalCall(const CallEvent &Call, CheckerContext &C) 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)
-
-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);
 bool frontModifiable(ProgramStateRef State, const MemRegion *Reg);
 bool backModifiable(ProgramStateRef State, const MemRegion *Reg);
 SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont);
 SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont);
 ProgramStateRef createContainerBegin(ProgramStateRef State,
                                      const MemRegion *Cont, const Expr *E,
                                      QualType T, const LocationContext *LCtx,
                                      unsigned BlockCount);
 ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont,
                                    const Expr *E, QualType T,
                                    const LocationContext *LCtx,
                                    unsigned BlockCount);
-const IteratorPosition *getIteratorPosition(ProgramStateRef State,
-                                            const SVal &Val);
-ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val,
-                                    const IteratorPosition &Pos);
+ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont,
+                                 const ContainerData &CData);
 ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val);
 ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym,
                                  long Scale);
 ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State,
                                                const MemRegion *Cont);
 ProgramStateRef
 invalidateAllIteratorPositionsExcept(ProgramStateRef State,
                                      const MemRegion *Cont, SymbolRef Offset,
ProgramStateRef reassignAllIteratorPositionsUnless(ProgramStateRef State,
                                                    const MemRegion *NewCont,
                                                    SymbolRef Offset,
                                                    BinaryOperator::Opcode Opc);
 ProgramStateRef rebaseSymbolInIteratorPositionsIf(
     ProgramStateRef State, SValBuilder &SVB, SymbolRef OldSym,
     SymbolRef NewSym, SymbolRef CondSym, BinaryOperator::Opcode Opc);
 ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1,
                               SymbolRef Sym2, bool Equal);
-const ContainerData *getContainerData(ProgramStateRef State,
-                                      const MemRegion *Cont);
-ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont,
-                                 const ContainerData &CData);
+SymbolRef rebaseSymbol(ProgramStateRef State, SValBuilder &SVB, SymbolRef Expr,
+                        SymbolRef OldSym, SymbolRef NewSym);
 bool hasLiveIterators(ProgramStateRef State, const MemRegion *Cont);
 bool isBoundThroughLazyCompoundVal(const Environment &Env,
                                    const MemRegion *Reg);
-bool isPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos);
-bool isAheadOfRange(ProgramStateRef State, const IteratorPosition &Pos);
-bool isBehindPastTheEnd(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"));
-  MismatchedBugType.reset(
-      new BugType(this, "Iterator(s) mismatched", "Misuse of STL APIs",
-                  /*SuppressOnSink=*/true));
-  InvalidatedBugType.reset(
-      new BugType(this, "Iterator invalidated", "Misuse of STL APIs"));
-  DebugMsgBugType.reset(
-      new BugType(this, "Checking analyzer assumptions", "debug",
-                  /*SuppressOnSink=*/true));
-}
-
-void IteratorChecker::checkPreCall(const CallEvent &Call,
-                                   CheckerContext &C) const {
-  // 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]) {
-      if (isIncrementOperator(Func->getOverloadedOperator())) {
-        // Check for out-of-range incrementions
-        if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
-          verifyIncrement(C, InstCall->getCXXThisVal());
-        } else {
-          if (Call.getNumArgs() >= 1) {
-            verifyIncrement(C, Call.getArgSVal(0));
-          }
-        }
-      } else if (isDecrementOperator(Func->getOverloadedOperator())) {
-        // Check for out-of-range decrementions
-        if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
-          verifyDecrement(C, InstCall->getCXXThisVal());
-        } else {
-          if (Call.getNumArgs() >= 1) {
-            verifyDecrement(C, Call.getArgSVal(0));
-          }
-        }
-      } else if (isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) {
-        if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
-          // Check for out-of-range incrementions and decrementions
-          if (Call.getNumArgs() >= 1 &&
-              Call.getArgExpr(0)->getType()->isIntegralOrEnumerationType()) {
-            verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(),
-                                   InstCall->getCXXThisVal(),
-                                   Call.getArgSVal(0));
-          }
-        } else {
-          if (Call.getNumArgs() >= 2 &&
-              Call.getArgExpr(1)->getType()->isIntegralOrEnumerationType()) {
-            verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(),
-                                   Call.getArgSVal(0), Call.getArgSVal(1));
-          }
-        }
-      } else if (isDereferenceOperator(Func->getOverloadedOperator())) {
-        // Check for dereference of out-of-range iterators
-        if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
-          verifyDereference(C, InstCall->getCXXThisVal());
-        } else {
-          verifyDereference(C, Call.getArgSVal(0));
-        }
-      }
-    } else if (ChecksEnabled[CK_MismatchedIteratorChecker] &&
-               isComparisonOperator(Func->getOverloadedOperator())) {
-      // Check for comparisons of iterators of different containers
-      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)) {
-    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 (Ctr->getParamDecl(0)->getName() != "first" ||
-        Ctr->getParamDecl(1)->getName() != "last")
-      return;
-
-    if (!isIteratorType(Call.getArgExpr(0)->getType()) ||
-        !isIteratorType(Call.getArgExpr(1)->getType()))
-      return;
-
-    verifyMatch(C, Call.getArgSVal(0), Call.getArgSVal(1));
-  } else {
-    // 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.
-    //
-    // Example:
-    // template<typename I1, typename I2>
-    // void f(I1 first1, I1 last1, I2 first2, I2 last2);
-    // 
-    // In this case the first two arguments to f() must be iterators must belong
-    // to the same container and the last to also to the same container but
-    // not necessarily to the same as the first two.
-
-    if (!ChecksEnabled[CK_MismatchedIteratorChecker])
-      return;
-
-    const auto *Templ = Func->getPrimaryTemplate();
-    if (!Templ)
-      return;
-
-    const auto *TParams = Templ->getTemplateParameters();
-    const auto *TArgs = Func->getTemplateSpecializationArgs();
-
-    // Iterate over all the template parameters
-    for (size_t I = 0; I < TParams->size(); ++I) {
-      const auto *TPDecl = dyn_cast<TemplateTypeParmDecl>(TParams->getParam(I));
-      if (!TPDecl)
-        continue;
-
-      if (TPDecl->isParameterPack())
-        continue;
-
-      const auto TAType = TArgs->get(I).getAsType();
-      if (!isIteratorType(TAType))
-        continue;
-
-      SVal LHS = UndefinedVal();
-
-      // For every template parameter which is an iterator type in the
-      // instantiation look for all functions' parameters' type by it and
-      // check whether they belong to the same container
-      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));
-        }
-      }
-    }
-  }
-}
+} // namespace
 
-void IteratorChecker::checkPostCall(const CallEvent &Call,
+void IteratorModeling::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 (isAssignmentOperator(Op)) {
if (isAssignmentOperator(Op)) {
                          InstCall->getCXXThisVal(), Call.getArgSVal(0), Op);
         return;
       }
 
       handleComparison(C, OrigExpr, Call.getReturnValue(), Call.getArgSVal(0),
                          Call.getArgSVal(1), Op);
       return;
     } else if (isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) {
+      const auto *OrigExpr = Call.getOriginExpr();
+      if (!OrigExpr)
+        return;
+
       if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
         if (Call.getNumArgs() >= 1 &&
               Call.getArgExpr(0)->getType()->isIntegralOrEnumerationType()) {
-          handleRandomIncrOrDecr(C, Func->getOverloadedOperator(),
+          handleRandomIncrOrDecr(C, OrigExpr, Func->getOverloadedOperator(),
                                  Call.getReturnValue(),
                                  InstCall->getCXXThisVal(), Call.getArgSVal(0));
           return;
         }
       } else {
         if (Call.getNumArgs() >= 2 &&
               Call.getArgExpr(1)->getType()->isIntegralOrEnumerationType()) {
-          handleRandomIncrOrDecr(C, Func->getOverloadedOperator(),
+          handleRandomIncrOrDecr(C, OrigExpr, Func->getOverloadedOperator(),
                                  Call.getReturnValue(), Call.getArgSVal(0),
                                  Call.getArgSVal(1));
           return;
         }
       }
     } else if (isIncrementOperator(Func->getOverloadedOperator())) {
       if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
         handleIncrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(),
for (unsigned i = 0; i < Call.getNumArgs(); ++i) {
                             Pos->getContainer());
           return;
         }
       }
     }
   }
 }
 
-void IteratorChecker::checkBind(SVal Loc, SVal Val, const Stmt *S,
+void IteratorModeling::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,
+void IteratorModeling::checkPostStmt(const MaterializeTemporaryExpr *MTE,
                                      CheckerContext &C) const {
   /* Transfer iterator state to temporary objects */
   auto State = C.getState();
   const auto *Pos = getIteratorPosition(State, C.getSVal(MTE->getSubExpr()));
   if (!Pos)
     return;
   State = setIteratorPosition(State, C.getSVal(MTE), *Pos);
   C.addTransition(State);
 }
 
-void IteratorChecker::checkLiveSymbols(ProgramStateRef State,
+void IteratorModeling::checkLiveSymbols(ProgramStateRef State,
                                         SymbolReaper &SR) const {
   // Keep symbolic expressions of iterator positions, container begins and ends
   // alive
   auto RegionMap = State->get<IteratorRegionMap>();
   for (const auto Reg : RegionMap) {
     const auto Offset = Reg.second.getOffset();
     for (auto i = Offset->symbol_begin(); i != Offset->symbol_end(); ++i)
       if (isa<SymbolData>(*i))
         SR.markLive(*i);
for (const auto Cont : ContMap) {
     if (CData.getEnd()) {
       SR.markLive(CData.getEnd());
       if(const auto *SIE = dyn_cast<SymIntExpr>(CData.getEnd()))
         SR.markLive(SIE->getLHS());
     }
   }
 }
 
-void IteratorChecker::checkDeadSymbols(SymbolReaper &SR,
+void IteratorModeling::checkDeadSymbols(SymbolReaper &SR,
                                         CheckerContext &C) const {
   // Cleanup
   auto State = C.getState();
 
   auto RegionMap = State->get<IteratorRegionMap>();
   for (const auto Reg : RegionMap) {
     if (!SR.isLiveRegion(Reg.first)) {
       // The region behind the `LazyCompoundVal` is often cleaned up before
       // the `LazyCompoundVal` itself. If there are iterator positions keyed
if (!SR.isLiveRegion(Cont.first)) {
         State = State->remove<ContainerMap>(Cont.first);
       }
     }
   }
 
   C.addTransition(State);
 }
 
-void IteratorChecker::handleComparison(CheckerContext &C, const Expr *CE,
+void IteratorModeling::handleComparison(CheckerContext &C, const Expr *CE,
                                         const SVal &RetVal, const SVal &LVal,
                                         const SVal &RVal,
                                         OverloadedOperatorKind Op) const {
   // Record the operands and the operator of the comparison for the next
   // evalAssume, if the result is a symbolic expression. If it is a concrete
   // value (only one branch is possible), then transfer the state between
   // the operands according to the operator and the result
    auto State = C.getState();
   const auto *LPos = getIteratorPosition(State, LVal);
   const auto *RPos = getIteratorPosition(State, RVal);
   const MemRegion *Cont = nullptr;
if (!LPos) {
     State = setIteratorPosition(State, RVal,
                                 IteratorPosition::getPosition(Cont, Sym));
     RPos = getIteratorPosition(State, RVal);
   }
 
   processComparison(C, State, LPos->getOffset(), RPos->getOffset(), RetVal, Op);
 }
 
-void IteratorChecker::processComparison(CheckerContext &C,
+void IteratorModeling::processComparison(CheckerContext &C,
                                          ProgramStateRef State, SymbolRef Sym1,
                                          SymbolRef Sym2, const SVal &RetVal,
                                          OverloadedOperatorKind Op) const {
   if (const auto TruthVal = RetVal.getAs<nonloc::ConcreteInt>()) {
     if ((State = relateSymbols(State, Sym1, Sym2,
                               (Op == OO_EqualEqual) ==
                                (TruthVal->getValue() != 0)))) {
       C.addTransition(State);
     } else {
       C.generateSink(State, C.getPredecessor());
     }
void IteratorModeling::processComparison(CheckerContext &C,
   }
   
   if (auto StateFalse = relateSymbols(State, Sym1, Sym2, Op != OO_EqualEqual)) {
     StateFalse = StateFalse->assume(*ConditionVal, false);
     C.addTransition(StateFalse);
   }
 }
 
-void IteratorChecker::verifyDereference(CheckerContext &C,
-                                        const SVal &Val) const {
-  auto State = C.getState();
-  const auto *Pos = getIteratorPosition(State, Val);
-  if (Pos && isPastTheEnd(State, *Pos)) {
-    auto *N = C.generateErrorNode(State);
-    if (!N)
-      return;
-    reportOutOfRangeBug("Past-the-end iterator dereferenced.", Val, C, N);
-    return;
-  }
-}
-
-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.generateErrorNode(State);
-    if (!N) {
-      return;
-    }
-    reportInvalidatedBug("Invalidated iterator accessed.", Val, C, N);
-  }
-}
-
-void IteratorChecker::handleIncrement(CheckerContext &C, const SVal &RetVal,
+void IteratorModeling::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();
+  auto &BVF = C.getSymbolManager().getBasicVals();
+
   const auto *Pos = getIteratorPosition(State, Iter);
-  if (Pos) {
-    auto &SymMgr = C.getSymbolManager();
-    auto &BVF = SymMgr.getBasicVals();
-    const auto NewPos =
-      advancePosition(C, OO_Plus, *Pos,
+  if (!Pos)
+    return;
+
+  auto NewState =
+    advancePosition(State, Iter, OO_Plus,
                     nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
-    State = setIteratorPosition(State, Iter, NewPos);
-    State = setIteratorPosition(State, RetVal, Postfix ? *Pos : NewPos);
-    C.addTransition(State);
-  }
-}
+  assert(NewState &&
+         "Advancing position by concrete int should always be successful");
+
+  const auto *NewPos = getIteratorPosition(NewState, Iter);
+  assert(NewPos &&
+         "Iterator should have position after successful advancement");
+
+  State = setIteratorPosition(State, Iter, *NewPos);
+  State = setIteratorPosition(State, RetVal, Postfix ? *Pos : *NewPos);
 
-void IteratorChecker::handleDecrement(CheckerContext &C, const SVal &RetVal,
+void IteratorModeling::handleDecrement(CheckerContext &C, const SVal &RetVal,
                                        const SVal &Iter, bool Postfix) const {
   // Decrement the symbolic expressions which represents the position of the
   // iterator
   auto State = C.getState();
+  auto &BVF = C.getSymbolManager().getBasicVals();
+
   const auto *Pos = getIteratorPosition(State, Iter);
-  if (Pos) {
-    auto &SymMgr = C.getSymbolManager();
-    auto &BVF = SymMgr.getBasicVals();
-    const auto NewPos =
-      advancePosition(C, OO_Minus, *Pos,
+  if (!Pos)
+    return;
+
+  auto NewState =
+    advancePosition(State, Iter, OO_Minus,
                     nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
-    State = setIteratorPosition(State, Iter, NewPos);
-    State = setIteratorPosition(State, RetVal, Postfix ? *Pos : NewPos);
-    C.addTransition(State);
-  }
-}
+  assert(NewState &&
+         "Advancing position by concrete int should always be successful");
+
+  const auto *NewPos = getIteratorPosition(NewState, Iter);
+  assert(NewPos &&
+         "Iterator should have position after successful advancement");
+
+  State = setIteratorPosition(State, Iter, *NewPos);
+  State = setIteratorPosition(State, RetVal, Postfix ? *Pos : *NewPos);
 
-void IteratorChecker::handleRandomIncrOrDecr(CheckerContext &C,
+void IteratorModeling::handleRandomIncrOrDecr(CheckerContext &C,
+                                              const Expr *CE,
                                               OverloadedOperatorKind Op,
                                               const SVal &RetVal,
                                               const SVal &LHS,
                                               const SVal &RHS) const {
   // Increment or decrement the symbolic expressions which represents the
   // position of the iterator
   auto State = C.getState();
+
   const auto *Pos = getIteratorPosition(State, LHS);
   if (!Pos)
     return;
 
   const auto *value = &RHS;
   if (auto loc = RHS.getAs<Loc>()) {
     const auto val = State->getRawSVal(*loc);
     value = &val;
   }
 
   auto &TgtVal = (Op == OO_PlusEqual || Op == OO_MinusEqual) ? LHS : RetVal;
-  State =
-      setIteratorPosition(State, TgtVal, advancePosition(C, Op, *Pos, *value));
-  C.addTransition(State);
-}
-
-void IteratorChecker::verifyIncrement(CheckerContext &C,
-                                      const SVal &Iter) const {
-  auto &BVF = C.getSValBuilder().getBasicValueFactory();
-  verifyRandomIncrOrDecr(C, OO_Plus, Iter,
-                     nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
-}
-
-void IteratorChecker::verifyDecrement(CheckerContext &C,
-                                      const SVal &Iter) const {
-  auto &BVF = C.getSValBuilder().getBasicValueFactory();
-  verifyRandomIncrOrDecr(C, OO_Minus, Iter,
-                     nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
-}
-
-void IteratorChecker::verifyRandomIncrOrDecr(CheckerContext &C,
-                                             OverloadedOperatorKind Op,
-                                             const SVal &LHS,
-                                             const SVal &RHS) const {
-  auto State = C.getState();
-
-  // If the iterator is initially inside its range, then the operation is valid
-  const auto *Pos = getIteratorPosition(State, LHS);
-  if (!Pos)
-    return;
-
-  auto Value = RHS;
-  if (auto ValAsLoc = RHS.getAs<Loc>()) {
-    Value = State->getRawSVal(*ValAsLoc);
-  }
-
-  if (Value.isUnknown())
-    return;
-
-  // Incremention or decremention by 0 is never a bug.
-  if (isZero(State, Value.castAs<NonLoc>()))
-    return;
-
-  // The result may be the past-end iterator of the container, but any other
-  // out of range position is undefined behaviour
-  if (isAheadOfRange(State, advancePosition(C, Op, *Pos, Value))) {
-    auto *N = C.generateErrorNode(State);
-    if (!N)
-      return;
-    reportOutOfRangeBug("Iterator decremented ahead of its valid range.", LHS,
-                        C, N);
-  }
-  if (isBehindPastTheEnd(State, advancePosition(C, Op, *Pos, Value))) {
-    auto *N = C.generateErrorNode(State);
-    if (!N)
-      return;
-    reportOutOfRangeBug("Iterator incremented behind the past-the-end "
-                        "iterator.", 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
-  Cont = Cont->getMostDerivedObjectRegion();
-
-  if (const auto *ContSym = Cont->getSymbolicBase()) {
-    if (isa<SymbolConjured>(ContSym->getSymbol()))
-      return;
-  }
-
-  auto State = C.getState();
-  const auto *Pos = getIteratorPosition(State, Iter);
-  if (!Pos)
-    return;
-
-  const auto *IterCont = Pos->getContainer();
-
-  // Skip symbolic regions based on conjured symbols. Two conjured symbols
-  // may or may not be the same. For example, the same function can return
-  // the same or a different container but we get different conjured symbols
-  // for each call. This may cause false positives so omit them from the check.
-  if (const auto *ContSym = IterCont->getSymbolicBase()) {
-    if (isa<SymbolConjured>(ContSym->getSymbol()))
-      return;
-  }
-
-  if (IterCont != 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);
-  if (!Pos1)
-    return;
-
-  const auto *IterCont1 = Pos1->getContainer();
-
-  // Skip symbolic regions based on conjured symbols. Two conjured symbols
-  // may or may not be the same. For example, the same function can return
-  // the same or a different container but we get different conjured symbols
-  // for each call. This may cause false positives so omit them from the check.
-  if (const auto *ContSym = IterCont1->getSymbolicBase()) {
-    if (isa<SymbolConjured>(ContSym->getSymbol()))
-      return;
-  }
+  auto NewState =
+    advancePosition(State, LHS, Op, *value);
+  if (NewState) {
+    const auto *NewPos = getIteratorPosition(NewState, LHS);
+    assert(NewPos &&
+           "Iterator should have position after successful advancement");
 
-  const auto *Pos2 = getIteratorPosition(State, Iter2);
-  if (!Pos2)
-    return;
-
-  const auto *IterCont2 = Pos2->getContainer();
-  if (const auto *ContSym = IterCont2->getSymbolicBase()) {
-    if (isa<SymbolConjured>(ContSym->getSymbol()))
-      return;
-  }
-
-  if (IterCont1 != IterCont2) {
-    auto *N = C.generateNonFatalErrorNode(State);
-    if (!N)
-      return;
-    reportMismatchedBug("Iterators of different containers used where the "
-                        "same container is expected.", Iter1, Iter2, C, N);
+    State = setIteratorPosition(NewState, TgtVal, *NewPos);
+    C.addTransition(State);
+  } else {
+    assignToContainer(C, CE, TgtVal, Pos->getContainer());
   }
 }
 
-void IteratorChecker::handleBegin(CheckerContext &C, const Expr *CE,
+void IteratorModeling::handleBegin(CheckerContext &C, const Expr *CE,
                                    const SVal &RetVal, const SVal &Cont) const {
   const auto *ContReg = Cont.getAsRegion();
   if (!ContReg)
     return;
 
   ContReg = ContReg->getMostDerivedObjectRegion();
 
   // If the container already has a begin symbol then use it. Otherwise first
   // create a new one.
   auto State = C.getState();
   auto BeginSym = getContainerBegin(State, ContReg);
   if (!BeginSym) {
     State = createContainerBegin(State, ContReg, CE, C.getASTContext().LongTy,
                                  C.getLocationContext(), C.blockCount());
     BeginSym = getContainerBegin(State, ContReg);
   }
   State = setIteratorPosition(State, RetVal,
                               IteratorPosition::getPosition(ContReg, BeginSym));
   C.addTransition(State);
 }
 
-void IteratorChecker::handleEnd(CheckerContext &C, const Expr *CE,
+void IteratorModeling::handleEnd(CheckerContext &C, const Expr *CE,
                                  const SVal &RetVal, const SVal &Cont) const {
   const auto *ContReg = Cont.getAsRegion();
   if (!ContReg)
     return;
 
   ContReg = ContReg->getMostDerivedObjectRegion();
 
   // If the container already has an end symbol then use it. Otherwise first
   // create a new one.
   auto State = C.getState();
   auto EndSym = getContainerEnd(State, ContReg);
   if (!EndSym) {
     State = createContainerEnd(State, ContReg, CE, C.getASTContext().LongTy,
                                C.getLocationContext(), C.blockCount());
     EndSym = getContainerEnd(State, ContReg);
   }
   State = setIteratorPosition(State, RetVal,
                               IteratorPosition::getPosition(ContReg, EndSym));
   C.addTransition(State);
 }
 
-void IteratorChecker::assignToContainer(CheckerContext &C, const Expr *CE,
+void IteratorModeling::assignToContainer(CheckerContext &C, const Expr *CE,
                                          const SVal &RetVal,
                                          const MemRegion *Cont) const {
   Cont = Cont->getMostDerivedObjectRegion();
 
   auto State = C.getState();
   auto &SymMgr = C.getSymbolManager();
   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,
+void IteratorModeling::handleAssign(CheckerContext &C, const SVal &Cont,
                                     const Expr *CE, const SVal &OldCont) const {
   const auto *ContReg = Cont.getAsRegion();
   if (!ContReg)
     return;
 
   ContReg = ContReg->getMostDerivedObjectRegion();
 
   // Assignment of a new value to a container always invalidates all its
   // iterators
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 {
+void IteratorModeling::handleClear(CheckerContext &C, const SVal &Cont) const {
   const auto *ContReg = Cont.getAsRegion();
   if (!ContReg)
     return;
 
   ContReg = ContReg->getMostDerivedObjectRegion();
 
   // The clear() operation invalidates all the iterators, except the past-end
   // iterators of list-like containers
if (CData) {
         return;
       }
     }
   }
   State = invalidateAllIteratorPositions(State, ContReg);
   C.addTransition(State);
 }
 
-void IteratorChecker::handlePushBack(CheckerContext &C,
+void IteratorModeling::handlePushBack(CheckerContext &C,
                                       const SVal &Cont) const {
   const auto *ContReg = Cont.getAsRegion();
   if (!ContReg)
     return;
 
   ContReg = ContReg->getMostDerivedObjectRegion();
 
   // For deque-like containers invalidate all iterator positions
   auto State = C.getState();
const auto newEndSym =
                     nonloc::SymbolVal(EndSym),
                     nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
                     SymMgr.getType(EndSym)).getAsSymbol();
     State = setContainerData(State, ContReg, CData->newEnd(newEndSym));
   }
   C.addTransition(State);
 }
 
-void IteratorChecker::handlePopBack(CheckerContext &C, const SVal &Cont) const {
+void IteratorModeling::handlePopBack(CheckerContext &C,
+                                     const SVal &Cont) const {
   const auto *ContReg = Cont.getAsRegion();
   if (!ContReg)
     return;
 
   ContReg = ContReg->getMostDerivedObjectRegion();
 
   auto State = C.getState();
   const auto CData = getContainerData(State, ContReg);
if (hasSubscriptOperator(State, ContReg) &&
       State = invalidateIteratorPositions(State, BackSym, BO_EQ);
     }
     auto newEndSym = BackSym;
     State = setContainerData(State, ContReg, CData->newEnd(newEndSym));
     C.addTransition(State);
   }
 }
 
-void IteratorChecker::handlePushFront(CheckerContext &C,
+void IteratorModeling::handlePushFront(CheckerContext &C,
                                        const SVal &Cont) const {
   const auto *ContReg = Cont.getAsRegion();
   if (!ContReg)
     return;
 
   ContReg = ContReg->getMostDerivedObjectRegion();
 
   // For deque-like containers invalidate all iterator positions
   auto State = C.getState();
if (const auto BeginSym = CData->getBegin()) {
                       nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
                       SymMgr.getType(BeginSym)).getAsSymbol();
       State = setContainerData(State, ContReg, CData->newBegin(newBeginSym));
       C.addTransition(State);
     }
   }
 }
 
-void IteratorChecker::handlePopFront(CheckerContext &C,
+void IteratorModeling::handlePopFront(CheckerContext &C,
                                       const SVal &Cont) const {
   const auto *ContReg = Cont.getAsRegion();
   if (!ContReg)
     return;
 
   ContReg = ContReg->getMostDerivedObjectRegion();
 
   auto State = C.getState();
   const auto CData = getContainerData(State, ContReg);
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 {
+void IteratorModeling::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 {
+void IteratorModeling::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.
if (const auto *CData = getContainerData(State, Cont)) {
       }
     }
   } else {
     State = invalidateIteratorPositions(State, Pos->getOffset(), BO_EQ);
   }
   C.addTransition(State);
 }
 
-void IteratorChecker::handleErase(CheckerContext &C, const SVal &Iter1,
+void IteratorModeling::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
if (hasSubscriptOperator(State, Cont) && backModifiable(State, Cont)) {
     }
   } else {
     State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GE,
                                         Pos2->getOffset(), BO_LT);
   }
   C.addTransition(State);
 }
 
-void IteratorChecker::handleEraseAfter(CheckerContext &C,
+void IteratorModeling::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,
+void IteratorModeling::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);
 }
 
-IteratorPosition IteratorChecker::advancePosition(CheckerContext &C,
-                                                  OverloadedOperatorKind Op,
-                                                  const IteratorPosition &Pos,
-                                                  const SVal &Distance) const {
-  auto State = C.getState();
-  auto &SymMgr = C.getSymbolManager();
-  auto &SVB = C.getSValBuilder();
-
-  assert ((Op == OO_Plus || Op == OO_PlusEqual ||
-           Op == OO_Minus || Op == OO_MinusEqual) &&
-          "Advance operator must be one of +, -, += and -=.");
-  auto BinOp = (Op == OO_Plus || Op == OO_PlusEqual) ? BO_Add : BO_Sub;
-  if (const auto IntDist = Distance.getAs<nonloc::ConcreteInt>()) {
-    // For concrete integers we can calculate the new position
-    return Pos.setTo(SVB.evalBinOp(State, BinOp,
-                                   nonloc::SymbolVal(Pos.getOffset()), *IntDist,
-                                   SymMgr.getType(Pos.getOffset()))
-                         .getAsSymbol());
-  } else {
-    // For other symbols create a new symbol to keep expressions simple
-    const auto &LCtx = C.getLocationContext();
-    const auto NewPosSym = SymMgr.conjureSymbol(nullptr, LCtx,
-                                             SymMgr.getType(Pos.getOffset()),
-                                             C.blockCount());
-    State = assumeNoOverflow(State, NewPosSym, 4);
-    return Pos.setTo(NewPosSym);
-  }
-}
-
-void IteratorChecker::reportOutOfRangeBug(const StringRef &Message,
-                                          const SVal &Val, CheckerContext &C,
-                                          ExplodedNode *ErrNode) const {
-  auto R = std::make_unique<PathSensitiveBugReport>(*OutOfRangeBugType, Message,
-                                                    ErrNode);
-  R->markInteresting(Val);
-  C.emitReport(std::move(R));
-}
-
-void IteratorChecker::reportMismatchedBug(const StringRef &Message,
-                                          const SVal &Val1, const SVal &Val2,
-                                          CheckerContext &C,
-                                          ExplodedNode *ErrNode) const {
-  auto R = std::make_unique<PathSensitiveBugReport>(*MismatchedBugType, Message,
-                                                    ErrNode);
-  R->markInteresting(Val1);
-  R->markInteresting(Val2);
-  C.emitReport(std::move(R));
-}
-
-void IteratorChecker::reportMismatchedBug(const StringRef &Message,
-                                          const SVal &Val, const MemRegion *Reg,
-                                          CheckerContext &C,
-                                          ExplodedNode *ErrNode) const {
-  auto R = std::make_unique<PathSensitiveBugReport>(*MismatchedBugType, Message,
-                                                    ErrNode);
-  R->markInteresting(Val);
-  R->markInteresting(Reg);
-  C.emitReport(std::move(R));
-}
-
-void IteratorChecker::reportInvalidatedBug(const StringRef &Message,
-                                           const SVal &Val, CheckerContext &C,
-                                           ExplodedNode *ErrNode) const {
-  auto R = std::make_unique<PathSensitiveBugReport>(*InvalidatedBugType,
-                                                    Message, ErrNode);
-  R->markInteresting(Val);
-  C.emitReport(std::move(R));
-}
-
-bool IteratorChecker::evalCall(const CallEvent &Call,
-                                     CheckerContext &C) const {
-  if (!ChecksEnabled[CK_DebugIteratorModeling])
-    return false;
-
-  const auto *CE = dyn_cast_or_null<CallExpr>(Call.getOriginExpr());
-  if (!CE)
-    return false;
-
-  const FnCheck *Handler = Callbacks.lookup(Call);
-  if (!Handler)
-    return false;
-
-  (this->**Handler)(CE, C);
-  return true;
-}
-
-template <typename Getter>
-void IteratorChecker::analyzerContainerDataField(const CallExpr *CE,
-                                                 CheckerContext &C,
-                                                 Getter get) const {
-  if (CE->getNumArgs() == 0) {
-    reportDebugMsg("Missing container argument", C);
-    return;
-  }
-
-  auto State = C.getState();
-  const MemRegion *Cont = C.getSVal(CE->getArg(0)).getAsRegion();
-  if (Cont) {
-    const auto *Data = getContainerData(State, Cont);
-    if (Data) {
-      SymbolRef Field = get(Data);
-      if (Field) {
-        State = State->BindExpr(CE, C.getLocationContext(),
-                                nonloc::SymbolVal(Field));
-        C.addTransition(State);
-        return;
-      }
-    }
-  }
-
-  auto &BVF = C.getSValBuilder().getBasicValueFactory();
-  State = State->BindExpr(CE, C.getLocationContext(),
-                   nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(0))));
-}
-
-void IteratorChecker::analyzerContainerBegin(const CallExpr *CE,
-                                             CheckerContext &C) const {
-  analyzerContainerDataField(CE, C, [](const ContainerData *D) {
-      return D->getBegin();
-    });
-}
-
-void IteratorChecker::analyzerContainerEnd(const CallExpr *CE,
-                                             CheckerContext &C) const {
-  analyzerContainerDataField(CE, C, [](const ContainerData *D) {
-      return D->getEnd();
-    });
-}
-
-template <typename Getter>
-void IteratorChecker::analyzerIteratorDataField(const CallExpr *CE,
-                                                CheckerContext &C,
-                                                Getter get,
-                                                SVal Default) const {
-  if (CE->getNumArgs() == 0) {
-    reportDebugMsg("Missing iterator argument", C);
-    return;
-  }
-
-  auto State = C.getState();
-  SVal V = C.getSVal(CE->getArg(0));
-  const auto *Pos = getIteratorPosition(State, V);
-  if (Pos) {
-    State = State->BindExpr(CE, C.getLocationContext(), get(Pos));
-  } else {
-    State = State->BindExpr(CE, C.getLocationContext(), Default);
-  }
-  C.addTransition(State);
-}
-
-void IteratorChecker::analyzerIteratorPosition(const CallExpr *CE,
-                                               CheckerContext &C) const {
-  auto &BVF = C.getSValBuilder().getBasicValueFactory();
-  analyzerIteratorDataField(CE, C, [](const IteratorPosition *P) {
-      return nonloc::SymbolVal(P->getOffset());
-    }, nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(0))));
-}
-
-void IteratorChecker::analyzerIteratorContainer(const CallExpr *CE,
-                                               CheckerContext &C) const {
-  auto &BVF = C.getSValBuilder().getBasicValueFactory();
-  analyzerIteratorDataField(CE, C, [](const IteratorPosition *P) {
-      return loc::MemRegionVal(P->getContainer());
-    }, loc::ConcreteInt(BVF.getValue(llvm::APSInt::get(0))));
-}
-
-void IteratorChecker::analyzerIteratorValidity(const CallExpr *CE,
-                                               CheckerContext &C) const {
-  auto &BVF = C.getSValBuilder().getBasicValueFactory();
-  analyzerIteratorDataField(CE, C, [&BVF](const IteratorPosition *P) {
-      return
-        nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get((P->isValid()))));
-    }, nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(0))));
-}
-
-ExplodedNode *IteratorChecker::reportDebugMsg(llvm::StringRef Msg,
-                                              CheckerContext &C) const {
-  ExplodedNode *N = C.generateNonFatalErrorNode();
-  if (!N)
-    return nullptr;
-
-  auto &BR = C.getBugReporter();
-  BR.emitReport(std::make_unique<PathSensitiveBugReport>(*DebugMsgBugType,
-                                                         Msg, N));
-  return N;
-}
-
 namespace {
 
-bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
-bool isGreater(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
-bool isEqual(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);
 const CXXRecordDecl *getCXXRecordDecl(ProgramStateRef State,
                                       const MemRegion *Reg);
-SymbolRef rebaseSymbol(ProgramStateRef State, SValBuilder &SVB, SymbolRef Expr,
-                        SymbolRef OldSym, SymbolRef NewSym);
-
-bool isIteratorType(const QualType &Type) {
-  if (Type->isPointerType())
-    return true;
-
-  const auto *CRD = Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl();
-  return isIterator(CRD);
-}
-
-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 HasCopyCtor = false, HasCopyAssign = true, HasDtor = false,
-       HasPreIncrOp = false, HasPostIncrOp = false, HasDerefOp = false;
-  for (const auto *Method : CRD->methods()) {
-    if (const auto *Ctor = dyn_cast<CXXConstructorDecl>(Method)) {
-      if (Ctor->isCopyConstructor()) {
-        HasCopyCtor = !Ctor->isDeleted() && Ctor->getAccess() == AS_public;
-      }
-      continue;
-    }
-    if (const auto *Dtor = dyn_cast<CXXDestructorDecl>(Method)) {
-      HasDtor = !Dtor->isDeleted() && Dtor->getAccess() == AS_public;
-      continue;
-    }
-    if (Method->isCopyAssignmentOperator()) {
-      HasCopyAssign = !Method->isDeleted() && Method->getAccess() == AS_public;
-      continue;
-    }
-    if (!Method->isOverloadedOperator())
-      continue;
-    const auto OPK = Method->getOverloadedOperator();
-    if (OPK == OO_PlusPlus) {
-      HasPreIncrOp = HasPreIncrOp || (Method->getNumParams() == 0);
-      HasPostIncrOp = HasPostIncrOp || (Method->getNumParams() == 1);
-      continue;
-    }
-    if (OPK == OO_Star) {
-      HasDerefOp = (Method->getNumParams() == 0);
-      continue;
-    }
-  }
-
-  return HasCopyCtor && HasCopyAssign && HasDtor && HasPreIncrOp &&
-         HasPostIncrOp && HasDerefOp;
-}
-
-bool isComparisonOperator(OverloadedOperatorKind OK) {
-  return OK == OO_EqualEqual || OK == OO_ExclaimEqual || OK == OO_Less ||
-         OK == OO_LessEqual || OK == OO_Greater || OK == OO_GreaterEqual;
-}
 
 bool isBeginCall(const FunctionDecl *Func) {
   const auto *IdInfo = Func->getIdentifier();
   if (!IdInfo)
     return false;
   return IdInfo->getName().endswith_lower("begin");
 }
 
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) ||
-         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 isDecrementOperator(OverloadedOperatorKind OK) {
-  return OK == OO_MinusMinus;
-}
-
-bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK) {
-  return OK == OO_Plus || OK == OO_PlusEqual || OK == OO_Minus ||
-         OK == OO_MinusEqual;
-}
-
 bool hasSubscriptOperator(ProgramStateRef State, const MemRegion *Reg) {
   const auto *CRD = getCXXRecordDecl(State, Reg);
   if (!CRD)
     return false;
 
   for (const auto *Method : CRD->methods()) {
     if (!Method->isOverloadedOperator())
       continue;
if (CDataPtr) {
     const auto CData = CDataPtr->newEnd(Sym);
     return setContainerData(State, Cont, CData);
   }
 
   const auto CData = ContainerData::fromEnd(Sym);
   return setContainerData(State, Cont, CData);
 }
 
-const ContainerData *getContainerData(ProgramStateRef State,
-                                      const MemRegion *Cont) {
-  return State->get<ContainerMap>(Cont);
-}
-
 ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont,
                                  const ContainerData &CData) {
   return State->set<ContainerMap>(Cont, CData);
 }
 
-const IteratorPosition *getIteratorPosition(ProgramStateRef State,
-                                            const SVal &Val) {
+ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val) {
   if (auto Reg = Val.getAsRegion()) {
     Reg = Reg->getMostDerivedObjectRegion();
-    return State->get<IteratorRegionMap>(Reg);
+    return State->remove<IteratorRegionMap>(Reg);
   } else if (const auto Sym = Val.getAsSymbol()) {
-    return State->get<IteratorSymbolMap>(Sym);
+    return State->remove<IteratorSymbolMap>(Sym);
   } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
-    return State->get<IteratorRegionMap>(LCVal->getRegion());
+    return State->remove<IteratorRegionMap>(LCVal->getRegion());
   }
   return nullptr;
 }
 
-ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val,
-                                    const IteratorPosition &Pos) {
-  if (auto Reg = Val.getAsRegion()) {
-    Reg = Reg->getMostDerivedObjectRegion();
-    return State->set<IteratorRegionMap>(Reg, Pos);
-  } else if (const auto Sym = Val.getAsSymbol()) {
-    return State->set<IteratorSymbolMap>(Sym, Pos);
-  } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
-    return State->set<IteratorRegionMap>(LCVal->getRegion(), Pos);
-  }
-  return nullptr;
+// This function tells the analyzer's engine that symbols produced by our
+// checker, most notably iterator positions, are relatively small.
+// A distance between items in the container should not be very large.
+// By assuming that it is within around 1/8 of the address space,
+// we can help the analyzer perform operations on these symbols
+// without being afraid of integer overflows.
+// FIXME: Should we provide it as an API, so that all checkers could use it?
+ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym,
+                                 long Scale) {
+  SValBuilder &SVB = State->getStateManager().getSValBuilder();
+  BasicValueFactory &BV = SVB.getBasicValueFactory();
+
+  QualType T = Sym->getType();
+  assert(T->isSignedIntegerOrEnumerationType());
+  APSIntType AT = BV.getAPSIntType(T);
+
+  ProgramStateRef NewState = State;
+
+  llvm::APSInt Max = AT.getMaxValue() / AT.getValue(Scale);
+  SVal IsCappedFromAbove =
+      SVB.evalBinOpNN(State, BO_LE, nonloc::SymbolVal(Sym),
+                      nonloc::ConcreteInt(Max), SVB.getConditionType());
+  if (auto DV = IsCappedFromAbove.getAs<DefinedSVal>()) {
+    NewState = NewState->assume(*DV, true);
+    if (!NewState)
+      return State;
   }
 
-ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val) {
-  if (auto Reg = Val.getAsRegion()) {
-    Reg = Reg->getMostDerivedObjectRegion();
-    return State->remove<IteratorRegionMap>(Reg);
-  } else if (const auto Sym = Val.getAsSymbol()) {
-    return State->remove<IteratorSymbolMap>(Sym);
-  } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
-    return State->remove<IteratorRegionMap>(LCVal->getRegion());
+  llvm::APSInt Min = -Max;
+  SVal IsCappedFromBelow =
+      SVB.evalBinOpNN(State, BO_GE, nonloc::SymbolVal(Sym),
+                      nonloc::ConcreteInt(Min), SVB.getConditionType());
+  if (auto DV = IsCappedFromBelow.getAs<DefinedSVal>()) {
+    NewState = NewState->assume(*DV, true);
+    if (!NewState)
+      return State;
   }
-  return nullptr;
+
+  return NewState;
 }
 
 ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1,
                               SymbolRef Sym2, bool Equal) {
   auto &SVB = State->getStateManager().getSValBuilder();
 
   // FIXME: This code should be reworked as follows:
   // 1. Subtract the operands using evalBinOp().
if (const auto LCVal = Binding.second.getAs<nonloc::LazyCompoundVal>()) {
       if (LCVal->getRegion() == Reg)
         return true;
     }
   }
 
   return false;
 }
 
-// This function tells the analyzer's engine that symbols produced by our
-// checker, most notably iterator positions, are relatively small.
-// A distance between items in the container should not be very large.
-// By assuming that it is within around 1/8 of the address space,
-// we can help the analyzer perform operations on these symbols
-// without being afraid of integer overflows.
-// FIXME: Should we provide it as an API, so that all checkers could use it?
-ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym,
-                                 long Scale) {
-  SValBuilder &SVB = State->getStateManager().getSValBuilder();
-  BasicValueFactory &BV = SVB.getBasicValueFactory();
-
-  QualType T = Sym->getType();
-  assert(T->isSignedIntegerOrEnumerationType());
-  APSIntType AT = BV.getAPSIntType(T);
-
-  ProgramStateRef NewState = State;
-
-  llvm::APSInt Max = AT.getMaxValue() / AT.getValue(Scale);
-  SVal IsCappedFromAbove =
-      SVB.evalBinOpNN(State, BO_LE, nonloc::SymbolVal(Sym),
-                      nonloc::ConcreteInt(Max), SVB.getConditionType());
-  if (auto DV = IsCappedFromAbove.getAs<DefinedSVal>()) {
-    NewState = NewState->assume(*DV, true);
-    if (!NewState)
-      return State;
-  }
-
-  llvm::APSInt Min = -Max;
-  SVal IsCappedFromBelow =
-      SVB.evalBinOpNN(State, BO_GE, nonloc::SymbolVal(Sym),
-                      nonloc::ConcreteInt(Min), SVB.getConditionType());
-  if (auto DV = IsCappedFromBelow.getAs<DefinedSVal>()) {
-    NewState = NewState->assume(*DV, true);
-    if (!NewState)
-      return State;
-  }
-
-  return NewState;
-}
-
 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)) {
SymbolRef rebaseSymbol(ProgramStateRef State, SValBuilder &SVB,
   const auto DiffInt = Diff.getAs<nonloc::ConcreteInt>();
   if (!DiffInt)
     return OrigExpr;
 
   return SVB.evalBinOpNN(State, BO_Add, *DiffInt, nonloc::SymbolVal(NewSym),
                          SymMgr.getType(OrigExpr)).getAsSymbol();
 }
 
-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 isPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos) {
-  const auto *Cont = Pos.getContainer();
-  const auto *CData = getContainerData(State, Cont);
-  if (!CData)
-    return false;
-
-  const auto End = CData->getEnd();
-  if (End) {
-    if (isEqual(State, Pos.getOffset(), End)) {
-      return true;
-    }
-  }
-
-  return false;
-}
-
-bool isAheadOfRange(ProgramStateRef State, const IteratorPosition &Pos) {
-  const auto *Cont = Pos.getContainer();
-  const auto *CData = getContainerData(State, Cont);
-  if (!CData)
-    return false;
-
-  const auto Beg = CData->getBegin();
-  if (Beg) {
-    if (isLess(State, Pos.getOffset(), Beg)) {
-      return true;
-    }
-  }
-
-  return false;
-}
-
-bool isBehindPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos) {
-  const auto *Cont = Pos.getContainer();
-  const auto *CData = getContainerData(State, Cont);
-  if (!CData)
-    return false;
-
-  const auto End = CData->getEnd();
-  if (End) {
-    if (isGreater(State, Pos.getOffset(), End)) {
-      return true;
-    }
-  }
-
-  return false;
-}
-
-bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
-  return compare(State, Sym1, Sym2, BO_LT);
-}
-
-bool isGreater(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
-  return compare(State, Sym1, Sym2, BO_GT);
-}
-
-bool isEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
-  return compare(State, Sym1, Sym2, BO_EQ);
-}
-
-bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
-             BinaryOperator::Opcode Opc) {
-  return compare(State, nonloc::SymbolVal(Sym1), nonloc::SymbolVal(Sym2), Opc);
-}
-
-bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2,
-             BinaryOperator::Opcode Opc) {
-  auto &SVB = State->getStateManager().getSValBuilder();
-
-  const auto comparison =
-    SVB.evalBinOp(State, Opc, NL1, NL2, SVB.getConditionType());
-
-  assert(comparison.getAs<DefinedSVal>() &&
-    "Symbol comparison must be a `DefinedSVal`");
-
-  return !State->assume(comparison.castAs<DefinedSVal>(), false);
-}
-
 } // namespace
 
 void ento::registerIteratorModeling(CheckerManager &mgr) {
-  mgr.registerChecker<IteratorChecker>();
+  mgr.registerChecker<IteratorModeling>();
 }
 
 bool ento::shouldRegisterIteratorModeling(const LangOptions &LO) {
   return true;
 }
-
-#define REGISTER_CHECKER(name)                                                 \
-  void ento::register##name(CheckerManager &Mgr) {                             \
-    auto *checker = Mgr.getChecker<IteratorChecker>();                         \
-    checker->ChecksEnabled[IteratorChecker::CK_##name] = true;                 \
-    checker->CheckNames[IteratorChecker::CK_##name] =                          \
-        Mgr.getCurrentCheckerName();                                           \
-  }                                                                            \
-                                                                               \
-  bool ento::shouldRegister##name(const LangOptions &LO) { return true; }
-
-REGISTER_CHECKER(IteratorRangeChecker)
-REGISTER_CHECKER(MismatchedIteratorChecker)
-REGISTER_CHECKER(InvalidatedIteratorChecker)
-REGISTER_CHECKER(DebugIteratorModeling)

clang/lib/StaticAnalyzer/Checkers/IteratorRangeChecker.cpp

+//===-- IteratorRangeChecker.cpp ----------------------------------*- C++ -*--//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Defines a checker for dereference of the past-the-end iterator and
+// out-of-range increments and decrements.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.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 "Iterator.h"
+
+using namespace clang;
+using namespace ento;
+using namespace iterator;
+
+namespace {
+
+class IteratorRangeChecker
+  : public Checker<check::PreCall> {
+
+  std::unique_ptr<BugType> OutOfRangeBugType;
+
+  void verifyDereference(CheckerContext &C, const SVal &Val) const;
+  void verifyIncrement(CheckerContext &C, const SVal &Iter) const;
+  void verifyDecrement(CheckerContext &C, const SVal &Iter) const;
+  void verifyRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op,
+                              const SVal &LHS, const SVal &RHS) const;
+  void reportBug(const StringRef &Message, const SVal &Val,
+                 CheckerContext &C, ExplodedNode *ErrNode) const;
+public:
+  IteratorRangeChecker();
+
+  void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
+
+};
+
+bool isPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos);
+bool isAheadOfRange(ProgramStateRef State, const IteratorPosition &Pos);
+bool isBehindPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos);
+bool isZero(ProgramStateRef State, const NonLoc &Val);
+
+} //namespace
+
+IteratorRangeChecker::IteratorRangeChecker() {
+  OutOfRangeBugType.reset(
+      new BugType(this, "Iterator out of range", "Misuse of STL APIs"));
+}
+
+void IteratorRangeChecker::checkPreCall(const CallEvent &Call,
+                                        CheckerContext &C) const {
+  // Check for out of range access
+  const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
+  if (!Func)
+    return;
+
+  if (Func->isOverloadedOperator()) {
+    if (isIncrementOperator(Func->getOverloadedOperator())) {
+      // Check for out-of-range incrementions
+      if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
+        verifyIncrement(C, InstCall->getCXXThisVal());
+      } else {
+        if (Call.getNumArgs() >= 1) {
+          verifyIncrement(C, Call.getArgSVal(0));
+        }
+      }
+    } else if (isDecrementOperator(Func->getOverloadedOperator())) {
+      // Check for out-of-range decrementions
+      if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
+        verifyDecrement(C, InstCall->getCXXThisVal());
+      } else {
+        if (Call.getNumArgs() >= 1) {
+          verifyDecrement(C, Call.getArgSVal(0));
+        }
+      }
+    } else if (isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) {
+      if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
+        // Check for out-of-range incrementions and decrementions
+        if (Call.getNumArgs() >= 1 &&
+            Call.getArgExpr(0)->getType()->isIntegralOrEnumerationType()) {
+          verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(),
+                                 InstCall->getCXXThisVal(),
+                                 Call.getArgSVal(0));
+        }
+      } else {
+        if (Call.getNumArgs() >= 2 &&
+            Call.getArgExpr(1)->getType()->isIntegralOrEnumerationType()) {
+          verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(),
+                                 Call.getArgSVal(0), Call.getArgSVal(1));
+        }
+      }
+    } else if (isDereferenceOperator(Func->getOverloadedOperator())) {
+      // Check for dereference of out-of-range iterators
+      if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
+        verifyDereference(C, InstCall->getCXXThisVal());
+      } else {
+        verifyDereference(C, Call.getArgSVal(0));
+      }
+    }
+  }
+}
+
+void IteratorRangeChecker::verifyDereference(CheckerContext &C,
+                                             const SVal &Val) const {
+  auto State = C.getState();
+  const auto *Pos = getIteratorPosition(State, Val);
+  if (Pos && isPastTheEnd(State, *Pos)) {
+    auto *N = C.generateErrorNode(State);
+    if (!N)
+      return;
+    reportBug("Past-the-end iterator dereferenced.", Val, C, N);
+    return;
+  }
+}
+
+void IteratorRangeChecker::verifyIncrement(CheckerContext &C,
+                                          const SVal &Iter) const {
+  auto &BVF = C.getSValBuilder().getBasicValueFactory();
+  verifyRandomIncrOrDecr(C, OO_Plus, Iter,
+                     nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
+}
+
+void IteratorRangeChecker::verifyDecrement(CheckerContext &C,
+                                          const SVal &Iter) const {
+  auto &BVF = C.getSValBuilder().getBasicValueFactory();
+  verifyRandomIncrOrDecr(C, OO_Minus, Iter,
+                     nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
+}
+
+void IteratorRangeChecker::verifyRandomIncrOrDecr(CheckerContext &C,
+                                                 OverloadedOperatorKind Op,
+                                                 const SVal &LHS,
+                                                 const SVal &RHS) const {
+  auto State = C.getState();
+
+  auto Value = RHS;
+  if (auto ValAsLoc = RHS.getAs<Loc>()) {
+    Value = State->getRawSVal(*ValAsLoc);
+  }
+
+  if (Value.isUnknown())
+    return;
+
+  // Incremention or decremention by 0 is never a bug.
+  if (isZero(State, Value.castAs<NonLoc>()))
+    return;
+
+  // The result may be the past-end iterator of the container, but any other
+  // out of range position is undefined behaviour
+  auto StateAfter = advancePosition(State, LHS, Op, Value);
+  if (!StateAfter)
+    return;
+
+  const auto *PosAfter = getIteratorPosition(StateAfter, LHS);
+  assert(PosAfter &&
+         "Iterator should have position after successful advancement");
+  if (isAheadOfRange(State, *PosAfter)) {
+    auto *N = C.generateErrorNode(State);
+    if (!N)
+      return;
+    reportBug("Iterator decremented ahead of its valid range.", LHS,
+                        C, N);
+  }
+  if (isBehindPastTheEnd(State, *PosAfter)) {
+    auto *N = C.generateErrorNode(State);
+    if (!N)
+      return;
+    reportBug("Iterator incremented behind the past-the-end "
+                        "iterator.", LHS, C, N);
+  }
+}
+
+void IteratorRangeChecker::reportBug(const StringRef &Message,
+                                    const SVal &Val, CheckerContext &C,
+                                    ExplodedNode *ErrNode) const {
+  auto R = std::make_unique<PathSensitiveBugReport>(*OutOfRangeBugType, Message,
+                                                    ErrNode);
+  R->markInteresting(Val);
+  C.emitReport(std::move(R));
+}
+
+namespace {
+
+bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
+bool isGreater(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
+bool isEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
+
+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 isPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos) {
+  const auto *Cont = Pos.getContainer();
+  const auto *CData = getContainerData(State, Cont);
+  if (!CData)
+    return false;
+
+  const auto End = CData->getEnd();
+  if (End) {
+    if (isEqual(State, Pos.getOffset(), End)) {
+      return true;
+    }
+  }
+
+  return false;
+}
+
+bool isAheadOfRange(ProgramStateRef State, const IteratorPosition &Pos) {
+  const auto *Cont = Pos.getContainer();
+  const auto *CData = getContainerData(State, Cont);
+  if (!CData)
+    return false;
+
+  const auto Beg = CData->getBegin();
+  if (Beg) {
+    if (isLess(State, Pos.getOffset(), Beg)) {
+      return true;
+    }
+  }
+
+  return false;
+}
+
+bool isBehindPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos) {
+  const auto *Cont = Pos.getContainer();
+  const auto *CData = getContainerData(State, Cont);
+  if (!CData)
+    return false;
+
+  const auto End = CData->getEnd();
+  if (End) {
+    if (isGreater(State, Pos.getOffset(), End)) {
+      return true;
+    }
+  }
+
+  return false;
+}
+
+bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
+  return compare(State, Sym1, Sym2, BO_LT);
+}
+
+bool isGreater(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
+  return compare(State, Sym1, Sym2, BO_GT);
+}
+
+bool isEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
+  return compare(State, Sym1, Sym2, BO_EQ);
+}
+
+} // namespace
+
+void ento::registerIteratorRangeChecker(CheckerManager &mgr) {
+  mgr.registerChecker<IteratorRangeChecker>();
+}
+
+bool ento::shouldRegisterIteratorRangeChecker(const LangOptions &LO) {
+  return true;
+}

clang/lib/StaticAnalyzer/Checkers/MismatchedIteratorChecker.cpp

+//===-- MismatchedIteratorChecker.cpp -----------------------------*- C++ -*--//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Defines a checker for mistakenly applying a foreign iterator on a container
+// and for using iterators of two different containers in a context where
+// iterators of the same container should be used.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.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 "Iterator.h"
+
+using namespace clang;
+using namespace ento;
+using namespace iterator;
+
+namespace {
+
+class MismatchedIteratorChecker
+  : public Checker<check::PreCall> {
+
+  std::unique_ptr<BugType> MismatchedBugType;
+
+  void verifyMatch(CheckerContext &C, const SVal &Iter,
+                   const MemRegion *Cont) const;
+  void verifyMatch(CheckerContext &C, const SVal &Iter1,
+                   const SVal &Iter2) const;
+  void reportBug(const StringRef &Message, const SVal &Val1,
+                 const SVal &Val2, CheckerContext &C,
+                 ExplodedNode *ErrNode) const;
+  void reportBug(const StringRef &Message, const SVal &Val,
+                 const MemRegion *Reg, CheckerContext &C,
+                 ExplodedNode *ErrNode) const;
+
+public:
+  MismatchedIteratorChecker();
+
+  void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
+
+};
+
+} // namespace
+
+MismatchedIteratorChecker::MismatchedIteratorChecker() {
+  MismatchedBugType.reset(
+      new BugType(this, "Iterator(s) mismatched", "Misuse of STL APIs",
+                  /*SuppressOnSink=*/true));
+}
+
+void MismatchedIteratorChecker::checkPreCall(const CallEvent &Call,
+                                             CheckerContext &C) const {
+  // Check for iterator mismatches
+  const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
+  if (!Func)
+    return;
+
+  if (Func->isOverloadedOperator() &&
+      isComparisonOperator(Func->getOverloadedOperator())) {
+    // Check for comparisons of iterators of different containers
+    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;
+    // 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 (Ctr->getParamDecl(0)->getName() != "first" ||
+        Ctr->getParamDecl(1)->getName() != "last")
+      return;
+
+    if (!isIteratorType(Call.getArgExpr(0)->getType()) ||
+        !isIteratorType(Call.getArgExpr(1)->getType()))
+      return;
+
+    verifyMatch(C, Call.getArgSVal(0), Call.getArgSVal(1));
+  } else {
+    // 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.
+    //
+    // Example:
+    // template<typename I1, typename I2>
+    // void f(I1 first1, I1 last1, I2 first2, I2 last2);
+    // 
+    // In this case the first two arguments to f() must be iterators must belong
+    // to the same container and the last to also to the same container but
+    // not necessarily to the same as the first two.
+
+    const auto *Templ = Func->getPrimaryTemplate();
+    if (!Templ)
+      return;
+
+    const auto *TParams = Templ->getTemplateParameters();
+    const auto *TArgs = Func->getTemplateSpecializationArgs();
+
+    // Iterate over all the template parameters
+    for (size_t I = 0; I < TParams->size(); ++I) {
+      const auto *TPDecl = dyn_cast<TemplateTypeParmDecl>(TParams->getParam(I));
+      if (!TPDecl)
+        continue;
+
+      if (TPDecl->isParameterPack())
+        continue;
+
+      const auto TAType = TArgs->get(I).getAsType();
+      if (!isIteratorType(TAType))
+        continue;
+
+      SVal LHS = UndefinedVal();
+
+      // For every template parameter which is an iterator type in the
+      // instantiation look for all functions' parameters' type by it and
+      // check whether they belong to the same container
+      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::verifyMatch(CheckerContext &C, const SVal &Iter,
+                                            const MemRegion *Cont) const {
+  // Verify match between a container and the container of an iterator
+  Cont = Cont->getMostDerivedObjectRegion();
+
+  if (const auto *ContSym = Cont->getSymbolicBase()) {
+    if (isa<SymbolConjured>(ContSym->getSymbol()))
+      return;
+  }
+
+  auto State = C.getState();
+  const auto *Pos = getIteratorPosition(State, Iter);
+  if (!Pos)
+    return;
+
+  const auto *IterCont = Pos->getContainer();
+
+  // Skip symbolic regions based on conjured symbols. Two conjured symbols
+  // may or may not be the same. For example, the same function can return
+  // the same or a different container but we get different conjured symbols
+  // for each call. This may cause false positives so omit them from the check.
+  if (const auto *ContSym = IterCont->getSymbolicBase()) {
+    if (isa<SymbolConjured>(ContSym->getSymbol()))
+      return;
+  }
+
+  if (IterCont != Cont) {
+    auto *N = C.generateNonFatalErrorNode(State);
+    if (!N) {
+      return;
+    }
+    reportBug("Container accessed using foreign iterator argument.",
+                        Iter, Cont, C, N);
+  }
+}
+
+void MismatchedIteratorChecker::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);
+  if (!Pos1)
+    return;
+
+  const auto *IterCont1 = Pos1->getContainer();
+
+  // Skip symbolic regions based on conjured symbols. Two conjured symbols
+  // may or may not be the same. For example, the same function can return
+  // the same or a different container but we get different conjured symbols
+  // for each call. This may cause false positives so omit them from the check.
+  if (const auto *ContSym = IterCont1->getSymbolicBase()) {
+    if (isa<SymbolConjured>(ContSym->getSymbol()))
+      return;
+  }
+
+  const auto *Pos2 = getIteratorPosition(State, Iter2);
+  if (!Pos2)
+    return;
+
+  const auto *IterCont2 = Pos2->getContainer();
+  if (const auto *ContSym = IterCont2->getSymbolicBase()) {
+    if (isa<SymbolConjured>(ContSym->getSymbol()))
+      return;
+  }
+
+  if (IterCont1 != IterCont2) {
+    auto *N = C.generateNonFatalErrorNode(State);
+    if (!N)
+      return;
+    reportBug("Iterators of different containers used where the "
+                        "same container is expected.", Iter1, Iter2, C, N);
+  }
+}
+
+void MismatchedIteratorChecker::reportBug(const StringRef &Message,
+                                          const SVal &Val1,
+                                          const SVal &Val2,
+                                          CheckerContext &C,
+                                          ExplodedNode *ErrNode) const {
+  auto R = std::make_unique<PathSensitiveBugReport>(*MismatchedBugType, Message,
+                                                    ErrNode);
+  R->markInteresting(Val1);
+  R->markInteresting(Val2);
+  C.emitReport(std::move(R));
+}
+
+void MismatchedIteratorChecker::reportBug(const StringRef &Message,
+                                          const SVal &Val, const MemRegion *Reg,
+                                          CheckerContext &C,
+                                          ExplodedNode *ErrNode) const {
+  auto R = std::make_unique<PathSensitiveBugReport>(*MismatchedBugType, Message,
+                                                    ErrNode);
+  R->markInteresting(Val);
+  R->markInteresting(Reg);
+  C.emitReport(std::move(R));
+}
+
+void ento::registerMismatchedIteratorChecker(CheckerManager &mgr) {
+  mgr.registerChecker<MismatchedIteratorChecker>();
+}
+
+bool ento::shouldRegisterMismatchedIteratorChecker(const LangOptions &LO) {
+  return true;
+}