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/NestedNameSpecifier.h"
20 #include "clang/AST/PrettyPrinter.h"
21 #include "clang/AST/RecursiveASTVisitor.h"
22 #include "clang/AST/Stmt.h"
23 #include "clang/AST/TemplateBase.h"
24 #include "clang/AST/TypeLoc.h"
25 #include "clang/Basic/SourceLocation.h"
26 #include "clang/Basic/SourceManager.h"
27 #include "clang/Basic/Specifiers.h"
28 #include "clang/Index/USRGeneration.h"
29 #include "llvm/ADT/ArrayRef.h"
30 #include "llvm/ADT/Optional.h"
31 #include "llvm/ADT/STLExtras.h"
32 #include "llvm/ADT/StringRef.h"
33 #include "llvm/Support/Casting.h"
34 #include "llvm/Support/raw_ostream.h"
35 #include <string>
36 #include <vector>
37 
38 namespace clang {
39 namespace clangd {
40 
41 namespace {
42 llvm::Optional<llvm::ArrayRef<TemplateArgumentLoc>>
43 getTemplateSpecializationArgLocs(const NamedDecl &ND) {
44   if (auto *Func = llvm::dyn_cast<FunctionDecl>(&ND)) {
45     if (const ASTTemplateArgumentListInfo *Args =
46             Func->getTemplateSpecializationArgsAsWritten())
47       return Args->arguments();
48   } else if (auto *Cls =
49                  llvm::dyn_cast<ClassTemplatePartialSpecializationDecl>(&ND)) {
50     if (auto *Args = Cls->getTemplateArgsAsWritten())
51       return Args->arguments();
52   } else if (auto *Var =
53                  llvm::dyn_cast<VarTemplatePartialSpecializationDecl>(&ND)) {
54     if (auto *Args = Var->getTemplateArgsAsWritten())
55       return Args->arguments();
56   } else if (auto *Var = llvm::dyn_cast<VarTemplateSpecializationDecl>(&ND))
57     return Var->getTemplateArgsInfo().arguments();
58   // We return None for ClassTemplateSpecializationDecls because it does not
59   // contain TemplateArgumentLoc information.
60   return llvm::None;
61 }
62 
63 template <class T>
64 bool isTemplateSpecializationKind(const NamedDecl *D,
65                                   TemplateSpecializationKind Kind) {
66   if (const auto *TD = dyn_cast<T>(D))
67     return TD->getTemplateSpecializationKind() == Kind;
68   return false;
69 }
70 
71 bool isTemplateSpecializationKind(const NamedDecl *D,
72                                   TemplateSpecializationKind Kind) {
73   return isTemplateSpecializationKind<FunctionDecl>(D, Kind) ||
74          isTemplateSpecializationKind<CXXRecordDecl>(D, Kind) ||
75          isTemplateSpecializationKind<VarDecl>(D, Kind);
76 }
77 
78 // Store all UsingDirectiveDecls in parent contexts of DestContext, that were
79 // introduced before InsertionPoint.
80 llvm::DenseSet<const NamespaceDecl *>
81 getUsingNamespaceDirectives(const DeclContext *DestContext,
82                             SourceLocation Until) {
83   const auto &SM = DestContext->getParentASTContext().getSourceManager();
84   llvm::DenseSet<const NamespaceDecl *> VisibleNamespaceDecls;
85   for (const auto *DC = DestContext; DC; DC = DC->getLookupParent()) {
86     for (const auto *D : DC->decls()) {
87       if (!SM.isWrittenInSameFile(D->getLocation(), Until) ||
88           !SM.isBeforeInTranslationUnit(D->getLocation(), Until))
89         continue;
90       if (auto *UDD = llvm::dyn_cast<UsingDirectiveDecl>(D))
91         VisibleNamespaceDecls.insert(
92             UDD->getNominatedNamespace()->getCanonicalDecl());
93     }
94   }
95   return VisibleNamespaceDecls;
96 }
97 
98 // Goes over all parents of SourceContext until we find a common ancestor for
99 // DestContext and SourceContext. Any qualifier including and above common
100 // ancestor is redundant, therefore we stop at lowest common ancestor.
101 // In addition to that stops early whenever IsVisible returns true. This can be
102 // used to implement support for "using namespace" decls.
103 std::string
104 getQualification(ASTContext &Context, const DeclContext *DestContext,
105                  const DeclContext *SourceContext,
106                  llvm::function_ref<bool(NestedNameSpecifier *)> IsVisible) {
107   std::vector<const NestedNameSpecifier *> Parents;
108   bool ReachedNS = false;
109   for (const DeclContext *CurContext = SourceContext; CurContext;
110        CurContext = CurContext->getLookupParent()) {
111     // Stop once we reach a common ancestor.
112     if (CurContext->Encloses(DestContext))
113       break;
114 
115     NestedNameSpecifier *NNS = nullptr;
116     if (auto *TD = llvm::dyn_cast<TagDecl>(CurContext)) {
117       // There can't be any more tag parents after hitting a namespace.
118       assert(!ReachedNS);
119       (void)ReachedNS;
120       NNS = NestedNameSpecifier::Create(Context, nullptr, false,
121                                         TD->getTypeForDecl());
122     } else if (auto *NSD = llvm::dyn_cast<NamespaceDecl>(CurContext)) {
123       ReachedNS = true;
124       NNS = NestedNameSpecifier::Create(Context, nullptr, NSD);
125       // Anonymous and inline namespace names are not spelled while qualifying
126       // a name, so skip those.
127       if (NSD->isAnonymousNamespace() || NSD->isInlineNamespace())
128         continue;
129     } else {
130       // Other types of contexts cannot be spelled in code, just skip over
131       // them.
132       continue;
133     }
134     // Stop if this namespace is already visible at DestContext.
135     if (IsVisible(NNS))
136       break;
137 
138     Parents.push_back(NNS);
139   }
140 
141   // Go over name-specifiers in reverse order to create necessary qualification,
142   // since we stored inner-most parent first.
143   std::string Result;
144   llvm::raw_string_ostream OS(Result);
145   for (const auto *Parent : llvm::reverse(Parents))
146     Parent->print(OS, Context.getPrintingPolicy());
147   return OS.str();
148 }
149 
150 } // namespace
151 
152 bool isImplicitTemplateInstantiation(const NamedDecl *D) {
153   return isTemplateSpecializationKind(D, TSK_ImplicitInstantiation);
154 }
155 
156 bool isExplicitTemplateSpecialization(const NamedDecl *D) {
157   return isTemplateSpecializationKind(D, TSK_ExplicitSpecialization);
158 }
159 
160 bool isImplementationDetail(const Decl *D) {
161   return !isSpelledInSource(D->getLocation(),
162                             D->getASTContext().getSourceManager());
163 }
164 
165 SourceLocation nameLocation(const clang::Decl &D, const SourceManager &SM) {
166   auto L = D.getLocation();
167   if (isSpelledInSource(L, SM))
168     return SM.getSpellingLoc(L);
169   return SM.getExpansionLoc(L);
170 }
171 
172 std::string printQualifiedName(const NamedDecl &ND) {
173   std::string QName;
174   llvm::raw_string_ostream OS(QName);
175   PrintingPolicy Policy(ND.getASTContext().getLangOpts());
176   // Note that inline namespaces are treated as transparent scopes. This
177   // reflects the way they're most commonly used for lookup. Ideally we'd
178   // include them, but at query time it's hard to find all the inline
179   // namespaces to query: the preamble doesn't have a dedicated list.
180   Policy.SuppressUnwrittenScope = true;
181   ND.printQualifiedName(OS, Policy);
182   OS.flush();
183   assert(!StringRef(QName).startswith("::"));
184   return QName;
185 }
186 
187 static bool isAnonymous(const DeclarationName &N) {
188   return N.isIdentifier() && !N.getAsIdentifierInfo();
189 }
190 
191 NestedNameSpecifierLoc getQualifierLoc(const NamedDecl &ND) {
192   if (auto *V = llvm::dyn_cast<DeclaratorDecl>(&ND))
193     return V->getQualifierLoc();
194   if (auto *T = llvm::dyn_cast<TagDecl>(&ND))
195     return T->getQualifierLoc();
196   return NestedNameSpecifierLoc();
197 }
198 
199 std::string printUsingNamespaceName(const ASTContext &Ctx,
200                                     const UsingDirectiveDecl &D) {
201   PrintingPolicy PP(Ctx.getLangOpts());
202   std::string Name;
203   llvm::raw_string_ostream Out(Name);
204 
205   if (auto *Qual = D.getQualifier())
206     Qual->print(Out, PP);
207   D.getNominatedNamespaceAsWritten()->printName(Out);
208   return Out.str();
209 }
210 
211 std::string printName(const ASTContext &Ctx, const NamedDecl &ND) {
212   std::string Name;
213   llvm::raw_string_ostream Out(Name);
214   PrintingPolicy PP(Ctx.getLangOpts());
215   // We don't consider a class template's args part of the constructor name.
216   PP.SuppressTemplateArgsInCXXConstructors = true;
217 
218   // Handle 'using namespace'. They all have the same name - <using-directive>.
219   if (auto *UD = llvm::dyn_cast<UsingDirectiveDecl>(&ND)) {
220     Out << "using namespace ";
221     if (auto *Qual = UD->getQualifier())
222       Qual->print(Out, PP);
223     UD->getNominatedNamespaceAsWritten()->printName(Out);
224     return Out.str();
225   }
226 
227   if (isAnonymous(ND.getDeclName())) {
228     // Come up with a presentation for an anonymous entity.
229     if (isa<NamespaceDecl>(ND))
230       return "(anonymous namespace)";
231     if (auto *Cls = llvm::dyn_cast<RecordDecl>(&ND)) {
232       if (Cls->isLambda())
233         return "(lambda)";
234       return ("(anonymous " + Cls->getKindName() + ")").str();
235     }
236     if (isa<EnumDecl>(ND))
237       return "(anonymous enum)";
238     return "(anonymous)";
239   }
240 
241   // Print nested name qualifier if it was written in the source code.
242   if (auto *Qualifier = getQualifierLoc(ND).getNestedNameSpecifier())
243     Qualifier->print(Out, PP);
244   // Print the name itself.
245   ND.getDeclName().print(Out, PP);
246   // Print template arguments.
247   Out << printTemplateSpecializationArgs(ND);
248 
249   return Out.str();
250 }
251 
252 std::string printTemplateSpecializationArgs(const NamedDecl &ND) {
253   std::string TemplateArgs;
254   llvm::raw_string_ostream OS(TemplateArgs);
255   PrintingPolicy Policy(ND.getASTContext().getLangOpts());
256   if (llvm::Optional<llvm::ArrayRef<TemplateArgumentLoc>> Args =
257           getTemplateSpecializationArgLocs(ND)) {
258     printTemplateArgumentList(OS, *Args, Policy);
259   } else if (auto *Cls = llvm::dyn_cast<ClassTemplateSpecializationDecl>(&ND)) {
260     if (const TypeSourceInfo *TSI = Cls->getTypeAsWritten()) {
261       // ClassTemplateSpecializationDecls do not contain
262       // TemplateArgumentTypeLocs, they only have TemplateArgumentTypes. So we
263       // create a new argument location list from TypeSourceInfo.
264       auto STL = TSI->getTypeLoc().getAs<TemplateSpecializationTypeLoc>();
265       llvm::SmallVector<TemplateArgumentLoc> ArgLocs;
266       ArgLocs.reserve(STL.getNumArgs());
267       for (unsigned I = 0; I < STL.getNumArgs(); ++I)
268         ArgLocs.push_back(STL.getArgLoc(I));
269       printTemplateArgumentList(OS, ArgLocs, Policy);
270     } else {
271       // FIXME: Fix cases when getTypeAsWritten returns null inside clang AST,
272       // e.g. friend decls. Currently we fallback to Template Arguments without
273       // location information.
274       printTemplateArgumentList(OS, Cls->getTemplateArgs().asArray(), Policy);
275     }
276   }
277   OS.flush();
278   return TemplateArgs;
279 }
280 
281 std::string printNamespaceScope(const DeclContext &DC) {
282   for (const auto *Ctx = &DC; Ctx != nullptr; Ctx = Ctx->getParent())
283     if (const auto *NS = dyn_cast<NamespaceDecl>(Ctx))
284       if (!NS->isAnonymousNamespace() && !NS->isInlineNamespace())
285         return printQualifiedName(*NS) + "::";
286   return "";
287 }
288 
289 static llvm::StringRef
290 getNameOrErrForObjCInterface(const ObjCInterfaceDecl *ID) {
291   return ID ? ID->getName() : "<<error-type>>";
292 }
293 
294 std::string printObjCMethod(const ObjCMethodDecl &Method) {
295   std::string Name;
296   llvm::raw_string_ostream OS(Name);
297 
298   OS << (Method.isInstanceMethod() ? '-' : '+') << '[';
299 
300   // Should always be true.
301   if (const ObjCContainerDecl *C =
302           dyn_cast<ObjCContainerDecl>(Method.getDeclContext()))
303     OS << printObjCContainer(*C);
304 
305   Method.getSelector().print(OS << ' ');
306   if (Method.isVariadic())
307     OS << ", ...";
308 
309   OS << ']';
310   OS.flush();
311   return Name;
312 }
313 
314 std::string printObjCContainer(const ObjCContainerDecl &C) {
315   if (const ObjCCategoryDecl *Category = dyn_cast<ObjCCategoryDecl>(&C)) {
316     std::string Name;
317     llvm::raw_string_ostream OS(Name);
318     const ObjCInterfaceDecl *Class = Category->getClassInterface();
319     OS << getNameOrErrForObjCInterface(Class) << '(' << Category->getName()
320        << ')';
321     OS.flush();
322     return Name;
323   }
324   if (const ObjCCategoryImplDecl *CID = dyn_cast<ObjCCategoryImplDecl>(&C)) {
325     std::string Name;
326     llvm::raw_string_ostream OS(Name);
327     const ObjCInterfaceDecl *Class = CID->getClassInterface();
328     OS << getNameOrErrForObjCInterface(Class) << '(' << CID->getName() << ')';
329     OS.flush();
330     return Name;
331   }
332   return C.getNameAsString();
333 }
334 
335 SymbolID getSymbolID(const Decl *D) {
336   llvm::SmallString<128> USR;
337   if (index::generateUSRForDecl(D, USR))
338     return {};
339   return SymbolID(USR);
340 }
341 
342 SymbolID getSymbolID(const llvm::StringRef MacroName, const MacroInfo *MI,
343                      const SourceManager &SM) {
344   if (MI == nullptr)
345     return {};
346   llvm::SmallString<128> USR;
347   if (index::generateUSRForMacro(MacroName, MI->getDefinitionLoc(), SM, USR))
348     return {};
349   return SymbolID(USR);
350 }
351 
352 std::string printType(const QualType QT, const DeclContext &CurContext,
353                       const llvm::StringRef Placeholder) {
354   std::string Result;
355   llvm::raw_string_ostream OS(Result);
356   PrintingPolicy PP(CurContext.getParentASTContext().getPrintingPolicy());
357   PP.SuppressTagKeyword = true;
358   PP.SuppressUnwrittenScope = true;
359 
360   class PrintCB : public PrintingCallbacks {
361   public:
362     PrintCB(const DeclContext *CurContext) : CurContext(CurContext) {}
363     virtual ~PrintCB() {}
364     virtual bool isScopeVisible(const DeclContext *DC) const override {
365       return DC->Encloses(CurContext);
366     }
367 
368   private:
369     const DeclContext *CurContext;
370   };
371   PrintCB PCB(&CurContext);
372   PP.Callbacks = &PCB;
373 
374   QT.print(OS, PP, Placeholder);
375   return OS.str();
376 }
377 
378 bool hasReservedName(const Decl &D) {
379   if (const auto *ND = llvm::dyn_cast<NamedDecl>(&D))
380     if (const auto *II = ND->getIdentifier())
381       return isReservedName(II->getName());
382   return false;
383 }
384 
385 bool hasReservedScope(const DeclContext &DC) {
386   for (const DeclContext *D = &DC; D; D = D->getParent()) {
387     if (D->isTransparentContext() || D->isInlineNamespace())
388       continue;
389     if (const auto *ND = llvm::dyn_cast<NamedDecl>(D))
390       if (hasReservedName(*ND))
391         return true;
392   }
393   return false;
394 }
395 
396 QualType declaredType(const TypeDecl *D) {
397   if (const auto *CTSD = llvm::dyn_cast<ClassTemplateSpecializationDecl>(D))
398     if (const auto *TSI = CTSD->getTypeAsWritten())
399       return TSI->getType();
400   return D->getASTContext().getTypeDeclType(D);
401 }
402 
403 namespace {
404 /// Computes the deduced type at a given location by visiting the relevant
405 /// nodes. We use this to display the actual type when hovering over an "auto"
406 /// keyword or "decltype()" expression.
407 /// FIXME: This could have been a lot simpler by visiting AutoTypeLocs but it
408 /// seems that the AutoTypeLocs that can be visited along with their AutoType do
409 /// not have the deduced type set. Instead, we have to go to the appropriate
410 /// DeclaratorDecl/FunctionDecl and work our back to the AutoType that does have
411 /// a deduced type set. The AST should be improved to simplify this scenario.
412 class DeducedTypeVisitor : public RecursiveASTVisitor<DeducedTypeVisitor> {
413   SourceLocation SearchedLocation;
414 
415 public:
416   DeducedTypeVisitor(SourceLocation SearchedLocation)
417       : SearchedLocation(SearchedLocation) {}
418 
419   // Handle auto initializers:
420   //- auto i = 1;
421   //- decltype(auto) i = 1;
422   //- auto& i = 1;
423   //- auto* i = &a;
424   bool VisitDeclaratorDecl(DeclaratorDecl *D) {
425     if (!D->getTypeSourceInfo() ||
426         D->getTypeSourceInfo()->getTypeLoc().getBeginLoc() != SearchedLocation)
427       return true;
428 
429     if (auto *AT = D->getType()->getContainedAutoType()) {
430       DeducedType = AT->desugar();
431     }
432     return true;
433   }
434 
435   // Handle auto return types:
436   //- auto foo() {}
437   //- auto& foo() {}
438   //- auto foo() -> int {}
439   //- auto foo() -> decltype(1+1) {}
440   //- operator auto() const { return 10; }
441   bool VisitFunctionDecl(FunctionDecl *D) {
442     if (!D->getTypeSourceInfo())
443       return true;
444     // Loc of auto in return type (c++14).
445     auto CurLoc = D->getReturnTypeSourceRange().getBegin();
446     // Loc of "auto" in operator auto()
447     if (CurLoc.isInvalid() && isa<CXXConversionDecl>(D))
448       CurLoc = D->getTypeSourceInfo()->getTypeLoc().getBeginLoc();
449     // Loc of "auto" in function with trailing return type (c++11).
450     if (CurLoc.isInvalid())
451       CurLoc = D->getSourceRange().getBegin();
452     if (CurLoc != SearchedLocation)
453       return true;
454 
455     const AutoType *AT = D->getReturnType()->getContainedAutoType();
456     if (AT && !AT->getDeducedType().isNull()) {
457       DeducedType = AT->getDeducedType();
458     } else if (auto *DT = dyn_cast<DecltypeType>(D->getReturnType())) {
459       // auto in a trailing return type just points to a DecltypeType and
460       // getContainedAutoType does not unwrap it.
461       if (!DT->getUnderlyingType().isNull())
462         DeducedType = DT->getUnderlyingType();
463     } else if (!D->getReturnType().isNull()) {
464       DeducedType = D->getReturnType();
465     }
466     return true;
467   }
468 
469   // Handle non-auto decltype, e.g.:
470   // - auto foo() -> decltype(expr) {}
471   // - decltype(expr);
472   bool VisitDecltypeTypeLoc(DecltypeTypeLoc TL) {
473     if (TL.getBeginLoc() != SearchedLocation)
474       return true;
475 
476     // A DecltypeType's underlying type can be another DecltypeType! E.g.
477     //  int I = 0;
478     //  decltype(I) J = I;
479     //  decltype(J) K = J;
480     const DecltypeType *DT = dyn_cast<DecltypeType>(TL.getTypePtr());
481     while (DT && !DT->getUnderlyingType().isNull()) {
482       DeducedType = DT->getUnderlyingType();
483       DT = dyn_cast<DecltypeType>(DeducedType.getTypePtr());
484     }
485     return true;
486   }
487 
488   // Handle functions/lambdas with `auto` typed parameters.
489   // We deduce the type if there's exactly one instantiation visible.
490   bool VisitParmVarDecl(ParmVarDecl *PVD) {
491     if (!PVD->getType()->isDependentType())
492       return true;
493     // 'auto' here does not name an AutoType, but an implicit template param.
494     TemplateTypeParmTypeLoc Auto =
495         getContainedAutoParamType(PVD->getTypeSourceInfo()->getTypeLoc());
496     if (Auto.isNull() || Auto.getNameLoc() != SearchedLocation)
497       return true;
498 
499     // We expect the TTP to be attached to this function template.
500     // Find the template and the param index.
501     auto *Templated = llvm::dyn_cast<FunctionDecl>(PVD->getDeclContext());
502     if (!Templated)
503       return true;
504     auto *FTD = Templated->getDescribedFunctionTemplate();
505     if (!FTD)
506       return true;
507     int ParamIndex = paramIndex(*FTD, *Auto.getDecl());
508     if (ParamIndex < 0) {
509       assert(false && "auto TTP is not from enclosing function?");
510       return true;
511     }
512 
513     // Now find the instantiation and the deduced template type arg.
514     auto *Instantiation =
515         llvm::dyn_cast_or_null<FunctionDecl>(getOnlyInstantiation(Templated));
516     if (!Instantiation)
517       return true;
518     const auto *Args = Instantiation->getTemplateSpecializationArgs();
519     if (Args->size() != FTD->getTemplateParameters()->size())
520       return true; // no weird variadic stuff
521     DeducedType = Args->get(ParamIndex).getAsType();
522     return true;
523   }
524 
525   static int paramIndex(const TemplateDecl &TD, NamedDecl &Param) {
526     unsigned I = 0;
527     for (auto *ND : *TD.getTemplateParameters()) {
528       if (&Param == ND)
529         return I;
530       ++I;
531     }
532     return -1;
533   }
534 
535   QualType DeducedType;
536 };
537 } // namespace
538 
539 llvm::Optional<QualType> getDeducedType(ASTContext &ASTCtx,
540                                         SourceLocation Loc) {
541   if (!Loc.isValid())
542     return {};
543   DeducedTypeVisitor V(Loc);
544   V.TraverseAST(ASTCtx);
545   if (V.DeducedType.isNull())
546     return llvm::None;
547   return V.DeducedType;
548 }
549 
550 TemplateTypeParmTypeLoc getContainedAutoParamType(TypeLoc TL) {
551   if (auto QTL = TL.getAs<QualifiedTypeLoc>())
552     return getContainedAutoParamType(QTL.getUnqualifiedLoc());
553   if (llvm::isa<PointerType, ReferenceType, ParenType>(TL.getTypePtr()))
554     return getContainedAutoParamType(TL.getNextTypeLoc());
555   if (auto FTL = TL.getAs<FunctionTypeLoc>())
556     return getContainedAutoParamType(FTL.getReturnLoc());
557   if (auto TTPTL = TL.getAs<TemplateTypeParmTypeLoc>()) {
558     if (TTPTL.getTypePtr()->getDecl()->isImplicit())
559       return TTPTL;
560   }
561   return {};
562 }
563 
564 template <typename TemplateDeclTy>
565 static NamedDecl *getOnlyInstantiationImpl(TemplateDeclTy *TD) {
566   NamedDecl *Only = nullptr;
567   for (auto *Spec : TD->specializations()) {
568     if (Spec->getTemplateSpecializationKind() == TSK_ExplicitSpecialization)
569       continue;
570     if (Only != nullptr)
571       return nullptr;
572     Only = Spec;
573   }
574   return Only;
575 }
576 
577 NamedDecl *getOnlyInstantiation(NamedDecl *TemplatedDecl) {
578   if (TemplateDecl *TD = TemplatedDecl->getDescribedTemplate()) {
579     if (auto *CTD = llvm::dyn_cast<ClassTemplateDecl>(TD))
580       return getOnlyInstantiationImpl(CTD);
581     if (auto *FTD = llvm::dyn_cast<FunctionTemplateDecl>(TD))
582       return getOnlyInstantiationImpl(FTD);
583     if (auto *VTD = llvm::dyn_cast<VarTemplateDecl>(TD))
584       return getOnlyInstantiationImpl(VTD);
585   }
586   return nullptr;
587 }
588 
589 std::vector<const Attr *> getAttributes(const DynTypedNode &N) {
590   std::vector<const Attr *> Result;
591   if (const auto *TL = N.get<TypeLoc>()) {
592     for (AttributedTypeLoc ATL = TL->getAs<AttributedTypeLoc>(); !ATL.isNull();
593          ATL = ATL.getModifiedLoc().getAs<AttributedTypeLoc>()) {
594       if (const Attr *A = ATL.getAttr())
595         Result.push_back(A);
596       assert(!ATL.getModifiedLoc().isNull());
597     }
598   }
599   if (const auto *S = N.get<AttributedStmt>()) {
600     for (; S != nullptr; S = dyn_cast<AttributedStmt>(S->getSubStmt()))
601       for (const Attr *A : S->getAttrs())
602         if (A)
603           Result.push_back(A);
604   }
605   if (const auto *D = N.get<Decl>()) {
606     for (const Attr *A : D->attrs())
607       if (A)
608         Result.push_back(A);
609   }
610   return Result;
611 }
612 
613 std::string getQualification(ASTContext &Context,
614                              const DeclContext *DestContext,
615                              SourceLocation InsertionPoint,
616                              const NamedDecl *ND) {
617   auto VisibleNamespaceDecls =
618       getUsingNamespaceDirectives(DestContext, InsertionPoint);
619   return getQualification(
620       Context, DestContext, ND->getDeclContext(),
621       [&](NestedNameSpecifier *NNS) {
622         if (NNS->getKind() != NestedNameSpecifier::Namespace)
623           return false;
624         const auto *CanonNSD = NNS->getAsNamespace()->getCanonicalDecl();
625         return llvm::any_of(VisibleNamespaceDecls,
626                             [CanonNSD](const NamespaceDecl *NSD) {
627                               return NSD->getCanonicalDecl() == CanonNSD;
628                             });
629       });
630 }
631 
632 std::string getQualification(ASTContext &Context,
633                              const DeclContext *DestContext,
634                              const NamedDecl *ND,
635                              llvm::ArrayRef<std::string> VisibleNamespaces) {
636   for (llvm::StringRef NS : VisibleNamespaces) {
637     assert(NS.endswith("::"));
638     (void)NS;
639   }
640   return getQualification(
641       Context, DestContext, ND->getDeclContext(),
642       [&](NestedNameSpecifier *NNS) {
643         return llvm::any_of(VisibleNamespaces, [&](llvm::StringRef Namespace) {
644           std::string NS;
645           llvm::raw_string_ostream OS(NS);
646           NNS->print(OS, Context.getPrintingPolicy());
647           return OS.str() == Namespace;
648         });
649       });
650 }
651 
652 bool hasUnstableLinkage(const Decl *D) {
653   // Linkage of a ValueDecl depends on the type.
654   // If that's not deduced yet, deducing it may change the linkage.
655   auto *VD = llvm::dyn_cast_or_null<ValueDecl>(D);
656   return VD && !VD->getType().isNull() && VD->getType()->isUndeducedType();
657 }
658 
659 bool isDeeplyNested(const Decl *D, unsigned MaxDepth) {
660   size_t ContextDepth = 0;
661   for (auto *Ctx = D->getDeclContext(); Ctx && !Ctx->isTranslationUnit();
662        Ctx = Ctx->getParent()) {
663     if (++ContextDepth == MaxDepth)
664       return true;
665   }
666   return false;
667 }
668 } // namespace clangd
669 } // namespace clang
670