Path: blob/main/contrib/llvm-project/clang/lib/Sema/HeuristicResolver.cpp
213766 views
//===--- HeuristicResolver.cpp ---------------------------*- C++-*-===//1//2// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.3// See https://llvm.org/LICENSE.txt for license information.4// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception5//6//===----------------------------------------------------------------------===//78#include "clang/Sema/HeuristicResolver.h"9#include "clang/AST/ASTContext.h"10#include "clang/AST/CXXInheritance.h"11#include "clang/AST/DeclTemplate.h"12#include "clang/AST/ExprCXX.h"13#include "clang/AST/TemplateBase.h"14#include "clang/AST/Type.h"15#include "llvm/ADT/identity.h"1617namespace clang {1819namespace {2021// Helper class for implementing HeuristicResolver.22// Unlike HeuristicResolver which is a long-lived class,23// a new instance of this class is created for every external24// call into a HeuristicResolver operation. That allows this25// class to store state that's local to such a top-level call,26// particularly "recursion protection sets" that keep track of27// nodes that have already been seen to avoid infinite recursion.28class HeuristicResolverImpl {29public:30HeuristicResolverImpl(ASTContext &Ctx) : Ctx(Ctx) {}3132// These functions match the public interface of HeuristicResolver33// (but aren't const since they may modify the recursion protection sets).34std::vector<const NamedDecl *>35resolveMemberExpr(const CXXDependentScopeMemberExpr *ME);36std::vector<const NamedDecl *>37resolveDeclRefExpr(const DependentScopeDeclRefExpr *RE);38std::vector<const NamedDecl *> resolveTypeOfCallExpr(const CallExpr *CE);39std::vector<const NamedDecl *> resolveCalleeOfCallExpr(const CallExpr *CE);40std::vector<const NamedDecl *>41resolveUsingValueDecl(const UnresolvedUsingValueDecl *UUVD);42std::vector<const NamedDecl *>43resolveDependentNameType(const DependentNameType *DNT);44std::vector<const NamedDecl *> resolveTemplateSpecializationType(45const DependentTemplateSpecializationType *DTST);46QualType resolveNestedNameSpecifierToType(const NestedNameSpecifier *NNS);47QualType getPointeeType(QualType T);48std::vector<const NamedDecl *>49lookupDependentName(CXXRecordDecl *RD, DeclarationName Name,50llvm::function_ref<bool(const NamedDecl *ND)> Filter);51TagDecl *resolveTypeToTagDecl(QualType T);52QualType simplifyType(QualType Type, const Expr *E, bool UnwrapPointer);53FunctionProtoTypeLoc getFunctionProtoTypeLoc(const Expr *Fn);5455private:56ASTContext &Ctx;5758// Recursion protection sets59llvm::SmallSet<const DependentNameType *, 4> SeenDependentNameTypes;6061// Given a tag-decl type and a member name, heuristically resolve the62// name to one or more declarations.63// The current heuristic is simply to look up the name in the primary64// template. This is a heuristic because the template could potentially65// have specializations that declare different members.66// Multiple declarations could be returned if the name is overloaded67// (e.g. an overloaded method in the primary template).68// This heuristic will give the desired answer in many cases, e.g.69// for a call to vector<T>::size().70std::vector<const NamedDecl *>71resolveDependentMember(QualType T, DeclarationName Name,72llvm::function_ref<bool(const NamedDecl *ND)> Filter);7374// Try to heuristically resolve the type of a possibly-dependent expression75// `E`.76QualType resolveExprToType(const Expr *E);77std::vector<const NamedDecl *> resolveExprToDecls(const Expr *E);7879bool findOrdinaryMemberInDependentClasses(const CXXBaseSpecifier *Specifier,80CXXBasePath &Path,81DeclarationName Name);82};8384// Convenience lambdas for use as the 'Filter' parameter of85// HeuristicResolver::resolveDependentMember().86const auto NoFilter = [](const NamedDecl *D) { return true; };87const auto NonStaticFilter = [](const NamedDecl *D) {88return D->isCXXInstanceMember();89};90const auto StaticFilter = [](const NamedDecl *D) {91return !D->isCXXInstanceMember();92};93const auto ValueFilter = [](const NamedDecl *D) { return isa<ValueDecl>(D); };94const auto TypeFilter = [](const NamedDecl *D) { return isa<TypeDecl>(D); };95const auto TemplateFilter = [](const NamedDecl *D) {96return isa<TemplateDecl>(D);97};9899QualType resolveDeclsToType(const std::vector<const NamedDecl *> &Decls,100ASTContext &Ctx) {101if (Decls.size() != 1) // Names an overload set -- just bail.102return QualType();103if (const auto *TD = dyn_cast<TypeDecl>(Decls[0])) {104return Ctx.getTypeDeclType(TD);105}106if (const auto *VD = dyn_cast<ValueDecl>(Decls[0])) {107return VD->getType();108}109return QualType();110}111112TemplateName getReferencedTemplateName(const Type *T) {113if (const auto *TST = T->getAs<TemplateSpecializationType>()) {114return TST->getTemplateName();115}116if (const auto *DTST = T->getAs<DeducedTemplateSpecializationType>()) {117return DTST->getTemplateName();118}119return TemplateName();120}121122// Helper function for HeuristicResolver::resolveDependentMember()123// which takes a possibly-dependent type `T` and heuristically124// resolves it to a CXXRecordDecl in which we can try name lookup.125TagDecl *HeuristicResolverImpl::resolveTypeToTagDecl(QualType QT) {126const Type *T = QT.getTypePtrOrNull();127if (!T)128return nullptr;129130// Unwrap type sugar such as type aliases.131T = T->getCanonicalTypeInternal().getTypePtr();132133if (const auto *DNT = T->getAs<DependentNameType>()) {134T = resolveDeclsToType(resolveDependentNameType(DNT), Ctx)135.getTypePtrOrNull();136if (!T)137return nullptr;138T = T->getCanonicalTypeInternal().getTypePtr();139}140141if (auto *TT = T->getAs<TagType>()) {142TagDecl *TD = TT->getDecl();143// Template might not be instantiated yet, fall back to primary template144// in such cases.145if (const auto *CTSD = dyn_cast<ClassTemplateSpecializationDecl>(TD)) {146if (CTSD->getTemplateSpecializationKind() == TSK_Undeclared) {147return CTSD->getSpecializedTemplate()->getTemplatedDecl();148}149}150return TD;151}152153if (const auto *ICNT = T->getAs<InjectedClassNameType>())154T = ICNT->getInjectedSpecializationType().getTypePtrOrNull();155if (!T)156return nullptr;157158TemplateName TN = getReferencedTemplateName(T);159if (TN.isNull())160return nullptr;161162const ClassTemplateDecl *TD =163dyn_cast_or_null<ClassTemplateDecl>(TN.getAsTemplateDecl());164if (!TD)165return nullptr;166167return TD->getTemplatedDecl();168}169170QualType HeuristicResolverImpl::getPointeeType(QualType T) {171if (T.isNull())172return QualType();173174if (T->isPointerType())175return T->castAs<PointerType>()->getPointeeType();176177// Try to handle smart pointer types.178179// Look up operator-> in the primary template. If we find one, it's probably a180// smart pointer type.181auto ArrowOps = resolveDependentMember(182T, Ctx.DeclarationNames.getCXXOperatorName(OO_Arrow), NonStaticFilter);183if (ArrowOps.empty())184return QualType();185186// Getting the return type of the found operator-> method decl isn't useful,187// because we discarded template arguments to perform lookup in the primary188// template scope, so the return type would just have the form U* where U is a189// template parameter type.190// Instead, just handle the common case where the smart pointer type has the191// form of SmartPtr<X, ...>, and assume X is the pointee type.192auto *TST = T->getAs<TemplateSpecializationType>();193if (!TST)194return QualType();195if (TST->template_arguments().size() == 0)196return QualType();197const TemplateArgument &FirstArg = TST->template_arguments()[0];198if (FirstArg.getKind() != TemplateArgument::Type)199return QualType();200return FirstArg.getAsType();201}202203QualType HeuristicResolverImpl::simplifyType(QualType Type, const Expr *E,204bool UnwrapPointer) {205bool DidUnwrapPointer = false;206// A type, together with an optional expression whose type it represents207// which may have additional information about the expression's type208// not stored in the QualType itself.209struct TypeExprPair {210QualType Type;211const Expr *E = nullptr;212};213TypeExprPair Current{Type, E};214auto SimplifyOneStep = [UnwrapPointer, &DidUnwrapPointer,215this](TypeExprPair T) -> TypeExprPair {216if (UnwrapPointer) {217if (QualType Pointee = getPointeeType(T.Type); !Pointee.isNull()) {218DidUnwrapPointer = true;219return {Pointee};220}221}222if (const auto *RT = T.Type->getAs<ReferenceType>()) {223// Does not count as "unwrap pointer".224return {RT->getPointeeType()};225}226if (const auto *BT = T.Type->getAs<BuiltinType>()) {227// If BaseType is the type of a dependent expression, it's just228// represented as BuiltinType::Dependent which gives us no information. We229// can get further by analyzing the dependent expression.230if (T.E && BT->getKind() == BuiltinType::Dependent) {231return {resolveExprToType(T.E), T.E};232}233}234if (const auto *AT = T.Type->getContainedAutoType()) {235// If T contains a dependent `auto` type, deduction will not have236// been performed on it yet. In simple cases (e.g. `auto` variable with237// initializer), get the approximate type that would result from238// deduction.239// FIXME: A more accurate implementation would propagate things like the240// `const` in `const auto`.241if (T.E && AT->isUndeducedAutoType()) {242if (const auto *DRE = dyn_cast<DeclRefExpr>(T.E)) {243if (const auto *VD = dyn_cast<VarDecl>(DRE->getDecl())) {244if (auto *Init = VD->getInit())245return {resolveExprToType(Init), Init};246}247}248}249}250if (const auto *TTPT = dyn_cast_if_present<TemplateTypeParmType>(T.Type)) {251// We can't do much useful with a template parameter (e.g. we cannot look252// up member names inside it). However, if the template parameter has a253// default argument, as a heuristic we can replace T with the default254// argument type.255if (const auto *TTPD = TTPT->getDecl()) {256if (TTPD->hasDefaultArgument()) {257const auto &DefaultArg = TTPD->getDefaultArgument().getArgument();258if (DefaultArg.getKind() == TemplateArgument::Type) {259return {DefaultArg.getAsType()};260}261}262}263}264return T;265};266// As an additional protection against infinite loops, bound the number of267// simplification steps.268size_t StepCount = 0;269const size_t MaxSteps = 64;270while (!Current.Type.isNull() && StepCount++ < MaxSteps) {271TypeExprPair New = SimplifyOneStep(Current);272if (New.Type == Current.Type)273break;274Current = New;275}276if (UnwrapPointer && !DidUnwrapPointer)277return QualType();278return Current.Type;279}280281std::vector<const NamedDecl *> HeuristicResolverImpl::resolveMemberExpr(282const CXXDependentScopeMemberExpr *ME) {283// If the expression has a qualifier, try resolving the member inside the284// qualifier's type.285// Note that we cannot use a NonStaticFilter in either case, for a couple286// of reasons:287// 1. It's valid to access a static member using instance member syntax,288// e.g. `instance.static_member`.289// 2. We can sometimes get a CXXDependentScopeMemberExpr for static290// member syntax too, e.g. if `X::static_member` occurs inside291// an instance method, it's represented as a CXXDependentScopeMemberExpr292// with `this` as the base expression as `X` as the qualifier293// (which could be valid if `X` names a base class after instantiation).294if (NestedNameSpecifier *NNS = ME->getQualifier()) {295if (QualType QualifierType = resolveNestedNameSpecifierToType(NNS);296!QualifierType.isNull()) {297auto Decls =298resolveDependentMember(QualifierType, ME->getMember(), NoFilter);299if (!Decls.empty())300return Decls;301}302303// Do not proceed to try resolving the member in the expression's base type304// without regard to the qualifier, as that could produce incorrect results.305// For example, `void foo() { this->Base::foo(); }` shouldn't resolve to306// foo() itself!307return {};308}309310// Try resolving the member inside the expression's base type.311Expr *Base = ME->isImplicitAccess() ? nullptr : ME->getBase();312QualType BaseType = ME->getBaseType();313BaseType = simplifyType(BaseType, Base, ME->isArrow());314return resolveDependentMember(BaseType, ME->getMember(), NoFilter);315}316317std::vector<const NamedDecl *>318HeuristicResolverImpl::resolveDeclRefExpr(const DependentScopeDeclRefExpr *RE) {319QualType Qualifier = resolveNestedNameSpecifierToType(RE->getQualifier());320Qualifier = simplifyType(Qualifier, nullptr, /*UnwrapPointer=*/false);321return resolveDependentMember(Qualifier, RE->getDeclName(), StaticFilter);322}323324std::vector<const NamedDecl *>325HeuristicResolverImpl::resolveTypeOfCallExpr(const CallExpr *CE) {326QualType CalleeType = resolveExprToType(CE->getCallee());327if (CalleeType.isNull())328return {};329if (const auto *FnTypePtr = CalleeType->getAs<PointerType>())330CalleeType = FnTypePtr->getPointeeType();331if (const FunctionType *FnType = CalleeType->getAs<FunctionType>()) {332if (const auto *D = resolveTypeToTagDecl(FnType->getReturnType())) {333return {D};334}335}336return {};337}338339std::vector<const NamedDecl *>340HeuristicResolverImpl::resolveCalleeOfCallExpr(const CallExpr *CE) {341if (const auto *ND = dyn_cast_or_null<NamedDecl>(CE->getCalleeDecl())) {342return {ND};343}344345return resolveExprToDecls(CE->getCallee());346}347348std::vector<const NamedDecl *> HeuristicResolverImpl::resolveUsingValueDecl(349const UnresolvedUsingValueDecl *UUVD) {350return resolveDependentMember(QualType(UUVD->getQualifier()->getAsType(), 0),351UUVD->getNameInfo().getName(), ValueFilter);352}353354std::vector<const NamedDecl *>355HeuristicResolverImpl::resolveDependentNameType(const DependentNameType *DNT) {356if (auto [_, inserted] = SeenDependentNameTypes.insert(DNT); !inserted)357return {};358return resolveDependentMember(359resolveNestedNameSpecifierToType(DNT->getQualifier()),360DNT->getIdentifier(), TypeFilter);361}362363std::vector<const NamedDecl *>364HeuristicResolverImpl::resolveTemplateSpecializationType(365const DependentTemplateSpecializationType *DTST) {366const DependentTemplateStorage &DTN = DTST->getDependentTemplateName();367return resolveDependentMember(368resolveNestedNameSpecifierToType(DTN.getQualifier()),369DTN.getName().getIdentifier(), TemplateFilter);370}371372std::vector<const NamedDecl *>373HeuristicResolverImpl::resolveExprToDecls(const Expr *E) {374if (const auto *ME = dyn_cast<CXXDependentScopeMemberExpr>(E)) {375return resolveMemberExpr(ME);376}377if (const auto *RE = dyn_cast<DependentScopeDeclRefExpr>(E)) {378return resolveDeclRefExpr(RE);379}380if (const auto *OE = dyn_cast<OverloadExpr>(E)) {381return {OE->decls_begin(), OE->decls_end()};382}383if (const auto *CE = dyn_cast<CallExpr>(E)) {384return resolveTypeOfCallExpr(CE);385}386if (const auto *ME = dyn_cast<MemberExpr>(E))387return {ME->getMemberDecl()};388389return {};390}391392QualType HeuristicResolverImpl::resolveExprToType(const Expr *E) {393std::vector<const NamedDecl *> Decls = resolveExprToDecls(E);394if (!Decls.empty())395return resolveDeclsToType(Decls, Ctx);396397return E->getType();398}399400QualType HeuristicResolverImpl::resolveNestedNameSpecifierToType(401const NestedNameSpecifier *NNS) {402if (!NNS)403return QualType();404405// The purpose of this function is to handle the dependent (Kind ==406// Identifier) case, but we need to recurse on the prefix because407// that may be dependent as well, so for convenience handle408// the TypeSpec cases too.409switch (NNS->getKind()) {410case NestedNameSpecifier::TypeSpec:411return QualType(NNS->getAsType(), 0);412case NestedNameSpecifier::Identifier: {413return resolveDeclsToType(414resolveDependentMember(415resolveNestedNameSpecifierToType(NNS->getPrefix()),416NNS->getAsIdentifier(), TypeFilter),417Ctx);418}419default:420break;421}422return QualType();423}424425bool isOrdinaryMember(const NamedDecl *ND) {426return ND->isInIdentifierNamespace(Decl::IDNS_Ordinary | Decl::IDNS_Tag |427Decl::IDNS_Member);428}429430bool findOrdinaryMember(const CXXRecordDecl *RD, CXXBasePath &Path,431DeclarationName Name) {432Path.Decls = RD->lookup(Name).begin();433for (DeclContext::lookup_iterator I = Path.Decls, E = I.end(); I != E; ++I)434if (isOrdinaryMember(*I))435return true;436437return false;438}439440bool HeuristicResolverImpl::findOrdinaryMemberInDependentClasses(441const CXXBaseSpecifier *Specifier, CXXBasePath &Path,442DeclarationName Name) {443TagDecl *TD = resolveTypeToTagDecl(Specifier->getType());444if (const auto *RD = dyn_cast_if_present<CXXRecordDecl>(TD)) {445return findOrdinaryMember(RD, Path, Name);446}447return false;448}449450std::vector<const NamedDecl *> HeuristicResolverImpl::lookupDependentName(451CXXRecordDecl *RD, DeclarationName Name,452llvm::function_ref<bool(const NamedDecl *ND)> Filter) {453std::vector<const NamedDecl *> Results;454455// Lookup in the class.456bool AnyOrdinaryMembers = false;457for (const NamedDecl *ND : RD->lookup(Name)) {458if (isOrdinaryMember(ND))459AnyOrdinaryMembers = true;460if (Filter(ND))461Results.push_back(ND);462}463if (AnyOrdinaryMembers)464return Results;465466// Perform lookup into our base classes.467CXXBasePaths Paths;468Paths.setOrigin(RD);469if (!RD->lookupInBases(470[&](const CXXBaseSpecifier *Specifier, CXXBasePath &Path) {471return findOrdinaryMemberInDependentClasses(Specifier, Path, Name);472},473Paths, /*LookupInDependent=*/true))474return Results;475for (DeclContext::lookup_iterator I = Paths.front().Decls, E = I.end();476I != E; ++I) {477if (isOrdinaryMember(*I) && Filter(*I))478Results.push_back(*I);479}480return Results;481}482483std::vector<const NamedDecl *> HeuristicResolverImpl::resolveDependentMember(484QualType QT, DeclarationName Name,485llvm::function_ref<bool(const NamedDecl *ND)> Filter) {486TagDecl *TD = resolveTypeToTagDecl(QT);487if (!TD)488return {};489if (auto *ED = dyn_cast<EnumDecl>(TD)) {490auto Result = ED->lookup(Name);491return {Result.begin(), Result.end()};492}493if (auto *RD = dyn_cast<CXXRecordDecl>(TD)) {494if (!RD->hasDefinition())495return {};496RD = RD->getDefinition();497return lookupDependentName(RD, Name, [&](const NamedDecl *ND) {498if (!Filter(ND))499return false;500if (const auto *MD = dyn_cast<CXXMethodDecl>(ND)) {501return !MD->isInstance() ||502MD->getMethodQualifiers().compatiblyIncludes(QT.getQualifiers(),503Ctx);504}505return true;506});507}508return {};509}510511FunctionProtoTypeLoc512HeuristicResolverImpl::getFunctionProtoTypeLoc(const Expr *Fn) {513TypeLoc Target;514const Expr *NakedFn = Fn->IgnoreParenCasts();515if (const auto *T = NakedFn->getType().getTypePtr()->getAs<TypedefType>()) {516Target = T->getDecl()->getTypeSourceInfo()->getTypeLoc();517} else if (const auto *DR = dyn_cast<DeclRefExpr>(NakedFn)) {518const auto *D = DR->getDecl();519if (const auto *const VD = dyn_cast<VarDecl>(D)) {520Target = VD->getTypeSourceInfo()->getTypeLoc();521}522} else if (const auto *ME = dyn_cast<MemberExpr>(NakedFn)) {523const auto *MD = ME->getMemberDecl();524if (const auto *FD = dyn_cast<FieldDecl>(MD)) {525Target = FD->getTypeSourceInfo()->getTypeLoc();526}527}528529if (!Target)530return {};531532// Unwrap types that may be wrapping the function type533while (true) {534if (auto P = Target.getAs<PointerTypeLoc>()) {535Target = P.getPointeeLoc();536continue;537}538if (auto A = Target.getAs<AttributedTypeLoc>()) {539Target = A.getModifiedLoc();540continue;541}542if (auto P = Target.getAs<ParenTypeLoc>()) {543Target = P.getInnerLoc();544continue;545}546break;547}548549if (auto F = Target.getAs<FunctionProtoTypeLoc>()) {550// In some edge cases the AST can contain a "trivial" FunctionProtoTypeLoc551// which has null parameters. Avoid these as they don't contain useful552// information.553if (llvm::all_of(F.getParams(), llvm::identity<ParmVarDecl *>()))554return F;555}556557return {};558}559560} // namespace561562std::vector<const NamedDecl *> HeuristicResolver::resolveMemberExpr(563const CXXDependentScopeMemberExpr *ME) const {564return HeuristicResolverImpl(Ctx).resolveMemberExpr(ME);565}566std::vector<const NamedDecl *> HeuristicResolver::resolveDeclRefExpr(567const DependentScopeDeclRefExpr *RE) const {568return HeuristicResolverImpl(Ctx).resolveDeclRefExpr(RE);569}570std::vector<const NamedDecl *>571HeuristicResolver::resolveTypeOfCallExpr(const CallExpr *CE) const {572return HeuristicResolverImpl(Ctx).resolveTypeOfCallExpr(CE);573}574std::vector<const NamedDecl *>575HeuristicResolver::resolveCalleeOfCallExpr(const CallExpr *CE) const {576return HeuristicResolverImpl(Ctx).resolveCalleeOfCallExpr(CE);577}578std::vector<const NamedDecl *> HeuristicResolver::resolveUsingValueDecl(579const UnresolvedUsingValueDecl *UUVD) const {580return HeuristicResolverImpl(Ctx).resolveUsingValueDecl(UUVD);581}582std::vector<const NamedDecl *> HeuristicResolver::resolveDependentNameType(583const DependentNameType *DNT) const {584return HeuristicResolverImpl(Ctx).resolveDependentNameType(DNT);585}586std::vector<const NamedDecl *>587HeuristicResolver::resolveTemplateSpecializationType(588const DependentTemplateSpecializationType *DTST) const {589return HeuristicResolverImpl(Ctx).resolveTemplateSpecializationType(DTST);590}591QualType HeuristicResolver::resolveNestedNameSpecifierToType(592const NestedNameSpecifier *NNS) const {593return HeuristicResolverImpl(Ctx).resolveNestedNameSpecifierToType(NNS);594}595std::vector<const NamedDecl *> HeuristicResolver::lookupDependentName(596CXXRecordDecl *RD, DeclarationName Name,597llvm::function_ref<bool(const NamedDecl *ND)> Filter) {598return HeuristicResolverImpl(Ctx).lookupDependentName(RD, Name, Filter);599}600const QualType HeuristicResolver::getPointeeType(QualType T) const {601return HeuristicResolverImpl(Ctx).getPointeeType(T);602}603TagDecl *HeuristicResolver::resolveTypeToTagDecl(QualType T) const {604return HeuristicResolverImpl(Ctx).resolveTypeToTagDecl(T);605}606QualType HeuristicResolver::simplifyType(QualType Type, const Expr *E,607bool UnwrapPointer) {608return HeuristicResolverImpl(Ctx).simplifyType(Type, E, UnwrapPointer);609}610611FunctionProtoTypeLoc612HeuristicResolver::getFunctionProtoTypeLoc(const Expr *Fn) const {613return HeuristicResolverImpl(Ctx).getFunctionProtoTypeLoc(Fn);614}615616} // namespace clang617618619