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 past-end iterator for
  50 // all containers whenever their `.end()` is called. Since the Constraint
  51 // Manager cannot handle SVals we need to take over its role. We post-check
  52 // equality and non-equality comparisons and propagate the position of the
  53 // iterator to the other side of the comparison if it is past-end and we are in
  54 // the 'equal' branch (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 #include "ClangSACheckers.h"
  64 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
  65 #include "clang/StaticAnalyzer/Core/Checker.h"
  66 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
  67 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
  68
  69 using namespace clang;
  70 using namespace ento;
  71
  72 namespace {
  73
  74 // Abstract position of an iterator. This helps to handle all three kinds
  75 // of operators in a common way by using a symbolic position.
  76 struct IteratorPosition {
  77 private:
  78
  79   // Container the iterator belongs to
  80   const MemRegion *Cont;
  81
  82   // Abstract offset
  83   SymbolRef Offset;
  84
  85   IteratorPosition(const MemRegion *C, SymbolRef Of)
  86       : Cont(C), Offset(Of) {}
  87
  88 public:
  89   const MemRegion *getContainer() const { return Cont; }
  90   SymbolRef getOffset() const { return Offset; }
  91
  92   static IteratorPosition getPosition(const MemRegion *C, SymbolRef Of) {
  93     return IteratorPosition(C, Of);
  94   }
  95
  96   IteratorPosition setTo(SymbolRef NewOf) const {
  97     return IteratorPosition(Cont, NewOf);
  98   }
  99
 100   bool operator==(const IteratorPosition &X) const {
 101     return Cont == X.Cont && Offset == X.Offset;
 102   }
 103
 104   bool operator!=(const IteratorPosition &X) const {
 105     return Cont != X.Cont || Offset != X.Offset;
 106   }
 107
 108   void Profile(llvm::FoldingSetNodeID &ID) const {
 109     ID.AddPointer(Cont);
 110     ID.Add(Offset);
 111   }
 112 };
 113
 114 typedef llvm::PointerUnion<const MemRegion *, SymbolRef> RegionOrSymbol;
 115
 116 // Structure to record the symbolic end position of a container
 117 struct ContainerData {
 118 private:
 119   SymbolRef End;
 120
 121   ContainerData(SymbolRef E) : End(E) {}
 122
 123 public:
 124   static ContainerData fromEnd(SymbolRef E) {
 125     return ContainerData(E);
 126   }
 127
 128   SymbolRef getEnd() const { return End; }
 129
 130   ContainerData newEnd(SymbolRef E) const { return ContainerData(E); }
 131
 132   bool operator==(const ContainerData &X) const {
 133     return End == X.End;
 134   }
 135
 136   bool operator!=(const ContainerData &X) const {
 137     return End != X.End;
 138   }
 139
 140   void Profile(llvm::FoldingSetNodeID &ID) const {
 141     ID.Add(End);
 142   }
 143 };
 144
 145 // Structure fo recording iterator comparisons. We needed to retrieve the
 146 // original comparison expression in assumptions.
 147 struct IteratorComparison {
 148 private:
 149   RegionOrSymbol Left, Right;
 150   bool Equality;
 151
 152 public:
 153   IteratorComparison(RegionOrSymbol L, RegionOrSymbol R, bool Eq)
 154       : Left(L), Right(R), Equality(Eq) {}
 155
 156   RegionOrSymbol getLeft() const { return Left; }
 157   RegionOrSymbol getRight() const { return Right; }
 158   bool isEquality() const { return Equality; }
 159   bool operator==(const IteratorComparison &X) const {
 160     return Left == X.Left && Right == X.Right && Equality == X.Equality;
 161   }
 162   bool operator!=(const IteratorComparison &X) const {
 163     return Left != X.Left || Right != X.Right || Equality != X.Equality;
 164   }
 165   void Profile(llvm::FoldingSetNodeID &ID) const { ID.AddInteger(Equality); }
 166 };
 167
 168 class IteratorChecker
 169     : public Checker<check::PreCall, check::PostCall,
 170                      check::PostStmt<MaterializeTemporaryExpr>,
 171                      check::DeadSymbols,
 172                      eval::Assume> {
 173
 174   std::unique_ptr<BugType> OutOfRangeBugType;
 175
 176   void handleComparison(CheckerContext &C, const SVal &RetVal, const SVal &LVal,
 177                         const SVal &RVal, OverloadedOperatorKind Op) const;
 178   void verifyDereference(CheckerContext &C, const SVal &Val) const;
 179   void handleEnd(CheckerContext &C, const Expr *CE, const SVal &RetVal,
 180                  const SVal &Cont) const;
 181   void assignToContainer(CheckerContext &C, const Expr *CE, const SVal &RetVal,
 182                          const MemRegion *Cont) const;
 183   void reportOutOfRangeBug(const StringRef &Message, const SVal &Val,
 184                            CheckerContext &C, ExplodedNode *ErrNode) const;
 185
 186 public:
 187   IteratorChecker();
 188
 189   enum CheckKind {
 190     CK_IteratorRangeChecker,
 191     CK_NumCheckKinds
 192   };
 193
 194   DefaultBool ChecksEnabled[CK_NumCheckKinds];
 195   CheckName CheckNames[CK_NumCheckKinds];
 196
 197   void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
 198   void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
 199   void checkPostStmt(const MaterializeTemporaryExpr *MTE,
 200                      CheckerContext &C) const;
 201   void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
 202   ProgramStateRef evalAssume(ProgramStateRef State, SVal Cond,
 203                              bool Assumption) const;
 204 };
 205 } // namespace
 206
 207 REGISTER_MAP_WITH_PROGRAMSTATE(IteratorSymbolMap, SymbolRef, IteratorPosition)
 208 REGISTER_MAP_WITH_PROGRAMSTATE(IteratorRegionMap, const MemRegion *,
 209                                IteratorPosition)
 210
 211 REGISTER_MAP_WITH_PROGRAMSTATE(ContainerMap, const MemRegion *, ContainerData)
 212
 213 REGISTER_MAP_WITH_PROGRAMSTATE(IteratorComparisonMap, const SymExpr *,
 214                                IteratorComparison)
 215
 216 namespace {
 217
 218 bool isIteratorType(const QualType &Type);
 219 bool isIterator(const CXXRecordDecl *CRD);
 220 bool isEndCall(const FunctionDecl *Func);
 221 bool isSimpleComparisonOperator(OverloadedOperatorKind OK);
 222 bool isDereferenceOperator(OverloadedOperatorKind OK);
 223 BinaryOperator::Opcode getOpcode(const SymExpr *SE);
 224 const RegionOrSymbol getRegionOrSymbol(const SVal &Val);
 225 const ProgramStateRef processComparison(ProgramStateRef State,
 226                                         RegionOrSymbol LVal,
 227                                         RegionOrSymbol RVal, bool Equal);
 228 const ProgramStateRef saveComparison(ProgramStateRef State,
 229                                      const SymExpr *Condition, const SVal &LVal,
 230                                      const SVal &RVal, bool Eq);
 231 const IteratorComparison *loadComparison(ProgramStateRef State,
 232                                          const SymExpr *Condition);
 233 SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont);
 234 ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont,
 235                                    const SymbolRef Sym);
 236 const IteratorPosition *getIteratorPosition(ProgramStateRef State,
 237                                             const SVal &Val);
 238 const IteratorPosition *getIteratorPosition(ProgramStateRef State,
 239                                             RegionOrSymbol RegOrSym);
 240 ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val,
 241                                     const IteratorPosition &Pos);
 242 ProgramStateRef setIteratorPosition(ProgramStateRef State,
 243                                     RegionOrSymbol RegOrSym,
 244                                     const IteratorPosition &Pos);
 245 ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val);
 246 ProgramStateRef adjustIteratorPosition(ProgramStateRef State,
 247                                        RegionOrSymbol RegOrSym,
 248                                        const IteratorPosition &Pos, bool Equal);
 249 ProgramStateRef relateIteratorPositions(ProgramStateRef State,
 250                                         const IteratorPosition &Pos1,
 251                                         const IteratorPosition &Pos2,
 252                                         bool Equal);
 253 const ContainerData *getContainerData(ProgramStateRef State,
 254                                       const MemRegion *Cont);
 255 ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont,
 256                                  const ContainerData &CData);
 257 bool isOutOfRange(ProgramStateRef State, const IteratorPosition &Pos);
 258 } // namespace
 259
 260 IteratorChecker::IteratorChecker() {
 261   OutOfRangeBugType.reset(
 262       new BugType(this, "Iterator out of range", "Misuse of STL APIs"));
 263   OutOfRangeBugType->setSuppressOnSink(true);
 264 }
 265
 266 void IteratorChecker::checkPreCall(const CallEvent &Call,
 267                                    CheckerContext &C) const {
 268   // Check for out of range access
 269   const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
 270   if (!Func)
 271     return;
 272
 273   if (Func->isOverloadedOperator()) {
 274     if (ChecksEnabled[CK_IteratorRangeChecker] &&
 275                isDereferenceOperator(Func->getOverloadedOperator())) {
 276       // Check for dereference of out-of-range iterators
 277       if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
 278         verifyDereference(C, InstCall->getCXXThisVal());
 279       } else {
 280         verifyDereference(C, Call.getArgSVal(0));
 281       }
 282     }
 283   }
 284 }
 285
 286 void IteratorChecker::checkPostCall(const CallEvent &Call,
 287                                     CheckerContext &C) const {
 288   // Record new iterator positions and iterator position changes
 289   const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
 290   if (!Func)
 291     return;
 292
 293   if (Func->isOverloadedOperator()) {
 294     const auto Op = Func->getOverloadedOperator();
 295     if (isSimpleComparisonOperator(Op)) {
 296       if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
 297         handleComparison(C, Call.getReturnValue(), InstCall->getCXXThisVal(),
 298                          Call.getArgSVal(0), Op);
 299       } else {
 300         handleComparison(C, Call.getReturnValue(), Call.getArgSVal(0),
 301                          Call.getArgSVal(1), Op);
 302       }
 303     }
 304   } else {
 305     const auto *OrigExpr = Call.getOriginExpr();
 306     if (!OrigExpr)
 307       return;
 308
 309     if (!isIteratorType(Call.getResultType()))
 310       return;
 311
 312     auto State = C.getState();
 313     // Already bound to container?
 314     if (getIteratorPosition(State, Call.getReturnValue()))
 315       return;
 316
 317     if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
 318       if (isEndCall(Func)) {
 319         handleEnd(C, OrigExpr, Call.getReturnValue(),
 320                   InstCall->getCXXThisVal());
 321         return;
 322       }
 323     }
 324
 325     // Copy-like and move constructors
 326     if (isa<CXXConstructorCall>(&Call) && Call.getNumArgs() == 1) {
 327       if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(0))) {
 328         State = setIteratorPosition(State, Call.getReturnValue(), *Pos);
 329         if (cast<CXXConstructorDecl>(Func)->isMoveConstructor()) {
 330           State = removeIteratorPosition(State, Call.getArgSVal(0));
 331         }
 332         C.addTransition(State);
 333         return;
 334       }
 335     }
 336
 337     // Assumption: if return value is an iterator which is not yet bound to a
 338     //             container, then look for the first iterator argument, and
 339     //             bind the return value to the same container. This approach
 340     //             works for STL algorithms.
 341     // FIXME: Add a more conservative mode
 342     for (unsigned i = 0; i < Call.getNumArgs(); ++i) {
 343       if (isIteratorType(Call.getArgExpr(i)->getType())) {
 344         if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(i))) {
 345           assignToContainer(C, OrigExpr, Call.getReturnValue(),
 346                             Pos->getContainer());
 347           return;
 348         }
 349       }
 350     }
 351   }
 352 }
 353
 354 void IteratorChecker::checkPostStmt(const MaterializeTemporaryExpr *MTE,
 355                                     CheckerContext &C) const {
 356   /* Transfer iterator state to temporary objects */
 357   auto State = C.getState();
 358   const auto *LCtx = C.getLocationContext();
 359   const auto *Pos =
 360       getIteratorPosition(State, State->getSVal(MTE->GetTemporaryExpr(), LCtx));
 361   if (!Pos)
 362     return;
 363   State = setIteratorPosition(State, State->getSVal(MTE, LCtx), *Pos);
 364   C.addTransition(State);
 365 }
 366
 367 void IteratorChecker::checkDeadSymbols(SymbolReaper &SR,
 368                                        CheckerContext &C) const {
 369   // Cleanup
 370   auto State = C.getState();
 371
 372   auto RegionMap = State->get<IteratorRegionMap>();
 373   for (const auto Reg : RegionMap) {
 374     if (!SR.isLiveRegion(Reg.first)) {
 375       State = State->remove<IteratorRegionMap>(Reg.first);
 376     }
 377   }
 378
 379   auto SymbolMap = State->get<IteratorSymbolMap>();
 380   for (const auto Sym : SymbolMap) {
 381     if (!SR.isLive(Sym.first)) {
 382       State = State->remove<IteratorSymbolMap>(Sym.first);
 383     }
 384   }
 385
 386   auto ContMap = State->get<ContainerMap>();
 387   for (const auto Cont : ContMap) {
 388     if (!SR.isLiveRegion(Cont.first)) {
 389       State = State->remove<ContainerMap>(Cont.first);
 390     }
 391   }
 392
 393   auto ComparisonMap = State->get<IteratorComparisonMap>();
 394   for (const auto Comp : ComparisonMap) {
 395     if (!SR.isLive(Comp.first)) {
 396       State = State->remove<IteratorComparisonMap>(Comp.first);
 397     }
 398   }
 399 }
 400
 401 ProgramStateRef IteratorChecker::evalAssume(ProgramStateRef State, SVal Cond,
 402                                             bool Assumption) const {
 403   // Load recorded comparison and transfer iterator state between sides
 404   // according to comparison operator and assumption
 405   const auto *SE = Cond.getAsSymExpr();
 406   if (!SE)
 407     return State;
 408
 409   auto Opc = getOpcode(SE);
 410   if (Opc != BO_EQ && Opc != BO_NE)
 411     return State;
 412
 413   bool Negated = false;
 414   const auto *Comp = loadComparison(State, SE);
 415   if (!Comp) {
 416     // Try negated comparison, which is a SymExpr to 0 integer comparison
 417     const auto *SIE = dyn_cast<SymIntExpr>(SE);
 418     if (!SIE)
 419       return State;
 420
 421     if (SIE->getRHS() != 0)
 422       return State;
 423
 424     SE = SIE->getLHS();
 425     Negated = SIE->getOpcode() == BO_EQ; // Equal to zero means negation
 426     Opc = getOpcode(SE);
 427     if (Opc != BO_EQ && Opc != BO_NE)
 428       return State;
 429
 430     Comp = loadComparison(State, SE);
 431     if (!Comp)
 432       return State;
 433   }
 434
 435   return processComparison(State, Comp->getLeft(), Comp->getRight(),
 436                            (Comp->isEquality() == Assumption) != Negated);
 437 }
 438
 439 void IteratorChecker::handleComparison(CheckerContext &C, const SVal &RetVal,
 440                                        const SVal &LVal, const SVal &RVal,
 441                                        OverloadedOperatorKind Op) const {
 442   // Record the operands and the operator of the comparison for the next
 443   // evalAssume, if the result is a symbolic expression. If it is a concrete
 444   // value (only one branch is possible), then transfer the state between
 445   // the operands according to the operator and the result
 446   auto State = C.getState();
 447   if (const auto *Condition = RetVal.getAsSymbolicExpression()) {
 448     const auto *LPos = getIteratorPosition(State, LVal);
 449     const auto *RPos = getIteratorPosition(State, RVal);
 450     if (!LPos && !RPos)
 451       return;
 452     State = saveComparison(State, Condition, LVal, RVal, Op == OO_EqualEqual);
 453     C.addTransition(State);
 454   } else if (const auto TruthVal = RetVal.getAs<nonloc::ConcreteInt>()) {
 455     if ((State = processComparison(
 456              State, getRegionOrSymbol(LVal), getRegionOrSymbol(RVal),
 457              (Op == OO_EqualEqual) == (TruthVal->getValue() != 0)))) {
 458       C.addTransition(State);
 459     } else {
 460       C.generateSink(State, C.getPredecessor());
 461     }
 462   }
 463 }
 464
 465 void IteratorChecker::verifyDereference(CheckerContext &C,
 466                                         const SVal &Val) const {
 467   auto State = C.getState();
 468   const auto *Pos = getIteratorPosition(State, Val);
 469   if (Pos && isOutOfRange(State, *Pos)) {
 470     // If I do not put a tag here, some range tests will fail
 471     static CheckerProgramPointTag Tag("IteratorRangeChecker",
 472                                       "IteratorOutOfRange");
 473     auto *N = C.generateNonFatalErrorNode(State, &Tag);
 474     if (!N) {
 475       return;
 476     }
 477     reportOutOfRangeBug("Iterator accessed outside of its range.", Val, C, N);
 478   }
 479 }
 480
 481 void IteratorChecker::handleEnd(CheckerContext &C, const Expr *CE,
 482                                 const SVal &RetVal, const SVal &Cont) const {
 483   const auto *ContReg = Cont.getAsRegion();
 484   if (!ContReg)
 485     return;
 486
 487   while (const auto *CBOR = ContReg->getAs<CXXBaseObjectRegion>()) {
 488     ContReg = CBOR->getSuperRegion();
 489   }
 490
 491   // If the container already has an end symbol then use it. Otherwise first
 492   // create a new one.
 493   auto State = C.getState();
 494   auto EndSym = getContainerEnd(State, ContReg);
 495   if (!EndSym) {
 496     auto &SymMgr = C.getSymbolManager();
 497     EndSym = SymMgr.conjureSymbol(CE, C.getLocationContext(),
 498                                   C.getASTContext().LongTy, C.blockCount());
 499     State = createContainerEnd(State, ContReg, EndSym);
 500   }
 501   State = setIteratorPosition(State, RetVal,
 502                               IteratorPosition::getPosition(ContReg, EndSym));
 503   C.addTransition(State);
 504 }
 505
 506 void IteratorChecker::assignToContainer(CheckerContext &C, const Expr *CE,
 507                                         const SVal &RetVal,
 508                                         const MemRegion *Cont) const {
 509   while (const auto *CBOR = Cont->getAs<CXXBaseObjectRegion>()) {
 510     Cont = CBOR->getSuperRegion();
 511   }
 512
 513   auto State = C.getState();
 514   auto &SymMgr = C.getSymbolManager();
 515   auto Sym = SymMgr.conjureSymbol(CE, C.getLocationContext(),
 516                                   C.getASTContext().LongTy, C.blockCount());
 517   State = setIteratorPosition(State, RetVal,
 518                               IteratorPosition::getPosition(Cont, Sym));
 519   C.addTransition(State);
 520 }
 521
 522 void IteratorChecker::reportOutOfRangeBug(const StringRef &Message,
 523                                           const SVal &Val, CheckerContext &C,
 524                                           ExplodedNode *ErrNode) const {
 525   auto R = llvm::make_unique<BugReport>(*OutOfRangeBugType, Message, ErrNode);
 526   R->markInteresting(Val);
 527   C.emitReport(std::move(R));
 528 }
 529
 530 namespace {
 531
 532 bool isGreaterOrEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
 533 bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
 534              BinaryOperator::Opcode Opc);
 535
 536 bool isIteratorType(const QualType &Type) {
 537   if (Type->isPointerType())
 538     return true;
 539
 540   const auto *CRD = Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl();
 541   return isIterator(CRD);
 542 }
 543
 544 bool isIterator(const CXXRecordDecl *CRD) {
 545   if (!CRD)
 546     return false;
 547
 548   const auto Name = CRD->getName();
 549   if (!(Name.endswith_lower("iterator") || Name.endswith_lower("iter") ||
 550         Name.endswith_lower("it")))
 551     return false;
 552
 553   bool HasCopyCtor = false, HasCopyAssign = true, HasDtor = false,
 554        HasPreIncrOp = false, HasPostIncrOp = false, HasDerefOp = false;
 555   for (const auto *Method : CRD->methods()) {
 556     if (const auto *Ctor = dyn_cast<CXXConstructorDecl>(Method)) {
 557       if (Ctor->isCopyConstructor()) {
 558         HasCopyCtor = !Ctor->isDeleted() && Ctor->getAccess() == AS_public;
 559       }
 560       continue;
 561     }
 562     if (const auto *Dtor = dyn_cast<CXXDestructorDecl>(Method)) {
 563       HasDtor = !Dtor->isDeleted() && Dtor->getAccess() == AS_public;
 564       continue;
 565     }
 566     if (Method->isCopyAssignmentOperator()) {
 567       HasCopyAssign = !Method->isDeleted() && Method->getAccess() == AS_public;
 568       continue;
 569     }
 570     if (!Method->isOverloadedOperator())
 571       continue;
 572     const auto OPK = Method->getOverloadedOperator();
 573     if (OPK == OO_PlusPlus) {
 574       HasPreIncrOp = HasPreIncrOp || (Method->getNumParams() == 0);
 575       HasPostIncrOp = HasPostIncrOp || (Method->getNumParams() == 1);
 576       continue;
 577     }
 578     if (OPK == OO_Star) {
 579       HasDerefOp = (Method->getNumParams() == 0);
 580       continue;
 581     }
 582   }
 583
 584   return HasCopyCtor && HasCopyAssign && HasDtor && HasPreIncrOp &&
 585          HasPostIncrOp && HasDerefOp;
 586 }
 587
 588 bool isEndCall(const FunctionDecl *Func) {
 589   const auto *IdInfo = Func->getIdentifier();
 590   if (!IdInfo)
 591     return false;
 592   return IdInfo->getName().endswith_lower("end");
 593 }
 594
 595 bool isSimpleComparisonOperator(OverloadedOperatorKind OK) {
 596   return OK == OO_EqualEqual || OK == OO_ExclaimEqual;
 597 }
 598
 599 bool isDereferenceOperator(OverloadedOperatorKind OK) {
 600   return OK == OO_Star || OK == OO_Arrow || OK == OO_ArrowStar ||
 601          OK == OO_Subscript;
 602 }
 603
 604 BinaryOperator::Opcode getOpcode(const SymExpr *SE) {
 605   if (const auto *BSE = dyn_cast<BinarySymExpr>(SE)) {
 606     return BSE->getOpcode();
 607   } else if (const auto *SC = dyn_cast<SymbolConjured>(SE)) {
 608     const auto *COE = dyn_cast<CXXOperatorCallExpr>(SC->getStmt());
 609     if (!COE)
 610       return BO_Comma; // Extremal value, neither EQ nor NE
 611     if (COE->getOperator() == OO_EqualEqual) {
 612       return BO_EQ;
 613     } else if (COE->getOperator() == OO_ExclaimEqual) {
 614       return BO_NE;
 615     }
 616     return BO_Comma; // Extremal value, neither EQ nor NE
 617   }
 618   return BO_Comma; // Extremal value, neither EQ nor NE
 619 }
 620
 621 const RegionOrSymbol getRegionOrSymbol(const SVal &Val) {
 622   if (const auto Reg = Val.getAsRegion()) {
 623     return Reg;
 624   } else if (const auto Sym = Val.getAsSymbol()) {
 625     return Sym;
 626   } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
 627     return LCVal->getRegion();
 628   }
 629   return RegionOrSymbol();
 630 }
 631
 632 const ProgramStateRef processComparison(ProgramStateRef State,
 633                                         RegionOrSymbol LVal,
 634                                         RegionOrSymbol RVal, bool Equal) {
 635   const auto *LPos = getIteratorPosition(State, LVal);
 636   const auto *RPos = getIteratorPosition(State, RVal);
 637   if (LPos && !RPos) {
 638     State = adjustIteratorPosition(State, RVal, *LPos, Equal);
 639   } else if (!LPos && RPos) {
 640     State = adjustIteratorPosition(State, LVal, *RPos, Equal);
 641   } else if (LPos && RPos) {
 642     State = relateIteratorPositions(State, *LPos, *RPos, Equal);
 643   }
 644   return State;
 645 }
 646
 647 const ProgramStateRef saveComparison(ProgramStateRef State,
 648                                      const SymExpr *Condition, const SVal &LVal,
 649                                      const SVal &RVal, bool Eq) {
 650   const auto Left = getRegionOrSymbol(LVal);
 651   const auto Right = getRegionOrSymbol(RVal);
 652   if (!Left || !Right)
 653     return State;
 654   return State->set<IteratorComparisonMap>(Condition,
 655                                            IteratorComparison(Left, Right, Eq));
 656 }
 657
 658 const IteratorComparison *loadComparison(ProgramStateRef State,
 659                                          const SymExpr *Condition) {
 660   return State->get<IteratorComparisonMap>(Condition);
 661 }
 662
 663 SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont) {
 664   const auto *CDataPtr = getContainerData(State, Cont);
 665   if (!CDataPtr)
 666     return nullptr;
 667
 668   return CDataPtr->getEnd();
 669 }
 670
 671 ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont,
 672                                    const SymbolRef Sym) {
 673   // Only create if it does not exist
 674   const auto *CDataPtr = getContainerData(State, Cont);
 675   if (CDataPtr) {
 676     if (CDataPtr->getEnd()) {
 677       return State;
 678     } else {
 679       const auto CData = CDataPtr->newEnd(Sym);
 680       return setContainerData(State, Cont, CData);
 681     }
 682   } else {
 683     const auto CData = ContainerData::fromEnd(Sym);
 684     return setContainerData(State, Cont, CData);
 685   }
 686 }
 687
 688 const ContainerData *getContainerData(ProgramStateRef State,
 689                                       const MemRegion *Cont) {
 690   return State->get<ContainerMap>(Cont);
 691 }
 692
 693 ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont,
 694                                  const ContainerData &CData) {
 695   return State->set<ContainerMap>(Cont, CData);
 696 }
 697
 698 const IteratorPosition *getIteratorPosition(ProgramStateRef State,
 699                                             const SVal &Val) {
 700   if (const auto Reg = Val.getAsRegion()) {
 701     return State->get<IteratorRegionMap>(Reg);
 702   } else if (const auto Sym = Val.getAsSymbol()) {
 703     return State->get<IteratorSymbolMap>(Sym);
 704   } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
 705     return State->get<IteratorRegionMap>(LCVal->getRegion());
 706   }
 707   return nullptr;
 708 }
 709
 710 const IteratorPosition *getIteratorPosition(ProgramStateRef State,
 711                                             RegionOrSymbol RegOrSym) {
 712   if (RegOrSym.is<const MemRegion *>()) {
 713     return State->get<IteratorRegionMap>(RegOrSym.get<const MemRegion *>());
 714   } else if (RegOrSym.is<SymbolRef>()) {
 715     return State->get<IteratorSymbolMap>(RegOrSym.get<SymbolRef>());
 716   }
 717   return nullptr;
 718 }
 719
 720 ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val,
 721                                     const IteratorPosition &Pos) {
 722   if (const auto Reg = Val.getAsRegion()) {
 723     return State->set<IteratorRegionMap>(Reg, Pos);
 724   } else if (const auto Sym = Val.getAsSymbol()) {
 725     return State->set<IteratorSymbolMap>(Sym, Pos);
 726   } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
 727     return State->set<IteratorRegionMap>(LCVal->getRegion(), Pos);
 728   }
 729   return nullptr;
 730 }
 731
 732 ProgramStateRef setIteratorPosition(ProgramStateRef State,
 733                                     RegionOrSymbol RegOrSym,
 734                                     const IteratorPosition &Pos) {
 735   if (RegOrSym.is<const MemRegion *>()) {
 736     return State->set<IteratorRegionMap>(RegOrSym.get<const MemRegion *>(),
 737                                          Pos);
 738   } else if (RegOrSym.is<SymbolRef>()) {
 739     return State->set<IteratorSymbolMap>(RegOrSym.get<SymbolRef>(), Pos);
 740   }
 741   return nullptr;
 742 }
 743
 744 ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val) {
 745   if (const auto Reg = Val.getAsRegion()) {
 746     return State->remove<IteratorRegionMap>(Reg);
 747   } else if (const auto Sym = Val.getAsSymbol()) {
 748     return State->remove<IteratorSymbolMap>(Sym);
 749   } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
 750     return State->remove<IteratorRegionMap>(LCVal->getRegion());
 751   }
 752   return nullptr;
 753 }
 754
 755 ProgramStateRef adjustIteratorPosition(ProgramStateRef State,
 756                                        RegionOrSymbol RegOrSym,
 757                                        const IteratorPosition &Pos,
 758                                        bool Equal) {
 759   if (Equal) {
 760     return setIteratorPosition(State, RegOrSym, Pos);
 761   } else {
 762     return State;
 763   }
 764 }
 765
 766 ProgramStateRef relateIteratorPositions(ProgramStateRef State,
 767                                         const IteratorPosition &Pos1,
 768                                         const IteratorPosition &Pos2,
 769                                         bool Equal) {
 770   // Try to compare them and get a defined value
 771   auto &SVB = State->getStateManager().getSValBuilder();
 772   const auto comparison =
 773       SVB.evalBinOp(State, BO_EQ, nonloc::SymbolVal(Pos1.getOffset()),
 774                     nonloc::SymbolVal(Pos2.getOffset()), SVB.getConditionType())
 775           .getAs<DefinedSVal>();
 776   if (comparison) {
 777     return State->assume(*comparison, Equal);
 778   }
 779
 780   return State;
 781 }
 782
 783 bool isOutOfRange(ProgramStateRef State, const IteratorPosition &Pos) {
 784   const auto *Cont = Pos.getContainer();
 785   const auto *CData = getContainerData(State, Cont);
 786   if (!CData)
 787     return false;
 788
 789   // Out of range means less than the begin symbol or greater or equal to the
 790   // end symbol.
 791
 792   const auto End = CData->getEnd();
 793   if (End) {
 794     if (isGreaterOrEqual(State, Pos.getOffset(), End)) {
 795       return true;
 796     }
 797   }
 798
 799   return false;
 800 }
 801
 802 bool isGreaterOrEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
 803   return compare(State, Sym1, Sym2, BO_GE);
 804 }
 805
 806 bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
 807              BinaryOperator::Opcode Opc) {
 808   auto &SMgr = State->getStateManager();
 809   auto &SVB = SMgr.getSValBuilder();
 810
 811   const auto comparison =
 812       SVB.evalBinOp(State, Opc, nonloc::SymbolVal(Sym1),
 813                     nonloc::SymbolVal(Sym2), SVB.getConditionType())
 814           .getAs<DefinedSVal>();
 815
 816   if(comparison) {
 817     return !!State->assume(*comparison, true);
 818   }
 819
 820   return false;
 821 }
 822
 823 } // namespace
 824
 825 #define REGISTER_CHECKER(name)                                                 \
 826   void ento::register##name(CheckerManager &Mgr) {                             \
 827     auto *checker = Mgr.registerChecker<IteratorChecker>();                    \
 828     checker->ChecksEnabled[IteratorChecker::CK_##name] = true;                 \
 829     checker->CheckNames[IteratorChecker::CK_##name] =                          \
 830         Mgr.getCurrentCheckName();                                             \
 831   }
 832
 833 REGISTER_CHECKER(IteratorRangeChecker)