1//===--- AST.cpp - Utility AST functions -----------------------*- 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 "AST.h"
10
11#include "SourceCode.h"
12#include "clang/AST/ASTContext.h"
13#include "clang/AST/ASTTypeTraits.h"
14#include "clang/AST/Decl.h"
15#include "clang/AST/DeclBase.h"
16#include "clang/AST/DeclCXX.h"
17#include "clang/AST/DeclObjC.h"
18#include "clang/AST/DeclTemplate.h"
19#include "clang/AST/DeclarationName.h"
20#include "clang/AST/ExprCXX.h"
21#include "clang/AST/NestedNameSpecifier.h"
22#include "clang/AST/PrettyPrinter.h"
23#include "clang/AST/RecursiveASTVisitor.h"
24#include "clang/AST/Stmt.h"
25#include "clang/AST/TemplateBase.h"
26#include "clang/AST/TypeLoc.h"
27#include "clang/Basic/Builtins.h"
28#include "clang/Basic/SourceLocation.h"
29#include "clang/Basic/SourceManager.h"
30#include "clang/Basic/Specifiers.h"
31#include "clang/Index/USRGeneration.h"
32#include "llvm/ADT/ArrayRef.h"
33#include "llvm/ADT/STLExtras.h"
34#include "llvm/ADT/SmallSet.h"
35#include "llvm/ADT/StringRef.h"
36#include "llvm/Support/Casting.h"
37#include "llvm/Support/raw_ostream.h"
38#include <iterator>
39#include <optional>
40#include <string>
41#include <vector>
42
43namespace clang {
44namespace clangd {
45
46namespace {
47std::optional<llvm::ArrayRef<TemplateArgumentLoc>>
48getTemplateSpecializationArgLocs(const NamedDecl &ND) {
49 if (auto *Func = llvm::dyn_cast<FunctionDecl>(Val: &ND)) {
50 if (const ASTTemplateArgumentListInfo *Args =
51 Func->getTemplateSpecializationArgsAsWritten())
52 return Args->arguments();
53 } else if (auto *Cls =
54 llvm::dyn_cast<ClassTemplatePartialSpecializationDecl>(Val: &ND)) {
55 if (auto *Args = Cls->getTemplateArgsAsWritten())
56 return Args->arguments();
57 } else if (auto *Var =
58 llvm::dyn_cast<VarTemplatePartialSpecializationDecl>(Val: &ND)) {
59 if (auto *Args = Var->getTemplateArgsAsWritten())
60 return Args->arguments();
61 } else if (auto *Var = llvm::dyn_cast<VarTemplateSpecializationDecl>(Val: &ND)) {
62 if (auto *Args = Var->getTemplateArgsInfo())
63 return Args->arguments();
64 }
65 // We return std::nullopt for ClassTemplateSpecializationDecls because it does
66 // not contain TemplateArgumentLoc information.
67 return std::nullopt;
68}
69
70template <class T>
71bool isTemplateSpecializationKind(const NamedDecl *D,
72 TemplateSpecializationKind Kind) {
73 if (const auto *TD = dyn_cast<T>(D))
74 return TD->getTemplateSpecializationKind() == Kind;
75 return false;
76}
77
78bool isTemplateSpecializationKind(const NamedDecl *D,
79 TemplateSpecializationKind Kind) {
80 return isTemplateSpecializationKind<FunctionDecl>(D, Kind) ||
81 isTemplateSpecializationKind<CXXRecordDecl>(D, Kind) ||
82 isTemplateSpecializationKind<VarDecl>(D, Kind);
83}
84
85// Store all UsingDirectiveDecls in parent contexts of DestContext, that were
86// introduced before InsertionPoint.
87llvm::DenseSet<const NamespaceDecl *>
88getUsingNamespaceDirectives(const DeclContext *DestContext,
89 SourceLocation Until) {
90 const auto &SM = DestContext->getParentASTContext().getSourceManager();
91 llvm::DenseSet<const NamespaceDecl *> VisibleNamespaceDecls;
92 for (const auto *DC = DestContext; DC; DC = DC->getLookupParent()) {
93 for (const auto *D : DC->decls()) {
94 if (!SM.isWrittenInSameFile(Loc1: D->getLocation(), Loc2: Until) ||
95 !SM.isBeforeInTranslationUnit(LHS: D->getLocation(), RHS: Until))
96 continue;
97 if (auto *UDD = llvm::dyn_cast<UsingDirectiveDecl>(Val: D))
98 VisibleNamespaceDecls.insert(
99 V: UDD->getNominatedNamespace()->getCanonicalDecl());
100 }
101 }
102 return VisibleNamespaceDecls;
103}
104
105// Goes over all parents of SourceContext until we find a common ancestor for
106// DestContext and SourceContext. Any qualifier including and above common
107// ancestor is redundant, therefore we stop at lowest common ancestor.
108// In addition to that stops early whenever IsVisible returns true. This can be
109// used to implement support for "using namespace" decls.
110std::string
111getQualification(ASTContext &Context, const DeclContext *DestContext,
112 const DeclContext *SourceContext,
113 llvm::function_ref<bool(NestedNameSpecifier *)> IsVisible) {
114 std::vector<const NestedNameSpecifier *> Parents;
115 bool ReachedNS = false;
116 for (const DeclContext *CurContext = SourceContext; CurContext;
117 CurContext = CurContext->getLookupParent()) {
118 // Stop once we reach a common ancestor.
119 if (CurContext->Encloses(DC: DestContext))
120 break;
121
122 NestedNameSpecifier *NNS = nullptr;
123 if (auto *TD = llvm::dyn_cast<TagDecl>(Val: CurContext)) {
124 // There can't be any more tag parents after hitting a namespace.
125 assert(!ReachedNS);
126 (void)ReachedNS;
127 NNS = NestedNameSpecifier::Create(Context, nullptr, false,
128 TD->getTypeForDecl());
129 } else if (auto *NSD = llvm::dyn_cast<NamespaceDecl>(Val: CurContext)) {
130 ReachedNS = true;
131 NNS = NestedNameSpecifier::Create(Context, Prefix: nullptr, NS: NSD);
132 // Anonymous and inline namespace names are not spelled while qualifying
133 // a name, so skip those.
134 if (NSD->isAnonymousNamespace() || NSD->isInlineNamespace())
135 continue;
136 } else {
137 // Other types of contexts cannot be spelled in code, just skip over
138 // them.
139 continue;
140 }
141 // Stop if this namespace is already visible at DestContext.
142 if (IsVisible(NNS))
143 break;
144
145 Parents.push_back(x: NNS);
146 }
147
148 // Go over name-specifiers in reverse order to create necessary qualification,
149 // since we stored inner-most parent first.
150 std::string Result;
151 llvm::raw_string_ostream OS(Result);
152 for (const auto *Parent : llvm::reverse(C&: Parents))
153 Parent->print(OS, Policy: Context.getPrintingPolicy());
154 return OS.str();
155}
156
157} // namespace
158
159bool isImplicitTemplateInstantiation(const NamedDecl *D) {
160 return isTemplateSpecializationKind(D, Kind: TSK_ImplicitInstantiation);
161}
162
163bool isExplicitTemplateSpecialization(const NamedDecl *D) {
164 return isTemplateSpecializationKind(D, Kind: TSK_ExplicitSpecialization);
165}
166
167bool isImplementationDetail(const Decl *D) {
168 return !isSpelledInSource(Loc: D->getLocation(),
169 SM: D->getASTContext().getSourceManager());
170}
171
172SourceLocation nameLocation(const clang::Decl &D, const SourceManager &SM) {
173 auto L = D.getLocation();
174 // For `- (void)foo` we want `foo` not the `-`.
175 if (const auto *MD = dyn_cast<ObjCMethodDecl>(Val: &D))
176 L = MD->getSelectorStartLoc();
177 if (isSpelledInSource(Loc: L, SM))
178 return SM.getSpellingLoc(Loc: L);
179 return SM.getExpansionLoc(Loc: L);
180}
181
182std::string printQualifiedName(const NamedDecl &ND) {
183 std::string QName;
184 llvm::raw_string_ostream OS(QName);
185 PrintingPolicy Policy(ND.getASTContext().getLangOpts());
186 // Note that inline namespaces are treated as transparent scopes. This
187 // reflects the way they're most commonly used for lookup. Ideally we'd
188 // include them, but at query time it's hard to find all the inline
189 // namespaces to query: the preamble doesn't have a dedicated list.
190 Policy.SuppressUnwrittenScope = true;
191 // (unnamed struct), not (unnamed struct at /path/to/foo.cc:42:1).
192 // In clangd, context is usually available and paths are mostly noise.
193 Policy.AnonymousTagLocations = false;
194 ND.printQualifiedName(OS, Policy);
195 OS.flush();
196 assert(!StringRef(QName).starts_with("::"));
197 return QName;
198}
199
200static bool isAnonymous(const DeclarationName &N) {
201 return N.isIdentifier() && !N.getAsIdentifierInfo();
202}
203
204NestedNameSpecifierLoc getQualifierLoc(const NamedDecl &ND) {
205 if (auto *V = llvm::dyn_cast<DeclaratorDecl>(Val: &ND))
206 return V->getQualifierLoc();
207 if (auto *T = llvm::dyn_cast<TagDecl>(Val: &ND))
208 return T->getQualifierLoc();
209 return NestedNameSpecifierLoc();
210}
211
212std::string printUsingNamespaceName(const ASTContext &Ctx,
213 const UsingDirectiveDecl &D) {
214 PrintingPolicy PP(Ctx.getLangOpts());
215 std::string Name;
216 llvm::raw_string_ostream Out(Name);
217
218 if (auto *Qual = D.getQualifier())
219 Qual->print(OS&: Out, Policy: PP);
220 D.getNominatedNamespaceAsWritten()->printName(OS&: Out);
221 return Out.str();
222}
223
224std::string printName(const ASTContext &Ctx, const NamedDecl &ND) {
225 std::string Name;
226 llvm::raw_string_ostream Out(Name);
227 PrintingPolicy PP(Ctx.getLangOpts());
228 // We don't consider a class template's args part of the constructor name.
229 PP.SuppressTemplateArgsInCXXConstructors = true;
230
231 // Handle 'using namespace'. They all have the same name - <using-directive>.
232 if (auto *UD = llvm::dyn_cast<UsingDirectiveDecl>(Val: &ND)) {
233 Out << "using namespace ";
234 if (auto *Qual = UD->getQualifier())
235 Qual->print(OS&: Out, Policy: PP);
236 UD->getNominatedNamespaceAsWritten()->printName(OS&: Out);
237 return Out.str();
238 }
239
240 if (isAnonymous(N: ND.getDeclName())) {
241 // Come up with a presentation for an anonymous entity.
242 if (isa<NamespaceDecl>(Val: ND))
243 return "(anonymous namespace)";
244 if (auto *Cls = llvm::dyn_cast<RecordDecl>(Val: &ND)) {
245 if (Cls->isLambda())
246 return "(lambda)";
247 return ("(anonymous " + Cls->getKindName() + ")").str();
248 }
249 if (isa<EnumDecl>(Val: ND))
250 return "(anonymous enum)";
251 return "(anonymous)";
252 }
253
254 // Print nested name qualifier if it was written in the source code.
255 if (auto *Qualifier = getQualifierLoc(ND).getNestedNameSpecifier())
256 Qualifier->print(OS&: Out, Policy: PP);
257 // Print the name itself.
258 ND.getDeclName().print(OS&: Out, Policy: PP);
259 // Print template arguments.
260 Out << printTemplateSpecializationArgs(ND);
261
262 return Out.str();
263}
264
265std::string printTemplateSpecializationArgs(const NamedDecl &ND) {
266 std::string TemplateArgs;
267 llvm::raw_string_ostream OS(TemplateArgs);
268 PrintingPolicy Policy(ND.getASTContext().getLangOpts());
269 if (std::optional<llvm::ArrayRef<TemplateArgumentLoc>> Args =
270 getTemplateSpecializationArgLocs(ND)) {
271 printTemplateArgumentList(OS, Args: *Args, Policy);
272 } else if (auto *Cls = llvm::dyn_cast<ClassTemplateSpecializationDecl>(Val: &ND)) {
273 if (const TypeSourceInfo *TSI = Cls->getTypeAsWritten()) {
274 // ClassTemplateSpecializationDecls do not contain
275 // TemplateArgumentTypeLocs, they only have TemplateArgumentTypes. So we
276 // create a new argument location list from TypeSourceInfo.
277 auto STL = TSI->getTypeLoc().getAs<TemplateSpecializationTypeLoc>();
278 llvm::SmallVector<TemplateArgumentLoc> ArgLocs;
279 ArgLocs.reserve(N: STL.getNumArgs());
280 for (unsigned I = 0; I < STL.getNumArgs(); ++I)
281 ArgLocs.push_back(Elt: STL.getArgLoc(i: I));
282 printTemplateArgumentList(OS, Args: ArgLocs, Policy);
283 } else {
284 // FIXME: Fix cases when getTypeAsWritten returns null inside clang AST,
285 // e.g. friend decls. Currently we fallback to Template Arguments without
286 // location information.
287 printTemplateArgumentList(OS, Args: Cls->getTemplateArgs().asArray(), Policy);
288 }
289 }
290 OS.flush();
291 return TemplateArgs;
292}
293
294std::string printNamespaceScope(const DeclContext &DC) {
295 for (const auto *Ctx = &DC; Ctx != nullptr; Ctx = Ctx->getParent())
296 if (const auto *NS = dyn_cast<NamespaceDecl>(Val: Ctx))
297 if (!NS->isAnonymousNamespace() && !NS->isInlineNamespace())
298 return printQualifiedName(*NS) + "::";
299 return "";
300}
301
302static llvm::StringRef
303getNameOrErrForObjCInterface(const ObjCInterfaceDecl *ID) {
304 return ID ? ID->getName() : "<<error-type>>";
305}
306
307std::string printObjCMethod(const ObjCMethodDecl &Method) {
308 std::string Name;
309 llvm::raw_string_ostream OS(Name);
310
311 OS << (Method.isInstanceMethod() ? '-' : '+') << '[';
312
313 // Should always be true.
314 if (const ObjCContainerDecl *C =
315 dyn_cast<ObjCContainerDecl>(Method.getDeclContext()))
316 OS << printObjCContainer(C: *C);
317
318 Method.getSelector().print(OS&: OS << ' ');
319 if (Method.isVariadic())
320 OS << ", ...";
321
322 OS << ']';
323 OS.flush();
324 return Name;
325}
326
327std::string printObjCContainer(const ObjCContainerDecl &C) {
328 if (const ObjCCategoryDecl *Category = dyn_cast<ObjCCategoryDecl>(Val: &C)) {
329 std::string Name;
330 llvm::raw_string_ostream OS(Name);
331 const ObjCInterfaceDecl *Class = Category->getClassInterface();
332 OS << getNameOrErrForObjCInterface(ID: Class) << '(' << Category->getName()
333 << ')';
334 OS.flush();
335 return Name;
336 }
337 if (const ObjCCategoryImplDecl *CID = dyn_cast<ObjCCategoryImplDecl>(Val: &C)) {
338 std::string Name;
339 llvm::raw_string_ostream OS(Name);
340 const ObjCInterfaceDecl *Class = CID->getClassInterface();
341 OS << getNameOrErrForObjCInterface(ID: Class) << '(' << CID->getName() << ')';
342 OS.flush();
343 return Name;
344 }
345 return C.getNameAsString();
346}
347
348SymbolID getSymbolID(const Decl *D) {
349 llvm::SmallString<128> USR;
350 if (index::generateUSRForDecl(D, Buf&: USR))
351 return {};
352 return SymbolID(USR);
353}
354
355SymbolID getSymbolID(const llvm::StringRef MacroName, const MacroInfo *MI,
356 const SourceManager &SM) {
357 if (MI == nullptr)
358 return {};
359 llvm::SmallString<128> USR;
360 if (index::generateUSRForMacro(MacroName, Loc: MI->getDefinitionLoc(), SM, Buf&: USR))
361 return {};
362 return SymbolID(USR);
363}
364
365const ObjCImplDecl *getCorrespondingObjCImpl(const ObjCContainerDecl *D) {
366 if (const auto *ID = dyn_cast<ObjCInterfaceDecl>(Val: D))
367 return ID->getImplementation();
368 if (const auto *CD = dyn_cast<ObjCCategoryDecl>(Val: D)) {
369 if (CD->IsClassExtension()) {
370 if (const auto *ID = CD->getClassInterface())
371 return ID->getImplementation();
372 return nullptr;
373 }
374 return CD->getImplementation();
375 }
376 return nullptr;
377}
378
379Symbol::IncludeDirective
380preferredIncludeDirective(llvm::StringRef FileName, const LangOptions &LangOpts,
381 ArrayRef<Inclusion> MainFileIncludes,
382 ArrayRef<const Decl *> TopLevelDecls) {
383 // Always prefer #include for non-ObjC code.
384 if (!LangOpts.ObjC)
385 return Symbol::IncludeDirective::Include;
386 // If this is not a header file and has ObjC set as the language, prefer
387 // #import.
388 if (!isHeaderFile(FileName, LangOpts))
389 return Symbol::IncludeDirective::Import;
390
391 // Headers lack proper compile flags most of the time, so we might treat a
392 // header as ObjC accidentally. Perform some extra checks to make sure this
393 // works.
394
395 // Any file with a #import, should keep #import-ing.
396 for (auto &Inc : MainFileIncludes)
397 if (Inc.Directive == tok::pp_import)
398 return Symbol::IncludeDirective::Import;
399
400 // Any file declaring an ObjC decl should also be #import-ing.
401 // No need to look over the references, as the file doesn't have any #imports,
402 // it must be declaring interesting ObjC-like decls.
403 for (const Decl *D : TopLevelDecls)
404 if (isa<ObjCContainerDecl, ObjCIvarDecl, ObjCMethodDecl, ObjCPropertyDecl>(
405 Val: D))
406 return Symbol::IncludeDirective::Import;
407
408 return Symbol::IncludeDirective::Include;
409}
410
411std::string printType(const QualType QT, const DeclContext &CurContext,
412 const llvm::StringRef Placeholder) {
413 std::string Result;
414 llvm::raw_string_ostream OS(Result);
415 PrintingPolicy PP(CurContext.getParentASTContext().getPrintingPolicy());
416 PP.SuppressTagKeyword = true;
417 PP.SuppressUnwrittenScope = true;
418
419 class PrintCB : public PrintingCallbacks {
420 public:
421 PrintCB(const DeclContext *CurContext) : CurContext(CurContext) {}
422 virtual ~PrintCB() {}
423 bool isScopeVisible(const DeclContext *DC) const override {
424 return DC->Encloses(DC: CurContext);
425 }
426
427 private:
428 const DeclContext *CurContext;
429 };
430 PrintCB PCB(&CurContext);
431 PP.Callbacks = &PCB;
432
433 QT.print(OS, Policy: PP, PlaceHolder: Placeholder);
434 return OS.str();
435}
436
437bool hasReservedName(const Decl &D) {
438 if (const auto *ND = llvm::dyn_cast<NamedDecl>(Val: &D))
439 if (const auto *II = ND->getIdentifier())
440 return isReservedName(Name: II->getName());
441 return false;
442}
443
444bool hasReservedScope(const DeclContext &DC) {
445 for (const DeclContext *D = &DC; D; D = D->getParent()) {
446 if (D->isTransparentContext() || D->isInlineNamespace())
447 continue;
448 if (const auto *ND = llvm::dyn_cast<NamedDecl>(Val: D))
449 if (hasReservedName(*ND))
450 return true;
451 }
452 return false;
453}
454
455QualType declaredType(const TypeDecl *D) {
456 if (const auto *CTSD = llvm::dyn_cast<ClassTemplateSpecializationDecl>(Val: D))
457 if (const auto *TSI = CTSD->getTypeAsWritten())
458 return TSI->getType();
459 return D->getASTContext().getTypeDeclType(D);
460}
461
462namespace {
463/// Computes the deduced type at a given location by visiting the relevant
464/// nodes. We use this to display the actual type when hovering over an "auto"
465/// keyword or "decltype()" expression.
466/// FIXME: This could have been a lot simpler by visiting AutoTypeLocs but it
467/// seems that the AutoTypeLocs that can be visited along with their AutoType do
468/// not have the deduced type set. Instead, we have to go to the appropriate
469/// DeclaratorDecl/FunctionDecl and work our back to the AutoType that does have
470/// a deduced type set. The AST should be improved to simplify this scenario.
471class DeducedTypeVisitor : public RecursiveASTVisitor<DeducedTypeVisitor> {
472 SourceLocation SearchedLocation;
473
474public:
475 DeducedTypeVisitor(SourceLocation SearchedLocation)
476 : SearchedLocation(SearchedLocation) {}
477
478 // Handle auto initializers:
479 //- auto i = 1;
480 //- decltype(auto) i = 1;
481 //- auto& i = 1;
482 //- auto* i = &a;
483 bool VisitDeclaratorDecl(DeclaratorDecl *D) {
484 if (!D->getTypeSourceInfo() ||
485 !D->getTypeSourceInfo()->getTypeLoc().getContainedAutoTypeLoc() ||
486 D->getTypeSourceInfo()
487 ->getTypeLoc()
488 .getContainedAutoTypeLoc()
489 .getNameLoc() != SearchedLocation)
490 return true;
491
492 if (auto *AT = D->getType()->getContainedAutoType()) {
493 DeducedType = AT->desugar();
494 }
495 return true;
496 }
497
498 // Handle auto return types:
499 //- auto foo() {}
500 //- auto& foo() {}
501 //- auto foo() -> int {}
502 //- auto foo() -> decltype(1+1) {}
503 //- operator auto() const { return 10; }
504 bool VisitFunctionDecl(FunctionDecl *D) {
505 if (!D->getTypeSourceInfo())
506 return true;
507 // Loc of auto in return type (c++14).
508 auto CurLoc = D->getReturnTypeSourceRange().getBegin();
509 // Loc of "auto" in operator auto()
510 if (CurLoc.isInvalid() && isa<CXXConversionDecl>(Val: D))
511 CurLoc = D->getTypeSourceInfo()->getTypeLoc().getBeginLoc();
512 // Loc of "auto" in function with trailing return type (c++11).
513 if (CurLoc.isInvalid())
514 CurLoc = D->getSourceRange().getBegin();
515 if (CurLoc != SearchedLocation)
516 return true;
517
518 const AutoType *AT = D->getReturnType()->getContainedAutoType();
519 if (AT && !AT->getDeducedType().isNull()) {
520 DeducedType = AT->getDeducedType();
521 } else if (auto *DT = dyn_cast<DecltypeType>(Val: D->getReturnType())) {
522 // auto in a trailing return type just points to a DecltypeType and
523 // getContainedAutoType does not unwrap it.
524 if (!DT->getUnderlyingType().isNull())
525 DeducedType = DT->getUnderlyingType();
526 } else if (!D->getReturnType().isNull()) {
527 DeducedType = D->getReturnType();
528 }
529 return true;
530 }
531
532 // Handle non-auto decltype, e.g.:
533 // - auto foo() -> decltype(expr) {}
534 // - decltype(expr);
535 bool VisitDecltypeTypeLoc(DecltypeTypeLoc TL) {
536 if (TL.getBeginLoc() != SearchedLocation)
537 return true;
538
539 // A DecltypeType's underlying type can be another DecltypeType! E.g.
540 // int I = 0;
541 // decltype(I) J = I;
542 // decltype(J) K = J;
543 const DecltypeType *DT = dyn_cast<DecltypeType>(TL.getTypePtr());
544 while (DT && !DT->getUnderlyingType().isNull()) {
545 DeducedType = DT->getUnderlyingType();
546 DT = dyn_cast<DecltypeType>(DeducedType.getTypePtr());
547 }
548 return true;
549 }
550
551 // Handle functions/lambdas with `auto` typed parameters.
552 // We deduce the type if there's exactly one instantiation visible.
553 bool VisitParmVarDecl(ParmVarDecl *PVD) {
554 if (!PVD->getType()->isDependentType())
555 return true;
556 // 'auto' here does not name an AutoType, but an implicit template param.
557 TemplateTypeParmTypeLoc Auto =
558 getContainedAutoParamType(PVD->getTypeSourceInfo()->getTypeLoc());
559 if (Auto.isNull() || Auto.getNameLoc() != SearchedLocation)
560 return true;
561
562 // We expect the TTP to be attached to this function template.
563 // Find the template and the param index.
564 auto *Templated = llvm::dyn_cast<FunctionDecl>(PVD->getDeclContext());
565 if (!Templated)
566 return true;
567 auto *FTD = Templated->getDescribedFunctionTemplate();
568 if (!FTD)
569 return true;
570 int ParamIndex = paramIndex(TD: *FTD, Param&: *Auto.getDecl());
571 if (ParamIndex < 0) {
572 assert(false && "auto TTP is not from enclosing function?");
573 return true;
574 }
575
576 // Now find the instantiation and the deduced template type arg.
577 auto *Instantiation =
578 llvm::dyn_cast_or_null<FunctionDecl>(getOnlyInstantiation(Templated));
579 if (!Instantiation)
580 return true;
581 const auto *Args = Instantiation->getTemplateSpecializationArgs();
582 if (Args->size() != FTD->getTemplateParameters()->size())
583 return true; // no weird variadic stuff
584 DeducedType = Args->get(ParamIndex).getAsType();
585 return true;
586 }
587
588 static int paramIndex(const TemplateDecl &TD, NamedDecl &Param) {
589 unsigned I = 0;
590 for (auto *ND : *TD.getTemplateParameters()) {
591 if (&Param == ND)
592 return I;
593 ++I;
594 }
595 return -1;
596 }
597
598 QualType DeducedType;
599};
600} // namespace
601
602std::optional<QualType> getDeducedType(ASTContext &ASTCtx, SourceLocation Loc) {
603 if (!Loc.isValid())
604 return {};
605 DeducedTypeVisitor V(Loc);
606 V.TraverseAST(ASTCtx);
607 if (V.DeducedType.isNull())
608 return std::nullopt;
609 return V.DeducedType;
610}
611
612TemplateTypeParmTypeLoc getContainedAutoParamType(TypeLoc TL) {
613 if (auto QTL = TL.getAs<QualifiedTypeLoc>())
614 return getContainedAutoParamType(TL: QTL.getUnqualifiedLoc());
615 if (llvm::isa<PointerType, ReferenceType, ParenType>(Val: TL.getTypePtr()))
616 return getContainedAutoParamType(TL: TL.getNextTypeLoc());
617 if (auto FTL = TL.getAs<FunctionTypeLoc>())
618 return getContainedAutoParamType(TL: FTL.getReturnLoc());
619 if (auto TTPTL = TL.getAs<TemplateTypeParmTypeLoc>()) {
620 if (TTPTL.getTypePtr()->getDecl()->isImplicit())
621 return TTPTL;
622 }
623 return {};
624}
625
626template <typename TemplateDeclTy>
627static NamedDecl *getOnlyInstantiationImpl(TemplateDeclTy *TD) {
628 NamedDecl *Only = nullptr;
629 for (auto *Spec : TD->specializations()) {
630 if (Spec->getTemplateSpecializationKind() == TSK_ExplicitSpecialization)
631 continue;
632 if (Only != nullptr)
633 return nullptr;
634 Only = Spec;
635 }
636 return Only;
637}
638
639NamedDecl *getOnlyInstantiation(NamedDecl *TemplatedDecl) {
640 if (TemplateDecl *TD = TemplatedDecl->getDescribedTemplate()) {
641 if (auto *CTD = llvm::dyn_cast<ClassTemplateDecl>(TD))
642 return getOnlyInstantiationImpl(CTD);
643 if (auto *FTD = llvm::dyn_cast<FunctionTemplateDecl>(TD))
644 return getOnlyInstantiationImpl(FTD);
645 if (auto *VTD = llvm::dyn_cast<VarTemplateDecl>(TD))
646 return getOnlyInstantiationImpl(VTD);
647 }
648 return nullptr;
649}
650
651std::vector<const Attr *> getAttributes(const DynTypedNode &N) {
652 std::vector<const Attr *> Result;
653 if (const auto *TL = N.get<TypeLoc>()) {
654 for (AttributedTypeLoc ATL = TL->getAs<AttributedTypeLoc>(); !ATL.isNull();
655 ATL = ATL.getModifiedLoc().getAs<AttributedTypeLoc>()) {
656 if (const Attr *A = ATL.getAttr())
657 Result.push_back(x: A);
658 assert(!ATL.getModifiedLoc().isNull());
659 }
660 }
661 if (const auto *S = N.get<AttributedStmt>()) {
662 for (; S != nullptr; S = dyn_cast<AttributedStmt>(Val: S->getSubStmt()))
663 for (const Attr *A : S->getAttrs())
664 if (A)
665 Result.push_back(x: A);
666 }
667 if (const auto *D = N.get<Decl>()) {
668 for (const Attr *A : D->attrs())
669 if (A)
670 Result.push_back(A);
671 }
672 return Result;
673}
674
675std::string getQualification(ASTContext &Context,
676 const DeclContext *DestContext,
677 SourceLocation InsertionPoint,
678 const NamedDecl *ND) {
679 auto VisibleNamespaceDecls =
680 getUsingNamespaceDirectives(DestContext, Until: InsertionPoint);
681 return getQualification(
682 Context, DestContext, ND->getDeclContext(),
683 [&](NestedNameSpecifier *NNS) {
684 if (NNS->getKind() != NestedNameSpecifier::Namespace)
685 return false;
686 const auto *CanonNSD = NNS->getAsNamespace()->getCanonicalDecl();
687 return llvm::any_of(Range&: VisibleNamespaceDecls,
688 P: [CanonNSD](const NamespaceDecl *NSD) {
689 return NSD->getCanonicalDecl() == CanonNSD;
690 });
691 });
692}
693
694std::string getQualification(ASTContext &Context,
695 const DeclContext *DestContext,
696 const NamedDecl *ND,
697 llvm::ArrayRef<std::string> VisibleNamespaces) {
698 for (llvm::StringRef NS : VisibleNamespaces) {
699 assert(NS.ends_with("::"));
700 (void)NS;
701 }
702 return getQualification(
703 Context, DestContext, ND->getDeclContext(),
704 [&](NestedNameSpecifier *NNS) {
705 return llvm::any_of(Range&: VisibleNamespaces, P: [&](llvm::StringRef Namespace) {
706 std::string NS;
707 llvm::raw_string_ostream OS(NS);
708 NNS->print(OS, Policy: Context.getPrintingPolicy());
709 return OS.str() == Namespace;
710 });
711 });
712}
713
714bool hasUnstableLinkage(const Decl *D) {
715 // Linkage of a ValueDecl depends on the type.
716 // If that's not deduced yet, deducing it may change the linkage.
717 auto *VD = llvm::dyn_cast_or_null<ValueDecl>(Val: D);
718 return VD && !VD->getType().isNull() && VD->getType()->isUndeducedType();
719}
720
721bool isDeeplyNested(const Decl *D, unsigned MaxDepth) {
722 size_t ContextDepth = 0;
723 for (auto *Ctx = D->getDeclContext(); Ctx && !Ctx->isTranslationUnit();
724 Ctx = Ctx->getParent()) {
725 if (++ContextDepth == MaxDepth)
726 return true;
727 }
728 return false;
729}
730
731namespace {
732
733// returns true for `X` in `template <typename... X> void foo()`
734bool isTemplateTypeParameterPack(NamedDecl *D) {
735 if (const auto *TTPD = dyn_cast<TemplateTypeParmDecl>(Val: D)) {
736 return TTPD->isParameterPack();
737 }
738 return false;
739}
740
741// Returns the template parameter pack type from an instantiated function
742// template, if it exists, nullptr otherwise.
743const TemplateTypeParmType *getFunctionPackType(const FunctionDecl *Callee) {
744 if (const auto *TemplateDecl = Callee->getPrimaryTemplate()) {
745 auto TemplateParams = TemplateDecl->getTemplateParameters()->asArray();
746 // find the template parameter pack from the back
747 const auto It = std::find_if(TemplateParams.rbegin(), TemplateParams.rend(),
748 isTemplateTypeParameterPack);
749 if (It != TemplateParams.rend()) {
750 const auto *TTPD = dyn_cast<TemplateTypeParmDecl>(*It);
751 return TTPD->getTypeForDecl()->castAs<TemplateTypeParmType>();
752 }
753 }
754 return nullptr;
755}
756
757// Returns the template parameter pack type that this parameter was expanded
758// from (if in the Args... or Args&... or Args&&... form), if this is the case,
759// nullptr otherwise.
760const TemplateTypeParmType *getUnderlyingPackType(const ParmVarDecl *Param) {
761 const auto *PlainType = Param->getType().getTypePtr();
762 if (auto *RT = dyn_cast<ReferenceType>(PlainType))
763 PlainType = RT->getPointeeTypeAsWritten().getTypePtr();
764 if (const auto *SubstType = dyn_cast<SubstTemplateTypeParmType>(PlainType)) {
765 const auto *ReplacedParameter = SubstType->getReplacedParameter();
766 if (ReplacedParameter->isParameterPack()) {
767 return ReplacedParameter->getTypeForDecl()
768 ->castAs<TemplateTypeParmType>();
769 }
770 }
771 return nullptr;
772}
773
774// This visitor walks over the body of an instantiated function template.
775// The template accepts a parameter pack and the visitor records whether
776// the pack parameters were forwarded to another call. For example, given:
777//
778// template <typename T, typename... Args>
779// auto make_unique(Args... args) {
780// return unique_ptr<T>(new T(args...));
781// }
782//
783// When called as `make_unique<std::string>(2, 'x')` this yields a function
784// `make_unique<std::string, int, char>` with two parameters.
785// The visitor records that those two parameters are forwarded to the
786// `constructor std::string(int, char);`.
787//
788// This information is recorded in the `ForwardingInfo` split into fully
789// resolved parameters (passed as argument to a parameter that is not an
790// expanded template type parameter pack) and forwarding parameters (passed to a
791// parameter that is an expanded template type parameter pack).
792class ForwardingCallVisitor
793 : public RecursiveASTVisitor<ForwardingCallVisitor> {
794public:
795 ForwardingCallVisitor(ArrayRef<const ParmVarDecl *> Parameters)
796 : Parameters{Parameters},
797 PackType{getUnderlyingPackType(Param: Parameters.front())} {}
798
799 bool VisitCallExpr(CallExpr *E) {
800 auto *Callee = getCalleeDeclOrUniqueOverload(E);
801 if (Callee) {
802 handleCall(Callee, Args: E->arguments());
803 }
804 return !Info.has_value();
805 }
806
807 bool VisitCXXConstructExpr(CXXConstructExpr *E) {
808 auto *Callee = E->getConstructor();
809 if (Callee) {
810 handleCall(Callee, Args: E->arguments());
811 }
812 return !Info.has_value();
813 }
814
815 // The expanded parameter pack to be resolved
816 ArrayRef<const ParmVarDecl *> Parameters;
817 // The type of the parameter pack
818 const TemplateTypeParmType *PackType;
819
820 struct ForwardingInfo {
821 // If the parameters were resolved to another FunctionDecl, these are its
822 // first non-variadic parameters (i.e. the first entries of the parameter
823 // pack that are passed as arguments bound to a non-pack parameter.)
824 ArrayRef<const ParmVarDecl *> Head;
825 // If the parameters were resolved to another FunctionDecl, these are its
826 // variadic parameters (i.e. the entries of the parameter pack that are
827 // passed as arguments bound to a pack parameter.)
828 ArrayRef<const ParmVarDecl *> Pack;
829 // If the parameters were resolved to another FunctionDecl, these are its
830 // last non-variadic parameters (i.e. the last entries of the parameter pack
831 // that are passed as arguments bound to a non-pack parameter.)
832 ArrayRef<const ParmVarDecl *> Tail;
833 // If the parameters were resolved to another forwarding FunctionDecl, this
834 // is it.
835 std::optional<FunctionDecl *> PackTarget;
836 };
837
838 // The output of this visitor
839 std::optional<ForwardingInfo> Info;
840
841private:
842 // inspects the given callee with the given args to check whether it
843 // contains Parameters, and sets Info accordingly.
844 void handleCall(FunctionDecl *Callee, typename CallExpr::arg_range Args) {
845 // Skip functions with less parameters, they can't be the target.
846 if (Callee->parameters().size() < Parameters.size())
847 return;
848 if (llvm::any_of(Range&: Args,
849 P: [](const Expr *E) { return isa<PackExpansionExpr>(Val: E); })) {
850 return;
851 }
852 auto PackLocation = findPack(Args);
853 if (!PackLocation)
854 return;
855 ArrayRef<ParmVarDecl *> MatchingParams =
856 Callee->parameters().slice(N: *PackLocation, M: Parameters.size());
857 // Check whether the function has a parameter pack as the last template
858 // parameter
859 if (const auto *TTPT = getFunctionPackType(Callee)) {
860 // In this case: Separate the parameters into head, pack and tail
861 auto IsExpandedPack = [&](const ParmVarDecl *P) {
862 return getUnderlyingPackType(Param: P) == TTPT;
863 };
864 ForwardingInfo FI;
865 FI.Head = MatchingParams.take_until(Pred: IsExpandedPack);
866 FI.Pack =
867 MatchingParams.drop_front(N: FI.Head.size()).take_while(Pred: IsExpandedPack);
868 FI.Tail = MatchingParams.drop_front(N: FI.Head.size() + FI.Pack.size());
869 FI.PackTarget = Callee;
870 Info = FI;
871 return;
872 }
873 // Default case: assume all parameters were fully resolved
874 ForwardingInfo FI;
875 FI.Head = MatchingParams;
876 Info = FI;
877 }
878
879 // Returns the beginning of the expanded pack represented by Parameters
880 // in the given arguments, if it is there.
881 std::optional<size_t> findPack(typename CallExpr::arg_range Args) {
882 // find the argument directly referring to the first parameter
883 assert(Parameters.size() <= static_cast<size_t>(llvm::size(Args)));
884 for (auto Begin = Args.begin(), End = Args.end() - Parameters.size() + 1;
885 Begin != End; ++Begin) {
886 if (const auto *RefArg = unwrapForward(*Begin)) {
887 if (Parameters.front() != RefArg->getDecl())
888 continue;
889 // Check that this expands all the way until the last parameter.
890 // It's enough to look at the last parameter, because it isn't possible
891 // to expand without expanding all of them.
892 auto ParamEnd = Begin + Parameters.size() - 1;
893 RefArg = unwrapForward(E: *ParamEnd);
894 if (!RefArg || Parameters.back() != RefArg->getDecl())
895 continue;
896 return std::distance(first: Args.begin(), last: Begin);
897 }
898 }
899 return std::nullopt;
900 }
901
902 static FunctionDecl *getCalleeDeclOrUniqueOverload(CallExpr *E) {
903 Decl *CalleeDecl = E->getCalleeDecl();
904 auto *Callee = dyn_cast_or_null<FunctionDecl>(Val: CalleeDecl);
905 if (!Callee) {
906 if (auto *Lookup = dyn_cast<UnresolvedLookupExpr>(Val: E->getCallee())) {
907 Callee = resolveOverload(Lookup, E);
908 }
909 }
910 // Ignore the callee if the number of arguments is wrong (deal with va_args)
911 if (Callee && Callee->getNumParams() == E->getNumArgs())
912 return Callee;
913 return nullptr;
914 }
915
916 static FunctionDecl *resolveOverload(UnresolvedLookupExpr *Lookup,
917 CallExpr *E) {
918 FunctionDecl *MatchingDecl = nullptr;
919 if (!Lookup->requiresADL()) {
920 // Check whether there is a single overload with this number of
921 // parameters
922 for (auto *Candidate : Lookup->decls()) {
923 if (auto *FuncCandidate = dyn_cast_or_null<FunctionDecl>(Candidate)) {
924 if (FuncCandidate->getNumParams() == E->getNumArgs()) {
925 if (MatchingDecl) {
926 // there are multiple candidates - abort
927 return nullptr;
928 }
929 MatchingDecl = FuncCandidate;
930 }
931 }
932 }
933 }
934 return MatchingDecl;
935 }
936
937 // Tries to get to the underlying argument by unwrapping implicit nodes and
938 // std::forward.
939 static const DeclRefExpr *unwrapForward(const Expr *E) {
940 E = E->IgnoreImplicitAsWritten();
941 // There might be an implicit copy/move constructor call on top of the
942 // forwarded arg.
943 // FIXME: Maybe mark implicit calls in the AST to properly filter here.
944 if (const auto *Const = dyn_cast<CXXConstructExpr>(Val: E))
945 if (Const->getConstructor()->isCopyOrMoveConstructor())
946 E = Const->getArg(Arg: 0)->IgnoreImplicitAsWritten();
947 if (const auto *Call = dyn_cast<CallExpr>(Val: E)) {
948 const auto Callee = Call->getBuiltinCallee();
949 if (Callee == Builtin::BIforward) {
950 return dyn_cast<DeclRefExpr>(
951 Val: Call->getArg(Arg: 0)->IgnoreImplicitAsWritten());
952 }
953 }
954 return dyn_cast<DeclRefExpr>(Val: E);
955 }
956};
957
958} // namespace
959
960SmallVector<const ParmVarDecl *>
961resolveForwardingParameters(const FunctionDecl *D, unsigned MaxDepth) {
962 auto Parameters = D->parameters();
963 // If the function has a template parameter pack
964 if (const auto *TTPT = getFunctionPackType(Callee: D)) {
965 // Split the parameters into head, pack and tail
966 auto IsExpandedPack = [TTPT](const ParmVarDecl *P) {
967 return getUnderlyingPackType(Param: P) == TTPT;
968 };
969 ArrayRef<const ParmVarDecl *> Head = Parameters.take_until(Pred: IsExpandedPack);
970 ArrayRef<const ParmVarDecl *> Pack =
971 Parameters.drop_front(N: Head.size()).take_while(Pred: IsExpandedPack);
972 ArrayRef<const ParmVarDecl *> Tail =
973 Parameters.drop_front(N: Head.size() + Pack.size());
974 SmallVector<const ParmVarDecl *> Result(Parameters.size());
975 // Fill in non-pack parameters
976 auto *HeadIt = std::copy(first: Head.begin(), last: Head.end(), result: Result.begin());
977 auto TailIt = std::copy(first: Tail.rbegin(), last: Tail.rend(), result: Result.rbegin());
978 // Recurse on pack parameters
979 size_t Depth = 0;
980 const FunctionDecl *CurrentFunction = D;
981 llvm::SmallSet<const FunctionTemplateDecl *, 4> SeenTemplates;
982 if (const auto *Template = D->getPrimaryTemplate()) {
983 SeenTemplates.insert(Ptr: Template);
984 }
985 while (!Pack.empty() && CurrentFunction && Depth < MaxDepth) {
986 // Find call expressions involving the pack
987 ForwardingCallVisitor V{Pack};
988 V.TraverseStmt(S: CurrentFunction->getBody());
989 if (!V.Info) {
990 break;
991 }
992 // If we found something: Fill in non-pack parameters
993 auto Info = *V.Info;
994 HeadIt = std::copy(first: Info.Head.begin(), last: Info.Head.end(), result: HeadIt);
995 TailIt = std::copy(first: Info.Tail.rbegin(), last: Info.Tail.rend(), result: TailIt);
996 // Prepare next recursion level
997 Pack = Info.Pack;
998 CurrentFunction = Info.PackTarget.value_or(u: nullptr);
999 Depth++;
1000 // If we are recursing into a previously encountered function: Abort
1001 if (CurrentFunction) {
1002 if (const auto *Template = CurrentFunction->getPrimaryTemplate()) {
1003 bool NewFunction = SeenTemplates.insert(Ptr: Template).second;
1004 if (!NewFunction) {
1005 return {Parameters.begin(), Parameters.end()};
1006 }
1007 }
1008 }
1009 }
1010 // Fill in the remaining unresolved pack parameters
1011 HeadIt = std::copy(first: Pack.begin(), last: Pack.end(), result: HeadIt);
1012 assert(TailIt.base() == HeadIt);
1013 return Result;
1014 }
1015 return {Parameters.begin(), Parameters.end()};
1016}
1017
1018bool isExpandedFromParameterPack(const ParmVarDecl *D) {
1019 return getUnderlyingPackType(Param: D) != nullptr;
1020}
1021
1022} // namespace clangd
1023} // namespace clang
1024

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