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