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