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

source code of clang-tools-extra/clangd/HeuristicResolver.cpp