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