[Analyzer] Iterator Checkers

[baloghadamsoftware]

Summary

IteratorRangeChecker, MismatchedIteratorChecker and InvalidatedIteratorChecker integrated in one single checker file. The checker always keeps track of the status of the iterators, but verification of out-of-range access, invalidated iterator access and mismatched iterator use can be separately enabled or disabled.

Tested on real code (Clang) without crash. Some false positives are still present.

[baloghadamsoftware]

Superseeds D28771 and D29419.

[zaks.anna]

@baloghadamsoftware Thanks for working on this!

However, this patch is getting too big. Could you, please, split it into incremental patches so that it would be easier to review? More motivation of why this is very important is here http://llvm.org/docs/DeveloperPolicy.html#incremental-development

[NoQ]

I think for this case it'd be great to (instead) add comments all over the place (especially in checker callbacks, eg. check[Pre|Post]Call() function bodies) to indicate what check every piece of code is for. That'd be equally easy to review, at least for me, but it'd also help greatly if we start splitting up checkers into modelling and checking parts.

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

239–241

I've got a fresh idea on this: Maybe it'd be easier to make an llvm::PointerUnion<SymbolRef, const MemRegion *> and enjoy a single map from that to IteratorPosition, rather than maintaining two maps.

I don't insist though, because i didn't really think if it makes the code any simpler.

[NoQ]

Hmm.

1. Could you do renaming the checker file in a separate patch, so that we saw an actual diff, not a whole greenish file, here on phabricator?
2. The invalidated iterator checker looks relatively small (a single check and a few rounds of iterator invalidations), would it be hard to split it up into a separate patch? That'd leave us with just one checker added.

[baloghadamsoftware]

Hello! I am not sure how to split it to incremental patches. As I mentioned in the description, the state of the iterator position is always tracked. So if I remove some of the checks it does not make the patch much smaller, since the checking part is quite small. If I remove parts of the tracking, I introduce lots of false positives and uncaught bugs.

Container and offset tracking is needed for both range and validity checks. Match check does not need the offset, but removing it means lots of work, and does not help either because the second patch (adding range and validity checks incrementally) will remain huge.

Doing the rename in a separate patch is useless, because this checker is totally new: the whole position tracking uses a new concept. What I reused is the method of transferring the position between various SVals. Doing the rename separately would mean the same amount of green and lots of red.

What I could do is to rearrange of the functions a bit (separate tracking and checking) and adding more comments to the function. Would it help?

[NoQ]

I had a look at how hard it is to split the patch.

In ~3 hours i reached this far:

0001-Delete-the-old-checker.patch38 KBDownload

0002-Reduced-patch-with-the-following-changes.patch77 KBDownload

0003-Add-support-for-iterator-invalidation-on-assignments.patch16 KBDownload

0004-Add-support-for-push_back.patch17 KBDownload

0005-Add-MismatchedIteratorChecker.patch9 KBDownload

0006-Add-support-for-mismatched-iterators-in-constructors.patch3 KBDownload

0007-Add-support-for-mismatched-iterators-in-comparisons.patch4 KBDownload

0008-Add-support-for-insert.patch11 KBDownload

0009-Add-support-for-emplace.patch12 KBDownload

0010-Add-support-for-erase.patch17 KBDownload

0011-Add-evalCall.patch15 KBDownload

0012-Add-checkBeginFunction.patch4 KBDownload

That job is around 40% done; in patch 0002, the checker has around 1.5k lines of code. Would you be willing to continue this? It should be possible to go on splitting up features until there's just one checker under, say, maybe ~500 lines of code (blind guess), with the only positive being simple_bad_end() in iterator-range.cpp.

My workflow was like this:

1. Put the original patch into a git branch.
2. Choose a feature that seems relatively independent. Good canindates for such features are:
   • Support for particular API.
   • Any particular hack.
   • Any particular rule to check in the checker.
   • The checker itself when it's already small enough.
3. Remove the feature and all tests that start failing.
   • Watch out for "unused function" compiler warnings.
   • Watch out for related tests, eg. remove "good" when you remove "bad".
   • Watch out for the system header simulator:
     • You'd need to update diagnostics/explicit-suppression.cpp test every time.
     • See if what you're removing was actually added by you, and no unrelated analyzer tests fail when you remove it.
   • This step is quite blind. If something is too interdependent, pick another feature.
4. Commit the removal to your branch.
5. Go to 2 unless satisfied with the work you've done.
6. Mass revert all removal commits in the opposite order. Revert of removal is addition, hence the revert-commits can go on review.
7. Mass squash all removal commits into the original commit. That'd be the first commit to go on review.

If you continue this, you'd take my patches 0001 and 0002 instead of your original patch, follow the same method, and then once you're done, add my other patches.

I believe the next good steps would be to remove the invalidated iterator checker (together with support for the clear() API) and then probably try to split out the support for iterator comparisons or support for increments/decrements, then maybe separate access checks from dereference checks.

Once this is done, it'd be great to have a separate review for each patch; it'd put a bit of stress on you to do the rebases once you address comments on the older patches, but that'd make everybody who wants to review the patch, either here on phabricator, or after the commit, a lot happier. I understand that it's not entirely a pleasant thing to do; i also understand that i might have caused confusion by asking you to merge checkers, while i didn't really mean to ask you to merge the patches as well; but it seems that it is universally accepted around there that changes should be small, so i guess it'd worth it.

Note that the point of incremental development is, of course, not splitting up huge patches before submitting to the review; the point is to actually start developing the second small patch only after the first small patch is published. Like, it's perfectly fine to submit an unfinished checker that does 10% of what you want and finds just one tiny bug and has completely obvious false positives due to lack of various modeling, as long as you say "i'd add these features in a follow-up patch". But now that we'd have to incrementally develop retroactively, it is still considered to be better than having huge commits.

[baloghadamsoftware]

Thank you for your help.

Actually, I did neither merge the patches nor the checkers. Based on the experiences in the prototype I created a totally new checker. Incremental development sounds good, but I did a lot of experimenting in this particular checker, which means I added things then removed them, I changed things then changed them back etc.

I can try to separate that small part (simple_good and simple_bad tests pass), but cutting the patch in 12+ parts is overkill. For example, separation of insert and emplace is pointless because they affect iterators exactly the same way. But I woul also merge them with erase, the patches remain small enough. I think 5 parts are more than enough, because review will take weeks, so uploading them incrementally one-by-one will take at least half a year.

[NoQ]

I've seen the new reviews. A lot of thanks for working on the patch split. I believe it'd eventually benefit everyone, similarly to how everybody benefits from code quality or something like that. I'd try to keep up with the "to split or not to split" discussion a bit below, not sure if it's of much interest since we're already trying this out practically and we'll see how much benefit it brings at the end :) And in any case, it's quite hard to see at first that the "incremental" mindset actually works in practice, as i do know that initially it feels strange at times.

In D31975#737751, @baloghadamsoftware wrote:

Actually, I did neither merge the patches nor the checkers. Based on the experiences in the prototype I created a totally new checker. Incremental development sounds good, but I did a lot of experimenting in this particular checker, which means I added things then removed them, I changed things then changed them back etc.

Yep. In this case, a high-level description of why a rewrite is necessary and what was wrong with the old approach would be really helpful, both after and before doing actual work. I'm really interested in what downsides you found in the old checker that needed a complete rewrite to mitigate. Because normally there are very few right ways to write the checker. I've a feeling this experience would be very useful to the community.

While it's definitely not worth it to publish a review every time you're conducting an experiment, it's a good idea to maintain the local history clean and incremental (probably utilizing rebase regularly, eg. if you patch up an old feature, move the patch back to that feature and squash it up after committing), so that splitting it up later was trivial.

In D31975#737751, @baloghadamsoftware wrote:

I can try to separate that small part (simple_good and simple_bad tests pass), but cutting the patch in 12+ parts is overkill. For example, separation of insert and emplace is pointless because they affect iterators exactly the same way. But I woul also merge them with erase, the patches remain small enough. I think 5 parts are more than enough

Yep, that's right, i definitely don't insist on re-using my examples; they were done in a rush and blindly and often don't look harmonously.

In D31975#737751, @baloghadamsoftware wrote:

because review will take weeks, so uploading them incrementally one-by-one will take at least half a year.

I believe it doesn't work that way :)

• Smaller changes are non-linearly easier to review; large changes require keeping all the stuff in your head, and you cannot move forward with the review until you understand all of it. Ultimately, reducing per-line-of-code workload on us would allow us to do more reviews and keep contributors happy.
  • In my experience, it especially applies to estimating test coverage - it would be hard to notice what features are not covered by tests because you need to keep all the features in your head simultaneously. I think i've noticed some strange things in the coverage when i was splitting up the patches, but i didn't record these anywhere.
• Small reviews can be completed in a few hours, maybe even in minutes, of continuous work, but large reviews require large continuous time slots; for patches with thousands of lines of code changed, we may never be able to find such time slots.
• Small reviews increase the chances that at least a part of the contributor's work lands. If some patches are delayed because an alternative approach is proposed, probably involving changes that you're not taking up, we can at least have the rest of the changes in.
• Small reviews would attract more reviewers, who may not be ready to review large changes, or are only sure about their skill in some technologies used but not in other.
• Because our contributors are contributing large changes, we have to apply review pressure on them to make sure these changes are complete and self-contained, because we cannot be sure they will be maintained by the author later. We'd much more eagerly accept a smaller change when the author says he'd fix things up in follow-up commits, even if these changes are obviously incomplete and lacking features. So the review for smaller changes is ultimately less strict.

So, ideally, i believe that reviews aren't normally slow; the impression that reviews are slow only appears when many authors try to contribute large patches.

Sorry for the ranting, and thanks again for investing more and more time into the Analyzer><

[baloghadamsoftware]

Split to 10 parts.

