================ @@ -0,0 +1,1199 @@ +//=== EffectAnalysis.cpp - Sema warnings for function effects -------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file implements caller/callee analysis for function effects. +// +//===----------------------------------------------------------------------===// + +#include "clang/AST/Decl.h" +#include "clang/AST/RecursiveASTVisitor.h" +#include "clang/AST/Stmt.h" +#include "clang/AST/Type.h" +#include "clang/Basic/SourceManager.h" +#include "clang/Sema/SemaInternal.h" + +#define DEBUG_TYPE "fxanalysis" + +using namespace clang; + +namespace { + +enum class ViolationID : uint8_t { + None = 0, // sentinel for an empty Violation + Throws, + Catches, + CallsObjC, + AllocatesMemory, + HasStaticLocal, + AccessesThreadLocal, + + // These only apply to callees, where the analysis stops at the Decl + DeclDisallowsInference, + + CallsDeclWithoutEffect, + CallsExprWithoutEffect, +}; + +// Represents a violation of the rules, potentially for the entire duration of +// the analysis phase, in order to refer to it when explaining why a caller has +// been made unsafe by a callee. Can be transformed into either a Diagnostic +// (warning or a note), depending on whether the violation pertains to a +// function failing to be verifed as holding an effect vs. a function failing to +// be inferred as holding that effect. +struct Violation { + FunctionEffect Effect; + FunctionEffect CalleeEffectPreventingInference; // only for certain IDs + ViolationID ID = ViolationID::None; + SourceLocation Loc; + const Decl *Callee = nullptr; // only valid for Calls* + + Violation() = default; + + Violation(const FunctionEffect &Effect, ViolationID ID, SourceLocation Loc, + const Decl *Callee = nullptr, + const FunctionEffect *CalleeEffect = nullptr) + : Effect(Effect), ID(ID), Loc(Loc), Callee(Callee) { + if (CalleeEffect != nullptr) + CalleeEffectPreventingInference = *CalleeEffect; + } +}; + +enum class SpecialFuncType : uint8_t { None, OperatorNew, OperatorDelete }; +enum class CallableType { + // unknown: probably function pointer + Unknown, + Function, + Virtual, + Block +}; + +// Return whether a function's effects CAN be verified. +// The question of whether it SHOULD be verified is independent. +static bool functionIsVerifiable(const FunctionDecl *FD) { + if (FD->isTrivial()) { + // Otherwise `struct x { int a; };` would have an unverifiable default + // constructor. + return true; + } + return FD->hasBody(); +} + +static bool isNoexcept(const FunctionDecl *FD) { + const auto *FPT = FD->getType()->castAs<FunctionProtoType>(); + if (FPT->isNothrow() || FD->hasAttr<NoThrowAttr>()) + return true; + return false; +} + +// Transitory, more extended information about a callable, which can be a +// function, block, or function pointer. +struct CallableInfo { + // CDecl holds the function's definition, if any. + // FunctionDecl if CallableType::Function or Virtual + // BlockDecl if CallableType::Block + const Decl *CDecl; + + // Remember whether the callable is a function, block, virtual method, + // or (presumed) function pointer. + CallableType CType = CallableType::Unknown; + + // Remember whether the callable is an operator new or delete function, + // so that calls to them are reported more meaningfully, as memory + // allocations. + SpecialFuncType FuncType = SpecialFuncType::None; + + // We inevitably want to know the callable's declared effects, so cache them. + FunctionEffectKindSet Effects; + + CallableInfo(const Decl &CD, SpecialFuncType FT = SpecialFuncType::None) + : CDecl(&CD), FuncType(FT) { + FunctionEffectsRef DeclEffects; + if (auto *FD = dyn_cast<FunctionDecl>(CDecl)) { + // Use the function's definition, if any. + if (const FunctionDecl *Def = FD->getDefinition()) + CDecl = FD = Def; + CType = CallableType::Function; + if (auto *Method = dyn_cast<CXXMethodDecl>(FD); + Method && Method->isVirtual()) + CType = CallableType::Virtual; + DeclEffects = FD->getFunctionEffects(); + } else if (auto *BD = dyn_cast<BlockDecl>(CDecl)) { + CType = CallableType::Block; + DeclEffects = BD->getFunctionEffects(); + } else if (auto *VD = dyn_cast<ValueDecl>(CDecl)) { + // ValueDecl is function, enum, or variable, so just look at its type. + DeclEffects = FunctionEffectsRef::get(VD->getType()); + } + Effects = FunctionEffectKindSet(DeclEffects); + } + + CallableType type() const { return CType; } + + bool isCalledDirectly() const { + return CType == CallableType::Function || CType == CallableType::Block; + } + + bool isVerifiable() const { + switch (CType) { + case CallableType::Unknown: + case CallableType::Virtual: + return false; + case CallableType::Block: + return true; + case CallableType::Function: + return functionIsVerifiable(dyn_cast<FunctionDecl>(CDecl)); + } + llvm_unreachable("undefined CallableType"); + } + + /// Generate a name for logging and diagnostics. + std::string name(Sema &Sem) const { + std::string Name; + llvm::raw_string_ostream OS(Name); + + if (auto *FD = dyn_cast<FunctionDecl>(CDecl)) + FD->getNameForDiagnostic(OS, Sem.getPrintingPolicy(), + /*Qualified=*/true); + else if (auto *BD = dyn_cast<BlockDecl>(CDecl)) + OS << "(block " << BD->getBlockManglingNumber() << ")"; + else if (auto *VD = dyn_cast<NamedDecl>(CDecl)) + VD->printQualifiedName(OS); + return Name; + } +}; + +// ---------- +// Map effects to single Violations, to hold the first (of potentially many) +// violations pertaining to an effect, per function. +class EffectToViolationMap { + // Since we currently only have a tiny number of effects (typically no more + // than 1), use a sorted SmallVector with an inline capacity of 1. Since it + // is often empty, use a unique_ptr to the SmallVector. + // Note that Violation itself contains a FunctionEffect which is the key. + using ImplVec = llvm::SmallVector<Violation, 1>; + std::unique_ptr<ImplVec> Impl; + +public: + // Insert a new Violation if we do not already have one for its effect. + void maybeInsert(const Violation &Viol) { + if (Impl == nullptr) + Impl = std::make_unique<ImplVec>(); + auto *Iter = _find(Viol.Effect); + if (Iter != Impl->end() && Iter->Effect == Viol.Effect) + return; + + Impl->insert(Iter, Viol); + } + + const Violation *lookup(FunctionEffect Key) { + if (Impl == nullptr) + return nullptr; + + auto *Iter = _find(Key); + if (Iter != Impl->end() && Iter->Effect == Key) + return &*Iter; + + return nullptr; + } + + size_t size() const { return Impl ? Impl->size() : 0; } + +private: + ImplVec::iterator _find(const FunctionEffect &key) { + // A linear search suffices for a tiny number of possible effects. + auto *End = Impl->end(); + for (auto *Iter = Impl->begin(); Iter != End; ++Iter) + if (!(Iter->Effect < key)) + return Iter; + return End; + } +}; + +// ---------- +// State pertaining to a function whose AST is walked and whose effect analysis +// is dependent on a subsequent analysis of other functions. +class PendingFunctionAnalysis { + friend class CompleteFunctionAnalysis; + +public: + struct DirectCall { + const Decl *Callee; + SourceLocation CallLoc; + // Not all recursive calls are detected, just enough + // to break cycles. + bool Recursed = false; + + DirectCall(const Decl *D, SourceLocation CallLoc) + : Callee(D), CallLoc(CallLoc) {} + }; + + // We always have two disjoint sets of effects to verify: + // 1. Effects declared explicitly by this function. + // 2. All other inferrable effects needing verification. + FunctionEffectKindSet DeclaredVerifiableEffects; + FunctionEffectKindSet FXToInfer; + +private: + // Violations pertaining to the function's explicit effects. + SmallVector<Violation, 0> ViolationsForExplicitFX; + + // Violations pertaining to other, non-explicit, inferrable effects. + EffectToViolationMap InferrableEffectToFirstViolation; + + // These unverified direct calls are what keeps the analysis "pending", + // until the callees can be verified. + SmallVector<DirectCall, 0> UnverifiedDirectCalls; + +public: + PendingFunctionAnalysis( + Sema &Sem, const CallableInfo &CInfo, + const FunctionEffectKindSet &AllInferrableEffectsToVerify) + : DeclaredVerifiableEffects(CInfo.Effects) { + // Check for effects we are not allowed to infer + FunctionEffectKindSet InferrableFX; + + for (const FunctionEffect &effect : AllInferrableEffectsToVerify) { + std::optional<FunctionEffect> ProblemCalleeEffect = + effect.effectProhibitingInference(*CInfo.CDecl, CInfo.Effects); + if (!ProblemCalleeEffect) + InferrableFX.insert(effect); + else { + // Add a Violation for this effect if a caller were to + // try to infer it. + InferrableEffectToFirstViolation.maybeInsert(Violation( + effect, ViolationID::DeclDisallowsInference, + CInfo.CDecl->getLocation(), nullptr, &*ProblemCalleeEffect)); + } + } + // InferrableFX is now the set of inferrable effects which are not + // prohibited + FXToInfer = FunctionEffectKindSet::difference(InferrableFX, + DeclaredVerifiableEffects); + } + + // Hide the way that Violations for explicitly required effects vs. inferred + // ones are handled differently. + void checkAddViolation(bool Inferring, const Violation &NewViol) { + if (!Inferring) + ViolationsForExplicitFX.push_back(NewViol); + else + InferrableEffectToFirstViolation.maybeInsert(NewViol); + } + + void addUnverifiedDirectCall(const Decl *D, SourceLocation CallLoc) { + UnverifiedDirectCalls.emplace_back(D, CallLoc); + } + + // Analysis is complete when there are no unverified direct calls. + bool isComplete() const { return UnverifiedDirectCalls.empty(); } + + const Violation *violationForInferrableEffect(FunctionEffect effect) { + return InferrableEffectToFirstViolation.lookup(effect); + } + + SmallVector<DirectCall, 0> &unverifiedCalls() { + assert(!isComplete()); + return UnverifiedDirectCalls; + } + + SmallVector<Violation, 0> &getViolationsForExplicitFX() { + return ViolationsForExplicitFX; + } + + void dump(Sema &SemaRef, llvm::raw_ostream &OS) const { + OS << "Pending: Declared "; + DeclaredVerifiableEffects.dump(OS); + OS << ", " << ViolationsForExplicitFX.size() << " violations; "; + OS << " Infer "; + FXToInfer.dump(OS); + OS << ", " << InferrableEffectToFirstViolation.size() << " violations"; + if (!UnverifiedDirectCalls.empty()) { + OS << "; Calls: "; + for (const DirectCall &Call : UnverifiedDirectCalls) { + CallableInfo CI(*Call.Callee); + OS << " " << CI.name(SemaRef); + } + } + OS << "\n"; + } +}; + +// ---------- +class CompleteFunctionAnalysis { + // Current size: 2 pointers +public: + // Has effects which are both the declared ones -- not to be inferred -- plus + // ones which have been successfully inferred. These are all considered + // "verified" for the purposes of callers; any issue with verifying declared + // effects has already been reported and is not the problem of any caller. + FunctionEffectKindSet VerifiedEffects; + +private: + // This is used to generate notes about failed inference. + EffectToViolationMap InferrableEffectToFirstViolation; + +public: + // The incoming Pending analysis is consumed (member(s) are moved-from). + CompleteFunctionAnalysis( + ASTContext &Ctx, PendingFunctionAnalysis &Pending, + const FunctionEffectKindSet &DeclaredEffects, + const FunctionEffectKindSet &AllInferrableEffectsToVerify) + : VerifiedEffects(DeclaredEffects) { + for (const FunctionEffect &effect : AllInferrableEffectsToVerify) + if (Pending.violationForInferrableEffect(effect) == nullptr) + VerifiedEffects.insert(effect); + + InferrableEffectToFirstViolation = + std::move(Pending.InferrableEffectToFirstViolation); + } + + const Violation *firstViolationForEffect(const FunctionEffect &Effect) { + return InferrableEffectToFirstViolation.lookup(Effect); + } + + void dump(llvm::raw_ostream &OS) const { + OS << "Complete: Verified "; + VerifiedEffects.dump(OS); + OS << "; Infer "; + OS << InferrableEffectToFirstViolation.size() << " violations\n"; + } +}; + +const Decl *CanonicalFunctionDecl(const Decl *D) { + if (auto *FD = dyn_cast<FunctionDecl>(D)) { + FD = FD->getCanonicalDecl(); + assert(FD != nullptr); + return FD; + } + return D; +} + +// ========== +class Analyzer { + Sema &Sem; + + // Subset of Sema.AllEffectsToVerify + FunctionEffectKindSet AllInferrableEffectsToVerify; + + using FuncAnalysisPtr = + llvm::PointerUnion<PendingFunctionAnalysis *, CompleteFunctionAnalysis *>; + + // Map all Decls analyzed to FuncAnalysisPtr. Pending state is larger + // than complete state, so use different objects to represent them. + // The state pointers are owned by the container. + class AnalysisMap : protected llvm::DenseMap<const Decl *, FuncAnalysisPtr> { + using Base = llvm::DenseMap<const Decl *, FuncAnalysisPtr>; + + public: + ~AnalysisMap(); + + // Use non-public inheritance in order to maintain the invariant + // that lookups and insertions are via the canonical Decls. + + FuncAnalysisPtr lookup(const Decl *Key) const { + return Base::lookup(CanonicalFunctionDecl(Key)); + } + + FuncAnalysisPtr &operator[](const Decl *Key) { + return Base::operator[](CanonicalFunctionDecl(Key)); + } + + /// Shortcut for the case where we only care about completed analysis. + CompleteFunctionAnalysis *completedAnalysisForDecl(const Decl *D) const { + if (FuncAnalysisPtr AP = lookup(D); + isa_and_nonnull<CompleteFunctionAnalysis *>(AP)) + return AP.get<CompleteFunctionAnalysis *>(); + return nullptr; + } + + void dump(Sema &SemaRef, llvm::raw_ostream &OS) { + OS << "\nAnalysisMap:\n"; + for (const auto &item : *this) { + CallableInfo CI(*item.first); + const auto AP = item.second; + OS << item.first << " " << CI.name(SemaRef) << " : "; + if (AP.isNull()) + OS << "null\n"; + else if (isa<CompleteFunctionAnalysis *>(AP)) { + auto *CFA = AP.get<CompleteFunctionAnalysis *>(); + OS << CFA << " "; + CFA->dump(OS); + } else if (isa<PendingFunctionAnalysis *>(AP)) { + auto *PFA = AP.get<PendingFunctionAnalysis *>(); + OS << PFA << " "; + PFA->dump(SemaRef, OS); + } else + llvm_unreachable("never"); + } + OS << "---\n"; + } + }; + AnalysisMap DeclAnalysis; + +public: + Analyzer(Sema &S) : Sem(S) {} + + void run(const TranslationUnitDecl &TU) { + // Gather all of the effects to be verified to see what operations need to + // be checked, and to see which ones are inferrable. + for (const FunctionEffect &Effect : Sem.AllEffectsToVerify) { + const FunctionEffect::Flags Flags = Effect.flags(); + if (Flags & FunctionEffect::FE_InferrableOnCallees) + AllInferrableEffectsToVerify.insert(Effect); + } + LLVM_DEBUG(llvm::dbgs() << "AllInferrableEffectsToVerify: "; + AllInferrableEffectsToVerify.dump(llvm::dbgs()); + llvm::dbgs() << "\n";); + + // We can use DeclsWithEffectsToVerify as a stack for a + // depth-first traversal; there's no need for a second container. But first, + // reverse it, so when working from the end, Decls are verified in the order + // they are declared. + SmallVector<const Decl *> &VerificationQueue = Sem.DeclsWithEffectsToVerify; + std::reverse(VerificationQueue.begin(), VerificationQueue.end()); + + while (!VerificationQueue.empty()) { + const Decl *D = VerificationQueue.back(); + if (FuncAnalysisPtr AP = DeclAnalysis.lookup(D)) { + if (isa<CompleteFunctionAnalysis *>(AP)) { + // already done + VerificationQueue.pop_back(); + continue; + } + if (isa<PendingFunctionAnalysis *>(AP)) { + // All children have been traversed; finish analysis. + auto *Pending = AP.get<PendingFunctionAnalysis *>(); + finishPendingAnalysis(D, Pending); + VerificationQueue.pop_back(); + continue; + } + llvm_unreachable("unexpected DeclAnalysis item"); + } + + // Not previously visited; begin a new analysis for this Decl. + PendingFunctionAnalysis *Pending = verifyDecl(D); + if (Pending == nullptr) { + // completed now + VerificationQueue.pop_back(); + continue; + } + + // Analysis remains pending because there are direct callees to be + // verified first. Push them onto the queue. + for (PendingFunctionAnalysis::DirectCall &Call : + Pending->unverifiedCalls()) { + FuncAnalysisPtr AP = DeclAnalysis.lookup(Call.Callee); + if (AP.isNull()) { + VerificationQueue.push_back(Call.Callee); + continue; + } + if (isa<PendingFunctionAnalysis *>(AP)) { + // This indicates recursion (not necessarily direct). For the + // purposes of effect analysis, we can just ignore it since + // no effects forbid recursion. + Call.Recursed = true; + continue; + } + llvm_unreachable("unexpected DeclAnalysis item"); + } + } + } + +private: + // Verify a single Decl. Return the pending structure if that was the result, + // else null. This method must not recurse. + PendingFunctionAnalysis *verifyDecl(const Decl *D) { + CallableInfo CInfo(*D); + bool isExternC = false; + + if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) { + assert(FD->getBuiltinID() == 0); ---------------- dougsonos wrote:
No good reason. I think I was afraid of what would happen if I tried to do an AST traversal of a built-in function that happened to have verifiable effects. But builtins aren't verifiable because they don't have bodies. https://github.com/llvm/llvm-project/pull/99656 _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
