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 modeling-checker for modeling STL iterator-like iterators.
  10 //
  11 //===----------------------------------------------------------------------===//
  12 //
  13 // In the code, iterator can be represented as a:
  14 // * type-I: typedef-ed pointer. Operations over such iterator, such as
  15 //           comparisons or increments, are modeled straightforwardly by the
  16 //           analyzer.
  17 // * type-II: structure with its method bodies available.  Operations over such
  18 //            iterator are inlined by the analyzer, and results of modeling
  19 //            these operations are exposing implementation details of the
  20 //            iterators, which is not necessarily helping.
  21 // * type-III: completely opaque structure. Operations over such iterator are
  22 //             modeled conservatively, producing conjured symbols everywhere.
  23 //
  24 // To handle all these types in a common way we introduce a structure called
  25 // IteratorPosition which is an abstraction of the position the iterator
  26 // represents using symbolic expressions. The checker handles all the
  27 // operations on this structure.
  28 //
  29 // Additionally, depending on the circumstances, operators of types II and III
  30 // can be represented as:
  31 // * type-IIa, type-IIIa: conjured structure symbols - when returned by value
  32 //                        from conservatively evaluated methods such as
  33 //                        `.begin()`.
  34 // * type-IIb, type-IIIb: memory regions of iterator-typed objects, such as
  35 //                        variables or temporaries, when the iterator object is
  36 //                        currently treated as an lvalue.
  37 // * type-IIc, type-IIIc: compound values of iterator-typed objects, when the
  38 //                        iterator object is treated as an rvalue taken of a
  39 //                        particular lvalue, eg. a copy of "type-a" iterator
  40 //                        object, or an iterator that existed before the
  41 //                        analysis has started.
  42 //
  43 // To handle any of these three different representations stored in an SVal we
  44 // use setter and getters functions which separate the three cases. To store
  45 // them we use a pointer union of symbol and memory region.
  46 //
  47 // The checker works the following way: We record the begin and the
  48 // past-end iterator for all containers whenever their `.begin()` and `.end()`
  49 // are called. Since the Constraint Manager cannot handle such SVals we need
  50 // to take over its role. We post-check equality and non-equality comparisons
  51 // and record that the two sides are equal if we are in the 'equal' branch
  52 // (true-branch for `==` and false-branch for `!=`).
  53 //
  54 // In case of type-I or type-II iterators we get a concrete integer as a result
  55 // of the comparison (1 or 0) but in case of type-III we only get a Symbol. In
  56 // this latter case we record the symbol and reload it in evalAssume() and do
  57 // the propagation there. We also handle (maybe double) negated comparisons
  58 // which are represented in the form of (x == 0 or x != 0) where x is the
  59 // comparison itself.
  60 //
  61 // Since `SimpleConstraintManager` cannot handle complex symbolic expressions
  62 // we only use expressions of the format S, S+n or S-n for iterator positions
  63 // where S is a conjured symbol and n is an unsigned concrete integer. When
  64 // making an assumption e.g. `S1 + n == S2 + m` we store `S1 - S2 == m - n` as
  65 // a constraint which we later retrieve when doing an actual comparison.
  66
  67 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
  68 #include "clang/AST/DeclTemplate.h"
  69 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
  70 #include "clang/StaticAnalyzer/Core/Checker.h"
  71 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
  72 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
  73 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h"
  74
  75 #include "Iterator.h"
  76
  77 #include <utility>
  78
  79 using namespace clang;
  80 using namespace ento;
  81 using namespace iterator;
  82
  83 namespace {
  84
  85 class IteratorModeling
  86     : public Checker<check::PostCall, check::PostStmt<UnaryOperator>,
  87                      check::PostStmt<BinaryOperator>,
  88                      check::PostStmt<MaterializeTemporaryExpr>,
  89                      check::Bind, check::LiveSymbols, check::DeadSymbols> {
  90
  91   using AdvanceFn = void (IteratorModeling::*)(CheckerContext &, const Expr *,
  92                                                SVal, SVal, SVal) const;
  93
  94   void handleOverloadedOperator(CheckerContext &C, const CallEvent &Call,
  95                                 OverloadedOperatorKind Op) const;
  96   void handleAdvanceLikeFunction(CheckerContext &C, const CallEvent &Call,
  97                                  const Expr *OrigExpr,
  98                                  const AdvanceFn *Handler) const;
  99
 100   void handleComparison(CheckerContext &C, const Expr *CE, SVal RetVal,
 101                         const SVal &LVal, const SVal &RVal,
 102                         OverloadedOperatorKind Op) const;
 103   void processComparison(CheckerContext &C, ProgramStateRef State,
 104                          SymbolRef Sym1, SymbolRef Sym2, const SVal &RetVal,
 105                          OverloadedOperatorKind Op) const;
 106   void handleIncrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter,
 107                        bool Postfix) const;
 108   void handleDecrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter,
 109                        bool Postfix) const;
 110   void handleRandomIncrOrDecr(CheckerContext &C, const Expr *CE,
 111                               OverloadedOperatorKind Op, const SVal &RetVal,
 112                               const SVal &LHS, const SVal &RHS) const;
 113   void handlePtrIncrOrDecr(CheckerContext &C, const Expr *Iterator,
 114                            OverloadedOperatorKind OK, SVal Offset) const;
 115   void handleAdvance(CheckerContext &C, const Expr *CE, SVal RetVal, SVal Iter,
 116                      SVal Amount) const;
 117   void handlePrev(CheckerContext &C, const Expr *CE, SVal RetVal, SVal Iter,
 118                   SVal Amount) const;
 119   void handleNext(CheckerContext &C, const Expr *CE, SVal RetVal, SVal Iter,
 120                   SVal Amount) const;
 121   void assignToContainer(CheckerContext &C, const Expr *CE, const SVal &RetVal,
 122                          const MemRegion *Cont) const;
 123   bool noChangeInAdvance(CheckerContext &C, SVal Iter, const Expr *CE) const;
 124   void printState(raw_ostream &Out, ProgramStateRef State, const char *NL,
 125                   const char *Sep) const override;
 126
 127   // std::advance, std::prev & std::next
 128   CallDescriptionMap<AdvanceFn> AdvanceLikeFunctions = {
 129       // template<class InputIt, class Distance>
 130       // void advance(InputIt& it, Distance n);
 131       {{{"std", "advance"}, 2}, &IteratorModeling::handleAdvance},
 132
 133       // template<class BidirIt>
 134       // BidirIt prev(
 135       //   BidirIt it,
 136       //   typename std::iterator_traits<BidirIt>::difference_type n = 1);
 137       {{{"std", "prev"}, 2}, &IteratorModeling::handlePrev},
 138
 139       // template<class ForwardIt>
 140       // ForwardIt next(
 141       //   ForwardIt it,
 142       //   typename std::iterator_traits<ForwardIt>::difference_type n = 1);
 143       {{{"std", "next"}, 2}, &IteratorModeling::handleNext},
 144   };
 145
 146 public:
 147   IteratorModeling() = default;
 148
 149   void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
 150   void checkBind(SVal Loc, SVal Val, const Stmt *S, CheckerContext &C) const;
 151   void checkPostStmt(const UnaryOperator *UO, CheckerContext &C) const;
 152   void checkPostStmt(const BinaryOperator *BO, CheckerContext &C) const;
 153   void checkPostStmt(const CXXConstructExpr *CCE, CheckerContext &C) const;
 154   void checkPostStmt(const DeclStmt *DS, CheckerContext &C) const;
 155   void checkPostStmt(const MaterializeTemporaryExpr *MTE,
 156                      CheckerContext &C) const;
 157   void checkLiveSymbols(ProgramStateRef State, SymbolReaper &SR) const;
 158   void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
 159 };
 160
 161 bool isSimpleComparisonOperator(OverloadedOperatorKind OK);
 162 bool isSimpleComparisonOperator(BinaryOperatorKind OK);
 163 ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val);
 164 ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1,
 165                               SymbolRef Sym2, bool Equal);
 166 bool isBoundThroughLazyCompoundVal(const Environment &Env,
 167                                    const MemRegion *Reg);
 168 const ExplodedNode *findCallEnter(const ExplodedNode *Node, const Expr *Call);
 169
 170 } // namespace
 171
 172 void IteratorModeling::checkPostCall(const CallEvent &Call,
 173                                      CheckerContext &C) const {
 174   // Record new iterator positions and iterator position changes
 175   const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
 176   if (!Func)
 177     return;
 178
 179   if (Func->isOverloadedOperator()) {
 180     const auto Op = Func->getOverloadedOperator();
 181     handleOverloadedOperator(C, Call, Op);
 182     return;
 183   }
 184
 185   const auto *OrigExpr = Call.getOriginExpr();
 186   if (!OrigExpr)
 187     return;
 188
 189   const AdvanceFn *Handler = AdvanceLikeFunctions.lookup(Call);
 190   if (Handler) {
 191     handleAdvanceLikeFunction(C, Call, OrigExpr, Handler);
 192     return;
 193   }
 194
 195   if (!isIteratorType(Call.getResultType()))
 196     return;
 197
 198   auto State = C.getState();
 199
 200   // Already bound to container?
 201   if (getIteratorPosition(State, Call.getReturnValue()))
 202     return;
 203
 204   // Copy-like and move constructors
 205   if (isa<CXXConstructorCall>(&Call) && Call.getNumArgs() == 1) {
 206     if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(0))) {
 207       State = setIteratorPosition(State, Call.getReturnValue(), *Pos);
 208       if (cast<CXXConstructorDecl>(Func)->isMoveConstructor()) {
 209         State = removeIteratorPosition(State, Call.getArgSVal(0));
 210       }
 211       C.addTransition(State);
 212       return;
 213     }
 214   }
 215
 216   // Assumption: if return value is an iterator which is not yet bound to a
 217   //             container, then look for the first iterator argument of the
 218   //             same type as the return value and bind the return value to
 219   //             the same container. This approach works for STL algorithms.
 220   // FIXME: Add a more conservative mode
 221   for (unsigned i = 0; i < Call.getNumArgs(); ++i) {
 222     if (isIteratorType(Call.getArgExpr(i)->getType()) &&
 223         Call.getArgExpr(i)->getType().getNonReferenceType().getDesugaredType(
 224             C.getASTContext()).getTypePtr() ==
 225         Call.getResultType().getDesugaredType(C.getASTContext()).getTypePtr()) {
 226       if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(i))) {
 227         assignToContainer(C, OrigExpr, Call.getReturnValue(),
 228                           Pos->getContainer());
 229         return;
 230       }
 231     }
 232   }
 233 }
 234
 235 void IteratorModeling::checkBind(SVal Loc, SVal Val, const Stmt *S,
 236                                  CheckerContext &C) const {
 237   auto State = C.getState();
 238   const auto *Pos = getIteratorPosition(State, Val);
 239   if (Pos) {
 240     State = setIteratorPosition(State, Loc, *Pos);
 241     C.addTransition(State);
 242   } else {
 243     const auto *OldPos = getIteratorPosition(State, Loc);
 244     if (OldPos) {
 245       State = removeIteratorPosition(State, Loc);
 246       C.addTransition(State);
 247     }
 248   }
 249 }
 250
 251 void IteratorModeling::checkPostStmt(const UnaryOperator *UO,
 252                                      CheckerContext &C) const {
 253   UnaryOperatorKind OK = UO->getOpcode();
 254   if (!isIncrementOperator(OK) && !isDecrementOperator(OK))
 255     return;
 256
 257   auto &SVB = C.getSValBuilder();
 258   handlePtrIncrOrDecr(C, UO->getSubExpr(),
 259                       isIncrementOperator(OK) ? OO_Plus : OO_Minus,
 260                       SVB.makeArrayIndex(1));
 261 }
 262
 263 void IteratorModeling::checkPostStmt(const BinaryOperator *BO,
 264                                      CheckerContext &C) const {
 265   ProgramStateRef State = C.getState();
 266   BinaryOperatorKind OK = BO->getOpcode();
 267   SVal RVal = State->getSVal(BO->getRHS(), C.getLocationContext());
 268
 269   if (isSimpleComparisonOperator(BO->getOpcode())) {
 270     SVal LVal = State->getSVal(BO->getLHS(), C.getLocationContext());
 271     SVal Result = State->getSVal(BO, C.getLocationContext());
 272     handleComparison(C, BO, Result, LVal, RVal,
 273                      BinaryOperator::getOverloadedOperator(OK));
 274   } else if (isRandomIncrOrDecrOperator(OK)) {
 275     handlePtrIncrOrDecr(C, BO->getLHS(),
 276                         BinaryOperator::getOverloadedOperator(OK), RVal);
 277   }
 278 }
 279
 280 void IteratorModeling::checkPostStmt(const MaterializeTemporaryExpr *MTE,
 281                                      CheckerContext &C) const {
 282   /* Transfer iterator state to temporary objects */
 283   auto State = C.getState();
 284   const auto *Pos = getIteratorPosition(State, C.getSVal(MTE->getSubExpr()));
 285   if (!Pos)
 286     return;
 287   State = setIteratorPosition(State, C.getSVal(MTE), *Pos);
 288   C.addTransition(State);
 289 }
 290
 291 void IteratorModeling::checkLiveSymbols(ProgramStateRef State,
 292                                         SymbolReaper &SR) const {
 293   // Keep symbolic expressions of iterator positions alive
 294   auto RegionMap = State->get<IteratorRegionMap>();
 295   for (const auto &Reg : RegionMap) {
 296     const auto Offset = Reg.second.getOffset();
 297     for (auto i = Offset->symbol_begin(); i != Offset->symbol_end(); ++i)
 298       if (isa<SymbolData>(*i))
 299         SR.markLive(*i);
 300   }
 301
 302   auto SymbolMap = State->get<IteratorSymbolMap>();
 303   for (const auto &Sym : SymbolMap) {
 304     const auto Offset = Sym.second.getOffset();
 305     for (auto i = Offset->symbol_begin(); i != Offset->symbol_end(); ++i)
 306       if (isa<SymbolData>(*i))
 307         SR.markLive(*i);
 308   }
 309
 310 }
 311
 312 void IteratorModeling::checkDeadSymbols(SymbolReaper &SR,
 313                                         CheckerContext &C) const {
 314   // Cleanup
 315   auto State = C.getState();
 316
 317   auto RegionMap = State->get<IteratorRegionMap>();
 318   for (const auto &Reg : RegionMap) {
 319     if (!SR.isLiveRegion(Reg.first)) {
 320       // The region behind the `LazyCompoundVal` is often cleaned up before
 321       // the `LazyCompoundVal` itself. If there are iterator positions keyed
 322       // by these regions their cleanup must be deferred.
 323       if (!isBoundThroughLazyCompoundVal(State->getEnvironment(), Reg.first)) {
 324         State = State->remove<IteratorRegionMap>(Reg.first);
 325       }
 326     }
 327   }
 328
 329   auto SymbolMap = State->get<IteratorSymbolMap>();
 330   for (const auto &Sym : SymbolMap) {
 331     if (!SR.isLive(Sym.first)) {
 332       State = State->remove<IteratorSymbolMap>(Sym.first);
 333     }
 334   }
 335
 336   C.addTransition(State);
 337 }
 338
 339 void
 340 IteratorModeling::handleOverloadedOperator(CheckerContext &C,
 341                                            const CallEvent &Call,
 342                                            OverloadedOperatorKind Op) const {
 343     if (isSimpleComparisonOperator(Op)) {
 344       const auto *OrigExpr = Call.getOriginExpr();
 345       if (!OrigExpr)
 346         return;
 347
 348       if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
 349         handleComparison(C, OrigExpr, Call.getReturnValue(),
 350                          InstCall->getCXXThisVal(), Call.getArgSVal(0), Op);
 351         return;
 352       }
 353
 354       handleComparison(C, OrigExpr, Call.getReturnValue(), Call.getArgSVal(0),
 355                          Call.getArgSVal(1), Op);
 356       return;
 357     } else if (isRandomIncrOrDecrOperator(Op)) {
 358       const auto *OrigExpr = Call.getOriginExpr();
 359       if (!OrigExpr)
 360         return;
 361
 362       if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
 363         if (Call.getNumArgs() >= 1 &&
 364               Call.getArgExpr(0)->getType()->isIntegralOrEnumerationType()) {
 365           handleRandomIncrOrDecr(C, OrigExpr, Op, Call.getReturnValue(),
 366                                  InstCall->getCXXThisVal(), Call.getArgSVal(0));
 367           return;
 368         }
 369       } else {
 370         if (Call.getNumArgs() >= 2 &&
 371               Call.getArgExpr(1)->getType()->isIntegralOrEnumerationType()) {
 372           handleRandomIncrOrDecr(C, OrigExpr, Op, Call.getReturnValue(),
 373                                  Call.getArgSVal(0), Call.getArgSVal(1));
 374           return;
 375         }
 376       }
 377     } else if (isIncrementOperator(Op)) {
 378       if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
 379         handleIncrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(),
 380                         Call.getNumArgs());
 381         return;
 382       }
 383
 384       handleIncrement(C, Call.getReturnValue(), Call.getArgSVal(0),
 385                       Call.getNumArgs());
 386       return;
 387     } else if (isDecrementOperator(Op)) {
 388       if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
 389         handleDecrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(),
 390                         Call.getNumArgs());
 391         return;
 392       }
 393
 394       handleDecrement(C, Call.getReturnValue(), Call.getArgSVal(0),
 395                         Call.getNumArgs());
 396       return;
 397     }
 398 }
 399
 400 void
 401 IteratorModeling::handleAdvanceLikeFunction(CheckerContext &C,
 402                                             const CallEvent &Call,
 403                                             const Expr *OrigExpr,
 404                                             const AdvanceFn *Handler) const {
 405   if (!C.wasInlined) {
 406     (this->**Handler)(C, OrigExpr, Call.getReturnValue(),
 407                       Call.getArgSVal(0), Call.getArgSVal(1));
 408     return;
 409   }
 410
 411   // If std::advance() was inlined, but a non-standard function it calls inside
 412   // was not, then we have to model it explicitly
 413   const auto *IdInfo = cast<FunctionDecl>(Call.getDecl())->getIdentifier();
 414   if (IdInfo) {
 415     if (IdInfo->getName() == "advance") {
 416       if (noChangeInAdvance(C, Call.getArgSVal(0), OrigExpr)) {
 417         (this->**Handler)(C, OrigExpr, Call.getReturnValue(),
 418                           Call.getArgSVal(0), Call.getArgSVal(1));
 419       }
 420     }
 421   }
 422 }
 423
 424 void IteratorModeling::handleComparison(CheckerContext &C, const Expr *CE,
 425                                        SVal RetVal, const SVal &LVal,
 426                                        const SVal &RVal,
 427                                        OverloadedOperatorKind Op) const {
 428   // Record the operands and the operator of the comparison for the next
 429   // evalAssume, if the result is a symbolic expression. If it is a concrete
 430   // value (only one branch is possible), then transfer the state between
 431   // the operands according to the operator and the result
 432    auto State = C.getState();
 433   const auto *LPos = getIteratorPosition(State, LVal);
 434   const auto *RPos = getIteratorPosition(State, RVal);
 435   const MemRegion *Cont = nullptr;
 436   if (LPos) {
 437     Cont = LPos->getContainer();
 438   } else if (RPos) {
 439     Cont = RPos->getContainer();
 440   }
 441   if (!Cont)
 442     return;
 443
 444   // At least one of the iterators has recorded positions. If one of them does
 445   // not then create a new symbol for the offset.
 446   SymbolRef Sym;
 447   if (!LPos || !RPos) {
 448     auto &SymMgr = C.getSymbolManager();
 449     Sym = SymMgr.conjureSymbol(CE, C.getLocationContext(),
 450                                C.getASTContext().LongTy, C.blockCount());
 451     State = assumeNoOverflow(State, Sym, 4);
 452   }
 453
 454   if (!LPos) {
 455     State = setIteratorPosition(State, LVal,
 456                                 IteratorPosition::getPosition(Cont, Sym));
 457     LPos = getIteratorPosition(State, LVal);
 458   } else if (!RPos) {
 459     State = setIteratorPosition(State, RVal,
 460                                 IteratorPosition::getPosition(Cont, Sym));
 461     RPos = getIteratorPosition(State, RVal);
 462   }
 463
 464   // We cannot make assumptions on `UnknownVal`. Let us conjure a symbol
 465   // instead.
 466   if (RetVal.isUnknown()) {
 467     auto &SymMgr = C.getSymbolManager();
 468     auto *LCtx = C.getLocationContext();
 469     RetVal = nonloc::SymbolVal(SymMgr.conjureSymbol(
 470         CE, LCtx, C.getASTContext().BoolTy, C.blockCount()));
 471     State = State->BindExpr(CE, LCtx, RetVal);
 472   }
 473
 474   processComparison(C, State, LPos->getOffset(), RPos->getOffset(), RetVal, Op);
 475 }
 476
 477 void IteratorModeling::processComparison(CheckerContext &C,
 478                                          ProgramStateRef State, SymbolRef Sym1,
 479                                          SymbolRef Sym2, const SVal &RetVal,
 480                                          OverloadedOperatorKind Op) const {
 481   if (const auto TruthVal = RetVal.getAs<nonloc::ConcreteInt>()) {
 482     if ((State = relateSymbols(State, Sym1, Sym2,
 483                               (Op == OO_EqualEqual) ==
 484                                (TruthVal->getValue() != 0)))) {
 485       C.addTransition(State);
 486     } else {
 487       C.generateSink(State, C.getPredecessor());
 488     }
 489     return;
 490   }
 491
 492   const auto ConditionVal = RetVal.getAs<DefinedSVal>();
 493   if (!ConditionVal)
 494     return;
 495
 496   if (auto StateTrue = relateSymbols(State, Sym1, Sym2, Op == OO_EqualEqual)) {
 497     StateTrue = StateTrue->assume(*ConditionVal, true);
 498     C.addTransition(StateTrue);
 499   }
 500
 501   if (auto StateFalse = relateSymbols(State, Sym1, Sym2, Op != OO_EqualEqual)) {
 502     StateFalse = StateFalse->assume(*ConditionVal, false);
 503     C.addTransition(StateFalse);
 504   }
 505 }
 506
 507 void IteratorModeling::handleIncrement(CheckerContext &C, const SVal &RetVal,
 508                                        const SVal &Iter, bool Postfix) const {
 509   // Increment the symbolic expressions which represents the position of the
 510   // iterator
 511   auto State = C.getState();
 512   auto &BVF = C.getSymbolManager().getBasicVals();
 513
 514   const auto *Pos = getIteratorPosition(State, Iter);
 515   if (!Pos)
 516     return;
 517
 518   auto NewState =
 519     advancePosition(State, Iter, OO_Plus,
 520                     nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
 521   assert(NewState &&
 522          "Advancing position by concrete int should always be successful");
 523
 524   const auto *NewPos = getIteratorPosition(NewState, Iter);
 525   assert(NewPos &&
 526          "Iterator should have position after successful advancement");
 527
 528   State = setIteratorPosition(State, Iter, *NewPos);
 529   State = setIteratorPosition(State, RetVal, Postfix ? *Pos : *NewPos);
 530   C.addTransition(State);
 531 }
 532
 533 void IteratorModeling::handleDecrement(CheckerContext &C, const SVal &RetVal,
 534                                        const SVal &Iter, bool Postfix) const {
 535   // Decrement the symbolic expressions which represents the position of the
 536   // iterator
 537   auto State = C.getState();
 538   auto &BVF = C.getSymbolManager().getBasicVals();
 539
 540   const auto *Pos = getIteratorPosition(State, Iter);
 541   if (!Pos)
 542     return;
 543
 544   auto NewState =
 545     advancePosition(State, Iter, OO_Minus,
 546                     nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
 547   assert(NewState &&
 548          "Advancing position by concrete int should always be successful");
 549
 550   const auto *NewPos = getIteratorPosition(NewState, Iter);
 551   assert(NewPos &&
 552          "Iterator should have position after successful advancement");
 553
 554   State = setIteratorPosition(State, Iter, *NewPos);
 555   State = setIteratorPosition(State, RetVal, Postfix ? *Pos : *NewPos);
 556   C.addTransition(State);
 557 }
 558
 559 void IteratorModeling::handleRandomIncrOrDecr(CheckerContext &C,
 560                                               const Expr *CE,
 561                                               OverloadedOperatorKind Op,
 562                                               const SVal &RetVal,
 563                                               const SVal &LHS,
 564                                               const SVal &RHS) const {
 565   // Increment or decrement the symbolic expressions which represents the
 566   // position of the iterator
 567   auto State = C.getState();
 568
 569   const auto *Pos = getIteratorPosition(State, LHS);
 570   if (!Pos)
 571     return;
 572
 573   const auto *value = &RHS;
 574   SVal val;
 575   if (auto loc = RHS.getAs<Loc>()) {
 576     val = State->getRawSVal(*loc);
 577     value = &val;
 578   }
 579
 580   auto &TgtVal = (Op == OO_PlusEqual || Op == OO_MinusEqual) ? LHS : RetVal;
 581
 582   // `AdvancedState` is a state where the position of `LHS` is advanced. We
 583   // only need this state to retrieve the new position, but we do not want
 584   // to change the position of `LHS` (in every case).
 585   auto AdvancedState = advancePosition(State, LHS, Op, *value);
 586   if (AdvancedState) {
 587     const auto *NewPos = getIteratorPosition(AdvancedState, LHS);
 588     assert(NewPos &&
 589            "Iterator should have position after successful advancement");
 590
 591     State = setIteratorPosition(State, TgtVal, *NewPos);
 592     C.addTransition(State);
 593   } else {
 594     assignToContainer(C, CE, TgtVal, Pos->getContainer());
 595   }
 596 }
 597
 598 void IteratorModeling::handlePtrIncrOrDecr(CheckerContext &C,
 599                                            const Expr *Iterator,
 600                                            OverloadedOperatorKind OK,
 601                                            SVal Offset) const {
 602   QualType PtrType = Iterator->getType();
 603   if (!PtrType->isPointerType())
 604     return;
 605   QualType ElementType = PtrType->getPointeeType();
 606
 607   ProgramStateRef State = C.getState();
 608   SVal OldVal = State->getSVal(Iterator, C.getLocationContext());
 609
 610   const IteratorPosition *OldPos = getIteratorPosition(State, OldVal);
 611   if (!OldPos)
 612     return;
 613
 614   SVal NewVal;
 615   if (OK == OO_Plus || OK == OO_PlusEqual)
 616     NewVal = State->getLValue(ElementType, Offset, OldVal);
 617   else {
 618     const llvm::APSInt &OffsetInt =
 619       Offset.castAs<nonloc::ConcreteInt>().getValue();
 620     auto &BVF = C.getSymbolManager().getBasicVals();
 621     SVal NegatedOffset = nonloc::ConcreteInt(BVF.getValue(-OffsetInt));
 622     NewVal = State->getLValue(ElementType, NegatedOffset, OldVal);
 623   }
 624
 625   // `AdvancedState` is a state where the position of `Old` is advanced. We
 626   // only need this state to retrieve the new position, but we do not want
 627   // ever to change the position of `OldVal`.
 628   auto AdvancedState = advancePosition(State, OldVal, OK, Offset);
 629   if (AdvancedState) {
 630     const IteratorPosition *NewPos = getIteratorPosition(AdvancedState, OldVal);
 631     assert(NewPos &&
 632            "Iterator should have position after successful advancement");
 633
 634     ProgramStateRef NewState = setIteratorPosition(State, NewVal, *NewPos);
 635     C.addTransition(NewState);
 636   } else {
 637     assignToContainer(C, Iterator, NewVal, OldPos->getContainer());
 638   }
 639 }
 640
 641 void IteratorModeling::handleAdvance(CheckerContext &C, const Expr *CE,
 642                                      SVal RetVal, SVal Iter,
 643                                      SVal Amount) const {
 644   handleRandomIncrOrDecr(C, CE, OO_PlusEqual, RetVal, Iter, Amount);
 645 }
 646
 647 void IteratorModeling::handlePrev(CheckerContext &C, const Expr *CE,
 648                                   SVal RetVal, SVal Iter, SVal Amount) const {
 649   handleRandomIncrOrDecr(C, CE, OO_Minus, RetVal, Iter, Amount);
 650 }
 651
 652 void IteratorModeling::handleNext(CheckerContext &C, const Expr *CE,
 653                                   SVal RetVal, SVal Iter, SVal Amount) const {
 654   handleRandomIncrOrDecr(C, CE, OO_Plus, RetVal, Iter, Amount);
 655 }
 656
 657 void IteratorModeling::assignToContainer(CheckerContext &C, const Expr *CE,
 658                                          const SVal &RetVal,
 659                                          const MemRegion *Cont) const {
 660   Cont = Cont->getMostDerivedObjectRegion();
 661
 662   auto State = C.getState();
 663   const auto *LCtx = C.getLocationContext();
 664   State = createIteratorPosition(State, RetVal, Cont, CE, LCtx, C.blockCount());
 665
 666   C.addTransition(State);
 667 }
 668
 669 bool IteratorModeling::noChangeInAdvance(CheckerContext &C, SVal Iter,
 670                                          const Expr *CE) const {
 671   // Compare the iterator position before and after the call. (To be called
 672   // from `checkPostCall()`.)
 673   const auto StateAfter = C.getState();
 674
 675   const auto *PosAfter = getIteratorPosition(StateAfter, Iter);
 676   // If we have no position after the call of `std::advance`, then we are not
 677   // interested. (Modeling of an inlined `std::advance()` should not remove the
 678   // position in any case.)
 679   if (!PosAfter)
 680     return false;
 681
 682   const ExplodedNode *N = findCallEnter(C.getPredecessor(), CE);
 683   assert(N && "Any call should have a `CallEnter` node.");
 684
 685   const auto StateBefore = N->getState();
 686   const auto *PosBefore = getIteratorPosition(StateBefore, Iter);
 687
 688   assert(PosBefore && "`std::advance() should not create new iterator "
 689          "position but change existing ones");
 690
 691   return PosBefore->getOffset() == PosAfter->getOffset();
 692 }
 693
 694 void IteratorModeling::printState(raw_ostream &Out, ProgramStateRef State,
 695                                   const char *NL, const char *Sep) const {
 696   auto SymbolMap = State->get<IteratorSymbolMap>();
 697   auto RegionMap = State->get<IteratorRegionMap>();
 698   // Use a counter to add newlines before every line except the first one.
 699   unsigned Count = 0;
 700
 701   if (!SymbolMap.isEmpty() || !RegionMap.isEmpty()) {
 702     Out << Sep << "Iterator Positions :" << NL;
 703     for (const auto &Sym : SymbolMap) {
 704       if (Count++)
 705         Out << NL;
 706
 707       Sym.first->dumpToStream(Out);
 708       Out << " : ";
 709       const auto Pos = Sym.second;
 710       Out << (Pos.isValid() ? "Valid" : "Invalid") << " ; Container == ";
 711       Pos.getContainer()->dumpToStream(Out);
 712       Out<<" ; Offset == ";
 713       Pos.getOffset()->dumpToStream(Out);
 714     }
 715
 716     for (const auto &Reg : RegionMap) {
 717       if (Count++)
 718         Out << NL;
 719
 720       Reg.first->dumpToStream(Out);
 721       Out << " : ";
 722       const auto Pos = Reg.second;
 723       Out << (Pos.isValid() ? "Valid" : "Invalid") << " ; Container == ";
 724       Pos.getContainer()->dumpToStream(Out);
 725       Out<<" ; Offset == ";
 726       Pos.getOffset()->dumpToStream(Out);
 727     }
 728   }
 729 }
 730
 731 namespace {
 732
 733 bool isSimpleComparisonOperator(OverloadedOperatorKind OK) {
 734   return OK == OO_EqualEqual || OK == OO_ExclaimEqual;
 735 }
 736
 737 bool isSimpleComparisonOperator(BinaryOperatorKind OK) {
 738   return OK == BO_EQ || OK == BO_NE;
 739 }
 740
 741 ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val) {
 742   if (auto Reg = Val.getAsRegion()) {
 743     Reg = Reg->getMostDerivedObjectRegion();
 744     return State->remove<IteratorRegionMap>(Reg);
 745   } else if (const auto Sym = Val.getAsSymbol()) {
 746     return State->remove<IteratorSymbolMap>(Sym);
 747   } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
 748     return State->remove<IteratorRegionMap>(LCVal->getRegion());
 749   }
 750   return nullptr;
 751 }
 752
 753 ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1,
 754                               SymbolRef Sym2, bool Equal) {
 755   auto &SVB = State->getStateManager().getSValBuilder();
 756
 757   // FIXME: This code should be reworked as follows:
 758   // 1. Subtract the operands using evalBinOp().
 759   // 2. Assume that the result doesn't overflow.
 760   // 3. Compare the result to 0.
 761   // 4. Assume the result of the comparison.
 762   const auto comparison =
 763     SVB.evalBinOp(State, BO_EQ, nonloc::SymbolVal(Sym1),
 764                   nonloc::SymbolVal(Sym2), SVB.getConditionType());
 765
 766   assert(comparison.getAs<DefinedSVal>() &&
 767     "Symbol comparison must be a `DefinedSVal`");
 768
 769   auto NewState = State->assume(comparison.castAs<DefinedSVal>(), Equal);
 770   if (!NewState)
 771     return nullptr;
 772
 773   if (const auto CompSym = comparison.getAsSymbol()) {
 774     assert(isa<SymIntExpr>(CompSym) &&
 775            "Symbol comparison must be a `SymIntExpr`");
 776     assert(BinaryOperator::isComparisonOp(
 777                cast<SymIntExpr>(CompSym)->getOpcode()) &&
 778            "Symbol comparison must be a comparison");
 779     return assumeNoOverflow(NewState, cast<SymIntExpr>(CompSym)->getLHS(), 2);
 780   }
 781
 782   return NewState;
 783 }
 784
 785 bool isBoundThroughLazyCompoundVal(const Environment &Env,
 786                                    const MemRegion *Reg) {
 787   for (const auto &Binding : Env) {
 788     if (const auto LCVal = Binding.second.getAs<nonloc::LazyCompoundVal>()) {
 789       if (LCVal->getRegion() == Reg)
 790         return true;
 791     }
 792   }
 793
 794   return false;
 795 }
 796
 797 const ExplodedNode *findCallEnter(const ExplodedNode *Node, const Expr *Call) {
 798   while (Node) {
 799     ProgramPoint PP = Node->getLocation();
 800     if (auto Enter = PP.getAs<CallEnter>()) {
 801       if (Enter->getCallExpr() == Call)
 802         break;
 803     }
 804
 805     Node = Node->getFirstPred();
 806   }
 807
 808   return Node;
 809 }
 810
 811 } // namespace
 812
 813 void ento::registerIteratorModeling(CheckerManager &mgr) {
 814   mgr.registerChecker<IteratorModeling>();
 815 }
 816
 817 bool ento::shouldRegisterIteratorModeling(const CheckerManager &mgr) {
 818   return true;
 819 }