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

   1 //===-- IteratorChecker.cpp ---------------------------------------*- C++ -*--//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // Defines a checker for using iterators outside their range (past end). Usage
  11 // means here dereferencing, incrementing etc.
  12 //
  13 //===----------------------------------------------------------------------===//
  14 //
  15 // In the code, iterator can be represented as a:
  16 // * type-I: typedef-ed pointer. Operations over such iterator, such as
  17 //           comparisons or increments, are modeled straightforwardly by the
  18 //           analyzer.
  19 // * type-II: structure with its method bodies available.  Operations over such
  20 //            iterator are inlined by the analyzer, and results of modeling
  21 //            these operations are exposing implementation details of the
  22 //            iterators, which is not necessarily helping.
  23 // * type-III: completely opaque structure. Operations over such iterator are
  24 //             modeled conservatively, producing conjured symbols everywhere.
  25 //
  26 // To handle all these types in a common way we introduce a structure called
  27 // IteratorPosition which is an abstraction of the position the iterator
  28 // represents using symbolic expressions. The checker handles all the
  29 // operations on this structure.
  30 //
  31 // Additionally, depending on the circumstances, operators of types II and III
  32 // can be represented as:
  33 // * type-IIa, type-IIIa: conjured structure symbols - when returned by value
  34 //                        from conservatively evaluated methods such as
  35 //                        `.begin()`.
  36 // * type-IIb, type-IIIb: memory regions of iterator-typed objects, such as
  37 //                        variables or temporaries, when the iterator object is
  38 //                        currently treated as an lvalue.
  39 // * type-IIc, type-IIIc: compound values of iterator-typed objects, when the
  40 //                        iterator object is treated as an rvalue taken of a
  41 //                        particular lvalue, eg. a copy of "type-a" iterator
  42 //                        object, or an iterator that existed before the
  43 //                        analysis has started.
  44 //
  45 // To handle any of these three different representations stored in an SVal we
  46 // use setter and getters functions which separate the three cases. To store
  47 // them we use a pointer union of symbol and memory region.
  48 //
  49 // The checker works the following way: We record the begin and the
  50 // past-end iterator for all containers whenever their `.begin()` and `.end()`
  51 // are called. Since the Constraint Manager cannot handle such SVals we need
  52 // to take over its role. We post-check equality and non-equality comparisons
  53 // and record that the two sides are equal if we are in the 'equal' branch
  54 // (true-branch for `==` and false-branch for `!=`).
  55 //
  56 // In case of type-I or type-II iterators we get a concrete integer as a result
  57 // of the comparison (1 or 0) but in case of type-III we only get a Symbol. In
  58 // this latter case we record the symbol and reload it in evalAssume() and do
  59 // the propagation there. We also handle (maybe double) negated comparisons
  60 // which are represented in the form of (x == 0 or x != 0) where x is the
  61 // comparison itself.
  62 //
  63 // Since `SimpleConstraintManager` cannot handle complex symbolic expressions
  64 // we only use expressions of the format S, S+n or S-n for iterator positions
  65 // where S is a conjured symbol and n is an unsigned concrete integer. When
  66 // making an assumption e.g. `S1 + n == S2 + m` we store `S1 - S2 == m - n` as
  67 // a constraint which we later retrieve when doing an actual comparison.
  68
  69 #include "ClangSACheckers.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
  75 using namespace clang;
  76 using namespace ento;
  77
  78 namespace {
  79
  80 // Abstract position of an iterator. This helps to handle all three kinds
  81 // of operators in a common way by using a symbolic position.
  82 struct IteratorPosition {
  83 private:
  84
  85   // Container the iterator belongs to
  86   const MemRegion *Cont;
  87
  88   // Abstract offset
  89   const SymbolRef Offset;
  90
  91   IteratorPosition(const MemRegion *C, SymbolRef Of)
  92       : Cont(C), Offset(Of) {}
  93
  94 public:
  95   const MemRegion *getContainer() const { return Cont; }
  96   SymbolRef getOffset() const { return Offset; }
  97
  98   static IteratorPosition getPosition(const MemRegion *C, SymbolRef Of) {
  99     return IteratorPosition(C, Of);
 100   }
 101
 102   IteratorPosition setTo(SymbolRef NewOf) const {
 103     return IteratorPosition(Cont, NewOf);
 104   }
 105
 106   bool operator==(const IteratorPosition &X) const {
 107     return Cont == X.Cont && Offset == X.Offset;
 108   }
 109
 110   bool operator!=(const IteratorPosition &X) const {
 111     return Cont != X.Cont || Offset != X.Offset;
 112   }
 113
 114   void Profile(llvm::FoldingSetNodeID &ID) const {
 115     ID.AddPointer(Cont);
 116     ID.Add(Offset);
 117   }
 118 };
 119
 120 typedef llvm::PointerUnion<const MemRegion *, SymbolRef> RegionOrSymbol;
 121
 122 // Structure to record the symbolic begin and end position of a container
 123 struct ContainerData {
 124 private:
 125   const SymbolRef Begin, End;
 126
 127   ContainerData(SymbolRef B, SymbolRef E) : Begin(B), End(E) {}
 128
 129 public:
 130   static ContainerData fromBegin(SymbolRef B) {
 131     return ContainerData(B, nullptr);
 132   }
 133
 134   static ContainerData fromEnd(SymbolRef E) {
 135     return ContainerData(nullptr, E);
 136   }
 137
 138   SymbolRef getBegin() const { return Begin; }
 139   SymbolRef getEnd() const { return End; }
 140
 141   ContainerData newBegin(SymbolRef B) const { return ContainerData(B, End); }
 142
 143   ContainerData newEnd(SymbolRef E) const { return ContainerData(Begin, E); }
 144
 145   bool operator==(const ContainerData &X) const {
 146     return Begin == X.Begin && End == X.End;
 147   }
 148
 149   bool operator!=(const ContainerData &X) const {
 150     return Begin != X.Begin || End != X.End;
 151   }
 152
 153   void Profile(llvm::FoldingSetNodeID &ID) const {
 154     ID.Add(Begin);
 155     ID.Add(End);
 156   }
 157 };
 158
 159 // Structure fo recording iterator comparisons. We needed to retrieve the
 160 // original comparison expression in assumptions.
 161 struct IteratorComparison {
 162 private:
 163   RegionOrSymbol Left, Right;
 164   bool Equality;
 165
 166 public:
 167   IteratorComparison(RegionOrSymbol L, RegionOrSymbol R, bool Eq)
 168       : Left(L), Right(R), Equality(Eq) {}
 169
 170   RegionOrSymbol getLeft() const { return Left; }
 171   RegionOrSymbol getRight() const { return Right; }
 172   bool isEquality() const { return Equality; }
 173   bool operator==(const IteratorComparison &X) const {
 174     return Left == X.Left && Right == X.Right && Equality == X.Equality;
 175   }
 176   bool operator!=(const IteratorComparison &X) const {
 177     return Left != X.Left || Right != X.Right || Equality != X.Equality;
 178   }
 179   void Profile(llvm::FoldingSetNodeID &ID) const { ID.AddInteger(Equality); }
 180 };
 181
 182 class IteratorChecker
 183     : public Checker<check::PreCall, check::PostCall,
 184                      check::PreStmt<CXXOperatorCallExpr>,
 185                      check::PostStmt<MaterializeTemporaryExpr>,
 186                      check::LiveSymbols, check::DeadSymbols,
 187                      eval::Assume> {
 188
 189   std::unique_ptr<BugType> OutOfRangeBugType;
 190
 191   void handleComparison(CheckerContext &C, const SVal &RetVal, const SVal &LVal,
 192                         const SVal &RVal, OverloadedOperatorKind Op) const;
 193   void verifyDereference(CheckerContext &C, const SVal &Val) const;
 194   void handleIncrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter,
 195                        bool Postfix) const;
 196   void handleDecrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter,
 197                        bool Postfix) const;
 198   void handleRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op,
 199                               const SVal &RetVal, const SVal &LHS,
 200                               const SVal &RHS) const;
 201   void handleBegin(CheckerContext &C, const Expr *CE, const SVal &RetVal,
 202                    const SVal &Cont) const;
 203   void handleEnd(CheckerContext &C, const Expr *CE, const SVal &RetVal,
 204                  const SVal &Cont) const;
 205   void assignToContainer(CheckerContext &C, const Expr *CE, const SVal &RetVal,
 206                          const MemRegion *Cont) const;
 207   void verifyRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op,
 208                               const SVal &RetVal, const SVal &LHS,
 209                               const SVal &RHS) const;
 210   void reportOutOfRangeBug(const StringRef &Message, const SVal &Val,
 211                            CheckerContext &C, ExplodedNode *ErrNode) const;
 212
 213 public:
 214   IteratorChecker();
 215
 216   enum CheckKind {
 217     CK_IteratorRangeChecker,
 218     CK_NumCheckKinds
 219   };
 220
 221   DefaultBool ChecksEnabled[CK_NumCheckKinds];
 222   CheckName CheckNames[CK_NumCheckKinds];
 223
 224   void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
 225   void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
 226   void checkPreStmt(const CXXOperatorCallExpr *COCE, CheckerContext &C) const;
 227   void checkPostStmt(const MaterializeTemporaryExpr *MTE,
 228                      CheckerContext &C) const;
 229   void checkLiveSymbols(ProgramStateRef State, SymbolReaper &SR) const;
 230   void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
 231   ProgramStateRef evalAssume(ProgramStateRef State, SVal Cond,
 232                              bool Assumption) const;
 233 };
 234 } // namespace
 235
 236 REGISTER_MAP_WITH_PROGRAMSTATE(IteratorSymbolMap, SymbolRef, IteratorPosition)
 237 REGISTER_MAP_WITH_PROGRAMSTATE(IteratorRegionMap, const MemRegion *,
 238                                IteratorPosition)
 239
 240 REGISTER_MAP_WITH_PROGRAMSTATE(ContainerMap, const MemRegion *, ContainerData)
 241
 242 REGISTER_MAP_WITH_PROGRAMSTATE(IteratorComparisonMap, const SymExpr *,
 243                                IteratorComparison)
 244
 245 namespace {
 246
 247 bool isIteratorType(const QualType &Type);
 248 bool isIterator(const CXXRecordDecl *CRD);
 249 bool isBeginCall(const FunctionDecl *Func);
 250 bool isEndCall(const FunctionDecl *Func);
 251 bool isSimpleComparisonOperator(OverloadedOperatorKind OK);
 252 bool isDereferenceOperator(OverloadedOperatorKind OK);
 253 bool isIncrementOperator(OverloadedOperatorKind OK);
 254 bool isDecrementOperator(OverloadedOperatorKind OK);
 255 bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK);
 256 BinaryOperator::Opcode getOpcode(const SymExpr *SE);
 257 const RegionOrSymbol getRegionOrSymbol(const SVal &Val);
 258 const ProgramStateRef processComparison(ProgramStateRef State,
 259                                         RegionOrSymbol LVal,
 260                                         RegionOrSymbol RVal, bool Equal);
 261 const ProgramStateRef saveComparison(ProgramStateRef State,
 262                                      const SymExpr *Condition, const SVal &LVal,
 263                                      const SVal &RVal, bool Eq);
 264 const IteratorComparison *loadComparison(ProgramStateRef State,
 265                                          const SymExpr *Condition);
 266 SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont);
 267 SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont);
 268 ProgramStateRef createContainerBegin(ProgramStateRef State,
 269                                      const MemRegion *Cont,
 270                                      const SymbolRef Sym);
 271 ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont,
 272                                    const SymbolRef Sym);
 273 const IteratorPosition *getIteratorPosition(ProgramStateRef State,
 274                                             const SVal &Val);
 275 const IteratorPosition *getIteratorPosition(ProgramStateRef State,
 276                                             RegionOrSymbol RegOrSym);
 277 ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val,
 278                                     const IteratorPosition &Pos);
 279 ProgramStateRef setIteratorPosition(ProgramStateRef State,
 280                                     RegionOrSymbol RegOrSym,
 281                                     const IteratorPosition &Pos);
 282 ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val);
 283 ProgramStateRef adjustIteratorPosition(ProgramStateRef State,
 284                                        RegionOrSymbol RegOrSym,
 285                                        const IteratorPosition &Pos, bool Equal);
 286 ProgramStateRef relateIteratorPositions(ProgramStateRef State,
 287                                         const IteratorPosition &Pos1,
 288                                         const IteratorPosition &Pos2,
 289                                         bool Equal);
 290 const ContainerData *getContainerData(ProgramStateRef State,
 291                                       const MemRegion *Cont);
 292 ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont,
 293                                  const ContainerData &CData);
 294 bool hasLiveIterators(ProgramStateRef State, const MemRegion *Cont);
 295 bool isOutOfRange(ProgramStateRef State, const IteratorPosition &Pos);
 296 bool isZero(ProgramStateRef State, const NonLoc &Val);
 297 } // namespace
 298
 299 IteratorChecker::IteratorChecker() {
 300   OutOfRangeBugType.reset(
 301       new BugType(this, "Iterator out of range", "Misuse of STL APIs"));
 302   OutOfRangeBugType->setSuppressOnSink(true);
 303 }
 304
 305 void IteratorChecker::checkPreCall(const CallEvent &Call,
 306                                    CheckerContext &C) const {
 307   // Check for out of range access
 308   const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
 309   if (!Func)
 310     return;
 311
 312   if (Func->isOverloadedOperator()) {
 313     if (ChecksEnabled[CK_IteratorRangeChecker] &&
 314         isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) {
 315       if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
 316         // Check for out-of-range incrementions and decrementions
 317         if (Call.getNumArgs() >= 1) {
 318           verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(),
 319                                  Call.getReturnValue(),
 320                                  InstCall->getCXXThisVal(), Call.getArgSVal(0));
 321         }
 322       } else {
 323         if (Call.getNumArgs() >= 2) {
 324           verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(),
 325                                  Call.getReturnValue(), Call.getArgSVal(0),
 326                                  Call.getArgSVal(1));
 327         }
 328       }
 329     } else if (ChecksEnabled[CK_IteratorRangeChecker] &&
 330                isDereferenceOperator(Func->getOverloadedOperator())) {
 331       // Check for dereference of out-of-range iterators
 332       if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
 333         verifyDereference(C, InstCall->getCXXThisVal());
 334       } else {
 335         verifyDereference(C, Call.getArgSVal(0));
 336       }
 337     }
 338   }
 339 }
 340
 341 void IteratorChecker::checkPostCall(const CallEvent &Call,
 342                                     CheckerContext &C) const {
 343   // Record new iterator positions and iterator position changes
 344   const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
 345   if (!Func)
 346     return;
 347
 348   if (Func->isOverloadedOperator()) {
 349     const auto Op = Func->getOverloadedOperator();
 350     if (isSimpleComparisonOperator(Op)) {
 351       if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
 352         handleComparison(C, Call.getReturnValue(), InstCall->getCXXThisVal(),
 353                          Call.getArgSVal(0), Op);
 354       } else {
 355         handleComparison(C, Call.getReturnValue(), Call.getArgSVal(0),
 356                          Call.getArgSVal(1), Op);
 357       }
 358     } else if (isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) {
 359       if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
 360         if (Call.getNumArgs() >= 1) {
 361           handleRandomIncrOrDecr(C, Func->getOverloadedOperator(),
 362                                  Call.getReturnValue(),
 363                                  InstCall->getCXXThisVal(), Call.getArgSVal(0));
 364         }
 365       } else {
 366         if (Call.getNumArgs() >= 2) {
 367           handleRandomIncrOrDecr(C, Func->getOverloadedOperator(),
 368                                  Call.getReturnValue(), Call.getArgSVal(0),
 369                                  Call.getArgSVal(1));
 370         }
 371       }
 372     } else if (isIncrementOperator(Func->getOverloadedOperator())) {
 373       if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
 374         handleIncrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(),
 375                         Call.getNumArgs());
 376       } else {
 377         handleIncrement(C, Call.getReturnValue(), Call.getArgSVal(0),
 378                         Call.getNumArgs());
 379       }
 380     } else if (isDecrementOperator(Func->getOverloadedOperator())) {
 381       if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
 382         handleDecrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(),
 383                         Call.getNumArgs());
 384       } else {
 385         handleDecrement(C, Call.getReturnValue(), Call.getArgSVal(0),
 386                         Call.getNumArgs());
 387       }
 388     }
 389   } else {
 390     const auto *OrigExpr = Call.getOriginExpr();
 391     if (!OrigExpr)
 392       return;
 393
 394     if (!isIteratorType(Call.getResultType()))
 395       return;
 396
 397     auto State = C.getState();
 398     // Already bound to container?
 399     if (getIteratorPosition(State, Call.getReturnValue()))
 400       return;
 401
 402     if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
 403       if (isBeginCall(Func)) {
 404         handleBegin(C, OrigExpr, Call.getReturnValue(),
 405                     InstCall->getCXXThisVal());
 406         return;
 407       }
 408       if (isEndCall(Func)) {
 409         handleEnd(C, OrigExpr, Call.getReturnValue(),
 410                   InstCall->getCXXThisVal());
 411         return;
 412       }
 413     }
 414
 415     // Copy-like and move constructors
 416     if (isa<CXXConstructorCall>(&Call) && Call.getNumArgs() == 1) {
 417       if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(0))) {
 418         State = setIteratorPosition(State, Call.getReturnValue(), *Pos);
 419         if (cast<CXXConstructorDecl>(Func)->isMoveConstructor()) {
 420           State = removeIteratorPosition(State, Call.getArgSVal(0));
 421         }
 422         C.addTransition(State);
 423         return;
 424       }
 425     }
 426
 427     // Assumption: if return value is an iterator which is not yet bound to a
 428     //             container, then look for the first iterator argument, and
 429     //             bind the return value to the same container. This approach
 430     //             works for STL algorithms.
 431     // FIXME: Add a more conservative mode
 432     for (unsigned i = 0; i < Call.getNumArgs(); ++i) {
 433       if (isIteratorType(Call.getArgExpr(i)->getType())) {
 434         if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(i))) {
 435           assignToContainer(C, OrigExpr, Call.getReturnValue(),
 436                             Pos->getContainer());
 437           return;
 438         }
 439       }
 440     }
 441   }
 442 }
 443
 444 void IteratorChecker::checkPreStmt(const CXXOperatorCallExpr *COCE,
 445                                    CheckerContext &C) const {
 446   const auto *ThisExpr = COCE->getArg(0);
 447
 448   auto State = C.getState();
 449   const auto *LCtx = C.getLocationContext();
 450
 451   const auto CurrentThis = State->getSVal(ThisExpr, LCtx);
 452   if (const auto *Reg = CurrentThis.getAsRegion()) {
 453     if (!Reg->getAs<CXXTempObjectRegion>())
 454       return;
 455     const auto OldState = C.getPredecessor()->getFirstPred()->getState();
 456     const auto OldThis = OldState->getSVal(ThisExpr, LCtx);
 457     // FIXME: This solution is unreliable. It may happen that another checker
 458     //        subscribes to the pre-statement check of `CXXOperatorCallExpr`
 459     //        and adds a transition before us. The proper fix is to make the
 460     //        CFG provide a `ConstructionContext` for the `CXXOperatorCallExpr`,
 461     //        which would turn the corresponding `CFGStmt` element into a
 462     //        `CFGCXXRecordTypedCall` element, which will allow `ExprEngine` to
 463     //        foresee that the `begin()`/`end()` call constructs the object
 464     //        directly in the temporary region that `CXXOperatorCallExpr` takes
 465     //        as its implicit object argument.
 466     const auto *Pos = getIteratorPosition(OldState, OldThis);
 467     if (!Pos)
 468       return;
 469     State = setIteratorPosition(State, CurrentThis, *Pos);
 470     C.addTransition(State);
 471   }
 472 }
 473
 474 void IteratorChecker::checkPostStmt(const MaterializeTemporaryExpr *MTE,
 475                                     CheckerContext &C) const {
 476   /* Transfer iterator state to temporary objects */
 477   auto State = C.getState();
 478   const auto *Pos =
 479       getIteratorPosition(State, C.getSVal(MTE->GetTemporaryExpr()));
 480   if (!Pos)
 481     return;
 482   State = setIteratorPosition(State, C.getSVal(MTE), *Pos);
 483   C.addTransition(State);
 484 }
 485
 486 void IteratorChecker::checkLiveSymbols(ProgramStateRef State,
 487                                        SymbolReaper &SR) const {
 488   // Keep symbolic expressions of iterator positions, container begins and ends
 489   // alive
 490   auto RegionMap = State->get<IteratorRegionMap>();
 491   for (const auto Reg : RegionMap) {
 492     const auto Offset = Reg.second.getOffset();
 493     for (auto i = Offset->symbol_begin(); i != Offset->symbol_end(); ++i)
 494       if (isa<SymbolData>(*i))
 495         SR.markLive(*i);
 496   }
 497
 498   auto SymbolMap = State->get<IteratorSymbolMap>();
 499   for (const auto Sym : SymbolMap) {
 500     const auto Offset = Sym.second.getOffset();
 501     for (auto i = Offset->symbol_begin(); i != Offset->symbol_end(); ++i)
 502       if (isa<SymbolData>(*i))
 503         SR.markLive(*i);
 504   }
 505
 506   auto ContMap = State->get<ContainerMap>();
 507   for (const auto Cont : ContMap) {
 508     const auto CData = Cont.second;
 509     if (CData.getBegin()) {
 510       SR.markLive(CData.getBegin());
 511     }
 512     if (CData.getEnd()) {
 513       SR.markLive(CData.getEnd());
 514     }
 515   }
 516 }
 517
 518 void IteratorChecker::checkDeadSymbols(SymbolReaper &SR,
 519                                        CheckerContext &C) const {
 520   // Cleanup
 521   auto State = C.getState();
 522
 523   auto RegionMap = State->get<IteratorRegionMap>();
 524   for (const auto Reg : RegionMap) {
 525     if (!SR.isLiveRegion(Reg.first)) {
 526       State = State->remove<IteratorRegionMap>(Reg.first);
 527     }
 528   }
 529
 530   auto SymbolMap = State->get<IteratorSymbolMap>();
 531   for (const auto Sym : SymbolMap) {
 532     if (!SR.isLive(Sym.first)) {
 533       State = State->remove<IteratorSymbolMap>(Sym.first);
 534     }
 535   }
 536
 537   auto ContMap = State->get<ContainerMap>();
 538   for (const auto Cont : ContMap) {
 539     if (!SR.isLiveRegion(Cont.first)) {
 540       // We must keep the container data while it has live iterators to be able
 541       // to compare them to the begin and the end of the container.
 542       if (!hasLiveIterators(State, Cont.first)) {
 543         State = State->remove<ContainerMap>(Cont.first);
 544       }
 545     }
 546   }
 547
 548   auto ComparisonMap = State->get<IteratorComparisonMap>();
 549   for (const auto Comp : ComparisonMap) {
 550     if (!SR.isLive(Comp.first)) {
 551       State = State->remove<IteratorComparisonMap>(Comp.first);
 552     }
 553   }
 554
 555   C.addTransition(State);
 556 }
 557
 558 ProgramStateRef IteratorChecker::evalAssume(ProgramStateRef State, SVal Cond,
 559                                             bool Assumption) const {
 560   // Load recorded comparison and transfer iterator state between sides
 561   // according to comparison operator and assumption
 562   const auto *SE = Cond.getAsSymExpr();
 563   if (!SE)
 564     return State;
 565
 566   auto Opc = getOpcode(SE);
 567   if (Opc != BO_EQ && Opc != BO_NE)
 568     return State;
 569
 570   bool Negated = false;
 571   const auto *Comp = loadComparison(State, SE);
 572   if (!Comp) {
 573     // Try negated comparison, which is a SymExpr to 0 integer comparison
 574     const auto *SIE = dyn_cast<SymIntExpr>(SE);
 575     if (!SIE)
 576       return State;
 577
 578     if (SIE->getRHS() != 0)
 579       return State;
 580
 581     SE = SIE->getLHS();
 582     Negated = SIE->getOpcode() == BO_EQ; // Equal to zero means negation
 583     Opc = getOpcode(SE);
 584     if (Opc != BO_EQ && Opc != BO_NE)
 585       return State;
 586
 587     Comp = loadComparison(State, SE);
 588     if (!Comp)
 589       return State;
 590   }
 591
 592   return processComparison(State, Comp->getLeft(), Comp->getRight(),
 593                            (Comp->isEquality() == Assumption) != Negated);
 594 }
 595
 596 void IteratorChecker::handleComparison(CheckerContext &C, const SVal &RetVal,
 597                                        const SVal &LVal, const SVal &RVal,
 598                                        OverloadedOperatorKind Op) const {
 599   // Record the operands and the operator of the comparison for the next
 600   // evalAssume, if the result is a symbolic expression. If it is a concrete
 601   // value (only one branch is possible), then transfer the state between
 602   // the operands according to the operator and the result
 603   auto State = C.getState();
 604   if (const auto *Condition = RetVal.getAsSymbolicExpression()) {
 605     const auto *LPos = getIteratorPosition(State, LVal);
 606     const auto *RPos = getIteratorPosition(State, RVal);
 607     if (!LPos && !RPos)
 608       return;
 609     State = saveComparison(State, Condition, LVal, RVal, Op == OO_EqualEqual);
 610     C.addTransition(State);
 611   } else if (const auto TruthVal = RetVal.getAs<nonloc::ConcreteInt>()) {
 612     if ((State = processComparison(
 613              State, getRegionOrSymbol(LVal), getRegionOrSymbol(RVal),
 614              (Op == OO_EqualEqual) == (TruthVal->getValue() != 0)))) {
 615       C.addTransition(State);
 616     } else {
 617       C.generateSink(State, C.getPredecessor());
 618     }
 619   }
 620 }
 621
 622 void IteratorChecker::verifyDereference(CheckerContext &C,
 623                                         const SVal &Val) const {
 624   auto State = C.getState();
 625   const auto *Pos = getIteratorPosition(State, Val);
 626   if (Pos && isOutOfRange(State, *Pos)) {
 627     // If I do not put a tag here, some range tests will fail
 628     static CheckerProgramPointTag Tag("IteratorRangeChecker",
 629                                       "IteratorOutOfRange");
 630     auto *N = C.generateNonFatalErrorNode(State, &Tag);
 631     if (!N)
 632       return;
 633     reportOutOfRangeBug("Iterator accessed outside of its range.", Val, C, N);
 634   }
 635 }
 636
 637 void IteratorChecker::handleIncrement(CheckerContext &C, const SVal &RetVal,
 638                                       const SVal &Iter, bool Postfix) const {
 639   // Increment the symbolic expressions which represents the position of the
 640   // iterator
 641   auto State = C.getState();
 642   const auto *Pos = getIteratorPosition(State, Iter);
 643   if (Pos) {
 644     auto &SymMgr = C.getSymbolManager();
 645     auto &BVF = SymMgr.getBasicVals();
 646     auto &SVB = C.getSValBuilder();
 647     const auto OldOffset = Pos->getOffset();
 648     auto NewOffset =
 649       SVB.evalBinOp(State, BO_Add,
 650                     nonloc::SymbolVal(OldOffset),
 651                     nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
 652                     SymMgr.getType(OldOffset)).getAsSymbol();
 653     auto NewPos = Pos->setTo(NewOffset);
 654     State = setIteratorPosition(State, Iter, NewPos);
 655     State = setIteratorPosition(State, RetVal, Postfix ? *Pos : NewPos);
 656     C.addTransition(State);
 657   }
 658 }
 659
 660 void IteratorChecker::handleDecrement(CheckerContext &C, const SVal &RetVal,
 661                                       const SVal &Iter, bool Postfix) const {
 662   // Decrement the symbolic expressions which represents the position of the
 663   // iterator
 664   auto State = C.getState();
 665   const auto *Pos = getIteratorPosition(State, Iter);
 666   if (Pos) {
 667     auto &SymMgr = C.getSymbolManager();
 668     auto &BVF = SymMgr.getBasicVals();
 669     auto &SVB = C.getSValBuilder();
 670     const auto OldOffset = Pos->getOffset();
 671     auto NewOffset =
 672       SVB.evalBinOp(State, BO_Sub,
 673                     nonloc::SymbolVal(OldOffset),
 674                     nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
 675                     SymMgr.getType(OldOffset)).getAsSymbol();
 676     auto NewPos = Pos->setTo(NewOffset);
 677     State = setIteratorPosition(State, Iter, NewPos);
 678     State = setIteratorPosition(State, RetVal, Postfix ? *Pos : NewPos);
 679     C.addTransition(State);
 680   }
 681 }
 682
 683 // This function tells the analyzer's engine that symbols produced by our
 684 // checker, most notably iterator positions, are relatively small.
 685 // A distance between items in the container should not be very large.
 686 // By assuming that it is within around 1/8 of the address space,
 687 // we can help the analyzer perform operations on these symbols
 688 // without being afraid of integer overflows.
 689 // FIXME: Should we provide it as an API, so that all checkers could use it?
 690 static ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym,
 691                                         long Scale) {
 692   SValBuilder &SVB = State->getStateManager().getSValBuilder();
 693   BasicValueFactory &BV = SVB.getBasicValueFactory();
 694
 695   QualType T = Sym->getType();
 696   assert(T->isSignedIntegerOrEnumerationType());
 697   APSIntType AT = BV.getAPSIntType(T);
 698
 699   ProgramStateRef NewState = State;
 700
 701   llvm::APSInt Max = AT.getMaxValue() / AT.getValue(Scale);
 702   SVal IsCappedFromAbove =
 703       SVB.evalBinOpNN(State, BO_LE, nonloc::SymbolVal(Sym),
 704                       nonloc::ConcreteInt(Max), SVB.getConditionType());
 705   if (auto DV = IsCappedFromAbove.getAs<DefinedSVal>()) {
 706     NewState = NewState->assume(*DV, true);
 707     if (!NewState)
 708       return State;
 709   }
 710
 711   llvm::APSInt Min = -Max;
 712   SVal IsCappedFromBelow =
 713       SVB.evalBinOpNN(State, BO_GE, nonloc::SymbolVal(Sym),
 714                       nonloc::ConcreteInt(Min), SVB.getConditionType());
 715   if (auto DV = IsCappedFromBelow.getAs<DefinedSVal>()) {
 716     NewState = NewState->assume(*DV, true);
 717     if (!NewState)
 718       return State;
 719   }
 720
 721   return NewState;
 722 }
 723
 724 void IteratorChecker::handleRandomIncrOrDecr(CheckerContext &C,
 725                                              OverloadedOperatorKind Op,
 726                                              const SVal &RetVal,
 727                                              const SVal &LHS,
 728                                              const SVal &RHS) const {
 729   // Increment or decrement the symbolic expressions which represents the
 730   // position of the iterator
 731   auto State = C.getState();
 732   const auto *Pos = getIteratorPosition(State, LHS);
 733   if (!Pos)
 734     return;
 735
 736   const auto *value = &RHS;
 737   if (auto loc = RHS.getAs<Loc>()) {
 738     const auto val = State->getRawSVal(*loc);
 739     value = &val;
 740   }
 741
 742   auto &SymMgr = C.getSymbolManager();
 743   auto &SVB = C.getSValBuilder();
 744   auto BinOp = (Op == OO_Plus || Op == OO_PlusEqual) ? BO_Add : BO_Sub;
 745   const auto OldOffset = Pos->getOffset();
 746   SymbolRef NewOffset;
 747   if (const auto intValue = value->getAs<nonloc::ConcreteInt>()) {
 748     // For concrete integers we can calculate the new position
 749     NewOffset = SVB.evalBinOp(State, BinOp, nonloc::SymbolVal(OldOffset),
 750                               *intValue,
 751                               SymMgr.getType(OldOffset)).getAsSymbol();
 752   } else {
 753     // For other symbols create a new symbol to keep expressions simple
 754     const auto &LCtx = C.getLocationContext();
 755     NewOffset = SymMgr.conjureSymbol(nullptr, LCtx, SymMgr.getType(OldOffset),
 756                                      C.blockCount());
 757     State = assumeNoOverflow(State, NewOffset, 4);
 758   }
 759   auto NewPos = Pos->setTo(NewOffset);
 760   auto &TgtVal = (Op == OO_PlusEqual || Op == OO_MinusEqual) ? LHS : RetVal;
 761   State = setIteratorPosition(State, TgtVal, NewPos);
 762   C.addTransition(State);
 763 }
 764
 765 void IteratorChecker::verifyRandomIncrOrDecr(CheckerContext &C,
 766                                              OverloadedOperatorKind Op,
 767                                              const SVal &RetVal,
 768                                              const SVal &LHS,
 769                                              const SVal &RHS) const {
 770   auto State = C.getState();
 771
 772   // If the iterator is initially inside its range, then the operation is valid
 773   const auto *Pos = getIteratorPosition(State, LHS);
 774   if (!Pos || !isOutOfRange(State, *Pos))
 775     return;
 776
 777   auto value = RHS;
 778   if (auto loc = RHS.getAs<Loc>()) {
 779     value = State->getRawSVal(*loc);
 780   }
 781
 782   // Incremention or decremention by 0 is never bug
 783   if (isZero(State, value.castAs<NonLoc>()))
 784     return;
 785
 786   auto &SymMgr = C.getSymbolManager();
 787   auto &SVB = C.getSValBuilder();
 788   auto BinOp = (Op == OO_Plus || Op == OO_PlusEqual) ? BO_Add : BO_Sub;
 789   const auto OldOffset = Pos->getOffset();
 790   const auto intValue = value.getAs<nonloc::ConcreteInt>();
 791   if (!intValue)
 792     return;
 793
 794   auto NewOffset = SVB.evalBinOp(State, BinOp, nonloc::SymbolVal(OldOffset),
 795                                  *intValue,
 796                                  SymMgr.getType(OldOffset)).getAsSymbol();
 797   auto NewPos = Pos->setTo(NewOffset);
 798
 799   // If out of range, the only valid operation is to step into the range
 800   if (isOutOfRange(State, NewPos)) {
 801     auto *N = C.generateNonFatalErrorNode(State);
 802     if (!N)
 803       return;
 804     reportOutOfRangeBug("Iterator accessed past its end.", LHS, C, N);
 805   }
 806 }
 807
 808 void IteratorChecker::handleBegin(CheckerContext &C, const Expr *CE,
 809                                   const SVal &RetVal, const SVal &Cont) const {
 810   const auto *ContReg = Cont.getAsRegion();
 811   if (!ContReg)
 812     return;
 813
 814   while (const auto *CBOR = ContReg->getAs<CXXBaseObjectRegion>()) {
 815     ContReg = CBOR->getSuperRegion();
 816   }
 817
 818   // If the container already has a begin symbol then use it. Otherwise first
 819   // create a new one.
 820   auto State = C.getState();
 821   auto BeginSym = getContainerBegin(State, ContReg);
 822   if (!BeginSym) {
 823     auto &SymMgr = C.getSymbolManager();
 824     BeginSym = SymMgr.conjureSymbol(CE, C.getLocationContext(),
 825                                     C.getASTContext().LongTy, C.blockCount());
 826     State = assumeNoOverflow(State, BeginSym, 4);
 827     State = createContainerBegin(State, ContReg, BeginSym);
 828   }
 829   State = setIteratorPosition(State, RetVal,
 830                               IteratorPosition::getPosition(ContReg, BeginSym));
 831   C.addTransition(State);
 832 }
 833
 834 void IteratorChecker::handleEnd(CheckerContext &C, const Expr *CE,
 835                                 const SVal &RetVal, const SVal &Cont) const {
 836   const auto *ContReg = Cont.getAsRegion();
 837   if (!ContReg)
 838     return;
 839
 840   while (const auto *CBOR = ContReg->getAs<CXXBaseObjectRegion>()) {
 841     ContReg = CBOR->getSuperRegion();
 842   }
 843
 844   // If the container already has an end symbol then use it. Otherwise first
 845   // create a new one.
 846   auto State = C.getState();
 847   auto EndSym = getContainerEnd(State, ContReg);
 848   if (!EndSym) {
 849     auto &SymMgr = C.getSymbolManager();
 850     EndSym = SymMgr.conjureSymbol(CE, C.getLocationContext(),
 851                                   C.getASTContext().LongTy, C.blockCount());
 852     State = assumeNoOverflow(State, EndSym, 4);
 853     State = createContainerEnd(State, ContReg, EndSym);
 854   }
 855   State = setIteratorPosition(State, RetVal,
 856                               IteratorPosition::getPosition(ContReg, EndSym));
 857   C.addTransition(State);
 858 }
 859
 860 void IteratorChecker::assignToContainer(CheckerContext &C, const Expr *CE,
 861                                         const SVal &RetVal,
 862                                         const MemRegion *Cont) const {
 863   while (const auto *CBOR = Cont->getAs<CXXBaseObjectRegion>()) {
 864     Cont = CBOR->getSuperRegion();
 865   }
 866
 867   auto State = C.getState();
 868   auto &SymMgr = C.getSymbolManager();
 869   auto Sym = SymMgr.conjureSymbol(CE, C.getLocationContext(),
 870                                   C.getASTContext().LongTy, C.blockCount());
 871   State = assumeNoOverflow(State, Sym, 4);
 872   State = setIteratorPosition(State, RetVal,
 873                               IteratorPosition::getPosition(Cont, Sym));
 874   C.addTransition(State);
 875 }
 876
 877 void IteratorChecker::reportOutOfRangeBug(const StringRef &Message,
 878                                           const SVal &Val, CheckerContext &C,
 879                                           ExplodedNode *ErrNode) const {
 880   auto R = llvm::make_unique<BugReport>(*OutOfRangeBugType, Message, ErrNode);
 881   R->markInteresting(Val);
 882   C.emitReport(std::move(R));
 883 }
 884
 885 namespace {
 886
 887 bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
 888 bool isGreaterOrEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
 889 bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
 890              BinaryOperator::Opcode Opc);
 891 bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2,
 892              BinaryOperator::Opcode Opc);
 893
 894 bool isIteratorType(const QualType &Type) {
 895   if (Type->isPointerType())
 896     return true;
 897
 898   const auto *CRD = Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl();
 899   return isIterator(CRD);
 900 }
 901
 902 bool isIterator(const CXXRecordDecl *CRD) {
 903   if (!CRD)
 904     return false;
 905
 906   const auto Name = CRD->getName();
 907   if (!(Name.endswith_lower("iterator") || Name.endswith_lower("iter") ||
 908         Name.endswith_lower("it")))
 909     return false;
 910
 911   bool HasCopyCtor = false, HasCopyAssign = true, HasDtor = false,
 912        HasPreIncrOp = false, HasPostIncrOp = false, HasDerefOp = false;
 913   for (const auto *Method : CRD->methods()) {
 914     if (const auto *Ctor = dyn_cast<CXXConstructorDecl>(Method)) {
 915       if (Ctor->isCopyConstructor()) {
 916         HasCopyCtor = !Ctor->isDeleted() && Ctor->getAccess() == AS_public;
 917       }
 918       continue;
 919     }
 920     if (const auto *Dtor = dyn_cast<CXXDestructorDecl>(Method)) {
 921       HasDtor = !Dtor->isDeleted() && Dtor->getAccess() == AS_public;
 922       continue;
 923     }
 924     if (Method->isCopyAssignmentOperator()) {
 925       HasCopyAssign = !Method->isDeleted() && Method->getAccess() == AS_public;
 926       continue;
 927     }
 928     if (!Method->isOverloadedOperator())
 929       continue;
 930     const auto OPK = Method->getOverloadedOperator();
 931     if (OPK == OO_PlusPlus) {
 932       HasPreIncrOp = HasPreIncrOp || (Method->getNumParams() == 0);
 933       HasPostIncrOp = HasPostIncrOp || (Method->getNumParams() == 1);
 934       continue;
 935     }
 936     if (OPK == OO_Star) {
 937       HasDerefOp = (Method->getNumParams() == 0);
 938       continue;
 939     }
 940   }
 941
 942   return HasCopyCtor && HasCopyAssign && HasDtor && HasPreIncrOp &&
 943          HasPostIncrOp && HasDerefOp;
 944 }
 945
 946 bool isBeginCall(const FunctionDecl *Func) {
 947   const auto *IdInfo = Func->getIdentifier();
 948   if (!IdInfo)
 949     return false;
 950   return IdInfo->getName().endswith_lower("begin");
 951 }
 952
 953 bool isEndCall(const FunctionDecl *Func) {
 954   const auto *IdInfo = Func->getIdentifier();
 955   if (!IdInfo)
 956     return false;
 957   return IdInfo->getName().endswith_lower("end");
 958 }
 959
 960 bool isSimpleComparisonOperator(OverloadedOperatorKind OK) {
 961   return OK == OO_EqualEqual || OK == OO_ExclaimEqual;
 962 }
 963
 964 bool isDereferenceOperator(OverloadedOperatorKind OK) {
 965   return OK == OO_Star || OK == OO_Arrow || OK == OO_ArrowStar ||
 966          OK == OO_Subscript;
 967 }
 968
 969 bool isIncrementOperator(OverloadedOperatorKind OK) {
 970   return OK == OO_PlusPlus;
 971 }
 972
 973 bool isDecrementOperator(OverloadedOperatorKind OK) {
 974   return OK == OO_MinusMinus;
 975 }
 976
 977 bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK) {
 978   return OK == OO_Plus || OK == OO_PlusEqual || OK == OO_Minus ||
 979          OK == OO_MinusEqual;
 980 }
 981
 982 BinaryOperator::Opcode getOpcode(const SymExpr *SE) {
 983   if (const auto *BSE = dyn_cast<BinarySymExpr>(SE)) {
 984     return BSE->getOpcode();
 985   } else if (const auto *SC = dyn_cast<SymbolConjured>(SE)) {
 986     const auto *COE = dyn_cast_or_null<CXXOperatorCallExpr>(SC->getStmt());
 987     if (!COE)
 988       return BO_Comma; // Extremal value, neither EQ nor NE
 989     if (COE->getOperator() == OO_EqualEqual) {
 990       return BO_EQ;
 991     } else if (COE->getOperator() == OO_ExclaimEqual) {
 992       return BO_NE;
 993     }
 994     return BO_Comma; // Extremal value, neither EQ nor NE
 995   }
 996   return BO_Comma; // Extremal value, neither EQ nor NE
 997 }
 998
 999 const RegionOrSymbol getRegionOrSymbol(const SVal &Val) {
1000   if (const auto Reg = Val.getAsRegion()) {
1001     return Reg;
1002   } else if (const auto Sym = Val.getAsSymbol()) {
1003     return Sym;
1004   } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
1005     return LCVal->getRegion();
1006   }
1007   return RegionOrSymbol();
1008 }
1009
1010 const ProgramStateRef processComparison(ProgramStateRef State,
1011                                         RegionOrSymbol LVal,
1012                                         RegionOrSymbol RVal, bool Equal) {
1013   const auto *LPos = getIteratorPosition(State, LVal);
1014   const auto *RPos = getIteratorPosition(State, RVal);
1015   if (LPos && !RPos) {
1016     State = adjustIteratorPosition(State, RVal, *LPos, Equal);
1017   } else if (!LPos && RPos) {
1018     State = adjustIteratorPosition(State, LVal, *RPos, Equal);
1019   } else if (LPos && RPos) {
1020     State = relateIteratorPositions(State, *LPos, *RPos, Equal);
1021   }
1022   return State;
1023 }
1024
1025 const ProgramStateRef saveComparison(ProgramStateRef State,
1026                                      const SymExpr *Condition, const SVal &LVal,
1027                                      const SVal &RVal, bool Eq) {
1028   const auto Left = getRegionOrSymbol(LVal);
1029   const auto Right = getRegionOrSymbol(RVal);
1030   if (!Left || !Right)
1031     return State;
1032   return State->set<IteratorComparisonMap>(Condition,
1033                                            IteratorComparison(Left, Right, Eq));
1034 }
1035
1036 const IteratorComparison *loadComparison(ProgramStateRef State,
1037                                          const SymExpr *Condition) {
1038   return State->get<IteratorComparisonMap>(Condition);
1039 }
1040
1041 SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont) {
1042   const auto *CDataPtr = getContainerData(State, Cont);
1043   if (!CDataPtr)
1044     return nullptr;
1045
1046   return CDataPtr->getBegin();
1047 }
1048
1049 SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont) {
1050   const auto *CDataPtr = getContainerData(State, Cont);
1051   if (!CDataPtr)
1052     return nullptr;
1053
1054   return CDataPtr->getEnd();
1055 }
1056
1057 ProgramStateRef createContainerBegin(ProgramStateRef State,
1058                                      const MemRegion *Cont,
1059                                      const SymbolRef Sym) {
1060   // Only create if it does not exist
1061   const auto *CDataPtr = getContainerData(State, Cont);
1062   if (CDataPtr) {
1063     if (CDataPtr->getBegin()) {
1064       return State;
1065     }
1066     const auto CData = CDataPtr->newBegin(Sym);
1067     return setContainerData(State, Cont, CData);
1068   }
1069   const auto CData = ContainerData::fromBegin(Sym);
1070   return setContainerData(State, Cont, CData);
1071 }
1072
1073 ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont,
1074                                    const SymbolRef Sym) {
1075   // Only create if it does not exist
1076   const auto *CDataPtr = getContainerData(State, Cont);
1077   if (CDataPtr) {
1078     if (CDataPtr->getEnd()) {
1079       return State;
1080     }
1081     const auto CData = CDataPtr->newEnd(Sym);
1082     return setContainerData(State, Cont, CData);
1083   }
1084   const auto CData = ContainerData::fromEnd(Sym);
1085   return setContainerData(State, Cont, CData);
1086 }
1087
1088 const ContainerData *getContainerData(ProgramStateRef State,
1089                                       const MemRegion *Cont) {
1090   return State->get<ContainerMap>(Cont);
1091 }
1092
1093 ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont,
1094                                  const ContainerData &CData) {
1095   return State->set<ContainerMap>(Cont, CData);
1096 }
1097
1098 const IteratorPosition *getIteratorPosition(ProgramStateRef State,
1099                                             const SVal &Val) {
1100   if (const auto Reg = Val.getAsRegion()) {
1101     return State->get<IteratorRegionMap>(Reg);
1102   } else if (const auto Sym = Val.getAsSymbol()) {
1103     return State->get<IteratorSymbolMap>(Sym);
1104   } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
1105     return State->get<IteratorRegionMap>(LCVal->getRegion());
1106   }
1107   return nullptr;
1108 }
1109
1110 const IteratorPosition *getIteratorPosition(ProgramStateRef State,
1111                                             RegionOrSymbol RegOrSym) {
1112   if (RegOrSym.is<const MemRegion *>()) {
1113     return State->get<IteratorRegionMap>(RegOrSym.get<const MemRegion *>());
1114   } else if (RegOrSym.is<SymbolRef>()) {
1115     return State->get<IteratorSymbolMap>(RegOrSym.get<SymbolRef>());
1116   }
1117   return nullptr;
1118 }
1119
1120 ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val,
1121                                     const IteratorPosition &Pos) {
1122   if (const auto Reg = Val.getAsRegion()) {
1123     return State->set<IteratorRegionMap>(Reg, Pos);
1124   } else if (const auto Sym = Val.getAsSymbol()) {
1125     return State->set<IteratorSymbolMap>(Sym, Pos);
1126   } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
1127     return State->set<IteratorRegionMap>(LCVal->getRegion(), Pos);
1128   }
1129   return nullptr;
1130 }
1131
1132 ProgramStateRef setIteratorPosition(ProgramStateRef State,
1133                                     RegionOrSymbol RegOrSym,
1134                                     const IteratorPosition &Pos) {
1135   if (RegOrSym.is<const MemRegion *>()) {
1136     return State->set<IteratorRegionMap>(RegOrSym.get<const MemRegion *>(),
1137                                          Pos);
1138   } else if (RegOrSym.is<SymbolRef>()) {
1139     return State->set<IteratorSymbolMap>(RegOrSym.get<SymbolRef>(), Pos);
1140   }
1141   return nullptr;
1142 }
1143
1144 ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val) {
1145   if (const auto Reg = Val.getAsRegion()) {
1146     return State->remove<IteratorRegionMap>(Reg);
1147   } else if (const auto Sym = Val.getAsSymbol()) {
1148     return State->remove<IteratorSymbolMap>(Sym);
1149   } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
1150     return State->remove<IteratorRegionMap>(LCVal->getRegion());
1151   }
1152   return nullptr;
1153 }
1154
1155 ProgramStateRef adjustIteratorPosition(ProgramStateRef State,
1156                                        RegionOrSymbol RegOrSym,
1157                                        const IteratorPosition &Pos,
1158                                        bool Equal) {
1159   if (Equal) {
1160     return setIteratorPosition(State, RegOrSym, Pos);
1161   } else {
1162     return State;
1163   }
1164 }
1165
1166 ProgramStateRef relateIteratorPositions(ProgramStateRef State,
1167                                         const IteratorPosition &Pos1,
1168                                         const IteratorPosition &Pos2,
1169                                         bool Equal) {
1170   auto &SVB = State->getStateManager().getSValBuilder();
1171
1172   // FIXME: This code should be reworked as follows:
1173   // 1. Subtract the operands using evalBinOp().
1174   // 2. Assume that the result doesn't overflow.
1175   // 3. Compare the result to 0.
1176   // 4. Assume the result of the comparison.
1177   const auto comparison =
1178       SVB.evalBinOp(State, BO_EQ, nonloc::SymbolVal(Pos1.getOffset()),
1179                     nonloc::SymbolVal(Pos2.getOffset()),
1180                     SVB.getConditionType());
1181
1182   assert(comparison.getAs<DefinedSVal>() &&
1183     "Symbol comparison must be a `DefinedSVal`");
1184
1185   auto NewState = State->assume(comparison.castAs<DefinedSVal>(), Equal);
1186   if (const auto CompSym = comparison.getAsSymbol()) {
1187     assert(isa<SymIntExpr>(CompSym) &&
1188            "Symbol comparison must be a `SymIntExpr`");
1189     assert(BinaryOperator::isComparisonOp(
1190                cast<SymIntExpr>(CompSym)->getOpcode()) &&
1191            "Symbol comparison must be a comparison");
1192     return assumeNoOverflow(NewState, cast<SymIntExpr>(CompSym)->getLHS(), 2);
1193   }
1194
1195   return NewState;
1196 }
1197
1198 bool hasLiveIterators(ProgramStateRef State, const MemRegion *Cont) {
1199   auto RegionMap = State->get<IteratorRegionMap>();
1200   for (const auto Reg : RegionMap) {
1201     if (Reg.second.getContainer() == Cont)
1202       return true;
1203   }
1204
1205   auto SymbolMap = State->get<IteratorSymbolMap>();
1206   for (const auto Sym : SymbolMap) {
1207     if (Sym.second.getContainer() == Cont)
1208       return true;
1209   }
1210
1211   return false;
1212 }
1213
1214 bool isZero(ProgramStateRef State, const NonLoc &Val) {
1215   auto &BVF = State->getBasicVals();
1216   return compare(State, Val,
1217                  nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(0))),
1218                  BO_EQ);
1219 }
1220
1221 bool isOutOfRange(ProgramStateRef State, const IteratorPosition &Pos) {
1222   const auto *Cont = Pos.getContainer();
1223   const auto *CData = getContainerData(State, Cont);
1224   if (!CData)
1225     return false;
1226
1227   // Out of range means less than the begin symbol or greater or equal to the
1228   // end symbol.
1229
1230   const auto Beg = CData->getBegin();
1231   if (Beg) {
1232     if (isLess(State, Pos.getOffset(), Beg)) {
1233       return true;
1234     }
1235   }
1236
1237   const auto End = CData->getEnd();
1238   if (End) {
1239     if (isGreaterOrEqual(State, Pos.getOffset(), End)) {
1240       return true;
1241     }
1242   }
1243
1244   return false;
1245 }
1246
1247 bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
1248   return compare(State, Sym1, Sym2, BO_LT);
1249 }
1250
1251 bool isGreaterOrEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
1252   return compare(State, Sym1, Sym2, BO_GE);
1253 }
1254
1255 bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
1256              BinaryOperator::Opcode Opc) {
1257   return compare(State, nonloc::SymbolVal(Sym1), nonloc::SymbolVal(Sym2), Opc);
1258 }
1259
1260 bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2,
1261              BinaryOperator::Opcode Opc) {
1262   auto &SVB = State->getStateManager().getSValBuilder();
1263
1264   const auto comparison =
1265     SVB.evalBinOp(State, Opc, NL1, NL2, SVB.getConditionType());
1266
1267   assert(comparison.getAs<DefinedSVal>() &&
1268     "Symbol comparison must be a `DefinedSVal`");
1269
1270   return !State->assume(comparison.castAs<DefinedSVal>(), false);
1271 }
1272
1273 } // namespace
1274
1275 #define REGISTER_CHECKER(name)                                                 \
1276   void ento::register##name(CheckerManager &Mgr) {                             \
1277     auto *checker = Mgr.registerChecker<IteratorChecker>();                    \
1278     checker->ChecksEnabled[IteratorChecker::CK_##name] = true;                 \
1279     checker->CheckNames[IteratorChecker::CK_##name] =                          \
1280         Mgr.getCurrentCheckName();                                             \
1281   }
1282
1283 REGISTER_CHECKER(IteratorRangeChecker)
1284