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