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/AST/DeclTemplate.h"
  68 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
  69 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
  70 #include "clang/StaticAnalyzer/Core/Checker.h"
  71 #include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.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 #include "llvm/ADT/STLExtras.h"
  76
  77 #include "Iterator.h"
  78
  79 #include <utility>
  80
  81 using namespace clang;
  82 using namespace ento;
  83 using namespace iterator;
  84
  85 namespace {
  86
  87 class IteratorModeling
  88     : public Checker<check::PostCall, check::PostStmt<UnaryOperator>,
  89                      check::PostStmt<BinaryOperator>,
  90                      check::PostStmt<MaterializeTemporaryExpr>,
  91                      check::Bind, check::LiveSymbols, check::DeadSymbols> {
  92
  93   using AdvanceFn = void (IteratorModeling::*)(CheckerContext &, const Expr *,
  94                                                SVal, SVal, SVal) const;
  95
  96   void handleOverloadedOperator(CheckerContext &C, const CallEvent &Call,
  97                                 OverloadedOperatorKind Op) const;
  98   void handleAdvanceLikeFunction(CheckerContext &C, const CallEvent &Call,
  99                                  const Expr *OrigExpr,
 100                                  const AdvanceFn *Handler) const;
 101
 102   void handleComparison(CheckerContext &C, const Expr *CE, SVal RetVal,
 103                         const SVal &LVal, const SVal &RVal,
 104                         OverloadedOperatorKind Op) const;
 105   void processComparison(CheckerContext &C, ProgramStateRef State,
 106                          SymbolRef Sym1, SymbolRef Sym2, const SVal &RetVal,
 107                          OverloadedOperatorKind Op) const;
 108   void handleIncrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter,
 109                        bool Postfix) const;
 110   void handleDecrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter,
 111                        bool Postfix) const;
 112   void handleRandomIncrOrDecr(CheckerContext &C, const Expr *CE,
 113                               OverloadedOperatorKind Op, const SVal &RetVal,
 114                               const SVal &Iterator, const SVal &Amount) const;
 115   void handlePtrIncrOrDecr(CheckerContext &C, const Expr *Iterator,
 116                            OverloadedOperatorKind OK, SVal Offset) const;
 117   void handleAdvance(CheckerContext &C, const Expr *CE, SVal RetVal, SVal Iter,
 118                      SVal Amount) const;
 119   void handlePrev(CheckerContext &C, const Expr *CE, SVal RetVal, SVal Iter,
 120                   SVal Amount) const;
 121   void handleNext(CheckerContext &C, const Expr *CE, SVal RetVal, SVal Iter,
 122                   SVal Amount) const;
 123   void assignToContainer(CheckerContext &C, const Expr *CE, const SVal &RetVal,
 124                          const MemRegion *Cont) const;
 125   bool noChangeInAdvance(CheckerContext &C, SVal Iter, const Expr *CE) const;
 126   void printState(raw_ostream &Out, ProgramStateRef State, const char *NL,
 127                   const char *Sep) const override;
 128
 129   // std::advance, std::prev & std::next
 130   CallDescriptionMap<AdvanceFn> AdvanceLikeFunctions = {
 131       // template<class InputIt, class Distance>
 132       // void advance(InputIt& it, Distance n);
 133       {{{"std", "advance"}, 2}, &IteratorModeling::handleAdvance},
 134
 135       // template<class BidirIt>
 136       // BidirIt prev(
 137       //   BidirIt it,
 138       //   typename std::iterator_traits<BidirIt>::difference_type n = 1);
 139       {{{"std", "prev"}, 2}, &IteratorModeling::handlePrev},
 140
 141       // template<class ForwardIt>
 142       // ForwardIt next(
 143       //   ForwardIt it,
 144       //   typename std::iterator_traits<ForwardIt>::difference_type n = 1);
 145       {{{"std", "next"}, 2}, &IteratorModeling::handleNext},
 146   };
 147
 148 public:
 149   IteratorModeling() = default;
 150
 151   void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
 152   void checkBind(SVal Loc, SVal Val, const Stmt *S, CheckerContext &C) const;
 153   void checkPostStmt(const UnaryOperator *UO, CheckerContext &C) const;
 154   void checkPostStmt(const BinaryOperator *BO, 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   const ProgramStateRef State = C.getState();
 266   const BinaryOperatorKind OK = BO->getOpcode();
 267   const Expr *const LHS = BO->getLHS();
 268   const Expr *const RHS = BO->getRHS();
 269   const SVal LVal = State->getSVal(LHS, C.getLocationContext());
 270   const SVal RVal = State->getSVal(RHS, C.getLocationContext());
 271
 272   if (isSimpleComparisonOperator(BO->getOpcode())) {
 273     SVal Result = State->getSVal(BO, C.getLocationContext());
 274     handleComparison(C, BO, Result, LVal, RVal,
 275                      BinaryOperator::getOverloadedOperator(OK));
 276   } else if (isRandomIncrOrDecrOperator(OK)) {
 277     // In case of operator+ the iterator can be either on the LHS (eg.: it + 1),
 278     // or on the RHS (eg.: 1 + it). Both cases are modeled.
 279     const bool IsIterOnLHS = BO->getLHS()->getType()->isPointerType();
 280     const Expr *const &IterExpr = IsIterOnLHS ? LHS : RHS;
 281     const Expr *const &AmountExpr = IsIterOnLHS ? RHS : LHS;
 282
 283     // The non-iterator side must have an integral or enumeration type.
 284     if (!AmountExpr->getType()->isIntegralOrEnumerationType())
 285       return;
 286     const SVal &AmountVal = IsIterOnLHS ? RVal : LVal;
 287     handlePtrIncrOrDecr(C, IterExpr, BinaryOperator::getOverloadedOperator(OK),
 288                         AmountVal);
 289   }
 290 }
 291
 292 void IteratorModeling::checkPostStmt(const MaterializeTemporaryExpr *MTE,
 293                                      CheckerContext &C) const {
 294   /* Transfer iterator state to temporary objects */
 295   auto State = C.getState();
 296   const auto *Pos = getIteratorPosition(State, C.getSVal(MTE->getSubExpr()));
 297   if (!Pos)
 298     return;
 299   State = setIteratorPosition(State, C.getSVal(MTE), *Pos);
 300   C.addTransition(State);
 301 }
 302
 303 void IteratorModeling::checkLiveSymbols(ProgramStateRef State,
 304                                         SymbolReaper &SR) const {
 305   // Keep symbolic expressions of iterator positions alive
 306   auto RegionMap = State->get<IteratorRegionMap>();
 307   for (const IteratorPosition &Pos : llvm::make_second_range(RegionMap)) {
 308     for (SymbolRef Sym : Pos.getOffset()->symbols())
 309       if (isa<SymbolData>(Sym))
 310         SR.markLive(Sym);
 311   }
 312
 313   auto SymbolMap = State->get<IteratorSymbolMap>();
 314   for (const IteratorPosition &Pos : llvm::make_second_range(SymbolMap)) {
 315     for (SymbolRef Sym : Pos.getOffset()->symbols())
 316       if (isa<SymbolData>(Sym))
 317         SR.markLive(Sym);
 318   }
 319 }
 320
 321 void IteratorModeling::checkDeadSymbols(SymbolReaper &SR,
 322                                         CheckerContext &C) const {
 323   // Cleanup
 324   auto State = C.getState();
 325
 326   auto RegionMap = State->get<IteratorRegionMap>();
 327   for (const auto &Reg : RegionMap) {
 328     if (!SR.isLiveRegion(Reg.first)) {
 329       // The region behind the `LazyCompoundVal` is often cleaned up before
 330       // the `LazyCompoundVal` itself. If there are iterator positions keyed
 331       // by these regions their cleanup must be deferred.
 332       if (!isBoundThroughLazyCompoundVal(State->getEnvironment(), Reg.first)) {
 333         State = State->remove<IteratorRegionMap>(Reg.first);
 334       }
 335     }
 336   }
 337
 338   auto SymbolMap = State->get<IteratorSymbolMap>();
 339   for (const auto &Sym : SymbolMap) {
 340     if (!SR.isLive(Sym.first)) {
 341       State = State->remove<IteratorSymbolMap>(Sym.first);
 342     }
 343   }
 344
 345   C.addTransition(State);
 346 }
 347
 348 void
 349 IteratorModeling::handleOverloadedOperator(CheckerContext &C,
 350                                            const CallEvent &Call,
 351                                            OverloadedOperatorKind Op) const {
 352     if (isSimpleComparisonOperator(Op)) {
 353       const auto *OrigExpr = Call.getOriginExpr();
 354       if (!OrigExpr)
 355         return;
 356
 357       if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
 358         handleComparison(C, OrigExpr, Call.getReturnValue(),
 359                          InstCall->getCXXThisVal(), Call.getArgSVal(0), Op);
 360         return;
 361       }
 362
 363       handleComparison(C, OrigExpr, Call.getReturnValue(), Call.getArgSVal(0),
 364                          Call.getArgSVal(1), Op);
 365       return;
 366     } else if (isRandomIncrOrDecrOperator(Op)) {
 367       const auto *OrigExpr = Call.getOriginExpr();
 368       if (!OrigExpr)
 369         return;
 370
 371       if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
 372         if (Call.getNumArgs() >= 1 &&
 373               Call.getArgExpr(0)->getType()->isIntegralOrEnumerationType()) {
 374           handleRandomIncrOrDecr(C, OrigExpr, Op, Call.getReturnValue(),
 375                                  InstCall->getCXXThisVal(), Call.getArgSVal(0));
 376           return;
 377         }
 378       } else if (Call.getNumArgs() >= 2) {
 379         const Expr *FirstArg = Call.getArgExpr(0);
 380         const Expr *SecondArg = Call.getArgExpr(1);
 381         const QualType FirstType = FirstArg->getType();
 382         const QualType SecondType = SecondArg->getType();
 383
 384         if (FirstType->isIntegralOrEnumerationType() ||
 385             SecondType->isIntegralOrEnumerationType()) {
 386           // In case of operator+ the iterator can be either on the LHS (eg.:
 387           // it + 1), or on the RHS (eg.: 1 + it). Both cases are modeled.
 388           const bool IsIterFirst = FirstType->isStructureOrClassType();
 389           const SVal FirstArg = Call.getArgSVal(0);
 390           const SVal SecondArg = Call.getArgSVal(1);
 391           const SVal &Iterator = IsIterFirst ? FirstArg : SecondArg;
 392           const SVal &Amount = IsIterFirst ? SecondArg : FirstArg;
 393
 394           handleRandomIncrOrDecr(C, OrigExpr, Op, Call.getReturnValue(),
 395                                  Iterator, Amount);
 396           return;
 397         }
 398       }
 399     } else if (isIncrementOperator(Op)) {
 400       if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
 401         handleIncrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(),
 402                         Call.getNumArgs());
 403         return;
 404       }
 405
 406       handleIncrement(C, Call.getReturnValue(), Call.getArgSVal(0),
 407                       Call.getNumArgs());
 408       return;
 409     } else if (isDecrementOperator(Op)) {
 410       if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
 411         handleDecrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(),
 412                         Call.getNumArgs());
 413         return;
 414       }
 415
 416       handleDecrement(C, Call.getReturnValue(), Call.getArgSVal(0),
 417                         Call.getNumArgs());
 418       return;
 419     }
 420 }
 421
 422 void
 423 IteratorModeling::handleAdvanceLikeFunction(CheckerContext &C,
 424                                             const CallEvent &Call,
 425                                             const Expr *OrigExpr,
 426                                             const AdvanceFn *Handler) const {
 427   if (!C.wasInlined) {
 428     (this->**Handler)(C, OrigExpr, Call.getReturnValue(),
 429                       Call.getArgSVal(0), Call.getArgSVal(1));
 430     return;
 431   }
 432
 433   // If std::advance() was inlined, but a non-standard function it calls inside
 434   // was not, then we have to model it explicitly
 435   const auto *IdInfo = cast<FunctionDecl>(Call.getDecl())->getIdentifier();
 436   if (IdInfo) {
 437     if (IdInfo->getName() == "advance") {
 438       if (noChangeInAdvance(C, Call.getArgSVal(0), OrigExpr)) {
 439         (this->**Handler)(C, OrigExpr, Call.getReturnValue(),
 440                           Call.getArgSVal(0), Call.getArgSVal(1));
 441       }
 442     }
 443   }
 444 }
 445
 446 void IteratorModeling::handleComparison(CheckerContext &C, const Expr *CE,
 447                                        SVal RetVal, const SVal &LVal,
 448                                        const SVal &RVal,
 449                                        OverloadedOperatorKind Op) const {
 450   // Record the operands and the operator of the comparison for the next
 451   // evalAssume, if the result is a symbolic expression. If it is a concrete
 452   // value (only one branch is possible), then transfer the state between
 453   // the operands according to the operator and the result
 454    auto State = C.getState();
 455   const auto *LPos = getIteratorPosition(State, LVal);
 456   const auto *RPos = getIteratorPosition(State, RVal);
 457   const MemRegion *Cont = nullptr;
 458   if (LPos) {
 459     Cont = LPos->getContainer();
 460   } else if (RPos) {
 461     Cont = RPos->getContainer();
 462   }
 463   if (!Cont)
 464     return;
 465
 466   // At least one of the iterators has recorded positions. If one of them does
 467   // not then create a new symbol for the offset.
 468   SymbolRef Sym;
 469   if (!LPos || !RPos) {
 470     auto &SymMgr = C.getSymbolManager();
 471     Sym = SymMgr.conjureSymbol(CE, C.getLocationContext(),
 472                                C.getASTContext().LongTy, C.blockCount());
 473     State = assumeNoOverflow(State, Sym, 4);
 474   }
 475
 476   if (!LPos) {
 477     State = setIteratorPosition(State, LVal,
 478                                 IteratorPosition::getPosition(Cont, Sym));
 479     LPos = getIteratorPosition(State, LVal);
 480   } else if (!RPos) {
 481     State = setIteratorPosition(State, RVal,
 482                                 IteratorPosition::getPosition(Cont, Sym));
 483     RPos = getIteratorPosition(State, RVal);
 484   }
 485
 486   // If the value for which we just tried to set a new iterator position is
 487   // an `SVal`for which no iterator position can be set then the setting was
 488   // unsuccessful. We cannot handle the comparison in this case.
 489   if (!LPos || !RPos)
 490     return;
 491
 492   // We cannot make assumptions on `UnknownVal`. Let us conjure a symbol
 493   // instead.
 494   if (RetVal.isUnknown()) {
 495     auto &SymMgr = C.getSymbolManager();
 496     auto *LCtx = C.getLocationContext();
 497     RetVal = nonloc::SymbolVal(SymMgr.conjureSymbol(
 498         CE, LCtx, C.getASTContext().BoolTy, C.blockCount()));
 499     State = State->BindExpr(CE, LCtx, RetVal);
 500   }
 501
 502   processComparison(C, State, LPos->getOffset(), RPos->getOffset(), RetVal, Op);
 503 }
 504
 505 void IteratorModeling::processComparison(CheckerContext &C,
 506                                          ProgramStateRef State, SymbolRef Sym1,
 507                                          SymbolRef Sym2, const SVal &RetVal,
 508                                          OverloadedOperatorKind Op) const {
 509   if (const auto TruthVal = RetVal.getAs<nonloc::ConcreteInt>()) {
 510     if ((State = relateSymbols(State, Sym1, Sym2,
 511                               (Op == OO_EqualEqual) ==
 512                                (TruthVal->getValue() != 0)))) {
 513       C.addTransition(State);
 514     } else {
 515       C.generateSink(State, C.getPredecessor());
 516     }
 517     return;
 518   }
 519
 520   const auto ConditionVal = RetVal.getAs<DefinedSVal>();
 521   if (!ConditionVal)
 522     return;
 523
 524   if (auto StateTrue = relateSymbols(State, Sym1, Sym2, Op == OO_EqualEqual)) {
 525     StateTrue = StateTrue->assume(*ConditionVal, true);
 526     C.addTransition(StateTrue);
 527   }
 528
 529   if (auto StateFalse = relateSymbols(State, Sym1, Sym2, Op != OO_EqualEqual)) {
 530     StateFalse = StateFalse->assume(*ConditionVal, false);
 531     C.addTransition(StateFalse);
 532   }
 533 }
 534
 535 void IteratorModeling::handleIncrement(CheckerContext &C, const SVal &RetVal,
 536                                        const SVal &Iter, bool Postfix) const {
 537   // Increment the symbolic expressions which represents the position of the
 538   // iterator
 539   auto State = C.getState();
 540   auto &BVF = C.getSymbolManager().getBasicVals();
 541
 542   const auto *Pos = getIteratorPosition(State, Iter);
 543   if (!Pos)
 544     return;
 545
 546   auto NewState =
 547     advancePosition(State, Iter, OO_Plus,
 548                     nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
 549   assert(NewState &&
 550          "Advancing position by concrete int should always be successful");
 551
 552   const auto *NewPos = getIteratorPosition(NewState, Iter);
 553   assert(NewPos &&
 554          "Iterator should have position after successful advancement");
 555
 556   State = setIteratorPosition(State, Iter, *NewPos);
 557   State = setIteratorPosition(State, RetVal, Postfix ? *Pos : *NewPos);
 558   C.addTransition(State);
 559 }
 560
 561 void IteratorModeling::handleDecrement(CheckerContext &C, const SVal &RetVal,
 562                                        const SVal &Iter, bool Postfix) const {
 563   // Decrement the symbolic expressions which represents the position of the
 564   // iterator
 565   auto State = C.getState();
 566   auto &BVF = C.getSymbolManager().getBasicVals();
 567
 568   const auto *Pos = getIteratorPosition(State, Iter);
 569   if (!Pos)
 570     return;
 571
 572   auto NewState =
 573     advancePosition(State, Iter, OO_Minus,
 574                     nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
 575   assert(NewState &&
 576          "Advancing position by concrete int should always be successful");
 577
 578   const auto *NewPos = getIteratorPosition(NewState, Iter);
 579   assert(NewPos &&
 580          "Iterator should have position after successful advancement");
 581
 582   State = setIteratorPosition(State, Iter, *NewPos);
 583   State = setIteratorPosition(State, RetVal, Postfix ? *Pos : *NewPos);
 584   C.addTransition(State);
 585 }
 586
 587 void IteratorModeling::handleRandomIncrOrDecr(CheckerContext &C, const Expr *CE,
 588                                               OverloadedOperatorKind Op,
 589                                               const SVal &RetVal,
 590                                               const SVal &Iterator,
 591                                               const SVal &Amount) const {
 592   // Increment or decrement the symbolic expressions which represents the
 593   // position of the iterator
 594   auto State = C.getState();
 595
 596   const auto *Pos = getIteratorPosition(State, Iterator);
 597   if (!Pos)
 598     return;
 599
 600   const auto *Value = &Amount;
 601   SVal Val;
 602   if (auto LocAmount = Amount.getAs<Loc>()) {
 603     Val = State->getRawSVal(*LocAmount);
 604     Value = &Val;
 605   }
 606
 607   const auto &TgtVal =
 608       (Op == OO_PlusEqual || Op == OO_MinusEqual) ? Iterator : RetVal;
 609
 610   // `AdvancedState` is a state where the position of `LHS` is advanced. We
 611   // only need this state to retrieve the new position, but we do not want
 612   // to change the position of `LHS` (in every case).
 613   auto AdvancedState = advancePosition(State, Iterator, Op, *Value);
 614   if (AdvancedState) {
 615     const auto *NewPos = getIteratorPosition(AdvancedState, Iterator);
 616     assert(NewPos &&
 617            "Iterator should have position after successful advancement");
 618
 619     State = setIteratorPosition(State, TgtVal, *NewPos);
 620     C.addTransition(State);
 621   } else {
 622     assignToContainer(C, CE, TgtVal, Pos->getContainer());
 623   }
 624 }
 625
 626 void IteratorModeling::handlePtrIncrOrDecr(CheckerContext &C,
 627                                            const Expr *Iterator,
 628                                            OverloadedOperatorKind OK,
 629                                            SVal Offset) const {
 630   if (!isa<DefinedSVal>(Offset))
 631     return;
 632
 633   QualType PtrType = Iterator->getType();
 634   if (!PtrType->isPointerType())
 635     return;
 636   QualType ElementType = PtrType->getPointeeType();
 637
 638   ProgramStateRef State = C.getState();
 639   SVal OldVal = State->getSVal(Iterator, C.getLocationContext());
 640
 641   const IteratorPosition *OldPos = getIteratorPosition(State, OldVal);
 642   if (!OldPos)
 643     return;
 644
 645   SVal NewVal;
 646   if (OK == OO_Plus || OK == OO_PlusEqual) {
 647     NewVal = State->getLValue(ElementType, Offset, OldVal);
 648   } else {
 649     auto &SVB = C.getSValBuilder();
 650     SVal NegatedOffset = SVB.evalMinus(Offset.castAs<NonLoc>());
 651     NewVal = State->getLValue(ElementType, NegatedOffset, OldVal);
 652   }
 653
 654   // `AdvancedState` is a state where the position of `Old` is advanced. We
 655   // only need this state to retrieve the new position, but we do not want
 656   // ever to change the position of `OldVal`.
 657   auto AdvancedState = advancePosition(State, OldVal, OK, Offset);
 658   if (AdvancedState) {
 659     const IteratorPosition *NewPos = getIteratorPosition(AdvancedState, OldVal);
 660     assert(NewPos &&
 661            "Iterator should have position after successful advancement");
 662
 663     ProgramStateRef NewState = setIteratorPosition(State, NewVal, *NewPos);
 664     C.addTransition(NewState);
 665   } else {
 666     assignToContainer(C, Iterator, NewVal, OldPos->getContainer());
 667   }
 668 }
 669
 670 void IteratorModeling::handleAdvance(CheckerContext &C, const Expr *CE,
 671                                      SVal RetVal, SVal Iter,
 672                                      SVal Amount) const {
 673   handleRandomIncrOrDecr(C, CE, OO_PlusEqual, RetVal, Iter, Amount);
 674 }
 675
 676 void IteratorModeling::handlePrev(CheckerContext &C, const Expr *CE,
 677                                   SVal RetVal, SVal Iter, SVal Amount) const {
 678   handleRandomIncrOrDecr(C, CE, OO_Minus, RetVal, Iter, Amount);
 679 }
 680
 681 void IteratorModeling::handleNext(CheckerContext &C, const Expr *CE,
 682                                   SVal RetVal, SVal Iter, SVal Amount) const {
 683   handleRandomIncrOrDecr(C, CE, OO_Plus, RetVal, Iter, Amount);
 684 }
 685
 686 void IteratorModeling::assignToContainer(CheckerContext &C, const Expr *CE,
 687                                          const SVal &RetVal,
 688                                          const MemRegion *Cont) const {
 689   Cont = Cont->getMostDerivedObjectRegion();
 690
 691   auto State = C.getState();
 692   const auto *LCtx = C.getLocationContext();
 693   State = createIteratorPosition(State, RetVal, Cont, CE, LCtx, C.blockCount());
 694
 695   C.addTransition(State);
 696 }
 697
 698 bool IteratorModeling::noChangeInAdvance(CheckerContext &C, SVal Iter,
 699                                          const Expr *CE) const {
 700   // Compare the iterator position before and after the call. (To be called
 701   // from `checkPostCall()`.)
 702   const auto StateAfter = C.getState();
 703
 704   const auto *PosAfter = getIteratorPosition(StateAfter, Iter);
 705   // If we have no position after the call of `std::advance`, then we are not
 706   // interested. (Modeling of an inlined `std::advance()` should not remove the
 707   // position in any case.)
 708   if (!PosAfter)
 709     return false;
 710
 711   const ExplodedNode *N = findCallEnter(C.getPredecessor(), CE);
 712   assert(N && "Any call should have a `CallEnter` node.");
 713
 714   const auto StateBefore = N->getState();
 715   const auto *PosBefore = getIteratorPosition(StateBefore, Iter);
 716   // FIXME: `std::advance()` should not create a new iterator position but
 717   //        change existing ones. However, in case of iterators implemented as
 718   //        pointers the handling of parameters in `std::advance()`-like
 719   //        functions is still incomplete which may result in cases where
 720   //        the new position is assigned to the wrong pointer. This causes
 721   //        crash if we use an assertion here.
 722   if (!PosBefore)
 723     return false;
 724
 725   return PosBefore->getOffset() == PosAfter->getOffset();
 726 }
 727
 728 void IteratorModeling::printState(raw_ostream &Out, ProgramStateRef State,
 729                                   const char *NL, const char *Sep) const {
 730   auto SymbolMap = State->get<IteratorSymbolMap>();
 731   auto RegionMap = State->get<IteratorRegionMap>();
 732   // Use a counter to add newlines before every line except the first one.
 733   unsigned Count = 0;
 734
 735   if (!SymbolMap.isEmpty() || !RegionMap.isEmpty()) {
 736     Out << Sep << "Iterator Positions :" << NL;
 737     for (const auto &Sym : SymbolMap) {
 738       if (Count++)
 739         Out << NL;
 740
 741       Sym.first->dumpToStream(Out);
 742       Out << " : ";
 743       const auto Pos = Sym.second;
 744       Out << (Pos.isValid() ? "Valid" : "Invalid") << " ; Container == ";
 745       Pos.getContainer()->dumpToStream(Out);
 746       Out<<" ; Offset == ";
 747       Pos.getOffset()->dumpToStream(Out);
 748     }
 749
 750     for (const auto &Reg : RegionMap) {
 751       if (Count++)
 752         Out << NL;
 753
 754       Reg.first->dumpToStream(Out);
 755       Out << " : ";
 756       const auto Pos = Reg.second;
 757       Out << (Pos.isValid() ? "Valid" : "Invalid") << " ; Container == ";
 758       Pos.getContainer()->dumpToStream(Out);
 759       Out<<" ; Offset == ";
 760       Pos.getOffset()->dumpToStream(Out);
 761     }
 762   }
 763 }
 764
 765 namespace {
 766
 767 bool isSimpleComparisonOperator(OverloadedOperatorKind OK) {
 768   return OK == OO_EqualEqual || OK == OO_ExclaimEqual;
 769 }
 770
 771 bool isSimpleComparisonOperator(BinaryOperatorKind OK) {
 772   return OK == BO_EQ || OK == BO_NE;
 773 }
 774
 775 ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val) {
 776   if (auto Reg = Val.getAsRegion()) {
 777     Reg = Reg->getMostDerivedObjectRegion();
 778     return State->remove<IteratorRegionMap>(Reg);
 779   } else if (const auto Sym = Val.getAsSymbol()) {
 780     return State->remove<IteratorSymbolMap>(Sym);
 781   } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
 782     return State->remove<IteratorRegionMap>(LCVal->getRegion());
 783   }
 784   return nullptr;
 785 }
 786
 787 ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1,
 788                               SymbolRef Sym2, bool Equal) {
 789   auto &SVB = State->getStateManager().getSValBuilder();
 790
 791   // FIXME: This code should be reworked as follows:
 792   // 1. Subtract the operands using evalBinOp().
 793   // 2. Assume that the result doesn't overflow.
 794   // 3. Compare the result to 0.
 795   // 4. Assume the result of the comparison.
 796   const auto comparison =
 797     SVB.evalBinOp(State, BO_EQ, nonloc::SymbolVal(Sym1),
 798                   nonloc::SymbolVal(Sym2), SVB.getConditionType());
 799
 800   assert(isa<DefinedSVal>(comparison) &&
 801          "Symbol comparison must be a `DefinedSVal`");
 802
 803   auto NewState = State->assume(comparison.castAs<DefinedSVal>(), Equal);
 804   if (!NewState)
 805     return nullptr;
 806
 807   if (const auto CompSym = comparison.getAsSymbol()) {
 808     assert(isa<SymIntExpr>(CompSym) &&
 809            "Symbol comparison must be a `SymIntExpr`");
 810     assert(BinaryOperator::isComparisonOp(
 811                cast<SymIntExpr>(CompSym)->getOpcode()) &&
 812            "Symbol comparison must be a comparison");
 813     return assumeNoOverflow(NewState, cast<SymIntExpr>(CompSym)->getLHS(), 2);
 814   }
 815
 816   return NewState;
 817 }
 818
 819 bool isBoundThroughLazyCompoundVal(const Environment &Env,
 820                                    const MemRegion *Reg) {
 821   for (const auto &Binding : Env) {
 822     if (const auto LCVal = Binding.second.getAs<nonloc::LazyCompoundVal>()) {
 823       if (LCVal->getRegion() == Reg)
 824         return true;
 825     }
 826   }
 827
 828   return false;
 829 }
 830
 831 const ExplodedNode *findCallEnter(const ExplodedNode *Node, const Expr *Call) {
 832   while (Node) {
 833     ProgramPoint PP = Node->getLocation();
 834     if (auto Enter = PP.getAs<CallEnter>()) {
 835       if (Enter->getCallExpr() == Call)
 836         break;
 837     }
 838
 839     Node = Node->getFirstPred();
 840   }
 841
 842   return Node;
 843 }
 844
 845 } // namespace
 846
 847 void ento::registerIteratorModeling(CheckerManager &mgr) {
 848   mgr.registerChecker<IteratorModeling>();
 849 }
 850
 851 bool ento::shouldRegisterIteratorModeling(const CheckerManager &mgr) {
 852   return true;
 853 }