include/clang/StaticAnalyzer/Checkers/Checkers.td

 def VirtualCallChecker : Checker<"VirtualCall">,
   HelpText<"Check virtual function calls during construction or destruction">,
   DescFile<"VirtualCallChecker.cpp">;
 
 } // end: "optin.cplusplus"
 
 let ParentPackage = CplusplusAlpha in {
 
+def IteratorRangeChecker : Checker<"IteratorRange">,
+  HelpText<"Check for iterators used outside their valid ranges">,
+  DescFile<"IteratorChecker.cpp">;
+
+def MismatchedIteratorChecker : Checker<"MismatchedIterator">,
+  HelpText<"Check for use of iterators of different containers where iterators of the same container are expected">,
+  DescFile<"IteratorChecker.cpp">;
+
+def InvalidatedIteratorChecker : Checker<"InvalidatedIterator">,
+  HelpText<"Check for use of invalidated iterators">,
+  DescFile<"IteratorChecker.cpp">;
+
 def MisusedMovedObjectChecker: Checker<"MisusedMovedObject">,
      HelpText<"Method calls on a moved-from object and copying a moved-from "
               "object will be reported">,
      DescFile<"MisusedMovedObjectChecker.cpp">;
 
-def IteratorPastEndChecker : Checker<"IteratorPastEnd">,
-  HelpText<"Check iterators used past end">,
-  DescFile<"IteratorPastEndChecker.cpp">;
-
 } // end: "alpha.cplusplus"
 
 
 //===----------------------------------------------------------------------===//
 // Valist checkers.
 //===----------------------------------------------------------------------===//
 
 let ParentPackage = Valist in {

lib/StaticAnalyzer/Checkers/CMakeLists.txt

add_clang_library(clangStaticAnalyzerCheckers
   DivZeroChecker.cpp
   DynamicTypePropagation.cpp
   DynamicTypeChecker.cpp
   ExprInspectionChecker.cpp
   FixedAddressChecker.cpp
   GenericTaintChecker.cpp
   GTestChecker.cpp
   IdenticalExprChecker.cpp
-  IteratorPastEndChecker.cpp
+  IteratorChecker.cpp
   IvarInvalidationChecker.cpp
   LLVMConventionsChecker.cpp
   LocalizationChecker.cpp
   MacOSKeychainAPIChecker.cpp
   MacOSXAPIChecker.cpp
   MallocChecker.cpp
   MallocOverflowSecurityChecker.cpp
   MallocSizeofChecker.cpp

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

+//===-- IteratorChecker.cpp ---------------------------------------*- C++ -*--//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Defines a checker for using iterators outside their range (past end). Usage
+// means here dereferencing, incrementing etc.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ClangSACheckers.h"
+#include "clang/AST/DeclTemplate.h"
+#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
+#include "clang/StaticAnalyzer/Core/Checker.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+
+#include <utility>
+
+using namespace clang;
+using namespace ento;
+
+namespace {
+
+struct IteratorPosition {
+private:
+  const MemRegion *Cont;
+  bool Valid;
+  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);
+  }
+};
+
+typedef llvm::PointerUnion<const MemRegion *, SymbolRef> RegionOrSymbol;
+
+struct ContainerData {
+private:
+  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);
+  }
+};
+
+struct IteratorComparison {
+private:
+  RegionOrSymbol Left, Right;
+  bool Equality;
+
+public:
+  IteratorComparison(RegionOrSymbol L, RegionOrSymbol R, bool Eq)
+      : Left(L), Right(R), Equality(Eq) {}
+
+  RegionOrSymbol getLeft() const { return Left; }
+  RegionOrSymbol getRight() const { return Right; }
+  bool isEquality() const { return Equality; }
+  bool operator==(const IteratorComparison &X) const {
+    return Left == X.Left && Right == X.Right && Equality == X.Equality;
+  }
+  bool operator!=(const IteratorComparison &X) const {
+    return Left != X.Left || Right != X.Right || Equality != X.Equality;
+  }
+  void Profile(llvm::FoldingSetNodeID &ID) const { ID.AddInteger(Equality); }
+};
+
+class IteratorChecker
+    : public Checker<check::PreCall, check::PostCall,
+                     check::PreStmt<CXXConstructExpr>,
+                     check::PreStmt<CXXOperatorCallExpr>,
+                     check::PostStmt<MaterializeTemporaryExpr>, check::Bind,
+                     check::BeginFunction, check::LiveSymbols,
+                     check::DeadSymbols, eval::Assume, eval::Call> {
+  mutable IdentifierInfo *II_find = nullptr, *II_find_end = nullptr,
+                         *II_find_first_of = nullptr, *II_find_if = nullptr,
+                         *II_find_if_not = nullptr, *II_lower_bound = nullptr,
+                         *II_upper_bound = nullptr, *II_search = nullptr,
+                         *II_search_n = nullptr;
+
+  std::unique_ptr<BugType> OutOfRangeBugType;
+  std::unique_ptr<BugType> MismatchedBugType;
+  std::unique_ptr<BugType> InvalidatedBugType;
+
+  void handleComparison(CheckerContext &C, const SVal &RetVal, const SVal &LVal,
+                        const SVal &RVal, OverloadedOperatorKind Op) const;
+  void verifyAccess(CheckerContext &C, const SVal &Val) const;
+  void verifyDereference(CheckerContext &C, const SVal &Val) const;
+  void handleIncrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter,
+                       bool Postfix) const;
+  void handleDecrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter,
+                       bool Postfix) const;
+  void handleRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op,
+                              const SVal &RetVal, const SVal &LHS,
+                              const SVal &RHS) const;
+  void handleBegin(CheckerContext &C, const Expr *CE, const SVal &RetVal,
+                   const SVal &Cont) const;
+  void handleEnd(CheckerContext &C, const Expr *CE, const SVal &RetVal,
+                 const SVal &Cont) const;
+  void assignToContainer(CheckerContext &C, const Expr *CE, const SVal &RetVal,
+                         const MemRegion *Cont) const;
+  void handleAssign(CheckerContext &C, const SVal &Cont,
+                    const Expr *CE = nullptr,
+                    const SVal &OldCont = UndefinedVal()) const;
+  void handleClear(CheckerContext &C, const SVal &Cont) const;
+  void handlePushBack(CheckerContext &C, const SVal &Cont) const;
+  void handlePopBack(CheckerContext &C, const SVal &Cont) const;
+  void handlePushFront(CheckerContext &C, const SVal &Cont) const;
+  void handlePopFront(CheckerContext &C, const SVal &Cont) const;
+  void handleInsert(CheckerContext &C, const SVal &Iter) const;
+  void handleErase(CheckerContext &C, const SVal &Iter) const;
+  void handleErase(CheckerContext &C, const SVal &Iter1,
+                   const SVal &Iter2) const;
+  void handleEraseAfter(CheckerContext &C, const SVal &Iter) const;
+  void handleEraseAfter(CheckerContext &C, const SVal &Iter1,
+                        const SVal &Iter2) const;
+  void verifyRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op,
+                              const SVal &RetVal, const SVal &LHS,
+                              const SVal &RHS) const;
+  void verifyMatch(CheckerContext &C, const SVal &Iter,
+                   const MemRegion *Cont) const;
+  void verifyMatch(CheckerContext &C, const SVal &Iter1,
+                   const SVal &Iter2) const;
+  bool evalFind(CheckerContext &C, const CallExpr *CE) const;
+  bool evalFindEnd(CheckerContext &C, const CallExpr *CE) const;
+  bool evalFindFirstOf(CheckerContext &C, const CallExpr *CE) const;
+  bool evalFindIf(CheckerContext &C, const CallExpr *CE) const;
+  bool evalFindIfNot(CheckerContext &C, const CallExpr *CE) const;
+  bool evalLowerBound(CheckerContext &C, const CallExpr *CE) const;
+  bool evalUpperBound(CheckerContext &C, const CallExpr *CE) const;
+  bool evalSearch(CheckerContext &C, const CallExpr *CE) const;
+  bool evalSearchN(CheckerContext &C, const CallExpr *CE) const;
+  void Find(CheckerContext &C, const CallExpr *CE) const;
+
+  void reportOutOfRangeBug(const StringRef &Message, const SVal &Val,
+                           CheckerContext &C, ExplodedNode *ErrNode) const;
+  void reportMismatchedBug(const StringRef &Message, const SVal &Val,
+                           CheckerContext &C, ExplodedNode *ErrNode) const;
+  void reportInvalidatedBug(const StringRef &Message, const SVal &Val,
+                            CheckerContext &C, ExplodedNode *ErrNode) const;
+
+  void initIdentifiers(ASTContext &Ctx) const;
+
+public:
+  IteratorChecker();
+
+  enum CheckKind {
+    CK_IteratorRangeChecker,
+    CK_MismatchedIteratorChecker,
+    CK_InvalidatedIteratorChecker,
+    CK_NumCheckKinds
+  };
+
+  DefaultBool ChecksEnabled[CK_NumCheckKinds];
+  CheckName CheckNames[CK_NumCheckKinds];
+
+  void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
+  void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
+  void checkPreStmt(const CXXConstructExpr *CCE, CheckerContext &C) const;
+  void checkPreStmt(const CXXOperatorCallExpr *COCE, CheckerContext &C) const;
+  void checkBind(SVal Loc, SVal Val, const Stmt *S, CheckerContext &C) const;
+  void checkBeginFunction(CheckerContext &C) const;
+  void checkPostStmt(const CXXConstructExpr *CCE, CheckerContext &C) const;
+  void checkPostStmt(const DeclStmt *DS, CheckerContext &C) const;
+  void checkPostStmt(const MaterializeTemporaryExpr *MTE,
+                     CheckerContext &C) const;
+  void checkLiveSymbols(ProgramStateRef State, SymbolReaper &SR) const;
+  void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
+  ProgramStateRef evalAssume(ProgramStateRef State, SVal Cond,
+                             bool Assumption) const;
+  bool evalCall(const CallExpr *CE, 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)
+
+REGISTER_MAP_WITH_PROGRAMSTATE(IteratorComparisonMap, const SymExpr *,
+                               IteratorComparison)
+
+#define INIT_ID(Id)                                                            \
+  if (!II_##Id)                                                                \
+  II_##Id = &Ctx.Idents.get(#Id)
+
+static llvm::APSInt Zero = llvm::APSInt::get(0);
+static llvm::APSInt One = llvm::APSInt::get(1);
+
+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(const MemRegion *Reg);
+bool frontModifiable(const MemRegion *Reg);
+bool backModifiable(const MemRegion *Reg);
+BinaryOperator::Opcode getOpcode(const SymExpr *SE);
+const RegionOrSymbol getRegionOrSymbol(const SVal &Val);
+const ProgramStateRef processComparison(ProgramStateRef State,
+                                        RegionOrSymbol LVal,
+                                        RegionOrSymbol RVal, bool Equal);
+const ProgramStateRef saveComparison(ProgramStateRef State,
+                                     const SymExpr *Condition, const SVal &LVal,
+                                     const SVal &RVal, bool Eq);
+const IteratorComparison *loadComparison(ProgramStateRef State,
+                                         const SymExpr *Condition);
+SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont);
+SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont);
+ProgramStateRef createContainerBegin(ProgramStateRef State,
+                                     const MemRegion *Cont,
+                                     const SymbolRef Sym);
+ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont,
+                                   const SymbolRef Sym);
+const IteratorPosition *getIteratorPosition(ProgramStateRef State,
+                                            const SVal &Val);
+const IteratorPosition *getIteratorPosition(ProgramStateRef State,
+                                            RegionOrSymbol RegOrSym);
+ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val,
+                                    const IteratorPosition &Pos);
+ProgramStateRef setIteratorPosition(ProgramStateRef State,
+                                    RegionOrSymbol RegOrSym,
+                                    const IteratorPosition &Pos);
+ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val);
+ProgramStateRef adjustIteratorPosition(ProgramStateRef State,
+                                       RegionOrSymbol RegOrSym,
+                                       const IteratorPosition &Pos, bool Equal);
+ProgramStateRef relateIteratorPositions(ProgramStateRef State,
+                                        const IteratorPosition &Pos1,
+                                        const IteratorPosition &Pos2,
+                                        bool Equal);
+ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State,
+                                               const MemRegion *Cont);
+ProgramStateRef
+invalidateAllIteratorPositionsExcept(ProgramStateRef State,
+                                     const MemRegion *Cont, SymbolRef Offset,
+                                     BinaryOperator::Opcode Opc);
+ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
+                                            SymbolRef Offset,
+                                            BinaryOperator::Opcode Opc);
+ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
+                                            SymbolRef Offset1,
+                                            BinaryOperator::Opcode Opc1,
+                                            SymbolRef Offset2,
+                                            BinaryOperator::Opcode Opc2);
+ProgramStateRef reassignAllIteratorPositions(ProgramStateRef State,
+                                             const MemRegion *Cont,
+                                             const MemRegion *NewCont);
+ProgramStateRef reassignAllIteratorPositionsUnless(ProgramStateRef State,
+                                                   const MemRegion *Cont,
+                                                   const MemRegion *NewCont,
+                                                   SymbolRef Offset,
+                                                   BinaryOperator::Opcode Opc);
+ProgramStateRef replaceSymbolInIteratorPositionsIf(
+    ProgramStateRef State, SymbolManager &SymMgr, SymbolRef OldSym,
+    SymbolRef NewSym, SymbolRef CondSym, BinaryOperator::Opcode Opc);
+const ContainerData *getContainerData(ProgramStateRef State,
+                                      const MemRegion *Cont);
+ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont,
+                                 const ContainerData &CData);
+bool isOutOfRange(ProgramStateRef State, const IteratorPosition &Pos);
+bool isZero(ProgramStateRef State, const NonLoc &Val);
+SymbolRef compact(SymbolManager &SymMgr, const SymbolRef Sym);
+std::pair<SymbolRef, llvm::APSInt>
+createDifference(SymbolManager &SymMgr, SymbolRef Sym1, SymbolRef Sym2);
+const llvm::APSInt *getDifference(ProgramStateRef State, SymbolRef Sym1,
+                                  SymbolRef Sym2);
+} // namespace
+
+IteratorChecker::IteratorChecker() {
+  OutOfRangeBugType.reset(
+      new BugType(this, "Iterator of out Range", "Misuse of STL APIs"));
+  OutOfRangeBugType->setSuppressOnSink(true);
+  MismatchedBugType.reset(
+      new BugType(this, "Iterator(s) mismatched", "Misuse of STL APIs"));
+  MismatchedBugType->setSuppressOnSink(true);
+  InvalidatedBugType.reset(
+      new BugType(this, "Iterator invalidated", "Misuse of STL APIs"));
+  InvalidatedBugType->setSuppressOnSink(true);
+}
+
+void IteratorChecker::checkPreCall(const CallEvent &Call,
+                                   CheckerContext &C) const {
+  // Check for out of range access or access of invalidated position and
+  // iterator mismatches
+  const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
+  if (!Func)
+    return;
+
+  if (Func->isOverloadedOperator()) {
+    if (ChecksEnabled[CK_InvalidatedIteratorChecker] &&
+        isAccessOperator(Func->getOverloadedOperator())) {
+      // Check for any kind of access of invalidated iterator positions
+      if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
+        verifyAccess(C, InstCall->getCXXThisVal());
+      } else {
+        verifyAccess(C, Call.getArgSVal(0));
+      }
+    }
+    if (ChecksEnabled[CK_IteratorRangeChecker] &&
+        isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) {
+      if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
+        // Check for out-of-range incrementions and decrementions
+        if (Call.getNumArgs() >= 1) {
+          verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(),
+                                 Call.getReturnValue(),
+                                 InstCall->getCXXThisVal(), Call.getArgSVal(0));
+        }
+      } else {
+        if (Call.getNumArgs() >= 2) {
+          verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(),
+                                 Call.getReturnValue(), Call.getArgSVal(0),
+                                 Call.getArgSVal(1));
+        }
+      }
+    } else if (ChecksEnabled[CK_IteratorRangeChecker] &&
+               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)) {
+    // 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.
+
+    if (!ChecksEnabled[CK_MismatchedIteratorChecker])
+      return;
+
+    const auto *Templ = Func->getPrimaryTemplate();
+    if (!Templ)
+      return;
+
+    const auto *TParams = Templ->getTemplateParameters();
+    const auto *TArgs = Func->getTemplateSpecializationArgs();
+
+    for (auto i = 0U; i < TParams->size(); ++i) {
+      const auto *TPDecl = dyn_cast<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 (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 IteratorChecker::checkPostCall(const CallEvent &Call,
+                                    CheckerContext &C) const {
+  // Record new iterator positions and iterator position changes
+  const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
+  if (!Func)
+    return;
+
+  if (Func->isOverloadedOperator()) {
+    const auto Op = Func->getOverloadedOperator();
+    if (isAssignmentOperator(Op)) {
+      const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call);
+      if (Func->getParamDecl(0)->getType()->isRValueReferenceType()) {
+        handleAssign(C, InstCall->getCXXThisVal(), Call.getOriginExpr(),
+                     Call.getArgSVal(0));
+      } else {
+        handleAssign(C, InstCall->getCXXThisVal());
+      }
+    } else if (isSimpleComparisonOperator(Op)) {
+      if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
+        handleComparison(C, Call.getReturnValue(), InstCall->getCXXThisVal(),
+                         Call.getArgSVal(0), Op);
+      } else {
+        handleComparison(C, Call.getReturnValue(), Call.getArgSVal(0),
+                         Call.getArgSVal(1), Op);
+      }
+    } else if (isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) {
+      if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
+        if (Call.getNumArgs() >= 1) {
+          handleRandomIncrOrDecr(C, Func->getOverloadedOperator(),
+                                 Call.getReturnValue(),
+                                 InstCall->getCXXThisVal(), Call.getArgSVal(0));
+        }
+      } else {
+        if (Call.getNumArgs() >= 2) {
+          handleRandomIncrOrDecr(C, Func->getOverloadedOperator(),
+                                 Call.getReturnValue(), Call.getArgSVal(0),
+                                 Call.getArgSVal(1));
+        }
+      }
+    } else if (isIncrementOperator(Func->getOverloadedOperator())) {
+      if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
+        handleIncrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(),
+                        Call.getNumArgs());
+      } else {
+        handleIncrement(C, Call.getReturnValue(), Call.getArgSVal(0),
+                        Call.getNumArgs());
+      }
+    } else if (isDecrementOperator(Func->getOverloadedOperator())) {
+      if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
+        handleDecrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(),
+                        Call.getNumArgs());
+      } else {
+        handleDecrement(C, Call.getReturnValue(), Call.getArgSVal(0),
+                        Call.getNumArgs());
+      }
+    }
+  } else {
+    if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
+      if (isAssignCall(Func)) {
+        handleAssign(C, InstCall->getCXXThisVal());
+      } else if (isClearCall(Func)) {
+        handleClear(C, InstCall->getCXXThisVal());
+      } else if (isPushBackCall(Func) || isEmplaceBackCall(Func)) {
+        handlePushBack(C, InstCall->getCXXThisVal());
+      } else if (isPopBackCall(Func)) {
+        handlePopBack(C, InstCall->getCXXThisVal());
+      } else if (isPushFrontCall(Func) || isEmplaceFrontCall(Func)) {
+        handlePushFront(C, InstCall->getCXXThisVal());
+      } else if (isPopFrontCall(Func)) {
+        handlePopFront(C, InstCall->getCXXThisVal());
+      } else if (isInsertCall(Func) || isEmplaceCall(Func)) {
+        handleInsert(C, Call.getArgSVal(0));
+      } else if (isEraseCall(Func)) {
+        if (Call.getNumArgs() == 1) {
+          handleErase(C, Call.getArgSVal(0));
+        } else if (Call.getNumArgs() == 2) {
+          handleErase(C, Call.getArgSVal(0), Call.getArgSVal(1));
+        }
+      } else if (isEraseAfterCall(Func)) {
+        if (Call.getNumArgs() == 1) {
+          handleEraseAfter(C, Call.getArgSVal(0));
+        } else if (Call.getNumArgs() == 2) {
+          handleEraseAfter(C, Call.getArgSVal(0), Call.getArgSVal(1));
+        }
+      }
+    }
+
+    const auto *OrigExpr = Call.getOriginExpr();
+    if (!OrigExpr)
+      return;
+
+    if (!isIteratorType(Call.getResultType()))
+      return;
+
+    auto State = C.getState();
+    // Already bound to container?
+    if (getIteratorPosition(State, Call.getReturnValue()))
+      return;
+
+    if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
+      if (isBeginCall(Func)) {
+        handleBegin(C, OrigExpr, Call.getReturnValue(),
+                    InstCall->getCXXThisVal());
+        return;
+      } else if (isEndCall(Func)) {
+        handleEnd(C, OrigExpr, Call.getReturnValue(),
+                  InstCall->getCXXThisVal());
+        return;
+      }
+    }
+
+    // Copy-like and move constructors
+    if (isa<CXXConstructorCall>(&Call) && Call.getNumArgs() == 1) {
+      if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(0))) {
+        State = setIteratorPosition(State, Call.getReturnValue(), *Pos);
+        if (cast<CXXConstructorDecl>(Func)->isMoveConstructor()) {
+          State = removeIteratorPosition(State, Call.getArgSVal(0));
+        }
+        C.addTransition(State);
+        return;
+      }
+    }
+
+    // Assumption: if return value is an iterator which is not yet bound to a
+    //             container, then look for the first iterator argument, and
+    //             bind the return value to the same container. This approach
+    //             works for STL algorithms.
+    for (unsigned i = 0; i < Call.getNumArgs(); ++i) {
+      if (isIteratorType(Call.getArgExpr(i)->getType())) {
+        if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(i))) {
+          assignToContainer(C, OrigExpr, Call.getReturnValue(),
+                            Pos->getContainer());
+          return;
+        }
+      }
+    }
+  }
+}
+
+void IteratorChecker::checkPreStmt(const CXXConstructExpr *CCE,
+                                   CheckerContext &C) const {
+  // Check match of first-last iterator pair in a constructor of a container
+  if (CCE->getNumArgs() < 2)
+    return;
+
+  const auto *Ctr = CCE->getConstructor();
+  if (Ctr->getNumParams() < 2)
+    return;
+
+  if (Ctr->getParamDecl(0)->getName() != "first" ||
+      Ctr->getParamDecl(1)->getName() != "last")
+    return;
+
+  if (!isIteratorType(CCE->getArg(0)->getType()) ||
+      !isIteratorType(CCE->getArg(1)->getType()))
+    return;
+
+  auto State = C.getState();
+  const auto *LCtx = C.getPredecessor()->getLocationContext();
+
+  verifyMatch(C, State->getSVal(CCE->getArg(0), LCtx),
+              State->getSVal(CCE->getArg(1), LCtx));
+}
+
+void IteratorChecker::checkPreStmt(const CXXOperatorCallExpr *COCE,
+                                   CheckerContext &C) const {
+  const auto *ThisExpr = COCE->getArg(0);
+
+  auto State = C.getState();
+  const auto *LCtx = C.getLocationContext();
+
+  const auto CurrentThis = State->getSVal(ThisExpr, LCtx);
+  if (const auto *Reg = CurrentThis.getAsRegion()) {
+    if (!Reg->getAs<CXXTempObjectRegion>())
+      return;
+    const auto OldState = C.getPredecessor()->getFirstPred()->getState();
+    const auto OldThis = OldState->getSVal(ThisExpr, LCtx);
+    const auto *Pos = getIteratorPosition(OldState, OldThis);
+    if (!Pos)
+      return;
+    State = setIteratorPosition(State, CurrentThis, *Pos);
+    C.addTransition(State);
+  }
+}
+
+void IteratorChecker::checkBind(SVal Loc, SVal Val, const Stmt *S,
+                                CheckerContext &C) const {
+  auto State = C.getState();
+  const auto *Pos = getIteratorPosition(State, Val);
+  if (Pos) {
+    State = setIteratorPosition(State, Loc, *Pos);
+    C.addTransition(State);
+  } else {
+    const auto *OldPos = getIteratorPosition(State, Loc);
+    if (OldPos) {
+      State = removeIteratorPosition(State, Loc);
+      C.addTransition(State);
+    }
+  }
+}
+
+void IteratorChecker::checkBeginFunction(CheckerContext &C) const {
+  // Copy state of iterator arguments to iterator parameters
+  auto State = C.getState();
+  const auto *LCtx = C.getLocationContext();
+
+  const auto *Site = cast<StackFrameContext>(LCtx)->getCallSite();
+  if (!Site)
+    return;
+
+  const auto *FD = dyn_cast<FunctionDecl>(LCtx->getDecl());
+  if (!FD)
+    return;
+
+  const auto *CE = dyn_cast<CallExpr>(Site);
+  if (!CE)
+    return;
+
+  bool Change = false;
+  int idx = 0;
+  for (const auto P : FD->parameters()) {
+    auto Param = State->getLValue(P, LCtx);
+    auto Arg = State->getSVal(CE->getArg(idx++), LCtx->getParent());
+    const auto *Pos = getIteratorPosition(State, Arg);
+    if (!Pos)
+      continue;
+    State = setIteratorPosition(State, Param, *Pos);
+    Change = true;
+  }
+  if (Change) {
+    C.addTransition(State);
+  }
+}
+
+void IteratorChecker::checkPostStmt(const MaterializeTemporaryExpr *MTE,
+                                    CheckerContext &C) const {
+  /* Transfer iterator state for to temporary objects */
+  auto State = C.getState();
+  const auto *LCtx = C.getLocationContext();
+  const auto *Pos =
+      getIteratorPosition(State, State->getSVal(MTE->GetTemporaryExpr(), LCtx));
+  if (!Pos)
+    return;
+  State = setIteratorPosition(State, State->getSVal(MTE, LCtx), *Pos);
+  C.addTransition(State);
+}
+
+void IteratorChecker::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 Pos = Reg.second;
+    SR.markLive(Pos.getOffset());
+  }
+
+  auto SymbolMap = State->get<IteratorSymbolMap>();
+  for (const auto Sym : SymbolMap) {
+    const auto Pos = Sym.second;
+    SR.markLive(Pos.getOffset());
+  }
+
+  auto ContMap = State->get<ContainerMap>();
+  for (const auto Cont : ContMap) {
+    const auto CData = Cont.second;
+    if (CData.getBegin()) {
+      SR.markLive(CData.getBegin());
+    }
+    if (CData.getEnd()) {
+      SR.markLive(CData.getEnd());
+    }
+  }
+}
+
+void IteratorChecker::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)) {
+      State = State->remove<IteratorRegionMap>(Reg.first);
+    }
+  }
+
+  auto SymbolMap = State->get<IteratorSymbolMap>();
+  for (const auto Sym : SymbolMap) {
+    if (!SR.isLive(Sym.first)) {
+      State = State->remove<IteratorSymbolMap>(Sym.first);
+    }
+  }
+
+  auto ContMap = State->get<ContainerMap>();
+  for (const auto Cont : ContMap) {
+    if (!SR.isLiveRegion(Cont.first)) {
+      State = State->remove<ContainerMap>(Cont.first);
+    }
+  }
+
+  auto ComparisonMap = State->get<IteratorComparisonMap>();
+  for (const auto Comp : ComparisonMap) {
+    if (!SR.isLive(Comp.first)) {
+      State = State->remove<IteratorComparisonMap>(Comp.first);
+    }
+  }
+}
+
+ProgramStateRef IteratorChecker::evalAssume(ProgramStateRef State, SVal Cond,
+                                            bool Assumption) const {
+  // Load recorded comparison and transfer iterator state between sides
+  // according to comparison operator and assumption
+  const auto *SE = Cond.getAsSymExpr();
+  if (!SE)
+    return State;
+
+  auto Opc = getOpcode(SE);
+  if (Opc != BO_EQ && Opc != BO_NE)
+    return State;
+
+  bool Negated = false;
+  const auto *Comp = loadComparison(State, SE);
+  if (!Comp) {
+    // Try negated comparison, which is a SymExpr to 0 integer comparison
+    const auto *SIE = dyn_cast<SymIntExpr>(SE);
+    if (!SIE)
+      return State;
+
+    if (SIE->getRHS() != 0)
+      return State;
+
+    SE = SIE->getLHS();
+    Negated = SIE->getOpcode() == BO_EQ; // Equal to zero means negation
+    Opc = getOpcode(SE);
+    if (Opc != BO_EQ && Opc != BO_NE)
+      return State;
+
+    Comp = loadComparison(State, SE);
+    if (!Comp)
+      return State;
+  }
+
+  return processComparison(State, Comp->getLeft(), Comp->getRight(),
+                           (Comp->isEquality() == Assumption) != Negated);
+}
+
+// FIXME: Evaluation of these STL calls should be moved to StdCLibraryFunctions
+//       checker (see patch r284960) or another similar checker for C++ STL
+//       functions (e.g. StdCXXLibraryFunctions or StdCppLibraryFunctions).
+bool IteratorChecker::evalCall(const CallExpr *CE, CheckerContext &C) const {
+  const FunctionDecl *FD = C.getCalleeDecl(CE);
+  if (!FD)
+    return false;
+
+  ASTContext &Ctx = C.getASTContext();
+  initIdentifiers(Ctx);
+
+  if (FD->getKind() == Decl::Function) {
+    if (FD->isInStdNamespace()) {
+      if (FD->getIdentifier() == II_find) {
+        return evalFind(C, CE);
+      } else if (FD->getIdentifier() == II_find_end) {
+        return evalFindEnd(C, CE);
+      } else if (FD->getIdentifier() == II_find_first_of) {
+        return evalFindFirstOf(C, CE);
+      } else if (FD->getIdentifier() == II_find_if) {
+        return evalFindIf(C, CE);
+      } else if (FD->getIdentifier() == II_find_if_not) {
+        return evalFindIfNot(C, CE);
+      } else if (FD->getIdentifier() == II_upper_bound) {
+        return evalUpperBound(C, CE);
+      } else if (FD->getIdentifier() == II_lower_bound) {
+        return evalLowerBound(C, CE);
+      } else if (FD->getIdentifier() == II_search) {
+        return evalSearch(C, CE);
+      } else if (FD->getIdentifier() == II_search_n) {
+        return evalSearchN(C, CE);
+      }
+    }
+  }
+
+  return false;
+}
+
+void IteratorChecker::handleComparison(CheckerContext &C, 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();
+  if (const auto *Condition = RetVal.getAsSymbolicExpression()) {
+    const auto *LPos = getIteratorPosition(State, LVal);
+    const auto *RPos = getIteratorPosition(State, RVal);
+    if (!LPos && !RPos)
+      return;
+    State = saveComparison(State, Condition, LVal, RVal, Op == OO_EqualEqual);
+    C.addTransition(State);
+  } else if (const auto TruthVal = RetVal.getAs<nonloc::ConcreteInt>()) {
+    if ((State = processComparison(
+             State, getRegionOrSymbol(LVal), getRegionOrSymbol(RVal),
+             (Op == OO_EqualEqual) == (TruthVal->getValue() != 0)))) {
+      C.addTransition(State);
+    } else {
+      C.generateSink(State, C.getPredecessor());
+    }
+  }
+}
+
+void IteratorChecker::verifyDereference(CheckerContext &C,
+                                        const SVal &Val) const {
+  auto State = C.getState();
+  const auto *Pos = getIteratorPosition(State, Val);
+  if (Pos && isOutOfRange(State, *Pos)) {
+    // If I do not put a tag here, some range tests will fail
+    static CheckerProgramPointTag Tag("IteratorRangeChecker",
+                                      "IteratorOutOfRange");
+    auto *N = C.generateNonFatalErrorNode(State, &Tag);
+    if (!N) {
+      return;
+    }
+    reportOutOfRangeBug("Iterator accessed outside of its range.", Val, C, N);
+  }
+}
+
+void IteratorChecker::verifyAccess(CheckerContext &C, const SVal &Val) const {
+  auto State = C.getState();
+  const auto *Pos = getIteratorPosition(State, Val);
+  if (Pos && !Pos->isValid()) {
+    // If I do not put a tag here, some invalidation tests will fail
+    static CheckerProgramPointTag Tag("InvalidatedIteratorChecker",
+                                      "InvalidatedIterator");
+    auto *N = C.generateNonFatalErrorNode(State, &Tag);
+    if (!N) {
+      return;
+    }
+    reportInvalidatedBug("Invalidated iterator accessed.", Val, C, N);
+  }
+}
+
+void IteratorChecker::handleIncrement(CheckerContext &C, const SVal &RetVal,
+                                      const SVal &Iter, bool Postfix) const {
+  // Increment the symbolic expressions which represents the position of the
+  // iterator
+  auto State = C.getState();
+  const auto *Pos = getIteratorPosition(State, Iter);
+  if (Pos) {
+    auto &SymMgr = C.getSymbolManager();
+    const auto oldOffset = Pos->getOffset();
+    auto newOffset =
+        compact(SymMgr, SymMgr.getSymIntExpr(oldOffset, BO_Add, One,
+                                             SymMgr.getType(oldOffset)));
+    auto newPos = Pos->setTo(newOffset);
+    State = setIteratorPosition(State, Iter, newPos);
+    State = setIteratorPosition(State, RetVal, Postfix ? *Pos : newPos);
+    C.addTransition(State);
+  }
+}
+
+void IteratorChecker::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();
+  const auto *Pos = getIteratorPosition(State, Iter);
+  if (Pos) {
+    auto &SymMgr = C.getSymbolManager();
+    const auto oldOffset = Pos->getOffset();
+    auto newOffset =
+        compact(SymMgr, SymMgr.getSymIntExpr(oldOffset, BO_Sub, One,
+                                             SymMgr.getType(oldOffset)));
+    auto newPos = Pos->setTo(newOffset);
+    State = setIteratorPosition(State, Iter, newPos);
+    State = setIteratorPosition(State, RetVal, Postfix ? *Pos : newPos);
+    C.addTransition(State);
+  }
+}
+
+void IteratorChecker::handleRandomIncrOrDecr(CheckerContext &C,
+                                             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 &SymMgr = C.getSymbolManager();
+  auto BinOp = (Op == OO_Plus || Op == OO_PlusEqual) ? BO_Add : BO_Sub;
+  const auto oldOffset = Pos->getOffset();
+  SymbolRef newOffset;
+  if (const auto intValue = value->getAs<nonloc::ConcreteInt>()) {
+    // For concrete integers we can calculate the new position
+    newOffset = compact(
+        SymMgr, SymMgr.getSymIntExpr(oldOffset, BinOp, intValue->getValue(),
+                                     SymMgr.getType(oldOffset)));
+  } else {
+    // For other symbols create a new symbol to keep expressions simple
+    const auto &LCtx = C.getLocationContext();
+    newOffset = SymMgr.conjureSymbol(nullptr, LCtx, SymMgr.getType(oldOffset),
+                                     C.blockCount());
+  }
+  auto newPos = Pos->setTo(newOffset);
+  auto &TgtVal = (Op == OO_PlusEqual || Op == OO_MinusEqual) ? LHS : RetVal;
+  State = setIteratorPosition(State, TgtVal, newPos);
+  C.addTransition(State);
+}
+
+void IteratorChecker::verifyRandomIncrOrDecr(CheckerContext &C,
+                                             OverloadedOperatorKind Op,
+                                             const SVal &RetVal,
+                                             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 || !isOutOfRange(State, *Pos))
+    return;
+
+  auto value = RHS;
+  if (auto loc = RHS.getAs<Loc>()) {
+    value = State->getRawSVal(*loc);
+  }
+
+  // Incremention or decremention by 0 is never bug
+  if (isZero(State, value.castAs<NonLoc>()))
+    return;
+
+  auto &SymMgr = C.getSymbolManager();
+  auto BinOp = (Op == OO_Plus || Op == OO_PlusEqual) ? BO_Add : BO_Sub;
+  const auto oldOffset = Pos->getOffset();
+  const auto intValue = value.getAs<nonloc::ConcreteInt>();
+  if (!intValue)
+    return;
+
+  SymbolRef newOffset = compact(
+      SymMgr, SymMgr.getSymIntExpr(oldOffset, BinOp, intValue->getValue(),
+                                   SymMgr.getType(oldOffset)));
+  auto newPos = Pos->setTo(newOffset);
+
+  // If out of range, the only valid operation is to step into the range
+  if (isOutOfRange(State, newPos)) {
+    auto *N = C.generateNonFatalErrorNode(State);
+    if (!N)
+      return;
+    reportOutOfRangeBug("Iterator accessed past its end.", LHS, C, N);
+  }
+}
+
+void IteratorChecker::verifyMatch(CheckerContext &C, const SVal &Iter,
+                                  const MemRegion *Cont) const {
+  // Verify match between a container and the container of an iterator
+  while (const auto *CBOR = Cont->getAs<CXXBaseObjectRegion>()) {
+    Cont = CBOR->getSuperRegion();
+  }
+
+  auto State = C.getState();
+  const auto *Pos = getIteratorPosition(State, Iter);
+  if (Pos && Pos->getContainer() != Cont) {
+    auto *N = C.generateNonFatalErrorNode(State);
+    if (!N) {
+      return;
+    }
+    reportMismatchedBug("Iterator access mismatched.", Iter, C, N);
+  }
+}
+
+void IteratorChecker::verifyMatch(CheckerContext &C, const SVal &Iter1,
+                                  const SVal &Iter2) const {
+  // Verify match between the containers of two iterators
+  auto State = C.getState();
+  const auto *Pos1 = getIteratorPosition(State, Iter1);
+  const auto *Pos2 = getIteratorPosition(State, Iter2);
+  if (Pos1 && Pos2 && Pos1->getContainer() != Pos2->getContainer()) {
+    // If I do not put a tag here, the comparison test will fail
+    static CheckerProgramPointTag Tag("MismatchedIteratorChecker",
+                                      "MismatchedIterator");
+    auto *N = C.generateNonFatalErrorNode(State, &Tag);
+    if (!N) {
+      return;
+    }
+    reportMismatchedBug("Iterator access mismatched.", Iter1, C, N);
+  }
+}
+
+void IteratorChecker::handleBegin(CheckerContext &C, const Expr *CE,
+                                  const SVal &RetVal, const SVal &Cont) const {
+  const auto *ContReg = Cont.getAsRegion();
+  if (!ContReg)
+    return;
+
+  while (const auto *CBOR = ContReg->getAs<CXXBaseObjectRegion>()) {
+    ContReg = CBOR->getSuperRegion();
+  }
+
+  // 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) {
+    auto &SymMgr = C.getSymbolManager();
+    BeginSym = SymMgr.conjureSymbol(CE, C.getLocationContext(),
+                                    C.getASTContext().LongTy, C.blockCount());
+    State = createContainerBegin(State, ContReg, BeginSym);
+  }
+  State = setIteratorPosition(State, RetVal,
+                              IteratorPosition::getPosition(ContReg, BeginSym));
+  C.addTransition(State);
+}
+
+void IteratorChecker::handleEnd(CheckerContext &C, const Expr *CE,
+                                const SVal &RetVal, const SVal &Cont) const {
+  const auto *ContReg = Cont.getAsRegion();
+  if (!ContReg)
+    return;
+
+  while (const auto *CBOR = ContReg->getAs<CXXBaseObjectRegion>()) {
+    ContReg = CBOR->getSuperRegion();
+  }
+
+  // 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) {
+    auto &SymMgr = C.getSymbolManager();
+    EndSym = SymMgr.conjureSymbol(CE, C.getLocationContext(),
+                                  C.getASTContext().LongTy, C.blockCount());
+    State = createContainerEnd(State, ContReg, EndSym);
+  }
+  State = setIteratorPosition(State, RetVal,
+                              IteratorPosition::getPosition(ContReg, EndSym));
+  C.addTransition(State);
+}
+
+void IteratorChecker::assignToContainer(CheckerContext &C, const Expr *CE,
+                                        const SVal &RetVal,
+                                        const MemRegion *Cont) const {
+  while (const auto *CBOR = Cont->getAs<CXXBaseObjectRegion>()) {
+    Cont = CBOR->getSuperRegion();
+  }
+
+  auto State = C.getState();
+  auto &SymMgr = C.getSymbolManager();
+  auto Sym = SymMgr.conjureSymbol(CE, C.getLocationContext(),
+                                  C.getASTContext().LongTy, C.blockCount());
+  State = setIteratorPosition(State, RetVal,
+                              IteratorPosition::getPosition(Cont, Sym));
+  C.addTransition(State);
+}
+
+void IteratorChecker::handleAssign(CheckerContext &C, const SVal &Cont,
+                                   const Expr *CE, const SVal &OldCont) const {
+  const auto *ContReg = Cont.getAsRegion();
+  if (!ContReg)
+    return;
+
+  while (const auto *CBOR = ContReg->getAs<CXXBaseObjectRegion>()) {
+    ContReg = CBOR->getSuperRegion();
+  }
+
+  // Assignment of a new value to a container always invalidates all its
+  // iterators
+  auto State = C.getState();
+  const auto CData = getContainerData(State, ContReg);
+  if (CData) {
+    State = invalidateAllIteratorPositions(State, ContReg);
+  }
+
+  // In case of move, iterators of the old container (except the past-end
+  // iterators) remain valid but refer to the new container
+  if (!OldCont.isUndef()) {
+    const auto *OldContReg = OldCont.getAsRegion();
+    if (OldContReg) {
+      while (const auto *CBOR = OldContReg->getAs<CXXBaseObjectRegion>()) {
+        OldContReg = CBOR->getSuperRegion();
+      }
+      const auto OldCData = getContainerData(State, OldContReg);
+      if (OldCData) {
+        if (const auto OldEndSym = OldCData->getEnd()) {
+          State = reassignAllIteratorPositionsUnless(State, OldContReg, ContReg,
+                                                     OldEndSym, BO_GE);
+          auto &SymMgr = C.getSymbolManager();
+          auto NewEndSym =
+              SymMgr.conjureSymbol(CE, C.getLocationContext(),
+                                   C.getASTContext().LongTy, C.blockCount());
+          if (CData) {
+            State = setContainerData(State, ContReg, CData->newEnd(NewEndSym));
+          } else {
+            State = setContainerData(State, ContReg,
+                                     ContainerData::fromEnd(NewEndSym));
+          }
+          State = replaceSymbolInIteratorPositionsIf(
+              State, SymMgr, OldEndSym, NewEndSym, OldEndSym, BO_LT);
+        } else {
+          State = reassignAllIteratorPositions(State, OldContReg, ContReg);
+        }
+        if (const auto OldBeginSym = OldCData->getBegin()) {
+          if (CData) {
+            State =
+                setContainerData(State, ContReg, CData->newBegin(OldBeginSym));
+          } else {
+            State = setContainerData(State, ContReg,
+                                     ContainerData::fromBegin(OldBeginSym));
+          }
+          State =
+              setContainerData(State, OldContReg, OldCData->newEnd(nullptr));
+        }
+      } else {
+        State = reassignAllIteratorPositions(State, OldContReg, ContReg);
+      }
+    }
+  }
+  C.addTransition(State);
+}
+
+void IteratorChecker::handleClear(CheckerContext &C, const SVal &Cont) const {
+  const auto *ContReg = Cont.getAsRegion();
+  if (!ContReg)
+    return;
+
+  while (const auto *CBOR = ContReg->getAs<CXXBaseObjectRegion>()) {
+    ContReg = CBOR->getSuperRegion();
+  }
+
+  // The clear() operation invalidates all the iterators, except the past-end
+  // iterators of list-like containers
+  auto State = C.getState();
+  if (!hasSubscriptOperator(ContReg) || !backModifiable(ContReg)) {
+    const auto CData = getContainerData(State, ContReg);
+    if (CData) {
+      if (const auto EndSym = CData->getEnd()) {
+        State =
+            invalidateAllIteratorPositionsExcept(State, ContReg, EndSym, BO_GE);
+        C.addTransition(State);
+        return;
+      }
+    }
+  }
+  State = invalidateAllIteratorPositions(State, ContReg);
+  C.addTransition(State);
+}
+
+void IteratorChecker::handlePushBack(CheckerContext &C,
+                                     const SVal &Cont) const {
+  const auto *ContReg = Cont.getAsRegion();
+  if (!ContReg)
+    return;
+
+  while (const auto *CBOR = ContReg->getAs<CXXBaseObjectRegion>()) {
+    ContReg = CBOR->getSuperRegion();
+  }
+
+  // For deque-like containers invalidate all iterator positions
+  auto State = C.getState();
+  if (hasSubscriptOperator(ContReg) && frontModifiable(ContReg)) {
+    State = invalidateAllIteratorPositions(State, ContReg);
+    C.addTransition(State);
+    return;
+  }
+
+  const auto CData = getContainerData(State, ContReg);
+  if (!CData)
+    return;
+
+  // For vector-like containers invalidate the past-end iterator positions
+  if (const auto EndSym = CData->getEnd()) {
+    if (hasSubscriptOperator(ContReg)) {
+      State = invalidateIteratorPositions(State, EndSym, BO_GE);
+    }
+    auto &SymMgr = C.getSymbolManager();
+    const auto newEndSym =
+        compact(SymMgr, SymMgr.getSymIntExpr(EndSym, BO_Add, One,
+                                             SymMgr.getType(EndSym)));
+    State = setContainerData(State, ContReg, CData->newEnd(newEndSym));
+  }
+  C.addTransition(State);
+}
+
+void IteratorChecker::handlePopBack(CheckerContext &C, const SVal &Cont) const {
+  const auto *ContReg = Cont.getAsRegion();
+  if (!ContReg)
+    return;
+
+  while (const auto *CBOR = ContReg->getAs<CXXBaseObjectRegion>()) {
+    ContReg = CBOR->getSuperRegion();
+  }
+
+  auto State = C.getState();
+  const auto CData = getContainerData(State, ContReg);
+  if (!CData)
+    return;
+
+  if (const auto EndSym = CData->getEnd()) {
+    auto &SymMgr = C.getSymbolManager();
+    const auto BackSym =
+        compact(SymMgr, SymMgr.getSymIntExpr(EndSym, BO_Sub, One,
+                                             SymMgr.getType(EndSym)));
+    // For vector-like and deque-like containers invalidate the last and the
+    // past-end iterator positions. For list-like containers only invalidate
+    // the last position
+    if (hasSubscriptOperator(ContReg) && backModifiable(ContReg)) {
+      State = invalidateIteratorPositions(State, BackSym, BO_GE);
+      State = setContainerData(State, ContReg, CData->newEnd(nullptr));
+    } else {
+      State = invalidateIteratorPositions(State, BackSym, BO_EQ);
+    }
+    auto newEndSym = BackSym;
+    State = setContainerData(State, ContReg, CData->newEnd(newEndSym));
+    C.addTransition(State);
+  }
+}
+
+void IteratorChecker::handlePushFront(CheckerContext &C,
+                                      const SVal &Cont) const {
+  const auto *ContReg = Cont.getAsRegion();
+  if (!ContReg)
+    return;
+
+  while (const auto *CBOR = ContReg->getAs<CXXBaseObjectRegion>()) {
+    ContReg = CBOR->getSuperRegion();
+  }
+
+  // For deque-like containers invalidate all iterator positions
+  auto State = C.getState();
+  if (hasSubscriptOperator(ContReg)) {
+    State = invalidateAllIteratorPositions(State, ContReg);
+    C.addTransition(State);
+  } else {
+    const auto CData = getContainerData(State, ContReg);
+    if (!CData)
+      return;
+
+    if (const auto BeginSym = CData->getBegin()) {
+      auto &SymMgr = C.getSymbolManager();
+      const auto newBeginSym =
+          compact(SymMgr, SymMgr.getSymIntExpr(BeginSym, BO_Sub, One,
+                                               SymMgr.getType(BeginSym)));
+      State = setContainerData(State, ContReg, CData->newBegin(newBeginSym));
+      C.addTransition(State);
+    }
+  }
+}
+
+void IteratorChecker::handlePopFront(CheckerContext &C,
+                                     const SVal &Cont) const {
+  const auto *ContReg = Cont.getAsRegion();
+  if (!ContReg)
+    return;
+
+  while (const auto *CBOR = ContReg->getAs<CXXBaseObjectRegion>()) {
+    ContReg = CBOR->getSuperRegion();
+  }
+
+  auto State = C.getState();
+  const auto CData = getContainerData(State, ContReg);
+  if (!CData)
+    return;
+
+  // For deque-like containers invalidate all iterator positions. For list-like
+  // iterators only invalidate the first position
+  if (const auto BeginSym = CData->getBegin()) {
+    if (hasSubscriptOperator(ContReg)) {
+      State = invalidateIteratorPositions(State, BeginSym, BO_LE);
+    } else {
+      State = invalidateIteratorPositions(State, BeginSym, BO_EQ);
+    }
+    auto &SymMgr = C.getSymbolManager();
+    const auto newBeginSym =
+        compact(SymMgr, SymMgr.getSymIntExpr(BeginSym, BO_Add, One,
+                                             SymMgr.getType(BeginSym)));
+    State = setContainerData(State, ContReg, CData->newBegin(newBeginSym));
+    C.addTransition(State);
+  }
+}
+
+void IteratorChecker::handleInsert(CheckerContext &C, const SVal &Iter) const {
+  auto State = C.getState();
+  const auto *Pos = getIteratorPosition(State, Iter);
+  if (!Pos)
+    return;
+
+  // For deque-like containers invalidate all iterator positions. For
+  // vector-like containers invalidate iterator positions after the insertion.
+  const auto *Cont = Pos->getContainer();
+  if (hasSubscriptOperator(Cont) && backModifiable(Cont)) {
+    if (frontModifiable(Cont)) {
+      State = invalidateAllIteratorPositions(State, Cont);
+    } else {
+      State = invalidateIteratorPositions(State, Pos->getOffset(), BO_GE);
+    }
+    if (const auto *CData = getContainerData(State, Cont)) {
+      if (const auto EndSym = CData->getEnd()) {
+        State = invalidateIteratorPositions(State, EndSym, BO_GE);
+        State = setContainerData(State, Cont, CData->newEnd(nullptr));
+      }
+    }
+    C.addTransition(State);
+  }
+}
+
+void IteratorChecker::handleErase(CheckerContext &C, const SVal &Iter) const {
+  auto State = C.getState();
+  const auto *Pos = getIteratorPosition(State, Iter);
+  if (!Pos)
+    return;
+
+  // For deque-like containers invalidate all iterator positions. For
+  // vector-like containers invalidate iterator positions at and after the
+  // deletion. For list-like containers only invalidate the deleted position.
+  const auto *Cont = Pos->getContainer();
+  if (hasSubscriptOperator(Cont) && backModifiable(Cont)) {
+    if (frontModifiable(Cont)) {
+      State = invalidateAllIteratorPositions(State, Cont);
+    } else {
+      State = invalidateIteratorPositions(State, Pos->getOffset(), BO_GE);
+    }
+    if (const auto *CData = getContainerData(State, Cont)) {
+      if (const auto EndSym = CData->getEnd()) {
+        State = invalidateIteratorPositions(State, EndSym, BO_GE);
+        State = setContainerData(State, Cont, CData->newEnd(nullptr));
+      }
+    }
+  } else {
+    State = invalidateIteratorPositions(State, Pos->getOffset(), BO_EQ);
+  }
+  C.addTransition(State);
+}
+
+void IteratorChecker::handleErase(CheckerContext &C, const SVal &Iter1,
+                                  const SVal &Iter2) const {
+  auto State = C.getState();
+  const auto *Pos1 = getIteratorPosition(State, Iter1);
+  const auto *Pos2 = getIteratorPosition(State, Iter2);
+  if (!Pos1 || !Pos2)
+    return;
+
+  // For deque-like containers invalidate all iterator positions. For
+  // vector-like containers invalidate iterator positions at and after the
+  // deletion range. For list-like containers only invalidate the deleted
+  // position range [first..last].
+  const auto *Cont = Pos1->getContainer();
+  if (hasSubscriptOperator(Cont) && backModifiable(Cont)) {
+    if (frontModifiable(Cont)) {
+      State = invalidateAllIteratorPositions(State, Cont);
+    } else {
+      State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GE);
+    }
+    if (const auto *CData = getContainerData(State, Cont)) {
+      if (const auto EndSym = CData->getEnd()) {
+        State = invalidateIteratorPositions(State, EndSym, BO_GE);
+        State = setContainerData(State, Cont, CData->newEnd(nullptr));
+      }
+    }
+  } else {
+    State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GE,
+                                        Pos2->getOffset(), BO_LT);
+  }
+  C.addTransition(State);
+}
+
+void IteratorChecker::handleEraseAfter(CheckerContext &C,
+                                       const SVal &Iter) const {
+  auto State = C.getState();
+  const auto *Pos = getIteratorPosition(State, Iter);
+  if (!Pos)
+    return;
+
+  // Invalidate the deleted iterator position, which is the position of the
+  // parameter plus one.
+  auto &SymMgr = C.getSymbolManager();
+  auto NextSym = SymMgr.getSymIntExpr(Pos->getOffset(), BO_Add, One,
+                                      SymMgr.getType(Pos->getOffset()));
+  State = invalidateIteratorPositions(State, NextSym, BO_EQ);
+  C.addTransition(State);
+}
+
+void IteratorChecker::handleEraseAfter(CheckerContext &C, const SVal &Iter1,
+                                       const SVal &Iter2) const {
+  auto State = C.getState();
+  const auto *Pos1 = getIteratorPosition(State, Iter1);
+  const auto *Pos2 = getIteratorPosition(State, Iter2);
+  if (!Pos1 || !Pos2)
+    return;
+
+  // Invalidate the deleted iterator position range (first..last)
+  State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GT,
+                                      Pos2->getOffset(), BO_LT);
+  C.addTransition(State);
+}
+
+bool IteratorChecker::evalFind(CheckerContext &C, const CallExpr *CE) const {
+  if (CE->getNumArgs() == 3 && isIteratorType(CE->getArg(0)->getType()) &&
+      isIteratorType(CE->getArg(1)->getType())) {
+    Find(C, CE);
+    return true;
+  }
+  return false;
+}
+
+bool IteratorChecker::evalFindEnd(CheckerContext &C, const CallExpr *CE) const {
+  if ((CE->getNumArgs() == 4 || CE->getNumArgs() == 5) &&
+      isIteratorType(CE->getArg(0)->getType()) &&
+      isIteratorType(CE->getArg(1)->getType()) &&
+      isIteratorType(CE->getArg(2)->getType()) &&
+      isIteratorType(CE->getArg(3)->getType())) {
+    Find(C, CE);
+    return true;
+  }
+  return false;
+}
+
+bool IteratorChecker::evalFindFirstOf(CheckerContext &C,
+                                      const CallExpr *CE) const {
+  if ((CE->getNumArgs() == 4 || CE->getNumArgs() == 5) &&
+      isIteratorType(CE->getArg(0)->getType()) &&
+      isIteratorType(CE->getArg(1)->getType()) &&
+      isIteratorType(CE->getArg(2)->getType()) &&
+      isIteratorType(CE->getArg(3)->getType())) {
+    Find(C, CE);
+    return true;
+  }
+  return false;
+}
+
+bool IteratorChecker::evalFindIf(CheckerContext &C, const CallExpr *CE) const {
+  if (CE->getNumArgs() == 3 && isIteratorType(CE->getArg(0)->getType()) &&
+      isIteratorType(CE->getArg(1)->getType())) {
+    Find(C, CE);
+    return true;
+  }
+  return false;
+}
+
+bool IteratorChecker::evalFindIfNot(CheckerContext &C,
+                                    const CallExpr *CE) const {
+  if (CE->getNumArgs() == 3 && isIteratorType(CE->getArg(0)->getType()) &&
+      isIteratorType(CE->getArg(1)->getType())) {
+    Find(C, CE);
+    return true;
+  }
+  return false;
+}
+
+bool IteratorChecker::evalLowerBound(CheckerContext &C,
+                                     const CallExpr *CE) const {
+  if ((CE->getNumArgs() == 3 || CE->getNumArgs() == 4) &&
+      isIteratorType(CE->getArg(0)->getType()) &&
+      isIteratorType(CE->getArg(1)->getType())) {
+    Find(C, CE);
+    return true;
+  }
+  return false;
+}
+
+bool IteratorChecker::evalUpperBound(CheckerContext &C,
+                                     const CallExpr *CE) const {
+  if ((CE->getNumArgs() == 3 || CE->getNumArgs() == 4) &&
+      isIteratorType(CE->getArg(0)->getType()) &&
+      isIteratorType(CE->getArg(1)->getType())) {
+    Find(C, CE);
+    return true;
+  }
+  return false;
+}
+
+bool IteratorChecker::evalSearch(CheckerContext &C, const CallExpr *CE) const {
+  if ((CE->getNumArgs() == 4 || CE->getNumArgs() == 5) &&
+      isIteratorType(CE->getArg(0)->getType()) &&
+      isIteratorType(CE->getArg(1)->getType()) &&
+      isIteratorType(CE->getArg(2)->getType()) &&
+      isIteratorType(CE->getArg(3)->getType())) {
+    Find(C, CE);
+    return true;
+  }
+  return false;
+}
+
+bool IteratorChecker::evalSearchN(CheckerContext &C, const CallExpr *CE) const {
+  if ((CE->getNumArgs() == 4 || CE->getNumArgs() == 5) &&
+      isIteratorType(CE->getArg(0)->getType()) &&
+      isIteratorType(CE->getArg(1)->getType())) {
+    Find(C, CE);
+    return true;
+  }
+  return false;
+}
+
+void IteratorChecker::Find(CheckerContext &C, const CallExpr *CE) const {
+  auto state = C.getState();
+  auto &svalBuilder = C.getSValBuilder();
+  const auto *LCtx = C.getLocationContext();
+
+  auto RetVal = svalBuilder.conjureSymbolVal(nullptr, CE, LCtx, C.blockCount());
+  auto SecondParam = state->getSVal(CE->getArg(1), LCtx);
+
+  auto stateFound = state->BindExpr(CE, LCtx, RetVal);
+  auto stateNotFound = state->BindExpr(CE, LCtx, SecondParam);
+
+  C.addTransition(stateFound);
+  C.addTransition(stateNotFound);
+}
+
+void IteratorChecker::reportOutOfRangeBug(const StringRef &Message,
+                                          const SVal &Val, CheckerContext &C,
+                                          ExplodedNode *ErrNode) const {
+  auto R = llvm::make_unique<BugReport>(*OutOfRangeBugType, Message, ErrNode);
+  R->markInteresting(Val);
+  C.emitReport(std::move(R));
+}
+
+void IteratorChecker::reportMismatchedBug(const StringRef &Message,
+                                          const SVal &Val, CheckerContext &C,
+                                          ExplodedNode *ErrNode) const {
+  auto R = llvm::make_unique<BugReport>(*MismatchedBugType, Message, ErrNode);
+  R->markInteresting(Val);
+  C.emitReport(std::move(R));
+}
+
+void IteratorChecker::reportInvalidatedBug(const StringRef &Message,
+                                           const SVal &Val, CheckerContext &C,
+                                           ExplodedNode *ErrNode) const {
+  auto R = llvm::make_unique<BugReport>(*InvalidatedBugType, Message, ErrNode);
+  R->markInteresting(Val);
+  C.emitReport(std::move(R));
+}
+
+void IteratorChecker::initIdentifiers(ASTContext &Ctx) const {
+  INIT_ID(find);
+  INIT_ID(find_end);
+  INIT_ID(find_first_of);
+  INIT_ID(find_if);
+  INIT_ID(find_if_not);
+  INIT_ID(lower_bound);
+  INIT_ID(upper_bound);
+  INIT_ID(search);
+  INIT_ID(search_n);
+}
+
+namespace {
+
+bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
+bool isGreaterOrEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
+bool compareToZero(ProgramStateRef State, const NonLoc &Val,
+                   BinaryOperator::Opcode Opc);
+bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
+             BinaryOperator::Opcode Opc);
+std::pair<SymbolRef, llvm::APSInt> decompose(const SymbolRef Sym);
+const CXXRecordDecl *getCXXRecordDecl(const MemRegion *Reg);
+SymbolRef replaceSymbol(SymbolManager &SymMgr, 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 isEndCall(const FunctionDecl *Func) {
+  const auto *IdInfo = Func->getIdentifier();
+  if (!IdInfo)
+    return false;
+  return IdInfo->getName().endswith_lower("end");
+}
+
+bool isAssignCall(const FunctionDecl *Func) {
+  const auto *IdInfo = Func->getIdentifier();
+  if (!IdInfo)
+    return false;
+  if (Func->getNumParams() > 2)
+    return false;
+  return IdInfo->getName() == "assign";
+}
+
+bool isClearCall(const FunctionDecl *Func) {
+  const auto *IdInfo = Func->getIdentifier();
+  if (!IdInfo)
+    return false;
+  if (Func->getNumParams() > 0)
+    return false;
+  return IdInfo->getName() == "clear";
+}
+
+bool isPushBackCall(const FunctionDecl *Func) {
+  const auto *IdInfo = Func->getIdentifier();
+  if (!IdInfo)
+    return false;
+  if (Func->getNumParams() != 1)
+    return false;
+  return IdInfo->getName() == "push_back";
+}
+
+bool isEmplaceBackCall(const FunctionDecl *Func) {
+  const auto *IdInfo = Func->getIdentifier();
+  if (!IdInfo)
+    return false;
+  if (Func->getNumParams() < 1)
+    return false;
+  return IdInfo->getName() == "emplace_back";
+}
+
+bool isPopBackCall(const FunctionDecl *Func) {
+  const auto *IdInfo = Func->getIdentifier();
+  if (!IdInfo)
+    return false;
+  if (Func->getNumParams() > 0)
+    return false;
+  return IdInfo->getName() == "pop_back";
+}
+
+bool isPushFrontCall(const FunctionDecl *Func) {
+  const auto *IdInfo = Func->getIdentifier();
+  if (!IdInfo)
+    return false;
+  if (Func->getNumParams() != 1)
+    return false;
+  return IdInfo->getName() == "push_front";
+}
+
+bool isEmplaceFrontCall(const FunctionDecl *Func) {
+  const auto *IdInfo = Func->getIdentifier();
+  if (!IdInfo)
+    return false;
+  if (Func->getNumParams() < 1)
+    return false;
+  return IdInfo->getName() == "emplace_front";
+}
+
+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;
+}
+BinaryOperator::Opcode getOpcode(const SymExpr *SE) {
+  if (const auto *BSE = dyn_cast<BinarySymExpr>(SE)) {
+    return BSE->getOpcode();
+  } else if (const auto *SC = dyn_cast<SymbolConjured>(SE)) {
+    const auto *COE = dyn_cast<CXXOperatorCallExpr>(SC->getStmt());
+    if (!COE)
+      return BO_Comma; // Extremal value, neither EQ nor NE
+    if (COE->getOperator() == OO_EqualEqual) {
+      return BO_EQ;
+    } else if (COE->getOperator() == OO_ExclaimEqual) {
+      return BO_NE;
+    }
+    return BO_Comma; // Extremal value, neither EQ nor NE
+  }
+  return BO_Comma; // Extremal value, neither EQ nor NE
+}
+
+bool hasSubscriptOperator(const MemRegion *Reg) {
+  const auto *CRD = getCXXRecordDecl(Reg);
+  if (!CRD)
+    return false;
+
+  for (const auto *Method : CRD->methods()) {
+    if (!Method->isOverloadedOperator())
+      continue;
+    const auto OPK = Method->getOverloadedOperator();
+    if (OPK == OO_Subscript) {
+      return true;
+    }
+  }
+  return false;
+}
+
+bool frontModifiable(const MemRegion *Reg) {
+  const auto *CRD = getCXXRecordDecl(Reg);
+  if (!CRD)
+    return false;
+
+  for (const auto *Method : CRD->methods()) {
+    if (!Method->getDeclName().isIdentifier())
+      continue;
+    if (Method->getName() == "push_front" || Method->getName() == "pop_front") {
+      return true;
+    }
+  }
+  return false;
+}
+
+bool backModifiable(const MemRegion *Reg) {
+  const auto *CRD = getCXXRecordDecl(Reg);
+  if (!CRD)
+    return false;
+
+  for (const auto *Method : CRD->methods()) {
+    if (!Method->getDeclName().isIdentifier())
+      continue;
+    if (Method->getName() == "push_back" || Method->getName() == "pop_back") {
+      return true;
+    }
+  }
+  return false;
+}
+
+const CXXRecordDecl *getCXXRecordDecl(const MemRegion *Reg) {
+  QualType Type;
+  if (const auto *TVReg = Reg->getAs<TypedValueRegion>()) {
+    Type = TVReg->getValueType();
+  } else if (const auto *SymReg = Reg->getAs<SymbolicRegion>()) {
+    Type = SymReg->getSymbol()->getType();
+  } else {
+    return nullptr;
+  }
+
+  if (const auto *RefT = Type->getAs<ReferenceType>()) {
+    Type = RefT->getPointeeType();
+  }
+
+  return Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl();
+}
+
+const RegionOrSymbol getRegionOrSymbol(const SVal &Val) {
+  if (const auto Reg = Val.getAsRegion()) {
+    return Reg;
+  } else if (const auto Sym = Val.getAsSymbol()) {
+    return Sym;
+  } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
+    return LCVal->getRegion();
+  }
+  return RegionOrSymbol();
+}
+
+const ProgramStateRef processComparison(ProgramStateRef State,
+                                        RegionOrSymbol LVal,
+                                        RegionOrSymbol RVal, bool Equal) {
+  const auto *LPos = getIteratorPosition(State, LVal);
+  const auto *RPos = getIteratorPosition(State, RVal);
+  if (LPos && !RPos) {
+    State = adjustIteratorPosition(State, RVal, *LPos, Equal);
+  } else if (!LPos && RPos) {
+    State = adjustIteratorPosition(State, LVal, *RPos, Equal);
+  } else if (LPos && RPos) {
+    State = relateIteratorPositions(State, *LPos, *RPos, Equal);
+  }
+  return State;
+}
+
+const ProgramStateRef saveComparison(ProgramStateRef State,
+                                     const SymExpr *Condition, const SVal &LVal,
+                                     const SVal &RVal, bool Eq) {
+  const auto Left = getRegionOrSymbol(LVal);
+  const auto Right = getRegionOrSymbol(RVal);
+  if (!Left || !Right)
+    return State;
+  return State->set<IteratorComparisonMap>(Condition,
+                                           IteratorComparison(Left, Right, Eq));
+}
+
+const IteratorComparison *loadComparison(ProgramStateRef State,
+                                         const SymExpr *Condition) {
+  return State->get<IteratorComparisonMap>(Condition);
+}
+
+SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont) {
+  const auto *CDataPtr = getContainerData(State, Cont);
+  if (!CDataPtr)
+    return nullptr;
+
+  return CDataPtr->getBegin();
+}
+
+SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont) {
+  const auto *CDataPtr = getContainerData(State, Cont);
+  if (!CDataPtr)
+    return nullptr;
+
+  return CDataPtr->getEnd();
+}
+
+ProgramStateRef createContainerBegin(ProgramStateRef State,
+                                     const MemRegion *Cont,
+                                     const SymbolRef Sym) {
+  // Only create if it does not exist
+  const auto *CDataPtr = getContainerData(State, Cont);
+  if (CDataPtr) {
+    if (CDataPtr->getBegin()) {
+      return State;
+    } else {
+      const auto CData = CDataPtr->newBegin(Sym);
+      return setContainerData(State, Cont, CData);
+    }
+  } else {
+    const auto CData = ContainerData::fromBegin(Sym);
+    return setContainerData(State, Cont, CData);
+  }
+}
+
+ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont,
+                                   const SymbolRef Sym) {
+  // Only create if it does not exist
+  const auto *CDataPtr = getContainerData(State, Cont);
+  if (CDataPtr) {
+    if (CDataPtr->getEnd()) {
+      return State;
+    } else {
+      const auto CData = CDataPtr->newEnd(Sym);
+      return setContainerData(State, Cont, CData);
+    }
+  } else {
+    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) {
+  if (const auto Reg = Val.getAsRegion()) {
+    return State->get<IteratorRegionMap>(Reg);
+  } else if (const auto Sym = Val.getAsSymbol()) {
+    return State->get<IteratorSymbolMap>(Sym);
+  } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
+    return State->get<IteratorRegionMap>(LCVal->getRegion());
+  }
+  return nullptr;
+}
+
+const IteratorPosition *getIteratorPosition(ProgramStateRef State,
+                                            RegionOrSymbol RegOrSym) {
+  if (RegOrSym.is<const MemRegion *>()) {
+    return State->get<IteratorRegionMap>(RegOrSym.get<const MemRegion *>());
+  } else if (RegOrSym.is<SymbolRef>()) {
+    return State->get<IteratorSymbolMap>(RegOrSym.get<SymbolRef>());
+  }
+  return nullptr;
+}
+
+ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val,
+                                    const IteratorPosition &Pos) {
+  if (const auto Reg = Val.getAsRegion()) {
+    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 setIteratorPosition(ProgramStateRef State,
+                                    RegionOrSymbol RegOrSym,
+                                    const IteratorPosition &Pos) {
+  if (RegOrSym.is<const MemRegion *>()) {
+    return State->set<IteratorRegionMap>(RegOrSym.get<const MemRegion *>(),
+                                         Pos);
+  } else if (RegOrSym.is<SymbolRef>()) {
+    return State->set<IteratorSymbolMap>(RegOrSym.get<SymbolRef>(), Pos);
+  }
+  return nullptr;
+}
+
+ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val) {
+  if (const auto Reg = Val.getAsRegion()) {
+    return State->remove<IteratorRegionMap>(Reg);
+  } else if (const auto Sym = Val.getAsSymbol()) {
+    return State->remove<IteratorSymbolMap>(Sym);
+  } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
+    return State->remove<IteratorRegionMap>(LCVal->getRegion());
+  }
+  return nullptr;
+}
+
+ProgramStateRef adjustIteratorPosition(ProgramStateRef State,
+                                       RegionOrSymbol RegOrSym,
+                                       const IteratorPosition &Pos,
+                                       bool Equal) {
+  if (Equal) {
+    return setIteratorPosition(State, RegOrSym, Pos);
+  } else {
+    return State;
+  }
+}
+
+ProgramStateRef relateIteratorPositions(ProgramStateRef State,
+                                        const IteratorPosition &Pos1,
+                                        const IteratorPosition &Pos2,
+                                        bool Equal) {
+  // First Try to compare them and get a defined value
+  auto &SVB = State->getStateManager().getSValBuilder();
+  const auto comparison =
+      SVB.evalBinOp(State, BO_EQ, nonloc::SymbolVal(Pos1.getOffset()),
+                    nonloc::SymbolVal(Pos2.getOffset()), SVB.getConditionType())
+          .getAs<DefinedSVal>();
+  if (comparison) {
+    return State->assume(*comparison, Equal);
+  }
+
+  // If we did not get a defined value for the comparison, store the difference
+  // as a constraint. Positions are represented in A, A+n or A-n format, where
+  // A is a conjured symbol and n a concrete integer. So for e.g. A+n == B+m
+  // assume A-B == m-n.
+  auto &SymMgr = State->getSymbolManager();
+  SymbolRef diffSim;
+  llvm::APSInt diffVal;
+  std::tie(diffSim, diffVal) =
+      createDifference(SymMgr, Pos1.getOffset(), Pos2.getOffset());
+
+  if (Equal) {
+    const auto equality =
+        SVB.makeNonLoc(diffSim, BO_EQ, diffVal, SVB.getConditionType())
+            .getAs<nonloc::SymbolVal>();
+
+    if (equality) {
+      return State->assume(*equality, Equal);
+    }
+  }
+
+  return State;
+}
+
+template <typename Condition, typename Process>
+ProgramStateRef processIteratorPositions(ProgramStateRef State, Condition Cond,
+                                         Process Proc) {
+  auto RegionMap = State->get<IteratorRegionMap>();
+  for (const auto Reg : RegionMap) {
+    if (Cond(Reg.second)) {
+      State = setIteratorPosition(State, Reg.first, Proc(Reg.second));
+    }
+  }
+
+  auto SymbolMap = State->get<IteratorSymbolMap>();
+  for (const auto Sym : SymbolMap) {
+    if (Cond(Sym.second)) {
+      State = setIteratorPosition(State, Sym.first, Proc(Sym.second));
+    }
+  }
+
+  return State;
+}
+
+ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State,
+                                               const MemRegion *Cont) {
+  auto MatchCont = [&](const IteratorPosition &Pos) {
+    return Pos.getContainer() == Cont;
+  };
+  auto Invalidate = [&](const IteratorPosition &Pos) {
+    return Pos.invalidate();
+  };
+  return processIteratorPositions(State, MatchCont, Invalidate);
+}
+
+ProgramStateRef
+invalidateAllIteratorPositionsExcept(ProgramStateRef State,
+                                     const MemRegion *Cont, SymbolRef Offset,
+                                     BinaryOperator::Opcode Opc) {
+  auto MatchContAndCompare = [&](const IteratorPosition &Pos) {
+    return Pos.getContainer() == Cont &&
+           !compare(State, Pos.getOffset(), Offset, Opc);
+  };
+  auto Invalidate = [&](const IteratorPosition &Pos) {
+    return Pos.invalidate();
+  };
+  return processIteratorPositions(State, MatchContAndCompare, Invalidate);
+}
+
+ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
+                                            SymbolRef Offset,
+                                            BinaryOperator::Opcode Opc) {
+  auto Compare = [&](const IteratorPosition &Pos) {
+    return compare(State, Pos.getOffset(), Offset, Opc);
+  };
+  auto Invalidate = [&](const IteratorPosition &Pos) {
+    return Pos.invalidate();
+  };
+  return processIteratorPositions(State, Compare, Invalidate);
+}
+
+ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
+                                            SymbolRef Offset1,
+                                            BinaryOperator::Opcode Opc1,
+                                            SymbolRef Offset2,
+                                            BinaryOperator::Opcode Opc2) {
+  auto Compare = [&](const IteratorPosition &Pos) {
+    return compare(State, Pos.getOffset(), Offset1, Opc1) &&
+           compare(State, Pos.getOffset(), Offset2, Opc2);
+  };
+  auto Invalidate = [&](const IteratorPosition &Pos) {
+    return Pos.invalidate();
+  };
+  return processIteratorPositions(State, Compare, Invalidate);
+}
+
+ProgramStateRef reassignAllIteratorPositions(ProgramStateRef State,
+                                             const MemRegion *Cont,
+                                             const MemRegion *NewCont) {
+  auto MatchCont = [&](const IteratorPosition &Pos) {
+    return Pos.getContainer() == Cont;
+  };
+  auto ReAssign = [&](const IteratorPosition &Pos) {
+    return Pos.reAssign(NewCont);
+  };
+  return processIteratorPositions(State, MatchCont, ReAssign);
+}
+
+ProgramStateRef reassignAllIteratorPositionsUnless(ProgramStateRef State,
+                                                   const MemRegion *Cont,
+                                                   const MemRegion *NewCont,
+                                                   SymbolRef Offset,
+                                                   BinaryOperator::Opcode Opc) {
+  auto MatchContAndCompare = [&](const IteratorPosition &Pos) {
+    return Pos.getContainer() == Cont &&
+           !compare(State, Pos.getOffset(), Offset, Opc);
+  };
+  auto ReAssign = [&](const IteratorPosition &Pos) {
+    return Pos.reAssign(NewCont);
+  };
+  return processIteratorPositions(State, MatchContAndCompare, ReAssign);
+}
+
+ProgramStateRef replaceSymbolInIteratorPositionsIf(
+    ProgramStateRef State, SymbolManager &SymMgr, SymbolRef OldSym,
+    SymbolRef NewSym, SymbolRef CondSym, BinaryOperator::Opcode Opc) {
+  auto LessThanEnd = [&](const IteratorPosition &Pos) {
+    return compare(State, Pos.getOffset(), CondSym, Opc);
+  };
+  auto ReplaceSymbol = [&](const IteratorPosition &Pos) {
+    return Pos.setTo(replaceSymbol(SymMgr, Pos.getOffset(), OldSym, NewSym));
+  };
+  return processIteratorPositions(State, LessThanEnd, ReplaceSymbol);
+}
+
+bool isZero(ProgramStateRef State, const NonLoc &Val) {
+  return compareToZero(State, Val, BO_EQ);
+}
+
+bool compareToZero(ProgramStateRef State, const NonLoc &Val,
+                   BinaryOperator::Opcode Opc) {
+  auto &SMgr = State->getStateManager();
+  auto &SVB = SMgr.getSValBuilder();
+
+  const auto comparison =
+      SVB.evalBinOpNN(State, Opc, Val, nonloc::ConcreteInt(Zero),
+                      SVB.getConditionType())
+          .getAs<DefinedSVal>();
+
+  if (!comparison)
+    return false;
+
+  ProgramStateRef StateTrue = State->assume(*comparison, true);
+  return !!StateTrue;
+}
+
+bool isOutOfRange(ProgramStateRef State, const IteratorPosition &Pos) {
+  const auto *Cont = Pos.getContainer();
+  const auto *CData = getContainerData(State, Cont);
+  if (!CData)
+    return false;
+
+  // Out of range means less than the begin symbol or greater or equal to the
+  // end symbol.
+
+  const auto Beg = CData->getBegin();
+  if (Beg) {
+    if (isLess(State, Pos.getOffset(), Beg)) {
+      return true;
+    }
+  }
+
+  const auto End = CData->getEnd();
+  if (End) {
+    if (isGreaterOrEqual(State, Pos.getOffset(), End)) {
+      return true;
+    }
+  }
+
+  return false;
+}
+
+bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
+  return compare(State, Sym1, Sym2, BO_LT);
+}
+
+bool isGreaterOrEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
+  return compare(State, Sym1, Sym2, BO_GE);
+}
+
+bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
+             BinaryOperator::Opcode Opc) {
+  auto &SMgr = State->getStateManager();
+  auto &SVB = SMgr.getSValBuilder();
+
+  llvm::APSInt Int1, Int2;
+
+  // Positions are in the format A, A+n or A-n, where A is a conjured symbol and
+  // n is a concrete integer. Decompose them to A and n (in case of A, we get
+  // zero instead of n and in case of A-n we get -n.
+  std::tie(Sym1, Int1) = decompose(Sym1);
+  std::tie(Sym2, Int2) = decompose(Sym2);
+
+  // Try to compare the symbols. Currently, we only get equality if they are
+  // exactly the same.
+  const auto comparison =
+      SVB.evalBinOp(State, BO_EQ, nonloc::SymbolVal(Sym1),
+                    nonloc::SymbolVal(Sym2), SVB.getConditionType())
+          .getAs<DefinedSVal>();
+
+  // If the are not the same, try to retrieve their difference from the
+  // assumptions. If found, adjust the concrete integers with the difference.
+  ProgramStateRef newState;
+  if (!comparison) {
+    const auto *Diff = getDifference(State, Sym1, Sym2);
+    if (Diff) {
+      Int1 += *Diff;
+    } else {
+      Diff = getDifference(State, Sym2, Sym1);
+      if (Diff) {
+        Int2 += *Diff;
+      } else {
+        return false;
+      }
+    }
+    newState = State;
+  } else {
+    newState = State->assume(*comparison, true);
+    if (!newState)
+      return false;
+  }
+
+  auto &BVF = newState->getSymbolManager().getBasicVals();
+  return BVF.evalAPSInt(Opc, Int1, Int2)->getExtValue();
+}
+
+SymbolRef replaceSymbol(SymbolManager &SymMgr, SymbolRef OrigExpr,
+                        SymbolRef OldExpr, SymbolRef NewSym) {
+  // We have a symbolic expression in the format of A+n, where we want to
+  // replace A+m with B, so the result becomes B+k, where k==n-m.
+  SymbolRef OrigSym, OldSym;
+  llvm::APSInt OrigInt, OldInt;
+  std::tie(OrigSym, OrigInt) = decompose(OrigExpr);
+  std::tie(OldSym, OldInt) = decompose(OldExpr);
+  if (OrigSym == OldSym) {
+    auto NewInt = OrigInt - OldInt;
+    if (NewInt == 0) {
+      return NewSym;
+    } else {
+      auto OpCode = (NewInt > 0) ? BO_Add : BO_Sub;
+      auto &BVF = SymMgr.getBasicVals();
+      auto &AbsInt =
+          (NewInt > 0) ? BVF.getValue(NewInt) : BVF.getValue(-NewInt);
+      return SymMgr.getSymIntExpr(NewSym, OpCode, AbsInt, OrigExpr->getType());
+    }
+  } else {
+    return OrigExpr;
+  }
+}
+
+SymbolRef compact(SymbolManager &SymMgr, const SymbolRef Sym) {
+  // Turn A+m+n into A+k, where k=m+n
+  if (const auto *Expr = dyn_cast<SymIntExpr>(Sym)) {
+    if (const auto *LExpr = dyn_cast<SymIntExpr>(Expr->getLHS())) {
+      auto &BVF = SymMgr.getBasicVals();
+      const auto &newRHS = (Expr->getOpcode() == LExpr->getOpcode())
+                               ? BVF.getValue(LExpr->getRHS() + Expr->getRHS())
+                               : BVF.getValue(LExpr->getRHS() - Expr->getRHS());
+      if (newRHS != 0) {
+        return SymMgr.getSymIntExpr(LExpr->getLHS(), LExpr->getOpcode(), newRHS,
+                                    Expr->getType());
+      } else {
+        return LExpr->getLHS();
+      }
+    } else {
+      return Expr;
+    }
+  } else {
+    return Sym;
+  }
+}
+
+std::pair<SymbolRef, llvm::APSInt>
+createDifference(SymbolManager &SymMgr, SymbolRef Sym1, SymbolRef Sym2) {
+  // Turn A+n and B+m into a pair of A-B and k, where k==m-n
+  llvm::APSInt Int1, Int2;
+  std::tie(Sym1, Int1) = decompose(Sym1);
+  std::tie(Sym2, Int2) = decompose(Sym2);
+
+  SymbolRef newSym = SymMgr.getSymSymExpr(Sym1, BO_Sub, Sym2, Sym1->getType());
+  llvm::APSInt newInt = Int2 - Int1;
+
+  return std::make_pair(newSym, newInt);
+}
+
+const llvm::APSInt *getDifference(ProgramStateRef State, SymbolRef Sym1,
+                                  SymbolRef Sym2) {
+  // Try to retrieve the difference A-B from the constraint manager
+  auto &SymMgr = State->getSymbolManager();
+  auto &CM = State->getConstraintManager();
+  auto diffSym = SymMgr.getSymSymExpr(Sym1, BO_Sub, Sym2, Sym1->getType());
+  return CM.getSymVal(State, diffSym);
+}
+
+std::pair<SymbolRef, llvm::APSInt> decompose(SymbolRef Sym) {
+  // Decompose A+n to a pair of A and n
+  if (const auto *Expr = dyn_cast<SymIntExpr>(Sym)) {
+    auto Int =
+        (Expr->getOpcode() == BO_Add) ? Expr->getRHS() : (-Expr->getRHS());
+    return std::make_pair(Expr->getLHS(), Int);
+  } else {
+    return std::make_pair(Sym, Zero);
+  }
+}
+
+} // namespace
+
+#define REGISTER_CHECKER(name)                                                 \
+  void ento::register##name(CheckerManager &Mgr) {                             \
+    auto *checker = Mgr.registerChecker<IteratorChecker>();                    \
+    checker->ChecksEnabled[IteratorChecker::CK_##name] = true;                 \
+    checker->CheckNames[IteratorChecker::CK_##name] =                          \
+        Mgr.getCurrentCheckName();                                             \
+  }
+
+REGISTER_CHECKER(IteratorRangeChecker)
+REGISTER_CHECKER(MismatchedIteratorChecker)
+REGISTER_CHECKER(InvalidatedIteratorChecker)

lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp

-//===-- IteratorPastEndChecker.cpp --------------------------------*- C++ -*--//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// Defines a checker for using iterators outside their range (past end). Usage
-// means here dereferencing, incrementing etc.
-//
-//===----------------------------------------------------------------------===//
-
-#include "ClangSACheckers.h"
-#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
-#include "clang/StaticAnalyzer/Core/Checker.h"
-#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
-#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
-
-#include <utility>
-
-using namespace clang;
-using namespace ento;
-
-namespace {
-struct IteratorPosition {
-private:
-  enum Kind { InRange, OutofRange } K;
-  IteratorPosition(Kind InK) : K(InK) {}
-
-public:
-  bool isInRange() const { return K == InRange; }
-  bool isOutofRange() const { return K == OutofRange; }
-
-  static IteratorPosition getInRange() { return IteratorPosition(InRange); }
-  static IteratorPosition getOutofRange() {
-    return IteratorPosition(OutofRange);
-  }
-
-  bool operator==(const IteratorPosition &X) const { return K == X.K; }
-  bool operator!=(const IteratorPosition &X) const { return K != X.K; }
-  void Profile(llvm::FoldingSetNodeID &ID) const { ID.AddInteger(K); }
-};
-
-typedef llvm::PointerUnion<const MemRegion *, SymbolRef> RegionOrSymbol;
-
-struct IteratorComparison {
-private:
-  RegionOrSymbol Left, Right;
-  bool Equality;
-
-public:
-  IteratorComparison(RegionOrSymbol L, RegionOrSymbol R, bool Eq)
-      : Left(L), Right(R), Equality(Eq) {}
-
-  RegionOrSymbol getLeft() const { return Left; }
-  RegionOrSymbol getRight() const { return Right; }
-  bool isEquality() const { return Equality; }
-  bool operator==(const IteratorComparison &X) const {
-    return Left == X.Left && Right == X.Right && Equality == X.Equality;
-  }
-  bool operator!=(const IteratorComparison &X) const {
-    return Left != X.Left || Right != X.Right || Equality != X.Equality;
-  }
-  void Profile(llvm::FoldingSetNodeID &ID) const { ID.AddInteger(Equality); }
-};
-
-class IteratorPastEndChecker
-    : public Checker<
-          check::PreCall, check::PostCall, check::PreStmt<CXXOperatorCallExpr>,
-          check::PostStmt<CXXConstructExpr>, check::PostStmt<DeclStmt>,
-          check::PostStmt<MaterializeTemporaryExpr>, check::BeginFunction,
-          check::DeadSymbols, eval::Assume, eval::Call> {
-  mutable IdentifierInfo *II_find = nullptr,
-                         *II_find_end = nullptr, *II_find_first_of = nullptr,
-                         *II_find_if = nullptr, *II_find_if_not = nullptr,
-                         *II_lower_bound = nullptr, *II_upper_bound = nullptr,
-                         *II_search = nullptr, *II_search_n = nullptr;
-
-  std::unique_ptr<BugType> PastEndBugType;
-
-  void handleComparison(CheckerContext &C, const SVal &RetVal, const SVal &LVal,
-                        const SVal &RVal, OverloadedOperatorKind Op) const;
-  void handleAccess(CheckerContext &C, const SVal &Val) const;
-  void handleDecrement(CheckerContext &C, const SVal &Val) const;
-  void handleEnd(CheckerContext &C, const SVal &RetVal) const;
-
-  bool evalFind(CheckerContext &C, const CallExpr *CE) const;
-  bool evalFindEnd(CheckerContext &C, const CallExpr *CE) const;
-  bool evalFindFirstOf(CheckerContext &C, const CallExpr *CE) const;
-  bool evalFindIf(CheckerContext &C, const CallExpr *CE) const;
-  bool evalFindIfNot(CheckerContext &C, const CallExpr *CE) const;
-  bool evalLowerBound(CheckerContext &C, const CallExpr *CE) const;
-  bool evalUpperBound(CheckerContext &C, const CallExpr *CE) const;
-  bool evalSearch(CheckerContext &C, const CallExpr *CE) const;
-  bool evalSearchN(CheckerContext &C, const CallExpr *CE) const;
-  void Find(CheckerContext &C, const CallExpr *CE) const;
-
-  void reportPastEndBug(const StringRef &Message, const SVal &Val,
-                        CheckerContext &C, ExplodedNode *ErrNode) const;
-  void initIdentifiers(ASTContext &Ctx) const;
-
-public:
-  IteratorPastEndChecker();
-
-  void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
-  void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
-  void checkPreStmt(const CXXOperatorCallExpr *COCE, CheckerContext &C) const;
-  void checkBeginFunction(CheckerContext &C) const;
-  void checkPostStmt(const CXXConstructExpr *CCE, CheckerContext &C) const;
-  void checkPostStmt(const DeclStmt *DS, CheckerContext &C) const;
-  void checkPostStmt(const MaterializeTemporaryExpr *MTE,
-                     CheckerContext &C) const;
-  void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
-  ProgramStateRef evalAssume(ProgramStateRef State, SVal Cond,
-                             bool Assumption) const;
-  bool evalCall(const CallExpr *CE, CheckerContext &C) const;
-};
-}
-
-REGISTER_MAP_WITH_PROGRAMSTATE(IteratorSymbolMap, SymbolRef, IteratorPosition)
-REGISTER_MAP_WITH_PROGRAMSTATE(IteratorRegionMap, const MemRegion *,
-                               IteratorPosition)
-
-REGISTER_MAP_WITH_PROGRAMSTATE(IteratorComparisonMap, const SymExpr *,
-                               IteratorComparison)
-
-#define INIT_ID(Id)                                                            \
-  if (!II_##Id)                                                                \
-  II_##Id = &Ctx.Idents.get(#Id)
-
-namespace {
-
-bool isIteratorType(const QualType &Type);
-bool isIterator(const CXXRecordDecl *CRD);
-bool isEndCall(const FunctionDecl *Func);
-bool isSimpleComparisonOperator(OverloadedOperatorKind OK);
-bool isAccessOperator(OverloadedOperatorKind OK);
-bool isDecrementOperator(OverloadedOperatorKind OK);
-BinaryOperator::Opcode getOpcode(const SymExpr *SE);
-const RegionOrSymbol getRegionOrSymbol(const SVal &Val);
-const ProgramStateRef processComparison(ProgramStateRef State,
-                                        RegionOrSymbol LVal,
-                                        RegionOrSymbol RVal, bool Equal);
-const ProgramStateRef saveComparison(ProgramStateRef State,
-                                     const SymExpr *Condition, const SVal &LVal,
-                                     const SVal &RVal, bool Eq);
-const IteratorComparison *loadComparison(ProgramStateRef State,
-                                         const SymExpr *Condition);
-const IteratorPosition *getIteratorPosition(ProgramStateRef State,
-                                            const SVal &Val);
-const IteratorPosition *getIteratorPosition(ProgramStateRef State,
-                                            RegionOrSymbol RegOrSym);
-ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val,
-                                    IteratorPosition Pos);
-ProgramStateRef setIteratorPosition(ProgramStateRef State,
-                                    RegionOrSymbol RegOrSym,
-                                    IteratorPosition Pos);
-ProgramStateRef adjustIteratorPosition(ProgramStateRef State,
-                                       RegionOrSymbol RegOrSym,
-                                       IteratorPosition Pos, bool Equal);
-bool contradictingIteratorPositions(IteratorPosition Pos1,
-                                    IteratorPosition Pos2, bool Equal);
-}
-
-IteratorPastEndChecker::IteratorPastEndChecker() {
-  PastEndBugType.reset(
-      new BugType(this, "Iterator Past End", "Misuse of STL APIs"));
-  PastEndBugType->setSuppressOnSink(true);
-}
-
-void IteratorPastEndChecker::checkPreCall(const CallEvent &Call,
-                                          CheckerContext &C) const {
-  // Check for access past end
-  const auto *Func = Call.getDecl()->getAsFunction();
-  if (!Func)
-    return;
-  if (Func->isOverloadedOperator()) {
-    if (isAccessOperator(Func->getOverloadedOperator())) {
-      if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
-        handleAccess(C, InstCall->getCXXThisVal());
-      } else {
-        handleAccess(C, Call.getArgSVal(0));
-      }
-    }
-  }
-}
-
-void IteratorPastEndChecker::checkPostCall(const CallEvent &Call,
-                                           CheckerContext &C) const {
-  // Record end() iterators, iterator decrementation and comparison
-  const auto *Func = Call.getDecl()->getAsFunction();
-  if (!Func)
-    return;
-  if (Func->isOverloadedOperator()) {
-    const auto Op = Func->getOverloadedOperator();
-    if (isSimpleComparisonOperator(Op)) {
-      if (Func->isCXXInstanceMember()) {
-        const auto &InstCall = static_cast<const CXXInstanceCall &>(Call);
-        handleComparison(C, InstCall.getReturnValue(), InstCall.getCXXThisVal(),
-                         InstCall.getArgSVal(0), Op);
-      } else {
-        handleComparison(C, Call.getReturnValue(), Call.getArgSVal(0),
-                         Call.getArgSVal(1), Op);
-      }
-    } else if (isDecrementOperator(Func->getOverloadedOperator())) {
-      if (Func->isCXXInstanceMember()) {
-        const auto &InstCall = static_cast<const CXXInstanceCall &>(Call);
-        handleDecrement(C, InstCall.getCXXThisVal());
-      } else {
-        handleDecrement(C, Call.getArgSVal(0));
-      }
-    }
-  } else if (Func->isCXXInstanceMember()) {
-    if (!isEndCall(Func))
-      return;
-    if (!isIteratorType(Call.getResultType()))
-      return;
-    handleEnd(C, Call.getReturnValue());
-  }
-}
-
-void IteratorPastEndChecker::checkPreStmt(const CXXOperatorCallExpr *COCE,
-                                          CheckerContext &C) const {
-  const auto *ThisExpr = COCE->getArg(0);
-
-  auto State = C.getState();
-  const auto *LCtx = C.getPredecessor()->getLocationContext();
-
-  const auto CurrentThis = State->getSVal(ThisExpr, LCtx);
-  if (const auto *Reg = CurrentThis.getAsRegion()) {
-    if (!Reg->getAs<CXXTempObjectRegion>())
-      return;
-    const auto OldState = C.getPredecessor()->getFirstPred()->getState();
-    const auto OldThis = OldState->getSVal(ThisExpr, LCtx);
-    const auto *Pos = getIteratorPosition(OldState, OldThis);
-    if (!Pos)
-      return;
-    State = setIteratorPosition(State, CurrentThis, *Pos);
-    C.addTransition(State);
-  }
-}
-
-void IteratorPastEndChecker::checkBeginFunction(CheckerContext &C) const {
-  // Copy state of iterator arguments to iterator parameters
-  auto State = C.getState();
-  const auto *LCtx = C.getLocationContext();
-
-  const auto *Site = cast<StackFrameContext>(LCtx)->getCallSite();
-  if (!Site)
-    return;
-
-  const auto *FD = dyn_cast<FunctionDecl>(LCtx->getDecl());
-  if (!FD)
-    return;
-
-  const auto *CE = dyn_cast<CallExpr>(Site);
-  if (!CE)
-    return;
-
-  bool Change = false;
-  int idx = 0;
-  for (const auto P : FD->parameters()) {
-    auto Param = State->getLValue(P, LCtx);
-    auto Arg = State->getSVal(CE->getArg(idx++), LCtx->getParent());
-    const auto *Pos = getIteratorPosition(State, Arg);
-    if (!Pos)
-      continue;
-    State = setIteratorPosition(State, Param, *Pos);
-    Change = true;
-  }
-  if (Change) {
-    C.addTransition(State);
-  }
-}
-
-void IteratorPastEndChecker::checkPostStmt(const CXXConstructExpr *CCE,
-                                           CheckerContext &C) const {
-  // Transfer iterator state in case of copy or move by constructor
-  const auto *ctr = CCE->getConstructor();
-  if (!ctr->isCopyOrMoveConstructor())
-    return;
-  const auto *RHSExpr = CCE->getArg(0);
-
-  auto State = C.getState();
-  const auto *LCtx = C.getLocationContext();
-
-  const auto RetVal = State->getSVal(CCE, LCtx);
-
-  const auto RHSVal = State->getSVal(RHSExpr, LCtx);
-  const auto *RHSPos = getIteratorPosition(State, RHSVal);
-  if (!RHSPos)
-    return;
-  State = setIteratorPosition(State, RetVal, *RHSPos);
-  C.addTransition(State);
-}
-
-void IteratorPastEndChecker::checkPostStmt(const DeclStmt *DS,
-                                           CheckerContext &C) const {
-  // Transfer iterator state to new variable declaration
-  for (const auto *D : DS->decls()) {
-    const auto *VD = dyn_cast<VarDecl>(D);
-    if (!VD || !VD->hasInit())
-      continue;
-
-    auto State = C.getState();
-    const auto *LCtx = C.getPredecessor()->getLocationContext();
-    const auto *Pos =
-        getIteratorPosition(State, State->getSVal(VD->getInit(), LCtx));
-    if (!Pos)
-      continue;
-    State = setIteratorPosition(State, State->getLValue(VD, LCtx), *Pos);
-    C.addTransition(State);
-  }
-}
-
-void IteratorPastEndChecker::checkPostStmt(const MaterializeTemporaryExpr *MTE,
-                                           CheckerContext &C) const {
-  /* Transfer iterator state for to temporary objects */
-  auto State = C.getState();
-  const auto *LCtx = C.getPredecessor()->getLocationContext();
-  const auto *Pos =
-      getIteratorPosition(State, State->getSVal(MTE->GetTemporaryExpr(), LCtx));
-  if (!Pos)
-    return;
-  State = setIteratorPosition(State, State->getSVal(MTE, LCtx), *Pos);
-  C.addTransition(State);
-}
-
-void IteratorPastEndChecker::checkDeadSymbols(SymbolReaper &SR,
-                                              CheckerContext &C) const {
-  auto State = C.getState();
-
-  auto RegionMap = State->get<IteratorRegionMap>();
-  for (const auto Reg : RegionMap) {
-    if (!SR.isLiveRegion(Reg.first)) {
-      State = State->remove<IteratorRegionMap>(Reg.first);
-    }
-  }
-
-  auto SymbolMap = State->get<IteratorSymbolMap>();
-  for (const auto Sym : SymbolMap) {
-    if (SR.isDead(Sym.first)) {
-      State = State->remove<IteratorSymbolMap>(Sym.first);
-    }
-  }
-
-  auto ComparisonMap = State->get<IteratorComparisonMap>();
-  for (const auto Comp : ComparisonMap) {
-    if (SR.isDead(Comp.first)) {
-      State = State->remove<IteratorComparisonMap>(Comp.first);
-    }
-  }
-}
-
-ProgramStateRef IteratorPastEndChecker::evalAssume(ProgramStateRef State,
-                                                   SVal Cond,
-                                                   bool Assumption) const {
-  // Load recorded comparison and transfer iterator state between sides
-  // according to comparison operator and assumption
-  const auto *SE = Cond.getAsSymExpr();
-  if (!SE)
-    return State;
-
-  auto Opc = getOpcode(SE);
-  if (Opc != BO_EQ && Opc != BO_NE)
-    return State;
-
-  bool Negated = false;
-  const auto *Comp = loadComparison(State, SE);
-  if (!Comp) {
-    // Try negated comparison, which is a SymExpr to 0 integer comparison
-    const auto *SIE = dyn_cast<SymIntExpr>(SE);
-    if (!SIE)
-      return State;
-
-    if (SIE->getRHS() != 0)
-      return State;
-
-    SE = SIE->getLHS();
-    Negated = SIE->getOpcode() == BO_EQ; // Equal to zero means negation
-    Opc = getOpcode(SE);
-    if (Opc != BO_EQ && Opc != BO_NE)
-      return State;
-
-    Comp = loadComparison(State, SE);
-    if (!Comp)
-      return State;
-  }
-
-  return processComparison(State, Comp->getLeft(), Comp->getRight(),
-                           (Comp->isEquality() == Assumption) != Negated);
-}
-
-// FIXME: Evaluation of these STL calls should be moved to StdCLibraryFunctions
-//       checker (see patch r284960) or another similar checker for C++ STL
-//       functions (e.g. StdCXXLibraryFunctions or StdCppLibraryFunctions).
-bool IteratorPastEndChecker::evalCall(const CallExpr *CE,
-                                      CheckerContext &C) const {
-  const FunctionDecl *FD = C.getCalleeDecl(CE);
-  if (!FD)
-    return false;
-
-  ASTContext &Ctx = C.getASTContext();
-  initIdentifiers(Ctx);
-
-  if (FD->getKind() == Decl::Function) {
-    if (FD->isInStdNamespace()) {
-      if (FD->getIdentifier() == II_find) {
-        return evalFind(C, CE);
-      } else if (FD->getIdentifier() == II_find_end) {
-        return evalFindEnd(C, CE);
-      } else if (FD->getIdentifier() == II_find_first_of) {
-        return evalFindFirstOf(C, CE);
-      } else if (FD->getIdentifier() == II_find_if) {
-        return evalFindIf(C, CE);
-      } else if (FD->getIdentifier() == II_find_if_not) {
-        return evalFindIfNot(C, CE);
-      } else if (FD->getIdentifier() == II_upper_bound) {
-        return evalUpperBound(C, CE);
-      } else if (FD->getIdentifier() == II_lower_bound) {
-        return evalLowerBound(C, CE);
-      } else if (FD->getIdentifier() == II_search) {
-        return evalSearch(C, CE);
-      } else if (FD->getIdentifier() == II_search_n) {
-        return evalSearchN(C, CE);
-      }
-    }
-  }
-
-  return false;
-}
-
-void IteratorPastEndChecker::handleComparison(CheckerContext &C,
-                                              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();
-  if (const auto *Condition = RetVal.getAsSymbolicExpression()) {
-    const auto *LPos = getIteratorPosition(State, LVal);
-    const auto *RPos = getIteratorPosition(State, RVal);
-    if (!LPos && !RPos)
-      return;
-    State = saveComparison(State, Condition, LVal, RVal, Op == OO_EqualEqual);
-    C.addTransition(State);
-  } else if (const auto TruthVal = RetVal.getAs<nonloc::ConcreteInt>()) {
-    if ((State = processComparison(
-             State, getRegionOrSymbol(LVal), getRegionOrSymbol(RVal),
-             (Op == OO_EqualEqual) == (TruthVal->getValue() != 0)))) {
-      C.addTransition(State);
-    } else {
-      C.generateSink(State, C.getPredecessor());
-    }
-  }
-}
-
-void IteratorPastEndChecker::handleAccess(CheckerContext &C,
-                                          const SVal &Val) const {
-  auto State = C.getState();
-  const auto *Pos = getIteratorPosition(State, Val);
-  if (Pos && Pos->isOutofRange()) {
-    auto *N = C.generateNonFatalErrorNode(State);
-    if (!N) {
-      return;
-    }
-    reportPastEndBug("Iterator accessed past its end.", Val, C, N);
-  }
-}
-
-void IteratorPastEndChecker::handleDecrement(CheckerContext &C,
-                                             const SVal &Val) const {
-  auto State = C.getState();
-  const auto *Pos = getIteratorPosition(State, Val);
-  if (Pos && Pos->isOutofRange()) {
-    State = setIteratorPosition(State, Val, IteratorPosition::getInRange());
-    // FIXME: We could also check for iterators ahead of their beginnig in the
-    //       future, but currently we do not care for such errors. We also
-    //       assume that the iterator is not past its end by more then one
-    //       position.
-    C.addTransition(State);
-  }
-}
-
-void IteratorPastEndChecker::handleEnd(CheckerContext &C,
-                                       const SVal &RetVal) const {
-  auto State = C.getState();
-  State = setIteratorPosition(State, RetVal, IteratorPosition::getOutofRange());
-  C.addTransition(State);
-}
-
-bool IteratorPastEndChecker::evalFind(CheckerContext &C,
-                                      const CallExpr *CE) const {
-  if (CE->getNumArgs() == 3 && isIteratorType(CE->getArg(0)->getType()) &&
-      isIteratorType(CE->getArg(1)->getType())) {
-    Find(C, CE);
-    return true;
-  }
-  return false;
-}
-
-bool IteratorPastEndChecker::evalFindEnd(CheckerContext &C,
-                                         const CallExpr *CE) const {
-  if ((CE->getNumArgs() == 4 || CE->getNumArgs() == 5) &&
-      isIteratorType(CE->getArg(0)->getType()) &&
-      isIteratorType(CE->getArg(1)->getType()) &&
-      isIteratorType(CE->getArg(2)->getType()) &&
-      isIteratorType(CE->getArg(3)->getType())) {
-    Find(C, CE);
-    return true;
-  }
-  return false;
-}
-
-bool IteratorPastEndChecker::evalFindFirstOf(CheckerContext &C,
-                                             const CallExpr *CE) const {
-  if ((CE->getNumArgs() == 4 || CE->getNumArgs() == 5) &&
-      isIteratorType(CE->getArg(0)->getType()) &&
-      isIteratorType(CE->getArg(1)->getType()) &&
-      isIteratorType(CE->getArg(2)->getType()) &&
-      isIteratorType(CE->getArg(3)->getType())) {
-    Find(C, CE);
-    return true;
-  }
-  return false;
-}
-
-bool IteratorPastEndChecker::evalFindIf(CheckerContext &C,
-                                        const CallExpr *CE) const {
-  if (CE->getNumArgs() == 3 && isIteratorType(CE->getArg(0)->getType()) &&
-      isIteratorType(CE->getArg(1)->getType())) {
-    Find(C, CE);
-    return true;
-  }
-  return false;
-}
-
-bool IteratorPastEndChecker::evalFindIfNot(CheckerContext &C,
-                                           const CallExpr *CE) const {
-  if (CE->getNumArgs() == 3 && isIteratorType(CE->getArg(0)->getType()) &&
-      isIteratorType(CE->getArg(1)->getType())) {
-    Find(C, CE);
-    return true;
-  }
-  return false;
-}
-
-bool IteratorPastEndChecker::evalLowerBound(CheckerContext &C,
-                                            const CallExpr *CE) const {
-  if ((CE->getNumArgs() == 3 || CE->getNumArgs() == 4) &&
-      isIteratorType(CE->getArg(0)->getType()) &&
-      isIteratorType(CE->getArg(1)->getType())) {
-    Find(C, CE);
-    return true;
-  }
-  return false;
-}
-
-bool IteratorPastEndChecker::evalUpperBound(CheckerContext &C,
-                                            const CallExpr *CE) const {
-  if ((CE->getNumArgs() == 3 || CE->getNumArgs() == 4) &&
-      isIteratorType(CE->getArg(0)->getType()) &&
-      isIteratorType(CE->getArg(1)->getType())) {
-    Find(C, CE);
-    return true;
-  }
-  return false;
-}
-
-bool IteratorPastEndChecker::evalSearch(CheckerContext &C,
-                                        const CallExpr *CE) const {
-  if ((CE->getNumArgs() == 4 || CE->getNumArgs() == 5) &&
-      isIteratorType(CE->getArg(0)->getType()) &&
-      isIteratorType(CE->getArg(1)->getType()) &&
-      isIteratorType(CE->getArg(2)->getType()) &&
-      isIteratorType(CE->getArg(3)->getType())) {
-    Find(C, CE);
-    return true;
-  }
-  return false;
-}
-
-bool IteratorPastEndChecker::evalSearchN(CheckerContext &C,
-                                         const CallExpr *CE) const {
-  if ((CE->getNumArgs() == 4 || CE->getNumArgs() == 5) &&
-      isIteratorType(CE->getArg(0)->getType()) &&
-      isIteratorType(CE->getArg(1)->getType())) {
-    Find(C, CE);
-    return true;
-  }
-  return false;
-}
-
-void IteratorPastEndChecker::Find(CheckerContext &C, const CallExpr *CE) const {
-  auto state = C.getState();
-  auto &svalBuilder = C.getSValBuilder();
-  const auto *LCtx = C.getLocationContext();
-
-  auto RetVal = svalBuilder.conjureSymbolVal(nullptr, CE, LCtx, C.blockCount());
-  auto SecondParam = state->getSVal(CE->getArg(1), LCtx);
-
-  auto stateFound = state->BindExpr(CE, LCtx, RetVal);
-  auto stateNotFound = state->BindExpr(CE, LCtx, SecondParam);
-
-  C.addTransition(stateFound);
-  C.addTransition(stateNotFound);
-}
-
-void IteratorPastEndChecker::reportPastEndBug(const StringRef &Message,
-                                              const SVal &Val,
-                                              CheckerContext &C,
-                                              ExplodedNode *ErrNode) const {
-  auto R = llvm::make_unique<BugReport>(*PastEndBugType, Message, ErrNode);
-  R->markInteresting(Val);
-  C.emitReport(std::move(R));
-}
-
-void IteratorPastEndChecker::initIdentifiers(ASTContext &Ctx) const {
-  INIT_ID(find);
-  INIT_ID(find_end);
-  INIT_ID(find_first_of);
-  INIT_ID(find_if);
-  INIT_ID(find_if_not);
-  INIT_ID(lower_bound);
-  INIT_ID(upper_bound);
-  INIT_ID(search);
-  INIT_ID(search_n);
-}
-
-namespace {
-
-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 isEndCall(const FunctionDecl *Func) {
-  const auto *IdInfo = Func->getIdentifier();
-  if (!IdInfo)
-    return false;
-  return IdInfo->getName().endswith_lower("end");
-}
-
-bool isSimpleComparisonOperator(OverloadedOperatorKind OK) {
-  return OK == OO_EqualEqual || OK == OO_ExclaimEqual;
-}
-
-bool isAccessOperator(OverloadedOperatorKind OK) {
-  return OK == OO_Star || OK == OO_Arrow || OK == OO_ArrowStar ||
-         OK == OO_Plus || OK == OO_PlusEqual || OK == OO_PlusPlus ||
-         OK == OO_Subscript;
-}
-
-bool isDecrementOperator(OverloadedOperatorKind OK) {
-  return OK == OO_MinusEqual || OK == OO_MinusMinus;
-}
-
-BinaryOperator::Opcode getOpcode(const SymExpr *SE) {
-  if (const auto *BSE = dyn_cast<BinarySymExpr>(SE)) {
-    return BSE->getOpcode();
-  } else if (const auto *SC = dyn_cast<SymbolConjured>(SE)) {
-    const auto *COE = dyn_cast<CXXOperatorCallExpr>(SC->getStmt());
-    if (!COE)
-      return BO_Comma; // Extremal value, neither EQ nor NE
-    if (COE->getOperator() == OO_EqualEqual) {
-      return BO_EQ;
-    } else if (COE->getOperator() == OO_ExclaimEqual) {
-      return BO_NE;
-    }
-    return BO_Comma; // Extremal value, neither EQ nor NE
-  }
-  return BO_Comma; // Extremal value, neither EQ nor NE
-}
-
-const RegionOrSymbol getRegionOrSymbol(const SVal &Val) {
-  if (const auto Reg = Val.getAsRegion()) {
-    return Reg;
-  } else if (const auto Sym = Val.getAsSymbol()) {
-    return Sym;
-  } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
-    return LCVal->getRegion();
-  }
-  return RegionOrSymbol();
-}
-
-const ProgramStateRef processComparison(ProgramStateRef State,
-                                        RegionOrSymbol LVal,
-                                        RegionOrSymbol RVal, bool Equal) {
-  const auto *LPos = getIteratorPosition(State, LVal);
-  const auto *RPos = getIteratorPosition(State, RVal);
-  if (LPos && !RPos) {
-    State = adjustIteratorPosition(State, RVal, *LPos, Equal);
-  } else if (!LPos && RPos) {
-    State = adjustIteratorPosition(State, LVal, *RPos, Equal);
-  } else if (LPos && RPos) {
-    if (contradictingIteratorPositions(*LPos, *RPos, Equal)) {
-      return nullptr;
-    }
-  }
-  return State;
-}
-
-const ProgramStateRef saveComparison(ProgramStateRef State,
-                                     const SymExpr *Condition, const SVal &LVal,
-                                     const SVal &RVal, bool Eq) {
-  const auto Left = getRegionOrSymbol(LVal);
-  const auto Right = getRegionOrSymbol(RVal);
-  if (!Left || !Right)
-    return State;
-  return State->set<IteratorComparisonMap>(Condition,
-                                           IteratorComparison(Left, Right, Eq));
-}
-
-const IteratorComparison *loadComparison(ProgramStateRef State,
-                                         const SymExpr *Condition) {
-  return State->get<IteratorComparisonMap>(Condition);
-}
-
-const IteratorPosition *getIteratorPosition(ProgramStateRef State,
-                                            const SVal &Val) {
-  if (const auto Reg = Val.getAsRegion()) {
-    return State->get<IteratorRegionMap>(Reg);
-  } else if (const auto Sym = Val.getAsSymbol()) {
-    return State->get<IteratorSymbolMap>(Sym);
-  } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
-    return State->get<IteratorRegionMap>(LCVal->getRegion());
-  }
-  return nullptr;
-}
-
-const IteratorPosition *getIteratorPosition(ProgramStateRef State,
-                                            RegionOrSymbol RegOrSym) {
-  if (RegOrSym.is<const MemRegion *>()) {
-    return State->get<IteratorRegionMap>(RegOrSym.get<const MemRegion *>());
-  } else if (RegOrSym.is<SymbolRef>()) {
-    return State->get<IteratorSymbolMap>(RegOrSym.get<SymbolRef>());
-  }
-  return nullptr;
-}
-
-ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val,
-                                    IteratorPosition Pos) {
-  if (const auto Reg = Val.getAsRegion()) {
-    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 setIteratorPosition(ProgramStateRef State,
-                                    RegionOrSymbol RegOrSym,
-                                    IteratorPosition Pos) {
-  if (RegOrSym.is<const MemRegion *>()) {
-    return State->set<IteratorRegionMap>(RegOrSym.get<const MemRegion *>(),
-                                         Pos);
-  } else if (RegOrSym.is<SymbolRef>()) {
-    return State->set<IteratorSymbolMap>(RegOrSym.get<SymbolRef>(), Pos);
-  }
-  return nullptr;
-}
-
-ProgramStateRef adjustIteratorPosition(ProgramStateRef State,
-                                       RegionOrSymbol RegOrSym,
-                                       IteratorPosition Pos, bool Equal) {
-
-  if ((Pos.isInRange() && Equal) || (Pos.isOutofRange() && !Equal)) {
-    return setIteratorPosition(State, RegOrSym, IteratorPosition::getInRange());
-  } else if (Pos.isOutofRange() && Equal) {
-    return setIteratorPosition(State, RegOrSym,
-                               IteratorPosition::getOutofRange());
-  } else {
-    return State;
-  }
-}
-
-bool contradictingIteratorPositions(IteratorPosition Pos1,
-                                    IteratorPosition Pos2, bool Equal) {
-  return ((Pos1 != Pos2) && Equal) ||
-         ((Pos1.isOutofRange() && Pos2.isOutofRange()) && !Equal);
-}
-}
-
-void ento::registerIteratorPastEndChecker(CheckerManager &Mgr) {
-  Mgr.registerChecker<IteratorPastEndChecker>();
-}

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

 // Like the compiler, the static analyzer treats some functions differently if
 // they come from a system header -- for example, it is assumed that system
 // functions do not arbitrarily free() their parameters, and that some bugs
 // found in system headers cannot be fixed by the user and should be
 // suppressed.
 #pragma clang system_header
 
 typedef unsigned char uint8_t;
 
 typedef __typeof__(sizeof(int)) size_t;
+typedef __typeof__((char*)0-(char*)0) ptrdiff_t;
 void *memmove(void *s1, const void *s2, size_t n);
 
-template <typename T, typename Ptr, typename Ref> struct __iterator {
-  typedef __iterator<T, T *, T &> iterator;
-  typedef __iterator<T, const T *, const T &> const_iterator;
-
-  __iterator(const Ptr p) : ptr(p) {}
-
-  __iterator<T, Ptr, Ref> operator++() { return *this; }
-  __iterator<T, Ptr, Ref> operator++(int) { return *this; }
-  __iterator<T, Ptr, Ref> operator--() { return *this; }
-  __iterator<T, Ptr, Ref> operator--(int) { return *this; }
+namespace std {
+  struct input_iterator_tag { };
+  struct output_iterator_tag { };
+  struct forward_iterator_tag : public input_iterator_tag { };
+  struct bidirectional_iterator_tag : public forward_iterator_tag { };
+  struct random_access_iterator_tag : public bidirectional_iterator_tag { };
+
+  template <typename Iterator> struct iterator_traits {
+    typedef typename Iterator::difference_type difference_type;
+    typedef typename Iterator::value_type value_type;
+    typedef typename Iterator::pointer pointer;
+    typedef typename Iterator::reference reference;
+    typedef typename Iterator::iterator_category iterator_category;
+  };
+}
+
+template <typename T, typename Ptr, typename Ref> struct __vector_iterator {
+  typedef __vector_iterator<T, T *, T &> iterator;
+  typedef __vector_iterator<T, const T *, const T &> const_iterator;
+
+  typedef ptrdiff_t difference_type;
+  typedef T value_type;
+  typedef Ptr pointer;
+  typedef Ref reference;
+  typedef std::random_access_iterator_tag iterator_category;
+
+  __vector_iterator(const Ptr p = 0) : ptr(p) {}
+  __vector_iterator(const iterator &rhs): ptr(rhs.base()) {}
+  __vector_iterator<T, Ptr, Ref> operator++() { ++ ptr; return *this; }
+  __vector_iterator<T, Ptr, Ref> operator++(int) {
+    auto tmp = *this;
+    ++ ptr;
+    return tmp;
+  }
+  __vector_iterator<T, Ptr, Ref> operator--() { -- ptr; return *this; }
+  __vector_iterator<T, Ptr, Ref> operator--(int) {
+    auto tmp = *this; -- ptr;
+    return tmp;
+  }
+  __vector_iterator<T, Ptr, Ref> operator+(difference_type n) {
+    return ptr + n;
+  }
+  __vector_iterator<T, Ptr, Ref> operator-(difference_type n) {
+    return ptr - n;
+  }
+  __vector_iterator<T, Ptr, Ref> operator+=(difference_type n) {
+    return ptr += n;
+  }
+  __vector_iterator<T, Ptr, Ref> operator-=(difference_type n) {
+    return ptr -= n;
+  }
+
   Ref operator*() const { return *ptr; }
   Ptr operator->() const { return *ptr; }
 
   bool operator==(const iterator &rhs) const { return ptr == rhs.ptr; }
   bool operator==(const const_iterator &rhs) const { return ptr == rhs.ptr; }
 
   bool operator!=(const iterator &rhs) const { return ptr != rhs.ptr; }
   bool operator!=(const const_iterator &rhs) const { return ptr != rhs.ptr; }
 
+  const Ptr& base() const { return ptr; }
+
 private:
   Ptr ptr;
 };
 
+template <typename T, typename Ptr, typename Ref> struct __deque_iterator {
+  typedef __deque_iterator<T, T *, T &> iterator;
+  typedef __deque_iterator<T, const T *, const T &> const_iterator;
+
+  typedef ptrdiff_t difference_type;
+  typedef T value_type;
+  typedef Ptr pointer;
+  typedef Ref reference;
+  typedef std::random_access_iterator_tag iterator_category;
+
+  __deque_iterator(const Ptr p = 0) : ptr(p) {}
+  __deque_iterator(const iterator &rhs): ptr(rhs.base()) {}
+  __deque_iterator<T, Ptr, Ref> operator++() { ++ ptr; return *this; }
+  __deque_iterator<T, Ptr, Ref> operator++(int) {
+    auto tmp = *this;
+    ++ ptr;
+    return tmp;
+  }
+  __deque_iterator<T, Ptr, Ref> operator--() { -- ptr; return *this; }
+  __deque_iterator<T, Ptr, Ref> operator--(int) {
+    auto tmp = *this; -- ptr;
+    return tmp;
+  }
+  __deque_iterator<T, Ptr, Ref> operator+(difference_type n) {
+    return ptr + n;
+  }
+  __deque_iterator<T, Ptr, Ref> operator-(difference_type n) {
+    return ptr - n;
+  }
+  __deque_iterator<T, Ptr, Ref> operator+=(difference_type n) {
+    return ptr += n;
+  }
+  __deque_iterator<T, Ptr, Ref> operator-=(difference_type n) {
+    return ptr -= n;
+  }
+
+  Ref operator*() const { return *ptr; }
+  Ptr operator->() const { return *ptr; }
+
+  bool operator==(const iterator &rhs) const { return ptr == rhs.ptr; }
+  bool operator==(const const_iterator &rhs) const { return ptr == rhs.ptr; }
+
+  bool operator!=(const iterator &rhs) const { return ptr != rhs.ptr; }
+  bool operator!=(const const_iterator &rhs) const { return ptr != rhs.ptr; }
+
+  const Ptr& base() const { return ptr; }
+
+private:
+  Ptr ptr;
+};
+
+template <typename T, typename Ptr, typename Ref> struct __list_iterator {
+  typedef __list_iterator<T, __typeof__(T::data) *, __typeof__(T::data) &> iterator;
+  typedef __list_iterator<T, const __typeof__(T::data) *, const __typeof__(T::data) &> const_iterator;
+
+  typedef ptrdiff_t difference_type;
+  typedef T value_type;
+  typedef Ptr pointer;
+  typedef Ref reference;
+  typedef std::bidirectional_iterator_tag iterator_category;
+
+  __list_iterator(T* it = 0) : item(it) {}
+  __list_iterator(const iterator &rhs): item(rhs.base()) {}
+  __list_iterator<T, Ptr, Ref> operator++() { item = item->next; return *this; }
+  __list_iterator<T, Ptr, Ref> operator++(int) {
+    auto tmp = *this;
+    item = item->next;
+    return tmp;
+  }
+  __list_iterator<T, Ptr, Ref> operator--() { item = item->prev; return *this; }
+  __list_iterator<T, Ptr, Ref> operator--(int) {
+    auto tmp = *this;
+    item = item->prev;
+    return tmp;
+  }
+
+  Ref operator*() const { return item->data; }
+  Ptr operator->() const { return item->data; }
+
+  bool operator==(const iterator &rhs) const { return item == rhs->item; }
+  bool operator==(const const_iterator &rhs) const { return item == rhs->item; }
+
+  bool operator!=(const iterator &rhs) const { return item != rhs->item; }
+  bool operator!=(const const_iterator &rhs) const { return item != rhs->item; }
+
+  const T* &base() const { return item; }
+
+private:
+  T* item;
+};
+
+template <typename T, typename Ptr, typename Ref> struct __fwdl_iterator {
+  typedef __fwdl_iterator<T, __typeof__(T::data) *, __typeof__(T::data) &> iterator;
+  typedef __fwdl_iterator<T, const __typeof__(T::data) *, const __typeof__(T::data) &> const_iterator;
+
+  typedef ptrdiff_t difference_type;
+  typedef T value_type;
+  typedef Ptr pointer;
+  typedef Ref reference;
+  typedef std::forward_iterator_tag iterator_category;
+
+  __fwdl_iterator(T* it = 0) : item(it) {}
+  __fwdl_iterator(const iterator &rhs): item(rhs.base()) {}
+  __fwdl_iterator<T, Ptr, Ref> operator++() { item = item->next; return *this; }
+  __fwdl_iterator<T, Ptr, Ref> operator++(int) {
+    auto tmp = *this;
+    item = item->next;
+    return tmp;
+  }
+  Ref operator*() const { return item->data; }
+  Ptr operator->() const { return item->data; }
+
+  bool operator==(const iterator &rhs) const { return item == rhs->item; }
+  bool operator==(const const_iterator &rhs) const { return item == rhs->item; }
+
+  bool operator!=(const iterator &rhs) const { return item != rhs->item; }
+  bool operator!=(const const_iterator &rhs) const { return item != rhs->item; }
+
+  const T* &base() const { return item; }
+
+private:
+  T* item;
+};
+
 namespace std {
   template <class T1, class T2>
   struct pair {
     T1 first;
     T2 second;
     
     pair() : first(), second() {}
     pair(const T1 &a, const T2 &b) : first(a), second(b) {}
     
     template<class U1, class U2>
-    pair(const pair<U1, U2> &other) : first(other.first), second(other.second) {}
+    pair(const pair<U1, U2> &other) : first(other.first),
+                                      second(other.second) {}
   };
   
   typedef __typeof__(sizeof(int)) size_t;
-  
+  template <class T> class initializer_list;
+  
+  template< class T > struct remove_reference      {typedef T type;};
+  template< class T > struct remove_reference<T&>  {typedef T type;};
+  template< class T > struct remove_reference<T&&> {typedef T type;};
+
+  template<class T> 
+  typename remove_reference<T>::type&& move(T&& a) {
+    typedef typename remove_reference<T>::type&& RvalRef;
+    return static_cast<RvalRef>(a);
+  }
+
   template<typename T>
   class vector {
-    typedef __iterator<T, T *, T &> iterator;
-    typedef __iterator<T, const T *, const T &> const_iterator;
+    typedef T value_type;
+    typedef size_t size_type;
+    typedef __vector_iterator<T, T *, T &> iterator;
+    typedef __vector_iterator<T, const T *, const T &> const_iterator;
 
     T *_start;
     T *_finish;
     T *_end_of_storage;
   public:
     vector() : _start(0), _finish(0), _end_of_storage(0) {}
+    template <typename InputIterator>
+    vector(InputIterator first, InputIterator last);
+    vector(const vector &other);
+    vector(vector &&other);
     ~vector();
     
     size_t size() const {
       return size_t(_finish - _start);
     }
-    
-    void push_back();
-    T pop_back();
+    vector& operator=(const vector &other);
+    vector& operator=(vector &&other);
+    vector& operator=(std::initializer_list<T> ilist);
+
+    void assign(size_type count, const T &value);
+    template <typename InputIterator >
+    void assign(InputIterator first, InputIterator last);
+    void assign(std::initializer_list<T> ilist);
+
+    void clear();
+
+    void push_back(const T &value);
+    void push_back(T &&value);
+    template<class... Args>
+    void emplace_back(Args&&... args);
+    void pop_back();
+
+    iterator insert(const_iterator position, const value_type &val);
+    iterator insert(const_iterator position, size_type n,
+                    const value_type &val);
+    template <typename InputIterator>
+    iterator insert(const_iterator position, InputIterator first,
+                    InputIterator last);
+    iterator insert(const_iterator position, value_type &&val);
+    iterator insert(const_iterator position, initializer_list<value_type> il);
+
+    template <class... Args>
+    iterator emplace(const_iterator position, Args&&... args);
+
+    iterator erase(const_iterator position);
+    iterator erase(const_iterator first, const_iterator last);
 
     T &operator[](size_t n) {
       return _start[n];
     }
     
     const T &operator[](size_t n) const {
       return _start[n];
     }
     
     iterator begin() { return iterator(_start); }
     const_iterator begin() const { return const_iterator(_start); }
+    const_iterator cbegin() const { return const_iterator(_start); }
     iterator end() { return iterator(_finish); }
     const_iterator end() const { return const_iterator(_finish); }
+    const_iterator cend() const { return const_iterator(_finish); }
+    T& front() { return *begin(); }
+    const T& front() const { return *begin(); }
+    T& back() { return *(end() - 1); }
+    const T& back() const { return *(end() - 1); }
+  };
+  
+  template<typename T>
+  class list {
+    struct __item {
+      T data;
+      __item *prev, *next;
+    } *_start, *_finish;
+  public:
+    typedef T value_type;
+    typedef size_t size_type;
+    typedef __list_iterator<__item, T *, T &> iterator;
+    typedef __list_iterator<__item, const T *, const T &> const_iterator;
+
+    list() : _start(0), _finish(0) {}
+    template <typename InputIterator>
+    list(InputIterator first, InputIterator last);
+    list(const list &other);
+    list(list &&other);
+    ~list();
+    
+    list& operator=(const list &other);
+    list& operator=(list &&other);
+    list& operator=(std::initializer_list<T> ilist);
+
+    void assign(size_type count, const T &value);
+    template <typename InputIterator >
+    void assign(InputIterator first, InputIterator last);
+    void assign(std::initializer_list<T> ilist);
+
+    void clear();
+
+    void push_back(const T &value);
+    void push_back(T &&value);
+    template<class... Args>
+    void emplace_back(Args&&... args);
+    void pop_back();
+
+    void push_front(const T &value);
+    void push_front(T &&value);
+    template<class... Args>
+    void emplace_front(Args&&... args);
+    void pop_front();
+
+    iterator insert(const_iterator position, const value_type &val);
+    iterator insert(const_iterator position, size_type n,
+                    const value_type &val);
+    template <typename InputIterator>
+    iterator insert(const_iterator position, InputIterator first,
+                    InputIterator last);
+    iterator insert(const_iterator position, value_type &&val);
+    iterator insert(const_iterator position, initializer_list<value_type> il);
+    
+    template <class... Args>
+    iterator emplace(const_iterator position, Args&&... args);
+
+    iterator erase(const_iterator position);
+    iterator erase(const_iterator first, const_iterator last);
+    
+    iterator begin() { return iterator(_start); }
+    const_iterator begin() const { return const_iterator(_start); }
+    const_iterator cbegin() const { return const_iterator(_start); }
+    iterator end() { return iterator(_finish); }
+    const_iterator end() const { return const_iterator(_finish); }
+    const_iterator cend() const { return const_iterator(_finish); }
+
+    T& front() { return *begin(); }
+    const T& front() const { return *begin(); }
+    T& back() { return *--end(); }
+    const T& back() const { return *--end(); }
+  };
+
+  template<typename T>
+  class deque {
+    typedef T value_type;
+    typedef size_t size_type;
+    typedef __deque_iterator<T, T *, T &> iterator;
+    typedef __deque_iterator<T, const T *, const T &> const_iterator;
+
+    T *_start;
+    T *_finish;
+    T *_end_of_storage;
+  public:
+    deque() : _start(0), _finish(0), _end_of_storage(0) {}
+    template <typename InputIterator>
+    deque(InputIterator first, InputIterator last);
+    deque(const deque &other);
+    deque(deque &&other);
+    ~deque();
+    
+    size_t size() const {
+      return size_t(_finish - _start);
+    }
+    
+    deque& operator=(const deque &other);
+    deque& operator=(deque &&other);
+    deque& operator=(std::initializer_list<T> ilist);
+
+    void assign(size_type count, const T &value);
+    template <typename InputIterator >
+    void assign(InputIterator first, InputIterator last);
+    void assign(std::initializer_list<T> ilist);
+
+    void clear();
+
+    void push_back(const T &value);
+    void push_back(T &&value);
+    template<class... Args>
+      void emplace_back(Args&&... args);
+    void pop_back();
+
+    void push_front(const T &value);
+    void push_front(T &&value);
+    template<class... Args>
+      void emplace_front(Args&&... args);
+    void pop_front();
+
+    iterator insert(const_iterator position, const value_type &val);
+    iterator insert(const_iterator position, size_type n,
+                    const value_type &val);
+    template <typename InputIterator>
+    iterator insert(const_iterator position, InputIterator first,
+                    InputIterator last);
+    iterator insert(const_iterator position, value_type &&val);
+    iterator insert(const_iterator position, initializer_list<value_type> il);
+    
+    template <class... Args>
+      iterator emplace(const_iterator position, Args&&... args);
+
+    iterator erase(const_iterator position);
+    iterator erase(const_iterator first, const_iterator last);
+
+    T &operator[](size_t n) {
+      return _start[n];
+    }
+    
+    const T &operator[](size_t n) const {
+      return _start[n];
+    }
+    
+    iterator begin() { return iterator(_start); }
+    const_iterator begin() const { return const_iterator(_start); }
+    const_iterator cbegin() const { return const_iterator(_start); }
+    iterator end() { return iterator(_finish); }
+    const_iterator end() const { return const_iterator(_finish); }
+    const_iterator cend() const { return const_iterator(_finish); }
+    T& front() { return *begin(); }
+    const T& front() const { return *begin(); }
+    T& back() { return *(end() - 1); }
+    const T& back() const { return *(end() - 1); }
+  };
+  
+  template<typename T>
+  class forward_list {
+    struct __item {
+      T data;
+      __item *next;
+    } *_start;
+  public:
+    typedef T value_type;
+    typedef size_t size_type;
+    typedef __fwdl_iterator<__item, T *, T &> iterator;
+    typedef __fwdl_iterator<__item, const T *, const T &> const_iterator;
+
+    forward_list() : _start(0) {}
+    template <typename InputIterator>
+    forward_list(InputIterator first, InputIterator last);
+    forward_list(const forward_list &other);
+    forward_list(forward_list &&other);
+    ~forward_list();
+    
+    forward_list& operator=(const forward_list &other);
+    forward_list& operator=(forward_list &&other);
+    forward_list& operator=(std::initializer_list<T> ilist);
+
+    void assign(size_type count, const T &value);
+    template <typename InputIterator >
+    void assign(InputIterator first, InputIterator last);
+    void assign(std::initializer_list<T> ilist);
+
+    void clear();
+
+    void push_front(const T &value);
+    void push_front(T &&value);
+    template<class... Args>
+    void emplace_front(Args&&... args);
+    void pop_front();
+
+    iterator insert_after(const_iterator position, const value_type &val);
+    iterator insert_after(const_iterator position, value_type &&val);
+    iterator insert_after(const_iterator position, size_type n,
+                          const value_type &val);
+    template <typename InputIterator>
+    iterator insert_after(const_iterator position, InputIterator first,
+                          InputIterator last);
+    iterator insert_after(const_iterator position,
+                          initializer_list<value_type> il);
+    
+    template <class... Args>
+    iterator emplace_after(const_iterator position, Args&&... args);
+
+    iterator erase_after(const_iterator position);
+    iterator erase_after(const_iterator first, const_iterator last);
+    
+    iterator begin() { return iterator(_start); }
+    const_iterator begin() const { return const_iterator(_start); }
+    const_iterator cbegin() const { return const_iterator(_start); }
+    iterator end() { return iterator(); }
+    const_iterator end() const { return const_iterator(); }
+    const_iterator cend() const { return const_iterator(); }
+
+    T& front() { return *begin(); }
+    const T& front() const { return *begin(); }
   };
-  
   class exception {
   public:
     exception() throw();
     virtual ~exception() throw();
     virtual const char *what() const throw() {
       return 0;
     }
   };
>::type __copy_backward(_Tp* __first, _Tp* __last, _Up* __result) {
     }
     return __result;
   }
 
   template<class InputIter, class OutputIter>
   OutputIter copy_backward(InputIter II, InputIter IE, OutputIter OI) {
     return __copy_backward(II, IE, OI);
   }
+}
+
+template <class BidirectionalIterator, class Distance>
+void __advance (BidirectionalIterator& it, Distance n,
+                std::bidirectional_iterator_tag) {
+  if (n >= 0) while(n-- > 0) ++it; else while (n++<0) --it;
+}
+
+template <class RandomAccessIterator, class Distance>
+void __advance (RandomAccessIterator& it, Distance n,
+                std::random_access_iterator_tag) {
+  it += n;
+}
+
+namespace std {
+  template <class InputIterator, class Distance>
+  void advance (InputIterator& it, Distance n) {
+    __advance(it, n, typename InputIterator::iterator_category());
+  }
+
+  template <class BidirectionalIterator>
+  BidirectionalIterator
+  prev (BidirectionalIterator it,
+        typename iterator_traits<BidirectionalIterator>::difference_type n =
+        1) {
+    advance(it, -n);
+    return it;
+  }
 
   template <class InputIterator, class T>
   InputIterator find(InputIterator first, InputIterator last, const T &val);
   template <class ForwardIterator1, class ForwardIterator2>
   ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1,
                             ForwardIterator2 first2, ForwardIterator2 last2);
   template <class ForwardIterator1, class ForwardIterator2>
   ForwardIterator1 find_first_of(ForwardIterator1 first1,
InputIterator upper_bound(InputIterator first, InputIterator last,
                             const T &val);
   template <class ForwardIterator1, class ForwardIterator2>
   ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1,
                           ForwardIterator2 first2, ForwardIterator2 last2);
   template <class ForwardIterator1, class ForwardIterator2>
   ForwardIterator1 search_n(ForwardIterator1 first1, ForwardIterator1 last1,
                             ForwardIterator2 first2, ForwardIterator2 last2);
 
-  struct input_iterator_tag { };
-  struct output_iterator_tag { };
-  struct forward_iterator_tag : public input_iterator_tag { };
-  struct bidirectional_iterator_tag : public forward_iterator_tag { };
-  struct random_access_iterator_tag : public bidirectional_iterator_tag { };
+  template <class InputIterator, class OutputIterator>
+  OutputIterator copy(InputIterator first, InputIterator last,
+                      OutputIterator result);
 
 }
 
 void* operator new(std::size_t, const std::nothrow_t&) throw();
 void* operator new[](std::size_t, const std::nothrow_t&) throw();
 void operator delete(void*, const std::nothrow_t&) throw();
 void operator delete[](void*, const std::nothrow_t&) throw();
 

