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