contrib/llvm/tools/clang/lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

   1 //===-- IteratorChecker.cpp ---------------------------------------*- C++ -*--//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // Defines a checker for using iterators outside their range (past end). Usage
  11 // means here dereferencing, incrementing etc.
  12 //
  13 //===----------------------------------------------------------------------===//
  14 //
  15 // In the code, iterator can be represented as a:
  16 // * type-I: typedef-ed pointer. Operations over such iterator, such as
  17 //           comparisons or increments, are modeled straightforwardly by the
  18 //           analyzer.
  19 // * type-II: structure with its method bodies available.  Operations over such
  20 //            iterator are inlined by the analyzer, and results of modeling
  21 //            these operations are exposing implementation details of the
  22 //            iterators, which is not necessarily helping.
  23 // * type-III: completely opaque structure. Operations over such iterator are
  24 //             modeled conservatively, producing conjured symbols everywhere.
  25 //
  26 // To handle all these types in a common way we introduce a structure called
  27 // IteratorPosition which is an abstraction of the position the iterator
  28 // represents using symbolic expressions. The checker handles all the
  29 // operations on this structure.
  30 //
  31 // Additionally, depending on the circumstances, operators of types II and III
  32 // can be represented as:
  33 // * type-IIa, type-IIIa: conjured structure symbols - when returned by value
  34 //                        from conservatively evaluated methods such as
  35 //                        `.begin()`.
  36 // * type-IIb, type-IIIb: memory regions of iterator-typed objects, such as
  37 //                        variables or temporaries, when the iterator object is
  38 //                        currently treated as an lvalue.
  39 // * type-IIc, type-IIIc: compound values of iterator-typed objects, when the
  40 //                        iterator object is treated as an rvalue taken of a
  41 //                        particular lvalue, eg. a copy of "type-a" iterator
  42 //                        object, or an iterator that existed before the
  43 //                        analysis has started.
  44 //
  45 // To handle any of these three different representations stored in an SVal we
  46 // use setter and getters functions which separate the three cases. To store
  47 // them we use a pointer union of symbol and memory region.
  48 //
  49 // The checker works the following way: We record the begin and the
  50 // past-end iterator for all containers whenever their `.begin()` and `.end()`
  51 // are called. Since the Constraint Manager cannot handle such SVals we need
  52 // to take over its role. We post-check equality and non-equality comparisons
  53 // and record that the two sides are equal if we are in the 'equal' branch
  54 // (true-branch for `==` and false-branch for `!=`).
  55 //
  56 // In case of type-I or type-II iterators we get a concrete integer as a result
  57 // of the comparison (1 or 0) but in case of type-III we only get a Symbol. In
  58 // this latter case we record the symbol and reload it in evalAssume() and do
  59 // the propagation there. We also handle (maybe double) negated comparisons
  60 // which are represented in the form of (x == 0 or x != 0) where x is the
  61 // comparison itself.
  62 //
  63 // Since `SimpleConstraintManager` cannot handle complex symbolic expressions
  64 // we only use expressions of the format S, S+n or S-n for iterator positions
  65 // where S is a conjured symbol and n is an unsigned concrete integer. When
  66 // making an assumption e.g. `S1 + n == S2 + m` we store `S1 - S2 == m - n` as
  67 // a constraint which we later retrieve when doing an actual comparison.
  68
  69 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
  70 #include "clang/AST/DeclTemplate.h"
  71 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
  72 #include "clang/StaticAnalyzer/Core/Checker.h"
  73 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
  74 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
  75 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicTypeMap.h"
  76
  77 #include <utility>
  78
  79 using namespace clang;
  80 using namespace ento;
  81
  82 namespace {
  83
  84 // Abstract position of an iterator. This helps to handle all three kinds
  85 // of operators in a common way by using a symbolic position.
  86 struct IteratorPosition {
  87 private:
  88
  89   // Container the iterator belongs to
  90   const MemRegion *Cont;
  91
  92   // Whether iterator is valid
  93   const bool Valid;
  94
  95   // Abstract offset
  96   const SymbolRef Offset;
  97
  98   IteratorPosition(const MemRegion *C, bool V, SymbolRef Of)
  99       : Cont(C), Valid(V), Offset(Of) {}
 100
 101 public:
 102   const MemRegion *getContainer() const { return Cont; }
 103   bool isValid() const { return Valid; }
 104   SymbolRef getOffset() const { return Offset; }
 105
 106   IteratorPosition invalidate() const {
 107     return IteratorPosition(Cont, false, Offset);
 108   }
 109
 110   static IteratorPosition getPosition(const MemRegion *C, SymbolRef Of) {
 111     return IteratorPosition(C, true, Of);
 112   }
 113
 114   IteratorPosition setTo(SymbolRef NewOf) const {
 115     return IteratorPosition(Cont, Valid, NewOf);
 116   }
 117
 118   IteratorPosition reAssign(const MemRegion *NewCont) const {
 119     return IteratorPosition(NewCont, Valid, Offset);
 120   }
 121
 122   bool operator==(const IteratorPosition &X) const {
 123     return Cont == X.Cont && Valid == X.Valid && Offset == X.Offset;
 124   }
 125
 126   bool operator!=(const IteratorPosition &X) const {
 127     return Cont != X.Cont || Valid != X.Valid || Offset != X.Offset;
 128   }
 129
 130   void Profile(llvm::FoldingSetNodeID &ID) const {
 131     ID.AddPointer(Cont);
 132     ID.AddInteger(Valid);
 133     ID.Add(Offset);
 134   }
 135 };
 136
 137 typedef llvm::PointerUnion<const MemRegion *, SymbolRef> RegionOrSymbol;
 138
 139 // Structure to record the symbolic begin and end position of a container
 140 struct ContainerData {
 141 private:
 142   const SymbolRef Begin, End;
 143
 144   ContainerData(SymbolRef B, SymbolRef E) : Begin(B), End(E) {}
 145
 146 public:
 147   static ContainerData fromBegin(SymbolRef B) {
 148     return ContainerData(B, nullptr);
 149   }
 150
 151   static ContainerData fromEnd(SymbolRef E) {
 152     return ContainerData(nullptr, E);
 153   }
 154
 155   SymbolRef getBegin() const { return Begin; }
 156   SymbolRef getEnd() const { return End; }
 157
 158   ContainerData newBegin(SymbolRef B) const { return ContainerData(B, End); }
 159
 160   ContainerData newEnd(SymbolRef E) const { return ContainerData(Begin, E); }
 161
 162   bool operator==(const ContainerData &X) const {
 163     return Begin == X.Begin && End == X.End;
 164   }
 165
 166   bool operator!=(const ContainerData &X) const {
 167     return Begin != X.Begin || End != X.End;
 168   }
 169
 170   void Profile(llvm::FoldingSetNodeID &ID) const {
 171     ID.Add(Begin);
 172     ID.Add(End);
 173   }
 174 };
 175
 176 // Structure fo recording iterator comparisons. We needed to retrieve the
 177 // original comparison expression in assumptions.
 178 struct IteratorComparison {
 179 private:
 180   RegionOrSymbol Left, Right;
 181   bool Equality;
 182
 183 public:
 184   IteratorComparison(RegionOrSymbol L, RegionOrSymbol R, bool Eq)
 185       : Left(L), Right(R), Equality(Eq) {}
 186
 187   RegionOrSymbol getLeft() const { return Left; }
 188   RegionOrSymbol getRight() const { return Right; }
 189   bool isEquality() const { return Equality; }
 190   bool operator==(const IteratorComparison &X) const {
 191     return Left == X.Left && Right == X.Right && Equality == X.Equality;
 192   }
 193   bool operator!=(const IteratorComparison &X) const {
 194     return Left != X.Left || Right != X.Right || Equality != X.Equality;
 195   }
 196   void Profile(llvm::FoldingSetNodeID &ID) const { ID.AddInteger(Equality); }
 197 };
 198
 199 class IteratorChecker
 200     : public Checker<check::PreCall, check::PostCall,
 201                      check::PostStmt<MaterializeTemporaryExpr>, check::Bind,
 202                      check::LiveSymbols, check::DeadSymbols,
 203                      eval::Assume> {
 204
 205   std::unique_ptr<BugType> OutOfRangeBugType;
 206   std::unique_ptr<BugType> MismatchedBugType;
 207   std::unique_ptr<BugType> InvalidatedBugType;
 208
 209   void handleComparison(CheckerContext &C, const SVal &RetVal, const SVal &LVal,
 210                         const SVal &RVal, OverloadedOperatorKind Op) const;
 211   void verifyAccess(CheckerContext &C, const SVal &Val) const;
 212   void verifyDereference(CheckerContext &C, const SVal &Val) const;
 213   void handleIncrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter,
 214                        bool Postfix) const;
 215   void handleDecrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter,
 216                        bool Postfix) const;
 217   void handleRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op,
 218                               const SVal &RetVal, const SVal &LHS,
 219                               const SVal &RHS) const;
 220   void handleBegin(CheckerContext &C, const Expr *CE, const SVal &RetVal,
 221                    const SVal &Cont) const;
 222   void handleEnd(CheckerContext &C, const Expr *CE, const SVal &RetVal,
 223                  const SVal &Cont) const;
 224   void assignToContainer(CheckerContext &C, const Expr *CE, const SVal &RetVal,
 225                          const MemRegion *Cont) const;
 226   void handleAssign(CheckerContext &C, const SVal &Cont,
 227                     const Expr *CE = nullptr,
 228                     const SVal &OldCont = UndefinedVal()) const;
 229   void handleClear(CheckerContext &C, const SVal &Cont) const;
 230   void handlePushBack(CheckerContext &C, const SVal &Cont) const;
 231   void handlePopBack(CheckerContext &C, const SVal &Cont) const;
 232   void handlePushFront(CheckerContext &C, const SVal &Cont) const;
 233   void handlePopFront(CheckerContext &C, const SVal &Cont) const;
 234   void handleInsert(CheckerContext &C, const SVal &Iter) const;
 235   void handleErase(CheckerContext &C, const SVal &Iter) const;
 236   void handleErase(CheckerContext &C, const SVal &Iter1,
 237                    const SVal &Iter2) const;
 238   void handleEraseAfter(CheckerContext &C, const SVal &Iter) const;
 239   void handleEraseAfter(CheckerContext &C, const SVal &Iter1,
 240                         const SVal &Iter2) const;
 241   void verifyIncrement(CheckerContext &C, const SVal &Iter) const;
 242   void verifyDecrement(CheckerContext &C, const SVal &Iter) const;
 243   void verifyRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op,
 244                               const SVal &LHS, const SVal &RHS) const;
 245   void verifyMatch(CheckerContext &C, const SVal &Iter,
 246                    const MemRegion *Cont) const;
 247   void verifyMatch(CheckerContext &C, const SVal &Iter1,
 248                    const SVal &Iter2) const;
 249   IteratorPosition advancePosition(CheckerContext &C, OverloadedOperatorKind Op,
 250                                    const IteratorPosition &Pos,
 251                                    const SVal &Distance) const;
 252   void reportOutOfRangeBug(const StringRef &Message, const SVal &Val,
 253                            CheckerContext &C, ExplodedNode *ErrNode) const;
 254   void reportMismatchedBug(const StringRef &Message, const SVal &Val1,
 255                            const SVal &Val2, CheckerContext &C,
 256                            ExplodedNode *ErrNode) const;
 257   void reportMismatchedBug(const StringRef &Message, const SVal &Val,
 258                            const MemRegion *Reg, CheckerContext &C,
 259                            ExplodedNode *ErrNode) const;
 260   void reportInvalidatedBug(const StringRef &Message, const SVal &Val,
 261                             CheckerContext &C, ExplodedNode *ErrNode) const;
 262
 263 public:
 264   IteratorChecker();
 265
 266   enum CheckKind {
 267     CK_IteratorRangeChecker,
 268     CK_MismatchedIteratorChecker,
 269     CK_InvalidatedIteratorChecker,
 270     CK_NumCheckKinds
 271   };
 272
 273   DefaultBool ChecksEnabled[CK_NumCheckKinds];
 274   CheckName CheckNames[CK_NumCheckKinds];
 275
 276   void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
 277   void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
 278   void checkBind(SVal Loc, SVal Val, const Stmt *S, CheckerContext &C) const;
 279   void checkPostStmt(const CXXConstructExpr *CCE, CheckerContext &C) const;
 280   void checkPostStmt(const DeclStmt *DS, CheckerContext &C) const;
 281   void checkPostStmt(const MaterializeTemporaryExpr *MTE,
 282                      CheckerContext &C) const;
 283   void checkLiveSymbols(ProgramStateRef State, SymbolReaper &SR) const;
 284   void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
 285   ProgramStateRef evalAssume(ProgramStateRef State, SVal Cond,
 286                              bool Assumption) const;
 287 };
 288 } // namespace
 289
 290 REGISTER_MAP_WITH_PROGRAMSTATE(IteratorSymbolMap, SymbolRef, IteratorPosition)
 291 REGISTER_MAP_WITH_PROGRAMSTATE(IteratorRegionMap, const MemRegion *,
 292                                IteratorPosition)
 293
 294 REGISTER_MAP_WITH_PROGRAMSTATE(ContainerMap, const MemRegion *, ContainerData)
 295
 296 REGISTER_MAP_WITH_PROGRAMSTATE(IteratorComparisonMap, const SymExpr *,
 297                                IteratorComparison)
 298
 299 namespace {
 300
 301 bool isIteratorType(const QualType &Type);
 302 bool isIterator(const CXXRecordDecl *CRD);
 303 bool isComparisonOperator(OverloadedOperatorKind OK);
 304 bool isBeginCall(const FunctionDecl *Func);
 305 bool isEndCall(const FunctionDecl *Func);
 306 bool isAssignCall(const FunctionDecl *Func);
 307 bool isClearCall(const FunctionDecl *Func);
 308 bool isPushBackCall(const FunctionDecl *Func);
 309 bool isEmplaceBackCall(const FunctionDecl *Func);
 310 bool isPopBackCall(const FunctionDecl *Func);
 311 bool isPushFrontCall(const FunctionDecl *Func);
 312 bool isEmplaceFrontCall(const FunctionDecl *Func);
 313 bool isPopFrontCall(const FunctionDecl *Func);
 314 bool isInsertCall(const FunctionDecl *Func);
 315 bool isEraseCall(const FunctionDecl *Func);
 316 bool isEraseAfterCall(const FunctionDecl *Func);
 317 bool isEmplaceCall(const FunctionDecl *Func);
 318 bool isAssignmentOperator(OverloadedOperatorKind OK);
 319 bool isSimpleComparisonOperator(OverloadedOperatorKind OK);
 320 bool isAccessOperator(OverloadedOperatorKind OK);
 321 bool isDereferenceOperator(OverloadedOperatorKind OK);
 322 bool isIncrementOperator(OverloadedOperatorKind OK);
 323 bool isDecrementOperator(OverloadedOperatorKind OK);
 324 bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK);
 325 bool hasSubscriptOperator(ProgramStateRef State, const MemRegion *Reg);
 326 bool frontModifiable(ProgramStateRef State, const MemRegion *Reg);
 327 bool backModifiable(ProgramStateRef State, const MemRegion *Reg);
 328 BinaryOperator::Opcode getOpcode(const SymExpr *SE);
 329 const RegionOrSymbol getRegionOrSymbol(const SVal &Val);
 330 const ProgramStateRef processComparison(ProgramStateRef State,
 331                                         RegionOrSymbol LVal,
 332                                         RegionOrSymbol RVal, bool Equal);
 333 const ProgramStateRef saveComparison(ProgramStateRef State,
 334                                      const SymExpr *Condition, const SVal &LVal,
 335                                      const SVal &RVal, bool Eq);
 336 const IteratorComparison *loadComparison(ProgramStateRef State,
 337                                          const SymExpr *Condition);
 338 SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont);
 339 SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont);
 340 ProgramStateRef createContainerBegin(ProgramStateRef State,
 341                                      const MemRegion *Cont,
 342                                      const SymbolRef Sym);
 343 ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont,
 344                                    const SymbolRef Sym);
 345 const IteratorPosition *getIteratorPosition(ProgramStateRef State,
 346                                             const SVal &Val);
 347 const IteratorPosition *getIteratorPosition(ProgramStateRef State,
 348                                             RegionOrSymbol RegOrSym);
 349 ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val,
 350                                     const IteratorPosition &Pos);
 351 ProgramStateRef setIteratorPosition(ProgramStateRef State,
 352                                     RegionOrSymbol RegOrSym,
 353                                     const IteratorPosition &Pos);
 354 ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val);
 355 ProgramStateRef adjustIteratorPosition(ProgramStateRef State,
 356                                        RegionOrSymbol RegOrSym,
 357                                        const IteratorPosition &Pos, bool Equal);
 358 ProgramStateRef relateIteratorPositions(ProgramStateRef State,
 359                                         const IteratorPosition &Pos1,
 360                                         const IteratorPosition &Pos2,
 361                                         bool Equal);
 362 ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State,
 363                                                const MemRegion *Cont);
 364 ProgramStateRef
 365 invalidateAllIteratorPositionsExcept(ProgramStateRef State,
 366                                      const MemRegion *Cont, SymbolRef Offset,
 367                                      BinaryOperator::Opcode Opc);
 368 ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
 369                                             SymbolRef Offset,
 370                                             BinaryOperator::Opcode Opc);
 371 ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
 372                                             SymbolRef Offset1,
 373                                             BinaryOperator::Opcode Opc1,
 374                                             SymbolRef Offset2,
 375                                             BinaryOperator::Opcode Opc2);
 376 ProgramStateRef reassignAllIteratorPositions(ProgramStateRef State,
 377                                              const MemRegion *Cont,
 378                                              const MemRegion *NewCont);
 379 ProgramStateRef reassignAllIteratorPositionsUnless(ProgramStateRef State,
 380                                                    const MemRegion *Cont,
 381                                                    const MemRegion *NewCont,
 382                                                    SymbolRef Offset,
 383                                                    BinaryOperator::Opcode Opc);
 384 ProgramStateRef rebaseSymbolInIteratorPositionsIf(
 385     ProgramStateRef State, SValBuilder &SVB, SymbolRef OldSym,
 386     SymbolRef NewSym, SymbolRef CondSym, BinaryOperator::Opcode Opc);
 387 const ContainerData *getContainerData(ProgramStateRef State,
 388                                       const MemRegion *Cont);
 389 ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont,
 390                                  const ContainerData &CData);
 391 bool hasLiveIterators(ProgramStateRef State, const MemRegion *Cont);
 392 bool isBoundThroughLazyCompoundVal(const Environment &Env,
 393                                    const MemRegion *Reg);
 394 bool isPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos);
 395 bool isAheadOfRange(ProgramStateRef State, const IteratorPosition &Pos);
 396 bool isBehindPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos);
 397 bool isZero(ProgramStateRef State, const NonLoc &Val);
 398 } // namespace
 399
 400 IteratorChecker::IteratorChecker() {
 401   OutOfRangeBugType.reset(
 402       new BugType(this, "Iterator out of range", "Misuse of STL APIs"));
 403   OutOfRangeBugType->setSuppressOnSink(true);
 404   MismatchedBugType.reset(
 405       new BugType(this, "Iterator(s) mismatched", "Misuse of STL APIs"));
 406   MismatchedBugType->setSuppressOnSink(true);
 407   InvalidatedBugType.reset(
 408       new BugType(this, "Iterator invalidated", "Misuse of STL APIs"));
 409   InvalidatedBugType->setSuppressOnSink(true);
 410 }
 411
 412 void IteratorChecker::checkPreCall(const CallEvent &Call,
 413                                    CheckerContext &C) const {
 414   // Check for out of range access or access of invalidated position and
 415   // iterator mismatches
 416   const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
 417   if (!Func)
 418     return;
 419
 420   if (Func->isOverloadedOperator()) {
 421     if (ChecksEnabled[CK_InvalidatedIteratorChecker] &&
 422         isAccessOperator(Func->getOverloadedOperator())) {
 423       // Check for any kind of access of invalidated iterator positions
 424       if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
 425         verifyAccess(C, InstCall->getCXXThisVal());
 426       } else {
 427         verifyAccess(C, Call.getArgSVal(0));
 428       }
 429     }
 430     if (ChecksEnabled[CK_IteratorRangeChecker]) {
 431       if (isIncrementOperator(Func->getOverloadedOperator())) {
 432         // Check for out-of-range incrementions
 433         if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
 434           verifyIncrement(C, InstCall->getCXXThisVal());
 435         } else {
 436           if (Call.getNumArgs() >= 1) {
 437             verifyIncrement(C, Call.getArgSVal(0));
 438           }
 439         }
 440       } else if (isDecrementOperator(Func->getOverloadedOperator())) {
 441         // Check for out-of-range decrementions
 442         if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
 443           verifyDecrement(C, InstCall->getCXXThisVal());
 444         } else {
 445           if (Call.getNumArgs() >= 1) {
 446             verifyDecrement(C, Call.getArgSVal(0));
 447           }
 448         }
 449       } else if (isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) {
 450         if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
 451           // Check for out-of-range incrementions and decrementions
 452           if (Call.getNumArgs() >= 1) {
 453             verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(),
 454                                    InstCall->getCXXThisVal(),
 455                                    Call.getArgSVal(0));
 456           }
 457         } else {
 458           if (Call.getNumArgs() >= 2) {
 459             verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(),
 460                                    Call.getArgSVal(0), Call.getArgSVal(1));
 461           }
 462         }
 463       } else if (isDereferenceOperator(Func->getOverloadedOperator())) {
 464         // Check for dereference of out-of-range iterators
 465         if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
 466           verifyDereference(C, InstCall->getCXXThisVal());
 467         } else {
 468           verifyDereference(C, Call.getArgSVal(0));
 469         }
 470       }
 471     } else if (ChecksEnabled[CK_MismatchedIteratorChecker] &&
 472                isComparisonOperator(Func->getOverloadedOperator())) {
 473       // Check for comparisons of iterators of different containers
 474       if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
 475         if (Call.getNumArgs() < 1)
 476           return;
 477
 478         if (!isIteratorType(InstCall->getCXXThisExpr()->getType()) ||
 479             !isIteratorType(Call.getArgExpr(0)->getType()))
 480           return;
 481
 482         verifyMatch(C, InstCall->getCXXThisVal(), Call.getArgSVal(0));
 483       } else {
 484         if (Call.getNumArgs() < 2)
 485           return;
 486
 487         if (!isIteratorType(Call.getArgExpr(0)->getType()) ||
 488             !isIteratorType(Call.getArgExpr(1)->getType()))
 489           return;
 490
 491         verifyMatch(C, Call.getArgSVal(0), Call.getArgSVal(1));
 492       }
 493     }
 494   } else if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
 495     if (!ChecksEnabled[CK_MismatchedIteratorChecker])
 496       return;
 497
 498     const auto *ContReg = InstCall->getCXXThisVal().getAsRegion();
 499     if (!ContReg)
 500       return;
 501     // Check for erase, insert and emplace using iterator of another container
 502     if (isEraseCall(Func) || isEraseAfterCall(Func)) {
 503       verifyMatch(C, Call.getArgSVal(0),
 504                   InstCall->getCXXThisVal().getAsRegion());
 505       if (Call.getNumArgs() == 2) {
 506         verifyMatch(C, Call.getArgSVal(1),
 507                     InstCall->getCXXThisVal().getAsRegion());
 508       }
 509     } else if (isInsertCall(Func)) {
 510       verifyMatch(C, Call.getArgSVal(0),
 511                   InstCall->getCXXThisVal().getAsRegion());
 512       if (Call.getNumArgs() == 3 &&
 513           isIteratorType(Call.getArgExpr(1)->getType()) &&
 514           isIteratorType(Call.getArgExpr(2)->getType())) {
 515         verifyMatch(C, Call.getArgSVal(1), Call.getArgSVal(2));
 516       }
 517     } else if (isEmplaceCall(Func)) {
 518       verifyMatch(C, Call.getArgSVal(0),
 519                   InstCall->getCXXThisVal().getAsRegion());
 520     }
 521   } else if (isa<CXXConstructorCall>(&Call)) {
 522     // Check match of first-last iterator pair in a constructor of a container
 523     if (Call.getNumArgs() < 2)
 524       return;
 525
 526     const auto *Ctr = cast<CXXConstructorDecl>(Call.getDecl());
 527     if (Ctr->getNumParams() < 2)
 528       return;
 529
 530     if (Ctr->getParamDecl(0)->getName() != "first" ||
 531         Ctr->getParamDecl(1)->getName() != "last")
 532       return;
 533
 534     if (!isIteratorType(Call.getArgExpr(0)->getType()) ||
 535         !isIteratorType(Call.getArgExpr(1)->getType()))
 536       return;
 537
 538     verifyMatch(C, Call.getArgSVal(0), Call.getArgSVal(1));
 539   } else {
 540     // The main purpose of iterators is to abstract away from different
 541     // containers and provide a (maybe limited) uniform access to them.
 542     // This implies that any correctly written template function that
 543     // works on multiple containers using iterators takes different
 544     // template parameters for different containers. So we can safely
 545     // assume that passing iterators of different containers as arguments
 546     // whose type replaces the same template parameter is a bug.
 547     //
 548     // Example:
 549     // template<typename I1, typename I2>
 550     // void f(I1 first1, I1 last1, I2 first2, I2 last2);
 551     //
 552     // In this case the first two arguments to f() must be iterators must belong
 553     // to the same container and the last to also to the same container but
 554     // not necessarily to the same as the first two.
 555
 556     if (!ChecksEnabled[CK_MismatchedIteratorChecker])
 557       return;
 558
 559     const auto *Templ = Func->getPrimaryTemplate();
 560     if (!Templ)
 561       return;
 562
 563     const auto *TParams = Templ->getTemplateParameters();
 564     const auto *TArgs = Func->getTemplateSpecializationArgs();
 565
 566     // Iterate over all the template parameters
 567     for (size_t I = 0; I < TParams->size(); ++I) {
 568       const auto *TPDecl = dyn_cast<TemplateTypeParmDecl>(TParams->getParam(I));
 569       if (!TPDecl)
 570         continue;
 571
 572       if (TPDecl->isParameterPack())
 573         continue;
 574
 575       const auto TAType = TArgs->get(I).getAsType();
 576       if (!isIteratorType(TAType))
 577         continue;
 578
 579       SVal LHS = UndefinedVal();
 580
 581       // For every template parameter which is an iterator type in the
 582       // instantiation look for all functions' parameters' type by it and
 583       // check whether they belong to the same container
 584       for (auto J = 0U; J < Func->getNumParams(); ++J) {
 585         const auto *Param = Func->getParamDecl(J);
 586         const auto *ParamType =
 587             Param->getType()->getAs<SubstTemplateTypeParmType>();
 588         if (!ParamType ||
 589             ParamType->getReplacedParameter()->getDecl() != TPDecl)
 590           continue;
 591         if (LHS.isUndef()) {
 592           LHS = Call.getArgSVal(J);
 593         } else {
 594           verifyMatch(C, LHS, Call.getArgSVal(J));
 595         }
 596       }
 597     }
 598   }
 599 }
 600
 601 void IteratorChecker::checkPostCall(const CallEvent &Call,
 602                                     CheckerContext &C) const {
 603   // Record new iterator positions and iterator position changes
 604   const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
 605   if (!Func)
 606     return;
 607
 608   if (Func->isOverloadedOperator()) {
 609     const auto Op = Func->getOverloadedOperator();
 610     if (isAssignmentOperator(Op)) {
 611       const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call);
 612       if (Func->getParamDecl(0)->getType()->isRValueReferenceType()) {
 613         handleAssign(C, InstCall->getCXXThisVal(), Call.getOriginExpr(),
 614                      Call.getArgSVal(0));
 615       } else {
 616         handleAssign(C, InstCall->getCXXThisVal());
 617       }
 618     } else if (isSimpleComparisonOperator(Op)) {
 619       if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
 620         handleComparison(C, Call.getReturnValue(), InstCall->getCXXThisVal(),
 621                          Call.getArgSVal(0), Op);
 622       } else {
 623         handleComparison(C, Call.getReturnValue(), Call.getArgSVal(0),
 624                          Call.getArgSVal(1), Op);
 625       }
 626     } else if (isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) {
 627       if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
 628         if (Call.getNumArgs() >= 1) {
 629           handleRandomIncrOrDecr(C, Func->getOverloadedOperator(),
 630                                  Call.getReturnValue(),
 631                                  InstCall->getCXXThisVal(), Call.getArgSVal(0));
 632         }
 633       } else {
 634         if (Call.getNumArgs() >= 2) {
 635           handleRandomIncrOrDecr(C, Func->getOverloadedOperator(),
 636                                  Call.getReturnValue(), Call.getArgSVal(0),
 637                                  Call.getArgSVal(1));
 638         }
 639       }
 640     } else if (isIncrementOperator(Func->getOverloadedOperator())) {
 641       if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
 642         handleIncrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(),
 643                         Call.getNumArgs());
 644       } else {
 645         handleIncrement(C, Call.getReturnValue(), Call.getArgSVal(0),
 646                         Call.getNumArgs());
 647       }
 648     } else if (isDecrementOperator(Func->getOverloadedOperator())) {
 649       if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
 650         handleDecrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(),
 651                         Call.getNumArgs());
 652       } else {
 653         handleDecrement(C, Call.getReturnValue(), Call.getArgSVal(0),
 654                         Call.getNumArgs());
 655       }
 656     }
 657   } else {
 658     if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
 659       if (isAssignCall(Func)) {
 660         handleAssign(C, InstCall->getCXXThisVal());
 661       } else if (isClearCall(Func)) {
 662         handleClear(C, InstCall->getCXXThisVal());
 663       } else if (isPushBackCall(Func) || isEmplaceBackCall(Func)) {
 664         handlePushBack(C, InstCall->getCXXThisVal());
 665       } else if (isPopBackCall(Func)) {
 666         handlePopBack(C, InstCall->getCXXThisVal());
 667       } else if (isPushFrontCall(Func) || isEmplaceFrontCall(Func)) {
 668         handlePushFront(C, InstCall->getCXXThisVal());
 669       } else if (isPopFrontCall(Func)) {
 670         handlePopFront(C, InstCall->getCXXThisVal());
 671       } else if (isInsertCall(Func) || isEmplaceCall(Func)) {
 672         handleInsert(C, Call.getArgSVal(0));
 673       } else if (isEraseCall(Func)) {
 674         if (Call.getNumArgs() == 1) {
 675           handleErase(C, Call.getArgSVal(0));
 676         } else if (Call.getNumArgs() == 2) {
 677           handleErase(C, Call.getArgSVal(0), Call.getArgSVal(1));
 678         }
 679       } else if (isEraseAfterCall(Func)) {
 680         if (Call.getNumArgs() == 1) {
 681           handleEraseAfter(C, Call.getArgSVal(0));
 682         } else if (Call.getNumArgs() == 2) {
 683           handleEraseAfter(C, Call.getArgSVal(0), Call.getArgSVal(1));
 684         }
 685       }
 686     }
 687
 688     const auto *OrigExpr = Call.getOriginExpr();
 689     if (!OrigExpr)
 690       return;
 691
 692     if (!isIteratorType(Call.getResultType()))
 693       return;
 694
 695     auto State = C.getState();
 696
 697     if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
 698       if (isBeginCall(Func)) {
 699         handleBegin(C, OrigExpr, Call.getReturnValue(),
 700                     InstCall->getCXXThisVal());
 701         return;
 702       }
 703       if (isEndCall(Func)) {
 704         handleEnd(C, OrigExpr, Call.getReturnValue(),
 705                   InstCall->getCXXThisVal());
 706         return;
 707       }
 708     }
 709
 710     // Already bound to container?
 711     if (getIteratorPosition(State, Call.getReturnValue()))
 712       return;
 713
 714     // Copy-like and move constructors
 715     if (isa<CXXConstructorCall>(&Call) && Call.getNumArgs() == 1) {
 716       if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(0))) {
 717         State = setIteratorPosition(State, Call.getReturnValue(), *Pos);
 718         if (cast<CXXConstructorDecl>(Func)->isMoveConstructor()) {
 719           State = removeIteratorPosition(State, Call.getArgSVal(0));
 720         }
 721         C.addTransition(State);
 722         return;
 723       }
 724     }
 725
 726     // Assumption: if return value is an iterator which is not yet bound to a
 727     //             container, then look for the first iterator argument, and
 728     //             bind the return value to the same container. This approach
 729     //             works for STL algorithms.
 730     // FIXME: Add a more conservative mode
 731     for (unsigned i = 0; i < Call.getNumArgs(); ++i) {
 732       if (isIteratorType(Call.getArgExpr(i)->getType())) {
 733         if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(i))) {
 734           assignToContainer(C, OrigExpr, Call.getReturnValue(),
 735                             Pos->getContainer());
 736           return;
 737         }
 738       }
 739     }
 740   }
 741 }
 742
 743 void IteratorChecker::checkBind(SVal Loc, SVal Val, const Stmt *S,
 744                                 CheckerContext &C) const {
 745   auto State = C.getState();
 746   const auto *Pos = getIteratorPosition(State, Val);
 747   if (Pos) {
 748     State = setIteratorPosition(State, Loc, *Pos);
 749     C.addTransition(State);
 750   } else {
 751     const auto *OldPos = getIteratorPosition(State, Loc);
 752     if (OldPos) {
 753       State = removeIteratorPosition(State, Loc);
 754       C.addTransition(State);
 755     }
 756   }
 757 }
 758
 759 void IteratorChecker::checkPostStmt(const MaterializeTemporaryExpr *MTE,
 760                                     CheckerContext &C) const {
 761   /* Transfer iterator state to temporary objects */
 762   auto State = C.getState();
 763   const auto *Pos =
 764       getIteratorPosition(State, C.getSVal(MTE->GetTemporaryExpr()));
 765   if (!Pos)
 766     return;
 767   State = setIteratorPosition(State, C.getSVal(MTE), *Pos);
 768   C.addTransition(State);
 769 }
 770
 771 void IteratorChecker::checkLiveSymbols(ProgramStateRef State,
 772                                        SymbolReaper &SR) const {
 773   // Keep symbolic expressions of iterator positions, container begins and ends
 774   // alive
 775   auto RegionMap = State->get<IteratorRegionMap>();
 776   for (const auto Reg : RegionMap) {
 777     const auto Offset = Reg.second.getOffset();
 778     for (auto i = Offset->symbol_begin(); i != Offset->symbol_end(); ++i)
 779       if (isa<SymbolData>(*i))
 780         SR.markLive(*i);
 781   }
 782
 783   auto SymbolMap = State->get<IteratorSymbolMap>();
 784   for (const auto Sym : SymbolMap) {
 785     const auto Offset = Sym.second.getOffset();
 786     for (auto i = Offset->symbol_begin(); i != Offset->symbol_end(); ++i)
 787       if (isa<SymbolData>(*i))
 788         SR.markLive(*i);
 789   }
 790
 791   auto ContMap = State->get<ContainerMap>();
 792   for (const auto Cont : ContMap) {
 793     const auto CData = Cont.second;
 794     if (CData.getBegin()) {
 795       SR.markLive(CData.getBegin());
 796       if(const auto *SIE = dyn_cast<SymIntExpr>(CData.getBegin()))
 797         SR.markLive(SIE->getLHS());
 798     }
 799     if (CData.getEnd()) {
 800       SR.markLive(CData.getEnd());
 801       if(const auto *SIE = dyn_cast<SymIntExpr>(CData.getEnd()))
 802         SR.markLive(SIE->getLHS());
 803     }
 804   }
 805 }
 806
 807 void IteratorChecker::checkDeadSymbols(SymbolReaper &SR,
 808                                        CheckerContext &C) const {
 809   // Cleanup
 810   auto State = C.getState();
 811
 812   auto RegionMap = State->get<IteratorRegionMap>();
 813   for (const auto Reg : RegionMap) {
 814     if (!SR.isLiveRegion(Reg.first)) {
 815       // The region behind the `LazyCompoundVal` is often cleaned up before
 816       // the `LazyCompoundVal` itself. If there are iterator positions keyed
 817       // by these regions their cleanup must be deferred.
 818       if (!isBoundThroughLazyCompoundVal(State->getEnvironment(), Reg.first)) {
 819         State = State->remove<IteratorRegionMap>(Reg.first);
 820       }
 821     }
 822   }
 823
 824   auto SymbolMap = State->get<IteratorSymbolMap>();
 825   for (const auto Sym : SymbolMap) {
 826     if (!SR.isLive(Sym.first)) {
 827       State = State->remove<IteratorSymbolMap>(Sym.first);
 828     }
 829   }
 830
 831   auto ContMap = State->get<ContainerMap>();
 832   for (const auto Cont : ContMap) {
 833     if (!SR.isLiveRegion(Cont.first)) {
 834       // We must keep the container data while it has live iterators to be able
 835       // to compare them to the begin and the end of the container.
 836       if (!hasLiveIterators(State, Cont.first)) {
 837         State = State->remove<ContainerMap>(Cont.first);
 838       }
 839     }
 840   }
 841
 842   auto ComparisonMap = State->get<IteratorComparisonMap>();
 843   for (const auto Comp : ComparisonMap) {
 844     if (!SR.isLive(Comp.first)) {
 845       State = State->remove<IteratorComparisonMap>(Comp.first);
 846     }
 847   }
 848
 849   C.addTransition(State);
 850 }
 851
 852 ProgramStateRef IteratorChecker::evalAssume(ProgramStateRef State, SVal Cond,
 853                                             bool Assumption) const {
 854   // Load recorded comparison and transfer iterator state between sides
 855   // according to comparison operator and assumption
 856   const auto *SE = Cond.getAsSymExpr();
 857   if (!SE)
 858     return State;
 859
 860   auto Opc = getOpcode(SE);
 861   if (Opc != BO_EQ && Opc != BO_NE)
 862     return State;
 863
 864   bool Negated = false;
 865   const auto *Comp = loadComparison(State, SE);
 866   if (!Comp) {
 867     // Try negated comparison, which is a SymExpr to 0 integer comparison
 868     const auto *SIE = dyn_cast<SymIntExpr>(SE);
 869     if (!SIE)
 870       return State;
 871
 872     if (SIE->getRHS() != 0)
 873       return State;
 874
 875     SE = SIE->getLHS();
 876     Negated = SIE->getOpcode() == BO_EQ; // Equal to zero means negation
 877     Opc = getOpcode(SE);
 878     if (Opc != BO_EQ && Opc != BO_NE)
 879       return State;
 880
 881     Comp = loadComparison(State, SE);
 882     if (!Comp)
 883       return State;
 884   }
 885
 886   return processComparison(State, Comp->getLeft(), Comp->getRight(),
 887                            (Comp->isEquality() == Assumption) != Negated);
 888 }
 889
 890 void IteratorChecker::handleComparison(CheckerContext &C, const SVal &RetVal,
 891                                        const SVal &LVal, const SVal &RVal,
 892                                        OverloadedOperatorKind Op) const {
 893   // Record the operands and the operator of the comparison for the next
 894   // evalAssume, if the result is a symbolic expression. If it is a concrete
 895   // value (only one branch is possible), then transfer the state between
 896   // the operands according to the operator and the result
 897   auto State = C.getState();
 898   if (const auto *Condition = RetVal.getAsSymbolicExpression()) {
 899     const auto *LPos = getIteratorPosition(State, LVal);
 900     const auto *RPos = getIteratorPosition(State, RVal);
 901     if (!LPos && !RPos)
 902       return;
 903     State = saveComparison(State, Condition, LVal, RVal, Op == OO_EqualEqual);
 904     C.addTransition(State);
 905   } else if (const auto TruthVal = RetVal.getAs<nonloc::ConcreteInt>()) {
 906     if ((State = processComparison(
 907              State, getRegionOrSymbol(LVal), getRegionOrSymbol(RVal),
 908              (Op == OO_EqualEqual) == (TruthVal->getValue() != 0)))) {
 909       C.addTransition(State);
 910     } else {
 911       C.generateSink(State, C.getPredecessor());
 912     }
 913   }
 914 }
 915
 916 void IteratorChecker::verifyDereference(CheckerContext &C,
 917                                         const SVal &Val) const {
 918   auto State = C.getState();
 919   const auto *Pos = getIteratorPosition(State, Val);
 920   if (Pos && isPastTheEnd(State, *Pos)) {
 921     auto *N = C.generateNonFatalErrorNode(State);
 922     if (!N)
 923       return;
 924     reportOutOfRangeBug("Past-the-end iterator dereferenced.", Val, C, N);
 925     return;
 926   }
 927 }
 928
 929 void IteratorChecker::verifyAccess(CheckerContext &C, const SVal &Val) const {
 930   auto State = C.getState();
 931   const auto *Pos = getIteratorPosition(State, Val);
 932   if (Pos && !Pos->isValid()) {
 933     auto *N = C.generateNonFatalErrorNode(State);
 934     if (!N) {
 935       return;
 936     }
 937     reportInvalidatedBug("Invalidated iterator accessed.", Val, C, N);
 938   }
 939 }
 940
 941 void IteratorChecker::handleIncrement(CheckerContext &C, const SVal &RetVal,
 942                                       const SVal &Iter, bool Postfix) const {
 943   // Increment the symbolic expressions which represents the position of the
 944   // iterator
 945   auto State = C.getState();
 946   const auto *Pos = getIteratorPosition(State, Iter);
 947   if (Pos) {
 948     auto &SymMgr = C.getSymbolManager();
 949     auto &BVF = SymMgr.getBasicVals();
 950     const auto NewPos =
 951       advancePosition(C, OO_Plus, *Pos,
 952                     nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
 953     State = setIteratorPosition(State, Iter, NewPos);
 954     State = setIteratorPosition(State, RetVal, Postfix ? *Pos : NewPos);
 955     C.addTransition(State);
 956   }
 957 }
 958
 959 void IteratorChecker::handleDecrement(CheckerContext &C, const SVal &RetVal,
 960                                       const SVal &Iter, bool Postfix) const {
 961   // Decrement the symbolic expressions which represents the position of the
 962   // iterator
 963   auto State = C.getState();
 964   const auto *Pos = getIteratorPosition(State, Iter);
 965   if (Pos) {
 966     auto &SymMgr = C.getSymbolManager();
 967     auto &BVF = SymMgr.getBasicVals();
 968     const auto NewPos =
 969       advancePosition(C, OO_Minus, *Pos,
 970                     nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
 971     State = setIteratorPosition(State, Iter, NewPos);
 972     State = setIteratorPosition(State, RetVal, Postfix ? *Pos : NewPos);
 973     C.addTransition(State);
 974   }
 975 }
 976
 977 // This function tells the analyzer's engine that symbols produced by our
 978 // checker, most notably iterator positions, are relatively small.
 979 // A distance between items in the container should not be very large.
 980 // By assuming that it is within around 1/8 of the address space,
 981 // we can help the analyzer perform operations on these symbols
 982 // without being afraid of integer overflows.
 983 // FIXME: Should we provide it as an API, so that all checkers could use it?
 984 static ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym,
 985                                         long Scale) {
 986   SValBuilder &SVB = State->getStateManager().getSValBuilder();
 987   BasicValueFactory &BV = SVB.getBasicValueFactory();
 988
 989   QualType T = Sym->getType();
 990   assert(T->isSignedIntegerOrEnumerationType());
 991   APSIntType AT = BV.getAPSIntType(T);
 992
 993   ProgramStateRef NewState = State;
 994
 995   llvm::APSInt Max = AT.getMaxValue() / AT.getValue(Scale);
 996   SVal IsCappedFromAbove =
 997       SVB.evalBinOpNN(State, BO_LE, nonloc::SymbolVal(Sym),
 998                       nonloc::ConcreteInt(Max), SVB.getConditionType());
 999   if (auto DV = IsCappedFromAbove.getAs<DefinedSVal>()) {
1000     NewState = NewState->assume(*DV, true);
1001     if (!NewState)
1002       return State;
1003   }
1004
1005   llvm::APSInt Min = -Max;
1006   SVal IsCappedFromBelow =
1007       SVB.evalBinOpNN(State, BO_GE, nonloc::SymbolVal(Sym),
1008                       nonloc::ConcreteInt(Min), SVB.getConditionType());
1009   if (auto DV = IsCappedFromBelow.getAs<DefinedSVal>()) {
1010     NewState = NewState->assume(*DV, true);
1011     if (!NewState)
1012       return State;
1013   }
1014
1015   return NewState;
1016 }
1017
1018 void IteratorChecker::handleRandomIncrOrDecr(CheckerContext &C,
1019                                              OverloadedOperatorKind Op,
1020                                              const SVal &RetVal,
1021                                              const SVal &LHS,
1022                                              const SVal &RHS) const {
1023   // Increment or decrement the symbolic expressions which represents the
1024   // position of the iterator
1025   auto State = C.getState();
1026   const auto *Pos = getIteratorPosition(State, LHS);
1027   if (!Pos)
1028     return;
1029
1030   const auto *value = &RHS;
1031   if (auto loc = RHS.getAs<Loc>()) {
1032     const auto val = State->getRawSVal(*loc);
1033     value = &val;
1034   }
1035
1036   auto &TgtVal = (Op == OO_PlusEqual || Op == OO_MinusEqual) ? LHS : RetVal;
1037   State =
1038       setIteratorPosition(State, TgtVal, advancePosition(C, Op, *Pos, *value));
1039   C.addTransition(State);
1040 }
1041
1042 void IteratorChecker::verifyIncrement(CheckerContext &C,
1043                                       const SVal &Iter) const {
1044   auto &BVF = C.getSValBuilder().getBasicValueFactory();
1045   verifyRandomIncrOrDecr(C, OO_Plus, Iter,
1046                      nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
1047 }
1048
1049 void IteratorChecker::verifyDecrement(CheckerContext &C,
1050                                       const SVal &Iter) const {
1051   auto &BVF = C.getSValBuilder().getBasicValueFactory();
1052   verifyRandomIncrOrDecr(C, OO_Minus, Iter,
1053                      nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
1054 }
1055
1056 void IteratorChecker::verifyRandomIncrOrDecr(CheckerContext &C,
1057                                              OverloadedOperatorKind Op,
1058                                              const SVal &LHS,
1059                                              const SVal &RHS) const {
1060   auto State = C.getState();
1061
1062   // If the iterator is initially inside its range, then the operation is valid
1063   const auto *Pos = getIteratorPosition(State, LHS);
1064   if (!Pos)
1065     return;
1066
1067   auto Value = RHS;
1068   if (auto ValAsLoc = RHS.getAs<Loc>()) {
1069     Value = State->getRawSVal(*ValAsLoc);
1070   }
1071
1072   if (Value.isUnknown())
1073     return;
1074
1075   // Incremention or decremention by 0 is never a bug.
1076   if (isZero(State, Value.castAs<NonLoc>()))
1077     return;
1078
1079   // The result may be the past-end iterator of the container, but any other
1080   // out of range position is undefined behaviour
1081   if (isAheadOfRange(State, advancePosition(C, Op, *Pos, Value))) {
1082     auto *N = C.generateNonFatalErrorNode(State);
1083     if (!N)
1084       return;
1085     reportOutOfRangeBug("Iterator decremented ahead of its valid range.", LHS,
1086                         C, N);
1087   }
1088   if (isBehindPastTheEnd(State, advancePosition(C, Op, *Pos, Value))) {
1089     auto *N = C.generateNonFatalErrorNode(State);
1090     if (!N)
1091       return;
1092     reportOutOfRangeBug("Iterator incremented behind the past-the-end "
1093                         "iterator.", LHS, C, N);
1094   }
1095 }
1096
1097 void IteratorChecker::verifyMatch(CheckerContext &C, const SVal &Iter,
1098                                   const MemRegion *Cont) const {
1099   // Verify match between a container and the container of an iterator
1100   Cont = Cont->getMostDerivedObjectRegion();
1101
1102   auto State = C.getState();
1103   const auto *Pos = getIteratorPosition(State, Iter);
1104   if (Pos && Pos->getContainer() != Cont) {
1105     auto *N = C.generateNonFatalErrorNode(State);
1106     if (!N) {
1107       return;
1108     }
1109     reportMismatchedBug("Container accessed using foreign iterator argument.", Iter, Cont, C, N);
1110   }
1111 }
1112
1113 void IteratorChecker::verifyMatch(CheckerContext &C, const SVal &Iter1,
1114                                   const SVal &Iter2) const {
1115   // Verify match between the containers of two iterators
1116   auto State = C.getState();
1117   const auto *Pos1 = getIteratorPosition(State, Iter1);
1118   const auto *Pos2 = getIteratorPosition(State, Iter2);
1119   if (Pos1 && Pos2 && Pos1->getContainer() != Pos2->getContainer()) {
1120     auto *N = C.generateNonFatalErrorNode(State);
1121     if (!N)
1122       return;
1123     reportMismatchedBug("Iterators of different containers used where the "
1124                         "same container is expected.", Iter1, Iter2, C, N);
1125   }
1126 }
1127
1128 void IteratorChecker::handleBegin(CheckerContext &C, const Expr *CE,
1129                                   const SVal &RetVal, const SVal &Cont) const {
1130   const auto *ContReg = Cont.getAsRegion();
1131   if (!ContReg)
1132     return;
1133
1134   ContReg = ContReg->getMostDerivedObjectRegion();
1135
1136   // If the container already has a begin symbol then use it. Otherwise first
1137   // create a new one.
1138   auto State = C.getState();
1139   auto BeginSym = getContainerBegin(State, ContReg);
1140   if (!BeginSym) {
1141     auto &SymMgr = C.getSymbolManager();
1142     BeginSym = SymMgr.conjureSymbol(CE, C.getLocationContext(),
1143                                     C.getASTContext().LongTy, C.blockCount());
1144     State = assumeNoOverflow(State, BeginSym, 4);
1145     State = createContainerBegin(State, ContReg, BeginSym);
1146   }
1147   State = setIteratorPosition(State, RetVal,
1148                               IteratorPosition::getPosition(ContReg, BeginSym));
1149   C.addTransition(State);
1150 }
1151
1152 void IteratorChecker::handleEnd(CheckerContext &C, const Expr *CE,
1153                                 const SVal &RetVal, const SVal &Cont) const {
1154   const auto *ContReg = Cont.getAsRegion();
1155   if (!ContReg)
1156     return;
1157
1158   ContReg = ContReg->getMostDerivedObjectRegion();
1159
1160   // If the container already has an end symbol then use it. Otherwise first
1161   // create a new one.
1162   auto State = C.getState();
1163   auto EndSym = getContainerEnd(State, ContReg);
1164   if (!EndSym) {
1165     auto &SymMgr = C.getSymbolManager();
1166     EndSym = SymMgr.conjureSymbol(CE, C.getLocationContext(),
1167                                   C.getASTContext().LongTy, C.blockCount());
1168     State = assumeNoOverflow(State, EndSym, 4);
1169     State = createContainerEnd(State, ContReg, EndSym);
1170   }
1171   State = setIteratorPosition(State, RetVal,
1172                               IteratorPosition::getPosition(ContReg, EndSym));
1173   C.addTransition(State);
1174 }
1175
1176 void IteratorChecker::assignToContainer(CheckerContext &C, const Expr *CE,
1177                                         const SVal &RetVal,
1178                                         const MemRegion *Cont) const {
1179   Cont = Cont->getMostDerivedObjectRegion();
1180
1181   auto State = C.getState();
1182   auto &SymMgr = C.getSymbolManager();
1183   auto Sym = SymMgr.conjureSymbol(CE, C.getLocationContext(),
1184                                   C.getASTContext().LongTy, C.blockCount());
1185   State = assumeNoOverflow(State, Sym, 4);
1186   State = setIteratorPosition(State, RetVal,
1187                               IteratorPosition::getPosition(Cont, Sym));
1188   C.addTransition(State);
1189 }
1190
1191 void IteratorChecker::handleAssign(CheckerContext &C, const SVal &Cont,
1192                                    const Expr *CE, const SVal &OldCont) const {
1193   const auto *ContReg = Cont.getAsRegion();
1194   if (!ContReg)
1195     return;
1196
1197   ContReg = ContReg->getMostDerivedObjectRegion();
1198
1199   // Assignment of a new value to a container always invalidates all its
1200   // iterators
1201   auto State = C.getState();
1202   const auto CData = getContainerData(State, ContReg);
1203   if (CData) {
1204     State = invalidateAllIteratorPositions(State, ContReg);
1205   }
1206
1207   // In case of move, iterators of the old container (except the past-end
1208   // iterators) remain valid but refer to the new container
1209   if (!OldCont.isUndef()) {
1210     const auto *OldContReg = OldCont.getAsRegion();
1211     if (OldContReg) {
1212       OldContReg = OldContReg->getMostDerivedObjectRegion();
1213       const auto OldCData = getContainerData(State, OldContReg);
1214       if (OldCData) {
1215         if (const auto OldEndSym = OldCData->getEnd()) {
1216           // If we already assigned an "end" symbol to the old container, then
1217           // first reassign all iterator positions to the new container which
1218           // are not past the container (thus not greater or equal to the
1219           // current "end" symbol).
1220           State = reassignAllIteratorPositionsUnless(State, OldContReg, ContReg,
1221                                                      OldEndSym, BO_GE);
1222           auto &SymMgr = C.getSymbolManager();
1223           auto &SVB = C.getSValBuilder();
1224           // Then generate and assign a new "end" symbol for the new container.
1225           auto NewEndSym =
1226               SymMgr.conjureSymbol(CE, C.getLocationContext(),
1227                                    C.getASTContext().LongTy, C.blockCount());
1228           State = assumeNoOverflow(State, NewEndSym, 4);
1229           if (CData) {
1230             State = setContainerData(State, ContReg, CData->newEnd(NewEndSym));
1231           } else {
1232             State = setContainerData(State, ContReg,
1233                                      ContainerData::fromEnd(NewEndSym));
1234           }
1235           // Finally, replace the old "end" symbol in the already reassigned
1236           // iterator positions with the new "end" symbol.
1237           State = rebaseSymbolInIteratorPositionsIf(
1238               State, SVB, OldEndSym, NewEndSym, OldEndSym, BO_LT);
1239         } else {
1240           // There was no "end" symbol assigned yet to the old container,
1241           // so reassign all iterator positions to the new container.
1242           State = reassignAllIteratorPositions(State, OldContReg, ContReg);
1243         }
1244         if (const auto OldBeginSym = OldCData->getBegin()) {
1245           // If we already assigned a "begin" symbol to the old container, then
1246           // assign it to the new container and remove it from the old one.
1247           if (CData) {
1248             State =
1249                 setContainerData(State, ContReg, CData->newBegin(OldBeginSym));
1250           } else {
1251             State = setContainerData(State, ContReg,
1252                                      ContainerData::fromBegin(OldBeginSym));
1253           }
1254           State =
1255               setContainerData(State, OldContReg, OldCData->newEnd(nullptr));
1256         }
1257       } else {
1258         // There was neither "begin" nor "end" symbol assigned yet to the old
1259         // container, so reassign all iterator positions to the new container.
1260         State = reassignAllIteratorPositions(State, OldContReg, ContReg);
1261       }
1262     }
1263   }
1264   C.addTransition(State);
1265 }
1266
1267 void IteratorChecker::handleClear(CheckerContext &C, const SVal &Cont) const {
1268   const auto *ContReg = Cont.getAsRegion();
1269   if (!ContReg)
1270     return;
1271
1272   ContReg = ContReg->getMostDerivedObjectRegion();
1273
1274   // The clear() operation invalidates all the iterators, except the past-end
1275   // iterators of list-like containers
1276   auto State = C.getState();
1277   if (!hasSubscriptOperator(State, ContReg) ||
1278       !backModifiable(State, ContReg)) {
1279     const auto CData = getContainerData(State, ContReg);
1280     if (CData) {
1281       if (const auto EndSym = CData->getEnd()) {
1282         State =
1283             invalidateAllIteratorPositionsExcept(State, ContReg, EndSym, BO_GE);
1284         C.addTransition(State);
1285         return;
1286       }
1287     }
1288   }
1289   State = invalidateAllIteratorPositions(State, ContReg);
1290   C.addTransition(State);
1291 }
1292
1293 void IteratorChecker::handlePushBack(CheckerContext &C,
1294                                      const SVal &Cont) const {
1295   const auto *ContReg = Cont.getAsRegion();
1296   if (!ContReg)
1297     return;
1298
1299   ContReg = ContReg->getMostDerivedObjectRegion();
1300
1301   // For deque-like containers invalidate all iterator positions
1302   auto State = C.getState();
1303   if (hasSubscriptOperator(State, ContReg) && frontModifiable(State, ContReg)) {
1304     State = invalidateAllIteratorPositions(State, ContReg);
1305     C.addTransition(State);
1306     return;
1307   }
1308
1309   const auto CData = getContainerData(State, ContReg);
1310   if (!CData)
1311     return;
1312
1313   // For vector-like containers invalidate the past-end iterator positions
1314   if (const auto EndSym = CData->getEnd()) {
1315     if (hasSubscriptOperator(State, ContReg)) {
1316       State = invalidateIteratorPositions(State, EndSym, BO_GE);
1317     }
1318     auto &SymMgr = C.getSymbolManager();
1319     auto &BVF = SymMgr.getBasicVals();
1320     auto &SVB = C.getSValBuilder();
1321     const auto newEndSym =
1322       SVB.evalBinOp(State, BO_Add,
1323                     nonloc::SymbolVal(EndSym),
1324                     nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
1325                     SymMgr.getType(EndSym)).getAsSymbol();
1326     State = setContainerData(State, ContReg, CData->newEnd(newEndSym));
1327   }
1328   C.addTransition(State);
1329 }
1330
1331 void IteratorChecker::handlePopBack(CheckerContext &C, const SVal &Cont) const {
1332   const auto *ContReg = Cont.getAsRegion();
1333   if (!ContReg)
1334     return;
1335
1336   ContReg = ContReg->getMostDerivedObjectRegion();
1337
1338   auto State = C.getState();
1339   const auto CData = getContainerData(State, ContReg);
1340   if (!CData)
1341     return;
1342
1343   if (const auto EndSym = CData->getEnd()) {
1344     auto &SymMgr = C.getSymbolManager();
1345     auto &BVF = SymMgr.getBasicVals();
1346     auto &SVB = C.getSValBuilder();
1347     const auto BackSym =
1348       SVB.evalBinOp(State, BO_Sub,
1349                     nonloc::SymbolVal(EndSym),
1350                     nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
1351                     SymMgr.getType(EndSym)).getAsSymbol();
1352     // For vector-like and deque-like containers invalidate the last and the
1353     // past-end iterator positions. For list-like containers only invalidate
1354     // the last position
1355     if (hasSubscriptOperator(State, ContReg) &&
1356         backModifiable(State, ContReg)) {
1357       State = invalidateIteratorPositions(State, BackSym, BO_GE);
1358       State = setContainerData(State, ContReg, CData->newEnd(nullptr));
1359     } else {
1360       State = invalidateIteratorPositions(State, BackSym, BO_EQ);
1361     }
1362     auto newEndSym = BackSym;
1363     State = setContainerData(State, ContReg, CData->newEnd(newEndSym));
1364     C.addTransition(State);
1365   }
1366 }
1367
1368 void IteratorChecker::handlePushFront(CheckerContext &C,
1369                                       const SVal &Cont) const {
1370   const auto *ContReg = Cont.getAsRegion();
1371   if (!ContReg)
1372     return;
1373
1374   ContReg = ContReg->getMostDerivedObjectRegion();
1375
1376   // For deque-like containers invalidate all iterator positions
1377   auto State = C.getState();
1378   if (hasSubscriptOperator(State, ContReg)) {
1379     State = invalidateAllIteratorPositions(State, ContReg);
1380     C.addTransition(State);
1381   } else {
1382     const auto CData = getContainerData(State, ContReg);
1383     if (!CData)
1384       return;
1385
1386     if (const auto BeginSym = CData->getBegin()) {
1387       auto &SymMgr = C.getSymbolManager();
1388       auto &BVF = SymMgr.getBasicVals();
1389       auto &SVB = C.getSValBuilder();
1390       const auto newBeginSym =
1391         SVB.evalBinOp(State, BO_Sub,
1392                       nonloc::SymbolVal(BeginSym),
1393                       nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
1394                       SymMgr.getType(BeginSym)).getAsSymbol();
1395       State = setContainerData(State, ContReg, CData->newBegin(newBeginSym));
1396       C.addTransition(State);
1397     }
1398   }
1399 }
1400
1401 void IteratorChecker::handlePopFront(CheckerContext &C,
1402                                      const SVal &Cont) const {
1403   const auto *ContReg = Cont.getAsRegion();
1404   if (!ContReg)
1405     return;
1406
1407   ContReg = ContReg->getMostDerivedObjectRegion();
1408
1409   auto State = C.getState();
1410   const auto CData = getContainerData(State, ContReg);
1411   if (!CData)
1412     return;
1413
1414   // For deque-like containers invalidate all iterator positions. For list-like
1415   // iterators only invalidate the first position
1416   if (const auto BeginSym = CData->getBegin()) {
1417     if (hasSubscriptOperator(State, ContReg)) {
1418       State = invalidateIteratorPositions(State, BeginSym, BO_LE);
1419     } else {
1420       State = invalidateIteratorPositions(State, BeginSym, BO_EQ);
1421     }
1422     auto &SymMgr = C.getSymbolManager();
1423     auto &BVF = SymMgr.getBasicVals();
1424     auto &SVB = C.getSValBuilder();
1425     const auto newBeginSym =
1426       SVB.evalBinOp(State, BO_Add,
1427                     nonloc::SymbolVal(BeginSym),
1428                     nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
1429                     SymMgr.getType(BeginSym)).getAsSymbol();
1430     State = setContainerData(State, ContReg, CData->newBegin(newBeginSym));
1431     C.addTransition(State);
1432   }
1433 }
1434
1435 void IteratorChecker::handleInsert(CheckerContext &C, const SVal &Iter) const {
1436   auto State = C.getState();
1437   const auto *Pos = getIteratorPosition(State, Iter);
1438   if (!Pos)
1439     return;
1440
1441   // For deque-like containers invalidate all iterator positions. For
1442   // vector-like containers invalidate iterator positions after the insertion.
1443   const auto *Cont = Pos->getContainer();
1444   if (hasSubscriptOperator(State, Cont) && backModifiable(State, Cont)) {
1445     if (frontModifiable(State, Cont)) {
1446       State = invalidateAllIteratorPositions(State, Cont);
1447     } else {
1448       State = invalidateIteratorPositions(State, Pos->getOffset(), BO_GE);
1449     }
1450     if (const auto *CData = getContainerData(State, Cont)) {
1451       if (const auto EndSym = CData->getEnd()) {
1452         State = invalidateIteratorPositions(State, EndSym, BO_GE);
1453         State = setContainerData(State, Cont, CData->newEnd(nullptr));
1454       }
1455     }
1456     C.addTransition(State);
1457   }
1458 }
1459
1460 void IteratorChecker::handleErase(CheckerContext &C, const SVal &Iter) const {
1461   auto State = C.getState();
1462   const auto *Pos = getIteratorPosition(State, Iter);
1463   if (!Pos)
1464     return;
1465
1466   // For deque-like containers invalidate all iterator positions. For
1467   // vector-like containers invalidate iterator positions at and after the
1468   // deletion. For list-like containers only invalidate the deleted position.
1469   const auto *Cont = Pos->getContainer();
1470   if (hasSubscriptOperator(State, Cont) && backModifiable(State, Cont)) {
1471     if (frontModifiable(State, Cont)) {
1472       State = invalidateAllIteratorPositions(State, Cont);
1473     } else {
1474       State = invalidateIteratorPositions(State, Pos->getOffset(), BO_GE);
1475     }
1476     if (const auto *CData = getContainerData(State, Cont)) {
1477       if (const auto EndSym = CData->getEnd()) {
1478         State = invalidateIteratorPositions(State, EndSym, BO_GE);
1479         State = setContainerData(State, Cont, CData->newEnd(nullptr));
1480       }
1481     }
1482   } else {
1483     State = invalidateIteratorPositions(State, Pos->getOffset(), BO_EQ);
1484   }
1485   C.addTransition(State);
1486 }
1487
1488 void IteratorChecker::handleErase(CheckerContext &C, const SVal &Iter1,
1489                                   const SVal &Iter2) const {
1490   auto State = C.getState();
1491   const auto *Pos1 = getIteratorPosition(State, Iter1);
1492   const auto *Pos2 = getIteratorPosition(State, Iter2);
1493   if (!Pos1 || !Pos2)
1494     return;
1495
1496   // For deque-like containers invalidate all iterator positions. For
1497   // vector-like containers invalidate iterator positions at and after the
1498   // deletion range. For list-like containers only invalidate the deleted
1499   // position range [first..last].
1500   const auto *Cont = Pos1->getContainer();
1501   if (hasSubscriptOperator(State, Cont) && backModifiable(State, Cont)) {
1502     if (frontModifiable(State, Cont)) {
1503       State = invalidateAllIteratorPositions(State, Cont);
1504     } else {
1505       State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GE);
1506     }
1507     if (const auto *CData = getContainerData(State, Cont)) {
1508       if (const auto EndSym = CData->getEnd()) {
1509         State = invalidateIteratorPositions(State, EndSym, BO_GE);
1510         State = setContainerData(State, Cont, CData->newEnd(nullptr));
1511       }
1512     }
1513   } else {
1514     State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GE,
1515                                         Pos2->getOffset(), BO_LT);
1516   }
1517   C.addTransition(State);
1518 }
1519
1520 void IteratorChecker::handleEraseAfter(CheckerContext &C,
1521                                        const SVal &Iter) const {
1522   auto State = C.getState();
1523   const auto *Pos = getIteratorPosition(State, Iter);
1524   if (!Pos)
1525     return;
1526
1527   // Invalidate the deleted iterator position, which is the position of the
1528   // parameter plus one.
1529   auto &SymMgr = C.getSymbolManager();
1530   auto &BVF = SymMgr.getBasicVals();
1531   auto &SVB = C.getSValBuilder();
1532   const auto NextSym =
1533     SVB.evalBinOp(State, BO_Add,
1534                   nonloc::SymbolVal(Pos->getOffset()),
1535                   nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
1536                   SymMgr.getType(Pos->getOffset())).getAsSymbol();
1537   State = invalidateIteratorPositions(State, NextSym, BO_EQ);
1538   C.addTransition(State);
1539 }
1540
1541 void IteratorChecker::handleEraseAfter(CheckerContext &C, const SVal &Iter1,
1542                                        const SVal &Iter2) const {
1543   auto State = C.getState();
1544   const auto *Pos1 = getIteratorPosition(State, Iter1);
1545   const auto *Pos2 = getIteratorPosition(State, Iter2);
1546   if (!Pos1 || !Pos2)
1547     return;
1548
1549   // Invalidate the deleted iterator position range (first..last)
1550   State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GT,
1551                                       Pos2->getOffset(), BO_LT);
1552   C.addTransition(State);
1553 }
1554
1555 IteratorPosition IteratorChecker::advancePosition(CheckerContext &C,
1556                                                   OverloadedOperatorKind Op,
1557                                                   const IteratorPosition &Pos,
1558                                                   const SVal &Distance) const {
1559   auto State = C.getState();
1560   auto &SymMgr = C.getSymbolManager();
1561   auto &SVB = C.getSValBuilder();
1562
1563   assert ((Op == OO_Plus || Op == OO_PlusEqual ||
1564            Op == OO_Minus || Op == OO_MinusEqual) &&
1565           "Advance operator must be one of +, -, += and -=.");
1566   auto BinOp = (Op == OO_Plus || Op == OO_PlusEqual) ? BO_Add : BO_Sub;
1567   if (const auto IntDist = Distance.getAs<nonloc::ConcreteInt>()) {
1568     // For concrete integers we can calculate the new position
1569     return Pos.setTo(SVB.evalBinOp(State, BinOp,
1570                                    nonloc::SymbolVal(Pos.getOffset()), *IntDist,
1571                                    SymMgr.getType(Pos.getOffset()))
1572                          .getAsSymbol());
1573   } else {
1574     // For other symbols create a new symbol to keep expressions simple
1575     const auto &LCtx = C.getLocationContext();
1576     const auto NewPosSym = SymMgr.conjureSymbol(nullptr, LCtx,
1577                                              SymMgr.getType(Pos.getOffset()),
1578                                              C.blockCount());
1579     State = assumeNoOverflow(State, NewPosSym, 4);
1580     return Pos.setTo(NewPosSym);
1581   }
1582 }
1583
1584 void IteratorChecker::reportOutOfRangeBug(const StringRef &Message,
1585                                           const SVal &Val, CheckerContext &C,
1586                                           ExplodedNode *ErrNode) const {
1587   auto R = llvm::make_unique<BugReport>(*OutOfRangeBugType, Message, ErrNode);
1588   R->markInteresting(Val);
1589   C.emitReport(std::move(R));
1590 }
1591
1592 void IteratorChecker::reportMismatchedBug(const StringRef &Message,
1593                                           const SVal &Val1, const SVal &Val2,
1594                                           CheckerContext &C,
1595                                           ExplodedNode *ErrNode) const {
1596   auto R = llvm::make_unique<BugReport>(*MismatchedBugType, Message, ErrNode);
1597   R->markInteresting(Val1);
1598   R->markInteresting(Val2);
1599   C.emitReport(std::move(R));
1600 }
1601
1602 void IteratorChecker::reportMismatchedBug(const StringRef &Message,
1603                                           const SVal &Val, const MemRegion *Reg,
1604                                           CheckerContext &C,
1605                                           ExplodedNode *ErrNode) const {
1606   auto R = llvm::make_unique<BugReport>(*MismatchedBugType, Message, ErrNode);
1607   R->markInteresting(Val);
1608   R->markInteresting(Reg);
1609   C.emitReport(std::move(R));
1610 }
1611
1612 void IteratorChecker::reportInvalidatedBug(const StringRef &Message,
1613                                            const SVal &Val, CheckerContext &C,
1614                                            ExplodedNode *ErrNode) const {
1615   auto R = llvm::make_unique<BugReport>(*InvalidatedBugType, Message, ErrNode);
1616   R->markInteresting(Val);
1617   C.emitReport(std::move(R));
1618 }
1619
1620 namespace {
1621
1622 bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
1623 bool isGreater(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
1624 bool isEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
1625 bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
1626              BinaryOperator::Opcode Opc);
1627 bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2,
1628              BinaryOperator::Opcode Opc);
1629 const CXXRecordDecl *getCXXRecordDecl(ProgramStateRef State,
1630                                       const MemRegion *Reg);
1631 SymbolRef rebaseSymbol(ProgramStateRef State, SValBuilder &SVB, SymbolRef Expr,
1632                         SymbolRef OldSym, SymbolRef NewSym);
1633
1634 bool isIteratorType(const QualType &Type) {
1635   if (Type->isPointerType())
1636     return true;
1637
1638   const auto *CRD = Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl();
1639   return isIterator(CRD);
1640 }
1641
1642 bool isIterator(const CXXRecordDecl *CRD) {
1643   if (!CRD)
1644     return false;
1645
1646   const auto Name = CRD->getName();
1647   if (!(Name.endswith_lower("iterator") || Name.endswith_lower("iter") ||
1648         Name.endswith_lower("it")))
1649     return false;
1650
1651   bool HasCopyCtor = false, HasCopyAssign = true, HasDtor = false,
1652        HasPreIncrOp = false, HasPostIncrOp = false, HasDerefOp = false;
1653   for (const auto *Method : CRD->methods()) {
1654     if (const auto *Ctor = dyn_cast<CXXConstructorDecl>(Method)) {
1655       if (Ctor->isCopyConstructor()) {
1656         HasCopyCtor = !Ctor->isDeleted() && Ctor->getAccess() == AS_public;
1657       }
1658       continue;
1659     }
1660     if (const auto *Dtor = dyn_cast<CXXDestructorDecl>(Method)) {
1661       HasDtor = !Dtor->isDeleted() && Dtor->getAccess() == AS_public;
1662       continue;
1663     }
1664     if (Method->isCopyAssignmentOperator()) {
1665       HasCopyAssign = !Method->isDeleted() && Method->getAccess() == AS_public;
1666       continue;
1667     }
1668     if (!Method->isOverloadedOperator())
1669       continue;
1670     const auto OPK = Method->getOverloadedOperator();
1671     if (OPK == OO_PlusPlus) {
1672       HasPreIncrOp = HasPreIncrOp || (Method->getNumParams() == 0);
1673       HasPostIncrOp = HasPostIncrOp || (Method->getNumParams() == 1);
1674       continue;
1675     }
1676     if (OPK == OO_Star) {
1677       HasDerefOp = (Method->getNumParams() == 0);
1678       continue;
1679     }
1680   }
1681
1682   return HasCopyCtor && HasCopyAssign && HasDtor && HasPreIncrOp &&
1683          HasPostIncrOp && HasDerefOp;
1684 }
1685
1686 bool isComparisonOperator(OverloadedOperatorKind OK) {
1687   return OK == OO_EqualEqual || OK == OO_ExclaimEqual || OK == OO_Less ||
1688          OK == OO_LessEqual || OK == OO_Greater || OK == OO_GreaterEqual;
1689 }
1690
1691 bool isBeginCall(const FunctionDecl *Func) {
1692   const auto *IdInfo = Func->getIdentifier();
1693   if (!IdInfo)
1694     return false;
1695   return IdInfo->getName().endswith_lower("begin");
1696 }
1697
1698 bool isEndCall(const FunctionDecl *Func) {
1699   const auto *IdInfo = Func->getIdentifier();
1700   if (!IdInfo)
1701     return false;
1702   return IdInfo->getName().endswith_lower("end");
1703 }
1704
1705 bool isAssignCall(const FunctionDecl *Func) {
1706   const auto *IdInfo = Func->getIdentifier();
1707   if (!IdInfo)
1708     return false;
1709   if (Func->getNumParams() > 2)
1710     return false;
1711   return IdInfo->getName() == "assign";
1712 }
1713
1714 bool isClearCall(const FunctionDecl *Func) {
1715   const auto *IdInfo = Func->getIdentifier();
1716   if (!IdInfo)
1717     return false;
1718   if (Func->getNumParams() > 0)
1719     return false;
1720   return IdInfo->getName() == "clear";
1721 }
1722
1723 bool isPushBackCall(const FunctionDecl *Func) {
1724   const auto *IdInfo = Func->getIdentifier();
1725   if (!IdInfo)
1726     return false;
1727   if (Func->getNumParams() != 1)
1728     return false;
1729   return IdInfo->getName() == "push_back";
1730 }
1731
1732 bool isEmplaceBackCall(const FunctionDecl *Func) {
1733   const auto *IdInfo = Func->getIdentifier();
1734   if (!IdInfo)
1735     return false;
1736   if (Func->getNumParams() < 1)
1737     return false;
1738   return IdInfo->getName() == "emplace_back";
1739 }
1740
1741 bool isPopBackCall(const FunctionDecl *Func) {
1742   const auto *IdInfo = Func->getIdentifier();
1743   if (!IdInfo)
1744     return false;
1745   if (Func->getNumParams() > 0)
1746     return false;
1747   return IdInfo->getName() == "pop_back";
1748 }
1749
1750 bool isPushFrontCall(const FunctionDecl *Func) {
1751   const auto *IdInfo = Func->getIdentifier();
1752   if (!IdInfo)
1753     return false;
1754   if (Func->getNumParams() != 1)
1755     return false;
1756   return IdInfo->getName() == "push_front";
1757 }
1758
1759 bool isEmplaceFrontCall(const FunctionDecl *Func) {
1760   const auto *IdInfo = Func->getIdentifier();
1761   if (!IdInfo)
1762     return false;
1763   if (Func->getNumParams() < 1)
1764     return false;
1765   return IdInfo->getName() == "emplace_front";
1766 }
1767
1768 bool isPopFrontCall(const FunctionDecl *Func) {
1769   const auto *IdInfo = Func->getIdentifier();
1770   if (!IdInfo)
1771     return false;
1772   if (Func->getNumParams() > 0)
1773     return false;
1774   return IdInfo->getName() == "pop_front";
1775 }
1776
1777 bool isInsertCall(const FunctionDecl *Func) {
1778   const auto *IdInfo = Func->getIdentifier();
1779   if (!IdInfo)
1780     return false;
1781   if (Func->getNumParams() < 2 || Func->getNumParams() > 3)
1782     return false;
1783   if (!isIteratorType(Func->getParamDecl(0)->getType()))
1784     return false;
1785   return IdInfo->getName() == "insert";
1786 }
1787
1788 bool isEmplaceCall(const FunctionDecl *Func) {
1789   const auto *IdInfo = Func->getIdentifier();
1790   if (!IdInfo)
1791     return false;
1792   if (Func->getNumParams() < 2)
1793     return false;
1794   if (!isIteratorType(Func->getParamDecl(0)->getType()))
1795     return false;
1796   return IdInfo->getName() == "emplace";
1797 }
1798
1799 bool isEraseCall(const FunctionDecl *Func) {
1800   const auto *IdInfo = Func->getIdentifier();
1801   if (!IdInfo)
1802     return false;
1803   if (Func->getNumParams() < 1 || Func->getNumParams() > 2)
1804     return false;
1805   if (!isIteratorType(Func->getParamDecl(0)->getType()))
1806     return false;
1807   if (Func->getNumParams() == 2 &&
1808       !isIteratorType(Func->getParamDecl(1)->getType()))
1809     return false;
1810   return IdInfo->getName() == "erase";
1811 }
1812
1813 bool isEraseAfterCall(const FunctionDecl *Func) {
1814   const auto *IdInfo = Func->getIdentifier();
1815   if (!IdInfo)
1816     return false;
1817   if (Func->getNumParams() < 1 || Func->getNumParams() > 2)
1818     return false;
1819   if (!isIteratorType(Func->getParamDecl(0)->getType()))
1820     return false;
1821   if (Func->getNumParams() == 2 &&
1822       !isIteratorType(Func->getParamDecl(1)->getType()))
1823     return false;
1824   return IdInfo->getName() == "erase_after";
1825 }
1826
1827 bool isAssignmentOperator(OverloadedOperatorKind OK) { return OK == OO_Equal; }
1828
1829 bool isSimpleComparisonOperator(OverloadedOperatorKind OK) {
1830   return OK == OO_EqualEqual || OK == OO_ExclaimEqual;
1831 }
1832
1833 bool isAccessOperator(OverloadedOperatorKind OK) {
1834   return isDereferenceOperator(OK) || isIncrementOperator(OK) ||
1835          isDecrementOperator(OK) || isRandomIncrOrDecrOperator(OK);
1836 }
1837
1838 bool isDereferenceOperator(OverloadedOperatorKind OK) {
1839   return OK == OO_Star || OK == OO_Arrow || OK == OO_ArrowStar ||
1840          OK == OO_Subscript;
1841 }
1842
1843 bool isIncrementOperator(OverloadedOperatorKind OK) {
1844   return OK == OO_PlusPlus;
1845 }
1846
1847 bool isDecrementOperator(OverloadedOperatorKind OK) {
1848   return OK == OO_MinusMinus;
1849 }
1850
1851 bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK) {
1852   return OK == OO_Plus || OK == OO_PlusEqual || OK == OO_Minus ||
1853          OK == OO_MinusEqual;
1854 }
1855
1856 BinaryOperator::Opcode getOpcode(const SymExpr *SE) {
1857   if (const auto *BSE = dyn_cast<BinarySymExpr>(SE)) {
1858     return BSE->getOpcode();
1859   } else if (const auto *SC = dyn_cast<SymbolConjured>(SE)) {
1860     const auto *COE = dyn_cast_or_null<CXXOperatorCallExpr>(SC->getStmt());
1861     if (!COE)
1862       return BO_Comma; // Extremal value, neither EQ nor NE
1863     if (COE->getOperator() == OO_EqualEqual) {
1864       return BO_EQ;
1865     } else if (COE->getOperator() == OO_ExclaimEqual) {
1866       return BO_NE;
1867     }
1868     return BO_Comma; // Extremal value, neither EQ nor NE
1869   }
1870   return BO_Comma; // Extremal value, neither EQ nor NE
1871 }
1872
1873 bool hasSubscriptOperator(ProgramStateRef State, const MemRegion *Reg) {
1874   const auto *CRD = getCXXRecordDecl(State, Reg);
1875   if (!CRD)
1876     return false;
1877
1878   for (const auto *Method : CRD->methods()) {
1879     if (!Method->isOverloadedOperator())
1880       continue;
1881     const auto OPK = Method->getOverloadedOperator();
1882     if (OPK == OO_Subscript) {
1883       return true;
1884     }
1885   }
1886   return false;
1887 }
1888
1889 bool frontModifiable(ProgramStateRef State, const MemRegion *Reg) {
1890   const auto *CRD = getCXXRecordDecl(State, Reg);
1891   if (!CRD)
1892     return false;
1893
1894   for (const auto *Method : CRD->methods()) {
1895     if (!Method->getDeclName().isIdentifier())
1896       continue;
1897     if (Method->getName() == "push_front" || Method->getName() == "pop_front") {
1898       return true;
1899     }
1900   }
1901   return false;
1902 }
1903
1904 bool backModifiable(ProgramStateRef State, const MemRegion *Reg) {
1905   const auto *CRD = getCXXRecordDecl(State, Reg);
1906   if (!CRD)
1907     return false;
1908
1909   for (const auto *Method : CRD->methods()) {
1910     if (!Method->getDeclName().isIdentifier())
1911       continue;
1912     if (Method->getName() == "push_back" || Method->getName() == "pop_back") {
1913       return true;
1914     }
1915   }
1916   return false;
1917 }
1918
1919 const CXXRecordDecl *getCXXRecordDecl(ProgramStateRef State,
1920                                       const MemRegion *Reg) {
1921   auto TI = getDynamicTypeInfo(State, Reg);
1922   if (!TI.isValid())
1923     return nullptr;
1924
1925   auto Type = TI.getType();
1926   if (const auto *RefT = Type->getAs<ReferenceType>()) {
1927     Type = RefT->getPointeeType();
1928   }
1929
1930   return Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl();
1931 }
1932
1933 const RegionOrSymbol getRegionOrSymbol(const SVal &Val) {
1934   if (const auto Reg = Val.getAsRegion()) {
1935     return Reg;
1936   } else if (const auto Sym = Val.getAsSymbol()) {
1937     return Sym;
1938   } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
1939     return LCVal->getRegion();
1940   }
1941   return RegionOrSymbol();
1942 }
1943
1944 const ProgramStateRef processComparison(ProgramStateRef State,
1945                                         RegionOrSymbol LVal,
1946                                         RegionOrSymbol RVal, bool Equal) {
1947   const auto *LPos = getIteratorPosition(State, LVal);
1948   const auto *RPos = getIteratorPosition(State, RVal);
1949   if (LPos && !RPos) {
1950     State = adjustIteratorPosition(State, RVal, *LPos, Equal);
1951   } else if (!LPos && RPos) {
1952     State = adjustIteratorPosition(State, LVal, *RPos, Equal);
1953   } else if (LPos && RPos) {
1954     State = relateIteratorPositions(State, *LPos, *RPos, Equal);
1955   }
1956   return State;
1957 }
1958
1959 const ProgramStateRef saveComparison(ProgramStateRef State,
1960                                      const SymExpr *Condition, const SVal &LVal,
1961                                      const SVal &RVal, bool Eq) {
1962   const auto Left = getRegionOrSymbol(LVal);
1963   const auto Right = getRegionOrSymbol(RVal);
1964   if (!Left || !Right)
1965     return State;
1966   return State->set<IteratorComparisonMap>(Condition,
1967                                            IteratorComparison(Left, Right, Eq));
1968 }
1969
1970 const IteratorComparison *loadComparison(ProgramStateRef State,
1971                                          const SymExpr *Condition) {
1972   return State->get<IteratorComparisonMap>(Condition);
1973 }
1974
1975 SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont) {
1976   const auto *CDataPtr = getContainerData(State, Cont);
1977   if (!CDataPtr)
1978     return nullptr;
1979
1980   return CDataPtr->getBegin();
1981 }
1982
1983 SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont) {
1984   const auto *CDataPtr = getContainerData(State, Cont);
1985   if (!CDataPtr)
1986     return nullptr;
1987
1988   return CDataPtr->getEnd();
1989 }
1990
1991 ProgramStateRef createContainerBegin(ProgramStateRef State,
1992                                      const MemRegion *Cont,
1993                                      const SymbolRef Sym) {
1994   // Only create if it does not exist
1995   const auto *CDataPtr = getContainerData(State, Cont);
1996   if (CDataPtr) {
1997     if (CDataPtr->getBegin()) {
1998       return State;
1999     }
2000     const auto CData = CDataPtr->newBegin(Sym);
2001     return setContainerData(State, Cont, CData);
2002   }
2003   const auto CData = ContainerData::fromBegin(Sym);
2004   return setContainerData(State, Cont, CData);
2005 }
2006
2007 ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont,
2008                                    const SymbolRef Sym) {
2009   // Only create if it does not exist
2010   const auto *CDataPtr = getContainerData(State, Cont);
2011   if (CDataPtr) {
2012     if (CDataPtr->getEnd()) {
2013       return State;
2014     }
2015     const auto CData = CDataPtr->newEnd(Sym);
2016     return setContainerData(State, Cont, CData);
2017   }
2018   const auto CData = ContainerData::fromEnd(Sym);
2019   return setContainerData(State, Cont, CData);
2020 }
2021
2022 const ContainerData *getContainerData(ProgramStateRef State,
2023                                       const MemRegion *Cont) {
2024   return State->get<ContainerMap>(Cont);
2025 }
2026
2027 ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont,
2028                                  const ContainerData &CData) {
2029   return State->set<ContainerMap>(Cont, CData);
2030 }
2031
2032 const IteratorPosition *getIteratorPosition(ProgramStateRef State,
2033                                             const SVal &Val) {
2034   if (auto Reg = Val.getAsRegion()) {
2035     Reg = Reg->getMostDerivedObjectRegion();
2036     return State->get<IteratorRegionMap>(Reg);
2037   } else if (const auto Sym = Val.getAsSymbol()) {
2038     return State->get<IteratorSymbolMap>(Sym);
2039   } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
2040     return State->get<IteratorRegionMap>(LCVal->getRegion());
2041   }
2042   return nullptr;
2043 }
2044
2045 const IteratorPosition *getIteratorPosition(ProgramStateRef State,
2046                                             RegionOrSymbol RegOrSym) {
2047   if (RegOrSym.is<const MemRegion *>()) {
2048     auto Reg = RegOrSym.get<const MemRegion *>()->getMostDerivedObjectRegion();
2049     return State->get<IteratorRegionMap>(Reg);
2050   } else if (RegOrSym.is<SymbolRef>()) {
2051     return State->get<IteratorSymbolMap>(RegOrSym.get<SymbolRef>());
2052   }
2053   return nullptr;
2054 }
2055
2056 ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val,
2057                                     const IteratorPosition &Pos) {
2058   if (auto Reg = Val.getAsRegion()) {
2059     Reg = Reg->getMostDerivedObjectRegion();
2060     return State->set<IteratorRegionMap>(Reg, Pos);
2061   } else if (const auto Sym = Val.getAsSymbol()) {
2062     return State->set<IteratorSymbolMap>(Sym, Pos);
2063   } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
2064     return State->set<IteratorRegionMap>(LCVal->getRegion(), Pos);
2065   }
2066   return nullptr;
2067 }
2068
2069 ProgramStateRef setIteratorPosition(ProgramStateRef State,
2070                                     RegionOrSymbol RegOrSym,
2071                                     const IteratorPosition &Pos) {
2072   if (RegOrSym.is<const MemRegion *>()) {
2073     auto Reg = RegOrSym.get<const MemRegion *>()->getMostDerivedObjectRegion();
2074     return State->set<IteratorRegionMap>(Reg, Pos);
2075   } else if (RegOrSym.is<SymbolRef>()) {
2076     return State->set<IteratorSymbolMap>(RegOrSym.get<SymbolRef>(), Pos);
2077   }
2078   return nullptr;
2079 }
2080
2081 ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val) {
2082   if (auto Reg = Val.getAsRegion()) {
2083     Reg = Reg->getMostDerivedObjectRegion();
2084     return State->remove<IteratorRegionMap>(Reg);
2085   } else if (const auto Sym = Val.getAsSymbol()) {
2086     return State->remove<IteratorSymbolMap>(Sym);
2087   } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
2088     return State->remove<IteratorRegionMap>(LCVal->getRegion());
2089   }
2090   return nullptr;
2091 }
2092
2093 ProgramStateRef adjustIteratorPosition(ProgramStateRef State,
2094                                        RegionOrSymbol RegOrSym,
2095                                        const IteratorPosition &Pos,
2096                                        bool Equal) {
2097   if (Equal) {
2098     return setIteratorPosition(State, RegOrSym, Pos);
2099   } else {
2100     return State;
2101   }
2102 }
2103
2104 ProgramStateRef relateIteratorPositions(ProgramStateRef State,
2105                                         const IteratorPosition &Pos1,
2106                                         const IteratorPosition &Pos2,
2107                                         bool Equal) {
2108   auto &SVB = State->getStateManager().getSValBuilder();
2109
2110   // FIXME: This code should be reworked as follows:
2111   // 1. Subtract the operands using evalBinOp().
2112   // 2. Assume that the result doesn't overflow.
2113   // 3. Compare the result to 0.
2114   // 4. Assume the result of the comparison.
2115   const auto comparison =
2116       SVB.evalBinOp(State, BO_EQ, nonloc::SymbolVal(Pos1.getOffset()),
2117                     nonloc::SymbolVal(Pos2.getOffset()),
2118                     SVB.getConditionType());
2119
2120   assert(comparison.getAs<DefinedSVal>() &&
2121     "Symbol comparison must be a `DefinedSVal`");
2122
2123   auto NewState = State->assume(comparison.castAs<DefinedSVal>(), Equal);
2124   if (const auto CompSym = comparison.getAsSymbol()) {
2125     assert(isa<SymIntExpr>(CompSym) &&
2126            "Symbol comparison must be a `SymIntExpr`");
2127     assert(BinaryOperator::isComparisonOp(
2128                cast<SymIntExpr>(CompSym)->getOpcode()) &&
2129            "Symbol comparison must be a comparison");
2130     return assumeNoOverflow(NewState, cast<SymIntExpr>(CompSym)->getLHS(), 2);
2131   }
2132
2133   return NewState;
2134 }
2135
2136 bool hasLiveIterators(ProgramStateRef State, const MemRegion *Cont) {
2137   auto RegionMap = State->get<IteratorRegionMap>();
2138   for (const auto Reg : RegionMap) {
2139     if (Reg.second.getContainer() == Cont)
2140       return true;
2141   }
2142
2143   auto SymbolMap = State->get<IteratorSymbolMap>();
2144   for (const auto Sym : SymbolMap) {
2145     if (Sym.second.getContainer() == Cont)
2146       return true;
2147   }
2148
2149   return false;
2150 }
2151
2152 bool isBoundThroughLazyCompoundVal(const Environment &Env,
2153                                    const MemRegion *Reg) {
2154   for (const auto Binding: Env) {
2155     if (const auto LCVal = Binding.second.getAs<nonloc::LazyCompoundVal>()) {
2156       if (LCVal->getRegion() == Reg)
2157         return true;
2158     }
2159   }
2160
2161   return false;
2162 }
2163
2164 template <typename Condition, typename Process>
2165 ProgramStateRef processIteratorPositions(ProgramStateRef State, Condition Cond,
2166                                          Process Proc) {
2167   auto &RegionMapFactory = State->get_context<IteratorRegionMap>();
2168   auto RegionMap = State->get<IteratorRegionMap>();
2169   bool Changed = false;
2170   for (const auto Reg : RegionMap) {
2171     if (Cond(Reg.second)) {
2172       RegionMap = RegionMapFactory.add(RegionMap, Reg.first, Proc(Reg.second));
2173       Changed = true;
2174     }
2175   }
2176
2177   if (Changed)
2178     State = State->set<IteratorRegionMap>(RegionMap);
2179
2180   auto &SymbolMapFactory = State->get_context<IteratorSymbolMap>();
2181   auto SymbolMap = State->get<IteratorSymbolMap>();
2182   Changed = false;
2183   for (const auto Sym : SymbolMap) {
2184     if (Cond(Sym.second)) {
2185       SymbolMap = SymbolMapFactory.add(SymbolMap, Sym.first, Proc(Sym.second));
2186       Changed = true;
2187     }
2188   }
2189
2190   if (Changed)
2191     State = State->set<IteratorSymbolMap>(SymbolMap);
2192
2193   return State;
2194 }
2195
2196 ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State,
2197                                                const MemRegion *Cont) {
2198   auto MatchCont = [&](const IteratorPosition &Pos) {
2199     return Pos.getContainer() == Cont;
2200   };
2201   auto Invalidate = [&](const IteratorPosition &Pos) {
2202     return Pos.invalidate();
2203   };
2204   return processIteratorPositions(State, MatchCont, Invalidate);
2205 }
2206
2207 ProgramStateRef
2208 invalidateAllIteratorPositionsExcept(ProgramStateRef State,
2209                                      const MemRegion *Cont, SymbolRef Offset,
2210                                      BinaryOperator::Opcode Opc) {
2211   auto MatchContAndCompare = [&](const IteratorPosition &Pos) {
2212     return Pos.getContainer() == Cont &&
2213            !compare(State, Pos.getOffset(), Offset, Opc);
2214   };
2215   auto Invalidate = [&](const IteratorPosition &Pos) {
2216     return Pos.invalidate();
2217   };
2218   return processIteratorPositions(State, MatchContAndCompare, Invalidate);
2219 }
2220
2221 ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
2222                                             SymbolRef Offset,
2223                                             BinaryOperator::Opcode Opc) {
2224   auto Compare = [&](const IteratorPosition &Pos) {
2225     return compare(State, Pos.getOffset(), Offset, Opc);
2226   };
2227   auto Invalidate = [&](const IteratorPosition &Pos) {
2228     return Pos.invalidate();
2229   };
2230   return processIteratorPositions(State, Compare, Invalidate);
2231 }
2232
2233 ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
2234                                             SymbolRef Offset1,
2235                                             BinaryOperator::Opcode Opc1,
2236                                             SymbolRef Offset2,
2237                                             BinaryOperator::Opcode Opc2) {
2238   auto Compare = [&](const IteratorPosition &Pos) {
2239     return compare(State, Pos.getOffset(), Offset1, Opc1) &&
2240            compare(State, Pos.getOffset(), Offset2, Opc2);
2241   };
2242   auto Invalidate = [&](const IteratorPosition &Pos) {
2243     return Pos.invalidate();
2244   };
2245   return processIteratorPositions(State, Compare, Invalidate);
2246 }
2247
2248 ProgramStateRef reassignAllIteratorPositions(ProgramStateRef State,
2249                                              const MemRegion *Cont,
2250                                              const MemRegion *NewCont) {
2251   auto MatchCont = [&](const IteratorPosition &Pos) {
2252     return Pos.getContainer() == Cont;
2253   };
2254   auto ReAssign = [&](const IteratorPosition &Pos) {
2255     return Pos.reAssign(NewCont);
2256   };
2257   return processIteratorPositions(State, MatchCont, ReAssign);
2258 }
2259
2260 ProgramStateRef reassignAllIteratorPositionsUnless(ProgramStateRef State,
2261                                                    const MemRegion *Cont,
2262                                                    const MemRegion *NewCont,
2263                                                    SymbolRef Offset,
2264                                                    BinaryOperator::Opcode Opc) {
2265   auto MatchContAndCompare = [&](const IteratorPosition &Pos) {
2266     return Pos.getContainer() == Cont &&
2267     !compare(State, Pos.getOffset(), Offset, Opc);
2268   };
2269   auto ReAssign = [&](const IteratorPosition &Pos) {
2270     return Pos.reAssign(NewCont);
2271   };
2272   return processIteratorPositions(State, MatchContAndCompare, ReAssign);
2273 }
2274
2275 // This function rebases symbolic expression `OldSym + Int` to `NewSym + Int`,
2276 // `OldSym - Int` to `NewSym - Int` and  `OldSym` to `NewSym` in any iterator
2277 // position offsets where `CondSym` is true.
2278 ProgramStateRef rebaseSymbolInIteratorPositionsIf(
2279     ProgramStateRef State, SValBuilder &SVB, SymbolRef OldSym,
2280     SymbolRef NewSym, SymbolRef CondSym, BinaryOperator::Opcode Opc) {
2281   auto LessThanEnd = [&](const IteratorPosition &Pos) {
2282     return compare(State, Pos.getOffset(), CondSym, Opc);
2283   };
2284   auto RebaseSymbol = [&](const IteratorPosition &Pos) {
2285     return Pos.setTo(rebaseSymbol(State, SVB, Pos.getOffset(), OldSym,
2286                                    NewSym));
2287   };
2288   return processIteratorPositions(State, LessThanEnd, RebaseSymbol);
2289 }
2290
2291 // This function rebases symbolic expression `OldExpr + Int` to `NewExpr + Int`,
2292 // `OldExpr - Int` to `NewExpr - Int` and  `OldExpr` to `NewExpr` in expression
2293 // `OrigExpr`.
2294 SymbolRef rebaseSymbol(ProgramStateRef State, SValBuilder &SVB,
2295                        SymbolRef OrigExpr, SymbolRef OldExpr,
2296                        SymbolRef NewSym) {
2297   auto &SymMgr = SVB.getSymbolManager();
2298   auto Diff = SVB.evalBinOpNN(State, BO_Sub, nonloc::SymbolVal(OrigExpr),
2299                               nonloc::SymbolVal(OldExpr),
2300                               SymMgr.getType(OrigExpr));
2301
2302   const auto DiffInt = Diff.getAs<nonloc::ConcreteInt>();
2303   if (!DiffInt)
2304     return OrigExpr;
2305
2306   return SVB.evalBinOpNN(State, BO_Add, *DiffInt, nonloc::SymbolVal(NewSym),
2307                          SymMgr.getType(OrigExpr)).getAsSymbol();
2308 }
2309
2310 bool isZero(ProgramStateRef State, const NonLoc &Val) {
2311   auto &BVF = State->getBasicVals();
2312   return compare(State, Val,
2313                  nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(0))),
2314                  BO_EQ);
2315 }
2316
2317 bool isPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos) {
2318   const auto *Cont = Pos.getContainer();
2319   const auto *CData = getContainerData(State, Cont);
2320   if (!CData)
2321     return false;
2322
2323   const auto End = CData->getEnd();
2324   if (End) {
2325     if (isEqual(State, Pos.getOffset(), End)) {
2326       return true;
2327     }
2328   }
2329
2330   return false;
2331 }
2332
2333 bool isAheadOfRange(ProgramStateRef State, const IteratorPosition &Pos) {
2334   const auto *Cont = Pos.getContainer();
2335   const auto *CData = getContainerData(State, Cont);
2336   if (!CData)
2337     return false;
2338
2339   const auto Beg = CData->getBegin();
2340   if (Beg) {
2341     if (isLess(State, Pos.getOffset(), Beg)) {
2342       return true;
2343     }
2344   }
2345
2346   return false;
2347 }
2348
2349 bool isBehindPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos) {
2350   const auto *Cont = Pos.getContainer();
2351   const auto *CData = getContainerData(State, Cont);
2352   if (!CData)
2353     return false;
2354
2355   const auto End = CData->getEnd();
2356   if (End) {
2357     if (isGreater(State, Pos.getOffset(), End)) {
2358       return true;
2359     }
2360   }
2361
2362   return false;
2363 }
2364
2365 bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
2366   return compare(State, Sym1, Sym2, BO_LT);
2367 }
2368
2369 bool isGreater(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
2370   return compare(State, Sym1, Sym2, BO_GT);
2371 }
2372
2373 bool isEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
2374   return compare(State, Sym1, Sym2, BO_EQ);
2375 }
2376
2377 bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
2378              BinaryOperator::Opcode Opc) {
2379   return compare(State, nonloc::SymbolVal(Sym1), nonloc::SymbolVal(Sym2), Opc);
2380 }
2381
2382
2383 bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2,
2384              BinaryOperator::Opcode Opc) {
2385   auto &SVB = State->getStateManager().getSValBuilder();
2386
2387   const auto comparison =
2388     SVB.evalBinOp(State, Opc, NL1, NL2, SVB.getConditionType());
2389
2390   assert(comparison.getAs<DefinedSVal>() &&
2391     "Symbol comparison must be a `DefinedSVal`");
2392
2393   return !State->assume(comparison.castAs<DefinedSVal>(), false);
2394 }
2395
2396 } // namespace
2397
2398 #define REGISTER_CHECKER(name)                                                 \
2399   void ento::register##name(CheckerManager &Mgr) {                             \
2400     auto *checker = Mgr.registerChecker<IteratorChecker>();                    \
2401     checker->ChecksEnabled[IteratorChecker::CK_##name] = true;                 \
2402     checker->CheckNames[IteratorChecker::CK_##name] =                          \
2403         Mgr.getCurrentCheckName();                                             \
2404   }
2405
2406 REGISTER_CHECKER(IteratorRangeChecker)
2407 REGISTER_CHECKER(MismatchedIteratorChecker)
2408 REGISTER_CHECKER(InvalidatedIteratorChecker)