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