1//===- CallEvent.cpp - Wrapper for all function and method calls ----------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9/// \file This file defines CallEvent and its subclasses, which represent path-
10/// sensitive instances of different kinds of function and method calls
11/// (C, C++, and Objective-C).
12//
13//===----------------------------------------------------------------------===//
14
15#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
16#include "clang/AST/ASTContext.h"
17#include "clang/AST/Attr.h"
18#include "clang/AST/Decl.h"
19#include "clang/AST/DeclBase.h"
20#include "clang/AST/DeclCXX.h"
21#include "clang/AST/DeclObjC.h"
22#include "clang/AST/Expr.h"
23#include "clang/AST/ExprCXX.h"
24#include "clang/AST/ExprObjC.h"
25#include "clang/AST/ParentMap.h"
26#include "clang/AST/Stmt.h"
27#include "clang/AST/Type.h"
28#include "clang/Analysis/AnalysisDeclContext.h"
29#include "clang/Analysis/CFG.h"
30#include "clang/Analysis/CFGStmtMap.h"
31#include "clang/Analysis/PathDiagnostic.h"
32#include "clang/Analysis/ProgramPoint.h"
33#include "clang/Basic/IdentifierTable.h"
34#include "clang/Basic/LLVM.h"
35#include "clang/Basic/SourceLocation.h"
36#include "clang/Basic/SourceManager.h"
37#include "clang/Basic/Specifiers.h"
38#include "clang/CrossTU/CrossTranslationUnit.h"
39#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
40#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h"
41#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicTypeInfo.h"
42#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
43#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
44#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h"
45#include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
46#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
47#include "clang/StaticAnalyzer/Core/PathSensitive/Store.h"
48#include "llvm/ADT/ArrayRef.h"
49#include "llvm/ADT/DenseMap.h"
50#include "llvm/ADT/None.h"
51#include "llvm/ADT/Optional.h"
52#include "llvm/ADT/PointerIntPair.h"
53#include "llvm/ADT/SmallSet.h"
54#include "llvm/ADT/SmallVector.h"
55#include "llvm/ADT/StringExtras.h"
56#include "llvm/ADT/StringRef.h"
57#include "llvm/Support/Casting.h"
58#include "llvm/Support/Compiler.h"
59#include "llvm/Support/Debug.h"
60#include "llvm/Support/ErrorHandling.h"
61#include "llvm/Support/raw_ostream.h"
62#include <cassert>
63#include <utility>
64
65#define DEBUG_TYPE "static-analyzer-call-event"
66
67using namespace clang;
68using namespace ento;
69
70QualType CallEvent::getResultType() const {
71  ASTContext &Ctx = getState()->getStateManager().getContext();
72  const Expr *E = getOriginExpr();
73  if (!E)
74    return Ctx.VoidTy;
75  assert(E);
76
77  QualType ResultTy = E->getType();
78
79  // A function that returns a reference to 'int' will have a result type
80  // of simply 'int'. Check the origin expr's value kind to recover the
81  // proper type.
82  switch (E->getValueKind()) {
83  case VK_LValue:
84    ResultTy = Ctx.getLValueReferenceType(ResultTy);
85    break;
86  case VK_XValue:
87    ResultTy = Ctx.getRValueReferenceType(ResultTy);
88    break;
89  case VK_RValue:
90    // No adjustment is necessary.
91    break;
92  }
93
94  return ResultTy;
95}
96
97static bool isCallback(QualType T) {
98  // If a parameter is a block or a callback, assume it can modify pointer.
99  if (T->isBlockPointerType() ||
100      T->isFunctionPointerType() ||
101      T->isObjCSelType())
102    return true;
103
104  // Check if a callback is passed inside a struct (for both, struct passed by
105  // reference and by value). Dig just one level into the struct for now.
106
107  if (T->isAnyPointerType() || T->isReferenceType())
108    T = T->getPointeeType();
109
110  if (const RecordType *RT = T->getAsStructureType()) {
111    const RecordDecl *RD = RT->getDecl();
112    for (const auto *I : RD->fields()) {
113      QualType FieldT = I->getType();
114      if (FieldT->isBlockPointerType() || FieldT->isFunctionPointerType())
115        return true;
116    }
117  }
118  return false;
119}
120
121static bool isVoidPointerToNonConst(QualType T) {
122  if (const auto *PT = T->getAs<PointerType>()) {
123    QualType PointeeTy = PT->getPointeeType();
124    if (PointeeTy.isConstQualified())
125      return false;
126    return PointeeTy->isVoidType();
127  } else
128    return false;
129}
130
131bool CallEvent::hasNonNullArgumentsWithType(bool (*Condition)(QualType)) const {
132  unsigned NumOfArgs = getNumArgs();
133
134  // If calling using a function pointer, assume the function does not
135  // satisfy the callback.
136  // TODO: We could check the types of the arguments here.
137  if (!getDecl())
138    return false;
139
140  unsigned Idx = 0;
141  for (CallEvent::param_type_iterator I = param_type_begin(),
142                                      E = param_type_end();
143       I != E && Idx < NumOfArgs; ++I, ++Idx) {
144    // If the parameter is 0, it's harmless.
145    if (getArgSVal(Idx).isZeroConstant())
146      continue;
147
148    if (Condition(*I))
149      return true;
150  }
151  return false;
152}
153
154bool CallEvent::hasNonZeroCallbackArg() const {
155  return hasNonNullArgumentsWithType(isCallback);
156}
157
158bool CallEvent::hasVoidPointerToNonConstArg() const {
159  return hasNonNullArgumentsWithType(isVoidPointerToNonConst);
160}
161
162bool CallEvent::isGlobalCFunction(StringRef FunctionName) const {
163  const auto *FD = dyn_cast_or_null<FunctionDecl>(getDecl());
164  if (!FD)
165    return false;
166
167  return CheckerContext::isCLibraryFunction(FD, FunctionName);
168}
169
170AnalysisDeclContext *CallEvent::getCalleeAnalysisDeclContext() const {
171  const Decl *D = getDecl();
172  if (!D)
173    return nullptr;
174
175  AnalysisDeclContext *ADC =
176      LCtx->getAnalysisDeclContext()->getManager()->getContext(D);
177
178  return ADC;
179}
180
181const StackFrameContext *
182CallEvent::getCalleeStackFrame(unsigned BlockCount) const {
183  AnalysisDeclContext *ADC = getCalleeAnalysisDeclContext();
184  if (!ADC)
185    return nullptr;
186
187  const Expr *E = getOriginExpr();
188  if (!E)
189    return nullptr;
190
191  // Recover CFG block via reverse lookup.
192  // TODO: If we were to keep CFG element information as part of the CallEvent
193  // instead of doing this reverse lookup, we would be able to build the stack
194  // frame for non-expression-based calls, and also we wouldn't need the reverse
195  // lookup.
196  CFGStmtMap *Map = LCtx->getAnalysisDeclContext()->getCFGStmtMap();
197  const CFGBlock *B = Map->getBlock(E);
198  assert(B);
199
200  // Also recover CFG index by scanning the CFG block.
201  unsigned Idx = 0, Sz = B->size();
202  for (; Idx < Sz; ++Idx)
203    if (auto StmtElem = (*B)[Idx].getAs<CFGStmt>())
204      if (StmtElem->getStmt() == E)
205        break;
206  assert(Idx < Sz);
207
208  return ADC->getManager()->getStackFrame(ADC, LCtx, E, B, BlockCount, Idx);
209}
210
211const ParamVarRegion
212*CallEvent::getParameterLocation(unsigned Index, unsigned BlockCount) const {
213  const StackFrameContext *SFC = getCalleeStackFrame(BlockCount);
214  // We cannot construct a VarRegion without a stack frame.
215  if (!SFC)
216    return nullptr;
217
218  const ParamVarRegion *PVR =
219    State->getStateManager().getRegionManager().getParamVarRegion(
220        getOriginExpr(), Index, SFC);
221  return PVR;
222}
223
224/// Returns true if a type is a pointer-to-const or reference-to-const
225/// with no further indirection.
226static bool isPointerToConst(QualType Ty) {
227  QualType PointeeTy = Ty->getPointeeType();
228  if (PointeeTy == QualType())
229    return false;
230  if (!PointeeTy.isConstQualified())
231    return false;
232  if (PointeeTy->isAnyPointerType())
233    return false;
234  return true;
235}
236
237// Try to retrieve the function declaration and find the function parameter
238// types which are pointers/references to a non-pointer const.
239// We will not invalidate the corresponding argument regions.
240static void findPtrToConstParams(llvm::SmallSet<unsigned, 4> &PreserveArgs,
241                                 const CallEvent &Call) {
242  unsigned Idx = 0;
243  for (CallEvent::param_type_iterator I = Call.param_type_begin(),
244                                      E = Call.param_type_end();
245       I != E; ++I, ++Idx) {
246    if (isPointerToConst(*I))
247      PreserveArgs.insert(Idx);
248  }
249}
250
251ProgramStateRef CallEvent::invalidateRegions(unsigned BlockCount,
252                                             ProgramStateRef Orig) const {
253  ProgramStateRef Result = (Orig ? Orig : getState());
254
255  // Don't invalidate anything if the callee is marked pure/const.
256  if (const Decl *callee = getDecl())
257    if (callee->hasAttr<PureAttr>() || callee->hasAttr<ConstAttr>())
258      return Result;
259
260  SmallVector<SVal, 8> ValuesToInvalidate;
261  RegionAndSymbolInvalidationTraits ETraits;
262
263  getExtraInvalidatedValues(ValuesToInvalidate, &ETraits);
264
265  // Indexes of arguments whose values will be preserved by the call.
266  llvm::SmallSet<unsigned, 4> PreserveArgs;
267  if (!argumentsMayEscape())
268    findPtrToConstParams(PreserveArgs, *this);
269
270  for (unsigned Idx = 0, Count = getNumArgs(); Idx != Count; ++Idx) {
271    // Mark this region for invalidation.  We batch invalidate regions
272    // below for efficiency.
273    if (PreserveArgs.count(Idx))
274      if (const MemRegion *MR = getArgSVal(Idx).getAsRegion())
275        ETraits.setTrait(MR->getBaseRegion(),
276                        RegionAndSymbolInvalidationTraits::TK_PreserveContents);
277        // TODO: Factor this out + handle the lower level const pointers.
278
279    ValuesToInvalidate.push_back(getArgSVal(Idx));
280
281    // If a function accepts an object by argument (which would of course be a
282    // temporary that isn't lifetime-extended), invalidate the object itself,
283    // not only other objects reachable from it. This is necessary because the
284    // destructor has access to the temporary object after the call.
285    // TODO: Support placement arguments once we start
286    // constructing them directly.
287    // TODO: This is unnecessary when there's no destructor, but that's
288    // currently hard to figure out.
289    if (getKind() != CE_CXXAllocator)
290      if (isArgumentConstructedDirectly(Idx))
291        if (auto AdjIdx = getAdjustedParameterIndex(Idx))
292          if (const TypedValueRegion *TVR =
293                  getParameterLocation(*AdjIdx, BlockCount))
294            ValuesToInvalidate.push_back(loc::MemRegionVal(TVR));
295  }
296
297  // Invalidate designated regions using the batch invalidation API.
298  // NOTE: Even if RegionsToInvalidate is empty, we may still invalidate
299  //  global variables.
300  return Result->invalidateRegions(ValuesToInvalidate, getOriginExpr(),
301                                   BlockCount, getLocationContext(),
302                                   /*CausedByPointerEscape*/ true,
303                                   /*Symbols=*/nullptr, this, &ETraits);
304}
305
306ProgramPoint CallEvent::getProgramPoint(bool IsPreVisit,
307                                        const ProgramPointTag *Tag) const {
308  if (const Expr *E = getOriginExpr()) {
309    if (IsPreVisit)
310      return PreStmt(E, getLocationContext(), Tag);
311    return PostStmt(E, getLocationContext(), Tag);
312  }
313
314  const Decl *D = getDecl();
315  assert(D && "Cannot get a program point without a statement or decl");
316
317  SourceLocation Loc = getSourceRange().getBegin();
318  if (IsPreVisit)
319    return PreImplicitCall(D, Loc, getLocationContext(), Tag);
320  return PostImplicitCall(D, Loc, getLocationContext(), Tag);
321}
322
323bool CallEvent::isCalled(const CallDescription &CD) const {
324  // FIXME: Add ObjC Message support.
325  if (getKind() == CE_ObjCMessage)
326    return false;
327
328  const IdentifierInfo *II = getCalleeIdentifier();
329  if (!II)
330    return false;
331  const FunctionDecl *FD = dyn_cast_or_null<FunctionDecl>(getDecl());
332  if (!FD)
333    return false;
334
335  if (CD.Flags & CDF_MaybeBuiltin) {
336    return CheckerContext::isCLibraryFunction(FD, CD.getFunctionName()) &&
337           (!CD.RequiredArgs || CD.RequiredArgs <= getNumArgs()) &&
338           (!CD.RequiredParams || CD.RequiredParams <= parameters().size());
339  }
340
341  if (!CD.IsLookupDone) {
342    CD.IsLookupDone = true;
343    CD.II = &getState()->getStateManager().getContext().Idents.get(
344        CD.getFunctionName());
345  }
346
347  if (II != CD.II)
348    return false;
349
350  // If CallDescription provides prefix names, use them to improve matching
351  // accuracy.
352  if (CD.QualifiedName.size() > 1 && FD) {
353    const DeclContext *Ctx = FD->getDeclContext();
354    // See if we'll be able to match them all.
355    size_t NumUnmatched = CD.QualifiedName.size() - 1;
356    for (; Ctx && isa<NamedDecl>(Ctx); Ctx = Ctx->getParent()) {
357      if (NumUnmatched == 0)
358        break;
359
360      if (const auto *ND = dyn_cast<NamespaceDecl>(Ctx)) {
361        if (ND->getName() == CD.QualifiedName[NumUnmatched - 1])
362          --NumUnmatched;
363        continue;
364      }
365
366      if (const auto *RD = dyn_cast<RecordDecl>(Ctx)) {
367        if (RD->getName() == CD.QualifiedName[NumUnmatched - 1])
368          --NumUnmatched;
369        continue;
370      }
371    }
372
373    if (NumUnmatched > 0)
374      return false;
375  }
376
377  return (!CD.RequiredArgs || CD.RequiredArgs == getNumArgs()) &&
378         (!CD.RequiredParams || CD.RequiredParams == parameters().size());
379}
380
381SVal CallEvent::getArgSVal(unsigned Index) const {
382  const Expr *ArgE = getArgExpr(Index);
383  if (!ArgE)
384    return UnknownVal();
385  return getSVal(ArgE);
386}
387
388SourceRange CallEvent::getArgSourceRange(unsigned Index) const {
389  const Expr *ArgE = getArgExpr(Index);
390  if (!ArgE)
391    return {};
392  return ArgE->getSourceRange();
393}
394
395SVal CallEvent::getReturnValue() const {
396  const Expr *E = getOriginExpr();
397  if (!E)
398    return UndefinedVal();
399  return getSVal(E);
400}
401
402LLVM_DUMP_METHOD void CallEvent::dump() const { dump(llvm::errs()); }
403
404void CallEvent::dump(raw_ostream &Out) const {
405  ASTContext &Ctx = getState()->getStateManager().getContext();
406  if (const Expr *E = getOriginExpr()) {
407    E->printPretty(Out, nullptr, Ctx.getPrintingPolicy());
408    Out << "\n";
409    return;
410  }
411
412  if (const Decl *D = getDecl()) {
413    Out << "Call to ";
414    D->print(Out, Ctx.getPrintingPolicy());
415    return;
416  }
417
418  Out << "Unknown call (type " << getKindAsString() << ")";
419}
420
421bool CallEvent::isCallStmt(const Stmt *S) {
422  return isa<CallExpr>(S) || isa<ObjCMessageExpr>(S)
423                          || isa<CXXConstructExpr>(S)
424                          || isa<CXXNewExpr>(S);
425}
426
427QualType CallEvent::getDeclaredResultType(const Decl *D) {
428  assert(D);
429  if (const auto *FD = dyn_cast<FunctionDecl>(D))
430    return FD->getReturnType();
431  if (const auto *MD = dyn_cast<ObjCMethodDecl>(D))
432    return MD->getReturnType();
433  if (const auto *BD = dyn_cast<BlockDecl>(D)) {
434    // Blocks are difficult because the return type may not be stored in the
435    // BlockDecl itself. The AST should probably be enhanced, but for now we
436    // just do what we can.
437    // If the block is declared without an explicit argument list, the
438    // signature-as-written just includes the return type, not the entire
439    // function type.
440    // FIXME: All blocks should have signatures-as-written, even if the return
441    // type is inferred. (That's signified with a dependent result type.)
442    if (const TypeSourceInfo *TSI = BD->getSignatureAsWritten()) {
443      QualType Ty = TSI->getType();
444      if (const FunctionType *FT = Ty->getAs<FunctionType>())
445        Ty = FT->getReturnType();
446      if (!Ty->isDependentType())
447        return Ty;
448    }
449
450    return {};
451  }
452
453  llvm_unreachable("unknown callable kind");
454}
455
456bool CallEvent::isVariadic(const Decl *D) {
457  assert(D);
458
459  if (const auto *FD = dyn_cast<FunctionDecl>(D))
460    return FD->isVariadic();
461  if (const auto *MD = dyn_cast<ObjCMethodDecl>(D))
462    return MD->isVariadic();
463  if (const auto *BD = dyn_cast<BlockDecl>(D))
464    return BD->isVariadic();
465
466  llvm_unreachable("unknown callable kind");
467}
468
469static void addParameterValuesToBindings(const StackFrameContext *CalleeCtx,
470                                         CallEvent::BindingsTy &Bindings,
471                                         SValBuilder &SVB,
472                                         const CallEvent &Call,
473                                         ArrayRef<ParmVarDecl*> parameters) {
474  MemRegionManager &MRMgr = SVB.getRegionManager();
475
476  // If the function has fewer parameters than the call has arguments, we simply
477  // do not bind any values to them.
478  unsigned NumArgs = Call.getNumArgs();
479  unsigned Idx = 0;
480  ArrayRef<ParmVarDecl*>::iterator I = parameters.begin(), E = parameters.end();
481  for (; I != E && Idx < NumArgs; ++I, ++Idx) {
482    assert(*I && "Formal parameter has no decl?");
483
484    // TODO: Support allocator calls.
485    if (Call.getKind() != CE_CXXAllocator)
486      if (Call.isArgumentConstructedDirectly(Call.getASTArgumentIndex(Idx)))
487        continue;
488
489    // TODO: Allocators should receive the correct size and possibly alignment,
490    // determined in compile-time but not represented as arg-expressions,
491    // which makes getArgSVal() fail and return UnknownVal.
492    SVal ArgVal = Call.getArgSVal(Idx);
493    if (!ArgVal.isUnknown()) {
494      Loc ParamLoc = SVB.makeLoc(
495          MRMgr.getParamVarRegion(Call.getOriginExpr(), Idx, CalleeCtx));
496      Bindings.push_back(std::make_pair(ParamLoc, ArgVal));
497    }
498  }
499
500  // FIXME: Variadic arguments are not handled at all right now.
501}
502
503const ConstructionContext *CallEvent::getConstructionContext() const {
504  const StackFrameContext *StackFrame = getCalleeStackFrame(0);
505  if (!StackFrame)
506    return nullptr;
507
508  const CFGElement Element = StackFrame->getCallSiteCFGElement();
509  if (const auto Ctor = Element.getAs<CFGConstructor>()) {
510    return Ctor->getConstructionContext();
511  }
512
513  if (const auto RecCall = Element.getAs<CFGCXXRecordTypedCall>()) {
514    return RecCall->getConstructionContext();
515  }
516
517  return nullptr;
518}
519
520Optional<SVal>
521CallEvent::getReturnValueUnderConstruction() const {
522  const auto *CC = getConstructionContext();
523  if (!CC)
524    return None;
525
526  EvalCallOptions CallOpts;
527  ExprEngine &Engine = getState()->getStateManager().getOwningEngine();
528  SVal RetVal =
529    Engine.computeObjectUnderConstruction(getOriginExpr(), getState(),
530                                          getLocationContext(), CC, CallOpts);
531  return RetVal;
532}
533
534ArrayRef<ParmVarDecl*> AnyFunctionCall::parameters() const {
535  const FunctionDecl *D = getDecl();
536  if (!D)
537    return None;
538  return D->parameters();
539}
540
541RuntimeDefinition AnyFunctionCall::getRuntimeDefinition() const {
542  const FunctionDecl *FD = getDecl();
543  if (!FD)
544    return {};
545
546  // Note that the AnalysisDeclContext will have the FunctionDecl with
547  // the definition (if one exists).
548  AnalysisDeclContext *AD =
549    getLocationContext()->getAnalysisDeclContext()->
550    getManager()->getContext(FD);
551  bool IsAutosynthesized;
552  Stmt* Body = AD->getBody(IsAutosynthesized);
553  LLVM_DEBUG({
554    if (IsAutosynthesized)
555      llvm::dbgs() << "Using autosynthesized body for " << FD->getName()
556                   << "\n";
557  });
558  if (Body) {
559    const Decl* Decl = AD->getDecl();
560    return RuntimeDefinition(Decl);
561  }
562
563  ExprEngine &Engine = getState()->getStateManager().getOwningEngine();
564  AnalyzerOptions &Opts = Engine.getAnalysisManager().options;
565
566  // Try to get CTU definition only if CTUDir is provided.
567  if (!Opts.IsNaiveCTUEnabled)
568    return {};
569
570  cross_tu::CrossTranslationUnitContext &CTUCtx =
571      *Engine.getCrossTranslationUnitContext();
572  llvm::Expected<const FunctionDecl *> CTUDeclOrError =
573      CTUCtx.getCrossTUDefinition(FD, Opts.CTUDir, Opts.CTUIndexName,
574                                  Opts.DisplayCTUProgress);
575
576  if (!CTUDeclOrError) {
577    handleAllErrors(CTUDeclOrError.takeError(),
578                    [&](const cross_tu::IndexError &IE) {
579                      CTUCtx.emitCrossTUDiagnostics(IE);
580                    });
581    return {};
582  }
583
584  return RuntimeDefinition(*CTUDeclOrError);
585}
586
587void AnyFunctionCall::getInitialStackFrameContents(
588                                        const StackFrameContext *CalleeCtx,
589                                        BindingsTy &Bindings) const {
590  const auto *D = cast<FunctionDecl>(CalleeCtx->getDecl());
591  SValBuilder &SVB = getState()->getStateManager().getSValBuilder();
592  addParameterValuesToBindings(CalleeCtx, Bindings, SVB, *this,
593                               D->parameters());
594}
595
596bool AnyFunctionCall::argumentsMayEscape() const {
597  if (CallEvent::argumentsMayEscape() || hasVoidPointerToNonConstArg())
598    return true;
599
600  const FunctionDecl *D = getDecl();
601  if (!D)
602    return true;
603
604  const IdentifierInfo *II = D->getIdentifier();
605  if (!II)
606    return false;
607
608  // This set of "escaping" APIs is
609
610  // - 'int pthread_setspecific(ptheread_key k, const void *)' stores a
611  //   value into thread local storage. The value can later be retrieved with
612  //   'void *ptheread_getspecific(pthread_key)'. So even thought the
613  //   parameter is 'const void *', the region escapes through the call.
614  if (II->isStr("pthread_setspecific"))
615    return true;
616
617  // - xpc_connection_set_context stores a value which can be retrieved later
618  //   with xpc_connection_get_context.
619  if (II->isStr("xpc_connection_set_context"))
620    return true;
621
622  // - funopen - sets a buffer for future IO calls.
623  if (II->isStr("funopen"))
624    return true;
625
626  // - __cxa_demangle - can reallocate memory and can return the pointer to
627  // the input buffer.
628  if (II->isStr("__cxa_demangle"))
629    return true;
630
631  StringRef FName = II->getName();
632
633  // - CoreFoundation functions that end with "NoCopy" can free a passed-in
634  //   buffer even if it is const.
635  if (FName.endswith("NoCopy"))
636    return true;
637
638  // - NSXXInsertXX, for example NSMapInsertIfAbsent, since they can
639  //   be deallocated by NSMapRemove.
640  if (FName.startswith("NS") && (FName.find("Insert") != StringRef::npos))
641    return true;
642
643  // - Many CF containers allow objects to escape through custom
644  //   allocators/deallocators upon container construction. (PR12101)
645  if (FName.startswith("CF") || FName.startswith("CG")) {
646    return StrInStrNoCase(FName, "InsertValue")  != StringRef::npos ||
647           StrInStrNoCase(FName, "AddValue")     != StringRef::npos ||
648           StrInStrNoCase(FName, "SetValue")     != StringRef::npos ||
649           StrInStrNoCase(FName, "WithData")     != StringRef::npos ||
650           StrInStrNoCase(FName, "AppendValue")  != StringRef::npos ||
651           StrInStrNoCase(FName, "SetAttribute") != StringRef::npos;
652  }
653
654  return false;
655}
656
657const FunctionDecl *SimpleFunctionCall::getDecl() const {
658  const FunctionDecl *D = getOriginExpr()->getDirectCallee();
659  if (D)
660    return D;
661
662  return getSVal(getOriginExpr()->getCallee()).getAsFunctionDecl();
663}
664
665const FunctionDecl *CXXInstanceCall::getDecl() const {
666  const auto *CE = cast_or_null<CallExpr>(getOriginExpr());
667  if (!CE)
668    return AnyFunctionCall::getDecl();
669
670  const FunctionDecl *D = CE->getDirectCallee();
671  if (D)
672    return D;
673
674  return getSVal(CE->getCallee()).getAsFunctionDecl();
675}
676
677void CXXInstanceCall::getExtraInvalidatedValues(
678    ValueList &Values, RegionAndSymbolInvalidationTraits *ETraits) const {
679  SVal ThisVal = getCXXThisVal();
680  Values.push_back(ThisVal);
681
682  // Don't invalidate if the method is const and there are no mutable fields.
683  if (const auto *D = cast_or_null<CXXMethodDecl>(getDecl())) {
684    if (!D->isConst())
685      return;
686    // Get the record decl for the class of 'This'. D->getParent() may return a
687    // base class decl, rather than the class of the instance which needs to be
688    // checked for mutable fields.
689    // TODO: We might as well look at the dynamic type of the object.
690    const Expr *Ex = getCXXThisExpr()->ignoreParenBaseCasts();
691    QualType T = Ex->getType();
692    if (T->isPointerType()) // Arrow or implicit-this syntax?
693      T = T->getPointeeType();
694    const CXXRecordDecl *ParentRecord = T->getAsCXXRecordDecl();
695    assert(ParentRecord);
696    if (ParentRecord->hasMutableFields())
697      return;
698    // Preserve CXXThis.
699    const MemRegion *ThisRegion = ThisVal.getAsRegion();
700    if (!ThisRegion)
701      return;
702
703    ETraits->setTrait(ThisRegion->getBaseRegion(),
704                      RegionAndSymbolInvalidationTraits::TK_PreserveContents);
705  }
706}
707
708SVal CXXInstanceCall::getCXXThisVal() const {
709  const Expr *Base = getCXXThisExpr();
710  // FIXME: This doesn't handle an overloaded ->* operator.
711  if (!Base)
712    return UnknownVal();
713
714  SVal ThisVal = getSVal(Base);
715  assert(ThisVal.isUnknownOrUndef() || ThisVal.getAs<Loc>());
716  return ThisVal;
717}
718
719RuntimeDefinition CXXInstanceCall::getRuntimeDefinition() const {
720  // Do we have a decl at all?
721  const Decl *D = getDecl();
722  if (!D)
723    return {};
724
725  // If the method is non-virtual, we know we can inline it.
726  const auto *MD = cast<CXXMethodDecl>(D);
727  if (!MD->isVirtual())
728    return AnyFunctionCall::getRuntimeDefinition();
729
730  // Do we know the implicit 'this' object being called?
731  const MemRegion *R = getCXXThisVal().getAsRegion();
732  if (!R)
733    return {};
734
735  // Do we know anything about the type of 'this'?
736  DynamicTypeInfo DynType = getDynamicTypeInfo(getState(), R);
737  if (!DynType.isValid())
738    return {};
739
740  // Is the type a C++ class? (This is mostly a defensive check.)
741  QualType RegionType = DynType.getType()->getPointeeType();
742  assert(!RegionType.isNull() && "DynamicTypeInfo should always be a pointer.");
743
744  const CXXRecordDecl *RD = RegionType->getAsCXXRecordDecl();
745  if (!RD || !RD->hasDefinition())
746    return {};
747
748  // Find the decl for this method in that class.
749  const CXXMethodDecl *Result = MD->getCorrespondingMethodInClass(RD, true);
750  if (!Result) {
751    // We might not even get the original statically-resolved method due to
752    // some particularly nasty casting (e.g. casts to sister classes).
753    // However, we should at least be able to search up and down our own class
754    // hierarchy, and some real bugs have been caught by checking this.
755    assert(!RD->isDerivedFrom(MD->getParent()) && "Couldn't find known method");
756
757    // FIXME: This is checking that our DynamicTypeInfo is at least as good as
758    // the static type. However, because we currently don't update
759    // DynamicTypeInfo when an object is cast, we can't actually be sure the
760    // DynamicTypeInfo is up to date. This assert should be re-enabled once
761    // this is fixed. <rdar://problem/12287087>
762    //assert(!MD->getParent()->isDerivedFrom(RD) && "Bad DynamicTypeInfo");
763
764    return {};
765  }
766
767  // Does the decl that we found have an implementation?
768  const FunctionDecl *Definition;
769  if (!Result->hasBody(Definition)) {
770    if (!DynType.canBeASubClass())
771      return AnyFunctionCall::getRuntimeDefinition();
772    return {};
773  }
774
775  // We found a definition. If we're not sure that this devirtualization is
776  // actually what will happen at runtime, make sure to provide the region so
777  // that ExprEngine can decide what to do with it.
778  if (DynType.canBeASubClass())
779    return RuntimeDefinition(Definition, R->StripCasts());
780  return RuntimeDefinition(Definition, /*DispatchRegion=*/nullptr);
781}
782
783void CXXInstanceCall::getInitialStackFrameContents(
784                                            const StackFrameContext *CalleeCtx,
785                                            BindingsTy &Bindings) const {
786  AnyFunctionCall::getInitialStackFrameContents(CalleeCtx, Bindings);
787
788  // Handle the binding of 'this' in the new stack frame.
789  SVal ThisVal = getCXXThisVal();
790  if (!ThisVal.isUnknown()) {
791    ProgramStateManager &StateMgr = getState()->getStateManager();
792    SValBuilder &SVB = StateMgr.getSValBuilder();
793
794    const auto *MD = cast<CXXMethodDecl>(CalleeCtx->getDecl());
795    Loc ThisLoc = SVB.getCXXThis(MD, CalleeCtx);
796
797    // If we devirtualized to a different member function, we need to make sure
798    // we have the proper layering of CXXBaseObjectRegions.
799    if (MD->getCanonicalDecl() != getDecl()->getCanonicalDecl()) {
800      ASTContext &Ctx = SVB.getContext();
801      const CXXRecordDecl *Class = MD->getParent();
802      QualType Ty = Ctx.getPointerType(Ctx.getRecordType(Class));
803
804      // FIXME: CallEvent maybe shouldn't be directly accessing StoreManager.
805      bool Failed;
806      ThisVal = StateMgr.getStoreManager().attemptDownCast(ThisVal, Ty, Failed);
807      if (Failed) {
808        // We might have suffered some sort of placement new earlier, so
809        // we're constructing in a completely unexpected storage.
810        // Fall back to a generic pointer cast for this-value.
811        const CXXMethodDecl *StaticMD = cast<CXXMethodDecl>(getDecl());
812        const CXXRecordDecl *StaticClass = StaticMD->getParent();
813        QualType StaticTy = Ctx.getPointerType(Ctx.getRecordType(StaticClass));
814        ThisVal = SVB.evalCast(ThisVal, Ty, StaticTy);
815      }
816    }
817
818    if (!ThisVal.isUnknown())
819      Bindings.push_back(std::make_pair(ThisLoc, ThisVal));
820  }
821}
822
823const Expr *CXXMemberCall::getCXXThisExpr() const {
824  return getOriginExpr()->getImplicitObjectArgument();
825}
826
827RuntimeDefinition CXXMemberCall::getRuntimeDefinition() const {
828  // C++11 [expr.call]p1: ...If the selected function is non-virtual, or if the
829  // id-expression in the class member access expression is a qualified-id,
830  // that function is called. Otherwise, its final overrider in the dynamic type
831  // of the object expression is called.
832  if (const auto *ME = dyn_cast<MemberExpr>(getOriginExpr()->getCallee()))
833    if (ME->hasQualifier())
834      return AnyFunctionCall::getRuntimeDefinition();
835
836  return CXXInstanceCall::getRuntimeDefinition();
837}
838
839const Expr *CXXMemberOperatorCall::getCXXThisExpr() const {
840  return getOriginExpr()->getArg(0);
841}
842
843const BlockDataRegion *BlockCall::getBlockRegion() const {
844  const Expr *Callee = getOriginExpr()->getCallee();
845  const MemRegion *DataReg = getSVal(Callee).getAsRegion();
846
847  return dyn_cast_or_null<BlockDataRegion>(DataReg);
848}
849
850ArrayRef<ParmVarDecl*> BlockCall::parameters() const {
851  const BlockDecl *D = getDecl();
852  if (!D)
853    return None;
854  return D->parameters();
855}
856
857void BlockCall::getExtraInvalidatedValues(ValueList &Values,
858                  RegionAndSymbolInvalidationTraits *ETraits) const {
859  // FIXME: This also needs to invalidate captured globals.
860  if (const MemRegion *R = getBlockRegion())
861    Values.push_back(loc::MemRegionVal(R));
862}
863
864void BlockCall::getInitialStackFrameContents(const StackFrameContext *CalleeCtx,
865                                             BindingsTy &Bindings) const {
866  SValBuilder &SVB = getState()->getStateManager().getSValBuilder();
867  ArrayRef<ParmVarDecl*> Params;
868  if (isConversionFromLambda()) {
869    auto *LambdaOperatorDecl = cast<CXXMethodDecl>(CalleeCtx->getDecl());
870    Params = LambdaOperatorDecl->parameters();
871
872    // For blocks converted from a C++ lambda, the callee declaration is the
873    // operator() method on the lambda so we bind "this" to
874    // the lambda captured by the block.
875    const VarRegion *CapturedLambdaRegion = getRegionStoringCapturedLambda();
876    SVal ThisVal = loc::MemRegionVal(CapturedLambdaRegion);
877    Loc ThisLoc = SVB.getCXXThis(LambdaOperatorDecl, CalleeCtx);
878    Bindings.push_back(std::make_pair(ThisLoc, ThisVal));
879  } else {
880    Params = cast<BlockDecl>(CalleeCtx->getDecl())->parameters();
881  }
882
883  addParameterValuesToBindings(CalleeCtx, Bindings, SVB, *this,
884                               Params);
885}
886
887SVal AnyCXXConstructorCall::getCXXThisVal() const {
888  if (Data)
889    return loc::MemRegionVal(static_cast<const MemRegion *>(Data));
890  return UnknownVal();
891}
892
893void AnyCXXConstructorCall::getExtraInvalidatedValues(ValueList &Values,
894                           RegionAndSymbolInvalidationTraits *ETraits) const {
895  SVal V = getCXXThisVal();
896  if (SymbolRef Sym = V.getAsSymbol(true))
897    ETraits->setTrait(Sym,
898                      RegionAndSymbolInvalidationTraits::TK_SuppressEscape);
899  Values.push_back(V);
900}
901
902void AnyCXXConstructorCall::getInitialStackFrameContents(
903                                             const StackFrameContext *CalleeCtx,
904                                             BindingsTy &Bindings) const {
905  AnyFunctionCall::getInitialStackFrameContents(CalleeCtx, Bindings);
906
907  SVal ThisVal = getCXXThisVal();
908  if (!ThisVal.isUnknown()) {
909    SValBuilder &SVB = getState()->getStateManager().getSValBuilder();
910    const auto *MD = cast<CXXMethodDecl>(CalleeCtx->getDecl());
911    Loc ThisLoc = SVB.getCXXThis(MD, CalleeCtx);
912    Bindings.push_back(std::make_pair(ThisLoc, ThisVal));
913  }
914}
915
916const StackFrameContext *
917CXXInheritedConstructorCall::getInheritingStackFrame() const {
918  const StackFrameContext *SFC = getLocationContext()->getStackFrame();
919  while (isa<CXXInheritedCtorInitExpr>(SFC->getCallSite()))
920    SFC = SFC->getParent()->getStackFrame();
921  return SFC;
922}
923
924SVal CXXDestructorCall::getCXXThisVal() const {
925  if (Data)
926    return loc::MemRegionVal(DtorDataTy::getFromOpaqueValue(Data).getPointer());
927  return UnknownVal();
928}
929
930RuntimeDefinition CXXDestructorCall::getRuntimeDefinition() const {
931  // Base destructors are always called non-virtually.
932  // Skip CXXInstanceCall's devirtualization logic in this case.
933  if (isBaseDestructor())
934    return AnyFunctionCall::getRuntimeDefinition();
935
936  return CXXInstanceCall::getRuntimeDefinition();
937}
938
939ArrayRef<ParmVarDecl*> ObjCMethodCall::parameters() const {
940  const ObjCMethodDecl *D = getDecl();
941  if (!D)
942    return None;
943  return D->parameters();
944}
945
946void ObjCMethodCall::getExtraInvalidatedValues(
947    ValueList &Values, RegionAndSymbolInvalidationTraits *ETraits) const {
948
949  // If the method call is a setter for property known to be backed by
950  // an instance variable, don't invalidate the entire receiver, just
951  // the storage for that instance variable.
952  if (const ObjCPropertyDecl *PropDecl = getAccessedProperty()) {
953    if (const ObjCIvarDecl *PropIvar = PropDecl->getPropertyIvarDecl()) {
954      SVal IvarLVal = getState()->getLValue(PropIvar, getReceiverSVal());
955      if (const MemRegion *IvarRegion = IvarLVal.getAsRegion()) {
956        ETraits->setTrait(
957          IvarRegion,
958          RegionAndSymbolInvalidationTraits::TK_DoNotInvalidateSuperRegion);
959        ETraits->setTrait(
960          IvarRegion,
961          RegionAndSymbolInvalidationTraits::TK_SuppressEscape);
962        Values.push_back(IvarLVal);
963      }
964      return;
965    }
966  }
967
968  Values.push_back(getReceiverSVal());
969}
970
971SVal ObjCMethodCall::getReceiverSVal() const {
972  // FIXME: Is this the best way to handle class receivers?
973  if (!isInstanceMessage())
974    return UnknownVal();
975
976  if (const Expr *RecE = getOriginExpr()->getInstanceReceiver())
977    return getSVal(RecE);
978
979  // An instance message with no expression means we are sending to super.
980  // In this case the object reference is the same as 'self'.
981  assert(getOriginExpr()->getReceiverKind() == ObjCMessageExpr::SuperInstance);
982  SVal SelfVal = getState()->getSelfSVal(getLocationContext());
983  assert(SelfVal.isValid() && "Calling super but not in ObjC method");
984  return SelfVal;
985}
986
987bool ObjCMethodCall::isReceiverSelfOrSuper() const {
988  if (getOriginExpr()->getReceiverKind() == ObjCMessageExpr::SuperInstance ||
989      getOriginExpr()->getReceiverKind() == ObjCMessageExpr::SuperClass)
990      return true;
991
992  if (!isInstanceMessage())
993    return false;
994
995  SVal RecVal = getSVal(getOriginExpr()->getInstanceReceiver());
996  SVal SelfVal = getState()->getSelfSVal(getLocationContext());
997
998  return (RecVal == SelfVal);
999}
1000
1001SourceRange ObjCMethodCall::getSourceRange() const {
1002  switch (getMessageKind()) {
1003  case OCM_Message:
1004    return getOriginExpr()->getSourceRange();
1005  case OCM_PropertyAccess:
1006  case OCM_Subscript:
1007    return getContainingPseudoObjectExpr()->getSourceRange();
1008  }
1009  llvm_unreachable("unknown message kind");
1010}
1011
1012using ObjCMessageDataTy = llvm::PointerIntPair<const PseudoObjectExpr *, 2>;
1013
1014const PseudoObjectExpr *ObjCMethodCall::getContainingPseudoObjectExpr() const {
1015  assert(Data && "Lazy lookup not yet performed.");
1016  assert(getMessageKind() != OCM_Message && "Explicit message send.");
1017  return ObjCMessageDataTy::getFromOpaqueValue(Data).getPointer();
1018}
1019
1020static const Expr *
1021getSyntacticFromForPseudoObjectExpr(const PseudoObjectExpr *POE) {
1022  const Expr *Syntactic = POE->getSyntacticForm();
1023
1024  // This handles the funny case of assigning to the result of a getter.
1025  // This can happen if the getter returns a non-const reference.
1026  if (const auto *BO = dyn_cast<BinaryOperator>(Syntactic))
1027    Syntactic = BO->getLHS();
1028
1029  return Syntactic;
1030}
1031
1032ObjCMessageKind ObjCMethodCall::getMessageKind() const {
1033  if (!Data) {
1034    // Find the parent, ignoring implicit casts.
1035    const ParentMap &PM = getLocationContext()->getParentMap();
1036    const Stmt *S = PM.getParentIgnoreParenCasts(getOriginExpr());
1037
1038    // Check if parent is a PseudoObjectExpr.
1039    if (const auto *POE = dyn_cast_or_null<PseudoObjectExpr>(S)) {
1040      const Expr *Syntactic = getSyntacticFromForPseudoObjectExpr(POE);
1041
1042      ObjCMessageKind K;
1043      switch (Syntactic->getStmtClass()) {
1044      case Stmt::ObjCPropertyRefExprClass:
1045        K = OCM_PropertyAccess;
1046        break;
1047      case Stmt::ObjCSubscriptRefExprClass:
1048        K = OCM_Subscript;
1049        break;
1050      default:
1051        // FIXME: Can this ever happen?
1052        K = OCM_Message;
1053        break;
1054      }
1055
1056      if (K != OCM_Message) {
1057        const_cast<ObjCMethodCall *>(this)->Data
1058          = ObjCMessageDataTy(POE, K).getOpaqueValue();
1059        assert(getMessageKind() == K);
1060        return K;
1061      }
1062    }
1063
1064    const_cast<ObjCMethodCall *>(this)->Data
1065      = ObjCMessageDataTy(nullptr, 1).getOpaqueValue();
1066    assert(getMessageKind() == OCM_Message);
1067    return OCM_Message;
1068  }
1069
1070  ObjCMessageDataTy Info = ObjCMessageDataTy::getFromOpaqueValue(Data);
1071  if (!Info.getPointer())
1072    return OCM_Message;
1073  return static_cast<ObjCMessageKind>(Info.getInt());
1074}
1075
1076const ObjCPropertyDecl *ObjCMethodCall::getAccessedProperty() const {
1077  // Look for properties accessed with property syntax (foo.bar = ...)
1078  if (getMessageKind() == OCM_PropertyAccess) {
1079    const PseudoObjectExpr *POE = getContainingPseudoObjectExpr();
1080    assert(POE && "Property access without PseudoObjectExpr?");
1081
1082    const Expr *Syntactic = getSyntacticFromForPseudoObjectExpr(POE);
1083    auto *RefExpr = cast<ObjCPropertyRefExpr>(Syntactic);
1084
1085    if (RefExpr->isExplicitProperty())
1086      return RefExpr->getExplicitProperty();
1087  }
1088
1089  // Look for properties accessed with method syntax ([foo setBar:...]).
1090  const ObjCMethodDecl *MD = getDecl();
1091  if (!MD || !MD->isPropertyAccessor())
1092    return nullptr;
1093
1094  // Note: This is potentially quite slow.
1095  return MD->findPropertyDecl();
1096}
1097
1098bool ObjCMethodCall::canBeOverridenInSubclass(ObjCInterfaceDecl *IDecl,
1099                                             Selector Sel) const {
1100  assert(IDecl);
1101  AnalysisManager &AMgr =
1102      getState()->getStateManager().getOwningEngine().getAnalysisManager();
1103  // If the class interface is declared inside the main file, assume it is not
1104  // subcassed.
1105  // TODO: It could actually be subclassed if the subclass is private as well.
1106  // This is probably very rare.
1107  SourceLocation InterfLoc = IDecl->getEndOfDefinitionLoc();
1108  if (InterfLoc.isValid() && AMgr.isInCodeFile(InterfLoc))
1109    return false;
1110
1111  // Assume that property accessors are not overridden.
1112  if (getMessageKind() == OCM_PropertyAccess)
1113    return false;
1114
1115  // We assume that if the method is public (declared outside of main file) or
1116  // has a parent which publicly declares the method, the method could be
1117  // overridden in a subclass.
1118
1119  // Find the first declaration in the class hierarchy that declares
1120  // the selector.
1121  ObjCMethodDecl *D = nullptr;
1122  while (true) {
1123    D = IDecl->lookupMethod(Sel, true);
1124
1125    // Cannot find a public definition.
1126    if (!D)
1127      return false;
1128
1129    // If outside the main file,
1130    if (D->getLocation().isValid() && !AMgr.isInCodeFile(D->getLocation()))
1131      return true;
1132
1133    if (D->isOverriding()) {
1134      // Search in the superclass on the next iteration.
1135      IDecl = D->getClassInterface();
1136      if (!IDecl)
1137        return false;
1138
1139      IDecl = IDecl->getSuperClass();
1140      if (!IDecl)
1141        return false;
1142
1143      continue;
1144    }
1145
1146    return false;
1147  };
1148
1149  llvm_unreachable("The while loop should always terminate.");
1150}
1151
1152static const ObjCMethodDecl *findDefiningRedecl(const ObjCMethodDecl *MD) {
1153  if (!MD)
1154    return MD;
1155
1156  // Find the redeclaration that defines the method.
1157  if (!MD->hasBody()) {
1158    for (auto I : MD->redecls())
1159      if (I->hasBody())
1160        MD = cast<ObjCMethodDecl>(I);
1161  }
1162  return MD;
1163}
1164
1165struct PrivateMethodKey {
1166  const ObjCInterfaceDecl *Interface;
1167  Selector LookupSelector;
1168  bool IsClassMethod;
1169};
1170
1171namespace llvm {
1172template <> struct DenseMapInfo<PrivateMethodKey> {
1173  using InterfaceInfo = DenseMapInfo<const ObjCInterfaceDecl *>;
1174  using SelectorInfo = DenseMapInfo<Selector>;
1175
1176  static inline PrivateMethodKey getEmptyKey() {
1177    return {InterfaceInfo::getEmptyKey(), SelectorInfo::getEmptyKey(), false};
1178  }
1179
1180  static inline PrivateMethodKey getTombstoneKey() {
1181    return {InterfaceInfo::getTombstoneKey(), SelectorInfo::getTombstoneKey(),
1182            true};
1183  }
1184
1185  static unsigned getHashValue(const PrivateMethodKey &Key) {
1186    return llvm::hash_combine(
1187        llvm::hash_code(InterfaceInfo::getHashValue(Key.Interface)),
1188        llvm::hash_code(SelectorInfo::getHashValue(Key.LookupSelector)),
1189        Key.IsClassMethod);
1190  }
1191
1192  static bool isEqual(const PrivateMethodKey &LHS,
1193                      const PrivateMethodKey &RHS) {
1194    return InterfaceInfo::isEqual(LHS.Interface, RHS.Interface) &&
1195           SelectorInfo::isEqual(LHS.LookupSelector, RHS.LookupSelector) &&
1196           LHS.IsClassMethod == RHS.IsClassMethod;
1197  }
1198};
1199} // end namespace llvm
1200
1201static const ObjCMethodDecl *
1202lookupRuntimeDefinition(const ObjCInterfaceDecl *Interface,
1203                        Selector LookupSelector, bool InstanceMethod) {
1204  // Repeatedly calling lookupPrivateMethod() is expensive, especially
1205  // when in many cases it returns null.  We cache the results so
1206  // that repeated queries on the same ObjCIntefaceDecl and Selector
1207  // don't incur the same cost.  On some test cases, we can see the
1208  // same query being issued thousands of times.
1209  //
1210  // NOTE: This cache is essentially a "global" variable, but it
1211  // only gets lazily created when we get here.  The value of the
1212  // cache probably comes from it being global across ExprEngines,
1213  // where the same queries may get issued.  If we are worried about
1214  // concurrency, or possibly loading/unloading ASTs, etc., we may
1215  // need to revisit this someday.  In terms of memory, this table
1216  // stays around until clang quits, which also may be bad if we
1217  // need to release memory.
1218  using PrivateMethodCache =
1219      llvm::DenseMap<PrivateMethodKey, Optional<const ObjCMethodDecl *>>;
1220
1221  static PrivateMethodCache PMC;
1222  Optional<const ObjCMethodDecl *> &Val =
1223      PMC[{Interface, LookupSelector, InstanceMethod}];
1224
1225  // Query lookupPrivateMethod() if the cache does not hit.
1226  if (!Val.hasValue()) {
1227    Val = Interface->lookupPrivateMethod(LookupSelector, InstanceMethod);
1228
1229    if (!*Val) {
1230      // Query 'lookupMethod' as a backup.
1231      Val = Interface->lookupMethod(LookupSelector, InstanceMethod);
1232    }
1233  }
1234
1235  return Val.getValue();
1236}
1237
1238RuntimeDefinition ObjCMethodCall::getRuntimeDefinition() const {
1239  const ObjCMessageExpr *E = getOriginExpr();
1240  assert(E);
1241  Selector Sel = E->getSelector();
1242
1243  if (E->isInstanceMessage()) {
1244    // Find the receiver type.
1245    const ObjCObjectType *ReceiverT = nullptr;
1246    bool CanBeSubClassed = false;
1247    bool LookingForInstanceMethod = true;
1248    QualType SupersType = E->getSuperType();
1249    const MemRegion *Receiver = nullptr;
1250
1251    if (!SupersType.isNull()) {
1252      // The receiver is guaranteed to be 'super' in this case.
1253      // Super always means the type of immediate predecessor to the method
1254      // where the call occurs.
1255      ReceiverT = cast<ObjCObjectPointerType>(SupersType)->getObjectType();
1256    } else {
1257      Receiver = getReceiverSVal().getAsRegion();
1258      if (!Receiver)
1259        return {};
1260
1261      DynamicTypeInfo DTI = getDynamicTypeInfo(getState(), Receiver);
1262      if (!DTI.isValid()) {
1263        assert(isa<AllocaRegion>(Receiver) &&
1264               "Unhandled untyped region class!");
1265        return {};
1266      }
1267
1268      QualType DynType = DTI.getType();
1269      CanBeSubClassed = DTI.canBeASubClass();
1270
1271      const auto *ReceiverDynT =
1272          dyn_cast<ObjCObjectPointerType>(DynType.getCanonicalType());
1273
1274      if (ReceiverDynT) {
1275        ReceiverT = ReceiverDynT->getObjectType();
1276
1277        // It can be actually class methods called with Class object as a
1278        // receiver. This type of messages is treated by the compiler as
1279        // instance (not class).
1280        if (ReceiverT->isObjCClass()) {
1281
1282          SVal SelfVal = getState()->getSelfSVal(getLocationContext());
1283          // For [self classMethod], return compiler visible declaration.
1284          if (Receiver == SelfVal.getAsRegion()) {
1285            return RuntimeDefinition(findDefiningRedecl(E->getMethodDecl()));
1286          }
1287
1288          // Otherwise, let's check if we know something about the type
1289          // inside of this class object.
1290          if (SymbolRef ReceiverSym = getReceiverSVal().getAsSymbol()) {
1291            DynamicTypeInfo DTI =
1292                getClassObjectDynamicTypeInfo(getState(), ReceiverSym);
1293            if (DTI.isValid()) {
1294              // Let's use this type for lookup.
1295              ReceiverT =
1296                  cast<ObjCObjectType>(DTI.getType().getCanonicalType());
1297
1298              CanBeSubClassed = DTI.canBeASubClass();
1299              // And it should be a class method instead.
1300              LookingForInstanceMethod = false;
1301            }
1302          }
1303        }
1304
1305        if (CanBeSubClassed)
1306          if (ObjCInterfaceDecl *IDecl = ReceiverT->getInterface())
1307            // Even if `DynamicTypeInfo` told us that it can be
1308            // not necessarily this type, but its descendants, we still want
1309            // to check again if this selector can be actually overridden.
1310            CanBeSubClassed = canBeOverridenInSubclass(IDecl, Sel);
1311      }
1312    }
1313
1314    // Lookup the instance method implementation.
1315    if (ReceiverT)
1316      if (ObjCInterfaceDecl *IDecl = ReceiverT->getInterface()) {
1317        const ObjCMethodDecl *MD =
1318            lookupRuntimeDefinition(IDecl, Sel, LookingForInstanceMethod);
1319
1320        if (MD && !MD->hasBody())
1321          MD = MD->getCanonicalDecl();
1322
1323        if (CanBeSubClassed)
1324          return RuntimeDefinition(MD, Receiver);
1325        else
1326          return RuntimeDefinition(MD, nullptr);
1327      }
1328  } else {
1329    // This is a class method.
1330    // If we have type info for the receiver class, we are calling via
1331    // class name.
1332    if (ObjCInterfaceDecl *IDecl = E->getReceiverInterface()) {
1333      // Find/Return the method implementation.
1334      return RuntimeDefinition(IDecl->lookupPrivateClassMethod(Sel));
1335    }
1336  }
1337
1338  return {};
1339}
1340
1341bool ObjCMethodCall::argumentsMayEscape() const {
1342  if (isInSystemHeader() && !isInstanceMessage()) {
1343    Selector Sel = getSelector();
1344    if (Sel.getNumArgs() == 1 &&
1345        Sel.getIdentifierInfoForSlot(0)->isStr("valueWithPointer"))
1346      return true;
1347  }
1348
1349  return CallEvent::argumentsMayEscape();
1350}
1351
1352void ObjCMethodCall::getInitialStackFrameContents(
1353                                             const StackFrameContext *CalleeCtx,
1354                                             BindingsTy &Bindings) const {
1355  const auto *D = cast<ObjCMethodDecl>(CalleeCtx->getDecl());
1356  SValBuilder &SVB = getState()->getStateManager().getSValBuilder();
1357  addParameterValuesToBindings(CalleeCtx, Bindings, SVB, *this,
1358                               D->parameters());
1359
1360  SVal SelfVal = getReceiverSVal();
1361  if (!SelfVal.isUnknown()) {
1362    const VarDecl *SelfD = CalleeCtx->getAnalysisDeclContext()->getSelfDecl();
1363    MemRegionManager &MRMgr = SVB.getRegionManager();
1364    Loc SelfLoc = SVB.makeLoc(MRMgr.getVarRegion(SelfD, CalleeCtx));
1365    Bindings.push_back(std::make_pair(SelfLoc, SelfVal));
1366  }
1367}
1368
1369CallEventRef<>
1370CallEventManager::getSimpleCall(const CallExpr *CE, ProgramStateRef State,
1371                                const LocationContext *LCtx) {
1372  if (const auto *MCE = dyn_cast<CXXMemberCallExpr>(CE))
1373    return create<CXXMemberCall>(MCE, State, LCtx);
1374
1375  if (const auto *OpCE = dyn_cast<CXXOperatorCallExpr>(CE)) {
1376    const FunctionDecl *DirectCallee = OpCE->getDirectCallee();
1377    if (const auto *MD = dyn_cast<CXXMethodDecl>(DirectCallee))
1378      if (MD->isInstance())
1379        return create<CXXMemberOperatorCall>(OpCE, State, LCtx);
1380
1381  } else if (CE->getCallee()->getType()->isBlockPointerType()) {
1382    return create<BlockCall>(CE, State, LCtx);
1383  }
1384
1385  // Otherwise, it's a normal function call, static member function call, or
1386  // something we can't reason about.
1387  return create<SimpleFunctionCall>(CE, State, LCtx);
1388}
1389
1390CallEventRef<>
1391CallEventManager::getCaller(const StackFrameContext *CalleeCtx,
1392                            ProgramStateRef State) {
1393  const LocationContext *ParentCtx = CalleeCtx->getParent();
1394  const LocationContext *CallerCtx = ParentCtx->getStackFrame();
1395  assert(CallerCtx && "This should not be used for top-level stack frames");
1396
1397  const Stmt *CallSite = CalleeCtx->getCallSite();
1398
1399  if (CallSite) {
1400    if (CallEventRef<> Out = getCall(CallSite, State, CallerCtx))
1401      return Out;
1402
1403    SValBuilder &SVB = State->getStateManager().getSValBuilder();
1404    const auto *Ctor = cast<CXXMethodDecl>(CalleeCtx->getDecl());
1405    Loc ThisPtr = SVB.getCXXThis(Ctor, CalleeCtx);
1406    SVal ThisVal = State->getSVal(ThisPtr);
1407
1408    if (const auto *CE = dyn_cast<CXXConstructExpr>(CallSite))
1409      return getCXXConstructorCall(CE, ThisVal.getAsRegion(), State, CallerCtx);
1410    else if (const auto *CIE = dyn_cast<CXXInheritedCtorInitExpr>(CallSite))
1411      return getCXXInheritedConstructorCall(CIE, ThisVal.getAsRegion(), State,
1412                                            CallerCtx);
1413    else {
1414      // All other cases are handled by getCall.
1415      llvm_unreachable("This is not an inlineable statement");
1416    }
1417  }
1418
1419  // Fall back to the CFG. The only thing we haven't handled yet is
1420  // destructors, though this could change in the future.
1421  const CFGBlock *B = CalleeCtx->getCallSiteBlock();
1422  CFGElement E = (*B)[CalleeCtx->getIndex()];
1423  assert((E.getAs<CFGImplicitDtor>() || E.getAs<CFGTemporaryDtor>()) &&
1424         "All other CFG elements should have exprs");
1425
1426  SValBuilder &SVB = State->getStateManager().getSValBuilder();
1427  const auto *Dtor = cast<CXXDestructorDecl>(CalleeCtx->getDecl());
1428  Loc ThisPtr = SVB.getCXXThis(Dtor, CalleeCtx);
1429  SVal ThisVal = State->getSVal(ThisPtr);
1430
1431  const Stmt *Trigger;
1432  if (Optional<CFGAutomaticObjDtor> AutoDtor = E.getAs<CFGAutomaticObjDtor>())
1433    Trigger = AutoDtor->getTriggerStmt();
1434  else if (Optional<CFGDeleteDtor> DeleteDtor = E.getAs<CFGDeleteDtor>())
1435    Trigger = DeleteDtor->getDeleteExpr();
1436  else
1437    Trigger = Dtor->getBody();
1438
1439  return getCXXDestructorCall(Dtor, Trigger, ThisVal.getAsRegion(),
1440                              E.getAs<CFGBaseDtor>().hasValue(), State,
1441                              CallerCtx);
1442}
1443
1444CallEventRef<> CallEventManager::getCall(const Stmt *S, ProgramStateRef State,
1445                                         const LocationContext *LC) {
1446  if (const auto *CE = dyn_cast<CallExpr>(S)) {
1447    return getSimpleCall(CE, State, LC);
1448  } else if (const auto *NE = dyn_cast<CXXNewExpr>(S)) {
1449    return getCXXAllocatorCall(NE, State, LC);
1450  } else if (const auto *ME = dyn_cast<ObjCMessageExpr>(S)) {
1451    return getObjCMethodCall(ME, State, LC);
1452  } else {
1453    return nullptr;
1454  }
1455}
1456