clang/lib/StaticAnalyzer/Core/CallEvent.cpp

   1 //===- CallEvent.cpp - Wrapper for all function and method calls ----------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 /// \file This file defines CallEvent and its subclasses, which represent path-
  10 /// sensitive instances of different kinds of function and method calls
  11 /// (C, C++, and Objective-C).
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
  16 #include "clang/AST/ASTContext.h"
  17 #include "clang/AST/Attr.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/Stmt.h"
  27 #include "clang/AST/Type.h"
  28 #include "clang/Analysis/AnalysisDeclContext.h"
  29 #include "clang/Analysis/CFG.h"
  30 #include "clang/Analysis/CFGStmtMap.h"
  31 #include "clang/Analysis/PathDiagnostic.h"
  32 #include "clang/Analysis/ProgramPoint.h"
  33 #include "clang/Basic/IdentifierTable.h"
  34 #include "clang/Basic/LLVM.h"
  35 #include "clang/Basic/SourceLocation.h"
  36 #include "clang/Basic/SourceManager.h"
  37 #include "clang/Basic/Specifiers.h"
  38 #include "clang/CrossTU/CrossTranslationUnit.h"
  39 #include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h"
  40 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
  41 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h"
  42 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicTypeInfo.h"
  43 #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
  44 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
  45 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h"
  46 #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
  47 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
  48 #include "clang/StaticAnalyzer/Core/PathSensitive/Store.h"
  49 #include "llvm/ADT/ArrayRef.h"
  50 #include "llvm/ADT/DenseMap.h"
  51 #include "llvm/ADT/ImmutableList.h"
  52 #include "llvm/ADT/PointerIntPair.h"
  53 #include "llvm/ADT/SmallSet.h"
  54 #include "llvm/ADT/SmallVector.h"
  55 #include "llvm/ADT/StringExtras.h"
  56 #include "llvm/ADT/StringRef.h"
  57 #include "llvm/Support/Casting.h"
  58 #include "llvm/Support/Compiler.h"
  59 #include "llvm/Support/Debug.h"
  60 #include "llvm/Support/ErrorHandling.h"
  61 #include "llvm/Support/raw_ostream.h"
  62 #include <cassert>
  63 #include <optional>
  64 #include <utility>
  65
  66 #define DEBUG_TYPE "static-analyzer-call-event"
  67
  68 using namespace clang;
  69 using namespace ento;
  70
  71 QualType CallEvent::getResultType() const {
  72   ASTContext &Ctx = getState()->getStateManager().getContext();
  73   const Expr *E = getOriginExpr();
  74   if (!E)
  75     return Ctx.VoidTy;
  76   return Ctx.getReferenceQualifiedType(E);
  77 }
  78
  79 static bool isCallback(QualType T) {
  80   // If a parameter is a block or a callback, assume it can modify pointer.
  81   if (T->isBlockPointerType() ||
  82       T->isFunctionPointerType() ||
  83       T->isObjCSelType())
  84     return true;
  85
  86   // Check if a callback is passed inside a struct (for both, struct passed by
  87   // reference and by value). Dig just one level into the struct for now.
  88
  89   if (T->isAnyPointerType() || T->isReferenceType())
  90     T = T->getPointeeType();
  91
  92   if (const RecordType *RT = T->getAsStructureType()) {
  93     const RecordDecl *RD = RT->getDecl();
  94     for (const auto *I : RD->fields()) {
  95       QualType FieldT = I->getType();
  96       if (FieldT->isBlockPointerType() || FieldT->isFunctionPointerType())
  97         return true;
  98     }
  99   }
 100   return false;
 101 }
 102
 103 static bool isVoidPointerToNonConst(QualType T) {
 104   if (const auto *PT = T->getAs<PointerType>()) {
 105     QualType PointeeTy = PT->getPointeeType();
 106     if (PointeeTy.isConstQualified())
 107       return false;
 108     return PointeeTy->isVoidType();
 109   } else
 110     return false;
 111 }
 112
 113 bool CallEvent::hasNonNullArgumentsWithType(bool (*Condition)(QualType)) const {
 114   unsigned NumOfArgs = getNumArgs();
 115
 116   // If calling using a function pointer, assume the function does not
 117   // satisfy the callback.
 118   // TODO: We could check the types of the arguments here.
 119   if (!getDecl())
 120     return false;
 121
 122   unsigned Idx = 0;
 123   for (CallEvent::param_type_iterator I = param_type_begin(),
 124                                       E = param_type_end();
 125        I != E && Idx < NumOfArgs; ++I, ++Idx) {
 126     // If the parameter is 0, it's harmless.
 127     if (getArgSVal(Idx).isZeroConstant())
 128       continue;
 129
 130     if (Condition(*I))
 131       return true;
 132   }
 133   return false;
 134 }
 135
 136 bool CallEvent::hasNonZeroCallbackArg() const {
 137   return hasNonNullArgumentsWithType(isCallback);
 138 }
 139
 140 bool CallEvent::hasVoidPointerToNonConstArg() const {
 141   return hasNonNullArgumentsWithType(isVoidPointerToNonConst);
 142 }
 143
 144 bool CallEvent::isGlobalCFunction(StringRef FunctionName) const {
 145   const auto *FD = dyn_cast_or_null<FunctionDecl>(getDecl());
 146   if (!FD)
 147     return false;
 148
 149   return CheckerContext::isCLibraryFunction(FD, FunctionName);
 150 }
 151
 152 AnalysisDeclContext *CallEvent::getCalleeAnalysisDeclContext() const {
 153   const Decl *D = getDecl();
 154   if (!D)
 155     return nullptr;
 156
 157   AnalysisDeclContext *ADC =
 158       LCtx->getAnalysisDeclContext()->getManager()->getContext(D);
 159
 160   return ADC;
 161 }
 162
 163 const StackFrameContext *
 164 CallEvent::getCalleeStackFrame(unsigned BlockCount) const {
 165   AnalysisDeclContext *ADC = getCalleeAnalysisDeclContext();
 166   if (!ADC)
 167     return nullptr;
 168
 169   const Expr *E = getOriginExpr();
 170   if (!E)
 171     return nullptr;
 172
 173   // Recover CFG block via reverse lookup.
 174   // TODO: If we were to keep CFG element information as part of the CallEvent
 175   // instead of doing this reverse lookup, we would be able to build the stack
 176   // frame for non-expression-based calls, and also we wouldn't need the reverse
 177   // lookup.
 178   CFGStmtMap *Map = LCtx->getAnalysisDeclContext()->getCFGStmtMap();
 179   const CFGBlock *B = Map->getBlock(E);
 180   assert(B);
 181
 182   // Also recover CFG index by scanning the CFG block.
 183   unsigned Idx = 0, Sz = B->size();
 184   for (; Idx < Sz; ++Idx)
 185     if (auto StmtElem = (*B)[Idx].getAs<CFGStmt>())
 186       if (StmtElem->getStmt() == E)
 187         break;
 188   assert(Idx < Sz);
 189
 190   return ADC->getManager()->getStackFrame(ADC, LCtx, E, B, BlockCount, Idx);
 191 }
 192
 193 const ParamVarRegion
 194 *CallEvent::getParameterLocation(unsigned Index, unsigned BlockCount) const {
 195   const StackFrameContext *SFC = getCalleeStackFrame(BlockCount);
 196   // We cannot construct a VarRegion without a stack frame.
 197   if (!SFC)
 198     return nullptr;
 199
 200   const ParamVarRegion *PVR =
 201     State->getStateManager().getRegionManager().getParamVarRegion(
 202         getOriginExpr(), Index, SFC);
 203   return PVR;
 204 }
 205
 206 /// Returns true if a type is a pointer-to-const or reference-to-const
 207 /// with no further indirection.
 208 static bool isPointerToConst(QualType Ty) {
 209   QualType PointeeTy = Ty->getPointeeType();
 210   if (PointeeTy == QualType())
 211     return false;
 212   if (!PointeeTy.isConstQualified())
 213     return false;
 214   if (PointeeTy->isAnyPointerType())
 215     return false;
 216   return true;
 217 }
 218
 219 // Try to retrieve the function declaration and find the function parameter
 220 // types which are pointers/references to a non-pointer const.
 221 // We will not invalidate the corresponding argument regions.
 222 static void findPtrToConstParams(llvm::SmallSet<unsigned, 4> &PreserveArgs,
 223                                  const CallEvent &Call) {
 224   unsigned Idx = 0;
 225   for (CallEvent::param_type_iterator I = Call.param_type_begin(),
 226                                       E = Call.param_type_end();
 227        I != E; ++I, ++Idx) {
 228     if (isPointerToConst(*I))
 229       PreserveArgs.insert(Idx);
 230   }
 231 }
 232
 233 ProgramStateRef CallEvent::invalidateRegions(unsigned BlockCount,
 234                                              ProgramStateRef Orig) const {
 235   ProgramStateRef Result = (Orig ? Orig : getState());
 236
 237   // Don't invalidate anything if the callee is marked pure/const.
 238   if (const Decl *callee = getDecl())
 239     if (callee->hasAttr<PureAttr>() || callee->hasAttr<ConstAttr>())
 240       return Result;
 241
 242   SmallVector<SVal, 8> ValuesToInvalidate;
 243   RegionAndSymbolInvalidationTraits ETraits;
 244
 245   getExtraInvalidatedValues(ValuesToInvalidate, &ETraits);
 246
 247   // Indexes of arguments whose values will be preserved by the call.
 248   llvm::SmallSet<unsigned, 4> PreserveArgs;
 249   if (!argumentsMayEscape())
 250     findPtrToConstParams(PreserveArgs, *this);
 251
 252   for (unsigned Idx = 0, Count = getNumArgs(); Idx != Count; ++Idx) {
 253     // Mark this region for invalidation.  We batch invalidate regions
 254     // below for efficiency.
 255     if (PreserveArgs.count(Idx))
 256       if (const MemRegion *MR = getArgSVal(Idx).getAsRegion())
 257         ETraits.setTrait(MR->getBaseRegion(),
 258                         RegionAndSymbolInvalidationTraits::TK_PreserveContents);
 259         // TODO: Factor this out + handle the lower level const pointers.
 260
 261     ValuesToInvalidate.push_back(getArgSVal(Idx));
 262
 263     // If a function accepts an object by argument (which would of course be a
 264     // temporary that isn't lifetime-extended), invalidate the object itself,
 265     // not only other objects reachable from it. This is necessary because the
 266     // destructor has access to the temporary object after the call.
 267     // TODO: Support placement arguments once we start
 268     // constructing them directly.
 269     // TODO: This is unnecessary when there's no destructor, but that's
 270     // currently hard to figure out.
 271     if (getKind() != CE_CXXAllocator)
 272       if (isArgumentConstructedDirectly(Idx))
 273         if (auto AdjIdx = getAdjustedParameterIndex(Idx))
 274           if (const TypedValueRegion *TVR =
 275                   getParameterLocation(*AdjIdx, BlockCount))
 276             ValuesToInvalidate.push_back(loc::MemRegionVal(TVR));
 277   }
 278
 279   // Invalidate designated regions using the batch invalidation API.
 280   // NOTE: Even if RegionsToInvalidate is empty, we may still invalidate
 281   //  global variables.
 282   return Result->invalidateRegions(ValuesToInvalidate, getOriginExpr(),
 283                                    BlockCount, getLocationContext(),
 284                                    /*CausedByPointerEscape*/ true,
 285                                    /*Symbols=*/nullptr, this, &ETraits);
 286 }
 287
 288 ProgramPoint CallEvent::getProgramPoint(bool IsPreVisit,
 289                                         const ProgramPointTag *Tag) const {
 290   if (const Expr *E = getOriginExpr()) {
 291     if (IsPreVisit)
 292       return PreStmt(E, getLocationContext(), Tag);
 293     return PostStmt(E, getLocationContext(), Tag);
 294   }
 295
 296   const Decl *D = getDecl();
 297   assert(D && "Cannot get a program point without a statement or decl");
 298
 299   SourceLocation Loc = getSourceRange().getBegin();
 300   if (IsPreVisit)
 301     return PreImplicitCall(D, Loc, getLocationContext(), Tag);
 302   return PostImplicitCall(D, Loc, getLocationContext(), Tag);
 303 }
 304
 305 SVal CallEvent::getArgSVal(unsigned Index) const {
 306   const Expr *ArgE = getArgExpr(Index);
 307   if (!ArgE)
 308     return UnknownVal();
 309   return getSVal(ArgE);
 310 }
 311
 312 SourceRange CallEvent::getArgSourceRange(unsigned Index) const {
 313   const Expr *ArgE = getArgExpr(Index);
 314   if (!ArgE)
 315     return {};
 316   return ArgE->getSourceRange();
 317 }
 318
 319 SVal CallEvent::getReturnValue() const {
 320   const Expr *E = getOriginExpr();
 321   if (!E)
 322     return UndefinedVal();
 323   return getSVal(E);
 324 }
 325
 326 LLVM_DUMP_METHOD void CallEvent::dump() const { dump(llvm::errs()); }
 327
 328 void CallEvent::dump(raw_ostream &Out) const {
 329   ASTContext &Ctx = getState()->getStateManager().getContext();
 330   if (const Expr *E = getOriginExpr()) {
 331     E->printPretty(Out, nullptr, Ctx.getPrintingPolicy());
 332     return;
 333   }
 334
 335   if (const Decl *D = getDecl()) {
 336     Out << "Call to ";
 337     D->print(Out, Ctx.getPrintingPolicy());
 338     return;
 339   }
 340
 341   Out << "Unknown call (type " << getKindAsString() << ")";
 342 }
 343
 344 bool CallEvent::isCallStmt(const Stmt *S) {
 345   return isa<CallExpr, ObjCMessageExpr, CXXConstructExpr, CXXNewExpr>(S);
 346 }
 347
 348 QualType CallEvent::getDeclaredResultType(const Decl *D) {
 349   assert(D);
 350   if (const auto *FD = dyn_cast<FunctionDecl>(D))
 351     return FD->getReturnType();
 352   if (const auto *MD = dyn_cast<ObjCMethodDecl>(D))
 353     return MD->getReturnType();
 354   if (const auto *BD = dyn_cast<BlockDecl>(D)) {
 355     // Blocks are difficult because the return type may not be stored in the
 356     // BlockDecl itself. The AST should probably be enhanced, but for now we
 357     // just do what we can.
 358     // If the block is declared without an explicit argument list, the
 359     // signature-as-written just includes the return type, not the entire
 360     // function type.
 361     // FIXME: All blocks should have signatures-as-written, even if the return
 362     // type is inferred. (That's signified with a dependent result type.)
 363     if (const TypeSourceInfo *TSI = BD->getSignatureAsWritten()) {
 364       QualType Ty = TSI->getType();
 365       if (const FunctionType *FT = Ty->getAs<FunctionType>())
 366         Ty = FT->getReturnType();
 367       if (!Ty->isDependentType())
 368         return Ty;
 369     }
 370
 371     return {};
 372   }
 373
 374   llvm_unreachable("unknown callable kind");
 375 }
 376
 377 bool CallEvent::isVariadic(const Decl *D) {
 378   assert(D);
 379
 380   if (const auto *FD = dyn_cast<FunctionDecl>(D))
 381     return FD->isVariadic();
 382   if (const auto *MD = dyn_cast<ObjCMethodDecl>(D))
 383     return MD->isVariadic();
 384   if (const auto *BD = dyn_cast<BlockDecl>(D))
 385     return BD->isVariadic();
 386
 387   llvm_unreachable("unknown callable kind");
 388 }
 389
 390 static bool isTransparentUnion(QualType T) {
 391   const RecordType *UT = T->getAsUnionType();
 392   return UT && UT->getDecl()->hasAttr<TransparentUnionAttr>();
 393 }
 394
 395 // In some cases, symbolic cases should be transformed before we associate
 396 // them with parameters.  This function incapsulates such cases.
 397 static SVal processArgument(SVal Value, const Expr *ArgumentExpr,
 398                             const ParmVarDecl *Parameter, SValBuilder &SVB) {
 399   QualType ParamType = Parameter->getType();
 400   QualType ArgumentType = ArgumentExpr->getType();
 401
 402   // Transparent unions allow users to easily convert values of union field
 403   // types into union-typed objects.
 404   //
 405   // Also, more importantly, they allow users to define functions with different
 406   // different parameter types, substituting types matching transparent union
 407   // field types with the union type itself.
 408   //
 409   // Here, we check specifically for latter cases and prevent binding
 410   // field-typed values to union-typed regions.
 411   if (isTransparentUnion(ParamType) &&
 412       // Let's check that we indeed trying to bind different types.
 413       !isTransparentUnion(ArgumentType)) {
 414     BasicValueFactory &BVF = SVB.getBasicValueFactory();
 415
 416     llvm::ImmutableList<SVal> CompoundSVals = BVF.getEmptySValList();
 417     CompoundSVals = BVF.prependSVal(Value, CompoundSVals);
 418
 419     // Wrap it with compound value.
 420     return SVB.makeCompoundVal(ParamType, CompoundSVals);
 421   }
 422
 423   return Value;
 424 }
 425
 426 /// Cast the argument value to the type of the parameter at the function
 427 /// declaration.
 428 /// Returns the argument value if it didn't need a cast.
 429 /// Or returns the cast argument if it needed a cast.
 430 /// Or returns 'Unknown' if it would need a cast but the callsite and the
 431 /// runtime definition don't match in terms of argument and parameter count.
 432 static SVal castArgToParamTypeIfNeeded(const CallEvent &Call, unsigned ArgIdx,
 433                                        SVal ArgVal, SValBuilder &SVB) {
 434   const FunctionDecl *RTDecl =
 435       Call.getRuntimeDefinition().getDecl()->getAsFunction();
 436   const auto *CallExprDecl = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
 437
 438   if (!RTDecl || !CallExprDecl)
 439     return ArgVal;
 440
 441   // The function decl of the Call (in the AST) will not have any parameter
 442   // declarations, if it was 'only' declared without a prototype. However, the
 443   // engine will find the appropriate runtime definition - basically a
 444   // redeclaration, which has a function body (and a function prototype).
 445   if (CallExprDecl->hasPrototype() || !RTDecl->hasPrototype())
 446     return ArgVal;
 447
 448   // Only do this cast if the number arguments at the callsite matches with
 449   // the parameters at the runtime definition.
 450   if (Call.getNumArgs() != RTDecl->getNumParams())
 451     return UnknownVal();
 452
 453   const Expr *ArgExpr = Call.getArgExpr(ArgIdx);
 454   const ParmVarDecl *Param = RTDecl->getParamDecl(ArgIdx);
 455   return SVB.evalCast(ArgVal, Param->getType(), ArgExpr->getType());
 456 }
 457
 458 static void addParameterValuesToBindings(const StackFrameContext *CalleeCtx,
 459                                          CallEvent::BindingsTy &Bindings,
 460                                          SValBuilder &SVB,
 461                                          const CallEvent &Call,
 462                                          ArrayRef<ParmVarDecl*> parameters) {
 463   MemRegionManager &MRMgr = SVB.getRegionManager();
 464
 465   // If the function has fewer parameters than the call has arguments, we simply
 466   // do not bind any values to them.
 467   unsigned NumArgs = Call.getNumArgs();
 468   unsigned Idx = 0;
 469   ArrayRef<ParmVarDecl*>::iterator I = parameters.begin(), E = parameters.end();
 470   for (; I != E && Idx < NumArgs; ++I, ++Idx) {
 471     assert(*I && "Formal parameter has no decl?");
 472
 473     // TODO: Support allocator calls.
 474     if (Call.getKind() != CE_CXXAllocator)
 475       if (Call.isArgumentConstructedDirectly(Call.getASTArgumentIndex(Idx)))
 476         continue;
 477
 478     // TODO: Allocators should receive the correct size and possibly alignment,
 479     // determined in compile-time but not represented as arg-expressions,
 480     // which makes getArgSVal() fail and return UnknownVal.
 481     SVal ArgVal = Call.getArgSVal(Idx);
 482     const Expr *ArgExpr = Call.getArgExpr(Idx);
 483
 484     if (ArgVal.isUnknown())
 485       continue;
 486
 487     // Cast the argument value to match the type of the parameter in some
 488     // edge-cases.
 489     ArgVal = castArgToParamTypeIfNeeded(Call, Idx, ArgVal, SVB);
 490
 491     Loc ParamLoc = SVB.makeLoc(
 492         MRMgr.getParamVarRegion(Call.getOriginExpr(), Idx, CalleeCtx));
 493     Bindings.push_back(
 494         std::make_pair(ParamLoc, processArgument(ArgVal, ArgExpr, *I, SVB)));
 495   }
 496
 497   // FIXME: Variadic arguments are not handled at all right now.
 498 }
 499
 500 const ConstructionContext *CallEvent::getConstructionContext() const {
 501   const StackFrameContext *StackFrame = getCalleeStackFrame(0);
 502   if (!StackFrame)
 503     return nullptr;
 504
 505   const CFGElement Element = StackFrame->getCallSiteCFGElement();
 506   if (const auto Ctor = Element.getAs<CFGConstructor>()) {
 507     return Ctor->getConstructionContext();
 508   }
 509
 510   if (const auto RecCall = Element.getAs<CFGCXXRecordTypedCall>()) {
 511     return RecCall->getConstructionContext();
 512   }
 513
 514   return nullptr;
 515 }
 516
 517 std::optional<SVal> CallEvent::getReturnValueUnderConstruction() const {
 518   const auto *CC = getConstructionContext();
 519   if (!CC)
 520     return std::nullopt;
 521
 522   EvalCallOptions CallOpts;
 523   ExprEngine &Engine = getState()->getStateManager().getOwningEngine();
 524   SVal RetVal = Engine.computeObjectUnderConstruction(
 525       getOriginExpr(), getState(), &Engine.getBuilderContext(),
 526       getLocationContext(), CC, CallOpts);
 527   return RetVal;
 528 }
 529
 530 ArrayRef<ParmVarDecl*> AnyFunctionCall::parameters() const {
 531   const FunctionDecl *D = getDecl();
 532   if (!D)
 533     return std::nullopt;
 534   return D->parameters();
 535 }
 536
 537 RuntimeDefinition AnyFunctionCall::getRuntimeDefinition() const {
 538   const FunctionDecl *FD = getDecl();
 539   if (!FD)
 540     return {};
 541
 542   // Note that the AnalysisDeclContext will have the FunctionDecl with
 543   // the definition (if one exists).
 544   AnalysisDeclContext *AD =
 545     getLocationContext()->getAnalysisDeclContext()->
 546     getManager()->getContext(FD);
 547   bool IsAutosynthesized;
 548   Stmt* Body = AD->getBody(IsAutosynthesized);
 549   LLVM_DEBUG({
 550     if (IsAutosynthesized)
 551       llvm::dbgs() << "Using autosynthesized body for " << FD->getName()
 552                    << "\n";
 553   });
 554
 555   ExprEngine &Engine = getState()->getStateManager().getOwningEngine();
 556   cross_tu::CrossTranslationUnitContext &CTUCtx =
 557       *Engine.getCrossTranslationUnitContext();
 558
 559   AnalyzerOptions &Opts = Engine.getAnalysisManager().options;
 560
 561   if (Body) {
 562     const Decl* Decl = AD->getDecl();
 563     if (Opts.IsNaiveCTUEnabled && CTUCtx.isImportedAsNew(Decl)) {
 564       // A newly created definition, but we had error(s) during the import.
 565       if (CTUCtx.hasError(Decl))
 566         return {};
 567       return RuntimeDefinition(Decl, /*Foreign=*/true);
 568     }
 569     return RuntimeDefinition(Decl, /*Foreign=*/false);
 570   }
 571
 572   // Try to get CTU definition only if CTUDir is provided.
 573   if (!Opts.IsNaiveCTUEnabled)
 574     return {};
 575
 576   llvm::Expected<const FunctionDecl *> CTUDeclOrError =
 577       CTUCtx.getCrossTUDefinition(FD, Opts.CTUDir, Opts.CTUIndexName,
 578                                   Opts.DisplayCTUProgress);
 579
 580   if (!CTUDeclOrError) {
 581     handleAllErrors(CTUDeclOrError.takeError(),
 582                     [&](const cross_tu::IndexError &IE) {
 583                       CTUCtx.emitCrossTUDiagnostics(IE);
 584                     });
 585     return {};
 586   }
 587
 588   return RuntimeDefinition(*CTUDeclOrError, /*Foreign=*/true);
 589 }
 590
 591 void AnyFunctionCall::getInitialStackFrameContents(
 592                                         const StackFrameContext *CalleeCtx,
 593                                         BindingsTy &Bindings) const {
 594   const auto *D = cast<FunctionDecl>(CalleeCtx->getDecl());
 595   SValBuilder &SVB = getState()->getStateManager().getSValBuilder();
 596   addParameterValuesToBindings(CalleeCtx, Bindings, SVB, *this,
 597                                D->parameters());
 598 }
 599
 600 bool AnyFunctionCall::argumentsMayEscape() const {
 601   if (CallEvent::argumentsMayEscape() || hasVoidPointerToNonConstArg())
 602     return true;
 603
 604   const FunctionDecl *D = getDecl();
 605   if (!D)
 606     return true;
 607
 608   const IdentifierInfo *II = D->getIdentifier();
 609   if (!II)
 610     return false;
 611
 612   // This set of "escaping" APIs is
 613
 614   // - 'int pthread_setspecific(ptheread_key k, const void *)' stores a
 615   //   value into thread local storage. The value can later be retrieved with
 616   //   'void *ptheread_getspecific(pthread_key)'. So even thought the
 617   //   parameter is 'const void *', the region escapes through the call.
 618   if (II->isStr("pthread_setspecific"))
 619     return true;
 620
 621   // - xpc_connection_set_context stores a value which can be retrieved later
 622   //   with xpc_connection_get_context.
 623   if (II->isStr("xpc_connection_set_context"))
 624     return true;
 625
 626   // - funopen - sets a buffer for future IO calls.
 627   if (II->isStr("funopen"))
 628     return true;
 629
 630   // - __cxa_demangle - can reallocate memory and can return the pointer to
 631   // the input buffer.
 632   if (II->isStr("__cxa_demangle"))
 633     return true;
 634
 635   StringRef FName = II->getName();
 636
 637   // - CoreFoundation functions that end with "NoCopy" can free a passed-in
 638   //   buffer even if it is const.
 639   if (FName.endswith("NoCopy"))
 640     return true;
 641
 642   // - NSXXInsertXX, for example NSMapInsertIfAbsent, since they can
 643   //   be deallocated by NSMapRemove.
 644   if (FName.startswith("NS") && FName.contains("Insert"))
 645     return true;
 646
 647   // - Many CF containers allow objects to escape through custom
 648   //   allocators/deallocators upon container construction. (PR12101)
 649   if (FName.startswith("CF") || FName.startswith("CG")) {
 650     return StrInStrNoCase(FName, "InsertValue")  != StringRef::npos ||
 651            StrInStrNoCase(FName, "AddValue")     != StringRef::npos ||
 652            StrInStrNoCase(FName, "SetValue")     != StringRef::npos ||
 653            StrInStrNoCase(FName, "WithData")     != StringRef::npos ||
 654            StrInStrNoCase(FName, "AppendValue")  != StringRef::npos ||
 655            StrInStrNoCase(FName, "SetAttribute") != StringRef::npos;
 656   }
 657
 658   return false;
 659 }
 660
 661 const FunctionDecl *SimpleFunctionCall::getDecl() const {
 662   const FunctionDecl *D = getOriginExpr()->getDirectCallee();
 663   if (D)
 664     return D;
 665
 666   return getSVal(getOriginExpr()->getCallee()).getAsFunctionDecl();
 667 }
 668
 669 const FunctionDecl *CXXInstanceCall::getDecl() const {
 670   const auto *CE = cast_or_null<CallExpr>(getOriginExpr());
 671   if (!CE)
 672     return AnyFunctionCall::getDecl();
 673
 674   const FunctionDecl *D = CE->getDirectCallee();
 675   if (D)
 676     return D;
 677
 678   return getSVal(CE->getCallee()).getAsFunctionDecl();
 679 }
 680
 681 void CXXInstanceCall::getExtraInvalidatedValues(
 682     ValueList &Values, RegionAndSymbolInvalidationTraits *ETraits) const {
 683   SVal ThisVal = getCXXThisVal();
 684   Values.push_back(ThisVal);
 685
 686   // Don't invalidate if the method is const and there are no mutable fields.
 687   if (const auto *D = cast_or_null<CXXMethodDecl>(getDecl())) {
 688     if (!D->isConst())
 689       return;
 690     // Get the record decl for the class of 'This'. D->getParent() may return a
 691     // base class decl, rather than the class of the instance which needs to be
 692     // checked for mutable fields.
 693     // TODO: We might as well look at the dynamic type of the object.
 694     const Expr *Ex = getCXXThisExpr()->IgnoreParenBaseCasts();
 695     QualType T = Ex->getType();
 696     if (T->isPointerType()) // Arrow or implicit-this syntax?
 697       T = T->getPointeeType();
 698     const CXXRecordDecl *ParentRecord = T->getAsCXXRecordDecl();
 699     assert(ParentRecord);
 700     if (ParentRecord->hasMutableFields())
 701       return;
 702     // Preserve CXXThis.
 703     const MemRegion *ThisRegion = ThisVal.getAsRegion();
 704     if (!ThisRegion)
 705       return;
 706
 707     ETraits->setTrait(ThisRegion->getBaseRegion(),
 708                       RegionAndSymbolInvalidationTraits::TK_PreserveContents);
 709   }
 710 }
 711
 712 SVal CXXInstanceCall::getCXXThisVal() const {
 713   const Expr *Base = getCXXThisExpr();
 714   // FIXME: This doesn't handle an overloaded ->* operator.
 715   if (!Base)
 716     return UnknownVal();
 717
 718   SVal ThisVal = getSVal(Base);
 719   assert(ThisVal.isUnknownOrUndef() || isa<Loc>(ThisVal));
 720   return ThisVal;
 721 }
 722
 723 RuntimeDefinition CXXInstanceCall::getRuntimeDefinition() const {
 724   // Do we have a decl at all?
 725   const Decl *D = getDecl();
 726   if (!D)
 727     return {};
 728
 729   // If the method is non-virtual, we know we can inline it.
 730   const auto *MD = cast<CXXMethodDecl>(D);
 731   if (!MD->isVirtual())
 732     return AnyFunctionCall::getRuntimeDefinition();
 733
 734   // Do we know the implicit 'this' object being called?
 735   const MemRegion *R = getCXXThisVal().getAsRegion();
 736   if (!R)
 737     return {};
 738
 739   // Do we know anything about the type of 'this'?
 740   DynamicTypeInfo DynType = getDynamicTypeInfo(getState(), R);
 741   if (!DynType.isValid())
 742     return {};
 743
 744   // Is the type a C++ class? (This is mostly a defensive check.)
 745   QualType RegionType = DynType.getType()->getPointeeType();
 746   assert(!RegionType.isNull() && "DynamicTypeInfo should always be a pointer.");
 747
 748   const CXXRecordDecl *RD = RegionType->getAsCXXRecordDecl();
 749   if (!RD || !RD->hasDefinition())
 750     return {};
 751
 752   // Find the decl for this method in that class.
 753   const CXXMethodDecl *Result = MD->getCorrespondingMethodInClass(RD, true);
 754   if (!Result) {
 755     // We might not even get the original statically-resolved method due to
 756     // some particularly nasty casting (e.g. casts to sister classes).
 757     // However, we should at least be able to search up and down our own class
 758     // hierarchy, and some real bugs have been caught by checking this.
 759     assert(!RD->isDerivedFrom(MD->getParent()) && "Couldn't find known method");
 760
 761     // FIXME: This is checking that our DynamicTypeInfo is at least as good as
 762     // the static type. However, because we currently don't update
 763     // DynamicTypeInfo when an object is cast, we can't actually be sure the
 764     // DynamicTypeInfo is up to date. This assert should be re-enabled once
 765     // this is fixed. <rdar://problem/12287087>
 766     //assert(!MD->getParent()->isDerivedFrom(RD) && "Bad DynamicTypeInfo");
 767
 768     return {};
 769   }
 770
 771   // Does the decl that we found have an implementation?
 772   const FunctionDecl *Definition;
 773   if (!Result->hasBody(Definition)) {
 774     if (!DynType.canBeASubClass())
 775       return AnyFunctionCall::getRuntimeDefinition();
 776     return {};
 777   }
 778
 779   // We found a definition. If we're not sure that this devirtualization is
 780   // actually what will happen at runtime, make sure to provide the region so
 781   // that ExprEngine can decide what to do with it.
 782   if (DynType.canBeASubClass())
 783     return RuntimeDefinition(Definition, R->StripCasts());
 784   return RuntimeDefinition(Definition, /*DispatchRegion=*/nullptr);
 785 }
 786
 787 void CXXInstanceCall::getInitialStackFrameContents(
 788                                             const StackFrameContext *CalleeCtx,
 789                                             BindingsTy &Bindings) const {
 790   AnyFunctionCall::getInitialStackFrameContents(CalleeCtx, Bindings);
 791
 792   // Handle the binding of 'this' in the new stack frame.
 793   SVal ThisVal = getCXXThisVal();
 794   if (!ThisVal.isUnknown()) {
 795     ProgramStateManager &StateMgr = getState()->getStateManager();
 796     SValBuilder &SVB = StateMgr.getSValBuilder();
 797
 798     const auto *MD = cast<CXXMethodDecl>(CalleeCtx->getDecl());
 799     Loc ThisLoc = SVB.getCXXThis(MD, CalleeCtx);
 800
 801     // If we devirtualized to a different member function, we need to make sure
 802     // we have the proper layering of CXXBaseObjectRegions.
 803     if (MD->getCanonicalDecl() != getDecl()->getCanonicalDecl()) {
 804       ASTContext &Ctx = SVB.getContext();
 805       const CXXRecordDecl *Class = MD->getParent();
 806       QualType Ty = Ctx.getPointerType(Ctx.getRecordType(Class));
 807
 808       // FIXME: CallEvent maybe shouldn't be directly accessing StoreManager.
 809       std::optional<SVal> V =
 810           StateMgr.getStoreManager().evalBaseToDerived(ThisVal, Ty);
 811       if (!V) {
 812         // We might have suffered some sort of placement new earlier, so
 813         // we're constructing in a completely unexpected storage.
 814         // Fall back to a generic pointer cast for this-value.
 815         const CXXMethodDecl *StaticMD = cast<CXXMethodDecl>(getDecl());
 816         const CXXRecordDecl *StaticClass = StaticMD->getParent();
 817         QualType StaticTy = Ctx.getPointerType(Ctx.getRecordType(StaticClass));
 818         ThisVal = SVB.evalCast(ThisVal, Ty, StaticTy);
 819       } else
 820         ThisVal = *V;
 821     }
 822
 823     if (!ThisVal.isUnknown())
 824       Bindings.push_back(std::make_pair(ThisLoc, ThisVal));
 825   }
 826 }
 827
 828 const Expr *CXXMemberCall::getCXXThisExpr() const {
 829   return getOriginExpr()->getImplicitObjectArgument();
 830 }
 831
 832 RuntimeDefinition CXXMemberCall::getRuntimeDefinition() const {
 833   // C++11 [expr.call]p1: ...If the selected function is non-virtual, or if the
 834   // id-expression in the class member access expression is a qualified-id,
 835   // that function is called. Otherwise, its final overrider in the dynamic type
 836   // of the object expression is called.
 837   if (const auto *ME = dyn_cast<MemberExpr>(getOriginExpr()->getCallee()))
 838     if (ME->hasQualifier())
 839       return AnyFunctionCall::getRuntimeDefinition();
 840
 841   return CXXInstanceCall::getRuntimeDefinition();
 842 }
 843
 844 const Expr *CXXMemberOperatorCall::getCXXThisExpr() const {
 845   return getOriginExpr()->getArg(0);
 846 }
 847
 848 const BlockDataRegion *BlockCall::getBlockRegion() const {
 849   const Expr *Callee = getOriginExpr()->getCallee();
 850   const MemRegion *DataReg = getSVal(Callee).getAsRegion();
 851
 852   return dyn_cast_or_null<BlockDataRegion>(DataReg);
 853 }
 854
 855 ArrayRef<ParmVarDecl*> BlockCall::parameters() const {
 856   const BlockDecl *D = getDecl();
 857   if (!D)
 858     return std::nullopt;
 859   return D->parameters();
 860 }
 861
 862 void BlockCall::getExtraInvalidatedValues(ValueList &Values,
 863                   RegionAndSymbolInvalidationTraits *ETraits) const {
 864   // FIXME: This also needs to invalidate captured globals.
 865   if (const MemRegion *R = getBlockRegion())
 866     Values.push_back(loc::MemRegionVal(R));
 867 }
 868
 869 void BlockCall::getInitialStackFrameContents(const StackFrameContext *CalleeCtx,
 870                                              BindingsTy &Bindings) const {
 871   SValBuilder &SVB = getState()->getStateManager().getSValBuilder();
 872   ArrayRef<ParmVarDecl*> Params;
 873   if (isConversionFromLambda()) {
 874     auto *LambdaOperatorDecl = cast<CXXMethodDecl>(CalleeCtx->getDecl());
 875     Params = LambdaOperatorDecl->parameters();
 876
 877     // For blocks converted from a C++ lambda, the callee declaration is the
 878     // operator() method on the lambda so we bind "this" to
 879     // the lambda captured by the block.
 880     const VarRegion *CapturedLambdaRegion = getRegionStoringCapturedLambda();
 881     SVal ThisVal = loc::MemRegionVal(CapturedLambdaRegion);
 882     Loc ThisLoc = SVB.getCXXThis(LambdaOperatorDecl, CalleeCtx);
 883     Bindings.push_back(std::make_pair(ThisLoc, ThisVal));
 884   } else {
 885     Params = cast<BlockDecl>(CalleeCtx->getDecl())->parameters();
 886   }
 887
 888   addParameterValuesToBindings(CalleeCtx, Bindings, SVB, *this,
 889                                Params);
 890 }
 891
 892 SVal AnyCXXConstructorCall::getCXXThisVal() const {
 893   if (Data)
 894     return loc::MemRegionVal(static_cast<const MemRegion *>(Data));
 895   return UnknownVal();
 896 }
 897
 898 void AnyCXXConstructorCall::getExtraInvalidatedValues(ValueList &Values,
 899                            RegionAndSymbolInvalidationTraits *ETraits) const {
 900   SVal V = getCXXThisVal();
 901   if (SymbolRef Sym = V.getAsSymbol(true))
 902     ETraits->setTrait(Sym,
 903                       RegionAndSymbolInvalidationTraits::TK_SuppressEscape);
 904   Values.push_back(V);
 905 }
 906
 907 void AnyCXXConstructorCall::getInitialStackFrameContents(
 908                                              const StackFrameContext *CalleeCtx,
 909                                              BindingsTy &Bindings) const {
 910   AnyFunctionCall::getInitialStackFrameContents(CalleeCtx, Bindings);
 911
 912   SVal ThisVal = getCXXThisVal();
 913   if (!ThisVal.isUnknown()) {
 914     SValBuilder &SVB = getState()->getStateManager().getSValBuilder();
 915     const auto *MD = cast<CXXMethodDecl>(CalleeCtx->getDecl());
 916     Loc ThisLoc = SVB.getCXXThis(MD, CalleeCtx);
 917     Bindings.push_back(std::make_pair(ThisLoc, ThisVal));
 918   }
 919 }
 920
 921 const StackFrameContext *
 922 CXXInheritedConstructorCall::getInheritingStackFrame() const {
 923   const StackFrameContext *SFC = getLocationContext()->getStackFrame();
 924   while (isa<CXXInheritedCtorInitExpr>(SFC->getCallSite()))
 925     SFC = SFC->getParent()->getStackFrame();
 926   return SFC;
 927 }
 928
 929 SVal CXXDestructorCall::getCXXThisVal() const {
 930   if (Data)
 931     return loc::MemRegionVal(DtorDataTy::getFromOpaqueValue(Data).getPointer());
 932   return UnknownVal();
 933 }
 934
 935 RuntimeDefinition CXXDestructorCall::getRuntimeDefinition() const {
 936   // Base destructors are always called non-virtually.
 937   // Skip CXXInstanceCall's devirtualization logic in this case.
 938   if (isBaseDestructor())
 939     return AnyFunctionCall::getRuntimeDefinition();
 940
 941   return CXXInstanceCall::getRuntimeDefinition();
 942 }
 943
 944 ArrayRef<ParmVarDecl*> ObjCMethodCall::parameters() const {
 945   const ObjCMethodDecl *D = getDecl();
 946   if (!D)
 947     return std::nullopt;
 948   return D->parameters();
 949 }
 950
 951 void ObjCMethodCall::getExtraInvalidatedValues(
 952     ValueList &Values, RegionAndSymbolInvalidationTraits *ETraits) const {
 953
 954   // If the method call is a setter for property known to be backed by
 955   // an instance variable, don't invalidate the entire receiver, just
 956   // the storage for that instance variable.
 957   if (const ObjCPropertyDecl *PropDecl = getAccessedProperty()) {
 958     if (const ObjCIvarDecl *PropIvar = PropDecl->getPropertyIvarDecl()) {
 959       SVal IvarLVal = getState()->getLValue(PropIvar, getReceiverSVal());
 960       if (const MemRegion *IvarRegion = IvarLVal.getAsRegion()) {
 961         ETraits->setTrait(
 962           IvarRegion,
 963           RegionAndSymbolInvalidationTraits::TK_DoNotInvalidateSuperRegion);
 964         ETraits->setTrait(
 965           IvarRegion,
 966           RegionAndSymbolInvalidationTraits::TK_SuppressEscape);
 967         Values.push_back(IvarLVal);
 968       }
 969       return;
 970     }
 971   }
 972
 973   Values.push_back(getReceiverSVal());
 974 }
 975
 976 SVal ObjCMethodCall::getReceiverSVal() const {
 977   // FIXME: Is this the best way to handle class receivers?
 978   if (!isInstanceMessage())
 979     return UnknownVal();
 980
 981   if (const Expr *RecE = getOriginExpr()->getInstanceReceiver())
 982     return getSVal(RecE);
 983
 984   // An instance message with no expression means we are sending to super.
 985   // In this case the object reference is the same as 'self'.
 986   assert(getOriginExpr()->getReceiverKind() == ObjCMessageExpr::SuperInstance);
 987   SVal SelfVal = getState()->getSelfSVal(getLocationContext());
 988   assert(SelfVal.isValid() && "Calling super but not in ObjC method");
 989   return SelfVal;
 990 }
 991
 992 bool ObjCMethodCall::isReceiverSelfOrSuper() const {
 993   if (getOriginExpr()->getReceiverKind() == ObjCMessageExpr::SuperInstance ||
 994       getOriginExpr()->getReceiverKind() == ObjCMessageExpr::SuperClass)
 995       return true;
 996
 997   if (!isInstanceMessage())
 998     return false;
 999
1000   SVal RecVal = getSVal(getOriginExpr()->getInstanceReceiver());
1001   SVal SelfVal = getState()->getSelfSVal(getLocationContext());
1002
1003   return (RecVal == SelfVal);
1004 }
1005
1006 SourceRange ObjCMethodCall::getSourceRange() const {
1007   switch (getMessageKind()) {
1008   case OCM_Message:
1009     return getOriginExpr()->getSourceRange();
1010   case OCM_PropertyAccess:
1011   case OCM_Subscript:
1012     return getContainingPseudoObjectExpr()->getSourceRange();
1013   }
1014   llvm_unreachable("unknown message kind");
1015 }
1016
1017 using ObjCMessageDataTy = llvm::PointerIntPair<const PseudoObjectExpr *, 2>;
1018
1019 const PseudoObjectExpr *ObjCMethodCall::getContainingPseudoObjectExpr() const {
1020   assert(Data && "Lazy lookup not yet performed.");
1021   assert(getMessageKind() != OCM_Message && "Explicit message send.");
1022   return ObjCMessageDataTy::getFromOpaqueValue(Data).getPointer();
1023 }
1024
1025 static const Expr *
1026 getSyntacticFromForPseudoObjectExpr(const PseudoObjectExpr *POE) {
1027   const Expr *Syntactic = POE->getSyntacticForm()->IgnoreParens();
1028
1029   // This handles the funny case of assigning to the result of a getter.
1030   // This can happen if the getter returns a non-const reference.
1031   if (const auto *BO = dyn_cast<BinaryOperator>(Syntactic))
1032     Syntactic = BO->getLHS()->IgnoreParens();
1033
1034   return Syntactic;
1035 }
1036
1037 ObjCMessageKind ObjCMethodCall::getMessageKind() const {
1038   if (!Data) {
1039     // Find the parent, ignoring implicit casts.
1040     const ParentMap &PM = getLocationContext()->getParentMap();
1041     const Stmt *S = PM.getParentIgnoreParenCasts(getOriginExpr());
1042
1043     // Check if parent is a PseudoObjectExpr.
1044     if (const auto *POE = dyn_cast_or_null<PseudoObjectExpr>(S)) {
1045       const Expr *Syntactic = getSyntacticFromForPseudoObjectExpr(POE);
1046
1047       ObjCMessageKind K;
1048       switch (Syntactic->getStmtClass()) {
1049       case Stmt::ObjCPropertyRefExprClass:
1050         K = OCM_PropertyAccess;
1051         break;
1052       case Stmt::ObjCSubscriptRefExprClass:
1053         K = OCM_Subscript;
1054         break;
1055       default:
1056         // FIXME: Can this ever happen?
1057         K = OCM_Message;
1058         break;
1059       }
1060
1061       if (K != OCM_Message) {
1062         const_cast<ObjCMethodCall *>(this)->Data
1063           = ObjCMessageDataTy(POE, K).getOpaqueValue();
1064         assert(getMessageKind() == K);
1065         return K;
1066       }
1067     }
1068
1069     const_cast<ObjCMethodCall *>(this)->Data
1070       = ObjCMessageDataTy(nullptr, 1).getOpaqueValue();
1071     assert(getMessageKind() == OCM_Message);
1072     return OCM_Message;
1073   }
1074
1075   ObjCMessageDataTy Info = ObjCMessageDataTy::getFromOpaqueValue(Data);
1076   if (!Info.getPointer())
1077     return OCM_Message;
1078   return static_cast<ObjCMessageKind>(Info.getInt());
1079 }
1080
1081 const ObjCPropertyDecl *ObjCMethodCall::getAccessedProperty() const {
1082   // Look for properties accessed with property syntax (foo.bar = ...)
1083   if (getMessageKind() == OCM_PropertyAccess) {
1084     const PseudoObjectExpr *POE = getContainingPseudoObjectExpr();
1085     assert(POE && "Property access without PseudoObjectExpr?");
1086
1087     const Expr *Syntactic = getSyntacticFromForPseudoObjectExpr(POE);
1088     auto *RefExpr = cast<ObjCPropertyRefExpr>(Syntactic);
1089
1090     if (RefExpr->isExplicitProperty())
1091       return RefExpr->getExplicitProperty();
1092   }
1093
1094   // Look for properties accessed with method syntax ([foo setBar:...]).
1095   const ObjCMethodDecl *MD = getDecl();
1096   if (!MD || !MD->isPropertyAccessor())
1097     return nullptr;
1098
1099   // Note: This is potentially quite slow.
1100   return MD->findPropertyDecl();
1101 }
1102
1103 bool ObjCMethodCall::canBeOverridenInSubclass(ObjCInterfaceDecl *IDecl,
1104                                              Selector Sel) const {
1105   assert(IDecl);
1106   AnalysisManager &AMgr =
1107       getState()->getStateManager().getOwningEngine().getAnalysisManager();
1108   // If the class interface is declared inside the main file, assume it is not
1109   // subcassed.
1110   // TODO: It could actually be subclassed if the subclass is private as well.
1111   // This is probably very rare.
1112   SourceLocation InterfLoc = IDecl->getEndOfDefinitionLoc();
1113   if (InterfLoc.isValid() && AMgr.isInCodeFile(InterfLoc))
1114     return false;
1115
1116   // Assume that property accessors are not overridden.
1117   if (getMessageKind() == OCM_PropertyAccess)
1118     return false;
1119
1120   // We assume that if the method is public (declared outside of main file) or
1121   // has a parent which publicly declares the method, the method could be
1122   // overridden in a subclass.
1123
1124   // Find the first declaration in the class hierarchy that declares
1125   // the selector.
1126   ObjCMethodDecl *D = nullptr;
1127   while (true) {
1128     D = IDecl->lookupMethod(Sel, true);
1129
1130     // Cannot find a public definition.
1131     if (!D)
1132       return false;
1133
1134     // If outside the main file,
1135     if (D->getLocation().isValid() && !AMgr.isInCodeFile(D->getLocation()))
1136       return true;
1137
1138     if (D->isOverriding()) {
1139       // Search in the superclass on the next iteration.
1140       IDecl = D->getClassInterface();
1141       if (!IDecl)
1142         return false;
1143
1144       IDecl = IDecl->getSuperClass();
1145       if (!IDecl)
1146         return false;
1147
1148       continue;
1149     }
1150
1151     return false;
1152   };
1153
1154   llvm_unreachable("The while loop should always terminate.");
1155 }
1156
1157 static const ObjCMethodDecl *findDefiningRedecl(const ObjCMethodDecl *MD) {
1158   if (!MD)
1159     return MD;
1160
1161   // Find the redeclaration that defines the method.
1162   if (!MD->hasBody()) {
1163     for (auto *I : MD->redecls())
1164       if (I->hasBody())
1165         MD = cast<ObjCMethodDecl>(I);
1166   }
1167   return MD;
1168 }
1169
1170 struct PrivateMethodKey {
1171   const ObjCInterfaceDecl *Interface;
1172   Selector LookupSelector;
1173   bool IsClassMethod;
1174 };
1175
1176 namespace llvm {
1177 template <> struct DenseMapInfo<PrivateMethodKey> {
1178   using InterfaceInfo = DenseMapInfo<const ObjCInterfaceDecl *>;
1179   using SelectorInfo = DenseMapInfo<Selector>;
1180
1181   static inline PrivateMethodKey getEmptyKey() {
1182     return {InterfaceInfo::getEmptyKey(), SelectorInfo::getEmptyKey(), false};
1183   }
1184
1185   static inline PrivateMethodKey getTombstoneKey() {
1186     return {InterfaceInfo::getTombstoneKey(), SelectorInfo::getTombstoneKey(),
1187             true};
1188   }
1189
1190   static unsigned getHashValue(const PrivateMethodKey &Key) {
1191     return llvm::hash_combine(
1192         llvm::hash_code(InterfaceInfo::getHashValue(Key.Interface)),
1193         llvm::hash_code(SelectorInfo::getHashValue(Key.LookupSelector)),
1194         Key.IsClassMethod);
1195   }
1196
1197   static bool isEqual(const PrivateMethodKey &LHS,
1198                       const PrivateMethodKey &RHS) {
1199     return InterfaceInfo::isEqual(LHS.Interface, RHS.Interface) &&
1200            SelectorInfo::isEqual(LHS.LookupSelector, RHS.LookupSelector) &&
1201            LHS.IsClassMethod == RHS.IsClassMethod;
1202   }
1203 };
1204 } // end namespace llvm
1205
1206 static const ObjCMethodDecl *
1207 lookupRuntimeDefinition(const ObjCInterfaceDecl *Interface,
1208                         Selector LookupSelector, bool InstanceMethod) {
1209   // Repeatedly calling lookupPrivateMethod() is expensive, especially
1210   // when in many cases it returns null.  We cache the results so
1211   // that repeated queries on the same ObjCIntefaceDecl and Selector
1212   // don't incur the same cost.  On some test cases, we can see the
1213   // same query being issued thousands of times.
1214   //
1215   // NOTE: This cache is essentially a "global" variable, but it
1216   // only gets lazily created when we get here.  The value of the
1217   // cache probably comes from it being global across ExprEngines,
1218   // where the same queries may get issued.  If we are worried about
1219   // concurrency, or possibly loading/unloading ASTs, etc., we may
1220   // need to revisit this someday.  In terms of memory, this table
1221   // stays around until clang quits, which also may be bad if we
1222   // need to release memory.
1223   using PrivateMethodCache =
1224       llvm::DenseMap<PrivateMethodKey, std::optional<const ObjCMethodDecl *>>;
1225
1226   static PrivateMethodCache PMC;
1227   std::optional<const ObjCMethodDecl *> &Val =
1228       PMC[{Interface, LookupSelector, InstanceMethod}];
1229
1230   // Query lookupPrivateMethod() if the cache does not hit.
1231   if (!Val) {
1232     Val = Interface->lookupPrivateMethod(LookupSelector, InstanceMethod);
1233
1234     if (!*Val) {
1235       // Query 'lookupMethod' as a backup.
1236       Val = Interface->lookupMethod(LookupSelector, InstanceMethod);
1237     }
1238   }
1239
1240   return *Val;
1241 }
1242
1243 RuntimeDefinition ObjCMethodCall::getRuntimeDefinition() const {
1244   const ObjCMessageExpr *E = getOriginExpr();
1245   assert(E);
1246   Selector Sel = E->getSelector();
1247
1248   if (E->isInstanceMessage()) {
1249     // Find the receiver type.
1250     const ObjCObjectType *ReceiverT = nullptr;
1251     bool CanBeSubClassed = false;
1252     bool LookingForInstanceMethod = true;
1253     QualType SupersType = E->getSuperType();
1254     const MemRegion *Receiver = nullptr;
1255
1256     if (!SupersType.isNull()) {
1257       // The receiver is guaranteed to be 'super' in this case.
1258       // Super always means the type of immediate predecessor to the method
1259       // where the call occurs.
1260       ReceiverT = cast<ObjCObjectPointerType>(SupersType)->getObjectType();
1261     } else {
1262       Receiver = getReceiverSVal().getAsRegion();
1263       if (!Receiver)
1264         return {};
1265
1266       DynamicTypeInfo DTI = getDynamicTypeInfo(getState(), Receiver);
1267       if (!DTI.isValid()) {
1268         assert(isa<AllocaRegion>(Receiver) &&
1269                "Unhandled untyped region class!");
1270         return {};
1271       }
1272
1273       QualType DynType = DTI.getType();
1274       CanBeSubClassed = DTI.canBeASubClass();
1275
1276       const auto *ReceiverDynT =
1277           dyn_cast<ObjCObjectPointerType>(DynType.getCanonicalType());
1278
1279       if (ReceiverDynT) {
1280         ReceiverT = ReceiverDynT->getObjectType();
1281
1282         // It can be actually class methods called with Class object as a
1283         // receiver. This type of messages is treated by the compiler as
1284         // instance (not class).
1285         if (ReceiverT->isObjCClass()) {
1286
1287           SVal SelfVal = getState()->getSelfSVal(getLocationContext());
1288           // For [self classMethod], return compiler visible declaration.
1289           if (Receiver == SelfVal.getAsRegion()) {
1290             return RuntimeDefinition(findDefiningRedecl(E->getMethodDecl()));
1291           }
1292
1293           // Otherwise, let's check if we know something about the type
1294           // inside of this class object.
1295           if (SymbolRef ReceiverSym = getReceiverSVal().getAsSymbol()) {
1296             DynamicTypeInfo DTI =
1297                 getClassObjectDynamicTypeInfo(getState(), ReceiverSym);
1298             if (DTI.isValid()) {
1299               // Let's use this type for lookup.
1300               ReceiverT =
1301                   cast<ObjCObjectType>(DTI.getType().getCanonicalType());
1302
1303               CanBeSubClassed = DTI.canBeASubClass();
1304               // And it should be a class method instead.
1305               LookingForInstanceMethod = false;
1306             }
1307           }
1308         }
1309
1310         if (CanBeSubClassed)
1311           if (ObjCInterfaceDecl *IDecl = ReceiverT->getInterface())
1312             // Even if `DynamicTypeInfo` told us that it can be
1313             // not necessarily this type, but its descendants, we still want
1314             // to check again if this selector can be actually overridden.
1315             CanBeSubClassed = canBeOverridenInSubclass(IDecl, Sel);
1316       }
1317     }
1318
1319     // Lookup the instance method implementation.
1320     if (ReceiverT)
1321       if (ObjCInterfaceDecl *IDecl = ReceiverT->getInterface()) {
1322         const ObjCMethodDecl *MD =
1323             lookupRuntimeDefinition(IDecl, Sel, LookingForInstanceMethod);
1324
1325         if (MD && !MD->hasBody())
1326           MD = MD->getCanonicalDecl();
1327
1328         if (CanBeSubClassed)
1329           return RuntimeDefinition(MD, Receiver);
1330         else
1331           return RuntimeDefinition(MD, nullptr);
1332       }
1333   } else {
1334     // This is a class method.
1335     // If we have type info for the receiver class, we are calling via
1336     // class name.
1337     if (ObjCInterfaceDecl *IDecl = E->getReceiverInterface()) {
1338       // Find/Return the method implementation.
1339       return RuntimeDefinition(IDecl->lookupPrivateClassMethod(Sel));
1340     }
1341   }
1342
1343   return {};
1344 }
1345
1346 bool ObjCMethodCall::argumentsMayEscape() const {
1347   if (isInSystemHeader() && !isInstanceMessage()) {
1348     Selector Sel = getSelector();
1349     if (Sel.getNumArgs() == 1 &&
1350         Sel.getIdentifierInfoForSlot(0)->isStr("valueWithPointer"))
1351       return true;
1352   }
1353
1354   return CallEvent::argumentsMayEscape();
1355 }
1356
1357 void ObjCMethodCall::getInitialStackFrameContents(
1358                                              const StackFrameContext *CalleeCtx,
1359                                              BindingsTy &Bindings) const {
1360   const auto *D = cast<ObjCMethodDecl>(CalleeCtx->getDecl());
1361   SValBuilder &SVB = getState()->getStateManager().getSValBuilder();
1362   addParameterValuesToBindings(CalleeCtx, Bindings, SVB, *this,
1363                                D->parameters());
1364
1365   SVal SelfVal = getReceiverSVal();
1366   if (!SelfVal.isUnknown()) {
1367     const VarDecl *SelfD = CalleeCtx->getAnalysisDeclContext()->getSelfDecl();
1368     MemRegionManager &MRMgr = SVB.getRegionManager();
1369     Loc SelfLoc = SVB.makeLoc(MRMgr.getVarRegion(SelfD, CalleeCtx));
1370     Bindings.push_back(std::make_pair(SelfLoc, SelfVal));
1371   }
1372 }
1373
1374 CallEventRef<>
1375 CallEventManager::getSimpleCall(const CallExpr *CE, ProgramStateRef State,
1376                                 const LocationContext *LCtx) {
1377   if (const auto *MCE = dyn_cast<CXXMemberCallExpr>(CE))
1378     return create<CXXMemberCall>(MCE, State, LCtx);
1379
1380   if (const auto *OpCE = dyn_cast<CXXOperatorCallExpr>(CE)) {
1381     const FunctionDecl *DirectCallee = OpCE->getDirectCallee();
1382     if (const auto *MD = dyn_cast<CXXMethodDecl>(DirectCallee))
1383       if (MD->isInstance())
1384         return create<CXXMemberOperatorCall>(OpCE, State, LCtx);
1385
1386   } else if (CE->getCallee()->getType()->isBlockPointerType()) {
1387     return create<BlockCall>(CE, State, LCtx);
1388   }
1389
1390   // Otherwise, it's a normal function call, static member function call, or
1391   // something we can't reason about.
1392   return create<SimpleFunctionCall>(CE, State, LCtx);
1393 }
1394
1395 CallEventRef<>
1396 CallEventManager::getCaller(const StackFrameContext *CalleeCtx,
1397                             ProgramStateRef State) {
1398   const LocationContext *ParentCtx = CalleeCtx->getParent();
1399   const LocationContext *CallerCtx = ParentCtx->getStackFrame();
1400   assert(CallerCtx && "This should not be used for top-level stack frames");
1401
1402   const Stmt *CallSite = CalleeCtx->getCallSite();
1403
1404   if (CallSite) {
1405     if (CallEventRef<> Out = getCall(CallSite, State, CallerCtx))
1406       return Out;
1407
1408     SValBuilder &SVB = State->getStateManager().getSValBuilder();
1409     const auto *Ctor = cast<CXXMethodDecl>(CalleeCtx->getDecl());
1410     Loc ThisPtr = SVB.getCXXThis(Ctor, CalleeCtx);
1411     SVal ThisVal = State->getSVal(ThisPtr);
1412
1413     if (const auto *CE = dyn_cast<CXXConstructExpr>(CallSite))
1414       return getCXXConstructorCall(CE, ThisVal.getAsRegion(), State, CallerCtx);
1415     else if (const auto *CIE = dyn_cast<CXXInheritedCtorInitExpr>(CallSite))
1416       return getCXXInheritedConstructorCall(CIE, ThisVal.getAsRegion(), State,
1417                                             CallerCtx);
1418     else {
1419       // All other cases are handled by getCall.
1420       llvm_unreachable("This is not an inlineable statement");
1421     }
1422   }
1423
1424   // Fall back to the CFG. The only thing we haven't handled yet is
1425   // destructors, though this could change in the future.
1426   const CFGBlock *B = CalleeCtx->getCallSiteBlock();
1427   CFGElement E = (*B)[CalleeCtx->getIndex()];
1428   assert((E.getAs<CFGImplicitDtor>() || E.getAs<CFGTemporaryDtor>()) &&
1429          "All other CFG elements should have exprs");
1430
1431   SValBuilder &SVB = State->getStateManager().getSValBuilder();
1432   const auto *Dtor = cast<CXXDestructorDecl>(CalleeCtx->getDecl());
1433   Loc ThisPtr = SVB.getCXXThis(Dtor, CalleeCtx);
1434   SVal ThisVal = State->getSVal(ThisPtr);
1435
1436   const Stmt *Trigger;
1437   if (std::optional<CFGAutomaticObjDtor> AutoDtor =
1438           E.getAs<CFGAutomaticObjDtor>())
1439     Trigger = AutoDtor->getTriggerStmt();
1440   else if (std::optional<CFGDeleteDtor> DeleteDtor = E.getAs<CFGDeleteDtor>())
1441     Trigger = DeleteDtor->getDeleteExpr();
1442   else
1443     Trigger = Dtor->getBody();
1444
1445   return getCXXDestructorCall(Dtor, Trigger, ThisVal.getAsRegion(),
1446                               E.getAs<CFGBaseDtor>().has_value(), State,
1447                               CallerCtx);
1448 }
1449
1450 CallEventRef<> CallEventManager::getCall(const Stmt *S, ProgramStateRef State,
1451                                          const LocationContext *LC) {
1452   if (const auto *CE = dyn_cast<CallExpr>(S)) {
1453     return getSimpleCall(CE, State, LC);
1454   } else if (const auto *NE = dyn_cast<CXXNewExpr>(S)) {
1455     return getCXXAllocatorCall(NE, State, LC);
1456   } else if (const auto *DE = dyn_cast<CXXDeleteExpr>(S)) {
1457     return getCXXDeallocatorCall(DE, State, LC);
1458   } else if (const auto *ME = dyn_cast<ObjCMessageExpr>(S)) {
1459     return getObjCMethodCall(ME, State, LC);
1460   } else {
1461     return nullptr;
1462   }
1463 }