contrib/llvm-project/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp

   1 //===- ExprEngine.cpp - Path-Sensitive Expression-Level Dataflow ----------===//
   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 //  This file defines a meta-engine for path-sensitive dataflow analysis that
  10 //  is built on CoreEngine, but provides the boilerplate to execute transfer
  11 //  functions and build the ExplodedGraph at the expression level.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
  16 #include "PrettyStackTraceLocationContext.h"
  17 #include "clang/AST/ASTContext.h"
  18 #include "clang/AST/Decl.h"
  19 #include "clang/AST/DeclBase.h"
  20 #include "clang/AST/DeclCXX.h"
  21 #include "clang/AST/DeclObjC.h"
  22 #include "clang/AST/Expr.h"
  23 #include "clang/AST/ExprCXX.h"
  24 #include "clang/AST/ExprObjC.h"
  25 #include "clang/AST/ParentMap.h"
  26 #include "clang/AST/PrettyPrinter.h"
  27 #include "clang/AST/Stmt.h"
  28 #include "clang/AST/StmtCXX.h"
  29 #include "clang/AST/StmtObjC.h"
  30 #include "clang/AST/Type.h"
  31 #include "clang/Analysis/AnalysisDeclContext.h"
  32 #include "clang/Analysis/CFG.h"
  33 #include "clang/Analysis/ConstructionContext.h"
  34 #include "clang/Analysis/ProgramPoint.h"
  35 #include "clang/Basic/IdentifierTable.h"
  36 #include "clang/Basic/JsonSupport.h"
  37 #include "clang/Basic/LLVM.h"
  38 #include "clang/Basic/LangOptions.h"
  39 #include "clang/Basic/PrettyStackTrace.h"
  40 #include "clang/Basic/SourceLocation.h"
  41 #include "clang/Basic/SourceManager.h"
  42 #include "clang/Basic/Specifiers.h"
  43 #include "clang/StaticAnalyzer/Core/AnalyzerOptions.h"
  44 #include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
  45 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
  46 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
  47 #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
  48 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
  49 #include "clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h"
  50 #include "clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h"
  51 #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
  52 #include "clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h"
  53 #include "clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h"
  54 #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
  55 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
  56 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
  57 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h"
  58 #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
  59 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
  60 #include "clang/StaticAnalyzer/Core/PathSensitive/Store.h"
  61 #include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h"
  62 #include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h"
  63 #include "llvm/ADT/APSInt.h"
  64 #include "llvm/ADT/DenseMap.h"
  65 #include "llvm/ADT/ImmutableMap.h"
  66 #include "llvm/ADT/ImmutableSet.h"
  67 #include "llvm/ADT/Optional.h"
  68 #include "llvm/ADT/SmallVector.h"
  69 #include "llvm/ADT/Statistic.h"
  70 #include "llvm/Support/Casting.h"
  71 #include "llvm/Support/Compiler.h"
  72 #include "llvm/Support/DOTGraphTraits.h"
  73 #include "llvm/Support/ErrorHandling.h"
  74 #include "llvm/Support/GraphWriter.h"
  75 #include "llvm/Support/SaveAndRestore.h"
  76 #include "llvm/Support/raw_ostream.h"
  77 #include <cassert>
  78 #include <cstdint>
  79 #include <memory>
  80 #include <string>
  81 #include <tuple>
  82 #include <utility>
  83 #include <vector>
  84
  85 using namespace clang;
  86 using namespace ento;
  87
  88 #define DEBUG_TYPE "ExprEngine"
  89
  90 STATISTIC(NumRemoveDeadBindings,
  91             "The # of times RemoveDeadBindings is called");
  92 STATISTIC(NumMaxBlockCountReached,
  93             "The # of aborted paths due to reaching the maximum block count in "
  94             "a top level function");
  95 STATISTIC(NumMaxBlockCountReachedInInlined,
  96             "The # of aborted paths due to reaching the maximum block count in "
  97             "an inlined function");
  98 STATISTIC(NumTimesRetriedWithoutInlining,
  99             "The # of times we re-evaluated a call without inlining");
 100
 101 //===----------------------------------------------------------------------===//
 102 // Internal program state traits.
 103 //===----------------------------------------------------------------------===//
 104
 105 namespace {
 106
 107 // When modeling a C++ constructor, for a variety of reasons we need to track
 108 // the location of the object for the duration of its ConstructionContext.
 109 // ObjectsUnderConstruction maps statements within the construction context
 110 // to the object's location, so that on every such statement the location
 111 // could have been retrieved.
 112
 113 /// ConstructedObjectKey is used for being able to find the path-sensitive
 114 /// memory region of a freshly constructed object while modeling the AST node
 115 /// that syntactically represents the object that is being constructed.
 116 /// Semantics of such nodes may sometimes require access to the region that's
 117 /// not otherwise present in the program state, or to the very fact that
 118 /// the construction context was present and contained references to these
 119 /// AST nodes.
 120 class ConstructedObjectKey {
 121   using ConstructedObjectKeyImpl =
 122       std::pair<ConstructionContextItem, const LocationContext *>;
 123   const ConstructedObjectKeyImpl Impl;
 124
 125 public:
 126   explicit ConstructedObjectKey(const ConstructionContextItem &Item,
 127                        const LocationContext *LC)
 128       : Impl(Item, LC) {}
 129
 130   const ConstructionContextItem &getItem() const { return Impl.first; }
 131   const LocationContext *getLocationContext() const { return Impl.second; }
 132
 133   ASTContext &getASTContext() const {
 134     return getLocationContext()->getDecl()->getASTContext();
 135   }
 136
 137   void printJson(llvm::raw_ostream &Out, PrinterHelper *Helper,
 138                  PrintingPolicy &PP) const {
 139     const Stmt *S = getItem().getStmtOrNull();
 140     const CXXCtorInitializer *I = nullptr;
 141     if (!S)
 142       I = getItem().getCXXCtorInitializer();
 143
 144     if (S)
 145       Out << "\"stmt_id\": " << S->getID(getASTContext());
 146     else
 147       Out << "\"init_id\": " << I->getID(getASTContext());
 148
 149     // Kind
 150     Out << ", \"kind\": \"" << getItem().getKindAsString()
 151         << "\", \"argument_index\": ";
 152
 153     if (getItem().getKind() == ConstructionContextItem::ArgumentKind)
 154       Out << getItem().getIndex();
 155     else
 156       Out << "null";
 157
 158     // Pretty-print
 159     Out << ", \"pretty\": ";
 160
 161     if (S) {
 162       S->printJson(Out, Helper, PP, /*AddQuotes=*/true);
 163     } else {
 164       Out << '\"' << I->getAnyMember()->getDeclName() << '\"';
 165     }
 166   }
 167
 168   void Profile(llvm::FoldingSetNodeID &ID) const {
 169     ID.Add(Impl.first);
 170     ID.AddPointer(Impl.second);
 171   }
 172
 173   bool operator==(const ConstructedObjectKey &RHS) const {
 174     return Impl == RHS.Impl;
 175   }
 176
 177   bool operator<(const ConstructedObjectKey &RHS) const {
 178     return Impl < RHS.Impl;
 179   }
 180 };
 181 } // namespace
 182
 183 typedef llvm::ImmutableMap<ConstructedObjectKey, SVal>
 184     ObjectsUnderConstructionMap;
 185 REGISTER_TRAIT_WITH_PROGRAMSTATE(ObjectsUnderConstruction,
 186                                  ObjectsUnderConstructionMap)
 187
 188 //===----------------------------------------------------------------------===//
 189 // Engine construction and deletion.
 190 //===----------------------------------------------------------------------===//
 191
 192 static const char* TagProviderName = "ExprEngine";
 193
 194 ExprEngine::ExprEngine(cross_tu::CrossTranslationUnitContext &CTU,
 195                        AnalysisManager &mgr, SetOfConstDecls *VisitedCalleesIn,
 196                        FunctionSummariesTy *FS, InliningModes HowToInlineIn)
 197     : CTU(CTU), IsCTUEnabled(mgr.getAnalyzerOptions().IsNaiveCTUEnabled),
 198       AMgr(mgr), AnalysisDeclContexts(mgr.getAnalysisDeclContextManager()),
 199       Engine(*this, FS, mgr.getAnalyzerOptions()), G(Engine.getGraph()),
 200       StateMgr(getContext(), mgr.getStoreManagerCreator(),
 201                mgr.getConstraintManagerCreator(), G.getAllocator(), this),
 202       SymMgr(StateMgr.getSymbolManager()), MRMgr(StateMgr.getRegionManager()),
 203       svalBuilder(StateMgr.getSValBuilder()), ObjCNoRet(mgr.getASTContext()),
 204       BR(mgr, *this), VisitedCallees(VisitedCalleesIn),
 205       HowToInline(HowToInlineIn) {
 206   unsigned TrimInterval = mgr.options.GraphTrimInterval;
 207   if (TrimInterval != 0) {
 208     // Enable eager node reclamation when constructing the ExplodedGraph.
 209     G.enableNodeReclamation(TrimInterval);
 210   }
 211 }
 212
 213 //===----------------------------------------------------------------------===//
 214 // Utility methods.
 215 //===----------------------------------------------------------------------===//
 216
 217 ProgramStateRef ExprEngine::getInitialState(const LocationContext *InitLoc) {
 218   ProgramStateRef state = StateMgr.getInitialState(InitLoc);
 219   const Decl *D = InitLoc->getDecl();
 220
 221   // Preconditions.
 222   // FIXME: It would be nice if we had a more general mechanism to add
 223   // such preconditions.  Some day.
 224   do {
 225     if (const auto *FD = dyn_cast<FunctionDecl>(D)) {
 226       // Precondition: the first argument of 'main' is an integer guaranteed
 227       //  to be > 0.
 228       const IdentifierInfo *II = FD->getIdentifier();
 229       if (!II || !(II->getName() == "main" && FD->getNumParams() > 0))
 230         break;
 231
 232       const ParmVarDecl *PD = FD->getParamDecl(0);
 233       QualType T = PD->getType();
 234       const auto *BT = dyn_cast<BuiltinType>(T);
 235       if (!BT || !BT->isInteger())
 236         break;
 237
 238       const MemRegion *R = state->getRegion(PD, InitLoc);
 239       if (!R)
 240         break;
 241
 242       SVal V = state->getSVal(loc::MemRegionVal(R));
 243       SVal Constraint_untested = evalBinOp(state, BO_GT, V,
 244                                            svalBuilder.makeZeroVal(T),
 245                                            svalBuilder.getConditionType());
 246
 247       Optional<DefinedOrUnknownSVal> Constraint =
 248           Constraint_untested.getAs<DefinedOrUnknownSVal>();
 249
 250       if (!Constraint)
 251         break;
 252
 253       if (ProgramStateRef newState = state->assume(*Constraint, true))
 254         state = newState;
 255     }
 256     break;
 257   }
 258   while (false);
 259
 260   if (const auto *MD = dyn_cast<ObjCMethodDecl>(D)) {
 261     // Precondition: 'self' is always non-null upon entry to an Objective-C
 262     // method.
 263     const ImplicitParamDecl *SelfD = MD->getSelfDecl();
 264     const MemRegion *R = state->getRegion(SelfD, InitLoc);
 265     SVal V = state->getSVal(loc::MemRegionVal(R));
 266
 267     if (Optional<Loc> LV = V.getAs<Loc>()) {
 268       // Assume that the pointer value in 'self' is non-null.
 269       state = state->assume(*LV, true);
 270       assert(state && "'self' cannot be null");
 271     }
 272   }
 273
 274   if (const auto *MD = dyn_cast<CXXMethodDecl>(D)) {
 275     if (!MD->isStatic()) {
 276       // Precondition: 'this' is always non-null upon entry to the
 277       // top-level function.  This is our starting assumption for
 278       // analyzing an "open" program.
 279       const StackFrameContext *SFC = InitLoc->getStackFrame();
 280       if (SFC->getParent() == nullptr) {
 281         loc::MemRegionVal L = svalBuilder.getCXXThis(MD, SFC);
 282         SVal V = state->getSVal(L);
 283         if (Optional<Loc> LV = V.getAs<Loc>()) {
 284           state = state->assume(*LV, true);
 285           assert(state && "'this' cannot be null");
 286         }
 287       }
 288     }
 289   }
 290
 291   return state;
 292 }
 293
 294 ProgramStateRef ExprEngine::createTemporaryRegionIfNeeded(
 295     ProgramStateRef State, const LocationContext *LC,
 296     const Expr *InitWithAdjustments, const Expr *Result,
 297     const SubRegion **OutRegionWithAdjustments) {
 298   // FIXME: This function is a hack that works around the quirky AST
 299   // we're often having with respect to C++ temporaries. If only we modelled
 300   // the actual execution order of statements properly in the CFG,
 301   // all the hassle with adjustments would not be necessary,
 302   // and perhaps the whole function would be removed.
 303   SVal InitValWithAdjustments = State->getSVal(InitWithAdjustments, LC);
 304   if (!Result) {
 305     // If we don't have an explicit result expression, we're in "if needed"
 306     // mode. Only create a region if the current value is a NonLoc.
 307     if (!isa<NonLoc>(InitValWithAdjustments)) {
 308       if (OutRegionWithAdjustments)
 309         *OutRegionWithAdjustments = nullptr;
 310       return State;
 311     }
 312     Result = InitWithAdjustments;
 313   } else {
 314     // We need to create a region no matter what. Make sure we don't try to
 315     // stuff a Loc into a non-pointer temporary region.
 316     assert(!isa<Loc>(InitValWithAdjustments) ||
 317            Loc::isLocType(Result->getType()) ||
 318            Result->getType()->isMemberPointerType());
 319   }
 320
 321   ProgramStateManager &StateMgr = State->getStateManager();
 322   MemRegionManager &MRMgr = StateMgr.getRegionManager();
 323   StoreManager &StoreMgr = StateMgr.getStoreManager();
 324
 325   // MaterializeTemporaryExpr may appear out of place, after a few field and
 326   // base-class accesses have been made to the object, even though semantically
 327   // it is the whole object that gets materialized and lifetime-extended.
 328   //
 329   // For example:
 330   //
 331   //   `-MaterializeTemporaryExpr
 332   //     `-MemberExpr
 333   //       `-CXXTemporaryObjectExpr
 334   //
 335   // instead of the more natural
 336   //
 337   //   `-MemberExpr
 338   //     `-MaterializeTemporaryExpr
 339   //       `-CXXTemporaryObjectExpr
 340   //
 341   // Use the usual methods for obtaining the expression of the base object,
 342   // and record the adjustments that we need to make to obtain the sub-object
 343   // that the whole expression 'Ex' refers to. This trick is usual,
 344   // in the sense that CodeGen takes a similar route.
 345
 346   SmallVector<const Expr *, 2> CommaLHSs;
 347   SmallVector<SubobjectAdjustment, 2> Adjustments;
 348
 349   const Expr *Init = InitWithAdjustments->skipRValueSubobjectAdjustments(
 350       CommaLHSs, Adjustments);
 351
 352   // Take the region for Init, i.e. for the whole object. If we do not remember
 353   // the region in which the object originally was constructed, come up with
 354   // a new temporary region out of thin air and copy the contents of the object
 355   // (which are currently present in the Environment, because Init is an rvalue)
 356   // into that region. This is not correct, but it is better than nothing.
 357   const TypedValueRegion *TR = nullptr;
 358   if (const auto *MT = dyn_cast<MaterializeTemporaryExpr>(Result)) {
 359     if (Optional<SVal> V = getObjectUnderConstruction(State, MT, LC)) {
 360       State = finishObjectConstruction(State, MT, LC);
 361       State = State->BindExpr(Result, LC, *V);
 362       return State;
 363     } else {
 364       StorageDuration SD = MT->getStorageDuration();
 365       // If this object is bound to a reference with static storage duration, we
 366       // put it in a different region to prevent "address leakage" warnings.
 367       if (SD == SD_Static || SD == SD_Thread) {
 368         TR = MRMgr.getCXXStaticTempObjectRegion(Init);
 369       } else {
 370         TR = MRMgr.getCXXTempObjectRegion(Init, LC);
 371       }
 372     }
 373   } else {
 374     TR = MRMgr.getCXXTempObjectRegion(Init, LC);
 375   }
 376
 377   SVal Reg = loc::MemRegionVal(TR);
 378   SVal BaseReg = Reg;
 379
 380   // Make the necessary adjustments to obtain the sub-object.
 381   for (const SubobjectAdjustment &Adj : llvm::reverse(Adjustments)) {
 382     switch (Adj.Kind) {
 383     case SubobjectAdjustment::DerivedToBaseAdjustment:
 384       Reg = StoreMgr.evalDerivedToBase(Reg, Adj.DerivedToBase.BasePath);
 385       break;
 386     case SubobjectAdjustment::FieldAdjustment:
 387       Reg = StoreMgr.getLValueField(Adj.Field, Reg);
 388       break;
 389     case SubobjectAdjustment::MemberPointerAdjustment:
 390       // FIXME: Unimplemented.
 391       State = State->invalidateRegions(Reg, InitWithAdjustments,
 392                                        currBldrCtx->blockCount(), LC, true,
 393                                        nullptr, nullptr, nullptr);
 394       return State;
 395     }
 396   }
 397
 398   // What remains is to copy the value of the object to the new region.
 399   // FIXME: In other words, what we should always do is copy value of the
 400   // Init expression (which corresponds to the bigger object) to the whole
 401   // temporary region TR. However, this value is often no longer present
 402   // in the Environment. If it has disappeared, we instead invalidate TR.
 403   // Still, what we can do is assign the value of expression Ex (which
 404   // corresponds to the sub-object) to the TR's sub-region Reg. At least,
 405   // values inside Reg would be correct.
 406   SVal InitVal = State->getSVal(Init, LC);
 407   if (InitVal.isUnknown()) {
 408     InitVal = getSValBuilder().conjureSymbolVal(Result, LC, Init->getType(),
 409                                                 currBldrCtx->blockCount());
 410     State = State->bindLoc(BaseReg.castAs<Loc>(), InitVal, LC, false);
 411
 412     // Then we'd need to take the value that certainly exists and bind it
 413     // over.
 414     if (InitValWithAdjustments.isUnknown()) {
 415       // Try to recover some path sensitivity in case we couldn't
 416       // compute the value.
 417       InitValWithAdjustments = getSValBuilder().conjureSymbolVal(
 418           Result, LC, InitWithAdjustments->getType(),
 419           currBldrCtx->blockCount());
 420     }
 421     State =
 422         State->bindLoc(Reg.castAs<Loc>(), InitValWithAdjustments, LC, false);
 423   } else {
 424     State = State->bindLoc(BaseReg.castAs<Loc>(), InitVal, LC, false);
 425   }
 426
 427   // The result expression would now point to the correct sub-region of the
 428   // newly created temporary region. Do this last in order to getSVal of Init
 429   // correctly in case (Result == Init).
 430   if (Result->isGLValue()) {
 431     State = State->BindExpr(Result, LC, Reg);
 432   } else {
 433     State = State->BindExpr(Result, LC, InitValWithAdjustments);
 434   }
 435
 436   // Notify checkers once for two bindLoc()s.
 437   State = processRegionChange(State, TR, LC);
 438
 439   if (OutRegionWithAdjustments)
 440     *OutRegionWithAdjustments = cast<SubRegion>(Reg.getAsRegion());
 441   return State;
 442 }
 443
 444 ProgramStateRef
 445 ExprEngine::addObjectUnderConstruction(ProgramStateRef State,
 446                                        const ConstructionContextItem &Item,
 447                                        const LocationContext *LC, SVal V) {
 448   ConstructedObjectKey Key(Item, LC->getStackFrame());
 449   // FIXME: Currently the state might already contain the marker due to
 450   // incorrect handling of temporaries bound to default parameters.
 451   assert(!State->get<ObjectsUnderConstruction>(Key) ||
 452          Key.getItem().getKind() ==
 453              ConstructionContextItem::TemporaryDestructorKind);
 454   return State->set<ObjectsUnderConstruction>(Key, V);
 455 }
 456
 457 Optional<SVal>
 458 ExprEngine::getObjectUnderConstruction(ProgramStateRef State,
 459                                        const ConstructionContextItem &Item,
 460                                        const LocationContext *LC) {
 461   ConstructedObjectKey Key(Item, LC->getStackFrame());
 462   return Optional<SVal>::create(State->get<ObjectsUnderConstruction>(Key));
 463 }
 464
 465 ProgramStateRef
 466 ExprEngine::finishObjectConstruction(ProgramStateRef State,
 467                                      const ConstructionContextItem &Item,
 468                                      const LocationContext *LC) {
 469   ConstructedObjectKey Key(Item, LC->getStackFrame());
 470   assert(State->contains<ObjectsUnderConstruction>(Key));
 471   return State->remove<ObjectsUnderConstruction>(Key);
 472 }
 473
 474 ProgramStateRef ExprEngine::elideDestructor(ProgramStateRef State,
 475                                             const CXXBindTemporaryExpr *BTE,
 476                                             const LocationContext *LC) {
 477   ConstructedObjectKey Key({BTE, /*IsElided=*/true}, LC);
 478   // FIXME: Currently the state might already contain the marker due to
 479   // incorrect handling of temporaries bound to default parameters.
 480   return State->set<ObjectsUnderConstruction>(Key, UnknownVal());
 481 }
 482
 483 ProgramStateRef
 484 ExprEngine::cleanupElidedDestructor(ProgramStateRef State,
 485                                     const CXXBindTemporaryExpr *BTE,
 486                                     const LocationContext *LC) {
 487   ConstructedObjectKey Key({BTE, /*IsElided=*/true}, LC);
 488   assert(State->contains<ObjectsUnderConstruction>(Key));
 489   return State->remove<ObjectsUnderConstruction>(Key);
 490 }
 491
 492 bool ExprEngine::isDestructorElided(ProgramStateRef State,
 493                                     const CXXBindTemporaryExpr *BTE,
 494                                     const LocationContext *LC) {
 495   ConstructedObjectKey Key({BTE, /*IsElided=*/true}, LC);
 496   return State->contains<ObjectsUnderConstruction>(Key);
 497 }
 498
 499 bool ExprEngine::areAllObjectsFullyConstructed(ProgramStateRef State,
 500                                                const LocationContext *FromLC,
 501                                                const LocationContext *ToLC) {
 502   const LocationContext *LC = FromLC;
 503   while (LC != ToLC) {
 504     assert(LC && "ToLC must be a parent of FromLC!");
 505     for (auto I : State->get<ObjectsUnderConstruction>())
 506       if (I.first.getLocationContext() == LC)
 507         return false;
 508
 509     LC = LC->getParent();
 510   }
 511   return true;
 512 }
 513
 514
 515 //===----------------------------------------------------------------------===//
 516 // Top-level transfer function logic (Dispatcher).
 517 //===----------------------------------------------------------------------===//
 518
 519 /// evalAssume - Called by ConstraintManager. Used to call checker-specific
 520 ///  logic for handling assumptions on symbolic values.
 521 ProgramStateRef ExprEngine::processAssume(ProgramStateRef state,
 522                                               SVal cond, bool assumption) {
 523   return getCheckerManager().runCheckersForEvalAssume(state, cond, assumption);
 524 }
 525
 526 ProgramStateRef
 527 ExprEngine::processRegionChanges(ProgramStateRef state,
 528                                  const InvalidatedSymbols *invalidated,
 529                                  ArrayRef<const MemRegion *> Explicits,
 530                                  ArrayRef<const MemRegion *> Regions,
 531                                  const LocationContext *LCtx,
 532                                  const CallEvent *Call) {
 533   return getCheckerManager().runCheckersForRegionChanges(state, invalidated,
 534                                                          Explicits, Regions,
 535                                                          LCtx, Call);
 536 }
 537
 538 static void
 539 printObjectsUnderConstructionJson(raw_ostream &Out, ProgramStateRef State,
 540                                   const char *NL, const LocationContext *LCtx,
 541                                   unsigned int Space = 0, bool IsDot = false) {
 542   PrintingPolicy PP =
 543       LCtx->getAnalysisDeclContext()->getASTContext().getPrintingPolicy();
 544
 545   ++Space;
 546   bool HasItem = false;
 547
 548   // Store the last key.
 549   const ConstructedObjectKey *LastKey = nullptr;
 550   for (const auto &I : State->get<ObjectsUnderConstruction>()) {
 551     const ConstructedObjectKey &Key = I.first;
 552     if (Key.getLocationContext() != LCtx)
 553       continue;
 554
 555     if (!HasItem) {
 556       Out << "[" << NL;
 557       HasItem = true;
 558     }
 559
 560     LastKey = &Key;
 561   }
 562
 563   for (const auto &I : State->get<ObjectsUnderConstruction>()) {
 564     const ConstructedObjectKey &Key = I.first;
 565     SVal Value = I.second;
 566     if (Key.getLocationContext() != LCtx)
 567       continue;
 568
 569     Indent(Out, Space, IsDot) << "{ ";
 570     Key.printJson(Out, nullptr, PP);
 571     Out << ", \"value\": \"" << Value << "\" }";
 572
 573     if (&Key != LastKey)
 574       Out << ',';
 575     Out << NL;
 576   }
 577
 578   if (HasItem)
 579     Indent(Out, --Space, IsDot) << ']'; // End of "location_context".
 580   else {
 581     Out << "null ";
 582   }
 583 }
 584
 585 void ExprEngine::printJson(raw_ostream &Out, ProgramStateRef State,
 586                            const LocationContext *LCtx, const char *NL,
 587                            unsigned int Space, bool IsDot) const {
 588   Indent(Out, Space, IsDot) << "\"constructing_objects\": ";
 589
 590   if (LCtx && !State->get<ObjectsUnderConstruction>().isEmpty()) {
 591     ++Space;
 592     Out << '[' << NL;
 593     LCtx->printJson(Out, NL, Space, IsDot, [&](const LocationContext *LC) {
 594       printObjectsUnderConstructionJson(Out, State, NL, LC, Space, IsDot);
 595     });
 596
 597     --Space;
 598     Indent(Out, Space, IsDot) << "]," << NL; // End of "constructing_objects".
 599   } else {
 600     Out << "null," << NL;
 601   }
 602
 603   getCheckerManager().runCheckersForPrintStateJson(Out, State, NL, Space,
 604                                                    IsDot);
 605 }
 606
 607 void ExprEngine::processEndWorklist() {
 608   // This prints the name of the top-level function if we crash.
 609   PrettyStackTraceLocationContext CrashInfo(getRootLocationContext());
 610   getCheckerManager().runCheckersForEndAnalysis(G, BR, *this);
 611 }
 612
 613 void ExprEngine::processCFGElement(const CFGElement E, ExplodedNode *Pred,
 614                                    unsigned StmtIdx, NodeBuilderContext *Ctx) {
 615   PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext());
 616   currStmtIdx = StmtIdx;
 617   currBldrCtx = Ctx;
 618
 619   switch (E.getKind()) {
 620     case CFGElement::Statement:
 621     case CFGElement::Constructor:
 622     case CFGElement::CXXRecordTypedCall:
 623       ProcessStmt(E.castAs<CFGStmt>().getStmt(), Pred);
 624       return;
 625     case CFGElement::Initializer:
 626       ProcessInitializer(E.castAs<CFGInitializer>(), Pred);
 627       return;
 628     case CFGElement::NewAllocator:
 629       ProcessNewAllocator(E.castAs<CFGNewAllocator>().getAllocatorExpr(),
 630                           Pred);
 631       return;
 632     case CFGElement::AutomaticObjectDtor:
 633     case CFGElement::DeleteDtor:
 634     case CFGElement::BaseDtor:
 635     case CFGElement::MemberDtor:
 636     case CFGElement::TemporaryDtor:
 637       ProcessImplicitDtor(E.castAs<CFGImplicitDtor>(), Pred);
 638       return;
 639     case CFGElement::LoopExit:
 640       ProcessLoopExit(E.castAs<CFGLoopExit>().getLoopStmt(), Pred);
 641       return;
 642     case CFGElement::LifetimeEnds:
 643     case CFGElement::ScopeBegin:
 644     case CFGElement::ScopeEnd:
 645       return;
 646   }
 647 }
 648
 649 static bool shouldRemoveDeadBindings(AnalysisManager &AMgr,
 650                                      const Stmt *S,
 651                                      const ExplodedNode *Pred,
 652                                      const LocationContext *LC) {
 653   // Are we never purging state values?
 654   if (AMgr.options.AnalysisPurgeOpt == PurgeNone)
 655     return false;
 656
 657   // Is this the beginning of a basic block?
 658   if (Pred->getLocation().getAs<BlockEntrance>())
 659     return true;
 660
 661   // Is this on a non-expression?
 662   if (!isa<Expr>(S))
 663     return true;
 664
 665   // Run before processing a call.
 666   if (CallEvent::isCallStmt(S))
 667     return true;
 668
 669   // Is this an expression that is consumed by another expression?  If so,
 670   // postpone cleaning out the state.
 671   ParentMap &PM = LC->getAnalysisDeclContext()->getParentMap();
 672   return !PM.isConsumedExpr(cast<Expr>(S));
 673 }
 674
 675 void ExprEngine::removeDead(ExplodedNode *Pred, ExplodedNodeSet &Out,
 676                             const Stmt *ReferenceStmt,
 677                             const LocationContext *LC,
 678                             const Stmt *DiagnosticStmt,
 679                             ProgramPoint::Kind K) {
 680   assert((K == ProgramPoint::PreStmtPurgeDeadSymbolsKind ||
 681           ReferenceStmt == nullptr || isa<ReturnStmt>(ReferenceStmt))
 682           && "PostStmt is not generally supported by the SymbolReaper yet");
 683   assert(LC && "Must pass the current (or expiring) LocationContext");
 684
 685   if (!DiagnosticStmt) {
 686     DiagnosticStmt = ReferenceStmt;
 687     assert(DiagnosticStmt && "Required for clearing a LocationContext");
 688   }
 689
 690   NumRemoveDeadBindings++;
 691   ProgramStateRef CleanedState = Pred->getState();
 692
 693   // LC is the location context being destroyed, but SymbolReaper wants a
 694   // location context that is still live. (If this is the top-level stack
 695   // frame, this will be null.)
 696   if (!ReferenceStmt) {
 697     assert(K == ProgramPoint::PostStmtPurgeDeadSymbolsKind &&
 698            "Use PostStmtPurgeDeadSymbolsKind for clearing a LocationContext");
 699     LC = LC->getParent();
 700   }
 701
 702   const StackFrameContext *SFC = LC ? LC->getStackFrame() : nullptr;
 703   SymbolReaper SymReaper(SFC, ReferenceStmt, SymMgr, getStoreManager());
 704
 705   for (auto I : CleanedState->get<ObjectsUnderConstruction>()) {
 706     if (SymbolRef Sym = I.second.getAsSymbol())
 707       SymReaper.markLive(Sym);
 708     if (const MemRegion *MR = I.second.getAsRegion())
 709       SymReaper.markLive(MR);
 710   }
 711
 712   getCheckerManager().runCheckersForLiveSymbols(CleanedState, SymReaper);
 713
 714   // Create a state in which dead bindings are removed from the environment
 715   // and the store. TODO: The function should just return new env and store,
 716   // not a new state.
 717   CleanedState = StateMgr.removeDeadBindingsFromEnvironmentAndStore(
 718       CleanedState, SFC, SymReaper);
 719
 720   // Process any special transfer function for dead symbols.
 721   // A tag to track convenience transitions, which can be removed at cleanup.
 722   static SimpleProgramPointTag cleanupTag(TagProviderName, "Clean Node");
 723   // Call checkers with the non-cleaned state so that they could query the
 724   // values of the soon to be dead symbols.
 725   ExplodedNodeSet CheckedSet;
 726   getCheckerManager().runCheckersForDeadSymbols(CheckedSet, Pred, SymReaper,
 727                                                 DiagnosticStmt, *this, K);
 728
 729   // For each node in CheckedSet, generate CleanedNodes that have the
 730   // environment, the store, and the constraints cleaned up but have the
 731   // user-supplied states as the predecessors.
 732   StmtNodeBuilder Bldr(CheckedSet, Out, *currBldrCtx);
 733   for (const auto I : CheckedSet) {
 734     ProgramStateRef CheckerState = I->getState();
 735
 736     // The constraint manager has not been cleaned up yet, so clean up now.
 737     CheckerState =
 738         getConstraintManager().removeDeadBindings(CheckerState, SymReaper);
 739
 740     assert(StateMgr.haveEqualEnvironments(CheckerState, Pred->getState()) &&
 741            "Checkers are not allowed to modify the Environment as a part of "
 742            "checkDeadSymbols processing.");
 743     assert(StateMgr.haveEqualStores(CheckerState, Pred->getState()) &&
 744            "Checkers are not allowed to modify the Store as a part of "
 745            "checkDeadSymbols processing.");
 746
 747     // Create a state based on CleanedState with CheckerState GDM and
 748     // generate a transition to that state.
 749     ProgramStateRef CleanedCheckerSt =
 750         StateMgr.getPersistentStateWithGDM(CleanedState, CheckerState);
 751     Bldr.generateNode(DiagnosticStmt, I, CleanedCheckerSt, &cleanupTag, K);
 752   }
 753 }
 754
 755 void ExprEngine::ProcessStmt(const Stmt *currStmt, ExplodedNode *Pred) {
 756   // Reclaim any unnecessary nodes in the ExplodedGraph.
 757   G.reclaimRecentlyAllocatedNodes();
 758
 759   PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
 760                                 currStmt->getBeginLoc(),
 761                                 "Error evaluating statement");
 762
 763   // Remove dead bindings and symbols.
 764   ExplodedNodeSet CleanedStates;
 765   if (shouldRemoveDeadBindings(AMgr, currStmt, Pred,
 766                                Pred->getLocationContext())) {
 767     removeDead(Pred, CleanedStates, currStmt,
 768                                     Pred->getLocationContext());
 769   } else
 770     CleanedStates.Add(Pred);
 771
 772   // Visit the statement.
 773   ExplodedNodeSet Dst;
 774   for (const auto I : CleanedStates) {
 775     ExplodedNodeSet DstI;
 776     // Visit the statement.
 777     Visit(currStmt, I, DstI);
 778     Dst.insert(DstI);
 779   }
 780
 781   // Enqueue the new nodes onto the work list.
 782   Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx);
 783 }
 784
 785 void ExprEngine::ProcessLoopExit(const Stmt* S, ExplodedNode *Pred) {
 786   PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
 787                                 S->getBeginLoc(),
 788                                 "Error evaluating end of the loop");
 789   ExplodedNodeSet Dst;
 790   Dst.Add(Pred);
 791   NodeBuilder Bldr(Pred, Dst, *currBldrCtx);
 792   ProgramStateRef NewState = Pred->getState();
 793
 794   if(AMgr.options.ShouldUnrollLoops)
 795     NewState = processLoopEnd(S, NewState);
 796
 797   LoopExit PP(S, Pred->getLocationContext());
 798   Bldr.generateNode(PP, NewState, Pred);
 799   // Enqueue the new nodes onto the work list.
 800   Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx);
 801 }
 802
 803 void ExprEngine::ProcessInitializer(const CFGInitializer CFGInit,
 804                                     ExplodedNode *Pred) {
 805   const CXXCtorInitializer *BMI = CFGInit.getInitializer();
 806   const Expr *Init = BMI->getInit()->IgnoreImplicit();
 807   const LocationContext *LC = Pred->getLocationContext();
 808
 809   PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
 810                                 BMI->getSourceLocation(),
 811                                 "Error evaluating initializer");
 812
 813   // We don't clean up dead bindings here.
 814   const auto *stackFrame = cast<StackFrameContext>(Pred->getLocationContext());
 815   const auto *decl = cast<CXXConstructorDecl>(stackFrame->getDecl());
 816
 817   ProgramStateRef State = Pred->getState();
 818   SVal thisVal = State->getSVal(svalBuilder.getCXXThis(decl, stackFrame));
 819
 820   ExplodedNodeSet Tmp;
 821   SVal FieldLoc;
 822
 823   // Evaluate the initializer, if necessary
 824   if (BMI->isAnyMemberInitializer()) {
 825     // Constructors build the object directly in the field,
 826     // but non-objects must be copied in from the initializer.
 827     if (getObjectUnderConstruction(State, BMI, LC)) {
 828       // The field was directly constructed, so there is no need to bind.
 829       // But we still need to stop tracking the object under construction.
 830       State = finishObjectConstruction(State, BMI, LC);
 831       NodeBuilder Bldr(Pred, Tmp, *currBldrCtx);
 832       PostStore PS(Init, LC, /*Loc*/ nullptr, /*tag*/ nullptr);
 833       Bldr.generateNode(PS, State, Pred);
 834     } else {
 835       const ValueDecl *Field;
 836       if (BMI->isIndirectMemberInitializer()) {
 837         Field = BMI->getIndirectMember();
 838         FieldLoc = State->getLValue(BMI->getIndirectMember(), thisVal);
 839       } else {
 840         Field = BMI->getMember();
 841         FieldLoc = State->getLValue(BMI->getMember(), thisVal);
 842       }
 843
 844       SVal InitVal;
 845       if (Init->getType()->isArrayType()) {
 846         // Handle arrays of trivial type. We can represent this with a
 847         // primitive load/copy from the base array region.
 848         const ArraySubscriptExpr *ASE;
 849         while ((ASE = dyn_cast<ArraySubscriptExpr>(Init)))
 850           Init = ASE->getBase()->IgnoreImplicit();
 851
 852         SVal LValue = State->getSVal(Init, stackFrame);
 853         if (!Field->getType()->isReferenceType())
 854           if (Optional<Loc> LValueLoc = LValue.getAs<Loc>())
 855             InitVal = State->getSVal(*LValueLoc);
 856
 857         // If we fail to get the value for some reason, use a symbolic value.
 858         if (InitVal.isUnknownOrUndef()) {
 859           SValBuilder &SVB = getSValBuilder();
 860           InitVal = SVB.conjureSymbolVal(BMI->getInit(), stackFrame,
 861                                          Field->getType(),
 862                                          currBldrCtx->blockCount());
 863         }
 864       } else {
 865         InitVal = State->getSVal(BMI->getInit(), stackFrame);
 866       }
 867
 868       PostInitializer PP(BMI, FieldLoc.getAsRegion(), stackFrame);
 869       evalBind(Tmp, Init, Pred, FieldLoc, InitVal, /*isInit=*/true, &PP);
 870     }
 871   } else {
 872     assert(BMI->isBaseInitializer() || BMI->isDelegatingInitializer());
 873     Tmp.insert(Pred);
 874     // We already did all the work when visiting the CXXConstructExpr.
 875   }
 876
 877   // Construct PostInitializer nodes whether the state changed or not,
 878   // so that the diagnostics don't get confused.
 879   PostInitializer PP(BMI, FieldLoc.getAsRegion(), stackFrame);
 880   ExplodedNodeSet Dst;
 881   NodeBuilder Bldr(Tmp, Dst, *currBldrCtx);
 882   for (const auto I : Tmp) {
 883     ProgramStateRef State = I->getState();
 884     Bldr.generateNode(PP, State, I);
 885   }
 886
 887   // Enqueue the new nodes onto the work list.
 888   Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx);
 889 }
 890
 891 void ExprEngine::ProcessImplicitDtor(const CFGImplicitDtor D,
 892                                      ExplodedNode *Pred) {
 893   ExplodedNodeSet Dst;
 894   switch (D.getKind()) {
 895   case CFGElement::AutomaticObjectDtor:
 896     ProcessAutomaticObjDtor(D.castAs<CFGAutomaticObjDtor>(), Pred, Dst);
 897     break;
 898   case CFGElement::BaseDtor:
 899     ProcessBaseDtor(D.castAs<CFGBaseDtor>(), Pred, Dst);
 900     break;
 901   case CFGElement::MemberDtor:
 902     ProcessMemberDtor(D.castAs<CFGMemberDtor>(), Pred, Dst);
 903     break;
 904   case CFGElement::TemporaryDtor:
 905     ProcessTemporaryDtor(D.castAs<CFGTemporaryDtor>(), Pred, Dst);
 906     break;
 907   case CFGElement::DeleteDtor:
 908     ProcessDeleteDtor(D.castAs<CFGDeleteDtor>(), Pred, Dst);
 909     break;
 910   default:
 911     llvm_unreachable("Unexpected dtor kind.");
 912   }
 913
 914   // Enqueue the new nodes onto the work list.
 915   Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx);
 916 }
 917
 918 void ExprEngine::ProcessNewAllocator(const CXXNewExpr *NE,
 919                                      ExplodedNode *Pred) {
 920   ExplodedNodeSet Dst;
 921   AnalysisManager &AMgr = getAnalysisManager();
 922   AnalyzerOptions &Opts = AMgr.options;
 923   // TODO: We're not evaluating allocators for all cases just yet as
 924   // we're not handling the return value correctly, which causes false
 925   // positives when the alpha.cplusplus.NewDeleteLeaks check is on.
 926   if (Opts.MayInlineCXXAllocator)
 927     VisitCXXNewAllocatorCall(NE, Pred, Dst);
 928   else {
 929     NodeBuilder Bldr(Pred, Dst, *currBldrCtx);
 930     const LocationContext *LCtx = Pred->getLocationContext();
 931     PostImplicitCall PP(NE->getOperatorNew(), NE->getBeginLoc(), LCtx);
 932     Bldr.generateNode(PP, Pred->getState(), Pred);
 933   }
 934   Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx);
 935 }
 936
 937 void ExprEngine::ProcessAutomaticObjDtor(const CFGAutomaticObjDtor Dtor,
 938                                          ExplodedNode *Pred,
 939                                          ExplodedNodeSet &Dst) {
 940   const VarDecl *varDecl = Dtor.getVarDecl();
 941   QualType varType = varDecl->getType();
 942
 943   ProgramStateRef state = Pred->getState();
 944   SVal dest = state->getLValue(varDecl, Pred->getLocationContext());
 945   const MemRegion *Region = dest.castAs<loc::MemRegionVal>().getRegion();
 946
 947   if (varType->isReferenceType()) {
 948     const MemRegion *ValueRegion = state->getSVal(Region).getAsRegion();
 949     if (!ValueRegion) {
 950       // FIXME: This should not happen. The language guarantees a presence
 951       // of a valid initializer here, so the reference shall not be undefined.
 952       // It seems that we're calling destructors over variables that
 953       // were not initialized yet.
 954       return;
 955     }
 956     Region = ValueRegion->getBaseRegion();
 957     varType = cast<TypedValueRegion>(Region)->getValueType();
 958   }
 959
 960   // FIXME: We need to run the same destructor on every element of the array.
 961   // This workaround will just run the first destructor (which will still
 962   // invalidate the entire array).
 963   EvalCallOptions CallOpts;
 964   Region = makeZeroElementRegion(state, loc::MemRegionVal(Region), varType,
 965                                  CallOpts.IsArrayCtorOrDtor).getAsRegion();
 966
 967   VisitCXXDestructor(varType, Region, Dtor.getTriggerStmt(),
 968                      /*IsBase=*/false, Pred, Dst, CallOpts);
 969 }
 970
 971 void ExprEngine::ProcessDeleteDtor(const CFGDeleteDtor Dtor,
 972                                    ExplodedNode *Pred,
 973                                    ExplodedNodeSet &Dst) {
 974   ProgramStateRef State = Pred->getState();
 975   const LocationContext *LCtx = Pred->getLocationContext();
 976   const CXXDeleteExpr *DE = Dtor.getDeleteExpr();
 977   const Stmt *Arg = DE->getArgument();
 978   QualType DTy = DE->getDestroyedType();
 979   SVal ArgVal = State->getSVal(Arg, LCtx);
 980
 981   // If the argument to delete is known to be a null value,
 982   // don't run destructor.
 983   if (State->isNull(ArgVal).isConstrainedTrue()) {
 984     QualType BTy = getContext().getBaseElementType(DTy);
 985     const CXXRecordDecl *RD = BTy->getAsCXXRecordDecl();
 986     const CXXDestructorDecl *Dtor = RD->getDestructor();
 987
 988     PostImplicitCall PP(Dtor, DE->getBeginLoc(), LCtx);
 989     NodeBuilder Bldr(Pred, Dst, *currBldrCtx);
 990     Bldr.generateNode(PP, Pred->getState(), Pred);
 991     return;
 992   }
 993
 994   EvalCallOptions CallOpts;
 995   const MemRegion *ArgR = ArgVal.getAsRegion();
 996   if (DE->isArrayForm()) {
 997     // FIXME: We need to run the same destructor on every element of the array.
 998     // This workaround will just run the first destructor (which will still
 999     // invalidate the entire array).
1000     CallOpts.IsArrayCtorOrDtor = true;
1001     // Yes, it may even be a multi-dimensional array.
1002     while (const auto *AT = getContext().getAsArrayType(DTy))
1003       DTy = AT->getElementType();
1004     if (ArgR)
1005       ArgR = getStoreManager().GetElementZeroRegion(cast<SubRegion>(ArgR), DTy);
1006   }
1007
1008   VisitCXXDestructor(DTy, ArgR, DE, /*IsBase=*/false, Pred, Dst, CallOpts);
1009 }
1010
1011 void ExprEngine::ProcessBaseDtor(const CFGBaseDtor D,
1012                                  ExplodedNode *Pred, ExplodedNodeSet &Dst) {
1013   const LocationContext *LCtx = Pred->getLocationContext();
1014
1015   const auto *CurDtor = cast<CXXDestructorDecl>(LCtx->getDecl());
1016   Loc ThisPtr = getSValBuilder().getCXXThis(CurDtor,
1017                                             LCtx->getStackFrame());
1018   SVal ThisVal = Pred->getState()->getSVal(ThisPtr);
1019
1020   // Create the base object region.
1021   const CXXBaseSpecifier *Base = D.getBaseSpecifier();
1022   QualType BaseTy = Base->getType();
1023   SVal BaseVal = getStoreManager().evalDerivedToBase(ThisVal, BaseTy,
1024                                                      Base->isVirtual());
1025
1026   EvalCallOptions CallOpts;
1027   VisitCXXDestructor(BaseTy, BaseVal.getAsRegion(), CurDtor->getBody(),
1028                      /*IsBase=*/true, Pred, Dst, CallOpts);
1029 }
1030
1031 void ExprEngine::ProcessMemberDtor(const CFGMemberDtor D,
1032                                    ExplodedNode *Pred, ExplodedNodeSet &Dst) {
1033   const FieldDecl *Member = D.getFieldDecl();
1034   QualType T = Member->getType();
1035   ProgramStateRef State = Pred->getState();
1036   const LocationContext *LCtx = Pred->getLocationContext();
1037
1038   const auto *CurDtor = cast<CXXDestructorDecl>(LCtx->getDecl());
1039   Loc ThisStorageLoc =
1040       getSValBuilder().getCXXThis(CurDtor, LCtx->getStackFrame());
1041   Loc ThisLoc = State->getSVal(ThisStorageLoc).castAs<Loc>();
1042   SVal FieldVal = State->getLValue(Member, ThisLoc);
1043
1044   // FIXME: We need to run the same destructor on every element of the array.
1045   // This workaround will just run the first destructor (which will still
1046   // invalidate the entire array).
1047   EvalCallOptions CallOpts;
1048   FieldVal = makeZeroElementRegion(State, FieldVal, T,
1049                                    CallOpts.IsArrayCtorOrDtor);
1050
1051   VisitCXXDestructor(T, FieldVal.getAsRegion(), CurDtor->getBody(),
1052                      /*IsBase=*/false, Pred, Dst, CallOpts);
1053 }
1054
1055 void ExprEngine::ProcessTemporaryDtor(const CFGTemporaryDtor D,
1056                                       ExplodedNode *Pred,
1057                                       ExplodedNodeSet &Dst) {
1058   const CXXBindTemporaryExpr *BTE = D.getBindTemporaryExpr();
1059   ProgramStateRef State = Pred->getState();
1060   const LocationContext *LC = Pred->getLocationContext();
1061   const MemRegion *MR = nullptr;
1062
1063   if (Optional<SVal> V =
1064           getObjectUnderConstruction(State, D.getBindTemporaryExpr(),
1065                                      Pred->getLocationContext())) {
1066     // FIXME: Currently we insert temporary destructors for default parameters,
1067     // but we don't insert the constructors, so the entry in
1068     // ObjectsUnderConstruction may be missing.
1069     State = finishObjectConstruction(State, D.getBindTemporaryExpr(),
1070                                      Pred->getLocationContext());
1071     MR = V->getAsRegion();
1072   }
1073
1074   // If copy elision has occurred, and the constructor corresponding to the
1075   // destructor was elided, we need to skip the destructor as well.
1076   if (isDestructorElided(State, BTE, LC)) {
1077     State = cleanupElidedDestructor(State, BTE, LC);
1078     NodeBuilder Bldr(Pred, Dst, *currBldrCtx);
1079     PostImplicitCall PP(D.getDestructorDecl(getContext()),
1080                         D.getBindTemporaryExpr()->getBeginLoc(),
1081                         Pred->getLocationContext());
1082     Bldr.generateNode(PP, State, Pred);
1083     return;
1084   }
1085
1086   ExplodedNodeSet CleanDtorState;
1087   StmtNodeBuilder StmtBldr(Pred, CleanDtorState, *currBldrCtx);
1088   StmtBldr.generateNode(D.getBindTemporaryExpr(), Pred, State);
1089
1090   QualType T = D.getBindTemporaryExpr()->getSubExpr()->getType();
1091   // FIXME: Currently CleanDtorState can be empty here due to temporaries being
1092   // bound to default parameters.
1093   assert(CleanDtorState.size() <= 1);
1094   ExplodedNode *CleanPred =
1095       CleanDtorState.empty() ? Pred : *CleanDtorState.begin();
1096
1097   EvalCallOptions CallOpts;
1098   CallOpts.IsTemporaryCtorOrDtor = true;
1099   if (!MR) {
1100     // If we have no MR, we still need to unwrap the array to avoid destroying
1101     // the whole array at once. Regardless, we'd eventually need to model array
1102     // destructors properly, element-by-element.
1103     while (const ArrayType *AT = getContext().getAsArrayType(T)) {
1104       T = AT->getElementType();
1105       CallOpts.IsArrayCtorOrDtor = true;
1106     }
1107   } else {
1108     // We'd eventually need to makeZeroElementRegion() trick here,
1109     // but for now we don't have the respective construction contexts,
1110     // so MR would always be null in this case. Do nothing for now.
1111   }
1112   VisitCXXDestructor(T, MR, D.getBindTemporaryExpr(),
1113                      /*IsBase=*/false, CleanPred, Dst, CallOpts);
1114 }
1115
1116 void ExprEngine::processCleanupTemporaryBranch(const CXXBindTemporaryExpr *BTE,
1117                                                NodeBuilderContext &BldCtx,
1118                                                ExplodedNode *Pred,
1119                                                ExplodedNodeSet &Dst,
1120                                                const CFGBlock *DstT,
1121                                                const CFGBlock *DstF) {
1122   BranchNodeBuilder TempDtorBuilder(Pred, Dst, BldCtx, DstT, DstF);
1123   ProgramStateRef State = Pred->getState();
1124   const LocationContext *LC = Pred->getLocationContext();
1125   if (getObjectUnderConstruction(State, BTE, LC)) {
1126     TempDtorBuilder.markInfeasible(false);
1127     TempDtorBuilder.generateNode(State, true, Pred);
1128   } else {
1129     TempDtorBuilder.markInfeasible(true);
1130     TempDtorBuilder.generateNode(State, false, Pred);
1131   }
1132 }
1133
1134 void ExprEngine::VisitCXXBindTemporaryExpr(const CXXBindTemporaryExpr *BTE,
1135                                            ExplodedNodeSet &PreVisit,
1136                                            ExplodedNodeSet &Dst) {
1137   // This is a fallback solution in case we didn't have a construction
1138   // context when we were constructing the temporary. Otherwise the map should
1139   // have been populated there.
1140   if (!getAnalysisManager().options.ShouldIncludeTemporaryDtorsInCFG) {
1141     // In case we don't have temporary destructors in the CFG, do not mark
1142     // the initialization - we would otherwise never clean it up.
1143     Dst = PreVisit;
1144     return;
1145   }
1146   StmtNodeBuilder StmtBldr(PreVisit, Dst, *currBldrCtx);
1147   for (ExplodedNode *Node : PreVisit) {
1148     ProgramStateRef State = Node->getState();
1149     const LocationContext *LC = Node->getLocationContext();
1150     if (!getObjectUnderConstruction(State, BTE, LC)) {
1151       // FIXME: Currently the state might also already contain the marker due to
1152       // incorrect handling of temporaries bound to default parameters; for
1153       // those, we currently skip the CXXBindTemporaryExpr but rely on adding
1154       // temporary destructor nodes.
1155       State = addObjectUnderConstruction(State, BTE, LC, UnknownVal());
1156     }
1157     StmtBldr.generateNode(BTE, Node, State);
1158   }
1159 }
1160
1161 ProgramStateRef ExprEngine::escapeValues(ProgramStateRef State,
1162                                          ArrayRef<SVal> Vs,
1163                                          PointerEscapeKind K,
1164                                          const CallEvent *Call) const {
1165   class CollectReachableSymbolsCallback final : public SymbolVisitor {
1166     InvalidatedSymbols &Symbols;
1167
1168   public:
1169     explicit CollectReachableSymbolsCallback(InvalidatedSymbols &Symbols)
1170         : Symbols(Symbols) {}
1171
1172     const InvalidatedSymbols &getSymbols() const { return Symbols; }
1173
1174     bool VisitSymbol(SymbolRef Sym) override {
1175       Symbols.insert(Sym);
1176       return true;
1177     }
1178   };
1179   InvalidatedSymbols Symbols;
1180   CollectReachableSymbolsCallback CallBack(Symbols);
1181   for (SVal V : Vs)
1182     State->scanReachableSymbols(V, CallBack);
1183
1184   return getCheckerManager().runCheckersForPointerEscape(
1185       State, CallBack.getSymbols(), Call, K, nullptr);
1186 }
1187
1188 void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred,
1189                        ExplodedNodeSet &DstTop) {
1190   PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
1191                                 S->getBeginLoc(), "Error evaluating statement");
1192   ExplodedNodeSet Dst;
1193   StmtNodeBuilder Bldr(Pred, DstTop, *currBldrCtx);
1194
1195   assert(!isa<Expr>(S) || S == cast<Expr>(S)->IgnoreParens());
1196
1197   switch (S->getStmtClass()) {
1198     // C++, OpenMP and ARC stuff we don't support yet.
1199     case Stmt::CXXDependentScopeMemberExprClass:
1200     case Stmt::CXXTryStmtClass:
1201     case Stmt::CXXTypeidExprClass:
1202     case Stmt::CXXUuidofExprClass:
1203     case Stmt::CXXFoldExprClass:
1204     case Stmt::MSPropertyRefExprClass:
1205     case Stmt::MSPropertySubscriptExprClass:
1206     case Stmt::CXXUnresolvedConstructExprClass:
1207     case Stmt::DependentScopeDeclRefExprClass:
1208     case Stmt::ArrayTypeTraitExprClass:
1209     case Stmt::ExpressionTraitExprClass:
1210     case Stmt::UnresolvedLookupExprClass:
1211     case Stmt::UnresolvedMemberExprClass:
1212     case Stmt::TypoExprClass:
1213     case Stmt::RecoveryExprClass:
1214     case Stmt::CXXNoexceptExprClass:
1215     case Stmt::PackExpansionExprClass:
1216     case Stmt::SubstNonTypeTemplateParmPackExprClass:
1217     case Stmt::FunctionParmPackExprClass:
1218     case Stmt::CoroutineBodyStmtClass:
1219     case Stmt::CoawaitExprClass:
1220     case Stmt::DependentCoawaitExprClass:
1221     case Stmt::CoreturnStmtClass:
1222     case Stmt::CoyieldExprClass:
1223     case Stmt::SEHTryStmtClass:
1224     case Stmt::SEHExceptStmtClass:
1225     case Stmt::SEHLeaveStmtClass:
1226     case Stmt::SEHFinallyStmtClass:
1227     case Stmt::OMPCanonicalLoopClass:
1228     case Stmt::OMPParallelDirectiveClass:
1229     case Stmt::OMPSimdDirectiveClass:
1230     case Stmt::OMPForDirectiveClass:
1231     case Stmt::OMPForSimdDirectiveClass:
1232     case Stmt::OMPSectionsDirectiveClass:
1233     case Stmt::OMPSectionDirectiveClass:
1234     case Stmt::OMPSingleDirectiveClass:
1235     case Stmt::OMPMasterDirectiveClass:
1236     case Stmt::OMPCriticalDirectiveClass:
1237     case Stmt::OMPParallelForDirectiveClass:
1238     case Stmt::OMPParallelForSimdDirectiveClass:
1239     case Stmt::OMPParallelSectionsDirectiveClass:
1240     case Stmt::OMPParallelMasterDirectiveClass:
1241     case Stmt::OMPParallelMaskedDirectiveClass:
1242     case Stmt::OMPTaskDirectiveClass:
1243     case Stmt::OMPTaskyieldDirectiveClass:
1244     case Stmt::OMPBarrierDirectiveClass:
1245     case Stmt::OMPTaskwaitDirectiveClass:
1246     case Stmt::OMPTaskgroupDirectiveClass:
1247     case Stmt::OMPFlushDirectiveClass:
1248     case Stmt::OMPDepobjDirectiveClass:
1249     case Stmt::OMPScanDirectiveClass:
1250     case Stmt::OMPOrderedDirectiveClass:
1251     case Stmt::OMPAtomicDirectiveClass:
1252     case Stmt::OMPTargetDirectiveClass:
1253     case Stmt::OMPTargetDataDirectiveClass:
1254     case Stmt::OMPTargetEnterDataDirectiveClass:
1255     case Stmt::OMPTargetExitDataDirectiveClass:
1256     case Stmt::OMPTargetParallelDirectiveClass:
1257     case Stmt::OMPTargetParallelForDirectiveClass:
1258     case Stmt::OMPTargetUpdateDirectiveClass:
1259     case Stmt::OMPTeamsDirectiveClass:
1260     case Stmt::OMPCancellationPointDirectiveClass:
1261     case Stmt::OMPCancelDirectiveClass:
1262     case Stmt::OMPTaskLoopDirectiveClass:
1263     case Stmt::OMPTaskLoopSimdDirectiveClass:
1264     case Stmt::OMPMasterTaskLoopDirectiveClass:
1265     case Stmt::OMPMaskedTaskLoopDirectiveClass:
1266     case Stmt::OMPMasterTaskLoopSimdDirectiveClass:
1267     case Stmt::OMPMaskedTaskLoopSimdDirectiveClass:
1268     case Stmt::OMPParallelMasterTaskLoopDirectiveClass:
1269     case Stmt::OMPParallelMaskedTaskLoopDirectiveClass:
1270     case Stmt::OMPParallelMasterTaskLoopSimdDirectiveClass:
1271     case Stmt::OMPParallelMaskedTaskLoopSimdDirectiveClass:
1272     case Stmt::OMPDistributeDirectiveClass:
1273     case Stmt::OMPDistributeParallelForDirectiveClass:
1274     case Stmt::OMPDistributeParallelForSimdDirectiveClass:
1275     case Stmt::OMPDistributeSimdDirectiveClass:
1276     case Stmt::OMPTargetParallelForSimdDirectiveClass:
1277     case Stmt::OMPTargetSimdDirectiveClass:
1278     case Stmt::OMPTeamsDistributeDirectiveClass:
1279     case Stmt::OMPTeamsDistributeSimdDirectiveClass:
1280     case Stmt::OMPTeamsDistributeParallelForSimdDirectiveClass:
1281     case Stmt::OMPTeamsDistributeParallelForDirectiveClass:
1282     case Stmt::OMPTargetTeamsDirectiveClass:
1283     case Stmt::OMPTargetTeamsDistributeDirectiveClass:
1284     case Stmt::OMPTargetTeamsDistributeParallelForDirectiveClass:
1285     case Stmt::OMPTargetTeamsDistributeParallelForSimdDirectiveClass:
1286     case Stmt::OMPTargetTeamsDistributeSimdDirectiveClass:
1287     case Stmt::OMPTileDirectiveClass:
1288     case Stmt::OMPInteropDirectiveClass:
1289     case Stmt::OMPDispatchDirectiveClass:
1290     case Stmt::OMPMaskedDirectiveClass:
1291     case Stmt::OMPGenericLoopDirectiveClass:
1292     case Stmt::OMPTeamsGenericLoopDirectiveClass:
1293     case Stmt::OMPTargetTeamsGenericLoopDirectiveClass:
1294     case Stmt::OMPParallelGenericLoopDirectiveClass:
1295     case Stmt::OMPTargetParallelGenericLoopDirectiveClass:
1296     case Stmt::CapturedStmtClass:
1297     case Stmt::OMPUnrollDirectiveClass:
1298     case Stmt::OMPMetaDirectiveClass: {
1299       const ExplodedNode *node = Bldr.generateSink(S, Pred, Pred->getState());
1300       Engine.addAbortedBlock(node, currBldrCtx->getBlock());
1301       break;
1302     }
1303
1304     case Stmt::ParenExprClass:
1305       llvm_unreachable("ParenExprs already handled.");
1306     case Stmt::GenericSelectionExprClass:
1307       llvm_unreachable("GenericSelectionExprs already handled.");
1308     // Cases that should never be evaluated simply because they shouldn't
1309     // appear in the CFG.
1310     case Stmt::BreakStmtClass:
1311     case Stmt::CaseStmtClass:
1312     case Stmt::CompoundStmtClass:
1313     case Stmt::ContinueStmtClass:
1314     case Stmt::CXXForRangeStmtClass:
1315     case Stmt::DefaultStmtClass:
1316     case Stmt::DoStmtClass:
1317     case Stmt::ForStmtClass:
1318     case Stmt::GotoStmtClass:
1319     case Stmt::IfStmtClass:
1320     case Stmt::IndirectGotoStmtClass:
1321     case Stmt::LabelStmtClass:
1322     case Stmt::NoStmtClass:
1323     case Stmt::NullStmtClass:
1324     case Stmt::SwitchStmtClass:
1325     case Stmt::WhileStmtClass:
1326     case Expr::MSDependentExistsStmtClass:
1327       llvm_unreachable("Stmt should not be in analyzer evaluation loop");
1328     case Stmt::ImplicitValueInitExprClass:
1329       // These nodes are shared in the CFG and would case caching out.
1330       // Moreover, no additional evaluation required for them, the
1331       // analyzer can reconstruct these values from the AST.
1332       llvm_unreachable("Should be pruned from CFG");
1333
1334     case Stmt::ObjCSubscriptRefExprClass:
1335     case Stmt::ObjCPropertyRefExprClass:
1336       llvm_unreachable("These are handled by PseudoObjectExpr");
1337
1338     case Stmt::GNUNullExprClass: {
1339       // GNU __null is a pointer-width integer, not an actual pointer.
1340       ProgramStateRef state = Pred->getState();
1341       state = state->BindExpr(
1342           S, Pred->getLocationContext(),
1343           svalBuilder.makeIntValWithWidth(getContext().VoidPtrTy, 0));
1344       Bldr.generateNode(S, Pred, state);
1345       break;
1346     }
1347
1348     case Stmt::ObjCAtSynchronizedStmtClass:
1349       Bldr.takeNodes(Pred);
1350       VisitObjCAtSynchronizedStmt(cast<ObjCAtSynchronizedStmt>(S), Pred, Dst);
1351       Bldr.addNodes(Dst);
1352       break;
1353
1354     case Expr::ConstantExprClass:
1355     case Stmt::ExprWithCleanupsClass:
1356       // Handled due to fully linearised CFG.
1357       break;
1358
1359     case Stmt::CXXBindTemporaryExprClass: {
1360       Bldr.takeNodes(Pred);
1361       ExplodedNodeSet PreVisit;
1362       getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this);
1363       ExplodedNodeSet Next;
1364       VisitCXXBindTemporaryExpr(cast<CXXBindTemporaryExpr>(S), PreVisit, Next);
1365       getCheckerManager().runCheckersForPostStmt(Dst, Next, S, *this);
1366       Bldr.addNodes(Dst);
1367       break;
1368     }
1369
1370     case Stmt::ArrayInitLoopExprClass:
1371       Bldr.takeNodes(Pred);
1372       VisitArrayInitLoopExpr(cast<ArrayInitLoopExpr>(S), Pred, Dst);
1373       Bldr.addNodes(Dst);
1374       break;
1375     // Cases not handled yet; but will handle some day.
1376     case Stmt::DesignatedInitExprClass:
1377     case Stmt::DesignatedInitUpdateExprClass:
1378     case Stmt::ArrayInitIndexExprClass:
1379     case Stmt::ExtVectorElementExprClass:
1380     case Stmt::ImaginaryLiteralClass:
1381     case Stmt::ObjCAtCatchStmtClass:
1382     case Stmt::ObjCAtFinallyStmtClass:
1383     case Stmt::ObjCAtTryStmtClass:
1384     case Stmt::ObjCAutoreleasePoolStmtClass:
1385     case Stmt::ObjCEncodeExprClass:
1386     case Stmt::ObjCIsaExprClass:
1387     case Stmt::ObjCProtocolExprClass:
1388     case Stmt::ObjCSelectorExprClass:
1389     case Stmt::ParenListExprClass:
1390     case Stmt::ShuffleVectorExprClass:
1391     case Stmt::ConvertVectorExprClass:
1392     case Stmt::VAArgExprClass:
1393     case Stmt::CUDAKernelCallExprClass:
1394     case Stmt::OpaqueValueExprClass:
1395     case Stmt::AsTypeExprClass:
1396     case Stmt::ConceptSpecializationExprClass:
1397     case Stmt::CXXRewrittenBinaryOperatorClass:
1398     case Stmt::RequiresExprClass:
1399       // Fall through.
1400
1401     // Cases we intentionally don't evaluate, since they don't need
1402     // to be explicitly evaluated.
1403     case Stmt::PredefinedExprClass:
1404     case Stmt::AddrLabelExprClass:
1405     case Stmt::AttributedStmtClass:
1406     case Stmt::IntegerLiteralClass:
1407     case Stmt::FixedPointLiteralClass:
1408     case Stmt::CharacterLiteralClass:
1409     case Stmt::CXXScalarValueInitExprClass:
1410     case Stmt::CXXBoolLiteralExprClass:
1411     case Stmt::ObjCBoolLiteralExprClass:
1412     case Stmt::ObjCAvailabilityCheckExprClass:
1413     case Stmt::FloatingLiteralClass:
1414     case Stmt::NoInitExprClass:
1415     case Stmt::SizeOfPackExprClass:
1416     case Stmt::StringLiteralClass:
1417     case Stmt::SourceLocExprClass:
1418     case Stmt::ObjCStringLiteralClass:
1419     case Stmt::CXXPseudoDestructorExprClass:
1420     case Stmt::SubstNonTypeTemplateParmExprClass:
1421     case Stmt::CXXNullPtrLiteralExprClass:
1422     case Stmt::OMPArraySectionExprClass:
1423     case Stmt::OMPArrayShapingExprClass:
1424     case Stmt::OMPIteratorExprClass:
1425     case Stmt::SYCLUniqueStableNameExprClass:
1426     case Stmt::TypeTraitExprClass: {
1427       Bldr.takeNodes(Pred);
1428       ExplodedNodeSet preVisit;
1429       getCheckerManager().runCheckersForPreStmt(preVisit, Pred, S, *this);
1430       getCheckerManager().runCheckersForPostStmt(Dst, preVisit, S, *this);
1431       Bldr.addNodes(Dst);
1432       break;
1433     }
1434
1435     case Stmt::CXXDefaultArgExprClass:
1436     case Stmt::CXXDefaultInitExprClass: {
1437       Bldr.takeNodes(Pred);
1438       ExplodedNodeSet PreVisit;
1439       getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this);
1440
1441       ExplodedNodeSet Tmp;
1442       StmtNodeBuilder Bldr2(PreVisit, Tmp, *currBldrCtx);
1443
1444       const Expr *ArgE;
1445       if (const auto *DefE = dyn_cast<CXXDefaultArgExpr>(S))
1446         ArgE = DefE->getExpr();
1447       else if (const auto *DefE = dyn_cast<CXXDefaultInitExpr>(S))
1448         ArgE = DefE->getExpr();
1449       else
1450         llvm_unreachable("unknown constant wrapper kind");
1451
1452       bool IsTemporary = false;
1453       if (const auto *MTE = dyn_cast<MaterializeTemporaryExpr>(ArgE)) {
1454         ArgE = MTE->getSubExpr();
1455         IsTemporary = true;
1456       }
1457
1458       Optional<SVal> ConstantVal = svalBuilder.getConstantVal(ArgE);
1459       if (!ConstantVal)
1460         ConstantVal = UnknownVal();
1461
1462       const LocationContext *LCtx = Pred->getLocationContext();
1463       for (const auto I : PreVisit) {
1464         ProgramStateRef State = I->getState();
1465         State = State->BindExpr(S, LCtx, *ConstantVal);
1466         if (IsTemporary)
1467           State = createTemporaryRegionIfNeeded(State, LCtx,
1468                                                 cast<Expr>(S),
1469                                                 cast<Expr>(S));
1470         Bldr2.generateNode(S, I, State);
1471       }
1472
1473       getCheckerManager().runCheckersForPostStmt(Dst, Tmp, S, *this);
1474       Bldr.addNodes(Dst);
1475       break;
1476     }
1477
1478     // Cases we evaluate as opaque expressions, conjuring a symbol.
1479     case Stmt::CXXStdInitializerListExprClass:
1480     case Expr::ObjCArrayLiteralClass:
1481     case Expr::ObjCDictionaryLiteralClass:
1482     case Expr::ObjCBoxedExprClass: {
1483       Bldr.takeNodes(Pred);
1484
1485       ExplodedNodeSet preVisit;
1486       getCheckerManager().runCheckersForPreStmt(preVisit, Pred, S, *this);
1487
1488       ExplodedNodeSet Tmp;
1489       StmtNodeBuilder Bldr2(preVisit, Tmp, *currBldrCtx);
1490
1491       const auto *Ex = cast<Expr>(S);
1492       QualType resultType = Ex->getType();
1493
1494       for (const auto N : preVisit) {
1495         const LocationContext *LCtx = N->getLocationContext();
1496         SVal result = svalBuilder.conjureSymbolVal(nullptr, Ex, LCtx,
1497                                                    resultType,
1498                                                    currBldrCtx->blockCount());
1499         ProgramStateRef State = N->getState()->BindExpr(Ex, LCtx, result);
1500
1501         // Escape pointers passed into the list, unless it's an ObjC boxed
1502         // expression which is not a boxable C structure.
1503         if (!(isa<ObjCBoxedExpr>(Ex) &&
1504               !cast<ObjCBoxedExpr>(Ex)->getSubExpr()
1505                                       ->getType()->isRecordType()))
1506           for (auto Child : Ex->children()) {
1507             assert(Child);
1508             SVal Val = State->getSVal(Child, LCtx);
1509             State = escapeValues(State, Val, PSK_EscapeOther);
1510           }
1511
1512         Bldr2.generateNode(S, N, State);
1513       }
1514
1515       getCheckerManager().runCheckersForPostStmt(Dst, Tmp, S, *this);
1516       Bldr.addNodes(Dst);
1517       break;
1518     }
1519
1520     case Stmt::ArraySubscriptExprClass:
1521       Bldr.takeNodes(Pred);
1522       VisitArraySubscriptExpr(cast<ArraySubscriptExpr>(S), Pred, Dst);
1523       Bldr.addNodes(Dst);
1524       break;
1525
1526     case Stmt::MatrixSubscriptExprClass:
1527       llvm_unreachable("Support for MatrixSubscriptExpr is not implemented.");
1528       break;
1529
1530     case Stmt::GCCAsmStmtClass:
1531       Bldr.takeNodes(Pred);
1532       VisitGCCAsmStmt(cast<GCCAsmStmt>(S), Pred, Dst);
1533       Bldr.addNodes(Dst);
1534       break;
1535
1536     case Stmt::MSAsmStmtClass:
1537       Bldr.takeNodes(Pred);
1538       VisitMSAsmStmt(cast<MSAsmStmt>(S), Pred, Dst);
1539       Bldr.addNodes(Dst);
1540       break;
1541
1542     case Stmt::BlockExprClass:
1543       Bldr.takeNodes(Pred);
1544       VisitBlockExpr(cast<BlockExpr>(S), Pred, Dst);
1545       Bldr.addNodes(Dst);
1546       break;
1547
1548     case Stmt::LambdaExprClass:
1549       if (AMgr.options.ShouldInlineLambdas) {
1550         Bldr.takeNodes(Pred);
1551         VisitLambdaExpr(cast<LambdaExpr>(S), Pred, Dst);
1552         Bldr.addNodes(Dst);
1553       } else {
1554         const ExplodedNode *node = Bldr.generateSink(S, Pred, Pred->getState());
1555         Engine.addAbortedBlock(node, currBldrCtx->getBlock());
1556       }
1557       break;
1558
1559     case Stmt::BinaryOperatorClass: {
1560       const auto *B = cast<BinaryOperator>(S);
1561       if (B->isLogicalOp()) {
1562         Bldr.takeNodes(Pred);
1563         VisitLogicalExpr(B, Pred, Dst);
1564         Bldr.addNodes(Dst);
1565         break;
1566       }
1567       else if (B->getOpcode() == BO_Comma) {
1568         ProgramStateRef state = Pred->getState();
1569         Bldr.generateNode(B, Pred,
1570                           state->BindExpr(B, Pred->getLocationContext(),
1571                                           state->getSVal(B->getRHS(),
1572                                                   Pred->getLocationContext())));
1573         break;
1574       }
1575
1576       Bldr.takeNodes(Pred);
1577
1578       if (AMgr.options.ShouldEagerlyAssume &&
1579           (B->isRelationalOp() || B->isEqualityOp())) {
1580         ExplodedNodeSet Tmp;
1581         VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Tmp);
1582         evalEagerlyAssumeBinOpBifurcation(Dst, Tmp, cast<Expr>(S));
1583       }
1584       else
1585         VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst);
1586
1587       Bldr.addNodes(Dst);
1588       break;
1589     }
1590
1591     case Stmt::CXXOperatorCallExprClass: {
1592       const auto *OCE = cast<CXXOperatorCallExpr>(S);
1593
1594       // For instance method operators, make sure the 'this' argument has a
1595       // valid region.
1596       const Decl *Callee = OCE->getCalleeDecl();
1597       if (const auto *MD = dyn_cast_or_null<CXXMethodDecl>(Callee)) {
1598         if (MD->isInstance()) {
1599           ProgramStateRef State = Pred->getState();
1600           const LocationContext *LCtx = Pred->getLocationContext();
1601           ProgramStateRef NewState =
1602             createTemporaryRegionIfNeeded(State, LCtx, OCE->getArg(0));
1603           if (NewState != State) {
1604             Pred = Bldr.generateNode(OCE, Pred, NewState, /*tag=*/nullptr,
1605                                      ProgramPoint::PreStmtKind);
1606             // Did we cache out?
1607             if (!Pred)
1608               break;
1609           }
1610         }
1611       }
1612       // FALLTHROUGH
1613       LLVM_FALLTHROUGH;
1614     }
1615
1616     case Stmt::CallExprClass:
1617     case Stmt::CXXMemberCallExprClass:
1618     case Stmt::UserDefinedLiteralClass:
1619       Bldr.takeNodes(Pred);
1620       VisitCallExpr(cast<CallExpr>(S), Pred, Dst);
1621       Bldr.addNodes(Dst);
1622       break;
1623
1624     case Stmt::CXXCatchStmtClass:
1625       Bldr.takeNodes(Pred);
1626       VisitCXXCatchStmt(cast<CXXCatchStmt>(S), Pred, Dst);
1627       Bldr.addNodes(Dst);
1628       break;
1629
1630     case Stmt::CXXTemporaryObjectExprClass:
1631     case Stmt::CXXConstructExprClass:
1632       Bldr.takeNodes(Pred);
1633       VisitCXXConstructExpr(cast<CXXConstructExpr>(S), Pred, Dst);
1634       Bldr.addNodes(Dst);
1635       break;
1636
1637     case Stmt::CXXInheritedCtorInitExprClass:
1638       Bldr.takeNodes(Pred);
1639       VisitCXXInheritedCtorInitExpr(cast<CXXInheritedCtorInitExpr>(S), Pred,
1640                                     Dst);
1641       Bldr.addNodes(Dst);
1642       break;
1643
1644     case Stmt::CXXNewExprClass: {
1645       Bldr.takeNodes(Pred);
1646
1647       ExplodedNodeSet PreVisit;
1648       getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this);
1649
1650       ExplodedNodeSet PostVisit;
1651       for (const auto i : PreVisit)
1652         VisitCXXNewExpr(cast<CXXNewExpr>(S), i, PostVisit);
1653
1654       getCheckerManager().runCheckersForPostStmt(Dst, PostVisit, S, *this);
1655       Bldr.addNodes(Dst);
1656       break;
1657     }
1658
1659     case Stmt::CXXDeleteExprClass: {
1660       Bldr.takeNodes(Pred);
1661       ExplodedNodeSet PreVisit;
1662       const auto *CDE = cast<CXXDeleteExpr>(S);
1663       getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this);
1664       ExplodedNodeSet PostVisit;
1665       getCheckerManager().runCheckersForPostStmt(PostVisit, PreVisit, S, *this);
1666
1667       for (const auto i : PostVisit)
1668         VisitCXXDeleteExpr(CDE, i, Dst);
1669
1670       Bldr.addNodes(Dst);
1671       break;
1672     }
1673       // FIXME: ChooseExpr is really a constant.  We need to fix
1674       //        the CFG do not model them as explicit control-flow.
1675
1676     case Stmt::ChooseExprClass: { // __builtin_choose_expr
1677       Bldr.takeNodes(Pred);
1678       const auto *C = cast<ChooseExpr>(S);
1679       VisitGuardedExpr(C, C->getLHS(), C->getRHS(), Pred, Dst);
1680       Bldr.addNodes(Dst);
1681       break;
1682     }
1683
1684     case Stmt::CompoundAssignOperatorClass:
1685       Bldr.takeNodes(Pred);
1686       VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst);
1687       Bldr.addNodes(Dst);
1688       break;
1689
1690     case Stmt::CompoundLiteralExprClass:
1691       Bldr.takeNodes(Pred);
1692       VisitCompoundLiteralExpr(cast<CompoundLiteralExpr>(S), Pred, Dst);
1693       Bldr.addNodes(Dst);
1694       break;
1695
1696     case Stmt::BinaryConditionalOperatorClass:
1697     case Stmt::ConditionalOperatorClass: { // '?' operator
1698       Bldr.takeNodes(Pred);
1699       const auto *C = cast<AbstractConditionalOperator>(S);
1700       VisitGuardedExpr(C, C->getTrueExpr(), C->getFalseExpr(), Pred, Dst);
1701       Bldr.addNodes(Dst);
1702       break;
1703     }
1704
1705     case Stmt::CXXThisExprClass:
1706       Bldr.takeNodes(Pred);
1707       VisitCXXThisExpr(cast<CXXThisExpr>(S), Pred, Dst);
1708       Bldr.addNodes(Dst);
1709       break;
1710
1711     case Stmt::DeclRefExprClass: {
1712       Bldr.takeNodes(Pred);
1713       const auto *DE = cast<DeclRefExpr>(S);
1714       VisitCommonDeclRefExpr(DE, DE->getDecl(), Pred, Dst);
1715       Bldr.addNodes(Dst);
1716       break;
1717     }
1718
1719     case Stmt::DeclStmtClass:
1720       Bldr.takeNodes(Pred);
1721       VisitDeclStmt(cast<DeclStmt>(S), Pred, Dst);
1722       Bldr.addNodes(Dst);
1723       break;
1724
1725     case Stmt::ImplicitCastExprClass:
1726     case Stmt::CStyleCastExprClass:
1727     case Stmt::CXXStaticCastExprClass:
1728     case Stmt::CXXDynamicCastExprClass:
1729     case Stmt::CXXReinterpretCastExprClass:
1730     case Stmt::CXXConstCastExprClass:
1731     case Stmt::CXXFunctionalCastExprClass:
1732     case Stmt::BuiltinBitCastExprClass:
1733     case Stmt::ObjCBridgedCastExprClass:
1734     case Stmt::CXXAddrspaceCastExprClass: {
1735       Bldr.takeNodes(Pred);
1736       const auto *C = cast<CastExpr>(S);
1737       ExplodedNodeSet dstExpr;
1738       VisitCast(C, C->getSubExpr(), Pred, dstExpr);
1739
1740       // Handle the postvisit checks.
1741       getCheckerManager().runCheckersForPostStmt(Dst, dstExpr, C, *this);
1742       Bldr.addNodes(Dst);
1743       break;
1744     }
1745
1746     case Expr::MaterializeTemporaryExprClass: {
1747       Bldr.takeNodes(Pred);
1748       const auto *MTE = cast<MaterializeTemporaryExpr>(S);
1749       ExplodedNodeSet dstPrevisit;
1750       getCheckerManager().runCheckersForPreStmt(dstPrevisit, Pred, MTE, *this);
1751       ExplodedNodeSet dstExpr;
1752       for (const auto i : dstPrevisit)
1753         CreateCXXTemporaryObject(MTE, i, dstExpr);
1754       getCheckerManager().runCheckersForPostStmt(Dst, dstExpr, MTE, *this);
1755       Bldr.addNodes(Dst);
1756       break;
1757     }
1758
1759     case Stmt::InitListExprClass:
1760       Bldr.takeNodes(Pred);
1761       VisitInitListExpr(cast<InitListExpr>(S), Pred, Dst);
1762       Bldr.addNodes(Dst);
1763       break;
1764
1765     case Stmt::MemberExprClass:
1766       Bldr.takeNodes(Pred);
1767       VisitMemberExpr(cast<MemberExpr>(S), Pred, Dst);
1768       Bldr.addNodes(Dst);
1769       break;
1770
1771     case Stmt::AtomicExprClass:
1772       Bldr.takeNodes(Pred);
1773       VisitAtomicExpr(cast<AtomicExpr>(S), Pred, Dst);
1774       Bldr.addNodes(Dst);
1775       break;
1776
1777     case Stmt::ObjCIvarRefExprClass:
1778       Bldr.takeNodes(Pred);
1779       VisitLvalObjCIvarRefExpr(cast<ObjCIvarRefExpr>(S), Pred, Dst);
1780       Bldr.addNodes(Dst);
1781       break;
1782
1783     case Stmt::ObjCForCollectionStmtClass:
1784       Bldr.takeNodes(Pred);
1785       VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S), Pred, Dst);
1786       Bldr.addNodes(Dst);
1787       break;
1788
1789     case Stmt::ObjCMessageExprClass:
1790       Bldr.takeNodes(Pred);
1791       VisitObjCMessage(cast<ObjCMessageExpr>(S), Pred, Dst);
1792       Bldr.addNodes(Dst);
1793       break;
1794
1795     case Stmt::ObjCAtThrowStmtClass:
1796     case Stmt::CXXThrowExprClass:
1797       // FIXME: This is not complete.  We basically treat @throw as
1798       // an abort.
1799       Bldr.generateSink(S, Pred, Pred->getState());
1800       break;
1801
1802     case Stmt::ReturnStmtClass:
1803       Bldr.takeNodes(Pred);
1804       VisitReturnStmt(cast<ReturnStmt>(S), Pred, Dst);
1805       Bldr.addNodes(Dst);
1806       break;
1807
1808     case Stmt::OffsetOfExprClass: {
1809       Bldr.takeNodes(Pred);
1810       ExplodedNodeSet PreVisit;
1811       getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this);
1812
1813       ExplodedNodeSet PostVisit;
1814       for (const auto Node : PreVisit)
1815         VisitOffsetOfExpr(cast<OffsetOfExpr>(S), Node, PostVisit);
1816
1817       getCheckerManager().runCheckersForPostStmt(Dst, PostVisit, S, *this);
1818       Bldr.addNodes(Dst);
1819       break;
1820     }
1821
1822     case Stmt::UnaryExprOrTypeTraitExprClass:
1823       Bldr.takeNodes(Pred);
1824       VisitUnaryExprOrTypeTraitExpr(cast<UnaryExprOrTypeTraitExpr>(S),
1825                                     Pred, Dst);
1826       Bldr.addNodes(Dst);
1827       break;
1828
1829     case Stmt::StmtExprClass: {
1830       const auto *SE = cast<StmtExpr>(S);
1831
1832       if (SE->getSubStmt()->body_empty()) {
1833         // Empty statement expression.
1834         assert(SE->getType() == getContext().VoidTy
1835                && "Empty statement expression must have void type.");
1836         break;
1837       }
1838
1839       if (const auto *LastExpr =
1840               dyn_cast<Expr>(*SE->getSubStmt()->body_rbegin())) {
1841         ProgramStateRef state = Pred->getState();
1842         Bldr.generateNode(SE, Pred,
1843                           state->BindExpr(SE, Pred->getLocationContext(),
1844                                           state->getSVal(LastExpr,
1845                                                   Pred->getLocationContext())));
1846       }
1847       break;
1848     }
1849
1850     case Stmt::UnaryOperatorClass: {
1851       Bldr.takeNodes(Pred);
1852       const auto *U = cast<UnaryOperator>(S);
1853       if (AMgr.options.ShouldEagerlyAssume && (U->getOpcode() == UO_LNot)) {
1854         ExplodedNodeSet Tmp;
1855         VisitUnaryOperator(U, Pred, Tmp);
1856         evalEagerlyAssumeBinOpBifurcation(Dst, Tmp, U);
1857       }
1858       else
1859         VisitUnaryOperator(U, Pred, Dst);
1860       Bldr.addNodes(Dst);
1861       break;
1862     }
1863
1864     case Stmt::PseudoObjectExprClass: {
1865       Bldr.takeNodes(Pred);
1866       ProgramStateRef state = Pred->getState();
1867       const auto *PE = cast<PseudoObjectExpr>(S);
1868       if (const Expr *Result = PE->getResultExpr()) {
1869         SVal V = state->getSVal(Result, Pred->getLocationContext());
1870         Bldr.generateNode(S, Pred,
1871                           state->BindExpr(S, Pred->getLocationContext(), V));
1872       }
1873       else
1874         Bldr.generateNode(S, Pred,
1875                           state->BindExpr(S, Pred->getLocationContext(),
1876                                                    UnknownVal()));
1877
1878       Bldr.addNodes(Dst);
1879       break;
1880     }
1881
1882     case Expr::ObjCIndirectCopyRestoreExprClass: {
1883       // ObjCIndirectCopyRestoreExpr implies passing a temporary for
1884       // correctness of lifetime management.  Due to limited analysis
1885       // of ARC, this is implemented as direct arg passing.
1886       Bldr.takeNodes(Pred);
1887       ProgramStateRef state = Pred->getState();
1888       const auto *OIE = cast<ObjCIndirectCopyRestoreExpr>(S);
1889       const Expr *E = OIE->getSubExpr();
1890       SVal V = state->getSVal(E, Pred->getLocationContext());
1891       Bldr.generateNode(S, Pred,
1892               state->BindExpr(S, Pred->getLocationContext(), V));
1893       Bldr.addNodes(Dst);
1894       break;
1895     }
1896   }
1897 }
1898
1899 bool ExprEngine::replayWithoutInlining(ExplodedNode *N,
1900                                        const LocationContext *CalleeLC) {
1901   const StackFrameContext *CalleeSF = CalleeLC->getStackFrame();
1902   const StackFrameContext *CallerSF = CalleeSF->getParent()->getStackFrame();
1903   assert(CalleeSF && CallerSF);
1904   ExplodedNode *BeforeProcessingCall = nullptr;
1905   const Stmt *CE = CalleeSF->getCallSite();
1906
1907   // Find the first node before we started processing the call expression.
1908   while (N) {
1909     ProgramPoint L = N->getLocation();
1910     BeforeProcessingCall = N;
1911     N = N->pred_empty() ? nullptr : *(N->pred_begin());
1912
1913     // Skip the nodes corresponding to the inlined code.
1914     if (L.getStackFrame() != CallerSF)
1915       continue;
1916     // We reached the caller. Find the node right before we started
1917     // processing the call.
1918     if (L.isPurgeKind())
1919       continue;
1920     if (L.getAs<PreImplicitCall>())
1921       continue;
1922     if (L.getAs<CallEnter>())
1923       continue;
1924     if (Optional<StmtPoint> SP = L.getAs<StmtPoint>())
1925       if (SP->getStmt() == CE)
1926         continue;
1927     break;
1928   }
1929
1930   if (!BeforeProcessingCall)
1931     return false;
1932
1933   // TODO: Clean up the unneeded nodes.
1934
1935   // Build an Epsilon node from which we will restart the analyzes.
1936   // Note that CE is permitted to be NULL!
1937   ProgramPoint NewNodeLoc =
1938                EpsilonPoint(BeforeProcessingCall->getLocationContext(), CE);
1939   // Add the special flag to GDM to signal retrying with no inlining.
1940   // Note, changing the state ensures that we are not going to cache out.
1941   ProgramStateRef NewNodeState = BeforeProcessingCall->getState();
1942   NewNodeState =
1943     NewNodeState->set<ReplayWithoutInlining>(const_cast<Stmt *>(CE));
1944
1945   // Make the new node a successor of BeforeProcessingCall.
1946   bool IsNew = false;
1947   ExplodedNode *NewNode = G.getNode(NewNodeLoc, NewNodeState, false, &IsNew);
1948   // We cached out at this point. Caching out is common due to us backtracking
1949   // from the inlined function, which might spawn several paths.
1950   if (!IsNew)
1951     return true;
1952
1953   NewNode->addPredecessor(BeforeProcessingCall, G);
1954
1955   // Add the new node to the work list.
1956   Engine.enqueueStmtNode(NewNode, CalleeSF->getCallSiteBlock(),
1957                                   CalleeSF->getIndex());
1958   NumTimesRetriedWithoutInlining++;
1959   return true;
1960 }
1961
1962 /// Block entrance.  (Update counters).
1963 void ExprEngine::processCFGBlockEntrance(const BlockEdge &L,
1964                                          NodeBuilderWithSinks &nodeBuilder,
1965                                          ExplodedNode *Pred) {
1966   PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext());
1967   // If we reach a loop which has a known bound (and meets
1968   // other constraints) then consider completely unrolling it.
1969   if(AMgr.options.ShouldUnrollLoops) {
1970     unsigned maxBlockVisitOnPath = AMgr.options.maxBlockVisitOnPath;
1971     const Stmt *Term = nodeBuilder.getContext().getBlock()->getTerminatorStmt();
1972     if (Term) {
1973       ProgramStateRef NewState = updateLoopStack(Term, AMgr.getASTContext(),
1974                                                  Pred, maxBlockVisitOnPath);
1975       if (NewState != Pred->getState()) {
1976         ExplodedNode *UpdatedNode = nodeBuilder.generateNode(NewState, Pred);
1977         if (!UpdatedNode)
1978           return;
1979         Pred = UpdatedNode;
1980       }
1981     }
1982     // Is we are inside an unrolled loop then no need the check the counters.
1983     if(isUnrolledState(Pred->getState()))
1984       return;
1985   }
1986
1987   // If this block is terminated by a loop and it has already been visited the
1988   // maximum number of times, widen the loop.
1989   unsigned int BlockCount = nodeBuilder.getContext().blockCount();
1990   if (BlockCount == AMgr.options.maxBlockVisitOnPath - 1 &&
1991       AMgr.options.ShouldWidenLoops) {
1992     const Stmt *Term = nodeBuilder.getContext().getBlock()->getTerminatorStmt();
1993     if (!isa_and_nonnull<ForStmt, WhileStmt, DoStmt>(Term))
1994       return;
1995     // Widen.
1996     const LocationContext *LCtx = Pred->getLocationContext();
1997     ProgramStateRef WidenedState =
1998         getWidenedLoopState(Pred->getState(), LCtx, BlockCount, Term);
1999     nodeBuilder.generateNode(WidenedState, Pred);
2000     return;
2001   }
2002
2003   // FIXME: Refactor this into a checker.
2004   if (BlockCount >= AMgr.options.maxBlockVisitOnPath) {
2005     static SimpleProgramPointTag tag(TagProviderName, "Block count exceeded");
2006     const ExplodedNode *Sink =
2007                    nodeBuilder.generateSink(Pred->getState(), Pred, &tag);
2008
2009     // Check if we stopped at the top level function or not.
2010     // Root node should have the location context of the top most function.
2011     const LocationContext *CalleeLC = Pred->getLocation().getLocationContext();
2012     const LocationContext *CalleeSF = CalleeLC->getStackFrame();
2013     const LocationContext *RootLC =
2014                         (*G.roots_begin())->getLocation().getLocationContext();
2015     if (RootLC->getStackFrame() != CalleeSF) {
2016       Engine.FunctionSummaries->markReachedMaxBlockCount(CalleeSF->getDecl());
2017
2018       // Re-run the call evaluation without inlining it, by storing the
2019       // no-inlining policy in the state and enqueuing the new work item on
2020       // the list. Replay should almost never fail. Use the stats to catch it
2021       // if it does.
2022       if ((!AMgr.options.NoRetryExhausted &&
2023            replayWithoutInlining(Pred, CalleeLC)))
2024         return;
2025       NumMaxBlockCountReachedInInlined++;
2026     } else
2027       NumMaxBlockCountReached++;
2028
2029     // Make sink nodes as exhausted(for stats) only if retry failed.
2030     Engine.blocksExhausted.push_back(std::make_pair(L, Sink));
2031   }
2032 }
2033
2034 //===----------------------------------------------------------------------===//
2035 // Branch processing.
2036 //===----------------------------------------------------------------------===//
2037
2038 /// RecoverCastedSymbol - A helper function for ProcessBranch that is used
2039 /// to try to recover some path-sensitivity for casts of symbolic
2040 /// integers that promote their values (which are currently not tracked well).
2041 /// This function returns the SVal bound to Condition->IgnoreCasts if all the
2042 //  cast(s) did was sign-extend the original value.
2043 static SVal RecoverCastedSymbol(ProgramStateRef state,
2044                                 const Stmt *Condition,
2045                                 const LocationContext *LCtx,
2046                                 ASTContext &Ctx) {
2047
2048   const auto *Ex = dyn_cast<Expr>(Condition);
2049   if (!Ex)
2050     return UnknownVal();
2051
2052   uint64_t bits = 0;
2053   bool bitsInit = false;
2054
2055   while (const auto *CE = dyn_cast<CastExpr>(Ex)) {
2056     QualType T = CE->getType();
2057
2058     if (!T->isIntegralOrEnumerationType())
2059       return UnknownVal();
2060
2061     uint64_t newBits = Ctx.getTypeSize(T);
2062     if (!bitsInit || newBits < bits) {
2063       bitsInit = true;
2064       bits = newBits;
2065     }
2066
2067     Ex = CE->getSubExpr();
2068   }
2069
2070   // We reached a non-cast.  Is it a symbolic value?
2071   QualType T = Ex->getType();
2072
2073   if (!bitsInit || !T->isIntegralOrEnumerationType() ||
2074       Ctx.getTypeSize(T) > bits)
2075     return UnknownVal();
2076
2077   return state->getSVal(Ex, LCtx);
2078 }
2079
2080 #ifndef NDEBUG
2081 static const Stmt *getRightmostLeaf(const Stmt *Condition) {
2082   while (Condition) {
2083     const auto *BO = dyn_cast<BinaryOperator>(Condition);
2084     if (!BO || !BO->isLogicalOp()) {
2085       return Condition;
2086     }
2087     Condition = BO->getRHS()->IgnoreParens();
2088   }
2089   return nullptr;
2090 }
2091 #endif
2092
2093 // Returns the condition the branch at the end of 'B' depends on and whose value
2094 // has been evaluated within 'B'.
2095 // In most cases, the terminator condition of 'B' will be evaluated fully in
2096 // the last statement of 'B'; in those cases, the resolved condition is the
2097 // given 'Condition'.
2098 // If the condition of the branch is a logical binary operator tree, the CFG is
2099 // optimized: in that case, we know that the expression formed by all but the
2100 // rightmost leaf of the logical binary operator tree must be true, and thus
2101 // the branch condition is at this point equivalent to the truth value of that
2102 // rightmost leaf; the CFG block thus only evaluates this rightmost leaf
2103 // expression in its final statement. As the full condition in that case was
2104 // not evaluated, and is thus not in the SVal cache, we need to use that leaf
2105 // expression to evaluate the truth value of the condition in the current state
2106 // space.
2107 static const Stmt *ResolveCondition(const Stmt *Condition,
2108                                     const CFGBlock *B) {
2109   if (const auto *Ex = dyn_cast<Expr>(Condition))
2110     Condition = Ex->IgnoreParens();
2111
2112   const auto *BO = dyn_cast<BinaryOperator>(Condition);
2113   if (!BO || !BO->isLogicalOp())
2114     return Condition;
2115
2116   assert(B->getTerminator().isStmtBranch() &&
2117          "Other kinds of branches are handled separately!");
2118
2119   // For logical operations, we still have the case where some branches
2120   // use the traditional "merge" approach and others sink the branch
2121   // directly into the basic blocks representing the logical operation.
2122   // We need to distinguish between those two cases here.
2123
2124   // The invariants are still shifting, but it is possible that the
2125   // last element in a CFGBlock is not a CFGStmt.  Look for the last
2126   // CFGStmt as the value of the condition.
2127   CFGBlock::const_reverse_iterator I = B->rbegin(), E = B->rend();
2128   for (; I != E; ++I) {
2129     CFGElement Elem = *I;
2130     Optional<CFGStmt> CS = Elem.getAs<CFGStmt>();
2131     if (!CS)
2132       continue;
2133     const Stmt *LastStmt = CS->getStmt();
2134     assert(LastStmt == Condition || LastStmt == getRightmostLeaf(Condition));
2135     return LastStmt;
2136   }
2137   llvm_unreachable("could not resolve condition");
2138 }
2139
2140 using ObjCForLctxPair =
2141     std::pair<const ObjCForCollectionStmt *, const LocationContext *>;
2142
2143 REGISTER_MAP_WITH_PROGRAMSTATE(ObjCForHasMoreIterations, ObjCForLctxPair, bool)
2144
2145 ProgramStateRef ExprEngine::setWhetherHasMoreIteration(
2146     ProgramStateRef State, const ObjCForCollectionStmt *O,
2147     const LocationContext *LC, bool HasMoreIteraton) {
2148   assert(!State->contains<ObjCForHasMoreIterations>({O, LC}));
2149   return State->set<ObjCForHasMoreIterations>({O, LC}, HasMoreIteraton);
2150 }
2151
2152 ProgramStateRef
2153 ExprEngine::removeIterationState(ProgramStateRef State,
2154                                  const ObjCForCollectionStmt *O,
2155                                  const LocationContext *LC) {
2156   assert(State->contains<ObjCForHasMoreIterations>({O, LC}));
2157   return State->remove<ObjCForHasMoreIterations>({O, LC});
2158 }
2159
2160 bool ExprEngine::hasMoreIteration(ProgramStateRef State,
2161                                   const ObjCForCollectionStmt *O,
2162                                   const LocationContext *LC) {
2163   assert(State->contains<ObjCForHasMoreIterations>({O, LC}));
2164   return *State->get<ObjCForHasMoreIterations>({O, LC});
2165 }
2166
2167 /// Split the state on whether there are any more iterations left for this loop.
2168 /// Returns a (HasMoreIteration, HasNoMoreIteration) pair, or None when the
2169 /// acquisition of the loop condition value failed.
2170 static Optional<std::pair<ProgramStateRef, ProgramStateRef>>
2171 assumeCondition(const Stmt *Condition, ExplodedNode *N) {
2172   ProgramStateRef State = N->getState();
2173   if (const auto *ObjCFor = dyn_cast<ObjCForCollectionStmt>(Condition)) {
2174     bool HasMoreIteraton =
2175         ExprEngine::hasMoreIteration(State, ObjCFor, N->getLocationContext());
2176     // Checkers have already ran on branch conditions, so the current
2177     // information as to whether the loop has more iteration becomes outdated
2178     // after this point.
2179     State = ExprEngine::removeIterationState(State, ObjCFor,
2180                                              N->getLocationContext());
2181     if (HasMoreIteraton)
2182       return std::pair<ProgramStateRef, ProgramStateRef>{State, nullptr};
2183     else
2184       return std::pair<ProgramStateRef, ProgramStateRef>{nullptr, State};
2185   }
2186   SVal X = State->getSVal(Condition, N->getLocationContext());
2187
2188   if (X.isUnknownOrUndef()) {
2189     // Give it a chance to recover from unknown.
2190     if (const auto *Ex = dyn_cast<Expr>(Condition)) {
2191       if (Ex->getType()->isIntegralOrEnumerationType()) {
2192         // Try to recover some path-sensitivity.  Right now casts of symbolic
2193         // integers that promote their values are currently not tracked well.
2194         // If 'Condition' is such an expression, try and recover the
2195         // underlying value and use that instead.
2196         SVal recovered =
2197             RecoverCastedSymbol(State, Condition, N->getLocationContext(),
2198                                 N->getState()->getStateManager().getContext());
2199
2200         if (!recovered.isUnknown()) {
2201           X = recovered;
2202         }
2203       }
2204     }
2205   }
2206
2207   // If the condition is still unknown, give up.
2208   if (X.isUnknownOrUndef())
2209     return None;
2210
2211   DefinedSVal V = X.castAs<DefinedSVal>();
2212
2213   ProgramStateRef StTrue, StFalse;
2214   return State->assume(V);
2215 }
2216
2217 void ExprEngine::processBranch(const Stmt *Condition,
2218                                NodeBuilderContext& BldCtx,
2219                                ExplodedNode *Pred,
2220                                ExplodedNodeSet &Dst,
2221                                const CFGBlock *DstT,
2222                                const CFGBlock *DstF) {
2223   assert((!Condition || !isa<CXXBindTemporaryExpr>(Condition)) &&
2224          "CXXBindTemporaryExprs are handled by processBindTemporary.");
2225   const LocationContext *LCtx = Pred->getLocationContext();
2226   PrettyStackTraceLocationContext StackCrashInfo(LCtx);
2227   currBldrCtx = &BldCtx;
2228
2229   // Check for NULL conditions; e.g. "for(;;)"
2230   if (!Condition) {
2231     BranchNodeBuilder NullCondBldr(Pred, Dst, BldCtx, DstT, DstF);
2232     NullCondBldr.markInfeasible(false);
2233     NullCondBldr.generateNode(Pred->getState(), true, Pred);
2234     return;
2235   }
2236
2237   if (const auto *Ex = dyn_cast<Expr>(Condition))
2238     Condition = Ex->IgnoreParens();
2239
2240   Condition = ResolveCondition(Condition, BldCtx.getBlock());
2241   PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
2242                                 Condition->getBeginLoc(),
2243                                 "Error evaluating branch");
2244
2245   ExplodedNodeSet CheckersOutSet;
2246   getCheckerManager().runCheckersForBranchCondition(Condition, CheckersOutSet,
2247                                                     Pred, *this);
2248   // We generated only sinks.
2249   if (CheckersOutSet.empty())
2250     return;
2251
2252   BranchNodeBuilder builder(CheckersOutSet, Dst, BldCtx, DstT, DstF);
2253   for (ExplodedNode *PredN : CheckersOutSet) {
2254     if (PredN->isSink())
2255       continue;
2256
2257     ProgramStateRef PrevState = PredN->getState();
2258
2259     ProgramStateRef StTrue, StFalse;
2260     if (const auto KnownCondValueAssumption = assumeCondition(Condition, PredN))
2261       std::tie(StTrue, StFalse) = *KnownCondValueAssumption;
2262     else {
2263       assert(!isa<ObjCForCollectionStmt>(Condition));
2264       builder.generateNode(PrevState, true, PredN);
2265       builder.generateNode(PrevState, false, PredN);
2266       continue;
2267     }
2268     if (StTrue && StFalse)
2269       assert(!isa<ObjCForCollectionStmt>(Condition));
2270
2271     // Process the true branch.
2272     if (builder.isFeasible(true)) {
2273       if (StTrue)
2274         builder.generateNode(StTrue, true, PredN);
2275       else
2276         builder.markInfeasible(true);
2277     }
2278
2279     // Process the false branch.
2280     if (builder.isFeasible(false)) {
2281       if (StFalse)
2282         builder.generateNode(StFalse, false, PredN);
2283       else
2284         builder.markInfeasible(false);
2285     }
2286   }
2287   currBldrCtx = nullptr;
2288 }
2289
2290 /// The GDM component containing the set of global variables which have been
2291 /// previously initialized with explicit initializers.
2292 REGISTER_TRAIT_WITH_PROGRAMSTATE(InitializedGlobalsSet,
2293                                  llvm::ImmutableSet<const VarDecl *>)
2294
2295 void ExprEngine::processStaticInitializer(const DeclStmt *DS,
2296                                           NodeBuilderContext &BuilderCtx,
2297                                           ExplodedNode *Pred,
2298                                           ExplodedNodeSet &Dst,
2299                                           const CFGBlock *DstT,
2300                                           const CFGBlock *DstF) {
2301   PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext());
2302   currBldrCtx = &BuilderCtx;
2303
2304   const auto *VD = cast<VarDecl>(DS->getSingleDecl());
2305   ProgramStateRef state = Pred->getState();
2306   bool initHasRun = state->contains<InitializedGlobalsSet>(VD);
2307   BranchNodeBuilder builder(Pred, Dst, BuilderCtx, DstT, DstF);
2308
2309   if (!initHasRun) {
2310     state = state->add<InitializedGlobalsSet>(VD);
2311   }
2312
2313   builder.generateNode(state, initHasRun, Pred);
2314   builder.markInfeasible(!initHasRun);
2315
2316   currBldrCtx = nullptr;
2317 }
2318
2319 /// processIndirectGoto - Called by CoreEngine.  Used to generate successor
2320 ///  nodes by processing the 'effects' of a computed goto jump.
2321 void ExprEngine::processIndirectGoto(IndirectGotoNodeBuilder &builder) {
2322   ProgramStateRef state = builder.getState();
2323   SVal V = state->getSVal(builder.getTarget(), builder.getLocationContext());
2324
2325   // Three possibilities:
2326   //
2327   //   (1) We know the computed label.
2328   //   (2) The label is NULL (or some other constant), or Undefined.
2329   //   (3) We have no clue about the label.  Dispatch to all targets.
2330   //
2331
2332   using iterator = IndirectGotoNodeBuilder::iterator;
2333
2334   if (Optional<loc::GotoLabel> LV = V.getAs<loc::GotoLabel>()) {
2335     const LabelDecl *L = LV->getLabel();
2336
2337     for (iterator I = builder.begin(), E = builder.end(); I != E; ++I) {
2338       if (I.getLabel() == L) {
2339         builder.generateNode(I, state);
2340         return;
2341       }
2342     }
2343
2344     llvm_unreachable("No block with label.");
2345   }
2346
2347   if (isa<UndefinedVal, loc::ConcreteInt>(V)) {
2348     // Dispatch to the first target and mark it as a sink.
2349     //ExplodedNode* N = builder.generateNode(builder.begin(), state, true);
2350     // FIXME: add checker visit.
2351     //    UndefBranches.insert(N);
2352     return;
2353   }
2354
2355   // This is really a catch-all.  We don't support symbolics yet.
2356   // FIXME: Implement dispatch for symbolic pointers.
2357
2358   for (iterator I = builder.begin(), E = builder.end(); I != E; ++I)
2359     builder.generateNode(I, state);
2360 }
2361
2362 void ExprEngine::processBeginOfFunction(NodeBuilderContext &BC,
2363                                         ExplodedNode *Pred,
2364                                         ExplodedNodeSet &Dst,
2365                                         const BlockEdge &L) {
2366   SaveAndRestore<const NodeBuilderContext *> NodeContextRAII(currBldrCtx, &BC);
2367   getCheckerManager().runCheckersForBeginFunction(Dst, L, Pred, *this);
2368 }
2369
2370 /// ProcessEndPath - Called by CoreEngine.  Used to generate end-of-path
2371 ///  nodes when the control reaches the end of a function.
2372 void ExprEngine::processEndOfFunction(NodeBuilderContext& BC,
2373                                       ExplodedNode *Pred,
2374                                       const ReturnStmt *RS) {
2375   ProgramStateRef State = Pred->getState();
2376
2377   if (!Pred->getStackFrame()->inTopFrame())
2378     State = finishArgumentConstruction(
2379         State, *getStateManager().getCallEventManager().getCaller(
2380                    Pred->getStackFrame(), Pred->getState()));
2381
2382   // FIXME: We currently cannot assert that temporaries are clear, because
2383   // lifetime extended temporaries are not always modelled correctly. In some
2384   // cases when we materialize the temporary, we do
2385   // createTemporaryRegionIfNeeded(), and the region changes, and also the
2386   // respective destructor becomes automatic from temporary. So for now clean up
2387   // the state manually before asserting. Ideally, this braced block of code
2388   // should go away.
2389   {
2390     const LocationContext *FromLC = Pred->getLocationContext();
2391     const LocationContext *ToLC = FromLC->getStackFrame()->getParent();
2392     const LocationContext *LC = FromLC;
2393     while (LC != ToLC) {
2394       assert(LC && "ToLC must be a parent of FromLC!");
2395       for (auto I : State->get<ObjectsUnderConstruction>())
2396         if (I.first.getLocationContext() == LC) {
2397           // The comment above only pardons us for not cleaning up a
2398           // temporary destructor. If any other statements are found here,
2399           // it must be a separate problem.
2400           assert(I.first.getItem().getKind() ==
2401                      ConstructionContextItem::TemporaryDestructorKind ||
2402                  I.first.getItem().getKind() ==
2403                      ConstructionContextItem::ElidedDestructorKind);
2404           State = State->remove<ObjectsUnderConstruction>(I.first);
2405         }
2406       LC = LC->getParent();
2407     }
2408   }
2409
2410   // Perform the transition with cleanups.
2411   if (State != Pred->getState()) {
2412     ExplodedNodeSet PostCleanup;
2413     NodeBuilder Bldr(Pred, PostCleanup, BC);
2414     Pred = Bldr.generateNode(Pred->getLocation(), State, Pred);
2415     if (!Pred) {
2416       // The node with clean temporaries already exists. We might have reached
2417       // it on a path on which we initialize different temporaries.
2418       return;
2419     }
2420   }
2421
2422   assert(areAllObjectsFullyConstructed(Pred->getState(),
2423                                        Pred->getLocationContext(),
2424                                        Pred->getStackFrame()->getParent()));
2425
2426   PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext());
2427
2428   ExplodedNodeSet Dst;
2429   if (Pred->getLocationContext()->inTopFrame()) {
2430     // Remove dead symbols.
2431     ExplodedNodeSet AfterRemovedDead;
2432     removeDeadOnEndOfFunction(BC, Pred, AfterRemovedDead);
2433
2434     // Notify checkers.
2435     for (const auto I : AfterRemovedDead)
2436       getCheckerManager().runCheckersForEndFunction(BC, Dst, I, *this, RS);
2437   } else {
2438     getCheckerManager().runCheckersForEndFunction(BC, Dst, Pred, *this, RS);
2439   }
2440
2441   Engine.enqueueEndOfFunction(Dst, RS);
2442 }
2443
2444 /// ProcessSwitch - Called by CoreEngine.  Used to generate successor
2445 ///  nodes by processing the 'effects' of a switch statement.
2446 void ExprEngine::processSwitch(SwitchNodeBuilder& builder) {
2447   using iterator = SwitchNodeBuilder::iterator;
2448
2449   ProgramStateRef state = builder.getState();
2450   const Expr *CondE = builder.getCondition();
2451   SVal  CondV_untested = state->getSVal(CondE, builder.getLocationContext());
2452
2453   if (CondV_untested.isUndef()) {
2454     //ExplodedNode* N = builder.generateDefaultCaseNode(state, true);
2455     // FIXME: add checker
2456     //UndefBranches.insert(N);
2457
2458     return;
2459   }
2460   DefinedOrUnknownSVal CondV = CondV_untested.castAs<DefinedOrUnknownSVal>();
2461
2462   ProgramStateRef DefaultSt = state;
2463
2464   iterator I = builder.begin(), EI = builder.end();
2465   bool defaultIsFeasible = I == EI;
2466
2467   for ( ; I != EI; ++I) {
2468     // Successor may be pruned out during CFG construction.
2469     if (!I.getBlock())
2470       continue;
2471
2472     const CaseStmt *Case = I.getCase();
2473
2474     // Evaluate the LHS of the case value.
2475     llvm::APSInt V1 = Case->getLHS()->EvaluateKnownConstInt(getContext());
2476     assert(V1.getBitWidth() == getContext().getIntWidth(CondE->getType()));
2477
2478     // Get the RHS of the case, if it exists.
2479     llvm::APSInt V2;
2480     if (const Expr *E = Case->getRHS())
2481       V2 = E->EvaluateKnownConstInt(getContext());
2482     else
2483       V2 = V1;
2484
2485     ProgramStateRef StateCase;
2486     if (Optional<NonLoc> NL = CondV.getAs<NonLoc>())
2487       std::tie(StateCase, DefaultSt) =
2488           DefaultSt->assumeInclusiveRange(*NL, V1, V2);
2489     else // UnknownVal
2490       StateCase = DefaultSt;
2491
2492     if (StateCase)
2493       builder.generateCaseStmtNode(I, StateCase);
2494
2495     // Now "assume" that the case doesn't match.  Add this state
2496     // to the default state (if it is feasible).
2497     if (DefaultSt)
2498       defaultIsFeasible = true;
2499     else {
2500       defaultIsFeasible = false;
2501       break;
2502     }
2503   }
2504
2505   if (!defaultIsFeasible)
2506     return;
2507
2508   // If we have switch(enum value), the default branch is not
2509   // feasible if all of the enum constants not covered by 'case:' statements
2510   // are not feasible values for the switch condition.
2511   //
2512   // Note that this isn't as accurate as it could be.  Even if there isn't
2513   // a case for a particular enum value as long as that enum value isn't
2514   // feasible then it shouldn't be considered for making 'default:' reachable.
2515   const SwitchStmt *SS = builder.getSwitch();
2516   const Expr *CondExpr = SS->getCond()->IgnoreParenImpCasts();
2517   if (CondExpr->getType()->getAs<EnumType>()) {
2518     if (SS->isAllEnumCasesCovered())
2519       return;
2520   }
2521
2522   builder.generateDefaultCaseNode(DefaultSt);
2523 }
2524
2525 //===----------------------------------------------------------------------===//
2526 // Transfer functions: Loads and stores.
2527 //===----------------------------------------------------------------------===//
2528
2529 void ExprEngine::VisitCommonDeclRefExpr(const Expr *Ex, const NamedDecl *D,
2530                                         ExplodedNode *Pred,
2531                                         ExplodedNodeSet &Dst) {
2532   StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
2533
2534   ProgramStateRef state = Pred->getState();
2535   const LocationContext *LCtx = Pred->getLocationContext();
2536
2537   if (const auto *VD = dyn_cast<VarDecl>(D)) {
2538     // C permits "extern void v", and if you cast the address to a valid type,
2539     // you can even do things with it. We simply pretend
2540     assert(Ex->isGLValue() || VD->getType()->isVoidType());
2541     const LocationContext *LocCtxt = Pred->getLocationContext();
2542     const Decl *D = LocCtxt->getDecl();
2543     const auto *MD = dyn_cast_or_null<CXXMethodDecl>(D);
2544     const auto *DeclRefEx = dyn_cast<DeclRefExpr>(Ex);
2545     Optional<std::pair<SVal, QualType>> VInfo;
2546
2547     if (AMgr.options.ShouldInlineLambdas && DeclRefEx &&
2548         DeclRefEx->refersToEnclosingVariableOrCapture() && MD &&
2549         MD->getParent()->isLambda()) {
2550       // Lookup the field of the lambda.
2551       const CXXRecordDecl *CXXRec = MD->getParent();
2552       llvm::DenseMap<const VarDecl *, FieldDecl *> LambdaCaptureFields;
2553       FieldDecl *LambdaThisCaptureField;
2554       CXXRec->getCaptureFields(LambdaCaptureFields, LambdaThisCaptureField);
2555
2556       // Sema follows a sequence of complex rules to determine whether the
2557       // variable should be captured.
2558       if (const FieldDecl *FD = LambdaCaptureFields[VD]) {
2559         Loc CXXThis =
2560             svalBuilder.getCXXThis(MD, LocCtxt->getStackFrame());
2561         SVal CXXThisVal = state->getSVal(CXXThis);
2562         VInfo = std::make_pair(state->getLValue(FD, CXXThisVal), FD->getType());
2563       }
2564     }
2565
2566     if (!VInfo)
2567       VInfo = std::make_pair(state->getLValue(VD, LocCtxt), VD->getType());
2568
2569     SVal V = VInfo->first;
2570     bool IsReference = VInfo->second->isReferenceType();
2571
2572     // For references, the 'lvalue' is the pointer address stored in the
2573     // reference region.
2574     if (IsReference) {
2575       if (const MemRegion *R = V.getAsRegion())
2576         V = state->getSVal(R);
2577       else
2578         V = UnknownVal();
2579     }
2580
2581     Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), nullptr,
2582                       ProgramPoint::PostLValueKind);
2583     return;
2584   }
2585   if (const auto *ED = dyn_cast<EnumConstantDecl>(D)) {
2586     assert(!Ex->isGLValue());
2587     SVal V = svalBuilder.makeIntVal(ED->getInitVal());
2588     Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V));
2589     return;
2590   }
2591   if (const auto *FD = dyn_cast<FunctionDecl>(D)) {
2592     SVal V = svalBuilder.getFunctionPointer(FD);
2593     Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), nullptr,
2594                       ProgramPoint::PostLValueKind);
2595     return;
2596   }
2597   if (isa<FieldDecl, IndirectFieldDecl>(D)) {
2598     // Delegate all work related to pointer to members to the surrounding
2599     // operator&.
2600     return;
2601   }
2602   if (const auto *BD = dyn_cast<BindingDecl>(D)) {
2603     const auto *DD = cast<DecompositionDecl>(BD->getDecomposedDecl());
2604
2605     SVal Base = state->getLValue(DD, LCtx);
2606     if (DD->getType()->isReferenceType()) {
2607       Base = state->getSVal(Base.getAsRegion());
2608     }
2609
2610     SVal V = UnknownVal();
2611
2612     // Handle binding to data members
2613     if (const auto *ME = dyn_cast<MemberExpr>(BD->getBinding())) {
2614       const auto *Field = cast<FieldDecl>(ME->getMemberDecl());
2615       V = state->getLValue(Field, Base);
2616     }
2617     // Handle binding to arrays
2618     else if (const auto *ASE = dyn_cast<ArraySubscriptExpr>(BD->getBinding())) {
2619       SVal Idx = state->getSVal(ASE->getIdx(), LCtx);
2620
2621       // Note: the index of an element in a structured binding is automatically
2622       // created and it is a unique identifier of the specific element. Thus it
2623       // cannot be a value that varies at runtime.
2624       assert(Idx.isConstant() && "BindingDecl array index is not a constant!");
2625
2626       V = state->getLValue(BD->getType(), Idx, Base);
2627     }
2628     // Handle binding to tuple-like strcutures
2629     else if (BD->getHoldingVar()) {
2630       // FIXME: handle tuples
2631       return;
2632     } else
2633       llvm_unreachable("An unknown case of structured binding encountered!");
2634
2635     if (BD->getType()->isReferenceType())
2636       V = state->getSVal(V.getAsRegion());
2637
2638     Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), nullptr,
2639                       ProgramPoint::PostLValueKind);
2640
2641     return;
2642   }
2643
2644   llvm_unreachable("Support for this Decl not implemented.");
2645 }
2646
2647 /// VisitArrayInitLoopExpr - Transfer function for array init loop.
2648 void ExprEngine::VisitArrayInitLoopExpr(const ArrayInitLoopExpr *Ex,
2649                                         ExplodedNode *Pred,
2650                                         ExplodedNodeSet &Dst) {
2651   ExplodedNodeSet CheckerPreStmt;
2652   getCheckerManager().runCheckersForPreStmt(CheckerPreStmt, Pred, Ex, *this);
2653
2654   ExplodedNodeSet EvalSet;
2655   StmtNodeBuilder Bldr(CheckerPreStmt, EvalSet, *currBldrCtx);
2656
2657   const Expr *Arr = Ex->getCommonExpr()->getSourceExpr();
2658
2659   for (auto *Node : CheckerPreStmt) {
2660     const LocationContext *LCtx = Node->getLocationContext();
2661     ProgramStateRef state = Node->getState();
2662
2663     SVal Base = UnknownVal();
2664
2665     // As in case of this expression the sub-expressions are not visited by any
2666     // other transfer functions, they are handled by matching their AST.
2667
2668     // Case of implicit copy or move ctor of object with array member
2669     //
2670     // Note: ExprEngine::VisitMemberExpr is not able to bind the array to the
2671     // environment.
2672     //
2673     //    struct S {
2674     //      int arr[2];
2675     //    };
2676     //
2677     //
2678     //    S a;
2679     //    S b = a;
2680     //
2681     // The AST in case of a *copy constructor* looks like this:
2682     //    ArrayInitLoopExpr
2683     //    |-OpaqueValueExpr
2684     //    | `-MemberExpr              <-- match this
2685     //    |   `-DeclRefExpr
2686     //    ` ...
2687     //
2688     //
2689     //    S c;
2690     //    S d = std::move(d);
2691     //
2692     // In case of a *move constructor* the resulting AST looks like:
2693     //    ArrayInitLoopExpr
2694     //    |-OpaqueValueExpr
2695     //    | `-MemberExpr              <-- match this first
2696     //    |   `-CXXStaticCastExpr     <-- match this after
2697     //    |     `-DeclRefExpr
2698     //    ` ...
2699     if (const auto *ME = dyn_cast<MemberExpr>(Arr)) {
2700       Expr *MEBase = ME->getBase();
2701
2702       // Move ctor
2703       if (auto CXXSCE = dyn_cast<CXXStaticCastExpr>(MEBase)) {
2704         MEBase = CXXSCE->getSubExpr();
2705       }
2706
2707       auto ObjDeclExpr = cast<DeclRefExpr>(MEBase);
2708       SVal Obj = state->getLValue(cast<VarDecl>(ObjDeclExpr->getDecl()), LCtx);
2709
2710       Base = state->getLValue(cast<FieldDecl>(ME->getMemberDecl()), Obj);
2711     }
2712
2713     // Case of lambda capture and decomposition declaration
2714     //
2715     //    int arr[2];
2716     //
2717     //    [arr]{ int a = arr[0]; }();
2718     //    auto[a, b] = arr;
2719     //
2720     // In both of these cases the AST looks like the following:
2721     //    ArrayInitLoopExpr
2722     //    |-OpaqueValueExpr
2723     //    | `-DeclRefExpr             <-- match this
2724     //    ` ...
2725     if (const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(Arr))
2726       Base = state->getLValue(cast<VarDecl>(DRE->getDecl()), LCtx);
2727
2728     // Create a lazy compound value to the original array
2729     if (const MemRegion *R = Base.getAsRegion())
2730       Base = state->getSVal(R);
2731     else
2732       Base = UnknownVal();
2733
2734     Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, Base));
2735   }
2736
2737   getCheckerManager().runCheckersForPostStmt(Dst, EvalSet, Ex, *this);
2738 }
2739
2740 /// VisitArraySubscriptExpr - Transfer function for array accesses
2741 void ExprEngine::VisitArraySubscriptExpr(const ArraySubscriptExpr *A,
2742                                              ExplodedNode *Pred,
2743                                              ExplodedNodeSet &Dst){
2744   const Expr *Base = A->getBase()->IgnoreParens();
2745   const Expr *Idx  = A->getIdx()->IgnoreParens();
2746
2747   ExplodedNodeSet CheckerPreStmt;
2748   getCheckerManager().runCheckersForPreStmt(CheckerPreStmt, Pred, A, *this);
2749
2750   ExplodedNodeSet EvalSet;
2751   StmtNodeBuilder Bldr(CheckerPreStmt, EvalSet, *currBldrCtx);
2752
2753   bool IsVectorType = A->getBase()->getType()->isVectorType();
2754
2755   // The "like" case is for situations where C standard prohibits the type to
2756   // be an lvalue, e.g. taking the address of a subscript of an expression of
2757   // type "void *".
2758   bool IsGLValueLike = A->isGLValue() ||
2759     (A->getType().isCForbiddenLValueType() && !AMgr.getLangOpts().CPlusPlus);
2760
2761   for (auto *Node : CheckerPreStmt) {
2762     const LocationContext *LCtx = Node->getLocationContext();
2763     ProgramStateRef state = Node->getState();
2764
2765     if (IsGLValueLike) {
2766       QualType T = A->getType();
2767
2768       // One of the forbidden LValue types! We still need to have sensible
2769       // symbolic locations to represent this stuff. Note that arithmetic on
2770       // void pointers is a GCC extension.
2771       if (T->isVoidType())
2772         T = getContext().CharTy;
2773
2774       SVal V = state->getLValue(T,
2775                                 state->getSVal(Idx, LCtx),
2776                                 state->getSVal(Base, LCtx));
2777       Bldr.generateNode(A, Node, state->BindExpr(A, LCtx, V), nullptr,
2778           ProgramPoint::PostLValueKind);
2779     } else if (IsVectorType) {
2780       // FIXME: non-glvalue vector reads are not modelled.
2781       Bldr.generateNode(A, Node, state, nullptr);
2782     } else {
2783       llvm_unreachable("Array subscript should be an lValue when not \
2784 a vector and not a forbidden lvalue type");
2785     }
2786   }
2787
2788   getCheckerManager().runCheckersForPostStmt(Dst, EvalSet, A, *this);
2789 }
2790
2791 /// VisitMemberExpr - Transfer function for member expressions.
2792 void ExprEngine::VisitMemberExpr(const MemberExpr *M, ExplodedNode *Pred,
2793                                  ExplodedNodeSet &Dst) {
2794   // FIXME: Prechecks eventually go in ::Visit().
2795   ExplodedNodeSet CheckedSet;
2796   getCheckerManager().runCheckersForPreStmt(CheckedSet, Pred, M, *this);
2797
2798   ExplodedNodeSet EvalSet;
2799   ValueDecl *Member = M->getMemberDecl();
2800
2801   // Handle static member variables and enum constants accessed via
2802   // member syntax.
2803   if (isa<VarDecl, EnumConstantDecl>(Member)) {
2804     for (const auto I : CheckedSet)
2805       VisitCommonDeclRefExpr(M, Member, I, EvalSet);
2806   } else {
2807     StmtNodeBuilder Bldr(CheckedSet, EvalSet, *currBldrCtx);
2808     ExplodedNodeSet Tmp;
2809
2810     for (const auto I : CheckedSet) {
2811       ProgramStateRef state = I->getState();
2812       const LocationContext *LCtx = I->getLocationContext();
2813       Expr *BaseExpr = M->getBase();
2814
2815       // Handle C++ method calls.
2816       if (const auto *MD = dyn_cast<CXXMethodDecl>(Member)) {
2817         if (MD->isInstance())
2818           state = createTemporaryRegionIfNeeded(state, LCtx, BaseExpr);
2819
2820         SVal MDVal = svalBuilder.getFunctionPointer(MD);
2821         state = state->BindExpr(M, LCtx, MDVal);
2822
2823         Bldr.generateNode(M, I, state);
2824         continue;
2825       }
2826
2827       // Handle regular struct fields / member variables.
2828       const SubRegion *MR = nullptr;
2829       state = createTemporaryRegionIfNeeded(state, LCtx, BaseExpr,
2830                                             /*Result=*/nullptr,
2831                                             /*OutRegionWithAdjustments=*/&MR);
2832       SVal baseExprVal =
2833           MR ? loc::MemRegionVal(MR) : state->getSVal(BaseExpr, LCtx);
2834
2835       const auto *field = cast<FieldDecl>(Member);
2836       SVal L = state->getLValue(field, baseExprVal);
2837
2838       if (M->isGLValue() || M->getType()->isArrayType()) {
2839         // We special-case rvalues of array type because the analyzer cannot
2840         // reason about them, since we expect all regions to be wrapped in Locs.
2841         // We instead treat these as lvalues and assume that they will decay to
2842         // pointers as soon as they are used.
2843         if (!M->isGLValue()) {
2844           assert(M->getType()->isArrayType());
2845           const auto *PE =
2846             dyn_cast<ImplicitCastExpr>(I->getParentMap().getParentIgnoreParens(M));
2847           if (!PE || PE->getCastKind() != CK_ArrayToPointerDecay) {
2848             llvm_unreachable("should always be wrapped in ArrayToPointerDecay");
2849           }
2850         }
2851
2852         if (field->getType()->isReferenceType()) {
2853           if (const MemRegion *R = L.getAsRegion())
2854             L = state->getSVal(R);
2855           else
2856             L = UnknownVal();
2857         }
2858
2859         Bldr.generateNode(M, I, state->BindExpr(M, LCtx, L), nullptr,
2860                           ProgramPoint::PostLValueKind);
2861       } else {
2862         Bldr.takeNodes(I);
2863         evalLoad(Tmp, M, M, I, state, L);
2864         Bldr.addNodes(Tmp);
2865       }
2866     }
2867   }
2868
2869   getCheckerManager().runCheckersForPostStmt(Dst, EvalSet, M, *this);
2870 }
2871
2872 void ExprEngine::VisitAtomicExpr(const AtomicExpr *AE, ExplodedNode *Pred,
2873                                  ExplodedNodeSet &Dst) {
2874   ExplodedNodeSet AfterPreSet;
2875   getCheckerManager().runCheckersForPreStmt(AfterPreSet, Pred, AE, *this);
2876
2877   // For now, treat all the arguments to C11 atomics as escaping.
2878   // FIXME: Ideally we should model the behavior of the atomics precisely here.
2879
2880   ExplodedNodeSet AfterInvalidateSet;
2881   StmtNodeBuilder Bldr(AfterPreSet, AfterInvalidateSet, *currBldrCtx);
2882
2883   for (const auto I : AfterPreSet) {
2884     ProgramStateRef State = I->getState();
2885     const LocationContext *LCtx = I->getLocationContext();
2886
2887     SmallVector<SVal, 8> ValuesToInvalidate;
2888     for (unsigned SI = 0, Count = AE->getNumSubExprs(); SI != Count; SI++) {
2889       const Expr *SubExpr = AE->getSubExprs()[SI];
2890       SVal SubExprVal = State->getSVal(SubExpr, LCtx);
2891       ValuesToInvalidate.push_back(SubExprVal);
2892     }
2893
2894     State = State->invalidateRegions(ValuesToInvalidate, AE,
2895                                     currBldrCtx->blockCount(),
2896                                     LCtx,
2897                                     /*CausedByPointerEscape*/true,
2898                                     /*Symbols=*/nullptr);
2899
2900     SVal ResultVal = UnknownVal();
2901     State = State->BindExpr(AE, LCtx, ResultVal);
2902     Bldr.generateNode(AE, I, State, nullptr,
2903                       ProgramPoint::PostStmtKind);
2904   }
2905
2906   getCheckerManager().runCheckersForPostStmt(Dst, AfterInvalidateSet, AE, *this);
2907 }
2908
2909 // A value escapes in four possible cases:
2910 // (1) We are binding to something that is not a memory region.
2911 // (2) We are binding to a MemRegion that does not have stack storage.
2912 // (3) We are binding to a top-level parameter region with a non-trivial
2913 //     destructor. We won't see the destructor during analysis, but it's there.
2914 // (4) We are binding to a MemRegion with stack storage that the store
2915 //     does not understand.
2916 ProgramStateRef ExprEngine::processPointerEscapedOnBind(
2917     ProgramStateRef State, ArrayRef<std::pair<SVal, SVal>> LocAndVals,
2918     const LocationContext *LCtx, PointerEscapeKind Kind,
2919     const CallEvent *Call) {
2920   SmallVector<SVal, 8> Escaped;
2921   for (const std::pair<SVal, SVal> &LocAndVal : LocAndVals) {
2922     // Cases (1) and (2).
2923     const MemRegion *MR = LocAndVal.first.getAsRegion();
2924     if (!MR || !MR->hasStackStorage()) {
2925       Escaped.push_back(LocAndVal.second);
2926       continue;
2927     }
2928
2929     // Case (3).
2930     if (const auto *VR = dyn_cast<VarRegion>(MR->getBaseRegion()))
2931       if (VR->hasStackParametersStorage() && VR->getStackFrame()->inTopFrame())
2932         if (const auto *RD = VR->getValueType()->getAsCXXRecordDecl())
2933           if (!RD->hasTrivialDestructor()) {
2934             Escaped.push_back(LocAndVal.second);
2935             continue;
2936           }
2937
2938     // Case (4): in order to test that, generate a new state with the binding
2939     // added. If it is the same state, then it escapes (since the store cannot
2940     // represent the binding).
2941     // Do this only if we know that the store is not supposed to generate the
2942     // same state.
2943     SVal StoredVal = State->getSVal(MR);
2944     if (StoredVal != LocAndVal.second)
2945       if (State ==
2946           (State->bindLoc(loc::MemRegionVal(MR), LocAndVal.second, LCtx)))
2947         Escaped.push_back(LocAndVal.second);
2948   }
2949
2950   if (Escaped.empty())
2951     return State;
2952
2953   return escapeValues(State, Escaped, Kind, Call);
2954 }
2955
2956 ProgramStateRef
2957 ExprEngine::processPointerEscapedOnBind(ProgramStateRef State, SVal Loc,
2958                                         SVal Val, const LocationContext *LCtx) {
2959   std::pair<SVal, SVal> LocAndVal(Loc, Val);
2960   return processPointerEscapedOnBind(State, LocAndVal, LCtx, PSK_EscapeOnBind,
2961                                      nullptr);
2962 }
2963
2964 ProgramStateRef
2965 ExprEngine::notifyCheckersOfPointerEscape(ProgramStateRef State,
2966     const InvalidatedSymbols *Invalidated,
2967     ArrayRef<const MemRegion *> ExplicitRegions,
2968     const CallEvent *Call,
2969     RegionAndSymbolInvalidationTraits &ITraits) {
2970   if (!Invalidated || Invalidated->empty())
2971     return State;
2972
2973   if (!Call)
2974     return getCheckerManager().runCheckersForPointerEscape(State,
2975                                                            *Invalidated,
2976                                                            nullptr,
2977                                                            PSK_EscapeOther,
2978                                                            &ITraits);
2979
2980   // If the symbols were invalidated by a call, we want to find out which ones
2981   // were invalidated directly due to being arguments to the call.
2982   InvalidatedSymbols SymbolsDirectlyInvalidated;
2983   for (const auto I : ExplicitRegions) {
2984     if (const SymbolicRegion *R = I->StripCasts()->getAs<SymbolicRegion>())
2985       SymbolsDirectlyInvalidated.insert(R->getSymbol());
2986   }
2987
2988   InvalidatedSymbols SymbolsIndirectlyInvalidated;
2989   for (const auto &sym : *Invalidated) {
2990     if (SymbolsDirectlyInvalidated.count(sym))
2991       continue;
2992     SymbolsIndirectlyInvalidated.insert(sym);
2993   }
2994
2995   if (!SymbolsDirectlyInvalidated.empty())
2996     State = getCheckerManager().runCheckersForPointerEscape(State,
2997         SymbolsDirectlyInvalidated, Call, PSK_DirectEscapeOnCall, &ITraits);
2998
2999   // Notify about the symbols that get indirectly invalidated by the call.
3000   if (!SymbolsIndirectlyInvalidated.empty())
3001     State = getCheckerManager().runCheckersForPointerEscape(State,
3002         SymbolsIndirectlyInvalidated, Call, PSK_IndirectEscapeOnCall, &ITraits);
3003
3004   return State;
3005 }
3006
3007 /// evalBind - Handle the semantics of binding a value to a specific location.
3008 ///  This method is used by evalStore and (soon) VisitDeclStmt, and others.
3009 void ExprEngine::evalBind(ExplodedNodeSet &Dst, const Stmt *StoreE,
3010                           ExplodedNode *Pred,
3011                           SVal location, SVal Val,
3012                           bool atDeclInit, const ProgramPoint *PP) {
3013   const LocationContext *LC = Pred->getLocationContext();
3014   PostStmt PS(StoreE, LC);
3015   if (!PP)
3016     PP = &PS;
3017
3018   // Do a previsit of the bind.
3019   ExplodedNodeSet CheckedSet;
3020   getCheckerManager().runCheckersForBind(CheckedSet, Pred, location, Val,
3021                                          StoreE, *this, *PP);
3022
3023   StmtNodeBuilder Bldr(CheckedSet, Dst, *currBldrCtx);
3024
3025   // If the location is not a 'Loc', it will already be handled by
3026   // the checkers.  There is nothing left to do.
3027   if (!isa<Loc>(location)) {
3028     const ProgramPoint L = PostStore(StoreE, LC, /*Loc*/nullptr,
3029                                      /*tag*/nullptr);
3030     ProgramStateRef state = Pred->getState();
3031     state = processPointerEscapedOnBind(state, location, Val, LC);
3032     Bldr.generateNode(L, state, Pred);
3033     return;
3034   }
3035
3036   for (const auto PredI : CheckedSet) {
3037     ProgramStateRef state = PredI->getState();
3038
3039     state = processPointerEscapedOnBind(state, location, Val, LC);
3040
3041     // When binding the value, pass on the hint that this is a initialization.
3042     // For initializations, we do not need to inform clients of region
3043     // changes.
3044     state = state->bindLoc(location.castAs<Loc>(),
3045                            Val, LC, /* notifyChanges = */ !atDeclInit);
3046
3047     const MemRegion *LocReg = nullptr;
3048     if (Optional<loc::MemRegionVal> LocRegVal =
3049             location.getAs<loc::MemRegionVal>()) {
3050       LocReg = LocRegVal->getRegion();
3051     }
3052
3053     const ProgramPoint L = PostStore(StoreE, LC, LocReg, nullptr);
3054     Bldr.generateNode(L, state, PredI);
3055   }
3056 }
3057
3058 /// evalStore - Handle the semantics of a store via an assignment.
3059 ///  @param Dst The node set to store generated state nodes
3060 ///  @param AssignE The assignment expression if the store happens in an
3061 ///         assignment.
3062 ///  @param LocationE The location expression that is stored to.
3063 ///  @param state The current simulation state
3064 ///  @param location The location to store the value
3065 ///  @param Val The value to be stored
3066 void ExprEngine::evalStore(ExplodedNodeSet &Dst, const Expr *AssignE,
3067                              const Expr *LocationE,
3068                              ExplodedNode *Pred,
3069                              ProgramStateRef state, SVal location, SVal Val,
3070                              const ProgramPointTag *tag) {
3071   // Proceed with the store.  We use AssignE as the anchor for the PostStore
3072   // ProgramPoint if it is non-NULL, and LocationE otherwise.
3073   const Expr *StoreE = AssignE ? AssignE : LocationE;
3074
3075   // Evaluate the location (checks for bad dereferences).
3076   ExplodedNodeSet Tmp;
3077   evalLocation(Tmp, AssignE, LocationE, Pred, state, location, false);
3078
3079   if (Tmp.empty())
3080     return;
3081
3082   if (location.isUndef())
3083     return;
3084
3085   for (const auto I : Tmp)
3086     evalBind(Dst, StoreE, I, location, Val, false);
3087 }
3088
3089 void ExprEngine::evalLoad(ExplodedNodeSet &Dst,
3090                           const Expr *NodeEx,
3091                           const Expr *BoundEx,
3092                           ExplodedNode *Pred,
3093                           ProgramStateRef state,
3094                           SVal location,
3095                           const ProgramPointTag *tag,
3096                           QualType LoadTy) {
3097   assert(!isa<NonLoc>(location) && "location cannot be a NonLoc.");
3098   assert(NodeEx);
3099   assert(BoundEx);
3100   // Evaluate the location (checks for bad dereferences).
3101   ExplodedNodeSet Tmp;
3102   evalLocation(Tmp, NodeEx, BoundEx, Pred, state, location, true);
3103   if (Tmp.empty())
3104     return;
3105
3106   StmtNodeBuilder Bldr(Tmp, Dst, *currBldrCtx);
3107   if (location.isUndef())
3108     return;
3109
3110   // Proceed with the load.
3111   for (const auto I : Tmp) {
3112     state = I->getState();
3113     const LocationContext *LCtx = I->getLocationContext();
3114
3115     SVal V = UnknownVal();
3116     if (location.isValid()) {
3117       if (LoadTy.isNull())
3118         LoadTy = BoundEx->getType();
3119       V = state->getSVal(location.castAs<Loc>(), LoadTy);
3120     }
3121
3122     Bldr.generateNode(NodeEx, I, state->BindExpr(BoundEx, LCtx, V), tag,
3123                       ProgramPoint::PostLoadKind);
3124   }
3125 }
3126
3127 void ExprEngine::evalLocation(ExplodedNodeSet &Dst,
3128                               const Stmt *NodeEx,
3129                               const Stmt *BoundEx,
3130                               ExplodedNode *Pred,
3131                               ProgramStateRef state,
3132                               SVal location,
3133                               bool isLoad) {
3134   StmtNodeBuilder BldrTop(Pred, Dst, *currBldrCtx);
3135   // Early checks for performance reason.
3136   if (location.isUnknown()) {
3137     return;
3138   }
3139
3140   ExplodedNodeSet Src;
3141   BldrTop.takeNodes(Pred);
3142   StmtNodeBuilder Bldr(Pred, Src, *currBldrCtx);
3143   if (Pred->getState() != state) {
3144     // Associate this new state with an ExplodedNode.
3145     // FIXME: If I pass null tag, the graph is incorrect, e.g for
3146     //   int *p;
3147     //   p = 0;
3148     //   *p = 0xDEADBEEF;
3149     // "p = 0" is not noted as "Null pointer value stored to 'p'" but
3150     // instead "int *p" is noted as
3151     // "Variable 'p' initialized to a null pointer value"
3152
3153     static SimpleProgramPointTag tag(TagProviderName, "Location");
3154     Bldr.generateNode(NodeEx, Pred, state, &tag);
3155   }
3156   ExplodedNodeSet Tmp;
3157   getCheckerManager().runCheckersForLocation(Tmp, Src, location, isLoad,
3158                                              NodeEx, BoundEx, *this);
3159   BldrTop.addNodes(Tmp);
3160 }
3161
3162 std::pair<const ProgramPointTag *, const ProgramPointTag*>
3163 ExprEngine::geteagerlyAssumeBinOpBifurcationTags() {
3164   static SimpleProgramPointTag
3165          eagerlyAssumeBinOpBifurcationTrue(TagProviderName,
3166                                            "Eagerly Assume True"),
3167          eagerlyAssumeBinOpBifurcationFalse(TagProviderName,
3168                                             "Eagerly Assume False");
3169   return std::make_pair(&eagerlyAssumeBinOpBifurcationTrue,
3170                         &eagerlyAssumeBinOpBifurcationFalse);
3171 }
3172
3173 void ExprEngine::evalEagerlyAssumeBinOpBifurcation(ExplodedNodeSet &Dst,
3174                                                    ExplodedNodeSet &Src,
3175                                                    const Expr *Ex) {
3176   StmtNodeBuilder Bldr(Src, Dst, *currBldrCtx);
3177
3178   for (const auto Pred : Src) {
3179     // Test if the previous node was as the same expression.  This can happen
3180     // when the expression fails to evaluate to anything meaningful and
3181     // (as an optimization) we don't generate a node.
3182     ProgramPoint P = Pred->getLocation();
3183     if (!P.getAs<PostStmt>() || P.castAs<PostStmt>().getStmt() != Ex) {
3184       continue;
3185     }
3186
3187     ProgramStateRef state = Pred->getState();
3188     SVal V = state->getSVal(Ex, Pred->getLocationContext());
3189     Optional<nonloc::SymbolVal> SEV = V.getAs<nonloc::SymbolVal>();
3190     if (SEV && SEV->isExpression()) {
3191       const std::pair<const ProgramPointTag *, const ProgramPointTag*> &tags =
3192         geteagerlyAssumeBinOpBifurcationTags();
3193
3194       ProgramStateRef StateTrue, StateFalse;
3195       std::tie(StateTrue, StateFalse) = state->assume(*SEV);
3196
3197       // First assume that the condition is true.
3198       if (StateTrue) {
3199         SVal Val = svalBuilder.makeIntVal(1U, Ex->getType());
3200         StateTrue = StateTrue->BindExpr(Ex, Pred->getLocationContext(), Val);
3201         Bldr.generateNode(Ex, Pred, StateTrue, tags.first);
3202       }
3203
3204       // Next, assume that the condition is false.
3205       if (StateFalse) {
3206         SVal Val = svalBuilder.makeIntVal(0U, Ex->getType());
3207         StateFalse = StateFalse->BindExpr(Ex, Pred->getLocationContext(), Val);
3208         Bldr.generateNode(Ex, Pred, StateFalse, tags.second);
3209       }
3210     }
3211   }
3212 }
3213
3214 void ExprEngine::VisitGCCAsmStmt(const GCCAsmStmt *A, ExplodedNode *Pred,
3215                                  ExplodedNodeSet &Dst) {
3216   StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
3217   // We have processed both the inputs and the outputs.  All of the outputs
3218   // should evaluate to Locs.  Nuke all of their values.
3219
3220   // FIXME: Some day in the future it would be nice to allow a "plug-in"
3221   // which interprets the inline asm and stores proper results in the
3222   // outputs.
3223
3224   ProgramStateRef state = Pred->getState();
3225
3226   for (const Expr *O : A->outputs()) {
3227     SVal X = state->getSVal(O, Pred->getLocationContext());
3228     assert(!isa<NonLoc>(X)); // Should be an Lval, or unknown, undef.
3229
3230     if (Optional<Loc> LV = X.getAs<Loc>())
3231       state = state->bindLoc(*LV, UnknownVal(), Pred->getLocationContext());
3232   }
3233
3234   Bldr.generateNode(A, Pred, state);
3235 }
3236
3237 void ExprEngine::VisitMSAsmStmt(const MSAsmStmt *A, ExplodedNode *Pred,
3238                                 ExplodedNodeSet &Dst) {
3239   StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
3240   Bldr.generateNode(A, Pred, Pred->getState());
3241 }
3242
3243 //===----------------------------------------------------------------------===//
3244 // Visualization.
3245 //===----------------------------------------------------------------------===//
3246
3247 namespace llvm {
3248
3249 template<>
3250 struct DOTGraphTraits<ExplodedGraph*> : public DefaultDOTGraphTraits {
3251   DOTGraphTraits (bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
3252
3253   static bool nodeHasBugReport(const ExplodedNode *N) {
3254     BugReporter &BR = static_cast<ExprEngine &>(
3255       N->getState()->getStateManager().getOwningEngine()).getBugReporter();
3256
3257     const auto EQClasses =
3258         llvm::make_range(BR.EQClasses_begin(), BR.EQClasses_end());
3259
3260     for (const auto &EQ : EQClasses) {
3261       for (const auto &I : EQ.getReports()) {
3262         const auto *PR = dyn_cast<PathSensitiveBugReport>(I.get());
3263         if (!PR)
3264           continue;
3265         const ExplodedNode *EN = PR->getErrorNode();
3266         if (EN->getState() == N->getState() &&
3267             EN->getLocation() == N->getLocation())
3268           return true;
3269       }
3270     }
3271     return false;
3272   }
3273
3274   /// \p PreCallback: callback before break.
3275   /// \p PostCallback: callback after break.
3276   /// \p Stop: stop iteration if returns @c true
3277   /// \return Whether @c Stop ever returned @c true.
3278   static bool traverseHiddenNodes(
3279       const ExplodedNode *N,
3280       llvm::function_ref<void(const ExplodedNode *)> PreCallback,
3281       llvm::function_ref<void(const ExplodedNode *)> PostCallback,
3282       llvm::function_ref<bool(const ExplodedNode *)> Stop) {
3283     while (true) {
3284       PreCallback(N);
3285       if (Stop(N))
3286         return true;
3287
3288       if (N->succ_size() != 1 || !isNodeHidden(N->getFirstSucc(), nullptr))
3289         break;
3290       PostCallback(N);
3291
3292       N = N->getFirstSucc();
3293     }
3294     return false;
3295   }
3296
3297   static bool isNodeHidden(const ExplodedNode *N, const ExplodedGraph *G) {
3298     return N->isTrivial();
3299   }
3300
3301   static std::string getNodeLabel(const ExplodedNode *N, ExplodedGraph *G){
3302     std::string Buf;
3303     llvm::raw_string_ostream Out(Buf);
3304
3305     const bool IsDot = true;
3306     const unsigned int Space = 1;
3307     ProgramStateRef State = N->getState();
3308
3309     Out << "{ \"state_id\": " << State->getID()
3310         << ",\\l";
3311
3312     Indent(Out, Space, IsDot) << "\"program_points\": [\\l";
3313
3314     // Dump program point for all the previously skipped nodes.
3315     traverseHiddenNodes(
3316         N,
3317         [&](const ExplodedNode *OtherNode) {
3318           Indent(Out, Space + 1, IsDot) << "{ ";
3319           OtherNode->getLocation().printJson(Out, /*NL=*/"\\l");
3320           Out << ", \"tag\": ";
3321           if (const ProgramPointTag *Tag = OtherNode->getLocation().getTag())
3322             Out << '\"' << Tag->getTagDescription() << "\"";
3323           else
3324             Out << "null";
3325           Out << ", \"node_id\": " << OtherNode->getID() <<
3326                  ", \"is_sink\": " << OtherNode->isSink() <<
3327                  ", \"has_report\": " << nodeHasBugReport(OtherNode) << " }";
3328         },
3329         // Adds a comma and a new-line between each program point.
3330         [&](const ExplodedNode *) { Out << ",\\l"; },
3331         [&](const ExplodedNode *) { return false; });
3332
3333     Out << "\\l"; // Adds a new-line to the last program point.
3334     Indent(Out, Space, IsDot) << "],\\l";
3335
3336     State->printDOT(Out, N->getLocationContext(), Space);
3337
3338     Out << "\\l}\\l";
3339     return Out.str();
3340   }
3341 };
3342
3343 } // namespace llvm
3344
3345 void ExprEngine::ViewGraph(bool trim) {
3346   std::string Filename = DumpGraph(trim);
3347   llvm::DisplayGraph(Filename, false, llvm::GraphProgram::DOT);
3348 }
3349
3350 void ExprEngine::ViewGraph(ArrayRef<const ExplodedNode *> Nodes) {
3351   std::string Filename = DumpGraph(Nodes);
3352   llvm::DisplayGraph(Filename, false, llvm::GraphProgram::DOT);
3353 }
3354
3355 std::string ExprEngine::DumpGraph(bool trim, StringRef Filename) {
3356   if (trim) {
3357     std::vector<const ExplodedNode *> Src;
3358
3359     // Iterate through the reports and get their nodes.
3360     for (BugReporter::EQClasses_iterator
3361            EI = BR.EQClasses_begin(), EE = BR.EQClasses_end(); EI != EE; ++EI) {
3362       const auto *R =
3363           dyn_cast<PathSensitiveBugReport>(EI->getReports()[0].get());
3364       if (!R)
3365         continue;
3366       const auto *N = const_cast<ExplodedNode *>(R->getErrorNode());
3367       Src.push_back(N);
3368     }
3369     return DumpGraph(Src, Filename);
3370   }
3371
3372   return llvm::WriteGraph(&G, "ExprEngine", /*ShortNames=*/false,
3373                           /*Title=*/"Exploded Graph",
3374                           /*Filename=*/std::string(Filename));
3375 }
3376
3377 std::string ExprEngine::DumpGraph(ArrayRef<const ExplodedNode *> Nodes,
3378                                   StringRef Filename) {
3379   std::unique_ptr<ExplodedGraph> TrimmedG(G.trim(Nodes));
3380
3381   if (!TrimmedG.get()) {
3382     llvm::errs() << "warning: Trimmed ExplodedGraph is empty.\n";
3383     return "";
3384   }
3385
3386   return llvm::WriteGraph(TrimmedG.get(), "TrimmedExprEngine",
3387                           /*ShortNames=*/false,
3388                           /*Title=*/"Trimmed Exploded Graph",
3389                           /*Filename=*/std::string(Filename));
3390 }
3391
3392 void *ProgramStateTrait<ReplayWithoutInlining>::GDMIndex() {
3393   static int index = 0;
3394   return &index;
3395 }
3396
3397 void ExprEngine::anchor() { }