brintos / llvm-project-archived public Read only

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-exception6//7//===----------------------------------------------------------------------===//8//9//  This file defines a meta-engine for path-sensitive dataflow analysis that10//  is built on CoreEngine, but provides the boilerplate to execute transfer11//  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/Specifiers.h"42#include "clang/StaticAnalyzer/Core/AnalyzerOptions.h"43#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"44#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"45#include "clang/StaticAnalyzer/Core/CheckerManager.h"46#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"47#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"48#include "clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h"49#include "clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h"50#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicExtent.h"51#include "clang/StaticAnalyzer/Core/PathSensitive/EntryPointStats.h"52#include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"53#include "clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h"54#include "clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h"55#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"56#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"57#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"58#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h"59#include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"60#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"61#include "clang/StaticAnalyzer/Core/PathSensitive/Store.h"62#include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h"63#include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h"64#include "llvm/ADT/APSInt.h"65#include "llvm/ADT/DenseMap.h"66#include "llvm/ADT/ImmutableMap.h"67#include "llvm/ADT/ImmutableSet.h"68#include "llvm/ADT/STLExtras.h"69#include "llvm/ADT/SmallVector.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/TimeProfiler.h"76#include "llvm/Support/raw_ostream.h"77#include <cassert>78#include <cstdint>79#include <memory>80#include <optional>81#include <string>82#include <tuple>83#include <utility>84#include <vector>85 86using namespace clang;87using namespace ento;88 89#define DEBUG_TYPE "ExprEngine"90 91STAT_COUNTER(NumRemoveDeadBindings,92             "The # of times RemoveDeadBindings is called");93STAT_COUNTER(94    NumMaxBlockCountReached,95    "The # of aborted paths due to reaching the maximum block count in "96    "a top level function");97STAT_COUNTER(98    NumMaxBlockCountReachedInInlined,99    "The # of aborted paths due to reaching the maximum block count in "100    "an inlined function");101STAT_COUNTER(NumTimesRetriedWithoutInlining,102             "The # of times we re-evaluated a call without inlining");103 104//===----------------------------------------------------------------------===//105// Internal program state traits.106//===----------------------------------------------------------------------===//107 108namespace {109 110// When modeling a C++ constructor, for a variety of reasons we need to track111// the location of the object for the duration of its ConstructionContext.112// ObjectsUnderConstruction maps statements within the construction context113// to the object's location, so that on every such statement the location114// could have been retrieved.115 116/// ConstructedObjectKey is used for being able to find the path-sensitive117/// memory region of a freshly constructed object while modeling the AST node118/// that syntactically represents the object that is being constructed.119/// Semantics of such nodes may sometimes require access to the region that's120/// not otherwise present in the program state, or to the very fact that121/// the construction context was present and contained references to these122/// AST nodes.123class ConstructedObjectKey {124  using ConstructedObjectKeyImpl =125      std::pair<ConstructionContextItem, const LocationContext *>;126  const ConstructedObjectKeyImpl Impl;127 128public:129  explicit ConstructedObjectKey(const ConstructionContextItem &Item,130                       const LocationContext *LC)131      : Impl(Item, LC) {}132 133  const ConstructionContextItem &getItem() const { return Impl.first; }134  const LocationContext *getLocationContext() const { return Impl.second; }135 136  ASTContext &getASTContext() const {137    return getLocationContext()->getDecl()->getASTContext();138  }139 140  void printJson(llvm::raw_ostream &Out, PrinterHelper *Helper,141                 PrintingPolicy &PP) const {142    const Stmt *S = getItem().getStmtOrNull();143    const CXXCtorInitializer *I = nullptr;144    if (!S)145      I = getItem().getCXXCtorInitializer();146 147    if (S)148      Out << "\"stmt_id\": " << S->getID(getASTContext());149    else150      Out << "\"init_id\": " << I->getID(getASTContext());151 152    // Kind153    Out << ", \"kind\": \"" << getItem().getKindAsString()154        << "\", \"argument_index\": ";155 156    if (getItem().getKind() == ConstructionContextItem::ArgumentKind)157      Out << getItem().getIndex();158    else159      Out << "null";160 161    // Pretty-print162    Out << ", \"pretty\": ";163 164    if (S) {165      S->printJson(Out, Helper, PP, /*AddQuotes=*/true);166    } else {167      Out << '\"' << I->getAnyMember()->getDeclName() << '\"';168    }169  }170 171  void Profile(llvm::FoldingSetNodeID &ID) const {172    ID.Add(Impl.first);173    ID.AddPointer(Impl.second);174  }175 176  bool operator==(const ConstructedObjectKey &RHS) const {177    return Impl == RHS.Impl;178  }179 180  bool operator<(const ConstructedObjectKey &RHS) const {181    return Impl < RHS.Impl;182  }183};184} // namespace185 186typedef llvm::ImmutableMap<ConstructedObjectKey, SVal>187    ObjectsUnderConstructionMap;188REGISTER_TRAIT_WITH_PROGRAMSTATE(ObjectsUnderConstruction,189                                 ObjectsUnderConstructionMap)190 191// This trait is responsible for storing the index of the element that is to be192// constructed in the next iteration. As a result a CXXConstructExpr is only193// stored if it is array type. Also the index is the index of the continuous194// memory region, which is important for multi-dimensional arrays. E.g:: int195// arr[2][2]; assume arr[1][1] will be the next element under construction, so196// the index is 3.197typedef llvm::ImmutableMap<198    std::pair<const CXXConstructExpr *, const LocationContext *>, unsigned>199    IndexOfElementToConstructMap;200REGISTER_TRAIT_WITH_PROGRAMSTATE(IndexOfElementToConstruct,201                                 IndexOfElementToConstructMap)202 203// This trait is responsible for holding our pending ArrayInitLoopExprs.204// It pairs the LocationContext and the initializer CXXConstructExpr with205// the size of the array that's being copy initialized.206typedef llvm::ImmutableMap<207    std::pair<const CXXConstructExpr *, const LocationContext *>, unsigned>208    PendingInitLoopMap;209REGISTER_TRAIT_WITH_PROGRAMSTATE(PendingInitLoop, PendingInitLoopMap)210 211typedef llvm::ImmutableMap<const LocationContext *, unsigned>212    PendingArrayDestructionMap;213REGISTER_TRAIT_WITH_PROGRAMSTATE(PendingArrayDestruction,214                                 PendingArrayDestructionMap)215 216//===----------------------------------------------------------------------===//217// Engine construction and deletion.218//===----------------------------------------------------------------------===//219 220static const char* TagProviderName = "ExprEngine";221 222ExprEngine::ExprEngine(cross_tu::CrossTranslationUnitContext &CTU,223                       AnalysisManager &mgr, SetOfConstDecls *VisitedCalleesIn,224                       FunctionSummariesTy *FS, InliningModes HowToInlineIn)225    : CTU(CTU), IsCTUEnabled(mgr.getAnalyzerOptions().IsNaiveCTUEnabled),226      AMgr(mgr), AnalysisDeclContexts(mgr.getAnalysisDeclContextManager()),227      Engine(*this, FS, mgr.getAnalyzerOptions()), G(Engine.getGraph()),228      StateMgr(getContext(), mgr.getStoreManagerCreator(),229               mgr.getConstraintManagerCreator(), G.getAllocator(), this),230      SymMgr(StateMgr.getSymbolManager()), MRMgr(StateMgr.getRegionManager()),231      svalBuilder(StateMgr.getSValBuilder()), ObjCNoRet(mgr.getASTContext()),232      BR(mgr, *this), VisitedCallees(VisitedCalleesIn),233      HowToInline(HowToInlineIn) {234  unsigned TrimInterval = mgr.options.GraphTrimInterval;235  if (TrimInterval != 0) {236    // Enable eager node reclamation when constructing the ExplodedGraph.237    G.enableNodeReclamation(TrimInterval);238  }239}240 241//===----------------------------------------------------------------------===//242// Utility methods.243//===----------------------------------------------------------------------===//244 245ProgramStateRef ExprEngine::getInitialState(const LocationContext *InitLoc) {246  ProgramStateRef state = StateMgr.getInitialState(InitLoc);247  const Decl *D = InitLoc->getDecl();248 249  // Preconditions.250  // FIXME: It would be nice if we had a more general mechanism to add251  // such preconditions.  Some day.252  do {253    if (const auto *FD = dyn_cast<FunctionDecl>(D)) {254      // Precondition: the first argument of 'main' is an integer guaranteed255      //  to be > 0.256      const IdentifierInfo *II = FD->getIdentifier();257      if (!II || !(II->getName() == "main" && FD->getNumParams() > 0))258        break;259 260      const ParmVarDecl *PD = FD->getParamDecl(0);261      QualType T = PD->getType();262      const auto *BT = dyn_cast<BuiltinType>(T);263      if (!BT || !BT->isInteger())264        break;265 266      const MemRegion *R = state->getRegion(PD, InitLoc);267      if (!R)268        break;269 270      SVal V = state->getSVal(loc::MemRegionVal(R));271      SVal Constraint_untested = evalBinOp(state, BO_GT, V,272                                           svalBuilder.makeZeroVal(T),273                                           svalBuilder.getConditionType());274 275      std::optional<DefinedOrUnknownSVal> Constraint =276          Constraint_untested.getAs<DefinedOrUnknownSVal>();277 278      if (!Constraint)279        break;280 281      if (ProgramStateRef newState = state->assume(*Constraint, true))282        state = newState;283    }284    break;285  }286  while (false);287 288  if (const auto *MD = dyn_cast<ObjCMethodDecl>(D)) {289    // Precondition: 'self' is always non-null upon entry to an Objective-C290    // method.291    const ImplicitParamDecl *SelfD = MD->getSelfDecl();292    const MemRegion *R = state->getRegion(SelfD, InitLoc);293    SVal V = state->getSVal(loc::MemRegionVal(R));294 295    if (std::optional<Loc> LV = V.getAs<Loc>()) {296      // Assume that the pointer value in 'self' is non-null.297      state = state->assume(*LV, true);298      assert(state && "'self' cannot be null");299    }300  }301 302  if (const auto *MD = dyn_cast<CXXMethodDecl>(D)) {303    if (MD->isImplicitObjectMemberFunction()) {304      // Precondition: 'this' is always non-null upon entry to the305      // top-level function.  This is our starting assumption for306      // analyzing an "open" program.307      const StackFrameContext *SFC = InitLoc->getStackFrame();308      if (SFC->getParent() == nullptr) {309        loc::MemRegionVal L = svalBuilder.getCXXThis(MD, SFC);310        SVal V = state->getSVal(L);311        if (std::optional<Loc> LV = V.getAs<Loc>()) {312          state = state->assume(*LV, true);313          assert(state && "'this' cannot be null");314        }315      }316    }317  }318 319  return state;320}321 322ProgramStateRef ExprEngine::createTemporaryRegionIfNeeded(323    ProgramStateRef State, const LocationContext *LC,324    const Expr *InitWithAdjustments, const Expr *Result,325    const SubRegion **OutRegionWithAdjustments) {326  // FIXME: This function is a hack that works around the quirky AST327  // we're often having with respect to C++ temporaries. If only we modelled328  // the actual execution order of statements properly in the CFG,329  // all the hassle with adjustments would not be necessary,330  // and perhaps the whole function would be removed.331  SVal InitValWithAdjustments = State->getSVal(InitWithAdjustments, LC);332  if (!Result) {333    // If we don't have an explicit result expression, we're in "if needed"334    // mode. Only create a region if the current value is a NonLoc.335    if (!isa<NonLoc>(InitValWithAdjustments)) {336      if (OutRegionWithAdjustments)337        *OutRegionWithAdjustments = nullptr;338      return State;339    }340    Result = InitWithAdjustments;341  } else {342    // We need to create a region no matter what. Make sure we don't try to343    // stuff a Loc into a non-pointer temporary region.344    assert(!isa<Loc>(InitValWithAdjustments) ||345           Loc::isLocType(Result->getType()) ||346           Result->getType()->isMemberPointerType());347  }348 349  ProgramStateManager &StateMgr = State->getStateManager();350  MemRegionManager &MRMgr = StateMgr.getRegionManager();351  StoreManager &StoreMgr = StateMgr.getStoreManager();352 353  // MaterializeTemporaryExpr may appear out of place, after a few field and354  // base-class accesses have been made to the object, even though semantically355  // it is the whole object that gets materialized and lifetime-extended.356  //357  // For example:358  //359  //   `-MaterializeTemporaryExpr360  //     `-MemberExpr361  //       `-CXXTemporaryObjectExpr362  //363  // instead of the more natural364  //365  //   `-MemberExpr366  //     `-MaterializeTemporaryExpr367  //       `-CXXTemporaryObjectExpr368  //369  // Use the usual methods for obtaining the expression of the base object,370  // and record the adjustments that we need to make to obtain the sub-object371  // that the whole expression 'Ex' refers to. This trick is usual,372  // in the sense that CodeGen takes a similar route.373 374  SmallVector<const Expr *, 2> CommaLHSs;375  SmallVector<SubobjectAdjustment, 2> Adjustments;376 377  const Expr *Init = InitWithAdjustments->skipRValueSubobjectAdjustments(378      CommaLHSs, Adjustments);379 380  // Take the region for Init, i.e. for the whole object. If we do not remember381  // the region in which the object originally was constructed, come up with382  // a new temporary region out of thin air and copy the contents of the object383  // (which are currently present in the Environment, because Init is an rvalue)384  // into that region. This is not correct, but it is better than nothing.385  const TypedValueRegion *TR = nullptr;386  if (const auto *MT = dyn_cast<MaterializeTemporaryExpr>(Result)) {387    if (std::optional<SVal> V = getObjectUnderConstruction(State, MT, LC)) {388      State = finishObjectConstruction(State, MT, LC);389      State = State->BindExpr(Result, LC, *V);390      return State;391    } else if (const ValueDecl *VD = MT->getExtendingDecl()) {392      StorageDuration SD = MT->getStorageDuration();393      assert(SD != SD_FullExpression);394      // If this object is bound to a reference with static storage duration, we395      // put it in a different region to prevent "address leakage" warnings.396      if (SD == SD_Static || SD == SD_Thread) {397        TR = MRMgr.getCXXStaticLifetimeExtendedObjectRegion(Init, VD);398      } else {399        TR = MRMgr.getCXXLifetimeExtendedObjectRegion(Init, VD, LC);400      }401    } else {402      assert(MT->getStorageDuration() == SD_FullExpression);403      TR = MRMgr.getCXXTempObjectRegion(Init, LC);404    }405  } else {406    TR = MRMgr.getCXXTempObjectRegion(Init, LC);407  }408 409  SVal Reg = loc::MemRegionVal(TR);410  SVal BaseReg = Reg;411 412  // Make the necessary adjustments to obtain the sub-object.413  for (const SubobjectAdjustment &Adj : llvm::reverse(Adjustments)) {414    switch (Adj.Kind) {415    case SubobjectAdjustment::DerivedToBaseAdjustment:416      Reg = StoreMgr.evalDerivedToBase(Reg, Adj.DerivedToBase.BasePath);417      break;418    case SubobjectAdjustment::FieldAdjustment:419      Reg = StoreMgr.getLValueField(Adj.Field, Reg);420      break;421    case SubobjectAdjustment::MemberPointerAdjustment:422      // FIXME: Unimplemented.423      State = State->invalidateRegions(Reg, getCFGElementRef(),424                                       currBldrCtx->blockCount(), LC, true,425                                       nullptr, nullptr, nullptr);426      return State;427    }428  }429 430  // What remains is to copy the value of the object to the new region.431  // FIXME: In other words, what we should always do is copy value of the432  // Init expression (which corresponds to the bigger object) to the whole433  // temporary region TR. However, this value is often no longer present434  // in the Environment. If it has disappeared, we instead invalidate TR.435  // Still, what we can do is assign the value of expression Ex (which436  // corresponds to the sub-object) to the TR's sub-region Reg. At least,437  // values inside Reg would be correct.438  SVal InitVal = State->getSVal(Init, LC);439  if (InitVal.isUnknown()) {440    InitVal = getSValBuilder().conjureSymbolVal(441        getCFGElementRef(), LC, Init->getType(), currBldrCtx->blockCount());442    State = State->bindLoc(BaseReg.castAs<Loc>(), InitVal, LC, false);443 444    // Then we'd need to take the value that certainly exists and bind it445    // over.446    if (InitValWithAdjustments.isUnknown()) {447      // Try to recover some path sensitivity in case we couldn't448      // compute the value.449      InitValWithAdjustments = getSValBuilder().conjureSymbolVal(450          getCFGElementRef(), LC, InitWithAdjustments->getType(),451          currBldrCtx->blockCount());452    }453    State =454        State->bindLoc(Reg.castAs<Loc>(), InitValWithAdjustments, LC, false);455  } else {456    State = State->bindLoc(BaseReg.castAs<Loc>(), InitVal, LC, false);457  }458 459  // The result expression would now point to the correct sub-region of the460  // newly created temporary region. Do this last in order to getSVal of Init461  // correctly in case (Result == Init).462  if (Result->isGLValue()) {463    State = State->BindExpr(Result, LC, Reg);464  } else {465    State = State->BindExpr(Result, LC, InitValWithAdjustments);466  }467 468  // Notify checkers once for two bindLoc()s.469  State = processRegionChange(State, TR, LC);470 471  if (OutRegionWithAdjustments)472    *OutRegionWithAdjustments = cast<SubRegion>(Reg.getAsRegion());473  return State;474}475 476ProgramStateRef ExprEngine::setIndexOfElementToConstruct(477    ProgramStateRef State, const CXXConstructExpr *E,478    const LocationContext *LCtx, unsigned Idx) {479  auto Key = std::make_pair(E, LCtx->getStackFrame());480 481  assert(!State->contains<IndexOfElementToConstruct>(Key) || Idx > 0);482 483  return State->set<IndexOfElementToConstruct>(Key, Idx);484}485 486std::optional<unsigned>487ExprEngine::getPendingInitLoop(ProgramStateRef State, const CXXConstructExpr *E,488                               const LocationContext *LCtx) {489  const unsigned *V = State->get<PendingInitLoop>({E, LCtx->getStackFrame()});490  return V ? std::make_optional(*V) : std::nullopt;491}492 493ProgramStateRef ExprEngine::removePendingInitLoop(ProgramStateRef State,494                                                  const CXXConstructExpr *E,495                                                  const LocationContext *LCtx) {496  auto Key = std::make_pair(E, LCtx->getStackFrame());497 498  assert(E && State->contains<PendingInitLoop>(Key));499  return State->remove<PendingInitLoop>(Key);500}501 502ProgramStateRef ExprEngine::setPendingInitLoop(ProgramStateRef State,503                                               const CXXConstructExpr *E,504                                               const LocationContext *LCtx,505                                               unsigned Size) {506  auto Key = std::make_pair(E, LCtx->getStackFrame());507 508  assert(!State->contains<PendingInitLoop>(Key) && Size > 0);509 510  return State->set<PendingInitLoop>(Key, Size);511}512 513std::optional<unsigned>514ExprEngine::getIndexOfElementToConstruct(ProgramStateRef State,515                                         const CXXConstructExpr *E,516                                         const LocationContext *LCtx) {517  const unsigned *V =518      State->get<IndexOfElementToConstruct>({E, LCtx->getStackFrame()});519  return V ? std::make_optional(*V) : std::nullopt;520}521 522ProgramStateRef523ExprEngine::removeIndexOfElementToConstruct(ProgramStateRef State,524                                            const CXXConstructExpr *E,525                                            const LocationContext *LCtx) {526  auto Key = std::make_pair(E, LCtx->getStackFrame());527 528  assert(E && State->contains<IndexOfElementToConstruct>(Key));529  return State->remove<IndexOfElementToConstruct>(Key);530}531 532std::optional<unsigned>533ExprEngine::getPendingArrayDestruction(ProgramStateRef State,534                                       const LocationContext *LCtx) {535  assert(LCtx && "LocationContext shouldn't be null!");536 537  const unsigned *V =538      State->get<PendingArrayDestruction>(LCtx->getStackFrame());539  return V ? std::make_optional(*V) : std::nullopt;540}541 542ProgramStateRef ExprEngine::setPendingArrayDestruction(543    ProgramStateRef State, const LocationContext *LCtx, unsigned Idx) {544  assert(LCtx && "LocationContext shouldn't be null!");545 546  auto Key = LCtx->getStackFrame();547 548  return State->set<PendingArrayDestruction>(Key, Idx);549}550 551ProgramStateRef552ExprEngine::removePendingArrayDestruction(ProgramStateRef State,553                                          const LocationContext *LCtx) {554  assert(LCtx && "LocationContext shouldn't be null!");555 556  auto Key = LCtx->getStackFrame();557 558  assert(LCtx && State->contains<PendingArrayDestruction>(Key));559  return State->remove<PendingArrayDestruction>(Key);560}561 562ProgramStateRef563ExprEngine::addObjectUnderConstruction(ProgramStateRef State,564                                       const ConstructionContextItem &Item,565                                       const LocationContext *LC, SVal V) {566  ConstructedObjectKey Key(Item, LC->getStackFrame());567 568  const Expr *Init = nullptr;569 570  if (auto DS = dyn_cast_or_null<DeclStmt>(Item.getStmtOrNull())) {571    if (auto VD = dyn_cast_or_null<VarDecl>(DS->getSingleDecl()))572      Init = VD->getInit();573  }574 575  if (auto LE = dyn_cast_or_null<LambdaExpr>(Item.getStmtOrNull()))576    Init = *(LE->capture_init_begin() + Item.getIndex());577 578  if (!Init && !Item.getStmtOrNull())579    Init = Item.getCXXCtorInitializer()->getInit();580 581  // In an ArrayInitLoopExpr the real initializer is returned by582  // getSubExpr(). Note that AILEs can be nested in case of583  // multidimesnional arrays.584  if (const auto *AILE = dyn_cast_or_null<ArrayInitLoopExpr>(Init))585    Init = extractElementInitializerFromNestedAILE(AILE);586 587  // FIXME: Currently the state might already contain the marker due to588  // incorrect handling of temporaries bound to default parameters.589  // The state will already contain the marker if we construct elements590  // in an array, as we visit the same statement multiple times before591  // the array declaration. The marker is removed when we exit the592  // constructor call.593  assert((!State->get<ObjectsUnderConstruction>(Key) ||594          Key.getItem().getKind() ==595              ConstructionContextItem::TemporaryDestructorKind ||596          State->contains<IndexOfElementToConstruct>(597              {dyn_cast_or_null<CXXConstructExpr>(Init), LC})) &&598         "The object is already marked as `UnderConstruction`, when it's not "599         "supposed to!");600  return State->set<ObjectsUnderConstruction>(Key, V);601}602 603std::optional<SVal>604ExprEngine::getObjectUnderConstruction(ProgramStateRef State,605                                       const ConstructionContextItem &Item,606                                       const LocationContext *LC) {607  ConstructedObjectKey Key(Item, LC->getStackFrame());608  const SVal *V = State->get<ObjectsUnderConstruction>(Key);609  return V ? std::make_optional(*V) : std::nullopt;610}611 612ProgramStateRef613ExprEngine::finishObjectConstruction(ProgramStateRef State,614                                     const ConstructionContextItem &Item,615                                     const LocationContext *LC) {616  ConstructedObjectKey Key(Item, LC->getStackFrame());617  assert(State->contains<ObjectsUnderConstruction>(Key));618  return State->remove<ObjectsUnderConstruction>(Key);619}620 621ProgramStateRef ExprEngine::elideDestructor(ProgramStateRef State,622                                            const CXXBindTemporaryExpr *BTE,623                                            const LocationContext *LC) {624  ConstructedObjectKey Key({BTE, /*IsElided=*/true}, LC);625  // FIXME: Currently the state might already contain the marker due to626  // incorrect handling of temporaries bound to default parameters.627  return State->set<ObjectsUnderConstruction>(Key, UnknownVal());628}629 630ProgramStateRef631ExprEngine::cleanupElidedDestructor(ProgramStateRef State,632                                    const CXXBindTemporaryExpr *BTE,633                                    const LocationContext *LC) {634  ConstructedObjectKey Key({BTE, /*IsElided=*/true}, LC);635  assert(State->contains<ObjectsUnderConstruction>(Key));636  return State->remove<ObjectsUnderConstruction>(Key);637}638 639bool ExprEngine::isDestructorElided(ProgramStateRef State,640                                    const CXXBindTemporaryExpr *BTE,641                                    const LocationContext *LC) {642  ConstructedObjectKey Key({BTE, /*IsElided=*/true}, LC);643  return State->contains<ObjectsUnderConstruction>(Key);644}645 646bool ExprEngine::areAllObjectsFullyConstructed(ProgramStateRef State,647                                               const LocationContext *FromLC,648                                               const LocationContext *ToLC) {649  const LocationContext *LC = FromLC;650  while (LC != ToLC) {651    assert(LC && "ToLC must be a parent of FromLC!");652    for (auto I : State->get<ObjectsUnderConstruction>())653      if (I.first.getLocationContext() == LC)654        return false;655 656    LC = LC->getParent();657  }658  return true;659}660 661 662//===----------------------------------------------------------------------===//663// Top-level transfer function logic (Dispatcher).664//===----------------------------------------------------------------------===//665 666/// evalAssume - Called by ConstraintManager. Used to call checker-specific667///  logic for handling assumptions on symbolic values.668ProgramStateRef ExprEngine::processAssume(ProgramStateRef state,669                                              SVal cond, bool assumption) {670  return getCheckerManager().runCheckersForEvalAssume(state, cond, assumption);671}672 673ProgramStateRef674ExprEngine::processRegionChanges(ProgramStateRef state,675                                 const InvalidatedSymbols *invalidated,676                                 ArrayRef<const MemRegion *> Explicits,677                                 ArrayRef<const MemRegion *> Regions,678                                 const LocationContext *LCtx,679                                 const CallEvent *Call) {680  return getCheckerManager().runCheckersForRegionChanges(state, invalidated,681                                                         Explicits, Regions,682                                                         LCtx, Call);683}684 685static void686printObjectsUnderConstructionJson(raw_ostream &Out, ProgramStateRef State,687                                  const char *NL, const LocationContext *LCtx,688                                  unsigned int Space = 0, bool IsDot = false) {689  PrintingPolicy PP =690      LCtx->getAnalysisDeclContext()->getASTContext().getPrintingPolicy();691 692  ++Space;693  bool HasItem = false;694 695  // Store the last key.696  const ConstructedObjectKey *LastKey = nullptr;697  for (const auto &I : State->get<ObjectsUnderConstruction>()) {698    const ConstructedObjectKey &Key = I.first;699    if (Key.getLocationContext() != LCtx)700      continue;701 702    if (!HasItem) {703      Out << '[' << NL;704      HasItem = true;705    }706 707    LastKey = &Key;708  }709 710  for (const auto &I : State->get<ObjectsUnderConstruction>()) {711    const ConstructedObjectKey &Key = I.first;712    SVal Value = I.second;713    if (Key.getLocationContext() != LCtx)714      continue;715 716    Indent(Out, Space, IsDot) << "{ ";717    Key.printJson(Out, nullptr, PP);718    Out << ", \"value\": \"" << Value << "\" }";719 720    if (&Key != LastKey)721      Out << ',';722    Out << NL;723  }724 725  if (HasItem)726    Indent(Out, --Space, IsDot) << ']'; // End of "location_context".727  else {728    Out << "null ";729  }730}731 732static void printIndicesOfElementsToConstructJson(733    raw_ostream &Out, ProgramStateRef State, const char *NL,734    const LocationContext *LCtx, unsigned int Space = 0, bool IsDot = false) {735  using KeyT = std::pair<const Expr *, const LocationContext *>;736 737  const auto &Context = LCtx->getAnalysisDeclContext()->getASTContext();738  PrintingPolicy PP = Context.getPrintingPolicy();739 740  ++Space;741  bool HasItem = false;742 743  // Store the last key.744  KeyT LastKey;745  for (const auto &I : State->get<IndexOfElementToConstruct>()) {746    const KeyT &Key = I.first;747    if (Key.second != LCtx)748      continue;749 750    if (!HasItem) {751      Out << '[' << NL;752      HasItem = true;753    }754 755    LastKey = Key;756  }757 758  for (const auto &I : State->get<IndexOfElementToConstruct>()) {759    const KeyT &Key = I.first;760    unsigned Value = I.second;761    if (Key.second != LCtx)762      continue;763 764    Indent(Out, Space, IsDot) << "{ ";765 766    // Expr767    const Expr *E = Key.first;768    Out << "\"stmt_id\": " << E->getID(Context);769 770    // Kind771    Out << ", \"kind\": null";772 773    // Pretty-print774    Out << ", \"pretty\": ";775    Out << "\"" << E->getStmtClassName() << ' '776        << E->getSourceRange().printToString(Context.getSourceManager()) << " '"777        << QualType::getAsString(E->getType().split(), PP);778    Out << "'\"";779 780    Out << ", \"value\": \"Current index: " << Value - 1 << "\" }";781 782    if (Key != LastKey)783      Out << ',';784    Out << NL;785  }786 787  if (HasItem)788    Indent(Out, --Space, IsDot) << ']'; // End of "location_context".789  else {790    Out << "null ";791  }792}793 794static void printPendingInitLoopJson(raw_ostream &Out, ProgramStateRef State,795                                     const char *NL,796                                     const LocationContext *LCtx,797                                     unsigned int Space = 0,798                                     bool IsDot = false) {799  using KeyT = std::pair<const CXXConstructExpr *, const LocationContext *>;800 801  const auto &Context = LCtx->getAnalysisDeclContext()->getASTContext();802  PrintingPolicy PP = Context.getPrintingPolicy();803 804  ++Space;805  bool HasItem = false;806 807  // Store the last key.808  KeyT LastKey;809  for (const auto &I : State->get<PendingInitLoop>()) {810    const KeyT &Key = I.first;811    if (Key.second != LCtx)812      continue;813 814    if (!HasItem) {815      Out << '[' << NL;816      HasItem = true;817    }818 819    LastKey = Key;820  }821 822  for (const auto &I : State->get<PendingInitLoop>()) {823    const KeyT &Key = I.first;824    unsigned Value = I.second;825    if (Key.second != LCtx)826      continue;827 828    Indent(Out, Space, IsDot) << "{ ";829 830    const CXXConstructExpr *E = Key.first;831    Out << "\"stmt_id\": " << E->getID(Context);832 833    Out << ", \"kind\": null";834    Out << ", \"pretty\": ";835    Out << '\"' << E->getStmtClassName() << ' '836        << E->getSourceRange().printToString(Context.getSourceManager()) << " '"837        << QualType::getAsString(E->getType().split(), PP);838    Out << "'\"";839 840    Out << ", \"value\": \"Flattened size: " << Value << "\"}";841 842    if (Key != LastKey)843      Out << ',';844    Out << NL;845  }846 847  if (HasItem)848    Indent(Out, --Space, IsDot) << ']'; // End of "location_context".849  else {850    Out << "null ";851  }852}853 854static void855printPendingArrayDestructionsJson(raw_ostream &Out, ProgramStateRef State,856                                  const char *NL, const LocationContext *LCtx,857                                  unsigned int Space = 0, bool IsDot = false) {858  using KeyT = const LocationContext *;859 860  ++Space;861  bool HasItem = false;862 863  // Store the last key.864  KeyT LastKey = nullptr;865  for (const auto &I : State->get<PendingArrayDestruction>()) {866    const KeyT &Key = I.first;867    if (Key != LCtx)868      continue;869 870    if (!HasItem) {871      Out << '[' << NL;872      HasItem = true;873    }874 875    LastKey = Key;876  }877 878  for (const auto &I : State->get<PendingArrayDestruction>()) {879    const KeyT &Key = I.first;880    if (Key != LCtx)881      continue;882 883    Indent(Out, Space, IsDot) << "{ ";884 885    Out << "\"stmt_id\": null";886    Out << ", \"kind\": null";887    Out << ", \"pretty\": \"Current index: \"";888    Out << ", \"value\": \"" << I.second << "\" }";889 890    if (Key != LastKey)891      Out << ',';892    Out << NL;893  }894 895  if (HasItem)896    Indent(Out, --Space, IsDot) << ']'; // End of "location_context".897  else {898    Out << "null ";899  }900}901 902/// A helper function to generalize program state trait printing.903/// The function invokes Printer as 'Printer(Out, State, NL, LC, Space, IsDot,904/// std::forward<Args>(args)...)'. \n One possible type for Printer is905/// 'void()(raw_ostream &, ProgramStateRef, const char *, const LocationContext906/// *, unsigned int, bool, ...)' \n \param Trait The state trait to be printed.907/// \param Printer A void function that prints Trait.908/// \param Args An additional parameter pack that is passed to Print upon909/// invocation.910template <typename Trait, typename Printer, typename... Args>911static void printStateTraitWithLocationContextJson(912    raw_ostream &Out, ProgramStateRef State, const LocationContext *LCtx,913    const char *NL, unsigned int Space, bool IsDot,914    const char *jsonPropertyName, Printer printer, Args &&...args) {915 916  using RequiredType =917      void (*)(raw_ostream &, ProgramStateRef, const char *,918               const LocationContext *, unsigned int, bool, Args &&...);919 920  // Try to do as much compile time checking as possible.921  // FIXME: check for invocable instead of function?922  static_assert(std::is_function_v<std::remove_pointer_t<Printer>>,923                "Printer is not a function!");924  static_assert(std::is_convertible_v<Printer, RequiredType>,925                "Printer doesn't have the required type!");926 927  if (LCtx && !State->get<Trait>().isEmpty()) {928    Indent(Out, Space, IsDot) << '\"' << jsonPropertyName << "\": ";929    ++Space;930    Out << '[' << NL;931    LCtx->printJson(Out, NL, Space, IsDot, [&](const LocationContext *LC) {932      printer(Out, State, NL, LC, Space, IsDot, std::forward<Args>(args)...);933    });934 935    --Space;936    Indent(Out, Space, IsDot) << "]," << NL; // End of "jsonPropertyName".937  }938}939 940void ExprEngine::printJson(raw_ostream &Out, ProgramStateRef State,941                           const LocationContext *LCtx, const char *NL,942                           unsigned int Space, bool IsDot) const {943 944  printStateTraitWithLocationContextJson<ObjectsUnderConstruction>(945      Out, State, LCtx, NL, Space, IsDot, "constructing_objects",946      printObjectsUnderConstructionJson);947  printStateTraitWithLocationContextJson<IndexOfElementToConstruct>(948      Out, State, LCtx, NL, Space, IsDot, "index_of_element",949      printIndicesOfElementsToConstructJson);950  printStateTraitWithLocationContextJson<PendingInitLoop>(951      Out, State, LCtx, NL, Space, IsDot, "pending_init_loops",952      printPendingInitLoopJson);953  printStateTraitWithLocationContextJson<PendingArrayDestruction>(954      Out, State, LCtx, NL, Space, IsDot, "pending_destructors",955      printPendingArrayDestructionsJson);956 957  getCheckerManager().runCheckersForPrintStateJson(Out, State, NL, Space,958                                                   IsDot);959}960 961void ExprEngine::processEndWorklist() {962  // This prints the name of the top-level function if we crash.963  PrettyStackTraceLocationContext CrashInfo(getRootLocationContext());964  getCheckerManager().runCheckersForEndAnalysis(G, BR, *this);965}966 967void ExprEngine::processCFGElement(const CFGElement E, ExplodedNode *Pred,968                                   unsigned StmtIdx, NodeBuilderContext *Ctx) {969  currStmtIdx = StmtIdx;970  currBldrCtx = Ctx;971 972  switch (E.getKind()) {973    case CFGElement::Statement:974    case CFGElement::Constructor:975    case CFGElement::CXXRecordTypedCall:976      ProcessStmt(E.castAs<CFGStmt>().getStmt(), Pred);977      return;978    case CFGElement::Initializer:979      ProcessInitializer(E.castAs<CFGInitializer>(), Pred);980      return;981    case CFGElement::NewAllocator:982      ProcessNewAllocator(E.castAs<CFGNewAllocator>().getAllocatorExpr(),983                          Pred);984      return;985    case CFGElement::AutomaticObjectDtor:986    case CFGElement::DeleteDtor:987    case CFGElement::BaseDtor:988    case CFGElement::MemberDtor:989    case CFGElement::TemporaryDtor:990      ProcessImplicitDtor(E.castAs<CFGImplicitDtor>(), Pred);991      return;992    case CFGElement::LoopExit:993      ProcessLoopExit(E.castAs<CFGLoopExit>().getLoopStmt(), Pred);994      return;995    case CFGElement::LifetimeEnds:996    case CFGElement::CleanupFunction:997    case CFGElement::ScopeBegin:998    case CFGElement::ScopeEnd:999      return;1000  }1001}1002 1003static bool shouldRemoveDeadBindings(AnalysisManager &AMgr,1004                                     const Stmt *S,1005                                     const ExplodedNode *Pred,1006                                     const LocationContext *LC) {1007  // Are we never purging state values?1008  if (AMgr.options.AnalysisPurgeOpt == PurgeNone)1009    return false;1010 1011  // Is this the beginning of a basic block?1012  if (Pred->getLocation().getAs<BlockEntrance>())1013    return true;1014 1015  // Is this on a non-expression?1016  if (!isa<Expr>(S))1017    return true;1018 1019  // Run before processing a call.1020  if (CallEvent::isCallStmt(S))1021    return true;1022 1023  // Is this an expression that is consumed by another expression?  If so,1024  // postpone cleaning out the state.1025  ParentMap &PM = LC->getAnalysisDeclContext()->getParentMap();1026  return !PM.isConsumedExpr(cast<Expr>(S));1027}1028 1029void ExprEngine::removeDead(ExplodedNode *Pred, ExplodedNodeSet &Out,1030                            const Stmt *ReferenceStmt,1031                            const LocationContext *LC,1032                            const Stmt *DiagnosticStmt,1033                            ProgramPoint::Kind K) {1034  llvm::TimeTraceScope TimeScope("ExprEngine::removeDead");1035  assert((K == ProgramPoint::PreStmtPurgeDeadSymbolsKind ||1036          ReferenceStmt == nullptr || isa<ReturnStmt>(ReferenceStmt))1037          && "PostStmt is not generally supported by the SymbolReaper yet");1038  assert(LC && "Must pass the current (or expiring) LocationContext");1039 1040  if (!DiagnosticStmt) {1041    DiagnosticStmt = ReferenceStmt;1042    assert(DiagnosticStmt && "Required for clearing a LocationContext");1043  }1044 1045  NumRemoveDeadBindings++;1046  ProgramStateRef CleanedState = Pred->getState();1047 1048  // LC is the location context being destroyed, but SymbolReaper wants a1049  // location context that is still live. (If this is the top-level stack1050  // frame, this will be null.)1051  if (!ReferenceStmt) {1052    assert(K == ProgramPoint::PostStmtPurgeDeadSymbolsKind &&1053           "Use PostStmtPurgeDeadSymbolsKind for clearing a LocationContext");1054    LC = LC->getParent();1055  }1056 1057  const StackFrameContext *SFC = LC ? LC->getStackFrame() : nullptr;1058  SymbolReaper SymReaper(SFC, ReferenceStmt, SymMgr, getStoreManager());1059 1060  for (auto I : CleanedState->get<ObjectsUnderConstruction>()) {1061    if (SymbolRef Sym = I.second.getAsSymbol())1062      SymReaper.markLive(Sym);1063    if (const MemRegion *MR = I.second.getAsRegion())1064      SymReaper.markLive(MR);1065  }1066 1067  getCheckerManager().runCheckersForLiveSymbols(CleanedState, SymReaper);1068 1069  // Create a state in which dead bindings are removed from the environment1070  // and the store. TODO: The function should just return new env and store,1071  // not a new state.1072  CleanedState = StateMgr.removeDeadBindingsFromEnvironmentAndStore(1073      CleanedState, SFC, SymReaper);1074 1075  // Process any special transfer function for dead symbols.1076  // Call checkers with the non-cleaned state so that they could query the1077  // values of the soon to be dead symbols.1078  ExplodedNodeSet CheckedSet;1079  getCheckerManager().runCheckersForDeadSymbols(CheckedSet, Pred, SymReaper,1080                                                DiagnosticStmt, *this, K);1081 1082  // Extend lifetime of symbols used for dynamic extent while the parent region1083  // is live. In this way size information about memory allocations is not lost1084  // if the region remains live.1085  markAllDynamicExtentLive(CleanedState, SymReaper);1086 1087  // For each node in CheckedSet, generate CleanedNodes that have the1088  // environment, the store, and the constraints cleaned up but have the1089  // user-supplied states as the predecessors.1090  StmtNodeBuilder Bldr(CheckedSet, Out, *currBldrCtx);1091  for (const auto I : CheckedSet) {1092    ProgramStateRef CheckerState = I->getState();1093 1094    // The constraint manager has not been cleaned up yet, so clean up now.1095    CheckerState =1096        getConstraintManager().removeDeadBindings(CheckerState, SymReaper);1097 1098    assert(StateMgr.haveEqualEnvironments(CheckerState, Pred->getState()) &&1099           "Checkers are not allowed to modify the Environment as a part of "1100           "checkDeadSymbols processing.");1101    assert(StateMgr.haveEqualStores(CheckerState, Pred->getState()) &&1102           "Checkers are not allowed to modify the Store as a part of "1103           "checkDeadSymbols processing.");1104 1105    // Create a state based on CleanedState with CheckerState GDM and1106    // generate a transition to that state.1107    ProgramStateRef CleanedCheckerSt =1108        StateMgr.getPersistentStateWithGDM(CleanedState, CheckerState);1109    Bldr.generateNode(DiagnosticStmt, I, CleanedCheckerSt, cleanupNodeTag(), K);1110  }1111}1112 1113const ProgramPointTag *ExprEngine::cleanupNodeTag() {1114  static SimpleProgramPointTag cleanupTag(TagProviderName, "Clean Node");1115  return &cleanupTag;1116}1117 1118void ExprEngine::ProcessStmt(const Stmt *currStmt, ExplodedNode *Pred) {1119  // Reclaim any unnecessary nodes in the ExplodedGraph.1120  G.reclaimRecentlyAllocatedNodes();1121 1122  PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),1123                                currStmt->getBeginLoc(),1124                                "Error evaluating statement");1125 1126  // Remove dead bindings and symbols.1127  ExplodedNodeSet CleanedStates;1128  if (shouldRemoveDeadBindings(AMgr, currStmt, Pred,1129                               Pred->getLocationContext())) {1130    removeDead(Pred, CleanedStates, currStmt,1131                                    Pred->getLocationContext());1132  } else1133    CleanedStates.Add(Pred);1134 1135  // Visit the statement.1136  ExplodedNodeSet Dst;1137  for (const auto I : CleanedStates) {1138    ExplodedNodeSet DstI;1139    // Visit the statement.1140    Visit(currStmt, I, DstI);1141    Dst.insert(DstI);1142  }1143 1144  // Enqueue the new nodes onto the work list.1145  Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx);1146}1147 1148void ExprEngine::ProcessLoopExit(const Stmt* S, ExplodedNode *Pred) {1149  PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),1150                                S->getBeginLoc(),1151                                "Error evaluating end of the loop");1152  ExplodedNodeSet Dst;1153  Dst.Add(Pred);1154  NodeBuilder Bldr(Pred, Dst, *currBldrCtx);1155  ProgramStateRef NewState = Pred->getState();1156 1157  if(AMgr.options.ShouldUnrollLoops)1158    NewState = processLoopEnd(S, NewState);1159 1160  LoopExit PP(S, Pred->getLocationContext());1161  Bldr.generateNode(PP, NewState, Pred);1162  // Enqueue the new nodes onto the work list.1163  Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx);1164}1165 1166void ExprEngine::ProcessInitializer(const CFGInitializer CFGInit,1167                                    ExplodedNode *Pred) {1168  const CXXCtorInitializer *BMI = CFGInit.getInitializer();1169  const Expr *Init = BMI->getInit()->IgnoreImplicit();1170  const LocationContext *LC = Pred->getLocationContext();1171 1172  PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),1173                                BMI->getSourceLocation(),1174                                "Error evaluating initializer");1175 1176  // We don't clean up dead bindings here.1177  const auto *stackFrame = cast<StackFrameContext>(Pred->getLocationContext());1178  const auto *decl = cast<CXXConstructorDecl>(stackFrame->getDecl());1179 1180  ProgramStateRef State = Pred->getState();1181  SVal thisVal = State->getSVal(svalBuilder.getCXXThis(decl, stackFrame));1182 1183  ExplodedNodeSet Tmp;1184  SVal FieldLoc;1185 1186  // Evaluate the initializer, if necessary1187  if (BMI->isAnyMemberInitializer()) {1188    // Constructors build the object directly in the field,1189    // but non-objects must be copied in from the initializer.1190    if (getObjectUnderConstruction(State, BMI, LC)) {1191      // The field was directly constructed, so there is no need to bind.1192      // But we still need to stop tracking the object under construction.1193      State = finishObjectConstruction(State, BMI, LC);1194      NodeBuilder Bldr(Pred, Tmp, *currBldrCtx);1195      PostStore PS(Init, LC, /*Loc*/ nullptr, /*tag*/ nullptr);1196      Bldr.generateNode(PS, State, Pred);1197    } else {1198      const ValueDecl *Field;1199      if (BMI->isIndirectMemberInitializer()) {1200        Field = BMI->getIndirectMember();1201        FieldLoc = State->getLValue(BMI->getIndirectMember(), thisVal);1202      } else {1203        Field = BMI->getMember();1204        FieldLoc = State->getLValue(BMI->getMember(), thisVal);1205      }1206 1207      SVal InitVal;1208      if (Init->getType()->isArrayType()) {1209        // Handle arrays of trivial type. We can represent this with a1210        // primitive load/copy from the base array region.1211        const ArraySubscriptExpr *ASE;1212        while ((ASE = dyn_cast<ArraySubscriptExpr>(Init)))1213          Init = ASE->getBase()->IgnoreImplicit();1214 1215        InitVal = State->getSVal(Init, stackFrame);1216 1217        // If we fail to get the value for some reason, use a symbolic value.1218        if (InitVal.isUnknownOrUndef()) {1219          SValBuilder &SVB = getSValBuilder();1220          InitVal =1221              SVB.conjureSymbolVal(getCFGElementRef(), stackFrame,1222                                   Field->getType(), currBldrCtx->blockCount());1223        }1224      } else {1225        InitVal = State->getSVal(BMI->getInit(), stackFrame);1226      }1227 1228      PostInitializer PP(BMI, FieldLoc.getAsRegion(), stackFrame);1229      evalBind(Tmp, Init, Pred, FieldLoc, InitVal, /*isInit=*/true, &PP);1230    }1231  } else if (BMI->isBaseInitializer() && isa<InitListExpr>(Init)) {1232    // When the base class is initialized with an initialization list and the1233    // base class does not have a ctor, there will not be a CXXConstructExpr to1234    // initialize the base region. Hence, we need to make the bind for it.1235    SVal BaseLoc = getStoreManager().evalDerivedToBase(1236        thisVal, QualType(BMI->getBaseClass(), 0), BMI->isBaseVirtual());1237    SVal InitVal = State->getSVal(Init, stackFrame);1238    evalBind(Tmp, Init, Pred, BaseLoc, InitVal, /*isInit=*/true);1239  } else {1240    assert(BMI->isBaseInitializer() || BMI->isDelegatingInitializer());1241    Tmp.insert(Pred);1242    // We already did all the work when visiting the CXXConstructExpr.1243  }1244 1245  // Construct PostInitializer nodes whether the state changed or not,1246  // so that the diagnostics don't get confused.1247  PostInitializer PP(BMI, FieldLoc.getAsRegion(), stackFrame);1248  ExplodedNodeSet Dst;1249  NodeBuilder Bldr(Tmp, Dst, *currBldrCtx);1250  for (const auto I : Tmp) {1251    ProgramStateRef State = I->getState();1252    Bldr.generateNode(PP, State, I);1253  }1254 1255  // Enqueue the new nodes onto the work list.1256  Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx);1257}1258 1259std::pair<ProgramStateRef, uint64_t>1260ExprEngine::prepareStateForArrayDestruction(const ProgramStateRef State,1261                                            const MemRegion *Region,1262                                            const QualType &ElementTy,1263                                            const LocationContext *LCtx,1264                                            SVal *ElementCountVal) {1265  assert(Region != nullptr && "Not-null region expected");1266 1267  QualType Ty = ElementTy.getDesugaredType(getContext());1268  while (const auto *NTy = dyn_cast<ArrayType>(Ty))1269    Ty = NTy->getElementType().getDesugaredType(getContext());1270 1271  auto ElementCount = getDynamicElementCount(State, Region, svalBuilder, Ty);1272 1273  if (ElementCountVal)1274    *ElementCountVal = ElementCount;1275 1276  // Note: the destructors are called in reverse order.1277  unsigned Idx = 0;1278  if (auto OptionalIdx = getPendingArrayDestruction(State, LCtx)) {1279    Idx = *OptionalIdx;1280  } else {1281    // The element count is either unknown, or an SVal that's not an integer.1282    if (!ElementCount.isConstant())1283      return {State, 0};1284 1285    Idx = ElementCount.getAsInteger()->getLimitedValue();1286  }1287 1288  if (Idx == 0)1289    return {State, 0};1290 1291  --Idx;1292 1293  return {setPendingArrayDestruction(State, LCtx, Idx), Idx};1294}1295 1296void ExprEngine::ProcessImplicitDtor(const CFGImplicitDtor D,1297                                     ExplodedNode *Pred) {1298  ExplodedNodeSet Dst;1299  switch (D.getKind()) {1300  case CFGElement::AutomaticObjectDtor:1301    ProcessAutomaticObjDtor(D.castAs<CFGAutomaticObjDtor>(), Pred, Dst);1302    break;1303  case CFGElement::BaseDtor:1304    ProcessBaseDtor(D.castAs<CFGBaseDtor>(), Pred, Dst);1305    break;1306  case CFGElement::MemberDtor:1307    ProcessMemberDtor(D.castAs<CFGMemberDtor>(), Pred, Dst);1308    break;1309  case CFGElement::TemporaryDtor:1310    ProcessTemporaryDtor(D.castAs<CFGTemporaryDtor>(), Pred, Dst);1311    break;1312  case CFGElement::DeleteDtor:1313    ProcessDeleteDtor(D.castAs<CFGDeleteDtor>(), Pred, Dst);1314    break;1315  default:1316    llvm_unreachable("Unexpected dtor kind.");1317  }1318 1319  // Enqueue the new nodes onto the work list.1320  Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx);1321}1322 1323void ExprEngine::ProcessNewAllocator(const CXXNewExpr *NE,1324                                     ExplodedNode *Pred) {1325  ExplodedNodeSet Dst;1326  AnalysisManager &AMgr = getAnalysisManager();1327  AnalyzerOptions &Opts = AMgr.options;1328  // TODO: We're not evaluating allocators for all cases just yet as1329  // we're not handling the return value correctly, which causes false1330  // positives when the alpha.cplusplus.NewDeleteLeaks check is on.1331  if (Opts.MayInlineCXXAllocator)1332    VisitCXXNewAllocatorCall(NE, Pred, Dst);1333  else {1334    NodeBuilder Bldr(Pred, Dst, *currBldrCtx);1335    const LocationContext *LCtx = Pred->getLocationContext();1336    PostImplicitCall PP(NE->getOperatorNew(), NE->getBeginLoc(), LCtx,1337                        getCFGElementRef());1338    Bldr.generateNode(PP, Pred->getState(), Pred);1339  }1340  Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx);1341}1342 1343void ExprEngine::ProcessAutomaticObjDtor(const CFGAutomaticObjDtor Dtor,1344                                         ExplodedNode *Pred,1345                                         ExplodedNodeSet &Dst) {1346  const auto *DtorDecl = Dtor.getDestructorDecl(getContext());1347  const VarDecl *varDecl = Dtor.getVarDecl();1348  QualType varType = varDecl->getType();1349 1350  ProgramStateRef state = Pred->getState();1351  const LocationContext *LCtx = Pred->getLocationContext();1352 1353  SVal dest = state->getLValue(varDecl, LCtx);1354  const MemRegion *Region = dest.castAs<loc::MemRegionVal>().getRegion();1355 1356  if (varType->isReferenceType()) {1357    const MemRegion *ValueRegion = state->getSVal(Region).getAsRegion();1358    if (!ValueRegion) {1359      // FIXME: This should not happen. The language guarantees a presence1360      // of a valid initializer here, so the reference shall not be undefined.1361      // It seems that we're calling destructors over variables that1362      // were not initialized yet.1363      return;1364    }1365    Region = ValueRegion->getBaseRegion();1366    varType = cast<TypedValueRegion>(Region)->getValueType();1367  }1368 1369  unsigned Idx = 0;1370  if (isa<ArrayType>(varType)) {1371    SVal ElementCount;1372    std::tie(state, Idx) = prepareStateForArrayDestruction(1373        state, Region, varType, LCtx, &ElementCount);1374 1375    if (ElementCount.isConstant()) {1376      uint64_t ArrayLength = ElementCount.getAsInteger()->getLimitedValue();1377      assert(ArrayLength &&1378             "An automatic dtor for a 0 length array shouldn't be triggered!");1379 1380      // Still handle this case if we don't have assertions enabled.1381      if (!ArrayLength) {1382        static SimpleProgramPointTag PT(1383            "ExprEngine", "Skipping automatic 0 length array destruction, "1384                          "which shouldn't be in the CFG.");1385        PostImplicitCall PP(DtorDecl, varDecl->getLocation(), LCtx,1386                            getCFGElementRef(), &PT);1387        NodeBuilder Bldr(Pred, Dst, *currBldrCtx);1388        Bldr.generateSink(PP, Pred->getState(), Pred);1389        return;1390      }1391    }1392  }1393 1394  EvalCallOptions CallOpts;1395  Region = makeElementRegion(state, loc::MemRegionVal(Region), varType,1396                             CallOpts.IsArrayCtorOrDtor, Idx)1397               .getAsRegion();1398 1399  NodeBuilder Bldr(Pred, Dst, getBuilderContext());1400 1401  static SimpleProgramPointTag PT("ExprEngine",1402                                  "Prepare for object destruction");1403  PreImplicitCall PP(DtorDecl, varDecl->getLocation(), LCtx, getCFGElementRef(),1404                     &PT);1405  Pred = Bldr.generateNode(PP, state, Pred);1406 1407  if (!Pred)1408    return;1409  Bldr.takeNodes(Pred);1410 1411  VisitCXXDestructor(varType, Region, Dtor.getTriggerStmt(),1412                     /*IsBase=*/false, Pred, Dst, CallOpts);1413}1414 1415void ExprEngine::ProcessDeleteDtor(const CFGDeleteDtor Dtor,1416                                   ExplodedNode *Pred,1417                                   ExplodedNodeSet &Dst) {1418  ProgramStateRef State = Pred->getState();1419  const LocationContext *LCtx = Pred->getLocationContext();1420  const CXXDeleteExpr *DE = Dtor.getDeleteExpr();1421  const Stmt *Arg = DE->getArgument();1422  QualType DTy = DE->getDestroyedType();1423  SVal ArgVal = State->getSVal(Arg, LCtx);1424 1425  // If the argument to delete is known to be a null value,1426  // don't run destructor.1427  if (State->isNull(ArgVal).isConstrainedTrue()) {1428    QualType BTy = getContext().getBaseElementType(DTy);1429    const CXXRecordDecl *RD = BTy->getAsCXXRecordDecl();1430    const CXXDestructorDecl *Dtor = RD->getDestructor();1431 1432    PostImplicitCall PP(Dtor, DE->getBeginLoc(), LCtx, getCFGElementRef());1433    NodeBuilder Bldr(Pred, Dst, *currBldrCtx);1434    Bldr.generateNode(PP, Pred->getState(), Pred);1435    return;1436  }1437 1438  auto getDtorDecl = [](const QualType &DTy) {1439    const CXXRecordDecl *RD = DTy->getAsCXXRecordDecl();1440    return RD->getDestructor();1441  };1442 1443  unsigned Idx = 0;1444  EvalCallOptions CallOpts;1445  const MemRegion *ArgR = ArgVal.getAsRegion();1446 1447  if (DE->isArrayForm()) {1448    CallOpts.IsArrayCtorOrDtor = true;1449    // Yes, it may even be a multi-dimensional array.1450    while (const auto *AT = getContext().getAsArrayType(DTy))1451      DTy = AT->getElementType();1452 1453    if (ArgR) {1454      SVal ElementCount;1455      std::tie(State, Idx) = prepareStateForArrayDestruction(1456          State, ArgR, DTy, LCtx, &ElementCount);1457 1458      // If we're about to destruct a 0 length array, don't run any of the1459      // destructors.1460      if (ElementCount.isConstant() &&1461          ElementCount.getAsInteger()->getLimitedValue() == 0) {1462 1463        static SimpleProgramPointTag PT(1464            "ExprEngine", "Skipping 0 length array delete destruction");1465        PostImplicitCall PP(getDtorDecl(DTy), DE->getBeginLoc(), LCtx,1466                            getCFGElementRef(), &PT);1467        NodeBuilder Bldr(Pred, Dst, *currBldrCtx);1468        Bldr.generateNode(PP, Pred->getState(), Pred);1469        return;1470      }1471 1472      ArgR = State->getLValue(DTy, svalBuilder.makeArrayIndex(Idx), ArgVal)1473                 .getAsRegion();1474    }1475  }1476 1477  NodeBuilder Bldr(Pred, Dst, getBuilderContext());1478  static SimpleProgramPointTag PT("ExprEngine",1479                                  "Prepare for object destruction");1480  PreImplicitCall PP(getDtorDecl(DTy), DE->getBeginLoc(), LCtx,1481                     getCFGElementRef(), &PT);1482  Pred = Bldr.generateNode(PP, State, Pred);1483 1484  if (!Pred)1485    return;1486  Bldr.takeNodes(Pred);1487 1488  VisitCXXDestructor(DTy, ArgR, DE, /*IsBase=*/false, Pred, Dst, CallOpts);1489}1490 1491void ExprEngine::ProcessBaseDtor(const CFGBaseDtor D,1492                                 ExplodedNode *Pred, ExplodedNodeSet &Dst) {1493  const LocationContext *LCtx = Pred->getLocationContext();1494 1495  const auto *CurDtor = cast<CXXDestructorDecl>(LCtx->getDecl());1496  Loc ThisPtr = getSValBuilder().getCXXThis(CurDtor,1497                                            LCtx->getStackFrame());1498  SVal ThisVal = Pred->getState()->getSVal(ThisPtr);1499 1500  // Create the base object region.1501  const CXXBaseSpecifier *Base = D.getBaseSpecifier();1502  QualType BaseTy = Base->getType();1503  SVal BaseVal = getStoreManager().evalDerivedToBase(ThisVal, BaseTy,1504                                                     Base->isVirtual());1505 1506  EvalCallOptions CallOpts;1507  VisitCXXDestructor(BaseTy, BaseVal.getAsRegion(), CurDtor->getBody(),1508                     /*IsBase=*/true, Pred, Dst, CallOpts);1509}1510 1511void ExprEngine::ProcessMemberDtor(const CFGMemberDtor D,1512                                   ExplodedNode *Pred, ExplodedNodeSet &Dst) {1513  const auto *DtorDecl = D.getDestructorDecl(getContext());1514  const FieldDecl *Member = D.getFieldDecl();1515  QualType T = Member->getType();1516  ProgramStateRef State = Pred->getState();1517  const LocationContext *LCtx = Pred->getLocationContext();1518 1519  const auto *CurDtor = cast<CXXDestructorDecl>(LCtx->getDecl());1520  Loc ThisStorageLoc =1521      getSValBuilder().getCXXThis(CurDtor, LCtx->getStackFrame());1522  Loc ThisLoc = State->getSVal(ThisStorageLoc).castAs<Loc>();1523  SVal FieldVal = State->getLValue(Member, ThisLoc);1524 1525  unsigned Idx = 0;1526  if (isa<ArrayType>(T)) {1527    SVal ElementCount;1528    std::tie(State, Idx) = prepareStateForArrayDestruction(1529        State, FieldVal.getAsRegion(), T, LCtx, &ElementCount);1530 1531    if (ElementCount.isConstant()) {1532      uint64_t ArrayLength = ElementCount.getAsInteger()->getLimitedValue();1533      assert(ArrayLength &&1534             "A member dtor for a 0 length array shouldn't be triggered!");1535 1536      // Still handle this case if we don't have assertions enabled.1537      if (!ArrayLength) {1538        static SimpleProgramPointTag PT(1539            "ExprEngine", "Skipping member 0 length array destruction, which "1540                          "shouldn't be in the CFG.");1541        PostImplicitCall PP(DtorDecl, Member->getLocation(), LCtx,1542                            getCFGElementRef(), &PT);1543        NodeBuilder Bldr(Pred, Dst, *currBldrCtx);1544        Bldr.generateSink(PP, Pred->getState(), Pred);1545        return;1546      }1547    }1548  }1549 1550  EvalCallOptions CallOpts;1551  FieldVal =1552      makeElementRegion(State, FieldVal, T, CallOpts.IsArrayCtorOrDtor, Idx);1553 1554  NodeBuilder Bldr(Pred, Dst, getBuilderContext());1555 1556  static SimpleProgramPointTag PT("ExprEngine",1557                                  "Prepare for object destruction");1558  PreImplicitCall PP(DtorDecl, Member->getLocation(), LCtx, getCFGElementRef(),1559                     &PT);1560  Pred = Bldr.generateNode(PP, State, Pred);1561 1562  if (!Pred)1563    return;1564  Bldr.takeNodes(Pred);1565 1566  VisitCXXDestructor(T, FieldVal.getAsRegion(), CurDtor->getBody(),1567                     /*IsBase=*/false, Pred, Dst, CallOpts);1568}1569 1570void ExprEngine::ProcessTemporaryDtor(const CFGTemporaryDtor D,1571                                      ExplodedNode *Pred,1572                                      ExplodedNodeSet &Dst) {1573  const CXXBindTemporaryExpr *BTE = D.getBindTemporaryExpr();1574  ProgramStateRef State = Pred->getState();1575  const LocationContext *LC = Pred->getLocationContext();1576  const MemRegion *MR = nullptr;1577 1578  if (std::optional<SVal> V = getObjectUnderConstruction(1579          State, D.getBindTemporaryExpr(), Pred->getLocationContext())) {1580    // FIXME: Currently we insert temporary destructors for default parameters,1581    // but we don't insert the constructors, so the entry in1582    // ObjectsUnderConstruction may be missing.1583    State = finishObjectConstruction(State, D.getBindTemporaryExpr(),1584                                     Pred->getLocationContext());1585    MR = V->getAsRegion();1586  }1587 1588  // If copy elision has occurred, and the constructor corresponding to the1589  // destructor was elided, we need to skip the destructor as well.1590  if (isDestructorElided(State, BTE, LC)) {1591    State = cleanupElidedDestructor(State, BTE, LC);1592    NodeBuilder Bldr(Pred, Dst, *currBldrCtx);1593    PostImplicitCall PP(D.getDestructorDecl(getContext()),1594                        D.getBindTemporaryExpr()->getBeginLoc(),1595                        Pred->getLocationContext(), getCFGElementRef());1596    Bldr.generateNode(PP, State, Pred);1597    return;1598  }1599 1600  ExplodedNodeSet CleanDtorState;1601  StmtNodeBuilder StmtBldr(Pred, CleanDtorState, *currBldrCtx);1602  StmtBldr.generateNode(D.getBindTemporaryExpr(), Pred, State);1603 1604  QualType T = D.getBindTemporaryExpr()->getSubExpr()->getType();1605  // FIXME: Currently CleanDtorState can be empty here due to temporaries being1606  // bound to default parameters.1607  assert(CleanDtorState.size() <= 1);1608  ExplodedNode *CleanPred =1609      CleanDtorState.empty() ? Pred : *CleanDtorState.begin();1610 1611  EvalCallOptions CallOpts;1612  CallOpts.IsTemporaryCtorOrDtor = true;1613  if (!MR) {1614    // FIXME: If we have no MR, we still need to unwrap the array to avoid1615    // destroying the whole array at once.1616    //1617    // For this case there is no universal solution as there is no way to1618    // directly create an array of temporary objects. There are some expressions1619    // however which can create temporary objects and have an array type.1620    //1621    // E.g.: std::initializer_list<S>{S(), S()};1622    //1623    // The expression above has a type of 'const struct S[2]' but it's a single1624    // 'std::initializer_list<>'. The destructors of the 2 temporary 'S()'1625    // objects will be called anyway, because they are 2 separate objects in 21626    // separate clusters, i.e.: not an array.1627    //1628    // Now the 'std::initializer_list<>' is not an array either even though it1629    // has the type of an array. The point is, we only want to invoke the1630    // destructor for the initializer list once not twice or so.1631    while (const ArrayType *AT = getContext().getAsArrayType(T)) {1632      T = AT->getElementType();1633 1634      // FIXME: Enable this flag once we handle this case properly.1635      // CallOpts.IsArrayCtorOrDtor = true;1636    }1637  } else {1638    // FIXME: We'd eventually need to makeElementRegion() trick here,1639    // but for now we don't have the respective construction contexts,1640    // so MR would always be null in this case. Do nothing for now.1641  }1642  VisitCXXDestructor(T, MR, D.getBindTemporaryExpr(),1643                     /*IsBase=*/false, CleanPred, Dst, CallOpts);1644}1645 1646void ExprEngine::processCleanupTemporaryBranch(const CXXBindTemporaryExpr *BTE,1647                                               NodeBuilderContext &BldCtx,1648                                               ExplodedNode *Pred,1649                                               ExplodedNodeSet &Dst,1650                                               const CFGBlock *DstT,1651                                               const CFGBlock *DstF) {1652  BranchNodeBuilder TempDtorBuilder(Pred, Dst, BldCtx, DstT, DstF);1653  ProgramStateRef State = Pred->getState();1654  const LocationContext *LC = Pred->getLocationContext();1655  if (getObjectUnderConstruction(State, BTE, LC)) {1656    TempDtorBuilder.generateNode(State, true, Pred);1657  } else {1658    TempDtorBuilder.generateNode(State, false, Pred);1659  }1660}1661 1662void ExprEngine::VisitCXXBindTemporaryExpr(const CXXBindTemporaryExpr *BTE,1663                                           ExplodedNodeSet &PreVisit,1664                                           ExplodedNodeSet &Dst) {1665  // This is a fallback solution in case we didn't have a construction1666  // context when we were constructing the temporary. Otherwise the map should1667  // have been populated there.1668  if (!getAnalysisManager().options.ShouldIncludeTemporaryDtorsInCFG) {1669    // In case we don't have temporary destructors in the CFG, do not mark1670    // the initialization - we would otherwise never clean it up.1671    Dst = PreVisit;1672    return;1673  }1674  StmtNodeBuilder StmtBldr(PreVisit, Dst, *currBldrCtx);1675  for (ExplodedNode *Node : PreVisit) {1676    ProgramStateRef State = Node->getState();1677    const LocationContext *LC = Node->getLocationContext();1678    if (!getObjectUnderConstruction(State, BTE, LC)) {1679      // FIXME: Currently the state might also already contain the marker due to1680      // incorrect handling of temporaries bound to default parameters; for1681      // those, we currently skip the CXXBindTemporaryExpr but rely on adding1682      // temporary destructor nodes.1683      State = addObjectUnderConstruction(State, BTE, LC, UnknownVal());1684    }1685    StmtBldr.generateNode(BTE, Node, State);1686  }1687}1688 1689ProgramStateRef ExprEngine::escapeValues(ProgramStateRef State,1690                                         ArrayRef<SVal> Vs,1691                                         PointerEscapeKind K,1692                                         const CallEvent *Call) const {1693  class CollectReachableSymbolsCallback final : public SymbolVisitor {1694    InvalidatedSymbols &Symbols;1695 1696  public:1697    explicit CollectReachableSymbolsCallback(InvalidatedSymbols &Symbols)1698        : Symbols(Symbols) {}1699 1700    const InvalidatedSymbols &getSymbols() const { return Symbols; }1701 1702    bool VisitSymbol(SymbolRef Sym) override {1703      Symbols.insert(Sym);1704      return true;1705    }1706  };1707  InvalidatedSymbols Symbols;1708  CollectReachableSymbolsCallback CallBack(Symbols);1709  for (SVal V : Vs)1710    State->scanReachableSymbols(V, CallBack);1711 1712  return getCheckerManager().runCheckersForPointerEscape(1713      State, CallBack.getSymbols(), Call, K, nullptr);1714}1715 1716void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred,1717                       ExplodedNodeSet &DstTop) {1718  PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),1719                                S->getBeginLoc(), "Error evaluating statement");1720  ExplodedNodeSet Dst;1721  StmtNodeBuilder Bldr(Pred, DstTop, *currBldrCtx);1722 1723  assert(!isa<Expr>(S) || S == cast<Expr>(S)->IgnoreParens());1724 1725  switch (S->getStmtClass()) {1726    // C++, OpenMP and ARC stuff we don't support yet.1727    case Stmt::CXXDependentScopeMemberExprClass:1728    case Stmt::CXXTryStmtClass:1729    case Stmt::CXXTypeidExprClass:1730    case Stmt::CXXUuidofExprClass:1731    case Stmt::CXXFoldExprClass:1732    case Stmt::MSPropertyRefExprClass:1733    case Stmt::MSPropertySubscriptExprClass:1734    case Stmt::CXXUnresolvedConstructExprClass:1735    case Stmt::DependentScopeDeclRefExprClass:1736    case Stmt::ArrayTypeTraitExprClass:1737    case Stmt::ExpressionTraitExprClass:1738    case Stmt::UnresolvedLookupExprClass:1739    case Stmt::UnresolvedMemberExprClass:1740    case Stmt::RecoveryExprClass:1741    case Stmt::CXXNoexceptExprClass:1742    case Stmt::PackExpansionExprClass:1743    case Stmt::PackIndexingExprClass:1744    case Stmt::SubstNonTypeTemplateParmPackExprClass:1745    case Stmt::FunctionParmPackExprClass:1746    case Stmt::CoroutineBodyStmtClass:1747    case Stmt::CoawaitExprClass:1748    case Stmt::DependentCoawaitExprClass:1749    case Stmt::CoreturnStmtClass:1750    case Stmt::CoyieldExprClass:1751    case Stmt::SEHTryStmtClass:1752    case Stmt::SEHExceptStmtClass:1753    case Stmt::SEHLeaveStmtClass:1754    case Stmt::SEHFinallyStmtClass:1755    case Stmt::OMPCanonicalLoopClass:1756    case Stmt::OMPParallelDirectiveClass:1757    case Stmt::OMPSimdDirectiveClass:1758    case Stmt::OMPForDirectiveClass:1759    case Stmt::OMPForSimdDirectiveClass:1760    case Stmt::OMPSectionsDirectiveClass:1761    case Stmt::OMPSectionDirectiveClass:1762    case Stmt::OMPScopeDirectiveClass:1763    case Stmt::OMPSingleDirectiveClass:1764    case Stmt::OMPMasterDirectiveClass:1765    case Stmt::OMPCriticalDirectiveClass:1766    case Stmt::OMPParallelForDirectiveClass:1767    case Stmt::OMPParallelForSimdDirectiveClass:1768    case Stmt::OMPParallelSectionsDirectiveClass:1769    case Stmt::OMPParallelMasterDirectiveClass:1770    case Stmt::OMPParallelMaskedDirectiveClass:1771    case Stmt::OMPTaskDirectiveClass:1772    case Stmt::OMPTaskyieldDirectiveClass:1773    case Stmt::OMPBarrierDirectiveClass:1774    case Stmt::OMPTaskwaitDirectiveClass:1775    case Stmt::OMPErrorDirectiveClass:1776    case Stmt::OMPTaskgroupDirectiveClass:1777    case Stmt::OMPFlushDirectiveClass:1778    case Stmt::OMPDepobjDirectiveClass:1779    case Stmt::OMPScanDirectiveClass:1780    case Stmt::OMPOrderedDirectiveClass:1781    case Stmt::OMPAtomicDirectiveClass:1782    case Stmt::OMPAssumeDirectiveClass:1783    case Stmt::OMPTargetDirectiveClass:1784    case Stmt::OMPTargetDataDirectiveClass:1785    case Stmt::OMPTargetEnterDataDirectiveClass:1786    case Stmt::OMPTargetExitDataDirectiveClass:1787    case Stmt::OMPTargetParallelDirectiveClass:1788    case Stmt::OMPTargetParallelForDirectiveClass:1789    case Stmt::OMPTargetUpdateDirectiveClass:1790    case Stmt::OMPTeamsDirectiveClass:1791    case Stmt::OMPCancellationPointDirectiveClass:1792    case Stmt::OMPCancelDirectiveClass:1793    case Stmt::OMPTaskLoopDirectiveClass:1794    case Stmt::OMPTaskLoopSimdDirectiveClass:1795    case Stmt::OMPMasterTaskLoopDirectiveClass:1796    case Stmt::OMPMaskedTaskLoopDirectiveClass:1797    case Stmt::OMPMasterTaskLoopSimdDirectiveClass:1798    case Stmt::OMPMaskedTaskLoopSimdDirectiveClass:1799    case Stmt::OMPParallelMasterTaskLoopDirectiveClass:1800    case Stmt::OMPParallelMaskedTaskLoopDirectiveClass:1801    case Stmt::OMPParallelMasterTaskLoopSimdDirectiveClass:1802    case Stmt::OMPParallelMaskedTaskLoopSimdDirectiveClass:1803    case Stmt::OMPDistributeDirectiveClass:1804    case Stmt::OMPDistributeParallelForDirectiveClass:1805    case Stmt::OMPDistributeParallelForSimdDirectiveClass:1806    case Stmt::OMPDistributeSimdDirectiveClass:1807    case Stmt::OMPTargetParallelForSimdDirectiveClass:1808    case Stmt::OMPTargetSimdDirectiveClass:1809    case Stmt::OMPTeamsDistributeDirectiveClass:1810    case Stmt::OMPTeamsDistributeSimdDirectiveClass:1811    case Stmt::OMPTeamsDistributeParallelForSimdDirectiveClass:1812    case Stmt::OMPTeamsDistributeParallelForDirectiveClass:1813    case Stmt::OMPTargetTeamsDirectiveClass:1814    case Stmt::OMPTargetTeamsDistributeDirectiveClass:1815    case Stmt::OMPTargetTeamsDistributeParallelForDirectiveClass:1816    case Stmt::OMPTargetTeamsDistributeParallelForSimdDirectiveClass:1817    case Stmt::OMPTargetTeamsDistributeSimdDirectiveClass:1818    case Stmt::OMPReverseDirectiveClass:1819    case Stmt::OMPStripeDirectiveClass:1820    case Stmt::OMPTileDirectiveClass:1821    case Stmt::OMPInterchangeDirectiveClass:1822    case Stmt::OMPFuseDirectiveClass:1823    case Stmt::OMPInteropDirectiveClass:1824    case Stmt::OMPDispatchDirectiveClass:1825    case Stmt::OMPMaskedDirectiveClass:1826    case Stmt::OMPGenericLoopDirectiveClass:1827    case Stmt::OMPTeamsGenericLoopDirectiveClass:1828    case Stmt::OMPTargetTeamsGenericLoopDirectiveClass:1829    case Stmt::OMPParallelGenericLoopDirectiveClass:1830    case Stmt::OMPTargetParallelGenericLoopDirectiveClass:1831    case Stmt::CapturedStmtClass:1832    case Stmt::SYCLKernelCallStmtClass:1833    case Stmt::OpenACCComputeConstructClass:1834    case Stmt::OpenACCLoopConstructClass:1835    case Stmt::OpenACCCombinedConstructClass:1836    case Stmt::OpenACCDataConstructClass:1837    case Stmt::OpenACCEnterDataConstructClass:1838    case Stmt::OpenACCExitDataConstructClass:1839    case Stmt::OpenACCHostDataConstructClass:1840    case Stmt::OpenACCWaitConstructClass:1841    case Stmt::OpenACCCacheConstructClass:1842    case Stmt::OpenACCInitConstructClass:1843    case Stmt::OpenACCShutdownConstructClass:1844    case Stmt::OpenACCSetConstructClass:1845    case Stmt::OpenACCUpdateConstructClass:1846    case Stmt::OpenACCAtomicConstructClass:1847    case Stmt::OMPUnrollDirectiveClass:1848    case Stmt::OMPMetaDirectiveClass:1849    case Stmt::HLSLOutArgExprClass: {1850      const ExplodedNode *node = Bldr.generateSink(S, Pred, Pred->getState());1851      Engine.addAbortedBlock(node, currBldrCtx->getBlock());1852      break;1853    }1854 1855    case Stmt::ParenExprClass:1856      llvm_unreachable("ParenExprs already handled.");1857    case Stmt::GenericSelectionExprClass:1858      llvm_unreachable("GenericSelectionExprs already handled.");1859    // Cases that should never be evaluated simply because they shouldn't1860    // appear in the CFG.1861    case Stmt::BreakStmtClass:1862    case Stmt::CaseStmtClass:1863    case Stmt::CompoundStmtClass:1864    case Stmt::ContinueStmtClass:1865    case Stmt::CXXForRangeStmtClass:1866    case Stmt::DefaultStmtClass:1867    case Stmt::DoStmtClass:1868    case Stmt::ForStmtClass:1869    case Stmt::GotoStmtClass:1870    case Stmt::IfStmtClass:1871    case Stmt::IndirectGotoStmtClass:1872    case Stmt::LabelStmtClass:1873    case Stmt::NoStmtClass:1874    case Stmt::NullStmtClass:1875    case Stmt::SwitchStmtClass:1876    case Stmt::WhileStmtClass:1877    case Expr::MSDependentExistsStmtClass:1878      llvm_unreachable("Stmt should not be in analyzer evaluation loop");1879    case Stmt::ImplicitValueInitExprClass:1880      // These nodes are shared in the CFG and would case caching out.1881      // Moreover, no additional evaluation required for them, the1882      // analyzer can reconstruct these values from the AST.1883      llvm_unreachable("Should be pruned from CFG");1884 1885    case Stmt::ObjCSubscriptRefExprClass:1886    case Stmt::ObjCPropertyRefExprClass:1887      llvm_unreachable("These are handled by PseudoObjectExpr");1888 1889    case Stmt::GNUNullExprClass: {1890      // GNU __null is a pointer-width integer, not an actual pointer.1891      ProgramStateRef state = Pred->getState();1892      state = state->BindExpr(1893          S, Pred->getLocationContext(),1894          svalBuilder.makeIntValWithWidth(getContext().VoidPtrTy, 0));1895      Bldr.generateNode(S, Pred, state);1896      break;1897    }1898 1899    case Stmt::ObjCAtSynchronizedStmtClass:1900      Bldr.takeNodes(Pred);1901      VisitObjCAtSynchronizedStmt(cast<ObjCAtSynchronizedStmt>(S), Pred, Dst);1902      Bldr.addNodes(Dst);1903      break;1904 1905    case Expr::ConstantExprClass:1906    case Stmt::ExprWithCleanupsClass:1907      // Handled due to fully linearised CFG.1908      break;1909 1910    case Stmt::CXXBindTemporaryExprClass: {1911      Bldr.takeNodes(Pred);1912      ExplodedNodeSet PreVisit;1913      getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this);1914      ExplodedNodeSet Next;1915      VisitCXXBindTemporaryExpr(cast<CXXBindTemporaryExpr>(S), PreVisit, Next);1916      getCheckerManager().runCheckersForPostStmt(Dst, Next, S, *this);1917      Bldr.addNodes(Dst);1918      break;1919    }1920 1921    case Stmt::ArrayInitLoopExprClass:1922      Bldr.takeNodes(Pred);1923      VisitArrayInitLoopExpr(cast<ArrayInitLoopExpr>(S), Pred, Dst);1924      Bldr.addNodes(Dst);1925      break;1926    // Cases not handled yet; but will handle some day.1927    case Stmt::DesignatedInitExprClass:1928    case Stmt::DesignatedInitUpdateExprClass:1929    case Stmt::ArrayInitIndexExprClass:1930    case Stmt::ExtVectorElementExprClass:1931    case Stmt::ImaginaryLiteralClass:1932    case Stmt::ObjCAtCatchStmtClass:1933    case Stmt::ObjCAtFinallyStmtClass:1934    case Stmt::ObjCAtTryStmtClass:1935    case Stmt::ObjCAutoreleasePoolStmtClass:1936    case Stmt::ObjCEncodeExprClass:1937    case Stmt::ObjCIsaExprClass:1938    case Stmt::ObjCProtocolExprClass:1939    case Stmt::ObjCSelectorExprClass:1940    case Stmt::ParenListExprClass:1941    case Stmt::ShuffleVectorExprClass:1942    case Stmt::ConvertVectorExprClass:1943    case Stmt::VAArgExprClass:1944    case Stmt::CUDAKernelCallExprClass:1945    case Stmt::OpaqueValueExprClass:1946    case Stmt::AsTypeExprClass:1947    case Stmt::ConceptSpecializationExprClass:1948    case Stmt::CXXRewrittenBinaryOperatorClass:1949    case Stmt::RequiresExprClass:1950    case Stmt::EmbedExprClass:1951      // Fall through.1952 1953    // Cases we intentionally don't evaluate, since they don't need1954    // to be explicitly evaluated.1955    case Stmt::PredefinedExprClass:1956    case Stmt::AddrLabelExprClass:1957    case Stmt::IntegerLiteralClass:1958    case Stmt::FixedPointLiteralClass:1959    case Stmt::CharacterLiteralClass:1960    case Stmt::CXXScalarValueInitExprClass:1961    case Stmt::CXXBoolLiteralExprClass:1962    case Stmt::ObjCBoolLiteralExprClass:1963    case Stmt::ObjCAvailabilityCheckExprClass:1964    case Stmt::FloatingLiteralClass:1965    case Stmt::NoInitExprClass:1966    case Stmt::SizeOfPackExprClass:1967    case Stmt::StringLiteralClass:1968    case Stmt::SourceLocExprClass:1969    case Stmt::ObjCStringLiteralClass:1970    case Stmt::CXXPseudoDestructorExprClass:1971    case Stmt::SubstNonTypeTemplateParmExprClass:1972    case Stmt::CXXNullPtrLiteralExprClass:1973    case Stmt::ArraySectionExprClass:1974    case Stmt::OMPArrayShapingExprClass:1975    case Stmt::OMPIteratorExprClass:1976    case Stmt::SYCLUniqueStableNameExprClass:1977    case Stmt::OpenACCAsteriskSizeExprClass:1978    case Stmt::TypeTraitExprClass: {1979      Bldr.takeNodes(Pred);1980      ExplodedNodeSet preVisit;1981      getCheckerManager().runCheckersForPreStmt(preVisit, Pred, S, *this);1982      getCheckerManager().runCheckersForPostStmt(Dst, preVisit, S, *this);1983      Bldr.addNodes(Dst);1984      break;1985    }1986 1987    case Stmt::AttributedStmtClass: {1988      Bldr.takeNodes(Pred);1989      VisitAttributedStmt(cast<AttributedStmt>(S), Pred, Dst);1990      Bldr.addNodes(Dst);1991      break;1992    }1993 1994    case Stmt::CXXDefaultArgExprClass:1995    case Stmt::CXXDefaultInitExprClass: {1996      Bldr.takeNodes(Pred);1997      ExplodedNodeSet PreVisit;1998      getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this);1999 2000      ExplodedNodeSet Tmp;2001      StmtNodeBuilder Bldr2(PreVisit, Tmp, *currBldrCtx);2002 2003      const Expr *ArgE;2004      if (const auto *DefE = dyn_cast<CXXDefaultArgExpr>(S))2005        ArgE = DefE->getExpr();2006      else if (const auto *DefE = dyn_cast<CXXDefaultInitExpr>(S))2007        ArgE = DefE->getExpr();2008      else2009        llvm_unreachable("unknown constant wrapper kind");2010 2011      bool IsTemporary = false;2012      if (const auto *MTE = dyn_cast<MaterializeTemporaryExpr>(ArgE)) {2013        ArgE = MTE->getSubExpr();2014        IsTemporary = true;2015      }2016 2017      std::optional<SVal> ConstantVal = svalBuilder.getConstantVal(ArgE);2018      if (!ConstantVal)2019        ConstantVal = UnknownVal();2020 2021      const LocationContext *LCtx = Pred->getLocationContext();2022      for (const auto I : PreVisit) {2023        ProgramStateRef State = I->getState();2024        State = State->BindExpr(S, LCtx, *ConstantVal);2025        if (IsTemporary)2026          State = createTemporaryRegionIfNeeded(State, LCtx,2027                                                cast<Expr>(S),2028                                                cast<Expr>(S));2029        Bldr2.generateNode(S, I, State);2030      }2031 2032      getCheckerManager().runCheckersForPostStmt(Dst, Tmp, S, *this);2033      Bldr.addNodes(Dst);2034      break;2035    }2036 2037    // Cases we evaluate as opaque expressions, conjuring a symbol.2038    case Stmt::CXXStdInitializerListExprClass:2039    case Expr::ObjCArrayLiteralClass:2040    case Expr::ObjCDictionaryLiteralClass:2041    case Expr::ObjCBoxedExprClass: {2042      Bldr.takeNodes(Pred);2043 2044      ExplodedNodeSet preVisit;2045      getCheckerManager().runCheckersForPreStmt(preVisit, Pred, S, *this);2046 2047      ExplodedNodeSet Tmp;2048      StmtNodeBuilder Bldr2(preVisit, Tmp, *currBldrCtx);2049 2050      const auto *Ex = cast<Expr>(S);2051      QualType resultType = Ex->getType();2052 2053      for (const auto N : preVisit) {2054        const LocationContext *LCtx = N->getLocationContext();2055        SVal result = svalBuilder.conjureSymbolVal(2056            /*symbolTag=*/nullptr, getCFGElementRef(), LCtx, resultType,2057            currBldrCtx->blockCount());2058        ProgramStateRef State = N->getState()->BindExpr(Ex, LCtx, result);2059 2060        // Escape pointers passed into the list, unless it's an ObjC boxed2061        // expression which is not a boxable C structure.2062        if (!(isa<ObjCBoxedExpr>(Ex) &&2063              !cast<ObjCBoxedExpr>(Ex)->getSubExpr()2064                                      ->getType()->isRecordType()))2065          for (auto Child : Ex->children()) {2066            assert(Child);2067            SVal Val = State->getSVal(Child, LCtx);2068            State = escapeValues(State, Val, PSK_EscapeOther);2069          }2070 2071        Bldr2.generateNode(S, N, State);2072      }2073 2074      getCheckerManager().runCheckersForPostStmt(Dst, Tmp, S, *this);2075      Bldr.addNodes(Dst);2076      break;2077    }2078 2079    case Stmt::ArraySubscriptExprClass:2080      Bldr.takeNodes(Pred);2081      VisitArraySubscriptExpr(cast<ArraySubscriptExpr>(S), Pred, Dst);2082      Bldr.addNodes(Dst);2083      break;2084 2085    case Stmt::MatrixSubscriptExprClass:2086      llvm_unreachable("Support for MatrixSubscriptExpr is not implemented.");2087      break;2088 2089    case Stmt::GCCAsmStmtClass: {2090      Bldr.takeNodes(Pred);2091      ExplodedNodeSet PreVisit;2092      getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this);2093      ExplodedNodeSet PostVisit;2094      for (ExplodedNode *const N : PreVisit)2095        VisitGCCAsmStmt(cast<GCCAsmStmt>(S), N, PostVisit);2096      getCheckerManager().runCheckersForPostStmt(Dst, PostVisit, S, *this);2097      Bldr.addNodes(Dst);2098      break;2099    }2100 2101    case Stmt::MSAsmStmtClass:2102      Bldr.takeNodes(Pred);2103      VisitMSAsmStmt(cast<MSAsmStmt>(S), Pred, Dst);2104      Bldr.addNodes(Dst);2105      break;2106 2107    case Stmt::BlockExprClass:2108      Bldr.takeNodes(Pred);2109      VisitBlockExpr(cast<BlockExpr>(S), Pred, Dst);2110      Bldr.addNodes(Dst);2111      break;2112 2113    case Stmt::LambdaExprClass:2114      if (AMgr.options.ShouldInlineLambdas) {2115        Bldr.takeNodes(Pred);2116        VisitLambdaExpr(cast<LambdaExpr>(S), Pred, Dst);2117        Bldr.addNodes(Dst);2118      } else {2119        const ExplodedNode *node = Bldr.generateSink(S, Pred, Pred->getState());2120        Engine.addAbortedBlock(node, currBldrCtx->getBlock());2121      }2122      break;2123 2124    case Stmt::BinaryOperatorClass: {2125      const auto *B = cast<BinaryOperator>(S);2126      if (B->isLogicalOp()) {2127        Bldr.takeNodes(Pred);2128        VisitLogicalExpr(B, Pred, Dst);2129        Bldr.addNodes(Dst);2130        break;2131      }2132      else if (B->getOpcode() == BO_Comma) {2133        ProgramStateRef state = Pred->getState();2134        Bldr.generateNode(B, Pred,2135                          state->BindExpr(B, Pred->getLocationContext(),2136                                          state->getSVal(B->getRHS(),2137                                                  Pred->getLocationContext())));2138        break;2139      }2140 2141      Bldr.takeNodes(Pred);2142 2143      if (AMgr.options.ShouldEagerlyAssume &&2144          (B->isRelationalOp() || B->isEqualityOp())) {2145        ExplodedNodeSet Tmp;2146        VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Tmp);2147        evalEagerlyAssumeBifurcation(Dst, Tmp, cast<Expr>(S));2148      }2149      else2150        VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst);2151 2152      Bldr.addNodes(Dst);2153      break;2154    }2155 2156    case Stmt::CXXOperatorCallExprClass: {2157      const auto *OCE = cast<CXXOperatorCallExpr>(S);2158 2159      // For instance method operators, make sure the 'this' argument has a2160      // valid region.2161      const Decl *Callee = OCE->getCalleeDecl();2162      if (const auto *MD = dyn_cast_or_null<CXXMethodDecl>(Callee)) {2163        if (MD->isImplicitObjectMemberFunction()) {2164          ProgramStateRef State = Pred->getState();2165          const LocationContext *LCtx = Pred->getLocationContext();2166          ProgramStateRef NewState =2167            createTemporaryRegionIfNeeded(State, LCtx, OCE->getArg(0));2168          if (NewState != State) {2169            Pred = Bldr.generateNode(OCE, Pred, NewState, /*tag=*/nullptr,2170                                     ProgramPoint::PreStmtKind);2171            // Did we cache out?2172            if (!Pred)2173              break;2174          }2175        }2176      }2177      [[fallthrough]];2178    }2179 2180    case Stmt::CallExprClass:2181    case Stmt::CXXMemberCallExprClass:2182    case Stmt::UserDefinedLiteralClass:2183      Bldr.takeNodes(Pred);2184      VisitCallExpr(cast<CallExpr>(S), Pred, Dst);2185      Bldr.addNodes(Dst);2186      break;2187 2188    case Stmt::CXXCatchStmtClass:2189      Bldr.takeNodes(Pred);2190      VisitCXXCatchStmt(cast<CXXCatchStmt>(S), Pred, Dst);2191      Bldr.addNodes(Dst);2192      break;2193 2194    case Stmt::CXXTemporaryObjectExprClass:2195    case Stmt::CXXConstructExprClass:2196      Bldr.takeNodes(Pred);2197      VisitCXXConstructExpr(cast<CXXConstructExpr>(S), Pred, Dst);2198      Bldr.addNodes(Dst);2199      break;2200 2201    case Stmt::CXXInheritedCtorInitExprClass:2202      Bldr.takeNodes(Pred);2203      VisitCXXInheritedCtorInitExpr(cast<CXXInheritedCtorInitExpr>(S), Pred,2204                                    Dst);2205      Bldr.addNodes(Dst);2206      break;2207 2208    case Stmt::CXXNewExprClass: {2209      Bldr.takeNodes(Pred);2210 2211      ExplodedNodeSet PreVisit;2212      getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this);2213 2214      ExplodedNodeSet PostVisit;2215      for (const auto i : PreVisit)2216        VisitCXXNewExpr(cast<CXXNewExpr>(S), i, PostVisit);2217 2218      getCheckerManager().runCheckersForPostStmt(Dst, PostVisit, S, *this);2219      Bldr.addNodes(Dst);2220      break;2221    }2222 2223    case Stmt::CXXDeleteExprClass: {2224      Bldr.takeNodes(Pred);2225      ExplodedNodeSet PreVisit;2226      const auto *CDE = cast<CXXDeleteExpr>(S);2227      getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this);2228      ExplodedNodeSet PostVisit;2229      getCheckerManager().runCheckersForPostStmt(PostVisit, PreVisit, S, *this);2230 2231      for (const auto i : PostVisit)2232        VisitCXXDeleteExpr(CDE, i, Dst);2233 2234      Bldr.addNodes(Dst);2235      break;2236    }2237      // FIXME: ChooseExpr is really a constant.  We need to fix2238      //        the CFG do not model them as explicit control-flow.2239 2240    case Stmt::ChooseExprClass: { // __builtin_choose_expr2241      Bldr.takeNodes(Pred);2242      const auto *C = cast<ChooseExpr>(S);2243      VisitGuardedExpr(C, C->getLHS(), C->getRHS(), Pred, Dst);2244      Bldr.addNodes(Dst);2245      break;2246    }2247 2248    case Stmt::CompoundAssignOperatorClass:2249      Bldr.takeNodes(Pred);2250      VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst);2251      Bldr.addNodes(Dst);2252      break;2253 2254    case Stmt::CompoundLiteralExprClass:2255      Bldr.takeNodes(Pred);2256      VisitCompoundLiteralExpr(cast<CompoundLiteralExpr>(S), Pred, Dst);2257      Bldr.addNodes(Dst);2258      break;2259 2260    case Stmt::BinaryConditionalOperatorClass:2261    case Stmt::ConditionalOperatorClass: { // '?' operator2262      Bldr.takeNodes(Pred);2263      const auto *C = cast<AbstractConditionalOperator>(S);2264      VisitGuardedExpr(C, C->getTrueExpr(), C->getFalseExpr(), Pred, Dst);2265      Bldr.addNodes(Dst);2266      break;2267    }2268 2269    case Stmt::CXXThisExprClass:2270      Bldr.takeNodes(Pred);2271      VisitCXXThisExpr(cast<CXXThisExpr>(S), Pred, Dst);2272      Bldr.addNodes(Dst);2273      break;2274 2275    case Stmt::DeclRefExprClass: {2276      Bldr.takeNodes(Pred);2277      const auto *DE = cast<DeclRefExpr>(S);2278      VisitCommonDeclRefExpr(DE, DE->getDecl(), Pred, Dst);2279      Bldr.addNodes(Dst);2280      break;2281    }2282 2283    case Stmt::DeclStmtClass:2284      Bldr.takeNodes(Pred);2285      VisitDeclStmt(cast<DeclStmt>(S), Pred, Dst);2286      Bldr.addNodes(Dst);2287      break;2288 2289    case Stmt::ImplicitCastExprClass:2290    case Stmt::CStyleCastExprClass:2291    case Stmt::CXXStaticCastExprClass:2292    case Stmt::CXXDynamicCastExprClass:2293    case Stmt::CXXReinterpretCastExprClass:2294    case Stmt::CXXConstCastExprClass:2295    case Stmt::CXXFunctionalCastExprClass:2296    case Stmt::BuiltinBitCastExprClass:2297    case Stmt::ObjCBridgedCastExprClass:2298    case Stmt::CXXAddrspaceCastExprClass: {2299      Bldr.takeNodes(Pred);2300      const auto *C = cast<CastExpr>(S);2301      ExplodedNodeSet dstExpr;2302      VisitCast(C, C->getSubExpr(), Pred, dstExpr);2303 2304      // Handle the postvisit checks.2305      getCheckerManager().runCheckersForPostStmt(Dst, dstExpr, C, *this);2306      Bldr.addNodes(Dst);2307      break;2308    }2309 2310    case Expr::MaterializeTemporaryExprClass: {2311      Bldr.takeNodes(Pred);2312      const auto *MTE = cast<MaterializeTemporaryExpr>(S);2313      ExplodedNodeSet dstPrevisit;2314      getCheckerManager().runCheckersForPreStmt(dstPrevisit, Pred, MTE, *this);2315      ExplodedNodeSet dstExpr;2316      for (const auto i : dstPrevisit)2317        CreateCXXTemporaryObject(MTE, i, dstExpr);2318      getCheckerManager().runCheckersForPostStmt(Dst, dstExpr, MTE, *this);2319      Bldr.addNodes(Dst);2320      break;2321    }2322 2323    case Stmt::InitListExprClass: {2324      const InitListExpr *E = cast<InitListExpr>(S);2325      Bldr.takeNodes(Pred);2326      ConstructInitList(E, E->inits(), E->isTransparent(), Pred, Dst);2327      Bldr.addNodes(Dst);2328      break;2329    }2330 2331    case Expr::CXXParenListInitExprClass: {2332      const CXXParenListInitExpr *E = cast<CXXParenListInitExpr>(S);2333      Bldr.takeNodes(Pred);2334      ConstructInitList(E, E->getInitExprs(), /*IsTransparent*/ false, Pred,2335                        Dst);2336      Bldr.addNodes(Dst);2337      break;2338    }2339 2340    case Stmt::MemberExprClass:2341      Bldr.takeNodes(Pred);2342      VisitMemberExpr(cast<MemberExpr>(S), Pred, Dst);2343      Bldr.addNodes(Dst);2344      break;2345 2346    case Stmt::AtomicExprClass:2347      Bldr.takeNodes(Pred);2348      VisitAtomicExpr(cast<AtomicExpr>(S), Pred, Dst);2349      Bldr.addNodes(Dst);2350      break;2351 2352    case Stmt::ObjCIvarRefExprClass:2353      Bldr.takeNodes(Pred);2354      VisitLvalObjCIvarRefExpr(cast<ObjCIvarRefExpr>(S), Pred, Dst);2355      Bldr.addNodes(Dst);2356      break;2357 2358    case Stmt::ObjCForCollectionStmtClass:2359      Bldr.takeNodes(Pred);2360      VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S), Pred, Dst);2361      Bldr.addNodes(Dst);2362      break;2363 2364    case Stmt::ObjCMessageExprClass:2365      Bldr.takeNodes(Pred);2366      VisitObjCMessage(cast<ObjCMessageExpr>(S), Pred, Dst);2367      Bldr.addNodes(Dst);2368      break;2369 2370    case Stmt::ObjCAtThrowStmtClass:2371    case Stmt::CXXThrowExprClass:2372      // FIXME: This is not complete.  We basically treat @throw as2373      // an abort.2374      Bldr.generateSink(S, Pred, Pred->getState());2375      break;2376 2377    case Stmt::ReturnStmtClass:2378      Bldr.takeNodes(Pred);2379      VisitReturnStmt(cast<ReturnStmt>(S), Pred, Dst);2380      Bldr.addNodes(Dst);2381      break;2382 2383    case Stmt::OffsetOfExprClass: {2384      Bldr.takeNodes(Pred);2385      ExplodedNodeSet PreVisit;2386      getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this);2387 2388      ExplodedNodeSet PostVisit;2389      for (const auto Node : PreVisit)2390        VisitOffsetOfExpr(cast<OffsetOfExpr>(S), Node, PostVisit);2391 2392      getCheckerManager().runCheckersForPostStmt(Dst, PostVisit, S, *this);2393      Bldr.addNodes(Dst);2394      break;2395    }2396 2397    case Stmt::UnaryExprOrTypeTraitExprClass:2398      Bldr.takeNodes(Pred);2399      VisitUnaryExprOrTypeTraitExpr(cast<UnaryExprOrTypeTraitExpr>(S),2400                                    Pred, Dst);2401      Bldr.addNodes(Dst);2402      break;2403 2404    case Stmt::StmtExprClass: {2405      const auto *SE = cast<StmtExpr>(S);2406 2407      if (SE->getSubStmt()->body_empty()) {2408        // Empty statement expression.2409        assert(SE->getType() == getContext().VoidTy2410               && "Empty statement expression must have void type.");2411        break;2412      }2413 2414      if (const auto *LastExpr =2415              dyn_cast<Expr>(*SE->getSubStmt()->body_rbegin())) {2416        ProgramStateRef state = Pred->getState();2417        Bldr.generateNode(SE, Pred,2418                          state->BindExpr(SE, Pred->getLocationContext(),2419                                          state->getSVal(LastExpr,2420                                                  Pred->getLocationContext())));2421      }2422      break;2423    }2424 2425    case Stmt::UnaryOperatorClass: {2426      Bldr.takeNodes(Pred);2427      const auto *U = cast<UnaryOperator>(S);2428      if (AMgr.options.ShouldEagerlyAssume && (U->getOpcode() == UO_LNot)) {2429        ExplodedNodeSet Tmp;2430        VisitUnaryOperator(U, Pred, Tmp);2431        evalEagerlyAssumeBifurcation(Dst, Tmp, U);2432      }2433      else2434        VisitUnaryOperator(U, Pred, Dst);2435      Bldr.addNodes(Dst);2436      break;2437    }2438 2439    case Stmt::PseudoObjectExprClass: {2440      Bldr.takeNodes(Pred);2441      ProgramStateRef state = Pred->getState();2442      const auto *PE = cast<PseudoObjectExpr>(S);2443      if (const Expr *Result = PE->getResultExpr()) {2444        SVal V = state->getSVal(Result, Pred->getLocationContext());2445        Bldr.generateNode(S, Pred,2446                          state->BindExpr(S, Pred->getLocationContext(), V));2447      }2448      else2449        Bldr.generateNode(S, Pred,2450                          state->BindExpr(S, Pred->getLocationContext(),2451                                                   UnknownVal()));2452 2453      Bldr.addNodes(Dst);2454      break;2455    }2456 2457    case Expr::ObjCIndirectCopyRestoreExprClass: {2458      // ObjCIndirectCopyRestoreExpr implies passing a temporary for2459      // correctness of lifetime management.  Due to limited analysis2460      // of ARC, this is implemented as direct arg passing.2461      Bldr.takeNodes(Pred);2462      ProgramStateRef state = Pred->getState();2463      const auto *OIE = cast<ObjCIndirectCopyRestoreExpr>(S);2464      const Expr *E = OIE->getSubExpr();2465      SVal V = state->getSVal(E, Pred->getLocationContext());2466      Bldr.generateNode(S, Pred,2467              state->BindExpr(S, Pred->getLocationContext(), V));2468      Bldr.addNodes(Dst);2469      break;2470    }2471  }2472}2473 2474bool ExprEngine::replayWithoutInlining(ExplodedNode *N,2475                                       const LocationContext *CalleeLC) {2476  const StackFrameContext *CalleeSF = CalleeLC->getStackFrame();2477  const StackFrameContext *CallerSF = CalleeSF->getParent()->getStackFrame();2478  assert(CalleeSF && CallerSF);2479  ExplodedNode *BeforeProcessingCall = nullptr;2480  const Stmt *CE = CalleeSF->getCallSite();2481 2482  // Find the first node before we started processing the call expression.2483  while (N) {2484    ProgramPoint L = N->getLocation();2485    BeforeProcessingCall = N;2486    N = N->pred_empty() ? nullptr : *(N->pred_begin());2487 2488    // Skip the nodes corresponding to the inlined code.2489    if (L.getStackFrame() != CallerSF)2490      continue;2491    // We reached the caller. Find the node right before we started2492    // processing the call.2493    if (L.isPurgeKind())2494      continue;2495    if (L.getAs<PreImplicitCall>())2496      continue;2497    if (L.getAs<CallEnter>())2498      continue;2499    if (std::optional<StmtPoint> SP = L.getAs<StmtPoint>())2500      if (SP->getStmt() == CE)2501        continue;2502    break;2503  }2504 2505  if (!BeforeProcessingCall)2506    return false;2507 2508  // TODO: Clean up the unneeded nodes.2509 2510  // Build an Epsilon node from which we will restart the analyzes.2511  // Note that CE is permitted to be NULL!2512  static SimpleProgramPointTag PT("ExprEngine", "Replay without inlining");2513  ProgramPoint NewNodeLoc = EpsilonPoint(2514      BeforeProcessingCall->getLocationContext(), CE, nullptr, &PT);2515  // Add the special flag to GDM to signal retrying with no inlining.2516  // Note, changing the state ensures that we are not going to cache out.2517  ProgramStateRef NewNodeState = BeforeProcessingCall->getState();2518  NewNodeState =2519    NewNodeState->set<ReplayWithoutInlining>(const_cast<Stmt *>(CE));2520 2521  // Make the new node a successor of BeforeProcessingCall.2522  bool IsNew = false;2523  ExplodedNode *NewNode = G.getNode(NewNodeLoc, NewNodeState, false, &IsNew);2524  // We cached out at this point. Caching out is common due to us backtracking2525  // from the inlined function, which might spawn several paths.2526  if (!IsNew)2527    return true;2528 2529  NewNode->addPredecessor(BeforeProcessingCall, G);2530 2531  // Add the new node to the work list.2532  Engine.enqueueStmtNode(NewNode, CalleeSF->getCallSiteBlock(),2533                                  CalleeSF->getIndex());2534  NumTimesRetriedWithoutInlining++;2535  return true;2536}2537 2538/// Return the innermost location context which is inlined at `Node`, unless2539/// it's the top-level (entry point) location context.2540static const LocationContext *getInlinedLocationContext(ExplodedNode *Node,2541                                                        ExplodedGraph &G) {2542  const LocationContext *CalleeLC = Node->getLocation().getLocationContext();2543  const LocationContext *RootLC =2544      G.getRoot()->getLocation().getLocationContext();2545 2546  if (CalleeLC->getStackFrame() == RootLC->getStackFrame())2547    return nullptr;2548 2549  return CalleeLC;2550}2551 2552/// Block entrance.  (Update counters).2553void ExprEngine::processCFGBlockEntrance(const BlockEdge &L,2554                                         NodeBuilderWithSinks &nodeBuilder,2555                                         ExplodedNode *Pred) {2556  // If we reach a loop which has a known bound (and meets2557  // other constraints) then consider completely unrolling it.2558  if(AMgr.options.ShouldUnrollLoops) {2559    unsigned maxBlockVisitOnPath = AMgr.options.maxBlockVisitOnPath;2560    const Stmt *Term = nodeBuilder.getContext().getBlock()->getTerminatorStmt();2561    if (Term) {2562      ProgramStateRef NewState = updateLoopStack(Term, AMgr.getASTContext(),2563                                                 Pred, maxBlockVisitOnPath);2564      if (NewState != Pred->getState()) {2565        ExplodedNode *UpdatedNode = nodeBuilder.generateNode(NewState, Pred);2566        if (!UpdatedNode)2567          return;2568        Pred = UpdatedNode;2569      }2570    }2571    // Is we are inside an unrolled loop then no need the check the counters.2572    if(isUnrolledState(Pred->getState()))2573      return;2574  }2575 2576  // If this block is terminated by a loop and it has already been visited the2577  // maximum number of times, widen the loop.2578  unsigned int BlockCount = nodeBuilder.getContext().blockCount();2579  if (BlockCount == AMgr.options.maxBlockVisitOnPath - 1 &&2580      AMgr.options.ShouldWidenLoops) {2581    const Stmt *Term = nodeBuilder.getContext().getBlock()->getTerminatorStmt();2582    if (!isa_and_nonnull<ForStmt, WhileStmt, DoStmt, CXXForRangeStmt>(Term))2583      return;2584 2585    // Widen.2586    const LocationContext *LCtx = Pred->getLocationContext();2587 2588    // FIXME:2589    // We cannot use the CFG element from the via `ExprEngine::getCFGElementRef`2590    // since we are currently at the block entrance and the current reference2591    // would be stale.  Ideally, we should pass on the terminator of the CFG2592    // block, but the terminator cannot be referred as a CFG element.2593    // Here we just pass the the first CFG element in the block.2594    ProgramStateRef WidenedState =2595        getWidenedLoopState(Pred->getState(), LCtx, BlockCount,2596                            *nodeBuilder.getContext().getBlock()->ref_begin());2597    nodeBuilder.generateNode(WidenedState, Pred);2598    return;2599  }2600 2601  // FIXME: Refactor this into a checker.2602  if (BlockCount >= AMgr.options.maxBlockVisitOnPath) {2603    static SimpleProgramPointTag tag(TagProviderName, "Block count exceeded");2604    const ExplodedNode *Sink =2605                   nodeBuilder.generateSink(Pred->getState(), Pred, &tag);2606 2607    if (const LocationContext *LC = getInlinedLocationContext(Pred, G)) {2608      // FIXME: This will unconditionally prevent inlining this function (even2609      // from other entry points), which is not a reasonable heuristic: even if2610      // we reached max block count on this particular execution path, there2611      // may be other execution paths (especially with other parametrizations)2612      // where the analyzer can reach the end of the function (so there is no2613      // natural reason to avoid inlining it). However, disabling this would2614      // significantly increase the analysis time (because more entry points2615      // would exhaust their allocated budget), so it must be compensated by a2616      // different (more reasonable) reduction of analysis scope.2617      Engine.FunctionSummaries->markShouldNotInline(2618          LC->getStackFrame()->getDecl());2619 2620      // Re-run the call evaluation without inlining it, by storing the2621      // no-inlining policy in the state and enqueuing the new work item on2622      // the list. Replay should almost never fail. Use the stats to catch it2623      // if it does.2624      if ((!AMgr.options.NoRetryExhausted && replayWithoutInlining(Pred, LC)))2625        return;2626      NumMaxBlockCountReachedInInlined++;2627    } else2628      NumMaxBlockCountReached++;2629 2630    // Make sink nodes as exhausted(for stats) only if retry failed.2631    Engine.blocksExhausted.push_back(std::make_pair(L, Sink));2632  }2633}2634 2635void ExprEngine::runCheckersForBlockEntrance(const NodeBuilderContext &BldCtx,2636                                             const BlockEntrance &Entrance,2637                                             ExplodedNode *Pred,2638                                             ExplodedNodeSet &Dst) {2639  llvm::PrettyStackTraceFormat CrashInfo(2640      "Processing block entrance B%d -> B%d",2641      Entrance.getPreviousBlock()->getBlockID(),2642      Entrance.getBlock()->getBlockID());2643  currBldrCtx = &BldCtx;2644  getCheckerManager().runCheckersForBlockEntrance(Dst, Pred, Entrance, *this);2645  currBldrCtx = nullptr;2646}2647 2648//===----------------------------------------------------------------------===//2649// Branch processing.2650//===----------------------------------------------------------------------===//2651 2652/// RecoverCastedSymbol - A helper function for ProcessBranch that is used2653/// to try to recover some path-sensitivity for casts of symbolic2654/// integers that promote their values (which are currently not tracked well).2655/// This function returns the SVal bound to Condition->IgnoreCasts if all the2656//  cast(s) did was sign-extend the original value.2657static SVal RecoverCastedSymbol(ProgramStateRef state,2658                                const Stmt *Condition,2659                                const LocationContext *LCtx,2660                                ASTContext &Ctx) {2661 2662  const auto *Ex = dyn_cast<Expr>(Condition);2663  if (!Ex)2664    return UnknownVal();2665 2666  uint64_t bits = 0;2667  bool bitsInit = false;2668 2669  while (const auto *CE = dyn_cast<CastExpr>(Ex)) {2670    QualType T = CE->getType();2671 2672    if (!T->isIntegralOrEnumerationType())2673      return UnknownVal();2674 2675    uint64_t newBits = Ctx.getTypeSize(T);2676    if (!bitsInit || newBits < bits) {2677      bitsInit = true;2678      bits = newBits;2679    }2680 2681    Ex = CE->getSubExpr();2682  }2683 2684  // We reached a non-cast.  Is it a symbolic value?2685  QualType T = Ex->getType();2686 2687  if (!bitsInit || !T->isIntegralOrEnumerationType() ||2688      Ctx.getTypeSize(T) > bits)2689    return UnknownVal();2690 2691  return state->getSVal(Ex, LCtx);2692}2693 2694#ifndef NDEBUG2695static const Stmt *getRightmostLeaf(const Stmt *Condition) {2696  while (Condition) {2697    const auto *BO = dyn_cast<BinaryOperator>(Condition);2698    if (!BO || !BO->isLogicalOp()) {2699      return Condition;2700    }2701    Condition = BO->getRHS()->IgnoreParens();2702  }2703  return nullptr;2704}2705#endif2706 2707// Returns the condition the branch at the end of 'B' depends on and whose value2708// has been evaluated within 'B'.2709// In most cases, the terminator condition of 'B' will be evaluated fully in2710// the last statement of 'B'; in those cases, the resolved condition is the2711// given 'Condition'.2712// If the condition of the branch is a logical binary operator tree, the CFG is2713// optimized: in that case, we know that the expression formed by all but the2714// rightmost leaf of the logical binary operator tree must be true, and thus2715// the branch condition is at this point equivalent to the truth value of that2716// rightmost leaf; the CFG block thus only evaluates this rightmost leaf2717// expression in its final statement. As the full condition in that case was2718// not evaluated, and is thus not in the SVal cache, we need to use that leaf2719// expression to evaluate the truth value of the condition in the current state2720// space.2721static const Stmt *ResolveCondition(const Stmt *Condition,2722                                    const CFGBlock *B) {2723  if (const auto *Ex = dyn_cast<Expr>(Condition))2724    Condition = Ex->IgnoreParens();2725 2726  const auto *BO = dyn_cast<BinaryOperator>(Condition);2727  if (!BO || !BO->isLogicalOp())2728    return Condition;2729 2730  assert(B->getTerminator().isStmtBranch() &&2731         "Other kinds of branches are handled separately!");2732 2733  // For logical operations, we still have the case where some branches2734  // use the traditional "merge" approach and others sink the branch2735  // directly into the basic blocks representing the logical operation.2736  // We need to distinguish between those two cases here.2737 2738  // The invariants are still shifting, but it is possible that the2739  // last element in a CFGBlock is not a CFGStmt.  Look for the last2740  // CFGStmt as the value of the condition.2741  for (CFGElement Elem : llvm::reverse(*B)) {2742    std::optional<CFGStmt> CS = Elem.getAs<CFGStmt>();2743    if (!CS)2744      continue;2745    const Stmt *LastStmt = CS->getStmt();2746    assert(LastStmt == Condition || LastStmt == getRightmostLeaf(Condition));2747    return LastStmt;2748  }2749  llvm_unreachable("could not resolve condition");2750}2751 2752using ObjCForLctxPair =2753    std::pair<const ObjCForCollectionStmt *, const LocationContext *>;2754 2755REGISTER_MAP_WITH_PROGRAMSTATE(ObjCForHasMoreIterations, ObjCForLctxPair, bool)2756 2757ProgramStateRef ExprEngine::setWhetherHasMoreIteration(2758    ProgramStateRef State, const ObjCForCollectionStmt *O,2759    const LocationContext *LC, bool HasMoreIteraton) {2760  assert(!State->contains<ObjCForHasMoreIterations>({O, LC}));2761  return State->set<ObjCForHasMoreIterations>({O, LC}, HasMoreIteraton);2762}2763 2764ProgramStateRef2765ExprEngine::removeIterationState(ProgramStateRef State,2766                                 const ObjCForCollectionStmt *O,2767                                 const LocationContext *LC) {2768  assert(State->contains<ObjCForHasMoreIterations>({O, LC}));2769  return State->remove<ObjCForHasMoreIterations>({O, LC});2770}2771 2772bool ExprEngine::hasMoreIteration(ProgramStateRef State,2773                                  const ObjCForCollectionStmt *O,2774                                  const LocationContext *LC) {2775  assert(State->contains<ObjCForHasMoreIterations>({O, LC}));2776  return *State->get<ObjCForHasMoreIterations>({O, LC});2777}2778 2779/// Split the state on whether there are any more iterations left for this loop.2780/// Returns a (HasMoreIteration, HasNoMoreIteration) pair, or std::nullopt when2781/// the acquisition of the loop condition value failed.2782static std::optional<std::pair<ProgramStateRef, ProgramStateRef>>2783assumeCondition(const Stmt *Condition, ExplodedNode *N) {2784  ProgramStateRef State = N->getState();2785  if (const auto *ObjCFor = dyn_cast<ObjCForCollectionStmt>(Condition)) {2786    bool HasMoreIteraton =2787        ExprEngine::hasMoreIteration(State, ObjCFor, N->getLocationContext());2788    // Checkers have already ran on branch conditions, so the current2789    // information as to whether the loop has more iteration becomes outdated2790    // after this point.2791    State = ExprEngine::removeIterationState(State, ObjCFor,2792                                             N->getLocationContext());2793    if (HasMoreIteraton)2794      return std::pair<ProgramStateRef, ProgramStateRef>{State, nullptr};2795    else2796      return std::pair<ProgramStateRef, ProgramStateRef>{nullptr, State};2797  }2798  SVal X = State->getSVal(Condition, N->getLocationContext());2799 2800  if (X.isUnknownOrUndef()) {2801    // Give it a chance to recover from unknown.2802    if (const auto *Ex = dyn_cast<Expr>(Condition)) {2803      if (Ex->getType()->isIntegralOrEnumerationType()) {2804        // Try to recover some path-sensitivity.  Right now casts of symbolic2805        // integers that promote their values are currently not tracked well.2806        // If 'Condition' is such an expression, try and recover the2807        // underlying value and use that instead.2808        SVal recovered =2809            RecoverCastedSymbol(State, Condition, N->getLocationContext(),2810                                N->getState()->getStateManager().getContext());2811 2812        if (!recovered.isUnknown()) {2813          X = recovered;2814        }2815      }2816    }2817  }2818 2819  // If the condition is still unknown, give up.2820  if (X.isUnknownOrUndef())2821    return std::nullopt;2822 2823  DefinedSVal V = X.castAs<DefinedSVal>();2824 2825  ProgramStateRef StTrue, StFalse;2826  return State->assume(V);2827}2828 2829void ExprEngine::processBranch(2830    const Stmt *Condition, NodeBuilderContext &BldCtx, ExplodedNode *Pred,2831    ExplodedNodeSet &Dst, const CFGBlock *DstT, const CFGBlock *DstF,2832    std::optional<unsigned> IterationsCompletedInLoop) {2833  assert((!Condition || !isa<CXXBindTemporaryExpr>(Condition)) &&2834         "CXXBindTemporaryExprs are handled by processBindTemporary.");2835  currBldrCtx = &BldCtx;2836 2837  // Check for NULL conditions; e.g. "for(;;)"2838  if (!Condition) {2839    BranchNodeBuilder NullCondBldr(Pred, Dst, BldCtx, DstT, DstF);2840    NullCondBldr.generateNode(Pred->getState(), true, Pred);2841    return;2842  }2843 2844  if (const auto *Ex = dyn_cast<Expr>(Condition))2845    Condition = Ex->IgnoreParens();2846 2847  Condition = ResolveCondition(Condition, BldCtx.getBlock());2848  PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),2849                                Condition->getBeginLoc(),2850                                "Error evaluating branch");2851 2852  ExplodedNodeSet CheckersOutSet;2853  getCheckerManager().runCheckersForBranchCondition(Condition, CheckersOutSet,2854                                                    Pred, *this);2855  // We generated only sinks.2856  if (CheckersOutSet.empty())2857    return;2858 2859  BranchNodeBuilder Builder(CheckersOutSet, Dst, BldCtx, DstT, DstF);2860  for (ExplodedNode *PredN : CheckersOutSet) {2861    if (PredN->isSink())2862      continue;2863 2864    ProgramStateRef PrevState = PredN->getState();2865 2866    ProgramStateRef StTrue = PrevState, StFalse = PrevState;2867    if (const auto KnownCondValueAssumption = assumeCondition(Condition, PredN))2868      std::tie(StTrue, StFalse) = *KnownCondValueAssumption;2869 2870    if (StTrue && StFalse)2871      assert(!isa<ObjCForCollectionStmt>(Condition));2872 2873    // We want to ensure consistent behavior between `eagerly-assume=false`,2874    // when the state split is always performed by the `assumeCondition()`2875    // call within this function and `eagerly-assume=true` (the default), when2876    // some conditions (comparison operators, unary negation) can trigger a2877    // state split before this callback. There are some contrived corner cases2878    // that behave differently with and without `eagerly-assume`, but I don't2879    // know about an example that could plausibly appear in "real" code.2880    bool BothFeasible =2881        (StTrue && StFalse) ||2882        didEagerlyAssumeBifurcateAt(PrevState, dyn_cast<Expr>(Condition));2883 2884    if (StTrue) {2885      // In a loop, if both branches are feasible (i.e. the analyzer doesn't2886      // understand the loop condition) and two iterations have already been2887      // completed, then don't assume a third iteration because it is a2888      // redundant execution path (unlikely to be different from earlier loop2889      // exits) and can cause false positives if e.g. the loop iterates over a2890      // two-element structure with an opaque condition.2891      //2892      // The iteration count "2" is hardcoded because it's the natural limit:2893      // * the fact that the programmer wrote a loop (and not just an `if`)2894      //   implies that they thought that the loop body might be executed twice;2895      // * however, there are situations where the programmer knows that there2896      //   are at most two iterations but writes a loop that appears to be2897      //   generic, because there is no special syntax for "loop with at most2898      //   two iterations". (This pattern is common in FFMPEG and appears in2899      //   many other projects as well.)2900      bool CompletedTwoIterations = IterationsCompletedInLoop.value_or(0) >= 2;2901      bool SkipTrueBranch = BothFeasible && CompletedTwoIterations;2902 2903      // FIXME: This "don't assume third iteration" heuristic partially2904      // conflicts with the widen-loop analysis option (which is off by2905      // default). If we intend to support and stabilize the loop widening,2906      // we must ensure that it 'plays nicely' with this logic.2907      if (!SkipTrueBranch || AMgr.options.ShouldWidenLoops) {2908        Builder.generateNode(StTrue, true, PredN);2909      } else if (!AMgr.options.InlineFunctionsWithAmbiguousLoops) {2910        // FIXME: There is an ancient and arbitrary heuristic in2911        // `ExprEngine::processCFGBlockEntrance` which prevents all further2912        // inlining of a function if it finds an execution path within that2913        // function which reaches the `MaxBlockVisitOnPath` limit (a/k/a2914        // `analyzer-max-loop`, by default four iterations in a loop). Adding2915        // this "don't assume third iteration" logic significantly increased2916        // the analysis runtime on some inputs because less functions were2917        // arbitrarily excluded from being inlined, so more entry points used2918        // up their full allocated budget. As a hacky compensation for this,2919        // here we apply the "should not inline" mark in cases when the loop2920        // could potentially reach the `MaxBlockVisitOnPath` limit without the2921        // "don't assume third iteration" logic. This slightly overcompensates2922        // (activates if the third iteration can be entered, and will not2923        // recognize cases where the fourth iteration would't be completed), but2924        // should be good enough for practical purposes.2925        if (const LocationContext *LC = getInlinedLocationContext(Pred, G)) {2926          Engine.FunctionSummaries->markShouldNotInline(2927              LC->getStackFrame()->getDecl());2928        }2929      }2930    }2931 2932    if (StFalse) {2933      // In a loop, if both branches are feasible (i.e. the analyzer doesn't2934      // understand the loop condition), we are before the first iteration and2935      // the analyzer option `assume-at-least-one-iteration` is set to `true`,2936      // then avoid creating the execution path where the loop is skipped.2937      //2938      // In some situations this "loop is skipped" execution path is an2939      // important corner case that may evade the notice of the developer and2940      // hide significant bugs -- however, there are also many situations where2941      // it's guaranteed that at least one iteration will happen (e.g. some2942      // data structure is always nonempty), but the analyzer cannot realize2943      // this and will produce false positives when it assumes that the loop is2944      // skipped.2945      bool BeforeFirstIteration = IterationsCompletedInLoop == std::optional{0};2946      bool SkipFalseBranch = BothFeasible && BeforeFirstIteration &&2947                             AMgr.options.ShouldAssumeAtLeastOneIteration;2948      if (!SkipFalseBranch)2949        Builder.generateNode(StFalse, false, PredN);2950    }2951  }2952  currBldrCtx = nullptr;2953}2954 2955/// The GDM component containing the set of global variables which have been2956/// previously initialized with explicit initializers.2957REGISTER_TRAIT_WITH_PROGRAMSTATE(InitializedGlobalsSet,2958                                 llvm::ImmutableSet<const VarDecl *>)2959 2960void ExprEngine::processStaticInitializer(2961    const DeclStmt *DS, NodeBuilderContext &BuilderCtx, ExplodedNode *Pred,2962    ExplodedNodeSet &Dst, const CFGBlock *DstT, const CFGBlock *DstF) {2963  currBldrCtx = &BuilderCtx;2964 2965  const auto *VD = cast<VarDecl>(DS->getSingleDecl());2966  ProgramStateRef state = Pred->getState();2967  bool initHasRun = state->contains<InitializedGlobalsSet>(VD);2968  BranchNodeBuilder Builder(Pred, Dst, BuilderCtx, DstT, DstF);2969 2970  if (!initHasRun) {2971    state = state->add<InitializedGlobalsSet>(VD);2972  }2973 2974  Builder.generateNode(state, initHasRun, Pred);2975 2976  currBldrCtx = nullptr;2977}2978 2979/// processIndirectGoto - Called by CoreEngine.  Used to generate successor2980///  nodes by processing the 'effects' of a computed goto jump.2981void ExprEngine::processIndirectGoto(IndirectGotoNodeBuilder &builder) {2982  ProgramStateRef state = builder.getState();2983  SVal V = state->getSVal(builder.getTarget(), builder.getLocationContext());2984 2985  // Three possibilities:2986  //2987  //   (1) We know the computed label.2988  //   (2) The label is NULL (or some other constant), or Undefined.2989  //   (3) We have no clue about the label.  Dispatch to all targets.2990  //2991 2992  using iterator = IndirectGotoNodeBuilder::iterator;2993 2994  if (std::optional<loc::GotoLabel> LV = V.getAs<loc::GotoLabel>()) {2995    const LabelDecl *L = LV->getLabel();2996 2997    for (iterator Succ : builder) {2998      if (Succ.getLabel() == L) {2999        builder.generateNode(Succ, state);3000        return;3001      }3002    }3003 3004    llvm_unreachable("No block with label.");3005  }3006 3007  if (isa<UndefinedVal, loc::ConcreteInt>(V)) {3008    // Dispatch to the first target and mark it as a sink.3009    //ExplodedNode* N = builder.generateNode(builder.begin(), state, true);3010    // FIXME: add checker visit.3011    //    UndefBranches.insert(N);3012    return;3013  }3014 3015  // This is really a catch-all.  We don't support symbolics yet.3016  // FIXME: Implement dispatch for symbolic pointers.3017 3018  for (iterator Succ : builder)3019    builder.generateNode(Succ, state);3020}3021 3022void ExprEngine::processBeginOfFunction(NodeBuilderContext &BC,3023                                        ExplodedNode *Pred,3024                                        ExplodedNodeSet &Dst,3025                                        const BlockEdge &L) {3026  SaveAndRestore<const NodeBuilderContext *> NodeContextRAII(currBldrCtx, &BC);3027  getCheckerManager().runCheckersForBeginFunction(Dst, L, Pred, *this);3028}3029 3030/// ProcessEndPath - Called by CoreEngine.  Used to generate end-of-path3031///  nodes when the control reaches the end of a function.3032void ExprEngine::processEndOfFunction(NodeBuilderContext& BC,3033                                      ExplodedNode *Pred,3034                                      const ReturnStmt *RS) {3035  ProgramStateRef State = Pred->getState();3036 3037  if (!Pred->getStackFrame()->inTopFrame())3038    State = finishArgumentConstruction(3039        State, *getStateManager().getCallEventManager().getCaller(3040                   Pred->getStackFrame(), Pred->getState()));3041 3042  // FIXME: We currently cannot assert that temporaries are clear, because3043  // lifetime extended temporaries are not always modelled correctly. In some3044  // cases when we materialize the temporary, we do3045  // createTemporaryRegionIfNeeded(), and the region changes, and also the3046  // respective destructor becomes automatic from temporary. So for now clean up3047  // the state manually before asserting. Ideally, this braced block of code3048  // should go away.3049  {3050    const LocationContext *FromLC = Pred->getLocationContext();3051    const LocationContext *ToLC = FromLC->getStackFrame()->getParent();3052    const LocationContext *LC = FromLC;3053    while (LC != ToLC) {3054      assert(LC && "ToLC must be a parent of FromLC!");3055      for (auto I : State->get<ObjectsUnderConstruction>())3056        if (I.first.getLocationContext() == LC) {3057          // The comment above only pardons us for not cleaning up a3058          // temporary destructor. If any other statements are found here,3059          // it must be a separate problem.3060          assert(I.first.getItem().getKind() ==3061                     ConstructionContextItem::TemporaryDestructorKind ||3062                 I.first.getItem().getKind() ==3063                     ConstructionContextItem::ElidedDestructorKind);3064          State = State->remove<ObjectsUnderConstruction>(I.first);3065        }3066      LC = LC->getParent();3067    }3068  }3069 3070  // Perform the transition with cleanups.3071  if (State != Pred->getState()) {3072    ExplodedNodeSet PostCleanup;3073    NodeBuilder Bldr(Pred, PostCleanup, BC);3074    Pred = Bldr.generateNode(Pred->getLocation(), State, Pred);3075    if (!Pred) {3076      // The node with clean temporaries already exists. We might have reached3077      // it on a path on which we initialize different temporaries.3078      return;3079    }3080  }3081 3082  assert(areAllObjectsFullyConstructed(Pred->getState(),3083                                       Pred->getLocationContext(),3084                                       Pred->getStackFrame()->getParent()));3085  ExplodedNodeSet Dst;3086  if (Pred->getLocationContext()->inTopFrame()) {3087    // Remove dead symbols.3088    ExplodedNodeSet AfterRemovedDead;3089    removeDeadOnEndOfFunction(BC, Pred, AfterRemovedDead);3090 3091    // Notify checkers.3092    for (const auto I : AfterRemovedDead)3093      getCheckerManager().runCheckersForEndFunction(BC, Dst, I, *this, RS);3094  } else {3095    getCheckerManager().runCheckersForEndFunction(BC, Dst, Pred, *this, RS);3096  }3097 3098  Engine.enqueueEndOfFunction(Dst, RS);3099}3100 3101/// ProcessSwitch - Called by CoreEngine.  Used to generate successor3102///  nodes by processing the 'effects' of a switch statement.3103void ExprEngine::processSwitch(SwitchNodeBuilder& builder) {3104  using iterator = SwitchNodeBuilder::iterator;3105 3106  ProgramStateRef state = builder.getState();3107  const Expr *CondE = builder.getCondition();3108  SVal  CondV_untested = state->getSVal(CondE, builder.getLocationContext());3109 3110  if (CondV_untested.isUndef()) {3111    //ExplodedNode* N = builder.generateDefaultCaseNode(state, true);3112    // FIXME: add checker3113    //UndefBranches.insert(N);3114 3115    return;3116  }3117  DefinedOrUnknownSVal CondV = CondV_untested.castAs<DefinedOrUnknownSVal>();3118 3119  ProgramStateRef DefaultSt = state;3120 3121  iterator I = builder.begin(), EI = builder.end();3122  bool defaultIsFeasible = I == EI;3123 3124  for ( ; I != EI; ++I) {3125    // Successor may be pruned out during CFG construction.3126    if (!I.getBlock())3127      continue;3128 3129    const CaseStmt *Case = I.getCase();3130 3131    // Evaluate the LHS of the case value.3132    llvm::APSInt V1 = Case->getLHS()->EvaluateKnownConstInt(getContext());3133    assert(V1.getBitWidth() == getContext().getIntWidth(CondE->getType()));3134 3135    // Get the RHS of the case, if it exists.3136    llvm::APSInt V2;3137    if (const Expr *E = Case->getRHS())3138      V2 = E->EvaluateKnownConstInt(getContext());3139    else3140      V2 = V1;3141 3142    ProgramStateRef StateCase;3143    if (std::optional<NonLoc> NL = CondV.getAs<NonLoc>())3144      std::tie(StateCase, DefaultSt) =3145          DefaultSt->assumeInclusiveRange(*NL, V1, V2);3146    else // UnknownVal3147      StateCase = DefaultSt;3148 3149    if (StateCase)3150      builder.generateCaseStmtNode(I, StateCase);3151 3152    // Now "assume" that the case doesn't match.  Add this state3153    // to the default state (if it is feasible).3154    if (DefaultSt)3155      defaultIsFeasible = true;3156    else {3157      defaultIsFeasible = false;3158      break;3159    }3160  }3161 3162  if (!defaultIsFeasible)3163    return;3164 3165  // If we have switch(enum value), the default branch is not3166  // feasible if all of the enum constants not covered by 'case:' statements3167  // are not feasible values for the switch condition.3168  //3169  // Note that this isn't as accurate as it could be.  Even if there isn't3170  // a case for a particular enum value as long as that enum value isn't3171  // feasible then it shouldn't be considered for making 'default:' reachable.3172  const SwitchStmt *SS = builder.getSwitch();3173  const Expr *CondExpr = SS->getCond()->IgnoreParenImpCasts();3174  if (CondExpr->getType()->isEnumeralType()) {3175    if (SS->isAllEnumCasesCovered())3176      return;3177  }3178 3179  builder.generateDefaultCaseNode(DefaultSt);3180}3181 3182//===----------------------------------------------------------------------===//3183// Transfer functions: Loads and stores.3184//===----------------------------------------------------------------------===//3185 3186void ExprEngine::VisitCommonDeclRefExpr(const Expr *Ex, const NamedDecl *D,3187                                        ExplodedNode *Pred,3188                                        ExplodedNodeSet &Dst) {3189  StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);3190 3191  ProgramStateRef state = Pred->getState();3192  const LocationContext *LCtx = Pred->getLocationContext();3193 3194  auto resolveAsLambdaCapturedVar =3195      [&](const ValueDecl *VD) -> std::optional<std::pair<SVal, QualType>> {3196    const auto *MD = dyn_cast<CXXMethodDecl>(LCtx->getDecl());3197    const auto *DeclRefEx = dyn_cast<DeclRefExpr>(Ex);3198    if (AMgr.options.ShouldInlineLambdas && DeclRefEx &&3199        DeclRefEx->refersToEnclosingVariableOrCapture() && MD &&3200        MD->getParent()->isLambda()) {3201      // Lookup the field of the lambda.3202      const CXXRecordDecl *CXXRec = MD->getParent();3203      llvm::DenseMap<const ValueDecl *, FieldDecl *> LambdaCaptureFields;3204      FieldDecl *LambdaThisCaptureField;3205      CXXRec->getCaptureFields(LambdaCaptureFields, LambdaThisCaptureField);3206 3207      // Sema follows a sequence of complex rules to determine whether the3208      // variable should be captured.3209      if (const FieldDecl *FD = LambdaCaptureFields[VD]) {3210        Loc CXXThis = svalBuilder.getCXXThis(MD, LCtx->getStackFrame());3211        SVal CXXThisVal = state->getSVal(CXXThis);3212        return std::make_pair(state->getLValue(FD, CXXThisVal), FD->getType());3213      }3214    }3215 3216    return std::nullopt;3217  };3218 3219  if (const auto *VD = dyn_cast<VarDecl>(D)) {3220    // C permits "extern void v", and if you cast the address to a valid type,3221    // you can even do things with it. We simply pretend3222    assert(Ex->isGLValue() || VD->getType()->isVoidType());3223    const LocationContext *LocCtxt = Pred->getLocationContext();3224    std::optional<std::pair<SVal, QualType>> VInfo =3225        resolveAsLambdaCapturedVar(VD);3226 3227    if (!VInfo)3228      VInfo = std::make_pair(state->getLValue(VD, LocCtxt), VD->getType());3229 3230    SVal V = VInfo->first;3231    bool IsReference = VInfo->second->isReferenceType();3232 3233    // For references, the 'lvalue' is the pointer address stored in the3234    // reference region.3235    if (IsReference) {3236      if (const MemRegion *R = V.getAsRegion())3237        V = state->getSVal(R);3238      else3239        V = UnknownVal();3240    }3241 3242    Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), nullptr,3243                      ProgramPoint::PostLValueKind);3244    return;3245  }3246  if (const auto *ED = dyn_cast<EnumConstantDecl>(D)) {3247    assert(!Ex->isGLValue());3248    SVal V = svalBuilder.makeIntVal(ED->getInitVal());3249    Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V));3250    return;3251  }3252  if (const auto *FD = dyn_cast<FunctionDecl>(D)) {3253    SVal V = svalBuilder.getFunctionPointer(FD);3254    Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), nullptr,3255                      ProgramPoint::PostLValueKind);3256    return;3257  }3258  if (isa<FieldDecl, IndirectFieldDecl>(D)) {3259    // Delegate all work related to pointer to members to the surrounding3260    // operator&.3261    return;3262  }3263  if (const auto *BD = dyn_cast<BindingDecl>(D)) {3264    // Handle structured bindings captured by lambda.3265    if (std::optional<std::pair<SVal, QualType>> VInfo =3266            resolveAsLambdaCapturedVar(BD)) {3267      auto [V, T] = VInfo.value();3268 3269      if (T->isReferenceType()) {3270        if (const MemRegion *R = V.getAsRegion())3271          V = state->getSVal(R);3272        else3273          V = UnknownVal();3274      }3275 3276      Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), nullptr,3277                        ProgramPoint::PostLValueKind);3278      return;3279    }3280 3281    const auto *DD = cast<DecompositionDecl>(BD->getDecomposedDecl());3282 3283    SVal Base = state->getLValue(DD, LCtx);3284    if (DD->getType()->isReferenceType()) {3285      if (const MemRegion *R = Base.getAsRegion())3286        Base = state->getSVal(R);3287      else3288        Base = UnknownVal();3289    }3290 3291    SVal V = UnknownVal();3292 3293    // Handle binding to data members3294    if (const auto *ME = dyn_cast<MemberExpr>(BD->getBinding())) {3295      const auto *Field = cast<FieldDecl>(ME->getMemberDecl());3296      V = state->getLValue(Field, Base);3297    }3298    // Handle binding to arrays3299    else if (const auto *ASE = dyn_cast<ArraySubscriptExpr>(BD->getBinding())) {3300      SVal Idx = state->getSVal(ASE->getIdx(), LCtx);3301 3302      // Note: the index of an element in a structured binding is automatically3303      // created and it is a unique identifier of the specific element. Thus it3304      // cannot be a value that varies at runtime.3305      assert(Idx.isConstant() && "BindingDecl array index is not a constant!");3306 3307      V = state->getLValue(BD->getType(), Idx, Base);3308    }3309    // Handle binding to tuple-like structures3310    else if (const auto *HV = BD->getHoldingVar()) {3311      V = state->getLValue(HV, LCtx);3312 3313      if (HV->getType()->isReferenceType()) {3314        if (const MemRegion *R = V.getAsRegion())3315          V = state->getSVal(R);3316        else3317          V = UnknownVal();3318      }3319    } else3320      llvm_unreachable("An unknown case of structured binding encountered!");3321 3322    // In case of tuple-like types the references are already handled, so we3323    // don't want to handle them again.3324    if (BD->getType()->isReferenceType() && !BD->getHoldingVar()) {3325      if (const MemRegion *R = V.getAsRegion())3326        V = state->getSVal(R);3327      else3328        V = UnknownVal();3329    }3330 3331    Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), nullptr,3332                      ProgramPoint::PostLValueKind);3333 3334    return;3335  }3336 3337  if (const auto *TPO = dyn_cast<TemplateParamObjectDecl>(D)) {3338    // FIXME: We should meaningfully implement this.3339    (void)TPO;3340    return;3341  }3342 3343  llvm_unreachable("Support for this Decl not implemented.");3344}3345 3346/// VisitArrayInitLoopExpr - Transfer function for array init loop.3347void ExprEngine::VisitArrayInitLoopExpr(const ArrayInitLoopExpr *Ex,3348                                        ExplodedNode *Pred,3349                                        ExplodedNodeSet &Dst) {3350  ExplodedNodeSet CheckerPreStmt;3351  getCheckerManager().runCheckersForPreStmt(CheckerPreStmt, Pred, Ex, *this);3352 3353  ExplodedNodeSet EvalSet;3354  StmtNodeBuilder Bldr(CheckerPreStmt, EvalSet, *currBldrCtx);3355 3356  const Expr *Arr = Ex->getCommonExpr()->getSourceExpr();3357 3358  for (auto *Node : CheckerPreStmt) {3359 3360    // The constructor visitior has already taken care of everything.3361    if (isa<CXXConstructExpr>(Ex->getSubExpr()))3362      break;3363 3364    const LocationContext *LCtx = Node->getLocationContext();3365    ProgramStateRef state = Node->getState();3366 3367    SVal Base = UnknownVal();3368 3369    // As in case of this expression the sub-expressions are not visited by any3370    // other transfer functions, they are handled by matching their AST.3371 3372    // Case of implicit copy or move ctor of object with array member3373    //3374    // Note: ExprEngine::VisitMemberExpr is not able to bind the array to the3375    // environment.3376    //3377    //    struct S {3378    //      int arr[2];3379    //    };3380    //3381    //3382    //    S a;3383    //    S b = a;3384    //3385    // The AST in case of a *copy constructor* looks like this:3386    //    ArrayInitLoopExpr3387    //    |-OpaqueValueExpr3388    //    | `-MemberExpr              <-- match this3389    //    |   `-DeclRefExpr3390    //    ` ...3391    //3392    //3393    //    S c;3394    //    S d = std::move(d);3395    //3396    // In case of a *move constructor* the resulting AST looks like:3397    //    ArrayInitLoopExpr3398    //    |-OpaqueValueExpr3399    //    | `-MemberExpr              <-- match this first3400    //    |   `-CXXStaticCastExpr     <-- match this after3401    //    |     `-DeclRefExpr3402    //    ` ...3403    if (const auto *ME = dyn_cast<MemberExpr>(Arr)) {3404      Expr *MEBase = ME->getBase();3405 3406      // Move ctor3407      if (auto CXXSCE = dyn_cast<CXXStaticCastExpr>(MEBase)) {3408        MEBase = CXXSCE->getSubExpr();3409      }3410 3411      auto ObjDeclExpr = cast<DeclRefExpr>(MEBase);3412      SVal Obj = state->getLValue(cast<VarDecl>(ObjDeclExpr->getDecl()), LCtx);3413 3414      Base = state->getLValue(cast<FieldDecl>(ME->getMemberDecl()), Obj);3415    }3416 3417    // Case of lambda capture and decomposition declaration3418    //3419    //    int arr[2];3420    //3421    //    [arr]{ int a = arr[0]; }();3422    //    auto[a, b] = arr;3423    //3424    // In both of these cases the AST looks like the following:3425    //    ArrayInitLoopExpr3426    //    |-OpaqueValueExpr3427    //    | `-DeclRefExpr             <-- match this3428    //    ` ...3429    if (const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(Arr))3430      Base = state->getLValue(cast<VarDecl>(DRE->getDecl()), LCtx);3431 3432    // Create a lazy compound value to the original array3433    if (const MemRegion *R = Base.getAsRegion())3434      Base = state->getSVal(R);3435    else3436      Base = UnknownVal();3437 3438    Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, Base));3439  }3440 3441  getCheckerManager().runCheckersForPostStmt(Dst, EvalSet, Ex, *this);3442}3443 3444/// VisitArraySubscriptExpr - Transfer function for array accesses3445void ExprEngine::VisitArraySubscriptExpr(const ArraySubscriptExpr *A,3446                                             ExplodedNode *Pred,3447                                             ExplodedNodeSet &Dst){3448  const Expr *Base = A->getBase()->IgnoreParens();3449  const Expr *Idx  = A->getIdx()->IgnoreParens();3450 3451  ExplodedNodeSet CheckerPreStmt;3452  getCheckerManager().runCheckersForPreStmt(CheckerPreStmt, Pred, A, *this);3453 3454  ExplodedNodeSet EvalSet;3455  StmtNodeBuilder Bldr(CheckerPreStmt, EvalSet, *currBldrCtx);3456 3457  bool IsVectorType = A->getBase()->getType()->isVectorType();3458 3459  // The "like" case is for situations where C standard prohibits the type to3460  // be an lvalue, e.g. taking the address of a subscript of an expression of3461  // type "void *".3462  bool IsGLValueLike = A->isGLValue() ||3463    (A->getType().isCForbiddenLValueType() && !AMgr.getLangOpts().CPlusPlus);3464 3465  for (auto *Node : CheckerPreStmt) {3466    const LocationContext *LCtx = Node->getLocationContext();3467    ProgramStateRef state = Node->getState();3468 3469    if (IsGLValueLike) {3470      QualType T = A->getType();3471 3472      // One of the forbidden LValue types! We still need to have sensible3473      // symbolic locations to represent this stuff. Note that arithmetic on3474      // void pointers is a GCC extension.3475      if (T->isVoidType())3476        T = getContext().CharTy;3477 3478      SVal V = state->getLValue(T,3479                                state->getSVal(Idx, LCtx),3480                                state->getSVal(Base, LCtx));3481      Bldr.generateNode(A, Node, state->BindExpr(A, LCtx, V), nullptr,3482          ProgramPoint::PostLValueKind);3483    } else if (IsVectorType) {3484      // FIXME: non-glvalue vector reads are not modelled.3485      Bldr.generateNode(A, Node, state, nullptr);3486    } else {3487      llvm_unreachable("Array subscript should be an lValue when not \3488a vector and not a forbidden lvalue type");3489    }3490  }3491 3492  getCheckerManager().runCheckersForPostStmt(Dst, EvalSet, A, *this);3493}3494 3495/// VisitMemberExpr - Transfer function for member expressions.3496void ExprEngine::VisitMemberExpr(const MemberExpr *M, ExplodedNode *Pred,3497                                 ExplodedNodeSet &Dst) {3498  // FIXME: Prechecks eventually go in ::Visit().3499  ExplodedNodeSet CheckedSet;3500  getCheckerManager().runCheckersForPreStmt(CheckedSet, Pred, M, *this);3501 3502  ExplodedNodeSet EvalSet;3503  ValueDecl *Member = M->getMemberDecl();3504 3505  // Handle static member variables and enum constants accessed via3506  // member syntax.3507  if (isa<VarDecl, EnumConstantDecl>(Member)) {3508    for (const auto I : CheckedSet)3509      VisitCommonDeclRefExpr(M, Member, I, EvalSet);3510  } else {3511    StmtNodeBuilder Bldr(CheckedSet, EvalSet, *currBldrCtx);3512    ExplodedNodeSet Tmp;3513 3514    for (const auto I : CheckedSet) {3515      ProgramStateRef state = I->getState();3516      const LocationContext *LCtx = I->getLocationContext();3517      Expr *BaseExpr = M->getBase();3518 3519      // Handle C++ method calls.3520      if (const auto *MD = dyn_cast<CXXMethodDecl>(Member)) {3521        if (MD->isImplicitObjectMemberFunction())3522          state = createTemporaryRegionIfNeeded(state, LCtx, BaseExpr);3523 3524        SVal MDVal = svalBuilder.getFunctionPointer(MD);3525        state = state->BindExpr(M, LCtx, MDVal);3526 3527        Bldr.generateNode(M, I, state);3528        continue;3529      }3530 3531      // Handle regular struct fields / member variables.3532      const SubRegion *MR = nullptr;3533      state = createTemporaryRegionIfNeeded(state, LCtx, BaseExpr,3534                                            /*Result=*/nullptr,3535                                            /*OutRegionWithAdjustments=*/&MR);3536      SVal baseExprVal =3537          MR ? loc::MemRegionVal(MR) : state->getSVal(BaseExpr, LCtx);3538 3539      // FIXME: Copied from RegionStoreManager::bind()3540      if (const auto *SR =3541              dyn_cast_or_null<SymbolicRegion>(baseExprVal.getAsRegion())) {3542        QualType T = SR->getPointeeStaticType();3543        baseExprVal =3544            loc::MemRegionVal(getStoreManager().GetElementZeroRegion(SR, T));3545      }3546 3547      const auto *field = cast<FieldDecl>(Member);3548      SVal L = state->getLValue(field, baseExprVal);3549 3550      if (M->isGLValue() || M->getType()->isArrayType()) {3551        // We special-case rvalues of array type because the analyzer cannot3552        // reason about them, since we expect all regions to be wrapped in Locs.3553        // We instead treat these as lvalues and assume that they will decay to3554        // pointers as soon as they are used.3555        if (!M->isGLValue()) {3556          assert(M->getType()->isArrayType());3557          const auto *PE =3558            dyn_cast<ImplicitCastExpr>(I->getParentMap().getParentIgnoreParens(M));3559          if (!PE || PE->getCastKind() != CK_ArrayToPointerDecay) {3560            llvm_unreachable("should always be wrapped in ArrayToPointerDecay");3561          }3562        }3563 3564        if (field->getType()->isReferenceType()) {3565          if (const MemRegion *R = L.getAsRegion())3566            L = state->getSVal(R);3567          else3568            L = UnknownVal();3569        }3570 3571        Bldr.generateNode(M, I, state->BindExpr(M, LCtx, L), nullptr,3572                          ProgramPoint::PostLValueKind);3573      } else {3574        Bldr.takeNodes(I);3575        evalLoad(Tmp, M, M, I, state, L);3576        Bldr.addNodes(Tmp);3577      }3578    }3579  }3580 3581  getCheckerManager().runCheckersForPostStmt(Dst, EvalSet, M, *this);3582}3583 3584void ExprEngine::VisitAtomicExpr(const AtomicExpr *AE, ExplodedNode *Pred,3585                                 ExplodedNodeSet &Dst) {3586  ExplodedNodeSet AfterPreSet;3587  getCheckerManager().runCheckersForPreStmt(AfterPreSet, Pred, AE, *this);3588 3589  // For now, treat all the arguments to C11 atomics as escaping.3590  // FIXME: Ideally we should model the behavior of the atomics precisely here.3591 3592  ExplodedNodeSet AfterInvalidateSet;3593  StmtNodeBuilder Bldr(AfterPreSet, AfterInvalidateSet, *currBldrCtx);3594 3595  for (const auto I : AfterPreSet) {3596    ProgramStateRef State = I->getState();3597    const LocationContext *LCtx = I->getLocationContext();3598 3599    SmallVector<SVal, 8> ValuesToInvalidate;3600    for (unsigned SI = 0, Count = AE->getNumSubExprs(); SI != Count; SI++) {3601      const Expr *SubExpr = AE->getSubExprs()[SI];3602      SVal SubExprVal = State->getSVal(SubExpr, LCtx);3603      ValuesToInvalidate.push_back(SubExprVal);3604    }3605 3606    State = State->invalidateRegions(ValuesToInvalidate, getCFGElementRef(),3607                                     currBldrCtx->blockCount(), LCtx,3608                                     /*CausedByPointerEscape*/ true,3609                                     /*Symbols=*/nullptr);3610 3611    SVal ResultVal = UnknownVal();3612    State = State->BindExpr(AE, LCtx, ResultVal);3613    Bldr.generateNode(AE, I, State, nullptr,3614                      ProgramPoint::PostStmtKind);3615  }3616 3617  getCheckerManager().runCheckersForPostStmt(Dst, AfterInvalidateSet, AE, *this);3618}3619 3620// A value escapes in four possible cases:3621// (1) We are binding to something that is not a memory region.3622// (2) We are binding to a MemRegion that does not have stack storage.3623// (3) We are binding to a top-level parameter region with a non-trivial3624//     destructor. We won't see the destructor during analysis, but it's there.3625// (4) We are binding to a MemRegion with stack storage that the store3626//     does not understand.3627ProgramStateRef ExprEngine::processPointerEscapedOnBind(3628    ProgramStateRef State, ArrayRef<std::pair<SVal, SVal>> LocAndVals,3629    const LocationContext *LCtx, PointerEscapeKind Kind,3630    const CallEvent *Call) {3631  SmallVector<SVal, 8> Escaped;3632  for (const std::pair<SVal, SVal> &LocAndVal : LocAndVals) {3633    // Cases (1) and (2).3634    const MemRegion *MR = LocAndVal.first.getAsRegion();3635    const MemSpaceRegion *Space = MR ? MR->getMemorySpace(State) : nullptr;3636    if (!MR || !isa<StackSpaceRegion, StaticGlobalSpaceRegion>(Space)) {3637      Escaped.push_back(LocAndVal.second);3638      continue;3639    }3640 3641    // Case (3).3642    if (const auto *VR = dyn_cast<VarRegion>(MR->getBaseRegion()))3643      if (isa<StackArgumentsSpaceRegion>(Space) &&3644          VR->getStackFrame()->inTopFrame())3645        if (const auto *RD = VR->getValueType()->getAsCXXRecordDecl())3646          if (!RD->hasTrivialDestructor()) {3647            Escaped.push_back(LocAndVal.second);3648            continue;3649          }3650 3651    // Case (4): in order to test that, generate a new state with the binding3652    // added. If it is the same state, then it escapes (since the store cannot3653    // represent the binding).3654    // Do this only if we know that the store is not supposed to generate the3655    // same state.3656    SVal StoredVal = State->getSVal(MR);3657    if (StoredVal != LocAndVal.second)3658      if (State ==3659          (State->bindLoc(loc::MemRegionVal(MR), LocAndVal.second, LCtx)))3660        Escaped.push_back(LocAndVal.second);3661  }3662 3663  if (Escaped.empty())3664    return State;3665 3666  return escapeValues(State, Escaped, Kind, Call);3667}3668 3669ProgramStateRef3670ExprEngine::processPointerEscapedOnBind(ProgramStateRef State, SVal Loc,3671                                        SVal Val, const LocationContext *LCtx) {3672  std::pair<SVal, SVal> LocAndVal(Loc, Val);3673  return processPointerEscapedOnBind(State, LocAndVal, LCtx, PSK_EscapeOnBind,3674                                     nullptr);3675}3676 3677ProgramStateRef3678ExprEngine::notifyCheckersOfPointerEscape(ProgramStateRef State,3679    const InvalidatedSymbols *Invalidated,3680    ArrayRef<const MemRegion *> ExplicitRegions,3681    const CallEvent *Call,3682    RegionAndSymbolInvalidationTraits &ITraits) {3683  if (!Invalidated || Invalidated->empty())3684    return State;3685 3686  if (!Call)3687    return getCheckerManager().runCheckersForPointerEscape(State,3688                                                           *Invalidated,3689                                                           nullptr,3690                                                           PSK_EscapeOther,3691                                                           &ITraits);3692 3693  // If the symbols were invalidated by a call, we want to find out which ones3694  // were invalidated directly due to being arguments to the call.3695  InvalidatedSymbols SymbolsDirectlyInvalidated;3696  for (const auto I : ExplicitRegions) {3697    if (const SymbolicRegion *R = I->StripCasts()->getAs<SymbolicRegion>())3698      SymbolsDirectlyInvalidated.insert(R->getSymbol());3699  }3700 3701  InvalidatedSymbols SymbolsIndirectlyInvalidated;3702  for (const auto &sym : *Invalidated) {3703    if (SymbolsDirectlyInvalidated.count(sym))3704      continue;3705    SymbolsIndirectlyInvalidated.insert(sym);3706  }3707 3708  if (!SymbolsDirectlyInvalidated.empty())3709    State = getCheckerManager().runCheckersForPointerEscape(State,3710        SymbolsDirectlyInvalidated, Call, PSK_DirectEscapeOnCall, &ITraits);3711 3712  // Notify about the symbols that get indirectly invalidated by the call.3713  if (!SymbolsIndirectlyInvalidated.empty())3714    State = getCheckerManager().runCheckersForPointerEscape(State,3715        SymbolsIndirectlyInvalidated, Call, PSK_IndirectEscapeOnCall, &ITraits);3716 3717  return State;3718}3719 3720/// evalBind - Handle the semantics of binding a value to a specific location.3721///  This method is used by evalStore and (soon) VisitDeclStmt, and others.3722void ExprEngine::evalBind(ExplodedNodeSet &Dst, const Stmt *StoreE,3723                          ExplodedNode *Pred, SVal location, SVal Val,3724                          bool AtDeclInit, const ProgramPoint *PP) {3725  const LocationContext *LC = Pred->getLocationContext();3726  PostStmt PS(StoreE, LC);3727  if (!PP)3728    PP = &PS;3729 3730  // Do a previsit of the bind.3731  ExplodedNodeSet CheckedSet;3732  getCheckerManager().runCheckersForBind(CheckedSet, Pred, location, Val,3733                                         StoreE, AtDeclInit, *this, *PP);3734 3735  StmtNodeBuilder Bldr(CheckedSet, Dst, *currBldrCtx);3736 3737  // If the location is not a 'Loc', it will already be handled by3738  // the checkers.  There is nothing left to do.3739  if (!isa<Loc>(location)) {3740    const ProgramPoint L = PostStore(StoreE, LC, /*Loc*/nullptr,3741                                     /*tag*/nullptr);3742    ProgramStateRef state = Pred->getState();3743    state = processPointerEscapedOnBind(state, location, Val, LC);3744    Bldr.generateNode(L, state, Pred);3745    return;3746  }3747 3748  for (const auto PredI : CheckedSet) {3749    ProgramStateRef state = PredI->getState();3750 3751    state = processPointerEscapedOnBind(state, location, Val, LC);3752 3753    // When binding the value, pass on the hint that this is a initialization.3754    // For initializations, we do not need to inform clients of region3755    // changes.3756    state = state->bindLoc(location.castAs<Loc>(), Val, LC,3757                           /* notifyChanges = */ !AtDeclInit);3758 3759    const MemRegion *LocReg = nullptr;3760    if (std::optional<loc::MemRegionVal> LocRegVal =3761            location.getAs<loc::MemRegionVal>()) {3762      LocReg = LocRegVal->getRegion();3763    }3764 3765    const ProgramPoint L = PostStore(StoreE, LC, LocReg, nullptr);3766    Bldr.generateNode(L, state, PredI);3767  }3768}3769 3770/// evalStore - Handle the semantics of a store via an assignment.3771///  @param Dst The node set to store generated state nodes3772///  @param AssignE The assignment expression if the store happens in an3773///         assignment.3774///  @param LocationE The location expression that is stored to.3775///  @param state The current simulation state3776///  @param location The location to store the value3777///  @param Val The value to be stored3778void ExprEngine::evalStore(ExplodedNodeSet &Dst, const Expr *AssignE,3779                             const Expr *LocationE,3780                             ExplodedNode *Pred,3781                             ProgramStateRef state, SVal location, SVal Val,3782                             const ProgramPointTag *tag) {3783  // Proceed with the store.  We use AssignE as the anchor for the PostStore3784  // ProgramPoint if it is non-NULL, and LocationE otherwise.3785  const Expr *StoreE = AssignE ? AssignE : LocationE;3786 3787  // Evaluate the location (checks for bad dereferences).3788  ExplodedNodeSet Tmp;3789  evalLocation(Tmp, AssignE, LocationE, Pred, state, location, false);3790 3791  if (Tmp.empty())3792    return;3793 3794  if (location.isUndef())3795    return;3796 3797  for (const auto I : Tmp)3798    evalBind(Dst, StoreE, I, location, Val, false);3799}3800 3801void ExprEngine::evalLoad(ExplodedNodeSet &Dst,3802                          const Expr *NodeEx,3803                          const Expr *BoundEx,3804                          ExplodedNode *Pred,3805                          ProgramStateRef state,3806                          SVal location,3807                          const ProgramPointTag *tag,3808                          QualType LoadTy) {3809  assert(!isa<NonLoc>(location) && "location cannot be a NonLoc.");3810  assert(NodeEx);3811  assert(BoundEx);3812  // Evaluate the location (checks for bad dereferences).3813  ExplodedNodeSet Tmp;3814  evalLocation(Tmp, NodeEx, BoundEx, Pred, state, location, true);3815  if (Tmp.empty())3816    return;3817 3818  StmtNodeBuilder Bldr(Tmp, Dst, *currBldrCtx);3819  if (location.isUndef())3820    return;3821 3822  // Proceed with the load.3823  for (const auto I : Tmp) {3824    state = I->getState();3825    const LocationContext *LCtx = I->getLocationContext();3826 3827    SVal V = UnknownVal();3828    if (location.isValid()) {3829      if (LoadTy.isNull())3830        LoadTy = BoundEx->getType();3831      V = state->getSVal(location.castAs<Loc>(), LoadTy);3832    }3833 3834    Bldr.generateNode(NodeEx, I, state->BindExpr(BoundEx, LCtx, V), tag,3835                      ProgramPoint::PostLoadKind);3836  }3837}3838 3839void ExprEngine::evalLocation(ExplodedNodeSet &Dst,3840                              const Stmt *NodeEx,3841                              const Stmt *BoundEx,3842                              ExplodedNode *Pred,3843                              ProgramStateRef state,3844                              SVal location,3845                              bool isLoad) {3846  StmtNodeBuilder BldrTop(Pred, Dst, *currBldrCtx);3847  // Early checks for performance reason.3848  if (location.isUnknown()) {3849    return;3850  }3851 3852  ExplodedNodeSet Src;3853  BldrTop.takeNodes(Pred);3854  StmtNodeBuilder Bldr(Pred, Src, *currBldrCtx);3855  if (Pred->getState() != state) {3856    // Associate this new state with an ExplodedNode.3857    // FIXME: If I pass null tag, the graph is incorrect, e.g for3858    //   int *p;3859    //   p = 0;3860    //   *p = 0xDEADBEEF;3861    // "p = 0" is not noted as "Null pointer value stored to 'p'" but3862    // instead "int *p" is noted as3863    // "Variable 'p' initialized to a null pointer value"3864 3865    static SimpleProgramPointTag tag(TagProviderName, "Location");3866    Bldr.generateNode(NodeEx, Pred, state, &tag);3867  }3868  ExplodedNodeSet Tmp;3869  getCheckerManager().runCheckersForLocation(Tmp, Src, location, isLoad,3870                                             NodeEx, BoundEx, *this);3871  BldrTop.addNodes(Tmp);3872}3873 3874std::pair<const ProgramPointTag *, const ProgramPointTag *>3875ExprEngine::getEagerlyAssumeBifurcationTags() {3876  static SimpleProgramPointTag TrueTag(TagProviderName, "Eagerly Assume True"),3877      FalseTag(TagProviderName, "Eagerly Assume False");3878 3879  return std::make_pair(&TrueTag, &FalseTag);3880}3881 3882/// If the last EagerlyAssume attempt was successful (i.e. the true and false3883/// cases were both feasible), this state trait stores the expression where it3884/// happened; otherwise this holds nullptr.3885REGISTER_TRAIT_WITH_PROGRAMSTATE(LastEagerlyAssumeExprIfSuccessful,3886                                 const Expr *)3887 3888void ExprEngine::evalEagerlyAssumeBifurcation(ExplodedNodeSet &Dst,3889                                              ExplodedNodeSet &Src,3890                                              const Expr *Ex) {3891  StmtNodeBuilder Bldr(Src, Dst, *currBldrCtx);3892 3893  for (ExplodedNode *Pred : Src) {3894    // Test if the previous node was as the same expression.  This can happen3895    // when the expression fails to evaluate to anything meaningful and3896    // (as an optimization) we don't generate a node.3897    ProgramPoint P = Pred->getLocation();3898    if (!P.getAs<PostStmt>() || P.castAs<PostStmt>().getStmt() != Ex) {3899      continue;3900    }3901 3902    ProgramStateRef State = Pred->getState();3903    State = State->set<LastEagerlyAssumeExprIfSuccessful>(nullptr);3904    SVal V = State->getSVal(Ex, Pred->getLocationContext());3905    std::optional<nonloc::SymbolVal> SEV = V.getAs<nonloc::SymbolVal>();3906    if (SEV && SEV->isExpression()) {3907      const auto &[TrueTag, FalseTag] = getEagerlyAssumeBifurcationTags();3908 3909      auto [StateTrue, StateFalse] = State->assume(*SEV);3910 3911      if (StateTrue && StateFalse) {3912        StateTrue = StateTrue->set<LastEagerlyAssumeExprIfSuccessful>(Ex);3913        StateFalse = StateFalse->set<LastEagerlyAssumeExprIfSuccessful>(Ex);3914      }3915 3916      // First assume that the condition is true.3917      if (StateTrue) {3918        SVal Val = svalBuilder.makeIntVal(1U, Ex->getType());3919        StateTrue = StateTrue->BindExpr(Ex, Pred->getLocationContext(), Val);3920        Bldr.generateNode(Ex, Pred, StateTrue, TrueTag);3921      }3922 3923      // Next, assume that the condition is false.3924      if (StateFalse) {3925        SVal Val = svalBuilder.makeIntVal(0U, Ex->getType());3926        StateFalse = StateFalse->BindExpr(Ex, Pred->getLocationContext(), Val);3927        Bldr.generateNode(Ex, Pred, StateFalse, FalseTag);3928      }3929    }3930  }3931}3932 3933bool ExprEngine::didEagerlyAssumeBifurcateAt(ProgramStateRef State,3934                                             const Expr *Ex) const {3935  return Ex && State->get<LastEagerlyAssumeExprIfSuccessful>() == Ex;3936}3937 3938void ExprEngine::VisitGCCAsmStmt(const GCCAsmStmt *A, ExplodedNode *Pred,3939                                 ExplodedNodeSet &Dst) {3940  StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);3941  // We have processed both the inputs and the outputs.  All of the outputs3942  // should evaluate to Locs.  Nuke all of their values.3943 3944  // FIXME: Some day in the future it would be nice to allow a "plug-in"3945  // which interprets the inline asm and stores proper results in the3946  // outputs.3947 3948  ProgramStateRef state = Pred->getState();3949 3950  for (const Expr *O : A->outputs()) {3951    SVal X = state->getSVal(O, Pred->getLocationContext());3952    assert(!isa<NonLoc>(X)); // Should be an Lval, or unknown, undef.3953 3954    if (std::optional<Loc> LV = X.getAs<Loc>())3955      state = state->invalidateRegions(*LV, getCFGElementRef(),3956                                       currBldrCtx->blockCount(),3957                                       Pred->getLocationContext(),3958                                       /*CausedByPointerEscape=*/true);3959  }3960 3961  // Do not reason about locations passed inside inline assembly.3962  for (const Expr *I : A->inputs()) {3963    SVal X = state->getSVal(I, Pred->getLocationContext());3964 3965    if (std::optional<Loc> LV = X.getAs<Loc>())3966      state = state->invalidateRegions(*LV, getCFGElementRef(),3967                                       currBldrCtx->blockCount(),3968                                       Pred->getLocationContext(),3969                                       /*CausedByPointerEscape=*/true);3970  }3971 3972  Bldr.generateNode(A, Pred, state);3973}3974 3975void ExprEngine::VisitMSAsmStmt(const MSAsmStmt *A, ExplodedNode *Pred,3976                                ExplodedNodeSet &Dst) {3977  StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);3978  Bldr.generateNode(A, Pred, Pred->getState());3979}3980 3981//===----------------------------------------------------------------------===//3982// Visualization.3983//===----------------------------------------------------------------------===//3984 3985namespace llvm {3986 3987template<>3988struct DOTGraphTraits<ExplodedGraph*> : public DefaultDOTGraphTraits {3989  DOTGraphTraits (bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}3990 3991  static bool nodeHasBugReport(const ExplodedNode *N) {3992    BugReporter &BR = static_cast<ExprEngine &>(3993      N->getState()->getStateManager().getOwningEngine()).getBugReporter();3994 3995    for (const auto &Class : BR.equivalenceClasses()) {3996      for (const auto &Report : Class.getReports()) {3997        const auto *PR = dyn_cast<PathSensitiveBugReport>(Report.get());3998        if (!PR)3999          continue;4000        const ExplodedNode *EN = PR->getErrorNode();4001        if (EN->getState() == N->getState() &&4002            EN->getLocation() == N->getLocation())4003          return true;4004      }4005    }4006    return false;4007  }4008 4009  /// \p PreCallback: callback before break.4010  /// \p PostCallback: callback after break.4011  /// \p Stop: stop iteration if returns @c true4012  /// \return Whether @c Stop ever returned @c true.4013  static bool traverseHiddenNodes(4014      const ExplodedNode *N,4015      llvm::function_ref<void(const ExplodedNode *)> PreCallback,4016      llvm::function_ref<void(const ExplodedNode *)> PostCallback,4017      llvm::function_ref<bool(const ExplodedNode *)> Stop) {4018    while (true) {4019      PreCallback(N);4020      if (Stop(N))4021        return true;4022 4023      if (N->succ_size() != 1 || !isNodeHidden(N->getFirstSucc(), nullptr))4024        break;4025      PostCallback(N);4026 4027      N = N->getFirstSucc();4028    }4029    return false;4030  }4031 4032  static bool isNodeHidden(const ExplodedNode *N, const ExplodedGraph *G) {4033    return N->isTrivial();4034  }4035 4036  static std::string getNodeLabel(const ExplodedNode *N, ExplodedGraph *G){4037    std::string Buf;4038    llvm::raw_string_ostream Out(Buf);4039 4040    const bool IsDot = true;4041    const unsigned int Space = 1;4042    ProgramStateRef State = N->getState();4043 4044    Out << "{ \"state_id\": " << State->getID()4045        << ",\\l";4046 4047    Indent(Out, Space, IsDot) << "\"program_points\": [\\l";4048 4049    // Dump program point for all the previously skipped nodes.4050    traverseHiddenNodes(4051        N,4052        [&](const ExplodedNode *OtherNode) {4053          Indent(Out, Space + 1, IsDot) << "{ ";4054          OtherNode->getLocation().printJson(Out, /*NL=*/"\\l");4055          Out << ", \"tag\": ";4056          if (const ProgramPointTag *Tag = OtherNode->getLocation().getTag())4057            Out << '\"' << Tag->getDebugTag() << '\"';4058          else4059            Out << "null";4060          Out << ", \"node_id\": " << OtherNode->getID() <<4061                 ", \"is_sink\": " << OtherNode->isSink() <<4062                 ", \"has_report\": " << nodeHasBugReport(OtherNode) << " }";4063        },4064        // Adds a comma and a new-line between each program point.4065        [&](const ExplodedNode *) { Out << ",\\l"; },4066        [&](const ExplodedNode *) { return false; });4067 4068    Out << "\\l"; // Adds a new-line to the last program point.4069    Indent(Out, Space, IsDot) << "],\\l";4070 4071    State->printDOT(Out, N->getLocationContext(), Space);4072 4073    Out << "\\l}\\l";4074    return Buf;4075  }4076};4077 4078} // namespace llvm4079 4080void ExprEngine::ViewGraph(bool trim) {4081  std::string Filename = DumpGraph(trim);4082  llvm::DisplayGraph(Filename, false, llvm::GraphProgram::DOT);4083}4084 4085void ExprEngine::ViewGraph(ArrayRef<const ExplodedNode *> Nodes) {4086  std::string Filename = DumpGraph(Nodes);4087  llvm::DisplayGraph(Filename, false, llvm::GraphProgram::DOT);4088}4089 4090std::string ExprEngine::DumpGraph(bool trim, StringRef Filename) {4091  if (trim) {4092    std::vector<const ExplodedNode *> Src;4093 4094    // Iterate through the reports and get their nodes.4095    for (const auto &Class : BR.equivalenceClasses()) {4096      const auto *R =4097          dyn_cast<PathSensitiveBugReport>(Class.getReports()[0].get());4098      if (!R)4099        continue;4100      const auto *N = const_cast<ExplodedNode *>(R->getErrorNode());4101      Src.push_back(N);4102    }4103    return DumpGraph(Src, Filename);4104  }4105 4106  return llvm::WriteGraph(&G, "ExprEngine", /*ShortNames=*/false,4107                          /*Title=*/"Exploded Graph",4108                          /*Filename=*/std::string(Filename));4109}4110 4111std::string ExprEngine::DumpGraph(ArrayRef<const ExplodedNode *> Nodes,4112                                  StringRef Filename) {4113  std::unique_ptr<ExplodedGraph> TrimmedG(G.trim(Nodes));4114 4115  if (!TrimmedG) {4116    llvm::errs() << "warning: Trimmed ExplodedGraph is empty.\n";4117    return "";4118  }4119 4120  return llvm::WriteGraph(TrimmedG.get(), "TrimmedExprEngine",4121                          /*ShortNames=*/false,4122                          /*Title=*/"Trimmed Exploded Graph",4123                          /*Filename=*/std::string(Filename));4124}4125 4126void *ProgramStateTrait<ReplayWithoutInlining>::GDMIndex() {4127  static int index = 0;4128  return &index;4129}4130 4131void ExprEngine::anchor() { }4132 4133void ExprEngine::ConstructInitList(const Expr *E, ArrayRef<Expr *> Args,4134                                   bool IsTransparent, ExplodedNode *Pred,4135                                   ExplodedNodeSet &Dst) {4136  assert((isa<InitListExpr, CXXParenListInitExpr>(E)));4137 4138  const LocationContext *LC = Pred->getLocationContext();4139 4140  StmtNodeBuilder B(Pred, Dst, *currBldrCtx);4141  ProgramStateRef S = Pred->getState();4142  QualType T = E->getType().getCanonicalType();4143 4144  bool IsCompound = T->isArrayType() || T->isRecordType() ||4145                    T->isAnyComplexType() || T->isVectorType();4146 4147  if (Args.size() > 1 || (E->isPRValue() && IsCompound && !IsTransparent)) {4148    llvm::ImmutableList<SVal> ArgList = getBasicVals().getEmptySValList();4149    for (Expr *E : llvm::reverse(Args))4150      ArgList = getBasicVals().prependSVal(S->getSVal(E, LC), ArgList);4151 4152    B.generateNode(E, Pred,4153                   S->BindExpr(E, LC, svalBuilder.makeCompoundVal(T, ArgList)));4154  } else {4155    B.generateNode(E, Pred,4156                   S->BindExpr(E, LC,4157                               Args.size() == 04158                                   ? getSValBuilder().makeZeroVal(T)4159                                   : S->getSVal(Args.front(), LC)));4160  }4161}4162