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

   1 //===-- IteratorPastEndChecker.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 #include "ClangSACheckers.h"
  16 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
  17 #include "clang/StaticAnalyzer/Core/Checker.h"
  18 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
  19 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
  20
  21 #include <utility>
  22
  23 using namespace clang;
  24 using namespace ento;
  25
  26 namespace {
  27 struct IteratorPosition {
  28 private:
  29   enum Kind { InRange, OutofRange } K;
  30   IteratorPosition(Kind InK) : K(InK) {}
  31
  32 public:
  33   bool isInRange() const { return K == InRange; }
  34   bool isOutofRange() const { return K == OutofRange; }
  35
  36   static IteratorPosition getInRange() { return IteratorPosition(InRange); }
  37   static IteratorPosition getOutofRange() {
  38     return IteratorPosition(OutofRange);
  39   }
  40
  41   bool operator==(const IteratorPosition &X) const { return K == X.K; }
  42   bool operator!=(const IteratorPosition &X) const { return K != X.K; }
  43   void Profile(llvm::FoldingSetNodeID &ID) const { ID.AddInteger(K); }
  44 };
  45
  46 typedef llvm::PointerUnion<const MemRegion *, SymbolRef> RegionOrSymbol;
  47
  48 struct IteratorComparison {
  49 private:
  50   RegionOrSymbol Left, Right;
  51   bool Equality;
  52
  53 public:
  54   IteratorComparison(RegionOrSymbol L, RegionOrSymbol R, bool Eq)
  55       : Left(L), Right(R), Equality(Eq) {}
  56
  57   RegionOrSymbol getLeft() const { return Left; }
  58   RegionOrSymbol getRight() const { return Right; }
  59   bool isEquality() const { return Equality; }
  60   bool operator==(const IteratorComparison &X) const {
  61     return Left == X.Left && Right == X.Right && Equality == X.Equality;
  62   }
  63   bool operator!=(const IteratorComparison &X) const {
  64     return Left != X.Left || Right != X.Right || Equality != X.Equality;
  65   }
  66   void Profile(llvm::FoldingSetNodeID &ID) const { ID.AddInteger(Equality); }
  67 };
  68
  69 class IteratorPastEndChecker
  70     : public Checker<
  71           check::PreCall, check::PostCall, check::PreStmt<CXXOperatorCallExpr>,
  72           check::PostStmt<CXXConstructExpr>, check::PostStmt<DeclStmt>,
  73           check::PostStmt<MaterializeTemporaryExpr>, check::BeginFunction,
  74           check::DeadSymbols, eval::Assume, eval::Call> {
  75   mutable IdentifierInfo *II_find = nullptr,
  76                          *II_find_end = nullptr, *II_find_first_of = nullptr,
  77                          *II_find_if = nullptr, *II_find_if_not = nullptr,
  78                          *II_lower_bound = nullptr, *II_upper_bound = nullptr,
  79                          *II_search = nullptr, *II_search_n = nullptr;
  80
  81   std::unique_ptr<BugType> PastEndBugType;
  82
  83   void handleComparison(CheckerContext &C, const SVal &RetVal, const SVal &LVal,
  84                         const SVal &RVal, OverloadedOperatorKind Op) const;
  85   void handleAccess(CheckerContext &C, const SVal &Val) const;
  86   void handleDecrement(CheckerContext &C, const SVal &Val) const;
  87   void handleEnd(CheckerContext &C, const SVal &RetVal) const;
  88
  89   bool evalFind(CheckerContext &C, const CallExpr *CE) const;
  90   bool evalFindEnd(CheckerContext &C, const CallExpr *CE) const;
  91   bool evalFindFirstOf(CheckerContext &C, const CallExpr *CE) const;
  92   bool evalFindIf(CheckerContext &C, const CallExpr *CE) const;
  93   bool evalFindIfNot(CheckerContext &C, const CallExpr *CE) const;
  94   bool evalLowerBound(CheckerContext &C, const CallExpr *CE) const;
  95   bool evalUpperBound(CheckerContext &C, const CallExpr *CE) const;
  96   bool evalSearch(CheckerContext &C, const CallExpr *CE) const;
  97   bool evalSearchN(CheckerContext &C, const CallExpr *CE) const;
  98   void Find(CheckerContext &C, const CallExpr *CE) const;
  99
 100   void reportPastEndBug(const StringRef &Message, const SVal &Val,
 101                         CheckerContext &C, ExplodedNode *ErrNode) const;
 102   void initIdentifiers(ASTContext &Ctx) const;
 103
 104 public:
 105   IteratorPastEndChecker();
 106
 107   void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
 108   void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
 109   void checkPreStmt(const CXXOperatorCallExpr *COCE, CheckerContext &C) const;
 110   void checkBeginFunction(CheckerContext &C) const;
 111   void checkPostStmt(const CXXConstructExpr *CCE, CheckerContext &C) const;
 112   void checkPostStmt(const DeclStmt *DS, CheckerContext &C) const;
 113   void checkPostStmt(const MaterializeTemporaryExpr *MTE,
 114                      CheckerContext &C) const;
 115   void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
 116   ProgramStateRef evalAssume(ProgramStateRef State, SVal Cond,
 117                              bool Assumption) const;
 118   bool evalCall(const CallExpr *CE, CheckerContext &C) const;
 119 };
 120 }
 121
 122 REGISTER_MAP_WITH_PROGRAMSTATE(IteratorSymbolMap, SymbolRef, IteratorPosition)
 123 REGISTER_MAP_WITH_PROGRAMSTATE(IteratorRegionMap, const MemRegion *,
 124                                IteratorPosition)
 125
 126 REGISTER_MAP_WITH_PROGRAMSTATE(IteratorComparisonMap, const SymExpr *,
 127                                IteratorComparison)
 128
 129 #define INIT_ID(Id)                                                            \
 130   if (!II_##Id)                                                                \
 131   II_##Id = &Ctx.Idents.get(#Id)
 132
 133 namespace {
 134
 135 bool isIteratorType(const QualType &Type);
 136 bool isIterator(const CXXRecordDecl *CRD);
 137 bool isEndCall(const FunctionDecl *Func);
 138 bool isSimpleComparisonOperator(OverloadedOperatorKind OK);
 139 bool isAccessOperator(OverloadedOperatorKind OK);
 140 bool isDecrementOperator(OverloadedOperatorKind OK);
 141 BinaryOperator::Opcode getOpcode(const SymExpr *SE);
 142 const RegionOrSymbol getRegionOrSymbol(const SVal &Val);
 143 const ProgramStateRef processComparison(ProgramStateRef State,
 144                                         RegionOrSymbol LVal,
 145                                         RegionOrSymbol RVal, bool Equal);
 146 const ProgramStateRef saveComparison(ProgramStateRef State,
 147                                      const SymExpr *Condition, const SVal &LVal,
 148                                      const SVal &RVal, bool Eq);
 149 const IteratorComparison *loadComparison(ProgramStateRef State,
 150                                          const SymExpr *Condition);
 151 const IteratorPosition *getIteratorPosition(ProgramStateRef State,
 152                                             const SVal &Val);
 153 const IteratorPosition *getIteratorPosition(ProgramStateRef State,
 154                                             RegionOrSymbol RegOrSym);
 155 ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val,
 156                                     IteratorPosition Pos);
 157 ProgramStateRef setIteratorPosition(ProgramStateRef State,
 158                                     RegionOrSymbol RegOrSym,
 159                                     IteratorPosition Pos);
 160 ProgramStateRef adjustIteratorPosition(ProgramStateRef State,
 161                                        RegionOrSymbol RegOrSym,
 162                                        IteratorPosition Pos, bool Equal);
 163 bool contradictingIteratorPositions(IteratorPosition Pos1,
 164                                     IteratorPosition Pos2, bool Equal);
 165 }
 166
 167 IteratorPastEndChecker::IteratorPastEndChecker() {
 168   PastEndBugType.reset(
 169       new BugType(this, "Iterator Past End", "Misuse of STL APIs"));
 170   PastEndBugType->setSuppressOnSink(true);
 171 }
 172
 173 void IteratorPastEndChecker::checkPreCall(const CallEvent &Call,
 174                                           CheckerContext &C) const {
 175   // Check for access past end
 176   const auto *Func = Call.getDecl()->getAsFunction();
 177   if (!Func)
 178     return;
 179   if (Func->isOverloadedOperator()) {
 180     if (isAccessOperator(Func->getOverloadedOperator())) {
 181       if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
 182         handleAccess(C, InstCall->getCXXThisVal());
 183       } else {
 184         handleAccess(C, Call.getArgSVal(0));
 185       }
 186     }
 187   }
 188 }
 189
 190 void IteratorPastEndChecker::checkPostCall(const CallEvent &Call,
 191                                            CheckerContext &C) const {
 192   // Record end() iterators, iterator decrementation and comparison
 193   const auto *Func = Call.getDecl()->getAsFunction();
 194   if (!Func)
 195     return;
 196   if (Func->isOverloadedOperator()) {
 197     const auto Op = Func->getOverloadedOperator();
 198     if (isSimpleComparisonOperator(Op)) {
 199       if (Func->isCXXInstanceMember()) {
 200         const auto &InstCall = static_cast<const CXXInstanceCall &>(Call);
 201         handleComparison(C, InstCall.getReturnValue(), InstCall.getCXXThisVal(),
 202                          InstCall.getArgSVal(0), Op);
 203       } else {
 204         handleComparison(C, Call.getReturnValue(), Call.getArgSVal(0),
 205                          Call.getArgSVal(1), Op);
 206       }
 207     } else if (isDecrementOperator(Func->getOverloadedOperator())) {
 208       if (Func->isCXXInstanceMember()) {
 209         const auto &InstCall = static_cast<const CXXInstanceCall &>(Call);
 210         handleDecrement(C, InstCall.getCXXThisVal());
 211       } else {
 212         handleDecrement(C, Call.getArgSVal(0));
 213       }
 214     }
 215   } else if (Func->isCXXInstanceMember()) {
 216     if (!isEndCall(Func))
 217       return;
 218     if (!isIteratorType(Call.getResultType()))
 219       return;
 220     handleEnd(C, Call.getReturnValue());
 221   }
 222 }
 223
 224 void IteratorPastEndChecker::checkPreStmt(const CXXOperatorCallExpr *COCE,
 225                                           CheckerContext &C) const {
 226   const auto *ThisExpr = COCE->getArg(0);
 227
 228   auto State = C.getState();
 229   const auto *LCtx = C.getPredecessor()->getLocationContext();
 230
 231   const auto CurrentThis = State->getSVal(ThisExpr, LCtx);
 232   if (const auto *Reg = CurrentThis.getAsRegion()) {
 233     if (!Reg->getAs<CXXTempObjectRegion>())
 234       return;
 235     const auto OldState = C.getPredecessor()->getFirstPred()->getState();
 236     const auto OldThis = OldState->getSVal(ThisExpr, LCtx);
 237     const auto *Pos = getIteratorPosition(OldState, OldThis);
 238     if (!Pos)
 239       return;
 240     State = setIteratorPosition(State, CurrentThis, *Pos);
 241     C.addTransition(State);
 242   }
 243 }
 244
 245 void IteratorPastEndChecker::checkBeginFunction(CheckerContext &C) const {
 246   // Copy state of iterator arguments to iterator parameters
 247   auto State = C.getState();
 248   const auto *LCtx = C.getLocationContext();
 249
 250   const auto *Site = cast<StackFrameContext>(LCtx)->getCallSite();
 251   if (!Site)
 252     return;
 253
 254   const auto *FD = dyn_cast<FunctionDecl>(LCtx->getDecl());
 255   if (!FD)
 256     return;
 257
 258   const auto *CE = dyn_cast<CallExpr>(Site);
 259   if (!CE)
 260     return;
 261
 262   bool Change = false;
 263   int idx = 0;
 264   for (const auto P : FD->parameters()) {
 265     auto Param = State->getLValue(P, LCtx);
 266     auto Arg = State->getSVal(CE->getArg(idx++), LCtx->getParent());
 267     const auto *Pos = getIteratorPosition(State, Arg);
 268     if (!Pos)
 269       continue;
 270     State = setIteratorPosition(State, Param, *Pos);
 271     Change = true;
 272   }
 273   if (Change) {
 274     C.addTransition(State);
 275   }
 276 }
 277
 278 void IteratorPastEndChecker::checkPostStmt(const CXXConstructExpr *CCE,
 279                                            CheckerContext &C) const {
 280   // Transfer iterator state in case of copy or move by constructor
 281   const auto *ctr = CCE->getConstructor();
 282   if (!ctr->isCopyOrMoveConstructor())
 283     return;
 284   const auto *RHSExpr = CCE->getArg(0);
 285
 286   auto State = C.getState();
 287   const auto *LCtx = C.getLocationContext();
 288
 289   const auto RetVal = State->getSVal(CCE, LCtx);
 290
 291   const auto RHSVal = State->getSVal(RHSExpr, LCtx);
 292   const auto *RHSPos = getIteratorPosition(State, RHSVal);
 293   if (!RHSPos)
 294     return;
 295   State = setIteratorPosition(State, RetVal, *RHSPos);
 296   C.addTransition(State);
 297 }
 298
 299 void IteratorPastEndChecker::checkPostStmt(const DeclStmt *DS,
 300                                            CheckerContext &C) const {
 301   // Transfer iterator state to new variable declaration
 302   for (const auto *D : DS->decls()) {
 303     const auto *VD = dyn_cast<VarDecl>(D);
 304     if (!VD || !VD->hasInit())
 305       continue;
 306
 307     auto State = C.getState();
 308     const auto *LCtx = C.getPredecessor()->getLocationContext();
 309     const auto *Pos =
 310         getIteratorPosition(State, State->getSVal(VD->getInit(), LCtx));
 311     if (!Pos)
 312       continue;
 313     State = setIteratorPosition(State, State->getLValue(VD, LCtx), *Pos);
 314     C.addTransition(State);
 315   }
 316 }
 317
 318 void IteratorPastEndChecker::checkPostStmt(const MaterializeTemporaryExpr *MTE,
 319                                            CheckerContext &C) const {
 320   /* Transfer iterator state for to temporary objects */
 321   auto State = C.getState();
 322   const auto *LCtx = C.getPredecessor()->getLocationContext();
 323   const auto *Pos =
 324       getIteratorPosition(State, State->getSVal(MTE->GetTemporaryExpr(), LCtx));
 325   if (!Pos)
 326     return;
 327   State = setIteratorPosition(State, State->getSVal(MTE, LCtx), *Pos);
 328   C.addTransition(State);
 329 }
 330
 331 void IteratorPastEndChecker::checkDeadSymbols(SymbolReaper &SR,
 332                                               CheckerContext &C) const {
 333   auto State = C.getState();
 334
 335   auto RegionMap = State->get<IteratorRegionMap>();
 336   for (const auto Reg : RegionMap) {
 337     if (!SR.isLiveRegion(Reg.first)) {
 338       State = State->remove<IteratorRegionMap>(Reg.first);
 339     }
 340   }
 341
 342   auto SymbolMap = State->get<IteratorSymbolMap>();
 343   for (const auto Sym : SymbolMap) {
 344     if (SR.isDead(Sym.first)) {
 345       State = State->remove<IteratorSymbolMap>(Sym.first);
 346     }
 347   }
 348
 349   auto ComparisonMap = State->get<IteratorComparisonMap>();
 350   for (const auto Comp : ComparisonMap) {
 351     if (SR.isDead(Comp.first)) {
 352       State = State->remove<IteratorComparisonMap>(Comp.first);
 353     }
 354   }
 355 }
 356
 357 ProgramStateRef IteratorPastEndChecker::evalAssume(ProgramStateRef State,
 358                                                    SVal Cond,
 359                                                    bool Assumption) const {
 360   // Load recorded comparison and transfer iterator state between sides
 361   // according to comparison operator and assumption
 362   const auto *SE = Cond.getAsSymExpr();
 363   if (!SE)
 364     return State;
 365
 366   auto Opc = getOpcode(SE);
 367   if (Opc != BO_EQ && Opc != BO_NE)
 368     return State;
 369
 370   bool Negated = false;
 371   const auto *Comp = loadComparison(State, SE);
 372   if (!Comp) {
 373     // Try negated comparison, which is a SymExpr to 0 integer comparison
 374     const auto *SIE = dyn_cast<SymIntExpr>(SE);
 375     if (!SIE)
 376       return State;
 377
 378     if (SIE->getRHS() != 0)
 379       return State;
 380
 381     SE = SIE->getLHS();
 382     Negated = SIE->getOpcode() == BO_EQ; // Equal to zero means negation
 383     Opc = getOpcode(SE);
 384     if (Opc != BO_EQ && Opc != BO_NE)
 385       return State;
 386
 387     Comp = loadComparison(State, SE);
 388     if (!Comp)
 389       return State;
 390   }
 391
 392   return processComparison(State, Comp->getLeft(), Comp->getRight(),
 393                            (Comp->isEquality() == Assumption) != Negated);
 394 }
 395
 396 // FIXME: Evaluation of these STL calls should be moved to StdCLibraryFunctions
 397 //       checker (see patch r284960) or another similar checker for C++ STL
 398 //       functions (e.g. StdCXXLibraryFunctions or StdCppLibraryFunctions).
 399 bool IteratorPastEndChecker::evalCall(const CallExpr *CE,
 400                                       CheckerContext &C) const {
 401   const FunctionDecl *FD = C.getCalleeDecl(CE);
 402   if (!FD)
 403     return false;
 404
 405   ASTContext &Ctx = C.getASTContext();
 406   initIdentifiers(Ctx);
 407
 408   if (FD->getKind() == Decl::Function) {
 409     if (FD->isInStdNamespace()) {
 410       if (FD->getIdentifier() == II_find) {
 411         return evalFind(C, CE);
 412       } else if (FD->getIdentifier() == II_find_end) {
 413         return evalFindEnd(C, CE);
 414       } else if (FD->getIdentifier() == II_find_first_of) {
 415         return evalFindFirstOf(C, CE);
 416       } else if (FD->getIdentifier() == II_find_if) {
 417         return evalFindIf(C, CE);
 418       } else if (FD->getIdentifier() == II_find_if) {
 419         return evalFindIf(C, CE);
 420       } else if (FD->getIdentifier() == II_find_if_not) {
 421         return evalFindIfNot(C, CE);
 422       } else if (FD->getIdentifier() == II_upper_bound) {
 423         return evalUpperBound(C, CE);
 424       } else if (FD->getIdentifier() == II_lower_bound) {
 425         return evalLowerBound(C, CE);
 426       } else if (FD->getIdentifier() == II_search) {
 427         return evalSearch(C, CE);
 428       } else if (FD->getIdentifier() == II_search_n) {
 429         return evalSearchN(C, CE);
 430       }
 431     }
 432   }
 433
 434   return false;
 435 }
 436
 437 void IteratorPastEndChecker::handleComparison(CheckerContext &C,
 438                                               const SVal &RetVal,
 439                                               const SVal &LVal,
 440                                               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 IteratorPastEndChecker::handleAccess(CheckerContext &C,
 466                                           const SVal &Val) const {
 467   auto State = C.getState();
 468   const auto *Pos = getIteratorPosition(State, Val);
 469   if (Pos && Pos->isOutofRange()) {
 470     auto *N = C.generateNonFatalErrorNode(State);
 471     if (!N) {
 472       return;
 473     }
 474     reportPastEndBug("Iterator accessed past its end.", Val, C, N);
 475   }
 476 }
 477
 478 void IteratorPastEndChecker::handleDecrement(CheckerContext &C,
 479                                              const SVal &Val) const {
 480   auto State = C.getState();
 481   const auto *Pos = getIteratorPosition(State, Val);
 482   if (Pos && Pos->isOutofRange()) {
 483     State = setIteratorPosition(State, Val, IteratorPosition::getInRange());
 484     // FIXME: We could also check for iterators ahead of their beginnig in the
 485     //       future, but currently we do not care for such errors. We also
 486     //       assume that the iterator is not past its end by more then one
 487     //       position.
 488     C.addTransition(State);
 489   }
 490 }
 491
 492 void IteratorPastEndChecker::handleEnd(CheckerContext &C,
 493                                        const SVal &RetVal) const {
 494   auto State = C.getState();
 495   State = setIteratorPosition(State, RetVal, IteratorPosition::getOutofRange());
 496   C.addTransition(State);
 497 }
 498
 499 bool IteratorPastEndChecker::evalFind(CheckerContext &C,
 500                                       const CallExpr *CE) const {
 501   if (CE->getNumArgs() == 3 && isIteratorType(CE->getArg(0)->getType()) &&
 502       isIteratorType(CE->getArg(1)->getType())) {
 503     Find(C, CE);
 504     return true;
 505   }
 506   return false;
 507 }
 508
 509 bool IteratorPastEndChecker::evalFindEnd(CheckerContext &C,
 510                                          const CallExpr *CE) const {
 511   if ((CE->getNumArgs() == 4 || CE->getNumArgs() == 5) &&
 512       isIteratorType(CE->getArg(0)->getType()) &&
 513       isIteratorType(CE->getArg(1)->getType()) &&
 514       isIteratorType(CE->getArg(2)->getType()) &&
 515       isIteratorType(CE->getArg(3)->getType())) {
 516     Find(C, CE);
 517     return true;
 518   }
 519   return false;
 520 }
 521
 522 bool IteratorPastEndChecker::evalFindFirstOf(CheckerContext &C,
 523                                              const CallExpr *CE) const {
 524   if ((CE->getNumArgs() == 4 || CE->getNumArgs() == 5) &&
 525       isIteratorType(CE->getArg(0)->getType()) &&
 526       isIteratorType(CE->getArg(1)->getType()) &&
 527       isIteratorType(CE->getArg(2)->getType()) &&
 528       isIteratorType(CE->getArg(3)->getType())) {
 529     Find(C, CE);
 530     return true;
 531   }
 532   return false;
 533 }
 534
 535 bool IteratorPastEndChecker::evalFindIf(CheckerContext &C,
 536                                         const CallExpr *CE) const {
 537   if (CE->getNumArgs() == 3 && isIteratorType(CE->getArg(0)->getType()) &&
 538       isIteratorType(CE->getArg(1)->getType())) {
 539     Find(C, CE);
 540     return true;
 541   }
 542   return false;
 543 }
 544
 545 bool IteratorPastEndChecker::evalFindIfNot(CheckerContext &C,
 546                                            const CallExpr *CE) const {
 547   if (CE->getNumArgs() == 3 && isIteratorType(CE->getArg(0)->getType()) &&
 548       isIteratorType(CE->getArg(1)->getType())) {
 549     Find(C, CE);
 550     return true;
 551   }
 552   return false;
 553 }
 554
 555 bool IteratorPastEndChecker::evalLowerBound(CheckerContext &C,
 556                                             const CallExpr *CE) const {
 557   if ((CE->getNumArgs() == 3 || CE->getNumArgs() == 4) &&
 558       isIteratorType(CE->getArg(0)->getType()) &&
 559       isIteratorType(CE->getArg(1)->getType())) {
 560     Find(C, CE);
 561     return true;
 562   }
 563   return false;
 564 }
 565
 566 bool IteratorPastEndChecker::evalUpperBound(CheckerContext &C,
 567                                             const CallExpr *CE) const {
 568   if ((CE->getNumArgs() == 3 || CE->getNumArgs() == 4) &&
 569       isIteratorType(CE->getArg(0)->getType()) &&
 570       isIteratorType(CE->getArg(1)->getType())) {
 571     Find(C, CE);
 572     return true;
 573   }
 574   return false;
 575 }
 576
 577 bool IteratorPastEndChecker::evalSearch(CheckerContext &C,
 578                                         const CallExpr *CE) const {
 579   if ((CE->getNumArgs() == 4 || CE->getNumArgs() == 5) &&
 580       isIteratorType(CE->getArg(0)->getType()) &&
 581       isIteratorType(CE->getArg(1)->getType()) &&
 582       isIteratorType(CE->getArg(2)->getType()) &&
 583       isIteratorType(CE->getArg(3)->getType())) {
 584     Find(C, CE);
 585     return true;
 586   }
 587   return false;
 588 }
 589
 590 bool IteratorPastEndChecker::evalSearchN(CheckerContext &C,
 591                                          const CallExpr *CE) const {
 592   if ((CE->getNumArgs() == 4 || CE->getNumArgs() == 5) &&
 593       isIteratorType(CE->getArg(0)->getType()) &&
 594       isIteratorType(CE->getArg(1)->getType())) {
 595     Find(C, CE);
 596     return true;
 597   }
 598   return false;
 599 }
 600
 601 void IteratorPastEndChecker::Find(CheckerContext &C, const CallExpr *CE) const {
 602   auto state = C.getState();
 603   auto &svalBuilder = C.getSValBuilder();
 604   const auto *LCtx = C.getLocationContext();
 605
 606   auto RetVal = svalBuilder.conjureSymbolVal(nullptr, CE, LCtx, C.blockCount());
 607   auto SecondParam = state->getSVal(CE->getArg(1), LCtx);
 608
 609   auto stateFound = state->BindExpr(CE, LCtx, RetVal);
 610   auto stateNotFound = state->BindExpr(CE, LCtx, SecondParam);
 611
 612   C.addTransition(stateFound);
 613   C.addTransition(stateNotFound);
 614 }
 615
 616 void IteratorPastEndChecker::reportPastEndBug(const StringRef &Message,
 617                                               const SVal &Val,
 618                                               CheckerContext &C,
 619                                               ExplodedNode *ErrNode) const {
 620   auto R = llvm::make_unique<BugReport>(*PastEndBugType, Message, ErrNode);
 621   R->markInteresting(Val);
 622   C.emitReport(std::move(R));
 623 }
 624
 625 void IteratorPastEndChecker::initIdentifiers(ASTContext &Ctx) const {
 626   INIT_ID(find);
 627   INIT_ID(find_end);
 628   INIT_ID(find_first_of);
 629   INIT_ID(find_if);
 630   INIT_ID(find_if_not);
 631   INIT_ID(lower_bound);
 632   INIT_ID(upper_bound);
 633   INIT_ID(search);
 634   INIT_ID(search_n);
 635 }
 636
 637 namespace {
 638
 639 bool isIteratorType(const QualType &Type) {
 640   if (Type->isPointerType())
 641     return true;
 642
 643   const auto *CRD = Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl();
 644   return isIterator(CRD);
 645 }
 646
 647 bool isIterator(const CXXRecordDecl *CRD) {
 648   if (!CRD)
 649     return false;
 650
 651   const auto Name = CRD->getName();
 652   if (!(Name.endswith_lower("iterator") || Name.endswith_lower("iter") ||
 653         Name.endswith_lower("it")))
 654     return false;
 655
 656   bool HasCopyCtor = false, HasCopyAssign = true, HasDtor = false,
 657        HasPreIncrOp = false, HasPostIncrOp = false, HasDerefOp = false;
 658   for (const auto *Method : CRD->methods()) {
 659     if (const auto *Ctor = dyn_cast<CXXConstructorDecl>(Method)) {
 660       if (Ctor->isCopyConstructor()) {
 661         HasCopyCtor = !Ctor->isDeleted() && Ctor->getAccess() == AS_public;
 662       }
 663       continue;
 664     }
 665     if (const auto *Dtor = dyn_cast<CXXDestructorDecl>(Method)) {
 666       HasDtor = !Dtor->isDeleted() && Dtor->getAccess() == AS_public;
 667       continue;
 668     }
 669     if (Method->isCopyAssignmentOperator()) {
 670       HasCopyAssign = !Method->isDeleted() && Method->getAccess() == AS_public;
 671       continue;
 672     }
 673     if (!Method->isOverloadedOperator())
 674       continue;
 675     const auto OPK = Method->getOverloadedOperator();
 676     if (OPK == OO_PlusPlus) {
 677       HasPreIncrOp = HasPreIncrOp || (Method->getNumParams() == 0);
 678       HasPostIncrOp = HasPostIncrOp || (Method->getNumParams() == 1);
 679       continue;
 680     }
 681     if (OPK == OO_Star) {
 682       HasDerefOp = (Method->getNumParams() == 0);
 683       continue;
 684     }
 685   }
 686
 687   return HasCopyCtor && HasCopyAssign && HasDtor && HasPreIncrOp &&
 688          HasPostIncrOp && HasDerefOp;
 689 }
 690
 691 bool isEndCall(const FunctionDecl *Func) {
 692   const auto *IdInfo = Func->getIdentifier();
 693   if (!IdInfo)
 694     return false;
 695   return IdInfo->getName().endswith_lower("end");
 696 }
 697
 698 bool isSimpleComparisonOperator(OverloadedOperatorKind OK) {
 699   return OK == OO_EqualEqual || OK == OO_ExclaimEqual;
 700 }
 701
 702 bool isAccessOperator(OverloadedOperatorKind OK) {
 703   return OK == OO_Star || OK == OO_Arrow || OK == OO_ArrowStar ||
 704          OK == OO_Plus || OK == OO_PlusEqual || OK == OO_PlusPlus ||
 705          OK == OO_Subscript;
 706 }
 707
 708 bool isDecrementOperator(OverloadedOperatorKind OK) {
 709   return OK == OO_MinusEqual || OK == OO_MinusMinus;
 710 }
 711
 712 BinaryOperator::Opcode getOpcode(const SymExpr *SE) {
 713   if (const auto *BSE = dyn_cast<BinarySymExpr>(SE)) {
 714     return BSE->getOpcode();
 715   } else if (const auto *SC = dyn_cast<SymbolConjured>(SE)) {
 716     const auto *COE = dyn_cast<CXXOperatorCallExpr>(SC->getStmt());
 717     if (!COE)
 718       return BO_Comma; // Extremal value, neither EQ nor NE
 719     if (COE->getOperator() == OO_EqualEqual) {
 720       return BO_EQ;
 721     } else if (COE->getOperator() == OO_ExclaimEqual) {
 722       return BO_NE;
 723     }
 724     return BO_Comma; // Extremal value, neither EQ nor NE
 725   }
 726   return BO_Comma; // Extremal value, neither EQ nor NE
 727 }
 728
 729 const RegionOrSymbol getRegionOrSymbol(const SVal &Val) {
 730   if (const auto Reg = Val.getAsRegion()) {
 731     return Reg;
 732   } else if (const auto Sym = Val.getAsSymbol()) {
 733     return Sym;
 734   } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
 735     return LCVal->getRegion();
 736   }
 737   return RegionOrSymbol();
 738 }
 739
 740 const ProgramStateRef processComparison(ProgramStateRef State,
 741                                         RegionOrSymbol LVal,
 742                                         RegionOrSymbol RVal, bool Equal) {
 743   const auto *LPos = getIteratorPosition(State, LVal);
 744   const auto *RPos = getIteratorPosition(State, RVal);
 745   if (LPos && !RPos) {
 746     State = adjustIteratorPosition(State, RVal, *LPos, Equal);
 747   } else if (!LPos && RPos) {
 748     State = adjustIteratorPosition(State, LVal, *RPos, Equal);
 749   } else if (LPos && RPos) {
 750     if (contradictingIteratorPositions(*LPos, *RPos, Equal)) {
 751       return nullptr;
 752     }
 753   }
 754   return State;
 755 }
 756
 757 const ProgramStateRef saveComparison(ProgramStateRef State,
 758                                      const SymExpr *Condition, const SVal &LVal,
 759                                      const SVal &RVal, bool Eq) {
 760   const auto Left = getRegionOrSymbol(LVal);
 761   const auto Right = getRegionOrSymbol(RVal);
 762   if (!Left || !Right)
 763     return State;
 764   return State->set<IteratorComparisonMap>(Condition,
 765                                            IteratorComparison(Left, Right, Eq));
 766 }
 767
 768 const IteratorComparison *loadComparison(ProgramStateRef State,
 769                                          const SymExpr *Condition) {
 770   return State->get<IteratorComparisonMap>(Condition);
 771 }
 772
 773 const IteratorPosition *getIteratorPosition(ProgramStateRef State,
 774                                             const SVal &Val) {
 775   if (const auto Reg = Val.getAsRegion()) {
 776     return State->get<IteratorRegionMap>(Reg);
 777   } else if (const auto Sym = Val.getAsSymbol()) {
 778     return State->get<IteratorSymbolMap>(Sym);
 779   } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
 780     return State->get<IteratorRegionMap>(LCVal->getRegion());
 781   }
 782   return nullptr;
 783 }
 784
 785 const IteratorPosition *getIteratorPosition(ProgramStateRef State,
 786                                             RegionOrSymbol RegOrSym) {
 787   if (RegOrSym.is<const MemRegion *>()) {
 788     return State->get<IteratorRegionMap>(RegOrSym.get<const MemRegion *>());
 789   } else if (RegOrSym.is<SymbolRef>()) {
 790     return State->get<IteratorSymbolMap>(RegOrSym.get<SymbolRef>());
 791   }
 792   return nullptr;
 793 }
 794
 795 ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val,
 796                                     IteratorPosition Pos) {
 797   if (const auto Reg = Val.getAsRegion()) {
 798     return State->set<IteratorRegionMap>(Reg, Pos);
 799   } else if (const auto Sym = Val.getAsSymbol()) {
 800     return State->set<IteratorSymbolMap>(Sym, Pos);
 801   } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
 802     return State->set<IteratorRegionMap>(LCVal->getRegion(), Pos);
 803   }
 804   return nullptr;
 805 }
 806
 807 ProgramStateRef setIteratorPosition(ProgramStateRef State,
 808                                     RegionOrSymbol RegOrSym,
 809                                     IteratorPosition Pos) {
 810   if (RegOrSym.is<const MemRegion *>()) {
 811     return State->set<IteratorRegionMap>(RegOrSym.get<const MemRegion *>(),
 812                                          Pos);
 813   } else if (RegOrSym.is<SymbolRef>()) {
 814     return State->set<IteratorSymbolMap>(RegOrSym.get<SymbolRef>(), Pos);
 815   }
 816   return nullptr;
 817 }
 818
 819 ProgramStateRef adjustIteratorPosition(ProgramStateRef State,
 820                                        RegionOrSymbol RegOrSym,
 821                                        IteratorPosition Pos, bool Equal) {
 822
 823   if ((Pos.isInRange() && Equal) || (Pos.isOutofRange() && !Equal)) {
 824     return setIteratorPosition(State, RegOrSym, IteratorPosition::getInRange());
 825   } else if (Pos.isOutofRange() && Equal) {
 826     return setIteratorPosition(State, RegOrSym,
 827                                IteratorPosition::getOutofRange());
 828   } else {
 829     return State;
 830   }
 831 }
 832
 833 bool contradictingIteratorPositions(IteratorPosition Pos1,
 834                                     IteratorPosition Pos2, bool Equal) {
 835   return ((Pos1 != Pos2) && Equal) ||
 836          ((Pos1.isOutofRange() && Pos2.isOutofRange()) && !Equal);
 837 }
 838 }
 839
 840 void ento::registerIteratorPastEndChecker(CheckerManager &Mgr) {
 841   Mgr.registerChecker<IteratorPastEndChecker>();
 842 }