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 "FindTarget.h"
12 #include "SourceCode.h"
13 #include "clang/AST/ASTContext.h"
14 #include "clang/AST/ASTTypeTraits.h"
15 #include "clang/AST/Decl.h"
16 #include "clang/AST/DeclBase.h"
17 #include "clang/AST/DeclCXX.h"
18 #include "clang/AST/DeclTemplate.h"
19 #include "clang/AST/DeclarationName.h"
20 #include "clang/AST/NestedNameSpecifier.h"
21 #include "clang/AST/PrettyPrinter.h"
22 #include "clang/AST/RecursiveASTVisitor.h"
23 #include "clang/AST/TemplateBase.h"
24 #include "clang/Basic/SourceLocation.h"
25 #include "clang/Basic/SourceManager.h"
26 #include "clang/Basic/Specifiers.h"
27 #include "clang/Index/USRGeneration.h"
28 #include "llvm/ADT/ArrayRef.h"
29 #include "llvm/ADT/Optional.h"
30 #include "llvm/ADT/STLExtras.h"
31 #include "llvm/ADT/StringRef.h"
32 #include "llvm/Support/Casting.h"
33 #include "llvm/Support/ScopedPrinter.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>>
getTemplateSpecializationArgLocs(const NamedDecl & ND)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>
isTemplateSpecializationKind(const NamedDecl * D,TemplateSpecializationKind Kind)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 
isTemplateSpecializationKind(const NamedDecl * D,TemplateSpecializationKind Kind)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 *>
getUsingNamespaceDirectives(const DeclContext * DestContext,SourceLocation Until)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
getQualification(ASTContext & Context,const DeclContext * DestContext,const DeclContext * SourceContext,llvm::function_ref<bool (NestedNameSpecifier *)> IsVisible)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       NNS = NestedNameSpecifier::Create(Context, nullptr, false,
120                                         TD->getTypeForDecl());
121     } else {
122       ReachedNS = true;
123       auto *NSD = llvm::cast<NamespaceDecl>(CurContext);
124       NNS = NestedNameSpecifier::Create(Context, nullptr, NSD);
125       // Anonymous and inline namespace names are not spelled while qualifying a
126       // name, so skip those.
127       if (NSD->isAnonymousNamespace() || NSD->isInlineNamespace())
128         continue;
129     }
130     // Stop if this namespace is already visible at DestContext.
131     if (IsVisible(NNS))
132       break;
133 
134     Parents.push_back(NNS);
135   }
136 
137   // Go over name-specifiers in reverse order to create necessary qualification,
138   // since we stored inner-most parent first.
139   std::string Result;
140   llvm::raw_string_ostream OS(Result);
141   for (const auto *Parent : llvm::reverse(Parents))
142     Parent->print(OS, Context.getPrintingPolicy());
143   return OS.str();
144 }
145 
146 } // namespace
147 
isImplicitTemplateInstantiation(const NamedDecl * D)148 bool isImplicitTemplateInstantiation(const NamedDecl *D) {
149   return isTemplateSpecializationKind(D, TSK_ImplicitInstantiation);
150 }
151 
isExplicitTemplateSpecialization(const NamedDecl * D)152 bool isExplicitTemplateSpecialization(const NamedDecl *D) {
153   return isTemplateSpecializationKind(D, TSK_ExplicitSpecialization);
154 }
155 
isImplementationDetail(const Decl * D)156 bool isImplementationDetail(const Decl *D) {
157   return !isSpelledInSource(D->getLocation(),
158                             D->getASTContext().getSourceManager());
159 }
160 
nameLocation(const clang::Decl & D,const SourceManager & SM)161 SourceLocation nameLocation(const clang::Decl &D, const SourceManager &SM) {
162   auto L = D.getLocation();
163   if (isSpelledInSource(L, SM))
164     return SM.getSpellingLoc(L);
165   return SM.getExpansionLoc(L);
166 }
167 
printQualifiedName(const NamedDecl & ND)168 std::string printQualifiedName(const NamedDecl &ND) {
169   std::string QName;
170   llvm::raw_string_ostream OS(QName);
171   PrintingPolicy Policy(ND.getASTContext().getLangOpts());
172   // Note that inline namespaces are treated as transparent scopes. This
173   // reflects the way they're most commonly used for lookup. Ideally we'd
174   // include them, but at query time it's hard to find all the inline
175   // namespaces to query: the preamble doesn't have a dedicated list.
176   Policy.SuppressUnwrittenScope = true;
177   ND.printQualifiedName(OS, Policy);
178   OS.flush();
179   assert(!StringRef(QName).startswith("::"));
180   return QName;
181 }
182 
isAnonymous(const DeclarationName & N)183 static bool isAnonymous(const DeclarationName &N) {
184   return N.isIdentifier() && !N.getAsIdentifierInfo();
185 }
186 
getQualifierLoc(const NamedDecl & ND)187 NestedNameSpecifierLoc getQualifierLoc(const NamedDecl &ND) {
188   if (auto *V = llvm::dyn_cast<DeclaratorDecl>(&ND))
189     return V->getQualifierLoc();
190   if (auto *T = llvm::dyn_cast<TagDecl>(&ND))
191     return T->getQualifierLoc();
192   return NestedNameSpecifierLoc();
193 }
194 
printUsingNamespaceName(const ASTContext & Ctx,const UsingDirectiveDecl & D)195 std::string printUsingNamespaceName(const ASTContext &Ctx,
196                                     const UsingDirectiveDecl &D) {
197   PrintingPolicy PP(Ctx.getLangOpts());
198   std::string Name;
199   llvm::raw_string_ostream Out(Name);
200 
201   if (auto *Qual = D.getQualifier())
202     Qual->print(Out, PP);
203   D.getNominatedNamespaceAsWritten()->printName(Out);
204   return Out.str();
205 }
206 
printName(const ASTContext & Ctx,const NamedDecl & ND)207 std::string printName(const ASTContext &Ctx, const NamedDecl &ND) {
208   std::string Name;
209   llvm::raw_string_ostream Out(Name);
210   PrintingPolicy PP(Ctx.getLangOpts());
211   // We don't consider a class template's args part of the constructor name.
212   PP.SuppressTemplateArgsInCXXConstructors = true;
213 
214   // Handle 'using namespace'. They all have the same name - <using-directive>.
215   if (auto *UD = llvm::dyn_cast<UsingDirectiveDecl>(&ND)) {
216     Out << "using namespace ";
217     if (auto *Qual = UD->getQualifier())
218       Qual->print(Out, PP);
219     UD->getNominatedNamespaceAsWritten()->printName(Out);
220     return Out.str();
221   }
222 
223   if (isAnonymous(ND.getDeclName())) {
224     // Come up with a presentation for an anonymous entity.
225     if (isa<NamespaceDecl>(ND))
226       return "(anonymous namespace)";
227     if (auto *Cls = llvm::dyn_cast<RecordDecl>(&ND)) {
228       if (Cls->isLambda())
229         return "(lambda)";
230       return ("(anonymous " + Cls->getKindName() + ")").str();
231     }
232     if (isa<EnumDecl>(ND))
233       return "(anonymous enum)";
234     return "(anonymous)";
235   }
236 
237   // Print nested name qualifier if it was written in the source code.
238   if (auto *Qualifier = getQualifierLoc(ND).getNestedNameSpecifier())
239     Qualifier->print(Out, PP);
240   // Print the name itself.
241   ND.getDeclName().print(Out, PP);
242   // Print template arguments.
243   Out << printTemplateSpecializationArgs(ND);
244 
245   return Out.str();
246 }
247 
printTemplateSpecializationArgs(const NamedDecl & ND)248 std::string printTemplateSpecializationArgs(const NamedDecl &ND) {
249   std::string TemplateArgs;
250   llvm::raw_string_ostream OS(TemplateArgs);
251   PrintingPolicy Policy(ND.getASTContext().getLangOpts());
252   if (llvm::Optional<llvm::ArrayRef<TemplateArgumentLoc>> Args =
253           getTemplateSpecializationArgLocs(ND)) {
254     printTemplateArgumentList(OS, *Args, Policy);
255   } else if (auto *Cls = llvm::dyn_cast<ClassTemplateSpecializationDecl>(&ND)) {
256     if (const TypeSourceInfo *TSI = Cls->getTypeAsWritten()) {
257       // ClassTemplateSpecializationDecls do not contain
258       // TemplateArgumentTypeLocs, they only have TemplateArgumentTypes. So we
259       // create a new argument location list from TypeSourceInfo.
260       auto STL = TSI->getTypeLoc().getAs<TemplateSpecializationTypeLoc>();
261       llvm::SmallVector<TemplateArgumentLoc, 8> ArgLocs;
262       ArgLocs.reserve(STL.getNumArgs());
263       for (unsigned I = 0; I < STL.getNumArgs(); ++I)
264         ArgLocs.push_back(STL.getArgLoc(I));
265       printTemplateArgumentList(OS, ArgLocs, Policy);
266     } else {
267       // FIXME: Fix cases when getTypeAsWritten returns null inside clang AST,
268       // e.g. friend decls. Currently we fallback to Template Arguments without
269       // location information.
270       printTemplateArgumentList(OS, Cls->getTemplateArgs().asArray(), Policy);
271     }
272   }
273   OS.flush();
274   return TemplateArgs;
275 }
276 
printNamespaceScope(const DeclContext & DC)277 std::string printNamespaceScope(const DeclContext &DC) {
278   for (const auto *Ctx = &DC; Ctx != nullptr; Ctx = Ctx->getParent())
279     if (const auto *NS = dyn_cast<NamespaceDecl>(Ctx))
280       if (!NS->isAnonymousNamespace() && !NS->isInlineNamespace())
281         return printQualifiedName(*NS) + "::";
282   return "";
283 }
284 
getSymbolID(const Decl * D)285 llvm::Optional<SymbolID> getSymbolID(const Decl *D) {
286   llvm::SmallString<128> USR;
287   if (index::generateUSRForDecl(D, USR))
288     return None;
289   return SymbolID(USR);
290 }
291 
getSymbolID(const llvm::StringRef MacroName,const MacroInfo * MI,const SourceManager & SM)292 llvm::Optional<SymbolID> getSymbolID(const llvm::StringRef MacroName,
293                                      const MacroInfo *MI,
294                                      const SourceManager &SM) {
295   if (MI == nullptr)
296     return None;
297   llvm::SmallString<128> USR;
298   if (index::generateUSRForMacro(MacroName, MI->getDefinitionLoc(), SM, USR))
299     return None;
300   return SymbolID(USR);
301 }
302 
303 // FIXME: This should be handled while printing underlying decls instead.
printType(const QualType QT,const DeclContext & CurContext)304 std::string printType(const QualType QT, const DeclContext &CurContext) {
305   std::string Result;
306   llvm::raw_string_ostream OS(Result);
307   auto Decls = explicitReferenceTargets(
308       ast_type_traits::DynTypedNode::create(QT), DeclRelation::Alias);
309   if (!Decls.empty())
310     OS << getQualification(CurContext.getParentASTContext(), &CurContext,
311                            Decls.front(),
312                            /*VisibleNamespaces=*/llvm::ArrayRef<std::string>{});
313   PrintingPolicy PP(CurContext.getParentASTContext().getPrintingPolicy());
314   PP.SuppressScope = true;
315   PP.SuppressTagKeyword = true;
316   QT.print(OS, PP);
317   return OS.str();
318 }
319 
declaredType(const TypeDecl * D)320 QualType declaredType(const TypeDecl *D) {
321   if (const auto *CTSD = llvm::dyn_cast<ClassTemplateSpecializationDecl>(D))
322     if (const auto *TSI = CTSD->getTypeAsWritten())
323       return TSI->getType();
324   return D->getASTContext().getTypeDeclType(D);
325 }
326 
327 namespace {
328 /// Computes the deduced type at a given location by visiting the relevant
329 /// nodes. We use this to display the actual type when hovering over an "auto"
330 /// keyword or "decltype()" expression.
331 /// FIXME: This could have been a lot simpler by visiting AutoTypeLocs but it
332 /// seems that the AutoTypeLocs that can be visited along with their AutoType do
333 /// not have the deduced type set. Instead, we have to go to the appropriate
334 /// DeclaratorDecl/FunctionDecl and work our back to the AutoType that does have
335 /// a deduced type set. The AST should be improved to simplify this scenario.
336 class DeducedTypeVisitor : public RecursiveASTVisitor<DeducedTypeVisitor> {
337   SourceLocation SearchedLocation;
338 
339 public:
DeducedTypeVisitor(SourceLocation SearchedLocation)340   DeducedTypeVisitor(SourceLocation SearchedLocation)
341       : SearchedLocation(SearchedLocation) {}
342 
343   // Handle auto initializers:
344   //- auto i = 1;
345   //- decltype(auto) i = 1;
346   //- auto& i = 1;
347   //- auto* i = &a;
VisitDeclaratorDecl(DeclaratorDecl * D)348   bool VisitDeclaratorDecl(DeclaratorDecl *D) {
349     if (!D->getTypeSourceInfo() ||
350         D->getTypeSourceInfo()->getTypeLoc().getBeginLoc() != SearchedLocation)
351       return true;
352 
353     if (auto *AT = D->getType()->getContainedAutoType()) {
354       if (!AT->getDeducedType().isNull())
355         DeducedType = AT->getDeducedType();
356     }
357     return true;
358   }
359 
360   // Handle auto return types:
361   //- auto foo() {}
362   //- auto& foo() {}
363   //- auto foo() -> int {}
364   //- auto foo() -> decltype(1+1) {}
365   //- operator auto() const { return 10; }
VisitFunctionDecl(FunctionDecl * D)366   bool VisitFunctionDecl(FunctionDecl *D) {
367     if (!D->getTypeSourceInfo())
368       return true;
369     // Loc of auto in return type (c++14).
370     auto CurLoc = D->getReturnTypeSourceRange().getBegin();
371     // Loc of "auto" in operator auto()
372     if (CurLoc.isInvalid() && dyn_cast<CXXConversionDecl>(D))
373       CurLoc = D->getTypeSourceInfo()->getTypeLoc().getBeginLoc();
374     // Loc of "auto" in function with trailing return type (c++11).
375     if (CurLoc.isInvalid())
376       CurLoc = D->getSourceRange().getBegin();
377     if (CurLoc != SearchedLocation)
378       return true;
379 
380     const AutoType *AT = D->getReturnType()->getContainedAutoType();
381     if (AT && !AT->getDeducedType().isNull()) {
382       DeducedType = AT->getDeducedType();
383     } else if (auto DT = dyn_cast<DecltypeType>(D->getReturnType())) {
384       // auto in a trailing return type just points to a DecltypeType and
385       // getContainedAutoType does not unwrap it.
386       if (!DT->getUnderlyingType().isNull())
387         DeducedType = DT->getUnderlyingType();
388     } else if (!D->getReturnType().isNull()) {
389       DeducedType = D->getReturnType();
390     }
391     return true;
392   }
393 
394   // Handle non-auto decltype, e.g.:
395   // - auto foo() -> decltype(expr) {}
396   // - decltype(expr);
VisitDecltypeTypeLoc(DecltypeTypeLoc TL)397   bool VisitDecltypeTypeLoc(DecltypeTypeLoc TL) {
398     if (TL.getBeginLoc() != SearchedLocation)
399       return true;
400 
401     // A DecltypeType's underlying type can be another DecltypeType! E.g.
402     //  int I = 0;
403     //  decltype(I) J = I;
404     //  decltype(J) K = J;
405     const DecltypeType *DT = dyn_cast<DecltypeType>(TL.getTypePtr());
406     while (DT && !DT->getUnderlyingType().isNull()) {
407       DeducedType = DT->getUnderlyingType();
408       DT = dyn_cast<DecltypeType>(DeducedType.getTypePtr());
409     }
410     return true;
411   }
412 
413   QualType DeducedType;
414 };
415 } // namespace
416 
getDeducedType(ASTContext & ASTCtx,SourceLocation Loc)417 llvm::Optional<QualType> getDeducedType(ASTContext &ASTCtx,
418                                         SourceLocation Loc) {
419   if (!Loc.isValid())
420     return {};
421   DeducedTypeVisitor V(Loc);
422   V.TraverseAST(ASTCtx);
423   if (V.DeducedType.isNull())
424     return llvm::None;
425   return V.DeducedType;
426 }
427 
getQualification(ASTContext & Context,const DeclContext * DestContext,SourceLocation InsertionPoint,const NamedDecl * ND)428 std::string getQualification(ASTContext &Context,
429                              const DeclContext *DestContext,
430                              SourceLocation InsertionPoint,
431                              const NamedDecl *ND) {
432   auto VisibleNamespaceDecls =
433       getUsingNamespaceDirectives(DestContext, InsertionPoint);
434   return getQualification(
435       Context, DestContext, ND->getDeclContext(),
436       [&](NestedNameSpecifier *NNS) {
437         if (NNS->getKind() != NestedNameSpecifier::Namespace)
438           return false;
439         const auto *CanonNSD = NNS->getAsNamespace()->getCanonicalDecl();
440         return llvm::any_of(VisibleNamespaceDecls,
441                             [CanonNSD](const NamespaceDecl *NSD) {
442                               return NSD->getCanonicalDecl() == CanonNSD;
443                             });
444       });
445 }
446 
getQualification(ASTContext & Context,const DeclContext * DestContext,const NamedDecl * ND,llvm::ArrayRef<std::string> VisibleNamespaces)447 std::string getQualification(ASTContext &Context,
448                              const DeclContext *DestContext,
449                              const NamedDecl *ND,
450                              llvm::ArrayRef<std::string> VisibleNamespaces) {
451   for (llvm::StringRef NS : VisibleNamespaces) {
452     assert(NS.endswith("::"));
453     (void)NS;
454   }
455   return getQualification(
456       Context, DestContext, ND->getDeclContext(),
457       [&](NestedNameSpecifier *NNS) {
458         return llvm::any_of(VisibleNamespaces, [&](llvm::StringRef Namespace) {
459           std::string NS;
460           llvm::raw_string_ostream OS(NS);
461           NNS->print(OS, Context.getPrintingPolicy());
462           return OS.str() == Namespace;
463         });
464       });
465 }
466 
hasUnstableLinkage(const Decl * D)467 bool hasUnstableLinkage(const Decl *D) {
468   // Linkage of a ValueDecl depends on the type.
469   // If that's not deduced yet, deducing it may change the linkage.
470   auto *VD = llvm::dyn_cast_or_null<ValueDecl>(D);
471   return VD && !VD->getType().isNull() && VD->getType()->isUndeducedType();
472 }
473 
474 } // namespace clangd
475 } // namespace clang
476