1	//=== SemaFunctionEffects.cpp - Sema handling of function effects ---------===//
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	// This file implements Sema handling of function effects.
10	//
11	//===----------------------------------------------------------------------===//
12
13	#include "clang/AST/Decl.h"
14	#include "clang/AST/DeclCXX.h"
15	#include "clang/AST/DynamicRecursiveASTVisitor.h"
16	#include "clang/AST/ExprObjC.h"
17	#include "clang/AST/Stmt.h"
18	#include "clang/AST/StmtObjC.h"
19	#include "clang/AST/Type.h"
20	#include "clang/Basic/SourceManager.h"
21	#include "clang/Sema/SemaInternal.h"
22
23	#define DEBUG_TYPE "effectanalysis"
24
25	using namespace clang;
26
27	namespace {
28
29	enum class ViolationID : uint8_t {
30	None = 0, // Sentinel for an empty Violation.
31	// These first 5 map to a %select{} in one of several FunctionEffects
32	// diagnostics, e.g. warn_func_effect_violation.
33	BaseDiagnosticIndex,
34	AllocatesMemory = BaseDiagnosticIndex,
35	ThrowsOrCatchesExceptions,
36	HasStaticLocalVariable,
37	AccessesThreadLocalVariable,
38	AccessesObjCMethodOrProperty,
39
40	// These only apply to callees, where the analysis stops at the Decl.
41	DeclDisallowsInference,
42
43	// These both apply to indirect calls. The difference is that sometimes
44	// we have an actual Decl (generally a variable) which is the function
45	// pointer being called, and sometimes, typically due to a cast, we only
46	// have an expression.
47	CallsDeclWithoutEffect,
48	CallsExprWithoutEffect,
49	};
50
51	// Information about the AST context in which a violation was found, so
52	// that diagnostics can point to the correct source.
53	class ViolationSite {
54	public:
55	enum class Kind : uint8_t {
56	Default, // Function body.
57	MemberInitializer,
58	DefaultArgExpr
59	};
60
61	private:
62	llvm::PointerIntPair<CXXDefaultArgExpr *, 2, Kind> Impl;
63
64	public:
65	ViolationSite() = default;
66
67	explicit ViolationSite(CXXDefaultArgExpr *E)
68	: Impl(E, Kind::DefaultArgExpr) {}
69
70	Kind kind() const { return static_cast<Kind>(Impl.getInt()); }
71	CXXDefaultArgExpr *defaultArgExpr() const { return Impl.getPointer(); }
72
73	void setKind(Kind K) { Impl.setPointerAndInt(PtrVal: nullptr, IntVal: K); }
74	};
75
76	// Represents a violation of the rules, potentially for the entire duration of
77	// the analysis phase, in order to refer to it when explaining why a caller has
78	// been made unsafe by a callee. Can be transformed into either a Diagnostic
79	// (warning or a note), depending on whether the violation pertains to a
80	// function failing to be verifed as holding an effect vs. a function failing to
81	// be inferred as holding that effect.
82	struct Violation {
83	FunctionEffect Effect;
84	std::optional<FunctionEffect>
85	CalleeEffectPreventingInference; // Only for certain IDs; can be nullopt.
86	ViolationID ID = ViolationID::None;
87	ViolationSite Site;
88	SourceLocation Loc;
89	const Decl *Callee =
90	nullptr; // Only valid for ViolationIDs Calls{Decl,Expr}WithoutEffect.
91
92	Violation(FunctionEffect Effect, ViolationID ID, ViolationSite VS,
93	SourceLocation Loc, const Decl *Callee = nullptr,
94	std::optional<FunctionEffect> CalleeEffect = std::nullopt)
95	: Effect(Effect), CalleeEffectPreventingInference(CalleeEffect), ID(ID),
96	Site(VS), Loc(Loc), Callee(Callee) {}
97
98	unsigned diagnosticSelectIndex() const {
99	return unsigned(ID) - unsigned(ViolationID::BaseDiagnosticIndex);
100	}
101	};
102
103	enum class SpecialFuncType : uint8_t { None, OperatorNew, OperatorDelete };
104	enum class CallableType : uint8_t {
105	// Unknown: probably function pointer.
106	Unknown,
107	Function,
108	Virtual,
109	Block
110	};
111
112	// Return whether a function's effects CAN be verified.
113	// The question of whether it SHOULD be verified is independent.
114	static bool functionIsVerifiable(const FunctionDecl *FD) {
115	if (FD->isTrivial()) {
116	// Otherwise `struct x { int a; };` would have an unverifiable default
117	// constructor.
118	return true;
119	}
120	return FD->hasBody();
121	}
122
123	static bool isNoexcept(const FunctionDecl *FD) {
124	const auto *FPT = FD->getType()->getAs<FunctionProtoType>();
125	return FPT && (FPT->isNothrow() || FD->hasAttr<NoThrowAttr>());
126	}
127
128	// This list is probably incomplete.
129	// FIXME: Investigate:
130	// __builtin_eh_return?
131	// __builtin_allow_runtime_check?
132	// __builtin_unwind_init and other similar things that sound exception-related.
133	// va_copy?
134	// coroutines?
135	static FunctionEffectKindSet getBuiltinFunctionEffects(unsigned BuiltinID) {
136	FunctionEffectKindSet Result;
137
138	switch (BuiltinID) {
139	case 0: // Not builtin.
140	default: // By default, builtins have no known effects.
141	break;
142
143	// These allocate/deallocate heap memory.
144	case Builtin::ID::BI__builtin_calloc:
145	case Builtin::ID::BI__builtin_malloc:
146	case Builtin::ID::BI__builtin_realloc:
147	case Builtin::ID::BI__builtin_free:
148	case Builtin::ID::BI__builtin_operator_delete:
149	case Builtin::ID::BI__builtin_operator_new:
150	case Builtin::ID::BIaligned_alloc:
151	case Builtin::ID::BIcalloc:
152	case Builtin::ID::BImalloc:
153	case Builtin::ID::BImemalign:
154	case Builtin::ID::BIrealloc:
155	case Builtin::ID::BIfree:
156
157	case Builtin::ID::BIfopen:
158	case Builtin::ID::BIpthread_create:
159	case Builtin::ID::BI_Block_object_dispose:
160	Result.insert(Effect: FunctionEffect(FunctionEffect::Kind::Allocating));
161	break;
162
163	// These block in some other way than allocating memory.
164	// longjmp() and friends are presumed unsafe because they are the moral
165	// equivalent of throwing a C++ exception, which is unsafe.
166	case Builtin::ID::BIlongjmp:
167	case Builtin::ID::BI_longjmp:
168	case Builtin::ID::BIsiglongjmp:
169	case Builtin::ID::BI__builtin_longjmp:
170	case Builtin::ID::BIobjc_exception_throw:
171
172	// Objective-C runtime.
173	case Builtin::ID::BIobjc_msgSend:
174	case Builtin::ID::BIobjc_msgSend_fpret:
175	case Builtin::ID::BIobjc_msgSend_fp2ret:
176	case Builtin::ID::BIobjc_msgSend_stret:
177	case Builtin::ID::BIobjc_msgSendSuper:
178	case Builtin::ID::BIobjc_getClass:
179	case Builtin::ID::BIobjc_getMetaClass:
180	case Builtin::ID::BIobjc_enumerationMutation:
181	case Builtin::ID::BIobjc_assign_ivar:
182	case Builtin::ID::BIobjc_assign_global:
183	case Builtin::ID::BIobjc_sync_enter:
184	case Builtin::ID::BIobjc_sync_exit:
185	case Builtin::ID::BINSLog:
186	case Builtin::ID::BINSLogv:
187
188	// stdio.h
189	case Builtin::ID::BIfread:
190	case Builtin::ID::BIfwrite:
191
192	// stdio.h: printf family.
193	case Builtin::ID::BIprintf:
194	case Builtin::ID::BI__builtin_printf:
195	case Builtin::ID::BIfprintf:
196	case Builtin::ID::BIsnprintf:
197	case Builtin::ID::BIsprintf:
198	case Builtin::ID::BIvprintf:
199	case Builtin::ID::BIvfprintf:
200	case Builtin::ID::BIvsnprintf:
201	case Builtin::ID::BIvsprintf:
202
203	// stdio.h: scanf family.
204	case Builtin::ID::BIscanf:
205	case Builtin::ID::BIfscanf:
206	case Builtin::ID::BIsscanf:
207	case Builtin::ID::BIvscanf:
208	case Builtin::ID::BIvfscanf:
209	case Builtin::ID::BIvsscanf:
210	Result.insert(Effect: FunctionEffect(FunctionEffect::Kind::Blocking));
211	break;
212	}
213
214	return Result;
215	}
216
217	// Transitory, more extended information about a callable, which can be a
218	// function, block, or function pointer.
219	struct CallableInfo {
220	// CDecl holds the function's definition, if any.
221	// FunctionDecl if CallableType::Function or Virtual
222	// BlockDecl if CallableType::Block
223	const Decl *CDecl;
224
225	// Remember whether the callable is a function, block, virtual method,
226	// or (presumed) function pointer.
227	CallableType CType = CallableType::Unknown;
228
229	// Remember whether the callable is an operator new or delete function,
230	// so that calls to them are reported more meaningfully, as memory
231	// allocations.
232	SpecialFuncType FuncType = SpecialFuncType::None;
233
234	// We inevitably want to know the callable's declared effects, so cache them.
235	FunctionEffectKindSet Effects;
236
237	CallableInfo(const Decl &CD, SpecialFuncType FT = SpecialFuncType::None)
238	: CDecl(&CD), FuncType(FT) {
239	FunctionEffectsRef DeclEffects;
240	if (auto *FD = dyn_cast<FunctionDecl>(Val: CDecl)) {
241	// Use the function's definition, if any.
242	if (const FunctionDecl *Def = FD->getDefinition())
243	CDecl = FD = Def;
244	CType = CallableType::Function;
245	if (auto *Method = dyn_cast<CXXMethodDecl>(Val: FD);
246	Method && Method->isVirtual())
247	CType = CallableType::Virtual;
248	DeclEffects = FD->getFunctionEffects();
249	} else if (auto *BD = dyn_cast<BlockDecl>(Val: CDecl)) {
250	CType = CallableType::Block;
251	DeclEffects = BD->getFunctionEffects();
252	} else if (auto *VD = dyn_cast<ValueDecl>(Val: CDecl)) {
253	// ValueDecl is function, enum, or variable, so just look at its type.
254	DeclEffects = FunctionEffectsRef::get(QT: VD->getType());
255	}
256	Effects = FunctionEffectKindSet(DeclEffects);
257	}
258
259	CallableType type() const { return CType; }
260
261	bool isCalledDirectly() const {
262	return CType == CallableType::Function || CType == CallableType::Block;
263	}
264
265	bool isVerifiable() const {
266	switch (CType) {
267	case CallableType::Unknown:
268	case CallableType::Virtual:
269	return false;
270	case CallableType::Block:
271	return true;
272	case CallableType::Function:
273	return functionIsVerifiable(FD: dyn_cast<FunctionDecl>(Val: CDecl));
274	}
275	llvm_unreachable("undefined CallableType");
276	}
277
278	/// Generate a name for logging and diagnostics.
279	std::string getNameForDiagnostic(Sema &S) const {
280	std::string Name;
281	llvm::raw_string_ostream OS(Name);
282
283	if (auto *FD = dyn_cast<FunctionDecl>(Val: CDecl))
284	FD->getNameForDiagnostic(OS, Policy: S.getPrintingPolicy(),
285	/*Qualified=*/true);
286	else if (auto *BD = dyn_cast<BlockDecl>(Val: CDecl))
287	OS << "(block " << BD->getBlockManglingNumber() << ")";
288	else if (auto *VD = dyn_cast<NamedDecl>(Val: CDecl))
289	VD->printQualifiedName(OS);
290	return Name;
291	}
292	};
293
294	// ----------
295	// Map effects to single Violations, to hold the first (of potentially many)
296	// violations pertaining to an effect, per function.
297	class EffectToViolationMap {
298	// Since we currently only have a tiny number of effects (typically no more
299	// than 1), use a SmallVector with an inline capacity of 1. Since it
300	// is often empty, use a unique_ptr to the SmallVector.
301	// Note that Violation itself contains a FunctionEffect which is the key.
302	// FIXME: Is there a way to simplify this using existing data structures?
303	using ImplVec = llvm::SmallVector<Violation, 1>;
304	std::unique_ptr<ImplVec> Impl;
305
306	public:
307	// Insert a new Violation if we do not already have one for its effect.
308	void maybeInsert(const Violation &Viol) {
309	if (Impl == nullptr)
310	Impl = std::make_unique<ImplVec>();
311	else if (lookup(Key: Viol.Effect) != nullptr)
312	return;
313
314	Impl->push_back(Elt: Viol);
315	}
316
317	const Violation *lookup(FunctionEffect Key) {
318	if (Impl == nullptr)
319	return nullptr;
320
321	auto *Iter = llvm::find_if(
322	Range&: *Impl, P: [&](const auto &Item) { return Item.Effect == Key; });
323	return Iter != Impl->end() ? &*Iter : nullptr;
324	}
325
326	size_t size() const { return Impl ? Impl->size() : 0; }
327	};
328
329	// ----------
330	// State pertaining to a function whose AST is walked and whose effect analysis
331	// is dependent on a subsequent analysis of other functions.
332	class PendingFunctionAnalysis {
333	friend class CompleteFunctionAnalysis;
334
335	public:
336	struct DirectCall {
337	const Decl *Callee;
338	SourceLocation CallLoc;
339	// Not all recursive calls are detected, just enough
340	// to break cycles.
341	bool Recursed = false;
342	ViolationSite VSite;
343
344	DirectCall(const Decl *D, SourceLocation CallLoc, ViolationSite VSite)
345	: Callee(D), CallLoc(CallLoc), VSite(VSite) {}
346	};
347
348	// We always have two disjoint sets of effects to verify:
349	// 1. Effects declared explicitly by this function.
350	// 2. All other inferrable effects needing verification.
351	FunctionEffectKindSet DeclaredVerifiableEffects;
352	FunctionEffectKindSet EffectsToInfer;
353
354	private:
355	// Violations pertaining to the function's explicit effects.
356	SmallVector<Violation, 0> ViolationsForExplicitEffects;
357
358	// Violations pertaining to other, non-explicit, inferrable effects.
359	EffectToViolationMap InferrableEffectToFirstViolation;
360
361	// These unverified direct calls are what keeps the analysis "pending",
362	// until the callees can be verified.
363	SmallVector<DirectCall, 0> UnverifiedDirectCalls;
364
365	public:
366	PendingFunctionAnalysis(Sema &S, const CallableInfo &CInfo,
367	FunctionEffectKindSet AllInferrableEffectsToVerify)
368	: DeclaredVerifiableEffects(CInfo.Effects) {
369	// Check for effects we are not allowed to infer.
370	FunctionEffectKindSet InferrableEffects;
371
372	for (FunctionEffect effect : AllInferrableEffectsToVerify) {
373	std::optional<FunctionEffect> ProblemCalleeEffect =
374	effect.effectProhibitingInference(Callee: *CInfo.CDecl, CalleeFX: CInfo.Effects);
375	if (!ProblemCalleeEffect)
376	InferrableEffects.insert(Effect: effect);
377	else {
378	// Add a Violation for this effect if a caller were to
379	// try to infer it.
380	InferrableEffectToFirstViolation.maybeInsert(Viol: Violation(
381	effect, ViolationID::DeclDisallowsInference, ViolationSite{},
382	CInfo.CDecl->getLocation(), nullptr, ProblemCalleeEffect));
383	}
384	}
385	// InferrableEffects is now the set of inferrable effects which are not
386	// prohibited.
387	EffectsToInfer = FunctionEffectKindSet::difference(
388	InferrableEffects, DeclaredVerifiableEffects);
389	}
390
391	// Hide the way that Violations for explicitly required effects vs. inferred
392	// ones are handled differently.
393	void checkAddViolation(bool Inferring, const Violation &NewViol) {
394	if (!Inferring)
395	ViolationsForExplicitEffects.push_back(Elt: NewViol);
396	else
397	InferrableEffectToFirstViolation.maybeInsert(Viol: NewViol);
398	}
399
400	void addUnverifiedDirectCall(const Decl *D, SourceLocation CallLoc,
401	ViolationSite VSite) {
402	UnverifiedDirectCalls.emplace_back(Args&: D, Args&: CallLoc, Args&: VSite);
403	}
404
405	// Analysis is complete when there are no unverified direct calls.
406	bool isComplete() const { return UnverifiedDirectCalls.empty(); }
407
408	const Violation *violationForInferrableEffect(FunctionEffect effect) {
409	return InferrableEffectToFirstViolation.lookup(Key: effect);
410	}
411
412	// Mutable because caller may need to set a DirectCall's Recursing flag.
413	MutableArrayRef<DirectCall> unverifiedCalls() {
414	assert(!isComplete());
415	return UnverifiedDirectCalls;
416	}
417
418	ArrayRef<Violation> getSortedViolationsForExplicitEffects(SourceManager &SM) {
419	if (!ViolationsForExplicitEffects.empty())
420	llvm::sort(C&: ViolationsForExplicitEffects,
421	Comp: [&SM](const Violation &LHS, const Violation &RHS) {
422	return SM.isBeforeInTranslationUnit(LHS: LHS.Loc, RHS: RHS.Loc);
423	});
424	return ViolationsForExplicitEffects;
425	}
426
427	void dump(Sema &SemaRef, llvm::raw_ostream &OS) const {
428	OS << "Pending: Declared ";
429	DeclaredVerifiableEffects.dump(OS);
430	OS << ", " << ViolationsForExplicitEffects.size() << " violations; ";
431	OS << " Infer ";
432	EffectsToInfer.dump(OS);
433	OS << ", " << InferrableEffectToFirstViolation.size() << " violations";
434	if (!UnverifiedDirectCalls.empty()) {
435	OS << "; Calls: ";
436	for (const DirectCall &Call : UnverifiedDirectCalls) {
437	CallableInfo CI(*Call.Callee);
438	OS << " " << CI.getNameForDiagnostic(S&: SemaRef);
439	}
440	}
441	OS << "\n";
442	}
443	};
444
445	// ----------
446	class CompleteFunctionAnalysis {
447	// Current size: 2 pointers
448	public:
449	// Has effects which are both the declared ones -- not to be inferred -- plus
450	// ones which have been successfully inferred. These are all considered
451	// "verified" for the purposes of callers; any issue with verifying declared
452	// effects has already been reported and is not the problem of any caller.
453	FunctionEffectKindSet VerifiedEffects;
454
455	private:
456	// This is used to generate notes about failed inference.
457	EffectToViolationMap InferrableEffectToFirstViolation;
458
459	public:
460	// The incoming Pending analysis is consumed (member(s) are moved-from).
461	CompleteFunctionAnalysis(ASTContext &Ctx, PendingFunctionAnalysis &&Pending,
462	FunctionEffectKindSet DeclaredEffects,
463	FunctionEffectKindSet AllInferrableEffectsToVerify)
464	: VerifiedEffects(DeclaredEffects) {
465	for (FunctionEffect effect : AllInferrableEffectsToVerify)
466	if (Pending.violationForInferrableEffect(effect) == nullptr)
467	VerifiedEffects.insert(effect);
468
469	InferrableEffectToFirstViolation =
470	std::move(Pending.InferrableEffectToFirstViolation);
471	}
472
473	const Violation *firstViolationForEffect(FunctionEffect Effect) {
474	return InferrableEffectToFirstViolation.lookup(Key: Effect);
475	}
476
477	void dump(llvm::raw_ostream &OS) const {
478	OS << "Complete: Verified ";
479	VerifiedEffects.dump(OS);
480	OS << "; Infer ";
481	OS << InferrableEffectToFirstViolation.size() << " violations\n";
482	}
483	};
484
485	// ==========
486	class Analyzer {
487	Sema &S;
488
489	// Subset of Sema.AllEffectsToVerify
490	FunctionEffectKindSet AllInferrableEffectsToVerify;
491
492	using FuncAnalysisPtr =
493	llvm::PointerUnion<PendingFunctionAnalysis *, CompleteFunctionAnalysis *>;
494
495	// Map all Decls analyzed to FuncAnalysisPtr. Pending state is larger
496	// than complete state, so use different objects to represent them.
497	// The state pointers are owned by the container.
498	class AnalysisMap : llvm::DenseMap<const Decl *, FuncAnalysisPtr> {
499	using Base = llvm::DenseMap<const Decl *, FuncAnalysisPtr>;
500
501	public:
502	~AnalysisMap();
503
504	// Use non-public inheritance in order to maintain the invariant
505	// that lookups and insertions are via the canonical Decls.
506
507	FuncAnalysisPtr lookup(const Decl *Key) const {
508	return Base::lookup(Val: Key->getCanonicalDecl());
509	}
510
511	FuncAnalysisPtr &operator[](const Decl *Key) {
512	return Base::operator[](Key: Key->getCanonicalDecl());
513	}
514
515	/// Shortcut for the case where we only care about completed analysis.
516	CompleteFunctionAnalysis *completedAnalysisForDecl(const Decl *D) const {
517	if (FuncAnalysisPtr AP = lookup(Key: D);
518	isa_and_nonnull<CompleteFunctionAnalysis *>(Val: AP))
519	return cast<CompleteFunctionAnalysis *>(Val&: AP);
520	return nullptr;
521	}
522
523	void dump(Sema &SemaRef, llvm::raw_ostream &OS) {
524	OS << "\nAnalysisMap:\n";
525	for (const auto &item : *this) {
526	CallableInfo CI(*item.first);
527	const auto AP = item.second;
528	OS << item.first << " " << CI.getNameForDiagnostic(S&: SemaRef) << " : ";
529	if (AP.isNull()) {
530	OS << "null\n";
531	} else if (auto *CFA = dyn_cast<CompleteFunctionAnalysis *>(Val: AP)) {
532	OS << CFA << " ";
533	CFA->dump(OS);
534	} else if (auto *PFA = dyn_cast<PendingFunctionAnalysis *>(Val: AP)) {
535	OS << PFA << " ";
536	PFA->dump(SemaRef, OS);
537	} else
538	llvm_unreachable("never");
539	}
540	OS << "---\n";
541	}
542	};
543	AnalysisMap DeclAnalysis;
544
545	public:
546	Analyzer(Sema &S) : S(S) {}
547
548	void run(const TranslationUnitDecl &TU) {
549	// Gather all of the effects to be verified to see what operations need to
550	// be checked, and to see which ones are inferrable.
551	for (FunctionEffect Effect : S.AllEffectsToVerify) {
552	const FunctionEffect::Flags Flags = Effect.flags();
553	if (Flags & FunctionEffect::FE_InferrableOnCallees)
554	AllInferrableEffectsToVerify.insert(Effect);
555	}
556	LLVM_DEBUG(llvm::dbgs() << "AllInferrableEffectsToVerify: ";
557	AllInferrableEffectsToVerify.dump(llvm::dbgs());
558	llvm::dbgs() << "\n";);
559
560	// We can use DeclsWithEffectsToVerify as a stack for a
561	// depth-first traversal; there's no need for a second container. But first,
562	// reverse it, so when working from the end, Decls are verified in the order
563	// they are declared.
564	SmallVector<const Decl *> &VerificationQueue = S.DeclsWithEffectsToVerify;
565	std::reverse(first: VerificationQueue.begin(), last: VerificationQueue.end());
566
567	while (!VerificationQueue.empty()) {
568	const Decl *D = VerificationQueue.back();
569	if (FuncAnalysisPtr AP = DeclAnalysis.lookup(Key: D)) {
570	if (auto *Pending = dyn_cast<PendingFunctionAnalysis *>(Val&: AP)) {
571	// All children have been traversed; finish analysis.
572	finishPendingAnalysis(D, Pending);
573	}
574	VerificationQueue.pop_back();
575	continue;
576	}
577
578	// Not previously visited; begin a new analysis for this Decl.
579	PendingFunctionAnalysis *Pending = verifyDecl(D);
580	if (Pending == nullptr) {
581	// Completed now.
582	VerificationQueue.pop_back();
583	continue;
584	}
585
586	// Analysis remains pending because there are direct callees to be
587	// verified first. Push them onto the queue.
588	for (PendingFunctionAnalysis::DirectCall &Call :
589	Pending->unverifiedCalls()) {
590	FuncAnalysisPtr AP = DeclAnalysis.lookup(Key: Call.Callee);
591	if (AP.isNull()) {
592	VerificationQueue.push_back(Elt: Call.Callee);
593	continue;
594	}
595
596	// This indicates recursion (not necessarily direct). For the
597	// purposes of effect analysis, we can just ignore it since
598	// no effects forbid recursion.
599	assert(isa<PendingFunctionAnalysis *>(AP));
600	Call.Recursed = true;
601	}
602	}
603	}
604
605	private:
606	// Verify a single Decl. Return the pending structure if that was the result,
607	// else null. This method must not recurse.
608	PendingFunctionAnalysis *verifyDecl(const Decl *D) {
609	CallableInfo CInfo(*D);
610	bool isExternC = false;
611
612	if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(Val: D))
613	isExternC = FD->getCanonicalDecl()->isExternCContext();
614
615	// For C++, with non-extern "C" linkage only - if any of the Decl's declared
616	// effects forbid throwing (e.g. nonblocking) then the function should also
617	// be declared noexcept.
618	if (S.getLangOpts().CPlusPlus && !isExternC) {
619	for (FunctionEffect Effect : CInfo.Effects) {
620	if (!(Effect.flags() & FunctionEffect::FE_ExcludeThrow))
621	continue;
622
623	bool IsNoexcept = false;
624	if (auto *FD = D->getAsFunction()) {
625	IsNoexcept = isNoexcept(FD);
626	} else if (auto *BD = dyn_cast<BlockDecl>(D)) {
627	if (auto *TSI = BD->getSignatureAsWritten()) {
628	auto *FPT = TSI->getType()->castAs<FunctionProtoType>();
629	IsNoexcept = FPT->isNothrow() || BD->hasAttr<NoThrowAttr>();
630	}
631	}
632	if (!IsNoexcept)
633	S.Diag(D->getBeginLoc(), diag::warn_perf_constraint_implies_noexcept)
634	<< GetCallableDeclKind(D, nullptr) << Effect.name();
635	break;
636	}
637	}
638
639	// Build a PendingFunctionAnalysis on the stack. If it turns out to be
640	// complete, we'll have avoided a heap allocation; if it's incomplete, it's
641	// a fairly trivial move to a heap-allocated object.
642	PendingFunctionAnalysis FAnalysis(S, CInfo, AllInferrableEffectsToVerify);
643
644	LLVM_DEBUG(llvm::dbgs()
645	<< "\nVerifying " << CInfo.getNameForDiagnostic(S) << " ";
646	FAnalysis.dump(S, llvm::dbgs()););
647
648	FunctionBodyASTVisitor Visitor(*this, FAnalysis, CInfo);
649
650	Visitor.run();
651	if (FAnalysis.isComplete()) {
652	completeAnalysis(CInfo, Pending: std::move(FAnalysis));
653	return nullptr;
654	}
655	// Move the pending analysis to the heap and save it in the map.
656	PendingFunctionAnalysis *PendingPtr =
657	new PendingFunctionAnalysis(std::move(FAnalysis));
658	DeclAnalysis[D] = PendingPtr;
659	LLVM_DEBUG(llvm::dbgs() << "inserted pending " << PendingPtr << "\n";
660	DeclAnalysis.dump(S, llvm::dbgs()););
661	return PendingPtr;
662	}
663
664	// Consume PendingFunctionAnalysis, create with it a CompleteFunctionAnalysis,
665	// inserted in the container.
666	void completeAnalysis(const CallableInfo &CInfo,
667	PendingFunctionAnalysis &&Pending) {
668	if (ArrayRef<Violation> Viols =
669	Pending.getSortedViolationsForExplicitEffects(SM&: S.getSourceManager());
670	!Viols.empty())
671	emitDiagnostics(Viols, CInfo);
672
673	CompleteFunctionAnalysis *CompletePtr = new CompleteFunctionAnalysis(
674	S.getASTContext(), std::move(Pending), CInfo.Effects,
675	AllInferrableEffectsToVerify);
676	DeclAnalysis[CInfo.CDecl] = CompletePtr;
677	LLVM_DEBUG(llvm::dbgs() << "inserted complete " << CompletePtr << "\n";
678	DeclAnalysis.dump(S, llvm::dbgs()););
679	}
680
681	// Called after all direct calls requiring inference have been found -- or
682	// not. Repeats calls to FunctionBodyASTVisitor::followCall() but without
683	// the possibility of inference. Deletes Pending.
684	void finishPendingAnalysis(const Decl *D, PendingFunctionAnalysis *Pending) {
685	CallableInfo Caller(*D);
686	LLVM_DEBUG(llvm::dbgs() << "finishPendingAnalysis for "
687	<< Caller.getNameForDiagnostic(S) << " : ";
688	Pending->dump(S, llvm::dbgs()); llvm::dbgs() << "\n";);
689	for (const PendingFunctionAnalysis::DirectCall &Call :
690	Pending->unverifiedCalls()) {
691	if (Call.Recursed)
692	continue;
693
694	CallableInfo Callee(*Call.Callee);
695	followCall(Caller, PFA&: *Pending, Callee, CallLoc: Call.CallLoc,
696	/*AssertNoFurtherInference=*/true, VSite: Call.VSite);
697	}
698	completeAnalysis(CInfo: Caller, Pending: std::move(*Pending));
699	delete Pending;
700	}
701
702	// Here we have a call to a Decl, either explicitly via a CallExpr or some
703	// other AST construct. PFA pertains to the caller.
704	void followCall(const CallableInfo &Caller, PendingFunctionAnalysis &PFA,
705	const CallableInfo &Callee, SourceLocation CallLoc,
706	bool AssertNoFurtherInference, ViolationSite VSite) {
707	const bool DirectCall = Callee.isCalledDirectly();
708
709	// Initially, the declared effects; inferred effects will be added.
710	FunctionEffectKindSet CalleeEffects = Callee.Effects;
711
712	bool IsInferencePossible = DirectCall;
713
714	if (DirectCall)
715	if (CompleteFunctionAnalysis *CFA =
716	DeclAnalysis.completedAnalysisForDecl(D: Callee.CDecl)) {
717	// Combine declared effects with those which may have been inferred.
718	CalleeEffects.insert(CFA->VerifiedEffects);
719	IsInferencePossible = false; // We've already traversed it.
720	}
721
722	if (AssertNoFurtherInference) {
723	assert(!IsInferencePossible);
724	}
725
726	if (!Callee.isVerifiable())
727	IsInferencePossible = false;
728
729	LLVM_DEBUG(llvm::dbgs()
730	<< "followCall from " << Caller.getNameForDiagnostic(S)
731	<< " to " << Callee.getNameForDiagnostic(S)
732	<< "; verifiable: " << Callee.isVerifiable() << "; callee ";
733	CalleeEffects.dump(llvm::dbgs()); llvm::dbgs() << "\n";
734	llvm::dbgs() << " callee " << Callee.CDecl << " canonical "
735	<< Callee.CDecl->getCanonicalDecl() << "\n";);
736
737	auto Check1Effect = [&](FunctionEffect Effect, bool Inferring) {
738	if (!Effect.shouldDiagnoseFunctionCall(Direct: DirectCall, CalleeFX: CalleeEffects))
739	return;
740
741	// If inference is not allowed, or the target is indirect (virtual
742	// method/function ptr?), generate a Violation now.
743	if (!IsInferencePossible ||
744	!(Effect.flags() & FunctionEffect::FE_InferrableOnCallees)) {
745	if (Callee.FuncType == SpecialFuncType::None)
746	PFA.checkAddViolation(Inferring,
747	NewViol: {Effect, ViolationID::CallsDeclWithoutEffect,
748	VSite, CallLoc, Callee.CDecl});
749	else
750	PFA.checkAddViolation(
751	Inferring,
752	NewViol: {Effect, ViolationID::AllocatesMemory, VSite, CallLoc});
753	} else {
754	// Inference is allowed and necessary; defer it.
755	PFA.addUnverifiedDirectCall(D: Callee.CDecl, CallLoc, VSite);
756	}
757	};
758
759	for (FunctionEffect Effect : PFA.DeclaredVerifiableEffects)
760	Check1Effect(Effect, false);
761
762	for (FunctionEffect Effect : PFA.EffectsToInfer)
763	Check1Effect(Effect, true);
764	}
765
766	// Describe a callable Decl for a diagnostic.
767	// (Not an enum class because the value is always converted to an integer for
768	// use in a diagnostic.)
769	enum CallableDeclKind {
770	CDK_Function,
771	CDK_Constructor,
772	CDK_Destructor,
773	CDK_Lambda,
774	CDK_Block,
775	CDK_MemberInitializer,
776	};
777
778	// Describe a call site or target using an enum mapping to a %select{}
779	// in a diagnostic, e.g. warn_func_effect_violation,
780	// warn_perf_constraint_implies_noexcept, and others.
781	static CallableDeclKind GetCallableDeclKind(const Decl *D,
782	const Violation *V) {
783	if (V != nullptr &&
784	V->Site.kind() == ViolationSite::Kind::MemberInitializer)
785	return CDK_MemberInitializer;
786	if (isa<BlockDecl>(Val: D))
787	return CDK_Block;
788	if (auto *Method = dyn_cast<CXXMethodDecl>(Val: D)) {
789	if (isa<CXXConstructorDecl>(Val: D))
790	return CDK_Constructor;
791	if (isa<CXXDestructorDecl>(Val: D))
792	return CDK_Destructor;
793	const CXXRecordDecl *Rec = Method->getParent();
794	if (Rec->isLambda())
795	return CDK_Lambda;
796	}
797	return CDK_Function;
798	};
799
800	// Should only be called when function's analysis is determined to be
801	// complete.
802	void emitDiagnostics(ArrayRef<Violation> Viols, const CallableInfo &CInfo) {
803	if (Viols.empty())
804	return;
805
806	auto MaybeAddTemplateNote = [&](const Decl *D) {
807	if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(Val: D)) {
808	while (FD != nullptr && FD->isTemplateInstantiation() &&
809	FD->getPointOfInstantiation().isValid()) {
810	S.Diag(FD->getPointOfInstantiation(),
811	diag::note_func_effect_from_template);
812	FD = FD->getTemplateInstantiationPattern();
813	}
814	}
815	};
816
817	// For note_func_effect_call_indirect.
818	enum { Indirect_VirtualMethod, Indirect_FunctionPtr };
819
820	auto MaybeAddSiteContext = [&](const Decl *D, const Violation &V) {
821	// If a violation site is a member initializer, add a note pointing to
822	// the constructor which invoked it.
823	if (V.Site.kind() == ViolationSite::Kind::MemberInitializer) {
824	unsigned ImplicitCtor = 0;
825	if (auto *Ctor = dyn_cast<CXXConstructorDecl>(Val: D);
826	Ctor && Ctor->isImplicit())
827	ImplicitCtor = 1;
828	S.Diag(D->getLocation(), diag::note_func_effect_in_constructor)
829	<< ImplicitCtor;
830	}
831
832	// If a violation site is a default argument expression, add a note
833	// pointing to the call site using the default argument.
834	else if (V.Site.kind() == ViolationSite::Kind::DefaultArgExpr)
835	S.Diag(V.Site.defaultArgExpr()->getUsedLocation(),
836	diag::note_in_evaluating_default_argument);
837	};
838
839	// Top-level violations are warnings.
840	for (const Violation &Viol1 : Viols) {
841	StringRef effectName = Viol1.Effect.name();
842	switch (Viol1.ID) {
843	case ViolationID::None:
844	case ViolationID::DeclDisallowsInference: // Shouldn't happen
845	// here.
846	llvm_unreachable("Unexpected violation kind");
847	break;
848	case ViolationID::AllocatesMemory:
849	case ViolationID::ThrowsOrCatchesExceptions:
850	case ViolationID::HasStaticLocalVariable:
851	case ViolationID::AccessesThreadLocalVariable:
852	case ViolationID::AccessesObjCMethodOrProperty:
853	S.Diag(Viol1.Loc, diag::warn_func_effect_violation)
854	<< GetCallableDeclKind(CInfo.CDecl, &Viol1) << effectName
855	<< Viol1.diagnosticSelectIndex();
856	MaybeAddSiteContext(CInfo.CDecl, Viol1);
857	MaybeAddTemplateNote(CInfo.CDecl);
858	break;
859	case ViolationID::CallsExprWithoutEffect:
860	S.Diag(Viol1.Loc, diag::warn_func_effect_calls_expr_without_effect)
861	<< GetCallableDeclKind(CInfo.CDecl, &Viol1) << effectName;
862	MaybeAddSiteContext(CInfo.CDecl, Viol1);
863	MaybeAddTemplateNote(CInfo.CDecl);
864	break;
865
866	case ViolationID::CallsDeclWithoutEffect: {
867	CallableInfo CalleeInfo(*Viol1.Callee);
868	std::string CalleeName = CalleeInfo.getNameForDiagnostic(S);
869
870	S.Diag(Viol1.Loc, diag::warn_func_effect_calls_func_without_effect)
871	<< GetCallableDeclKind(CInfo.CDecl, &Viol1) << effectName
872	<< GetCallableDeclKind(CalleeInfo.CDecl, nullptr) << CalleeName;
873	MaybeAddSiteContext(CInfo.CDecl, Viol1);
874	MaybeAddTemplateNote(CInfo.CDecl);
875
876	// Emit notes explaining the transitive chain of inferences: Why isn't
877	// the callee safe?
878	for (const Decl *Callee = Viol1.Callee; Callee != nullptr;) {
879	std::optional<CallableInfo> MaybeNextCallee;
880	CompleteFunctionAnalysis *Completed =
881	DeclAnalysis.completedAnalysisForDecl(D: CalleeInfo.CDecl);
882	if (Completed == nullptr) {
883	// No result - could be
884	// - non-inline and extern
885	// - indirect (virtual or through function pointer)
886	// - effect has been explicitly disclaimed (e.g. "blocking")
887
888	CallableType CType = CalleeInfo.type();
889	if (CType == CallableType::Virtual)
890	S.Diag(Callee->getLocation(),
891	diag::note_func_effect_call_indirect)
892	<< Indirect_VirtualMethod << effectName;
893	else if (CType == CallableType::Unknown)
894	S.Diag(Callee->getLocation(),
895	diag::note_func_effect_call_indirect)
896	<< Indirect_FunctionPtr << effectName;
897	else if (CalleeInfo.Effects.contains(Viol1.Effect.oppositeKind()))
898	S.Diag(Callee->getLocation(),
899	diag::note_func_effect_call_disallows_inference)
900	<< GetCallableDeclKind(CInfo.CDecl, nullptr) << effectName
901	<< FunctionEffect(Viol1.Effect.oppositeKind()).name();
902	else if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(Val: Callee);
903	FD == nullptr || FD->getBuiltinID() == 0) {
904	// A builtin callee generally doesn't have a useful source
905	// location at which to insert a note.
906	S.Diag(Callee->getLocation(), diag::note_func_effect_call_extern)
907	<< effectName;
908	}
909	break;
910	}
911	const Violation *PtrViol2 =
912	Completed->firstViolationForEffect(Effect: Viol1.Effect);
913	if (PtrViol2 == nullptr)
914	break;
915
916	const Violation &Viol2 = *PtrViol2;
917	switch (Viol2.ID) {
918	case ViolationID::None:
919	llvm_unreachable("Unexpected violation kind");
920	break;
921	case ViolationID::DeclDisallowsInference:
922	S.Diag(Viol2.Loc, diag::note_func_effect_call_disallows_inference)
923	<< GetCallableDeclKind(CalleeInfo.CDecl, nullptr) << effectName
924	<< Viol2.CalleeEffectPreventingInference->name();
925	break;
926	case ViolationID::CallsExprWithoutEffect:
927	S.Diag(Viol2.Loc, diag::note_func_effect_call_indirect)
928	<< Indirect_FunctionPtr << effectName;
929	break;
930	case ViolationID::AllocatesMemory:
931	case ViolationID::ThrowsOrCatchesExceptions:
932	case ViolationID::HasStaticLocalVariable:
933	case ViolationID::AccessesThreadLocalVariable:
934	case ViolationID::AccessesObjCMethodOrProperty:
935	S.Diag(Viol2.Loc, diag::note_func_effect_violation)
936	<< GetCallableDeclKind(CalleeInfo.CDecl, &Viol2) << effectName
937	<< Viol2.diagnosticSelectIndex();
938	MaybeAddSiteContext(CalleeInfo.CDecl, Viol2);
939	break;
940	case ViolationID::CallsDeclWithoutEffect:
941	MaybeNextCallee.emplace(*Viol2.Callee);
942	S.Diag(Viol2.Loc, diag::note_func_effect_calls_func_without_effect)
943	<< GetCallableDeclKind(CalleeInfo.CDecl, &Viol2) << effectName
944	<< GetCallableDeclKind(Viol2.Callee, nullptr)
945	<< MaybeNextCallee->getNameForDiagnostic(S);
946	break;
947	}
948	MaybeAddTemplateNote(Callee);
949	Callee = Viol2.Callee;
950	if (MaybeNextCallee) {
951	CalleeInfo = *MaybeNextCallee;
952	CalleeName = CalleeInfo.getNameForDiagnostic(S);
953	}
954	}
955	} break;
956	}
957	}
958	}
959
960	// ----------
961	// This AST visitor is used to traverse the body of a function during effect
962	// verification. This happens in 2 situations:
963	// [1] The function has declared effects which need to be validated.
964	// [2] The function has not explicitly declared an effect in question, and is
965	// being checked for implicit conformance.
966	//
967	// Violations are always routed to a PendingFunctionAnalysis.
968	struct FunctionBodyASTVisitor : DynamicRecursiveASTVisitor {
969	Analyzer &Outer;
970	PendingFunctionAnalysis &CurrentFunction;
971	CallableInfo &CurrentCaller;
972	ViolationSite VSite;
973	const Expr *TrailingRequiresClause = nullptr;
974	const Expr *NoexceptExpr = nullptr;
975
976	FunctionBodyASTVisitor(Analyzer &Outer,
977	PendingFunctionAnalysis &CurrentFunction,
978	CallableInfo &CurrentCaller)
979	: Outer(Outer), CurrentFunction(CurrentFunction),
980	CurrentCaller(CurrentCaller) {
981	ShouldVisitImplicitCode = true;
982	ShouldWalkTypesOfTypeLocs = false;
983	}
984
985	// -- Entry point --
986	void run() {
987	// The target function may have implicit code paths beyond the
988	// body: member and base destructors. Visit these first.
989	if (auto *Dtor = dyn_cast<CXXDestructorDecl>(Val: CurrentCaller.CDecl))
990	followDestructor(Rec: dyn_cast<CXXRecordDecl>(Dtor->getParent()), Dtor);
991
992	if (auto *FD = dyn_cast<FunctionDecl>(Val: CurrentCaller.CDecl)) {
993	TrailingRequiresClause = FD->getTrailingRequiresClause().ConstraintExpr;
994
995	// Note that FD->getType->getAs<FunctionProtoType>() can yield a
996	// noexcept Expr which has been boiled down to a constant expression.
997	// Going through the TypeSourceInfo obtains the actual expression which
998	// will be traversed as part of the function -- unless we capture it
999	// here and have TraverseStmt skip it.
1000	if (TypeSourceInfo *TSI = FD->getTypeSourceInfo()) {
1001	if (FunctionProtoTypeLoc TL =
1002	TSI->getTypeLoc().getAs<FunctionProtoTypeLoc>())
1003	if (const FunctionProtoType *FPT = TL.getTypePtr())
1004	NoexceptExpr = FPT->getNoexceptExpr();
1005	}
1006	}
1007
1008	// Do an AST traversal of the function/block body
1009	TraverseDecl(const_cast<Decl *>(CurrentCaller.CDecl));
1010	}
1011
1012	// -- Methods implementing common logic --
1013
1014	// Handle a language construct forbidden by some effects. Only effects whose
1015	// flags include the specified flag receive a violation. \p Flag describes
1016	// the construct.
1017	void diagnoseLanguageConstruct(FunctionEffect::FlagBit Flag,
1018	ViolationID VID, SourceLocation Loc,
1019	const Decl *Callee = nullptr) {
1020	// If there are any declared verifiable effects which forbid the construct
1021	// represented by the flag, store just one violation.
1022	for (FunctionEffect Effect : CurrentFunction.DeclaredVerifiableEffects) {
1023	if (Effect.flags() & Flag) {
1024	addViolation(/*inferring=*/false, Effect, VID, Loc, Callee);
1025	break;
1026	}
1027	}
1028	// For each inferred effect which forbids the construct, store a
1029	// violation, if we don't already have a violation for that effect.
1030	for (FunctionEffect Effect : CurrentFunction.EffectsToInfer)
1031	if (Effect.flags() & Flag)
1032	addViolation(/*inferring=*/true, Effect, VID, Loc, Callee);
1033	}
1034
1035	void addViolation(bool Inferring, FunctionEffect Effect, ViolationID VID,
1036	SourceLocation Loc, const Decl *Callee = nullptr) {
1037	CurrentFunction.checkAddViolation(
1038	Inferring, NewViol: Violation(Effect, VID, VSite, Loc, Callee));
1039	}
1040
1041	// Here we have a call to a Decl, either explicitly via a CallExpr or some
1042	// other AST construct. CallableInfo pertains to the callee.
1043	void followCall(CallableInfo &CI, SourceLocation CallLoc) {
1044	// Check for a call to a builtin function, whose effects are
1045	// handled specially.
1046	if (const auto *FD = dyn_cast<FunctionDecl>(Val: CI.CDecl)) {
1047	if (unsigned BuiltinID = FD->getBuiltinID()) {
1048	CI.Effects = getBuiltinFunctionEffects(BuiltinID);
1049	if (CI.Effects.empty()) {
1050	// A builtin with no known effects is assumed safe.
1051	return;
1052	}
1053	// A builtin WITH effects doesn't get any special treatment for
1054	// being noreturn/noexcept, e.g. longjmp(), so we skip the check
1055	// below.
1056	} else {
1057	// If the callee is both `noreturn` and `noexcept`, it presumably
1058	// terminates. Ignore it for the purposes of effect analysis.
1059	// If not C++, `noreturn` alone is sufficient.
1060	if (FD->isNoReturn() &&
1061	(!Outer.S.getLangOpts().CPlusPlus || isNoexcept(FD)))
1062	return;
1063	}
1064	}
1065
1066	Outer.followCall(Caller: CurrentCaller, PFA&: CurrentFunction, Callee: CI, CallLoc,
1067	/*AssertNoFurtherInference=*/false, VSite);
1068	}
1069
1070	void checkIndirectCall(CallExpr *Call, QualType CalleeType) {
1071	FunctionEffectKindSet CalleeEffects;
1072	if (FunctionEffectsRef Effects = FunctionEffectsRef::get(QT: CalleeType);
1073	!Effects.empty())
1074	CalleeEffects.insert(FX: Effects);
1075
1076	auto Check1Effect = [&](FunctionEffect Effect, bool Inferring) {
1077	if (Effect.shouldDiagnoseFunctionCall(
1078	/*direct=*/Direct: false, CalleeFX: CalleeEffects))
1079	addViolation(Inferring, Effect, VID: ViolationID::CallsExprWithoutEffect,
1080	Loc: Call->getBeginLoc());
1081	};
1082
1083	for (FunctionEffect Effect : CurrentFunction.DeclaredVerifiableEffects)
1084	Check1Effect(Effect, false);
1085
1086	for (FunctionEffect Effect : CurrentFunction.EffectsToInfer)
1087	Check1Effect(Effect, true);
1088	}
1089
1090	// This destructor's body should be followed by the caller, but here we
1091	// follow the field and base destructors.
1092	void followDestructor(const CXXRecordDecl *Rec,
1093	const CXXDestructorDecl *Dtor) {
1094	SourceLocation DtorLoc = Dtor->getLocation();
1095	for (const FieldDecl *Field : Rec->fields())
1096	followTypeDtor(Field->getType(), DtorLoc);
1097
1098	if (const auto *Class = dyn_cast<CXXRecordDecl>(Val: Rec))
1099	for (const CXXBaseSpecifier &Base : Class->bases())
1100	followTypeDtor(QT: Base.getType(), CallSite: DtorLoc);
1101	}
1102
1103	void followTypeDtor(QualType QT, SourceLocation CallSite) {
1104	const Type *Ty = QT.getTypePtr();
1105	while (Ty->isArrayType()) {
1106	const ArrayType *Arr = Ty->getAsArrayTypeUnsafe();
1107	QT = Arr->getElementType();
1108	Ty = QT.getTypePtr();
1109	}
1110
1111	if (Ty->isRecordType()) {
1112	if (const CXXRecordDecl *Class = Ty->getAsCXXRecordDecl()) {
1113	if (CXXDestructorDecl *Dtor = Class->getDestructor();
1114	Dtor && !Dtor->isDeleted()) {
1115	CallableInfo CI(*Dtor);
1116	followCall(CI, CallLoc: CallSite);
1117	}
1118	}
1119	}
1120	}
1121
1122	// -- Methods for use of RecursiveASTVisitor --
1123
1124	bool VisitCXXThrowExpr(CXXThrowExpr *Throw) override {
1125	diagnoseLanguageConstruct(Flag: FunctionEffect::FE_ExcludeThrow,
1126	VID: ViolationID::ThrowsOrCatchesExceptions,
1127	Loc: Throw->getThrowLoc());
1128	return true;
1129	}
1130
1131	bool VisitCXXCatchStmt(CXXCatchStmt *Catch) override {
1132	diagnoseLanguageConstruct(Flag: FunctionEffect::FE_ExcludeCatch,
1133	VID: ViolationID::ThrowsOrCatchesExceptions,
1134	Loc: Catch->getCatchLoc());
1135	return true;
1136	}
1137
1138	bool VisitObjCAtThrowStmt(ObjCAtThrowStmt *Throw) override {
1139	diagnoseLanguageConstruct(Flag: FunctionEffect::FE_ExcludeThrow,
1140	VID: ViolationID::ThrowsOrCatchesExceptions,
1141	Loc: Throw->getThrowLoc());
1142	return true;
1143	}
1144
1145	bool VisitObjCAtCatchStmt(ObjCAtCatchStmt *Catch) override {
1146	diagnoseLanguageConstruct(Flag: FunctionEffect::FE_ExcludeCatch,
1147	VID: ViolationID::ThrowsOrCatchesExceptions,
1148	Loc: Catch->getAtCatchLoc());
1149	return true;
1150	}
1151
1152	bool VisitObjCAtFinallyStmt(ObjCAtFinallyStmt *Finally) override {
1153	diagnoseLanguageConstruct(Flag: FunctionEffect::FE_ExcludeCatch,
1154	VID: ViolationID::ThrowsOrCatchesExceptions,
1155	Loc: Finally->getAtFinallyLoc());
1156	return true;
1157	}
1158
1159	bool VisitObjCMessageExpr(ObjCMessageExpr *Msg) override {
1160	diagnoseLanguageConstruct(Flag: FunctionEffect::FE_ExcludeObjCMessageSend,
1161	VID: ViolationID::AccessesObjCMethodOrProperty,
1162	Loc: Msg->getBeginLoc());
1163	return true;
1164	}
1165
1166	bool VisitObjCAutoreleasePoolStmt(ObjCAutoreleasePoolStmt *ARP) override {
1167	// Under the hood, @autorelease (potentially?) allocates memory and
1168	// invokes ObjC methods. We don't currently have memory allocation as
1169	// a "language construct" but we do have ObjC messaging, so diagnose that.
1170	diagnoseLanguageConstruct(Flag: FunctionEffect::FE_ExcludeObjCMessageSend,
1171	VID: ViolationID::AccessesObjCMethodOrProperty,
1172	Loc: ARP->getBeginLoc());
1173	return true;
1174	}
1175
1176	bool VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt *Sync) override {
1177	// Under the hood, this calls objc_sync_enter and objc_sync_exit, wrapped
1178	// in a @try/@finally block. Diagnose this generically as "ObjC
1179	// messaging".
1180	diagnoseLanguageConstruct(Flag: FunctionEffect::FE_ExcludeObjCMessageSend,
1181	VID: ViolationID::AccessesObjCMethodOrProperty,
1182	Loc: Sync->getBeginLoc());
1183	return true;
1184	}
1185
1186	bool VisitSEHExceptStmt(SEHExceptStmt *Exc) override {
1187	diagnoseLanguageConstruct(Flag: FunctionEffect::FE_ExcludeCatch,
1188	VID: ViolationID::ThrowsOrCatchesExceptions,
1189	Loc: Exc->getExceptLoc());
1190	return true;
1191	}
1192
1193	bool VisitCallExpr(CallExpr *Call) override {
1194	LLVM_DEBUG(llvm::dbgs()
1195	<< "VisitCallExpr : "
1196	<< Call->getBeginLoc().printToString(Outer.S.SourceMgr)
1197	<< "\n";);
1198
1199	Expr *CalleeExpr = Call->getCallee();
1200	if (const Decl *Callee = CalleeExpr->getReferencedDeclOfCallee()) {
1201	CallableInfo CI(*Callee);
1202	followCall(CI, CallLoc: Call->getBeginLoc());
1203	return true;
1204	}
1205
1206	if (isa<CXXPseudoDestructorExpr>(Val: CalleeExpr)) {
1207	// Just destroying a scalar, fine.
1208	return true;
1209	}
1210
1211	// No Decl, just an Expr. Just check based on its type.
1212	checkIndirectCall(Call, CalleeType: CalleeExpr->getType());
1213
1214	return true;
1215	}
1216
1217	bool VisitVarDecl(VarDecl *Var) override {
1218	LLVM_DEBUG(llvm::dbgs()
1219	<< "VisitVarDecl : "
1220	<< Var->getBeginLoc().printToString(Outer.S.SourceMgr)
1221	<< "\n";);
1222
1223	if (Var->isStaticLocal())
1224	diagnoseLanguageConstruct(Flag: FunctionEffect::FE_ExcludeStaticLocalVars,
1225	VID: ViolationID::HasStaticLocalVariable,
1226	Loc: Var->getLocation());
1227
1228	const QualType::DestructionKind DK =
1229	Var->needsDestruction(Ctx: Outer.S.getASTContext());
1230	if (DK == QualType::DK_cxx_destructor)
1231	followTypeDtor(QT: Var->getType(), CallSite: Var->getLocation());
1232	return true;
1233	}
1234
1235	bool VisitCXXNewExpr(CXXNewExpr *New) override {
1236	// RecursiveASTVisitor does not visit the implicit call to operator new.
1237	if (FunctionDecl *FD = New->getOperatorNew()) {
1238	CallableInfo CI(*FD, SpecialFuncType::OperatorNew);
1239	followCall(CI, CallLoc: New->getBeginLoc());
1240	}
1241
1242	// It's a bit excessive to check operator delete here, since it's
1243	// just a fallback for operator new followed by a failed constructor.
1244	// We could check it via New->getOperatorDelete().
1245
1246	// It DOES however visit the called constructor
1247	return true;
1248	}
1249
1250	bool VisitCXXDeleteExpr(CXXDeleteExpr *Delete) override {
1251	// RecursiveASTVisitor does not visit the implicit call to operator
1252	// delete.
1253	if (FunctionDecl *FD = Delete->getOperatorDelete()) {
1254	CallableInfo CI(*FD, SpecialFuncType::OperatorDelete);
1255	followCall(CI, CallLoc: Delete->getBeginLoc());
1256	}
1257
1258	// It DOES however visit the called destructor
1259
1260	return true;
1261	}
1262
1263	bool VisitCXXConstructExpr(CXXConstructExpr *Construct) override {
1264	LLVM_DEBUG(llvm::dbgs() << "VisitCXXConstructExpr : "
1265	<< Construct->getBeginLoc().printToString(
1266	Outer.S.SourceMgr)
1267	<< "\n";);
1268
1269	// RecursiveASTVisitor does not visit the implicit call to the
1270	// constructor.
1271	const CXXConstructorDecl *Ctor = Construct->getConstructor();
1272	CallableInfo CI(*Ctor);
1273	followCall(CI, CallLoc: Construct->getLocation());
1274
1275	return true;
1276	}
1277
1278	bool TraverseStmt(Stmt *Statement) override {
1279	// If this statement is a `requires` clause from the top-level function
1280	// being traversed, ignore it, since it's not generating runtime code.
1281	// We skip the traversal of lambdas (beyond their captures, see
1282	// TraverseLambdaExpr below), so just caching this from our constructor
1283	// should suffice.
1284	if (Statement != TrailingRequiresClause && Statement != NoexceptExpr)
1285	return DynamicRecursiveASTVisitor::TraverseStmt(Statement);
1286	return true;
1287	}
1288
1289	bool TraverseConstructorInitializer(CXXCtorInitializer *Init) override {
1290	ViolationSite PrevVS = VSite;
1291	if (Init->isAnyMemberInitializer())
1292	VSite.setKind(ViolationSite::Kind::MemberInitializer);
1293	bool Result =
1294	DynamicRecursiveASTVisitor::TraverseConstructorInitializer(Init);
1295	VSite = PrevVS;
1296	return Result;
1297	}
1298
1299	bool TraverseCXXDefaultArgExpr(CXXDefaultArgExpr *E) override {
1300	LLVM_DEBUG(llvm::dbgs()
1301	<< "TraverseCXXDefaultArgExpr : "
1302	<< E->getUsedLocation().printToString(Outer.S.SourceMgr)
1303	<< "\n";);
1304
1305	ViolationSite PrevVS = VSite;
1306	if (VSite.kind() == ViolationSite::Kind::Default)
1307	VSite = ViolationSite{E};
1308
1309	bool Result = DynamicRecursiveASTVisitor::TraverseCXXDefaultArgExpr(E);
1310	VSite = PrevVS;
1311	return Result;
1312	}
1313
1314	bool TraverseLambdaExpr(LambdaExpr *Lambda) override {
1315	// We override this so as to be able to skip traversal of the lambda's
1316	// body. We have to explicitly traverse the captures. Why not return
1317	// false from shouldVisitLambdaBody()? Because we need to visit a lambda's
1318	// body when we are verifying the lambda itself; we only want to skip it
1319	// in the context of the outer function.
1320	for (unsigned I = 0, N = Lambda->capture_size(); I < N; ++I)
1321	TraverseLambdaCapture(Lambda, Lambda->capture_begin() + I,
1322	Lambda->capture_init_begin()[I]);
1323
1324	return true;
1325	}
1326
1327	bool TraverseBlockExpr(BlockExpr * /*unused*/) override {
1328	// As with lambdas, don't traverse the block's body.
1329	// TODO: are the capture expressions (ctor call?) safe?
1330	return true;
1331	}
1332
1333	bool VisitDeclRefExpr(DeclRefExpr *E) override {
1334	const ValueDecl *Val = E->getDecl();
1335	if (const auto *Var = dyn_cast<VarDecl>(Val)) {
1336	if (Var->getTLSKind() != VarDecl::TLS_None) {
1337	// At least on macOS, thread-local variables are initialized on
1338	// first access, including a heap allocation.
1339	diagnoseLanguageConstruct(Flag: FunctionEffect::FE_ExcludeThreadLocalVars,
1340	VID: ViolationID::AccessesThreadLocalVariable,
1341	Loc: E->getLocation());
1342	}
1343	}
1344	return true;
1345	}
1346
1347	bool TraverseGenericSelectionExpr(GenericSelectionExpr *Node) override {
1348	return TraverseStmt(Node->getResultExpr());
1349	}
1350	bool
1351	TraverseUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *Node) override {
1352	return true;
1353	}
1354
1355	bool TraverseTypeOfExprTypeLoc(TypeOfExprTypeLoc Node) override {
1356	return true;
1357	}
1358
1359	bool TraverseDecltypeTypeLoc(DecltypeTypeLoc Node) override { return true; }
1360
1361	bool TraverseCXXNoexceptExpr(CXXNoexceptExpr *Node) override {
1362	return true;
1363	}
1364
1365	bool TraverseCXXTypeidExpr(CXXTypeidExpr *Node) override { return true; }
1366
1367	// Skip concept requirements since they don't generate code.
1368	bool TraverseConceptRequirement(concepts::Requirement *R) override {
1369	return true;
1370	}
1371	};
1372	};
1373
1374	Analyzer::AnalysisMap::~AnalysisMap() {
1375	for (const auto &Item : *this) {
1376	FuncAnalysisPtr AP = Item.second;
1377	if (auto *PFA = dyn_cast<PendingFunctionAnalysis *>(Val&: AP))
1378	delete PFA;
1379	else
1380	delete cast<CompleteFunctionAnalysis *>(Val&: AP);
1381	}
1382	}
1383
1384	} // anonymous namespace
1385
1386	namespace clang {
1387
1388	bool Sema::diagnoseConflictingFunctionEffect(
1389	const FunctionEffectsRef &FX, const FunctionEffectWithCondition &NewEC,
1390	SourceLocation NewAttrLoc) {
1391	// If the new effect has a condition, we can't detect conflicts until the
1392	// condition is resolved.
1393	if (NewEC.Cond.getCondition() != nullptr)
1394	return false;
1395
1396	// Diagnose the new attribute as incompatible with a previous one.
1397	auto Incompatible = [&](const FunctionEffectWithCondition &PrevEC) {
1398	Diag(NewAttrLoc, diag::err_attributes_are_not_compatible)
1399	<< ("'" + NewEC.description() + "'")
1400	<< ("'" + PrevEC.description() + "'") << false;
1401	// We don't necessarily have the location of the previous attribute,
1402	// so no note.
1403	return true;
1404	};
1405
1406	// Compare against previous attributes.
1407	FunctionEffect::Kind NewKind = NewEC.Effect.kind();
1408
1409	for (const FunctionEffectWithCondition &PrevEC : FX) {
1410	// Again, can't check yet when the effect is conditional.
1411	if (PrevEC.Cond.getCondition() != nullptr)
1412	continue;
1413
1414	FunctionEffect::Kind PrevKind = PrevEC.Effect.kind();
1415	// Note that we allow PrevKind == NewKind; it's redundant and ignored.
1416
1417	if (PrevEC.Effect.oppositeKind() == NewKind)
1418	return Incompatible(PrevEC);
1419
1420	// A new allocating is incompatible with a previous nonblocking.
1421	if (PrevKind == FunctionEffect::Kind::NonBlocking &&
1422	NewKind == FunctionEffect::Kind::Allocating)
1423	return Incompatible(PrevEC);
1424
1425	// A new nonblocking is incompatible with a previous allocating.
1426	if (PrevKind == FunctionEffect::Kind::Allocating &&
1427	NewKind == FunctionEffect::Kind::NonBlocking)
1428	return Incompatible(PrevEC);
1429	}
1430
1431	return false;
1432	}
1433
1434	void Sema::diagnoseFunctionEffectMergeConflicts(
1435	const FunctionEffectSet::Conflicts &Errs, SourceLocation NewLoc,
1436	SourceLocation OldLoc) {
1437	for (const FunctionEffectSet::Conflict &Conflict : Errs) {
1438	Diag(NewLoc, diag::warn_conflicting_func_effects)
1439	<< Conflict.Kept.description() << Conflict.Rejected.description();
1440	Diag(OldLoc, diag::note_previous_declaration);
1441	}
1442	}
1443
1444	// Decl should be a FunctionDecl or BlockDecl.
1445	void Sema::maybeAddDeclWithEffects(const Decl *D,
1446	const FunctionEffectsRef &FX) {
1447	if (!D->hasBody()) {
1448	if (const auto *FD = D->getAsFunction(); FD && !FD->willHaveBody())
1449	return;
1450	}
1451
1452	if (Diags.getIgnoreAllWarnings() ||
1453	(Diags.getSuppressSystemWarnings() &&
1454	SourceMgr.isInSystemHeader(Loc: D->getLocation())))
1455	return;
1456
1457	if (hasUncompilableErrorOccurred())
1458	return;
1459
1460	// For code in dependent contexts, we'll do this at instantiation time.
1461	// Without this check, we would analyze the function based on placeholder
1462	// template parameters, and potentially generate spurious diagnostics.
1463	if (cast<DeclContext>(Val: D)->isDependentContext())
1464	return;
1465
1466	addDeclWithEffects(D, FX);
1467	}
1468
1469	void Sema::addDeclWithEffects(const Decl *D, const FunctionEffectsRef &FX) {
1470	// To avoid the possibility of conflict, don't add effects which are
1471	// not FE_InferrableOnCallees and therefore not verified; this removes
1472	// blocking/allocating but keeps nonblocking/nonallocating.
1473	// Also, ignore any conditions when building the list of effects.
1474	bool AnyVerifiable = false;
1475	for (const FunctionEffectWithCondition &EC : FX)
1476	if (EC.Effect.flags() & FunctionEffect::FE_InferrableOnCallees) {
1477	AllEffectsToVerify.insert(EC.Effect);
1478	AnyVerifiable = true;
1479	}
1480
1481	// Record the declaration for later analysis.
1482	if (AnyVerifiable)
1483	DeclsWithEffectsToVerify.push_back(Elt: D);
1484	}
1485
1486	void Sema::performFunctionEffectAnalysis(TranslationUnitDecl *TU) {
1487	if (hasUncompilableErrorOccurred() || Diags.getIgnoreAllWarnings())
1488	return;
1489	if (TU == nullptr)
1490	return;
1491	Analyzer{*this}.run(TU: *TU);
1492	}
1493
1494	Sema::FunctionEffectDiffVector::FunctionEffectDiffVector(
1495	const FunctionEffectsRef &Old, const FunctionEffectsRef &New) {
1496
1497	FunctionEffectsRef::iterator POld = Old.begin();
1498	FunctionEffectsRef::iterator OldEnd = Old.end();
1499	FunctionEffectsRef::iterator PNew = New.begin();
1500	FunctionEffectsRef::iterator NewEnd = New.end();
1501
1502	while (true) {
1503	int cmp = 0;
1504	if (POld == OldEnd) {
1505	if (PNew == NewEnd)
1506	break;
1507	cmp = 1;
1508	} else if (PNew == NewEnd)
1509	cmp = -1;
1510	else {
1511	FunctionEffectWithCondition Old = *POld;
1512	FunctionEffectWithCondition New = *PNew;
1513	if (Old.Effect.kind() < New.Effect.kind())
1514	cmp = -1;
1515	else if (New.Effect.kind() < Old.Effect.kind())
1516	cmp = 1;
1517	else {
1518	cmp = 0;
1519	if (Old.Cond.getCondition() != New.Cond.getCondition()) {
1520	// FIXME: Cases where the expressions are equivalent but
1521	// don't have the same identity.
1522	push_back(Elt: FunctionEffectDiff{
1523	.EffectKind: Old.Effect.kind(), .DiffKind: FunctionEffectDiff::Kind::ConditionMismatch,
1524	.Old: Old, .New: New});
1525	}
1526	}
1527	}
1528
1529	if (cmp < 0) {
1530	// removal
1531	FunctionEffectWithCondition Old = *POld;
1532	push_back(Elt: FunctionEffectDiff{.EffectKind: Old.Effect.kind(),
1533	.DiffKind: FunctionEffectDiff::Kind::Removed, .Old: Old,
1534	.New: std::nullopt});
1535	++POld;
1536	} else if (cmp > 0) {
1537	// addition
1538	FunctionEffectWithCondition New = *PNew;
1539	push_back(Elt: FunctionEffectDiff{.EffectKind: New.Effect.kind(),
1540	.DiffKind: FunctionEffectDiff::Kind::Added,
1541	.Old: std::nullopt, .New: New});
1542	++PNew;
1543	} else {
1544	++POld;
1545	++PNew;
1546	}
1547	}
1548	}
1549
1550	bool Sema::FunctionEffectDiff::shouldDiagnoseConversion(
1551	QualType SrcType, const FunctionEffectsRef &SrcFX, QualType DstType,
1552	const FunctionEffectsRef &DstFX) const {
1553
1554	switch (EffectKind) {
1555	case FunctionEffect::Kind::NonAllocating:
1556	// nonallocating can't be added (spoofed) during a conversion, unless we
1557	// have nonblocking.
1558	if (DiffKind == Kind::Added) {
1559	for (const auto &CFE : SrcFX) {
1560	if (CFE.Effect.kind() == FunctionEffect::Kind::NonBlocking)
1561	return false;
1562	}
1563	}
1564	[[fallthrough]];
1565	case FunctionEffect::Kind::NonBlocking:
1566	// nonblocking can't be added (spoofed) during a conversion.
1567	switch (DiffKind) {
1568	case Kind::Added:
1569	return true;
1570	case Kind::Removed:
1571	return false;
1572	case Kind::ConditionMismatch:
1573	// FIXME: Condition mismatches are too coarse right now -- expressions
1574	// which are equivalent but don't have the same identity are detected as
1575	// mismatches. We're going to diagnose those anyhow until expression
1576	// matching is better.
1577	return true;
1578	}
1579	break;
1580	case FunctionEffect::Kind::Blocking:
1581	case FunctionEffect::Kind::Allocating:
1582	return false;
1583	}
1584	llvm_unreachable("unknown effect kind");
1585	}
1586
1587	bool Sema::FunctionEffectDiff::shouldDiagnoseRedeclaration(
1588	const FunctionDecl &OldFunction, const FunctionEffectsRef &OldFX,
1589	const FunctionDecl &NewFunction, const FunctionEffectsRef &NewFX) const {
1590	switch (EffectKind) {
1591	case FunctionEffect::Kind::NonAllocating:
1592	case FunctionEffect::Kind::NonBlocking:
1593	// nonblocking/nonallocating can't be removed in a redeclaration.
1594	switch (DiffKind) {
1595	case Kind::Added:
1596	return false; // No diagnostic.
1597	case Kind::Removed:
1598	return true; // Issue diagnostic.
1599	case Kind::ConditionMismatch:
1600	// All these forms of mismatches are diagnosed.
1601	return true;
1602	}
1603	break;
1604	case FunctionEffect::Kind::Blocking:
1605	case FunctionEffect::Kind::Allocating:
1606	return false;
1607	}
1608	llvm_unreachable("unknown effect kind");
1609	}
1610
1611	Sema::FunctionEffectDiff::OverrideResult
1612	Sema::FunctionEffectDiff::shouldDiagnoseMethodOverride(
1613	const CXXMethodDecl &OldMethod, const FunctionEffectsRef &OldFX,
1614	const CXXMethodDecl &NewMethod, const FunctionEffectsRef &NewFX) const {
1615	switch (EffectKind) {
1616	case FunctionEffect::Kind::NonAllocating:
1617	case FunctionEffect::Kind::NonBlocking:
1618	switch (DiffKind) {
1619
1620	// If added on an override, that's fine and not diagnosed.
1621	case Kind::Added:
1622	return OverrideResult::NoAction;
1623
1624	// If missing from an override (removed), propagate from base to derived.
1625	case Kind::Removed:
1626	return OverrideResult::Merge;
1627
1628	// If there's a mismatch involving the effect's polarity or condition,
1629	// issue a warning.
1630	case Kind::ConditionMismatch:
1631	return OverrideResult::Warn;
1632	}
1633	break;
1634	case FunctionEffect::Kind::Blocking:
1635	case FunctionEffect::Kind::Allocating:
1636	return OverrideResult::NoAction;
1637	}
1638	llvm_unreachable("unknown effect kind");
1639	}
1640
1641	} // namespace clang
1642