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