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