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