contrib/llvm-project/clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp

   1 //===-- IteratorModeling.cpp --------------------------------------*- C++ -*--//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // Defines a checker for using iterators outside their range (past end). Usage
  10 // means here dereferencing, incrementing etc.
  11 //
  12 //===----------------------------------------------------------------------===//
  13 //
  14 // In the code, iterator can be represented as a:
  15 // * type-I: typedef-ed pointer. Operations over such iterator, such as
  16 //           comparisons or increments, are modeled straightforwardly by the
  17 //           analyzer.
  18 // * type-II: structure with its method bodies available.  Operations over such
  19 //            iterator are inlined by the analyzer, and results of modeling
  20 //            these operations are exposing implementation details of the
  21 //            iterators, which is not necessarily helping.
  22 // * type-III: completely opaque structure. Operations over such iterator are
  23 //             modeled conservatively, producing conjured symbols everywhere.
  24 //
  25 // To handle all these types in a common way we introduce a structure called
  26 // IteratorPosition which is an abstraction of the position the iterator
  27 // represents using symbolic expressions. The checker handles all the
  28 // operations on this structure.
  29 //
  30 // Additionally, depending on the circumstances, operators of types II and III
  31 // can be represented as:
  32 // * type-IIa, type-IIIa: conjured structure symbols - when returned by value
  33 //                        from conservatively evaluated methods such as
  34 //                        `.begin()`.
  35 // * type-IIb, type-IIIb: memory regions of iterator-typed objects, such as
  36 //                        variables or temporaries, when the iterator object is
  37 //                        currently treated as an lvalue.
  38 // * type-IIc, type-IIIc: compound values of iterator-typed objects, when the
  39 //                        iterator object is treated as an rvalue taken of a
  40 //                        particular lvalue, eg. a copy of "type-a" iterator
  41 //                        object, or an iterator that existed before the
  42 //                        analysis has started.
  43 //
  44 // To handle any of these three different representations stored in an SVal we
  45 // use setter and getters functions which separate the three cases. To store
  46 // them we use a pointer union of symbol and memory region.
  47 //
  48 // The checker works the following way: We record the begin and the
  49 // past-end iterator for all containers whenever their `.begin()` and `.end()`
  50 // are called. Since the Constraint Manager cannot handle such SVals we need
  51 // to take over its role. We post-check equality and non-equality comparisons
  52 // and record that the two sides are equal if we are in the 'equal' branch
  53 // (true-branch for `==` and false-branch for `!=`).
  54 //
  55 // In case of type-I or type-II iterators we get a concrete integer as a result
  56 // of the comparison (1 or 0) but in case of type-III we only get a Symbol. In
  57 // this latter case we record the symbol and reload it in evalAssume() and do
  58 // the propagation there. We also handle (maybe double) negated comparisons
  59 // which are represented in the form of (x == 0 or x != 0) where x is the
  60 // comparison itself.
  61 //
  62 // Since `SimpleConstraintManager` cannot handle complex symbolic expressions
  63 // we only use expressions of the format S, S+n or S-n for iterator positions
  64 // where S is a conjured symbol and n is an unsigned concrete integer. When
  65 // making an assumption e.g. `S1 + n == S2 + m` we store `S1 - S2 == m - n` as
  66 // a constraint which we later retrieve when doing an actual comparison.
  67
  68 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
  69 #include "clang/AST/DeclTemplate.h"
  70 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
  71 #include "clang/StaticAnalyzer/Core/Checker.h"
  72 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
  73 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
  74 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h"
  75
  76 #include "Iterator.h"
  77
  78 #include <utility>
  79
  80 using namespace clang;
  81 using namespace ento;
  82 using namespace iterator;
  83
  84 namespace {
  85
  86 class IteratorModeling
  87     : public Checker<check::PostCall, check::PostStmt<MaterializeTemporaryExpr>,
  88                      check::Bind, check::LiveSymbols, check::DeadSymbols> {
  89
  90   void handleComparison(CheckerContext &C, const Expr *CE, SVal RetVal,
  91                         const SVal &LVal, const SVal &RVal,
  92                         OverloadedOperatorKind Op) const;
  93   void processComparison(CheckerContext &C, ProgramStateRef State,
  94                          SymbolRef Sym1, SymbolRef Sym2, const SVal &RetVal,
  95                          OverloadedOperatorKind Op) const;
  96   void handleIncrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter,
  97                        bool Postfix) const;
  98   void handleDecrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter,
  99                        bool Postfix) const;
 100   void handleRandomIncrOrDecr(CheckerContext &C, const Expr *CE,
 101                               OverloadedOperatorKind Op, const SVal &RetVal,
 102                               const SVal &LHS, const SVal &RHS) const;
 103   void handleBegin(CheckerContext &C, const Expr *CE, const SVal &RetVal,
 104                    const SVal &Cont) const;
 105   void handleEnd(CheckerContext &C, const Expr *CE, const SVal &RetVal,
 106                  const SVal &Cont) const;
 107   void assignToContainer(CheckerContext &C, const Expr *CE, const SVal &RetVal,
 108                          const MemRegion *Cont) const;
 109   void handleAssign(CheckerContext &C, const SVal &Cont,
 110                     const Expr *CE = nullptr,
 111                     const SVal &OldCont = UndefinedVal()) const;
 112   void handleClear(CheckerContext &C, const SVal &Cont) const;
 113   void handlePushBack(CheckerContext &C, const SVal &Cont) const;
 114   void handlePopBack(CheckerContext &C, const SVal &Cont) const;
 115   void handlePushFront(CheckerContext &C, const SVal &Cont) const;
 116   void handlePopFront(CheckerContext &C, const SVal &Cont) const;
 117   void handleInsert(CheckerContext &C, const SVal &Iter) const;
 118   void handleErase(CheckerContext &C, const SVal &Iter) const;
 119   void handleErase(CheckerContext &C, const SVal &Iter1,
 120                    const SVal &Iter2) const;
 121   void handleEraseAfter(CheckerContext &C, const SVal &Iter) const;
 122   void handleEraseAfter(CheckerContext &C, const SVal &Iter1,
 123                         const SVal &Iter2) const;
 124   void printState(raw_ostream &Out, ProgramStateRef State, const char *NL,
 125                   const char *Sep) const override;
 126
 127 public:
 128   IteratorModeling() {}
 129
 130   void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
 131   void checkBind(SVal Loc, SVal Val, const Stmt *S, CheckerContext &C) const;
 132   void checkPostStmt(const CXXConstructExpr *CCE, CheckerContext &C) const;
 133   void checkPostStmt(const DeclStmt *DS, CheckerContext &C) const;
 134   void checkPostStmt(const MaterializeTemporaryExpr *MTE,
 135                      CheckerContext &C) const;
 136   void checkLiveSymbols(ProgramStateRef State, SymbolReaper &SR) const;
 137   void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
 138 };
 139
 140 bool isBeginCall(const FunctionDecl *Func);
 141 bool isEndCall(const FunctionDecl *Func);
 142 bool isAssignCall(const FunctionDecl *Func);
 143 bool isClearCall(const FunctionDecl *Func);
 144 bool isPushBackCall(const FunctionDecl *Func);
 145 bool isEmplaceBackCall(const FunctionDecl *Func);
 146 bool isPopBackCall(const FunctionDecl *Func);
 147 bool isPushFrontCall(const FunctionDecl *Func);
 148 bool isEmplaceFrontCall(const FunctionDecl *Func);
 149 bool isPopFrontCall(const FunctionDecl *Func);
 150 bool isAssignmentOperator(OverloadedOperatorKind OK);
 151 bool isSimpleComparisonOperator(OverloadedOperatorKind OK);
 152 bool hasSubscriptOperator(ProgramStateRef State, const MemRegion *Reg);
 153 bool frontModifiable(ProgramStateRef State, const MemRegion *Reg);
 154 bool backModifiable(ProgramStateRef State, const MemRegion *Reg);
 155 SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont);
 156 SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont);
 157 ProgramStateRef createContainerBegin(ProgramStateRef State,
 158                                      const MemRegion *Cont, const Expr *E,
 159                                      QualType T, const LocationContext *LCtx,
 160                                      unsigned BlockCount);
 161 ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont,
 162                                    const Expr *E, QualType T,
 163                                    const LocationContext *LCtx,
 164                                    unsigned BlockCount);
 165 ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont,
 166                                  const ContainerData &CData);
 167 ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val);
 168 ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym,
 169                                  long Scale);
 170 ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State,
 171                                                const MemRegion *Cont);
 172 ProgramStateRef
 173 invalidateAllIteratorPositionsExcept(ProgramStateRef State,
 174                                      const MemRegion *Cont, SymbolRef Offset,
 175                                      BinaryOperator::Opcode Opc);
 176 ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
 177                                             SymbolRef Offset,
 178                                             BinaryOperator::Opcode Opc);
 179 ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
 180                                             SymbolRef Offset1,
 181                                             BinaryOperator::Opcode Opc1,
 182                                             SymbolRef Offset2,
 183                                             BinaryOperator::Opcode Opc2);
 184 ProgramStateRef reassignAllIteratorPositions(ProgramStateRef State,
 185                                              const MemRegion *Cont,
 186                                              const MemRegion *NewCont);
 187 ProgramStateRef reassignAllIteratorPositionsUnless(ProgramStateRef State,
 188                                                    const MemRegion *Cont,
 189                                                    const MemRegion *NewCont,
 190                                                    SymbolRef Offset,
 191                                                    BinaryOperator::Opcode Opc);
 192 ProgramStateRef rebaseSymbolInIteratorPositionsIf(
 193     ProgramStateRef State, SValBuilder &SVB, SymbolRef OldSym,
 194     SymbolRef NewSym, SymbolRef CondSym, BinaryOperator::Opcode Opc);
 195 ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1,
 196                               SymbolRef Sym2, bool Equal);
 197 SymbolRef rebaseSymbol(ProgramStateRef State, SValBuilder &SVB, SymbolRef Expr,
 198                         SymbolRef OldSym, SymbolRef NewSym);
 199 bool hasLiveIterators(ProgramStateRef State, const MemRegion *Cont);
 200 bool isBoundThroughLazyCompoundVal(const Environment &Env,
 201                                    const MemRegion *Reg);
 202
 203 } // namespace
 204
 205 void IteratorModeling::checkPostCall(const CallEvent &Call,
 206                                      CheckerContext &C) const {
 207   // Record new iterator positions and iterator position changes
 208   const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
 209   if (!Func)
 210     return;
 211
 212   if (Func->isOverloadedOperator()) {
 213     const auto Op = Func->getOverloadedOperator();
 214     if (isAssignmentOperator(Op)) {
 215       // Overloaded 'operator=' must be a non-static member function.
 216       const auto *InstCall = cast<CXXInstanceCall>(&Call);
 217       if (cast<CXXMethodDecl>(Func)->isMoveAssignmentOperator()) {
 218         handleAssign(C, InstCall->getCXXThisVal(), Call.getOriginExpr(),
 219                      Call.getArgSVal(0));
 220         return;
 221       }
 222
 223       handleAssign(C, InstCall->getCXXThisVal());
 224       return;
 225     } else if (isSimpleComparisonOperator(Op)) {
 226       const auto *OrigExpr = Call.getOriginExpr();
 227       if (!OrigExpr)
 228         return;
 229
 230       if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
 231         handleComparison(C, OrigExpr, Call.getReturnValue(),
 232                          InstCall->getCXXThisVal(), Call.getArgSVal(0), Op);
 233         return;
 234       }
 235
 236       handleComparison(C, OrigExpr, Call.getReturnValue(), Call.getArgSVal(0),
 237                          Call.getArgSVal(1), Op);
 238       return;
 239     } else if (isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) {
 240       const auto *OrigExpr = Call.getOriginExpr();
 241       if (!OrigExpr)
 242         return;
 243
 244       if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
 245         if (Call.getNumArgs() >= 1 &&
 246               Call.getArgExpr(0)->getType()->isIntegralOrEnumerationType()) {
 247           handleRandomIncrOrDecr(C, OrigExpr, Func->getOverloadedOperator(),
 248                                  Call.getReturnValue(),
 249                                  InstCall->getCXXThisVal(), Call.getArgSVal(0));
 250           return;
 251         }
 252       } else {
 253         if (Call.getNumArgs() >= 2 &&
 254               Call.getArgExpr(1)->getType()->isIntegralOrEnumerationType()) {
 255           handleRandomIncrOrDecr(C, OrigExpr, Func->getOverloadedOperator(),
 256                                  Call.getReturnValue(), Call.getArgSVal(0),
 257                                  Call.getArgSVal(1));
 258           return;
 259         }
 260       }
 261     } else if (isIncrementOperator(Func->getOverloadedOperator())) {
 262       if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
 263         handleIncrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(),
 264                         Call.getNumArgs());
 265         return;
 266       }
 267
 268       handleIncrement(C, Call.getReturnValue(), Call.getArgSVal(0),
 269                       Call.getNumArgs());
 270       return;
 271     } else if (isDecrementOperator(Func->getOverloadedOperator())) {
 272       if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
 273         handleDecrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(),
 274                         Call.getNumArgs());
 275         return;
 276       }
 277
 278       handleDecrement(C, Call.getReturnValue(), Call.getArgSVal(0),
 279                         Call.getNumArgs());
 280       return;
 281     }
 282   } else {
 283     if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
 284       if (isAssignCall(Func)) {
 285         handleAssign(C, InstCall->getCXXThisVal());
 286         return;
 287       }
 288
 289       if (isClearCall(Func)) {
 290         handleClear(C, InstCall->getCXXThisVal());
 291         return;
 292       }
 293
 294       if (isPushBackCall(Func) || isEmplaceBackCall(Func)) {
 295         handlePushBack(C, InstCall->getCXXThisVal());
 296         return;
 297       }
 298
 299       if (isPopBackCall(Func)) {
 300         handlePopBack(C, InstCall->getCXXThisVal());
 301         return;
 302       }
 303
 304       if (isPushFrontCall(Func) || isEmplaceFrontCall(Func)) {
 305         handlePushFront(C, InstCall->getCXXThisVal());
 306         return;
 307       }
 308
 309       if (isPopFrontCall(Func)) {
 310         handlePopFront(C, InstCall->getCXXThisVal());
 311         return;
 312       }
 313
 314       if (isInsertCall(Func) || isEmplaceCall(Func)) {
 315         handleInsert(C, Call.getArgSVal(0));
 316         return;
 317       }
 318
 319       if (isEraseCall(Func)) {
 320         if (Call.getNumArgs() == 1) {
 321           handleErase(C, Call.getArgSVal(0));
 322           return;
 323         }
 324
 325         if (Call.getNumArgs() == 2) {
 326           handleErase(C, Call.getArgSVal(0), Call.getArgSVal(1));
 327           return;
 328         }
 329       }
 330
 331       if (isEraseAfterCall(Func)) {
 332         if (Call.getNumArgs() == 1) {
 333           handleEraseAfter(C, Call.getArgSVal(0));
 334           return;
 335         }
 336
 337         if (Call.getNumArgs() == 2) {
 338           handleEraseAfter(C, Call.getArgSVal(0), Call.getArgSVal(1));
 339           return;
 340         }
 341       }
 342     }
 343
 344     const auto *OrigExpr = Call.getOriginExpr();
 345     if (!OrigExpr)
 346       return;
 347
 348     if (!isIteratorType(Call.getResultType()))
 349       return;
 350
 351     auto State = C.getState();
 352
 353     if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
 354       if (isBeginCall(Func)) {
 355         handleBegin(C, OrigExpr, Call.getReturnValue(),
 356                     InstCall->getCXXThisVal());
 357         return;
 358       }
 359
 360       if (isEndCall(Func)) {
 361         handleEnd(C, OrigExpr, Call.getReturnValue(),
 362                   InstCall->getCXXThisVal());
 363         return;
 364       }
 365     }
 366
 367     // Already bound to container?
 368     if (getIteratorPosition(State, Call.getReturnValue()))
 369       return;
 370
 371     // Copy-like and move constructors
 372     if (isa<CXXConstructorCall>(&Call) && Call.getNumArgs() == 1) {
 373       if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(0))) {
 374         State = setIteratorPosition(State, Call.getReturnValue(), *Pos);
 375         if (cast<CXXConstructorDecl>(Func)->isMoveConstructor()) {
 376           State = removeIteratorPosition(State, Call.getArgSVal(0));
 377         }
 378         C.addTransition(State);
 379         return;
 380       }
 381     }
 382
 383     // Assumption: if return value is an iterator which is not yet bound to a
 384     //             container, then look for the first iterator argument, and
 385     //             bind the return value to the same container. This approach
 386     //             works for STL algorithms.
 387     // FIXME: Add a more conservative mode
 388     for (unsigned i = 0; i < Call.getNumArgs(); ++i) {
 389       if (isIteratorType(Call.getArgExpr(i)->getType())) {
 390         if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(i))) {
 391           assignToContainer(C, OrigExpr, Call.getReturnValue(),
 392                             Pos->getContainer());
 393           return;
 394         }
 395       }
 396     }
 397   }
 398 }
 399
 400 void IteratorModeling::checkBind(SVal Loc, SVal Val, const Stmt *S,
 401                                  CheckerContext &C) const {
 402   auto State = C.getState();
 403   const auto *Pos = getIteratorPosition(State, Val);
 404   if (Pos) {
 405     State = setIteratorPosition(State, Loc, *Pos);
 406     C.addTransition(State);
 407   } else {
 408     const auto *OldPos = getIteratorPosition(State, Loc);
 409     if (OldPos) {
 410       State = removeIteratorPosition(State, Loc);
 411       C.addTransition(State);
 412     }
 413   }
 414 }
 415
 416 void IteratorModeling::checkPostStmt(const MaterializeTemporaryExpr *MTE,
 417                                      CheckerContext &C) const {
 418   /* Transfer iterator state to temporary objects */
 419   auto State = C.getState();
 420   const auto *Pos = getIteratorPosition(State, C.getSVal(MTE->getSubExpr()));
 421   if (!Pos)
 422     return;
 423   State = setIteratorPosition(State, C.getSVal(MTE), *Pos);
 424   C.addTransition(State);
 425 }
 426
 427 void IteratorModeling::checkLiveSymbols(ProgramStateRef State,
 428                                         SymbolReaper &SR) const {
 429   // Keep symbolic expressions of iterator positions, container begins and ends
 430   // alive
 431   auto RegionMap = State->get<IteratorRegionMap>();
 432   for (const auto &Reg : RegionMap) {
 433     const auto Offset = Reg.second.getOffset();
 434     for (auto i = Offset->symbol_begin(); i != Offset->symbol_end(); ++i)
 435       if (isa<SymbolData>(*i))
 436         SR.markLive(*i);
 437   }
 438
 439   auto SymbolMap = State->get<IteratorSymbolMap>();
 440   for (const auto &Sym : SymbolMap) {
 441     const auto Offset = Sym.second.getOffset();
 442     for (auto i = Offset->symbol_begin(); i != Offset->symbol_end(); ++i)
 443       if (isa<SymbolData>(*i))
 444         SR.markLive(*i);
 445   }
 446
 447   auto ContMap = State->get<ContainerMap>();
 448   for (const auto &Cont : ContMap) {
 449     const auto CData = Cont.second;
 450     if (CData.getBegin()) {
 451       SR.markLive(CData.getBegin());
 452       if(const auto *SIE = dyn_cast<SymIntExpr>(CData.getBegin()))
 453         SR.markLive(SIE->getLHS());
 454     }
 455     if (CData.getEnd()) {
 456       SR.markLive(CData.getEnd());
 457       if(const auto *SIE = dyn_cast<SymIntExpr>(CData.getEnd()))
 458         SR.markLive(SIE->getLHS());
 459     }
 460   }
 461 }
 462
 463 void IteratorModeling::checkDeadSymbols(SymbolReaper &SR,
 464                                         CheckerContext &C) const {
 465   // Cleanup
 466   auto State = C.getState();
 467
 468   auto RegionMap = State->get<IteratorRegionMap>();
 469   for (const auto &Reg : RegionMap) {
 470     if (!SR.isLiveRegion(Reg.first)) {
 471       // The region behind the `LazyCompoundVal` is often cleaned up before
 472       // the `LazyCompoundVal` itself. If there are iterator positions keyed
 473       // by these regions their cleanup must be deferred.
 474       if (!isBoundThroughLazyCompoundVal(State->getEnvironment(), Reg.first)) {
 475         State = State->remove<IteratorRegionMap>(Reg.first);
 476       }
 477     }
 478   }
 479
 480   auto SymbolMap = State->get<IteratorSymbolMap>();
 481   for (const auto &Sym : SymbolMap) {
 482     if (!SR.isLive(Sym.first)) {
 483       State = State->remove<IteratorSymbolMap>(Sym.first);
 484     }
 485   }
 486
 487   auto ContMap = State->get<ContainerMap>();
 488   for (const auto &Cont : ContMap) {
 489     if (!SR.isLiveRegion(Cont.first)) {
 490       // We must keep the container data while it has live iterators to be able
 491       // to compare them to the begin and the end of the container.
 492       if (!hasLiveIterators(State, Cont.first)) {
 493         State = State->remove<ContainerMap>(Cont.first);
 494       }
 495     }
 496   }
 497
 498   C.addTransition(State);
 499 }
 500
 501 void IteratorModeling::handleComparison(CheckerContext &C, const Expr *CE,
 502                                        SVal RetVal, const SVal &LVal,
 503                                        const SVal &RVal,
 504                                        OverloadedOperatorKind Op) const {
 505   // Record the operands and the operator of the comparison for the next
 506   // evalAssume, if the result is a symbolic expression. If it is a concrete
 507   // value (only one branch is possible), then transfer the state between
 508   // the operands according to the operator and the result
 509    auto State = C.getState();
 510   const auto *LPos = getIteratorPosition(State, LVal);
 511   const auto *RPos = getIteratorPosition(State, RVal);
 512   const MemRegion *Cont = nullptr;
 513   if (LPos) {
 514     Cont = LPos->getContainer();
 515   } else if (RPos) {
 516     Cont = RPos->getContainer();
 517   }
 518   if (!Cont)
 519     return;
 520
 521   // At least one of the iterators have recorded positions. If one of them has
 522   // not then create a new symbol for the offset.
 523   SymbolRef Sym;
 524   if (!LPos || !RPos) {
 525     auto &SymMgr = C.getSymbolManager();
 526     Sym = SymMgr.conjureSymbol(CE, C.getLocationContext(),
 527                                C.getASTContext().LongTy, C.blockCount());
 528     State = assumeNoOverflow(State, Sym, 4);
 529   }
 530
 531   if (!LPos) {
 532     State = setIteratorPosition(State, LVal,
 533                                 IteratorPosition::getPosition(Cont, Sym));
 534     LPos = getIteratorPosition(State, LVal);
 535   } else if (!RPos) {
 536     State = setIteratorPosition(State, RVal,
 537                                 IteratorPosition::getPosition(Cont, Sym));
 538     RPos = getIteratorPosition(State, RVal);
 539   }
 540
 541   // We cannot make assumpotions on `UnknownVal`. Let us conjure a symbol
 542   // instead.
 543   if (RetVal.isUnknown()) {
 544     auto &SymMgr = C.getSymbolManager();
 545     auto *LCtx = C.getLocationContext();
 546     RetVal = nonloc::SymbolVal(SymMgr.conjureSymbol(
 547         CE, LCtx, C.getASTContext().BoolTy, C.blockCount()));
 548     State = State->BindExpr(CE, LCtx, RetVal);
 549   }
 550
 551   processComparison(C, State, LPos->getOffset(), RPos->getOffset(), RetVal, Op);
 552 }
 553
 554 void IteratorModeling::processComparison(CheckerContext &C,
 555                                          ProgramStateRef State, SymbolRef Sym1,
 556                                          SymbolRef Sym2, const SVal &RetVal,
 557                                          OverloadedOperatorKind Op) const {
 558   if (const auto TruthVal = RetVal.getAs<nonloc::ConcreteInt>()) {
 559     if ((State = relateSymbols(State, Sym1, Sym2,
 560                               (Op == OO_EqualEqual) ==
 561                                (TruthVal->getValue() != 0)))) {
 562       C.addTransition(State);
 563     } else {
 564       C.generateSink(State, C.getPredecessor());
 565     }
 566     return;
 567   }
 568
 569   const auto ConditionVal = RetVal.getAs<DefinedSVal>();
 570   if (!ConditionVal)
 571     return;
 572
 573   if (auto StateTrue = relateSymbols(State, Sym1, Sym2, Op == OO_EqualEqual)) {
 574     StateTrue = StateTrue->assume(*ConditionVal, true);
 575     C.addTransition(StateTrue);
 576   }
 577
 578   if (auto StateFalse = relateSymbols(State, Sym1, Sym2, Op != OO_EqualEqual)) {
 579     StateFalse = StateFalse->assume(*ConditionVal, false);
 580     C.addTransition(StateFalse);
 581   }
 582 }
 583
 584 void IteratorModeling::handleIncrement(CheckerContext &C, const SVal &RetVal,
 585                                        const SVal &Iter, bool Postfix) const {
 586   // Increment the symbolic expressions which represents the position of the
 587   // iterator
 588   auto State = C.getState();
 589   auto &BVF = C.getSymbolManager().getBasicVals();
 590
 591   const auto *Pos = getIteratorPosition(State, Iter);
 592   if (!Pos)
 593     return;
 594
 595   auto NewState =
 596     advancePosition(State, Iter, OO_Plus,
 597                     nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
 598   assert(NewState &&
 599          "Advancing position by concrete int should always be successful");
 600
 601   const auto *NewPos = getIteratorPosition(NewState, Iter);
 602   assert(NewPos &&
 603          "Iterator should have position after successful advancement");
 604
 605   State = setIteratorPosition(State, Iter, *NewPos);
 606   State = setIteratorPosition(State, RetVal, Postfix ? *Pos : *NewPos);
 607   C.addTransition(State);
 608 }
 609
 610 void IteratorModeling::handleDecrement(CheckerContext &C, const SVal &RetVal,
 611                                        const SVal &Iter, bool Postfix) const {
 612   // Decrement the symbolic expressions which represents the position of the
 613   // iterator
 614   auto State = C.getState();
 615   auto &BVF = C.getSymbolManager().getBasicVals();
 616
 617   const auto *Pos = getIteratorPosition(State, Iter);
 618   if (!Pos)
 619     return;
 620
 621   auto NewState =
 622     advancePosition(State, Iter, OO_Minus,
 623                     nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
 624   assert(NewState &&
 625          "Advancing position by concrete int should always be successful");
 626
 627   const auto *NewPos = getIteratorPosition(NewState, Iter);
 628   assert(NewPos &&
 629          "Iterator should have position after successful advancement");
 630
 631   State = setIteratorPosition(State, Iter, *NewPos);
 632   State = setIteratorPosition(State, RetVal, Postfix ? *Pos : *NewPos);
 633   C.addTransition(State);
 634 }
 635
 636 void IteratorModeling::handleRandomIncrOrDecr(CheckerContext &C,
 637                                               const Expr *CE,
 638                                               OverloadedOperatorKind Op,
 639                                               const SVal &RetVal,
 640                                               const SVal &LHS,
 641                                               const SVal &RHS) const {
 642   // Increment or decrement the symbolic expressions which represents the
 643   // position of the iterator
 644   auto State = C.getState();
 645
 646   const auto *Pos = getIteratorPosition(State, LHS);
 647   if (!Pos)
 648     return;
 649
 650   const auto *value = &RHS;
 651   if (auto loc = RHS.getAs<Loc>()) {
 652     const auto val = State->getRawSVal(*loc);
 653     value = &val;
 654   }
 655
 656   auto &TgtVal = (Op == OO_PlusEqual || Op == OO_MinusEqual) ? LHS : RetVal;
 657
 658   auto NewState =
 659     advancePosition(State, LHS, Op, *value);
 660   if (NewState) {
 661     const auto *NewPos = getIteratorPosition(NewState, LHS);
 662     assert(NewPos &&
 663            "Iterator should have position after successful advancement");
 664
 665     State = setIteratorPosition(NewState, TgtVal, *NewPos);
 666     C.addTransition(State);
 667   } else {
 668     assignToContainer(C, CE, TgtVal, Pos->getContainer());
 669   }
 670 }
 671
 672 void IteratorModeling::handleBegin(CheckerContext &C, const Expr *CE,
 673                                    const SVal &RetVal, const SVal &Cont) const {
 674   const auto *ContReg = Cont.getAsRegion();
 675   if (!ContReg)
 676     return;
 677
 678   ContReg = ContReg->getMostDerivedObjectRegion();
 679
 680   // If the container already has a begin symbol then use it. Otherwise first
 681   // create a new one.
 682   auto State = C.getState();
 683   auto BeginSym = getContainerBegin(State, ContReg);
 684   if (!BeginSym) {
 685     State = createContainerBegin(State, ContReg, CE, C.getASTContext().LongTy,
 686                                  C.getLocationContext(), C.blockCount());
 687     BeginSym = getContainerBegin(State, ContReg);
 688   }
 689   State = setIteratorPosition(State, RetVal,
 690                               IteratorPosition::getPosition(ContReg, BeginSym));
 691   C.addTransition(State);
 692 }
 693
 694 void IteratorModeling::handleEnd(CheckerContext &C, const Expr *CE,
 695                                  const SVal &RetVal, const SVal &Cont) const {
 696   const auto *ContReg = Cont.getAsRegion();
 697   if (!ContReg)
 698     return;
 699
 700   ContReg = ContReg->getMostDerivedObjectRegion();
 701
 702   // If the container already has an end symbol then use it. Otherwise first
 703   // create a new one.
 704   auto State = C.getState();
 705   auto EndSym = getContainerEnd(State, ContReg);
 706   if (!EndSym) {
 707     State = createContainerEnd(State, ContReg, CE, C.getASTContext().LongTy,
 708                                C.getLocationContext(), C.blockCount());
 709     EndSym = getContainerEnd(State, ContReg);
 710   }
 711   State = setIteratorPosition(State, RetVal,
 712                               IteratorPosition::getPosition(ContReg, EndSym));
 713   C.addTransition(State);
 714 }
 715
 716 void IteratorModeling::assignToContainer(CheckerContext &C, const Expr *CE,
 717                                          const SVal &RetVal,
 718                                          const MemRegion *Cont) const {
 719   Cont = Cont->getMostDerivedObjectRegion();
 720
 721   auto State = C.getState();
 722   auto &SymMgr = C.getSymbolManager();
 723   auto Sym = SymMgr.conjureSymbol(CE, C.getLocationContext(),
 724                                   C.getASTContext().LongTy, C.blockCount());
 725   State = assumeNoOverflow(State, Sym, 4);
 726   State = setIteratorPosition(State, RetVal,
 727                               IteratorPosition::getPosition(Cont, Sym));
 728   C.addTransition(State);
 729 }
 730
 731 void IteratorModeling::handleAssign(CheckerContext &C, const SVal &Cont,
 732                                     const Expr *CE, const SVal &OldCont) const {
 733   const auto *ContReg = Cont.getAsRegion();
 734   if (!ContReg)
 735     return;
 736
 737   ContReg = ContReg->getMostDerivedObjectRegion();
 738
 739   // Assignment of a new value to a container always invalidates all its
 740   // iterators
 741   auto State = C.getState();
 742   const auto CData = getContainerData(State, ContReg);
 743   if (CData) {
 744     State = invalidateAllIteratorPositions(State, ContReg);
 745   }
 746
 747   // In case of move, iterators of the old container (except the past-end
 748   // iterators) remain valid but refer to the new container
 749   if (!OldCont.isUndef()) {
 750     const auto *OldContReg = OldCont.getAsRegion();
 751     if (OldContReg) {
 752       OldContReg = OldContReg->getMostDerivedObjectRegion();
 753       const auto OldCData = getContainerData(State, OldContReg);
 754       if (OldCData) {
 755         if (const auto OldEndSym = OldCData->getEnd()) {
 756           // If we already assigned an "end" symbol to the old container, then
 757           // first reassign all iterator positions to the new container which
 758           // are not past the container (thus not greater or equal to the
 759           // current "end" symbol).
 760           State = reassignAllIteratorPositionsUnless(State, OldContReg, ContReg,
 761                                                      OldEndSym, BO_GE);
 762           auto &SymMgr = C.getSymbolManager();
 763           auto &SVB = C.getSValBuilder();
 764           // Then generate and assign a new "end" symbol for the new container.
 765           auto NewEndSym =
 766               SymMgr.conjureSymbol(CE, C.getLocationContext(),
 767                                    C.getASTContext().LongTy, C.blockCount());
 768           State = assumeNoOverflow(State, NewEndSym, 4);
 769           if (CData) {
 770             State = setContainerData(State, ContReg, CData->newEnd(NewEndSym));
 771           } else {
 772             State = setContainerData(State, ContReg,
 773                                      ContainerData::fromEnd(NewEndSym));
 774           }
 775           // Finally, replace the old "end" symbol in the already reassigned
 776           // iterator positions with the new "end" symbol.
 777           State = rebaseSymbolInIteratorPositionsIf(
 778               State, SVB, OldEndSym, NewEndSym, OldEndSym, BO_LT);
 779         } else {
 780           // There was no "end" symbol assigned yet to the old container,
 781           // so reassign all iterator positions to the new container.
 782           State = reassignAllIteratorPositions(State, OldContReg, ContReg);
 783         }
 784         if (const auto OldBeginSym = OldCData->getBegin()) {
 785           // If we already assigned a "begin" symbol to the old container, then
 786           // assign it to the new container and remove it from the old one.
 787           if (CData) {
 788             State =
 789                 setContainerData(State, ContReg, CData->newBegin(OldBeginSym));
 790           } else {
 791             State = setContainerData(State, ContReg,
 792                                      ContainerData::fromBegin(OldBeginSym));
 793           }
 794           State =
 795               setContainerData(State, OldContReg, OldCData->newEnd(nullptr));
 796         }
 797       } else {
 798         // There was neither "begin" nor "end" symbol assigned yet to the old
 799         // container, so reassign all iterator positions to the new container.
 800         State = reassignAllIteratorPositions(State, OldContReg, ContReg);
 801       }
 802     }
 803   }
 804   C.addTransition(State);
 805 }
 806
 807 void IteratorModeling::handleClear(CheckerContext &C, const SVal &Cont) const {
 808   const auto *ContReg = Cont.getAsRegion();
 809   if (!ContReg)
 810     return;
 811
 812   ContReg = ContReg->getMostDerivedObjectRegion();
 813
 814   // The clear() operation invalidates all the iterators, except the past-end
 815   // iterators of list-like containers
 816   auto State = C.getState();
 817   if (!hasSubscriptOperator(State, ContReg) ||
 818       !backModifiable(State, ContReg)) {
 819     const auto CData = getContainerData(State, ContReg);
 820     if (CData) {
 821       if (const auto EndSym = CData->getEnd()) {
 822         State =
 823             invalidateAllIteratorPositionsExcept(State, ContReg, EndSym, BO_GE);
 824         C.addTransition(State);
 825         return;
 826       }
 827     }
 828   }
 829   State = invalidateAllIteratorPositions(State, ContReg);
 830   C.addTransition(State);
 831 }
 832
 833 void IteratorModeling::handlePushBack(CheckerContext &C,
 834                                       const SVal &Cont) const {
 835   const auto *ContReg = Cont.getAsRegion();
 836   if (!ContReg)
 837     return;
 838
 839   ContReg = ContReg->getMostDerivedObjectRegion();
 840
 841   // For deque-like containers invalidate all iterator positions
 842   auto State = C.getState();
 843   if (hasSubscriptOperator(State, ContReg) && frontModifiable(State, ContReg)) {
 844     State = invalidateAllIteratorPositions(State, ContReg);
 845     C.addTransition(State);
 846     return;
 847   }
 848
 849   const auto CData = getContainerData(State, ContReg);
 850   if (!CData)
 851     return;
 852
 853   // For vector-like containers invalidate the past-end iterator positions
 854   if (const auto EndSym = CData->getEnd()) {
 855     if (hasSubscriptOperator(State, ContReg)) {
 856       State = invalidateIteratorPositions(State, EndSym, BO_GE);
 857     }
 858     auto &SymMgr = C.getSymbolManager();
 859     auto &BVF = SymMgr.getBasicVals();
 860     auto &SVB = C.getSValBuilder();
 861     const auto newEndSym =
 862       SVB.evalBinOp(State, BO_Add,
 863                     nonloc::SymbolVal(EndSym),
 864                     nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
 865                     SymMgr.getType(EndSym)).getAsSymbol();
 866     State = setContainerData(State, ContReg, CData->newEnd(newEndSym));
 867   }
 868   C.addTransition(State);
 869 }
 870
 871 void IteratorModeling::handlePopBack(CheckerContext &C,
 872                                      const SVal &Cont) const {
 873   const auto *ContReg = Cont.getAsRegion();
 874   if (!ContReg)
 875     return;
 876
 877   ContReg = ContReg->getMostDerivedObjectRegion();
 878
 879   auto State = C.getState();
 880   const auto CData = getContainerData(State, ContReg);
 881   if (!CData)
 882     return;
 883
 884   if (const auto EndSym = CData->getEnd()) {
 885     auto &SymMgr = C.getSymbolManager();
 886     auto &BVF = SymMgr.getBasicVals();
 887     auto &SVB = C.getSValBuilder();
 888     const auto BackSym =
 889       SVB.evalBinOp(State, BO_Sub,
 890                     nonloc::SymbolVal(EndSym),
 891                     nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
 892                     SymMgr.getType(EndSym)).getAsSymbol();
 893     // For vector-like and deque-like containers invalidate the last and the
 894     // past-end iterator positions. For list-like containers only invalidate
 895     // the last position
 896     if (hasSubscriptOperator(State, ContReg) &&
 897         backModifiable(State, ContReg)) {
 898       State = invalidateIteratorPositions(State, BackSym, BO_GE);
 899       State = setContainerData(State, ContReg, CData->newEnd(nullptr));
 900     } else {
 901       State = invalidateIteratorPositions(State, BackSym, BO_EQ);
 902     }
 903     auto newEndSym = BackSym;
 904     State = setContainerData(State, ContReg, CData->newEnd(newEndSym));
 905     C.addTransition(State);
 906   }
 907 }
 908
 909 void IteratorModeling::handlePushFront(CheckerContext &C,
 910                                        const SVal &Cont) const {
 911   const auto *ContReg = Cont.getAsRegion();
 912   if (!ContReg)
 913     return;
 914
 915   ContReg = ContReg->getMostDerivedObjectRegion();
 916
 917   // For deque-like containers invalidate all iterator positions
 918   auto State = C.getState();
 919   if (hasSubscriptOperator(State, ContReg)) {
 920     State = invalidateAllIteratorPositions(State, ContReg);
 921     C.addTransition(State);
 922   } else {
 923     const auto CData = getContainerData(State, ContReg);
 924     if (!CData)
 925       return;
 926
 927     if (const auto BeginSym = CData->getBegin()) {
 928       auto &SymMgr = C.getSymbolManager();
 929       auto &BVF = SymMgr.getBasicVals();
 930       auto &SVB = C.getSValBuilder();
 931       const auto newBeginSym =
 932         SVB.evalBinOp(State, BO_Sub,
 933                       nonloc::SymbolVal(BeginSym),
 934                       nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
 935                       SymMgr.getType(BeginSym)).getAsSymbol();
 936       State = setContainerData(State, ContReg, CData->newBegin(newBeginSym));
 937       C.addTransition(State);
 938     }
 939   }
 940 }
 941
 942 void IteratorModeling::handlePopFront(CheckerContext &C,
 943                                       const SVal &Cont) const {
 944   const auto *ContReg = Cont.getAsRegion();
 945   if (!ContReg)
 946     return;
 947
 948   ContReg = ContReg->getMostDerivedObjectRegion();
 949
 950   auto State = C.getState();
 951   const auto CData = getContainerData(State, ContReg);
 952   if (!CData)
 953     return;
 954
 955   // For deque-like containers invalidate all iterator positions. For list-like
 956   // iterators only invalidate the first position
 957   if (const auto BeginSym = CData->getBegin()) {
 958     if (hasSubscriptOperator(State, ContReg)) {
 959       State = invalidateIteratorPositions(State, BeginSym, BO_LE);
 960     } else {
 961       State = invalidateIteratorPositions(State, BeginSym, BO_EQ);
 962     }
 963     auto &SymMgr = C.getSymbolManager();
 964     auto &BVF = SymMgr.getBasicVals();
 965     auto &SVB = C.getSValBuilder();
 966     const auto newBeginSym =
 967       SVB.evalBinOp(State, BO_Add,
 968                     nonloc::SymbolVal(BeginSym),
 969                     nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
 970                     SymMgr.getType(BeginSym)).getAsSymbol();
 971     State = setContainerData(State, ContReg, CData->newBegin(newBeginSym));
 972     C.addTransition(State);
 973   }
 974 }
 975
 976 void IteratorModeling::handleInsert(CheckerContext &C, const SVal &Iter) const {
 977   auto State = C.getState();
 978   const auto *Pos = getIteratorPosition(State, Iter);
 979   if (!Pos)
 980     return;
 981
 982   // For deque-like containers invalidate all iterator positions. For
 983   // vector-like containers invalidate iterator positions after the insertion.
 984   const auto *Cont = Pos->getContainer();
 985   if (hasSubscriptOperator(State, Cont) && backModifiable(State, Cont)) {
 986     if (frontModifiable(State, Cont)) {
 987       State = invalidateAllIteratorPositions(State, Cont);
 988     } else {
 989       State = invalidateIteratorPositions(State, Pos->getOffset(), BO_GE);
 990     }
 991     if (const auto *CData = getContainerData(State, Cont)) {
 992       if (const auto EndSym = CData->getEnd()) {
 993         State = invalidateIteratorPositions(State, EndSym, BO_GE);
 994         State = setContainerData(State, Cont, CData->newEnd(nullptr));
 995       }
 996     }
 997     C.addTransition(State);
 998   }
 999 }
1000
1001 void IteratorModeling::handleErase(CheckerContext &C, const SVal &Iter) const {
1002   auto State = C.getState();
1003   const auto *Pos = getIteratorPosition(State, Iter);
1004   if (!Pos)
1005     return;
1006
1007   // For deque-like containers invalidate all iterator positions. For
1008   // vector-like containers invalidate iterator positions at and after the
1009   // deletion. For list-like containers only invalidate the deleted position.
1010   const auto *Cont = Pos->getContainer();
1011   if (hasSubscriptOperator(State, Cont) && backModifiable(State, Cont)) {
1012     if (frontModifiable(State, Cont)) {
1013       State = invalidateAllIteratorPositions(State, Cont);
1014     } else {
1015       State = invalidateIteratorPositions(State, Pos->getOffset(), BO_GE);
1016     }
1017     if (const auto *CData = getContainerData(State, Cont)) {
1018       if (const auto EndSym = CData->getEnd()) {
1019         State = invalidateIteratorPositions(State, EndSym, BO_GE);
1020         State = setContainerData(State, Cont, CData->newEnd(nullptr));
1021       }
1022     }
1023   } else {
1024     State = invalidateIteratorPositions(State, Pos->getOffset(), BO_EQ);
1025   }
1026   C.addTransition(State);
1027 }
1028
1029 void IteratorModeling::handleErase(CheckerContext &C, const SVal &Iter1,
1030                                    const SVal &Iter2) const {
1031   auto State = C.getState();
1032   const auto *Pos1 = getIteratorPosition(State, Iter1);
1033   const auto *Pos2 = getIteratorPosition(State, Iter2);
1034   if (!Pos1 || !Pos2)
1035     return;
1036
1037   // For deque-like containers invalidate all iterator positions. For
1038   // vector-like containers invalidate iterator positions at and after the
1039   // deletion range. For list-like containers only invalidate the deleted
1040   // position range [first..last].
1041   const auto *Cont = Pos1->getContainer();
1042   if (hasSubscriptOperator(State, Cont) && backModifiable(State, Cont)) {
1043     if (frontModifiable(State, Cont)) {
1044       State = invalidateAllIteratorPositions(State, Cont);
1045     } else {
1046       State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GE);
1047     }
1048     if (const auto *CData = getContainerData(State, Cont)) {
1049       if (const auto EndSym = CData->getEnd()) {
1050         State = invalidateIteratorPositions(State, EndSym, BO_GE);
1051         State = setContainerData(State, Cont, CData->newEnd(nullptr));
1052       }
1053     }
1054   } else {
1055     State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GE,
1056                                         Pos2->getOffset(), BO_LT);
1057   }
1058   C.addTransition(State);
1059 }
1060
1061 void IteratorModeling::handleEraseAfter(CheckerContext &C,
1062                                         const SVal &Iter) const {
1063   auto State = C.getState();
1064   const auto *Pos = getIteratorPosition(State, Iter);
1065   if (!Pos)
1066     return;
1067
1068   // Invalidate the deleted iterator position, which is the position of the
1069   // parameter plus one.
1070   auto &SymMgr = C.getSymbolManager();
1071   auto &BVF = SymMgr.getBasicVals();
1072   auto &SVB = C.getSValBuilder();
1073   const auto NextSym =
1074     SVB.evalBinOp(State, BO_Add,
1075                   nonloc::SymbolVal(Pos->getOffset()),
1076                   nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
1077                   SymMgr.getType(Pos->getOffset())).getAsSymbol();
1078   State = invalidateIteratorPositions(State, NextSym, BO_EQ);
1079   C.addTransition(State);
1080 }
1081
1082 void IteratorModeling::handleEraseAfter(CheckerContext &C, const SVal &Iter1,
1083                                         const SVal &Iter2) const {
1084   auto State = C.getState();
1085   const auto *Pos1 = getIteratorPosition(State, Iter1);
1086   const auto *Pos2 = getIteratorPosition(State, Iter2);
1087   if (!Pos1 || !Pos2)
1088     return;
1089
1090   // Invalidate the deleted iterator position range (first..last)
1091   State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GT,
1092                                       Pos2->getOffset(), BO_LT);
1093   C.addTransition(State);
1094 }
1095
1096 void IteratorModeling::printState(raw_ostream &Out, ProgramStateRef State,
1097                                   const char *NL, const char *Sep) const {
1098
1099   auto ContMap = State->get<ContainerMap>();
1100
1101   if (!ContMap.isEmpty()) {
1102     Out << Sep << "Container Data :" << NL;
1103     for (const auto &Cont : ContMap) {
1104       Cont.first->dumpToStream(Out);
1105       Out << " : [ ";
1106       const auto CData = Cont.second;
1107       if (CData.getBegin())
1108         CData.getBegin()->dumpToStream(Out);
1109       else
1110         Out << "<Unknown>";
1111       Out << " .. ";
1112       if (CData.getEnd())
1113         CData.getEnd()->dumpToStream(Out);
1114       else
1115         Out << "<Unknown>";
1116       Out << " ]" << NL;
1117     }
1118   }
1119
1120   auto SymbolMap = State->get<IteratorSymbolMap>();
1121   auto RegionMap = State->get<IteratorRegionMap>();
1122
1123   if (!SymbolMap.isEmpty() || !RegionMap.isEmpty()) {
1124     Out << Sep << "Iterator Positions :" << NL;
1125     for (const auto &Sym : SymbolMap) {
1126       Sym.first->dumpToStream(Out);
1127       Out << " : ";
1128       const auto Pos = Sym.second;
1129       Out << (Pos.isValid() ? "Valid" : "Invalid") << " ; Container == ";
1130       Pos.getContainer()->dumpToStream(Out);
1131       Out<<" ; Offset == ";
1132       Pos.getOffset()->dumpToStream(Out);
1133     }
1134
1135     for (const auto &Reg : RegionMap) {
1136       Reg.first->dumpToStream(Out);
1137       Out << " : ";
1138       const auto Pos = Reg.second;
1139       Out << (Pos.isValid() ? "Valid" : "Invalid") << " ; Container == ";
1140       Pos.getContainer()->dumpToStream(Out);
1141       Out<<" ; Offset == ";
1142       Pos.getOffset()->dumpToStream(Out);
1143     }
1144   }
1145 }
1146
1147
1148 namespace {
1149
1150 const CXXRecordDecl *getCXXRecordDecl(ProgramStateRef State,
1151                                       const MemRegion *Reg);
1152
1153 bool isBeginCall(const FunctionDecl *Func) {
1154   const auto *IdInfo = Func->getIdentifier();
1155   if (!IdInfo)
1156     return false;
1157   return IdInfo->getName().endswith_lower("begin");
1158 }
1159
1160 bool isEndCall(const FunctionDecl *Func) {
1161   const auto *IdInfo = Func->getIdentifier();
1162   if (!IdInfo)
1163     return false;
1164   return IdInfo->getName().endswith_lower("end");
1165 }
1166
1167 bool isAssignCall(const FunctionDecl *Func) {
1168   const auto *IdInfo = Func->getIdentifier();
1169   if (!IdInfo)
1170     return false;
1171   if (Func->getNumParams() > 2)
1172     return false;
1173   return IdInfo->getName() == "assign";
1174 }
1175
1176 bool isClearCall(const FunctionDecl *Func) {
1177   const auto *IdInfo = Func->getIdentifier();
1178   if (!IdInfo)
1179     return false;
1180   if (Func->getNumParams() > 0)
1181     return false;
1182   return IdInfo->getName() == "clear";
1183 }
1184
1185 bool isPushBackCall(const FunctionDecl *Func) {
1186   const auto *IdInfo = Func->getIdentifier();
1187   if (!IdInfo)
1188     return false;
1189   if (Func->getNumParams() != 1)
1190     return false;
1191   return IdInfo->getName() == "push_back";
1192 }
1193
1194 bool isEmplaceBackCall(const FunctionDecl *Func) {
1195   const auto *IdInfo = Func->getIdentifier();
1196   if (!IdInfo)
1197     return false;
1198   if (Func->getNumParams() < 1)
1199     return false;
1200   return IdInfo->getName() == "emplace_back";
1201 }
1202
1203 bool isPopBackCall(const FunctionDecl *Func) {
1204   const auto *IdInfo = Func->getIdentifier();
1205   if (!IdInfo)
1206     return false;
1207   if (Func->getNumParams() > 0)
1208     return false;
1209   return IdInfo->getName() == "pop_back";
1210 }
1211
1212 bool isPushFrontCall(const FunctionDecl *Func) {
1213   const auto *IdInfo = Func->getIdentifier();
1214   if (!IdInfo)
1215     return false;
1216   if (Func->getNumParams() != 1)
1217     return false;
1218   return IdInfo->getName() == "push_front";
1219 }
1220
1221 bool isEmplaceFrontCall(const FunctionDecl *Func) {
1222   const auto *IdInfo = Func->getIdentifier();
1223   if (!IdInfo)
1224     return false;
1225   if (Func->getNumParams() < 1)
1226     return false;
1227   return IdInfo->getName() == "emplace_front";
1228 }
1229
1230 bool isPopFrontCall(const FunctionDecl *Func) {
1231   const auto *IdInfo = Func->getIdentifier();
1232   if (!IdInfo)
1233     return false;
1234   if (Func->getNumParams() > 0)
1235     return false;
1236   return IdInfo->getName() == "pop_front";
1237 }
1238
1239 bool isAssignmentOperator(OverloadedOperatorKind OK) { return OK == OO_Equal; }
1240
1241 bool isSimpleComparisonOperator(OverloadedOperatorKind OK) {
1242   return OK == OO_EqualEqual || OK == OO_ExclaimEqual;
1243 }
1244
1245 bool hasSubscriptOperator(ProgramStateRef State, const MemRegion *Reg) {
1246   const auto *CRD = getCXXRecordDecl(State, Reg);
1247   if (!CRD)
1248     return false;
1249
1250   for (const auto *Method : CRD->methods()) {
1251     if (!Method->isOverloadedOperator())
1252       continue;
1253     const auto OPK = Method->getOverloadedOperator();
1254     if (OPK == OO_Subscript) {
1255       return true;
1256     }
1257   }
1258   return false;
1259 }
1260
1261 bool frontModifiable(ProgramStateRef State, const MemRegion *Reg) {
1262   const auto *CRD = getCXXRecordDecl(State, Reg);
1263   if (!CRD)
1264     return false;
1265
1266   for (const auto *Method : CRD->methods()) {
1267     if (!Method->getDeclName().isIdentifier())
1268       continue;
1269     if (Method->getName() == "push_front" || Method->getName() == "pop_front") {
1270       return true;
1271     }
1272   }
1273   return false;
1274 }
1275
1276 bool backModifiable(ProgramStateRef State, const MemRegion *Reg) {
1277   const auto *CRD = getCXXRecordDecl(State, Reg);
1278   if (!CRD)
1279     return false;
1280
1281   for (const auto *Method : CRD->methods()) {
1282     if (!Method->getDeclName().isIdentifier())
1283       continue;
1284     if (Method->getName() == "push_back" || Method->getName() == "pop_back") {
1285       return true;
1286     }
1287   }
1288   return false;
1289 }
1290
1291 const CXXRecordDecl *getCXXRecordDecl(ProgramStateRef State,
1292                                       const MemRegion *Reg) {
1293   auto TI = getDynamicTypeInfo(State, Reg);
1294   if (!TI.isValid())
1295     return nullptr;
1296
1297   auto Type = TI.getType();
1298   if (const auto *RefT = Type->getAs<ReferenceType>()) {
1299     Type = RefT->getPointeeType();
1300   }
1301
1302   return Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl();
1303 }
1304
1305 SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont) {
1306   const auto *CDataPtr = getContainerData(State, Cont);
1307   if (!CDataPtr)
1308     return nullptr;
1309
1310   return CDataPtr->getBegin();
1311 }
1312
1313 SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont) {
1314   const auto *CDataPtr = getContainerData(State, Cont);
1315   if (!CDataPtr)
1316     return nullptr;
1317
1318   return CDataPtr->getEnd();
1319 }
1320
1321 ProgramStateRef createContainerBegin(ProgramStateRef State,
1322                                      const MemRegion *Cont, const Expr *E,
1323                                      QualType T, const LocationContext *LCtx,
1324                                      unsigned BlockCount) {
1325   // Only create if it does not exist
1326   const auto *CDataPtr = getContainerData(State, Cont);
1327   if (CDataPtr && CDataPtr->getBegin())
1328     return State;
1329
1330   auto &SymMgr = State->getSymbolManager();
1331   const SymbolConjured *Sym = SymMgr.conjureSymbol(E, LCtx, T, BlockCount,
1332                                                    "begin");
1333   State = assumeNoOverflow(State, Sym, 4);
1334
1335   if (CDataPtr) {
1336     const auto CData = CDataPtr->newBegin(Sym);
1337     return setContainerData(State, Cont, CData);
1338   }
1339
1340   const auto CData = ContainerData::fromBegin(Sym);
1341   return setContainerData(State, Cont, CData);
1342 }
1343
1344 ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont,
1345                                    const Expr *E, QualType T,
1346                                    const LocationContext *LCtx,
1347                                    unsigned BlockCount) {
1348   // Only create if it does not exist
1349   const auto *CDataPtr = getContainerData(State, Cont);
1350   if (CDataPtr && CDataPtr->getEnd())
1351     return State;
1352
1353   auto &SymMgr = State->getSymbolManager();
1354   const SymbolConjured *Sym = SymMgr.conjureSymbol(E, LCtx, T, BlockCount,
1355                                                   "end");
1356   State = assumeNoOverflow(State, Sym, 4);
1357
1358   if (CDataPtr) {
1359     const auto CData = CDataPtr->newEnd(Sym);
1360     return setContainerData(State, Cont, CData);
1361   }
1362
1363   const auto CData = ContainerData::fromEnd(Sym);
1364   return setContainerData(State, Cont, CData);
1365 }
1366
1367 ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont,
1368                                  const ContainerData &CData) {
1369   return State->set<ContainerMap>(Cont, CData);
1370 }
1371
1372 ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val) {
1373   if (auto Reg = Val.getAsRegion()) {
1374     Reg = Reg->getMostDerivedObjectRegion();
1375     return State->remove<IteratorRegionMap>(Reg);
1376   } else if (const auto Sym = Val.getAsSymbol()) {
1377     return State->remove<IteratorSymbolMap>(Sym);
1378   } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
1379     return State->remove<IteratorRegionMap>(LCVal->getRegion());
1380   }
1381   return nullptr;
1382 }
1383
1384 // This function tells the analyzer's engine that symbols produced by our
1385 // checker, most notably iterator positions, are relatively small.
1386 // A distance between items in the container should not be very large.
1387 // By assuming that it is within around 1/8 of the address space,
1388 // we can help the analyzer perform operations on these symbols
1389 // without being afraid of integer overflows.
1390 // FIXME: Should we provide it as an API, so that all checkers could use it?
1391 ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym,
1392                                  long Scale) {
1393   SValBuilder &SVB = State->getStateManager().getSValBuilder();
1394   BasicValueFactory &BV = SVB.getBasicValueFactory();
1395
1396   QualType T = Sym->getType();
1397   assert(T->isSignedIntegerOrEnumerationType());
1398   APSIntType AT = BV.getAPSIntType(T);
1399
1400   ProgramStateRef NewState = State;
1401
1402   llvm::APSInt Max = AT.getMaxValue() / AT.getValue(Scale);
1403   SVal IsCappedFromAbove =
1404       SVB.evalBinOpNN(State, BO_LE, nonloc::SymbolVal(Sym),
1405                       nonloc::ConcreteInt(Max), SVB.getConditionType());
1406   if (auto DV = IsCappedFromAbove.getAs<DefinedSVal>()) {
1407     NewState = NewState->assume(*DV, true);
1408     if (!NewState)
1409       return State;
1410   }
1411
1412   llvm::APSInt Min = -Max;
1413   SVal IsCappedFromBelow =
1414       SVB.evalBinOpNN(State, BO_GE, nonloc::SymbolVal(Sym),
1415                       nonloc::ConcreteInt(Min), SVB.getConditionType());
1416   if (auto DV = IsCappedFromBelow.getAs<DefinedSVal>()) {
1417     NewState = NewState->assume(*DV, true);
1418     if (!NewState)
1419       return State;
1420   }
1421
1422   return NewState;
1423 }
1424
1425 ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1,
1426                               SymbolRef Sym2, bool Equal) {
1427   auto &SVB = State->getStateManager().getSValBuilder();
1428
1429   // FIXME: This code should be reworked as follows:
1430   // 1. Subtract the operands using evalBinOp().
1431   // 2. Assume that the result doesn't overflow.
1432   // 3. Compare the result to 0.
1433   // 4. Assume the result of the comparison.
1434   const auto comparison =
1435     SVB.evalBinOp(State, BO_EQ, nonloc::SymbolVal(Sym1),
1436                   nonloc::SymbolVal(Sym2), SVB.getConditionType());
1437
1438   assert(comparison.getAs<DefinedSVal>() &&
1439     "Symbol comparison must be a `DefinedSVal`");
1440
1441   auto NewState = State->assume(comparison.castAs<DefinedSVal>(), Equal);
1442   if (!NewState)
1443     return nullptr;
1444
1445   if (const auto CompSym = comparison.getAsSymbol()) {
1446     assert(isa<SymIntExpr>(CompSym) &&
1447            "Symbol comparison must be a `SymIntExpr`");
1448     assert(BinaryOperator::isComparisonOp(
1449                cast<SymIntExpr>(CompSym)->getOpcode()) &&
1450            "Symbol comparison must be a comparison");
1451     return assumeNoOverflow(NewState, cast<SymIntExpr>(CompSym)->getLHS(), 2);
1452   }
1453
1454   return NewState;
1455 }
1456
1457 bool hasLiveIterators(ProgramStateRef State, const MemRegion *Cont) {
1458   auto RegionMap = State->get<IteratorRegionMap>();
1459   for (const auto &Reg : RegionMap) {
1460     if (Reg.second.getContainer() == Cont)
1461       return true;
1462   }
1463
1464   auto SymbolMap = State->get<IteratorSymbolMap>();
1465   for (const auto &Sym : SymbolMap) {
1466     if (Sym.second.getContainer() == Cont)
1467       return true;
1468   }
1469
1470   return false;
1471 }
1472
1473 bool isBoundThroughLazyCompoundVal(const Environment &Env,
1474                                    const MemRegion *Reg) {
1475   for (const auto &Binding : Env) {
1476     if (const auto LCVal = Binding.second.getAs<nonloc::LazyCompoundVal>()) {
1477       if (LCVal->getRegion() == Reg)
1478         return true;
1479     }
1480   }
1481
1482   return false;
1483 }
1484
1485 template <typename Condition, typename Process>
1486 ProgramStateRef processIteratorPositions(ProgramStateRef State, Condition Cond,
1487                                          Process Proc) {
1488   auto &RegionMapFactory = State->get_context<IteratorRegionMap>();
1489   auto RegionMap = State->get<IteratorRegionMap>();
1490   bool Changed = false;
1491   for (const auto &Reg : RegionMap) {
1492     if (Cond(Reg.second)) {
1493       RegionMap = RegionMapFactory.add(RegionMap, Reg.first, Proc(Reg.second));
1494       Changed = true;
1495     }
1496   }
1497
1498   if (Changed)
1499     State = State->set<IteratorRegionMap>(RegionMap);
1500
1501   auto &SymbolMapFactory = State->get_context<IteratorSymbolMap>();
1502   auto SymbolMap = State->get<IteratorSymbolMap>();
1503   Changed = false;
1504   for (const auto &Sym : SymbolMap) {
1505     if (Cond(Sym.second)) {
1506       SymbolMap = SymbolMapFactory.add(SymbolMap, Sym.first, Proc(Sym.second));
1507       Changed = true;
1508     }
1509   }
1510
1511   if (Changed)
1512     State = State->set<IteratorSymbolMap>(SymbolMap);
1513
1514   return State;
1515 }
1516
1517 ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State,
1518                                                const MemRegion *Cont) {
1519   auto MatchCont = [&](const IteratorPosition &Pos) {
1520     return Pos.getContainer() == Cont;
1521   };
1522   auto Invalidate = [&](const IteratorPosition &Pos) {
1523     return Pos.invalidate();
1524   };
1525   return processIteratorPositions(State, MatchCont, Invalidate);
1526 }
1527
1528 ProgramStateRef
1529 invalidateAllIteratorPositionsExcept(ProgramStateRef State,
1530                                      const MemRegion *Cont, SymbolRef Offset,
1531                                      BinaryOperator::Opcode Opc) {
1532   auto MatchContAndCompare = [&](const IteratorPosition &Pos) {
1533     return Pos.getContainer() == Cont &&
1534            !compare(State, Pos.getOffset(), Offset, Opc);
1535   };
1536   auto Invalidate = [&](const IteratorPosition &Pos) {
1537     return Pos.invalidate();
1538   };
1539   return processIteratorPositions(State, MatchContAndCompare, Invalidate);
1540 }
1541
1542 ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
1543                                             SymbolRef Offset,
1544                                             BinaryOperator::Opcode Opc) {
1545   auto Compare = [&](const IteratorPosition &Pos) {
1546     return compare(State, Pos.getOffset(), Offset, Opc);
1547   };
1548   auto Invalidate = [&](const IteratorPosition &Pos) {
1549     return Pos.invalidate();
1550   };
1551   return processIteratorPositions(State, Compare, Invalidate);
1552 }
1553
1554 ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
1555                                             SymbolRef Offset1,
1556                                             BinaryOperator::Opcode Opc1,
1557                                             SymbolRef Offset2,
1558                                             BinaryOperator::Opcode Opc2) {
1559   auto Compare = [&](const IteratorPosition &Pos) {
1560     return compare(State, Pos.getOffset(), Offset1, Opc1) &&
1561            compare(State, Pos.getOffset(), Offset2, Opc2);
1562   };
1563   auto Invalidate = [&](const IteratorPosition &Pos) {
1564     return Pos.invalidate();
1565   };
1566   return processIteratorPositions(State, Compare, Invalidate);
1567 }
1568
1569 ProgramStateRef reassignAllIteratorPositions(ProgramStateRef State,
1570                                              const MemRegion *Cont,
1571                                              const MemRegion *NewCont) {
1572   auto MatchCont = [&](const IteratorPosition &Pos) {
1573     return Pos.getContainer() == Cont;
1574   };
1575   auto ReAssign = [&](const IteratorPosition &Pos) {
1576     return Pos.reAssign(NewCont);
1577   };
1578   return processIteratorPositions(State, MatchCont, ReAssign);
1579 }
1580
1581 ProgramStateRef reassignAllIteratorPositionsUnless(ProgramStateRef State,
1582                                                    const MemRegion *Cont,
1583                                                    const MemRegion *NewCont,
1584                                                    SymbolRef Offset,
1585                                                    BinaryOperator::Opcode Opc) {
1586   auto MatchContAndCompare = [&](const IteratorPosition &Pos) {
1587     return Pos.getContainer() == Cont &&
1588     !compare(State, Pos.getOffset(), Offset, Opc);
1589   };
1590   auto ReAssign = [&](const IteratorPosition &Pos) {
1591     return Pos.reAssign(NewCont);
1592   };
1593   return processIteratorPositions(State, MatchContAndCompare, ReAssign);
1594 }
1595
1596 // This function rebases symbolic expression `OldSym + Int` to `NewSym + Int`,
1597 // `OldSym - Int` to `NewSym - Int` and  `OldSym` to `NewSym` in any iterator
1598 // position offsets where `CondSym` is true.
1599 ProgramStateRef rebaseSymbolInIteratorPositionsIf(
1600     ProgramStateRef State, SValBuilder &SVB, SymbolRef OldSym,
1601     SymbolRef NewSym, SymbolRef CondSym, BinaryOperator::Opcode Opc) {
1602   auto LessThanEnd = [&](const IteratorPosition &Pos) {
1603     return compare(State, Pos.getOffset(), CondSym, Opc);
1604   };
1605   auto RebaseSymbol = [&](const IteratorPosition &Pos) {
1606     return Pos.setTo(rebaseSymbol(State, SVB, Pos.getOffset(), OldSym,
1607                                    NewSym));
1608   };
1609   return processIteratorPositions(State, LessThanEnd, RebaseSymbol);
1610 }
1611
1612 // This function rebases symbolic expression `OldExpr + Int` to `NewExpr + Int`,
1613 // `OldExpr - Int` to `NewExpr - Int` and  `OldExpr` to `NewExpr` in expression
1614 // `OrigExpr`.
1615 SymbolRef rebaseSymbol(ProgramStateRef State, SValBuilder &SVB,
1616                        SymbolRef OrigExpr, SymbolRef OldExpr,
1617                        SymbolRef NewSym) {
1618   auto &SymMgr = SVB.getSymbolManager();
1619   auto Diff = SVB.evalBinOpNN(State, BO_Sub, nonloc::SymbolVal(OrigExpr),
1620                               nonloc::SymbolVal(OldExpr),
1621                               SymMgr.getType(OrigExpr));
1622
1623   const auto DiffInt = Diff.getAs<nonloc::ConcreteInt>();
1624   if (!DiffInt)
1625     return OrigExpr;
1626
1627   return SVB.evalBinOpNN(State, BO_Add, *DiffInt, nonloc::SymbolVal(NewSym),
1628                          SymMgr.getType(OrigExpr)).getAsSymbol();
1629 }
1630
1631 } // namespace
1632
1633 void ento::registerIteratorModeling(CheckerManager &mgr) {
1634   mgr.registerChecker<IteratorModeling>();
1635 }
1636
1637 bool ento::shouldRegisterIteratorModeling(const LangOptions &LO) {
1638   return true;
1639 }