clang 20.0.0git
HeuristicResolver.cpp
Go to the documentation of this file.
1//===--- HeuristicResolver.cpp ---------------------------*- C++-*-===//
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
13#include "clang/AST/ExprCXX.h"
14#include "clang/AST/Type.h"
15
16namespace clang {
17
18namespace {
19
20// Helper class for implementing HeuristicResolver.
21// Unlike HeuristicResolver which is a long-lived class,
22// a new instance of this class is created for every external
23// call into a HeuristicResolver operation. That allows this
24// class to store state that's local to such a top-level call,
25// particularly "recursion protection sets" that keep track of
26// nodes that have already been seen to avoid infinite recursion.
27class HeuristicResolverImpl {
28public:
29 HeuristicResolverImpl(ASTContext &Ctx) : Ctx(Ctx) {}
30
31 // These functions match the public interface of HeuristicResolver
32 // (but aren't const since they may modify the recursion protection sets).
33 std::vector<const NamedDecl *>
34 resolveMemberExpr(const CXXDependentScopeMemberExpr *ME);
35 std::vector<const NamedDecl *>
36 resolveDeclRefExpr(const DependentScopeDeclRefExpr *RE);
37 std::vector<const NamedDecl *> resolveTypeOfCallExpr(const CallExpr *CE);
38 std::vector<const NamedDecl *> resolveCalleeOfCallExpr(const CallExpr *CE);
39 std::vector<const NamedDecl *>
40 resolveUsingValueDecl(const UnresolvedUsingValueDecl *UUVD);
41 std::vector<const NamedDecl *>
42 resolveDependentNameType(const DependentNameType *DNT);
43 std::vector<const NamedDecl *> resolveTemplateSpecializationType(
44 const DependentTemplateSpecializationType *DTST);
45 QualType resolveNestedNameSpecifierToType(const NestedNameSpecifier *NNS);
46 QualType getPointeeType(QualType T);
47
48private:
49 ASTContext &Ctx;
50
51 // Recursion protection sets
52 llvm::SmallSet<const DependentNameType *, 4> SeenDependentNameTypes;
53
54 // Given a tag-decl type and a member name, heuristically resolve the
55 // name to one or more declarations.
56 // The current heuristic is simply to look up the name in the primary
57 // template. This is a heuristic because the template could potentially
58 // have specializations that declare different members.
59 // Multiple declarations could be returned if the name is overloaded
60 // (e.g. an overloaded method in the primary template).
61 // This heuristic will give the desired answer in many cases, e.g.
62 // for a call to vector<T>::size().
63 std::vector<const NamedDecl *>
64 resolveDependentMember(QualType T, DeclarationName Name,
65 llvm::function_ref<bool(const NamedDecl *ND)> Filter);
66
67 // Try to heuristically resolve the type of a possibly-dependent expression
68 // `E`.
69 QualType resolveExprToType(const Expr *E);
70 std::vector<const NamedDecl *> resolveExprToDecls(const Expr *E);
71
72 // Helper function for HeuristicResolver::resolveDependentMember()
73 // which takes a possibly-dependent type `T` and heuristically
74 // resolves it to a TagDecl in which we can try name lookup.
75 TagDecl *resolveTypeToTagDecl(const Type *T);
76
77 // This is a reimplementation of CXXRecordDecl::lookupDependentName()
78 // so that the implementation can call into other HeuristicResolver helpers.
79 // FIXME: Once HeuristicResolver is upstreamed to the clang libraries
80 // (https://github.com/clangd/clangd/discussions/1662),
81 // CXXRecordDecl::lookupDepenedentName() can be removed, and its call sites
82 // can be modified to benefit from the more comprehensive heuristics offered
83 // by HeuristicResolver instead.
84 std::vector<const NamedDecl *>
85 lookupDependentName(CXXRecordDecl *RD, DeclarationName Name,
86 llvm::function_ref<bool(const NamedDecl *ND)> Filter);
87 bool findOrdinaryMemberInDependentClasses(const CXXBaseSpecifier *Specifier,
88 CXXBasePath &Path,
89 DeclarationName Name);
90};
91
92// Convenience lambdas for use as the 'Filter' parameter of
93// HeuristicResolver::resolveDependentMember().
94const auto NoFilter = [](const NamedDecl *D) { return true; };
95const auto NonStaticFilter = [](const NamedDecl *D) {
96 return D->isCXXInstanceMember();
97};
98const auto StaticFilter = [](const NamedDecl *D) {
99 return !D->isCXXInstanceMember();
100};
101const auto ValueFilter = [](const NamedDecl *D) { return isa<ValueDecl>(D); };
102const auto TypeFilter = [](const NamedDecl *D) { return isa<TypeDecl>(D); };
103const auto TemplateFilter = [](const NamedDecl *D) {
104 return isa<TemplateDecl>(D);
105};
106
107QualType resolveDeclsToType(const std::vector<const NamedDecl *> &Decls,
108 ASTContext &Ctx) {
109 if (Decls.size() != 1) // Names an overload set -- just bail.
110 return QualType();
111 if (const auto *TD = dyn_cast<TypeDecl>(Decls[0])) {
112 return Ctx.getTypeDeclType(TD);
113 }
114 if (const auto *VD = dyn_cast<ValueDecl>(Decls[0])) {
115 return VD->getType();
116 }
117 return QualType();
118}
119
120TemplateName getReferencedTemplateName(const Type *T) {
121 if (const auto *TST = T->getAs<TemplateSpecializationType>()) {
122 return TST->getTemplateName();
123 }
124 if (const auto *DTST = T->getAs<DeducedTemplateSpecializationType>()) {
125 return DTST->getTemplateName();
126 }
127 return TemplateName();
128}
129
130// Helper function for HeuristicResolver::resolveDependentMember()
131// which takes a possibly-dependent type `T` and heuristically
132// resolves it to a CXXRecordDecl in which we can try name lookup.
133TagDecl *HeuristicResolverImpl::resolveTypeToTagDecl(const Type *T) {
134 assert(T);
135
136 // Unwrap type sugar such as type aliases.
138
139 if (const auto *DNT = T->getAs<DependentNameType>()) {
140 T = resolveDeclsToType(resolveDependentNameType(DNT), Ctx)
141 .getTypePtrOrNull();
142 if (!T)
143 return nullptr;
145 }
146
147 if (auto *TT = T->getAs<TagType>()) {
148 return TT->getDecl();
149 }
150
151 if (const auto *ICNT = T->getAs<InjectedClassNameType>())
152 T = ICNT->getInjectedSpecializationType().getTypePtrOrNull();
153 if (!T)
154 return nullptr;
155
156 TemplateName TN = getReferencedTemplateName(T);
157 if (TN.isNull())
158 return nullptr;
159
160 const ClassTemplateDecl *TD =
161 dyn_cast_or_null<ClassTemplateDecl>(TN.getAsTemplateDecl());
162 if (!TD)
163 return nullptr;
164
165 return TD->getTemplatedDecl();
166}
167
168QualType HeuristicResolverImpl::getPointeeType(QualType T) {
169 if (T.isNull())
170 return QualType();
171
172 if (T->isPointerType())
173 return T->castAs<PointerType>()->getPointeeType();
174
175 // Try to handle smart pointer types.
176
177 // Look up operator-> in the primary template. If we find one, it's probably a
178 // smart pointer type.
179 auto ArrowOps = resolveDependentMember(
180 T, Ctx.DeclarationNames.getCXXOperatorName(OO_Arrow), NonStaticFilter);
181 if (ArrowOps.empty())
182 return QualType();
183
184 // Getting the return type of the found operator-> method decl isn't useful,
185 // because we discarded template arguments to perform lookup in the primary
186 // template scope, so the return type would just have the form U* where U is a
187 // template parameter type.
188 // Instead, just handle the common case where the smart pointer type has the
189 // form of SmartPtr<X, ...>, and assume X is the pointee type.
190 auto *TST = T->getAs<TemplateSpecializationType>();
191 if (!TST)
192 return QualType();
193 if (TST->template_arguments().size() == 0)
194 return QualType();
195 const TemplateArgument &FirstArg = TST->template_arguments()[0];
196 if (FirstArg.getKind() != TemplateArgument::Type)
197 return QualType();
198 return FirstArg.getAsType();
199}
200
201std::vector<const NamedDecl *> HeuristicResolverImpl::resolveMemberExpr(
202 const CXXDependentScopeMemberExpr *ME) {
203 // If the expression has a qualifier, try resolving the member inside the
204 // qualifier's type.
205 // Note that we cannot use a NonStaticFilter in either case, for a couple
206 // of reasons:
207 // 1. It's valid to access a static member using instance member syntax,
208 // e.g. `instance.static_member`.
209 // 2. We can sometimes get a CXXDependentScopeMemberExpr for static
210 // member syntax too, e.g. if `X::static_member` occurs inside
211 // an instance method, it's represented as a CXXDependentScopeMemberExpr
212 // with `this` as the base expression as `X` as the qualifier
213 // (which could be valid if `X` names a base class after instantiation).
214 if (NestedNameSpecifier *NNS = ME->getQualifier()) {
215 if (QualType QualifierType = resolveNestedNameSpecifierToType(NNS);
216 !QualifierType.isNull()) {
217 auto Decls =
218 resolveDependentMember(QualifierType, ME->getMember(), NoFilter);
219 if (!Decls.empty())
220 return Decls;
221 }
222
223 // Do not proceed to try resolving the member in the expression's base type
224 // without regard to the qualifier, as that could produce incorrect results.
225 // For example, `void foo() { this->Base::foo(); }` shouldn't resolve to
226 // foo() itself!
227 return {};
228 }
229
230 // Try resolving the member inside the expression's base type.
231 Expr *Base = ME->isImplicitAccess() ? nullptr : ME->getBase();
232 QualType BaseType = ME->getBaseType();
233 if (ME->isArrow()) {
234 BaseType = getPointeeType(BaseType);
235 if (BaseType.isNull())
236 return {};
237 }
238 if (const auto *BT = BaseType->getAs<BuiltinType>()) {
239 // If BaseType is the type of a dependent expression, it's just
240 // represented as BuiltinType::Dependent which gives us no information. We
241 // can get further by analyzing the dependent expression.
242 if (Base && BT->getKind() == BuiltinType::Dependent) {
243 BaseType = resolveExprToType(Base);
244 if (BaseType.isNull())
245 return {};
246 }
247 }
248 if (const auto *AT = BaseType->getContainedAutoType()) {
249 // If BaseType contains a dependent `auto` type, deduction will not have
250 // been performed on it yet. In simple cases (e.g. `auto` variable with
251 // initializer), get the approximate type that would result from deduction.
252 // FIXME: A more accurate implementation would propagate things like the
253 // `const` in `const auto`.
254 if (AT->isUndeducedAutoType()) {
255 if (const auto *DRE = dyn_cast<DeclRefExpr>(Base)) {
256 if (const auto *VD = dyn_cast<VarDecl>(DRE->getDecl())) {
257 if (VD->hasInit())
258 BaseType = resolveExprToType(VD->getInit());
259 }
260 }
261 }
262 }
263 return resolveDependentMember(BaseType, ME->getMember(), NoFilter);
264}
265
266std::vector<const NamedDecl *>
267HeuristicResolverImpl::resolveDeclRefExpr(const DependentScopeDeclRefExpr *RE) {
268 return resolveDependentMember(
269 resolveNestedNameSpecifierToType(RE->getQualifier()), RE->getDeclName(),
270 StaticFilter);
271}
272
273std::vector<const NamedDecl *>
274HeuristicResolverImpl::resolveTypeOfCallExpr(const CallExpr *CE) {
275 QualType CalleeType = resolveExprToType(CE->getCallee());
276 if (CalleeType.isNull())
277 return {};
278 if (const auto *FnTypePtr = CalleeType->getAs<PointerType>())
279 CalleeType = FnTypePtr->getPointeeType();
280 if (const FunctionType *FnType = CalleeType->getAs<FunctionType>()) {
281 if (const auto *D =
282 resolveTypeToTagDecl(FnType->getReturnType().getTypePtr())) {
283 return {D};
284 }
285 }
286 return {};
287}
288
289std::vector<const NamedDecl *>
290HeuristicResolverImpl::resolveCalleeOfCallExpr(const CallExpr *CE) {
291 if (const auto *ND = dyn_cast_or_null<NamedDecl>(CE->getCalleeDecl())) {
292 return {ND};
293 }
294
295 return resolveExprToDecls(CE->getCallee());
296}
297
298std::vector<const NamedDecl *> HeuristicResolverImpl::resolveUsingValueDecl(
299 const UnresolvedUsingValueDecl *UUVD) {
300 return resolveDependentMember(QualType(UUVD->getQualifier()->getAsType(), 0),
301 UUVD->getNameInfo().getName(), ValueFilter);
302}
303
304std::vector<const NamedDecl *>
305HeuristicResolverImpl::resolveDependentNameType(const DependentNameType *DNT) {
306 if (auto [_, inserted] = SeenDependentNameTypes.insert(DNT); !inserted)
307 return {};
308 return resolveDependentMember(
309 resolveNestedNameSpecifierToType(DNT->getQualifier()),
310 DNT->getIdentifier(), TypeFilter);
311}
312
313std::vector<const NamedDecl *>
314HeuristicResolverImpl::resolveTemplateSpecializationType(
315 const DependentTemplateSpecializationType *DTST) {
316 return resolveDependentMember(
317 resolveNestedNameSpecifierToType(DTST->getQualifier()),
318 DTST->getIdentifier(), TemplateFilter);
319}
320
321std::vector<const NamedDecl *>
322HeuristicResolverImpl::resolveExprToDecls(const Expr *E) {
323 if (const auto *ME = dyn_cast<CXXDependentScopeMemberExpr>(E)) {
324 return resolveMemberExpr(ME);
325 }
326 if (const auto *RE = dyn_cast<DependentScopeDeclRefExpr>(E)) {
327 return resolveDeclRefExpr(RE);
328 }
329 if (const auto *OE = dyn_cast<OverloadExpr>(E)) {
330 return {OE->decls_begin(), OE->decls_end()};
331 }
332 if (const auto *CE = dyn_cast<CallExpr>(E)) {
333 return resolveTypeOfCallExpr(CE);
334 }
335 if (const auto *ME = dyn_cast<MemberExpr>(E))
336 return {ME->getMemberDecl()};
337
338 return {};
339}
340
341QualType HeuristicResolverImpl::resolveExprToType(const Expr *E) {
342 std::vector<const NamedDecl *> Decls = resolveExprToDecls(E);
343 if (!Decls.empty())
344 return resolveDeclsToType(Decls, Ctx);
345
346 return E->getType();
347}
348
349QualType HeuristicResolverImpl::resolveNestedNameSpecifierToType(
350 const NestedNameSpecifier *NNS) {
351 if (!NNS)
352 return QualType();
353
354 // The purpose of this function is to handle the dependent (Kind ==
355 // Identifier) case, but we need to recurse on the prefix because
356 // that may be dependent as well, so for convenience handle
357 // the TypeSpec cases too.
358 switch (NNS->getKind()) {
361 return QualType(NNS->getAsType(), 0);
363 return resolveDeclsToType(
364 resolveDependentMember(
365 resolveNestedNameSpecifierToType(NNS->getPrefix()),
366 NNS->getAsIdentifier(), TypeFilter),
367 Ctx);
368 }
369 default:
370 break;
371 }
372 return QualType();
373}
374
375bool isOrdinaryMember(const NamedDecl *ND) {
376 return ND->isInIdentifierNamespace(Decl::IDNS_Ordinary | Decl::IDNS_Tag |
378}
379
380bool findOrdinaryMember(const CXXRecordDecl *RD, CXXBasePath &Path,
381 DeclarationName Name) {
382 Path.Decls = RD->lookup(Name).begin();
383 for (DeclContext::lookup_iterator I = Path.Decls, E = I.end(); I != E; ++I)
384 if (isOrdinaryMember(*I))
385 return true;
386
387 return false;
388}
389
390bool HeuristicResolverImpl::findOrdinaryMemberInDependentClasses(
391 const CXXBaseSpecifier *Specifier, CXXBasePath &Path,
392 DeclarationName Name) {
393 TagDecl *TD = resolveTypeToTagDecl(Specifier->getType().getTypePtr());
394 if (const auto *RD = dyn_cast_if_present<CXXRecordDecl>(TD)) {
395 return findOrdinaryMember(RD, Path, Name);
396 }
397 return false;
398}
399
400std::vector<const NamedDecl *> HeuristicResolverImpl::lookupDependentName(
401 CXXRecordDecl *RD, DeclarationName Name,
402 llvm::function_ref<bool(const NamedDecl *ND)> Filter) {
403 std::vector<const NamedDecl *> Results;
404
405 // Lookup in the class.
406 bool AnyOrdinaryMembers = false;
407 for (const NamedDecl *ND : RD->lookup(Name)) {
408 if (isOrdinaryMember(ND))
409 AnyOrdinaryMembers = true;
410 if (Filter(ND))
411 Results.push_back(ND);
412 }
413 if (AnyOrdinaryMembers)
414 return Results;
415
416 // Perform lookup into our base classes.
417 CXXBasePaths Paths;
418 Paths.setOrigin(RD);
419 if (!RD->lookupInBases(
420 [&](const CXXBaseSpecifier *Specifier, CXXBasePath &Path) {
421 return findOrdinaryMemberInDependentClasses(Specifier, Path, Name);
422 },
423 Paths, /*LookupInDependent=*/true))
424 return Results;
425 for (DeclContext::lookup_iterator I = Paths.front().Decls, E = I.end();
426 I != E; ++I) {
427 if (isOrdinaryMember(*I) && Filter(*I))
428 Results.push_back(*I);
429 }
430 return Results;
431}
432
433std::vector<const NamedDecl *> HeuristicResolverImpl::resolveDependentMember(
434 QualType QT, DeclarationName Name,
435 llvm::function_ref<bool(const NamedDecl *ND)> Filter) {
436 const Type *T = QT.getTypePtrOrNull();
437 if (!T)
438 return {};
439 TagDecl *TD = resolveTypeToTagDecl(T);
440 if (!TD)
441 return {};
442 if (auto *ED = dyn_cast<EnumDecl>(TD)) {
443 auto Result = ED->lookup(Name);
444 return {Result.begin(), Result.end()};
445 }
446 if (auto *RD = dyn_cast<CXXRecordDecl>(TD)) {
447 if (!RD->hasDefinition())
448 return {};
449 RD = RD->getDefinition();
450 return lookupDependentName(RD, Name, [&](const NamedDecl *ND) {
451 if (!Filter(ND))
452 return false;
453 if (const auto *MD = dyn_cast<CXXMethodDecl>(ND)) {
454 return MD->getMethodQualifiers().compatiblyIncludes(QT.getQualifiers(),
455 Ctx);
456 }
457 return true;
458 });
459 }
460 return {};
461}
462} // namespace
463
464std::vector<const NamedDecl *> HeuristicResolver::resolveMemberExpr(
465 const CXXDependentScopeMemberExpr *ME) const {
466 return HeuristicResolverImpl(Ctx).resolveMemberExpr(ME);
467}
468std::vector<const NamedDecl *> HeuristicResolver::resolveDeclRefExpr(
469 const DependentScopeDeclRefExpr *RE) const {
470 return HeuristicResolverImpl(Ctx).resolveDeclRefExpr(RE);
471}
472std::vector<const NamedDecl *>
474 return HeuristicResolverImpl(Ctx).resolveTypeOfCallExpr(CE);
475}
476std::vector<const NamedDecl *>
478 return HeuristicResolverImpl(Ctx).resolveCalleeOfCallExpr(CE);
479}
480std::vector<const NamedDecl *> HeuristicResolver::resolveUsingValueDecl(
481 const UnresolvedUsingValueDecl *UUVD) const {
482 return HeuristicResolverImpl(Ctx).resolveUsingValueDecl(UUVD);
483}
484std::vector<const NamedDecl *> HeuristicResolver::resolveDependentNameType(
485 const DependentNameType *DNT) const {
486 return HeuristicResolverImpl(Ctx).resolveDependentNameType(DNT);
487}
488std::vector<const NamedDecl *>
490 const DependentTemplateSpecializationType *DTST) const {
491 return HeuristicResolverImpl(Ctx).resolveTemplateSpecializationType(DTST);
492}
494 const NestedNameSpecifier *NNS) const {
495 return HeuristicResolverImpl(Ctx).resolveNestedNameSpecifierToType(NNS);
496}
498 return HeuristicResolverImpl(Ctx).getPointeeType(T);
499}
500
501} // namespace clang
Defines the clang::ASTContext interface.
MatchType Type
static bool findOrdinaryMemberInDependentClasses(const CXXBaseSpecifier *Specifier, CXXBasePath &Path, DeclarationName Name)
static bool isOrdinaryMember(const NamedDecl *ND)
static bool findOrdinaryMember(const CXXRecordDecl *RD, CXXBasePath &Path, DeclarationName Name)
const Decl * D
IndirectLocalPath & Path
Expr * E
Defines the C++ template declaration subclasses.
Defines the clang::Expr interface and subclasses for C++ expressions.
static QualType getPointeeType(const MemRegion *R)
C Language Family Type Representation.
const NestedNameSpecifier * Specifier
DeclarationNameTable DeclarationNames
Definition: ASTContext.h:684
QualType getTypeDeclType(const TypeDecl *Decl, const TypeDecl *PrevDecl=nullptr) const
Return the unique reference to the type for the specified type declaration.
Definition: ASTContext.h:1703
Represents a C++ member access expression where the actual member referenced could not be resolved be...
Definition: ExprCXX.h:3683
CallExpr - Represents a function call (C99 6.5.2.2, C++ [expr.call]).
Definition: Expr.h:2874
lookup_result::iterator lookup_iterator
Definition: DeclBase.h:2569
@ IDNS_Ordinary
Ordinary names.
Definition: DeclBase.h:144
@ IDNS_Member
Members, declared with object declarations within tag definitions.
Definition: DeclBase.h:136
@ IDNS_Tag
Tags, declared with 'struct foo;' and referenced with 'struct foo'.
Definition: DeclBase.h:125
DeclarationName getCXXOperatorName(OverloadedOperatorKind Op)
Get the name of the overloadable C++ operator corresponding to Op.
Represents a qualified type name for which the type name is dependent.
Definition: Type.h:7030
A qualified reference to a name whose declaration cannot yet be resolved.
Definition: ExprCXX.h:3323
Represents a template specialization type whose template cannot be resolved, e.g.
Definition: Type.h:7082
QualType getType() const
Definition: Expr.h:142
std::vector< const NamedDecl * > resolveDeclRefExpr(const DependentScopeDeclRefExpr *RE) const
const QualType getPointeeType(QualType T) const
std::vector< const NamedDecl * > resolveMemberExpr(const CXXDependentScopeMemberExpr *ME) const
QualType resolveNestedNameSpecifierToType(const NestedNameSpecifier *NNS) const
std::vector< const NamedDecl * > resolveCalleeOfCallExpr(const CallExpr *CE) const
std::vector< const NamedDecl * > resolveTypeOfCallExpr(const CallExpr *CE) const
std::vector< const NamedDecl * > resolveUsingValueDecl(const UnresolvedUsingValueDecl *UUVD) const
std::vector< const NamedDecl * > resolveTemplateSpecializationType(const DependentTemplateSpecializationType *DTST) const
std::vector< const NamedDecl * > resolveDependentNameType(const DependentNameType *DNT) const
Represents a C++ nested name specifier, such as "\::std::vector<int>::".
@ TypeSpec
A type, stored as a Type*.
@ TypeSpecWithTemplate
A type that was preceded by the 'template' keyword, stored as a Type*.
@ Identifier
An identifier, stored as an IdentifierInfo*.
A (possibly-)qualified type.
Definition: Type.h:929
const Type * getTypePtr() const
Retrieves a pointer to the underlying (unqualified) type.
Definition: Type.h:7937
@ Type
The template argument is a type.
Definition: TemplateBase.h:70
bool isPointerType() const
Definition: Type.h:8192
const T * castAs() const
Member-template castAs<specific type>.
Definition: Type.h:8810
QualType getCanonicalTypeInternal() const
Definition: Type.h:2990
const T * getAs() const
Member-template getAs<specific type>'.
Definition: Type.h:8741
Represents a dependent using declaration which was not marked with typename.
Definition: DeclCXX.h:3924
llvm::cl::opt< std::string > Filter
The JSON file list parser is used to communicate input to InstallAPI.
@ Result
The result type of a method or function.
const FunctionProtoType * T