test/Analysis/diagnostics/explicit-suppression.cpp

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

test/Analysis/invalidated-iterator.cpp

+// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.InvalidatedIterator -analyzer-eagerly-assume -analyzer-config c++-container-inlining=false %s -verify
+// RUN: %clang_analyze_cc1 -std=c++11 -analyze -analyzer-checker=core,cplusplus,alpha.cplusplus.InvalidatedIterator -analyzer-eagerly-assume -analyzer-config c++-container-inlining=true -DINLINE=1 %s -verify
+
+#include "Inputs/system-header-simulator-cxx.h"
+
+void bad_copy_assign_operator_list1(std::list<int> &L1,
+                                    const std::list<int> &L2) {
+  auto i0 = L1.cbegin();
+  L1 = L2;
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_copy_assign_operator_vector1(std::vector<int> &V1,
+                                      const std::vector<int> &V2) {
+  auto i0 = V1.cbegin();
+  V1 = V2;
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_copy_assign_operator_deque1(std::deque<int> &D1,
+                                     const std::deque<int> &D2) {
+  auto i0 = D1.cbegin();
+  D1 = D2;
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_copy_assign_operator_forward_list1(std::forward_list<int> &FL1,
+                                            const std::forward_list<int> &FL2) {
+  auto i0 = FL1.cbegin();
+  FL1 = FL2;
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_assign_list1(std::list<int> &L, int n) {
+  auto i0 = L.cbegin();
+  L.assign(10, n);
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_assign_vector1(std::vector<int> &V, int n) {
+  auto i0 = V.cbegin();
+  V.assign(10, n);
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_assign_deque1(std::deque<int> &D, int n) {
+  auto i0 = D.cbegin();
+  D.assign(10, n);
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_assign_forward_list1(std::forward_list<int> &FL, int n) {
+  auto i0 = FL.cbegin();
+  FL.assign(10, n);
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void good_clear_list1(std::list<int> &L) {
+  auto i0 = L.cend();
+  L.clear();
+  --i0; // no-warning
+}
+
+void bad_clear_list1(std::list<int> &L) {
+  auto i0 = L.cbegin(), i1 = L.cend();
+  L.clear();
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_clear_vector1(std::vector<int> &V) {
+  auto i0 = V.cbegin(), i1 = V.cend();
+  V.clear();
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+  --i1; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_clear_deque1(std::deque<int> &D) {
+  auto i0 = D.cbegin(), i1 = D.cend();
+  D.clear();
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+  --i1; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void good_push_back_list1(std::list<int> &L, int n) {
+  auto i0 = L.cbegin(), i1 = L.cend();
+  L.push_back(n);
+  *i0; // no-warning
+  --i1; // no-warning
+}
+
+void good_push_back_vector1(std::vector<int> &V, int n) {
+  auto i0 = V.cbegin(), i1 = V.cend();
+  V.push_back(n);
+  *i0; // no-warning
+}
+
+void bad_push_back_vector1(std::vector<int> &V, int n) {
+  auto i0 = V.cbegin(), i1 = V.cend();
+  V.push_back(n);
+  --i1; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_push_back_deque1(std::deque<int> &D, int n) {
+  auto i0 = D.cbegin(), i1 = D.cend();
+  D.push_back(n);
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+  --i1; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void good_emplace_back_list1(std::list<int> &L, int n) {
+  auto i0 = L.cbegin(), i1 = L.cend();
+  L.emplace_back(n);
+  *i0; // no-warning
+  --i1; // no-warning
+}
+
+void good_emplace_back_vector1(std::vector<int> &V, int n) {
+  auto i0 = V.cbegin(), i1 = V.cend();
+  V.emplace_back(n);
+  *i0; // no-warning
+}
+
+void bad_emplace_back_vector1(std::vector<int> &V, int n) {
+  auto i0 = V.cbegin(), i1 = V.cend();
+  V.emplace_back(n);
+  --i1; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_emplace_back_deque1(std::deque<int> &D, int n) {
+  auto i0 = D.cbegin(), i1 = D.cend();
+  D.emplace_back(n);
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+  --i1; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void good_pop_back_list1(std::list<int> &L, int n) {
+  auto i0 = L.cbegin(), i1 = L.cend(), i2 = i1--;
+  L.pop_back();
+  *i0; // no-warning
+  *i2; // no-warning
+}
+
+void bad_pop_back_list1(std::list<int> &L, int n) {
+  auto i0 = L.cbegin(), i1 = L.cend(), i2 = i1--;
+  L.pop_back();
+  *i1; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void good_pop_back_vector1(std::vector<int> &V, int n) {
+  auto i0 = V.cbegin(), i1 = V.cend(), i2 = i1--;
+  V.pop_back();
+  *i0; // no-warning
+}
+
+void bad_pop_back_vector1(std::vector<int> &V, int n) {
+  auto i0 = V.cbegin(), i1 = V.cend(), i2 = i1--;
+  V.pop_back();
+  *i1; // expected-warning{{Invalidated iterator accessed}}
+  --i2; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void good_pop_back_deque1(std::deque<int> &D, int n) {
+  auto i0 = D.cbegin(), i1 = D.cend(), i2 = i1--;
+  D.pop_back();
+  *i0; // no-warning
+}
+
+void bad_pop_back_deque1(std::deque<int> &D, int n) {
+  auto i0 = D.cbegin(), i1 = D.cend(), i2 = i1--;
+  D.pop_back();
+  *i1; // expected-warning{{Invalidated iterator accessed}}
+  --i2; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void good_push_front_list1(std::list<int> &L, int n) {
+  auto i0 = L.cbegin(), i1 = L.cend();
+  L.push_front(n);
+  *i0; // no-warning
+  --i1; // no-warning
+}
+
+void bad_push_front_deque1(std::deque<int> &D, int n) {
+  auto i0 = D.cbegin(), i1 = D.cend();
+  D.push_front(n);
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+  --i1; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void good_push_front_forward_list1(std::forward_list<int> &FL, int n) {
+  auto i0 = FL.cbegin(), i1 = FL.cend();
+  FL.push_front(n);
+  *i0; // no-warning
+}
+
+void good_emplace_front_list1(std::list<int> &L, int n) {
+  auto i0 = L.cbegin(), i1 = L.cend();
+  L.emplace_front(n);
+  *i0; // no-warning
+  --i1; // no-warning
+}
+
+void bad_emplace_front_deque1(std::deque<int> &D, int n) {
+  auto i0 = D.cbegin(), i1 = D.cend();
+  D.emplace_front(n);
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+  --i1; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void good_emplace_front_forward_list1(std::forward_list<int> &FL, int n) {
+  auto i0 = FL.cbegin(), i1 = FL.cend();
+  FL.emplace_front(n);
+  *i0; // no-warning
+}
+
+void good_pop_front_list1(std::list<int> &L, int n) {
+  auto i1 = L.cbegin(), i0 = i1++;
+  L.pop_front();
+  *i1; // no-warning
+}
+
+void bad_pop_front_list1(std::list<int> &L, int n) {
+  auto i1 = L.cbegin(), i0 = i1++;
+  L.pop_front();
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void good_pop_front_deque1(std::deque<int> &D, int n) {
+  auto i1 = D.cbegin(), i0 = i1++;
+  D.pop_front();
+  *i1; // no-warning
+}
+
+void bad_pop_front_deque1(std::deque<int> &D, int n) {
+  auto i1 = D.cbegin(), i0 = i1++;
+  D.pop_front();
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void good_pop_front_forward_list1(std::forward_list<int> &FL, int n) {
+  auto i1 = FL.cbegin(), i0 = i1++;
+  FL.pop_front();
+  *i1; // no-warning
+}
+
+void bad_pop_front_forward_list1(std::forward_list<int> &FL, int n) {
+  auto i1 = FL.cbegin(), i0 = i1++;
+  FL.pop_front();
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void good_insert_list1(std::list<int> &L, int n) {
+  auto i1 = L.cbegin(), i0 = i1++;
+  L.insert(i1, n);
+  *i0; // no-warning
+  *i1; // no-warning
+}
+
+void good_insert_vector1(std::vector<int> &V, int n) {
+  auto i1 = V.cbegin(), i0 = i1++;
+  V.insert(i1, n);
+  *i0; // no-warning
+}
+
+void bad_insert_vector1(std::vector<int> &V, int n) {
+  auto i1 = V.cbegin(), i0 = i1++;
+  V.insert(i1, n);
+  *i1; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_insert_deque1(std::deque<int> &D, int n) {
+  auto i1 = D.cbegin(), i0 = i1++;
+  D.insert(i1, n);
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+  *i1; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void good_emplace_list1(std::list<int> &L, int n) {
+  auto i1 = L.cbegin(), i0 = i1++;
+  L.emplace(i1, n);
+  *i0; // no-warning
+  *i1; // no-warning
+}
+
+void good_emplace_vector1(std::vector<int> &V, int n) {
+  auto i1 = V.cbegin(), i0 = i1++;
+  V.emplace(i1, n);
+  *i0; // no-warning
+}
+
+void bad_emplace_vector1(std::vector<int> &V, int n) {
+  auto i1 = V.cbegin(), i0 = i1++;
+  V.emplace(i1, n);
+  *i1; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_emplace_deque1(std::deque<int> &D, int n) {
+  auto i1 = D.cbegin(), i0 = i1++;
+  D.emplace(i1, n);
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+  *i1; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void good_erase_list1(std::list<int> &L) {
+  auto i2 = L.cbegin(), i0 = i2++, i1 = i2++;
+  L.erase(i1);
+  *i0; // no-warning
+  *i2; // no-warning
+}
+
+void bad_erase_list1(std::list<int> &L) {
+  auto i0 = L.cbegin();
+  L.erase(i0);
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void good_erase_vector1(std::vector<int> &V) {
+  auto i2 = V.cbegin(), i0 = i2++, i1 = i2++;
+  V.erase(i1);
+  *i0; // no-warning
+}
+
+void bad_erase_vector1(std::vector<int> &V) {
+  auto i1 = V.cbegin(), i0 = i1++;
+  V.erase(i0);
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+  *i1; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_erase_deque1(std::deque<int> &D) {
+  auto i2 = D.cbegin(), i0 = i2++, i1 = i2++;
+  D.erase(i1);
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+  *i1; // expected-warning{{Invalidated iterator accessed}}
+  *i2; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void good_erase_list2(std::list<int> &L) {
+  auto i3 = L.cbegin(), i0 = i3++, i1 = i3++, i2 = i3++;
+  L.erase(i1, i3);
+  *i0; // no-warning
+  *i3; // no-warning
+}
+
+void bad_erase_list2(std::list<int> &L) {
+  auto i2 = L.cbegin(), i0 = i2++, i1 = i2++;
+  L.erase(i0, i2);
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+  *i1; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void good_erase_vector2(std::vector<int> &V) {
+  auto i3 = V.cbegin(), i0 = i3++, i1 = i3++, i2 = i3++;;
+  V.erase(i1, i3);
+  *i0; // no-warning
+}
+
+void bad_erase_vector2(std::vector<int> &V) {
+  auto i2 = V.cbegin(), i0 = i2++, i1 = i2++;
+  V.erase(i0, i2);
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+  *i1; // expected-warning{{Invalidated iterator accessed}}
+  *i2; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void bad_erase_deque2(std::deque<int> &D) {
+  auto i3 = D.cbegin(), i0 = i3++, i1 = i3++, i2 = i3++;
+  D.erase(i1, i3);
+  *i0; // expected-warning{{Invalidated iterator accessed}}
+  *i1; // expected-warning{{Invalidated iterator accessed}}
+  *i2; // expected-warning{{Invalidated iterator accessed}}
+  *i3; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void good_erase_after_forward_list1(std::forward_list<int> &FL) {
+  auto i2 = FL.cbegin(), i0 = i2++, i1 = i2++;
+  FL.erase_after(i0);
+  *i0; // no-warning
+  *i2; // no-warning
+}
+
+void bad_erase_after_forward_list1(std::forward_list<int> &FL) {
+  auto i1 = FL.cbegin(), i0 = i1++;
+  FL.erase_after(i0);
+  *i1; // expected-warning{{Invalidated iterator accessed}}
+}
+
+void good_erase_after_forward_list2(std::forward_list<int> &FL) {
+  auto i3 = FL.cbegin(), i0 = i3++, i1 = i3++, i2 = i3++;
+  FL.erase_after(i0, i3);
+  *i0; // no-warning
+  *i3; // no-warning
+}
+
+void bad_erase_after_forward_list2(std::forward_list<int> &FL) {
+  auto i3 = FL.cbegin(), i0 = i3++, i1 = i3++, i2 = i3++;
+  FL.erase_after(i0, i3);
+  *i1; // expected-warning{{Invalidated iterator accessed}}
+  *i2; // expected-warning{{Invalidated iterator accessed}}
+}

test/Analysis/iterator-past-end.cpp

-// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.IteratorPastEnd -analyzer-eagerly-assume -analyzer-config c++-container-inlining=false %s -verify
-// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.IteratorPastEnd -analyzer-eagerly-assume -analyzer-config c++-container-inlining=true -DINLINE=1 %s -verify
-
-#include "Inputs/system-header-simulator-cxx.h"
-
-void simple_good(const std::vector<int> &v) {
-  auto i = v.end();
-  if (i != v.end())
-    *i; // no-warning
-}
-
-void simple_good_negated(const std::vector<int> &v) {
-  auto i = v.end();
-  if (!(i == v.end()))
-    *i; // no-warning
-}
-
-void simple_bad(const std::vector<int> &v) {
-  auto i = v.end();
-  *i; // expected-warning{{Iterator accessed past its end}}
-}
-
-void copy(const std::vector<int> &v) {
-  auto i1 = v.end();
-  auto i2 = i1;
-  *i2; // expected-warning{{Iterator accessed past its end}}
-}
-
-void decrease(const std::vector<int> &v) {
-  auto i = v.end();
-  --i;
-  *i; // no-warning
-}
-
-void copy_and_decrease1(const std::vector<int> &v) {
-  auto i1 = v.end();
-  auto i2 = i1;
-  --i1;
-  *i1; // no-warning
-}
-
-void copy_and_decrease2(const std::vector<int> &v) {
-  auto i1 = v.end();
-  auto i2 = i1;
-  --i1;
-  *i2; // expected-warning{{Iterator accessed past its end}}
-}
-
-void copy_and_increase1(const std::vector<int> &v) {
-  auto i1 = v.begin();
-  auto i2 = i1;
-  ++i1;
-  if (i1 == v.end())
-    *i2; // no-warning
-}
-
-void copy_and_increase2(const std::vector<int> &v) {
-  auto i1 = v.begin();
-  auto i2 = i1;
-  ++i1;
-  if (i2 == v.end())
-    *i2; // expected-warning{{Iterator accessed past its end}}
-}
-
-void good_find(std::vector<int> &vec, int e) {
-  auto first = std::find(vec.begin(), vec.end(), e);
-  if (vec.end() != first)
-    *first; // no-warning
-}
-
-void bad_find(std::vector<int> &vec, int e) {
-  auto first = std::find(vec.begin(), vec.end(), e);
-  *first; // expected-warning{{Iterator accessed past its end}}
-}
-
-void good_find_end(std::vector<int> &vec, std::vector<int> &seq) {
-  auto last = std::find_end(vec.begin(), vec.end(), seq.begin(), seq.end());
-  if (vec.end() != last)
-    *last; // no-warning
-}
-
-void bad_find_end(std::vector<int> &vec, std::vector<int> &seq) {
-  auto last = std::find_end(vec.begin(), vec.end(), seq.begin(), seq.end());
-  *last; // expected-warning{{Iterator accessed past its end}}
-}
-
-void good_find_first_of(std::vector<int> &vec, std::vector<int> &seq) {
-  auto first =
-      std::find_first_of(vec.begin(), vec.end(), seq.begin(), seq.end());
-  if (vec.end() != first)
-    *first; // no-warning
-}
-
-void bad_find_first_of(std::vector<int> &vec, std::vector<int> &seq) {
-  auto first = std::find_end(vec.begin(), vec.end(), seq.begin(), seq.end());
-  *first; // expected-warning{{Iterator accessed past its end}}
-}
-
-bool odd(int i) { return i % 2; }
-
-void good_find_if(std::vector<int> &vec) {
-  auto first = std::find_if(vec.begin(), vec.end(), odd);
-  if (vec.end() != first)
-    *first; // no-warning
-}
-
-void bad_find_if(std::vector<int> &vec, int e) {
-  auto first = std::find_if(vec.begin(), vec.end(), odd);
-  *first; // expected-warning{{Iterator accessed past its end}}
-}
-
-void good_find_if_not(std::vector<int> &vec) {
-  auto first = std::find_if_not(vec.begin(), vec.end(), odd);
-  if (vec.end() != first)
-    *first; // no-warning
-}
-
-void bad_find_if_not(std::vector<int> &vec, int e) {
-  auto first = std::find_if_not(vec.begin(), vec.end(), odd);
-  *first; // expected-warning{{Iterator accessed past its end}}
-}
-
-void good_lower_bound(std::vector<int> &vec, int e) {
-  auto first = std::lower_bound(vec.begin(), vec.end(), e);
-  if (vec.end() != first)
-    *first; // no-warning
-}
-
-void bad_lower_bound(std::vector<int> &vec, int e) {
-  auto first = std::lower_bound(vec.begin(), vec.end(), e);
-  *first; // expected-warning{{Iterator accessed past its end}}
-}
-
-void good_upper_bound(std::vector<int> &vec, int e) {
-  auto last = std::lower_bound(vec.begin(), vec.end(), e);
-  if (vec.end() != last)
-    *last; // no-warning
-}
-
-void bad_upper_bound(std::vector<int> &vec, int e) {
-  auto last = std::lower_bound(vec.begin(), vec.end(), e);
-  *last; // expected-warning{{Iterator accessed past its end}}
-}
-
-void good_search(std::vector<int> &vec, std::vector<int> &seq) {
-  auto first = std::search(vec.begin(), vec.end(), seq.begin(), seq.end());
-  if (vec.end() != first)
-    *first; // no-warning
-}
-
-void bad_search(std::vector<int> &vec, std::vector<int> &seq) {
-  auto first = std::search(vec.begin(), vec.end(), seq.begin(), seq.end());
-  *first; // expected-warning{{Iterator accessed past its end}}
-}
-
-void good_search_n(std::vector<int> &vec, std::vector<int> &seq) {
-  auto nth = std::search_n(vec.begin(), vec.end(), seq.begin(), seq.end());
-  if (vec.end() != nth)
-    *nth; // no-warning
-}
-
-void bad_search_n(std::vector<int> &vec, std::vector<int> &seq) {
-  auto nth = std::search_n(vec.begin(), vec.end(), seq.begin(), seq.end());
-  *nth; // expected-warning{{Iterator accessed past its end}}
-}
-
-template <class InputIterator, class T>
-InputIterator nonStdFind(InputIterator first, InputIterator last,
-                         const T &val) {
-  for (auto i = first; i != last; ++i) {
-    if (*i == val) {
-      return i;
-    }
-  }
-  return last;
-}
-
-void good_non_std_find(std::vector<int> &vec, int e) {
-  auto first = nonStdFind(vec.begin(), vec.end(), e);
-  if (vec.end() != first)
-    *first; // no-warning
-}
-
-void bad_non_std_find(std::vector<int> &vec, int e) {
-  auto first = nonStdFind(vec.begin(), vec.end(), e);
-  *first; // expected-warning{{Iterator accessed past its end}}
-}
-
-void tricky(std::vector<int> &vec, int e) {
-  const auto first = vec.begin();
-  const auto comp1 = (first != vec.end()), comp2 = (first == vec.end());
-  if (comp1)
-    *first;
-}
-
-void loop(std::vector<int> &vec, int e) {
-  auto start = vec.begin();
-  while (true) {
-    auto item = std::find(start, vec.end(), e);
-    if (item == vec.end())
-      break;
-    *item;          // no-warning
-    start = ++item; // no-warning
-  }
-}

test/Analysis/iterator-range.cpp

+// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.IteratorRange -analyzer-eagerly-assume -analyzer-config c++-container-inlining=false %s -verify
+// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.IteratorRange -analyzer-eagerly-assume -analyzer-config c++-container-inlining=true -DINLINE=1 %s -verify
+
+#include "Inputs/system-header-simulator-cxx.h"
+
+void simple_good_end(const std::vector<int> &v) {
+  auto i = v.end();
+  if (i != v.end())
+    *i; // no-warning
+}
+
+void simple_good_end_negated(const std::vector<int> &v) {
+  auto i = v.end();
+  if (!(i == v.end()))
+    *i; // no-warning
+}
+
+void simple_bad_end(const std::vector<int> &v) {
+  auto i = v.end();
+  *i; // expected-warning{{Iterator accessed outside of its range}}
+}
+
+void simple_good_begin(const std::vector<int> &v) {
+  auto i = v.begin();
+  if (i != v.begin())
+    *--i; // no-warning
+}
+
+void simple_good_begin_negated(const std::vector<int> &v) {
+  auto i = v.begin();
+  if (!(i == v.begin()))
+    *--i; // no-warning
+}
+
+void simple_bad_begin(const std::vector<int> &v) {
+  auto i = v.begin();
+  *--i; // expected-warning{{Iterator accessed outside of its range}}
+}
+
+void copy(const std::vector<int> &v) {
+  auto i1 = v.end();
+  auto i2 = i1;
+  *i2; // expected-warning{{Iterator accessed outside of its range}}
+}
+
+void decrease(const std::vector<int> &v) {
+  auto i = v.end();
+  --i;
+  *i; // no-warning
+}
+
+void copy_and_decrease1(const std::vector<int> &v) {
+  auto i1 = v.end();
+  auto i2 = i1;
+  --i1;
+  *i1; // no-warning
+}
+
+void copy_and_decrease2(const std::vector<int> &v) {
+  auto i1 = v.end();
+  auto i2 = i1;
+  --i1;
+  *i2; // expected-warning{{Iterator accessed outside of its range}}
+}
+
+void copy_and_increase1(const std::vector<int> &v) {
+  auto i1 = v.begin();
+  auto i2 = i1;
+  ++i1;
+  if (i1 == v.end())
+    *i2; // no-warning
+}
+
+void copy_and_increase2(const std::vector<int> &v) {
+  auto i1 = v.begin();
+  auto i2 = i1;
+  ++i1;
+  if (i2 == v.end())
+    *i2; // expected-warning{{Iterator accessed outside of its range}}
+}
+
+void good_find(std::vector<int> &V, int e) {
+  auto first = std::find(V.begin(), V.end(), e);
+  if (V.end() != first)
+    *first; // no-warning
+}
+
+void bad_find(std::vector<int> &V, int e) {
+  auto first = std::find(V.begin(), V.end(), e);
+  *first; // expected-warning{{Iterator accessed outside of its range}}
+}
+
+void good_find_end(std::vector<int> &V, std::vector<int> &seq) {
+  auto last = std::find_end(V.begin(), V.end(), seq.begin(), seq.end());
+  if (V.end() != last)
+    *last; // no-warning
+}
+
+void bad_find_end(std::vector<int> &V, std::vector<int> &seq) {
+  auto last = std::find_end(V.begin(), V.end(), seq.begin(), seq.end());
+  *last; // expected-warning{{Iterator accessed outside of its range}}
+}
+
+void good_find_first_of(std::vector<int> &V, std::vector<int> &seq) {
+  auto first =
+      std::find_first_of(V.begin(), V.end(), seq.begin(), seq.end());
+  if (V.end() != first)
+    *first; // no-warning
+}
+
+void bad_find_first_of(std::vector<int> &V, std::vector<int> &seq) {
+  auto first = std::find_end(V.begin(), V.end(), seq.begin(), seq.end());
+  *first; // expected-warning{{Iterator accessed outside of its range}}
+}
+
+bool odd(int i) { return i % 2; }
+
+void good_find_if(std::vector<int> &V) {
+  auto first = std::find_if(V.begin(), V.end(), odd);
+  if (V.end() != first)
+    *first; // no-warning
+}
+
+void bad_find_if(std::vector<int> &V, int e) {
+  auto first = std::find_if(V.begin(), V.end(), odd);
+  *first; // expected-warning{{Iterator accessed outside of its range}}
+}
+
+void good_find_if_not(std::vector<int> &V) {
+  auto first = std::find_if_not(V.begin(), V.end(), odd);
+  if (V.end() != first)
+    *first; // no-warning
+}
+
+void bad_find_if_not(std::vector<int> &V, int e) {
+  auto first = std::find_if_not(V.begin(), V.end(), odd);
+  *first; // expected-warning{{Iterator accessed outside of its range}}
+}
+
+void good_lower_bound(std::vector<int> &V, int e) {
+  auto first = std::lower_bound(V.begin(), V.end(), e);
+  if (V.end() != first)
+    *first; // no-warning
+}
+
+void bad_lower_bound(std::vector<int> &V, int e) {
+  auto first = std::lower_bound(V.begin(), V.end(), e);
+  *first; // expected-warning{{Iterator accessed outside of its range}}
+}
+
+void good_upper_bound(std::vector<int> &V, int e) {
+  auto last = std::lower_bound(V.begin(), V.end(), e);
+  if (V.end() != last)
+    *last; // no-warning
+}
+
+void bad_upper_bound(std::vector<int> &V, int e) {
+  auto last = std::lower_bound(V.begin(), V.end(), e);
+  *last; // expected-warning{{Iterator accessed outside of its range}}
+}
+
+void good_search(std::vector<int> &V, std::vector<int> &seq) {
+  auto first = std::search(V.begin(), V.end(), seq.begin(), seq.end());
+  if (V.end() != first)
+    *first; // no-warning
+}
+
+void bad_search(std::vector<int> &V, std::vector<int> &seq) {
+  auto first = std::search(V.begin(), V.end(), seq.begin(), seq.end());
+  *first; // expected-warning{{Iterator accessed outside of its range}}
+}
+
+void good_search_n(std::vector<int> &V, std::vector<int> &seq) {
+  auto nth = std::search_n(V.begin(), V.end(), seq.begin(), seq.end());
+  if (V.end() != nth)
+    *nth; // no-warning
+}
+
+void bad_search_n(std::vector<int> &V, std::vector<int> &seq) {
+  auto nth = std::search_n(V.begin(), V.end(), seq.begin(), seq.end());
+  *nth; // expected-warning{{Iterator accessed outside of its range}}
+}
+
+template <class InputIterator, class T>
+InputIterator nonStdFind(InputIterator first, InputIterator last,
+                         const T &val) {
+  for (auto i = first; i != last; ++i) {
+    if (*i == val) {
+      return i;
+    }
+  }
+  return last;
+}
+
+void good_non_std_find(std::vector<int> &V, int e) {
+  auto first = nonStdFind(V.begin(), V.end(), e);
+  if (V.end() != first)
+    *first; // no-warning
+}
+
+void bad_non_std_find(std::vector<int> &V, int e) {
+  auto first = nonStdFind(V.begin(), V.end(), e);
+  *first; // expected-warning{{Iterator accessed outside of its range}}
+}
+
+void tricky(std::vector<int> &V, int e) {
+  const auto first = V.begin();
+  const auto comp1 = (first != V.end()), comp2 = (first == V.end());
+  if (comp1)
+    *first;
+}
+
+void loop(std::vector<int> &V, int e) {
+  auto start = V.begin();
+  while (true) {
+    auto item = std::find(start, V.end(), e);
+    if (item == V.end())
+      break;
+    *item;          // no-warning
+    start = ++item; // no-warning
+  }
+}
+
+void good_push_back(std::list<int> &L, int n) {
+  auto i0 = --L.cend();
+  L.push_back(n);
+  *++i0; // no-warning
+}
+
+void bad_push_back(std::list<int> &L, int n) {
+  auto i0 = --L.cend();
+  L.push_back(n);
+  ++i0;
+  *++i0; // expected-warning{{Iterator accessed outside of its range}}
+}
+
+void good_pop_back(std::list<int> &L, int n) {
+  auto i0 = --L.cend(); --i0;
+  L.pop_back();
+  *i0; // no-warning
+}
+
+void bad_pop_back(std::list<int> &L, int n) {
+  auto i0 = --L.cend(); --i0;
+  L.pop_back();
+  *++i0; // expected-warning{{Iterator accessed outside of its range}}
+}
+
+void good_push_front(std::list<int> &L, int n) {
+  auto i0 = L.cbegin();
+  L.push_front(n);
+  *--i0; // no-warning
+}
+
+void bad_push_front(std::list<int> &L, int n) {
+  auto i0 = L.cbegin();
+  L.push_front(n);
+  --i0;
+  *--i0; // expected-warning{{Iterator accessed outside of its range}}
+}
+
+void good_pop_front(std::list<int> &L, int n) {
+  auto i0 = ++L.cbegin();
+  L.pop_front();
+  *i0; // no-warning
+}
+
+void bad_pop_front(std::list<int> &L, int n) {
+  auto i0 = ++L.cbegin();
+  L.pop_front();
+  *--i0; // expected-warning{{Iterator accessed outside of its range}}
+}
+
+void bad_move(std::list<int> &L1, std::list<int> &L2) {
+  auto i0 = --L2.cend();
+  L1 = std::move(L2);
+  *++i0; // expected-warning{{Iterator accessed outside of its range}}
+}
+
+void bad_move_push_back(std::list<int> &L1, std::list<int> &L2, int n) {
+  auto i0 = --L2.cend();
+  L2.push_back(n);
+  L1 = std::move(L2);
+  ++i0;
+  *++i0; // expected-warning{{Iterator accessed outside of its range}}
+}

test/Analysis/mismatched-iterator.cpp

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