contrib/llvm/tools/clang/lib/StaticAnalyzer/Core/CallEvent.cpp

   1 //===- Calls.cpp - Wrapper for all function and method calls ------*- C++ -*--//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 /// \file This file defines CallEvent and its subclasses, which represent path-
  11 /// sensitive instances of different kinds of function and method calls
  12 /// (C, C++, and Objective-C).
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
  17 #include "clang/AST/ParentMap.h"
  18 #include "clang/Analysis/ProgramPoint.h"
  19 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
  20 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicTypeMap.h"
  21 #include "llvm/ADT/SmallSet.h"
  22 #include "llvm/ADT/StringExtras.h"
  23 #include "llvm/Support/raw_ostream.h"
  24
  25 using namespace clang;
  26 using namespace ento;
  27
  28 QualType CallEvent::getResultType() const {
  29   const Expr *E = getOriginExpr();
  30   assert(E && "Calls without origin expressions do not have results");
  31   QualType ResultTy = E->getType();
  32
  33   ASTContext &Ctx = getState()->getStateManager().getContext();
  34
  35   // A function that returns a reference to 'int' will have a result type
  36   // of simply 'int'. Check the origin expr's value kind to recover the
  37   // proper type.
  38   switch (E->getValueKind()) {
  39   case VK_LValue:
  40     ResultTy = Ctx.getLValueReferenceType(ResultTy);
  41     break;
  42   case VK_XValue:
  43     ResultTy = Ctx.getRValueReferenceType(ResultTy);
  44     break;
  45   case VK_RValue:
  46     // No adjustment is necessary.
  47     break;
  48   }
  49
  50   return ResultTy;
  51 }
  52
  53 static bool isCallback(QualType T) {
  54   // If a parameter is a block or a callback, assume it can modify pointer.
  55   if (T->isBlockPointerType() ||
  56       T->isFunctionPointerType() ||
  57       T->isObjCSelType())
  58     return true;
  59
  60   // Check if a callback is passed inside a struct (for both, struct passed by
  61   // reference and by value). Dig just one level into the struct for now.
  62
  63   if (T->isAnyPointerType() || T->isReferenceType())
  64     T = T->getPointeeType();
  65
  66   if (const RecordType *RT = T->getAsStructureType()) {
  67     const RecordDecl *RD = RT->getDecl();
  68     for (const auto *I : RD->fields()) {
  69       QualType FieldT = I->getType();
  70       if (FieldT->isBlockPointerType() || FieldT->isFunctionPointerType())
  71         return true;
  72     }
  73   }
  74   return false;
  75 }
  76
  77 static bool isVoidPointerToNonConst(QualType T) {
  78   if (const PointerType *PT = T->getAs<PointerType>()) {
  79     QualType PointeeTy = PT->getPointeeType();
  80     if (PointeeTy.isConstQualified())
  81       return false;
  82     return PointeeTy->isVoidType();
  83   } else
  84     return false;
  85 }
  86
  87 bool CallEvent::hasNonNullArgumentsWithType(bool (*Condition)(QualType)) const {
  88   unsigned NumOfArgs = getNumArgs();
  89
  90   // If calling using a function pointer, assume the function does not
  91   // satisfy the callback.
  92   // TODO: We could check the types of the arguments here.
  93   if (!getDecl())
  94     return false;
  95
  96   unsigned Idx = 0;
  97   for (CallEvent::param_type_iterator I = param_type_begin(),
  98                                       E = param_type_end();
  99        I != E && Idx < NumOfArgs; ++I, ++Idx) {
 100     if (NumOfArgs <= Idx)
 101       break;
 102
 103     // If the parameter is 0, it's harmless.
 104     if (getArgSVal(Idx).isZeroConstant())
 105       continue;
 106
 107     if (Condition(*I))
 108       return true;
 109   }
 110   return false;
 111 }
 112
 113 bool CallEvent::hasNonZeroCallbackArg() const {
 114   return hasNonNullArgumentsWithType(isCallback);
 115 }
 116
 117 bool CallEvent::hasVoidPointerToNonConstArg() const {
 118   return hasNonNullArgumentsWithType(isVoidPointerToNonConst);
 119 }
 120
 121 bool CallEvent::isGlobalCFunction(StringRef FunctionName) const {
 122   const FunctionDecl *FD = dyn_cast_or_null<FunctionDecl>(getDecl());
 123   if (!FD)
 124     return false;
 125
 126   return CheckerContext::isCLibraryFunction(FD, FunctionName);
 127 }
 128
 129 /// \brief Returns true if a type is a pointer-to-const or reference-to-const
 130 /// with no further indirection.
 131 static bool isPointerToConst(QualType Ty) {
 132   QualType PointeeTy = Ty->getPointeeType();
 133   if (PointeeTy == QualType())
 134     return false;
 135   if (!PointeeTy.isConstQualified())
 136     return false;
 137   if (PointeeTy->isAnyPointerType())
 138     return false;
 139   return true;
 140 }
 141
 142 // Try to retrieve the function declaration and find the function parameter
 143 // types which are pointers/references to a non-pointer const.
 144 // We will not invalidate the corresponding argument regions.
 145 static void findPtrToConstParams(llvm::SmallSet<unsigned, 4> &PreserveArgs,
 146                                  const CallEvent &Call) {
 147   unsigned Idx = 0;
 148   for (CallEvent::param_type_iterator I = Call.param_type_begin(),
 149                                       E = Call.param_type_end();
 150        I != E; ++I, ++Idx) {
 151     if (isPointerToConst(*I))
 152       PreserveArgs.insert(Idx);
 153   }
 154 }
 155
 156 ProgramStateRef CallEvent::invalidateRegions(unsigned BlockCount,
 157                                              ProgramStateRef Orig) const {
 158   ProgramStateRef Result = (Orig ? Orig : getState());
 159
 160   // Don't invalidate anything if the callee is marked pure/const.
 161   if (const Decl *callee = getDecl())
 162     if (callee->hasAttr<PureAttr>() || callee->hasAttr<ConstAttr>())
 163       return Result;
 164
 165   SmallVector<SVal, 8> ValuesToInvalidate;
 166   RegionAndSymbolInvalidationTraits ETraits;
 167
 168   getExtraInvalidatedValues(ValuesToInvalidate, &ETraits);
 169
 170   // Indexes of arguments whose values will be preserved by the call.
 171   llvm::SmallSet<unsigned, 4> PreserveArgs;
 172   if (!argumentsMayEscape())
 173     findPtrToConstParams(PreserveArgs, *this);
 174
 175   for (unsigned Idx = 0, Count = getNumArgs(); Idx != Count; ++Idx) {
 176     // Mark this region for invalidation.  We batch invalidate regions
 177     // below for efficiency.
 178     if (PreserveArgs.count(Idx))
 179       if (const MemRegion *MR = getArgSVal(Idx).getAsRegion())
 180         ETraits.setTrait(MR->getBaseRegion(),
 181                         RegionAndSymbolInvalidationTraits::TK_PreserveContents);
 182         // TODO: Factor this out + handle the lower level const pointers.
 183
 184     ValuesToInvalidate.push_back(getArgSVal(Idx));
 185   }
 186
 187   // Invalidate designated regions using the batch invalidation API.
 188   // NOTE: Even if RegionsToInvalidate is empty, we may still invalidate
 189   //  global variables.
 190   return Result->invalidateRegions(ValuesToInvalidate, getOriginExpr(),
 191                                    BlockCount, getLocationContext(),
 192                                    /*CausedByPointerEscape*/ true,
 193                                    /*Symbols=*/nullptr, this, &ETraits);
 194 }
 195
 196 ProgramPoint CallEvent::getProgramPoint(bool IsPreVisit,
 197                                         const ProgramPointTag *Tag) const {
 198   if (const Expr *E = getOriginExpr()) {
 199     if (IsPreVisit)
 200       return PreStmt(E, getLocationContext(), Tag);
 201     return PostStmt(E, getLocationContext(), Tag);
 202   }
 203
 204   const Decl *D = getDecl();
 205   assert(D && "Cannot get a program point without a statement or decl");
 206
 207   SourceLocation Loc = getSourceRange().getBegin();
 208   if (IsPreVisit)
 209     return PreImplicitCall(D, Loc, getLocationContext(), Tag);
 210   return PostImplicitCall(D, Loc, getLocationContext(), Tag);
 211 }
 212
 213 bool CallEvent::isCalled(const CallDescription &CD) const {
 214   assert(getKind() != CE_ObjCMessage && "Obj-C methods are not supported");
 215   if (!CD.II)
 216     CD.II = &getState()->getStateManager().getContext().Idents.get(CD.FuncName);
 217   if (getCalleeIdentifier() != CD.II)
 218     return false;
 219   return (CD.RequiredArgs == CallDescription::NoArgRequirement ||
 220           CD.RequiredArgs == getNumArgs());
 221 }
 222
 223 SVal CallEvent::getArgSVal(unsigned Index) const {
 224   const Expr *ArgE = getArgExpr(Index);
 225   if (!ArgE)
 226     return UnknownVal();
 227   return getSVal(ArgE);
 228 }
 229
 230 SourceRange CallEvent::getArgSourceRange(unsigned Index) const {
 231   const Expr *ArgE = getArgExpr(Index);
 232   if (!ArgE)
 233     return SourceRange();
 234   return ArgE->getSourceRange();
 235 }
 236
 237 SVal CallEvent::getReturnValue() const {
 238   const Expr *E = getOriginExpr();
 239   if (!E)
 240     return UndefinedVal();
 241   return getSVal(E);
 242 }
 243
 244 LLVM_DUMP_METHOD void CallEvent::dump() const { dump(llvm::errs()); }
 245
 246 void CallEvent::dump(raw_ostream &Out) const {
 247   ASTContext &Ctx = getState()->getStateManager().getContext();
 248   if (const Expr *E = getOriginExpr()) {
 249     E->printPretty(Out, nullptr, Ctx.getPrintingPolicy());
 250     Out << "\n";
 251     return;
 252   }
 253
 254   if (const Decl *D = getDecl()) {
 255     Out << "Call to ";
 256     D->print(Out, Ctx.getPrintingPolicy());
 257     return;
 258   }
 259
 260   // FIXME: a string representation of the kind would be nice.
 261   Out << "Unknown call (type " << getKind() << ")";
 262 }
 263
 264
 265 bool CallEvent::isCallStmt(const Stmt *S) {
 266   return isa<CallExpr>(S) || isa<ObjCMessageExpr>(S)
 267                           || isa<CXXConstructExpr>(S)
 268                           || isa<CXXNewExpr>(S);
 269 }
 270
 271 QualType CallEvent::getDeclaredResultType(const Decl *D) {
 272   assert(D);
 273   if (const FunctionDecl* FD = dyn_cast<FunctionDecl>(D))
 274     return FD->getReturnType();
 275   if (const ObjCMethodDecl* MD = dyn_cast<ObjCMethodDecl>(D))
 276     return MD->getReturnType();
 277   if (const BlockDecl *BD = dyn_cast<BlockDecl>(D)) {
 278     // Blocks are difficult because the return type may not be stored in the
 279     // BlockDecl itself. The AST should probably be enhanced, but for now we
 280     // just do what we can.
 281     // If the block is declared without an explicit argument list, the
 282     // signature-as-written just includes the return type, not the entire
 283     // function type.
 284     // FIXME: All blocks should have signatures-as-written, even if the return
 285     // type is inferred. (That's signified with a dependent result type.)
 286     if (const TypeSourceInfo *TSI = BD->getSignatureAsWritten()) {
 287       QualType Ty = TSI->getType();
 288       if (const FunctionType *FT = Ty->getAs<FunctionType>())
 289         Ty = FT->getReturnType();
 290       if (!Ty->isDependentType())
 291         return Ty;
 292     }
 293
 294     return QualType();
 295   }
 296
 297   llvm_unreachable("unknown callable kind");
 298 }
 299
 300 bool CallEvent::isVariadic(const Decl *D) {
 301   assert(D);
 302
 303   if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D))
 304     return FD->isVariadic();
 305   if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D))
 306     return MD->isVariadic();
 307   if (const BlockDecl *BD = dyn_cast<BlockDecl>(D))
 308     return BD->isVariadic();
 309
 310   llvm_unreachable("unknown callable kind");
 311 }
 312
 313 static void addParameterValuesToBindings(const StackFrameContext *CalleeCtx,
 314                                          CallEvent::BindingsTy &Bindings,
 315                                          SValBuilder &SVB,
 316                                          const CallEvent &Call,
 317                                          ArrayRef<ParmVarDecl*> parameters) {
 318   MemRegionManager &MRMgr = SVB.getRegionManager();
 319
 320   // If the function has fewer parameters than the call has arguments, we simply
 321   // do not bind any values to them.
 322   unsigned NumArgs = Call.getNumArgs();
 323   unsigned Idx = 0;
 324   ArrayRef<ParmVarDecl*>::iterator I = parameters.begin(), E = parameters.end();
 325   for (; I != E && Idx < NumArgs; ++I, ++Idx) {
 326     const ParmVarDecl *ParamDecl = *I;
 327     assert(ParamDecl && "Formal parameter has no decl?");
 328
 329     SVal ArgVal = Call.getArgSVal(Idx);
 330     if (!ArgVal.isUnknown()) {
 331       Loc ParamLoc = SVB.makeLoc(MRMgr.getVarRegion(ParamDecl, CalleeCtx));
 332       Bindings.push_back(std::make_pair(ParamLoc, ArgVal));
 333     }
 334   }
 335
 336   // FIXME: Variadic arguments are not handled at all right now.
 337 }
 338
 339 ArrayRef<ParmVarDecl*> AnyFunctionCall::parameters() const {
 340   const FunctionDecl *D = getDecl();
 341   if (!D)
 342     return None;
 343   return D->parameters();
 344 }
 345
 346 void AnyFunctionCall::getInitialStackFrameContents(
 347                                         const StackFrameContext *CalleeCtx,
 348                                         BindingsTy &Bindings) const {
 349   const FunctionDecl *D = cast<FunctionDecl>(CalleeCtx->getDecl());
 350   SValBuilder &SVB = getState()->getStateManager().getSValBuilder();
 351   addParameterValuesToBindings(CalleeCtx, Bindings, SVB, *this,
 352                                D->parameters());
 353 }
 354
 355 bool AnyFunctionCall::argumentsMayEscape() const {
 356   if (CallEvent::argumentsMayEscape() || hasVoidPointerToNonConstArg())
 357     return true;
 358
 359   const FunctionDecl *D = getDecl();
 360   if (!D)
 361     return true;
 362
 363   const IdentifierInfo *II = D->getIdentifier();
 364   if (!II)
 365     return false;
 366
 367   // This set of "escaping" APIs is
 368
 369   // - 'int pthread_setspecific(ptheread_key k, const void *)' stores a
 370   //   value into thread local storage. The value can later be retrieved with
 371   //   'void *ptheread_getspecific(pthread_key)'. So even thought the
 372   //   parameter is 'const void *', the region escapes through the call.
 373   if (II->isStr("pthread_setspecific"))
 374     return true;
 375
 376   // - xpc_connection_set_context stores a value which can be retrieved later
 377   //   with xpc_connection_get_context.
 378   if (II->isStr("xpc_connection_set_context"))
 379     return true;
 380
 381   // - funopen - sets a buffer for future IO calls.
 382   if (II->isStr("funopen"))
 383     return true;
 384
 385   // - __cxa_demangle - can reallocate memory and can return the pointer to
 386   // the input buffer.
 387   if (II->isStr("__cxa_demangle"))
 388     return true;
 389
 390   StringRef FName = II->getName();
 391
 392   // - CoreFoundation functions that end with "NoCopy" can free a passed-in
 393   //   buffer even if it is const.
 394   if (FName.endswith("NoCopy"))
 395     return true;
 396
 397   // - NSXXInsertXX, for example NSMapInsertIfAbsent, since they can
 398   //   be deallocated by NSMapRemove.
 399   if (FName.startswith("NS") && (FName.find("Insert") != StringRef::npos))
 400     return true;
 401
 402   // - Many CF containers allow objects to escape through custom
 403   //   allocators/deallocators upon container construction. (PR12101)
 404   if (FName.startswith("CF") || FName.startswith("CG")) {
 405     return StrInStrNoCase(FName, "InsertValue")  != StringRef::npos ||
 406            StrInStrNoCase(FName, "AddValue")     != StringRef::npos ||
 407            StrInStrNoCase(FName, "SetValue")     != StringRef::npos ||
 408            StrInStrNoCase(FName, "WithData")     != StringRef::npos ||
 409            StrInStrNoCase(FName, "AppendValue")  != StringRef::npos ||
 410            StrInStrNoCase(FName, "SetAttribute") != StringRef::npos;
 411   }
 412
 413   return false;
 414 }
 415
 416
 417 const FunctionDecl *SimpleFunctionCall::getDecl() const {
 418   const FunctionDecl *D = getOriginExpr()->getDirectCallee();
 419   if (D)
 420     return D;
 421
 422   return getSVal(getOriginExpr()->getCallee()).getAsFunctionDecl();
 423 }
 424
 425
 426 const FunctionDecl *CXXInstanceCall::getDecl() const {
 427   const CallExpr *CE = cast_or_null<CallExpr>(getOriginExpr());
 428   if (!CE)
 429     return AnyFunctionCall::getDecl();
 430
 431   const FunctionDecl *D = CE->getDirectCallee();
 432   if (D)
 433     return D;
 434
 435   return getSVal(CE->getCallee()).getAsFunctionDecl();
 436 }
 437
 438 void CXXInstanceCall::getExtraInvalidatedValues(
 439     ValueList &Values, RegionAndSymbolInvalidationTraits *ETraits) const {
 440   SVal ThisVal = getCXXThisVal();
 441   Values.push_back(ThisVal);
 442
 443   // Don't invalidate if the method is const and there are no mutable fields.
 444   if (const CXXMethodDecl *D = cast_or_null<CXXMethodDecl>(getDecl())) {
 445     if (!D->isConst())
 446       return;
 447     // Get the record decl for the class of 'This'. D->getParent() may return a
 448     // base class decl, rather than the class of the instance which needs to be
 449     // checked for mutable fields.
 450     const Expr *Ex = getCXXThisExpr()->ignoreParenBaseCasts();
 451     const CXXRecordDecl *ParentRecord = Ex->getType()->getAsCXXRecordDecl();
 452     if (!ParentRecord || ParentRecord->hasMutableFields())
 453       return;
 454     // Preserve CXXThis.
 455     const MemRegion *ThisRegion = ThisVal.getAsRegion();
 456     if (!ThisRegion)
 457       return;
 458
 459     ETraits->setTrait(ThisRegion->getBaseRegion(),
 460                       RegionAndSymbolInvalidationTraits::TK_PreserveContents);
 461   }
 462 }
 463
 464 SVal CXXInstanceCall::getCXXThisVal() const {
 465   const Expr *Base = getCXXThisExpr();
 466   // FIXME: This doesn't handle an overloaded ->* operator.
 467   if (!Base)
 468     return UnknownVal();
 469
 470   SVal ThisVal = getSVal(Base);
 471   assert(ThisVal.isUnknownOrUndef() || ThisVal.getAs<Loc>());
 472   return ThisVal;
 473 }
 474
 475
 476 RuntimeDefinition CXXInstanceCall::getRuntimeDefinition() const {
 477   // Do we have a decl at all?
 478   const Decl *D = getDecl();
 479   if (!D)
 480     return RuntimeDefinition();
 481
 482   // If the method is non-virtual, we know we can inline it.
 483   const CXXMethodDecl *MD = cast<CXXMethodDecl>(D);
 484   if (!MD->isVirtual())
 485     return AnyFunctionCall::getRuntimeDefinition();
 486
 487   // Do we know the implicit 'this' object being called?
 488   const MemRegion *R = getCXXThisVal().getAsRegion();
 489   if (!R)
 490     return RuntimeDefinition();
 491
 492   // Do we know anything about the type of 'this'?
 493   DynamicTypeInfo DynType = getDynamicTypeInfo(getState(), R);
 494   if (!DynType.isValid())
 495     return RuntimeDefinition();
 496
 497   // Is the type a C++ class? (This is mostly a defensive check.)
 498   QualType RegionType = DynType.getType()->getPointeeType();
 499   assert(!RegionType.isNull() && "DynamicTypeInfo should always be a pointer.");
 500
 501   const CXXRecordDecl *RD = RegionType->getAsCXXRecordDecl();
 502   if (!RD || !RD->hasDefinition())
 503     return RuntimeDefinition();
 504
 505   // Find the decl for this method in that class.
 506   const CXXMethodDecl *Result = MD->getCorrespondingMethodInClass(RD, true);
 507   if (!Result) {
 508     // We might not even get the original statically-resolved method due to
 509     // some particularly nasty casting (e.g. casts to sister classes).
 510     // However, we should at least be able to search up and down our own class
 511     // hierarchy, and some real bugs have been caught by checking this.
 512     assert(!RD->isDerivedFrom(MD->getParent()) && "Couldn't find known method");
 513
 514     // FIXME: This is checking that our DynamicTypeInfo is at least as good as
 515     // the static type. However, because we currently don't update
 516     // DynamicTypeInfo when an object is cast, we can't actually be sure the
 517     // DynamicTypeInfo is up to date. This assert should be re-enabled once
 518     // this is fixed. <rdar://problem/12287087>
 519     //assert(!MD->getParent()->isDerivedFrom(RD) && "Bad DynamicTypeInfo");
 520
 521     return RuntimeDefinition();
 522   }
 523
 524   // Does the decl that we found have an implementation?
 525   const FunctionDecl *Definition;
 526   if (!Result->hasBody(Definition))
 527     return RuntimeDefinition();
 528
 529   // We found a definition. If we're not sure that this devirtualization is
 530   // actually what will happen at runtime, make sure to provide the region so
 531   // that ExprEngine can decide what to do with it.
 532   if (DynType.canBeASubClass())
 533     return RuntimeDefinition(Definition, R->StripCasts());
 534   return RuntimeDefinition(Definition, /*DispatchRegion=*/nullptr);
 535 }
 536
 537 void CXXInstanceCall::getInitialStackFrameContents(
 538                                             const StackFrameContext *CalleeCtx,
 539                                             BindingsTy &Bindings) const {
 540   AnyFunctionCall::getInitialStackFrameContents(CalleeCtx, Bindings);
 541
 542   // Handle the binding of 'this' in the new stack frame.
 543   SVal ThisVal = getCXXThisVal();
 544   if (!ThisVal.isUnknown()) {
 545     ProgramStateManager &StateMgr = getState()->getStateManager();
 546     SValBuilder &SVB = StateMgr.getSValBuilder();
 547
 548     const CXXMethodDecl *MD = cast<CXXMethodDecl>(CalleeCtx->getDecl());
 549     Loc ThisLoc = SVB.getCXXThis(MD, CalleeCtx);
 550
 551     // If we devirtualized to a different member function, we need to make sure
 552     // we have the proper layering of CXXBaseObjectRegions.
 553     if (MD->getCanonicalDecl() != getDecl()->getCanonicalDecl()) {
 554       ASTContext &Ctx = SVB.getContext();
 555       const CXXRecordDecl *Class = MD->getParent();
 556       QualType Ty = Ctx.getPointerType(Ctx.getRecordType(Class));
 557
 558       // FIXME: CallEvent maybe shouldn't be directly accessing StoreManager.
 559       bool Failed;
 560       ThisVal = StateMgr.getStoreManager().attemptDownCast(ThisVal, Ty, Failed);
 561       assert(!Failed && "Calling an incorrectly devirtualized method");
 562     }
 563
 564     if (!ThisVal.isUnknown())
 565       Bindings.push_back(std::make_pair(ThisLoc, ThisVal));
 566   }
 567 }
 568
 569
 570
 571 const Expr *CXXMemberCall::getCXXThisExpr() const {
 572   return getOriginExpr()->getImplicitObjectArgument();
 573 }
 574
 575 RuntimeDefinition CXXMemberCall::getRuntimeDefinition() const {
 576   // C++11 [expr.call]p1: ...If the selected function is non-virtual, or if the
 577   // id-expression in the class member access expression is a qualified-id,
 578   // that function is called. Otherwise, its final overrider in the dynamic type
 579   // of the object expression is called.
 580   if (const MemberExpr *ME = dyn_cast<MemberExpr>(getOriginExpr()->getCallee()))
 581     if (ME->hasQualifier())
 582       return AnyFunctionCall::getRuntimeDefinition();
 583
 584   return CXXInstanceCall::getRuntimeDefinition();
 585 }
 586
 587
 588 const Expr *CXXMemberOperatorCall::getCXXThisExpr() const {
 589   return getOriginExpr()->getArg(0);
 590 }
 591
 592
 593 const BlockDataRegion *BlockCall::getBlockRegion() const {
 594   const Expr *Callee = getOriginExpr()->getCallee();
 595   const MemRegion *DataReg = getSVal(Callee).getAsRegion();
 596
 597   return dyn_cast_or_null<BlockDataRegion>(DataReg);
 598 }
 599
 600 ArrayRef<ParmVarDecl*> BlockCall::parameters() const {
 601   const BlockDecl *D = getDecl();
 602   if (!D)
 603     return nullptr;
 604   return D->parameters();
 605 }
 606
 607 void BlockCall::getExtraInvalidatedValues(ValueList &Values,
 608                   RegionAndSymbolInvalidationTraits *ETraits) const {
 609   // FIXME: This also needs to invalidate captured globals.
 610   if (const MemRegion *R = getBlockRegion())
 611     Values.push_back(loc::MemRegionVal(R));
 612 }
 613
 614 void BlockCall::getInitialStackFrameContents(const StackFrameContext *CalleeCtx,
 615                                              BindingsTy &Bindings) const {
 616   SValBuilder &SVB = getState()->getStateManager().getSValBuilder();
 617   ArrayRef<ParmVarDecl*> Params;
 618   if (isConversionFromLambda()) {
 619     auto *LambdaOperatorDecl = cast<CXXMethodDecl>(CalleeCtx->getDecl());
 620     Params = LambdaOperatorDecl->parameters();
 621
 622     // For blocks converted from a C++ lambda, the callee declaration is the
 623     // operator() method on the lambda so we bind "this" to
 624     // the lambda captured by the block.
 625     const VarRegion *CapturedLambdaRegion = getRegionStoringCapturedLambda();
 626     SVal ThisVal = loc::MemRegionVal(CapturedLambdaRegion);
 627     Loc ThisLoc = SVB.getCXXThis(LambdaOperatorDecl, CalleeCtx);
 628     Bindings.push_back(std::make_pair(ThisLoc, ThisVal));
 629   } else {
 630     Params = cast<BlockDecl>(CalleeCtx->getDecl())->parameters();
 631   }
 632
 633   addParameterValuesToBindings(CalleeCtx, Bindings, SVB, *this,
 634                                Params);
 635 }
 636
 637
 638 SVal CXXConstructorCall::getCXXThisVal() const {
 639   if (Data)
 640     return loc::MemRegionVal(static_cast<const MemRegion *>(Data));
 641   return UnknownVal();
 642 }
 643
 644 void CXXConstructorCall::getExtraInvalidatedValues(ValueList &Values,
 645                            RegionAndSymbolInvalidationTraits *ETraits) const {
 646   if (Data)
 647     Values.push_back(loc::MemRegionVal(static_cast<const MemRegion *>(Data)));
 648 }
 649
 650 void CXXConstructorCall::getInitialStackFrameContents(
 651                                              const StackFrameContext *CalleeCtx,
 652                                              BindingsTy &Bindings) const {
 653   AnyFunctionCall::getInitialStackFrameContents(CalleeCtx, Bindings);
 654
 655   SVal ThisVal = getCXXThisVal();
 656   if (!ThisVal.isUnknown()) {
 657     SValBuilder &SVB = getState()->getStateManager().getSValBuilder();
 658     const CXXMethodDecl *MD = cast<CXXMethodDecl>(CalleeCtx->getDecl());
 659     Loc ThisLoc = SVB.getCXXThis(MD, CalleeCtx);
 660     Bindings.push_back(std::make_pair(ThisLoc, ThisVal));
 661   }
 662 }
 663
 664 SVal CXXDestructorCall::getCXXThisVal() const {
 665   if (Data)
 666     return loc::MemRegionVal(DtorDataTy::getFromOpaqueValue(Data).getPointer());
 667   return UnknownVal();
 668 }
 669
 670 RuntimeDefinition CXXDestructorCall::getRuntimeDefinition() const {
 671   // Base destructors are always called non-virtually.
 672   // Skip CXXInstanceCall's devirtualization logic in this case.
 673   if (isBaseDestructor())
 674     return AnyFunctionCall::getRuntimeDefinition();
 675
 676   return CXXInstanceCall::getRuntimeDefinition();
 677 }
 678
 679 ArrayRef<ParmVarDecl*> ObjCMethodCall::parameters() const {
 680   const ObjCMethodDecl *D = getDecl();
 681   if (!D)
 682     return None;
 683   return D->parameters();
 684 }
 685
 686 void ObjCMethodCall::getExtraInvalidatedValues(
 687     ValueList &Values, RegionAndSymbolInvalidationTraits *ETraits) const {
 688
 689   // If the method call is a setter for property known to be backed by
 690   // an instance variable, don't invalidate the entire receiver, just
 691   // the storage for that instance variable.
 692   if (const ObjCPropertyDecl *PropDecl = getAccessedProperty()) {
 693     if (const ObjCIvarDecl *PropIvar = PropDecl->getPropertyIvarDecl()) {
 694       SVal IvarLVal = getState()->getLValue(PropIvar, getReceiverSVal());
 695       const MemRegion *IvarRegion = IvarLVal.getAsRegion();
 696       ETraits->setTrait(
 697           IvarRegion,
 698           RegionAndSymbolInvalidationTraits::TK_DoNotInvalidateSuperRegion);
 699       ETraits->setTrait(IvarRegion,
 700                         RegionAndSymbolInvalidationTraits::TK_SuppressEscape);
 701       Values.push_back(IvarLVal);
 702       return;
 703     }
 704   }
 705
 706   Values.push_back(getReceiverSVal());
 707 }
 708
 709 SVal ObjCMethodCall::getSelfSVal() const {
 710   const LocationContext *LCtx = getLocationContext();
 711   const ImplicitParamDecl *SelfDecl = LCtx->getSelfDecl();
 712   if (!SelfDecl)
 713     return SVal();
 714   return getState()->getSVal(getState()->getRegion(SelfDecl, LCtx));
 715 }
 716
 717 SVal ObjCMethodCall::getReceiverSVal() const {
 718   // FIXME: Is this the best way to handle class receivers?
 719   if (!isInstanceMessage())
 720     return UnknownVal();
 721
 722   if (const Expr *RecE = getOriginExpr()->getInstanceReceiver())
 723     return getSVal(RecE);
 724
 725   // An instance message with no expression means we are sending to super.
 726   // In this case the object reference is the same as 'self'.
 727   assert(getOriginExpr()->getReceiverKind() == ObjCMessageExpr::SuperInstance);
 728   SVal SelfVal = getSelfSVal();
 729   assert(SelfVal.isValid() && "Calling super but not in ObjC method");
 730   return SelfVal;
 731 }
 732
 733 bool ObjCMethodCall::isReceiverSelfOrSuper() const {
 734   if (getOriginExpr()->getReceiverKind() == ObjCMessageExpr::SuperInstance ||
 735       getOriginExpr()->getReceiverKind() == ObjCMessageExpr::SuperClass)
 736       return true;
 737
 738   if (!isInstanceMessage())
 739     return false;
 740
 741   SVal RecVal = getSVal(getOriginExpr()->getInstanceReceiver());
 742
 743   return (RecVal == getSelfSVal());
 744 }
 745
 746 SourceRange ObjCMethodCall::getSourceRange() const {
 747   switch (getMessageKind()) {
 748   case OCM_Message:
 749     return getOriginExpr()->getSourceRange();
 750   case OCM_PropertyAccess:
 751   case OCM_Subscript:
 752     return getContainingPseudoObjectExpr()->getSourceRange();
 753   }
 754   llvm_unreachable("unknown message kind");
 755 }
 756
 757 typedef llvm::PointerIntPair<const PseudoObjectExpr *, 2> ObjCMessageDataTy;
 758
 759 const PseudoObjectExpr *ObjCMethodCall::getContainingPseudoObjectExpr() const {
 760   assert(Data && "Lazy lookup not yet performed.");
 761   assert(getMessageKind() != OCM_Message && "Explicit message send.");
 762   return ObjCMessageDataTy::getFromOpaqueValue(Data).getPointer();
 763 }
 764
 765 static const Expr *
 766 getSyntacticFromForPseudoObjectExpr(const PseudoObjectExpr *POE) {
 767   const Expr *Syntactic = POE->getSyntacticForm();
 768
 769   // This handles the funny case of assigning to the result of a getter.
 770   // This can happen if the getter returns a non-const reference.
 771   if (const BinaryOperator *BO = dyn_cast<BinaryOperator>(Syntactic))
 772     Syntactic = BO->getLHS();
 773
 774   return Syntactic;
 775 }
 776
 777 ObjCMessageKind ObjCMethodCall::getMessageKind() const {
 778   if (!Data) {
 779
 780     // Find the parent, ignoring implicit casts.
 781     ParentMap &PM = getLocationContext()->getParentMap();
 782     const Stmt *S = PM.getParentIgnoreParenCasts(getOriginExpr());
 783
 784     // Check if parent is a PseudoObjectExpr.
 785     if (const PseudoObjectExpr *POE = dyn_cast_or_null<PseudoObjectExpr>(S)) {
 786       const Expr *Syntactic = getSyntacticFromForPseudoObjectExpr(POE);
 787
 788       ObjCMessageKind K;
 789       switch (Syntactic->getStmtClass()) {
 790       case Stmt::ObjCPropertyRefExprClass:
 791         K = OCM_PropertyAccess;
 792         break;
 793       case Stmt::ObjCSubscriptRefExprClass:
 794         K = OCM_Subscript;
 795         break;
 796       default:
 797         // FIXME: Can this ever happen?
 798         K = OCM_Message;
 799         break;
 800       }
 801
 802       if (K != OCM_Message) {
 803         const_cast<ObjCMethodCall *>(this)->Data
 804           = ObjCMessageDataTy(POE, K).getOpaqueValue();
 805         assert(getMessageKind() == K);
 806         return K;
 807       }
 808     }
 809
 810     const_cast<ObjCMethodCall *>(this)->Data
 811       = ObjCMessageDataTy(nullptr, 1).getOpaqueValue();
 812     assert(getMessageKind() == OCM_Message);
 813     return OCM_Message;
 814   }
 815
 816   ObjCMessageDataTy Info = ObjCMessageDataTy::getFromOpaqueValue(Data);
 817   if (!Info.getPointer())
 818     return OCM_Message;
 819   return static_cast<ObjCMessageKind>(Info.getInt());
 820 }
 821
 822 const ObjCPropertyDecl *ObjCMethodCall::getAccessedProperty() const {
 823   // Look for properties accessed with property syntax (foo.bar = ...)
 824   if ( getMessageKind() == OCM_PropertyAccess) {
 825     const PseudoObjectExpr *POE = getContainingPseudoObjectExpr();
 826     assert(POE && "Property access without PseudoObjectExpr?");
 827
 828     const Expr *Syntactic = getSyntacticFromForPseudoObjectExpr(POE);
 829     auto *RefExpr = cast<ObjCPropertyRefExpr>(Syntactic);
 830
 831     if (RefExpr->isExplicitProperty())
 832       return RefExpr->getExplicitProperty();
 833   }
 834
 835   // Look for properties accessed with method syntax ([foo setBar:...]).
 836   const ObjCMethodDecl *MD = getDecl();
 837   if (!MD || !MD->isPropertyAccessor())
 838     return nullptr;
 839
 840   // Note: This is potentially quite slow.
 841   return MD->findPropertyDecl();
 842 }
 843
 844 bool ObjCMethodCall::canBeOverridenInSubclass(ObjCInterfaceDecl *IDecl,
 845                                              Selector Sel) const {
 846   assert(IDecl);
 847   const SourceManager &SM =
 848     getState()->getStateManager().getContext().getSourceManager();
 849
 850   // If the class interface is declared inside the main file, assume it is not
 851   // subcassed.
 852   // TODO: It could actually be subclassed if the subclass is private as well.
 853   // This is probably very rare.
 854   SourceLocation InterfLoc = IDecl->getEndOfDefinitionLoc();
 855   if (InterfLoc.isValid() && SM.isInMainFile(InterfLoc))
 856     return false;
 857
 858   // Assume that property accessors are not overridden.
 859   if (getMessageKind() == OCM_PropertyAccess)
 860     return false;
 861
 862   // We assume that if the method is public (declared outside of main file) or
 863   // has a parent which publicly declares the method, the method could be
 864   // overridden in a subclass.
 865
 866   // Find the first declaration in the class hierarchy that declares
 867   // the selector.
 868   ObjCMethodDecl *D = nullptr;
 869   while (true) {
 870     D = IDecl->lookupMethod(Sel, true);
 871
 872     // Cannot find a public definition.
 873     if (!D)
 874       return false;
 875
 876     // If outside the main file,
 877     if (D->getLocation().isValid() && !SM.isInMainFile(D->getLocation()))
 878       return true;
 879
 880     if (D->isOverriding()) {
 881       // Search in the superclass on the next iteration.
 882       IDecl = D->getClassInterface();
 883       if (!IDecl)
 884         return false;
 885
 886       IDecl = IDecl->getSuperClass();
 887       if (!IDecl)
 888         return false;
 889
 890       continue;
 891     }
 892
 893     return false;
 894   };
 895
 896   llvm_unreachable("The while loop should always terminate.");
 897 }
 898
 899 RuntimeDefinition ObjCMethodCall::getRuntimeDefinition() const {
 900   const ObjCMessageExpr *E = getOriginExpr();
 901   assert(E);
 902   Selector Sel = E->getSelector();
 903
 904   if (E->isInstanceMessage()) {
 905
 906     // Find the receiver type.
 907     const ObjCObjectPointerType *ReceiverT = nullptr;
 908     bool CanBeSubClassed = false;
 909     QualType SupersType = E->getSuperType();
 910     const MemRegion *Receiver = nullptr;
 911
 912     if (!SupersType.isNull()) {
 913       // Super always means the type of immediate predecessor to the method
 914       // where the call occurs.
 915       ReceiverT = cast<ObjCObjectPointerType>(SupersType);
 916     } else {
 917       Receiver = getReceiverSVal().getAsRegion();
 918       if (!Receiver)
 919         return RuntimeDefinition();
 920
 921       DynamicTypeInfo DTI = getDynamicTypeInfo(getState(), Receiver);
 922       QualType DynType = DTI.getType();
 923       CanBeSubClassed = DTI.canBeASubClass();
 924       ReceiverT = dyn_cast<ObjCObjectPointerType>(DynType);
 925
 926       if (ReceiverT && CanBeSubClassed)
 927         if (ObjCInterfaceDecl *IDecl = ReceiverT->getInterfaceDecl())
 928           if (!canBeOverridenInSubclass(IDecl, Sel))
 929             CanBeSubClassed = false;
 930     }
 931
 932     // Lookup the method implementation.
 933     if (ReceiverT)
 934       if (ObjCInterfaceDecl *IDecl = ReceiverT->getInterfaceDecl()) {
 935         // Repeatedly calling lookupPrivateMethod() is expensive, especially
 936         // when in many cases it returns null.  We cache the results so
 937         // that repeated queries on the same ObjCIntefaceDecl and Selector
 938         // don't incur the same cost.  On some test cases, we can see the
 939         // same query being issued thousands of times.
 940         //
 941         // NOTE: This cache is essentially a "global" variable, but it
 942         // only gets lazily created when we get here.  The value of the
 943         // cache probably comes from it being global across ExprEngines,
 944         // where the same queries may get issued.  If we are worried about
 945         // concurrency, or possibly loading/unloading ASTs, etc., we may
 946         // need to revisit this someday.  In terms of memory, this table
 947         // stays around until clang quits, which also may be bad if we
 948         // need to release memory.
 949         typedef std::pair<const ObjCInterfaceDecl*, Selector>
 950                 PrivateMethodKey;
 951         typedef llvm::DenseMap<PrivateMethodKey,
 952                                Optional<const ObjCMethodDecl *> >
 953                 PrivateMethodCache;
 954
 955         static PrivateMethodCache PMC;
 956         Optional<const ObjCMethodDecl *> &Val = PMC[std::make_pair(IDecl, Sel)];
 957
 958         // Query lookupPrivateMethod() if the cache does not hit.
 959         if (!Val.hasValue()) {
 960           Val = IDecl->lookupPrivateMethod(Sel);
 961
 962           // If the method is a property accessor, we should try to "inline" it
 963           // even if we don't actually have an implementation.
 964           if (!*Val)
 965             if (const ObjCMethodDecl *CompileTimeMD = E->getMethodDecl())
 966               if (CompileTimeMD->isPropertyAccessor()) {
 967                 if (!CompileTimeMD->getSelfDecl() &&
 968                     isa<ObjCCategoryDecl>(CompileTimeMD->getDeclContext())) {
 969                   // If the method is an accessor in a category, and it doesn't
 970                   // have a self declaration, first
 971                   // try to find the method in a class extension. This
 972                   // works around a bug in Sema where multiple accessors
 973                   // are synthesized for properties in class
 974                   // extensions that are redeclared in a category and the
 975                   // the implicit parameters are not filled in for
 976                   // the method on the category.
 977                   // This ensures we find the accessor in the extension, which
 978                   // has the implicit parameters filled in.
 979                   auto *ID = CompileTimeMD->getClassInterface();
 980                   for (auto *CatDecl : ID->visible_extensions()) {
 981                     Val = CatDecl->getMethod(Sel,
 982                                              CompileTimeMD->isInstanceMethod());
 983                     if (*Val)
 984                       break;
 985                   }
 986                 }
 987                 if (!*Val)
 988                   Val = IDecl->lookupInstanceMethod(Sel);
 989               }
 990         }
 991
 992         const ObjCMethodDecl *MD = Val.getValue();
 993         if (CanBeSubClassed)
 994           return RuntimeDefinition(MD, Receiver);
 995         else
 996           return RuntimeDefinition(MD, nullptr);
 997       }
 998
 999   } else {
1000     // This is a class method.
1001     // If we have type info for the receiver class, we are calling via
1002     // class name.
1003     if (ObjCInterfaceDecl *IDecl = E->getReceiverInterface()) {
1004       // Find/Return the method implementation.
1005       return RuntimeDefinition(IDecl->lookupPrivateClassMethod(Sel));
1006     }
1007   }
1008
1009   return RuntimeDefinition();
1010 }
1011
1012 bool ObjCMethodCall::argumentsMayEscape() const {
1013   if (isInSystemHeader() && !isInstanceMessage()) {
1014     Selector Sel = getSelector();
1015     if (Sel.getNumArgs() == 1 &&
1016         Sel.getIdentifierInfoForSlot(0)->isStr("valueWithPointer"))
1017       return true;
1018   }
1019
1020   return CallEvent::argumentsMayEscape();
1021 }
1022
1023 void ObjCMethodCall::getInitialStackFrameContents(
1024                                              const StackFrameContext *CalleeCtx,
1025                                              BindingsTy &Bindings) const {
1026   const ObjCMethodDecl *D = cast<ObjCMethodDecl>(CalleeCtx->getDecl());
1027   SValBuilder &SVB = getState()->getStateManager().getSValBuilder();
1028   addParameterValuesToBindings(CalleeCtx, Bindings, SVB, *this,
1029                                D->parameters());
1030
1031   SVal SelfVal = getReceiverSVal();
1032   if (!SelfVal.isUnknown()) {
1033     const VarDecl *SelfD = CalleeCtx->getAnalysisDeclContext()->getSelfDecl();
1034     MemRegionManager &MRMgr = SVB.getRegionManager();
1035     Loc SelfLoc = SVB.makeLoc(MRMgr.getVarRegion(SelfD, CalleeCtx));
1036     Bindings.push_back(std::make_pair(SelfLoc, SelfVal));
1037   }
1038 }
1039
1040 CallEventRef<>
1041 CallEventManager::getSimpleCall(const CallExpr *CE, ProgramStateRef State,
1042                                 const LocationContext *LCtx) {
1043   if (const CXXMemberCallExpr *MCE = dyn_cast<CXXMemberCallExpr>(CE))
1044     return create<CXXMemberCall>(MCE, State, LCtx);
1045
1046   if (const CXXOperatorCallExpr *OpCE = dyn_cast<CXXOperatorCallExpr>(CE)) {
1047     const FunctionDecl *DirectCallee = OpCE->getDirectCallee();
1048     if (const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(DirectCallee))
1049       if (MD->isInstance())
1050         return create<CXXMemberOperatorCall>(OpCE, State, LCtx);
1051
1052   } else if (CE->getCallee()->getType()->isBlockPointerType()) {
1053     return create<BlockCall>(CE, State, LCtx);
1054   }
1055
1056   // Otherwise, it's a normal function call, static member function call, or
1057   // something we can't reason about.
1058   return create<SimpleFunctionCall>(CE, State, LCtx);
1059 }
1060
1061
1062 CallEventRef<>
1063 CallEventManager::getCaller(const StackFrameContext *CalleeCtx,
1064                             ProgramStateRef State) {
1065   const LocationContext *ParentCtx = CalleeCtx->getParent();
1066   const LocationContext *CallerCtx = ParentCtx->getCurrentStackFrame();
1067   assert(CallerCtx && "This should not be used for top-level stack frames");
1068
1069   const Stmt *CallSite = CalleeCtx->getCallSite();
1070
1071   if (CallSite) {
1072     if (const CallExpr *CE = dyn_cast<CallExpr>(CallSite))
1073       return getSimpleCall(CE, State, CallerCtx);
1074
1075     switch (CallSite->getStmtClass()) {
1076     case Stmt::CXXConstructExprClass:
1077     case Stmt::CXXTemporaryObjectExprClass: {
1078       SValBuilder &SVB = State->getStateManager().getSValBuilder();
1079       const CXXMethodDecl *Ctor = cast<CXXMethodDecl>(CalleeCtx->getDecl());
1080       Loc ThisPtr = SVB.getCXXThis(Ctor, CalleeCtx);
1081       SVal ThisVal = State->getSVal(ThisPtr);
1082
1083       return getCXXConstructorCall(cast<CXXConstructExpr>(CallSite),
1084                                    ThisVal.getAsRegion(), State, CallerCtx);
1085     }
1086     case Stmt::CXXNewExprClass:
1087       return getCXXAllocatorCall(cast<CXXNewExpr>(CallSite), State, CallerCtx);
1088     case Stmt::ObjCMessageExprClass:
1089       return getObjCMethodCall(cast<ObjCMessageExpr>(CallSite),
1090                                State, CallerCtx);
1091     default:
1092       llvm_unreachable("This is not an inlineable statement.");
1093     }
1094   }
1095
1096   // Fall back to the CFG. The only thing we haven't handled yet is
1097   // destructors, though this could change in the future.
1098   const CFGBlock *B = CalleeCtx->getCallSiteBlock();
1099   CFGElement E = (*B)[CalleeCtx->getIndex()];
1100   assert(E.getAs<CFGImplicitDtor>() &&
1101          "All other CFG elements should have exprs");
1102   assert(!E.getAs<CFGTemporaryDtor>() && "We don't handle temporaries yet");
1103
1104   SValBuilder &SVB = State->getStateManager().getSValBuilder();
1105   const CXXDestructorDecl *Dtor = cast<CXXDestructorDecl>(CalleeCtx->getDecl());
1106   Loc ThisPtr = SVB.getCXXThis(Dtor, CalleeCtx);
1107   SVal ThisVal = State->getSVal(ThisPtr);
1108
1109   const Stmt *Trigger;
1110   if (Optional<CFGAutomaticObjDtor> AutoDtor = E.getAs<CFGAutomaticObjDtor>())
1111     Trigger = AutoDtor->getTriggerStmt();
1112   else if (Optional<CFGDeleteDtor> DeleteDtor = E.getAs<CFGDeleteDtor>())
1113     Trigger = cast<Stmt>(DeleteDtor->getDeleteExpr());
1114   else
1115     Trigger = Dtor->getBody();
1116
1117   return getCXXDestructorCall(Dtor, Trigger, ThisVal.getAsRegion(),
1118                               E.getAs<CFGBaseDtor>().hasValue(), State,
1119                               CallerCtx);
1120 }