CallEvent.cpp revision 9b072b31ee2f41b8e30d1d22142c9ab72ac5ff1f 
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
24using namespace clang;
25using namespace ento;
26
27QualType 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
52static 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
82bool 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
104bool 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.
114static 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.
128static 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
139ProgramStateRef 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
174ProgramPoint 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
191SVal CallEvent::getArgSVal(unsigned Index) const {
192  const Expr *ArgE = getArgExpr(Index);
193  if (!ArgE)
194    return UnknownVal();
195  return getSVal(ArgE);
196}
197
198SourceRange CallEvent::getArgSourceRange(unsigned Index) const {
199  const Expr *ArgE = getArgExpr(Index);
200  if (!ArgE)
201    return SourceRange();
202  return ArgE->getSourceRange();
203}
204
205SVal CallEvent::getReturnValue() const {
206  const Expr *E = getOriginExpr();
207  if (!E)
208    return UndefinedVal();
209  return getSVal(E);
210}
211
212void CallEvent::dump() const {
213  dump(llvm::errs());
214}
215
216void 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
235bool CallEvent::isCallStmt(const Stmt *S) {
236  return isa<CallExpr>(S) || isa<ObjCMessageExpr>(S)
237                          || isa<CXXConstructExpr>(S)
238                          || isa<CXXNewExpr>(S);
239}
240
241QualType 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
270bool 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
283static 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
310CallEvent::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
318CallEvent::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
326void 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
335bool 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
392const 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
401const 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
413void CXXInstanceCall::getExtraInvalidatedValues(ValueList &Values) const {
414  Values.push_back(getCXXThisVal());
415}
416
417SVal 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
429RuntimeDefinition 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
490void 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
524const Expr *CXXMemberCall::getCXXThisExpr() const {
525  return getOriginExpr()->getImplicitObjectArgument();
526}
527
528RuntimeDefinition 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
541const Expr *CXXMemberOperatorCall::getCXXThisExpr() const {
542  return getOriginExpr()->getArg(0);
543}
544
545
546const 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
553CallEvent::param_iterator BlockCall::param_begin() const {
554  const BlockDecl *D = getBlockDecl();
555  if (!D)
556    return 0;
557  return D->param_begin();
558}
559
560CallEvent::param_iterator BlockCall::param_end() const {
561  const BlockDecl *D = getBlockDecl();
562  if (!D)
563    return 0;
564  return D->param_end();
565}
566
567void 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
573void 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
582SVal CXXConstructorCall::getCXXThisVal() const {
583  if (Data)
584    return loc::MemRegionVal(static_cast<const MemRegion *>(Data));
585  return UnknownVal();
586}
587
588void CXXConstructorCall::getExtraInvalidatedValues(ValueList &Values) const {
589  if (Data)
590    Values.push_back(loc::MemRegionVal(static_cast<const MemRegion *>(Data)));
591}
592
593void 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
609SVal CXXDestructorCall::getCXXThisVal() const {
610  if (Data)
611    return loc::MemRegionVal(DtorDataTy::getFromOpaqueValue(Data).getPointer());
612  return UnknownVal();
613}
614
615RuntimeDefinition 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
625CallEvent::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
633CallEvent::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
641void
642ObjCMethodCall::getExtraInvalidatedValues(ValueList &Values) const {
643  Values.push_back(getReceiverSVal());
644}
645
646SVal 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
654SVal 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
670bool 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
683SourceRange 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
694typedef llvm::PointerIntPair<const PseudoObjectExpr *, 2> ObjCMessageDataTy;
695
696const 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
702ObjCMessageKind 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
753bool 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
808RuntimeDefinition 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
891void 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
908CallEventRef<>
909CallEventManager::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
930CallEventRef<>
931CallEventManager::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}
989