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