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

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