[Analyzer] Iterator Checker - Part 1: Minimal Checker for a Simple Test Case

[baloghadamsoftware]

Summary

This is the first part of the new Iterator Checker. This part contains the very core infrastructure. It only checks for out-of-range iterators in a very simple case.

[NoQ]

Thank you very much!

I think you might have forgotten to include the newly added files in this review(?)><

[baloghadamsoftware]

Checker and test included now :-)

[NoQ]

I see the checker going towards what we call "metadata symbols", which seems logical.

I still feel the checker deserves a lot more comments around the code. In particular, i'd definitely love to see a human-readable explanation of what kinds of iterators are supported (from plain pointers or integers to opaque structures): you did great job abstracting away these differences in the high-level logic, but i'd like to demonstrate how does the low-level logic (eg. offsets and comparisons, i.e. these moments when you're operating on various SVal objects directly) works in all these cases, because this part of the checker requires the most ingenuity to handle, while the rest is more or less straightforward.

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

211–214 ↗

(On Diff #97060)

These functions are currently unused; my compiler warns about that, and buildbots would probably yell at us when we commit it, so i guess it's better to add them when they are actually used; they'd also be tested as well.

219 ↗

(On Diff #97060)

Before we forget: Range -> range. As we've noticed recently in D32702 :), we don't capitalize every word in bug types and categories.

294–297 ↗

(On Diff #97060)

I guess this deserves a test case (we could split this out as a separate feature as well).

I'm also afraid that we can encounter false positives on functions that are not STL algorithms. I suggest doing this by default only for STL functions (or maybe for other specific classes of functions for which we know it works this way) and do this for other functions under a checker option (i.e. something like -analyzer-config IteratorChecker:AggressiveAssumptions=true, similar to MallocChecker's "Optimistic" option).

323–324 ↗

(On Diff #97060)

This callback is currently untested as well. I'm doing this bit of manual "mutation testing" by removing pieces of code and re-running tests because not only we'd rather keep every commit self-sufficient, but also we'd rather make sure we didn't forget anything, which is much easier to do patch-by-patch.

478–479 ↗

(On Diff #97060)

I see what you did here! And i suggest considering SymbolMetadata here instead of SymbolConjured, because it was designed for this purpose: the checker for some reason knows there's a special property of an object he wants to track, the checker doesn't have a ready-made symbolic value to represent this property (because the engine didn't know this property even exists, so it didn't denote its value), so the checker comes up with its own notation. SymbolMetadata is used, for example, in CStringChecker to denote an unknown string length for a given null-terminated string region.

This symbol carries the connection to the region (you may use it to reverse-lookup the region if necessary), and in particular it is considered to be live as long as the base region is live (so you don't have to deal with liveness manually; see also comments around SymbolReaper::MarkInUse). It's also easier to debug, because we can track the symbol back to the checker. Generally, symbol class hierarchy is cool because we know a lot about the symbol by just looking at it, and SymbolConjured is a sad fallback we use when we didn't care or manage to come up with a better symbol.

I'm not sure if LongTy is superior to IntTy here, since we don't know what to expect from the container anyway.

Also, please de-duplicate the symbol creation code. Birth of a symbol is something so rare it deserves a drum roll :)

I'd take a pause to figure out if the same logic should be applied to the map from containers to end-iterators.

513 ↗

(On Diff #97060)

One more unused function.

515–516 ↗

(On Diff #97060)

One more unused function.

[baloghadamsoftware]

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

211–214 ↗

(On Diff #97060)

Sorry, I forgot to delete it. I will do it.

219 ↗

(On Diff #97060)

Agree.

294–297 ↗

(On Diff #97060)

I will check whether this piece of code could be moved in a later part of the checker. However, I suggest to first wait for the first false positives before we introduce such an option. This far the false positives in my initial tests had different reasons, not this one.

478–479 ↗

(On Diff #97060)

SymbolMetaData is bound to a MemRegion. Iterators are sometimes symbols and sometimes memory regions, this was one of the first lessons I learned from my first iterator checker.

513 ↗

(On Diff #97060)

OK.

515–516 ↗

(On Diff #97060)

I thought I removed it.

[NoQ]

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

478–479 ↗

(On Diff #97060)

Oh. Hmm. Ok. Right.

To be sure: in what cases do you need to create a new symbol when the iterator is already a symbol? How broken do we become if we try to say that the symbolic iterator and its own offset are the same thing?

[NoQ]

Noticed a few more things.

It sounds as if once this first patch lands, the rest should be easy :)

Regarding the comments in the code. I materialized my wishes to something like:

• At the top of the file:

// In the code, iterator can be represented as a:
// * type-I: typedef-ed pointer. Operations over such iterator, such as comparisons or increments, are modeled straightforwardly by the analyzer.
// * type-II: structure with its method bodies available.  Operations over such iterator are inlined by the analyzer, and results of modeling these operations are exposing implementation details of the iterators, which is not necessarily helping.
// * type-III: completely opaque structure. Operations over such iterator are modeled conservatively, producing conjured symbols everywhere.
//
// Additionally, depending on the circumstances, operators of types II and III can be represented as:
// * type-IIa, type-IIIa: conjured structure symbols - when returned by value from conservatively evaluated methods such as `.begin()`.
// * type-IIb, type-IIIb: memory regions of iterator-typed objects, such as variables or temporaries, when the iterator object is currently treated as an lvalue.
// * type-IIc, type-IIIc: compound values of iterator-typed objects, when the iterator object is treated as an rvalue taken of a particular lvalue, eg. a copy of "type-a" iterator object, or an iterator that existed before the analysis has started.

Not sure if type-IIa iterators actually make sense. It's ok if you come up with your own classification :)

Then, in methods that deal with iterator SVals directly, i wish we had hints explaining what's going on in these ~7 cases. In my opinion, that'd greatly help people understand the code later, and it'd help us understand how to avoid this variety and provide checker authors with a better API as soon as we get to this, so it's the biggest concern for me about this checker.

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

16 ↗

(On Diff #97060)

This header seems unused for now.

22 ↗

(On Diff #97060)

This header seems unused for now.

153–155 ↗

(On Diff #97060)

Carryover from the other review: did you try using RegionOrSymbol as a key and keep only one map?

166–167 ↗

(On Diff #97060)

I've a bit of doubt about those. Would they call their constructors every time clang starts, regardless of whether the analyzer or the checker is enabled? Maybe having them as private variables inside the checker class would be better?

As in http://llvm.org/docs/CodingStandards.html#do-not-use-static-constructors

294–297 ↗

(On Diff #97060)

Unfortunately, we've had a poor experience with this approach in other checkers. You never know, and it seems that it's always better to have a safe fallback mode available under a flag, because if a few classes of false positives are found, and we are forced to reduce the checker to a safer behavior, it'd be hard to remember all the places where unsafe heuristics were used.

478–479 ↗

(On Diff #97060)

All right, i guess it wasn't a great idea. Even if iterators are plain pointers, the offset is a pointer difference. I still have this feeling that the analyzer is not good enough for this checker yet, so at least it's great that we have it moving.

I once wished we had "metadata regions" for symbols and regions, and then automatically gaining symbols for these region values (http://lists.llvm.org/pipermail/cfe-dev/2016-May/049000.html), that would have made things a lot cooler maybe. Never mind.

test/Analysis/iterator-range.cpp

1–2 ↗

(On Diff #97060)

Could we add run-lines without -analyzer-eagerly-assume? Currently all variants are passing, but if new tests will fail, we could #ifndef them out.

9 ↗

(On Diff #97060)

I'd suggest sticking clang_analyzer_warnIfReached() here to demonstrate that there is no warning because the branch is dead. That'd make the test stronger.

[baloghadamsoftware]

Updated according to the review.

[baloghadamsoftware]

In D32592#747132, @NoQ wrote:

Then, in methods that deal with iterator SVals directly, i wish we had hints explaining what's going on in these ~7 cases. In my opinion, that'd greatly help people understand the code later, and it'd help us understand how to avoid this variety and provide checker authors with a better API as soon as we get to this, so it's the biggest concern for me about this checker.

I am not sure which method do you mean? I think here the crucial functions are the setIteratorPosition() and the getIteratorPosition() functions which provide a common way to handle all these SVals.

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

166–167 ↗

(On Diff #97060)

Not needed in this patch. I delete them from here.

219 ↗

(On Diff #97060)

Also "out of" instead of "of out" :-)

294–297 ↗

(On Diff #97060)

I think this heuristic is well marked by the comment, easy to find if it causes false positives. When I started working on Clang (Tidy first) reviewers discouraged me to add options before experiencing false positives.

323–324 ↗

(On Diff #97060)

OK, removed from the first patch.

test/Analysis/iterator-range.cpp

1–2 ↗

(On Diff #97060)

In my first checker Anna suggested to always use this option. She also wrote that she plans to remove possibility to execute the Analyzer without eagerly assume.

[baloghadamsoftware]

Any comments regarding the last changes?

[NoQ]

Sorry, got carried away by GSoC and critical stuff...

In D32592#749613, @baloghadamsoftware wrote:

In D32592#747132, @NoQ wrote:

Then, in methods that deal with iterator SVals directly, i wish we had hints explaining what's going on in these ~7 cases. In my opinion, that'd greatly help people understand the code later, and it'd help us understand how to avoid this variety and provide checker authors with a better API as soon as we get to this, so it's the biggest concern for me about this checker.

I am not sure which method do you mean? I think here the crucial functions are the setIteratorPosition() and the getIteratorPosition() functions which provide a common way to handle all these SVals.

Hmm, i think i mostly mean evalAssume() and the comparisons mechanism. You're having multiple cases, like:
(1) if the assumed value is a BinarySymExpr for which there's a stored comparison (good for type-II iterators),
(2) if it's a symbol that was conjured by a conservatively evaluated comparison operator (here you lookup the opcode from the referenced expression) for which there's a stored comparison (good for type-III iterators),
(3) if it's a binary symbolic expression of form ($x == 0) or ($x != 0) where $x is one of (1) or (2).

I believe that the whole idea behind storing comparison results should have high-level comments explaining how it works (being tricky but solid - essentially it extends the constraint manager, taking over when handling iterator constraints, which sounds like the right thing to do).

I think we should land after that; i only have comment-related comments now :)

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

131 ↗

(On Diff #98275)

Strcutre -> Structure :)

294–297 ↗

(On Diff #97060)

Well, it's a bit sad to say, but that's one of the things that we didn't agree upon with clang-tidy, i guess; historically, they started as a lint-like tool that produces nice-to-fix-anyway kinds of warnings (having nice bug-finding checks nowadays), and we always kept positioning ourselves as a "quiet" tool that reports only real critical bugs for users that never would be annoyed immensely by every single false positive (doesn't make this true though), and it makes us nervous about every single potential false positive class.

I guess we could leave that as a task for later, with a "FIXME: Add a more conservative mode".

test/Analysis/iterator-range.cpp

1–2 ↗

(On Diff #97060)

Ouch, right. Suffering from short-term memory loss :)

[baloghadamsoftware]

Comments added and fixed.

[NoQ]

I believe we can move on to the next one :) Just hope we didn't screw up the rebase too much here. Thanks again!

cfe/trunk/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 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 {

cfe/trunk/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

cfe/trunk/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.
+//
+//===----------------------------------------------------------------------===//
+//
+// In the code, iterator can be represented as a:
+// * type-I: typedef-ed pointer. Operations over such iterator, such as
+//           comparisons or increments, are modeled straightforwardly by the
+//           analyzer.
+// * type-II: structure with its method bodies available.  Operations over such
+//            iterator are inlined by the analyzer, and results of modeling
+//            these operations are exposing implementation details of the
+//            iterators, which is not necessarily helping.
+// * type-III: completely opaque structure. Operations over such iterator are
+//             modeled conservatively, producing conjured symbols everywhere.
+//
+// To handle all these types in a common way we introduce a structure called
+// IteratorPosition which is an abstraction of the position the iterator
+// represents using symbolic expressions. The checker handles all the
+// operations on this structure.
+//
+// Additionally, depending on the circumstances, operators of types II and III
+// can be represented as:
+// * type-IIa, type-IIIa: conjured structure symbols - when returned by value
+//                        from conservatively evaluated methods such as
+//                        `.begin()`.
+// * type-IIb, type-IIIb: memory regions of iterator-typed objects, such as
+//                        variables or temporaries, when the iterator object is
+//                        currently treated as an lvalue.
+// * type-IIc, type-IIIc: compound values of iterator-typed objects, when the
+//                        iterator object is treated as an rvalue taken of a
+//                        particular lvalue, eg. a copy of "type-a" iterator
+//                        object, or an iterator that existed before the
+//                        analysis has started.
+//
+// To handle any of these three different representations stored in an SVal we
+// use setter and getters functions which separate the three cases. To store
+// them we use a pointer union of symbol and memory region.
+//
+// The checker works the following way: We record the past-end iterator for
+// all containers whenever their `.end()` is called. Since the Constraint
+// Manager cannot handle SVals we need to take over its role. We post-check
+// equality and non-equality comparisons and propagate the position of the
+// iterator to the other side of the comparison if it is past-end and we are in
+// the 'equal' branch (true-branch for `==` and false-branch for `!=`).
+//
+// In case of type-I or type-II iterators we get a concrete integer as a result
+// of the comparison (1 or 0) but in case of type-III we only get a Symbol. In
+// this latter case we record the symbol and reload it in evalAssume() and do
+// the propagation there. We also handle (maybe double) negated comparisons
+// which are represented in the form of (x == 0 or x !=0 ) where x is the
+// comparison itself.
+
+#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"
+
+using namespace clang;
+using namespace ento;
+
+namespace {
+
+// Abstract position of an iterator. This helps to handle all three kinds
+// of operators in a common way by using a symbolic position.
+struct IteratorPosition {
+private:
+
+  // Container the iterator belongs to
+  const MemRegion *Cont;
+
+  // Abstract offset
+  SymbolRef Offset;
+
+  IteratorPosition(const MemRegion *C, SymbolRef Of)
+      : Cont(C), Offset(Of) {}
+
+public:
+  const MemRegion *getContainer() const { return Cont; }
+  SymbolRef getOffset() const { return Offset; }
+
+  static IteratorPosition getPosition(const MemRegion *C, SymbolRef Of) {
+    return IteratorPosition(C, Of);
+  }
+
+  IteratorPosition setTo(SymbolRef NewOf) const {
+    return IteratorPosition(Cont, NewOf);
+  }
+
+  bool operator==(const IteratorPosition &X) const {
+    return Cont == X.Cont && Offset == X.Offset;
+  }
+
+  bool operator!=(const IteratorPosition &X) const {
+    return Cont != X.Cont || Offset != X.Offset;
+  }
+
+  void Profile(llvm::FoldingSetNodeID &ID) const {
+    ID.AddPointer(Cont);
+    ID.Add(Offset);
+  }
+};
+
+typedef llvm::PointerUnion<const MemRegion *, SymbolRef> RegionOrSymbol;
+
+// Structure to record the symbolic end position of a container
+struct ContainerData {
+private:
+  SymbolRef End;
+
+  ContainerData(SymbolRef E) : End(E) {}
+
+public:
+  static ContainerData fromEnd(SymbolRef E) {
+    return ContainerData(E);
+  }
+
+  SymbolRef getEnd() const { return End; }
+
+  ContainerData newEnd(SymbolRef E) const { return ContainerData(E); }
+
+  bool operator==(const ContainerData &X) const {
+    return End == X.End;
+  }
+
+  bool operator!=(const ContainerData &X) const {
+    return End != X.End;
+  }
+
+  void Profile(llvm::FoldingSetNodeID &ID) const {
+    ID.Add(End);
+  }
+};
+
+// Structure fo recording iterator comparisons. We needed to retrieve the
+// original comparison expression in assumptions.
+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::PostStmt<MaterializeTemporaryExpr>,
+                     check::DeadSymbols,
+                     eval::Assume> {
+
+  std::unique_ptr<BugType> OutOfRangeBugType;
+
+  void handleComparison(CheckerContext &C, const SVal &RetVal, const SVal &LVal,
+                        const SVal &RVal, OverloadedOperatorKind Op) const;
+  void verifyDereference(CheckerContext &C, const SVal &Val) 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 reportOutOfRangeBug(const StringRef &Message, const SVal &Val,
+                           CheckerContext &C, ExplodedNode *ErrNode) const;
+
+public:
+  IteratorChecker();
+
+  enum CheckKind {
+    CK_IteratorRangeChecker,
+    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 checkPostStmt(const MaterializeTemporaryExpr *MTE,
+                     CheckerContext &C) const;
+  void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
+  ProgramStateRef evalAssume(ProgramStateRef State, SVal Cond,
+                             bool Assumption) const;
+};
+} // namespace
+
+REGISTER_MAP_WITH_PROGRAMSTATE(IteratorSymbolMap, SymbolRef, IteratorPosition)
+REGISTER_MAP_WITH_PROGRAMSTATE(IteratorRegionMap, const MemRegion *,
+                               IteratorPosition)
+
+REGISTER_MAP_WITH_PROGRAMSTATE(ContainerMap, const MemRegion *, ContainerData)
+
+REGISTER_MAP_WITH_PROGRAMSTATE(IteratorComparisonMap, const SymExpr *,
+                               IteratorComparison)
+
+namespace {
+
+bool isIteratorType(const QualType &Type);
+bool isIterator(const CXXRecordDecl *CRD);
+bool isEndCall(const FunctionDecl *Func);
+bool isSimpleComparisonOperator(OverloadedOperatorKind OK);
+bool isDereferenceOperator(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);
+SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont);
+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);
+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);
+} // namespace
+
+IteratorChecker::IteratorChecker() {
+  OutOfRangeBugType.reset(
+      new BugType(this, "Iterator out of range", "Misuse of STL APIs"));
+  OutOfRangeBugType->setSuppressOnSink(true);
+}
+
+void IteratorChecker::checkPreCall(const CallEvent &Call,
+                                   CheckerContext &C) const {
+  // Check for out of range access
+  const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
+  if (!Func)
+    return;
+
+  if (Func->isOverloadedOperator()) {
+    if (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));
+      }
+    }
+  }
+}
+
+void IteratorChecker::checkPostCall(const CallEvent &Call,
+                                    CheckerContext &C) const {
+  // Record new iterator positions and iterator position changes
+  const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
+  if (!Func)
+    return;
+
+  if (Func->isOverloadedOperator()) {
+    const auto Op = Func->getOverloadedOperator();
+    if (isSimpleComparisonOperator(Op)) {
+      if (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 {
+    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 (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.
+    // FIXME: Add a more conservative mode
+    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::checkPostStmt(const MaterializeTemporaryExpr *MTE,
+                                    CheckerContext &C) const {
+  /* Transfer iterator state 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::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);
+}
+
+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::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::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));
+}
+
+namespace {
+
+bool isGreaterOrEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
+bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
+             BinaryOperator::Opcode Opc);
+
+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 isDereferenceOperator(OverloadedOperatorKind OK) {
+  return OK == OO_Star || OK == OO_Arrow || OK == OO_ArrowStar ||
+         OK == OO_Subscript;
+}
+
+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) {
+    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 getContainerEnd(ProgramStateRef State, const MemRegion *Cont) {
+  const auto *CDataPtr = getContainerData(State, Cont);
+  if (!CDataPtr)
+    return nullptr;
+
+  return CDataPtr->getEnd();
+}
+
+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) {
+  // 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);
+  }
+
+  return State;
+}
+
+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 End = CData->getEnd();
+  if (End) {
+    if (isGreaterOrEqual(State, Pos.getOffset(), End)) {
+      return true;
+    }
+  }
+
+  return false;
+}
+
+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();
+
+  const auto comparison =
+      SVB.evalBinOp(State, Opc, nonloc::SymbolVal(Sym1),
+                    nonloc::SymbolVal(Sym2), SVB.getConditionType())
+          .getAs<DefinedSVal>();
+
+  if(comparison) {
+    return !!State->assume(*comparison, true);
+  }
+
+  return false;
+}
+
+} // 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)

cfe/trunk/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>();
-}

cfe/trunk/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();
+    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);
+
+    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);
+    }
     
     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();
+    
+    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,
-                                 ForwardIterator1 last1,
-                                 ForwardIterator2 first2,
-                                 ForwardIterator2 last2);
-  template <class InputIterator, class UnaryPredicate>
-  InputIterator find_if(InputIterator first, InputIterator last,
-                        UnaryPredicate pred);
-  template <class InputIterator, class UnaryPredicate>
-  InputIterator find_if_not(InputIterator first, InputIterator last,
-                            UnaryPredicate pred);
-  template <class InputIterator, class T>
-  InputIterator lower_bound(InputIterator first, InputIterator last,
-                            const T &val);
-  template <class InputIterator, class T>
-  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();
 

cfe/trunk/test/Analysis/diagnostics/explicit-suppression.cpp

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

cfe/trunk/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
-  }
-}

cfe/trunk/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 clang_analyzer_warnIfReached();
+
+void simple_good_end(const std::vector<int> &v) {
+  auto i = v.end();
+  if (i != v.end()) {
+    clang_analyzer_warnIfReached();
+    *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}}
+}